| 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:49:35 -0800
From: Alexander Duyck <alexander.h.duyck@...hat.com>
To: netdev@...r.kernel.org
Subject: [RFC PATCH 15/29] fib_trie: Add tnode struct as a container for
fields not needed in key_vector
This change pulls the fields not explicitly needed in the key_vector and
placed them in the new tnode structure. By doing this we will eventually
be able to reduce the key_vector down to 16 bytes on 64 bit systems, and
12 bytes on 32 bit systems.
Signed-off-by: Alexander Duyck <alexander.h.duyck@...hat.com>
---
net/ipv4/fib_trie.c | 87 +++++++++++++++++++++++++++------------------------
1 file changed, 46 insertions(+), 41 deletions(-)
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 711f8f2..b1e9141 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -108,6 +108,10 @@ struct key_vector {
};
};
+struct tnode {
+ struct key_vector kv[1];
+};
+
#ifdef CONFIG_IP_FIB_TRIE_STATS
struct trie_use_stats {
unsigned int gets;
@@ -264,9 +268,9 @@ static inline void alias_free_mem_rcu(struct fib_alias *fa)
call_rcu(&fa->rcu, __alias_free_mem);
}
-#define TNODE_SIZE offsetof(struct key_vector, tnode[0])
+#define TNODE_SIZE(n) offsetof(struct tnode, kv[0].tnode[n])
#define TNODE_KMALLOC_MAX \
- ilog2((PAGE_SIZE - TNODE_SIZE) / sizeof(struct key_vector *))
+ ilog2((PAGE_SIZE - TNODE_SIZE(0)) / sizeof(struct key_vector *))
static void __node_free_rcu(struct rcu_head *head)
{
@@ -282,7 +286,7 @@ static void __node_free_rcu(struct rcu_head *head)
#define node_free(n) call_rcu(&n->rcu, __node_free_rcu)
-static struct key_vector *tnode_alloc(size_t size)
+static struct tnode *tnode_alloc(size_t size)
{
if (size <= PAGE_SIZE)
return kzalloc(size, GFP_KERNEL);
@@ -302,49 +306,51 @@ static inline void empty_child_dec(struct key_vector *n)
static struct key_vector *leaf_new(t_key key, struct fib_alias *fa)
{
- struct key_vector *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
- if (l) {
- l->parent = NULL;
- /* set key and pos to reflect full key value
- * any trailing zeros in the key should be ignored
- * as the nodes are searched
- */
- l->key = key;
- l->slen = fa->fa_slen;
- l->pos = 0;
- /* set bits to 0 indicating we are not a tnode */
- l->bits = 0;
-
- /* link leaf to fib alias */
- INIT_HLIST_HEAD(&l->leaf);
- hlist_add_head(&fa->fa_list, &l->leaf);
- }
+ struct tnode *kv = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
+ struct key_vector *l = kv->kv;
+
+ if (!kv)
+ return NULL;
+
+ /* initialize key vector */
+ l->key = key;
+ l->pos = 0;
+ l->bits = 0;
+ l->slen = fa->fa_slen;
+
+ /* link leaf to fib alias */
+ INIT_HLIST_HEAD(&l->leaf);
+ hlist_add_head(&fa->fa_list, &l->leaf);
+
return l;
}
static struct key_vector *tnode_new(t_key key, int pos, int bits)
{
- size_t sz = offsetof(struct key_vector, tnode[1ul << bits]);
- struct key_vector *tn = tnode_alloc(sz);
+ size_t sz = TNODE_SIZE(1ul << bits);
+ struct tnode *tnode = tnode_alloc(sz);
unsigned int shift = pos + bits;
+ struct key_vector *tn = tnode->kv;
/* verify bits and pos their msb bits clear and values are valid */
BUG_ON(!bits || (shift > KEYLENGTH));
- if (tn) {
- tn->parent = NULL;
- tn->slen = pos;
- tn->pos = pos;
- tn->bits = bits;
- tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
- if (bits == KEYLENGTH)
- tn->full_children = 1;
- else
- tn->empty_children = 1ul << bits;
- }
-
- pr_debug("AT %p s=%zu %zu\n", tn, TNODE_SIZE,
+ pr_debug("AT %p s=%zu %zu\n", tnode, TNODE_SIZE(0),
sizeof(struct key_vector *) << bits);
+
+ if (!tnode)
+ return NULL;
+
+ if (bits == KEYLENGTH)
+ tn->full_children = 1;
+ else
+ tn->empty_children = 1ul << bits;
+
+ tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
+ tn->pos = pos;
+ tn->bits = bits;
+ tn->slen = pos;
+
return tn;
}
@@ -437,8 +443,7 @@ static void tnode_free(struct key_vector *tn)
while (head) {
head = head->next;
- tnode_free_size += offsetof(struct key_vector,
- tnode[1 << tn->bits]);
+ tnode_free_size += TNODE_SIZE(1 << tn->bits);
node_free(tn);
tn = container_of(head, struct key_vector, rcu);
@@ -1724,7 +1729,7 @@ void __init fib_trie_init(void)
0, SLAB_PANIC, NULL);
trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
- sizeof(struct key_vector),
+ sizeof(struct tnode),
0, SLAB_PANIC, NULL);
}
@@ -1882,13 +1887,13 @@ static void trie_show_stats(struct seq_file *seq, struct trie_stat *stat)
seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
- bytes = sizeof(struct key_vector) * stat->leaves;
+ bytes = TNODE_SIZE(1) * stat->leaves;
seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
bytes += sizeof(struct fib_alias) * stat->prefixes;
seq_printf(seq, "\tInternal nodes: %u\n\t", stat->tnodes);
- bytes += TNODE_SIZE * stat->tnodes;
+ bytes += TNODE_SIZE(0) * stat->tnodes;
max = MAX_STAT_DEPTH;
while (max > 0 && stat->nodesizes[max-1] == 0)
@@ -1957,7 +1962,7 @@ static int fib_triestat_seq_show(struct seq_file *seq, void *v)
seq_printf(seq,
"Basic info: size of leaf:"
" %Zd bytes, size of tnode: %Zd bytes.\n",
- sizeof(struct key_vector), TNODE_SIZE);
+ TNODE_SIZE(1), TNODE_SIZE(0));
for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
struct hlist_head *head = &net->ipv4.fib_table_hash[h];
--
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