lists.openwall.net | lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC | |
Open Source and information security mailing list archives
| ||
|
Date: Tue, 24 Feb 2015 12:50:36 -0800 From: Alexander Duyck <alexander.h.duyck@...hat.com> To: netdev@...r.kernel.org Subject: [RFC PATCH 24/29] fib_trie: Update tnode_new to drop use of put_child_root This change makes it so that the tnode_new function will now insert itself into the parent. This is to enable the eventual moving of fields from the key_vector of the local node into the parent. Signed-off-by: Alexander Duyck <alexander.h.duyck@...hat.com> --- net/ipv4/fib_trie.c | 47 +++++++++++++++++++++++++++++++++++------------ 1 file changed, 35 insertions(+), 12 deletions(-) diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c index 65ea194..e91233b 100644 --- a/net/ipv4/fib_trie.c +++ b/net/ipv4/fib_trie.c @@ -437,40 +437,63 @@ static void leaf_init(struct key_vector *tn, t_key key, struct key_vector *l) rcu_assign_pointer(tn->tnode, l); } -static struct key_vector *tnode_new(struct key_vector *pn, t_key key, +static struct key_vector *tnode_new(struct key_vector *tn, t_key key, int pos, int bits) { size_t sz = TNODE_SIZE(1ul << bits); struct tnode *tnode = tnode_alloc(sz); - struct key_vector *tn = tnode->kv; unsigned int shift = pos + bits; + unsigned long i; /* verify bits and pos their msb bits clear and values are valid */ BUG_ON(!bits || (shift > KEYLENGTH)); - pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0), - sizeof(struct key_vector *) << bits); + pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0), sz - TNODE_SIZE(0)); if (!tnode) return NULL; + /* link tnode to parent */ + NODE_INIT_PARENT(tnode->kv, tn); + + /* update parent node stats */ + if (!IS_TRIE(tn)) { + unsigned long idx = get_index(key, tn); + struct key_vector *n = get_child(tn + idx); + + BUG_ON(idx >= child_length(tn)); + + if (!n) + empty_child_dec(tn); + else if (tnode_full(tn, n)) + tn_info(tn)->full_children--; + if ((pos + bits) == tn->pos) + tn_info(tn)->full_children++; + + /* update offset to correct key_vector for update */ + tn += idx; + } + /* populate tn_info section */ + key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; if (bits == KEYLENGTH) tnode->full_children = 1; else tnode->empty_children = 1ul << bits; + /* populate keys as though we are full of leaves */ + for (i = (1ul << bits); i--;) + tnode->kv[i].key = key + (i << pos); + /* populate key vector */ - tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0; - tn->pos = pos; - tn->bits = bits; - tn->slen = pos; + tnode->kv[0].pos = pos; + tnode->kv[0].bits = bits; + tnode->kv[0].slen = pos; /* link parent to node */ - NODE_INIT_PARENT(tn, pn); - put_child_root(pn, tn->key, tn); + rcu_assign_pointer(tn->tnode, tnode->kv); - return tn; + return tnode->kv; } static struct key_vector *tnode_clone(struct tnode *oldtnode) @@ -2256,7 +2279,7 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v) fib_table_print(seq, iter->tb); if (IS_TNODE(n)) { - __be32 prf = htonl(n->key); + __be32 prf = htonl((n->key >> n->pos) << n->pos); seq_indent(seq, iter->depth-1); seq_printf(seq, " +-- %pI4/%zu %u %u %u\n", -- To unsubscribe from this list: send the line "unsubscribe netdev" in the body of a message to majordomo@...r.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html
Powered by blists - more mailing lists