1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:56:43 -0800
3 Subject: [PATCH] fib_trie: Push assignment of child to parent down into
6 This change makes it so that the assignment of the tnode to the parent is
7 handled directly within whatever function is currently handling the node be
8 it inflate, halve, or resize. By doing this we can avoid some of the need
9 to set NULL pointers in the tree while we are resizing the subnodes.
11 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
12 Signed-off-by: David S. Miller <davem@davemloft.net>
15 --- a/net/ipv4/fib_trie.c
16 +++ b/net/ipv4/fib_trie.c
17 @@ -146,9 +146,7 @@ struct trie {
21 -static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
22 - struct tnode *n, int wasfull);
23 -static struct tnode *resize(struct trie *t, struct tnode *tn);
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;
28 @@ -396,22 +394,13 @@ static inline int tnode_full(const struc
29 return n && ((n->pos + n->bits) == tn->pos) && IS_TNODE(n);
32 -static inline void put_child(struct tnode *tn, unsigned long i,
35 - tnode_put_child_reorg(tn, i, n, -1);
39 - * Add a child at position i overwriting the old value.
40 - * Update the value of full_children and empty_children.
43 -static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
44 - struct tnode *n, int wasfull)
45 +/* Add a child at position i overwriting the old value.
46 + * Update the value of full_children and empty_children.
48 +static void put_child(struct tnode *tn, unsigned long i, struct tnode *n)
50 struct tnode *chi = rtnl_dereference(tn->child[i]);
52 + int isfull, wasfull;
54 BUG_ON(i >= tnode_child_length(tn));
56 @@ -422,10 +411,9 @@ static void tnode_put_child_reorg(struct
59 /* update fullChildren */
61 - wasfull = tnode_full(tn, chi);
63 + wasfull = tnode_full(tn, chi);
64 isfull = tnode_full(tn, n);
66 if (wasfull && !isfull)
68 else if (!wasfull && isfull)
69 @@ -458,9 +446,10 @@ static void tnode_clean_free(struct tnod
73 -static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
74 +static int inflate(struct trie *t, struct tnode *oldtnode)
76 unsigned long olen = tnode_child_length(oldtnode);
77 + struct tnode *tp = node_parent(oldtnode);
81 @@ -468,9 +457,8 @@ static struct tnode *inflate(struct trie
82 pr_debug("In inflate\n");
84 tn = tnode_new(oldtnode->key, oldtnode->pos - 1, oldtnode->bits + 1);
87 - return ERR_PTR(-ENOMEM);
91 * Preallocate and store tnodes before the actual work so we
92 @@ -564,30 +552,36 @@ static struct tnode *inflate(struct trie
93 put_child(left, j, rtnl_dereference(inode->child[j]));
94 put_child(right, j, rtnl_dereference(inode->child[j + size]));
96 - put_child(tn, 2*i, resize(t, left));
97 - put_child(tn, 2*i+1, resize(t, right));
99 + put_child(tn, 2 * i, left);
100 + put_child(tn, 2 * i + 1, right);
102 tnode_free_safe(inode);
108 + put_child_root(tp, t, tn->key, tn);
109 tnode_free_safe(oldtnode);
113 tnode_clean_free(tn);
114 - return ERR_PTR(-ENOMEM);
118 -static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
119 +static int halve(struct trie *t, struct tnode *oldtnode)
121 unsigned long olen = tnode_child_length(oldtnode);
122 + struct tnode *tp = node_parent(oldtnode);
123 struct tnode *tn, *left, *right;
126 pr_debug("In halve\n");
128 tn = tnode_new(oldtnode->key, oldtnode->pos + 1, oldtnode->bits - 1);
131 - return ERR_PTR(-ENOMEM);
135 * Preallocate and store tnodes before the actual work so we
136 @@ -606,8 +600,10 @@ static struct tnode *halve(struct trie *
138 newn = tnode_new(left->key, oldtnode->pos, 1);
143 + tnode_clean_free(tn);
147 put_child(tn, i/2, newn);
149 @@ -635,16 +631,18 @@ static struct tnode *halve(struct trie *
151 /* Two nonempty children */
152 newBinNode = tnode_get_child(tn, i/2);
153 - put_child(tn, i/2, NULL);
154 put_child(newBinNode, 0, left);
155 put_child(newBinNode, 1, right);
156 - put_child(tn, i/2, resize(t, newBinNode));
158 + put_child(tn, i / 2, newBinNode);
160 + resize(t, newBinNode);
163 + put_child_root(tp, t, tn->key, tn);
164 tnode_free_safe(oldtnode);
167 - tnode_clean_free(tn);
168 - return ERR_PTR(-ENOMEM);
173 /* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
174 @@ -704,45 +702,48 @@ nomem:
175 * tnode_child_length(tn)
178 -static bool should_inflate(const struct tnode *tn)
179 +static bool should_inflate(const struct tnode *tp, const struct tnode *tn)
181 unsigned long used = tnode_child_length(tn);
182 unsigned long threshold = used;
184 /* Keep root node larger */
185 - threshold *= node_parent(tn) ? inflate_threshold :
186 - inflate_threshold_root;
187 + threshold *= tp ? inflate_threshold : inflate_threshold_root;
188 used += tn->full_children;
189 used -= tn->empty_children;
191 return tn->pos && ((50 * used) >= threshold);
194 -static bool should_halve(const struct tnode *tn)
195 +static bool should_halve(const struct tnode *tp, const struct tnode *tn)
197 unsigned long used = tnode_child_length(tn);
198 unsigned long threshold = used;
200 /* Keep root node larger */
201 - threshold *= node_parent(tn) ? halve_threshold :
202 - halve_threshold_root;
203 + threshold *= tp ? halve_threshold : halve_threshold_root;
204 used -= tn->empty_children;
206 return (tn->bits > 1) && ((100 * used) < threshold);
210 -static struct tnode *resize(struct trie *t, struct tnode *tn)
211 +static void resize(struct trie *t, struct tnode *tn)
213 - struct tnode *old_tn, *n = NULL;
214 + struct tnode *tp = node_parent(tn), *n = NULL;
215 + struct tnode __rcu **cptr;
221 pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
222 tn, inflate_threshold, halve_threshold);
224 + /* track the tnode via the pointer from the parent instead of
225 + * doing it ourselves. This way we can let RCU fully do its
226 + * thing without us interfering
228 + cptr = tp ? &tp->child[get_index(tn->key, tp)] : &t->trie;
229 + BUG_ON(tn != rtnl_dereference(*cptr));
232 if (tn->empty_children > (tnode_child_length(tn) - 1))
234 @@ -755,39 +756,35 @@ static struct tnode *resize(struct trie
235 * nonempty nodes that are above the threshold.
238 - while (should_inflate(tn) && max_work--) {
240 - tn = inflate(t, tn);
244 + while (should_inflate(tp, tn) && max_work--) {
245 + if (inflate(t, tn)) {
246 #ifdef CONFIG_IP_FIB_TRIE_STATS
247 this_cpu_inc(t->stats->resize_node_skipped);
252 + tn = rtnl_dereference(*cptr);
255 /* Return if at least one inflate is run */
256 if (max_work != MAX_WORK)
260 /* Halve as long as the number of empty children in this
261 * node is above threshold.
264 - while (should_halve(tn) && max_work--) {
269 + while (should_halve(tp, tn) && max_work--) {
270 + if (halve(t, tn)) {
271 #ifdef CONFIG_IP_FIB_TRIE_STATS
272 this_cpu_inc(t->stats->resize_node_skipped);
278 + tn = rtnl_dereference(*cptr);
281 /* Only one child remains */
282 if (tn->empty_children == (tnode_child_length(tn) - 1)) {
283 @@ -797,11 +794,12 @@ one_child:
284 n = tnode_get_child(tn, --i);
286 /* compress one level */
287 - node_set_parent(n, NULL);
288 + put_child_root(tp, t, tn->key, n);
289 + node_set_parent(n, tp);
291 + /* drop dead node */
298 /* readside must use rcu_read_lock currently dump routines
299 @@ -882,34 +880,19 @@ static struct tnode *fib_find_node(struc
301 static void trie_rebalance(struct trie *t, struct tnode *tn)
309 - while (tn != NULL && (tp = node_parent(tn)) != NULL) {
310 - cindex = get_index(key, tp);
311 - wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
312 - tn = resize(t, tn);
314 - tnode_put_child_reorg(tp, cindex, tn, wasfull);
316 - tp = node_parent(tn);
318 - rcu_assign_pointer(t->trie, tn);
319 + while ((tp = node_parent(tn)) != NULL) {
328 /* Handle last (top) tnode */
330 - tn = resize(t, tn);
333 - rcu_assign_pointer(t->trie, tn);