aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
authorOlof Johansson <olof@lixom.net>2005-08-09 23:24:39 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2005-08-29 18:53:52 -0400
commit91b9a277fc4d207249e459a455abf804ebb5499d (patch)
treea9e150feeec7788e59a9585e935189325a32e043 /net/ipv4/fib_trie.c
parent7663f18807805f02608457af8e2f59eee5d910fd (diff)
[IPV4]: FIB Trie cleanups.
Below is a patch that cleans up some of this, supposedly without changing any behaviour: * Whitespace cleanups * Introduce DBG() * BUG_ON() instead of if () { BUG(); } * Remove some of the deep nesting to make the code flow more comprehensible * Some mask operations were simplified Signed-off-by: Olof Johansson <olof@lixom.net> Signed-off-by: Robert Olsson <robert.olsson@its.uu.se> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c1237
1 files changed, 592 insertions, 645 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 45efd5f4741b..6f818cc7efd0 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -89,27 +89,27 @@ typedef unsigned int t_key;
89#define T_TNODE 0 89#define T_TNODE 0
90#define T_LEAF 1 90#define T_LEAF 1
91#define NODE_TYPE_MASK 0x1UL 91#define NODE_TYPE_MASK 0x1UL
92#define NODE_PARENT(_node) \ 92#define NODE_PARENT(node) \
93 ((struct tnode *)((_node)->_parent & ~NODE_TYPE_MASK)) 93 ((struct tnode *)((node)->parent & ~NODE_TYPE_MASK))
94#define NODE_SET_PARENT(_node, _ptr) \ 94#define NODE_SET_PARENT(node, ptr) \
95 ((_node)->_parent = (((unsigned long)(_ptr)) | \ 95 ((node)->parent = (((unsigned long)(ptr)) | \
96 ((_node)->_parent & NODE_TYPE_MASK))) 96 ((node)->parent & NODE_TYPE_MASK)))
97#define NODE_INIT_PARENT(_node, _type) \ 97#define NODE_INIT_PARENT(node, type) \
98 ((_node)->_parent = (_type)) 98 ((node)->parent = (type))
99#define NODE_TYPE(_node) \ 99#define NODE_TYPE(node) \
100 ((_node)->_parent & NODE_TYPE_MASK) 100 ((node)->parent & NODE_TYPE_MASK)
101 101
102#define IS_TNODE(n) (!(n->_parent & T_LEAF)) 102#define IS_TNODE(n) (!(n->parent & T_LEAF))
103#define IS_LEAF(n) (n->_parent & T_LEAF) 103#define IS_LEAF(n) (n->parent & T_LEAF)
104 104
105struct node { 105struct node {
106 t_key key; 106 t_key key;
107 unsigned long _parent; 107 unsigned long parent;
108}; 108};
109 109
110struct leaf { 110struct leaf {
111 t_key key; 111 t_key key;
112 unsigned long _parent; 112 unsigned long parent;
113 struct hlist_head list; 113 struct hlist_head list;
114}; 114};
115 115
@@ -120,13 +120,13 @@ struct leaf_info {
120}; 120};
121 121
122struct tnode { 122struct tnode {
123 t_key key; 123 t_key key;
124 unsigned long _parent; 124 unsigned long parent;
125 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */ 125 unsigned short pos:5; /* 2log(KEYLENGTH) bits needed */
126 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */ 126 unsigned short bits:5; /* 2log(KEYLENGTH) bits needed */
127 unsigned short full_children; /* KEYLENGTH bits needed */ 127 unsigned short full_children; /* KEYLENGTH bits needed */
128 unsigned short empty_children; /* KEYLENGTH bits needed */ 128 unsigned short empty_children; /* KEYLENGTH bits needed */
129 struct node *child[0]; 129 struct node *child[0];
130}; 130};
131 131
132#ifdef CONFIG_IP_FIB_TRIE_STATS 132#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -150,16 +150,18 @@ struct trie_stat {
150}; 150};
151 151
152struct trie { 152struct trie {
153 struct node *trie; 153 struct node *trie;
154#ifdef CONFIG_IP_FIB_TRIE_STATS 154#ifdef CONFIG_IP_FIB_TRIE_STATS
155 struct trie_use_stats stats; 155 struct trie_use_stats stats;
156#endif 156#endif
157 int size; 157 int size;
158 unsigned int revision; 158 unsigned int revision;
159}; 159};
160 160
161static int trie_debug = 0; 161static int trie_debug = 0;
162 162
163#define DBG(x...) do { if (trie_debug) printk(x); } while (0)
164
163static int tnode_full(struct tnode *tn, struct node *n); 165static int tnode_full(struct tnode *tn, struct node *n);
164static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); 166static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
165static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); 167static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
@@ -171,56 +173,31 @@ static void tnode_free(struct tnode *tn);
171static void trie_dump_seq(struct seq_file *seq, struct trie *t); 173static void trie_dump_seq(struct seq_file *seq, struct trie *t);
172extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio); 174extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio);
173extern int fib_detect_death(struct fib_info *fi, int order, 175extern int fib_detect_death(struct fib_info *fi, int order,
174 struct fib_info **last_resort, int *last_idx, int *dflt); 176 struct fib_info **last_resort, int *last_idx, int *dflt);
175 177
176extern void rtmsg_fib(int event, u32 key, struct fib_alias *fa, int z, int tb_id, 178extern 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); 179 struct nlmsghdr *n, struct netlink_skb_parms *req);
178 180
179static kmem_cache_t *fn_alias_kmem; 181static kmem_cache_t *fn_alias_kmem;
180static struct trie *trie_local = NULL, *trie_main = NULL; 182static struct trie *trie_local = NULL, *trie_main = NULL;
181 183
182static void trie_bug(char *err)
183{
184 printk("Trie Bug: %s\n", err);
185 BUG();
186}
187
188static inline struct node *tnode_get_child(struct tnode *tn, int i) 184static inline struct node *tnode_get_child(struct tnode *tn, int i)
189{ 185{
190 if (i >= 1<<tn->bits) 186 BUG_ON(i >= 1 << tn->bits);
191 trie_bug("tnode_get_child");
192 187
193 return tn->child[i]; 188 return tn->child[i];
194} 189}
195 190
196static inline int tnode_child_length(struct tnode *tn) 191static inline int tnode_child_length(struct tnode *tn)
197{ 192{
198 return 1<<tn->bits; 193 return 1 << tn->bits;
199} 194}
200 195
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
219static inline t_key tkey_extract_bits(t_key a, int offset, int bits) 196static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
220{ 197{
221 if (offset < KEYLENGTH) 198 if (offset < KEYLENGTH)
222 return ((t_key)(a << offset)) >> (KEYLENGTH - bits); 199 return ((t_key)(a << offset)) >> (KEYLENGTH - bits);
223 else 200 else
224 return 0; 201 return 0;
225} 202}
226 203
@@ -233,8 +210,8 @@ static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
233{ 210{
234 if (bits == 0 || offset >= KEYLENGTH) 211 if (bits == 0 || offset >= KEYLENGTH)
235 return 1; 212 return 1;
236 bits = bits > KEYLENGTH ? KEYLENGTH : bits; 213 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
237 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0; 214 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
238} 215}
239 216
240static inline int tkey_mismatch(t_key a, int offset, t_key b) 217static inline int tkey_mismatch(t_key a, int offset, t_key b)
@@ -249,7 +226,7 @@ static inline int tkey_mismatch(t_key a, int offset, t_key b)
249 return i; 226 return i;
250} 227}
251 228
252/* Candiate for fib_semantics */ 229/* Candidate for fib_semantics */
253 230
254static void fn_free_alias(struct fib_alias *fa) 231static void fn_free_alias(struct fib_alias *fa)
255{ 232{
@@ -295,7 +272,7 @@ static void fn_free_alias(struct fib_alias *fa)
295 tp->pos = 7 272 tp->pos = 7
296 tp->bits = 3 273 tp->bits = 3
297 n->pos = 15 274 n->pos = 15
298 n->bits=4 275 n->bits = 4
299 276
300 First, let's just ignore the bits that come before the parent tp, that is 277 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 278 the bits from 0 to (tp->pos-1). They are *known* but at this point we do
@@ -343,10 +320,13 @@ static struct leaf *leaf_new(void)
343static struct leaf_info *leaf_info_new(int plen) 320static struct leaf_info *leaf_info_new(int plen)
344{ 321{
345 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL); 322 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
346 if (li) { 323
347 li->plen = plen; 324 if (!li)
348 INIT_LIST_HEAD(&li->falh); 325 return NULL;
349 } 326
327 li->plen = plen;
328 INIT_LIST_HEAD(&li->falh);
329
350 return li; 330 return li;
351} 331}
352 332
@@ -373,7 +353,7 @@ static struct tnode *tnode_alloc(unsigned int size)
373static void __tnode_free(struct tnode *tn) 353static void __tnode_free(struct tnode *tn)
374{ 354{
375 unsigned int size = sizeof(struct tnode) + 355 unsigned int size = sizeof(struct tnode) +
376 (1<<tn->bits) * sizeof(struct node *); 356 (1 << tn->bits) * sizeof(struct node *);
377 357
378 if (size <= PAGE_SIZE) 358 if (size <= PAGE_SIZE)
379 kfree(tn); 359 kfree(tn);
@@ -387,7 +367,7 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
387 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *); 367 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
388 struct tnode *tn = tnode_alloc(sz); 368 struct tnode *tn = tnode_alloc(sz);
389 369
390 if (tn) { 370 if (tn) {
391 memset(tn, 0, sz); 371 memset(tn, 0, sz);
392 NODE_INIT_PARENT(tn, T_TNODE); 372 NODE_INIT_PARENT(tn, T_TNODE);
393 tn->pos = pos; 373 tn->pos = pos;
@@ -397,29 +377,21 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
397 tn->empty_children = 1<<bits; 377 tn->empty_children = 1<<bits;
398 } 378 }
399 379
400 if (trie_debug > 0) 380 DBG("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode),
401 printk("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode), 381 (unsigned int) (sizeof(struct node) * 1<<bits));
402 (unsigned int) (sizeof(struct node) * 1<<bits));
403 return tn; 382 return tn;
404} 383}
405 384
406static void tnode_free(struct tnode *tn) 385static void tnode_free(struct tnode *tn)
407{ 386{
408 if (!tn) { 387 BUG_ON(!tn);
409 trie_bug("tnode_free\n"); 388
410 }
411 if (IS_LEAF(tn)) { 389 if (IS_LEAF(tn)) {
412 free_leaf((struct leaf *)tn); 390 free_leaf((struct leaf *)tn);
413 if (trie_debug > 0 ) 391 DBG("FL %p \n", tn);
414 printk("FL %p \n", tn); 392 } else {
415 }
416 else if (IS_TNODE(tn)) {
417 __tnode_free(tn); 393 __tnode_free(tn);
418 if (trie_debug > 0 ) 394 DBG("FT %p \n", tn);
419 printk("FT %p \n", tn);
420 }
421 else {
422 trie_bug("tnode_free\n");
423 } 395 }
424} 396}
425 397
@@ -453,7 +425,7 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int w
453 425
454 if (i >= 1<<tn->bits) { 426 if (i >= 1<<tn->bits) {
455 printk("bits=%d, i=%d\n", tn->bits, i); 427 printk("bits=%d, i=%d\n", tn->bits, i);
456 trie_bug("tnode_put_child_reorg bits"); 428 BUG();
457 } 429 }
458 write_lock_bh(&fib_lock); 430 write_lock_bh(&fib_lock);
459 chi = tn->child[i]; 431 chi = tn->child[i];
@@ -465,15 +437,15 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int w
465 tn->empty_children--; 437 tn->empty_children--;
466 438
467 /* update fullChildren */ 439 /* update fullChildren */
468 if (wasfull == -1) 440 if (wasfull == -1)
469 wasfull = tnode_full(tn, chi); 441 wasfull = tnode_full(tn, chi);
470 442
471 isfull = tnode_full(tn, n); 443 isfull = tnode_full(tn, n);
472 if (wasfull && !isfull) 444 if (wasfull && !isfull)
473 tn->full_children--; 445 tn->full_children--;
474
475 else if (!wasfull && isfull) 446 else if (!wasfull && isfull)
476 tn->full_children++; 447 tn->full_children++;
448
477 if (n) 449 if (n)
478 NODE_SET_PARENT(n, tn); 450 NODE_SET_PARENT(n, tn);
479 451
@@ -489,9 +461,8 @@ static struct node *resize(struct trie *t, struct tnode *tn)
489 if (!tn) 461 if (!tn)
490 return NULL; 462 return NULL;
491 463
492 if (trie_debug) 464 DBG("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
493 printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 465 tn, inflate_threshold, halve_threshold);
494 tn, inflate_threshold, halve_threshold);
495 466
496 /* No children */ 467 /* No children */
497 if (tn->empty_children == tnode_child_length(tn)) { 468 if (tn->empty_children == tnode_child_length(tn)) {
@@ -501,20 +472,21 @@ static struct node *resize(struct trie *t, struct tnode *tn)
501 /* One child */ 472 /* One child */
502 if (tn->empty_children == tnode_child_length(tn) - 1) 473 if (tn->empty_children == tnode_child_length(tn) - 1)
503 for (i = 0; i < tnode_child_length(tn); i++) { 474 for (i = 0; i < tnode_child_length(tn); i++) {
475 struct node *n;
504 476
505 write_lock_bh(&fib_lock); 477 write_lock_bh(&fib_lock);
506 if (tn->child[i] != NULL) { 478 n = tn->child[i];
507 479 if (!n) {
508 /* compress one level */
509 struct node *n = tn->child[i];
510 if (n)
511 NODE_INIT_PARENT(n, NODE_TYPE(n));
512
513 write_unlock_bh(&fib_lock); 480 write_unlock_bh(&fib_lock);
514 tnode_free(tn); 481 continue;
515 return n;
516 } 482 }
483
484 /* compress one level */
485 NODE_INIT_PARENT(n, NODE_TYPE(n));
486
517 write_unlock_bh(&fib_lock); 487 write_unlock_bh(&fib_lock);
488 tnode_free(tn);
489 return n;
518 } 490 }
519 /* 491 /*
520 * Double as long as the resulting node has a number of 492 * Double as long as the resulting node has a number of
@@ -566,16 +538,16 @@ static struct node *resize(struct trie *t, struct tnode *tn)
566 * 538 *
567 * expand not_to_be_doubled and to_be_doubled, and shorten: 539 * expand not_to_be_doubled and to_be_doubled, and shorten:
568 * 100 * (tnode_child_length(tn) - tn->empty_children + 540 * 100 * (tnode_child_length(tn) - tn->empty_children +
569 * tn->full_children ) >= inflate_threshold * new_child_length 541 * tn->full_children) >= inflate_threshold * new_child_length
570 * 542 *
571 * expand new_child_length: 543 * expand new_child_length:
572 * 100 * (tnode_child_length(tn) - tn->empty_children + 544 * 100 * (tnode_child_length(tn) - tn->empty_children +
573 * tn->full_children ) >= 545 * tn->full_children) >=
574 * inflate_threshold * tnode_child_length(tn) * 2 546 * inflate_threshold * tnode_child_length(tn) * 2
575 * 547 *
576 * shorten again: 548 * shorten again:
577 * 50 * (tn->full_children + tnode_child_length(tn) - 549 * 50 * (tn->full_children + tnode_child_length(tn) -
578 * tn->empty_children ) >= inflate_threshold * 550 * tn->empty_children) >= inflate_threshold *
579 * tnode_child_length(tn) 551 * tnode_child_length(tn)
580 * 552 *
581 */ 553 */
@@ -624,20 +596,23 @@ static struct node *resize(struct trie *t, struct tnode *tn)
624 596
625 if (tn->empty_children == tnode_child_length(tn) - 1) 597 if (tn->empty_children == tnode_child_length(tn) - 1)
626 for (i = 0; i < tnode_child_length(tn); i++) { 598 for (i = 0; i < tnode_child_length(tn); i++) {
627 599 struct node *n;
628 write_lock_bh(&fib_lock);
629 if (tn->child[i] != NULL) {
630 /* compress one level */
631 struct node *n = tn->child[i];
632 600
633 if (n) 601 write_lock_bh(&fib_lock);
634 NODE_INIT_PARENT(n, NODE_TYPE(n));
635 602
603 n = tn->child[i];
604 if (!n) {
636 write_unlock_bh(&fib_lock); 605 write_unlock_bh(&fib_lock);
637 tnode_free(tn); 606 continue;
638 return n;
639 } 607 }
608
609 /* compress one level */
610
611 NODE_INIT_PARENT(n, NODE_TYPE(n));
612
640 write_unlock_bh(&fib_lock); 613 write_unlock_bh(&fib_lock);
614 tnode_free(tn);
615 return n;
641 } 616 }
642 617
643 return (struct node *) tn; 618 return (struct node *) tn;
@@ -650,8 +625,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
650 int olen = tnode_child_length(tn); 625 int olen = tnode_child_length(tn);
651 int i; 626 int i;
652 627
653 if (trie_debug) 628 DBG("In inflate\n");
654 printk("In inflate\n");
655 629
656 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); 630 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
657 631
@@ -666,8 +640,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
666 * fails. In case of failure we return the oldnode and inflate 640 * fails. In case of failure we return the oldnode and inflate
667 * of tnode is ignored. 641 * of tnode is ignored.
668 */ 642 */
669 643
670 for(i = 0; i < olen; i++) { 644 for (i = 0; i < olen; i++) {
671 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i); 645 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
672 646
673 if (inode && 647 if (inode &&
@@ -675,7 +649,6 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
675 inode->pos == oldtnode->pos + oldtnode->bits && 649 inode->pos == oldtnode->pos + oldtnode->bits &&
676 inode->bits > 1) { 650 inode->bits > 1) {
677 struct tnode *left, *right; 651 struct tnode *left, *right;
678
679 t_key m = TKEY_GET_MASK(inode->pos, 1); 652 t_key m = TKEY_GET_MASK(inode->pos, 1);
680 653
681 left = tnode_new(inode->key&(~m), inode->pos + 1, 654 left = tnode_new(inode->key&(~m), inode->pos + 1,
@@ -685,7 +658,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
685 *err = -ENOMEM; 658 *err = -ENOMEM;
686 break; 659 break;
687 } 660 }
688 661
689 right = tnode_new(inode->key|m, inode->pos + 1, 662 right = tnode_new(inode->key|m, inode->pos + 1,
690 inode->bits - 1); 663 inode->bits - 1);
691 664
@@ -703,18 +676,20 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
703 int size = tnode_child_length(tn); 676 int size = tnode_child_length(tn);
704 int j; 677 int j;
705 678
706 for(j = 0; j < size; j++) 679 for (j = 0; j < size; j++)
707 if (tn->child[j]) 680 if (tn->child[j])
708 tnode_free((struct tnode *)tn->child[j]); 681 tnode_free((struct tnode *)tn->child[j]);
709 682
710 tnode_free(tn); 683 tnode_free(tn);
711 684
712 *err = -ENOMEM; 685 *err = -ENOMEM;
713 return oldtnode; 686 return oldtnode;
714 } 687 }
715 688
716 for(i = 0; i < olen; i++) { 689 for (i = 0; i < olen; i++) {
717 struct node *node = tnode_get_child(oldtnode, i); 690 struct node *node = tnode_get_child(oldtnode, i);
691 struct tnode *left, *right;
692 int size, j;
718 693
719 /* An empty child */ 694 /* An empty child */
720 if (node == NULL) 695 if (node == NULL)
@@ -740,56 +715,51 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
740 put_child(t, tn, 2*i+1, inode->child[1]); 715 put_child(t, tn, 2*i+1, inode->child[1]);
741 716
742 tnode_free(inode); 717 tnode_free(inode);
718 continue;
743 } 719 }
744 720
745 /* An internal node with more than two children */ 721 /* An internal node with more than two children */
746 else { 722
747 struct tnode *left, *right; 723 /* We will replace this node 'inode' with two new
748 int size, j; 724 * ones, 'left' and 'right', each with half of the
749 725 * original children. The two new nodes will have
750 /* We will replace this node 'inode' with two new 726 * a position one bit further down the key and this
751 * ones, 'left' and 'right', each with half of the 727 * means that the "significant" part of their keys
752 * original children. The two new nodes will have 728 * (see the discussion near the top of this file)
753 * a position one bit further down the key and this 729 * will differ by one bit, which will be "0" in
754 * means that the "significant" part of their keys 730 * left's key and "1" in right's key. Since we are
755 * (see the discussion near the top of this file) 731 * moving the key position by one step, the bit that
756 * will differ by one bit, which will be "0" in 732 * we are moving away from - the bit at position
757 * left's key and "1" in right's key. Since we are 733 * (inode->pos) - is the one that will differ between
758 * moving the key position by one step, the bit that 734 * left and right. So... we synthesize that bit in the
759 * we are moving away from - the bit at position 735 * two new keys.
760 * (inode->pos) - is the one that will differ between 736 * The mask 'm' below will be a single "one" bit at
761 * left and right. So... we synthesize that bit in the 737 * the position (inode->pos)
762 * two new keys. 738 */
763 * The mask 'm' below will be a single "one" bit at
764 * the position (inode->pos)
765 */
766
767 /* Use the old key, but set the new significant
768 * bit to zero.
769 */
770 739
771 left = (struct tnode *) tnode_get_child(tn, 2*i); 740 /* Use the old key, but set the new significant
772 put_child(t, tn, 2*i, NULL); 741 * bit to zero.
742 */
773 743
774 if (!left) 744 left = (struct tnode *) tnode_get_child(tn, 2*i);
775 BUG(); 745 put_child(t, tn, 2*i, NULL);
776 746
777 right = (struct tnode *) tnode_get_child(tn, 2*i+1); 747 BUG_ON(!left);
778 put_child(t, tn, 2*i+1, NULL);
779 748
780 if (!right) 749 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
781 BUG(); 750 put_child(t, tn, 2*i+1, NULL);
782 751
783 size = tnode_child_length(left); 752 BUG_ON(!right);
784 for(j = 0; j < size; j++) {
785 put_child(t, left, j, inode->child[j]);
786 put_child(t, right, j, inode->child[j + size]);
787 }
788 put_child(t, tn, 2*i, resize(t, left));
789 put_child(t, tn, 2*i+1, resize(t, right));
790 753
791 tnode_free(inode); 754 size = tnode_child_length(left);
755 for (j = 0; j < size; j++) {
756 put_child(t, left, j, inode->child[j]);
757 put_child(t, right, j, inode->child[j + size]);
792 } 758 }
759 put_child(t, tn, 2*i, resize(t, left));
760 put_child(t, tn, 2*i+1, resize(t, right));
761
762 tnode_free(inode);
793 } 763 }
794 tnode_free(oldtnode); 764 tnode_free(oldtnode);
795 return tn; 765 return tn;
@@ -802,7 +772,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
802 int i; 772 int i;
803 int olen = tnode_child_length(tn); 773 int olen = tnode_child_length(tn);
804 774
805 if (trie_debug) printk("In halve\n"); 775 DBG("In halve\n");
806 776
807 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); 777 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
808 778
@@ -818,7 +788,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
818 * of tnode is ignored. 788 * of tnode is ignored.
819 */ 789 */
820 790
821 for(i = 0; i < olen; i += 2) { 791 for (i = 0; i < olen; i += 2) {
822 left = tnode_get_child(oldtnode, i); 792 left = tnode_get_child(oldtnode, i);
823 right = tnode_get_child(oldtnode, i+1); 793 right = tnode_get_child(oldtnode, i+1);
824 794
@@ -839,17 +809,19 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
839 int size = tnode_child_length(tn); 809 int size = tnode_child_length(tn);
840 int j; 810 int j;
841 811
842 for(j = 0; j < size; j++) 812 for (j = 0; j < size; j++)
843 if (tn->child[j]) 813 if (tn->child[j])
844 tnode_free((struct tnode *)tn->child[j]); 814 tnode_free((struct tnode *)tn->child[j]);
845 815
846 tnode_free(tn); 816 tnode_free(tn);
847 817
848 *err = -ENOMEM; 818 *err = -ENOMEM;
849 return oldtnode; 819 return oldtnode;
850 } 820 }
851 821
852 for(i = 0; i < olen; i += 2) { 822 for (i = 0; i < olen; i += 2) {
823 struct tnode *newBinNode;
824
853 left = tnode_get_child(oldtnode, i); 825 left = tnode_get_child(oldtnode, i);
854 right = tnode_get_child(oldtnode, i+1); 826 right = tnode_get_child(oldtnode, i+1);
855 827
@@ -858,38 +830,39 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
858 if (right == NULL) /* Both are empty */ 830 if (right == NULL) /* Both are empty */
859 continue; 831 continue;
860 put_child(t, tn, i/2, right); 832 put_child(t, tn, i/2, right);
861 } else if (right == NULL) 833 continue;
834 }
835
836 if (right == NULL) {
862 put_child(t, tn, i/2, left); 837 put_child(t, tn, i/2, left);
838 continue;
839 }
863 840
864 /* Two nonempty children */ 841 /* Two nonempty children */
865 else { 842 newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
866 struct tnode *newBinNode = 843 put_child(t, tn, i/2, NULL);
867 (struct tnode *) tnode_get_child(tn, i/2);
868 put_child(t, tn, i/2, NULL);
869 844
870 if (!newBinNode) 845 BUG_ON(!newBinNode);
871 BUG();
872 846
873 put_child(t, newBinNode, 0, left); 847 put_child(t, newBinNode, 0, left);
874 put_child(t, newBinNode, 1, right); 848 put_child(t, newBinNode, 1, right);
875 put_child(t, tn, i/2, resize(t, newBinNode)); 849 put_child(t, tn, i/2, resize(t, newBinNode));
876 }
877 } 850 }
878 tnode_free(oldtnode); 851 tnode_free(oldtnode);
879 return tn; 852 return tn;
880} 853}
881 854
882static void *trie_init(struct trie *t) 855static void trie_init(struct trie *t)
883{ 856{
884 if (t) { 857 if (!t)
885 t->size = 0; 858 return;
886 t->trie = NULL; 859
887 t->revision = 0; 860 t->size = 0;
861 t->trie = NULL;
862 t->revision = 0;
888#ifdef CONFIG_IP_FIB_TRIE_STATS 863#ifdef CONFIG_IP_FIB_TRIE_STATS
889 memset(&t->stats, 0, sizeof(struct trie_use_stats)); 864 memset(&t->stats, 0, sizeof(struct trie_use_stats));
890#endif 865#endif
891 }
892 return t;
893} 866}
894 867
895static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen) 868static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
@@ -897,39 +870,37 @@ static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
897 struct hlist_node *node; 870 struct hlist_node *node;
898 struct leaf_info *li; 871 struct leaf_info *li;
899 872
900 hlist_for_each_entry(li, node, head, hlist) { 873 hlist_for_each_entry(li, node, head, hlist)
901 if (li->plen == plen) 874 if (li->plen == plen)
902 return li; 875 return li;
903 } 876
904 return NULL; 877 return NULL;
905} 878}
906 879
907static inline struct list_head * get_fa_head(struct leaf *l, int plen) 880static inline struct list_head * get_fa_head(struct leaf *l, int plen)
908{ 881{
909 struct list_head *fa_head = NULL;
910 struct leaf_info *li = find_leaf_info(&l->list, plen); 882 struct leaf_info *li = find_leaf_info(&l->list, plen);
911 883
912 if (li) 884 if (!li)
913 fa_head = &li->falh; 885 return NULL;
914 886
915 return fa_head; 887 return &li->falh;
916} 888}
917 889
918static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) 890static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
919{ 891{
920 struct leaf_info *li = NULL, *last = NULL; 892 struct leaf_info *li = NULL, *last = NULL;
921 struct hlist_node *node, *tmp; 893 struct hlist_node *node;
922 894
923 write_lock_bh(&fib_lock); 895 write_lock_bh(&fib_lock);
924 896
925 if (hlist_empty(head)) 897 if (hlist_empty(head)) {
926 hlist_add_head(&new->hlist, head); 898 hlist_add_head(&new->hlist, head);
927 else { 899 } else {
928 hlist_for_each_entry_safe(li, node, tmp, head, hlist) { 900 hlist_for_each_entry(li, node, head, hlist) {
929
930 if (new->plen > li->plen) 901 if (new->plen > li->plen)
931 break; 902 break;
932 903
933 last = li; 904 last = li;
934 } 905 }
935 if (last) 906 if (last)
@@ -952,49 +923,47 @@ fib_find_node(struct trie *t, u32 key)
952 923
953 while (n != NULL && NODE_TYPE(n) == T_TNODE) { 924 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
954 tn = (struct tnode *) n; 925 tn = (struct tnode *) n;
955 926
956 check_tnode(tn); 927 check_tnode(tn);
957 928
958 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 929 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
959 pos=tn->pos + tn->bits; 930 pos = tn->pos + tn->bits;
960 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 931 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
961 } 932 } else
962 else
963 break; 933 break;
964 } 934 }
965 /* Case we have found a leaf. Compare prefixes */ 935 /* Case we have found a leaf. Compare prefixes */
966 936
967 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) { 937 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
968 struct leaf *l = (struct leaf *) n; 938 return (struct leaf *)n;
969 return l; 939
970 }
971 return NULL; 940 return NULL;
972} 941}
973 942
974static struct node *trie_rebalance(struct trie *t, struct tnode *tn) 943static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
975{ 944{
976 int i = 0; 945 int i;
977 int wasfull; 946 int wasfull;
978 t_key cindex, key; 947 t_key cindex, key;
979 struct tnode *tp = NULL; 948 struct tnode *tp = NULL;
980 949
981 if (!tn) 950 BUG_ON(!tn);
982 BUG();
983 951
984 key = tn->key; 952 key = tn->key;
985 i = 0; 953 i = 0;
986 954
987 while (tn != NULL && NODE_PARENT(tn) != NULL) { 955 while (tn != NULL && NODE_PARENT(tn) != NULL) {
988
989 if (i > 10) { 956 if (i > 10) {
990 printk("Rebalance tn=%p \n", tn); 957 printk("Rebalance tn=%p \n", tn);
991 if (tn) printk("tn->parent=%p \n", NODE_PARENT(tn)); 958 if (tn)
992 959 printk("tn->parent=%p \n", NODE_PARENT(tn));
960
993 printk("Rebalance tp=%p \n", tp); 961 printk("Rebalance tp=%p \n", tp);
994 if (tp) printk("tp->parent=%p \n", NODE_PARENT(tp)); 962 if (tp)
963 printk("tp->parent=%p \n", NODE_PARENT(tp));
995 } 964 }
996 965
997 if (i > 12) BUG(); 966 BUG_ON(i > 12); /* Why is this a bug? -ojn */
998 i++; 967 i++;
999 968
1000 tp = NODE_PARENT(tn); 969 tp = NODE_PARENT(tn);
@@ -1002,7 +971,7 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
1002 wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); 971 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1003 tn = (struct tnode *) resize (t, (struct tnode *)tn); 972 tn = (struct tnode *) resize (t, (struct tnode *)tn);
1004 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); 973 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
1005 974
1006 if (!NODE_PARENT(tn)) 975 if (!NODE_PARENT(tn))
1007 break; 976 break;
1008 977
@@ -1050,20 +1019,19 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1050 1019
1051 while (n != NULL && NODE_TYPE(n) == T_TNODE) { 1020 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1052 tn = (struct tnode *) n; 1021 tn = (struct tnode *) n;
1053 1022
1054 check_tnode(tn); 1023 check_tnode(tn);
1055 1024
1056 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 1025 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1057 tp = tn; 1026 tp = tn;
1058 pos=tn->pos + tn->bits; 1027 pos = tn->pos + tn->bits;
1059 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 1028 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1060 1029
1061 if (n && NODE_PARENT(n) != tn) { 1030 if (n && NODE_PARENT(n) != tn) {
1062 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); 1031 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1063 BUG(); 1032 BUG();
1064 } 1033 }
1065 } 1034 } else
1066 else
1067 break; 1035 break;
1068 } 1036 }
1069 1037
@@ -1073,17 +1041,15 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1073 * tp is n's (parent) ----> NULL or TNODE 1041 * tp is n's (parent) ----> NULL or TNODE
1074 */ 1042 */
1075 1043
1076 if (tp && IS_LEAF(tp)) 1044 BUG_ON(tp && IS_LEAF(tp));
1077 BUG();
1078
1079 1045
1080 /* Case 1: n is a leaf. Compare prefixes */ 1046 /* Case 1: n is a leaf. Compare prefixes */
1081 1047
1082 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) { 1048 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1083 struct leaf *l = ( struct leaf *) n; 1049 struct leaf *l = (struct leaf *) n;
1084 1050
1085 li = leaf_info_new(plen); 1051 li = leaf_info_new(plen);
1086 1052
1087 if (!li) { 1053 if (!li) {
1088 *err = -ENOMEM; 1054 *err = -ENOMEM;
1089 goto err; 1055 goto err;
@@ -1113,35 +1079,31 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1113 fa_head = &li->falh; 1079 fa_head = &li->falh;
1114 insert_leaf_info(&l->list, li); 1080 insert_leaf_info(&l->list, li);
1115 1081
1116 /* Case 2: n is NULL, and will just insert a new leaf */
1117 if (t->trie && n == NULL) { 1082 if (t->trie && n == NULL) {
1083 /* Case 2: n is NULL, and will just insert a new leaf */
1118 1084
1119 NODE_SET_PARENT(l, tp); 1085 NODE_SET_PARENT(l, tp);
1120
1121 if (!tp)
1122 BUG();
1123 1086
1124 else { 1087 BUG_ON(!tp);
1125 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1088
1126 put_child(t, (struct tnode *)tp, cindex, (struct node *)l); 1089 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1127 } 1090 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
1128 } 1091 } else {
1129 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */ 1092 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1130 else {
1131 /* 1093 /*
1132 * Add a new tnode here 1094 * Add a new tnode here
1133 * first tnode need some special handling 1095 * first tnode need some special handling
1134 */ 1096 */
1135 1097
1136 if (tp) 1098 if (tp)
1137 pos=tp->pos+tp->bits; 1099 pos = tp->pos+tp->bits;
1138 else 1100 else
1139 pos=0; 1101 pos = 0;
1102
1140 if (n) { 1103 if (n) {
1141 newpos = tkey_mismatch(key, pos, n->key); 1104 newpos = tkey_mismatch(key, pos, n->key);
1142 tn = tnode_new(n->key, newpos, 1); 1105 tn = tnode_new(n->key, newpos, 1);
1143 } 1106 } else {
1144 else {
1145 newpos = 0; 1107 newpos = 0;
1146 tn = tnode_new(key, newpos, 1); /* First tnode */ 1108 tn = tnode_new(key, newpos, 1); /* First tnode */
1147 } 1109 }
@@ -1151,32 +1113,32 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1151 tnode_free((struct tnode *) l); 1113 tnode_free((struct tnode *) l);
1152 *err = -ENOMEM; 1114 *err = -ENOMEM;
1153 goto err; 1115 goto err;
1154 } 1116 }
1155 1117
1156 NODE_SET_PARENT(tn, tp); 1118 NODE_SET_PARENT(tn, tp);
1157 1119
1158 missbit=tkey_extract_bits(key, newpos, 1); 1120 missbit = tkey_extract_bits(key, newpos, 1);
1159 put_child(t, tn, missbit, (struct node *)l); 1121 put_child(t, tn, missbit, (struct node *)l);
1160 put_child(t, tn, 1-missbit, n); 1122 put_child(t, tn, 1-missbit, n);
1161 1123
1162 if (tp) { 1124 if (tp) {
1163 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1125 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1164 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn); 1126 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
1165 } 1127 } else {
1166 else {
1167 t->trie = (struct node*) tn; /* First tnode */ 1128 t->trie = (struct node*) tn; /* First tnode */
1168 tp = tn; 1129 tp = tn;
1169 } 1130 }
1170 } 1131 }
1171 if (tp && tp->pos+tp->bits > 32) { 1132
1133 if (tp && tp->pos + tp->bits > 32)
1172 printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", 1134 printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1173 tp, tp->pos, tp->bits, key, plen); 1135 tp, tp->pos, tp->bits, key, plen);
1174 } 1136
1175 /* Rebalance the trie */ 1137 /* Rebalance the trie */
1176 t->trie = trie_rebalance(t, tp); 1138 t->trie = trie_rebalance(t, tp);
1177done: 1139done:
1178 t->revision++; 1140 t->revision++;
1179err:; 1141err:
1180 return fa_head; 1142 return fa_head;
1181} 1143}
1182 1144
@@ -1204,17 +1166,18 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1204 1166
1205 key = ntohl(key); 1167 key = ntohl(key);
1206 1168
1207 if (trie_debug) 1169 DBG("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
1208 printk("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
1209 1170
1210 mask = ntohl( inet_make_mask(plen) ); 1171 mask = ntohl(inet_make_mask(plen));
1211 1172
1212 if (key & ~mask) 1173 if (key & ~mask)
1213 return -EINVAL; 1174 return -EINVAL;
1214 1175
1215 key = key & mask; 1176 key = key & mask;
1216 1177
1217 if ((fi = fib_create_info(r, rta, nlhdr, &err)) == NULL) 1178 fi = fib_create_info(r, rta, nlhdr, &err);
1179
1180 if (!fi)
1218 goto err; 1181 goto err;
1219 1182
1220 l = fib_find_node(t, key); 1183 l = fib_find_node(t, key);
@@ -1236,8 +1199,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1236 * and we need to allocate a new one of those as well. 1199 * and we need to allocate a new one of those as well.
1237 */ 1200 */
1238 1201
1239 if (fa && 1202 if (fa && fa->fa_info->fib_priority == fi->fib_priority) {
1240 fa->fa_info->fib_priority == fi->fib_priority) {
1241 struct fib_alias *fa_orig; 1203 struct fib_alias *fa_orig;
1242 1204
1243 err = -EEXIST; 1205 err = -EEXIST;
@@ -1261,9 +1223,9 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1261 1223
1262 fib_release_info(fi_drop); 1224 fib_release_info(fi_drop);
1263 if (state & FA_S_ACCESSED) 1225 if (state & FA_S_ACCESSED)
1264 rt_cache_flush(-1); 1226 rt_cache_flush(-1);
1265 1227
1266 goto succeeded; 1228 goto succeeded;
1267 } 1229 }
1268 /* Error if we find a perfect match which 1230 /* Error if we find a perfect match which
1269 * uses the same scope, type, and nexthop 1231 * uses the same scope, type, and nexthop
@@ -1285,7 +1247,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1285 fa = fa_orig; 1247 fa = fa_orig;
1286 } 1248 }
1287 err = -ENOENT; 1249 err = -ENOENT;
1288 if (!(nlhdr->nlmsg_flags&NLM_F_CREATE)) 1250 if (!(nlhdr->nlmsg_flags & NLM_F_CREATE))
1289 goto out; 1251 goto out;
1290 1252
1291 err = -ENOBUFS; 1253 err = -ENOBUFS;
@@ -1298,9 +1260,6 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1298 new_fa->fa_type = type; 1260 new_fa->fa_type = type;
1299 new_fa->fa_scope = r->rtm_scope; 1261 new_fa->fa_scope = r->rtm_scope;
1300 new_fa->fa_state = 0; 1262 new_fa->fa_state = 0;
1301#if 0
1302 new_fa->dst = NULL;
1303#endif
1304 /* 1263 /*
1305 * Insert new entry to the list. 1264 * Insert new entry to the list.
1306 */ 1265 */
@@ -1314,8 +1273,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1314 1273
1315 write_lock_bh(&fib_lock); 1274 write_lock_bh(&fib_lock);
1316 1275
1317 list_add_tail(&new_fa->fa_list, 1276 list_add_tail(&new_fa->fa_list, (fa ? &fa->fa_list : fa_head));
1318 (fa ? &fa->fa_list : fa_head));
1319 1277
1320 write_unlock_bh(&fib_lock); 1278 write_unlock_bh(&fib_lock);
1321 1279
@@ -1328,7 +1286,7 @@ out_free_new_fa:
1328 kmem_cache_free(fn_alias_kmem, new_fa); 1286 kmem_cache_free(fn_alias_kmem, new_fa);
1329out: 1287out:
1330 fib_release_info(fi); 1288 fib_release_info(fi);
1331err:; 1289err:
1332 return err; 1290 return err;
1333} 1291}
1334 1292
@@ -1342,7 +1300,6 @@ static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *pl
1342 struct hlist_node *node; 1300 struct hlist_node *node;
1343 1301
1344 hlist_for_each_entry(li, node, hhead, hlist) { 1302 hlist_for_each_entry(li, node, hhead, hlist) {
1345
1346 i = li->plen; 1303 i = li->plen;
1347 mask = ntohl(inet_make_mask(i)); 1304 mask = ntohl(inet_make_mask(i));
1348 if (l->key != (key & mask)) 1305 if (l->key != (key & mask))
@@ -1370,13 +1327,18 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1370 struct node *n; 1327 struct node *n;
1371 struct tnode *pn; 1328 struct tnode *pn;
1372 int pos, bits; 1329 int pos, bits;
1373 t_key key=ntohl(flp->fl4_dst); 1330 t_key key = ntohl(flp->fl4_dst);
1374 int chopped_off; 1331 int chopped_off;
1375 t_key cindex = 0; 1332 t_key cindex = 0;
1376 int current_prefix_length = KEYLENGTH; 1333 int current_prefix_length = KEYLENGTH;
1334 struct tnode *cn;
1335 t_key node_prefix, key_prefix, pref_mismatch;
1336 int mp;
1337
1377 n = t->trie; 1338 n = t->trie;
1378 1339
1379 read_lock(&fib_lock); 1340 read_lock(&fib_lock);
1341
1380 if (!n) 1342 if (!n)
1381 goto failed; 1343 goto failed;
1382 1344
@@ -1393,8 +1355,7 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1393 pn = (struct tnode *) n; 1355 pn = (struct tnode *) n;
1394 chopped_off = 0; 1356 chopped_off = 0;
1395 1357
1396 while (pn) { 1358 while (pn) {
1397
1398 pos = pn->pos; 1359 pos = pn->pos;
1399 bits = pn->bits; 1360 bits = pn->bits;
1400 1361
@@ -1410,130 +1371,129 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1410 goto backtrace; 1371 goto backtrace;
1411 } 1372 }
1412 1373
1413 if (IS_TNODE(n)) { 1374 if (IS_LEAF(n)) {
1375 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0)
1376 goto found;
1377 else
1378 goto backtrace;
1379 }
1380
1414#define HL_OPTIMIZE 1381#define HL_OPTIMIZE
1415#ifdef HL_OPTIMIZE 1382#ifdef HL_OPTIMIZE
1416 struct tnode *cn = (struct tnode *)n; 1383 cn = (struct tnode *)n;
1417 t_key node_prefix, key_prefix, pref_mismatch;
1418 int mp;
1419 1384
1420 /* 1385 /*
1421 * It's a tnode, and we can do some extra checks here if we 1386 * It's a tnode, and we can do some extra checks here if we
1422 * like, to avoid descending into a dead-end branch. 1387 * like, to avoid descending into a dead-end branch.
1423 * This tnode is in the parent's child array at index 1388 * This tnode is in the parent's child array at index
1424 * key[p_pos..p_pos+p_bits] but potentially with some bits 1389 * key[p_pos..p_pos+p_bits] but potentially with some bits
1425 * chopped off, so in reality the index may be just a 1390 * chopped off, so in reality the index may be just a
1426 * subprefix, padded with zero at the end. 1391 * subprefix, padded with zero at the end.
1427 * We can also take a look at any skipped bits in this 1392 * We can also take a look at any skipped bits in this
1428 * tnode - everything up to p_pos is supposed to be ok, 1393 * tnode - everything up to p_pos is supposed to be ok,
1429 * and the non-chopped bits of the index (se previous 1394 * and the non-chopped bits of the index (se previous
1430 * paragraph) are also guaranteed ok, but the rest is 1395 * paragraph) are also guaranteed ok, but the rest is
1431 * considered unknown. 1396 * considered unknown.
1432 * 1397 *
1433 * The skipped bits are key[pos+bits..cn->pos]. 1398 * The skipped bits are key[pos+bits..cn->pos].
1434 */ 1399 */
1435
1436 /* If current_prefix_length < pos+bits, we are already doing
1437 * actual prefix matching, which means everything from
1438 * pos+(bits-chopped_off) onward must be zero along some
1439 * branch of this subtree - otherwise there is *no* valid
1440 * prefix present. Here we can only check the skipped
1441 * bits. Remember, since we have already indexed into the
1442 * parent's child array, we know that the bits we chopped of
1443 * *are* zero.
1444 */
1445 1400
1446 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */ 1401 /* If current_prefix_length < pos+bits, we are already doing
1447 1402 * actual prefix matching, which means everything from
1448 if (current_prefix_length < pos+bits) { 1403 * pos+(bits-chopped_off) onward must be zero along some
1449 if (tkey_extract_bits(cn->key, current_prefix_length, 1404 * branch of this subtree - otherwise there is *no* valid
1450 cn->pos - current_prefix_length) != 0 || 1405 * prefix present. Here we can only check the skipped
1451 !(cn->child[0])) 1406 * bits. Remember, since we have already indexed into the
1452 goto backtrace; 1407 * parent's child array, we know that the bits we chopped of
1453 } 1408 * *are* zero.
1409 */
1454 1410
1455 /* 1411 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1456 * If chopped_off=0, the index is fully validated and we
1457 * only need to look at the skipped bits for this, the new,
1458 * tnode. What we actually want to do is to find out if
1459 * these skipped bits match our key perfectly, or if we will
1460 * have to count on finding a matching prefix further down,
1461 * because if we do, we would like to have some way of
1462 * verifying the existence of such a prefix at this point.
1463 */
1464 1412
1465 /* The only thing we can do at this point is to verify that 1413 if (current_prefix_length < pos+bits) {
1466 * any such matching prefix can indeed be a prefix to our 1414 if (tkey_extract_bits(cn->key, current_prefix_length,
1467 * key, and if the bits in the node we are inspecting that 1415 cn->pos - current_prefix_length) != 0 ||
1468 * do not match our key are not ZERO, this cannot be true. 1416 !(cn->child[0]))
1469 * Thus, find out where there is a mismatch (before cn->pos) 1417 goto backtrace;
1470 * and verify that all the mismatching bits are zero in the 1418 }
1471 * new tnode's key.
1472 */
1473 1419
1474 /* Note: We aren't very concerned about the piece of the key 1420 /*
1475 * that precede pn->pos+pn->bits, since these have already been 1421 * If chopped_off=0, the index is fully validated and we
1476 * checked. The bits after cn->pos aren't checked since these are 1422 * only need to look at the skipped bits for this, the new,
1477 * by definition "unknown" at this point. Thus, what we want to 1423 * tnode. What we actually want to do is to find out if
1478 * see is if we are about to enter the "prefix matching" state, 1424 * these skipped bits match our key perfectly, or if we will
1479 * and in that case verify that the skipped bits that will prevail 1425 * have to count on finding a matching prefix further down,
1480 * throughout this subtree are zero, as they have to be if we are 1426 * because if we do, we would like to have some way of
1481 * to find a matching prefix. 1427 * verifying the existence of such a prefix at this point.
1482 */ 1428 */
1483 1429
1484 node_prefix = MASK_PFX(cn->key, cn->pos); 1430 /* The only thing we can do at this point is to verify that
1485 key_prefix = MASK_PFX(key, cn->pos); 1431 * any such matching prefix can indeed be a prefix to our
1486 pref_mismatch = key_prefix^node_prefix; 1432 * key, and if the bits in the node we are inspecting that
1487 mp = 0; 1433 * do not match our key are not ZERO, this cannot be true.
1434 * Thus, find out where there is a mismatch (before cn->pos)
1435 * and verify that all the mismatching bits are zero in the
1436 * new tnode's key.
1437 */
1488 1438
1489 /* In short: If skipped bits in this node do not match the search 1439 /* Note: We aren't very concerned about the piece of the key
1490 * key, enter the "prefix matching" state.directly. 1440 * that precede pn->pos+pn->bits, since these have already been
1491 */ 1441 * checked. The bits after cn->pos aren't checked since these are
1492 if (pref_mismatch) { 1442 * by definition "unknown" at this point. Thus, what we want to
1493 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) { 1443 * see is if we are about to enter the "prefix matching" state,
1494 mp++; 1444 * and in that case verify that the skipped bits that will prevail
1495 pref_mismatch = pref_mismatch <<1; 1445 * throughout this subtree are zero, as they have to be if we are
1496 } 1446 * to find a matching prefix.
1497 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); 1447 */
1498 1448
1499 if (key_prefix != 0) 1449 node_prefix = MASK_PFX(cn->key, cn->pos);
1500 goto backtrace; 1450 key_prefix = MASK_PFX(key, cn->pos);
1501 1451 pref_mismatch = key_prefix^node_prefix;
1502 if (current_prefix_length >= cn->pos) 1452 mp = 0;
1503 current_prefix_length=mp; 1453
1504 } 1454 /* In short: If skipped bits in this node do not match the search
1505#endif 1455 * key, enter the "prefix matching" state.directly.
1506 pn = (struct tnode *)n; /* Descend */ 1456 */
1507 chopped_off = 0; 1457 if (pref_mismatch) {
1508 continue; 1458 while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) {
1459 mp++;
1460 pref_mismatch = pref_mismatch <<1;
1461 }
1462 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1463
1464 if (key_prefix != 0)
1465 goto backtrace;
1466
1467 if (current_prefix_length >= cn->pos)
1468 current_prefix_length = mp;
1509 } 1469 }
1510 if (IS_LEAF(n)) { 1470#endif
1511 if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) 1471 pn = (struct tnode *)n; /* Descend */
1512 goto found; 1472 chopped_off = 0;
1513 } 1473 continue;
1474
1514backtrace: 1475backtrace:
1515 chopped_off++; 1476 chopped_off++;
1516 1477
1517 /* As zero don't change the child key (cindex) */ 1478 /* As zero don't change the child key (cindex) */
1518 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) { 1479 while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1))))
1519 chopped_off++; 1480 chopped_off++;
1520 }
1521 1481
1522 /* Decrease current_... with bits chopped off */ 1482 /* Decrease current_... with bits chopped off */
1523 if (current_prefix_length > pn->pos + pn->bits - chopped_off) 1483 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1524 current_prefix_length = pn->pos + pn->bits - chopped_off; 1484 current_prefix_length = pn->pos + pn->bits - chopped_off;
1525 1485
1526 /* 1486 /*
1527 * Either we do the actual chop off according or if we have 1487 * Either we do the actual chop off according or if we have
1528 * chopped off all bits in this tnode walk up to our parent. 1488 * chopped off all bits in this tnode walk up to our parent.
1529 */ 1489 */
1530 1490
1531 if (chopped_off <= pn->bits) 1491 if (chopped_off <= pn->bits) {
1532 cindex &= ~(1 << (chopped_off-1)); 1492 cindex &= ~(1 << (chopped_off-1));
1533 else { 1493 } else {
1534 if (NODE_PARENT(pn) == NULL) 1494 if (NODE_PARENT(pn) == NULL)
1535 goto failed; 1495 goto failed;
1536 1496
1537 /* Get Child's index */ 1497 /* Get Child's index */
1538 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits); 1498 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
1539 pn = NODE_PARENT(pn); 1499 pn = NODE_PARENT(pn);
@@ -1559,24 +1519,23 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1559 struct node *n = t->trie; 1519 struct node *n = t->trie;
1560 struct leaf *l; 1520 struct leaf *l;
1561 1521
1562 if (trie_debug) 1522 DBG("entering trie_leaf_remove(%p)\n", n);
1563 printk("entering trie_leaf_remove(%p)\n", n);
1564 1523
1565 /* Note that in the case skipped bits, those bits are *not* checked! 1524 /* Note that in the case skipped bits, those bits are *not* checked!
1566 * When we finish this, we will have NULL or a T_LEAF, and the 1525 * When we finish this, we will have NULL or a T_LEAF, and the
1567 * T_LEAF may or may not match our key. 1526 * T_LEAF may or may not match our key.
1568 */ 1527 */
1569 1528
1570 while (n != NULL && IS_TNODE(n)) { 1529 while (n != NULL && IS_TNODE(n)) {
1571 struct tnode *tn = (struct tnode *) n; 1530 struct tnode *tn = (struct tnode *) n;
1572 check_tnode(tn); 1531 check_tnode(tn);
1573 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); 1532 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1574 1533
1575 if (n && NODE_PARENT(n) != tn) { 1534 if (n && NODE_PARENT(n) != tn) {
1576 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); 1535 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1577 BUG(); 1536 BUG();
1578 } 1537 }
1579 } 1538 }
1580 l = (struct leaf *) n; 1539 l = (struct leaf *) n;
1581 1540
1582 if (!n || !tkey_equals(l->key, key)) 1541 if (!n || !tkey_equals(l->key, key))
@@ -1597,8 +1556,7 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1597 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1556 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1598 put_child(t, (struct tnode *)tp, cindex, NULL); 1557 put_child(t, (struct tnode *)tp, cindex, NULL);
1599 t->trie = trie_rebalance(t, tp); 1558 t->trie = trie_rebalance(t, tp);
1600 } 1559 } else
1601 else
1602 t->trie = NULL; 1560 t->trie = NULL;
1603 1561
1604 return 1; 1562 return 1;
@@ -1606,7 +1564,7 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1606 1564
1607static int 1565static int
1608fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, 1566fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1609 struct nlmsghdr *nlhdr, struct netlink_skb_parms *req) 1567 struct nlmsghdr *nlhdr, struct netlink_skb_parms *req)
1610{ 1568{
1611 struct trie *t = (struct trie *) tb->tb_data; 1569 struct trie *t = (struct trie *) tb->tb_data;
1612 u32 key, mask; 1570 u32 key, mask;
@@ -1615,6 +1573,9 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1615 struct fib_alias *fa, *fa_to_delete; 1573 struct fib_alias *fa, *fa_to_delete;
1616 struct list_head *fa_head; 1574 struct list_head *fa_head;
1617 struct leaf *l; 1575 struct leaf *l;
1576 int kill_li = 0;
1577 struct leaf_info *li;
1578
1618 1579
1619 if (plen > 32) 1580 if (plen > 32)
1620 return -EINVAL; 1581 return -EINVAL;
@@ -1624,7 +1585,7 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1624 memcpy(&key, rta->rta_dst, 4); 1585 memcpy(&key, rta->rta_dst, 4);
1625 1586
1626 key = ntohl(key); 1587 key = ntohl(key);
1627 mask = ntohl( inet_make_mask(plen) ); 1588 mask = ntohl(inet_make_mask(plen));
1628 1589
1629 if (key & ~mask) 1590 if (key & ~mask)
1630 return -EINVAL; 1591 return -EINVAL;
@@ -1641,8 +1602,7 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1641 if (!fa) 1602 if (!fa)
1642 return -ESRCH; 1603 return -ESRCH;
1643 1604
1644 if (trie_debug) 1605 DBG("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1645 printk("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t);
1646 1606
1647 fa_to_delete = NULL; 1607 fa_to_delete = NULL;
1648 fa_head = fa->fa_list.prev; 1608 fa_head = fa->fa_list.prev;
@@ -1664,39 +1624,36 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1664 } 1624 }
1665 } 1625 }
1666 1626
1667 if (fa_to_delete) { 1627 if (!fa_to_delete)
1668 int kill_li = 0; 1628 return -ESRCH;
1669 struct leaf_info *li;
1670 1629
1671 fa = fa_to_delete; 1630 fa = fa_to_delete;
1672 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req); 1631 rtmsg_fib(RTM_DELROUTE, htonl(key), fa, plen, tb->tb_id, nlhdr, req);
1632
1633 l = fib_find_node(t, key);
1634 li = find_leaf_info(&l->list, plen);
1673 1635
1674 l = fib_find_node(t, key); 1636 write_lock_bh(&fib_lock);
1675 li = find_leaf_info(&l->list, plen);
1676 1637
1677 write_lock_bh(&fib_lock); 1638 list_del(&fa->fa_list);
1678 1639
1679 list_del(&fa->fa_list); 1640 if (list_empty(fa_head)) {
1641 hlist_del(&li->hlist);
1642 kill_li = 1;
1643 }
1644 write_unlock_bh(&fib_lock);
1680 1645
1681 if (list_empty(fa_head)) { 1646 if (kill_li)
1682 hlist_del(&li->hlist); 1647 free_leaf_info(li);
1683 kill_li = 1;
1684 }
1685 write_unlock_bh(&fib_lock);
1686
1687 if (kill_li)
1688 free_leaf_info(li);
1689 1648
1690 if (hlist_empty(&l->list)) 1649 if (hlist_empty(&l->list))
1691 trie_leaf_remove(t, key); 1650 trie_leaf_remove(t, key);
1692 1651
1693 if (fa->fa_state & FA_S_ACCESSED) 1652 if (fa->fa_state & FA_S_ACCESSED)
1694 rt_cache_flush(-1); 1653 rt_cache_flush(-1);
1695 1654
1696 fn_free_alias(fa); 1655 fn_free_alias(fa);
1697 return 0; 1656 return 0;
1698 }
1699 return -ESRCH;
1700} 1657}
1701 1658
1702static int trie_flush_list(struct trie *t, struct list_head *head) 1659static int trie_flush_list(struct trie *t, struct list_head *head)
@@ -1706,9 +1663,8 @@ static int trie_flush_list(struct trie *t, struct list_head *head)
1706 1663
1707 list_for_each_entry_safe(fa, fa_node, head, fa_list) { 1664 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1708 struct fib_info *fi = fa->fa_info; 1665 struct fib_info *fi = fa->fa_info;
1709
1710 if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
1711 1666
1667 if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
1712 write_lock_bh(&fib_lock); 1668 write_lock_bh(&fib_lock);
1713 list_del(&fa->fa_list); 1669 list_del(&fa->fa_list);
1714 write_unlock_bh(&fib_lock); 1670 write_unlock_bh(&fib_lock);
@@ -1728,11 +1684,9 @@ static int trie_flush_leaf(struct trie *t, struct leaf *l)
1728 struct leaf_info *li = NULL; 1684 struct leaf_info *li = NULL;
1729 1685
1730 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) { 1686 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1731
1732 found += trie_flush_list(t, &li->falh); 1687 found += trie_flush_list(t, &li->falh);
1733 1688
1734 if (list_empty(&li->falh)) { 1689 if (list_empty(&li->falh)) {
1735
1736 write_lock_bh(&fib_lock); 1690 write_lock_bh(&fib_lock);
1737 hlist_del(&li->hlist); 1691 hlist_del(&li->hlist);
1738 write_unlock_bh(&fib_lock); 1692 write_unlock_bh(&fib_lock);
@@ -1757,8 +1711,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1757 return (struct leaf *) t->trie; 1711 return (struct leaf *) t->trie;
1758 1712
1759 p = (struct tnode*) t->trie; /* Start */ 1713 p = (struct tnode*) t->trie; /* Start */
1760 } 1714 } else
1761 else
1762 p = (struct tnode *) NODE_PARENT(c); 1715 p = (struct tnode *) NODE_PARENT(c);
1763 1716
1764 while (p) { 1717 while (p) {
@@ -1771,29 +1724,28 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1771 pos = 0; 1724 pos = 0;
1772 1725
1773 last = 1 << p->bits; 1726 last = 1 << p->bits;
1774 for(idx = pos; idx < last ; idx++) { 1727 for (idx = pos; idx < last ; idx++) {
1775 if (p->child[idx]) { 1728 if (!p->child[idx])
1776 1729 continue;
1777 /* Decend if tnode */ 1730
1778 1731 /* Decend if tnode */
1779 while (IS_TNODE(p->child[idx])) { 1732 while (IS_TNODE(p->child[idx])) {
1780 p = (struct tnode*) p->child[idx]; 1733 p = (struct tnode*) p->child[idx];
1781 idx = 0; 1734 idx = 0;
1782 1735
1783 /* Rightmost non-NULL branch */ 1736 /* Rightmost non-NULL branch */
1784 if (p && IS_TNODE(p)) 1737 if (p && IS_TNODE(p))
1785 while (p->child[idx] == NULL && idx < (1 << p->bits)) idx++; 1738 while (p->child[idx] == NULL && idx < (1 << p->bits)) idx++;
1786 1739
1787 /* Done with this tnode? */ 1740 /* Done with this tnode? */
1788 if (idx >= (1 << p->bits) || p->child[idx] == NULL ) 1741 if (idx >= (1 << p->bits) || p->child[idx] == NULL)
1789 goto up; 1742 goto up;
1790 }
1791 return (struct leaf*) p->child[idx];
1792 } 1743 }
1744 return (struct leaf*) p->child[idx];
1793 } 1745 }
1794up: 1746up:
1795 /* No more children go up one step */ 1747 /* No more children go up one step */
1796 c = (struct node*) p; 1748 c = (struct node *) p;
1797 p = (struct tnode *) NODE_PARENT(p); 1749 p = (struct tnode *) NODE_PARENT(p);
1798 } 1750 }
1799 return NULL; /* Ready. Root of trie */ 1751 return NULL; /* Ready. Root of trie */
@@ -1807,7 +1759,7 @@ static int fn_trie_flush(struct fib_table *tb)
1807 1759
1808 t->revision++; 1760 t->revision++;
1809 1761
1810 for (h=0; (l = nextleaf(t, l)) != NULL; h++) { 1762 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1811 found += trie_flush_leaf(t, l); 1763 found += trie_flush_leaf(t, l);
1812 1764
1813 if (ll && hlist_empty(&ll->list)) 1765 if (ll && hlist_empty(&ll->list))
@@ -1818,12 +1770,11 @@ static int fn_trie_flush(struct fib_table *tb)
1818 if (ll && hlist_empty(&ll->list)) 1770 if (ll && hlist_empty(&ll->list))
1819 trie_leaf_remove(t, ll->key); 1771 trie_leaf_remove(t, ll->key);
1820 1772
1821 if (trie_debug) 1773 DBG("trie_flush found=%d\n", found);
1822 printk("trie_flush found=%d\n", found);
1823 return found; 1774 return found;
1824} 1775}
1825 1776
1826static int trie_last_dflt=-1; 1777static int trie_last_dflt = -1;
1827 1778
1828static void 1779static void
1829fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) 1780fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res)
@@ -1855,18 +1806,18 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
1855 1806
1856 list_for_each_entry(fa, fa_head, fa_list) { 1807 list_for_each_entry(fa, fa_head, fa_list) {
1857 struct fib_info *next_fi = fa->fa_info; 1808 struct fib_info *next_fi = fa->fa_info;
1858 1809
1859 if (fa->fa_scope != res->scope || 1810 if (fa->fa_scope != res->scope ||
1860 fa->fa_type != RTN_UNICAST) 1811 fa->fa_type != RTN_UNICAST)
1861 continue; 1812 continue;
1862 1813
1863 if (next_fi->fib_priority > res->fi->fib_priority) 1814 if (next_fi->fib_priority > res->fi->fib_priority)
1864 break; 1815 break;
1865 if (!next_fi->fib_nh[0].nh_gw || 1816 if (!next_fi->fib_nh[0].nh_gw ||
1866 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK) 1817 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1867 continue; 1818 continue;
1868 fa->fa_state |= FA_S_ACCESSED; 1819 fa->fa_state |= FA_S_ACCESSED;
1869 1820
1870 if (fi == NULL) { 1821 if (fi == NULL) {
1871 if (next_fi != res->fi) 1822 if (next_fi != res->fi)
1872 break; 1823 break;
@@ -1913,9 +1864,9 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
1913 int i, s_i; 1864 int i, s_i;
1914 struct fib_alias *fa; 1865 struct fib_alias *fa;
1915 1866
1916 u32 xkey=htonl(key); 1867 u32 xkey = htonl(key);
1917 1868
1918 s_i=cb->args[3]; 1869 s_i = cb->args[3];
1919 i = 0; 1870 i = 0;
1920 1871
1921 list_for_each_entry(fa, fah, fa_list) { 1872 list_for_each_entry(fa, fah, fa_list) {
@@ -1946,10 +1897,10 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
1946 fa->fa_info, 0) < 0) { 1897 fa->fa_info, 0) < 0) {
1947 cb->args[3] = i; 1898 cb->args[3] = i;
1948 return -1; 1899 return -1;
1949 } 1900 }
1950 i++; 1901 i++;
1951 } 1902 }
1952 cb->args[3]=i; 1903 cb->args[3] = i;
1953 return skb->len; 1904 return skb->len;
1954} 1905}
1955 1906
@@ -1959,10 +1910,10 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1959 int h, s_h; 1910 int h, s_h;
1960 struct list_head *fa_head; 1911 struct list_head *fa_head;
1961 struct leaf *l = NULL; 1912 struct leaf *l = NULL;
1962 s_h=cb->args[2];
1963 1913
1964 for (h=0; (l = nextleaf(t, l)) != NULL; h++) { 1914 s_h = cb->args[2];
1965 1915
1916 for (h = 0; (l = nextleaf(t, l)) != NULL; h++) {
1966 if (h < s_h) 1917 if (h < s_h)
1967 continue; 1918 continue;
1968 if (h > s_h) 1919 if (h > s_h)
@@ -1970,7 +1921,7 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1970 sizeof(cb->args) - 3*sizeof(cb->args[0])); 1921 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1971 1922
1972 fa_head = get_fa_head(l, plen); 1923 fa_head = get_fa_head(l, plen);
1973 1924
1974 if (!fa_head) 1925 if (!fa_head)
1975 continue; 1926 continue;
1976 1927
@@ -1978,11 +1929,11 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1978 continue; 1929 continue;
1979 1930
1980 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { 1931 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
1981 cb->args[2]=h; 1932 cb->args[2] = h;
1982 return -1; 1933 return -1;
1983 } 1934 }
1984 } 1935 }
1985 cb->args[2]=h; 1936 cb->args[2] = h;
1986 return skb->len; 1937 return skb->len;
1987} 1938}
1988 1939
@@ -1994,13 +1945,12 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
1994 s_m = cb->args[1]; 1945 s_m = cb->args[1];
1995 1946
1996 read_lock(&fib_lock); 1947 read_lock(&fib_lock);
1997 for (m=0; m<=32; m++) { 1948 for (m = 0; m <= 32; m++) {
1998
1999 if (m < s_m) 1949 if (m < s_m)
2000 continue; 1950 continue;
2001 if (m > s_m) 1951 if (m > s_m)
2002 memset(&cb->args[2], 0, 1952 memset(&cb->args[2], 0,
2003 sizeof(cb->args) - 2*sizeof(cb->args[0])); 1953 sizeof(cb->args) - 2*sizeof(cb->args[0]));
2004 1954
2005 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) { 1955 if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) {
2006 cb->args[1] = m; 1956 cb->args[1] = m;
@@ -2010,7 +1960,7 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin
2010 read_unlock(&fib_lock); 1960 read_unlock(&fib_lock);
2011 cb->args[1] = m; 1961 cb->args[1] = m;
2012 return skb->len; 1962 return skb->len;
2013 out: 1963out:
2014 read_unlock(&fib_lock); 1964 read_unlock(&fib_lock);
2015 return -1; 1965 return -1;
2016} 1966}
@@ -2051,9 +2001,9 @@ struct fib_table * __init fib_hash_init(int id)
2051 trie_init(t); 2001 trie_init(t);
2052 2002
2053 if (id == RT_TABLE_LOCAL) 2003 if (id == RT_TABLE_LOCAL)
2054 trie_local = t; 2004 trie_local = t;
2055 else if (id == RT_TABLE_MAIN) 2005 else if (id == RT_TABLE_MAIN)
2056 trie_main = t; 2006 trie_main = t;
2057 2007
2058 if (id == RT_TABLE_LOCAL) 2008 if (id == RT_TABLE_LOCAL)
2059 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION); 2009 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
@@ -2065,7 +2015,8 @@ struct fib_table * __init fib_hash_init(int id)
2065 2015
2066static void putspace_seq(struct seq_file *seq, int n) 2016static void putspace_seq(struct seq_file *seq, int n)
2067{ 2017{
2068 while (n--) seq_printf(seq, " "); 2018 while (n--)
2019 seq_printf(seq, " ");
2069} 2020}
2070 2021
2071static void printbin_seq(struct seq_file *seq, unsigned int v, int bits) 2022static void printbin_seq(struct seq_file *seq, unsigned int v, int bits)
@@ -2086,29 +2037,22 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2086 seq_printf(seq, "%d/", cindex); 2037 seq_printf(seq, "%d/", cindex);
2087 printbin_seq(seq, cindex, bits); 2038 printbin_seq(seq, cindex, bits);
2088 seq_printf(seq, ": "); 2039 seq_printf(seq, ": ");
2089 } 2040 } else
2090 else
2091 seq_printf(seq, "<root>: "); 2041 seq_printf(seq, "<root>: ");
2092 seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n); 2042 seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n);
2093 2043
2094 if (IS_LEAF(n))
2095 seq_printf(seq, "key=%d.%d.%d.%d\n",
2096 n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) % 256, n->key % 256);
2097 else {
2098 int plen = ((struct tnode *)n)->pos;
2099 t_key prf=MASK_PFX(n->key, plen);
2100 seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
2101 prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf % 256, plen);
2102 }
2103 if (IS_LEAF(n)) { 2044 if (IS_LEAF(n)) {
2104 struct leaf *l=(struct leaf *)n; 2045 struct leaf *l = (struct leaf *)n;
2105 struct fib_alias *fa; 2046 struct fib_alias *fa;
2106 int i; 2047 int i;
2107 for (i=32; i>=0; i--) 2048
2108 if (find_leaf_info(&l->list, i)) { 2049 seq_printf(seq, "key=%d.%d.%d.%d\n",
2109 2050 n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) % 256, n->key % 256);
2051
2052 for (i = 32; i >= 0; i--)
2053 if (find_leaf_info(&l->list, i)) {
2110 struct list_head *fa_head = get_fa_head(l, i); 2054 struct list_head *fa_head = get_fa_head(l, i);
2111 2055
2112 if (!fa_head) 2056 if (!fa_head)
2113 continue; 2057 continue;
2114 2058
@@ -2118,17 +2062,16 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2118 putspace_seq(seq, indent+2); 2062 putspace_seq(seq, indent+2);
2119 seq_printf(seq, "{/%d...dumping}\n", i); 2063 seq_printf(seq, "{/%d...dumping}\n", i);
2120 2064
2121
2122 list_for_each_entry(fa, fa_head, fa_list) { 2065 list_for_each_entry(fa, fa_head, fa_list) {
2123 putspace_seq(seq, indent+2); 2066 putspace_seq(seq, indent+2);
2124 if (fa->fa_info->fib_nh == NULL) {
2125 seq_printf(seq, "Error _fib_nh=NULL\n");
2126 continue;
2127 }
2128 if (fa->fa_info == NULL) { 2067 if (fa->fa_info == NULL) {
2129 seq_printf(seq, "Error fa_info=NULL\n"); 2068 seq_printf(seq, "Error fa_info=NULL\n");
2130 continue; 2069 continue;
2131 } 2070 }
2071 if (fa->fa_info->fib_nh == NULL) {
2072 seq_printf(seq, "Error _fib_nh=NULL\n");
2073 continue;
2074 }
2132 2075
2133 seq_printf(seq, "{type=%d scope=%d TOS=%d}\n", 2076 seq_printf(seq, "{type=%d scope=%d TOS=%d}\n",
2134 fa->fa_type, 2077 fa->fa_type,
@@ -2136,11 +2079,16 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2136 fa->fa_tos); 2079 fa->fa_tos);
2137 } 2080 }
2138 } 2081 }
2139 } 2082 } else {
2140 else if (IS_TNODE(n)) {
2141 struct tnode *tn = (struct tnode *)n; 2083 struct tnode *tn = (struct tnode *)n;
2084 int plen = ((struct tnode *)n)->pos;
2085 t_key prf = MASK_PFX(n->key, plen);
2086
2087 seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
2088 prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf % 256, plen);
2089
2142 putspace_seq(seq, indent); seq_printf(seq, "| "); 2090 putspace_seq(seq, indent); seq_printf(seq, "| ");
2143 seq_printf(seq, "{key prefix=%08x/", tn->key&TKEY_GET_MASK(0, tn->pos)); 2091 seq_printf(seq, "{key prefix=%08x/", tn->key & TKEY_GET_MASK(0, tn->pos));
2144 printbin_seq(seq, tkey_extract_bits(tn->key, 0, tn->pos), tn->pos); 2092 printbin_seq(seq, tkey_extract_bits(tn->key, 0, tn->pos), tn->pos);
2145 seq_printf(seq, "}\n"); 2093 seq_printf(seq, "}\n");
2146 putspace_seq(seq, indent); seq_printf(seq, "| "); 2094 putspace_seq(seq, indent); seq_printf(seq, "| ");
@@ -2155,100 +2103,103 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2155static void trie_dump_seq(struct seq_file *seq, struct trie *t) 2103static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2156{ 2104{
2157 struct node *n = t->trie; 2105 struct node *n = t->trie;
2158 int cindex=0; 2106 int cindex = 0;
2159 int indent=1; 2107 int indent = 1;
2160 int pend=0; 2108 int pend = 0;
2161 int depth = 0; 2109 int depth = 0;
2110 struct tnode *tn;
2162 2111
2163 read_lock(&fib_lock); 2112 read_lock(&fib_lock);
2164 2113
2165 seq_printf(seq, "------ trie_dump of t=%p ------\n", t); 2114 seq_printf(seq, "------ trie_dump of t=%p ------\n", t);
2166 if (n) {
2167 printnode_seq(seq, indent, n, pend, cindex, 0);
2168 if (IS_TNODE(n)) {
2169 struct tnode *tn = (struct tnode *)n;
2170 pend = tn->pos+tn->bits;
2171 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2172 indent += 3;
2173 depth++;
2174
2175 while (tn && cindex < (1 << tn->bits)) {
2176 if (tn->child[cindex]) {
2177
2178 /* Got a child */
2179
2180 printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits);
2181 if (IS_LEAF(tn->child[cindex])) {
2182 cindex++;
2183
2184 }
2185 else {
2186 /*
2187 * New tnode. Decend one level
2188 */
2189
2190 depth++;
2191 n = tn->child[cindex];
2192 tn = (struct tnode *)n;
2193 pend = tn->pos+tn->bits;
2194 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2195 indent+=3;
2196 cindex=0;
2197 }
2198 }
2199 else
2200 cindex++;
2201 2115
2116 if (!n) {
2117 seq_printf(seq, "------ trie is empty\n");
2118
2119 read_unlock(&fib_lock);
2120 return;
2121 }
2122
2123 printnode_seq(seq, indent, n, pend, cindex, 0);
2124
2125 if (!IS_TNODE(n)) {
2126 read_unlock(&fib_lock);
2127 return;
2128 }
2129
2130 tn = (struct tnode *)n;
2131 pend = tn->pos+tn->bits;
2132 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2133 indent += 3;
2134 depth++;
2135
2136 while (tn && cindex < (1 << tn->bits)) {
2137 if (tn->child[cindex]) {
2138 /* Got a child */
2139
2140 printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits);
2141 if (IS_LEAF(tn->child[cindex])) {
2142 cindex++;
2143 } else {
2202 /* 2144 /*
2203 * Test if we are done 2145 * New tnode. Decend one level
2204 */ 2146 */
2205
2206 while (cindex >= (1 << tn->bits)) {
2207 2147
2208 /* 2148 depth++;
2209 * Move upwards and test for root 2149 tn = (struct tnode *)tn->child[cindex];
2210 * pop off all traversed nodes 2150 pend = tn->pos + tn->bits;
2211 */ 2151 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2212 2152 indent += 3;
2213 if (NODE_PARENT(tn) == NULL) { 2153 cindex = 0;
2214 tn = NULL;
2215 n = NULL;
2216 break;
2217 }
2218 else {
2219 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2220 tn = NODE_PARENT(tn);
2221 cindex++;
2222 n = (struct node *)tn;
2223 pend = tn->pos+tn->bits;
2224 indent-=3;
2225 depth--;
2226 }
2227 }
2228 } 2154 }
2155 } else
2156 cindex++;
2157
2158 /*
2159 * Test if we are done
2160 */
2161
2162 while (cindex >= (1 << tn->bits)) {
2163 /*
2164 * Move upwards and test for root
2165 * pop off all traversed nodes
2166 */
2167
2168 if (NODE_PARENT(tn) == NULL) {
2169 tn = NULL;
2170 break;
2171 }
2172
2173 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2174 cindex++;
2175 tn = NODE_PARENT(tn);
2176 pend = tn->pos + tn->bits;
2177 indent -= 3;
2178 depth--;
2229 } 2179 }
2230 else n = NULL;
2231 } 2180 }
2232 else seq_printf(seq, "------ trie is empty\n");
2233 2181
2234 read_unlock(&fib_lock); 2182 read_unlock(&fib_lock);
2235} 2183}
2236 2184
2237static struct trie_stat *trie_stat_new(void) 2185static struct trie_stat *trie_stat_new(void)
2238{ 2186{
2239 struct trie_stat *s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL); 2187 struct trie_stat *s;
2240 int i; 2188 int i;
2241 2189
2242 if (s) { 2190 s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL);
2243 s->totdepth = 0; 2191 if (!s)
2244 s->maxdepth = 0; 2192 return NULL;
2245 s->tnodes = 0; 2193
2246 s->leaves = 0; 2194 s->totdepth = 0;
2247 s->nullpointers = 0; 2195 s->maxdepth = 0;
2248 2196 s->tnodes = 0;
2249 for(i=0; i< MAX_CHILDS; i++) 2197 s->leaves = 0;
2250 s->nodesizes[i] = 0; 2198 s->nullpointers = 0;
2251 } 2199
2200 for (i = 0; i < MAX_CHILDS; i++)
2201 s->nodesizes[i] = 0;
2202
2252 return s; 2203 return s;
2253} 2204}
2254 2205
@@ -2257,91 +2208,81 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2257 struct node *n = t->trie; 2208 struct node *n = t->trie;
2258 struct trie_stat *s = trie_stat_new(); 2209 struct trie_stat *s = trie_stat_new();
2259 int cindex = 0; 2210 int cindex = 0;
2260 int indent = 1;
2261 int pend = 0; 2211 int pend = 0;
2262 int depth = 0; 2212 int depth = 0;
2263 2213
2264 read_lock(&fib_lock); 2214 if (!s)
2215 return NULL;
2216 if (!n)
2217 return s;
2265 2218
2266 if (s) { 2219 read_lock(&fib_lock);
2267 if (n) {
2268 if (IS_TNODE(n)) {
2269 struct tnode *tn = (struct tnode *)n;
2270 pend = tn->pos+tn->bits;
2271 indent += 3;
2272 s->nodesizes[tn->bits]++;
2273 depth++;
2274 2220
2275 while (tn && cindex < (1 << tn->bits)) { 2221 if (IS_TNODE(n)) {
2276 if (tn->child[cindex]) { 2222 struct tnode *tn = (struct tnode *)n;
2277 /* Got a child */ 2223 pend = tn->pos+tn->bits;
2278 2224 s->nodesizes[tn->bits]++;
2279 if (IS_LEAF(tn->child[cindex])) { 2225 depth++;
2280 cindex++; 2226
2281 2227 while (tn && cindex < (1 << tn->bits)) {
2282 /* stats */ 2228 if (tn->child[cindex]) {
2283 if (depth > s->maxdepth) 2229 /* Got a child */
2284 s->maxdepth = depth;
2285 s->totdepth += depth;
2286 s->leaves++;
2287 }
2288
2289 else {
2290 /*
2291 * New tnode. Decend one level
2292 */
2293
2294 s->tnodes++;
2295 s->nodesizes[tn->bits]++;
2296 depth++;
2297
2298 n = tn->child[cindex];
2299 tn = (struct tnode *)n;
2300 pend = tn->pos+tn->bits;
2301
2302 indent += 3;
2303 cindex = 0;
2304 }
2305 }
2306 else {
2307 cindex++;
2308 s->nullpointers++;
2309 }
2310 2230
2231 if (IS_LEAF(tn->child[cindex])) {
2232 cindex++;
2233
2234 /* stats */
2235 if (depth > s->maxdepth)
2236 s->maxdepth = depth;
2237 s->totdepth += depth;
2238 s->leaves++;
2239 } else {
2311 /* 2240 /*
2312 * Test if we are done 2241 * New tnode. Decend one level
2313 */ 2242 */
2314 2243
2315 while (cindex >= (1 << tn->bits)) { 2244 s->tnodes++;
2316 2245 s->nodesizes[tn->bits]++;
2317 /* 2246 depth++;
2318 * Move upwards and test for root 2247
2319 * pop off all traversed nodes 2248 n = tn->child[cindex];
2320 */ 2249 tn = (struct tnode *)n;
2321 2250 pend = tn->pos+tn->bits;
2322 2251
2323 if (NODE_PARENT(tn) == NULL) { 2252 cindex = 0;
2324 tn = NULL;
2325 n = NULL;
2326 break;
2327 }
2328 else {
2329 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2330 tn = NODE_PARENT(tn);
2331 cindex++;
2332 n = (struct node *)tn;
2333 pend = tn->pos+tn->bits;
2334 indent -= 3;
2335 depth--;
2336 }
2337 }
2338 } 2253 }
2254 } else {
2255 cindex++;
2256 s->nullpointers++;
2339 } 2257 }
2340 else n = NULL; 2258
2259 /*
2260 * Test if we are done
2261 */
2262
2263 while (cindex >= (1 << tn->bits)) {
2264 /*
2265 * Move upwards and test for root
2266 * pop off all traversed nodes
2267 */
2268
2269 if (NODE_PARENT(tn) == NULL) {
2270 tn = NULL;
2271 n = NULL;
2272 break;
2273 }
2274
2275 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2276 tn = NODE_PARENT(tn);
2277 cindex++;
2278 n = (struct node *)tn;
2279 pend = tn->pos+tn->bits;
2280 depth--;
2281 }
2341 } 2282 }
2342 } 2283 }
2343 2284
2344 read_unlock(&fib_lock); 2285 read_unlock(&fib_lock);
2345 return s; 2286 return s;
2346} 2287}
2347 2288
@@ -2359,17 +2300,22 @@ static struct fib_alias *fib_triestat_get_next(struct seq_file *seq)
2359 2300
2360static void *fib_triestat_seq_start(struct seq_file *seq, loff_t *pos) 2301static void *fib_triestat_seq_start(struct seq_file *seq, loff_t *pos)
2361{ 2302{
2362 void *v = NULL; 2303 if (!ip_fib_main_table)
2304 return NULL;
2363 2305
2364 if (ip_fib_main_table) 2306 if (*pos)
2365 v = *pos ? fib_triestat_get_next(seq) : SEQ_START_TOKEN; 2307 return fib_triestat_get_next(seq);
2366 return v; 2308 else
2309 return SEQ_START_TOKEN;
2367} 2310}
2368 2311
2369static void *fib_triestat_seq_next(struct seq_file *seq, void *v, loff_t *pos) 2312static void *fib_triestat_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2370{ 2313{
2371 ++*pos; 2314 ++*pos;
2372 return v == SEQ_START_TOKEN ? fib_triestat_get_first(seq) : fib_triestat_get_next(seq); 2315 if (v == SEQ_START_TOKEN)
2316 return fib_triestat_get_first(seq);
2317 else
2318 return fib_triestat_get_next(seq);
2373} 2319}
2374 2320
2375static void fib_triestat_seq_stop(struct seq_file *seq, void *v) 2321static void fib_triestat_seq_stop(struct seq_file *seq, void *v)
@@ -2388,22 +2334,22 @@ static void collect_and_show(struct trie *t, struct seq_file *seq)
2388{ 2334{
2389 int bytes = 0; /* How many bytes are used, a ref is 4 bytes */ 2335 int bytes = 0; /* How many bytes are used, a ref is 4 bytes */
2390 int i, max, pointers; 2336 int i, max, pointers;
2391 struct trie_stat *stat; 2337 struct trie_stat *stat;
2392 int avdepth; 2338 int avdepth;
2393 2339
2394 stat = trie_collect_stats(t); 2340 stat = trie_collect_stats(t);
2395 2341
2396 bytes=0; 2342 bytes = 0;
2397 seq_printf(seq, "trie=%p\n", t); 2343 seq_printf(seq, "trie=%p\n", t);
2398 2344
2399 if (stat) { 2345 if (stat) {
2400 if (stat->leaves) 2346 if (stat->leaves)
2401 avdepth=stat->totdepth*100 / stat->leaves; 2347 avdepth = stat->totdepth*100 / stat->leaves;
2402 else 2348 else
2403 avdepth=0; 2349 avdepth = 0;
2404 seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth % 100 ); 2350 seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth % 100);
2405 seq_printf(seq, "Max depth: %4d\n", stat->maxdepth); 2351 seq_printf(seq, "Max depth: %4d\n", stat->maxdepth);
2406 2352
2407 seq_printf(seq, "Leaves: %d\n", stat->leaves); 2353 seq_printf(seq, "Leaves: %d\n", stat->leaves);
2408 bytes += sizeof(struct leaf) * stat->leaves; 2354 bytes += sizeof(struct leaf) * stat->leaves;
2409 seq_printf(seq, "Internal nodes: %d\n", stat->tnodes); 2355 seq_printf(seq, "Internal nodes: %d\n", stat->tnodes);
@@ -2455,11 +2401,9 @@ static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2455 2401
2456 if (trie_main) 2402 if (trie_main)
2457 collect_and_show(trie_main, seq); 2403 collect_and_show(trie_main, seq);
2458 } 2404 } else {
2459 else { 2405 snprintf(bf, sizeof(bf), "*\t%08X\t%08X", 200, 400);
2460 snprintf(bf, sizeof(bf), 2406
2461 "*\t%08X\t%08X", 200, 400);
2462
2463 seq_printf(seq, "%-127s\n", bf); 2407 seq_printf(seq, "%-127s\n", bf);
2464 } 2408 }
2465 return 0; 2409 return 0;
@@ -2520,22 +2464,27 @@ static struct fib_alias *fib_trie_get_next(struct seq_file *seq)
2520 2464
2521static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos) 2465static void *fib_trie_seq_start(struct seq_file *seq, loff_t *pos)
2522{ 2466{
2523 void *v = NULL; 2467 if (!ip_fib_main_table)
2468 return NULL;
2524 2469
2525 if (ip_fib_main_table) 2470 if (*pos)
2526 v = *pos ? fib_trie_get_next(seq) : SEQ_START_TOKEN; 2471 return fib_trie_get_next(seq);
2527 return v; 2472 else
2473 return SEQ_START_TOKEN;
2528} 2474}
2529 2475
2530static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos) 2476static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2531{ 2477{
2532 ++*pos; 2478 ++*pos;
2533 return v == SEQ_START_TOKEN ? fib_trie_get_first(seq) : fib_trie_get_next(seq); 2479 if (v == SEQ_START_TOKEN)
2480 return fib_trie_get_first(seq);
2481 else
2482 return fib_trie_get_next(seq);
2483
2534} 2484}
2535 2485
2536static void fib_trie_seq_stop(struct seq_file *seq, void *v) 2486static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2537{ 2487{
2538
2539} 2488}
2540 2489
2541/* 2490/*
@@ -2555,9 +2504,7 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
2555 2504
2556 if (trie_main) 2505 if (trie_main)
2557 trie_dump_seq(seq, trie_main); 2506 trie_dump_seq(seq, trie_main);
2558 } 2507 } else {
2559
2560 else {
2561 snprintf(bf, sizeof(bf), 2508 snprintf(bf, sizeof(bf),
2562 "*\t%08X\t%08X", 200, 400); 2509 "*\t%08X\t%08X", 200, 400);
2563 seq_printf(seq, "%-127s\n", bf); 2510 seq_printf(seq, "%-127s\n", bf);
generated by cgit v1.2.2 (git 2.25.0) at 2024-10-04 21:22:34 -0400