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 * Version: $Id: inetpeer.c,v 1.7 2001/09/20 21:22:50 davem Exp $
8 * Authors: Andrey V. Savochkin <saw@msu.ru>
11 #include <linux/module.h>
12 #include <linux/types.h>
13 #include <linux/slab.h>
14 #include <linux/interrupt.h>
15 #include <linux/spinlock.h>
16 #include <linux/random.h>
17 #include <linux/sched.h>
18 #include <linux/timer.h>
19 #include <linux/time.h>
20 #include <linux/kernel.h>
22 #include <linux/net.h>
24 #include <net/inetpeer.h>
27 * Theory of operations.
28 * We keep one entry for each peer IP address. The nodes contains long-living
29 * information about the peer which doesn't depend on routes.
30 * At this moment this information consists only of ID field for the next
31 * outgoing IP packet. This field is incremented with each packet as encoded
32 * in inet_getid() function (include/net/inetpeer.h).
33 * At the moment of writing this notes identifier of IP packets is generated
34 * to be unpredictable using this code only for packets subjected
35 * (actually or potentially) to defragmentation. I.e. DF packets less than
36 * PMTU in size uses a constant ID and do not use this code (see
37 * ip_select_ident() in include/net/ip.h).
39 * Route cache entries hold references to our nodes.
40 * New cache entries get references via lookup by destination IP address in
41 * the avl tree. The reference is grabbed only when it's needed i.e. only
42 * when we try to output IP packet which needs an unpredictable ID (see
43 * __ip_select_ident() in net/ipv4/route.c).
44 * Nodes are removed only when reference counter goes to 0.
45 * When it's happened the node may be removed when a sufficient amount of
46 * time has been passed since its last use. The less-recently-used entry can
47 * also be removed if the pool is overloaded i.e. if the total amount of
48 * entries is greater-or-equal than the threshold.
50 * Node pool is organised as an AVL tree.
51 * Such an implementation has been chosen not just for fun. It's a way to
52 * prevent easy and efficient DoS attacks by creating hash collisions. A huge
53 * amount of long living nodes in a single hash slot would significantly delay
54 * lookups performed with disabled BHs.
56 * Serialisation issues.
57 * 1. Nodes may appear in the tree only with the pool write lock held.
58 * 2. Nodes may disappear from the tree only with the pool write lock held
59 * AND reference count being 0.
60 * 3. Nodes appears and disappears from unused node list only under
61 * "inet_peer_unused_lock".
62 * 4. Global variable peer_total is modified under the pool lock.
63 * 5. struct inet_peer fields modification:
64 * avl_left, avl_right, avl_parent, avl_height: pool lock
65 * unused_next, unused_prevp: unused node list lock
66 * refcnt: atomically against modifications on other CPU;
67 * usually under some other lock to prevent node disappearing
68 * dtime: unused node list lock
69 * v4daddr: unchangeable
73 /* Exported for inet_getid inline function. */
74 DEFINE_SPINLOCK(inet_peer_idlock
);
76 static kmem_cache_t
*peer_cachep __read_mostly
;
78 #define node_height(x) x->avl_height
79 static struct inet_peer peer_fake_node
= {
80 .avl_left
= &peer_fake_node
,
81 .avl_right
= &peer_fake_node
,
84 #define peer_avl_empty (&peer_fake_node)
85 static struct inet_peer
*peer_root
= peer_avl_empty
;
86 static DEFINE_RWLOCK(peer_pool_lock
);
87 #define PEER_MAXDEPTH 40 /* sufficient for about 2^27 nodes */
89 static int peer_total
;
90 /* Exported for sysctl_net_ipv4. */
91 int inet_peer_threshold
= 65536 + 128; /* start to throw entries more
92 * aggressively at this stage */
93 int inet_peer_minttl
= 120 * HZ
; /* TTL under high load: 120 sec */
94 int inet_peer_maxttl
= 10 * 60 * HZ
; /* usual time to live: 10 min */
96 static struct inet_peer
*inet_peer_unused_head
;
97 /* Exported for inet_putpeer inline function. */
98 struct inet_peer
**inet_peer_unused_tailp
= &inet_peer_unused_head
;
99 DEFINE_SPINLOCK(inet_peer_unused_lock
);
100 #define PEER_MAX_CLEANUP_WORK 30
102 static void peer_check_expire(unsigned long dummy
);
103 static DEFINE_TIMER(peer_periodic_timer
, peer_check_expire
, 0, 0);
105 /* Exported for sysctl_net_ipv4. */
106 int inet_peer_gc_mintime
= 10 * HZ
,
107 inet_peer_gc_maxtime
= 120 * HZ
;
109 /* Called from ip_output.c:ip_init */
110 void __init
inet_initpeers(void)
114 /* Use the straight interface to information about memory. */
116 /* The values below were suggested by Alexey Kuznetsov
117 * <kuznet@ms2.inr.ac.ru>. I don't have any opinion about the values
120 if (si
.totalram
<= (32768*1024)/PAGE_SIZE
)
121 inet_peer_threshold
>>= 1; /* max pool size about 1MB on IA32 */
122 if (si
.totalram
<= (16384*1024)/PAGE_SIZE
)
123 inet_peer_threshold
>>= 1; /* about 512KB */
124 if (si
.totalram
<= (8192*1024)/PAGE_SIZE
)
125 inet_peer_threshold
>>= 2; /* about 128KB */
127 peer_cachep
= kmem_cache_create("inet_peer_cache",
128 sizeof(struct inet_peer
),
129 0, SLAB_HWCACHE_ALIGN
|SLAB_PANIC
,
132 /* All the timers, started at system startup tend
133 to synchronize. Perturb it a bit.
135 peer_periodic_timer
.expires
= jiffies
136 + net_random() % inet_peer_gc_maxtime
137 + inet_peer_gc_maxtime
;
138 add_timer(&peer_periodic_timer
);
141 /* Called with or without local BH being disabled. */
142 static void unlink_from_unused(struct inet_peer
*p
)
144 spin_lock_bh(&inet_peer_unused_lock
);
145 if (p
->unused_prevp
!= NULL
) {
146 /* On unused list. */
147 *p
->unused_prevp
= p
->unused_next
;
148 if (p
->unused_next
!= NULL
)
149 p
->unused_next
->unused_prevp
= p
->unused_prevp
;
151 inet_peer_unused_tailp
= p
->unused_prevp
;
152 p
->unused_prevp
= NULL
; /* mark it as removed */
154 spin_unlock_bh(&inet_peer_unused_lock
);
157 /* Called with local BH disabled and the pool lock held. */
158 #define lookup(daddr) \
160 struct inet_peer *u, **v; \
162 *stackptr++ = &peer_root; \
163 for (u = peer_root; u != peer_avl_empty; ) { \
164 if (daddr == u->v4daddr) \
166 if ((__force __u32)daddr < (__force __u32)u->v4daddr) \
176 /* Called with local BH disabled and the pool write lock held. */
177 #define lookup_rightempty(start) \
179 struct inet_peer *u, **v; \
180 *stackptr++ = &start->avl_left; \
181 v = &start->avl_left; \
182 for (u = *v; u->avl_right != peer_avl_empty; ) { \
190 /* Called with local BH disabled and the pool write lock held.
191 * Variable names are the proof of operation correctness.
192 * Look into mm/map_avl.c for more detail description of the ideas. */
193 static void peer_avl_rebalance(struct inet_peer
**stack
[],
194 struct inet_peer
***stackend
)
196 struct inet_peer
**nodep
, *node
, *l
, *r
;
199 while (stackend
> stack
) {
206 if (lh
> rh
+ 1) { /* l: RH+2 */
207 struct inet_peer
*ll
, *lr
, *lrl
, *lrr
;
211 lrh
= node_height(lr
);
212 if (lrh
<= node_height(ll
)) { /* ll: RH+1 */
213 node
->avl_left
= lr
; /* lr: RH or RH+1 */
214 node
->avl_right
= r
; /* r: RH */
215 node
->avl_height
= lrh
+ 1; /* RH+1 or RH+2 */
216 l
->avl_left
= ll
; /* ll: RH+1 */
217 l
->avl_right
= node
; /* node: RH+1 or RH+2 */
218 l
->avl_height
= node
->avl_height
+ 1;
220 } else { /* ll: RH, lr: RH+1 */
221 lrl
= lr
->avl_left
; /* lrl: RH or RH-1 */
222 lrr
= lr
->avl_right
; /* lrr: RH or RH-1 */
223 node
->avl_left
= lrr
; /* lrr: RH or RH-1 */
224 node
->avl_right
= r
; /* r: RH */
225 node
->avl_height
= rh
+ 1; /* node: RH+1 */
226 l
->avl_left
= ll
; /* ll: RH */
227 l
->avl_right
= lrl
; /* lrl: RH or RH-1 */
228 l
->avl_height
= rh
+ 1; /* l: RH+1 */
229 lr
->avl_left
= l
; /* l: RH+1 */
230 lr
->avl_right
= node
; /* node: RH+1 */
231 lr
->avl_height
= rh
+ 2;
234 } else if (rh
> lh
+ 1) { /* r: LH+2 */
235 struct inet_peer
*rr
, *rl
, *rlr
, *rll
;
239 rlh
= node_height(rl
);
240 if (rlh
<= node_height(rr
)) { /* rr: LH+1 */
241 node
->avl_right
= rl
; /* rl: LH or LH+1 */
242 node
->avl_left
= l
; /* l: LH */
243 node
->avl_height
= rlh
+ 1; /* LH+1 or LH+2 */
244 r
->avl_right
= rr
; /* rr: LH+1 */
245 r
->avl_left
= node
; /* node: LH+1 or LH+2 */
246 r
->avl_height
= node
->avl_height
+ 1;
248 } else { /* rr: RH, rl: RH+1 */
249 rlr
= rl
->avl_right
; /* rlr: LH or LH-1 */
250 rll
= rl
->avl_left
; /* rll: LH or LH-1 */
251 node
->avl_right
= rll
; /* rll: LH or LH-1 */
252 node
->avl_left
= l
; /* l: LH */
253 node
->avl_height
= lh
+ 1; /* node: LH+1 */
254 r
->avl_right
= rr
; /* rr: LH */
255 r
->avl_left
= rlr
; /* rlr: LH or LH-1 */
256 r
->avl_height
= lh
+ 1; /* r: LH+1 */
257 rl
->avl_right
= r
; /* r: LH+1 */
258 rl
->avl_left
= node
; /* node: LH+1 */
259 rl
->avl_height
= lh
+ 2;
263 node
->avl_height
= (lh
> rh
? lh
: rh
) + 1;
268 /* Called with local BH disabled and the pool write lock held. */
269 #define link_to_pool(n) \
272 n->avl_left = peer_avl_empty; \
273 n->avl_right = peer_avl_empty; \
275 peer_avl_rebalance(stack, stackptr); \
278 /* May be called with local BH enabled. */
279 static void unlink_from_pool(struct inet_peer
*p
)
285 write_lock_bh(&peer_pool_lock
);
286 /* Check the reference counter. It was artificially incremented by 1
287 * in cleanup() function to prevent sudden disappearing. If the
288 * reference count is still 1 then the node is referenced only as `p'
289 * here and from the pool. So under the exclusive pool lock it's safe
290 * to remove the node and free it later. */
291 if (atomic_read(&p
->refcnt
) == 1) {
292 struct inet_peer
**stack
[PEER_MAXDEPTH
];
293 struct inet_peer
***stackptr
, ***delp
;
294 if (lookup(p
->v4daddr
) != p
)
296 delp
= stackptr
- 1; /* *delp[0] == p */
297 if (p
->avl_left
== peer_avl_empty
) {
298 *delp
[0] = p
->avl_right
;
301 /* look for a node to insert instead of p */
303 t
= lookup_rightempty(p
);
304 BUG_ON(*stackptr
[-1] != t
);
305 **--stackptr
= t
->avl_left
;
306 /* t is removed, t->v4daddr > x->v4daddr for any
307 * x in p->avl_left subtree.
308 * Put t in the old place of p. */
310 t
->avl_left
= p
->avl_left
;
311 t
->avl_right
= p
->avl_right
;
312 t
->avl_height
= p
->avl_height
;
313 BUG_ON(delp
[1] != &p
->avl_left
);
314 delp
[1] = &t
->avl_left
; /* was &p->avl_left */
316 peer_avl_rebalance(stack
, stackptr
);
320 write_unlock_bh(&peer_pool_lock
);
323 kmem_cache_free(peer_cachep
, p
);
325 /* The node is used again. Decrease the reference counter
326 * back. The loop "cleanup -> unlink_from_unused
327 * -> unlink_from_pool -> putpeer -> link_to_unused
328 * -> cleanup (for the same node)"
329 * doesn't really exist because the entry will have a
330 * recent deletion time and will not be cleaned again soon. */
334 /* May be called with local BH enabled. */
335 static int cleanup_once(unsigned long ttl
)
339 /* Remove the first entry from the list of unused nodes. */
340 spin_lock_bh(&inet_peer_unused_lock
);
341 p
= inet_peer_unused_head
;
343 if (time_after(p
->dtime
+ ttl
, jiffies
)) {
344 /* Do not prune fresh entries. */
345 spin_unlock_bh(&inet_peer_unused_lock
);
348 inet_peer_unused_head
= p
->unused_next
;
349 if (p
->unused_next
!= NULL
)
350 p
->unused_next
->unused_prevp
= p
->unused_prevp
;
352 inet_peer_unused_tailp
= p
->unused_prevp
;
353 p
->unused_prevp
= NULL
; /* mark as not on the list */
354 /* Grab an extra reference to prevent node disappearing
355 * before unlink_from_pool() call. */
356 atomic_inc(&p
->refcnt
);
358 spin_unlock_bh(&inet_peer_unused_lock
);
361 /* It means that the total number of USED entries has
362 * grown over inet_peer_threshold. It shouldn't really
363 * happen because of entry limits in route cache. */
370 /* Called with or without local BH being disabled. */
371 struct inet_peer
*inet_getpeer(__be32 daddr
, int create
)
373 struct inet_peer
*p
, *n
;
374 struct inet_peer
**stack
[PEER_MAXDEPTH
], ***stackptr
;
376 /* Look up for the address quickly. */
377 read_lock_bh(&peer_pool_lock
);
379 if (p
!= peer_avl_empty
)
380 atomic_inc(&p
->refcnt
);
381 read_unlock_bh(&peer_pool_lock
);
383 if (p
!= peer_avl_empty
) {
384 /* The existing node has been found. */
385 /* Remove the entry from unused list if it was there. */
386 unlink_from_unused(p
);
393 /* Allocate the space outside the locked region. */
394 n
= kmem_cache_alloc(peer_cachep
, GFP_ATOMIC
);
398 atomic_set(&n
->refcnt
, 1);
399 atomic_set(&n
->rid
, 0);
400 n
->ip_id_count
= secure_ip_id(daddr
);
403 write_lock_bh(&peer_pool_lock
);
404 /* Check if an entry has suddenly appeared. */
406 if (p
!= peer_avl_empty
)
411 n
->unused_prevp
= NULL
; /* not on the list */
413 write_unlock_bh(&peer_pool_lock
);
415 if (peer_total
>= inet_peer_threshold
)
416 /* Remove one less-recently-used entry. */
422 /* The appropriate node is already in the pool. */
423 atomic_inc(&p
->refcnt
);
424 write_unlock_bh(&peer_pool_lock
);
425 /* Remove the entry from unused list if it was there. */
426 unlink_from_unused(p
);
427 /* Free preallocated the preallocated node. */
428 kmem_cache_free(peer_cachep
, n
);
432 /* Called with local BH disabled. */
433 static void peer_check_expire(unsigned long dummy
)
438 if (peer_total
>= inet_peer_threshold
)
439 ttl
= inet_peer_minttl
;
441 ttl
= inet_peer_maxttl
442 - (inet_peer_maxttl
- inet_peer_minttl
) / HZ
*
443 peer_total
/ inet_peer_threshold
* HZ
;
444 for (i
= 0; i
< PEER_MAX_CLEANUP_WORK
&& !cleanup_once(ttl
); i
++);
446 /* Trigger the timer after inet_peer_gc_mintime .. inet_peer_gc_maxtime
447 * interval depending on the total number of entries (more entries,
449 if (peer_total
>= inet_peer_threshold
)
450 peer_periodic_timer
.expires
= jiffies
+ inet_peer_gc_mintime
;
452 peer_periodic_timer
.expires
= jiffies
453 + inet_peer_gc_maxtime
454 - (inet_peer_gc_maxtime
- inet_peer_gc_mintime
) / HZ
*
455 peer_total
/ inet_peer_threshold
* HZ
;
456 add_timer(&peer_periodic_timer
);