aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c772
1 files changed, 387 insertions, 385 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 4be234c7d8c3..a701405fab0b 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -90,14 +90,14 @@ typedef unsigned int t_key;
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)
@@ -147,7 +147,7 @@ struct trie_stat {
147 unsigned int leaves; 147 unsigned int leaves;
148 unsigned int nullpointers; 148 unsigned int nullpointers;
149 unsigned int nodesizes[MAX_CHILDS]; 149 unsigned int nodesizes[MAX_CHILDS];
150}; 150};
151 151
152struct trie { 152struct trie {
153 struct node *trie; 153 struct node *trie;
@@ -185,9 +185,9 @@ static void trie_bug(char *err)
185 BUG(); 185 BUG();
186} 186}
187 187
188static inline struct node *tnode_get_child(struct tnode *tn, int i) 188static inline struct node *tnode_get_child(struct tnode *tn, int i)
189{ 189{
190 if (i >= 1<<tn->bits) 190 if (i >= 1<<tn->bits)
191 trie_bug("tnode_get_child"); 191 trie_bug("tnode_get_child");
192 192
193 return tn->child[i]; 193 return tn->child[i];
@@ -202,7 +202,7 @@ static inline int tnode_child_length(struct tnode *tn)
202 _________________________________________________________________ 202 _________________________________________________________________
203 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C | 203 | i | i | i | i | i | i | i | N | N | N | S | S | S | S | S | C |
204 ---------------------------------------------------------------- 204 ----------------------------------------------------------------
205 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 205 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
206 206
207 _________________________________________________________________ 207 _________________________________________________________________
208 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u | 208 | C | C | C | u | u | u | u | u | u | u | u | u | u | u | u | u |
@@ -226,25 +226,25 @@ static inline t_key tkey_extract_bits(t_key a, int offset, int bits)
226 226
227static inline int tkey_equals(t_key a, t_key b) 227static inline int tkey_equals(t_key a, t_key b)
228{ 228{
229 return a == b; 229 return a == b;
230} 230}
231 231
232static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b) 232static inline int tkey_sub_equals(t_key a, int offset, int bits, t_key b)
233{ 233{
234 if (bits == 0 || offset >= KEYLENGTH) 234 if (bits == 0 || offset >= KEYLENGTH)
235 return 1; 235 return 1;
236 bits = bits > KEYLENGTH ? KEYLENGTH : bits; 236 bits = bits > KEYLENGTH ? KEYLENGTH : bits;
237 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0; 237 return ((a ^ b) << offset) >> (KEYLENGTH - bits) == 0;
238} 238}
239 239
240static inline int tkey_mismatch(t_key a, int offset, t_key b) 240static inline int tkey_mismatch(t_key a, int offset, t_key b)
241{ 241{
242 t_key diff = a ^ b; 242 t_key diff = a ^ b;
243 int i = offset; 243 int i = offset;
244 244
245 if(!diff) 245 if (!diff)
246 return 0; 246 return 0;
247 while((diff << i) >> (KEYLENGTH-1) == 0) 247 while ((diff << i) >> (KEYLENGTH-1) == 0)
248 i++; 248 i++;
249 return i; 249 return i;
250} 250}
@@ -314,6 +314,7 @@ static void fn_free_alias(struct fib_alias *fa)
314 The bits from (n->pos) to (n->pos + n->bits - 1) - "C" - are the index into 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. 315 n's child array, and will of course be different for each child.
316 316
317
317 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown 318 The rest of the bits, from (n->pos + n->bits) onward, are completely unknown
318 at this point. 319 at this point.
319 320
@@ -321,7 +322,7 @@ static void fn_free_alias(struct fib_alias *fa)
321 322
322static void check_tnode(struct tnode *tn) 323static void check_tnode(struct tnode *tn)
323{ 324{
324 if(tn && tn->pos+tn->bits > 32) { 325 if (tn && tn->pos+tn->bits > 32) {
325 printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos, tn->bits); 326 printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos, tn->bits);
326 } 327 }
327} 328}
@@ -332,7 +333,7 @@ static int inflate_threshold = 50;
332static struct leaf *leaf_new(void) 333static struct leaf *leaf_new(void)
333{ 334{
334 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL); 335 struct leaf *l = kmalloc(sizeof(struct leaf), GFP_KERNEL);
335 if(l) { 336 if (l) {
336 NODE_INIT_PARENT(l, T_LEAF); 337 NODE_INIT_PARENT(l, T_LEAF);
337 INIT_HLIST_HEAD(&l->list); 338 INIT_HLIST_HEAD(&l->list);
338 } 339 }
@@ -342,7 +343,7 @@ static struct leaf *leaf_new(void)
342static struct leaf_info *leaf_info_new(int plen) 343static struct leaf_info *leaf_info_new(int plen)
343{ 344{
344 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL); 345 struct leaf_info *li = kmalloc(sizeof(struct leaf_info), GFP_KERNEL);
345 if(li) { 346 if (li) {
346 li->plen = plen; 347 li->plen = plen;
347 INIT_LIST_HEAD(&li->falh); 348 INIT_LIST_HEAD(&li->falh);
348 } 349 }
@@ -365,7 +366,7 @@ static struct tnode *tnode_alloc(unsigned int size)
365 return kmalloc(size, GFP_KERNEL); 366 return kmalloc(size, GFP_KERNEL);
366 } else { 367 } else {
367 return (struct tnode *) 368 return (struct tnode *)
368 __get_free_pages(GFP_KERNEL, get_order(size)); 369 __get_free_pages(GFP_KERNEL, get_order(size));
369 } 370 }
370} 371}
371 372
@@ -386,7 +387,7 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
386 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *); 387 int sz = sizeof(struct tnode) + nchildren * sizeof(struct node *);
387 struct tnode *tn = tnode_alloc(sz); 388 struct tnode *tn = tnode_alloc(sz);
388 389
389 if(tn) { 390 if (tn) {
390 memset(tn, 0, sz); 391 memset(tn, 0, sz);
391 NODE_INIT_PARENT(tn, T_TNODE); 392 NODE_INIT_PARENT(tn, T_TNODE);
392 tn->pos = pos; 393 tn->pos = pos;
@@ -395,7 +396,8 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
395 tn->full_children = 0; 396 tn->full_children = 0;
396 tn->empty_children = 1<<bits; 397 tn->empty_children = 1<<bits;
397 } 398 }
398 if(trie_debug > 0) 399
400 if (trie_debug > 0)
399 printk("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),
400 (unsigned int) (sizeof(struct node) * 1<<bits)); 402 (unsigned int) (sizeof(struct node) * 1<<bits));
401 return tn; 403 return tn;
@@ -403,17 +405,17 @@ static struct tnode* tnode_new(t_key key, int pos, int bits)
403 405
404static void tnode_free(struct tnode *tn) 406static void tnode_free(struct tnode *tn)
405{ 407{
406 if(!tn) { 408 if (!tn) {
407 trie_bug("tnode_free\n"); 409 trie_bug("tnode_free\n");
408 } 410 }
409 if(IS_LEAF(tn)) { 411 if (IS_LEAF(tn)) {
410 free_leaf((struct leaf *)tn); 412 free_leaf((struct leaf *)tn);
411 if(trie_debug > 0 ) 413 if (trie_debug > 0 )
412 printk("FL %p \n", tn); 414 printk("FL %p \n", tn);
413 } 415 }
414 else if(IS_TNODE(tn)) { 416 else if (IS_TNODE(tn)) {
415 __tnode_free(tn); 417 __tnode_free(tn);
416 if(trie_debug > 0 ) 418 if (trie_debug > 0 )
417 printk("FT %p \n", tn); 419 printk("FT %p \n", tn);
418 } 420 }
419 else { 421 else {
@@ -428,58 +430,58 @@ static void tnode_free(struct tnode *tn)
428 430
429static inline int tnode_full(struct tnode *tn, struct node *n) 431static inline int tnode_full(struct tnode *tn, struct node *n)
430{ 432{
431 if(n == NULL || IS_LEAF(n)) 433 if (n == NULL || IS_LEAF(n))
432 return 0; 434 return 0;
433 435
434 return ((struct tnode *) n)->pos == tn->pos + tn->bits; 436 return ((struct tnode *) n)->pos == tn->pos + tn->bits;
435} 437}
436 438
437static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n) 439static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n)
438{ 440{
439 tnode_put_child_reorg(tn, i, n, -1); 441 tnode_put_child_reorg(tn, i, n, -1);
440} 442}
441 443
442 /* 444 /*
443 * Add a child at position i overwriting the old value. 445 * Add a child at position i overwriting the old value.
444 * Update the value of full_children and empty_children. 446 * Update the value of full_children and empty_children.
445 */ 447 */
446 448
447static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull) 449static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull)
448{ 450{
449 struct node *chi; 451 struct node *chi;
450 int isfull; 452 int isfull;
451 453
452 if(i >= 1<<tn->bits) { 454 if (i >= 1<<tn->bits) {
453 printk("bits=%d, i=%d\n", tn->bits, i); 455 printk("bits=%d, i=%d\n", tn->bits, i);
454 trie_bug("tnode_put_child_reorg bits"); 456 trie_bug("tnode_put_child_reorg bits");
455 } 457 }
456 write_lock_bh(&fib_lock); 458 write_lock_bh(&fib_lock);
457 chi = tn->child[i]; 459 chi = tn->child[i];
458 460
459 /* update emptyChildren */ 461 /* update emptyChildren */
460 if (n == NULL && chi != NULL) 462 if (n == NULL && chi != NULL)
461 tn->empty_children++; 463 tn->empty_children++;
462 else if (n != NULL && chi == NULL) 464 else if (n != NULL && chi == NULL)
463 tn->empty_children--; 465 tn->empty_children--;
464 466
465 /* update fullChildren */ 467 /* update fullChildren */
466 if (wasfull == -1) 468 if (wasfull == -1)
467 wasfull = tnode_full(tn, chi); 469 wasfull = tnode_full(tn, chi);
468 470
469 isfull = tnode_full(tn, n); 471 isfull = tnode_full(tn, n);
470 if (wasfull && !isfull) 472 if (wasfull && !isfull)
471 tn->full_children--; 473 tn->full_children--;
472 474
473 else if (!wasfull && isfull) 475 else if (!wasfull && isfull)
474 tn->full_children++; 476 tn->full_children++;
475 if(n) 477 if (n)
476 NODE_SET_PARENT(n, tn); 478 NODE_SET_PARENT(n, tn);
477 479
478 tn->child[i] = n; 480 tn->child[i] = n;
479 write_unlock_bh(&fib_lock); 481 write_unlock_bh(&fib_lock);
480} 482}
481 483
482static struct node *resize(struct trie *t, struct tnode *tn) 484static struct node *resize(struct trie *t, struct tnode *tn)
483{ 485{
484 int i; 486 int i;
485 int err = 0; 487 int err = 0;
@@ -487,8 +489,8 @@ static struct node *resize(struct trie *t, struct tnode *tn)
487 if (!tn) 489 if (!tn)
488 return NULL; 490 return NULL;
489 491
490 if(trie_debug) 492 if (trie_debug)
491 printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n", 493 printk("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
492 tn, inflate_threshold, halve_threshold); 494 tn, inflate_threshold, halve_threshold);
493 495
494 /* No children */ 496 /* No children */
@@ -505,7 +507,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
505 507
506 /* compress one level */ 508 /* compress one level */
507 struct node *n = tn->child[i]; 509 struct node *n = tn->child[i];
508 if(n) 510 if (n)
509 NODE_INIT_PARENT(n, NODE_TYPE(n)); 511 NODE_INIT_PARENT(n, NODE_TYPE(n));
510 512
511 write_unlock_bh(&fib_lock); 513 write_unlock_bh(&fib_lock);
@@ -514,72 +516,72 @@ static struct node *resize(struct trie *t, struct tnode *tn)
514 } 516 }
515 write_unlock_bh(&fib_lock); 517 write_unlock_bh(&fib_lock);
516 } 518 }
517 /* 519 /*
518 * Double as long as the resulting node has a number of 520 * Double as long as the resulting node has a number of
519 * nonempty nodes that are above the threshold. 521 * nonempty nodes that are above the threshold.
520 */ 522 */
521 523
522 /* 524 /*
523 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of 525 * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
524 * the Helsinki University of Technology and Matti Tikkanen of Nokia 526 * the Helsinki University of Technology and Matti Tikkanen of Nokia
525 * Telecommunications, page 6: 527 * Telecommunications, page 6:
526 * "A node is doubled if the ratio of non-empty children to all 528 * "A node is doubled if the ratio of non-empty children to all
527 * children in the *doubled* node is at least 'high'." 529 * children in the *doubled* node is at least 'high'."
528 * 530 *
529 * 'high' in this instance is the variable 'inflate_threshold'. It 531 * 'high' in this instance is the variable 'inflate_threshold'. It
530 * is expressed as a percentage, so we multiply it with 532 * is expressed as a percentage, so we multiply it with
531 * tnode_child_length() and instead of multiplying by 2 (since the 533 * tnode_child_length() and instead of multiplying by 2 (since the
532 * child array will be doubled by inflate()) and multiplying 534 * child array will be doubled by inflate()) and multiplying
533 * the left-hand side by 100 (to handle the percentage thing) we 535 * the left-hand side by 100 (to handle the percentage thing) we
534 * multiply the left-hand side by 50. 536 * multiply the left-hand side by 50.
535 * 537 *
536 * The left-hand side may look a bit weird: tnode_child_length(tn) 538 * 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 539 * - 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" 540 * 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. 541 * 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 542 * All of those will be doubled in the resulting inflated tnode, so
541 * we just count them one extra time here. 543 * we just count them one extra time here.
542 * 544 *
543 * A clearer way to write this would be: 545 * A clearer way to write this would be:
544 * 546 *
545 * to_be_doubled = tn->full_children; 547 * to_be_doubled = tn->full_children;
546 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - 548 * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
547 * tn->full_children; 549 * tn->full_children;
548 * 550 *
549 * new_child_length = tnode_child_length(tn) * 2; 551 * new_child_length = tnode_child_length(tn) * 2;
550 * 552 *
551 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / 553 * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
552 * new_child_length; 554 * new_child_length;
553 * if (new_fill_factor >= inflate_threshold) 555 * if (new_fill_factor >= inflate_threshold)
554 * 556 *
555 * ...and so on, tho it would mess up the while() loop. 557 * ...and so on, tho it would mess up the while () loop.
556 * 558 *
557 * anyway, 559 * anyway,
558 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= 560 * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
559 * inflate_threshold 561 * inflate_threshold
560 * 562 *
561 * avoid a division: 563 * avoid a division:
562 * 100 * (not_to_be_doubled + 2*to_be_doubled) >= 564 * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
563 * inflate_threshold * new_child_length 565 * inflate_threshold * new_child_length
564 * 566 *
565 * expand not_to_be_doubled and to_be_doubled, and shorten: 567 * expand not_to_be_doubled and to_be_doubled, and shorten:
566 * 100 * (tnode_child_length(tn) - tn->empty_children + 568 * 100 * (tnode_child_length(tn) - tn->empty_children +
567 * tn->full_children ) >= inflate_threshold * new_child_length 569 * tn->full_children ) >= inflate_threshold * new_child_length
568 * 570 *
569 * expand new_child_length: 571 * expand new_child_length:
570 * 100 * (tnode_child_length(tn) - tn->empty_children + 572 * 100 * (tnode_child_length(tn) - tn->empty_children +
571 * tn->full_children ) >= 573 * tn->full_children ) >=
572 * inflate_threshold * tnode_child_length(tn) * 2 574 * inflate_threshold * tnode_child_length(tn) * 2
573 * 575 *
574 * shorten again: 576 * shorten again:
575 * 50 * (tn->full_children + tnode_child_length(tn) - 577 * 50 * (tn->full_children + tnode_child_length(tn) -
576 * tn->empty_children ) >= inflate_threshold * 578 * tn->empty_children ) >= inflate_threshold *
577 * tnode_child_length(tn) 579 * tnode_child_length(tn)
578 * 580 *
579 */ 581 */
580 582
581 check_tnode(tn); 583 check_tnode(tn);
582 584
583 err = 0; 585 err = 0;
584 while ((tn->full_children > 0 && 586 while ((tn->full_children > 0 &&
585 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= 587 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >=
@@ -587,7 +589,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
587 589
588 tn = inflate(t, tn, &err); 590 tn = inflate(t, tn, &err);
589 591
590 if(err) { 592 if (err) {
591#ifdef CONFIG_IP_FIB_TRIE_STATS 593#ifdef CONFIG_IP_FIB_TRIE_STATS
592 t->stats.resize_node_skipped++; 594 t->stats.resize_node_skipped++;
593#endif 595#endif
@@ -609,7 +611,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
609 611
610 tn = halve(t, tn, &err); 612 tn = halve(t, tn, &err);
611 613
612 if(err) { 614 if (err) {
613#ifdef CONFIG_IP_FIB_TRIE_STATS 615#ifdef CONFIG_IP_FIB_TRIE_STATS
614 t->stats.resize_node_skipped++; 616 t->stats.resize_node_skipped++;
615#endif 617#endif
@@ -617,18 +619,18 @@ static struct node *resize(struct trie *t, struct tnode *tn)
617 } 619 }
618 } 620 }
619 621
620 622
621 /* Only one child remains */ 623 /* Only one child remains */
622 624
623 if (tn->empty_children == tnode_child_length(tn) - 1) 625 if (tn->empty_children == tnode_child_length(tn) - 1)
624 for (i = 0; i < tnode_child_length(tn); i++) { 626 for (i = 0; i < tnode_child_length(tn); i++) {
625 627
626 write_lock_bh(&fib_lock); 628 write_lock_bh(&fib_lock);
627 if (tn->child[i] != NULL) { 629 if (tn->child[i] != NULL) {
628 /* compress one level */ 630 /* compress one level */
629 struct node *n = tn->child[i]; 631 struct node *n = tn->child[i];
630 632
631 if(n) 633 if (n)
632 NODE_INIT_PARENT(n, NODE_TYPE(n)); 634 NODE_INIT_PARENT(n, NODE_TYPE(n));
633 635
634 write_unlock_bh(&fib_lock); 636 write_unlock_bh(&fib_lock);
@@ -648,7 +650,7 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
648 int olen = tnode_child_length(tn); 650 int olen = tnode_child_length(tn);
649 int i; 651 int i;
650 652
651 if(trie_debug) 653 if (trie_debug)
652 printk("In inflate\n"); 654 printk("In inflate\n");
653 655
654 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); 656 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1);
@@ -659,12 +661,12 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
659 } 661 }
660 662
661 /* 663 /*
662 * Preallocate and store tnodes before the actual work so we 664 * Preallocate and store tnodes before the actual work so we
663 * don't get into an inconsistent state if memory allocation 665 * don't get into an inconsistent state if memory allocation
664 * fails. In case of failure we return the oldnode and inflate 666 * fails. In case of failure we return the oldnode and inflate
665 * of tnode is ignored. 667 * of tnode is ignored.
666 */ 668 */
667 669
668 for(i = 0; i < olen; i++) { 670 for(i = 0; i < olen; i++) {
669 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i); 671 struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i);
670 672
@@ -675,20 +677,20 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
675 struct tnode *left, *right; 677 struct tnode *left, *right;
676 678
677 t_key m = TKEY_GET_MASK(inode->pos, 1); 679 t_key m = TKEY_GET_MASK(inode->pos, 1);
678 680
679 left = tnode_new(inode->key&(~m), inode->pos + 1, 681 left = tnode_new(inode->key&(~m), inode->pos + 1,
680 inode->bits - 1); 682 inode->bits - 1);
681 683
682 if(!left) { 684 if (!left) {
683 *err = -ENOMEM; 685 *err = -ENOMEM;
684 break; 686 break;
685 } 687 }
686 688
687 right = tnode_new(inode->key|m, inode->pos + 1, 689 right = tnode_new(inode->key|m, inode->pos + 1,
688 inode->bits - 1); 690 inode->bits - 1);
689 691
690 if(!right) { 692 if (!right) {
691 *err = -ENOMEM; 693 *err = -ENOMEM;
692 break; 694 break;
693 } 695 }
694 696
@@ -697,32 +699,32 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
697 } 699 }
698 } 700 }
699 701
700 if(*err) { 702 if (*err) {
701 int size = tnode_child_length(tn); 703 int size = tnode_child_length(tn);
702 int j; 704 int j;
703 705
704 for(j = 0; j < size; j++) 706 for(j = 0; j < size; j++)
705 if( tn->child[j]) 707 if (tn->child[j])
706 tnode_free((struct tnode *)tn->child[j]); 708 tnode_free((struct tnode *)tn->child[j]);
707 709
708 tnode_free(tn); 710 tnode_free(tn);
709 711
710 *err = -ENOMEM; 712 *err = -ENOMEM;
711 return oldtnode; 713 return oldtnode;
712 } 714 }
713 715
714 for(i = 0; i < olen; i++) { 716 for(i = 0; i < olen; i++) {
715 struct node *node = tnode_get_child(oldtnode, i); 717 struct node *node = tnode_get_child(oldtnode, i);
716 718
717 /* An empty child */ 719 /* An empty child */
718 if (node == NULL) 720 if (node == NULL)
719 continue; 721 continue;
720 722
721 /* A leaf or an internal node with skipped bits */ 723 /* A leaf or an internal node with skipped bits */
722 724
723 if(IS_LEAF(node) || ((struct tnode *) node)->pos > 725 if (IS_LEAF(node) || ((struct tnode *) node)->pos >
724 tn->pos + tn->bits - 1) { 726 tn->pos + tn->bits - 1) {
725 if(tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, 727 if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits,
726 1) == 0) 728 1) == 0)
727 put_child(t, tn, 2*i, node); 729 put_child(t, tn, 2*i, node);
728 else 730 else
@@ -745,37 +747,37 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn, int *err)
745 struct tnode *left, *right; 747 struct tnode *left, *right;
746 int size, j; 748 int size, j;
747 749
748 /* We will replace this node 'inode' with two new 750 /* We will replace this node 'inode' with two new
749 * ones, 'left' and 'right', each with half of the 751 * ones, 'left' and 'right', each with half of the
750 * original children. The two new nodes will have 752 * original children. The two new nodes will have
751 * a position one bit further down the key and this 753 * a position one bit further down the key and this
752 * means that the "significant" part of their keys 754 * means that the "significant" part of their keys
753 * (see the discussion near the top of this file) 755 * (see the discussion near the top of this file)
754 * will differ by one bit, which will be "0" in 756 * will differ by one bit, which will be "0" in
755 * left's key and "1" in right's key. Since we are 757 * left's key and "1" in right's key. Since we are
756 * moving the key position by one step, the bit that 758 * moving the key position by one step, the bit that
757 * we are moving away from - the bit at position 759 * we are moving away from - the bit at position
758 * (inode->pos) - is the one that will differ between 760 * (inode->pos) - is the one that will differ between
759 * left and right. So... we synthesize that bit in the 761 * left and right. So... we synthesize that bit in the
760 * two new keys. 762 * two new keys.
761 * The mask 'm' below will be a single "one" bit at 763 * The mask 'm' below will be a single "one" bit at
762 * the position (inode->pos) 764 * the position (inode->pos)
763 */ 765 */
764 766
765 /* Use the old key, but set the new significant 767 /* Use the old key, but set the new significant
766 * bit to zero. 768 * bit to zero.
767 */ 769 */
768 770
769 left = (struct tnode *) tnode_get_child(tn, 2*i); 771 left = (struct tnode *) tnode_get_child(tn, 2*i);
770 put_child(t, tn, 2*i, NULL); 772 put_child(t, tn, 2*i, NULL);
771 773
772 if(!left) 774 if (!left)
773 BUG(); 775 BUG();
774 776
775 right = (struct tnode *) tnode_get_child(tn, 2*i+1); 777 right = (struct tnode *) tnode_get_child(tn, 2*i+1);
776 put_child(t, tn, 2*i+1, NULL); 778 put_child(t, tn, 2*i+1, NULL);
777 779
778 if(!right) 780 if (!right)
779 BUG(); 781 BUG();
780 782
781 size = tnode_child_length(left); 783 size = tnode_child_length(left);
@@ -800,9 +802,9 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
800 int i; 802 int i;
801 int olen = tnode_child_length(tn); 803 int olen = tnode_child_length(tn);
802 804
803 if(trie_debug) printk("In halve\n"); 805 if (trie_debug) printk("In halve\n");
804 806
805 tn=tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); 807 tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1);
806 808
807 if (!tn) { 809 if (!tn) {
808 *err = -ENOMEM; 810 *err = -ENOMEM;
@@ -810,39 +812,39 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
810 } 812 }
811 813
812 /* 814 /*
813 * Preallocate and store tnodes before the actual work so we 815 * Preallocate and store tnodes before the actual work so we
814 * don't get into an inconsistent state if memory allocation 816 * don't get into an inconsistent state if memory allocation
815 * fails. In case of failure we return the oldnode and halve 817 * fails. In case of failure we return the oldnode and halve
816 * of tnode is ignored. 818 * of tnode is ignored.
817 */ 819 */
818 820
819 for(i = 0; i < olen; i += 2) { 821 for(i = 0; i < olen; i += 2) {
820 left = tnode_get_child(oldtnode, i); 822 left = tnode_get_child(oldtnode, i);
821 right = tnode_get_child(oldtnode, i+1); 823 right = tnode_get_child(oldtnode, i+1);
822 824
823 /* Two nonempty children */ 825 /* Two nonempty children */
824 if( left && right) { 826 if (left && right) {
825 struct tnode *newBinNode = 827 struct tnode *newBinNode =
826 tnode_new(left->key, tn->pos + tn->bits, 1); 828 tnode_new(left->key, tn->pos + tn->bits, 1);
827 829
828 if(!newBinNode) { 830 if (!newBinNode) {
829 *err = -ENOMEM; 831 *err = -ENOMEM;
830 break; 832 break;
831 } 833 }
832 put_child(t, tn, i/2, (struct node *)newBinNode); 834 put_child(t, tn, i/2, (struct node *)newBinNode);
833 } 835 }
834 } 836 }
835 837
836 if(*err) { 838 if (*err) {
837 int size = tnode_child_length(tn); 839 int size = tnode_child_length(tn);
838 int j; 840 int j;
839 841
840 for(j = 0; j < size; j++) 842 for(j = 0; j < size; j++)
841 if( tn->child[j]) 843 if (tn->child[j])
842 tnode_free((struct tnode *)tn->child[j]); 844 tnode_free((struct tnode *)tn->child[j]);
843 845
844 tnode_free(tn); 846 tnode_free(tn);
845 847
846 *err = -ENOMEM; 848 *err = -ENOMEM;
847 return oldtnode; 849 return oldtnode;
848 } 850 }
@@ -850,7 +852,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
850 for(i = 0; i < olen; i += 2) { 852 for(i = 0; i < olen; i += 2) {
851 left = tnode_get_child(oldtnode, i); 853 left = tnode_get_child(oldtnode, i);
852 right = tnode_get_child(oldtnode, i+1); 854 right = tnode_get_child(oldtnode, i+1);
853 855
854 /* At least one of the children is empty */ 856 /* At least one of the children is empty */
855 if (left == NULL) { 857 if (left == NULL) {
856 if (right == NULL) /* Both are empty */ 858 if (right == NULL) /* Both are empty */
@@ -858,14 +860,14 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
858 put_child(t, tn, i/2, right); 860 put_child(t, tn, i/2, right);
859 } else if (right == NULL) 861 } else if (right == NULL)
860 put_child(t, tn, i/2, left); 862 put_child(t, tn, i/2, left);
861 863
862 /* Two nonempty children */ 864 /* Two nonempty children */
863 else { 865 else {
864 struct tnode *newBinNode = 866 struct tnode *newBinNode =
865 (struct tnode *) tnode_get_child(tn, i/2); 867 (struct tnode *) tnode_get_child(tn, i/2);
866 put_child(t, tn, i/2, NULL); 868 put_child(t, tn, i/2, NULL);
867 869
868 if(!newBinNode) 870 if (!newBinNode)
869 BUG(); 871 BUG();
870 872
871 put_child(t, newBinNode, 0, left); 873 put_child(t, newBinNode, 0, left);
@@ -879,7 +881,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn, int *err)
879 881
880static void *trie_init(struct trie *t) 882static void *trie_init(struct trie *t)
881{ 883{
882 if(t) { 884 if (t) {
883 t->size = 0; 885 t->size = 0;
884 t->trie = NULL; 886 t->trie = NULL;
885 t->revision = 0; 887 t->revision = 0;
@@ -896,8 +898,7 @@ static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
896 struct leaf_info *li; 898 struct leaf_info *li;
897 899
898 hlist_for_each_entry(li, node, head, hlist) { 900 hlist_for_each_entry(li, node, head, hlist) {
899 901 if (li->plen == plen)
900 if ( li->plen == plen )
901 return li; 902 return li;
902 } 903 }
903 return NULL; 904 return NULL;
@@ -905,35 +906,35 @@ static struct leaf_info *find_leaf_info(struct hlist_head *head, int plen)
905 906
906static inline struct list_head * get_fa_head(struct leaf *l, int plen) 907static inline struct list_head * get_fa_head(struct leaf *l, int plen)
907{ 908{
908 struct list_head *fa_head=NULL; 909 struct list_head *fa_head = NULL;
909 struct leaf_info *li = find_leaf_info(&l->list, plen); 910 struct leaf_info *li = find_leaf_info(&l->list, plen);
910 911
911 if(li) 912 if (li)
912 fa_head = &li->falh; 913 fa_head = &li->falh;
913 914
914 return fa_head; 915 return fa_head;
915} 916}
916 917
917static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new) 918static void insert_leaf_info(struct hlist_head *head, struct leaf_info *new)
918{ 919{
919 struct leaf_info *li=NULL, *last=NULL; 920 struct leaf_info *li = NULL, *last = NULL;
920 struct hlist_node *node, *tmp; 921 struct hlist_node *node, *tmp;
921 922
922 write_lock_bh(&fib_lock); 923 write_lock_bh(&fib_lock);
923 924
924 if(hlist_empty(head)) 925 if (hlist_empty(head))
925 hlist_add_head(&new->hlist, head); 926 hlist_add_head(&new->hlist, head);
926 else { 927 else {
927 hlist_for_each_entry_safe(li, node, tmp, head, hlist) { 928 hlist_for_each_entry_safe(li, node, tmp, head, hlist) {
928 929
929 if (new->plen > li->plen) 930 if (new->plen > li->plen)
930 break; 931 break;
931 932
932 last = li; 933 last = li;
933 } 934 }
934 if(last) 935 if (last)
935 hlist_add_after(&last->hlist, &new->hlist); 936 hlist_add_after(&last->hlist, &new->hlist);
936 else 937 else
937 hlist_add_before(&new->hlist, &li->hlist); 938 hlist_add_before(&new->hlist, &li->hlist);
938 } 939 }
939 write_unlock_bh(&fib_lock); 940 write_unlock_bh(&fib_lock);
@@ -947,14 +948,14 @@ fib_find_node(struct trie *t, u32 key)
947 struct node *n; 948 struct node *n;
948 949
949 pos = 0; 950 pos = 0;
950 n=t->trie; 951 n = t->trie;
951 952
952 while (n != NULL && NODE_TYPE(n) == T_TNODE) { 953 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
953 tn = (struct tnode *) n; 954 tn = (struct tnode *) n;
954 955
955 check_tnode(tn); 956 check_tnode(tn);
956 957
957 if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 958 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
958 pos=tn->pos + tn->bits; 959 pos=tn->pos + tn->bits;
959 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 960 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
960 } 961 }
@@ -977,23 +978,23 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
977 t_key cindex, key; 978 t_key cindex, key;
978 struct tnode *tp = NULL; 979 struct tnode *tp = NULL;
979 980
980 if(!tn) 981 if (!tn)
981 BUG(); 982 BUG();
982 983
983 key = tn->key; 984 key = tn->key;
984 i = 0; 985 i = 0;
985 986
986 while (tn != NULL && NODE_PARENT(tn) != NULL) { 987 while (tn != NULL && NODE_PARENT(tn) != NULL) {
987 988
988 if( i > 10 ) { 989 if (i > 10) {
989 printk("Rebalance tn=%p \n", tn); 990 printk("Rebalance tn=%p \n", tn);
990 if(tn) printk("tn->parent=%p \n", NODE_PARENT(tn)); 991 if (tn) printk("tn->parent=%p \n", NODE_PARENT(tn));
991 992
992 printk("Rebalance tp=%p \n", tp); 993 printk("Rebalance tp=%p \n", tp);
993 if(tp) printk("tp->parent=%p \n", NODE_PARENT(tp)); 994 if (tp) printk("tp->parent=%p \n", NODE_PARENT(tp));
994 } 995 }
995 996
996 if( i > 12 ) BUG(); 997 if (i > 12) BUG();
997 i++; 998 i++;
998 999
999 tp = NODE_PARENT(tn); 1000 tp = NODE_PARENT(tn);
@@ -1001,14 +1002,14 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
1001 wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); 1002 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
1002 tn = (struct tnode *) resize (t, (struct tnode *)tn); 1003 tn = (struct tnode *) resize (t, (struct tnode *)tn);
1003 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); 1004 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
1004 1005
1005 if(!NODE_PARENT(tn)) 1006 if (!NODE_PARENT(tn))
1006 break; 1007 break;
1007 1008
1008 tn = NODE_PARENT(tn); 1009 tn = NODE_PARENT(tn);
1009 } 1010 }
1010 /* Handle last (top) tnode */ 1011 /* Handle last (top) tnode */
1011 if (IS_TNODE(tn)) 1012 if (IS_TNODE(tn))
1012 tn = (struct tnode*) resize(t, (struct tnode *)tn); 1013 tn = (struct tnode*) resize(t, (struct tnode *)tn);
1013 1014
1014 return (struct node*) tn; 1015 return (struct node*) tn;
@@ -1022,42 +1023,42 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1022 struct node *n; 1023 struct node *n;
1023 struct leaf *l; 1024 struct leaf *l;
1024 int missbit; 1025 int missbit;
1025 struct list_head *fa_head=NULL; 1026 struct list_head *fa_head = NULL;
1026 struct leaf_info *li; 1027 struct leaf_info *li;
1027 t_key cindex; 1028 t_key cindex;
1028 1029
1029 pos = 0; 1030 pos = 0;
1030 n=t->trie; 1031 n = t->trie;
1031 1032
1032 /* If we point to NULL, stop. Either the tree is empty and we should 1033 /* 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 * 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 * 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 * 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 * a T_TNODE might be skipping any number of bits - its 'pos' need
1037 * not be the parent's 'pos'+'bits'! 1038 * not be the parent's 'pos'+'bits'!
1038 * 1039 *
1039 * If it does match the current key, get pos/bits from it, extract 1040 * 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 * the index from our key, push the T_TNODE and walk the tree.
1041 * 1042 *
1042 * If it doesn't, we have to replace it with a new T_TNODE. 1043 * If it doesn't, we have to replace it with a new T_TNODE.
1043 * 1044 *
1044 * If we point to a T_LEAF, it might or might not have the same key 1045 * 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 * as we do. If it does, just change the value, update the T_LEAF's
1046 * value, and return it. 1047 * value, and return it.
1047 * If it doesn't, we need to replace it with a T_TNODE. 1048 * If it doesn't, we need to replace it with a T_TNODE.
1048 */ 1049 */
1049 1050
1050 while (n != NULL && NODE_TYPE(n) == T_TNODE) { 1051 while (n != NULL && NODE_TYPE(n) == T_TNODE) {
1051 tn = (struct tnode *) n; 1052 tn = (struct tnode *) n;
1052
1053 check_tnode(tn);
1054 1053
1055 if(tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { 1054 check_tnode(tn);
1055
1056 if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
1056 tp = tn; 1057 tp = tn;
1057 pos=tn->pos + tn->bits; 1058 pos=tn->pos + tn->bits;
1058 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 1059 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1059 1060
1060 if(n && NODE_PARENT(n) != tn) { 1061 if (n && NODE_PARENT(n) != tn) {
1061 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); 1062 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1062 BUG(); 1063 BUG();
1063 } 1064 }
@@ -1069,21 +1070,21 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1069 /* 1070 /*
1070 * n ----> NULL, LEAF or TNODE 1071 * n ----> NULL, LEAF or TNODE
1071 * 1072 *
1072 * tp is n's (parent) ----> NULL or TNODE 1073 * tp is n's (parent) ----> NULL or TNODE
1073 */ 1074 */
1074 1075
1075 if(tp && IS_LEAF(tp)) 1076 if (tp && IS_LEAF(tp))
1076 BUG(); 1077 BUG();
1077 1078
1078 1079
1079 /* Case 1: n is a leaf. Compare prefixes */ 1080 /* Case 1: n is a leaf. Compare prefixes */
1080 1081
1081 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) { 1082 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
1082 struct leaf *l = ( struct leaf *) n; 1083 struct leaf *l = ( struct leaf *) n;
1083 1084
1084 li = leaf_info_new(plen); 1085 li = leaf_info_new(plen);
1085 1086
1086 if(! li) { 1087 if (!li) {
1087 *err = -ENOMEM; 1088 *err = -ENOMEM;
1088 goto err; 1089 goto err;
1089 } 1090 }
@@ -1095,7 +1096,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1095 t->size++; 1096 t->size++;
1096 l = leaf_new(); 1097 l = leaf_new();
1097 1098
1098 if(! l) { 1099 if (!l) {
1099 *err = -ENOMEM; 1100 *err = -ENOMEM;
1100 goto err; 1101 goto err;
1101 } 1102 }
@@ -1103,7 +1104,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1103 l->key = key; 1104 l->key = key;
1104 li = leaf_info_new(plen); 1105 li = leaf_info_new(plen);
1105 1106
1106 if(! li) { 1107 if (!li) {
1107 tnode_free((struct tnode *) l); 1108 tnode_free((struct tnode *) l);
1108 *err = -ENOMEM; 1109 *err = -ENOMEM;
1109 goto err; 1110 goto err;
@@ -1116,8 +1117,8 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1116 if (t->trie && n == NULL) { 1117 if (t->trie && n == NULL) {
1117 1118
1118 NODE_SET_PARENT(l, tp); 1119 NODE_SET_PARENT(l, tp);
1119 1120
1120 if (!tp) 1121 if (!tp)
1121 BUG(); 1122 BUG();
1122 1123
1123 else { 1124 else {
@@ -1127,8 +1128,8 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1127 } 1128 }
1128 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */ 1129 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
1129 else { 1130 else {
1130 /* 1131 /*
1131 * Add a new tnode here 1132 * Add a new tnode here
1132 * first tnode need some special handling 1133 * first tnode need some special handling
1133 */ 1134 */
1134 1135
@@ -1136,39 +1137,39 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1136 pos=tp->pos+tp->bits; 1137 pos=tp->pos+tp->bits;
1137 else 1138 else
1138 pos=0; 1139 pos=0;
1139 if(n) { 1140 if (n) {
1140 newpos = tkey_mismatch(key, pos, n->key); 1141 newpos = tkey_mismatch(key, pos, n->key);
1141 tn = tnode_new(n->key, newpos, 1); 1142 tn = tnode_new(n->key, newpos, 1);
1142 } 1143 }
1143 else { 1144 else {
1144 newpos = 0; 1145 newpos = 0;
1145 tn = tnode_new(key, newpos, 1); /* First tnode */ 1146 tn = tnode_new(key, newpos, 1); /* First tnode */
1146 } 1147 }
1147 1148
1148 if(!tn) { 1149 if (!tn) {
1149 free_leaf_info(li); 1150 free_leaf_info(li);
1150 tnode_free((struct tnode *) l); 1151 tnode_free((struct tnode *) l);
1151 *err = -ENOMEM; 1152 *err = -ENOMEM;
1152 goto err; 1153 goto err;
1153 } 1154 }
1154 1155
1155 NODE_SET_PARENT(tn, tp); 1156 NODE_SET_PARENT(tn, tp);
1156 1157
1157 missbit=tkey_extract_bits(key, newpos, 1); 1158 missbit=tkey_extract_bits(key, newpos, 1);
1158 put_child(t, tn, missbit, (struct node *)l); 1159 put_child(t, tn, missbit, (struct node *)l);
1159 put_child(t, tn, 1-missbit, n); 1160 put_child(t, tn, 1-missbit, n);
1160 1161
1161 if(tp) { 1162 if (tp) {
1162 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1163 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1163 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn); 1164 put_child(t, (struct tnode *)tp, cindex, (struct node *)tn);
1164 } 1165 }
1165 else { 1166 else {
1166 t->trie = (struct node*) tn; /* First tnode */ 1167 t->trie = (struct node*) tn; /* First tnode */
1167 tp = tn; 1168 tp = tn;
1168 } 1169 }
1169 } 1170 }
1170 if(tp && tp->pos+tp->bits > 32) { 1171 if (tp && tp->pos+tp->bits > 32) {
1171 printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", 1172 printk("ERROR tp=%p pos=%d, bits=%d, key=%0x plen=%d\n",
1172 tp, tp->pos, tp->bits, key, plen); 1173 tp, tp->pos, tp->bits, key, plen);
1173 } 1174 }
1174 /* Rebalance the trie */ 1175 /* Rebalance the trie */
@@ -1185,7 +1186,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1185{ 1186{
1186 struct trie *t = (struct trie *) tb->tb_data; 1187 struct trie *t = (struct trie *) tb->tb_data;
1187 struct fib_alias *fa, *new_fa; 1188 struct fib_alias *fa, *new_fa;
1188 struct list_head *fa_head=NULL; 1189 struct list_head *fa_head = NULL;
1189 struct fib_info *fi; 1190 struct fib_info *fi;
1190 int plen = r->rtm_dst_len; 1191 int plen = r->rtm_dst_len;
1191 int type = r->rtm_type; 1192 int type = r->rtm_type;
@@ -1198,17 +1199,17 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1198 return -EINVAL; 1199 return -EINVAL;
1199 1200
1200 key = 0; 1201 key = 0;
1201 if (rta->rta_dst) 1202 if (rta->rta_dst)
1202 memcpy(&key, rta->rta_dst, 4); 1203 memcpy(&key, rta->rta_dst, 4);
1203 1204
1204 key = ntohl(key); 1205 key = ntohl(key);
1205 1206
1206 if(trie_debug) 1207 if (trie_debug)
1207 printk("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); 1208 printk("Insert table=%d %08x/%d\n", tb->tb_id, key, plen);
1208 1209
1209 mask = ntohl( inet_make_mask(plen) ); 1210 mask = ntohl( inet_make_mask(plen) );
1210 1211
1211 if(key & ~mask) 1212 if (key & ~mask)
1212 return -EINVAL; 1213 return -EINVAL;
1213 1214
1214 key = key & mask; 1215 key = key & mask;
@@ -1217,9 +1218,9 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1217 goto err; 1218 goto err;
1218 1219
1219 l = fib_find_node(t, key); 1220 l = fib_find_node(t, key);
1220 fa = NULL; 1221 fa = NULL;
1221 1222
1222 if(l) { 1223 if (l) {
1223 fa_head = get_fa_head(l, plen); 1224 fa_head = get_fa_head(l, plen);
1224 fa = fib_find_alias(fa_head, tos, fi->fib_priority); 1225 fa = fib_find_alias(fa_head, tos, fi->fib_priority);
1225 } 1226 }
@@ -1298,16 +1299,16 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1298 new_fa->fa_scope = r->rtm_scope; 1299 new_fa->fa_scope = r->rtm_scope;
1299 new_fa->fa_state = 0; 1300 new_fa->fa_state = 0;
1300#if 0 1301#if 0
1301 new_fa->dst = NULL; 1302 new_fa->dst = NULL;
1302#endif 1303#endif
1303 /* 1304 /*
1304 * Insert new entry to the list. 1305 * Insert new entry to the list.
1305 */ 1306 */
1306 1307
1307 if(!fa_head) { 1308 if (!fa_head) {
1308 fa_head = fib_insert_node(t, &err, key, plen); 1309 fa_head = fib_insert_node(t, &err, key, plen);
1309 err = 0; 1310 err = 0;
1310 if(err) 1311 if (err)
1311 goto out_free_new_fa; 1312 goto out_free_new_fa;
1312 } 1313 }
1313 1314
@@ -1327,11 +1328,11 @@ out_free_new_fa:
1327 kmem_cache_free(fn_alias_kmem, new_fa); 1328 kmem_cache_free(fn_alias_kmem, new_fa);
1328out: 1329out:
1329 fib_release_info(fi); 1330 fib_release_info(fi);
1330err:; 1331err:;
1331 return err; 1332 return err;
1332} 1333}
1333 1334
1334static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *plen, const struct flowi *flp, 1335static 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 struct fib_result *res, int *err)
1336{ 1337{
1337 int i; 1338 int i;
@@ -1339,12 +1340,12 @@ static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *pl
1339 struct leaf_info *li; 1340 struct leaf_info *li;
1340 struct hlist_head *hhead = &l->list; 1341 struct hlist_head *hhead = &l->list;
1341 struct hlist_node *node; 1342 struct hlist_node *node;
1342 1343
1343 hlist_for_each_entry(li, node, hhead, hlist) { 1344 hlist_for_each_entry(li, node, hhead, hlist) {
1344 1345
1345 i = li->plen; 1346 i = li->plen;
1346 mask = ntohl(inet_make_mask(i)); 1347 mask = ntohl(inet_make_mask(i));
1347 if (l->key != (key & mask)) 1348 if (l->key != (key & mask))
1348 continue; 1349 continue;
1349 1350
1350 if (((*err) = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) == 0) { 1351 if (((*err) = fib_semantic_match(&li->falh, flp, res, l->key, mask, i)) == 0) {
@@ -1376,7 +1377,7 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1376 n = t->trie; 1377 n = t->trie;
1377 1378
1378 read_lock(&fib_lock); 1379 read_lock(&fib_lock);
1379 if(!n) 1380 if (!n)
1380 goto failed; 1381 goto failed;
1381 1382
1382#ifdef CONFIG_IP_FIB_TRIE_STATS 1383#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -1385,19 +1386,19 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1385 1386
1386 /* Just a leaf? */ 1387 /* Just a leaf? */
1387 if (IS_LEAF(n)) { 1388 if (IS_LEAF(n)) {
1388 if( check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret) ) 1389 if (check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret))
1389 goto found; 1390 goto found;
1390 goto failed; 1391 goto failed;
1391 } 1392 }
1392 pn = (struct tnode *) n; 1393 pn = (struct tnode *) n;
1393 chopped_off = 0; 1394 chopped_off = 0;
1394 1395
1395 while (pn) { 1396 while (pn) {
1396 1397
1397 pos = pn->pos; 1398 pos = pn->pos;
1398 bits = pn->bits; 1399 bits = pn->bits;
1399 1400
1400 if(!chopped_off) 1401 if (!chopped_off)
1401 cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits); 1402 cindex = tkey_extract_bits(MASK_PFX(key, current_prefix_length), pos, bits);
1402 1403
1403 n = tnode_get_child(pn, cindex); 1404 n = tnode_get_child(pn, cindex);
@@ -1417,33 +1418,33 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1417 int mp; 1418 int mp;
1418 1419
1419 /* 1420 /*
1420 * It's a tnode, and we can do some extra checks here if we 1421 * 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 * like, to avoid descending into a dead-end branch.
1422 * This tnode is in the parent's child array at index 1423 * 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 * 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 * chopped off, so in reality the index may be just a
1425 * subprefix, padded with zero at the end. 1426 * subprefix, padded with zero at the end.
1426 * We can also take a look at any skipped bits in this 1427 * 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 * tnode - everything up to p_pos is supposed to be ok,
1428 * and the non-chopped bits of the index (se previous 1429 * and the non-chopped bits of the index (se previous
1429 * paragraph) are also guaranteed ok, but the rest is 1430 * paragraph) are also guaranteed ok, but the rest is
1430 * considered unknown. 1431 * considered unknown.
1431 * 1432 *
1432 * The skipped bits are key[pos+bits..cn->pos]. 1433 * The skipped bits are key[pos+bits..cn->pos].
1433 */ 1434 */
1434 1435
1435 /* If current_prefix_length < pos+bits, we are already doing 1436 /* If current_prefix_length < pos+bits, we are already doing
1436 * actual prefix matching, which means everything from 1437 * actual prefix matching, which means everything from
1437 * pos+(bits-chopped_off) onward must be zero along some 1438 * pos+(bits-chopped_off) onward must be zero along some
1438 * branch of this subtree - otherwise there is *no* valid 1439 * branch of this subtree - otherwise there is *no* valid
1439 * prefix present. Here we can only check the skipped 1440 * prefix present. Here we can only check the skipped
1440 * bits. Remember, since we have already indexed into the 1441 * bits. Remember, since we have already indexed into the
1441 * parent's child array, we know that the bits we chopped of 1442 * parent's child array, we know that the bits we chopped of
1442 * *are* zero. 1443 * *are* zero.
1443 */ 1444 */
1444 1445
1445 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */ 1446 /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */
1446 1447
1447 if (current_prefix_length < pos+bits) { 1448 if (current_prefix_length < pos+bits) {
1448 if (tkey_extract_bits(cn->key, current_prefix_length, 1449 if (tkey_extract_bits(cn->key, current_prefix_length,
1449 cn->pos - current_prefix_length) != 0 || 1450 cn->pos - current_prefix_length) != 0 ||
@@ -1452,13 +1453,13 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1452 } 1453 }
1453 1454
1454 /* 1455 /*
1455 * If chopped_off=0, the index is fully validated and we 1456 * 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 * 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 * 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 * these skipped bits match our key perfectly, or if we will
1459 * have to count on finding a matching prefix further down, 1460 * have to count on finding a matching prefix further down,
1460 * because if we do, we would like to have some way of 1461 * because if we do, we would like to have some way of
1461 * verifying the existence of such a prefix at this point. 1462 * verifying the existence of such a prefix at this point.
1462 */ 1463 */
1463 1464
1464 /* The only thing we can do at this point is to verify that 1465 /* The only thing we can do at this point is to verify that
@@ -1470,22 +1471,22 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1470 * new tnode's key. 1471 * new tnode's key.
1471 */ 1472 */
1472 1473
1473 /* Note: We aren't very concerned about the piece of the key 1474 /* 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 * 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 * 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 * 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 * 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 * 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 * throughout this subtree are zero, as they have to be if we are
1480 * to find a matching prefix. 1481 * to find a matching prefix.
1481 */ 1482 */
1482 1483
1483 node_prefix = MASK_PFX(cn->key, cn->pos); 1484 node_prefix = MASK_PFX(cn->key, cn->pos);
1484 key_prefix = MASK_PFX(key, cn->pos); 1485 key_prefix = MASK_PFX(key, cn->pos);
1485 pref_mismatch = key_prefix^node_prefix; 1486 pref_mismatch = key_prefix^node_prefix;
1486 mp = 0; 1487 mp = 0;
1487 1488
1488 /* In short: If skipped bits in this node do not match the search 1489 /* In short: If skipped bits in this node do not match the search
1489 * key, enter the "prefix matching" state.directly. 1490 * key, enter the "prefix matching" state.directly.
1490 */ 1491 */
1491 if (pref_mismatch) { 1492 if (pref_mismatch) {
@@ -1494,7 +1495,7 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1494 pref_mismatch = pref_mismatch <<1; 1495 pref_mismatch = pref_mismatch <<1;
1495 } 1496 }
1496 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); 1497 key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp);
1497 1498
1498 if (key_prefix != 0) 1499 if (key_prefix != 0)
1499 goto backtrace; 1500 goto backtrace;
1500 1501
@@ -1505,9 +1506,9 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result
1505 pn = (struct tnode *)n; /* Descend */ 1506 pn = (struct tnode *)n; /* Descend */
1506 chopped_off = 0; 1507 chopped_off = 0;
1507 continue; 1508 continue;
1508 } 1509 }
1509 if (IS_LEAF(n)) { 1510 if (IS_LEAF(n)) {
1510 if( check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret)) 1511 if (check_leaf(t, (struct leaf *)n, key, &plen, flp, res, &ret))
1511 goto found; 1512 goto found;
1512 } 1513 }
1513backtrace: 1514backtrace:
@@ -1521,18 +1522,18 @@ backtrace:
1521 /* Decrease current_... with bits chopped off */ 1522 /* Decrease current_... with bits chopped off */
1522 if (current_prefix_length > pn->pos + pn->bits - chopped_off) 1523 if (current_prefix_length > pn->pos + pn->bits - chopped_off)
1523 current_prefix_length = pn->pos + pn->bits - chopped_off; 1524 current_prefix_length = pn->pos + pn->bits - chopped_off;
1524 1525
1525 /* 1526 /*
1526 * Either we do the actual chop off according or if we have 1527 * 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 * chopped off all bits in this tnode walk up to our parent.
1528 */ 1529 */
1529 1530
1530 if(chopped_off <= pn->bits) 1531 if (chopped_off <= pn->bits)
1531 cindex &= ~(1 << (chopped_off-1)); 1532 cindex &= ~(1 << (chopped_off-1));
1532 else { 1533 else {
1533 if( NODE_PARENT(pn) == NULL) 1534 if (NODE_PARENT(pn) == NULL)
1534 goto failed; 1535 goto failed;
1535 1536
1536 /* Get Child's index */ 1537 /* Get Child's index */
1537 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits); 1538 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits);
1538 pn = NODE_PARENT(pn); 1539 pn = NODE_PARENT(pn);
@@ -1542,10 +1543,10 @@ backtrace:
1542 t->stats.backtrack++; 1543 t->stats.backtrack++;
1543#endif 1544#endif
1544 goto backtrace; 1545 goto backtrace;
1545 } 1546 }
1546 } 1547 }
1547failed: 1548failed:
1548 ret = 1; 1549 ret = 1;
1549found: 1550found:
1550 read_unlock(&fib_lock); 1551 read_unlock(&fib_lock);
1551 return ret; 1552 return ret;
@@ -1558,11 +1559,11 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1558 struct node *n = t->trie; 1559 struct node *n = t->trie;
1559 struct leaf *l; 1560 struct leaf *l;
1560 1561
1561 if(trie_debug) 1562 if (trie_debug)
1562 printk("entering trie_leaf_remove(%p)\n", n); 1563 printk("entering trie_leaf_remove(%p)\n", n);
1563 1564
1564 /* Note that in the case skipped bits, those bits are *not* checked! 1565 /* 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 * 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 * T_LEAF may or may not match our key.
1567 */ 1568 */
1568 1569
@@ -1571,19 +1572,19 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1571 check_tnode(tn); 1572 check_tnode(tn);
1572 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); 1573 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1573 1574
1574 if(n && NODE_PARENT(n) != tn) { 1575 if (n && NODE_PARENT(n) != tn) {
1575 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); 1576 printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n));
1576 BUG(); 1577 BUG();
1577 } 1578 }
1578 } 1579 }
1579 l = (struct leaf *) n; 1580 l = (struct leaf *) n;
1580 1581
1581 if(!n || !tkey_equals(l->key, key)) 1582 if (!n || !tkey_equals(l->key, key))
1582 return 0; 1583 return 0;
1583 1584
1584 /* 1585 /*
1585 * Key found. 1586 * Key found.
1586 * Remove the leaf and rebalance the tree 1587 * Remove the leaf and rebalance the tree
1587 */ 1588 */
1588 1589
1589 t->revision++; 1590 t->revision++;
@@ -1592,7 +1593,7 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1592 tp = NODE_PARENT(n); 1593 tp = NODE_PARENT(n);
1593 tnode_free((struct tnode *) n); 1594 tnode_free((struct tnode *) n);
1594 1595
1595 if(tp) { 1596 if (tp) {
1596 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1597 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1597 put_child(t, (struct tnode *)tp, cindex, NULL); 1598 put_child(t, (struct tnode *)tp, cindex, NULL);
1598 t->trie = trie_rebalance(t, tp); 1599 t->trie = trie_rebalance(t, tp);
@@ -1615,23 +1616,23 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1615 struct list_head *fa_head; 1616 struct list_head *fa_head;
1616 struct leaf *l; 1617 struct leaf *l;
1617 1618
1618 if (plen > 32) 1619 if (plen > 32)
1619 return -EINVAL; 1620 return -EINVAL;
1620 1621
1621 key = 0; 1622 key = 0;
1622 if (rta->rta_dst) 1623 if (rta->rta_dst)
1623 memcpy(&key, rta->rta_dst, 4); 1624 memcpy(&key, rta->rta_dst, 4);
1624 1625
1625 key = ntohl(key); 1626 key = ntohl(key);
1626 mask = ntohl( inet_make_mask(plen) ); 1627 mask = ntohl( inet_make_mask(plen) );
1627 1628
1628 if(key & ~mask) 1629 if (key & ~mask)
1629 return -EINVAL; 1630 return -EINVAL;
1630 1631
1631 key = key & mask; 1632 key = key & mask;
1632 l = fib_find_node(t, key); 1633 l = fib_find_node(t, key);
1633 1634
1634 if(!l) 1635 if (!l)
1635 return -ESRCH; 1636 return -ESRCH;
1636 1637
1637 fa_head = get_fa_head(l, plen); 1638 fa_head = get_fa_head(l, plen);
@@ -1677,16 +1678,16 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta,
1677 1678
1678 list_del(&fa->fa_list); 1679 list_del(&fa->fa_list);
1679 1680
1680 if(list_empty(fa_head)) { 1681 if (list_empty(fa_head)) {
1681 hlist_del(&li->hlist); 1682 hlist_del(&li->hlist);
1682 kill_li = 1; 1683 kill_li = 1;
1683 } 1684 }
1684 write_unlock_bh(&fib_lock); 1685 write_unlock_bh(&fib_lock);
1685 1686
1686 if(kill_li) 1687 if (kill_li)
1687 free_leaf_info(li); 1688 free_leaf_info(li);
1688 1689
1689 if(hlist_empty(&l->list)) 1690 if (hlist_empty(&l->list))
1690 trie_leaf_remove(t, key); 1691 trie_leaf_remove(t, key);
1691 1692
1692 if (fa->fa_state & FA_S_ACCESSED) 1693 if (fa->fa_state & FA_S_ACCESSED)
@@ -1705,12 +1706,12 @@ static int trie_flush_list(struct trie *t, struct list_head *head)
1705 1706
1706 list_for_each_entry_safe(fa, fa_node, head, fa_list) { 1707 list_for_each_entry_safe(fa, fa_node, head, fa_list) {
1707 struct fib_info *fi = fa->fa_info; 1708 struct fib_info *fi = fa->fa_info;
1708 1709
1709 if (fi && (fi->fib_flags&RTNH_F_DEAD)) { 1710 if (fi && (fi->fib_flags&RTNH_F_DEAD)) {
1710 1711
1711 write_lock_bh(&fib_lock); 1712 write_lock_bh(&fib_lock);
1712 list_del(&fa->fa_list); 1713 list_del(&fa->fa_list);
1713 write_unlock_bh(&fib_lock); 1714 write_unlock_bh(&fib_lock);
1714 1715
1715 fn_free_alias(fa); 1716 fn_free_alias(fa);
1716 found++; 1717 found++;
@@ -1727,14 +1728,14 @@ static int trie_flush_leaf(struct trie *t, struct leaf *l)
1727 struct leaf_info *li = NULL; 1728 struct leaf_info *li = NULL;
1728 1729
1729 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) { 1730 hlist_for_each_entry_safe(li, node, tmp, lih, hlist) {
1730 1731
1731 found += trie_flush_list(t, &li->falh); 1732 found += trie_flush_list(t, &li->falh);
1732 1733
1733 if (list_empty(&li->falh)) { 1734 if (list_empty(&li->falh)) {
1734 1735
1735 write_lock_bh(&fib_lock); 1736 write_lock_bh(&fib_lock);
1736 hlist_del(&li->hlist); 1737 hlist_del(&li->hlist);
1737 write_unlock_bh(&fib_lock); 1738 write_unlock_bh(&fib_lock);
1738 1739
1739 free_leaf_info(li); 1740 free_leaf_info(li);
1740 } 1741 }
@@ -1748,8 +1749,8 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1748 struct tnode *p; 1749 struct tnode *p;
1749 int idx; 1750 int idx;
1750 1751
1751 if(c == NULL) { 1752 if (c == NULL) {
1752 if(t->trie == NULL) 1753 if (t->trie == NULL)
1753 return NULL; 1754 return NULL;
1754 1755
1755 if (IS_LEAF(t->trie)) /* trie w. just a leaf */ 1756 if (IS_LEAF(t->trie)) /* trie w. just a leaf */
@@ -1757,33 +1758,34 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1757 1758
1758 p = (struct tnode*) t->trie; /* Start */ 1759 p = (struct tnode*) t->trie; /* Start */
1759 } 1760 }
1760 else 1761 else
1761 p = (struct tnode *) NODE_PARENT(c); 1762 p = (struct tnode *) NODE_PARENT(c);
1763
1762 while (p) { 1764 while (p) {
1763 int pos, last; 1765 int pos, last;
1764 1766
1765 /* Find the next child of the parent */ 1767 /* Find the next child of the parent */
1766 if(c) 1768 if (c)
1767 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits); 1769 pos = 1 + tkey_extract_bits(c->key, p->pos, p->bits);
1768 else 1770 else
1769 pos = 0; 1771 pos = 0;
1770 1772
1771 last = 1 << p->bits; 1773 last = 1 << p->bits;
1772 for(idx = pos; idx < last ; idx++) { 1774 for(idx = pos; idx < last ; idx++) {
1773 if( p->child[idx]) { 1775 if (p->child[idx]) {
1774 1776
1775 /* Decend if tnode */ 1777 /* Decend if tnode */
1776 1778
1777 while (IS_TNODE(p->child[idx])) { 1779 while (IS_TNODE(p->child[idx])) {
1778 p = (struct tnode*) p->child[idx]; 1780 p = (struct tnode*) p->child[idx];
1779 idx = 0; 1781 idx = 0;
1780 1782
1781 /* Rightmost non-NULL branch */ 1783 /* Rightmost non-NULL branch */
1782 if( p && IS_TNODE(p) ) 1784 if (p && IS_TNODE(p))
1783 while ( p->child[idx] == NULL && idx < (1 << p->bits) ) idx++; 1785 while (p->child[idx] == NULL && idx < (1 << p->bits)) idx++;
1784 1786
1785 /* Done with this tnode? */ 1787 /* Done with this tnode? */
1786 if( idx >= (1 << p->bits) || p->child[idx] == NULL ) 1788 if (idx >= (1 << p->bits) || p->child[idx] == NULL )
1787 goto up; 1789 goto up;
1788 } 1790 }
1789 return (struct leaf*) p->child[idx]; 1791 return (struct leaf*) p->child[idx];
@@ -1816,7 +1818,7 @@ static int fn_trie_flush(struct fib_table *tb)
1816 if (ll && hlist_empty(&ll->list)) 1818 if (ll && hlist_empty(&ll->list))
1817 trie_leaf_remove(t, ll->key); 1819 trie_leaf_remove(t, ll->key);
1818 1820
1819 if(trie_debug) 1821 if (trie_debug)
1820 printk("trie_flush found=%d\n", found); 1822 printk("trie_flush found=%d\n", found);
1821 return found; 1823 return found;
1822} 1824}
@@ -1839,32 +1841,32 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
1839 order = -1; 1841 order = -1;
1840 1842
1841 read_lock(&fib_lock); 1843 read_lock(&fib_lock);
1842 1844
1843 l = fib_find_node(t, 0); 1845 l = fib_find_node(t, 0);
1844 if(!l) 1846 if (!l)
1845 goto out; 1847 goto out;
1846 1848
1847 fa_head = get_fa_head(l, 0); 1849 fa_head = get_fa_head(l, 0);
1848 if(!fa_head) 1850 if (!fa_head)
1849 goto out; 1851 goto out;
1850 1852
1851 if (list_empty(fa_head)) 1853 if (list_empty(fa_head))
1852 goto out; 1854 goto out;
1853 1855
1854 list_for_each_entry(fa, fa_head, fa_list) { 1856 list_for_each_entry(fa, fa_head, fa_list) {
1855 struct fib_info *next_fi = fa->fa_info; 1857 struct fib_info *next_fi = fa->fa_info;
1856 1858
1857 if (fa->fa_scope != res->scope || 1859 if (fa->fa_scope != res->scope ||
1858 fa->fa_type != RTN_UNICAST) 1860 fa->fa_type != RTN_UNICAST)
1859 continue; 1861 continue;
1860 1862
1861 if (next_fi->fib_priority > res->fi->fib_priority) 1863 if (next_fi->fib_priority > res->fi->fib_priority)
1862 break; 1864 break;
1863 if (!next_fi->fib_nh[0].nh_gw || 1865 if (!next_fi->fib_nh[0].nh_gw ||
1864 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK) 1866 next_fi->fib_nh[0].nh_scope != RT_SCOPE_LINK)
1865 continue; 1867 continue;
1866 fa->fa_state |= FA_S_ACCESSED; 1868 fa->fa_state |= FA_S_ACCESSED;
1867 1869
1868 if (fi == NULL) { 1870 if (fi == NULL) {
1869 if (next_fi != res->fi) 1871 if (next_fi != res->fi)
1870 break; 1872 break;
@@ -1902,10 +1904,10 @@ fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib
1902 } 1904 }
1903 trie_last_dflt = last_idx; 1905 trie_last_dflt = last_idx;
1904 out:; 1906 out:;
1905 read_unlock(&fib_lock); 1907 read_unlock(&fib_lock);
1906} 1908}
1907 1909
1908static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb, 1910static 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) 1911 struct sk_buff *skb, struct netlink_callback *cb)
1910{ 1912{
1911 int i, s_i; 1913 int i, s_i;
@@ -1951,7 +1953,7 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi
1951 return skb->len; 1953 return skb->len;
1952} 1954}
1953 1955
1954static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb, 1956static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb,
1955 struct netlink_callback *cb) 1957 struct netlink_callback *cb)
1956{ 1958{
1957 int h, s_h; 1959 int h, s_h;
@@ -1968,11 +1970,11 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str
1968 sizeof(cb->args) - 3*sizeof(cb->args[0])); 1970 sizeof(cb->args) - 3*sizeof(cb->args[0]));
1969 1971
1970 fa_head = get_fa_head(l, plen); 1972 fa_head = get_fa_head(l, plen);
1971 1973
1972 if(!fa_head) 1974 if (!fa_head)
1973 continue; 1975 continue;
1974 1976
1975 if(list_empty(fa_head)) 1977 if (list_empty(fa_head))
1976 continue; 1978 continue;
1977 1979
1978 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { 1980 if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) {
@@ -2048,10 +2050,10 @@ struct fib_table * __init fib_hash_init(int id)
2048 2050
2049 trie_init(t); 2051 trie_init(t);
2050 2052
2051 if (id == RT_TABLE_LOCAL) 2053 if (id == RT_TABLE_LOCAL)
2052 trie_local=t; 2054 trie_local = t;
2053 else if (id == RT_TABLE_MAIN) 2055 else if (id == RT_TABLE_MAIN)
2054 trie_main=t; 2056 trie_main = t;
2055 2057
2056 if (id == RT_TABLE_LOCAL) 2058 if (id == RT_TABLE_LOCAL)
2057 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION); 2059 printk("IPv4 FIB: Using LC-trie version %s\n", VERSION);
@@ -2072,7 +2074,7 @@ static void printbin_seq(struct seq_file *seq, unsigned int v, int bits)
2072 seq_printf(seq, "%s", (v & (1<<bits))?"1":"0"); 2074 seq_printf(seq, "%s", (v & (1<<bits))?"1":"0");
2073} 2075}
2074 2076
2075static void printnode_seq(struct seq_file *seq, int indent, struct node *n, 2077static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2076 int pend, int cindex, int bits) 2078 int pend, int cindex, int bits)
2077{ 2079{
2078 putspace_seq(seq, indent); 2080 putspace_seq(seq, indent);
@@ -2090,12 +2092,12 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2090 seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n); 2092 seq_printf(seq, "%s:%p ", IS_LEAF(n)?"Leaf":"Internal node", n);
2091 2093
2092 if (IS_LEAF(n)) 2094 if (IS_LEAF(n))
2093 seq_printf(seq, "key=%d.%d.%d.%d\n", 2095 seq_printf(seq, "key=%d.%d.%d.%d\n",
2094 n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) % 256, n->key % 256); 2096 n->key >> 24, (n->key >> 16) % 256, (n->key >> 8) % 256, n->key % 256);
2095 else { 2097 else {
2096 int plen=((struct tnode *)n)->pos; 2098 int plen = ((struct tnode *)n)->pos;
2097 t_key prf=MASK_PFX(n->key, plen); 2099 t_key prf=MASK_PFX(n->key, plen);
2098 seq_printf(seq, "key=%d.%d.%d.%d/%d\n", 2100 seq_printf(seq, "key=%d.%d.%d.%d/%d\n",
2099 prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf % 256, plen); 2101 prf >> 24, (prf >> 16) % 256, (prf >> 8) % 256, prf % 256, plen);
2100 } 2102 }
2101 if (IS_LEAF(n)) { 2103 if (IS_LEAF(n)) {
@@ -2103,14 +2105,14 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2103 struct fib_alias *fa; 2105 struct fib_alias *fa;
2104 int i; 2106 int i;
2105 for (i=32; i>=0; i--) 2107 for (i=32; i>=0; i--)
2106 if(find_leaf_info(&l->list, i)) { 2108 if (find_leaf_info(&l->list, i)) {
2107 2109
2108 struct list_head *fa_head = get_fa_head(l, i); 2110 struct list_head *fa_head = get_fa_head(l, i);
2109 2111
2110 if(!fa_head) 2112 if (!fa_head)
2111 continue; 2113 continue;
2112 2114
2113 if(list_empty(fa_head)) 2115 if (list_empty(fa_head))
2114 continue; 2116 continue;
2115 2117
2116 putspace_seq(seq, indent+2); 2118 putspace_seq(seq, indent+2);
@@ -2136,7 +2138,7 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2136 } 2138 }
2137 } 2139 }
2138 else if (IS_TNODE(n)) { 2140 else if (IS_TNODE(n)) {
2139 struct tnode *tn=(struct tnode *)n; 2141 struct tnode *tn = (struct tnode *)n;
2140 putspace_seq(seq, indent); seq_printf(seq, "| "); 2142 putspace_seq(seq, indent); seq_printf(seq, "| ");
2141 seq_printf(seq, "{key prefix=%08x/", tn->key&TKEY_GET_MASK(0, tn->pos)); 2143 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); 2144 printbin_seq(seq, tkey_extract_bits(tn->key, 0, tn->pos), tn->pos);
@@ -2152,7 +2154,7 @@ static void printnode_seq(struct seq_file *seq, int indent, struct node *n,
2152 2154
2153static void trie_dump_seq(struct seq_file *seq, struct trie *t) 2155static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2154{ 2156{
2155 struct node *n=t->trie; 2157 struct node *n = t->trie;
2156 int cindex=0; 2158 int cindex=0;
2157 int indent=1; 2159 int indent=1;
2158 int pend=0; 2160 int pend=0;
@@ -2164,7 +2166,7 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2164 if (n) { 2166 if (n) {
2165 printnode_seq(seq, indent, n, pend, cindex, 0); 2167 printnode_seq(seq, indent, n, pend, cindex, 0);
2166 if (IS_TNODE(n)) { 2168 if (IS_TNODE(n)) {
2167 struct tnode *tn=(struct tnode *)n; 2169 struct tnode *tn = (struct tnode *)n;
2168 pend = tn->pos+tn->bits; 2170 pend = tn->pos+tn->bits;
2169 putspace_seq(seq, indent); seq_printf(seq, "\\--\n"); 2171 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2170 indent += 3; 2172 indent += 3;
@@ -2172,42 +2174,42 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2172 2174
2173 while (tn && cindex < (1 << tn->bits)) { 2175 while (tn && cindex < (1 << tn->bits)) {
2174 if (tn->child[cindex]) { 2176 if (tn->child[cindex]) {
2175 2177
2176 /* Got a child */ 2178 /* Got a child */
2177 2179
2178 printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits); 2180 printnode_seq(seq, indent, tn->child[cindex], pend, cindex, tn->bits);
2179 if (IS_LEAF(tn->child[cindex])) { 2181 if (IS_LEAF(tn->child[cindex])) {
2180 cindex++; 2182 cindex++;
2181 2183
2182 } 2184 }
2183 else { 2185 else {
2184 /* 2186 /*
2185 * New tnode. Decend one level 2187 * New tnode. Decend one level
2186 */ 2188 */
2187 2189
2188 depth++; 2190 depth++;
2189 n=tn->child[cindex]; 2191 n = tn->child[cindex];
2190 tn=(struct tnode *)n; 2192 tn = (struct tnode *)n;
2191 pend=tn->pos+tn->bits; 2193 pend = tn->pos+tn->bits;
2192 putspace_seq(seq, indent); seq_printf(seq, "\\--\n"); 2194 putspace_seq(seq, indent); seq_printf(seq, "\\--\n");
2193 indent+=3; 2195 indent+=3;
2194 cindex=0; 2196 cindex=0;
2195 } 2197 }
2196 } 2198 }
2197 else 2199 else
2198 cindex++; 2200 cindex++;
2199 2201
2200 /* 2202 /*
2201 * Test if we are done 2203 * Test if we are done
2202 */ 2204 */
2203 2205
2204 while (cindex >= (1 << tn->bits)) { 2206 while (cindex >= (1 << tn->bits)) {
2205 2207
2206 /* 2208 /*
2207 * Move upwards and test for root 2209 * Move upwards and test for root
2208 * pop off all traversed nodes 2210 * pop off all traversed nodes
2209 */ 2211 */
2210 2212
2211 if (NODE_PARENT(tn) == NULL) { 2213 if (NODE_PARENT(tn) == NULL) {
2212 tn = NULL; 2214 tn = NULL;
2213 n = NULL; 2215 n = NULL;
@@ -2217,8 +2219,8 @@ static void trie_dump_seq(struct seq_file *seq, struct trie *t)
2217 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits); 2219 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2218 tn = NODE_PARENT(tn); 2220 tn = NODE_PARENT(tn);
2219 cindex++; 2221 cindex++;
2220 n=(struct node *)tn; 2222 n = (struct node *)tn;
2221 pend=tn->pos+tn->bits; 2223 pend = tn->pos+tn->bits;
2222 indent-=3; 2224 indent-=3;
2223 depth--; 2225 depth--;
2224 } 2226 }
@@ -2236,36 +2238,36 @@ static struct trie_stat *trie_stat_new(void)
2236{ 2238{
2237 struct trie_stat *s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL); 2239 struct trie_stat *s = kmalloc(sizeof(struct trie_stat), GFP_KERNEL);
2238 int i; 2240 int i;
2239 2241
2240 if(s) { 2242 if (s) {
2241 s->totdepth = 0; 2243 s->totdepth = 0;
2242 s->maxdepth = 0; 2244 s->maxdepth = 0;
2243 s->tnodes = 0; 2245 s->tnodes = 0;
2244 s->leaves = 0; 2246 s->leaves = 0;
2245 s->nullpointers = 0; 2247 s->nullpointers = 0;
2246 2248
2247 for(i=0; i< MAX_CHILDS; i++) 2249 for(i=0; i< MAX_CHILDS; i++)
2248 s->nodesizes[i] = 0; 2250 s->nodesizes[i] = 0;
2249 } 2251 }
2250 return s; 2252 return s;
2251} 2253}
2252 2254
2253static struct trie_stat *trie_collect_stats(struct trie *t) 2255static struct trie_stat *trie_collect_stats(struct trie *t)
2254{ 2256{
2255 struct node *n=t->trie; 2257 struct node *n = t->trie;
2256 struct trie_stat *s = trie_stat_new(); 2258 struct trie_stat *s = trie_stat_new();
2257 int cindex = 0; 2259 int cindex = 0;
2258 int indent = 1; 2260 int indent = 1;
2259 int pend = 0; 2261 int pend = 0;
2260 int depth = 0; 2262 int depth = 0;
2261 2263
2262 read_lock(&fib_lock); 2264 read_lock(&fib_lock);
2263 2265
2264 if (s) { 2266 if (s) {
2265 if (n) { 2267 if (n) {
2266 if (IS_TNODE(n)) { 2268 if (IS_TNODE(n)) {
2267 struct tnode *tn = (struct tnode *)n; 2269 struct tnode *tn = (struct tnode *)n;
2268 pend=tn->pos+tn->bits; 2270 pend = tn->pos+tn->bits;
2269 indent += 3; 2271 indent += 3;
2270 s->nodesizes[tn->bits]++; 2272 s->nodesizes[tn->bits]++;
2271 depth++; 2273 depth++;
@@ -2273,26 +2275,26 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2273 while (tn && cindex < (1 << tn->bits)) { 2275 while (tn && cindex < (1 << tn->bits)) {
2274 if (tn->child[cindex]) { 2276 if (tn->child[cindex]) {
2275 /* Got a child */ 2277 /* Got a child */
2276 2278
2277 if (IS_LEAF(tn->child[cindex])) { 2279 if (IS_LEAF(tn->child[cindex])) {
2278 cindex++; 2280 cindex++;
2279 2281
2280 /* stats */ 2282 /* stats */
2281 if (depth > s->maxdepth) 2283 if (depth > s->maxdepth)
2282 s->maxdepth = depth; 2284 s->maxdepth = depth;
2283 s->totdepth += depth; 2285 s->totdepth += depth;
2284 s->leaves++; 2286 s->leaves++;
2285 } 2287 }
2286 2288
2287 else { 2289 else {
2288 /* 2290 /*
2289 * New tnode. Decend one level 2291 * New tnode. Decend one level
2290 */ 2292 */
2291 2293
2292 s->tnodes++; 2294 s->tnodes++;
2293 s->nodesizes[tn->bits]++; 2295 s->nodesizes[tn->bits]++;
2294 depth++; 2296 depth++;
2295 2297
2296 n = tn->child[cindex]; 2298 n = tn->child[cindex];
2297 tn = (struct tnode *)n; 2299 tn = (struct tnode *)n;
2298 pend = tn->pos+tn->bits; 2300 pend = tn->pos+tn->bits;
@@ -2303,13 +2305,13 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2303 } 2305 }
2304 else { 2306 else {
2305 cindex++; 2307 cindex++;
2306 s->nullpointers++; 2308 s->nullpointers++;
2307 } 2309 }
2308 2310
2309 /* 2311 /*
2310 * Test if we are done 2312 * Test if we are done
2311 */ 2313 */
2312 2314
2313 while (cindex >= (1 << tn->bits)) { 2315 while (cindex >= (1 << tn->bits)) {
2314 2316
2315 /* 2317 /*
@@ -2317,7 +2319,7 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2317 * pop off all traversed nodes 2319 * pop off all traversed nodes
2318 */ 2320 */
2319 2321
2320 2322
2321 if (NODE_PARENT(tn) == NULL) { 2323 if (NODE_PARENT(tn) == NULL) {
2322 tn = NULL; 2324 tn = NULL;
2323 n = NULL; 2325 n = NULL;
@@ -2326,9 +2328,9 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2326 else { 2328 else {
2327 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits); 2329 cindex = tkey_extract_bits(tn->key, NODE_PARENT(tn)->pos, NODE_PARENT(tn)->bits);
2328 tn = NODE_PARENT(tn); 2330 tn = NODE_PARENT(tn);
2329 cindex++; 2331 cindex++;
2330 n = (struct node *)tn; 2332 n = (struct node *)tn;
2331 pend=tn->pos+tn->bits; 2333 pend = tn->pos+tn->bits;
2332 indent -= 3; 2334 indent -= 3;
2333 depth--; 2335 depth--;
2334 } 2336 }
@@ -2339,7 +2341,7 @@ static struct trie_stat *trie_collect_stats(struct trie *t)
2339 } 2341 }
2340 } 2342 }
2341 2343
2342 read_unlock(&fib_lock); 2344 read_unlock(&fib_lock);
2343 return s; 2345 return s;
2344} 2346}
2345 2347
@@ -2375,7 +2377,7 @@ static void fib_triestat_seq_stop(struct seq_file *seq, void *v)
2375 2377
2376} 2378}
2377 2379
2378/* 2380/*
2379 * This outputs /proc/net/fib_triestats 2381 * This outputs /proc/net/fib_triestats
2380 * 2382 *
2381 * It always works in backward compatibility mode. 2383 * It always works in backward compatibility mode.
@@ -2401,7 +2403,7 @@ static void collect_and_show(struct trie *t, struct seq_file *seq)
2401 avdepth=0; 2403 avdepth=0;
2402 seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth % 100 ); 2404 seq_printf(seq, "Aver depth: %d.%02d\n", avdepth / 100, avdepth % 100 );
2403 seq_printf(seq, "Max depth: %4d\n", stat->maxdepth); 2405 seq_printf(seq, "Max depth: %4d\n", stat->maxdepth);
2404 2406
2405 seq_printf(seq, "Leaves: %d\n", stat->leaves); 2407 seq_printf(seq, "Leaves: %d\n", stat->leaves);
2406 bytes += sizeof(struct leaf) * stat->leaves; 2408 bytes += sizeof(struct leaf) * stat->leaves;
2407 seq_printf(seq, "Internal nodes: %d\n", stat->tnodes); 2409 seq_printf(seq, "Internal nodes: %d\n", stat->tnodes);
@@ -2413,7 +2415,7 @@ static void collect_and_show(struct trie *t, struct seq_file *seq)
2413 max--; 2415 max--;
2414 pointers = 0; 2416 pointers = 0;
2415 2417
2416 for (i = 1; i <= max; i++) 2418 for (i = 1; i <= max; i++)
2417 if (stat->nodesizes[i] != 0) { 2419 if (stat->nodesizes[i] != 0) {
2418 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]); 2420 seq_printf(seq, " %d: %d", i, stat->nodesizes[i]);
2419 pointers += (1<<i) * stat->nodesizes[i]; 2421 pointers += (1<<i) * stat->nodesizes[i];
@@ -2444,30 +2446,30 @@ static void collect_and_show(struct trie *t, struct seq_file *seq)
2444static int fib_triestat_seq_show(struct seq_file *seq, void *v) 2446static int fib_triestat_seq_show(struct seq_file *seq, void *v)
2445{ 2447{
2446 char bf[128]; 2448 char bf[128];
2447 2449
2448 if (v == SEQ_START_TOKEN) { 2450 if (v == SEQ_START_TOKEN) {
2449 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n", 2451 seq_printf(seq, "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n",
2450 sizeof(struct leaf), sizeof(struct tnode)); 2452 sizeof(struct leaf), sizeof(struct tnode));
2451 if (trie_local) 2453 if (trie_local)
2452 collect_and_show(trie_local, seq); 2454 collect_and_show(trie_local, seq);
2453 2455
2454 if (trie_main) 2456 if (trie_main)
2455 collect_and_show(trie_main, seq); 2457 collect_and_show(trie_main, seq);
2456 } 2458 }
2457 else { 2459 else {
2458 snprintf(bf, sizeof(bf), 2460 snprintf(bf, sizeof(bf),
2459 "*\t%08X\t%08X", 200, 400); 2461 "*\t%08X\t%08X", 200, 400);
2460 2462
2461 seq_printf(seq, "%-127s\n", bf); 2463 seq_printf(seq, "%-127s\n", bf);
2462 } 2464 }
2463 return 0; 2465 return 0;
2464} 2466}
2465 2467
2466static struct seq_operations fib_triestat_seq_ops = { 2468static struct seq_operations fib_triestat_seq_ops = {
2467 .start = fib_triestat_seq_start, 2469 .start = fib_triestat_seq_start,
2468 .next = fib_triestat_seq_next, 2470 .next = fib_triestat_seq_next,
2469 .stop = fib_triestat_seq_stop, 2471 .stop = fib_triestat_seq_stop,
2470 .show = fib_triestat_seq_show, 2472 .show = fib_triestat_seq_show,
2471}; 2473};
2472 2474
2473static int fib_triestat_seq_open(struct inode *inode, struct file *file) 2475static int fib_triestat_seq_open(struct inode *inode, struct file *file)
@@ -2479,7 +2481,7 @@ static int fib_triestat_seq_open(struct inode *inode, struct file *file)
2479 if (rc) 2481 if (rc)
2480 goto out_kfree; 2482 goto out_kfree;
2481 2483
2482 seq = file->private_data; 2484 seq = file->private_data;
2483out: 2485out:
2484 return rc; 2486 return rc;
2485out_kfree: 2487out_kfree:
@@ -2487,11 +2489,11 @@ out_kfree:
2487} 2489}
2488 2490
2489static struct file_operations fib_triestat_seq_fops = { 2491static struct file_operations fib_triestat_seq_fops = {
2490 .owner = THIS_MODULE, 2492 .owner = THIS_MODULE,
2491 .open = fib_triestat_seq_open, 2493 .open = fib_triestat_seq_open,
2492 .read = seq_read, 2494 .read = seq_read,
2493 .llseek = seq_lseek, 2495 .llseek = seq_lseek,
2494 .release = seq_release_private, 2496 .release = seq_release_private,
2495}; 2497};
2496 2498
2497int __init fib_stat_proc_init(void) 2499int __init fib_stat_proc_init(void)
@@ -2536,7 +2538,7 @@ static void fib_trie_seq_stop(struct seq_file *seq, void *v)
2536 2538
2537} 2539}
2538 2540
2539/* 2541/*
2540 * This outputs /proc/net/fib_trie. 2542 * This outputs /proc/net/fib_trie.
2541 * 2543 *
2542 * It always works in backward compatibility mode. 2544 * It always works in backward compatibility mode.
@@ -2548,10 +2550,10 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
2548 char bf[128]; 2550 char bf[128];
2549 2551
2550 if (v == SEQ_START_TOKEN) { 2552 if (v == SEQ_START_TOKEN) {
2551 if (trie_local) 2553 if (trie_local)
2552 trie_dump_seq(seq, trie_local); 2554 trie_dump_seq(seq, trie_local);
2553 2555
2554 if (trie_main) 2556 if (trie_main)
2555 trie_dump_seq(seq, trie_main); 2557 trie_dump_seq(seq, trie_main);
2556 } 2558 }
2557 2559
@@ -2565,10 +2567,10 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
2565} 2567}
2566 2568
2567static struct seq_operations fib_trie_seq_ops = { 2569static struct seq_operations fib_trie_seq_ops = {
2568 .start = fib_trie_seq_start, 2570 .start = fib_trie_seq_start,
2569 .next = fib_trie_seq_next, 2571 .next = fib_trie_seq_next,
2570 .stop = fib_trie_seq_stop, 2572 .stop = fib_trie_seq_stop,
2571 .show = fib_trie_seq_show, 2573 .show = fib_trie_seq_show,
2572}; 2574};
2573 2575
2574static int fib_trie_seq_open(struct inode *inode, struct file *file) 2576static int fib_trie_seq_open(struct inode *inode, struct file *file)
@@ -2580,7 +2582,7 @@ static int fib_trie_seq_open(struct inode *inode, struct file *file)
2580 if (rc) 2582 if (rc)
2581 goto out_kfree; 2583 goto out_kfree;
2582 2584
2583 seq = file->private_data; 2585 seq = file->private_data;
2584out: 2586out:
2585 return rc; 2587 return rc;
2586out_kfree: 2588out_kfree:
@@ -2588,11 +2590,11 @@ out_kfree:
2588} 2590}
2589 2591
2590static struct file_operations fib_trie_seq_fops = { 2592static struct file_operations fib_trie_seq_fops = {
2591 .owner = THIS_MODULE, 2593 .owner = THIS_MODULE,
2592 .open = fib_trie_seq_open, 2594 .open = fib_trie_seq_open,
2593 .read = seq_read, 2595 .read = seq_read,
2594 .llseek = seq_lseek, 2596 .llseek = seq_lseek,
2595 .release = seq_release_private, 2597 .release= seq_release_private,
2596}; 2598};
2597 2599
2598int __init fib_proc_init(void) 2600int __init fib_proc_init(void)
generated by cgit v1.2.2 (git 2.25.0) at 2024-11-10 15:12:12 -0500