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 write lock held.
55 * 2. Nodes may disappear from the tree only with the pool write 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
= __RW_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
),
132 0, SLAB_HWCACHE_ALIGN
|SLAB_PANIC
,
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.
156 * _stack is known to be NULL or not at compile time,
157 * so compiler will optimize the if (_stack) tests.
159 #define lookup(_daddr, _stack) \
161 struct inet_peer *u, **v; \
162 if (_stack != NULL) { \
164 *stackptr++ = &peers.root; \
166 for (u = peers.root; u != peer_avl_empty; ) { \
167 if (_daddr == u->v4daddr) \
169 if ((__force __u32)_daddr < (__force __u32)u->v4daddr) \
173 if (_stack != NULL) \
180 /* Called with local BH disabled and the pool write lock held. */
181 #define lookup_rightempty(start) \
183 struct inet_peer *u, **v; \
184 *stackptr++ = &start->avl_left; \
185 v = &start->avl_left; \
186 for (u = *v; u->avl_right != peer_avl_empty; ) { \
194 /* Called with local BH disabled and the pool write lock held.
195 * Variable names are the proof of operation correctness.
196 * Look into mm/map_avl.c for more detail description of the ideas. */
197 static void peer_avl_rebalance(struct inet_peer
**stack
[],
198 struct inet_peer
***stackend
)
200 struct inet_peer
**nodep
, *node
, *l
, *r
;
203 while (stackend
> stack
) {
210 if (lh
> rh
+ 1) { /* l: RH+2 */
211 struct inet_peer
*ll
, *lr
, *lrl
, *lrr
;
215 lrh
= node_height(lr
);
216 if (lrh
<= node_height(ll
)) { /* ll: RH+1 */
217 node
->avl_left
= lr
; /* lr: RH or RH+1 */
218 node
->avl_right
= r
; /* r: RH */
219 node
->avl_height
= lrh
+ 1; /* RH+1 or RH+2 */
220 l
->avl_left
= ll
; /* ll: RH+1 */
221 l
->avl_right
= node
; /* node: RH+1 or RH+2 */
222 l
->avl_height
= node
->avl_height
+ 1;
224 } else { /* ll: RH, lr: RH+1 */
225 lrl
= lr
->avl_left
; /* lrl: RH or RH-1 */
226 lrr
= lr
->avl_right
; /* lrr: RH or RH-1 */
227 node
->avl_left
= lrr
; /* lrr: RH or RH-1 */
228 node
->avl_right
= r
; /* r: RH */
229 node
->avl_height
= rh
+ 1; /* node: RH+1 */
230 l
->avl_left
= ll
; /* ll: RH */
231 l
->avl_right
= lrl
; /* lrl: RH or RH-1 */
232 l
->avl_height
= rh
+ 1; /* l: RH+1 */
233 lr
->avl_left
= l
; /* l: RH+1 */
234 lr
->avl_right
= node
; /* node: RH+1 */
235 lr
->avl_height
= rh
+ 2;
238 } else if (rh
> lh
+ 1) { /* r: LH+2 */
239 struct inet_peer
*rr
, *rl
, *rlr
, *rll
;
243 rlh
= node_height(rl
);
244 if (rlh
<= node_height(rr
)) { /* rr: LH+1 */
245 node
->avl_right
= rl
; /* rl: LH or LH+1 */
246 node
->avl_left
= l
; /* l: LH */
247 node
->avl_height
= rlh
+ 1; /* LH+1 or LH+2 */
248 r
->avl_right
= rr
; /* rr: LH+1 */
249 r
->avl_left
= node
; /* node: LH+1 or LH+2 */
250 r
->avl_height
= node
->avl_height
+ 1;
252 } else { /* rr: RH, rl: RH+1 */
253 rlr
= rl
->avl_right
; /* rlr: LH or LH-1 */
254 rll
= rl
->avl_left
; /* rll: LH or LH-1 */
255 node
->avl_right
= rll
; /* rll: LH or LH-1 */
256 node
->avl_left
= l
; /* l: LH */
257 node
->avl_height
= lh
+ 1; /* node: LH+1 */
258 r
->avl_right
= rr
; /* rr: LH */
259 r
->avl_left
= rlr
; /* rlr: LH or LH-1 */
260 r
->avl_height
= lh
+ 1; /* r: LH+1 */
261 rl
->avl_right
= r
; /* r: LH+1 */
262 rl
->avl_left
= node
; /* node: LH+1 */
263 rl
->avl_height
= lh
+ 2;
267 node
->avl_height
= (lh
> rh
? lh
: rh
) + 1;
272 /* Called with local BH disabled and the pool write lock held. */
273 #define link_to_pool(n) \
276 n->avl_left = peer_avl_empty; \
277 n->avl_right = peer_avl_empty; \
279 peer_avl_rebalance(stack, stackptr); \
282 /* May be called with local BH enabled. */
283 static void unlink_from_pool(struct inet_peer
*p
)
289 write_lock_bh(&peers
.lock
);
290 /* Check the reference counter. It was artificially incremented by 1
291 * in cleanup() function to prevent sudden disappearing. If the
292 * reference count is still 1 then the node is referenced only as `p'
293 * here and from the pool. So under the exclusive pool lock it's safe
294 * to remove the node and free it later. */
295 if (atomic_read(&p
->refcnt
) == 1) {
296 struct inet_peer
**stack
[PEER_MAXDEPTH
];
297 struct inet_peer
***stackptr
, ***delp
;
298 if (lookup(p
->v4daddr
, stack
) != p
)
300 delp
= stackptr
- 1; /* *delp[0] == p */
301 if (p
->avl_left
== peer_avl_empty
) {
302 *delp
[0] = p
->avl_right
;
305 /* look for a node to insert instead of p */
307 t
= lookup_rightempty(p
);
308 BUG_ON(*stackptr
[-1] != t
);
309 **--stackptr
= t
->avl_left
;
310 /* t is removed, t->v4daddr > x->v4daddr for any
311 * x in p->avl_left subtree.
312 * Put t in the old place of p. */
314 t
->avl_left
= p
->avl_left
;
315 t
->avl_right
= p
->avl_right
;
316 t
->avl_height
= p
->avl_height
;
317 BUG_ON(delp
[1] != &p
->avl_left
);
318 delp
[1] = &t
->avl_left
; /* was &p->avl_left */
320 peer_avl_rebalance(stack
, stackptr
);
324 write_unlock_bh(&peers
.lock
);
327 kmem_cache_free(peer_cachep
, p
);
329 /* The node is used again. Decrease the reference counter
330 * back. The loop "cleanup -> unlink_from_unused
331 * -> unlink_from_pool -> putpeer -> link_to_unused
332 * -> cleanup (for the same node)"
333 * doesn't really exist because the entry will have a
334 * recent deletion time and will not be cleaned again soon. */
338 /* May be called with local BH enabled. */
339 static int cleanup_once(unsigned long ttl
)
341 struct inet_peer
*p
= NULL
;
343 /* Remove the first entry from the list of unused nodes. */
344 spin_lock_bh(&unused_peers
.lock
);
345 if (!list_empty(&unused_peers
.list
)) {
348 p
= list_first_entry(&unused_peers
.list
, struct inet_peer
, unused
);
349 delta
= (__u32
)jiffies
- p
->dtime
;
352 /* Do not prune fresh entries. */
353 spin_unlock_bh(&unused_peers
.lock
);
357 list_del_init(&p
->unused
);
359 /* Grab an extra reference to prevent node disappearing
360 * before unlink_from_pool() call. */
361 atomic_inc(&p
->refcnt
);
363 spin_unlock_bh(&unused_peers
.lock
);
366 /* It means that the total number of USED entries has
367 * grown over inet_peer_threshold. It shouldn't really
368 * happen because of entry limits in route cache. */
375 /* Called with or without local BH being disabled. */
376 struct inet_peer
*inet_getpeer(__be32 daddr
, int create
)
378 struct inet_peer
*p
, *n
;
379 struct inet_peer
**stack
[PEER_MAXDEPTH
], ***stackptr
;
381 /* Look up for the address quickly. */
382 read_lock_bh(&peers
.lock
);
383 p
= lookup(daddr
, NULL
);
384 if (p
!= peer_avl_empty
)
385 atomic_inc(&p
->refcnt
);
386 read_unlock_bh(&peers
.lock
);
388 if (p
!= peer_avl_empty
) {
389 /* The existing node has been found. */
390 /* Remove the entry from unused list if it was there. */
391 unlink_from_unused(p
);
398 /* Allocate the space outside the locked region. */
399 n
= kmem_cache_alloc(peer_cachep
, GFP_ATOMIC
);
403 atomic_set(&n
->refcnt
, 1);
404 atomic_set(&n
->rid
, 0);
405 atomic_set(&n
->ip_id_count
, secure_ip_id(daddr
));
408 write_lock_bh(&peers
.lock
);
409 /* Check if an entry has suddenly appeared. */
410 p
= lookup(daddr
, stack
);
411 if (p
!= peer_avl_empty
)
416 INIT_LIST_HEAD(&n
->unused
);
418 write_unlock_bh(&peers
.lock
);
420 if (peers
.total
>= inet_peer_threshold
)
421 /* Remove one less-recently-used entry. */
427 /* The appropriate node is already in the pool. */
428 atomic_inc(&p
->refcnt
);
429 write_unlock_bh(&peers
.lock
);
430 /* Remove the entry from unused list if it was there. */
431 unlink_from_unused(p
);
432 /* Free preallocated the preallocated node. */
433 kmem_cache_free(peer_cachep
, n
);
437 /* Called with local BH disabled. */
438 static void peer_check_expire(unsigned long dummy
)
440 unsigned long now
= jiffies
;
443 if (peers
.total
>= inet_peer_threshold
)
444 ttl
= inet_peer_minttl
;
446 ttl
= inet_peer_maxttl
447 - (inet_peer_maxttl
- inet_peer_minttl
) / HZ
*
448 peers
.total
/ inet_peer_threshold
* HZ
;
449 while (!cleanup_once(ttl
)) {
454 /* Trigger the timer after inet_peer_gc_mintime .. inet_peer_gc_maxtime
455 * interval depending on the total number of entries (more entries,
457 if (peers
.total
>= inet_peer_threshold
)
458 peer_periodic_timer
.expires
= jiffies
+ inet_peer_gc_mintime
;
460 peer_periodic_timer
.expires
= jiffies
461 + inet_peer_gc_maxtime
462 - (inet_peer_gc_maxtime
- inet_peer_gc_mintime
) / HZ
*
463 peers
.total
/ inet_peer_threshold
* HZ
;
464 add_timer(&peer_periodic_timer
);
467 void inet_putpeer(struct inet_peer
*p
)
471 if (atomic_dec_and_lock(&p
->refcnt
, &unused_peers
.lock
)) {
472 list_add_tail(&p
->unused
, &unused_peers
.list
);
473 p
->dtime
= (__u32
)jiffies
;
474 spin_unlock(&unused_peers
.lock
);