diff options
Diffstat (limited to 'net/ipv4')
| -rw-r--r-- | net/ipv4/fib_trie.c | 100 |
1 files changed, 65 insertions, 35 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 80892f565030..f874e1811eab 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -83,7 +83,8 @@ #define MAX_STAT_DEPTH 32 -#define KEYLENGTH (8*sizeof(t_key)) +#define KEYLENGTH (8*sizeof(t_key)) +#define KEY_MAX ((t_key)~0) typedef unsigned int t_key; @@ -102,8 +103,8 @@ struct tnode { union { /* The fields in this struct are valid if bits > 0 (TNODE) */ struct { - unsigned int full_children; /* KEYLENGTH bits needed */ - unsigned int empty_children; /* KEYLENGTH bits needed */ + t_key empty_children; /* KEYLENGTH bits needed */ + t_key full_children; /* KEYLENGTH bits needed */ struct tnode __rcu *child[0]; }; /* This list pointer if valid if bits == 0 (LEAF) */ @@ -302,6 +303,16 @@ static struct tnode *tnode_alloc(size_t size) return vzalloc(size); } +static inline void empty_child_inc(struct tnode *n) +{ + ++n->empty_children ? : ++n->full_children; +} + +static inline void empty_child_dec(struct tnode *n) +{ + n->empty_children-- ? : n->full_children--; +} + static struct tnode *leaf_new(t_key key) { struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL); @@ -335,7 +346,7 @@ static struct leaf_info *leaf_info_new(int plen) static struct tnode *tnode_new(t_key key, int pos, int bits) { - size_t sz = offsetof(struct tnode, child[1 << bits]); + size_t sz = offsetof(struct tnode, child[1ul << bits]); struct tnode *tn = tnode_alloc(sz); unsigned int shift = pos + bits; @@ -348,8 +359,10 @@ static struct tnode *tnode_new(t_key key, int pos, int bits) tn->pos = pos; tn->bits = bits; tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; - tn->full_children = 0; - tn->empty_children = 1<<bits; + if (bits == KEYLENGTH) + tn->full_children = 1; + else + tn->empty_children = 1ul << bits; } pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode), @@ -375,11 +388,11 @@ static void put_child(struct tnode *tn, unsigned long i, struct tnode *n) BUG_ON(i >= tnode_child_length(tn)); - /* update emptyChildren */ + /* update emptyChildren, overflow into fullChildren */ if (n == NULL && chi != NULL) - tn->empty_children++; - else if (n != NULL && chi == NULL) - tn->empty_children--; + empty_child_inc(tn); + if (n != NULL && chi == NULL) + empty_child_dec(tn); /* update fullChildren */ wasfull = tnode_full(tn, chi); @@ -630,6 +643,24 @@ static int halve(struct trie *t, struct tnode *oldtnode) return 0; } +static void collapse(struct trie *t, struct tnode *oldtnode) +{ + struct tnode *n, *tp; + unsigned long i; + + /* scan the tnode looking for that one child that might still exist */ + for (n = NULL, i = tnode_child_length(oldtnode); !n && i;) + n = tnode_get_child(oldtnode, --i); + + /* compress one level */ + tp = node_parent(oldtnode); + put_child_root(tp, t, oldtnode->key, n); + node_set_parent(n, tp); + + /* drop dead node */ + node_free(oldtnode); +} + static unsigned char update_suffix(struct tnode *tn) { unsigned char slen = tn->pos; @@ -729,10 +760,12 @@ static bool should_inflate(const struct tnode *tp, const struct tnode *tn) /* Keep root node larger */ threshold *= tp ? inflate_threshold : inflate_threshold_root; - used += tn->full_children; used -= tn->empty_children; + used += tn->full_children; - return tn->pos && ((50 * used) >= threshold); + /* if bits == KEYLENGTH then pos = 0, and will fail below */ + + return (used > 1) && tn->pos && ((50 * used) >= threshold); } static bool should_halve(const struct tnode *tp, const struct tnode *tn) @@ -744,13 +777,29 @@ static bool should_halve(const struct tnode *tp, const struct tnode *tn) threshold *= tp ? halve_threshold : halve_threshold_root; used -= tn->empty_children; - return (tn->bits > 1) && ((100 * used) < threshold); + /* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */ + + return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold); +} + +static bool should_collapse(const struct tnode *tn) +{ + unsigned long used = tnode_child_length(tn); + + used -= tn->empty_children; + + /* account for bits == KEYLENGTH case */ + if ((tn->bits == KEYLENGTH) && tn->full_children) + used -= KEY_MAX; + + /* One child or none, time to drop us from the trie */ + return used < 2; } #define MAX_WORK 10 static void resize(struct trie *t, struct tnode *tn) { - struct tnode *tp = node_parent(tn), *n = NULL; + struct tnode *tp = node_parent(tn); struct tnode __rcu **cptr; int max_work = MAX_WORK; @@ -764,14 +813,6 @@ static void resize(struct trie *t, struct tnode *tn) cptr = tp ? &tp->child[get_index(tn->key, tp)] : &t->trie; BUG_ON(tn != rtnl_dereference(*cptr)); - /* No children */ - if (tn->empty_children > (tnode_child_length(tn) - 1)) - goto no_children; - - /* One child */ - if (tn->empty_children == (tnode_child_length(tn) - 1)) - goto one_child; - /* Double as long as the resulting node has a number of * nonempty nodes that are above the threshold. */ @@ -807,19 +848,8 @@ static void resize(struct trie *t, struct tnode *tn) } /* Only one child remains */ - if (tn->empty_children == (tnode_child_length(tn) - 1)) { - unsigned long i; -one_child: - for (i = tnode_child_length(tn); !n && i;) - n = tnode_get_child(tn, --i); -no_children: - /* compress one level */ - put_child_root(tp, t, tn->key, n); - node_set_parent(n, tp); - - /* drop dead node */ - tnode_free_init(tn); - tnode_free(tn); + if (should_collapse(tn)) { + collapse(t, tn); return; } |
