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.c237
1 files changed, 142 insertions, 95 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 9291e7c41fc7..899210b3c6b7 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -155,7 +155,8 @@ struct trie {
155}; 155};
156 156
157static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n); 157static void put_child(struct trie *t, struct tnode *tn, int i, struct node *n);
158static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull); 158static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n,
159 int wasfull);
159static struct node *resize(struct trie *t, struct tnode *tn); 160static struct node *resize(struct trie *t, struct tnode *tn);
160static struct tnode *inflate(struct trie *t, struct tnode *tn); 161static struct tnode *inflate(struct trie *t, struct tnode *tn);
161static struct tnode *halve(struct trie *t, struct tnode *tn); 162static 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
398static struct tnode* tnode_new(t_key key, int pos, int bits) 399static 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
430static inline void put_child(struct trie *t, struct tnode *tn, int i, struct node *n) 431static 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
440static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int wasfull) 442static 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
902static inline struct list_head * get_fa_head(struct leaf *l, int plen) 913static 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 */
1292static inline int check_leaf(struct trie *t, struct leaf *l, 1313static 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
1322static int 1345static int fn_trie_lookup(struct fib_table *tb, const struct flowi *flp,
1323fn_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
1768static void 1803static void fn_trie_select_default(struct fib_table *tb,
1769fn_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
1840static int fn_trie_dump_fa(t_key key, int plen, struct list_head *fah, struct fib_table *tb, 1876static 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
1879static int fn_trie_dump_plen(struct trie *t, int plen, struct fib_table *tb, struct sk_buff *skb, 1916static 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
1912static int fn_trie_dump(struct fib_table *tb, struct sk_buff *skb, struct netlink_callback *cb) 1949static 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
1940void __init fib_hash_init(void) 1978void __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
2151static void fib_trie_show(struct seq_file *seq, const char *name, struct trie *trie) 2194static 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
generated by cgit v1.2.2 (git 2.25.0) at 2024-12-02 20:58:43 -0500