1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:56:37 -0800
3 Subject: [PATCH] fib_trie: Add functions should_inflate and should_halve
5 This change pulls the logic for if we should inflate/halve the nodes out
6 into separate functions. It also addresses what I believe is a bug where 1
7 full node is all that is needed to keep a node from ever being halved.
9 Simple script to reproduce the issue:
10 modprobe dummy; ifconfig dummy0 up
11 for i in `seq 0 255`; do ifconfig dummy0:$i 10.0.${i}.1/24 up; done
12 ifconfig dummy0:256 10.0.255.33/16 up
13 for i in `seq 0 254`; do ifconfig dummy0:$i down; done
15 Results from /proc/net/fib_triestat
39 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
40 Signed-off-by: David S. Miller <davem@davemloft.net>
43 --- a/net/ipv4/fib_trie.c
44 +++ b/net/ipv4/fib_trie.c
45 @@ -647,12 +647,94 @@ nomem:
46 return ERR_PTR(-ENOMEM);
49 +/* From "Implementing a dynamic compressed trie" by Stefan Nilsson of
50 + * the Helsinki University of Technology and Matti Tikkanen of Nokia
51 + * Telecommunications, page 6:
52 + * "A node is doubled if the ratio of non-empty children to all
53 + * children in the *doubled* node is at least 'high'."
55 + * 'high' in this instance is the variable 'inflate_threshold'. It
56 + * is expressed as a percentage, so we multiply it with
57 + * tnode_child_length() and instead of multiplying by 2 (since the
58 + * child array will be doubled by inflate()) and multiplying
59 + * the left-hand side by 100 (to handle the percentage thing) we
60 + * multiply the left-hand side by 50.
62 + * The left-hand side may look a bit weird: tnode_child_length(tn)
63 + * - tn->empty_children is of course the number of non-null children
64 + * in the current node. tn->full_children is the number of "full"
65 + * children, that is non-null tnodes with a skip value of 0.
66 + * All of those will be doubled in the resulting inflated tnode, so
67 + * we just count them one extra time here.
69 + * A clearer way to write this would be:
71 + * to_be_doubled = tn->full_children;
72 + * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
73 + * tn->full_children;
75 + * new_child_length = tnode_child_length(tn) * 2;
77 + * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
79 + * if (new_fill_factor >= inflate_threshold)
81 + * ...and so on, tho it would mess up the while () loop.
84 + * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
88 + * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
89 + * inflate_threshold * new_child_length
91 + * expand not_to_be_doubled and to_be_doubled, and shorten:
92 + * 100 * (tnode_child_length(tn) - tn->empty_children +
93 + * tn->full_children) >= inflate_threshold * new_child_length
95 + * expand new_child_length:
96 + * 100 * (tnode_child_length(tn) - tn->empty_children +
97 + * tn->full_children) >=
98 + * inflate_threshold * tnode_child_length(tn) * 2
101 + * 50 * (tn->full_children + tnode_child_length(tn) -
102 + * tn->empty_children) >= inflate_threshold *
103 + * tnode_child_length(tn)
106 +static bool should_inflate(const struct tnode *tn)
108 + unsigned long used = tnode_child_length(tn);
109 + unsigned long threshold = used;
111 + /* Keep root node larger */
112 + threshold *= node_parent(tn) ? inflate_threshold :
113 + inflate_threshold_root;
114 + used += tn->full_children;
115 + used -= tn->empty_children;
117 + return tn->pos && ((50 * used) >= threshold);
120 +static bool should_halve(const struct tnode *tn)
122 + unsigned long used = tnode_child_length(tn);
123 + unsigned long threshold = used;
125 + /* Keep root node larger */
126 + threshold *= node_parent(tn) ? halve_threshold :
127 + halve_threshold_root;
128 + used -= tn->empty_children;
130 + return (tn->bits > 1) && ((100 * used) < threshold);
134 static struct tnode *resize(struct trie *t, struct tnode *tn)
136 struct tnode *old_tn, *n = NULL;
137 - int inflate_threshold_use;
138 - int halve_threshold_use;
142 @@ -668,86 +750,12 @@ static struct tnode *resize(struct trie
144 if (tn->empty_children == (tnode_child_length(tn) - 1))
147 - * Double as long as the resulting node has a number of
148 - * nonempty nodes that are above the threshold.
152 - * From "Implementing a dynamic compressed trie" by Stefan Nilsson of
153 - * the Helsinki University of Technology and Matti Tikkanen of Nokia
154 - * Telecommunications, page 6:
155 - * "A node is doubled if the ratio of non-empty children to all
156 - * children in the *doubled* node is at least 'high'."
158 - * 'high' in this instance is the variable 'inflate_threshold'. It
159 - * is expressed as a percentage, so we multiply it with
160 - * tnode_child_length() and instead of multiplying by 2 (since the
161 - * child array will be doubled by inflate()) and multiplying
162 - * the left-hand side by 100 (to handle the percentage thing) we
163 - * multiply the left-hand side by 50.
165 - * The left-hand side may look a bit weird: tnode_child_length(tn)
166 - * - tn->empty_children is of course the number of non-null children
167 - * in the current node. tn->full_children is the number of "full"
168 - * children, that is non-null tnodes with a skip value of 0.
169 - * All of those will be doubled in the resulting inflated tnode, so
170 - * we just count them one extra time here.
172 - * A clearer way to write this would be:
174 - * to_be_doubled = tn->full_children;
175 - * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children -
176 - * tn->full_children;
178 - * new_child_length = tnode_child_length(tn) * 2;
180 - * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) /
181 - * new_child_length;
182 - * if (new_fill_factor >= inflate_threshold)
184 - * ...and so on, tho it would mess up the while () loop.
187 - * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >=
188 - * inflate_threshold
190 - * avoid a division:
191 - * 100 * (not_to_be_doubled + 2*to_be_doubled) >=
192 - * inflate_threshold * new_child_length
194 - * expand not_to_be_doubled and to_be_doubled, and shorten:
195 - * 100 * (tnode_child_length(tn) - tn->empty_children +
196 - * tn->full_children) >= inflate_threshold * new_child_length
198 - * expand new_child_length:
199 - * 100 * (tnode_child_length(tn) - tn->empty_children +
200 - * tn->full_children) >=
201 - * inflate_threshold * tnode_child_length(tn) * 2
204 - * 50 * (tn->full_children + tnode_child_length(tn) -
205 - * tn->empty_children) >= inflate_threshold *
206 - * tnode_child_length(tn)
208 + /* Double as long as the resulting node has a number of
209 + * nonempty nodes that are above the threshold.
212 - /* Keep root node larger */
214 - if (!node_parent(tn)) {
215 - inflate_threshold_use = inflate_threshold_root;
216 - halve_threshold_use = halve_threshold_root;
218 - inflate_threshold_use = inflate_threshold;
219 - halve_threshold_use = halve_threshold;
223 - while ((tn->full_children > 0 && max_work-- &&
224 - 50 * (tn->full_children + tnode_child_length(tn)
225 - - tn->empty_children)
226 - >= inflate_threshold_use * tnode_child_length(tn))) {
228 + while (should_inflate(tn) && max_work--) {
232 @@ -764,16 +772,11 @@ static struct tnode *resize(struct trie
233 if (max_work != MAX_WORK)
237 - * Halve as long as the number of empty children in this
238 + /* Halve as long as the number of empty children in this
239 * node is above threshold.
243 - while (tn->bits > 1 && max_work-- &&
244 - 100 * (tnode_child_length(tn) - tn->empty_children) <
245 - halve_threshold_use * tnode_child_length(tn)) {
247 + while (should_halve(tn) && max_work--) {