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.c100
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
160static int trie_debug = 0;
161
162#define DBG(x...) do { if (trie_debug) printk(x); } while (0)
163
164static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); 160static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
165static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); 161static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull);
166static struct node *resize(struct trie *t, struct tnode *tn); 162static struct node *resize(struct trie *t, struct tnode *tn);
@@ -168,12 +164,6 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn);
168static struct tnode *halve(struct trie *t, struct tnode *tn); 164static struct tnode *halve(struct trie *t, struct tnode *tn);
169static void tnode_free(struct tnode *tn); 165static void tnode_free(struct tnode *tn);
170static void trie_dump_seq(struct seq_file *seq, struct trie *t); 166static void trie_dump_seq(struct seq_file *seq, struct trie *t);
171extern struct fib_alias *fib_find_alias(struct list_head *fah, u8 tos, u32 prio);
172extern int fib_detect_death(struct fib_info *fi, int order,
173 struct fib_info **last_resort, int *last_idx, int *dflt);
174
175extern 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
178static kmem_cache_t *fn_alias_kmem; 168static kmem_cache_t *fn_alias_kmem;
179static struct trie *trie_local = NULL, *trie_main = NULL; 169static 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
297static void check_tnode(struct tnode *tn) 287static 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
304static int halve_threshold = 25; 292static 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
382static void tnode_free(struct tnode *tn) 370static 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
1285static inline int check_leaf(struct trie *t, struct leaf *l, t_key key, int *plen, const struct flowi *flp, 1249static 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