diff options
author | Alexander Duyck <alexander.h.duyck@redhat.com> | 2015-03-06 12:54:21 -0500 |
---|---|---|
committer | David S. Miller <davem@davemloft.net> | 2015-03-06 15:49:28 -0500 |
commit | 2e1ac88a48370620429cd9e54c41365531962809 (patch) | |
tree | 8558c255e8d83c8e963e0cf6713a0d1cc466a545 /net/ipv4/fib_trie.c | |
parent | 754baf8decce722db6d02bb0db745402f8cbc16f (diff) |
fib_trie: Rename tnode_child_length to child_length
We are now checking the length of a key_vector instead of a tnode so it
makes sense to probably just rename this to child_length since it would
probably even be applicable to a leaf.
Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.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 | 53 |
1 files changed, 29 insertions, 24 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index b9e2a6195572..b88c0d0f48ed 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c | |||
@@ -92,8 +92,6 @@ typedef unsigned int t_key; | |||
92 | #define IS_TNODE(n) ((n)->bits) | 92 | #define IS_TNODE(n) ((n)->bits) |
93 | #define IS_LEAF(n) (!(n)->bits) | 93 | #define IS_LEAF(n) (!(n)->bits) |
94 | 94 | ||
95 | #define get_index(_key, _kv) (((_key) ^ (_kv)->key) >> (_kv)->pos) | ||
96 | |||
97 | struct key_vector { | 95 | struct key_vector { |
98 | struct rcu_head rcu; | 96 | struct rcu_head rcu; |
99 | 97 | ||
@@ -177,11 +175,18 @@ static inline void node_set_parent(struct key_vector *n, struct key_vector *tp) | |||
177 | /* This provides us with the number of children in this node, in the case of a | 175 | /* This provides us with the number of children in this node, in the case of a |
178 | * leaf this will return 0 meaning none of the children are accessible. | 176 | * leaf this will return 0 meaning none of the children are accessible. |
179 | */ | 177 | */ |
180 | static inline unsigned long tnode_child_length(const struct key_vector *tn) | 178 | static inline unsigned long child_length(const struct key_vector *tn) |
181 | { | 179 | { |
182 | return (1ul << tn->bits) & ~(1ul); | 180 | return (1ul << tn->bits) & ~(1ul); |
183 | } | 181 | } |
184 | 182 | ||
183 | static inline unsigned long get_index(t_key key, struct key_vector *kv) | ||
184 | { | ||
185 | unsigned long index = key ^ kv->key; | ||
186 | |||
187 | return index >> kv->pos; | ||
188 | } | ||
189 | |||
185 | static inline struct fib_table *trie_get_table(struct trie *t) | 190 | static inline struct fib_table *trie_get_table(struct trie *t) |
186 | { | 191 | { |
187 | unsigned long *tb_data = (unsigned long *)t; | 192 | unsigned long *tb_data = (unsigned long *)t; |
@@ -374,7 +379,7 @@ static void put_child(struct key_vector *tn, unsigned long i, | |||
374 | struct key_vector *chi = get_child(tn, i); | 379 | struct key_vector *chi = get_child(tn, i); |
375 | int isfull, wasfull; | 380 | int isfull, wasfull; |
376 | 381 | ||
377 | BUG_ON(i >= tnode_child_length(tn)); | 382 | BUG_ON(i >= child_length(tn)); |
378 | 383 | ||
379 | /* update emptyChildren, overflow into fullChildren */ | 384 | /* update emptyChildren, overflow into fullChildren */ |
380 | if (n == NULL && chi != NULL) | 385 | if (n == NULL && chi != NULL) |
@@ -402,7 +407,7 @@ static void update_children(struct key_vector *tn) | |||
402 | unsigned long i; | 407 | unsigned long i; |
403 | 408 | ||
404 | /* update all of the child parent pointers */ | 409 | /* update all of the child parent pointers */ |
405 | for (i = tnode_child_length(tn); i;) { | 410 | for (i = child_length(tn); i;) { |
406 | struct key_vector *inode = get_child(tn, --i); | 411 | struct key_vector *inode = get_child(tn, --i); |
407 | 412 | ||
408 | if (!inode) | 413 | if (!inode) |
@@ -480,7 +485,7 @@ static struct key_vector __rcu **replace(struct trie *t, | |||
480 | cptr = tp ? tp->tnode : t->tnode; | 485 | cptr = tp ? tp->tnode : t->tnode; |
481 | 486 | ||
482 | /* resize children now that oldtnode is freed */ | 487 | /* resize children now that oldtnode is freed */ |
483 | for (i = tnode_child_length(tn); i;) { | 488 | for (i = child_length(tn); i;) { |
484 | struct key_vector *inode = get_child(tn, --i); | 489 | struct key_vector *inode = get_child(tn, --i); |
485 | 490 | ||
486 | /* resize child node */ | 491 | /* resize child node */ |
@@ -512,7 +517,7 @@ static struct key_vector __rcu **inflate(struct trie *t, | |||
512 | * point to existing tnodes and the links between our allocated | 517 | * point to existing tnodes and the links between our allocated |
513 | * nodes. | 518 | * nodes. |
514 | */ | 519 | */ |
515 | for (i = tnode_child_length(oldtnode), m = 1u << tn->pos; i;) { | 520 | for (i = child_length(oldtnode), m = 1u << tn->pos; i;) { |
516 | struct key_vector *inode = get_child(oldtnode, --i); | 521 | struct key_vector *inode = get_child(oldtnode, --i); |
517 | struct key_vector *node0, *node1; | 522 | struct key_vector *node0, *node1; |
518 | unsigned long j, k; | 523 | unsigned long j, k; |
@@ -562,7 +567,7 @@ static struct key_vector __rcu **inflate(struct trie *t, | |||
562 | tnode_free_append(tn, node0); | 567 | tnode_free_append(tn, node0); |
563 | 568 | ||
564 | /* populate child pointers in new nodes */ | 569 | /* populate child pointers in new nodes */ |
565 | for (k = tnode_child_length(inode), j = k / 2; j;) { | 570 | for (k = child_length(inode), j = k / 2; j;) { |
566 | put_child(node1, --j, get_child(inode, --k)); | 571 | put_child(node1, --j, get_child(inode, --k)); |
567 | put_child(node0, j, get_child(inode, j)); | 572 | put_child(node0, j, get_child(inode, j)); |
568 | put_child(node1, --j, get_child(inode, --k)); | 573 | put_child(node1, --j, get_child(inode, --k)); |
@@ -607,7 +612,7 @@ static struct key_vector __rcu **halve(struct trie *t, | |||
607 | * point to existing tnodes and the links between our allocated | 612 | * point to existing tnodes and the links between our allocated |
608 | * nodes. | 613 | * nodes. |
609 | */ | 614 | */ |
610 | for (i = tnode_child_length(oldtnode); i;) { | 615 | for (i = child_length(oldtnode); i;) { |
611 | struct key_vector *node1 = get_child(oldtnode, --i); | 616 | struct key_vector *node1 = get_child(oldtnode, --i); |
612 | struct key_vector *node0 = get_child(oldtnode, --i); | 617 | struct key_vector *node0 = get_child(oldtnode, --i); |
613 | struct key_vector *inode; | 618 | struct key_vector *inode; |
@@ -648,7 +653,7 @@ static void collapse(struct trie *t, struct key_vector *oldtnode) | |||
648 | unsigned long i; | 653 | unsigned long i; |
649 | 654 | ||
650 | /* scan the tnode looking for that one child that might still exist */ | 655 | /* scan the tnode looking for that one child that might still exist */ |
651 | for (n = NULL, i = tnode_child_length(oldtnode); !n && i;) | 656 | for (n = NULL, i = child_length(oldtnode); !n && i;) |
652 | n = get_child(oldtnode, --i); | 657 | n = get_child(oldtnode, --i); |
653 | 658 | ||
654 | /* compress one level */ | 659 | /* compress one level */ |
@@ -670,7 +675,7 @@ static unsigned char update_suffix(struct key_vector *tn) | |||
670 | * why we start with a stride of 2 since a stride of 1 would | 675 | * why we start with a stride of 2 since a stride of 1 would |
671 | * represent the nodes with suffix length equal to tn->pos | 676 | * represent the nodes with suffix length equal to tn->pos |
672 | */ | 677 | */ |
673 | for (i = 0, stride = 0x2ul ; i < tnode_child_length(tn); i += stride) { | 678 | for (i = 0, stride = 0x2ul ; i < child_length(tn); i += stride) { |
674 | struct key_vector *n = get_child(tn, i); | 679 | struct key_vector *n = get_child(tn, i); |
675 | 680 | ||
676 | if (!n || (n->slen <= slen)) | 681 | if (!n || (n->slen <= slen)) |
@@ -703,12 +708,12 @@ static unsigned char update_suffix(struct key_vector *tn) | |||
703 | * | 708 | * |
704 | * 'high' in this instance is the variable 'inflate_threshold'. It | 709 | * 'high' in this instance is the variable 'inflate_threshold'. It |
705 | * is expressed as a percentage, so we multiply it with | 710 | * is expressed as a percentage, so we multiply it with |
706 | * tnode_child_length() and instead of multiplying by 2 (since the | 711 | * child_length() and instead of multiplying by 2 (since the |
707 | * child array will be doubled by inflate()) and multiplying | 712 | * child array will be doubled by inflate()) and multiplying |
708 | * the left-hand side by 100 (to handle the percentage thing) we | 713 | * the left-hand side by 100 (to handle the percentage thing) we |
709 | * multiply the left-hand side by 50. | 714 | * multiply the left-hand side by 50. |
710 | * | 715 | * |
711 | * The left-hand side may look a bit weird: tnode_child_length(tn) | 716 | * The left-hand side may look a bit weird: child_length(tn) |
712 | * - tn->empty_children is of course the number of non-null children | 717 | * - tn->empty_children is of course the number of non-null children |
713 | * in the current node. tn->full_children is the number of "full" | 718 | * in the current node. tn->full_children is the number of "full" |
714 | * children, that is non-null tnodes with a skip value of 0. | 719 | * children, that is non-null tnodes with a skip value of 0. |
@@ -718,10 +723,10 @@ static unsigned char update_suffix(struct key_vector *tn) | |||
718 | * A clearer way to write this would be: | 723 | * A clearer way to write this would be: |
719 | * | 724 | * |
720 | * to_be_doubled = tn->full_children; | 725 | * to_be_doubled = tn->full_children; |
721 | * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - | 726 | * not_to_be_doubled = child_length(tn) - tn->empty_children - |
722 | * tn->full_children; | 727 | * tn->full_children; |
723 | * | 728 | * |
724 | * new_child_length = tnode_child_length(tn) * 2; | 729 | * new_child_length = child_length(tn) * 2; |
725 | * | 730 | * |
726 | * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / | 731 | * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / |
727 | * new_child_length; | 732 | * new_child_length; |
@@ -738,23 +743,23 @@ static unsigned char update_suffix(struct key_vector *tn) | |||
738 | * inflate_threshold * new_child_length | 743 | * inflate_threshold * new_child_length |
739 | * | 744 | * |
740 | * expand not_to_be_doubled and to_be_doubled, and shorten: | 745 | * expand not_to_be_doubled and to_be_doubled, and shorten: |
741 | * 100 * (tnode_child_length(tn) - tn->empty_children + | 746 | * 100 * (child_length(tn) - tn->empty_children + |
742 | * tn->full_children) >= inflate_threshold * new_child_length | 747 | * tn->full_children) >= inflate_threshold * new_child_length |
743 | * | 748 | * |
744 | * expand new_child_length: | 749 | * expand new_child_length: |
745 | * 100 * (tnode_child_length(tn) - tn->empty_children + | 750 | * 100 * (child_length(tn) - tn->empty_children + |
746 | * tn->full_children) >= | 751 | * tn->full_children) >= |
747 | * inflate_threshold * tnode_child_length(tn) * 2 | 752 | * inflate_threshold * child_length(tn) * 2 |
748 | * | 753 | * |
749 | * shorten again: | 754 | * shorten again: |
750 | * 50 * (tn->full_children + tnode_child_length(tn) - | 755 | * 50 * (tn->full_children + child_length(tn) - |
751 | * tn->empty_children) >= inflate_threshold * | 756 | * tn->empty_children) >= inflate_threshold * |
752 | * tnode_child_length(tn) | 757 | * child_length(tn) |
753 | * | 758 | * |
754 | */ | 759 | */ |
755 | static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) | 760 | static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) |
756 | { | 761 | { |
757 | unsigned long used = tnode_child_length(tn); | 762 | unsigned long used = child_length(tn); |
758 | unsigned long threshold = used; | 763 | unsigned long threshold = used; |
759 | 764 | ||
760 | /* Keep root node larger */ | 765 | /* Keep root node larger */ |
@@ -769,7 +774,7 @@ static inline bool should_inflate(struct key_vector *tp, struct key_vector *tn) | |||
769 | 774 | ||
770 | static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) | 775 | static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) |
771 | { | 776 | { |
772 | unsigned long used = tnode_child_length(tn); | 777 | unsigned long used = child_length(tn); |
773 | unsigned long threshold = used; | 778 | unsigned long threshold = used; |
774 | 779 | ||
775 | /* Keep root node larger */ | 780 | /* Keep root node larger */ |
@@ -783,7 +788,7 @@ static inline bool should_halve(struct key_vector *tp, struct key_vector *tn) | |||
783 | 788 | ||
784 | static inline bool should_collapse(struct key_vector *tn) | 789 | static inline bool should_collapse(struct key_vector *tn) |
785 | { | 790 | { |
786 | unsigned long used = tnode_child_length(tn); | 791 | unsigned long used = child_length(tn); |
787 | 792 | ||
788 | used -= tn->empty_children; | 793 | used -= tn->empty_children; |
789 | 794 | ||
@@ -1874,7 +1879,7 @@ static struct key_vector *fib_trie_get_next(struct fib_trie_iter *iter) | |||
1874 | pr_debug("get_next iter={node=%p index=%d depth=%d}\n", | 1879 | pr_debug("get_next iter={node=%p index=%d depth=%d}\n", |
1875 | iter->tnode, iter->index, iter->depth); | 1880 | iter->tnode, iter->index, iter->depth); |
1876 | rescan: | 1881 | rescan: |
1877 | while (cindex < tnode_child_length(tn)) { | 1882 | while (cindex < child_length(tn)) { |
1878 | struct key_vector *n = get_child_rcu(tn, cindex); | 1883 | struct key_vector *n = get_child_rcu(tn, cindex); |
1879 | 1884 | ||
1880 | if (n) { | 1885 | if (n) { |