OpenWrt – Blame information for rev 1
?pathlinks?
Rev | Author | Line No. | Line |
---|---|---|---|
1 | office | 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 |
||
4 | |||
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. |
||
8 | |||
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 |
||
14 | |||
15 | Results from /proc/net/fib_triestat |
||
16 | Before: |
||
17 | Local: |
||
18 | Aver depth: 3.00 |
||
19 | Max depth: 4 |
||
20 | Leaves: 17 |
||
21 | Prefixes: 18 |
||
22 | Internal nodes: 11 |
||
23 | 1: 8 2: 2 10: 1 |
||
24 | Pointers: 1048 |
||
25 | Null ptrs: 1021 |
||
26 | Total size: 11 kB |
||
27 | After: |
||
28 | Local: |
||
29 | Aver depth: 3.41 |
||
30 | Max depth: 5 |
||
31 | Leaves: 17 |
||
32 | Prefixes: 18 |
||
33 | Internal nodes: 12 |
||
34 | 1: 8 2: 3 3: 1 |
||
35 | Pointers: 36 |
||
36 | Null ptrs: 8 |
||
37 | Total size: 3 kB |
||
38 | |||
39 | Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com> |
||
40 | Signed-off-by: David S. Miller <davem@davemloft.net> |
||
41 | --- |
||
42 | |||
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); |
||
47 | } |
||
48 | |||
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'." |
||
54 | + * |
||
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. |
||
61 | + * |
||
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. |
||
68 | + * |
||
69 | + * A clearer way to write this would be: |
||
70 | + * |
||
71 | + * to_be_doubled = tn->full_children; |
||
72 | + * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - |
||
73 | + * tn->full_children; |
||
74 | + * |
||
75 | + * new_child_length = tnode_child_length(tn) * 2; |
||
76 | + * |
||
77 | + * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / |
||
78 | + * new_child_length; |
||
79 | + * if (new_fill_factor >= inflate_threshold) |
||
80 | + * |
||
81 | + * ...and so on, tho it would mess up the while () loop. |
||
82 | + * |
||
83 | + * anyway, |
||
84 | + * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= |
||
85 | + * inflate_threshold |
||
86 | + * |
||
87 | + * avoid a division: |
||
88 | + * 100 * (not_to_be_doubled + 2*to_be_doubled) >= |
||
89 | + * inflate_threshold * new_child_length |
||
90 | + * |
||
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 |
||
94 | + * |
||
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 |
||
99 | + * |
||
100 | + * shorten again: |
||
101 | + * 50 * (tn->full_children + tnode_child_length(tn) - |
||
102 | + * tn->empty_children) >= inflate_threshold * |
||
103 | + * tnode_child_length(tn) |
||
104 | + * |
||
105 | + */ |
||
106 | +static bool should_inflate(const struct tnode *tn) |
||
107 | +{ |
||
108 | + unsigned long used = tnode_child_length(tn); |
||
109 | + unsigned long threshold = used; |
||
110 | + |
||
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; |
||
116 | + |
||
117 | + return tn->pos && ((50 * used) >= threshold); |
||
118 | +} |
||
119 | + |
||
120 | +static bool should_halve(const struct tnode *tn) |
||
121 | +{ |
||
122 | + unsigned long used = tnode_child_length(tn); |
||
123 | + unsigned long threshold = used; |
||
124 | + |
||
125 | + /* Keep root node larger */ |
||
126 | + threshold *= node_parent(tn) ? halve_threshold : |
||
127 | + halve_threshold_root; |
||
128 | + used -= tn->empty_children; |
||
129 | + |
||
130 | + return (tn->bits > 1) && ((100 * used) < threshold); |
||
131 | +} |
||
132 | + |
||
133 | #define MAX_WORK 10 |
||
134 | static struct tnode *resize(struct trie *t, struct tnode *tn) |
||
135 | { |
||
136 | struct tnode *old_tn, *n = NULL; |
||
137 | - int inflate_threshold_use; |
||
138 | - int halve_threshold_use; |
||
139 | int max_work; |
||
140 | |||
141 | if (!tn) |
||
142 | @@ -668,86 +750,12 @@ static struct tnode *resize(struct trie |
||
143 | /* One child */ |
||
144 | if (tn->empty_children == (tnode_child_length(tn) - 1)) |
||
145 | goto one_child; |
||
146 | - /* |
||
147 | - * Double as long as the resulting node has a number of |
||
148 | - * nonempty nodes that are above the threshold. |
||
149 | - */ |
||
150 | |||
151 | - /* |
||
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'." |
||
157 | - * |
||
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. |
||
164 | - * |
||
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. |
||
171 | - * |
||
172 | - * A clearer way to write this would be: |
||
173 | - * |
||
174 | - * to_be_doubled = tn->full_children; |
||
175 | - * not_to_be_doubled = tnode_child_length(tn) - tn->empty_children - |
||
176 | - * tn->full_children; |
||
177 | - * |
||
178 | - * new_child_length = tnode_child_length(tn) * 2; |
||
179 | - * |
||
180 | - * new_fill_factor = 100 * (not_to_be_doubled + 2*to_be_doubled) / |
||
181 | - * new_child_length; |
||
182 | - * if (new_fill_factor >= inflate_threshold) |
||
183 | - * |
||
184 | - * ...and so on, tho it would mess up the while () loop. |
||
185 | - * |
||
186 | - * anyway, |
||
187 | - * 100 * (not_to_be_doubled + 2*to_be_doubled) / new_child_length >= |
||
188 | - * inflate_threshold |
||
189 | - * |
||
190 | - * avoid a division: |
||
191 | - * 100 * (not_to_be_doubled + 2*to_be_doubled) >= |
||
192 | - * inflate_threshold * new_child_length |
||
193 | - * |
||
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 |
||
197 | - * |
||
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 |
||
202 | - * |
||
203 | - * shorten again: |
||
204 | - * 50 * (tn->full_children + tnode_child_length(tn) - |
||
205 | - * tn->empty_children) >= inflate_threshold * |
||
206 | - * tnode_child_length(tn) |
||
207 | - * |
||
208 | + /* Double as long as the resulting node has a number of |
||
209 | + * nonempty nodes that are above the threshold. |
||
210 | */ |
||
211 | - |
||
212 | - /* Keep root node larger */ |
||
213 | - |
||
214 | - if (!node_parent(tn)) { |
||
215 | - inflate_threshold_use = inflate_threshold_root; |
||
216 | - halve_threshold_use = halve_threshold_root; |
||
217 | - } else { |
||
218 | - inflate_threshold_use = inflate_threshold; |
||
219 | - halve_threshold_use = halve_threshold; |
||
220 | - } |
||
221 | - |
||
222 | max_work = MAX_WORK; |
||
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))) { |
||
227 | - |
||
228 | + while (should_inflate(tn) && max_work--) { |
||
229 | old_tn = tn; |
||
230 | tn = inflate(t, tn); |
||
231 | |||
232 | @@ -764,16 +772,11 @@ static struct tnode *resize(struct trie |
||
233 | if (max_work != MAX_WORK) |
||
234 | return tn; |
||
235 | |||
236 | - /* |
||
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. |
||
240 | */ |
||
241 | - |
||
242 | max_work = MAX_WORK; |
||
243 | - while (tn->bits > 1 && max_work-- && |
||
244 | - 100 * (tnode_child_length(tn) - tn->empty_children) < |
||
245 | - halve_threshold_use * tnode_child_length(tn)) { |
||
246 | - |
||
247 | + while (should_halve(tn) && max_work--) { |
||
248 | old_tn = tn; |
||
249 | tn = halve(t, tn); |
||
250 | if (IS_ERR(tn)) { |