2 * INETPEER - A storage for permanent information about peers
4 * This source is covered by the GNU GPL, the same as all kernel sources.
6 * Authors: Andrey V. Savochkin <saw@msu.ru>
9 #include <linux/module.h>
10 #include <linux/types.h>
11 #include <linux/slab.h>
12 #include <linux/interrupt.h>
13 #include <linux/spinlock.h>
14 #include <linux/random.h>
15 #include <linux/timer.h>
16 #include <linux/time.h>
17 #include <linux/kernel.h>
19 #include <linux/net.h>
21 #include <net/inetpeer.h>
24 * Theory of operations.
25 * We keep one entry for each peer IP address. The nodes contains long-living
26 * information about the peer which doesn't depend on routes.
27 * At this moment this information consists only of ID field for the next
28 * outgoing IP packet. This field is incremented with each packet as encoded
29 * in inet_getid() function (include/net/inetpeer.h).
30 * At the moment of writing this notes identifier of IP packets is generated
31 * to be unpredictable using this code only for packets subjected
32 * (actually or potentially) to defragmentation. I.e. DF packets less than
33 * PMTU in size uses a constant ID and do not use this code (see
34 * ip_select_ident() in include/net/ip.h).
36 * Route cache entries hold references to our nodes.
37 * New cache entries get references via lookup by destination IP address in
38 * the avl tree. The reference is grabbed only when it's needed i.e. only
39 * when we try to output IP packet which needs an unpredictable ID (see
40 * __ip_select_ident() in net/ipv4/route.c).
41 * Nodes are removed only when reference counter goes to 0.
42 * When it's happened the node may be removed when a sufficient amount of
43 * time has been passed since its last use. The less-recently-used entry can
44 * also be removed if the pool is overloaded i.e. if the total amount of
45 * entries is greater-or-equal than the threshold.
47 * Node pool is organised as an AVL tree.
48 * Such an implementation has been chosen not just for fun. It's a way to
49 * prevent easy and efficient DoS attacks by creating hash collisions. A huge
50 * amount of long living nodes in a single hash slot would significantly delay
51 * lookups performed with disabled BHs.
53 * Serialisation issues.
54 * 1. Nodes may appear in the tree only with the pool lock held.
55 * 2. Nodes may disappear from the tree only with the pool lock held
56 * AND reference count being 0.
57 * 3. Nodes appears and disappears from unused node list only under
58 * "inet_peer_unused_lock".
59 * 4. Global variable peer_total is modified under the pool lock.
60 * 5. struct inet_peer fields modification:
61 * avl_left, avl_right, avl_parent, avl_height: pool lock
62 * unused: unused node list lock
63 * refcnt: atomically against modifications on other CPU;
64 * usually under some other lock to prevent node disappearing
65 * dtime: unused node list lock
66 * v4daddr: unchangeable
70 static struct kmem_cache
*peer_cachep __read_mostly
;
72 #define node_height(x) x->avl_height
74 #define peer_avl_empty ((struct inet_peer *)&peer_fake_node)
75 static const struct inet_peer peer_fake_node
= {
76 .avl_left
= peer_avl_empty
,
77 .avl_right
= peer_avl_empty
,
82 struct inet_peer
*root
;
86 .root
= peer_avl_empty
,
87 .lock
= __SPIN_LOCK_UNLOCKED(peers
.lock
),
90 #define PEER_MAXDEPTH 40 /* sufficient for about 2^27 nodes */
92 /* Exported for sysctl_net_ipv4. */
93 int inet_peer_threshold __read_mostly
= 65536 + 128; /* start to throw entries more
94 * aggressively at this stage */
95 int inet_peer_minttl __read_mostly
= 120 * HZ
; /* TTL under high load: 120 sec */
96 int inet_peer_maxttl __read_mostly
= 10 * 60 * HZ
; /* usual time to live: 10 min */
97 int inet_peer_gc_mintime __read_mostly
= 10 * HZ
;
98 int inet_peer_gc_maxtime __read_mostly
= 120 * HZ
;
101 struct list_head list
;
104 .list
= LIST_HEAD_INIT(unused_peers
.list
),
105 .lock
= __SPIN_LOCK_UNLOCKED(unused_peers
.lock
),
108 static void peer_check_expire(unsigned long dummy
);
109 static DEFINE_TIMER(peer_periodic_timer
, peer_check_expire
, 0, 0);
112 /* Called from ip_output.c:ip_init */
113 void __init
inet_initpeers(void)
117 /* Use the straight interface to information about memory. */
119 /* The values below were suggested by Alexey Kuznetsov
120 * <kuznet@ms2.inr.ac.ru>. I don't have any opinion about the values
123 if (si
.totalram
<= (32768*1024)/PAGE_SIZE
)
124 inet_peer_threshold
>>= 1; /* max pool size about 1MB on IA32 */
125 if (si
.totalram
<= (16384*1024)/PAGE_SIZE
)
126 inet_peer_threshold
>>= 1; /* about 512KB */
127 if (si
.totalram
<= (8192*1024)/PAGE_SIZE
)
128 inet_peer_threshold
>>= 2; /* about 128KB */
130 peer_cachep
= kmem_cache_create("inet_peer_cache",
131 sizeof(struct inet_peer
),
135 /* All the timers, started at system startup tend
136 to synchronize. Perturb it a bit.
138 peer_periodic_timer
.expires
= jiffies
139 + net_random() % inet_peer_gc_maxtime
140 + inet_peer_gc_maxtime
;
141 add_timer(&peer_periodic_timer
);
144 /* Called with or without local BH being disabled. */
145 static void unlink_from_unused(struct inet_peer
*p
)
147 if (!list_empty(&p
->unused
)) {
148 spin_lock_bh(&unused_peers
.lock
);
149 list_del_init(&p
->unused
);
150 spin_unlock_bh(&unused_peers
.lock
);
155 * Called with local BH disabled and the pool lock held.
157 #define lookup(_daddr, _stack) \
159 struct inet_peer *u, **v; \
162 *stackptr++ = &peers.root; \
163 for (u = peers.root; u != peer_avl_empty; ) { \
164 if (_daddr == u->v4daddr) \
166 if ((__force __u32)_daddr < (__force __u32)u->v4daddr) \
177 * Called with rcu_read_lock_bh()
178 * Because we hold no lock against a writer, its quite possible we fall
179 * in an endless loop.
180 * But every pointer we follow is guaranteed to be valid thanks to RCU.
181 * We exit from this function if number of links exceeds PEER_MAXDEPTH
183 static struct inet_peer
*lookup_rcu_bh(__be32 daddr
)
185 struct inet_peer
*u
= rcu_dereference_bh(peers
.root
);
188 while (u
!= peer_avl_empty
) {
189 if (daddr
== u
->v4daddr
) {
190 if (unlikely(!atomic_inc_not_zero(&u
->refcnt
)))
194 if ((__force __u32
)daddr
< (__force __u32
)u
->v4daddr
)
195 u
= rcu_dereference_bh(u
->avl_left
);
197 u
= rcu_dereference_bh(u
->avl_right
);
198 if (unlikely(++count
== PEER_MAXDEPTH
))
204 /* Called with local BH disabled and the pool lock held. */
205 #define lookup_rightempty(start) \
207 struct inet_peer *u, **v; \
208 *stackptr++ = &start->avl_left; \
209 v = &start->avl_left; \
210 for (u = *v; u->avl_right != peer_avl_empty; ) { \
218 /* Called with local BH disabled and the pool lock held.
219 * Variable names are the proof of operation correctness.
220 * Look into mm/map_avl.c for more detail description of the ideas.
222 static void peer_avl_rebalance(struct inet_peer
**stack
[],
223 struct inet_peer
***stackend
)
225 struct inet_peer
**nodep
, *node
, *l
, *r
;
228 while (stackend
> stack
) {
235 if (lh
> rh
+ 1) { /* l: RH+2 */
236 struct inet_peer
*ll
, *lr
, *lrl
, *lrr
;
240 lrh
= node_height(lr
);
241 if (lrh
<= node_height(ll
)) { /* ll: RH+1 */
242 node
->avl_left
= lr
; /* lr: RH or RH+1 */
243 node
->avl_right
= r
; /* r: RH */
244 node
->avl_height
= lrh
+ 1; /* RH+1 or RH+2 */
245 l
->avl_left
= ll
; /* ll: RH+1 */
246 l
->avl_right
= node
; /* node: RH+1 or RH+2 */
247 l
->avl_height
= node
->avl_height
+ 1;
249 } else { /* ll: RH, lr: RH+1 */
250 lrl
= lr
->avl_left
; /* lrl: RH or RH-1 */
251 lrr
= lr
->avl_right
; /* lrr: RH or RH-1 */
252 node
->avl_left
= lrr
; /* lrr: RH or RH-1 */
253 node
->avl_right
= r
; /* r: RH */
254 node
->avl_height
= rh
+ 1; /* node: RH+1 */
255 l
->avl_left
= ll
; /* ll: RH */
256 l
->avl_right
= lrl
; /* lrl: RH or RH-1 */
257 l
->avl_height
= rh
+ 1; /* l: RH+1 */
258 lr
->avl_left
= l
; /* l: RH+1 */
259 lr
->avl_right
= node
; /* node: RH+1 */
260 lr
->avl_height
= rh
+ 2;
263 } else if (rh
> lh
+ 1) { /* r: LH+2 */
264 struct inet_peer
*rr
, *rl
, *rlr
, *rll
;
268 rlh
= node_height(rl
);
269 if (rlh
<= node_height(rr
)) { /* rr: LH+1 */
270 node
->avl_right
= rl
; /* rl: LH or LH+1 */
271 node
->avl_left
= l
; /* l: LH */
272 node
->avl_height
= rlh
+ 1; /* LH+1 or LH+2 */
273 r
->avl_right
= rr
; /* rr: LH+1 */
274 r
->avl_left
= node
; /* node: LH+1 or LH+2 */
275 r
->avl_height
= node
->avl_height
+ 1;
277 } else { /* rr: RH, rl: RH+1 */
278 rlr
= rl
->avl_right
; /* rlr: LH or LH-1 */
279 rll
= rl
->avl_left
; /* rll: LH or LH-1 */
280 node
->avl_right
= rll
; /* rll: LH or LH-1 */
281 node
->avl_left
= l
; /* l: LH */
282 node
->avl_height
= lh
+ 1; /* node: LH+1 */
283 r
->avl_right
= rr
; /* rr: LH */
284 r
->avl_left
= rlr
; /* rlr: LH or LH-1 */
285 r
->avl_height
= lh
+ 1; /* r: LH+1 */
286 rl
->avl_right
= r
; /* r: LH+1 */
287 rl
->avl_left
= node
; /* node: LH+1 */
288 rl
->avl_height
= lh
+ 2;
292 node
->avl_height
= (lh
> rh
? lh
: rh
) + 1;
297 /* Called with local BH disabled and the pool lock held. */
298 #define link_to_pool(n) \
301 n->avl_left = peer_avl_empty; \
302 n->avl_right = peer_avl_empty; \
303 smp_wmb(); /* lockless readers can catch us now */ \
305 peer_avl_rebalance(stack, stackptr); \
308 static void inetpeer_free_rcu(struct rcu_head
*head
)
310 kmem_cache_free(peer_cachep
, container_of(head
, struct inet_peer
, rcu
));
313 /* May be called with local BH enabled. */
314 static void unlink_from_pool(struct inet_peer
*p
)
320 spin_lock_bh(&peers
.lock
);
321 /* Check the reference counter. It was artificially incremented by 1
322 * in cleanup() function to prevent sudden disappearing. If we can
323 * atomically (because of lockless readers) take this last reference,
324 * it's safe to remove the node and free it later.
326 if (atomic_cmpxchg(&p
->refcnt
, 1, 0) == 1) {
327 struct inet_peer
**stack
[PEER_MAXDEPTH
];
328 struct inet_peer
***stackptr
, ***delp
;
329 if (lookup(p
->v4daddr
, stack
) != p
)
331 delp
= stackptr
- 1; /* *delp[0] == p */
332 if (p
->avl_left
== peer_avl_empty
) {
333 *delp
[0] = p
->avl_right
;
336 /* look for a node to insert instead of p */
338 t
= lookup_rightempty(p
);
339 BUG_ON(*stackptr
[-1] != t
);
340 **--stackptr
= t
->avl_left
;
341 /* t is removed, t->v4daddr > x->v4daddr for any
342 * x in p->avl_left subtree.
343 * Put t in the old place of p. */
345 t
->avl_left
= p
->avl_left
;
346 t
->avl_right
= p
->avl_right
;
347 t
->avl_height
= p
->avl_height
;
348 BUG_ON(delp
[1] != &p
->avl_left
);
349 delp
[1] = &t
->avl_left
; /* was &p->avl_left */
351 peer_avl_rebalance(stack
, stackptr
);
355 spin_unlock_bh(&peers
.lock
);
358 call_rcu_bh(&p
->rcu
, inetpeer_free_rcu
);
360 /* The node is used again. Decrease the reference counter
361 * back. The loop "cleanup -> unlink_from_unused
362 * -> unlink_from_pool -> putpeer -> link_to_unused
363 * -> cleanup (for the same node)"
364 * doesn't really exist because the entry will have a
365 * recent deletion time and will not be cleaned again soon.
370 /* May be called with local BH enabled. */
371 static int cleanup_once(unsigned long ttl
)
373 struct inet_peer
*p
= NULL
;
375 /* Remove the first entry from the list of unused nodes. */
376 spin_lock_bh(&unused_peers
.lock
);
377 if (!list_empty(&unused_peers
.list
)) {
380 p
= list_first_entry(&unused_peers
.list
, struct inet_peer
, unused
);
381 delta
= (__u32
)jiffies
- p
->dtime
;
384 /* Do not prune fresh entries. */
385 spin_unlock_bh(&unused_peers
.lock
);
389 list_del_init(&p
->unused
);
391 /* Grab an extra reference to prevent node disappearing
392 * before unlink_from_pool() call. */
393 atomic_inc(&p
->refcnt
);
395 spin_unlock_bh(&unused_peers
.lock
);
398 /* It means that the total number of USED entries has
399 * grown over inet_peer_threshold. It shouldn't really
400 * happen because of entry limits in route cache. */
407 /* Called with or without local BH being disabled. */
408 struct inet_peer
*inet_getpeer(__be32 daddr
, int create
)
411 struct inet_peer
**stack
[PEER_MAXDEPTH
], ***stackptr
;
413 /* Look up for the address quickly, lockless.
414 * Because of a concurrent writer, we might not find an existing entry.
417 p
= lookup_rcu_bh(daddr
);
418 rcu_read_unlock_bh();
421 /* The existing node has been found.
422 * Remove the entry from unused list if it was there.
424 unlink_from_unused(p
);
428 /* retry an exact lookup, taking the lock before.
429 * At least, nodes should be hot in our cache.
431 spin_lock_bh(&peers
.lock
);
432 p
= lookup(daddr
, stack
);
433 if (p
!= peer_avl_empty
) {
434 atomic_inc(&p
->refcnt
);
435 spin_unlock_bh(&peers
.lock
);
436 /* Remove the entry from unused list if it was there. */
437 unlink_from_unused(p
);
440 p
= create
? kmem_cache_alloc(peer_cachep
, GFP_ATOMIC
) : NULL
;
443 atomic_set(&p
->refcnt
, 1);
444 atomic_set(&p
->rid
, 0);
445 atomic_set(&p
->ip_id_count
, secure_ip_id(daddr
));
447 INIT_LIST_HEAD(&p
->unused
);
454 spin_unlock_bh(&peers
.lock
);
456 if (peers
.total
>= inet_peer_threshold
)
457 /* Remove one less-recently-used entry. */
463 /* Called with local BH disabled. */
464 static void peer_check_expire(unsigned long dummy
)
466 unsigned long now
= jiffies
;
469 if (peers
.total
>= inet_peer_threshold
)
470 ttl
= inet_peer_minttl
;
472 ttl
= inet_peer_maxttl
473 - (inet_peer_maxttl
- inet_peer_minttl
) / HZ
*
474 peers
.total
/ inet_peer_threshold
* HZ
;
475 while (!cleanup_once(ttl
)) {
480 /* Trigger the timer after inet_peer_gc_mintime .. inet_peer_gc_maxtime
481 * interval depending on the total number of entries (more entries,
483 if (peers
.total
>= inet_peer_threshold
)
484 peer_periodic_timer
.expires
= jiffies
+ inet_peer_gc_mintime
;
486 peer_periodic_timer
.expires
= jiffies
487 + inet_peer_gc_maxtime
488 - (inet_peer_gc_maxtime
- inet_peer_gc_mintime
) / HZ
*
489 peers
.total
/ inet_peer_threshold
* HZ
;
490 add_timer(&peer_periodic_timer
);
493 void inet_putpeer(struct inet_peer
*p
)
497 if (atomic_dec_and_lock(&p
->refcnt
, &unused_peers
.lock
)) {
498 list_add_tail(&p
->unused
, &unused_peers
.list
);
499 p
->dtime
= (__u32
)jiffies
;
500 spin_unlock(&unused_peers
.lock
);