inetpeer.c 19.3 KB
Newer Older
Linus Torvalds's avatar
Linus Torvalds committed
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
/*
 *		INETPEER - A storage for permanent information about peers
 *
 *  This source is covered by the GNU GPL, the same as all kernel sources.
 *
 *  Authors:	Andrey V. Savochkin <saw@msu.ru>
 */

#include <linux/module.h>
#include <linux/types.h>
#include <linux/slab.h>
#include <linux/interrupt.h>
#include <linux/spinlock.h>
#include <linux/random.h>
#include <linux/timer.h>
#include <linux/time.h>
#include <linux/kernel.h>
#include <linux/mm.h>
#include <linux/net.h>
20
#include <net/ip.h>
Linus Torvalds's avatar
Linus Torvalds committed
21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
#include <net/inetpeer.h>

/*
 *  Theory of operations.
 *  We keep one entry for each peer IP address.  The nodes contains long-living
 *  information about the peer which doesn't depend on routes.
 *  At this moment this information consists only of ID field for the next
 *  outgoing IP packet.  This field is incremented with each packet as encoded
 *  in inet_getid() function (include/net/inetpeer.h).
 *  At the moment of writing this notes identifier of IP packets is generated
 *  to be unpredictable using this code only for packets subjected
 *  (actually or potentially) to defragmentation.  I.e. DF packets less than
 *  PMTU in size uses a constant ID and do not use this code (see
 *  ip_select_ident() in include/net/ip.h).
 *
 *  Route cache entries hold references to our nodes.
 *  New cache entries get references via lookup by destination IP address in
 *  the avl tree.  The reference is grabbed only when it's needed i.e. only
 *  when we try to output IP packet which needs an unpredictable ID (see
 *  __ip_select_ident() in net/ipv4/route.c).
 *  Nodes are removed only when reference counter goes to 0.
 *  When it's happened the node may be removed when a sufficient amount of
 *  time has been passed since its last use.  The less-recently-used entry can
 *  also be removed if the pool is overloaded i.e. if the total amount of
 *  entries is greater-or-equal than the threshold.
 *
 *  Node pool is organised as an AVL tree.
 *  Such an implementation has been chosen not just for fun.  It's a way to
 *  prevent easy and efficient DoS attacks by creating hash collisions.  A huge
 *  amount of long living nodes in a single hash slot would significantly delay
 *  lookups performed with disabled BHs.
 *
 *  Serialisation issues.
Eric Dumazet's avatar
Eric Dumazet committed
54 55
 *  1.  Nodes may appear in the tree only with the pool lock held.
 *  2.  Nodes may disappear from the tree only with the pool lock held
Linus Torvalds's avatar
Linus Torvalds committed
56 57 58 59 60 61
 *      AND reference count being 0.
 *  3.  Nodes appears and disappears from unused node list only under
 *      "inet_peer_unused_lock".
 *  4.  Global variable peer_total is modified under the pool lock.
 *  5.  struct inet_peer fields modification:
 *		avl_left, avl_right, avl_parent, avl_height: pool lock
62
 *		unused: unused node list lock
Linus Torvalds's avatar
Linus Torvalds committed
63 64 65
 *		refcnt: atomically against modifications on other CPU;
 *		   usually under some other lock to prevent node disappearing
 *		dtime: unused node list lock
66
 *		daddr: unchangeable
67
 *		ip_id_count: atomic value (no lock needed)
Linus Torvalds's avatar
Linus Torvalds committed
68 69
 */

70
static struct kmem_cache *peer_cachep __read_mostly;
Linus Torvalds's avatar
Linus Torvalds committed
71 72

#define node_height(x) x->avl_height
Eric Dumazet's avatar
Eric Dumazet committed
73 74

#define peer_avl_empty ((struct inet_peer *)&peer_fake_node)
Eric Dumazet's avatar
Eric Dumazet committed
75
#define peer_avl_empty_rcu ((struct inet_peer __rcu __force *)&peer_fake_node)
Eric Dumazet's avatar
Eric Dumazet committed
76
static const struct inet_peer peer_fake_node = {
Eric Dumazet's avatar
Eric Dumazet committed
77 78
	.avl_left	= peer_avl_empty_rcu,
	.avl_right	= peer_avl_empty_rcu,
Linus Torvalds's avatar
Linus Torvalds committed
79 80
	.avl_height	= 0
};
Eric Dumazet's avatar
Eric Dumazet committed
81

82
struct inet_peer_base {
Eric Dumazet's avatar
Eric Dumazet committed
83
	struct inet_peer __rcu *root;
Eric Dumazet's avatar
Eric Dumazet committed
84
	spinlock_t	lock;
Eric Dumazet's avatar
Eric Dumazet committed
85
	int		total;
86 87 88
};

static struct inet_peer_base v4_peers = {
Eric Dumazet's avatar
Eric Dumazet committed
89
	.root		= peer_avl_empty_rcu,
90
	.lock		= __SPIN_LOCK_UNLOCKED(v4_peers.lock),
Eric Dumazet's avatar
Eric Dumazet committed
91 92
	.total		= 0,
};
93 94 95 96 97 98 99

static struct inet_peer_base v6_peers = {
	.root		= peer_avl_empty_rcu,
	.lock		= __SPIN_LOCK_UNLOCKED(v6_peers.lock),
	.total		= 0,
};

Linus Torvalds's avatar
Linus Torvalds committed
100 101 102
#define PEER_MAXDEPTH 40 /* sufficient for about 2^27 nodes */

/* Exported for sysctl_net_ipv4.  */
Eric Dumazet's avatar
Eric Dumazet committed
103
int inet_peer_threshold __read_mostly = 65536 + 128;	/* start to throw entries more
Linus Torvalds's avatar
Linus Torvalds committed
104
					 * aggressively at this stage */
Eric Dumazet's avatar
Eric Dumazet committed
105 106 107 108
int inet_peer_minttl __read_mostly = 120 * HZ;	/* TTL under high load: 120 sec */
int inet_peer_maxttl __read_mostly = 10 * 60 * HZ;	/* usual time to live: 10 min */
int inet_peer_gc_mintime __read_mostly = 10 * HZ;
int inet_peer_gc_maxtime __read_mostly = 120 * HZ;
Linus Torvalds's avatar
Linus Torvalds committed
109

Eric Dumazet's avatar
Eric Dumazet committed
110 111 112 113 114 115 116
static struct {
	struct list_head	list;
	spinlock_t		lock;
} unused_peers = {
	.list			= LIST_HEAD_INIT(unused_peers.list),
	.lock			= __SPIN_LOCK_UNLOCKED(unused_peers.lock),
};
Linus Torvalds's avatar
Linus Torvalds committed
117 118

static void peer_check_expire(unsigned long dummy);
119
static DEFINE_TIMER(peer_periodic_timer, peer_check_expire, 0, 0);
Linus Torvalds's avatar
Linus Torvalds committed
120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141


/* Called from ip_output.c:ip_init  */
void __init inet_initpeers(void)
{
	struct sysinfo si;

	/* Use the straight interface to information about memory. */
	si_meminfo(&si);
	/* The values below were suggested by Alexey Kuznetsov
	 * <kuznet@ms2.inr.ac.ru>.  I don't have any opinion about the values
	 * myself.  --SAW
	 */
	if (si.totalram <= (32768*1024)/PAGE_SIZE)
		inet_peer_threshold >>= 1; /* max pool size about 1MB on IA32 */
	if (si.totalram <= (16384*1024)/PAGE_SIZE)
		inet_peer_threshold >>= 1; /* about 512KB */
	if (si.totalram <= (8192*1024)/PAGE_SIZE)
		inet_peer_threshold >>= 2; /* about 128KB */

	peer_cachep = kmem_cache_create("inet_peer_cache",
			sizeof(struct inet_peer),
142
			0, SLAB_HWCACHE_ALIGN | SLAB_PANIC,
143
			NULL);
Linus Torvalds's avatar
Linus Torvalds committed
144 145 146 147 148 149 150 151 152 153 154 155 156

	/* All the timers, started at system startup tend
	   to synchronize. Perturb it a bit.
	 */
	peer_periodic_timer.expires = jiffies
		+ net_random() % inet_peer_gc_maxtime
		+ inet_peer_gc_maxtime;
	add_timer(&peer_periodic_timer);
}

/* Called with or without local BH being disabled. */
static void unlink_from_unused(struct inet_peer *p)
{
Eric Dumazet's avatar
Eric Dumazet committed
157 158 159 160 161
	if (!list_empty(&p->unused)) {
		spin_lock_bh(&unused_peers.lock);
		list_del_init(&p->unused);
		spin_unlock_bh(&unused_peers.lock);
	}
Linus Torvalds's avatar
Linus Torvalds committed
162 163
}

164 165
static int addr_compare(const struct inetpeer_addr *a,
			const struct inetpeer_addr *b)
166 167 168 169
{
	int i, n = (a->family == AF_INET ? 1 : 4);

	for (i = 0; i < n; i++) {
170
		if (a->addr.a6[i] == b->addr.a6[i])
171
			continue;
172
		if (a->addr.a6[i] < b->addr.a6[i])
173 174 175 176 177 178 179
			return -1;
		return 1;
	}

	return 0;
}

Eric Dumazet's avatar
Eric Dumazet committed
180 181 182
/*
 * Called with local BH disabled and the pool lock held.
 */
183
#define lookup(_daddr, _stack, _base)				\
Linus Torvalds's avatar
Linus Torvalds committed
184
({								\
Eric Dumazet's avatar
Eric Dumazet committed
185 186
	struct inet_peer *u;					\
	struct inet_peer __rcu **v;				\
Eric Dumazet's avatar
Eric Dumazet committed
187 188
								\
	stackptr = _stack;					\
189 190 191
	*stackptr++ = &_base->root;				\
	for (u = rcu_dereference_protected(_base->root,		\
			lockdep_is_held(&_base->lock));		\
Eric Dumazet's avatar
Eric Dumazet committed
192
	     u != peer_avl_empty; ) {				\
193 194
		int cmp = addr_compare(_daddr, &u->daddr);	\
		if (cmp == 0)					\
Linus Torvalds's avatar
Linus Torvalds committed
195
			break;					\
196
		if (cmp == -1)					\
Linus Torvalds's avatar
Linus Torvalds committed
197 198 199
			v = &u->avl_left;			\
		else						\
			v = &u->avl_right;			\
Eric Dumazet's avatar
Eric Dumazet committed
200
		*stackptr++ = v;				\
Eric Dumazet's avatar
Eric Dumazet committed
201
		u = rcu_dereference_protected(*v,		\
202
			lockdep_is_held(&_base->lock));		\
Linus Torvalds's avatar
Linus Torvalds committed
203 204 205 206
	}							\
	u;							\
})

Eric Dumazet's avatar
Eric Dumazet committed
207 208 209 210 211 212 213
/*
 * Called with rcu_read_lock_bh()
 * Because we hold no lock against a writer, its quite possible we fall
 * in an endless loop.
 * But every pointer we follow is guaranteed to be valid thanks to RCU.
 * We exit from this function if number of links exceeds PEER_MAXDEPTH
 */
214
static struct inet_peer *lookup_rcu_bh(const struct inetpeer_addr *daddr,
215
				       struct inet_peer_base *base)
Eric Dumazet's avatar
Eric Dumazet committed
216
{
217
	struct inet_peer *u = rcu_dereference_bh(base->root);
Eric Dumazet's avatar
Eric Dumazet committed
218 219 220
	int count = 0;

	while (u != peer_avl_empty) {
221 222
		int cmp = addr_compare(daddr, &u->daddr);
		if (cmp == 0) {
223 224 225 226 227 228
			/* Before taking a reference, check if this entry was
			 * deleted, unlink_from_pool() sets refcnt=-1 to make
			 * distinction between an unused entry (refcnt=0) and
			 * a freed one.
			 */
			if (unlikely(!atomic_add_unless(&u->refcnt, 1, -1)))
Eric Dumazet's avatar
Eric Dumazet committed
229 230 231
				u = NULL;
			return u;
		}
232
		if (cmp == -1)
Eric Dumazet's avatar
Eric Dumazet committed
233 234 235 236 237 238 239 240 241 242
			u = rcu_dereference_bh(u->avl_left);
		else
			u = rcu_dereference_bh(u->avl_right);
		if (unlikely(++count == PEER_MAXDEPTH))
			break;
	}
	return NULL;
}

/* Called with local BH disabled and the pool lock held. */
243
#define lookup_rightempty(start, base)				\
Linus Torvalds's avatar
Linus Torvalds committed
244
({								\
Eric Dumazet's avatar
Eric Dumazet committed
245 246
	struct inet_peer *u;					\
	struct inet_peer __rcu **v;				\
Linus Torvalds's avatar
Linus Torvalds committed
247 248
	*stackptr++ = &start->avl_left;				\
	v = &start->avl_left;					\
Eric Dumazet's avatar
Eric Dumazet committed
249
	for (u = rcu_dereference_protected(*v,			\
250
			lockdep_is_held(&base->lock));		\
Eric Dumazet's avatar
Eric Dumazet committed
251
	     u->avl_right != peer_avl_empty_rcu; ) {		\
Linus Torvalds's avatar
Linus Torvalds committed
252 253
		v = &u->avl_right;				\
		*stackptr++ = v;				\
Eric Dumazet's avatar
Eric Dumazet committed
254
		u = rcu_dereference_protected(*v,		\
255
			lockdep_is_held(&base->lock));		\
Linus Torvalds's avatar
Linus Torvalds committed
256 257 258 259
	}							\
	u;							\
})

Eric Dumazet's avatar
Eric Dumazet committed
260
/* Called with local BH disabled and the pool lock held.
Linus Torvalds's avatar
Linus Torvalds committed
261
 * Variable names are the proof of operation correctness.
Eric Dumazet's avatar
Eric Dumazet committed
262 263
 * Look into mm/map_avl.c for more detail description of the ideas.
 */
Eric Dumazet's avatar
Eric Dumazet committed
264
static void peer_avl_rebalance(struct inet_peer __rcu **stack[],
265 266
			       struct inet_peer __rcu ***stackend,
			       struct inet_peer_base *base)
Linus Torvalds's avatar
Linus Torvalds committed
267
{
Eric Dumazet's avatar
Eric Dumazet committed
268 269
	struct inet_peer __rcu **nodep;
	struct inet_peer *node, *l, *r;
Linus Torvalds's avatar
Linus Torvalds committed
270 271 272 273
	int lh, rh;

	while (stackend > stack) {
		nodep = *--stackend;
Eric Dumazet's avatar
Eric Dumazet committed
274
		node = rcu_dereference_protected(*nodep,
275
				lockdep_is_held(&base->lock));
Eric Dumazet's avatar
Eric Dumazet committed
276
		l = rcu_dereference_protected(node->avl_left,
277
				lockdep_is_held(&base->lock));
Eric Dumazet's avatar
Eric Dumazet committed
278
		r = rcu_dereference_protected(node->avl_right,
279
				lockdep_is_held(&base->lock));
Linus Torvalds's avatar
Linus Torvalds committed
280 281 282 283 284
		lh = node_height(l);
		rh = node_height(r);
		if (lh > rh + 1) { /* l: RH+2 */
			struct inet_peer *ll, *lr, *lrl, *lrr;
			int lrh;
Eric Dumazet's avatar
Eric Dumazet committed
285
			ll = rcu_dereference_protected(l->avl_left,
286
				lockdep_is_held(&base->lock));
Eric Dumazet's avatar
Eric Dumazet committed
287
			lr = rcu_dereference_protected(l->avl_right,
288
				lockdep_is_held(&base->lock));
Linus Torvalds's avatar
Linus Torvalds committed
289 290
			lrh = node_height(lr);
			if (lrh <= node_height(ll)) {	/* ll: RH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
291 292
				RCU_INIT_POINTER(node->avl_left, lr);	/* lr: RH or RH+1 */
				RCU_INIT_POINTER(node->avl_right, r);	/* r: RH */
Linus Torvalds's avatar
Linus Torvalds committed
293
				node->avl_height = lrh + 1; /* RH+1 or RH+2 */
Eric Dumazet's avatar
Eric Dumazet committed
294 295
				RCU_INIT_POINTER(l->avl_left, ll);       /* ll: RH+1 */
				RCU_INIT_POINTER(l->avl_right, node);	/* node: RH+1 or RH+2 */
Linus Torvalds's avatar
Linus Torvalds committed
296
				l->avl_height = node->avl_height + 1;
Eric Dumazet's avatar
Eric Dumazet committed
297
				RCU_INIT_POINTER(*nodep, l);
Linus Torvalds's avatar
Linus Torvalds committed
298
			} else { /* ll: RH, lr: RH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
299
				lrl = rcu_dereference_protected(lr->avl_left,
300
					lockdep_is_held(&base->lock));	/* lrl: RH or RH-1 */
Eric Dumazet's avatar
Eric Dumazet committed
301
				lrr = rcu_dereference_protected(lr->avl_right,
302
					lockdep_is_held(&base->lock));	/* lrr: RH or RH-1 */
Eric Dumazet's avatar
Eric Dumazet committed
303 304
				RCU_INIT_POINTER(node->avl_left, lrr);	/* lrr: RH or RH-1 */
				RCU_INIT_POINTER(node->avl_right, r);	/* r: RH */
Linus Torvalds's avatar
Linus Torvalds committed
305
				node->avl_height = rh + 1; /* node: RH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
306 307
				RCU_INIT_POINTER(l->avl_left, ll);	/* ll: RH */
				RCU_INIT_POINTER(l->avl_right, lrl);	/* lrl: RH or RH-1 */
Linus Torvalds's avatar
Linus Torvalds committed
308
				l->avl_height = rh + 1;	/* l: RH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
309 310
				RCU_INIT_POINTER(lr->avl_left, l);	/* l: RH+1 */
				RCU_INIT_POINTER(lr->avl_right, node);	/* node: RH+1 */
Linus Torvalds's avatar
Linus Torvalds committed
311
				lr->avl_height = rh + 2;
Eric Dumazet's avatar
Eric Dumazet committed
312
				RCU_INIT_POINTER(*nodep, lr);
Linus Torvalds's avatar
Linus Torvalds committed
313 314 315 316
			}
		} else if (rh > lh + 1) { /* r: LH+2 */
			struct inet_peer *rr, *rl, *rlr, *rll;
			int rlh;
Eric Dumazet's avatar
Eric Dumazet committed
317
			rr = rcu_dereference_protected(r->avl_right,
318
				lockdep_is_held(&base->lock));
Eric Dumazet's avatar
Eric Dumazet committed
319
			rl = rcu_dereference_protected(r->avl_left,
320
				lockdep_is_held(&base->lock));
Linus Torvalds's avatar
Linus Torvalds committed
321 322
			rlh = node_height(rl);
			if (rlh <= node_height(rr)) {	/* rr: LH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
323 324
				RCU_INIT_POINTER(node->avl_right, rl);	/* rl: LH or LH+1 */
				RCU_INIT_POINTER(node->avl_left, l);	/* l: LH */
Linus Torvalds's avatar
Linus Torvalds committed
325
				node->avl_height = rlh + 1; /* LH+1 or LH+2 */
Eric Dumazet's avatar
Eric Dumazet committed
326 327
				RCU_INIT_POINTER(r->avl_right, rr);	/* rr: LH+1 */
				RCU_INIT_POINTER(r->avl_left, node);	/* node: LH+1 or LH+2 */
Linus Torvalds's avatar
Linus Torvalds committed
328
				r->avl_height = node->avl_height + 1;
Eric Dumazet's avatar
Eric Dumazet committed
329
				RCU_INIT_POINTER(*nodep, r);
Linus Torvalds's avatar
Linus Torvalds committed
330
			} else { /* rr: RH, rl: RH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
331
				rlr = rcu_dereference_protected(rl->avl_right,
332
					lockdep_is_held(&base->lock));	/* rlr: LH or LH-1 */
Eric Dumazet's avatar
Eric Dumazet committed
333
				rll = rcu_dereference_protected(rl->avl_left,
334
					lockdep_is_held(&base->lock));	/* rll: LH or LH-1 */
Eric Dumazet's avatar
Eric Dumazet committed
335 336
				RCU_INIT_POINTER(node->avl_right, rll);	/* rll: LH or LH-1 */
				RCU_INIT_POINTER(node->avl_left, l);	/* l: LH */
Linus Torvalds's avatar
Linus Torvalds committed
337
				node->avl_height = lh + 1; /* node: LH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
338 339
				RCU_INIT_POINTER(r->avl_right, rr);	/* rr: LH */
				RCU_INIT_POINTER(r->avl_left, rlr);	/* rlr: LH or LH-1 */
Linus Torvalds's avatar
Linus Torvalds committed
340
				r->avl_height = lh + 1;	/* r: LH+1 */
Eric Dumazet's avatar
Eric Dumazet committed
341 342
				RCU_INIT_POINTER(rl->avl_right, r);	/* r: LH+1 */
				RCU_INIT_POINTER(rl->avl_left, node);	/* node: LH+1 */
Linus Torvalds's avatar
Linus Torvalds committed
343
				rl->avl_height = lh + 2;
Eric Dumazet's avatar
Eric Dumazet committed
344
				RCU_INIT_POINTER(*nodep, rl);
Linus Torvalds's avatar
Linus Torvalds committed
345 346 347 348 349 350 351
			}
		} else {
			node->avl_height = (lh > rh ? lh : rh) + 1;
		}
	}
}

Eric Dumazet's avatar
Eric Dumazet committed
352
/* Called with local BH disabled and the pool lock held. */
353
#define link_to_pool(n, base)					\
Linus Torvalds's avatar
Linus Torvalds committed
354 355
do {								\
	n->avl_height = 1;					\
Eric Dumazet's avatar
Eric Dumazet committed
356 357 358 359
	n->avl_left = peer_avl_empty_rcu;			\
	n->avl_right = peer_avl_empty_rcu;			\
	/* lockless readers can catch us now */			\
	rcu_assign_pointer(**--stackptr, n);			\
360
	peer_avl_rebalance(stack, stackptr, base);		\
Eric Dumazet's avatar
Eric Dumazet committed
361
} while (0)
Linus Torvalds's avatar
Linus Torvalds committed
362

Eric Dumazet's avatar
Eric Dumazet committed
363 364 365 366 367
static void inetpeer_free_rcu(struct rcu_head *head)
{
	kmem_cache_free(peer_cachep, container_of(head, struct inet_peer, rcu));
}

Linus Torvalds's avatar
Linus Torvalds committed
368
/* May be called with local BH enabled. */
369
static void unlink_from_pool(struct inet_peer *p, struct inet_peer_base *base)
Linus Torvalds's avatar
Linus Torvalds committed
370 371 372 373 374
{
	int do_free;

	do_free = 0;

375
	spin_lock_bh(&base->lock);
Linus Torvalds's avatar
Linus Torvalds committed
376
	/* Check the reference counter.  It was artificially incremented by 1
Eric Dumazet's avatar
Eric Dumazet committed
377 378 379
	 * in cleanup() function to prevent sudden disappearing.  If we can
	 * atomically (because of lockless readers) take this last reference,
	 * it's safe to remove the node and free it later.
380
	 * We use refcnt=-1 to alert lockless readers this entry is deleted.
Eric Dumazet's avatar
Eric Dumazet committed
381
	 */
382
	if (atomic_cmpxchg(&p->refcnt, 1, -1) == 1) {
Eric Dumazet's avatar
Eric Dumazet committed
383 384
		struct inet_peer __rcu **stack[PEER_MAXDEPTH];
		struct inet_peer __rcu ***stackptr, ***delp;
385
		if (lookup(&p->daddr, stack, base) != p)
Linus Torvalds's avatar
Linus Torvalds committed
386 387
			BUG();
		delp = stackptr - 1; /* *delp[0] == p */
Eric Dumazet's avatar
Eric Dumazet committed
388
		if (p->avl_left == peer_avl_empty_rcu) {
Linus Torvalds's avatar
Linus Torvalds committed
389 390 391 392 393
			*delp[0] = p->avl_right;
			--stackptr;
		} else {
			/* look for a node to insert instead of p */
			struct inet_peer *t;
394
			t = lookup_rightempty(p, base);
Eric Dumazet's avatar
Eric Dumazet committed
395
			BUG_ON(rcu_dereference_protected(*stackptr[-1],
396
					lockdep_is_held(&base->lock)) != t);
Linus Torvalds's avatar
Linus Torvalds committed
397
			**--stackptr = t->avl_left;
398
			/* t is removed, t->daddr > x->daddr for any
Linus Torvalds's avatar
Linus Torvalds committed
399 400
			 * x in p->avl_left subtree.
			 * Put t in the old place of p. */
Eric Dumazet's avatar
Eric Dumazet committed
401
			RCU_INIT_POINTER(*delp[0], t);
Linus Torvalds's avatar
Linus Torvalds committed
402 403 404
			t->avl_left = p->avl_left;
			t->avl_right = p->avl_right;
			t->avl_height = p->avl_height;
405
			BUG_ON(delp[1] != &p->avl_left);
Linus Torvalds's avatar
Linus Torvalds committed
406 407
			delp[1] = &t->avl_left; /* was &p->avl_left */
		}
408 409
		peer_avl_rebalance(stack, stackptr, base);
		base->total--;
Linus Torvalds's avatar
Linus Torvalds committed
410 411
		do_free = 1;
	}
412
	spin_unlock_bh(&base->lock);
Linus Torvalds's avatar
Linus Torvalds committed
413 414

	if (do_free)
Eric Dumazet's avatar
Eric Dumazet committed
415
		call_rcu_bh(&p->rcu, inetpeer_free_rcu);
Linus Torvalds's avatar
Linus Torvalds committed
416 417 418 419 420 421
	else
		/* The node is used again.  Decrease the reference counter
		 * back.  The loop "cleanup -> unlink_from_unused
		 *   -> unlink_from_pool -> putpeer -> link_to_unused
		 *   -> cleanup (for the same node)"
		 * doesn't really exist because the entry will have a
Eric Dumazet's avatar
Eric Dumazet committed
422 423
		 * recent deletion time and will not be cleaned again soon.
		 */
Linus Torvalds's avatar
Linus Torvalds committed
424 425 426
		inet_putpeer(p);
}

427 428 429 430 431
static struct inet_peer_base *family_to_base(int family)
{
	return (family == AF_INET ? &v4_peers : &v6_peers);
}

432 433
static struct inet_peer_base *peer_to_base(struct inet_peer *p)
{
434
	return family_to_base(p->daddr.family);
435 436
}

Linus Torvalds's avatar
Linus Torvalds committed
437 438 439
/* May be called with local BH enabled. */
static int cleanup_once(unsigned long ttl)
{
440
	struct inet_peer *p = NULL;
Linus Torvalds's avatar
Linus Torvalds committed
441 442

	/* Remove the first entry from the list of unused nodes. */
Eric Dumazet's avatar
Eric Dumazet committed
443 444
	spin_lock_bh(&unused_peers.lock);
	if (!list_empty(&unused_peers.list)) {
445 446
		__u32 delta;

Eric Dumazet's avatar
Eric Dumazet committed
447
		p = list_first_entry(&unused_peers.list, struct inet_peer, unused);
448 449
		delta = (__u32)jiffies - p->dtime;

450
		if (delta < ttl) {
Linus Torvalds's avatar
Linus Torvalds committed
451
			/* Do not prune fresh entries. */
Eric Dumazet's avatar
Eric Dumazet committed
452
			spin_unlock_bh(&unused_peers.lock);
Linus Torvalds's avatar
Linus Torvalds committed
453 454
			return -1;
		}
455 456 457

		list_del_init(&p->unused);

Linus Torvalds's avatar
Linus Torvalds committed
458 459 460 461
		/* Grab an extra reference to prevent node disappearing
		 * before unlink_from_pool() call. */
		atomic_inc(&p->refcnt);
	}
Eric Dumazet's avatar
Eric Dumazet committed
462
	spin_unlock_bh(&unused_peers.lock);
Linus Torvalds's avatar
Linus Torvalds committed
463 464 465 466 467 468 469

	if (p == NULL)
		/* It means that the total number of USED entries has
		 * grown over inet_peer_threshold.  It shouldn't really
		 * happen because of entry limits in route cache. */
		return -1;

470
	unlink_from_pool(p, peer_to_base(p));
Linus Torvalds's avatar
Linus Torvalds committed
471 472 473 474
	return 0;
}

/* Called with or without local BH being disabled. */
475
struct inet_peer *inet_getpeer(struct inetpeer_addr *daddr, int create)
Linus Torvalds's avatar
Linus Torvalds committed
476
{
Eric Dumazet's avatar
Eric Dumazet committed
477
	struct inet_peer __rcu **stack[PEER_MAXDEPTH], ***stackptr;
478
	struct inet_peer_base *base = family_to_base(daddr->family);
479
	struct inet_peer *p;
Linus Torvalds's avatar
Linus Torvalds committed
480

Eric Dumazet's avatar
Eric Dumazet committed
481 482 483 484
	/* Look up for the address quickly, lockless.
	 * Because of a concurrent writer, we might not find an existing entry.
	 */
	rcu_read_lock_bh();
485
	p = lookup_rcu_bh(daddr, base);
Eric Dumazet's avatar
Eric Dumazet committed
486 487 488 489 490 491 492 493 494
	rcu_read_unlock_bh();

	if (p) {
		/* The existing node has been found.
		 * Remove the entry from unused list if it was there.
		 */
		unlink_from_unused(p);
		return p;
	}
Linus Torvalds's avatar
Linus Torvalds committed
495

Eric Dumazet's avatar
Eric Dumazet committed
496 497 498
	/* retry an exact lookup, taking the lock before.
	 * At least, nodes should be hot in our cache.
	 */
499
	spin_lock_bh(&base->lock);
500
	p = lookup(daddr, stack, base);
Linus Torvalds's avatar
Linus Torvalds committed
501
	if (p != peer_avl_empty) {
Eric Dumazet's avatar
Eric Dumazet committed
502
		atomic_inc(&p->refcnt);
503
		spin_unlock_bh(&base->lock);
Linus Torvalds's avatar
Linus Torvalds committed
504 505 506 507
		/* Remove the entry from unused list if it was there. */
		unlink_from_unused(p);
		return p;
	}
Eric Dumazet's avatar
Eric Dumazet committed
508 509
	p = create ? kmem_cache_alloc(peer_cachep, GFP_ATOMIC) : NULL;
	if (p) {
510
		p->daddr = *daddr;
Eric Dumazet's avatar
Eric Dumazet committed
511 512
		atomic_set(&p->refcnt, 1);
		atomic_set(&p->rid, 0);
513
		atomic_set(&p->ip_id_count, secure_ip_id(daddr->addr.a4));
Eric Dumazet's avatar
Eric Dumazet committed
514
		p->tcp_ts_stamp = 0;
515
		p->metrics[RTAX_LOCK-1] = INETPEER_METRICS_NEW;
516 517
		p->rate_tokens = 0;
		p->rate_last = 0;
518 519
		p->pmtu_expires = 0;
		memset(&p->redirect_learned, 0, sizeof(p->redirect_learned));
Eric Dumazet's avatar
Eric Dumazet committed
520 521 522 523
		INIT_LIST_HEAD(&p->unused);


		/* Link the node. */
524 525
		link_to_pool(p, base);
		base->total++;
Eric Dumazet's avatar
Eric Dumazet committed
526
	}
527
	spin_unlock_bh(&base->lock);
Linus Torvalds's avatar
Linus Torvalds committed
528

529
	if (base->total >= inet_peer_threshold)
Linus Torvalds's avatar
Linus Torvalds committed
530 531 532 533 534 535
		/* Remove one less-recently-used entry. */
		cleanup_once(0);

	return p;
}

536 537
static int compute_total(void)
{
538
	return v4_peers.total + v6_peers.total;
539
}
540
EXPORT_SYMBOL_GPL(inet_getpeer);
541

Linus Torvalds's avatar
Linus Torvalds committed
542 543 544
/* Called with local BH disabled. */
static void peer_check_expire(unsigned long dummy)
{
545
	unsigned long now = jiffies;
546
	int ttl, total;
Linus Torvalds's avatar
Linus Torvalds committed
547

548 549
	total = compute_total();
	if (total >= inet_peer_threshold)
Linus Torvalds's avatar
Linus Torvalds committed
550 551 552 553
		ttl = inet_peer_minttl;
	else
		ttl = inet_peer_maxttl
				- (inet_peer_maxttl - inet_peer_minttl) / HZ *
554
					total / inet_peer_threshold * HZ;
555 556 557 558
	while (!cleanup_once(ttl)) {
		if (jiffies != now)
			break;
	}
Linus Torvalds's avatar
Linus Torvalds committed
559 560 561 562

	/* Trigger the timer after inet_peer_gc_mintime .. inet_peer_gc_maxtime
	 * interval depending on the total number of entries (more entries,
	 * less interval). */
563 564
	total = compute_total();
	if (total >= inet_peer_threshold)
565 566 567 568 569
		peer_periodic_timer.expires = jiffies + inet_peer_gc_mintime;
	else
		peer_periodic_timer.expires = jiffies
			+ inet_peer_gc_maxtime
			- (inet_peer_gc_maxtime - inet_peer_gc_mintime) / HZ *
570
				total / inet_peer_threshold * HZ;
Linus Torvalds's avatar
Linus Torvalds committed
571 572
	add_timer(&peer_periodic_timer);
}
573 574 575

void inet_putpeer(struct inet_peer *p)
{
Eric Dumazet's avatar
Eric Dumazet committed
576 577 578 579
	local_bh_disable();

	if (atomic_dec_and_lock(&p->refcnt, &unused_peers.lock)) {
		list_add_tail(&p->unused, &unused_peers.list);
580
		p->dtime = (__u32)jiffies;
Eric Dumazet's avatar
Eric Dumazet committed
581
		spin_unlock(&unused_peers.lock);
582
	}
Eric Dumazet's avatar
Eric Dumazet committed
583 584

	local_bh_enable();
585
}
586
EXPORT_SYMBOL_GPL(inet_putpeer);
587 588 589 590 591 592 593 594 595 596 597 598 599 600 601 602 603 604 605 606 607 608 609 610 611 612 613 614 615 616 617 618 619 620 621 622 623 624 625 626 627

/*
 *	Check transmit rate limitation for given message.
 *	The rate information is held in the inet_peer entries now.
 *	This function is generic and could be used for other purposes
 *	too. It uses a Token bucket filter as suggested by Alexey Kuznetsov.
 *
 *	Note that the same inet_peer fields are modified by functions in
 *	route.c too, but these work for packet destinations while xrlim_allow
 *	works for icmp destinations. This means the rate limiting information
 *	for one "ip object" is shared - and these ICMPs are twice limited:
 *	by source and by destination.
 *
 *	RFC 1812: 4.3.2.8 SHOULD be able to limit error message rate
 *			  SHOULD allow setting of rate limits
 *
 * 	Shared between ICMPv4 and ICMPv6.
 */
#define XRLIM_BURST_FACTOR 6
bool inet_peer_xrlim_allow(struct inet_peer *peer, int timeout)
{
	unsigned long now, token;
	bool rc = false;

	if (!peer)
		return true;

	token = peer->rate_tokens;
	now = jiffies;
	token += now - peer->rate_last;
	peer->rate_last = now;
	if (token > XRLIM_BURST_FACTOR * timeout)
		token = XRLIM_BURST_FACTOR * timeout;
	if (token >= timeout) {
		token -= timeout;
		rc = true;
	}
	peer->rate_tokens = token;
	return rc;
}
EXPORT_SYMBOL(inet_peer_xrlim_allow);