1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:56:31 -0800
3 Subject: [PATCH] fib_trie: Move resize to after inflate/halve
5 This change consists of a cut/paste of resize to behind inflate and halve
6 so that I could remove the two function prototypes.
8 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
9 Signed-off-by: David S. Miller <davem@davemloft.net>
12 --- a/net/ipv4/fib_trie.c
13 +++ b/net/ipv4/fib_trie.c
14 @@ -149,8 +149,6 @@ struct trie {
15 static void tnode_put_child_reorg(struct tnode *tn, unsigned long i,
16 struct tnode *n, int wasfull);
17 static struct tnode *resize(struct trie *t, struct tnode *tn);
18 -static struct tnode *inflate(struct trie *t, struct tnode *tn);
19 -static struct tnode *halve(struct trie *t, struct tnode *tn);
20 /* tnodes to free after resize(); protected by RTNL */
21 static struct callback_head *tnode_free_head;
22 static size_t tnode_free_size;
23 @@ -447,161 +445,6 @@ static void put_child_root(struct tnode
24 rcu_assign_pointer(t->trie, n);
28 -static struct tnode *resize(struct trie *t, struct tnode *tn)
30 - struct tnode *old_tn, *n = NULL;
31 - int inflate_threshold_use;
32 - int halve_threshold_use;
38 - pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
39 - tn, inflate_threshold, halve_threshold);
42 - if (tn->empty_children > (tnode_child_length(tn) - 1))
46 - if (tn->empty_children == (tnode_child_length(tn) - 1))
49 - * Double as long as the resulting node has a number of
50 - * nonempty nodes that are above the threshold.
54 - * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
55 - * the Helsinki University of Technology and Matti Tikkanen of Nokia
56 - * Telecommunications, page 6:
57 - * "A node is doubled if the ratio of non-empty children to all
58 - * children in the *doubled* node is at least 'high'."
60 - * 'high' in this instance is the variable 'inflate_threshold'. It
61 - * is expressed as a percentage, so we multiply it with
62 - * tnode_child_length() and instead of multiplying by 2 (since the
63 - * child array will be doubled by inflate()) and multiplying
64 - * the left-hand side by 100 (to handle the percentage thing) we
65 - * multiply the left-hand side by 50.
67 - * The left-hand side may look a bit weird: tnode_child_length(tn)
68 - * - tn->empty_children is of course the number of non-null children
69 - * in the current node. tn->full_children is the number of "full"
70 - * children, that is non-null tnodes with a skip value of 0.
71 - * All of those will be doubled in the resulting inflated tnode, so
72 - * we just count them one extra time here.
74 - * A clearer way to write this would be:
76 - * to_be_doubled = tn->full_children;
77 - * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
78 - * tn->full_children;
80 - * new_child_length = tnode_child_length(tn) * 2;
82 - * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
84 - * if (new_fill_factor >= inflate_threshold)
86 - * ...and so on, tho it would mess up the while () loop.
89 - * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
93 - * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
94 - * inflate_threshold * new_child_length
96 - * expand not_to_be_doubled and to_be_doubled, and shorten:
97 - * 100 * (tnode_child_length(tn) - tn->empty_children +
98 - * tn->full_children) >= inflate_threshold * new_child_length
100 - * expand new_child_length:
101 - * 100 * (tnode_child_length(tn) - tn->empty_children +
102 - * tn->full_children) >=
103 - * inflate_threshold * tnode_child_length(tn) * 2
106 - * 50 * (tn->full_children + tnode_child_length(tn) -
107 - * tn->empty_children) >= inflate_threshold *
108 - * tnode_child_length(tn)
112 - /* Keep root node larger */
114 - if (!node_parent(tn)) {
115 - inflate_threshold_use = inflate_threshold_root;
116 - halve_threshold_use = halve_threshold_root;
118 - inflate_threshold_use = inflate_threshold;
119 - halve_threshold_use = halve_threshold;
122 - max_work = MAX_WORK;
123 - while ((tn->full_children > 0 && max_work-- &&
124 - 50 * (tn->full_children + tnode_child_length(tn)
125 - - tn->empty_children)
126 - >= inflate_threshold_use * tnode_child_length(tn))) {
129 - tn = inflate(t, tn);
133 -#ifdef CONFIG_IP_FIB_TRIE_STATS
134 - this_cpu_inc(t->stats->resize_node_skipped);
140 - /* Return if at least one inflate is run */
141 - if (max_work != MAX_WORK)
145 - * Halve as long as the number of empty children in this
146 - * node is above threshold.
149 - max_work = MAX_WORK;
150 - while (tn->bits > 1 && max_work-- &&
151 - 100 * (tnode_child_length(tn) - tn->empty_children) <
152 - halve_threshold_use * tnode_child_length(tn)) {
158 -#ifdef CONFIG_IP_FIB_TRIE_STATS
159 - this_cpu_inc(t->stats->resize_node_skipped);
166 - /* Only one child remains */
167 - if (tn->empty_children == (tnode_child_length(tn) - 1)) {
170 - for (i = tnode_child_length(tn); !n && i;)
171 - n = tnode_get_child(tn, --i);
173 - /* compress one level */
174 - node_set_parent(n, NULL);
175 - tnode_free_safe(tn);
182 static void tnode_clean_free(struct tnode *tn)
184 struct tnode *tofree;
185 @@ -804,6 +647,160 @@ nomem:
186 return ERR_PTR(-ENOMEM);
190 +static struct tnode *resize(struct trie *t, struct tnode *tn)
192 + struct tnode *old_tn, *n = NULL;
193 + int inflate_threshold_use;
194 + int halve_threshold_use;
200 + pr_debug("In tnode_resize %p inflate_threshold=%d threshold=%d\n",
201 + tn, inflate_threshold, halve_threshold);
204 + if (tn->empty_children > (tnode_child_length(tn) - 1))
208 + if (tn->empty_children == (tnode_child_length(tn) - 1))
211 + * Double as long as the resulting node has a number of
212 + * nonempty nodes that are above the threshold.
216 + * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
217 + * the Helsinki University of Technology and Matti Tikkanen of Nokia
218 + * Telecommunications, page 6:
219 + * "A node is doubled if the ratio of non-empty children to all
220 + * children in the *doubled* node is at least 'high'."
222 + * 'high' in this instance is the variable 'inflate_threshold'. It
223 + * is expressed as a percentage, so we multiply it with
224 + * tnode_child_length() and instead of multiplying by 2 (since the
225 + * child array will be doubled by inflate()) and multiplying
226 + * the left-hand side by 100 (to handle the percentage thing) we
227 + * multiply the left-hand side by 50.
229 + * The left-hand side may look a bit weird: tnode_child_length(tn)
230 + * - tn->empty_children is of course the number of non-null children
231 + * in the current node. tn->full_children is the number of "full"
232 + * children, that is non-null tnodes with a skip value of 0.
233 + * All of those will be doubled in the resulting inflated tnode, so
234 + * we just count them one extra time here.
236 + * A clearer way to write this would be:
238 + * to_be_doubled = tn->full_children;
239 + * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
240 + * tn->full_children;
242 + * new_child_length = tnode_child_length(tn) * 2;
244 + * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
245 + * new_child_length;
246 + * if (new_fill_factor >= inflate_threshold)
248 + * ...and so on, tho it would mess up the while () loop.
251 + * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
252 + * inflate_threshold
254 + * avoid a division:
255 + * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
256 + * inflate_threshold * new_child_length
258 + * expand not_to_be_doubled and to_be_doubled, and shorten:
259 + * 100 * (tnode_child_length(tn) - tn->empty_children +
260 + * tn->full_children) >= inflate_threshold * new_child_length
262 + * expand new_child_length:
263 + * 100 * (tnode_child_length(tn) - tn->empty_children +
264 + * tn->full_children) >=
265 + * inflate_threshold * tnode_child_length(tn) * 2
268 + * 50 * (tn->full_children + tnode_child_length(tn) -
269 + * tn->empty_children) >= inflate_threshold *
270 + * tnode_child_length(tn)
274 + /* Keep root node larger */
276 + if (!node_parent(tn)) {
277 + inflate_threshold_use = inflate_threshold_root;
278 + halve_threshold_use = halve_threshold_root;
280 + inflate_threshold_use = inflate_threshold;
281 + halve_threshold_use = halve_threshold;
284 + max_work = MAX_WORK;
285 + while ((tn->full_children > 0 && max_work-- &&
286 + 50 * (tn->full_children + tnode_child_length(tn)
287 + - tn->empty_children)
288 + >= inflate_threshold_use * tnode_child_length(tn))) {
291 + tn = inflate(t, tn);
295 +#ifdef CONFIG_IP_FIB_TRIE_STATS
296 + this_cpu_inc(t->stats->resize_node_skipped);
302 + /* Return if at least one inflate is run */
303 + if (max_work != MAX_WORK)
307 + * Halve as long as the number of empty children in this
308 + * node is above threshold.
311 + max_work = MAX_WORK;
312 + while (tn->bits > 1 && max_work-- &&
313 + 100 * (tnode_child_length(tn) - tn->empty_children) <
314 + halve_threshold_use * tnode_child_length(tn)) {
320 +#ifdef CONFIG_IP_FIB_TRIE_STATS
321 + this_cpu_inc(t->stats->resize_node_skipped);
328 + /* Only one child remains */
329 + if (tn->empty_children == (tnode_child_length(tn) - 1)) {
332 + for (i = tnode_child_length(tn); !n && i;)
333 + n = tnode_get_child(tn, --i);
335 + /* compress one level */
336 + node_set_parent(n, NULL);
337 + tnode_free_safe(tn);
343 /* readside must use rcu_read_lock currently dump routines
344 via get_fa_head and dump */