diff options
author | Stephen Hemminger <stephen.hemminger@vyatta.com> | 2008-01-23 00:53:36 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2008-01-28 18:10:56 -0500 |
commit | a07f5f508a4d9728c8e57d7f66294bf5b254ff7f (patch) | |
tree | 86f5fae939e2deac0c91eb065b4d7479636e58b3 /net/ipv4/fib_trie.c | |
parent | bc3c8c1e02ae89668239742fd592f21e1998fa46 (diff) |
[IPV4] fib_trie: style cleanup
Style cleanups:
* make check_leaf return -1 or plen, rather than by reference
* Get rid of #ifdef that is always set
* split out embedded function calls in if statements.
* checkpatch warnings
Signed-off-by: Stephen Hemminger <stephen.hemminger@vyatta.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r-- | net/ipv4/fib_trie.c | 237 |
1 files changed, 142 insertions, 95 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 9291e7c41fc..899210b3c6b 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c | |||
@@ -155,7 +155,8 @@ struct trie { | |||
155 | }; | 155 | }; |
156 | 156 | ||
157 | static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); | 157 | static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); |
158 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); | 158 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, |
159 | int wasfull); | ||
159 | static struct node *resize(struct trie *t, struct tnode *tn); | 160 | static struct node *resize(struct trie *t, struct tnode *tn); |
160 | static struct tnode *inflate(struct trie *t, struct tnode *tn); | 161 | static struct tnode *inflate(struct trie *t, struct tnode *tn); |
161 | static struct tnode *halve(struct trie *t, struct tnode *tn); | 162 | static struct tnode *halve(struct trie *t, struct tnode *tn); |
@@ -395,7 +396,7 @@ static struct leaf_info *leaf_info_new(int plen) | |||
395 | return li; | 396 | return li; |
396 | } | 397 | } |
397 | 398 | ||
398 | static struct tnode* tnode_new(t_key key, int pos, int bits) | 399 | static struct tnode *tnode_new(t_key key, int pos, int bits) |
399 | { | 400 | { |
400 | size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits); | 401 | size_t sz = sizeof(struct tnode) + (sizeof(struct node *) << bits); |
401 | struct tnode *tn = tnode_alloc(sz); | 402 | struct tnode *tn = tnode_alloc(sz); |
@@ -427,7 +428,8 @@ static inline int tnode_full(const struct tnode *tn, const struct node *n) | |||
427 | return ((struct tnode *) n)->pos == tn->pos + tn->bits; | 428 | return ((struct tnode *) n)->pos == tn->pos + tn->bits; |
428 | } | 429 | } |
429 | 430 | ||
430 | static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n) | 431 | static inline void put_child(struct trie *t, struct tnode *tn, int i, |
432 | struct node *n) | ||
431 | { | 433 | { |
432 | tnode_put_child_reorg(tn, i, n, -1); | 434 | tnode_put_child_reorg(tn, i, n, -1); |
433 | } | 435 | } |
@@ -437,7 +439,8 @@ static inline void put_child(struct trie *t, struct tnode *tn, int i, struct nod | |||
437 | * Update the value of full_children and empty_children. | 439 | * Update the value of full_children and empty_children. |
438 | */ | 440 | */ |
439 | 441 | ||
440 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull) | 442 | static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, |
443 | int wasfull) | ||
441 | { | 444 | { |
442 | struct node *chi = tn->child[i]; | 445 | struct node *chi = tn->child[i]; |
443 | int isfull; | 446 | int isfull; |
@@ -577,11 +580,13 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
577 | err = 0; | 580 | err = 0; |
578 | max_resize = 10; | 581 | max_resize = 10; |
579 | while ((tn->full_children > 0 && max_resize-- && | 582 | while ((tn->full_children > 0 && max_resize-- && |
580 | 50 * (tn->full_children + tnode_child_length(tn) - tn->empty_children) >= | 583 | 50 * (tn->full_children + tnode_child_length(tn) |
581 | inflate_threshold_use * tnode_child_length(tn))) { | 584 | - tn->empty_children) |
585 | >= inflate_threshold_use * tnode_child_length(tn))) { | ||
582 | 586 | ||
583 | old_tn = tn; | 587 | old_tn = tn; |
584 | tn = inflate(t, tn); | 588 | tn = inflate(t, tn); |
589 | |||
585 | if (IS_ERR(tn)) { | 590 | if (IS_ERR(tn)) { |
586 | tn = old_tn; | 591 | tn = old_tn; |
587 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 592 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
@@ -593,11 +598,13 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
593 | 598 | ||
594 | if (max_resize < 0) { | 599 | if (max_resize < 0) { |
595 | if (!tn->parent) | 600 | if (!tn->parent) |
596 | printk(KERN_WARNING "Fix inflate_threshold_root. Now=%d size=%d bits\n", | 601 | pr_warning("Fix inflate_threshold_root." |
597 | inflate_threshold_root, tn->bits); | 602 | " Now=%d size=%d bits\n", |
603 | inflate_threshold_root, tn->bits); | ||
598 | else | 604 | else |
599 | printk(KERN_WARNING "Fix inflate_threshold. Now=%d size=%d bits\n", | 605 | pr_warning("Fix inflate_threshold." |
600 | inflate_threshold, tn->bits); | 606 | " Now=%d size=%d bits\n", |
607 | inflate_threshold, tn->bits); | ||
601 | } | 608 | } |
602 | 609 | ||
603 | check_tnode(tn); | 610 | check_tnode(tn); |
@@ -634,11 +641,13 @@ static struct node *resize(struct trie *t, struct tnode *tn) | |||
634 | 641 | ||
635 | if (max_resize < 0) { | 642 | if (max_resize < 0) { |
636 | if (!tn->parent) | 643 | if (!tn->parent) |
637 | printk(KERN_WARNING "Fix halve_threshold_root. Now=%d size=%d bits\n", | 644 | pr_warning("Fix halve_threshold_root." |
638 | halve_threshold_root, tn->bits); | 645 | " Now=%d size=%d bits\n", |
646 | halve_threshold_root, tn->bits); | ||
639 | else | 647 | else |
640 | printk(KERN_WARNING "Fix halve_threshold. Now=%d size=%d bits\n", | 648 | pr_warning("Fix halve_threshold." |
641 | halve_threshold, tn->bits); | 649 | " Now=%d size=%d bits\n", |
650 | halve_threshold, tn->bits); | ||
642 | } | 651 | } |
643 | 652 | ||
644 | /* Only one child remains */ | 653 | /* Only one child remains */ |
@@ -681,8 +690,9 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) | |||
681 | */ | 690 | */ |
682 | 691 | ||
683 | for (i = 0; i < olen; i++) { | 692 | for (i = 0; i < olen; i++) { |
684 | struct tnode *inode = (struct tnode *) tnode_get_child(oldtnode, i); | 693 | struct tnode *inode; |
685 | 694 | ||
695 | inode = (struct tnode *) tnode_get_child(oldtnode, i); | ||
686 | if (inode && | 696 | if (inode && |
687 | IS_TNODE(inode) && | 697 | IS_TNODE(inode) && |
688 | inode->pos == oldtnode->pos + oldtnode->bits && | 698 | inode->pos == oldtnode->pos + oldtnode->bits && |
@@ -722,8 +732,9 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn) | |||
722 | 732 | ||
723 | if (IS_LEAF(node) || ((struct tnode *) node)->pos > | 733 | if (IS_LEAF(node) || ((struct tnode *) node)->pos > |
724 | tn->pos + tn->bits - 1) { | 734 | tn->pos + tn->bits - 1) { |
725 | if (tkey_extract_bits(node->key, oldtnode->pos + oldtnode->bits, | 735 | if (tkey_extract_bits(node->key, |
726 | 1) == 0) | 736 | oldtnode->pos + oldtnode->bits, |
737 | 1) == 0) | ||
727 | put_child(t, tn, 2*i, node); | 738 | put_child(t, tn, 2*i, node); |
728 | else | 739 | else |
729 | put_child(t, tn, 2*i+1, node); | 740 | put_child(t, tn, 2*i+1, node); |
@@ -899,7 +910,7 @@ static struct leaf_info *find_leaf_info(struct leaf *l, int plen) | |||
899 | return NULL; | 910 | return NULL; |
900 | } | 911 | } |
901 | 912 | ||
902 | static inline struct list_head * get_fa_head(struct leaf *l, int plen) | 913 | static inline struct list_head *get_fa_head(struct leaf *l, int plen) |
903 | { | 914 | { |
904 | struct leaf_info *li = find_leaf_info(l, plen); | 915 | struct leaf_info *li = find_leaf_info(l, plen); |
905 | 916 | ||
@@ -949,7 +960,10 @@ fib_find_node(struct trie *t, u32 key) | |||
949 | 960 | ||
950 | if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { | 961 | if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { |
951 | pos = tn->pos + tn->bits; | 962 | pos = tn->pos + tn->bits; |
952 | n = tnode_get_child_rcu(tn, tkey_extract_bits(key, tn->pos, tn->bits)); | 963 | n = tnode_get_child_rcu(tn, |
964 | tkey_extract_bits(key, | ||
965 | tn->pos, | ||
966 | tn->bits)); | ||
953 | } else | 967 | } else |
954 | break; | 968 | break; |
955 | } | 969 | } |
@@ -970,8 +984,10 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn) | |||
970 | while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) { | 984 | while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) { |
971 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); | 985 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); |
972 | wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); | 986 | wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); |
973 | tn = (struct tnode *) resize (t, (struct tnode *)tn); | 987 | tn = (struct tnode *) resize(t, (struct tnode *)tn); |
974 | tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); | 988 | |
989 | tnode_put_child_reorg((struct tnode *)tp, cindex, | ||
990 | (struct node *)tn, wasfull); | ||
975 | 991 | ||
976 | tp = node_parent((struct node *) tn); | 992 | tp = node_parent((struct node *) tn); |
977 | if (!tp) | 993 | if (!tp) |
@@ -981,9 +997,9 @@ static struct node *trie_rebalance(struct trie *t, struct tnode *tn) | |||
981 | 997 | ||
982 | /* Handle last (top) tnode */ | 998 | /* Handle last (top) tnode */ |
983 | if (IS_TNODE(tn)) | 999 | if (IS_TNODE(tn)) |
984 | tn = (struct tnode*) resize(t, (struct tnode *)tn); | 1000 | tn = (struct tnode *)resize(t, (struct tnode *)tn); |
985 | 1001 | ||
986 | return (struct node*) tn; | 1002 | return (struct node *)tn; |
987 | } | 1003 | } |
988 | 1004 | ||
989 | /* only used from updater-side */ | 1005 | /* only used from updater-side */ |
@@ -1028,7 +1044,10 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1028 | if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { | 1044 | if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) { |
1029 | tp = tn; | 1045 | tp = tn; |
1030 | pos = tn->pos + tn->bits; | 1046 | pos = tn->pos + tn->bits; |
1031 | n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); | 1047 | n = tnode_get_child(tn, |
1048 | tkey_extract_bits(key, | ||
1049 | tn->pos, | ||
1050 | tn->bits)); | ||
1032 | 1051 | ||
1033 | BUG_ON(n && node_parent(n) != tn); | 1052 | BUG_ON(n && node_parent(n) != tn); |
1034 | } else | 1053 | } else |
@@ -1113,16 +1132,18 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen) | |||
1113 | 1132 | ||
1114 | if (tp) { | 1133 | if (tp) { |
1115 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); | 1134 | cindex = tkey_extract_bits(key, tp->pos, tp->bits); |
1116 | put_child(t, (struct tnode *)tp, cindex, (struct node *)tn); | 1135 | put_child(t, (struct tnode *)tp, cindex, |
1136 | (struct node *)tn); | ||
1117 | } else { | 1137 | } else { |
1118 | rcu_assign_pointer(t->trie, (struct node *)tn); /* First tnode */ | 1138 | rcu_assign_pointer(t->trie, (struct node *)tn); |
1119 | tp = tn; | 1139 | tp = tn; |
1120 | } | 1140 | } |
1121 | } | 1141 | } |
1122 | 1142 | ||
1123 | if (tp && tp->pos + tp->bits > 32) | 1143 | if (tp && tp->pos + tp->bits > 32) |
1124 | printk(KERN_WARNING "fib_trie tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", | 1144 | pr_warning("fib_trie" |
1125 | tp, tp->pos, tp->bits, key, plen); | 1145 | " tp=%p pos=%d, bits=%d, key=%0x plen=%d\n", |
1146 | tp, tp->pos, tp->bits, key, plen); | ||
1126 | 1147 | ||
1127 | /* Rebalance the trie */ | 1148 | /* Rebalance the trie */ |
1128 | 1149 | ||
@@ -1235,10 +1256,10 @@ static int fn_trie_insert(struct fib_table *tb, struct fib_config *cfg) | |||
1235 | break; | 1256 | break; |
1236 | if (fa->fa_type == cfg->fc_type && | 1257 | if (fa->fa_type == cfg->fc_type && |
1237 | fa->fa_scope == cfg->fc_scope && | 1258 | fa->fa_scope == cfg->fc_scope && |
1238 | fa->fa_info == fi) { | 1259 | fa->fa_info == fi) |
1239 | goto out; | 1260 | goto out; |
1240 | } | ||
1241 | } | 1261 | } |
1262 | |||
1242 | if (!(cfg->fc_nlflags & NLM_F_APPEND)) | 1263 | if (!(cfg->fc_nlflags & NLM_F_APPEND)) |
1243 | fa = fa_orig; | 1264 | fa = fa_orig; |
1244 | } | 1265 | } |
@@ -1289,38 +1310,40 @@ err: | |||
1289 | 1310 | ||
1290 | 1311 | ||
1291 | /* should be called with rcu_read_lock */ | 1312 | /* should be called with rcu_read_lock */ |
1292 | static inline int check_leaf(struct trie *t, struct leaf *l, | 1313 | static int check_leaf(struct trie *t, struct leaf *l, |
1293 | t_key key, int *plen, const struct flowi *flp, | 1314 | t_key key, const struct flowi *flp, |
1294 | struct fib_result *res) | 1315 | struct fib_result *res) |
1295 | { | 1316 | { |
1296 | int err, i; | ||
1297 | __be32 mask; | ||
1298 | struct leaf_info *li; | 1317 | struct leaf_info *li; |
1299 | struct hlist_head *hhead = &l->list; | 1318 | struct hlist_head *hhead = &l->list; |
1300 | struct hlist_node *node; | 1319 | struct hlist_node *node; |
1301 | 1320 | ||
1302 | hlist_for_each_entry_rcu(li, node, hhead, hlist) { | 1321 | hlist_for_each_entry_rcu(li, node, hhead, hlist) { |
1303 | i = li->plen; | 1322 | int err; |
1304 | mask = inet_make_mask(i); | 1323 | int plen = li->plen; |
1324 | __be32 mask = inet_make_mask(plen); | ||
1325 | |||
1305 | if (l->key != (key & ntohl(mask))) | 1326 | if (l->key != (key & ntohl(mask))) |
1306 | continue; | 1327 | continue; |
1307 | 1328 | ||
1308 | if ((err = fib_semantic_match(&li->falh, flp, res, htonl(l->key), mask, i)) <= 0) { | 1329 | err = fib_semantic_match(&li->falh, flp, res, |
1309 | *plen = i; | 1330 | htonl(l->key), mask, plen); |
1331 | |||
1310 | #ifdef CONFIG_IP_FIB_TRIE_STATS | 1332 | #ifdef CONFIG_IP_FIB_TRIE_STATS |
1333 | if (err <= 0) | ||
1311 | t->stats.semantic_match_passed++; | 1334 | t->stats.semantic_match_passed++; |
1335 | else | ||
1336 | t->stats.semantic_match_miss++; | ||
1312 | #endif | 1337 | #endif |
1313 | return err; | 1338 | if (err <= 0) |
1314 | } | 1339 | return plen; |
1315 | #ifdef CONFIG_IP_FIB_TRIE_STATS | ||
1316 | t->stats.semantic_match_miss++; | ||
1317 | #endif | ||
1318 | } | 1340 | } |
1319 | return 1; | 1341 | |
1342 | return -1; | ||
1320 | } | 1343 | } |
1321 | 1344 | ||
1322 | static int | 1345 | static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, |
1323 | fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) | 1346 | struct fib_result *res) |
1324 | { | 1347 | { |
1325 | struct trie *t = (struct trie *) tb->tb_data; | 1348 | struct trie *t = (struct trie *) tb->tb_data; |
1326 | int plen, ret = 0; | 1349 | int plen, ret = 0; |
@@ -1347,10 +1370,13 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1347 | 1370 | ||
1348 | /* Just a leaf? */ | 1371 | /* Just a leaf? */ |
1349 | if (IS_LEAF(n)) { | 1372 | if (IS_LEAF(n)) { |
1350 | if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) | 1373 | plen = check_leaf(t, (struct leaf *)n, key, flp, res); |
1351 | goto found; | 1374 | if (plen < 0) |
1352 | goto failed; | 1375 | goto failed; |
1376 | ret = 0; | ||
1377 | goto found; | ||
1353 | } | 1378 | } |
1379 | |||
1354 | pn = (struct tnode *) n; | 1380 | pn = (struct tnode *) n; |
1355 | chopped_off = 0; | 1381 | chopped_off = 0; |
1356 | 1382 | ||
@@ -1372,14 +1398,14 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1372 | } | 1398 | } |
1373 | 1399 | ||
1374 | if (IS_LEAF(n)) { | 1400 | if (IS_LEAF(n)) { |
1375 | if ((ret = check_leaf(t, (struct leaf *)n, key, &plen, flp, res)) <= 0) | 1401 | plen = check_leaf(t, (struct leaf *)n, key, flp, res); |
1376 | goto found; | 1402 | if (plen < 0) |
1377 | else | ||
1378 | goto backtrace; | 1403 | goto backtrace; |
1404 | |||
1405 | ret = 0; | ||
1406 | goto found; | ||
1379 | } | 1407 | } |
1380 | 1408 | ||
1381 | #define HL_OPTIMIZE | ||
1382 | #ifdef HL_OPTIMIZE | ||
1383 | cn = (struct tnode *)n; | 1409 | cn = (struct tnode *)n; |
1384 | 1410 | ||
1385 | /* | 1411 | /* |
@@ -1408,12 +1434,13 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1408 | * *are* zero. | 1434 | * *are* zero. |
1409 | */ | 1435 | */ |
1410 | 1436 | ||
1411 | /* NOTA BENE: CHECKING ONLY SKIPPED BITS FOR THE NEW NODE HERE */ | 1437 | /* NOTA BENE: Checking only skipped bits |
1438 | for the new node here */ | ||
1412 | 1439 | ||
1413 | if (current_prefix_length < pos+bits) { | 1440 | if (current_prefix_length < pos+bits) { |
1414 | if (tkey_extract_bits(cn->key, current_prefix_length, | 1441 | if (tkey_extract_bits(cn->key, current_prefix_length, |
1415 | cn->pos - current_prefix_length) != 0 || | 1442 | cn->pos - current_prefix_length) |
1416 | !(cn->child[0])) | 1443 | || !(cn->child[0])) |
1417 | goto backtrace; | 1444 | goto backtrace; |
1418 | } | 1445 | } |
1419 | 1446 | ||
@@ -1436,14 +1463,17 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1436 | * new tnode's key. | 1463 | * new tnode's key. |
1437 | */ | 1464 | */ |
1438 | 1465 | ||
1439 | /* Note: We aren't very concerned about the piece of the key | 1466 | /* |
1440 | * that precede pn->pos+pn->bits, since these have already been | 1467 | * Note: We aren't very concerned about the piece of |
1441 | * checked. The bits after cn->pos aren't checked since these are | 1468 | * the key that precede pn->pos+pn->bits, since these |
1442 | * by definition "unknown" at this point. Thus, what we want to | 1469 | * have already been checked. The bits after cn->pos |
1443 | * see is if we are about to enter the "prefix matching" state, | 1470 | * aren't checked since these are by definition |
1444 | * and in that case verify that the skipped bits that will prevail | 1471 | * "unknown" at this point. Thus, what we want to see |
1445 | * throughout this subtree are zero, as they have to be if we are | 1472 | * is if we are about to enter the "prefix matching" |
1446 | * to find a matching prefix. | 1473 | * state, and in that case verify that the skipped |
1474 | * bits that will prevail throughout this subtree are | ||
1475 | * zero, as they have to be if we are to find a | ||
1476 | * matching prefix. | ||
1447 | */ | 1477 | */ |
1448 | 1478 | ||
1449 | node_prefix = mask_pfx(cn->key, cn->pos); | 1479 | node_prefix = mask_pfx(cn->key, cn->pos); |
@@ -1451,13 +1481,15 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1451 | pref_mismatch = key_prefix^node_prefix; | 1481 | pref_mismatch = key_prefix^node_prefix; |
1452 | mp = 0; | 1482 | mp = 0; |
1453 | 1483 | ||
1454 | /* In short: If skipped bits in this node do not match the search | 1484 | /* |
1455 | * key, enter the "prefix matching" state.directly. | 1485 | * In short: If skipped bits in this node do not match |
1486 | * the search key, enter the "prefix matching" | ||
1487 | * state.directly. | ||
1456 | */ | 1488 | */ |
1457 | if (pref_mismatch) { | 1489 | if (pref_mismatch) { |
1458 | while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) { | 1490 | while (!(pref_mismatch & (1<<(KEYLENGTH-1)))) { |
1459 | mp++; | 1491 | mp++; |
1460 | pref_mismatch = pref_mismatch <<1; | 1492 | pref_mismatch = pref_mismatch << 1; |
1461 | } | 1493 | } |
1462 | key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); | 1494 | key_prefix = tkey_extract_bits(cn->key, mp, cn->pos-mp); |
1463 | 1495 | ||
@@ -1467,7 +1499,7 @@ fn_trie_lookup(struct fib_table *tb, const struct flowi *flp, struct fib_result | |||
1467 | if (current_prefix_length >= cn->pos) | 1499 | if (current_prefix_length >= cn->pos) |
1468 | current_prefix_length = mp; | 1500 | current_prefix_length = mp; |
1469 | } | 1501 | } |
1470 | #endif | 1502 | |
1471 | pn = (struct tnode *)n; /* Descend */ | 1503 | pn = (struct tnode *)n; /* Descend */ |
1472 | chopped_off = 0; | 1504 | chopped_off = 0; |
1473 | continue; | 1505 | continue; |
@@ -1476,12 +1508,14 @@ backtrace: | |||
1476 | chopped_off++; | 1508 | chopped_off++; |
1477 | 1509 | ||
1478 | /* As zero don't change the child key (cindex) */ | 1510 | /* As zero don't change the child key (cindex) */ |
1479 | while ((chopped_off <= pn->bits) && !(cindex & (1<<(chopped_off-1)))) | 1511 | while ((chopped_off <= pn->bits) |
1512 | && !(cindex & (1<<(chopped_off-1)))) | ||
1480 | chopped_off++; | 1513 | chopped_off++; |
1481 | 1514 | ||
1482 | /* Decrease current_... with bits chopped off */ | 1515 | /* Decrease current_... with bits chopped off */ |
1483 | if (current_prefix_length > pn->pos + pn->bits - chopped_off) | 1516 | if (current_prefix_length > pn->pos + pn->bits - chopped_off) |
1484 | current_prefix_length = pn->pos + pn->bits - chopped_off; | 1517 | current_prefix_length = pn->pos + pn->bits |
1518 | - chopped_off; | ||
1485 | 1519 | ||
1486 | /* | 1520 | /* |
1487 | * Either we do the actual chop off according or if we have | 1521 | * Either we do the actual chop off according or if we have |
@@ -1531,7 +1565,8 @@ static int trie_leaf_remove(struct trie *t, t_key key) | |||
1531 | while (n != NULL && IS_TNODE(n)) { | 1565 | while (n != NULL && IS_TNODE(n)) { |
1532 | struct tnode *tn = (struct tnode *) n; | 1566 | struct tnode *tn = (struct tnode *) n; |
1533 | check_tnode(tn); | 1567 | check_tnode(tn); |
1534 | n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); | 1568 | n = tnode_get_child(tn, tkey_extract_bits(key, |
1569 | tn->pos, tn->bits)); | ||
1535 | 1570 | ||
1536 | BUG_ON(n && node_parent(n) != tn); | 1571 | BUG_ON(n && node_parent(n) != tn); |
1537 | } | 1572 | } |
@@ -1697,7 +1732,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf) | |||
1697 | if (IS_LEAF(trie)) /* trie w. just a leaf */ | 1732 | if (IS_LEAF(trie)) /* trie w. just a leaf */ |
1698 | return (struct leaf *) trie; | 1733 | return (struct leaf *) trie; |
1699 | 1734 | ||
1700 | p = (struct tnode*) trie; /* Start */ | 1735 | p = (struct tnode *)trie; /* Start */ |
1701 | } else | 1736 | } else |
1702 | p = node_parent_rcu(c); | 1737 | p = node_parent_rcu(c); |
1703 | 1738 | ||
@@ -1765,8 +1800,9 @@ static int fn_trie_flush(struct fib_table *tb) | |||
1765 | return found; | 1800 | return found; |
1766 | } | 1801 | } |
1767 | 1802 | ||
1768 | static void | 1803 | static void fn_trie_select_default(struct fib_table *tb, |
1769 | fn_trie_select_default(struct fib_table *tb, const struct flowi *flp, struct fib_result *res) | 1804 | const struct flowi *flp, |
1805 | struct fib_result *res) | ||
1770 | { | 1806 | { |
1771 | struct trie *t = (struct trie *) tb->tb_data; | 1807 | struct trie *t = (struct trie *) tb->tb_data; |
1772 | int order, last_idx; | 1808 | int order, last_idx; |
@@ -1837,7 +1873,8 @@ out: | |||
1837 | rcu_read_unlock(); | 1873 | rcu_read_unlock(); |
1838 | } | 1874 | } |
1839 | 1875 | ||
1840 | static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb, | 1876 | static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, |
1877 | struct fib_table *tb, | ||
1841 | struct sk_buff *skb, struct netlink_callback *cb) | 1878 | struct sk_buff *skb, struct netlink_callback *cb) |
1842 | { | 1879 | { |
1843 | int i, s_i; | 1880 | int i, s_i; |
@@ -1876,8 +1913,8 @@ static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fi | |||
1876 | return skb->len; | 1913 | return skb->len; |
1877 | } | 1914 | } |
1878 | 1915 | ||
1879 | static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb, | 1916 | static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, |
1880 | struct netlink_callback *cb) | 1917 | struct sk_buff *skb, struct netlink_callback *cb) |
1881 | { | 1918 | { |
1882 | int h, s_h; | 1919 | int h, s_h; |
1883 | struct list_head *fa_head; | 1920 | struct list_head *fa_head; |
@@ -1900,7 +1937,7 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str | |||
1900 | if (list_empty(fa_head)) | 1937 | if (list_empty(fa_head)) |
1901 | continue; | 1938 | continue; |
1902 | 1939 | ||
1903 | if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb)<0) { | 1940 | if (fn_trie_dump_fa(l->key, plen, fa_head, tb, skb, cb) < 0) { |
1904 | cb->args[3] = h; | 1941 | cb->args[3] = h; |
1905 | return -1; | 1942 | return -1; |
1906 | } | 1943 | } |
@@ -1909,7 +1946,8 @@ static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, str | |||
1909 | return skb->len; | 1946 | return skb->len; |
1910 | } | 1947 | } |
1911 | 1948 | ||
1912 | static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb) | 1949 | static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, |
1950 | struct netlink_callback *cb) | ||
1913 | { | 1951 | { |
1914 | int m, s_m; | 1952 | int m, s_m; |
1915 | struct trie *t = (struct trie *) tb->tb_data; | 1953 | struct trie *t = (struct trie *) tb->tb_data; |
@@ -1924,7 +1962,7 @@ static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlin | |||
1924 | memset(&cb->args[3], 0, | 1962 | memset(&cb->args[3], 0, |
1925 | sizeof(cb->args) - 3*sizeof(cb->args[0])); | 1963 | sizeof(cb->args) - 3*sizeof(cb->args[0])); |
1926 | 1964 | ||
1927 | if (fn_trie_dump_plen(t, 32-m, tb, skb, cb)<0) { | 1965 | if (fn_trie_dump_plen(t, 32-m, tb, skb, cb) < 0) { |
1928 | cb->args[2] = m; | 1966 | cb->args[2] = m; |
1929 | goto out; | 1967 | goto out; |
1930 | } | 1968 | } |
@@ -1939,7 +1977,8 @@ out: | |||
1939 | 1977 | ||
1940 | void __init fib_hash_init(void) | 1978 | void __init fib_hash_init(void) |
1941 | { | 1979 | { |
1942 | fn_alias_kmem = kmem_cache_create("ip_fib_alias", sizeof(struct fib_alias), | 1980 | fn_alias_kmem = kmem_cache_create("ip_fib_alias", |
1981 | sizeof(struct fib_alias), | ||
1943 | 0, SLAB_PANIC, NULL); | 1982 | 0, SLAB_PANIC, NULL); |
1944 | 1983 | ||
1945 | trie_leaf_kmem = kmem_cache_create("ip_fib_trie", | 1984 | trie_leaf_kmem = kmem_cache_create("ip_fib_trie", |
@@ -1973,7 +2012,7 @@ struct fib_table *fib_hash_table(u32 id) | |||
1973 | memset(t, 0, sizeof(*t)); | 2012 | memset(t, 0, sizeof(*t)); |
1974 | 2013 | ||
1975 | if (id == RT_TABLE_LOCAL) | 2014 | if (id == RT_TABLE_LOCAL) |
1976 | printk(KERN_INFO "IPv4 FIB: Using LC-trie version %s\n", VERSION); | 2015 | pr_info("IPv4 FIB: Using LC-trie version %s\n", VERSION); |
1977 | 2016 | ||
1978 | return tb; | 2017 | return tb; |
1979 | } | 2018 | } |
@@ -2107,7 +2146,8 @@ static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat) | |||
2107 | else | 2146 | else |
2108 | avdepth = 0; | 2147 | avdepth = 0; |
2109 | 2148 | ||
2110 | seq_printf(seq, "\tAver depth: %u.%02d\n", avdepth / 100, avdepth % 100 ); | 2149 | seq_printf(seq, "\tAver depth: %u.%02d\n", |
2150 | avdepth / 100, avdepth % 100); | ||
2111 | seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth); | 2151 | seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth); |
2112 | 2152 | ||
2113 | seq_printf(seq, "\tLeaves: %u\n", stat->leaves); | 2153 | seq_printf(seq, "\tLeaves: %u\n", stat->leaves); |
@@ -2139,16 +2179,20 @@ static void trie_show_usage(struct seq_file *seq, | |||
2139 | const struct trie_use_stats *stats) | 2179 | const struct trie_use_stats *stats) |
2140 | { | 2180 | { |
2141 | seq_printf(seq, "\nCounters:\n---------\n"); | 2181 | seq_printf(seq, "\nCounters:\n---------\n"); |
2142 | seq_printf(seq,"gets = %u\n", stats->gets); | 2182 | seq_printf(seq, "gets = %u\n", stats->gets); |
2143 | seq_printf(seq,"backtracks = %u\n", stats->backtrack); | 2183 | seq_printf(seq, "backtracks = %u\n", stats->backtrack); |
2144 | seq_printf(seq,"semantic match passed = %u\n", stats->semantic_match_passed); | 2184 | seq_printf(seq, "semantic match passed = %u\n", |
2145 | seq_printf(seq,"semantic match miss = %u\n", stats->semantic_match_miss); | 2185 | stats->semantic_match_passed); |
2146 | seq_printf(seq,"null node hit= %u\n", stats->null_node_hit); | 2186 | seq_printf(seq, "semantic match miss = %u\n", |
2147 | seq_printf(seq,"skipped node resize = %u\n\n", stats->resize_node_skipped); | 2187 | stats->semantic_match_miss); |
2188 | seq_printf(seq, "null node hit= %u\n", stats->null_node_hit); | ||
2189 | seq_printf(seq, "skipped node resize = %u\n\n", | ||
2190 | stats->resize_node_skipped); | ||
2148 | } | 2191 | } |
2149 | #endif /* CONFIG_IP_FIB_TRIE_STATS */ | 2192 | #endif /* CONFIG_IP_FIB_TRIE_STATS */ |
2150 | 2193 | ||
2151 | static void fib_trie_show(struct seq_file *seq, const char *name, struct trie *trie) | 2194 | static void fib_trie_show(struct seq_file *seq, const char *name, |
2195 | struct trie *trie) | ||
2152 | { | 2196 | { |
2153 | struct trie_stat stat; | 2197 | struct trie_stat stat; |
2154 | 2198 | ||
@@ -2166,7 +2210,8 @@ static int fib_triestat_seq_show(struct seq_file *seq, void *v) | |||
2166 | struct fib_table *tb; | 2210 | struct fib_table *tb; |
2167 | 2211 | ||
2168 | seq_printf(seq, | 2212 | seq_printf(seq, |
2169 | "Basic info: size of leaf: %Zd bytes, size of tnode: %Zd bytes.\n", | 2213 | "Basic info: size of leaf:" |
2214 | " %Zd bytes, size of tnode: %Zd bytes.\n", | ||
2170 | sizeof(struct leaf), sizeof(struct tnode)); | 2215 | sizeof(struct leaf), sizeof(struct tnode)); |
2171 | 2216 | ||
2172 | tb = fib_get_table(net, RT_TABLE_LOCAL); | 2217 | tb = fib_get_table(net, RT_TABLE_LOCAL); |
@@ -2439,10 +2484,11 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) | |||
2439 | 2484 | ||
2440 | if (iter->trie == iter->trie_local) | 2485 | if (iter->trie == iter->trie_local) |
2441 | return 0; | 2486 | return 0; |
2487 | |||
2442 | if (IS_TNODE(l)) | 2488 | if (IS_TNODE(l)) |
2443 | return 0; | 2489 | return 0; |
2444 | 2490 | ||
2445 | for (i=32; i>=0; i--) { | 2491 | for (i = 32; i >= 0; i--) { |
2446 | struct leaf_info *li = find_leaf_info(l, i); | 2492 | struct leaf_info *li = find_leaf_info(l, i); |
2447 | struct fib_alias *fa; | 2493 | struct fib_alias *fa; |
2448 | __be32 mask, prefix; | 2494 | __be32 mask, prefix; |
@@ -2469,7 +2515,8 @@ static int fib_route_seq_show(struct seq_file *seq, void *v) | |||
2469 | fi->fib_nh->nh_gw, flags, 0, 0, | 2515 | fi->fib_nh->nh_gw, flags, 0, 0, |
2470 | fi->fib_priority, | 2516 | fi->fib_priority, |
2471 | mask, | 2517 | mask, |
2472 | (fi->fib_advmss ? fi->fib_advmss + 40 : 0), | 2518 | (fi->fib_advmss ? |
2519 | fi->fib_advmss + 40 : 0), | ||
2473 | fi->fib_window, | 2520 | fi->fib_window, |
2474 | fi->fib_rtt >> 3); | 2521 | fi->fib_rtt >> 3); |
2475 | else | 2522 | else |