1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:55:41 -0800
3 Subject: [PATCH] fib_trie: Merge tnode_free and leaf_free into node_free
5 Both the leaf and the tnode had an rcu_head in them, but they had them in
6 slightly different places. Since we now have them in the same spot and
7 know that any node with bits == 0 is a leaf and the rest are either vmalloc
8 or kmalloc tnodes depending on the value of bits it makes it easy to combine
9 the functions and reduce overhead.
11 In addition I have taken advantage of the rcu_head pointer to go ahead and
12 put together a simple linked list instead of using the tnode pointer as
13 this way we can merge either type of structure for freeing.
15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
16 Signed-off-by: David S. Miller <davem@davemloft.net>
19 --- a/net/ipv4/fib_trie.c
20 +++ b/net/ipv4/fib_trie.c
21 @@ -95,15 +95,17 @@ struct tnode {
22 unsigned char bits; /* 2log(KEYLENGTH) bits needed */
23 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
24 struct tnode __rcu *parent;
26 - struct rcu_head rcu;
27 - struct tnode *tnode_free;
29 + struct rcu_head rcu;
30 + /* everything above this comment must be the same as rt_trie_node */
31 unsigned int full_children; /* KEYLENGTH bits needed */
32 unsigned int empty_children; /* KEYLENGTH bits needed */
33 struct rt_trie_node __rcu *child[0];
36 +/* This struct represents the shared bits between tnode and leaf. If any
37 + * ordering is changed here is must also be updated in tnode and leaf as
43 @@ -118,6 +120,7 @@ struct leaf {
45 struct tnode __rcu *parent;
47 + /* everything above this comment must be the same as rt_trie_node */
48 struct hlist_head list;
51 @@ -163,7 +166,7 @@ static struct rt_trie_node *resize(struc
52 static struct tnode *inflate(struct trie *t, struct tnode *tn);
53 static struct tnode *halve(struct trie *t, struct tnode *tn);
54 /* tnodes to free after resize(); protected by RTNL */
55 -static struct tnode *tnode_free_head;
56 +static struct callback_head *tnode_free_head;
57 static size_t tnode_free_size;
60 @@ -336,17 +339,23 @@ static inline void alias_free_mem_rcu(st
61 call_rcu(&fa->rcu, __alias_free_mem);
64 -static void __leaf_free_rcu(struct rcu_head *head)
66 - struct leaf *l = container_of(head, struct leaf, rcu);
67 - kmem_cache_free(trie_leaf_kmem, l);
69 +#define TNODE_KMALLOC_MAX \
70 + ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct rt_trie_node *))
72 -static inline void free_leaf(struct leaf *l)
73 +static void __node_free_rcu(struct rcu_head *head)
75 - call_rcu(&l->rcu, __leaf_free_rcu);
76 + struct rt_trie_node *n = container_of(head, struct rt_trie_node, rcu);
79 + kmem_cache_free(trie_leaf_kmem, n);
80 + else if (n->bits <= TNODE_KMALLOC_MAX)
86 +#define node_free(n) call_rcu(&n->rcu, __node_free_rcu)
88 static inline void free_leaf_info(struct leaf_info *leaf)
91 @@ -360,43 +369,24 @@ static struct tnode *tnode_alloc(size_t
95 -static void __tnode_free_rcu(struct rcu_head *head)
97 - struct tnode *tn = container_of(head, struct tnode, rcu);
98 - size_t size = sizeof(struct tnode) +
99 - (sizeof(struct rt_trie_node *) << tn->bits);
101 - if (size <= PAGE_SIZE)
107 -static inline void tnode_free(struct tnode *tn)
110 - free_leaf((struct leaf *) tn);
112 - call_rcu(&tn->rcu, __tnode_free_rcu);
115 static void tnode_free_safe(struct tnode *tn)
118 - tn->tnode_free = tnode_free_head;
119 - tnode_free_head = tn;
120 - tnode_free_size += sizeof(struct tnode) +
121 - (sizeof(struct rt_trie_node *) << tn->bits);
122 + tn->rcu.next = tnode_free_head;
123 + tnode_free_head = &tn->rcu;
126 static void tnode_free_flush(void)
129 + struct callback_head *head;
131 + while ((head = tnode_free_head)) {
132 + struct tnode *tn = container_of(head, struct tnode, rcu);
134 + tnode_free_head = head->next;
135 + tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
137 - while ((tn = tnode_free_head)) {
138 - tnode_free_head = tn->tnode_free;
139 - tn->tnode_free = NULL;
144 if (tnode_free_size >= PAGE_SIZE * sync_pages) {
145 @@ -437,7 +427,7 @@ static struct leaf_info *leaf_info_new(i
147 static struct tnode *tnode_new(t_key key, int pos, int bits)
149 - size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
150 + size_t sz = offsetof(struct tnode, child[1 << bits]);
151 struct tnode *tn = tnode_alloc(sz);
152 unsigned int shift = pos + bits;
154 @@ -666,15 +656,15 @@ no_children:
156 static void tnode_clean_free(struct tnode *tn)
158 + struct rt_trie_node *tofree;
160 - struct tnode *tofree;
162 for (i = 0; i < tnode_child_length(tn); i++) {
163 - tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
164 + tofree = rtnl_dereference(tn->child[i]);
166 - tnode_free(tofree);
173 static struct tnode *inflate(struct trie *t, struct tnode *tn)
174 @@ -717,7 +707,7 @@ static struct tnode *inflate(struct trie
183 @@ -1068,7 +1058,7 @@ static struct list_head *fib_insert_node
184 li = leaf_info_new(plen);
192 @@ -1100,7 +1090,7 @@ static struct list_head *fib_insert_node
201 @@ -1580,7 +1570,7 @@ static void trie_leaf_remove(struct trie
203 RCU_INIT_POINTER(t->trie, NULL);