diff options
| -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 | ||
