projects / deliverable / linux.git / blob
? search:
summary | shortlog | log | commit | commitdiff | tree
blame | history | raw | HEAD
Merge with rsync://fileserver/linux
[deliverable/linux.git] / net / ipv4 / fib_trie.c
1 /*
2 * This program is free software; you can redistribute it and/or
3 * modify it under the terms of the GNU General Public License
4 * as published by the Free Software Foundation; either version
5 * 2 of the License, or (at your option) any later version.
6 *
7 * Robert Olsson <robert.olsson@its.uu.se> Uppsala Universitet
8 * & Swedish University of Agricultural Sciences.
9 *
10 * Jens Laas <jens.laas@data.slu.se> Swedish University of
11 * Agricultural Sciences.
12 *
13 * Hans Liss <hans.liss@its.uu.se> Uppsala Universitet
14 *
15 * This work is based on the LPC-trie which is originally descibed in:
16 *
17 * An experimental study of compression methods for dynamic tries
18 * Stefan Nilsson and Matti Tikkanen. Algorithmica, 33(1):19-33, 2002.
19 * http://www.nada.kth.se/~snilsson/public/papers/dyntrie2/
20 *
21 *
22 * IP-address lookup using LC-tries. Stefan Nilsson and Gunnar Karlsson
23 * IEEE Journal on Selected Areas in Communications, 17(6):1083-1092, June 1999
24 *
25 * Version: $Id: fib_trie.c,v 1.3 2005/06/08 14:20:01 robert Exp $
26 *
27 *
28 * Code from fib_hash has been reused which includes the following header:
29 *
30 *
31 * INET An implementation of the TCP/IP protocol suite for the LINUX
32 * operating system. INET is implemented using the BSD Socket
33 * interface as the means of communication with the user level.
34 *
35 * IPv4 FIB: lookup engine and maintenance routines.
36 *
37 *
38 * Authors: Alexey Kuznetsov, <kuznet@ms2.inr.ac.ru>
39 *
40 * This program is free software; you can redistribute it and/or
41 * modify it under the terms of the GNU General Public License
42 * as published by the Free Software Foundation; either version
43 * 2 of the License, or (at your option) any later version.
44 */
45
46 #define VERSION "0.325"
47
48 #include <linux/config.h>
49 #include <asm/uaccess.h>
50 #include <asm/system.h>
51 #include <asm/bitops.h>
52 #include <linux/types.h>
53 #include <linux/kernel.h>
54 #include <linux/sched.h>
55 #include <linux/mm.h>
56 #include <linux/string.h>
57 #include <linux/socket.h>
58 #include <linux/sockios.h>
59 #include <linux/errno.h>
60 #include <linux/in.h>
61 #include <linux/inet.h>
62 #include <linux/netdevice.h>
63 #include <linux/if_arp.h>
64 #include <linux/proc_fs.h>
65 #include <linux/skbuff.h>
66 #include <linux/netlink.h>
67 #include <linux/init.h>
68 #include <linux/list.h>
69 #include <net/ip.h>
70 #include <net/protocol.h>
71 #include <net/route.h>
72 #include <net/tcp.h>
73 #include <net/sock.h>
74 #include <net/ip_fib.h>
75 #include "fib_lookup.h"
76
77 #undef CONFIG_IP_FIB_TRIE_STATS
78 #define MAX_CHILDS 16384
79
80 #define EXTRACT(p, n, str) ((str)<<(p)>>(32-(n)))
81 #define KEYLENGTH (8*sizeof(t_key))
82 #define MASK_PFX(k, l) (((l)==0)?0:(k >> (KEYLENGTH-l)) << (KEYLENGTH-l))
83 #define TKEY_GET_MASK(offset, bits) (((bits)==0)?0:((t_key)(-1) << (KEYLENGTH - bits) >> offset))
84
85 static DEFINE_RWLOCK(fib_lock);
86
87 typedef unsigned int t_key;
88
89 #define T_TNODE 0
90 #define T_LEAF 1
91 #define NODE_TYPE_MASK 0x1UL
92 #define NODE_PARENT(_node) \
93 ((struct tnode *)((_node)->_parent & ~NODE_TYPE_MASK))
94 #define NODE_SET_PARENT(_node, _ptr) \
95 ((_node)->_parent = (((unsigned long)(_ptr)) | \
96 ((_node)->_parent & NODE_TYPE_MASK)))
97 #define NODE_INIT_PARENT(_node, _type) \
98 ((_node)->_parent = (_type))
99 #define NODE_TYPE(_node) \
100 ((_node)->_parent & NODE_TYPE_MASK)
101
102 #define IS_TNODE(n) (!(n->_parent & T_LEAF))
103 #define IS_LEAF(n) (n->_parent & T_LEAF)
104
105 struct node {
106 t_key key;
107 unsigned long _parent;
108 };
109
110 struct leaf {
111 t_key key;
112 unsigned long _parent;
113 struct hlist_head list;
114 };
115
116 struct leaf_info {
117 struct hlist_node hlist;
118 int plen;
119 struct list_head falh;
120 };
121
122 struct tnode {
123 t_key key;
124 unsigned long _parent;
125 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
126 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
127 unsigned short full_children; /* KEYLENGTH bits needed */
128 unsigned short empty_children; /* KEYLENGTH bits needed */
129 struct node *child[0];
130 };
131
132 #ifdef CONFIG_IP_FIB_TRIE_STATS
133 struct trie_use_stats {
134 unsigned int gets;
135 unsigned int backtrack;
136 unsigned int semantic_match_passed;
137 unsigned int semantic_match_miss;
138 unsigned int null_node_hit;
139 unsigned int resize_node_skipped;
140 };
141 #endif
142
143 struct trie_stat {
144 unsigned int totdepth;
145 unsigned int maxdepth;
146 unsigned int tnodes;
147 unsigned int leaves;
148 unsigned int nullpointers;
149 unsigned int nodesizes[MAX_CHILDS];
150 };
151
152 struct trie {
153 struct node *trie;
154 #ifdef CONFIG_IP_FIB_TRIE_STATS
155 struct trie_use_stats stats;
156 #endif
157 int size;
158 unsigned int revision;
159 };
160
161 static int trie_debug = 0;
162
163 static int tnode_full(struct tnode *tn, struct node *n);
164 static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
165 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
166 static int tnode_child_length(struct tnode *tn);
167 static struct node *resize(struct trie *t, struct tnode *tn);
168 static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err);
169 static struct tnode *halve(struct trie *t, struct tnode *tn, int *err);
170 static void tnode_free(struct tnode *tn);
171 static void trie_dump_seq(struct seq_file *seq, struct trie *t);
172 extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio);
173 extern int fib_detect_death(struct fib_info *fi, int order,
174 struct fib_info **last_resort, int *last_idx, int *dflt);
175
176 extern void rtmsg_fib(int event, u32 key, struct fib_alias *fa, int z, int tb_id,
177 struct nlmsghdr *n, struct netlink_skb_parms *req);
178
179 static kmem_cache_t *fn_alias_kmem;
180 static struct trie *trie_local = NULL, *trie_main = NULL;
181
182 static void trie_bug(char *err)
183 {
184 printk("Trie Bug: %s\n", err);
185 BUG();
186 }
187
188 static inline struct node *tnode_get_child(struct tnode *tn, int i)
189 {
190 if (i >= 1<<tn->bits)
191 trie_bug("tnode_get_child");
192
193 return tn->child[i];
194 }
195
196 static inline int tnode_child_length(struct tnode *tn)
197 {
198 return 1<<tn->bits;
199 }
200
201 /*
202 _________________________________________________________________
203 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
204 ----------------------------------------------------------------
205 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
206
207 _________________________________________________________________
208 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
209 -----------------------------------------------------------------
210 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
211
212 tp->pos = 7
213 tp->bits = 3
214 n->pos = 15
215 n->bits=4
216 KEYLENGTH=32
217 */
218
219 static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
220 {
221 if (offset < KEYLENGTH)
222 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
223 else
224 return 0;
225 }
226
227 static inline int tkey_equals(t_key a, t_key b)
228 {
229 return a == b;
230 }
231
232 static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
233 {
234 if (bits == 0 || offset >= KEYLENGTH)
235 return 1;
236 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
237 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
238 }
239
240 static inline int tkey_mismatch(t_key a, int offset, t_key b)
241 {
242 t_key diff = a ^ b;
243 int i = offset;
244
245 if(!diff)
246 return 0;
247 while((diff << i) >> (KEYLENGTH-1) == 0)
248 i++;
249 return i;
250 }
251
252 /* Candiate for fib_semantics */
253
254 static void fn_free_alias(struct fib_alias *fa)
255 {
256 fib_release_info(fa->fa_info);
257 kmem_cache_free(fn_alias_kmem, fa);
258 }
259
260 /*
261 To understand this stuff, an understanding of keys and all their bits is
262 necessary. Every node in the trie has a key associated with it, but not
263 all of the bits in that key are significant.
264
265 Consider a node 'n' and its parent 'tp'.
266
267 If n is a leaf, every bit in its key is significant. Its presence is
268 necessitaded by path compression, since during a tree traversal (when
269 searching for a leaf - unless we are doing an insertion) we will completely
270 ignore all skipped bits we encounter. Thus we need to verify, at the end of
271 a potentially successful search, that we have indeed been walking the
272 correct key path.
273
274 Note that we can never "miss" the correct key in the tree if present by
275 following the wrong path. Path compression ensures that segments of the key
276 that are the same for all keys with a given prefix are skipped, but the
277 skipped part *is* identical for each node in the subtrie below the skipped
278 bit! trie_insert() in this implementation takes care of that - note the
279 call to tkey_sub_equals() in trie_insert().
280
281 if n is an internal node - a 'tnode' here, the various parts of its key
282 have many different meanings.
283
284 Example:
285 _________________________________________________________________
286 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
287 -----------------------------------------------------------------
288 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
289
290 _________________________________________________________________
291 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
292 -----------------------------------------------------------------
293 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
294
295 tp->pos = 7
296 tp->bits = 3
297 n->pos = 15
298 n->bits=4
299
300 First, let's just ignore the bits that come before the parent tp, that is
301 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
302 not use them for anything.
303
304 The bits from (tp->pos) to (tp->pos + tp->bits - 1) - "N", above - are the
305 index into the parent's child array. That is, they will be used to find
306 'n' among tp's children.
307
308 The bits from (tp->pos + tp->bits) to (n->pos - 1) - "S" - are skipped bits
309 for the node n.
310
311 All the bits we have seen so far are significant to the node n. The rest
312 of the bits are really not needed or indeed known in n->key.
313
314 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into
315 n's child array, and will of course be different for each child.
316
317 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
318 at this point.
319
320 */
321
322 static void check_tnode(struct tnode *tn)
323 {
324 if(tn && tn->pos+tn->bits > 32) {
325 printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos, tn->bits);
326 }
327 }
328
329 static int halve_threshold = 25;
330 static int inflate_threshold = 50;
331
332 static struct leaf *leaf_new(void)
333 {
334 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
335 if(l) {
336 NODE_INIT_PARENT(l, T_LEAF);
337 INIT_HLIST_HEAD(&l->list);
338 }
339 return l;
340 }
341
342 static struct leaf_info *leaf_info_new(int plen)
343 {
344 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
345 if(li) {
346 li->plen = plen;
347 INIT_LIST_HEAD(&li->falh);
348 }
349 return li;
350 }
351
352 static inline void free_leaf(struct leaf *l)
353 {
354 kfree(l);
355 }
356
357 static inline void free_leaf_info(struct leaf_info *li)
358 {
359 kfree(li);
360 }
361
362 static struct tnode *tnode_alloc(unsigned int size)
363 {
364 if (size <= PAGE_SIZE) {
365 return kmalloc(size, GFP_KERNEL);
366 } else {
367 return (struct tnode *)
368 __get_free_pages(GFP_KERNEL, get_order(size));
369 }
370 }
371
372 static void __tnode_free(struct tnode *tn)
373 {
374 unsigned int size = sizeof(struct tnode) +
375 (1<<tn->bits) * sizeof(struct node *);
376
377 if (size <= PAGE_SIZE)
378 kfree(tn);
379 else
380 free_pages((unsigned long)tn, get_order(size));
381 }
382
383 static struct tnode* tnode_new(t_key key, int pos, int bits)
384 {
385 int nchildren = 1<<bits;
386 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
387 struct tnode *tn = tnode_alloc(sz);
388
389 if(tn) {
390 memset(tn, 0, sz);
391 NODE_INIT_PARENT(tn, T_TNODE);
392 tn->pos = pos;
393 tn->bits = bits;
394 tn->key = key;
395 tn->full_children = 0;
396 tn->empty_children = 1<<bits;
397 }
398 if(trie_debug > 0)
399 printk("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
400 (unsigned int) (sizeof(struct node) * 1<<bits));
401 return tn;
402 }
403
404 static void tnode_free(struct tnode *tn)
405 {
406 if(!tn) {
407 trie_bug("tnode_free\n");
408 }
409 if(IS_LEAF(tn)) {
410 free_leaf((struct leaf *)tn);
411 if(trie_debug > 0 )
412 printk("FL %p \n", tn);
413 }
414 else if(IS_TNODE(tn)) {
415 __tnode_free(tn);
416 if(trie_debug > 0 )
417 printk("FT %p \n", tn);
418 }
419 else {
420 trie_bug("tnode_free\n");
421 }
422 }
423
424 /*
425 * Check whether a tnode 'n' is "full", i.e. it is an internal node
426 * and no bits are skipped. See discussion in dyntree paper p. 6
427 */
428
429 static inline int tnode_full(struct tnode *tn, struct node *n)
430 {
431 if(n == NULL || IS_LEAF(n))
432 return 0;
433
434 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
435 }
436
437 static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
438 {
439 tnode_put_child_reorg(tn, i, n, -1);
440 }
441
442 /*
443 * Add a child at position i overwriting the old value.
444 * Update the value of full_children and empty_children.
445 */
446
447 static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
448 {
449 struct node *chi;
450 int isfull;
451
452 if(i >= 1<<tn->bits) {
453 printk("bits=%d, i=%d\n", tn->bits, i);
454 trie_bug("tnode_put_child_reorg bits");
455 }
456 write_lock_bh(&fib_lock);
457 chi = tn->child[i];
458
459 /* update emptyChildren */
460 if (n == NULL && chi != NULL)
461 tn->empty_children++;
462 else if (n != NULL && chi == NULL)
463 tn->empty_children--;
464
465 /* update fullChildren */
466 if (wasfull == -1)
467 wasfull = tnode_full(tn, chi);
468
469 isfull = tnode_full(tn, n);
470 if (wasfull && !isfull)
471 tn->full_children--;
472
473 else if (!wasfull && isfull)
474 tn->full_children++;
475 if(n)
476 NODE_SET_PARENT(n, tn);
477
478 tn->child[i] = n;
479 write_unlock_bh(&fib_lock);
480 }
481
482 static struct node *resize(struct trie *t, struct tnode *tn)
483 {
484 int i;
485 int err = 0;
486
487 if (!tn)
488 return NULL;
489
490 if(trie_debug)
491 printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
492 tn, inflate_threshold, halve_threshold);
493
494 /* No children */
495 if (tn->empty_children == tnode_child_length(tn)) {
496 tnode_free(tn);
497 return NULL;
498 }
499 /* One child */
500 if (tn->empty_children == tnode_child_length(tn) - 1)
501 for (i = 0; i < tnode_child_length(tn); i++) {
502
503 write_lock_bh(&fib_lock);
504 if (tn->child[i] != NULL) {
505
506 /* compress one level */
507 struct node *n = tn->child[i];
508 if(n)
509 NODE_INIT_PARENT(n, NODE_TYPE(n));
510
511 write_unlock_bh(&fib_lock);
512 tnode_free(tn);
513 return n;
514 }
515 write_unlock_bh(&fib_lock);
516 }
517 /*
518 * Double as long as the resulting node has a number of
519 * nonempty nodes that are above the threshold.
520 */
521
522 /*
523 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
524 * the Helsinki University of Technology and Matti Tikkanen of Nokia
525 * Telecommunications, page 6:
526 * "A node is doubled if the ratio of non-empty children to all
527 * children in the *doubled* node is at least 'high'."
528 *
529 * 'high' in this instance is the variable 'inflate_threshold'. It
530 * is expressed as a percentage, so we multiply it with
531 * tnode_child_length() and instead of multiplying by 2 (since the
532 * child array will be doubled by inflate()) and multiplying
533 * the left-hand side by 100 (to handle the percentage thing) we
534 * multiply the left-hand side by 50.
535 *
536 * The left-hand side may look a bit weird: tnode_child_length(tn)
537 * - tn->empty_children is of course the number of non-null children
538 * in the current node. tn->full_children is the number of "full"
539 * children, that is non-null tnodes with a skip value of 0.
540 * All of those will be doubled in the resulting inflated tnode, so
541 * we just count them one extra time here.
542 *
543 * A clearer way to write this would be:
544 *
545 * to_be_doubled = tn->full_children;
546 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
547 * tn->full_children;
548 *
549 * new_child_length = tnode_child_length(tn) * 2;
550 *
551 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
552 * new_child_length;
553 * if (new_fill_factor >= inflate_threshold)
554 *
555 * ...and so on, tho it would mess up the while() loop.
556 *
557 * anyway,
558 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
559 * inflate_threshold
560 *
561 * avoid a division:
562 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
563 * inflate_threshold * new_child_length
564 *
565 * expand not_to_be_doubled and to_be_doubled, and shorten:
566 * 100 * (tnode_child_length(tn) - tn->empty_children +
567 * tn->full_children ) >= inflate_threshold * new_child_length
568 *
569 * expand new_child_length:
570 * 100 * (tnode_child_length(tn) - tn->empty_children +
571 * tn->full_children ) >=
572 * inflate_threshold * tnode_child_length(tn) * 2
573 *
574 * shorten again:
575 * 50 * (tn->full_children + tnode_child_length(tn) -
576 * tn->empty_children ) >= inflate_threshold *
577 * tnode_child_length(tn)
578 *
579 */
580
581 check_tnode(tn);
582
583 err = 0;
584 while ((tn->full_children > 0 &&
585 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
586 inflate_threshold * tnode_child_length(tn))) {
587
588 tn = inflate(t, tn, &err);
589
590 if(err) {
591 #ifdef CONFIG_IP_FIB_TRIE_STATS
592 t->stats.resize_node_skipped++;
593 #endif
594 break;
595 }
596 }
597
598 check_tnode(tn);
599
600 /*
601 * Halve as long as the number of empty children in this
602 * node is above threshold.
603 */
604
605 err = 0;
606 while (tn->bits > 1 &&
607 100 * (tnode_child_length(tn) - tn->empty_children) <
608 halve_threshold * tnode_child_length(tn)) {
609
610 tn = halve(t, tn, &err);
611
612 if(err) {
613 #ifdef CONFIG_IP_FIB_TRIE_STATS
614 t->stats.resize_node_skipped++;
615 #endif
616 break;
617 }
618 }
619
620
621 /* Only one child remains */
622
623 if (tn->empty_children == tnode_child_length(tn) - 1)
624 for (i = 0; i < tnode_child_length(tn); i++) {
625
626 write_lock_bh(&fib_lock);
627 if (tn->child[i] != NULL) {
628 /* compress one level */
629 struct node *n = tn->child[i];
630
631 if(n)
632 NODE_INIT_PARENT(n, NODE_TYPE(n));
633
634 write_unlock_bh(&fib_lock);
635 tnode_free(tn);
636 return n;
637 }
638 write_unlock_bh(&fib_lock);
639 }
640
641 return (struct node *) tn;
642 }
643
644 static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
645 {
646 struct tnode *inode;
647 struct tnode *oldtnode = tn;
648 int olen = tnode_child_length(tn);
649 int i;
650
651 if(trie_debug)
652 printk("In inflate\n");
653
654 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
655
656 if (!tn) {
657 *err = -ENOMEM;
658 return oldtnode;
659 }
660
661 /*
662 * Preallocate and store tnodes before the actual work so we
663 * don't get into an inconsistent state if memory allocation
664 * fails. In case of failure we return the oldnode and inflate
665 * of tnode is ignored.
666 */
667
668 for(i = 0; i < olen; i++) {
669 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
670
671 if (inode &&
672 IS_TNODE(inode) &&
673 inode->pos == oldtnode->pos + oldtnode->bits &&
674 inode->bits > 1) {
675 struct tnode *left, *right;
676
677 t_key m = TKEY_GET_MASK(inode->pos, 1);
678
679 left = tnode_new(inode->key&(~m), inode->pos + 1,
680 inode->bits - 1);
681
682 if(!left) {
683 *err = -ENOMEM;
684 break;
685 }
686
687 right = tnode_new(inode->key|m, inode->pos + 1,
688 inode->bits - 1);
689
690 if(!right) {
691 *err = -ENOMEM;
692 break;
693 }
694
695 put_child(t, tn, 2*i, (struct node *) left);
696 put_child(t, tn, 2*i+1, (struct node *) right);
697 }
698 }
699
700 if(*err) {
701 int size = tnode_child_length(tn);
702 int j;
703
704 for(j = 0; j < size; j++)
705 if( tn->child[j])
706 tnode_free((struct tnode *)tn->child[j]);
707
708 tnode_free(tn);
709
710 *err = -ENOMEM;
711 return oldtnode;
712 }
713
714 for(i = 0; i < olen; i++) {
715 struct node *node = tnode_get_child(oldtnode, i);
716
717 /* An empty child */
718 if (node == NULL)
719 continue;
720
721 /* A leaf or an internal node with skipped bits */
722
723 if(IS_LEAF(node) || ((struct tnode *) node)->pos >
724 tn->pos + tn->bits - 1) {
725 if(tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
726 1) == 0)
727 put_child(t, tn, 2*i, node);
728 else
729 put_child(t, tn, 2*i+1, node);
730 continue;
731 }
732
733 /* An internal node with two children */
734 inode = (struct tnode *) node;
735
736 if (inode->bits == 1) {
737 put_child(t, tn, 2*i, inode->child[0]);
738 put_child(t, tn, 2*i+1, inode->child[1]);
739
740 tnode_free(inode);
741 }
742
743 /* An internal node with more than two children */
744 else {
745 struct tnode *left, *right;
746 int size, j;
747
748 /* We will replace this node 'inode' with two new
749 * ones, 'left' and 'right', each with half of the
750 * original children. The two new nodes will have
751 * a position one bit further down the key and this
752 * means that the "significant" part of their keys
753 * (see the discussion near the top of this file)
754 * will differ by one bit, which will be "0" in
755 * left's key and "1" in right's key. Since we are
756 * moving the key position by one step, the bit that
757 * we are moving away from - the bit at position
758 * (inode->pos) - is the one that will differ between
759 * left and right. So... we synthesize that bit in the
760 * two new keys.
761 * The mask 'm' below will be a single "one" bit at
762 * the position (inode->pos)
763 */
764
765 /* Use the old key, but set the new significant
766 * bit to zero.
767 */
768
769 left = (struct tnode *) tnode_get_child(tn, 2*i);
770 put_child(t, tn, 2*i, NULL);
771
772 if(!left)
773 BUG();
774
775 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
776 put_child(t, tn, 2*i+1, NULL);
777
778 if(!right)
779 BUG();
780
781 size = tnode_child_length(left);
782 for(j = 0; j < size; j++) {
783 put_child(t, left, j, inode->child[j]);
784 put_child(t, right, j, inode->child[j + size]);
785 }
786 put_child(t, tn, 2*i, resize(t, left));
787 put_child(t, tn, 2*i+1, resize(t, right));
788
789 tnode_free(inode);
790 }
791 }
792 tnode_free(oldtnode);
793 return tn;
794 }
795
796 static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
797 {
798 struct tnode *oldtnode = tn;
799 struct node *left, *right;
800 int i;
801 int olen = tnode_child_length(tn);
802
803 if(trie_debug) printk("In halve\n");
804
805 tn=tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
806
807 if (!tn) {
808 *err = -ENOMEM;
809 return oldtnode;
810 }
811
812 /*
813 * Preallocate and store tnodes before the actual work so we
814 * don't get into an inconsistent state if memory allocation
815 * fails. In case of failure we return the oldnode and halve
816 * of tnode is ignored.
817 */
818
819 for(i = 0; i < olen; i += 2) {
820 left = tnode_get_child(oldtnode, i);
821 right = tnode_get_child(oldtnode, i+1);
822
823 /* Two nonempty children */
824 if( left && right) {
825 struct tnode *newBinNode =
826 tnode_new(left->key, tn->pos + tn->bits, 1);
827
828 if(!newBinNode) {
829 *err = -ENOMEM;
830 break;
831 }
832 put_child(t, tn, i/2, (struct node *)newBinNode);
833 }
834 }
835
836 if(*err) {
837 int size = tnode_child_length(tn);
838 int j;
839
840 for(j = 0; j < size; j++)
841 if( tn->child[j])
842 tnode_free((struct tnode *)tn->child[j]);
843
844 tnode_free(tn);
845
846 *err = -ENOMEM;
847 return oldtnode;
848 }
849
850 for(i = 0; i < olen; i += 2) {
851 left = tnode_get_child(oldtnode, i);
852 right = tnode_get_child(oldtnode, i+1);
853
854 /* At least one of the children is empty */
855 if (left == NULL) {
856 if (right == NULL) /* Both are empty */
857 continue;
858 put_child(t, tn, i/2, right);
859 } else if (right == NULL)
860 put_child(t, tn, i/2, left);
861
862 /* Two nonempty children */
863 else {
864 struct tnode *newBinNode =
865 (struct tnode *) tnode_get_child(tn, i/2);
866 put_child(t, tn, i/2, NULL);
867
868 if(!newBinNode)
869 BUG();
870
871 put_child(t, newBinNode, 0, left);
872 put_child(t, newBinNode, 1, right);
873 put_child(t, tn, i/2, resize(t, newBinNode));
874 }
875 }
876 tnode_free(oldtnode);
877 return tn;
878 }
879
880 static void *trie_init(struct trie *t)
881 {
882 if(t) {
883 t->size = 0;
884 t->trie = NULL;
885 t->revision = 0;
886 #ifdef CONFIG_IP_FIB_TRIE_STATS
887 memset(&t->stats, 0, sizeof(struct trie_use_stats));
888 #endif
889 }
890 return t;
891 }
892
893 static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
894 {
895 struct hlist_node *node;
896 struct leaf_info *li;
897
898 hlist_for_each_entry(li, node, head, hlist) {
899
900 if ( li->plen == plen )
901 return li;
902 }
903 return NULL;
904 }
905
906 static inline struct list_head * get_fa_head(struct leaf *l, int plen)
907 {
908 struct list_head *fa_head=NULL;
909 struct leaf_info *li = find_leaf_info(&l->list, plen);
910
911 if(li)
912 fa_head = &li->falh;
913
914 return fa_head;
915 }
916
917 static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
918 {
919 struct leaf_info *li=NULL, *last=NULL;
920 struct hlist_node *node, *tmp;
921
922 write_lock_bh(&fib_lock);
923
924 if(hlist_empty(head))
925 hlist_add_head(&new->hlist, head);
926 else {
927 hlist_for_each_entry_safe(li, node, tmp, head, hlist) {
928
929 if (new->plen > li->plen)
930 break;
931
932 last = li;
933 }
934 if(last)
935 hlist_add_after(&last->hlist, &new->hlist);
936 else
937 hlist_add_before(&new->hlist, &li->hlist);
938 }
939 write_unlock_bh(&fib_lock);
940 }
941
942 static struct leaf *
943 fib_find_node(struct trie *t, u32 key)
944 {
945 int pos;
946 struct tnode *tn;
947 struct node *n;
948
949 pos = 0;
950 n=t->trie;
951
952 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
953 tn = (struct tnode *) n;
954
955 check_tnode(tn);
956
957 if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
958 pos=tn->pos + tn->bits;
959 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
960 }
961 else
962 break;
963 }
964 /* Case we have found a leaf. Compare prefixes */
965
966 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
967 struct leaf *l = (struct leaf *) n;
968 return l;
969 }
970 return NULL;
971 }
972
973 static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
974 {
975 int i = 0;
976 int wasfull;
977 t_key cindex, key;
978 struct tnode *tp = NULL;
979
980 if(!tn)
981 BUG();
982
983 key = tn->key;
984 i = 0;
985
986 while (tn != NULL && NODE_PARENT(tn) != NULL) {
987
988 if( i > 10 ) {
989 printk("Rebalance tn=%p \n", tn);
990 if(tn) printk("tn->parent=%p \n", NODE_PARENT(tn));
991
992 printk("Rebalance tp=%p \n", tp);
993 if(tp) printk("tp->parent=%p \n", NODE_PARENT(tp));
994 }
995
996 if( i > 12 ) BUG();
997 i++;
998
999 tp = NODE_PARENT(tn);
1000 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1001 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1002 tn = (struct tnode *) resize (t, (struct tnode *)tn);
1003 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
1004
1005 if(!NODE_PARENT(tn))
1006 break;
1007
1008 tn = NODE_PARENT(tn);
1009 }
1010 /* Handle last (top) tnode */
1011 if (IS_TNODE(tn))
1012 tn = (struct tnode*) resize(t, (struct tnode *)tn);
1013
1014 return (struct node*) tn;
1015 }
1016
1017 static struct list_head *
1018 fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1019 {
1020 int pos, newpos;
1021 struct tnode *tp = NULL, *tn = NULL;
1022 struct node *n;
1023 struct leaf *l;
1024 int missbit;
1025 struct list_head *fa_head=NULL;
1026 struct leaf_info *li;
1027 t_key cindex;
1028
1029 pos = 0;
1030 n=t->trie;
1031
1032 /* If we point to NULL, stop. Either the tree is empty and we should
1033 * just put a new leaf in if, or we have reached an empty child slot,
1034 * and we should just put our new leaf in that.
1035 * If we point to a T_TNODE, check if it matches our key. Note that
1036 * a T_TNODE might be skipping any number of bits - its 'pos' need
1037 * not be the parent's 'pos'+'bits'!
1038 *
1039 * If it does match the current key, get pos/bits from it, extract
1040 * the index from our key, push the T_TNODE and walk the tree.
1041 *
1042 * If it doesn't, we have to replace it with a new T_TNODE.
1043 *
1044 * If we point to a T_LEAF, it might or might not have the same key
1045 * as we do. If it does, just change the value, update the T_LEAF's
1046 * value, and return it.
1047 * If it doesn't, we need to replace it with a T_TNODE.
1048 */
1049
1050 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1051 tn = (struct tnode *) n;
1052
1053 check_tnode(tn);
1054
1055 if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1056 tp = tn;
1057 pos=tn->pos + tn->bits;
1058 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1059
1060 if(n && NODE_PARENT(n) != tn) {
1061 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1062 BUG();
1063 }
1064 }
1065 else
1066 break;
1067 }
1068
1069 /*
1070 * n ----> NULL, LEAF or TNODE
1071 *
1072 * tp is n's (parent) ----> NULL or TNODE
1073 */
1074
1075 if(tp && IS_LEAF(tp))
1076 BUG();
1077
1078
1079 /* Case 1: n is a leaf. Compare prefixes */
1080
1081 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1082 struct leaf *l = ( struct leaf *) n;
1083
1084 li = leaf_info_new(plen);
1085
1086 if(! li) {
1087 *err = -ENOMEM;
1088 goto err;
1089 }
1090
1091 fa_head = &li->falh;
1092 insert_leaf_info(&l->list, li);
1093 goto done;
1094 }
1095 t->size++;
1096 l = leaf_new();
1097
1098 if(! l) {
1099 *err = -ENOMEM;
1100 goto err;
1101 }
1102
1103 l->key = key;
1104 li = leaf_info_new(plen);
1105
1106 if(! li) {
1107 tnode_free((struct tnode *) l);
1108 *err = -ENOMEM;
1109 goto err;
1110 }
1111
1112 fa_head = &li->falh;
1113 insert_leaf_info(&l->list, li);
1114
1115 /* Case 2: n is NULL, and will just insert a new leaf */
1116 if (t->trie && n == NULL) {
1117
1118 NODE_SET_PARENT(l, tp);
1119
1120 if (!tp)
1121 BUG();
1122
1123 else {
1124 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1125 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1126 }
1127 }
1128 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1129 else {
1130 /*
1131 * Add a new tnode here
1132 * first tnode need some special handling
1133 */
1134
1135 if (tp)
1136 pos=tp->pos+tp->bits;
1137 else
1138 pos=0;
1139 if(n) {
1140 newpos = tkey_mismatch(key, pos, n->key);
1141 tn = tnode_new(n->key, newpos, 1);
1142 }
1143 else {
1144 newpos = 0;
1145 tn = tnode_new(key, newpos, 1); /* First tnode */
1146 }
1147
1148 if(!tn) {
1149 free_leaf_info(li);
1150 tnode_free((struct tnode *) l);
1151 *err = -ENOMEM;
1152 goto err;
1153 }
1154
1155 NODE_SET_PARENT(tn, tp);
1156
1157 missbit=tkey_extract_bits(key, newpos, 1);
1158 put_child(t, tn, missbit, (struct node *)l);
1159 put_child(t, tn, 1-missbit, n);
1160
1161 if(tp) {
1162 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1163 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
1164 }
1165 else {
1166 t->trie = (struct node*) tn; /* First tnode */
1167 tp = tn;
1168 }
1169 }
1170 if(tp && tp->pos+tp->bits > 32) {
1171 printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1172 tp, tp->pos, tp->bits, key, plen);
1173 }
1174 /* Rebalance the trie */
1175 t->trie = trie_rebalance(t, tp);
1176 done:
1177 t->revision++;
1178 err:;
1179 return fa_head;
1180 }
1181
1182 static int
1183 fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1184 struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
1185 {
1186 struct trie *t = (struct trie *) tb->tb_data;
1187 struct fib_alias *fa, *new_fa;
1188 struct list_head *fa_head=NULL;
1189 struct fib_info *fi;
1190 int plen = r->rtm_dst_len;
1191 int type = r->rtm_type;
1192 u8 tos = r->rtm_tos;
1193 u32 key, mask;
1194 int err;
1195 struct leaf *l;
1196
1197 if (plen > 32)
1198 return -EINVAL;
1199
1200 key = 0;
1201 if (rta->rta_dst)
1202 memcpy(&key, rta->rta_dst, 4);
1203
1204 key = ntohl(key);
1205
1206 if(trie_debug)
1207 printk("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
1208
1209 mask = ntohl( inet_make_mask(plen) );
1210
1211 if(key & ~mask)
1212 return -EINVAL;
1213
1214 key = key & mask;
1215
1216 if ((fi = fib_create_info(r, rta, nlhdr, &err)) == NULL)
1217 goto err;
1218
1219 l = fib_find_node(t, key);
1220 fa = NULL;
1221
1222 if(l) {
1223 fa_head = get_fa_head(l, plen);
1224 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1225 }
1226
1227 /* Now fa, if non-NULL, points to the first fib alias
1228 * with the same keys [prefix,tos,priority], if such key already
1229 * exists or to the node before which we will insert new one.
1230 *
1231 * If fa is NULL, we will need to allocate a new one and
1232 * insert to the head of f.
1233 *
1234 * If f is NULL, no fib node matched the destination key
1235 * and we need to allocate a new one of those as well.
1236 */
1237
1238 if (fa &&
1239 fa->fa_info->fib_priority == fi->fib_priority) {
1240 struct fib_alias *fa_orig;
1241
1242 err = -EEXIST;
1243 if (nlhdr->nlmsg_flags & NLM_F_EXCL)
1244 goto out;
1245
1246 if (nlhdr->nlmsg_flags & NLM_F_REPLACE) {
1247 struct fib_info *fi_drop;
1248 u8 state;
1249
1250 write_lock_bh(&fib_lock);
1251
1252 fi_drop = fa->fa_info;
1253 fa->fa_info = fi;
1254 fa->fa_type = type;
1255 fa->fa_scope = r->rtm_scope;
1256 state = fa->fa_state;
1257 fa->fa_state &= ~FA_S_ACCESSED;
1258
1259 write_unlock_bh(&fib_lock);
1260
1261 fib_release_info(fi_drop);
1262 if (state & FA_S_ACCESSED)
1263 rt_cache_flush(-1);
1264
1265 goto succeeded;
1266 }
1267 /* Error if we find a perfect match which
1268 * uses the same scope, type, and nexthop
1269 * information.
1270 */
1271 fa_orig = fa;
1272 list_for_each_entry(fa, fa_orig->fa_list.prev, fa_list) {
1273 if (fa->fa_tos != tos)
1274 break;
1275 if (fa->fa_info->fib_priority != fi->fib_priority)
1276 break;
1277 if (fa->fa_type == type &&
1278 fa->fa_scope == r->rtm_scope &&
1279 fa->fa_info == fi) {
1280 goto out;
1281 }
1282 }
1283 if (!(nlhdr->nlmsg_flags & NLM_F_APPEND))
1284 fa = fa_orig;
1285 }
1286 err = -ENOENT;
1287 if (!(nlhdr->nlmsg_flags&NLM_F_CREATE))
1288 goto out;
1289
1290 err = -ENOBUFS;
1291 new_fa = kmem_cache_alloc(fn_alias_kmem, SLAB_KERNEL);
1292 if (new_fa == NULL)
1293 goto out;
1294
1295 new_fa->fa_info = fi;
1296 new_fa->fa_tos = tos;
1297 new_fa->fa_type = type;
1298 new_fa->fa_scope = r->rtm_scope;
1299 new_fa->fa_state = 0;
1300 #if 0
1301 new_fa->dst = NULL;
1302 #endif
1303 /*
1304 * Insert new entry to the list.
1305 */
1306
1307 if(!fa_head) {
1308 fa_head = fib_insert_node(t, &err, key, plen);
1309 err = 0;
1310 if(err)
1311 goto out_free_new_fa;
1312 }
1313
1314 write_lock_bh(&fib_lock);
1315
1316 list_add_tail(&new_fa->fa_list,
1317 (fa ? &fa->fa_list : fa_head));
1318
1319 write_unlock_bh(&fib_lock);
1320
1321 rt_cache_flush(-1);
1322 rtmsg_fib(RTM_NEWROUTE, htonl(key), new_fa, plen, tb->tb_id, nlhdr, req);
1323 succeeded:
1324 return 0;
1325
1326 out_free_new_fa:
1327 kmem_cache_free(fn_alias_kmem, new_fa);
1328 out:
1329 fib_release_info(fi);
1330 err:;
1331 return err;
1332 }
1333
1334 static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *plen, const struct flowi *flp,
1335 struct fib_result *res, int *err)
1336 {
1337 int i;
1338 t_key mask;
1339 struct leaf_info *li;
1340 struct hlist_head *hhead = &l->list;
1341 struct hlist_node *node;
1342
1343 hlist_for_each_entry(li, node, hhead, hlist) {
1344
1345 i = li->plen;
1346 mask = ntohl(inet_make_mask(i));
1347 if (l->key != (key & mask))
1348 continue;
1349
1350 if (((*err) = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) == 0) {
1351 *plen = i;
1352 #ifdef CONFIG_IP_FIB_TRIE_STATS
1353 t->stats.semantic_match_passed++;
1354 #endif
1355 return 1;
1356 }
1357 #ifdef CONFIG_IP_FIB_TRIE_STATS
1358 t->stats.semantic_match_miss++;
1359 #endif
1360 }
1361 return 0;
1362 }
1363
1364 static int
1365 fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1366 {
1367 struct trie *t = (struct trie *) tb->tb_data;
1368 int plen, ret = 0;
1369 struct node *n;
1370 struct tnode *pn;
1371 int pos, bits;
1372 t_key key=ntohl(flp->fl4_dst);
1373 int chopped_off;
1374 t_key cindex = 0;
1375 int current_prefix_length = KEYLENGTH;
1376 n = t->trie;
1377
1378 read_lock(&fib_lock);
1379 if(!n)
1380 goto failed;
1381
1382 #ifdef CONFIG_IP_FIB_TRIE_STATS
1383 t->stats.gets++;
1384 #endif
1385
1386 /* Just a leaf? */
1387 if (IS_LEAF(n)) {
1388 if( check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret) )
1389 goto found;
1390 goto failed;
1391 }
1392 pn = (struct tnode *) n;
1393 chopped_off = 0;
1394
1395 while (pn) {
1396
1397 pos = pn->pos;
1398 bits = pn->bits;
1399
1400 if(!chopped_off)
1401 cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
1402
1403 n = tnode_get_child(pn, cindex);
1404
1405 if (n == NULL) {
1406 #ifdef CONFIG_IP_FIB_TRIE_STATS
1407 t->stats.null_node_hit++;
1408 #endif
1409 goto backtrace;
1410 }
1411
1412 if (IS_TNODE(n)) {
1413 #define HL_OPTIMIZE
1414 #ifdef HL_OPTIMIZE
1415 struct tnode *cn = (struct tnode *)n;
1416 t_key node_prefix, key_prefix, pref_mismatch;
1417 int mp;
1418
1419 /*
1420 * It's a tnode, and we can do some extra checks here if we
1421 * like, to avoid descending into a dead-end branch.
1422 * This tnode is in the parent's child array at index
1423 * key[p_pos..p_pos+p_bits] but potentially with some bits
1424 * chopped off, so in reality the index may be just a
1425 * subprefix, padded with zero at the end.
1426 * We can also take a look at any skipped bits in this
1427 * tnode - everything up to p_pos is supposed to be ok,
1428 * and the non-chopped bits of the index (se previous
1429 * paragraph) are also guaranteed ok, but the rest is
1430 * considered unknown.
1431 *
1432 * The skipped bits are key[pos+bits..cn->pos].
1433 */
1434
1435 /* If current_prefix_length < pos+bits, we are already doing
1436 * actual prefix matching, which means everything from
1437 * pos+(bits-chopped_off) onward must be zero along some
1438 * branch of this subtree - otherwise there is *no* valid
1439 * prefix present. Here we can only check the skipped
1440 * bits. Remember, since we have already indexed into the
1441 * parent's child array, we know that the bits we chopped of
1442 * *are* zero.
1443 */
1444
1445 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1446
1447 if (current_prefix_length < pos+bits) {
1448 if (tkey_extract_bits(cn->key, current_prefix_length,
1449 cn->pos - current_prefix_length) != 0 ||
1450 !(cn->child[0]))
1451 goto backtrace;
1452 }
1453
1454 /*
1455 * If chopped_off=0, the index is fully validated and we
1456 * only need to look at the skipped bits for this, the new,
1457 * tnode. What we actually want to do is to find out if
1458 * these skipped bits match our key perfectly, or if we will
1459 * have to count on finding a matching prefix further down,
1460 * because if we do, we would like to have some way of
1461 * verifying the existence of such a prefix at this point.
1462 */
1463
1464 /* The only thing we can do at this point is to verify that
1465 * any such matching prefix can indeed be a prefix to our
1466 * key, and if the bits in the node we are inspecting that
1467 * do not match our key are not ZERO, this cannot be true.
1468 * Thus, find out where there is a mismatch (before cn->pos)
1469 * and verify that all the mismatching bits are zero in the
1470 * new tnode's key.
1471 */
1472
1473 /* Note: We aren't very concerned about the piece of the key
1474 * that precede pn->pos+pn->bits, since these have already been
1475 * checked. The bits after cn->pos aren't checked since these are
1476 * by definition "unknown" at this point. Thus, what we want to
1477 * see is if we are about to enter the "prefix matching" state,
1478 * and in that case verify that the skipped bits that will prevail
1479 * throughout this subtree are zero, as they have to be if we are
1480 * to find a matching prefix.
1481 */
1482
1483 node_prefix = MASK_PFX(cn->key, cn->pos);
1484 key_prefix = MASK_PFX(key, cn->pos);
1485 pref_mismatch = key_prefix^node_prefix;
1486 mp = 0;
1487
1488 /* In short: If skipped bits in this node do not match the search
1489 * key, enter the "prefix matching" state.directly.
1490 */
1491 if (pref_mismatch) {
1492 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1493 mp++;
1494 pref_mismatch = pref_mismatch <<1;
1495 }
1496 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1497
1498 if (key_prefix != 0)
1499 goto backtrace;
1500
1501 if (current_prefix_length >= cn->pos)
1502 current_prefix_length=mp;
1503 }
1504 #endif
1505 pn = (struct tnode *)n; /* Descend */
1506 chopped_off = 0;
1507 continue;
1508 }
1509 if (IS_LEAF(n)) {
1510 if( check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret))
1511 goto found;
1512 }
1513 backtrace:
1514 chopped_off++;
1515
1516 /* As zero don't change the child key (cindex) */
1517 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) {
1518 chopped_off++;
1519 }
1520
1521 /* Decrease current_... with bits chopped off */
1522 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1523 current_prefix_length = pn->pos + pn->bits - chopped_off;
1524
1525 /*
1526 * Either we do the actual chop off according or if we have
1527 * chopped off all bits in this tnode walk up to our parent.
1528 */
1529
1530 if(chopped_off <= pn->bits)
1531 cindex &= ~(1 << (chopped_off-1));
1532 else {
1533 if( NODE_PARENT(pn) == NULL)
1534 goto failed;
1535
1536 /* Get Child's index */
1537 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
1538 pn = NODE_PARENT(pn);
1539 chopped_off = 0;
1540
1541 #ifdef CONFIG_IP_FIB_TRIE_STATS
1542 t->stats.backtrack++;
1543 #endif
1544 goto backtrace;
1545 }
1546 }
1547 failed:
1548 ret = 1;
1549 found:
1550 read_unlock(&fib_lock);
1551 return ret;
1552 }
1553
1554 static int trie_leaf_remove(struct trie *t, t_key key)
1555 {
1556 t_key cindex;
1557 struct tnode *tp = NULL;
1558 struct node *n = t->trie;
1559 struct leaf *l;
1560
1561 if(trie_debug)
1562 printk("entering trie_leaf_remove(%p)\n", n);
1563
1564 /* Note that in the case skipped bits, those bits are *not* checked!
1565 * When we finish this, we will have NULL or a T_LEAF, and the
1566 * T_LEAF may or may not match our key.
1567 */
1568
1569 while (n != NULL && IS_TNODE(n)) {
1570 struct tnode *tn = (struct tnode *) n;
1571 check_tnode(tn);
1572 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1573
1574 if(n && NODE_PARENT(n) != tn) {
1575 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1576 BUG();
1577 }
1578 }
1579 l = (struct leaf *) n;
1580
1581 if(!n || !tkey_equals(l->key, key))
1582 return 0;
1583
1584 /*
1585 * Key found.
1586 * Remove the leaf and rebalance the tree
1587 */
1588
1589 t->revision++;
1590 t->size--;
1591
1592 tp = NODE_PARENT(n);
1593 tnode_free((struct tnode *) n);
1594
1595 if(tp) {
1596 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1597 put_child(t, (struct tnode *)tp, cindex, NULL);
1598 t->trie = trie_rebalance(t, tp);
1599 }
1600 else
1601 t->trie = NULL;
1602
1603 return 1;
1604 }
1605
1606 static int
1607 fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1608 struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
1609 {
1610 struct trie *t = (struct trie *) tb->tb_data;
1611 u32 key, mask;
1612 int plen = r->rtm_dst_len;
1613 u8 tos = r->rtm_tos;
1614 struct fib_alias *fa, *fa_to_delete;
1615 struct list_head *fa_head;
1616 struct leaf *l;
1617
1618 if (plen > 32)
1619 return -EINVAL;
1620
1621 key = 0;
1622 if (rta->rta_dst)
1623 memcpy(&key, rta->rta_dst, 4);
1624
1625 key = ntohl(key);
1626 mask = ntohl( inet_make_mask(plen) );
1627
1628 if(key & ~mask)
1629 return -EINVAL;
1630
1631 key = key & mask;
1632 l = fib_find_node(t, key);
1633
1634 if(!l)
1635 return -ESRCH;
1636
1637 fa_head = get_fa_head(l, plen);
1638 fa = fib_find_alias(fa_head, tos, 0);
1639
1640 if (!fa)
1641 return -ESRCH;
1642
1643 if (trie_debug)
1644 printk("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1645
1646 fa_to_delete = NULL;
1647 fa_head = fa->fa_list.prev;
1648 list_for_each_entry(fa, fa_head, fa_list) {
1649 struct fib_info *fi = fa->fa_info;
1650
1651 if (fa->fa_tos != tos)
1652 break;
1653
1654 if ((!r->rtm_type ||
1655 fa->fa_type == r->rtm_type) &&
1656 (r->rtm_scope == RT_SCOPE_NOWHERE ||
1657 fa->fa_scope == r->rtm_scope) &&
1658 (!r->rtm_protocol ||
1659 fi->fib_protocol == r->rtm_protocol) &&
1660 fib_nh_match(r, nlhdr, rta, fi) == 0) {
1661 fa_to_delete = fa;
1662 break;
1663 }
1664 }
1665
1666 if (fa_to_delete) {
1667 int kill_li = 0;
1668 struct leaf_info *li;
1669
1670 fa = fa_to_delete;
1671 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);
1672
1673 l = fib_find_node(t, key);
1674 li = find_leaf_info(&l->list, plen);
1675
1676 write_lock_bh(&fib_lock);
1677
1678 list_del(&fa->fa_list);
1679
1680 if(list_empty(fa_head)) {
1681 hlist_del(&li->hlist);
1682 kill_li = 1;
1683 }
1684 write_unlock_bh(&fib_lock);
1685
1686 if(kill_li)
1687 free_leaf_info(li);
1688
1689 if(hlist_empty(&l->list))
1690 trie_leaf_remove(t, key);
1691
1692 if (fa->fa_state & FA_S_ACCESSED)
1693 rt_cache_flush(-1);
1694
1695 fn_free_alias(fa);
1696 return 0;
1697 }
1698 return -ESRCH;
1699 }
1700
1701 static int trie_flush_list(struct trie *t, struct list_head *head)
1702 {
1703 struct fib_alias *fa, *fa_node;
1704 int found = 0;
1705
1706 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1707 struct fib_info *fi = fa->fa_info;
1708
1709 if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
1710
1711 write_lock_bh(&fib_lock);
1712 list_del(&fa->fa_list);
1713 write_unlock_bh(&fib_lock);
1714
1715 fn_free_alias(fa);
1716 found++;
1717 }
1718 }
1719 return found;
1720 }
1721
1722 static int trie_flush_leaf(struct trie *t, struct leaf *l)
1723 {
1724 int found = 0;
1725 struct hlist_head *lih = &l->list;
1726 struct hlist_node *node, *tmp;
1727 struct leaf_info *li = NULL;
1728
1729 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1730
1731 found += trie_flush_list(t, &li->falh);
1732
1733 if (list_empty(&li->falh)) {
1734
1735 write_lock_bh(&fib_lock);
1736 hlist_del(&li->hlist);
1737 write_unlock_bh(&fib_lock);
1738
1739 free_leaf_info(li);
1740 }
1741 }
1742 return found;
1743 }
1744
1745 static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1746 {
1747 struct node *c = (struct node *) thisleaf;
1748 struct tnode *p;
1749 int idx;
1750
1751 if(c == NULL) {
1752 if(t->trie == NULL)
1753 return NULL;
1754
1755 if (IS_LEAF(t->trie)) /* trie w. just a leaf */
1756 return (struct leaf *) t->trie;
1757
1758 p = (struct tnode*) t->trie; /* Start */
1759 }
1760 else
1761 p = (struct tnode *) NODE_PARENT(c);
1762 while (p) {
1763 int pos, last;
1764
1765 /* Find the next child of the parent */
1766 if(c)
1767 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1768 else
1769 pos = 0;
1770
1771 last = 1 << p->bits;
1772 for(idx = pos; idx < last ; idx++) {
1773 if( p->child[idx]) {
1774
1775 /* Decend if tnode */
1776
1777 while (IS_TNODE(p->child[idx])) {
1778 p = (struct tnode*) p->child[idx];
1779 idx = 0;
1780
1781 /* Rightmost non-NULL branch */
1782 if( p && IS_TNODE(p) )
1783 while ( p->child[idx] == NULL && idx < (1 << p->bits) ) idx++;
1784
1785 /* Done with this tnode? */
1786 if( idx >= (1 << p->bits) || p->child[idx] == NULL )
1787 goto up;
1788 }
1789 return (struct leaf*) p->child[idx];
1790 }
1791 }
1792 up:
1793 /* No more children go up one step */
1794 c = (struct node*) p;
1795 p = (struct tnode *) NODE_PARENT(p);
1796 }
1797 return NULL; /* Ready. Root of trie */
1798 }
1799
1800 static int fn_trie_flush(struct fib_table *tb)
1801 {
1802 struct trie *t = (struct trie *) tb->tb_data;
1803 struct leaf *ll = NULL, *l = NULL;
1804 int found = 0, h;
1805
1806 t->revision++;
1807
1808 for (h=0; (l = nextleaf(t, l)) != NULL; h++) {
1809 found += trie_flush_leaf(t, l);
1810
1811 if (ll && hlist_empty(&ll->list))
1812 trie_leaf_remove(t, ll->key);
1813 ll = l;
1814 }
1815
1816 if (ll && hlist_empty(&ll->list))
1817 trie_leaf_remove(t, ll->key);
1818
1819 if(trie_debug)
1820 printk("trie_flush found=%d\n", found);
1821 return found;
1822 }
1823
1824 static int trie_last_dflt=-1;
1825
1826 static void
1827 fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
1828 {
1829 struct trie *t = (struct trie *) tb->tb_data;
1830 int order, last_idx;
1831 struct fib_info *fi = NULL;
1832 struct fib_info *last_resort;
1833 struct fib_alias *fa = NULL;
1834 struct list_head *fa_head;
1835 struct leaf *l;
1836
1837 last_idx = -1;
1838 last_resort = NULL;
1839 order = -1;
1840
1841 read_lock(&fib_lock);
1842
1843 l = fib_find_node(t, 0);
1844 if(!l)
1845 goto out;
1846
1847 fa_head = get_fa_head(l, 0);
1848 if(!fa_head)
1849 goto out;
1850
1851 if (list_empty(fa_head))
1852 goto out;
1853
1854 list_for_each_entry(fa, fa_head, fa_list) {
1855 struct fib_info *next_fi = fa->fa_info;
1856
1857 if (fa->fa_scope != res->scope ||
1858 fa->fa_type != RTN_UNICAST)
1859 continue;
1860
1861 if (next_fi->fib_priority > res->fi->fib_priority)
1862 break;
1863 if (!next_fi->fib_nh[0].nh_gw ||
1864 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1865 continue;
1866 fa->fa_state |= FA_S_ACCESSED;
1867
1868 if (fi == NULL) {
1869 if (next_fi != res->fi)
1870 break;
1871 } else if (!fib_detect_death(fi, order, &last_resort,
1872 &last_idx, &trie_last_dflt)) {
1873 if (res->fi)
1874 fib_info_put(res->fi);
1875 res->fi = fi;
1876 atomic_inc(&fi->fib_clntref);
1877 trie_last_dflt = order;
1878 goto out;
1879 }
1880 fi = next_fi;
1881 order++;
1882 }
1883 if (order <= 0 || fi == NULL) {
1884 trie_last_dflt = -1;
1885 goto out;
1886 }
1887
1888 if (!fib_detect_death(fi, order, &last_resort, &last_idx, &trie_last_dflt)) {
1889 if (res->fi)
1890 fib_info_put(res->fi);
1891 res->fi = fi;
1892 atomic_inc(&fi->fib_clntref);
1893 trie_last_dflt = order;
1894 goto out;
1895 }
1896 if (last_idx >= 0) {
1897 if (res->fi)
1898 fib_info_put(res->fi);
1899 res->fi = last_resort;
1900 if (last_resort)
1901 atomic_inc(&last_resort->fib_clntref);
1902 }
1903 trie_last_dflt = last_idx;
1904 out:;
1905 read_unlock(&fib_lock);
1906 }
1907
1908 static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb,
1909 struct sk_buff *skb, struct netlink_callback *cb)
1910 {
1911 int i, s_i;
1912 struct fib_alias *fa;
1913
1914 u32 xkey=htonl(key);
1915
1916 s_i=cb->args[3];
1917 i = 0;
1918
1919 list_for_each_entry(fa, fah, fa_list) {
1920 if (i < s_i) {
1921 i++;
1922 continue;
1923 }
1924 if (fa->fa_info->fib_nh == NULL) {
1925 printk("Trie error _fib_nh=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
1926 i++;
1927 continue;
1928 }
1929 if (fa->fa_info == NULL) {
1930 printk("Trie error fa_info=NULL in fa[%d] k=%08x plen=%d\n", i, key, plen);
1931 i++;
1932 continue;
1933 }
1934
1935 if (fib_dump_info(skb, NETLINK_CB(cb->skb).pid,
1936 cb->nlh->nlmsg_seq,
1937 RTM_NEWROUTE,
1938 tb->tb_id,
1939 fa->fa_type,
1940 fa->fa_scope,
1941 &xkey,
1942 plen,
1943 fa->fa_tos,
1944 fa->fa_info, 0) < 0) {
1945 cb->args[3] = i;
1946 return -1;
1947 }
1948 i++;
1949 }
1950 cb->args[3]=i;
1951 return skb->len;
1952 }
1953
1954 static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1955 struct netlink_callback *cb)
1956 {
1957 int h, s_h;
1958 struct list_head *fa_head;
1959 struct leaf *l = NULL;
1960 s_h=cb->args[2];
1961
1962 for (h=0; (l = nextleaf(t, l)) != NULL; h++) {
1963
1964 if (h < s_h)
1965 continue;
1966 if (h > s_h)
1967 memset(&cb->args[3], 0,
1968 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1969
1970 fa_head = get_fa_head(l, plen);
1971
1972 if(!fa_head)
1973 continue;
1974
1975 if(list_empty(fa_head))
1976 continue;
1977
1978 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1979 cb->args[2]=h;
1980 return -1;
1981 }
1982 }
1983 cb->args[2]=h;
1984 return skb->len;
1985 }
1986
1987 static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb)
1988 {
1989 int m, s_m;
1990 struct trie *t = (struct trie *) tb->tb_data;
1991
1992 s_m = cb->args[1];
1993
1994 read_lock(&fib_lock);
1995 for (m=0; m<=32; m++) {
1996
1997 if (m < s_m)
1998 continue;
1999 if (m > s_m)
2000 memset(&cb->args[2], 0,
2001 sizeof(cb->args) - 2*sizeof(cb->args[0]));
2002
2003 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
2004 cb->args[1] = m;
2005 goto out;
2006 }
2007 }
2008 read_unlock(&fib_lock);
2009 cb->args[1] = m;
2010 return skb->len;
2011 out:
2012 read_unlock(&fib_lock);
2013 return -1;
2014 }
2015
2016 /* Fix more generic FIB names for init later */
2017
2018 #ifdef CONFIG_IP_MULTIPLE_TABLES
2019 struct fib_table * fib_hash_init(int id)
2020 #else
2021 struct fib_table * __init fib_hash_init(int id)
2022 #endif
2023 {
2024 struct fib_table *tb;
2025 struct trie *t;
2026
2027 if (fn_alias_kmem == NULL)
2028 fn_alias_kmem = kmem_cache_create("ip_fib_alias",
2029 sizeof(struct fib_alias),
2030 0, SLAB_HWCACHE_ALIGN,
2031 NULL, NULL);
2032
2033 tb = kmalloc(sizeof(struct fib_table) + sizeof(struct trie),
2034 GFP_KERNEL);
2035 if (tb == NULL)
2036 return NULL;
2037
2038 tb->tb_id = id;
2039 tb->tb_lookup = fn_trie_lookup;
2040 tb->tb_insert = fn_trie_insert;
2041 tb->tb_delete = fn_trie_delete;
2042 tb->tb_flush = fn_trie_flush;
2043 tb->tb_select_default = fn_trie_select_default;
2044 tb->tb_dump = fn_trie_dump;
2045 memset(tb->tb_data, 0, sizeof(struct trie));
2046
2047 t = (struct trie *) tb->tb_data;
2048
2049 trie_init(t);
2050
2051 if (id == RT_TABLE_LOCAL)
2052 trie_local=t;
2053 else if (id == RT_TABLE_MAIN)
2054 trie_main=t;
2055
2056 if (id == RT_TABLE_LOCAL)
2057 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
2058
2059 return tb;
2060 }
2061
2062 /* Trie dump functions */
2063
2064 static void putspace_seq(struct seq_file *seq, int n)
2065 {
2066 while (n--) seq_printf(seq, " ");
2067 }
2068
2069 static void printbin_seq(struct seq_file *seq, unsigned int v, int bits)
2070 {
2071 while (bits--)
2072 seq_printf(seq, "%s", (v & (1<<bits))?"1":"0");
2073 }
2074
2075 static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2076 int pend, int cindex, int bits)
2077 {
2078 putspace_seq(seq, indent);
2079 if (IS_LEAF(n))
2080 seq_printf(seq, "|");
2081 else
2082 seq_printf(seq, "+");
2083 if (bits) {
2084 seq_printf(seq, "%d/", cindex);
2085 printbin_seq(seq, cindex, bits);
2086 seq_printf(seq, ": ");
2087 }
2088 else
2089 seq_printf(seq, "<root>: ");
2090 seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n);
2091
2092 if (IS_LEAF(n))
2093 seq_printf(seq, "key=%d.%d.%d.%d\n",
2094 n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) % 256, n->key % 256);
2095 else {
2096 int plen=((struct tnode *)n)->pos;
2097 t_key prf=MASK_PFX(n->key, plen);
2098 seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
2099 prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf % 256, plen);
2100 }
2101 if (IS_LEAF(n)) {
2102 struct leaf *l=(struct leaf *)n;
2103 struct fib_alias *fa;
2104 int i;
2105 for (i=32; i>=0; i--)
2106 if(find_leaf_info(&l->list, i)) {
2107
2108 struct list_head *fa_head = get_fa_head(l, i);
2109
2110 if(!fa_head)
2111 continue;
2112
2113 if(list_empty(fa_head))
2114 continue;
2115
2116 putspace_seq(seq, indent+2);
2117 seq_printf(seq, "{/%d...dumping}\n", i);
2118
2119
2120 list_for_each_entry(fa, fa_head, fa_list) {
2121 putspace_seq(seq, indent+2);
2122 if (fa->fa_info->fib_nh == NULL) {
2123 seq_printf(seq, "Error _fib_nh=NULL\n");
2124 continue;
2125 }
2126 if (fa->fa_info == NULL) {
2127 seq_printf(seq, "Error fa_info=NULL\n");
2128 continue;
2129 }
2130
2131 seq_printf(seq, "{type=%d scope=%d TOS=%d}\n",
2132 fa->fa_type,
2133 fa->fa_scope,
2134 fa->fa_tos);
2135 }
2136 }
2137 }
2138 else if (IS_TNODE(n)) {
2139 struct tnode *tn=(struct tnode *)n;
2140 putspace_seq(seq, indent); seq_printf(seq, "| ");
2141 seq_printf(seq, "{key prefix=%08x/", tn->key&TKEY_GET_MASK(0, tn->pos));
2142 printbin_seq(seq, tkey_extract_bits(tn->key, 0, tn->pos), tn->pos);
2143 seq_printf(seq, "}\n");
2144 putspace_seq(seq, indent); seq_printf(seq, "| ");
2145 seq_printf(seq, "{pos=%d", tn->pos);
2146 seq_printf(seq, " (skip=%d bits)", tn->pos - pend);
2147 seq_printf(seq, " bits=%d (%u children)}\n", tn->bits, (1 << tn->bits));
2148 putspace_seq(seq, indent); seq_printf(seq, "| ");
2149 seq_printf(seq, "{empty=%d full=%d}\n", tn->empty_children, tn->full_children);
2150 }
2151 }
2152
2153 static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2154 {
2155 struct node *n=t->trie;
2156 int cindex=0;
2157 int indent=1;
2158 int pend=0;
2159 int depth = 0;
2160
2161 read_lock(&fib_lock);
2162
2163 seq_printf(seq, "------ trie_dump of t=%p ------\n", t);
2164 if (n) {
2165 printnode_seq(seq, indent, n, pend, cindex, 0);
2166 if (IS_TNODE(n)) {
2167 struct tnode *tn=(struct tnode *)n;
2168 pend = tn->pos+tn->bits;
2169 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2170 indent += 3;
2171 depth++;
2172
2173 while (tn && cindex < (1 << tn->bits)) {
2174 if (tn->child[cindex]) {
2175
2176 /* Got a child */
2177
2178 printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits);
2179 if (IS_LEAF(tn->child[cindex])) {
2180 cindex++;
2181
2182 }
2183 else {
2184 /*
2185 * New tnode. Decend one level
2186 */
2187
2188 depth++;
2189 n=tn->child[cindex];
2190 tn=(struct tnode *)n;
2191 pend=tn->pos+tn->bits;
2192 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2193 indent+=3;
2194 cindex=0;
2195 }
2196 }
2197 else
2198 cindex++;
2199
2200 /*
2201 * Test if we are done
2202 */
2203
2204 while (cindex >= (1 << tn->bits)) {
2205
2206 /*
2207 * Move upwards and test for root
2208 * pop off all traversed nodes
2209 */
2210
2211 if (NODE_PARENT(tn) == NULL) {
2212 tn = NULL;
2213 n = NULL;
2214 break;
2215 }
2216 else {
2217 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2218 tn = NODE_PARENT(tn);
2219 cindex++;
2220 n=(struct node *)tn;
2221 pend=tn->pos+tn->bits;
2222 indent-=3;
2223 depth--;
2224 }
2225 }
2226 }
2227 }
2228 else n = NULL;
2229 }
2230 else seq_printf(seq, "------ trie is empty\n");
2231
2232 read_unlock(&fib_lock);
2233 }
2234
2235 static struct trie_stat *trie_stat_new(void)
2236 {
2237 struct trie_stat *s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL);
2238 int i;
2239
2240 if(s) {
2241 s->totdepth = 0;
2242 s->maxdepth = 0;
2243 s->tnodes = 0;
2244 s->leaves = 0;
2245 s->nullpointers = 0;
2246
2247 for(i=0; i< MAX_CHILDS; i++)
2248 s->nodesizes[i] = 0;
2249 }
2250 return s;
2251 }
2252
2253 static struct trie_stat *trie_collect_stats(struct trie *t)
2254 {
2255 struct node *n=t->trie;
2256 struct trie_stat *s = trie_stat_new();
2257 int cindex = 0;
2258 int indent = 1;
2259 int pend = 0;
2260 int depth = 0;
2261
2262 read_lock(&fib_lock);
2263
2264 if (s) {
2265 if (n) {
2266 if (IS_TNODE(n)) {
2267 struct tnode *tn = (struct tnode *)n;
2268 pend=tn->pos+tn->bits;
2269 indent += 3;
2270 s->nodesizes[tn->bits]++;
2271 depth++;
2272
2273 while (tn && cindex < (1 << tn->bits)) {
2274 if (tn->child[cindex]) {
2275 /* Got a child */
2276
2277 if (IS_LEAF(tn->child[cindex])) {
2278 cindex++;
2279
2280 /* stats */
2281 if (depth > s->maxdepth)
2282 s->maxdepth = depth;
2283 s->totdepth += depth;
2284 s->leaves++;
2285 }
2286
2287 else {
2288 /*
2289 * New tnode. Decend one level
2290 */
2291
2292 s->tnodes++;
2293 s->nodesizes[tn->bits]++;
2294 depth++;
2295
2296 n = tn->child[cindex];
2297 tn = (struct tnode *)n;
2298 pend = tn->pos+tn->bits;
2299
2300 indent += 3;
2301 cindex = 0;
2302 }
2303 }
2304 else {
2305 cindex++;
2306 s->nullpointers++;
2307 }
2308
2309 /*
2310 * Test if we are done
2311 */
2312
2313 while (cindex >= (1 << tn->bits)) {
2314
2315 /*
2316 * Move upwards and test for root
2317 * pop off all traversed nodes
2318 */
2319
2320
2321 if (NODE_PARENT(tn) == NULL) {
2322 tn = NULL;
2323 n = NULL;
2324 break;
2325 }
2326 else {
2327 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2328 tn = NODE_PARENT(tn);
2329 cindex++;
2330 n = (struct node *)tn;
2331 pend=tn->pos+tn->bits;
2332 indent -= 3;
2333 depth--;
2334 }
2335 }
2336 }
2337 }
2338 else n = NULL;
2339 }
2340 }
2341
2342 read_unlock(&fib_lock);
2343 return s;
2344 }
2345
2346 #ifdef CONFIG_PROC_FS
2347
2348 static struct fib_alias *fib_triestat_get_first(struct seq_file *seq)
2349 {
2350 return NULL;
2351 }
2352
2353 static struct fib_alias *fib_triestat_get_next(struct seq_file *seq)
2354 {
2355 return NULL;
2356 }
2357
2358 static void *fib_triestat_seq_start(struct seq_file *seq, loff_t *pos)
2359 {
2360 void *v = NULL;
2361
2362 if (ip_fib_main_table)
2363 v = *pos ? fib_triestat_get_next(seq) : SEQ_START_TOKEN;
2364 return v;
2365 }
2366
2367 static void *fib_triestat_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2368 {
2369 ++*pos;
2370 return v == SEQ_START_TOKEN ? fib_triestat_get_first(seq) : fib_triestat_get_next(seq);
2371 }
2372
2373 static void fib_triestat_seq_stop(struct seq_file *seq, void *v)
2374 {
2375
2376 }
2377
2378 /*
2379 * This outputs /proc/net/fib_triestats
2380 *
2381 * It always works in backward compatibility mode.
2382 * The format of the file is not supposed to be changed.
2383 */
2384
2385 static void collect_and_show(struct trie *t, struct seq_file *seq)
2386 {
2387 int bytes = 0; /* How many bytes are used, a ref is 4 bytes */
2388 int i, max, pointers;
2389 struct trie_stat *stat;
2390 int avdepth;
2391
2392 stat = trie_collect_stats(t);
2393
2394 bytes=0;
2395 seq_printf(seq, "trie=%p\n", t);
2396
2397 if (stat) {
2398 if (stat->leaves)
2399 avdepth=stat->totdepth*100 / stat->leaves;
2400 else
2401 avdepth=0;
2402 seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
2403 seq_printf(seq, "Max depth: %4d\n", stat->maxdepth);
2404
2405 seq_printf(seq, "Leaves: %d\n", stat->leaves);
2406 bytes += sizeof(struct leaf) * stat->leaves;
2407 seq_printf(seq, "Internal nodes: %d\n", stat->tnodes);
2408 bytes += sizeof(struct tnode) * stat->tnodes;
2409
2410 max = MAX_CHILDS-1;
2411
2412 while (max >= 0 && stat->nodesizes[max] == 0)
2413 max--;
2414 pointers = 0;
2415
2416 for (i = 1; i <= max; i++)
2417 if (stat->nodesizes[i] != 0) {
2418 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
2419 pointers += (1<<i) * stat->nodesizes[i];
2420 }
2421 seq_printf(seq, "\n");
2422 seq_printf(seq, "Pointers: %d\n", pointers);
2423 bytes += sizeof(struct node *) * pointers;
2424 seq_printf(seq, "Null ptrs: %d\n", stat->nullpointers);
2425 seq_printf(seq, "Total size: %d kB\n", bytes / 1024);
2426
2427 kfree(stat);
2428 }
2429
2430 #ifdef CONFIG_IP_FIB_TRIE_STATS
2431 seq_printf(seq, "Counters:\n---------\n");
2432 seq_printf(seq,"gets = %d\n", t->stats.gets);
2433 seq_printf(seq,"backtracks = %d\n", t->stats.backtrack);
2434 seq_printf(seq,"semantic match passed = %d\n", t->stats.semantic_match_passed);
2435 seq_printf(seq,"semantic match miss = %d\n", t->stats.semantic_match_miss);
2436 seq_printf(seq,"null node hit= %d\n", t->stats.null_node_hit);
2437 seq_printf(seq,"skipped node resize = %d\n", t->stats.resize_node_skipped);
2438 #ifdef CLEAR_STATS
2439 memset(&(t->stats), 0, sizeof(t->stats));
2440 #endif
2441 #endif /* CONFIG_IP_FIB_TRIE_STATS */
2442 }
2443
2444 static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2445 {
2446 char bf[128];
2447
2448 if (v == SEQ_START_TOKEN) {
2449 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2450 sizeof(struct leaf), sizeof(struct tnode));
2451 if (trie_local)
2452 collect_and_show(trie_local, seq);
2453
2454 if (trie_main)
2455 collect_and_show(trie_main, seq);
2456 }
2457 else {
2458 snprintf(bf, sizeof(bf),
2459 "*\t%08X\t%08X", 200, 400);
2460
2461 seq_printf(seq, "%-127s\n", bf);
2462 }
2463 return 0;
2464 }
2465
2466 static struct seq_operations fib_triestat_seq_ops = {
2467 .start = fib_triestat_seq_start,
2468 .next = fib_triestat_seq_next,
2469 .stop = fib_triestat_seq_stop,
2470 .show = fib_triestat_seq_show,
2471 };
2472
2473 static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2474 {
2475 struct seq_file *seq;
2476 int rc = -ENOMEM;
2477
2478 rc = seq_open(file, &fib_triestat_seq_ops);
2479 if (rc)
2480 goto out_kfree;
2481
2482 seq = file->private_data;
2483 out:
2484 return rc;
2485 out_kfree:
2486 goto out;
2487 }
2488
2489 static struct file_operations fib_triestat_seq_fops = {
2490 .owner = THIS_MODULE,
2491 .open = fib_triestat_seq_open,
2492 .read = seq_read,
2493 .llseek = seq_lseek,
2494 .release = seq_release_private,
2495 };
2496
2497 int __init fib_stat_proc_init(void)
2498 {
2499 if (!proc_net_fops_create("fib_triestat", S_IRUGO, &fib_triestat_seq_fops))
2500 return -ENOMEM;
2501 return 0;
2502 }
2503
2504 void __init fib_stat_proc_exit(void)
2505 {
2506 proc_net_remove("fib_triestat");
2507 }
2508
2509 static struct fib_alias *fib_trie_get_first(struct seq_file *seq)
2510 {
2511 return NULL;
2512 }
2513
2514 static struct fib_alias *fib_trie_get_next(struct seq_file *seq)
2515 {
2516 return NULL;
2517 }
2518
2519 static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2520 {
2521 void *v = NULL;
2522
2523 if (ip_fib_main_table)
2524 v = *pos ? fib_trie_get_next(seq) : SEQ_START_TOKEN;
2525 return v;
2526 }
2527
2528 static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2529 {
2530 ++*pos;
2531 return v == SEQ_START_TOKEN ? fib_trie_get_first(seq) : fib_trie_get_next(seq);
2532 }
2533
2534 static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2535 {
2536
2537 }
2538
2539 /*
2540 * This outputs /proc/net/fib_trie.
2541 *
2542 * It always works in backward compatibility mode.
2543 * The format of the file is not supposed to be changed.
2544 */
2545
2546 static int fib_trie_seq_show(struct seq_file *seq, void *v)
2547 {
2548 char bf[128];
2549
2550 if (v == SEQ_START_TOKEN) {
2551 if (trie_local)
2552 trie_dump_seq(seq, trie_local);
2553
2554 if (trie_main)
2555 trie_dump_seq(seq, trie_main);
2556 }
2557
2558 else {
2559 snprintf(bf, sizeof(bf),
2560 "*\t%08X\t%08X", 200, 400);
2561 seq_printf(seq, "%-127s\n", bf);
2562 }
2563
2564 return 0;
2565 }
2566
2567 static struct seq_operations fib_trie_seq_ops = {
2568 .start = fib_trie_seq_start,
2569 .next = fib_trie_seq_next,
2570 .stop = fib_trie_seq_stop,
2571 .show = fib_trie_seq_show,
2572 };
2573
2574 static int fib_trie_seq_open(struct inode *inode, struct file *file)
2575 {
2576 struct seq_file *seq;
2577 int rc = -ENOMEM;
2578
2579 rc = seq_open(file, &fib_trie_seq_ops);
2580 if (rc)
2581 goto out_kfree;
2582
2583 seq = file->private_data;
2584 out:
2585 return rc;
2586 out_kfree:
2587 goto out;
2588 }
2589
2590 static struct file_operations fib_trie_seq_fops = {
2591 .owner = THIS_MODULE,
2592 .open = fib_trie_seq_open,
2593 .read = seq_read,
2594 .llseek = seq_lseek,
2595 .release = seq_release_private,
2596 };
2597
2598 int __init fib_proc_init(void)
2599 {
2600 if (!proc_net_fops_create("fib_trie", S_IRUGO, &fib_trie_seq_fops))
2601 return -ENOMEM;
2602 return 0;
2603 }
2604
2605 void __init fib_proc_exit(void)
2606 {
2607 proc_net_remove("fib_trie");
2608 }
2609
2610 #endif /* CONFIG_PROC_FS */
Linux kernel - Deliverables
This page took 0.086574 seconds and 6 git commands to generate.