diff options
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r-- | net/ipv4/fib_trie.c | 100 |
1 files changed, 31 insertions, 69 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 395f64df6f9a..9c4c7f0367b0 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c | |||
@@ -157,10 +157,6 @@ struct trie { | |||
157 | unsigned int revision; | 157 | unsigned int revision; |
158 | }; | 158 | }; |
159 | 159 | ||
160 | static int trie_debug = 0; | ||
161 | |||
162 | #define DBG(x...) do { if (trie_debug) printk(x); } while (0) | ||
163 | |||
164 | static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); | 160 | static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); |
165 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); | 161 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); |
166 | static struct node *resize(struct trie *t, struct tnode *tn); | 162 | static struct node *resize(struct trie *t, struct tnode *tn); |
@@ -168,12 +164,6 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn); | |||
168 | static struct tnode *halve(struct trie *t, struct tnode *tn); | 164 | static struct tnode *halve(struct trie *t, struct tnode *tn); |
169 | static void tnode_free(struct tnode *tn); | 165 | static void tnode_free(struct tnode *tn); |
170 | static void trie_dump_seq(struct seq_file *seq, struct trie *t); | 166 | static void trie_dump_seq(struct seq_file *seq, struct trie *t); |
171 | extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio); | ||
172 | extern int fib_detect_death(struct fib_info *fi, int order, | ||
173 | struct fib_info **last_resort, int *last_idx, int *dflt); | ||
174 | |||
175 | extern void rtmsg_fib(int event, u32 key, struct fib_alias *fa, int z, int tb_id, | ||
176 | struct nlmsghdr *n, struct netlink_skb_parms *req); | ||
177 | 167 | ||
178 | static kmem_cache_t *fn_alias_kmem; | 168 | static kmem_cache_t *fn_alias_kmem; |
179 | static struct trie *trie_local = NULL, *trie_main = NULL; | 169 | static struct trie *trie_local = NULL, *trie_main = NULL; |
@@ -294,11 +284,9 @@ static void fn_free_alias(struct fib_alias *fa) | |||
294 | 284 | ||
295 | */ | 285 | */ |
296 | 286 | ||
297 | static void check_tnode(struct tnode *tn) | 287 | static inline void check_tnode(const struct tnode *tn) |
298 | { | 288 | { |
299 | if (tn && tn->pos+tn->bits > 32) { | 289 | WARN_ON(tn && tn->pos+tn->bits > 32); |
300 | printk("TNODE ERROR tn=%p, pos=%d, bits=%d\n", tn, tn->pos, tn->bits); | ||
301 | } | ||
302 | } | 290 | } |
303 | 291 | ||
304 | static int halve_threshold = 25; | 292 | static int halve_threshold = 25; |
@@ -374,21 +362,19 @@ static struct tnode* tnode_new(t_key key, int pos, int bits) | |||
374 | tn->empty_children = 1<<bits; | 362 | tn->empty_children = 1<<bits; |
375 | } | 363 | } |
376 | 364 | ||
377 | DBG("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode), | 365 | pr_debug("AT %p s=%u %u\n", tn, (unsigned int) sizeof(struct tnode), |
378 | (unsigned int) (sizeof(struct node) * 1<<bits)); | 366 | (unsigned int) (sizeof(struct node) * 1<<bits)); |
379 | return tn; | 367 | return tn; |
380 | } | 368 | } |
381 | 369 | ||
382 | static void tnode_free(struct tnode *tn) | 370 | static void tnode_free(struct tnode *tn) |
383 | { | 371 | { |
384 | BUG_ON(!tn); | ||
385 | |||
386 | if (IS_LEAF(tn)) { | 372 | if (IS_LEAF(tn)) { |
387 | free_leaf((struct leaf *)tn); | 373 | free_leaf((struct leaf *)tn); |
388 | DBG("FL %p \n", tn); | 374 | pr_debug("FL %p \n", tn); |
389 | } else { | 375 | } else { |
390 | __tnode_free(tn); | 376 | __tnode_free(tn); |
391 | DBG("FT %p \n", tn); | 377 | pr_debug("FT %p \n", tn); |
392 | } | 378 | } |
393 | } | 379 | } |
394 | 380 | ||
@@ -420,10 +406,8 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int w | |||
420 | struct node *chi; | 406 | struct node *chi; |
421 | int isfull; | 407 | int isfull; |
422 | 408 | ||
423 | if (i >= 1<<tn->bits) { | 409 | BUG_ON(i >= 1<<tn->bits); |
424 | printk("bits=%d, i=%d\n", tn->bits, i); | 410 | |
425 | BUG(); | ||
426 | } | ||
427 | write_lock_bh(&fib_lock); | 411 | write_lock_bh(&fib_lock); |
428 | chi = tn->child[i]; | 412 | chi = tn->child[i]; |
429 | 413 | ||
@@ -459,8 +443,8 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
459 | if (!tn) | 443 | if (!tn) |
460 | return NULL; | 444 | return NULL; |
461 | 445 | ||
462 | DBG("In tnode_resize %p inflate_threshold=%d threshold=%d\n", | 446 | pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n", |
463 | tn, inflate_threshold, halve_threshold); | 447 | tn, inflate_threshold, halve_threshold); |
464 | 448 | ||
465 | /* No children */ | 449 | /* No children */ |
466 | if (tn->empty_children == tnode_child_length(tn)) { | 450 | if (tn->empty_children == tnode_child_length(tn)) { |
@@ -625,11 +609,11 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) | |||
625 | int olen = tnode_child_length(tn); | 609 | int olen = tnode_child_length(tn); |
626 | int i; | 610 | int i; |
627 | 611 | ||
628 | DBG("In inflate\n"); | 612 | pr_debug("In inflate\n"); |
629 | 613 | ||
630 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); | 614 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits + 1); |
631 | 615 | ||
632 | if (!tn) | 616 | if (!tn) |
633 | return ERR_PTR(-ENOMEM); | 617 | return ERR_PTR(-ENOMEM); |
634 | 618 | ||
635 | /* | 619 | /* |
@@ -749,12 +733,12 @@ nomem: | |||
749 | int size = tnode_child_length(tn); | 733 | int size = tnode_child_length(tn); |
750 | int j; | 734 | int j; |
751 | 735 | ||
752 | for(j = 0; j < size; j++) | 736 | for (j = 0; j < size; j++) |
753 | if (tn->child[j]) | 737 | if (tn->child[j]) |
754 | tnode_free((struct tnode *)tn->child[j]); | 738 | tnode_free((struct tnode *)tn->child[j]); |
755 | 739 | ||
756 | tnode_free(tn); | 740 | tnode_free(tn); |
757 | 741 | ||
758 | return ERR_PTR(-ENOMEM); | 742 | return ERR_PTR(-ENOMEM); |
759 | } | 743 | } |
760 | } | 744 | } |
@@ -766,7 +750,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn) | |||
766 | int i; | 750 | int i; |
767 | int olen = tnode_child_length(tn); | 751 | int olen = tnode_child_length(tn); |
768 | 752 | ||
769 | DBG("In halve\n"); | 753 | pr_debug("In halve\n"); |
770 | 754 | ||
771 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); | 755 | tn = tnode_new(oldtnode->key, oldtnode->pos, oldtnode->bits - 1); |
772 | 756 | ||
@@ -785,14 +769,14 @@ static struct tnode *halve(struct trie *t, struct tnode *tn) | |||
785 | right = tnode_get_child(oldtnode, i+1); | 769 | right = tnode_get_child(oldtnode, i+1); |
786 | 770 | ||
787 | /* Two nonempty children */ | 771 | /* Two nonempty children */ |
788 | if (left && right) { | 772 | if (left && right) { |
789 | struct tnode *newn; | 773 | struct tnode *newn; |
790 | 774 | ||
791 | newn = tnode_new(left->key, tn->pos + tn->bits, 1); | 775 | newn = tnode_new(left->key, tn->pos + tn->bits, 1); |
792 | 776 | ||
793 | if (!newn) | 777 | if (!newn) |
794 | goto nomem; | 778 | goto nomem; |
795 | 779 | ||
796 | put_child(t, tn, i/2, (struct node *)newn); | 780 | put_child(t, tn, i/2, (struct node *)newn); |
797 | } | 781 | } |
798 | 782 | ||
@@ -810,7 +794,7 @@ static struct tnode *halve(struct trie *t, struct tnode *tn) | |||
810 | continue; | 794 | continue; |
811 | put_child(t, tn, i/2, right); | 795 | put_child(t, tn, i/2, right); |
812 | continue; | 796 | continue; |
813 | } | 797 | } |
814 | 798 | ||
815 | if (right == NULL) { | 799 | if (right == NULL) { |
816 | put_child(t, tn, i/2, left); | 800 | put_child(t, tn, i/2, left); |
@@ -820,9 +804,6 @@ static struct tnode *halve(struct trie *t, struct tnode *tn) | |||
820 | /* Two nonempty children */ | 804 | /* Two nonempty children */ |
821 | newBinNode = (struct tnode *) tnode_get_child(tn, i/2); | 805 | newBinNode = (struct tnode *) tnode_get_child(tn, i/2); |
822 | put_child(t, tn, i/2, NULL); | 806 | put_child(t, tn, i/2, NULL); |
823 | |||
824 | BUG_ON(!newBinNode); | ||
825 | |||
826 | put_child(t, newBinNode, 0, left); | 807 | put_child(t, newBinNode, 0, left); |
827 | put_child(t, newBinNode, 1, right); | 808 | put_child(t, newBinNode, 1, right); |
828 | put_child(t, tn, i/2, resize(t, newBinNode)); | 809 | put_child(t, tn, i/2, resize(t, newBinNode)); |
@@ -834,12 +815,12 @@ nomem: | |||
834 | int size = tnode_child_length(tn); | 815 | int size = tnode_child_length(tn); |
835 | int j; | 816 | int j; |
836 | 817 | ||
837 | for(j = 0; j < size; j++) | 818 | for (j = 0; j < size; j++) |
838 | if (tn->child[j]) | 819 | if (tn->child[j]) |
839 | tnode_free((struct tnode *)tn->child[j]); | 820 | tnode_free((struct tnode *)tn->child[j]); |
840 | 821 | ||
841 | tnode_free(tn); | 822 | tnode_free(tn); |
842 | 823 | ||
843 | return ERR_PTR(-ENOMEM); | 824 | return ERR_PTR(-ENOMEM); |
844 | } | 825 | } |
845 | } | 826 | } |
@@ -939,22 +920,10 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn) | |||
939 | t_key cindex, key; | 920 | t_key cindex, key; |
940 | struct tnode *tp = NULL; | 921 | struct tnode *tp = NULL; |
941 | 922 | ||
942 | BUG_ON(!tn); | ||
943 | |||
944 | key = tn->key; | 923 | key = tn->key; |
945 | i = 0; | 924 | i = 0; |
946 | 925 | ||
947 | while (tn != NULL && NODE_PARENT(tn) != NULL) { | 926 | while (tn != NULL && NODE_PARENT(tn) != NULL) { |
948 | if (i > 10) { | ||
949 | printk("Rebalance tn=%p \n", tn); | ||
950 | if (tn) | ||
951 | printk("tn->parent=%p \n", NODE_PARENT(tn)); | ||
952 | |||
953 | printk("Rebalance tp=%p \n", tp); | ||
954 | if (tp) | ||
955 | printk("tp->parent=%p \n", NODE_PARENT(tp)); | ||
956 | } | ||
957 | |||
958 | BUG_ON(i > 12); /* Why is this a bug? -ojn */ | 927 | BUG_ON(i > 12); /* Why is this a bug? -ojn */ |
959 | i++; | 928 | i++; |
960 | 929 | ||
@@ -1019,10 +988,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen) | |||
1019 | pos = tn->pos + tn->bits; | 988 | pos = tn->pos + tn->bits; |
1020 | n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); | 989 | n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); |
1021 | 990 | ||
1022 | if (n && NODE_PARENT(n) != tn) { | 991 | BUG_ON(n && NODE_PARENT(n) != tn); |
1023 | printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); | ||
1024 | BUG(); | ||
1025 | } | ||
1026 | } else | 992 | } else |
1027 | break; | 993 | break; |
1028 | } | 994 | } |
@@ -1076,8 +1042,6 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen) | |||
1076 | 1042 | ||
1077 | NODE_SET_PARENT(l, tp); | 1043 | NODE_SET_PARENT(l, tp); |
1078 | 1044 | ||
1079 | BUG_ON(!tp); | ||
1080 | |||
1081 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); | 1045 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); |
1082 | put_child(t, (struct tnode *)tp, cindex, (struct node *)l); | 1046 | put_child(t, (struct tnode *)tp, cindex, (struct node *)l); |
1083 | } else { | 1047 | } else { |
@@ -1158,7 +1122,7 @@ fn_trie_insert(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, | |||
1158 | 1122 | ||
1159 | key = ntohl(key); | 1123 | key = ntohl(key); |
1160 | 1124 | ||
1161 | DBG("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); | 1125 | pr_debug("Insert table=%d %08x/%d\n", tb->tb_id, key, plen); |
1162 | 1126 | ||
1163 | mask = ntohl(inet_make_mask(plen)); | 1127 | mask = ntohl(inet_make_mask(plen)); |
1164 | 1128 | ||
@@ -1282,7 +1246,8 @@ err: | |||
1282 | return err; | 1246 | return err; |
1283 | } | 1247 | } |
1284 | 1248 | ||
1285 | static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *plen, const struct flowi *flp, | 1249 | static inline int check_leaf(struct trie *t, struct leaf *l, |
1250 | t_key key, int *plen, const struct flowi *flp, | ||
1286 | struct fib_result *res) | 1251 | struct fib_result *res) |
1287 | { | 1252 | { |
1288 | int err, i; | 1253 | int err, i; |
@@ -1511,7 +1476,7 @@ static int trie_leaf_remove(struct trie *t, t_key key) | |||
1511 | struct node *n = t->trie; | 1476 | struct node *n = t->trie; |
1512 | struct leaf *l; | 1477 | struct leaf *l; |
1513 | 1478 | ||
1514 | DBG("entering trie_leaf_remove(%p)\n", n); | 1479 | pr_debug("entering trie_leaf_remove(%p)\n", n); |
1515 | 1480 | ||
1516 | /* Note that in the case skipped bits, those bits are *not* checked! | 1481 | /* Note that in the case skipped bits, those bits are *not* checked! |
1517 | * When we finish this, we will have NULL or a T_LEAF, and the | 1482 | * When we finish this, we will have NULL or a T_LEAF, and the |
@@ -1523,10 +1488,7 @@ static int trie_leaf_remove(struct trie *t, t_key key) | |||
1523 | check_tnode(tn); | 1488 | check_tnode(tn); |
1524 | n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); | 1489 | n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); |
1525 | 1490 | ||
1526 | if (n && NODE_PARENT(n) != tn) { | 1491 | BUG_ON(n && NODE_PARENT(n) != tn); |
1527 | printk("BUG tn=%p, n->parent=%p\n", tn, NODE_PARENT(n)); | ||
1528 | BUG(); | ||
1529 | } | ||
1530 | } | 1492 | } |
1531 | l = (struct leaf *) n; | 1493 | l = (struct leaf *) n; |
1532 | 1494 | ||
@@ -1594,7 +1556,7 @@ fn_trie_delete(struct fib_table *tb, struct rtmsg *r, struct kern_rta *rta, | |||
1594 | if (!fa) | 1556 | if (!fa) |
1595 | return -ESRCH; | 1557 | return -ESRCH; |
1596 | 1558 | ||
1597 | DBG("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); | 1559 | pr_debug("Deleting %08x/%d tos=%d t=%p\n", key, plen, tos, t); |
1598 | 1560 | ||
1599 | fa_to_delete = NULL; | 1561 | fa_to_delete = NULL; |
1600 | fa_head = fa->fa_list.prev; | 1562 | fa_head = fa->fa_list.prev; |
@@ -1762,7 +1724,7 @@ static int fn_trie_flush(struct fib_table *tb) | |||
1762 | if (ll && hlist_empty(&ll->list)) | 1724 | if (ll && hlist_empty(&ll->list)) |
1763 | trie_leaf_remove(t, ll->key); | 1725 | trie_leaf_remove(t, ll->key); |
1764 | 1726 | ||
1765 | DBG("trie_flush found=%d\n", found); | 1727 | pr_debug("trie_flush found=%d\n", found); |
1766 | return found; | 1728 | return found; |
1767 | } | 1729 | } |
1768 | 1730 | ||