1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:56:49 -0800
3 Subject: [PATCH] fib_trie: Push tnode flushing down to inflate/halve
5 This change pushes the tnode freeing down into the inflate and halve
6 functions. It makes more sense here as we have a better grasp of what is
7 going on and when a given cluster of nodes is ready to be freed.
9 I believe this may address a bug in the freeing logic as well. For some
10 reason if the freelist got to a certain size we would call
11 synchronize_rcu(). I'm assuming that what they meant to do is call
12 synchronize_rcu() after they had handed off that much memory via
13 call_rcu(). As such that is what I have updated the behavior to be.
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 @@ -147,8 +147,6 @@ struct trie {
24 static void resize(struct trie *t, struct tnode *tn);
25 -/* tnodes to free after resize(); protected by RTNL */
26 -static struct callback_head *tnode_free_head;
27 static size_t tnode_free_size;
30 @@ -307,32 +305,6 @@ static struct tnode *tnode_alloc(size_t
34 -static void tnode_free_safe(struct tnode *tn)
36 - BUG_ON(IS_LEAF(tn));
37 - tn->rcu.next = tnode_free_head;
38 - tnode_free_head = &tn->rcu;
41 -static void tnode_free_flush(void)
43 - struct callback_head *head;
45 - while ((head = tnode_free_head)) {
46 - struct tnode *tn = container_of(head, struct tnode, rcu);
48 - tnode_free_head = head->next;
49 - tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
54 - if (tnode_free_size >= PAGE_SIZE * sync_pages) {
55 - tnode_free_size = 0;
60 static struct tnode *leaf_new(t_key key)
62 struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
63 @@ -433,17 +405,33 @@ static void put_child_root(struct tnode
64 rcu_assign_pointer(t->trie, n);
67 -static void tnode_clean_free(struct tnode *tn)
68 +static inline void tnode_free_init(struct tnode *tn)
70 - struct tnode *tofree;
72 + tn->rcu.next = NULL;
75 +static inline void tnode_free_append(struct tnode *tn, struct tnode *n)
77 + n->rcu.next = tn->rcu.next;
78 + tn->rcu.next = &n->rcu;
81 - for (i = 0; i < tnode_child_length(tn); i++) {
82 - tofree = tnode_get_child(tn, i);
85 +static void tnode_free(struct tnode *tn)
87 + struct callback_head *head = &tn->rcu;
91 + tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
94 + tn = container_of(head, struct tnode, rcu);
97 + if (tnode_free_size >= PAGE_SIZE * sync_pages) {
98 + tnode_free_size = 0;
104 static int inflate(struct trie *t, struct tnode *oldtnode)
105 @@ -476,20 +464,23 @@ static int inflate(struct trie *t, struc
109 + tnode_free_append(tn, left);
111 right = tnode_new(inode->key | m, inode->pos,
119 + tnode_free_append(tn, right);
121 put_child(tn, 2*i, left);
122 put_child(tn, 2*i+1, right);
126 + /* prepare oldtnode to be freed */
127 + tnode_free_init(oldtnode);
129 for (i = 0; i < olen; i++) {
130 struct tnode *inode = tnode_get_child(oldtnode, i);
131 struct tnode *left, *right;
132 @@ -505,12 +496,13 @@ static int inflate(struct trie *t, struc
136 + /* drop the node in the old tnode free list */
137 + tnode_free_append(oldtnode, inode);
139 /* An internal node with two children */
140 if (inode->bits == 1) {
141 put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
142 put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
144 - tnode_free_safe(inode);
148 @@ -556,17 +548,19 @@ static int inflate(struct trie *t, struc
149 put_child(tn, 2 * i, left);
150 put_child(tn, 2 * i + 1, right);
152 - tnode_free_safe(inode);
154 + /* resize child nodes */
159 put_child_root(tp, t, tn->key, tn);
160 - tnode_free_safe(oldtnode);
162 + /* we completed without error, prepare to free old node */
163 + tnode_free(oldtnode);
166 - tnode_clean_free(tn);
167 + /* all pointers should be clean so we are done */
172 @@ -599,17 +593,20 @@ static int halve(struct trie *t, struct
175 newn = tnode_new(left->key, oldtnode->pos, 1);
178 - tnode_clean_free(tn);
182 + tnode_free_append(tn, newn);
184 put_child(tn, i/2, newn);
189 + /* prepare oldtnode to be freed */
190 + tnode_free_init(oldtnode);
192 for (i = 0; i < olen; i += 2) {
193 struct tnode *newBinNode;
195 @@ -636,11 +633,14 @@ static int halve(struct trie *t, struct
197 put_child(tn, i / 2, newBinNode);
199 + /* resize child node */
200 resize(t, newBinNode);
203 put_child_root(tp, t, tn->key, tn);
204 - tnode_free_safe(oldtnode);
206 + /* all pointers should be clean so we are done */
207 + tnode_free(oldtnode);
211 @@ -798,7 +798,8 @@ no_children:
212 node_set_parent(n, tp);
215 - tnode_free_safe(tn);
216 + tnode_free_init(tn);
221 @@ -884,16 +885,12 @@ static void trie_rebalance(struct trie *
223 while ((tp = node_parent(tn)) != NULL) {
226 - tnode_free_flush();
230 /* Handle last (top) tnode */
234 - tnode_free_flush();
237 /* only used from updater-side */