kernel: update kernel 3.18 to version 3.18.23
[openwrt/staging/chunkeey.git] / target / linux / generic / patches-3.18 / 080-05-fib_trie-Merge-leaf-into-tnode.patch
1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Wed, 31 Dec 2014 10:55:47 -0800
3 Subject: [PATCH] fib_trie: Merge leaf into tnode
4
5 This change makes it so that leaf and tnode are the same struct. As a
6 result there is no need for rt_trie_node anymore since everyting can be
7 merged into tnode.
8
9 On 32b systems this results in the leaf being 4 bytes larger, however I
10 don't know if that is really an issue as this and an eariler patch that
11 added bits & pos have increased the size from 20 to 28. If I am not
12 mistaken slub/slab allocate on power of 2 sizes so 20 was likely being
13 rounded up to 32 anyway.
14
15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
16 Signed-off-by: David S. Miller <davem@davemloft.net>
17 ---
18
19 --- a/net/ipv4/fib_trie.c
20 +++ b/net/ipv4/fib_trie.c
21 @@ -96,32 +96,16 @@ struct tnode {
22 unsigned char pos; /* 2log(KEYLENGTH) bits needed */
23 struct tnode __rcu *parent;
24 struct rcu_head rcu;
25 - /* everything above this comment must be the same as rt_trie_node */
26 - unsigned int full_children; /* KEYLENGTH bits needed */
27 - unsigned int empty_children; /* KEYLENGTH bits needed */
28 - struct rt_trie_node __rcu *child[0];
29 -};
30 -
31 -/* This struct represents the shared bits between tnode and leaf. If any
32 - * ordering is changed here is must also be updated in tnode and leaf as
33 - * well.
34 - */
35 -struct rt_trie_node {
36 - t_key key;
37 - unsigned char bits;
38 - unsigned char pos;
39 - struct tnode __rcu *parent;
40 - struct rcu_head rcu;
41 -};
42 -
43 -struct leaf {
44 - t_key key;
45 - unsigned char bits;
46 - unsigned char pos;
47 - struct tnode __rcu *parent;
48 - struct rcu_head rcu;
49 - /* everything above this comment must be the same as rt_trie_node */
50 - struct hlist_head list;
51 + union {
52 + /* The fields in this struct are valid if bits > 0 (TNODE) */
53 + struct {
54 + unsigned int full_children; /* KEYLENGTH bits needed */
55 + unsigned int empty_children; /* KEYLENGTH bits needed */
56 + struct tnode __rcu *child[0];
57 + };
58 + /* This list pointer if valid if bits == 0 (LEAF) */
59 + struct hlist_head list;
60 + };
61 };
62
63 struct leaf_info {
64 @@ -154,15 +138,15 @@ struct trie_stat {
65 };
66
67 struct trie {
68 - struct rt_trie_node __rcu *trie;
69 + struct tnode __rcu *trie;
70 #ifdef CONFIG_IP_FIB_TRIE_STATS
71 struct trie_use_stats __percpu *stats;
72 #endif
73 };
74
75 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
76 +static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
77 int wasfull);
78 -static struct rt_trie_node *resize(struct trie *t, struct tnode *tn);
79 +static struct tnode *resize(struct trie *t, struct tnode *tn);
80 static struct tnode *inflate(struct trie *t, struct tnode *tn);
81 static struct tnode *halve(struct trie *t, struct tnode *tn);
82 /* tnodes to free after resize(); protected by RTNL */
83 @@ -186,10 +170,10 @@ static struct kmem_cache *trie_leaf_kmem
84 #define node_parent_rcu(n) rcu_dereference_rtnl((n)->parent)
85
86 /* wrapper for rcu_assign_pointer */
87 -static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
88 +static inline void node_set_parent(struct tnode *n, struct tnode *tp)
89 {
90 - if (node)
91 - rcu_assign_pointer(node->parent, ptr);
92 + if (n)
93 + rcu_assign_pointer(n->parent, tp);
94 }
95
96 #define NODE_INIT_PARENT(n, p) RCU_INIT_POINTER((n)->parent, p)
97 @@ -205,7 +189,7 @@ static inline int tnode_child_length(con
98 /*
99 * caller must hold RTNL
100 */
101 -static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
102 +static inline struct tnode *tnode_get_child(const struct tnode *tn, unsigned int i)
103 {
104 BUG_ON(i >= tnode_child_length(tn));
105
106 @@ -215,7 +199,7 @@ static inline struct rt_trie_node *tnode
107 /*
108 * caller must hold RCU read lock or RTNL
109 */
110 -static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
111 +static inline struct tnode *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
112 {
113 BUG_ON(i >= tnode_child_length(tn));
114
115 @@ -340,11 +324,11 @@ static inline void alias_free_mem_rcu(st
116 }
117
118 #define TNODE_KMALLOC_MAX \
119 - ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct rt_trie_node *))
120 + ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct tnode *))
121
122 static void __node_free_rcu(struct rcu_head *head)
123 {
124 - struct rt_trie_node *n = container_of(head, struct rt_trie_node, rcu);
125 + struct tnode *n = container_of(head, struct tnode, rcu);
126
127 if (IS_LEAF(n))
128 kmem_cache_free(trie_leaf_kmem, n);
129 @@ -395,9 +379,9 @@ static void tnode_free_flush(void)
130 }
131 }
132
133 -static struct leaf *leaf_new(t_key key)
134 +static struct tnode *leaf_new(t_key key)
135 {
136 - struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
137 + struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
138 if (l) {
139 l->parent = NULL;
140 /* set key and pos to reflect full key value
141 @@ -444,7 +428,7 @@ static struct tnode *tnode_new(t_key key
142 }
143
144 pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
145 - sizeof(struct rt_trie_node *) << bits);
146 + sizeof(struct tnode *) << bits);
147 return tn;
148 }
149
150 @@ -453,13 +437,13 @@ static struct tnode *tnode_new(t_key key
151 * and no bits are skipped. See discussion in dyntree paper p. 6
152 */
153
154 -static inline int tnode_full(const struct tnode *tn, const struct rt_trie_node *n)
155 +static inline int tnode_full(const struct tnode *tn, const struct tnode *n)
156 {
157 return n && IS_TNODE(n) && (n->pos == (tn->pos + tn->bits));
158 }
159
160 static inline void put_child(struct tnode *tn, int i,
161 - struct rt_trie_node *n)
162 + struct tnode *n)
163 {
164 tnode_put_child_reorg(tn, i, n, -1);
165 }
166 @@ -469,10 +453,10 @@ static inline void put_child(struct tnod
167 * Update the value of full_children and empty_children.
168 */
169
170 -static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
171 +static void tnode_put_child_reorg(struct tnode *tn, int i, struct tnode *n,
172 int wasfull)
173 {
174 - struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
175 + struct tnode *chi = rtnl_dereference(tn->child[i]);
176 int isfull;
177
178 BUG_ON(i >= 1<<tn->bits);
179 @@ -499,10 +483,9 @@ static void tnode_put_child_reorg(struct
180 }
181
182 #define MAX_WORK 10
183 -static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
184 +static struct tnode *resize(struct trie *t, struct tnode *tn)
185 {
186 - struct rt_trie_node *n = NULL;
187 - struct tnode *old_tn;
188 + struct tnode *old_tn, *n = NULL;
189 int inflate_threshold_use;
190 int halve_threshold_use;
191 int max_work;
192 @@ -614,7 +597,7 @@ static struct rt_trie_node *resize(struc
193
194 /* Return if at least one inflate is run */
195 if (max_work != MAX_WORK)
196 - return (struct rt_trie_node *) tn;
197 + return tn;
198
199 /*
200 * Halve as long as the number of empty children in this
201 @@ -650,13 +633,13 @@ no_children:
202 tnode_free_safe(tn);
203 return n;
204 }
205 - return (struct rt_trie_node *) tn;
206 + return tn;
207 }
208
209
210 static void tnode_clean_free(struct tnode *tn)
211 {
212 - struct rt_trie_node *tofree;
213 + struct tnode *tofree;
214 int i;
215
216 for (i = 0; i < tnode_child_length(tn); i++) {
217 @@ -667,10 +650,10 @@ static void tnode_clean_free(struct tnod
218 node_free(tn);
219 }
220
221 -static struct tnode *inflate(struct trie *t, struct tnode *tn)
222 +static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
223 {
224 - struct tnode *oldtnode = tn;
225 - int olen = tnode_child_length(tn);
226 + int olen = tnode_child_length(oldtnode);
227 + struct tnode *tn;
228 int i;
229
230 pr_debug("In inflate\n");
231 @@ -690,11 +673,8 @@ static struct tnode *inflate(struct trie
232 for (i = 0; i < olen; i++) {
233 struct tnode *inode;
234
235 - inode = (struct tnode *) tnode_get_child(oldtnode, i);
236 - if (inode &&
237 - IS_TNODE(inode) &&
238 - inode->pos == oldtnode->pos + oldtnode->bits &&
239 - inode->bits > 1) {
240 + inode = tnode_get_child(oldtnode, i);
241 + if (tnode_full(oldtnode, inode) && inode->bits > 1) {
242 struct tnode *left, *right;
243 t_key m = ~0U << (KEYLENGTH - 1) >> inode->pos;
244
245 @@ -711,33 +691,29 @@ static struct tnode *inflate(struct trie
246 goto nomem;
247 }
248
249 - put_child(tn, 2*i, (struct rt_trie_node *) left);
250 - put_child(tn, 2*i+1, (struct rt_trie_node *) right);
251 + put_child(tn, 2*i, left);
252 + put_child(tn, 2*i+1, right);
253 }
254 }
255
256 for (i = 0; i < olen; i++) {
257 - struct tnode *inode;
258 - struct rt_trie_node *node = tnode_get_child(oldtnode, i);
259 + struct tnode *inode = tnode_get_child(oldtnode, i);
260 struct tnode *left, *right;
261 int size, j;
262
263 /* An empty child */
264 - if (node == NULL)
265 + if (inode == NULL)
266 continue;
267
268 /* A leaf or an internal node with skipped bits */
269 -
270 - if (IS_LEAF(node) || (node->pos > (tn->pos + tn->bits - 1))) {
271 + if (!tnode_full(oldtnode, inode)) {
272 put_child(tn,
273 - tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
274 - node);
275 + tkey_extract_bits(inode->key, tn->pos, tn->bits),
276 + inode);
277 continue;
278 }
279
280 /* An internal node with two children */
281 - inode = (struct tnode *) node;
282 -
283 if (inode->bits == 1) {
284 put_child(tn, 2*i, rtnl_dereference(inode->child[0]));
285 put_child(tn, 2*i+1, rtnl_dereference(inode->child[1]));
286 @@ -769,12 +745,12 @@ static struct tnode *inflate(struct trie
287 * bit to zero.
288 */
289
290 - left = (struct tnode *) tnode_get_child(tn, 2*i);
291 + left = tnode_get_child(tn, 2*i);
292 put_child(tn, 2*i, NULL);
293
294 BUG_ON(!left);
295
296 - right = (struct tnode *) tnode_get_child(tn, 2*i+1);
297 + right = tnode_get_child(tn, 2*i+1);
298 put_child(tn, 2*i+1, NULL);
299
300 BUG_ON(!right);
301 @@ -796,12 +772,11 @@ nomem:
302 return ERR_PTR(-ENOMEM);
303 }
304
305 -static struct tnode *halve(struct trie *t, struct tnode *tn)
306 +static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
307 {
308 - struct tnode *oldtnode = tn;
309 - struct rt_trie_node *left, *right;
310 + int olen = tnode_child_length(oldtnode);
311 + struct tnode *tn, *left, *right;
312 int i;
313 - int olen = tnode_child_length(tn);
314
315 pr_debug("In halve\n");
316
317 @@ -830,7 +805,7 @@ static struct tnode *halve(struct trie *
318 if (!newn)
319 goto nomem;
320
321 - put_child(tn, i/2, (struct rt_trie_node *)newn);
322 + put_child(tn, i/2, newn);
323 }
324
325 }
326 @@ -855,7 +830,7 @@ static struct tnode *halve(struct trie *
327 }
328
329 /* Two nonempty children */
330 - newBinNode = (struct tnode *) tnode_get_child(tn, i/2);
331 + newBinNode = tnode_get_child(tn, i/2);
332 put_child(tn, i/2, NULL);
333 put_child(newBinNode, 0, left);
334 put_child(newBinNode, 1, right);
335 @@ -871,7 +846,7 @@ nomem:
336 /* readside must use rcu_read_lock currently dump routines
337 via get_fa_head and dump */
338
339 -static struct leaf_info *find_leaf_info(struct leaf *l, int plen)
340 +static struct leaf_info *find_leaf_info(struct tnode *l, int plen)
341 {
342 struct hlist_head *head = &l->list;
343 struct leaf_info *li;
344 @@ -883,7 +858,7 @@ static struct leaf_info *find_leaf_info(
345 return NULL;
346 }
347
348 -static inline struct list_head *get_fa_head(struct leaf *l, int plen)
349 +static inline struct list_head *get_fa_head(struct tnode *l, int plen)
350 {
351 struct leaf_info *li = find_leaf_info(l, plen);
352
353 @@ -915,32 +890,25 @@ static void insert_leaf_info(struct hlis
354
355 /* rcu_read_lock needs to be hold by caller from readside */
356
357 -static struct leaf *
358 -fib_find_node(struct trie *t, u32 key)
359 +static struct tnode *fib_find_node(struct trie *t, u32 key)
360 {
361 - int pos;
362 - struct tnode *tn;
363 - struct rt_trie_node *n;
364 -
365 - pos = 0;
366 - n = rcu_dereference_rtnl(t->trie);
367 + struct tnode *n = rcu_dereference_rtnl(t->trie);
368 + int pos = 0;
369
370 while (n && IS_TNODE(n)) {
371 - tn = (struct tnode *) n;
372 -
373 - if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
374 - pos = tn->pos + tn->bits;
375 - n = tnode_get_child_rcu(tn,
376 + if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
377 + pos = n->pos + n->bits;
378 + n = tnode_get_child_rcu(n,
379 tkey_extract_bits(key,
380 - tn->pos,
381 - tn->bits));
382 + n->pos,
383 + n->bits));
384 } else
385 break;
386 }
387 /* Case we have found a leaf. Compare prefixes */
388
389 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
390 - return (struct leaf *)n;
391 + return n;
392
393 return NULL;
394 }
395 @@ -956,14 +924,13 @@ static void trie_rebalance(struct trie *
396 while (tn != NULL && (tp = node_parent(tn)) != NULL) {
397 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
398 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
399 - tn = (struct tnode *)resize(t, tn);
400 + tn = resize(t, tn);
401
402 - tnode_put_child_reorg(tp, cindex,
403 - (struct rt_trie_node *)tn, wasfull);
404 + tnode_put_child_reorg(tp, cindex, tn, wasfull);
405
406 tp = node_parent(tn);
407 if (!tp)
408 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
409 + rcu_assign_pointer(t->trie, tn);
410
411 tnode_free_flush();
412 if (!tp)
413 @@ -973,9 +940,9 @@ static void trie_rebalance(struct trie *
414
415 /* Handle last (top) tnode */
416 if (IS_TNODE(tn))
417 - tn = (struct tnode *)resize(t, tn);
418 + tn = resize(t, tn);
419
420 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
421 + rcu_assign_pointer(t->trie, tn);
422 tnode_free_flush();
423 }
424
425 @@ -985,8 +952,8 @@ static struct list_head *fib_insert_node
426 {
427 int pos, newpos;
428 struct tnode *tp = NULL, *tn = NULL;
429 - struct rt_trie_node *n;
430 - struct leaf *l;
431 + struct tnode *n;
432 + struct tnode *l;
433 int missbit;
434 struct list_head *fa_head = NULL;
435 struct leaf_info *li;
436 @@ -1014,17 +981,15 @@ static struct list_head *fib_insert_node
437 */
438
439 while (n && IS_TNODE(n)) {
440 - tn = (struct tnode *) n;
441 -
442 - if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
443 - tp = tn;
444 - pos = tn->pos + tn->bits;
445 - n = tnode_get_child(tn,
446 + if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
447 + tp = n;
448 + pos = n->pos + n->bits;
449 + n = tnode_get_child(n,
450 tkey_extract_bits(key,
451 - tn->pos,
452 - tn->bits));
453 + n->pos,
454 + n->bits));
455
456 - BUG_ON(n && node_parent(n) != tn);
457 + BUG_ON(n && node_parent(n) != tp);
458 } else
459 break;
460 }
461 @@ -1040,14 +1005,13 @@ static struct list_head *fib_insert_node
462 /* Case 1: n is a leaf. Compare prefixes */
463
464 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
465 - l = (struct leaf *) n;
466 li = leaf_info_new(plen);
467
468 if (!li)
469 return NULL;
470
471 fa_head = &li->falh;
472 - insert_leaf_info(&l->list, li);
473 + insert_leaf_info(&n->list, li);
474 goto done;
475 }
476 l = leaf_new(key);
477 @@ -1068,10 +1032,10 @@ static struct list_head *fib_insert_node
478 if (t->trie && n == NULL) {
479 /* Case 2: n is NULL, and will just insert a new leaf */
480
481 - node_set_parent((struct rt_trie_node *)l, tp);
482 + node_set_parent(l, tp);
483
484 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
485 - put_child(tp, cindex, (struct rt_trie_node *)l);
486 + put_child(tp, cindex, l);
487 } else {
488 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
489 /*
490 @@ -1094,17 +1058,17 @@ static struct list_head *fib_insert_node
491 return NULL;
492 }
493
494 - node_set_parent((struct rt_trie_node *)tn, tp);
495 + node_set_parent(tn, tp);
496
497 missbit = tkey_extract_bits(key, newpos, 1);
498 - put_child(tn, missbit, (struct rt_trie_node *)l);
499 + put_child(tn, missbit, l);
500 put_child(tn, 1-missbit, n);
501
502 if (tp) {
503 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
504 - put_child(tp, cindex, (struct rt_trie_node *)tn);
505 + put_child(tp, cindex, tn);
506 } else {
507 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
508 + rcu_assign_pointer(t->trie, tn);
509 }
510
511 tp = tn;
512 @@ -1134,7 +1098,7 @@ int fib_table_insert(struct fib_table *t
513 u8 tos = cfg->fc_tos;
514 u32 key, mask;
515 int err;
516 - struct leaf *l;
517 + struct tnode *l;
518
519 if (plen > 32)
520 return -EINVAL;
521 @@ -1292,7 +1256,7 @@ err:
522 }
523
524 /* should be called with rcu_read_lock */
525 -static int check_leaf(struct fib_table *tb, struct trie *t, struct leaf *l,
526 +static int check_leaf(struct fib_table *tb, struct trie *t, struct tnode *l,
527 t_key key, const struct flowi4 *flp,
528 struct fib_result *res, int fib_flags)
529 {
530 @@ -1365,7 +1329,7 @@ int fib_table_lookup(struct fib_table *t
531 struct trie_use_stats __percpu *stats = t->stats;
532 #endif
533 int ret;
534 - struct rt_trie_node *n;
535 + struct tnode *n;
536 struct tnode *pn;
537 unsigned int pos, bits;
538 t_key key = ntohl(flp->daddr);
539 @@ -1387,11 +1351,11 @@ int fib_table_lookup(struct fib_table *t
540
541 /* Just a leaf? */
542 if (IS_LEAF(n)) {
543 - ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
544 + ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
545 goto found;
546 }
547
548 - pn = (struct tnode *) n;
549 + pn = n;
550 chopped_off = 0;
551
552 while (pn) {
553 @@ -1412,13 +1376,13 @@ int fib_table_lookup(struct fib_table *t
554 }
555
556 if (IS_LEAF(n)) {
557 - ret = check_leaf(tb, t, (struct leaf *)n, key, flp, res, fib_flags);
558 + ret = check_leaf(tb, t, n, key, flp, res, fib_flags);
559 if (ret > 0)
560 goto backtrace;
561 goto found;
562 }
563
564 - cn = (struct tnode *)n;
565 + cn = n;
566
567 /*
568 * It's a tnode, and we can do some extra checks here if we
569 @@ -1506,7 +1470,7 @@ int fib_table_lookup(struct fib_table *t
570 current_prefix_length = mp;
571 }
572
573 - pn = (struct tnode *)n; /* Descend */
574 + pn = n; /* Descend */
575 chopped_off = 0;
576 continue;
577
578 @@ -1557,7 +1521,7 @@ EXPORT_SYMBOL_GPL(fib_table_lookup);
579 /*
580 * Remove the leaf and return parent.
581 */
582 -static void trie_leaf_remove(struct trie *t, struct leaf *l)
583 +static void trie_leaf_remove(struct trie *t, struct tnode *l)
584 {
585 struct tnode *tp = node_parent(l);
586
587 @@ -1584,7 +1548,7 @@ int fib_table_delete(struct fib_table *t
588 u8 tos = cfg->fc_tos;
589 struct fib_alias *fa, *fa_to_delete;
590 struct list_head *fa_head;
591 - struct leaf *l;
592 + struct tnode *l;
593 struct leaf_info *li;
594
595 if (plen > 32)
596 @@ -1682,7 +1646,7 @@ static int trie_flush_list(struct list_h
597 return found;
598 }
599
600 -static int trie_flush_leaf(struct leaf *l)
601 +static int trie_flush_leaf(struct tnode *l)
602 {
603 int found = 0;
604 struct hlist_head *lih = &l->list;
605 @@ -1704,7 +1668,7 @@ static int trie_flush_leaf(struct leaf *
606 * Scan for the next right leaf starting at node p->child[idx]
607 * Since we have back pointer, no recursion necessary.
608 */
609 -static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
610 +static struct tnode *leaf_walk_rcu(struct tnode *p, struct tnode *c)
611 {
612 do {
613 t_key idx;
614 @@ -1720,47 +1684,46 @@ static struct leaf *leaf_walk_rcu(struct
615 continue;
616
617 if (IS_LEAF(c))
618 - return (struct leaf *) c;
619 + return c;
620
621 /* Rescan start scanning in new node */
622 - p = (struct tnode *) c;
623 + p = c;
624 idx = 0;
625 }
626
627 /* Node empty, walk back up to parent */
628 - c = (struct rt_trie_node *) p;
629 + c = p;
630 } while ((p = node_parent_rcu(c)) != NULL);
631
632 return NULL; /* Root of trie */
633 }
634
635 -static struct leaf *trie_firstleaf(struct trie *t)
636 +static struct tnode *trie_firstleaf(struct trie *t)
637 {
638 - struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
639 + struct tnode *n = rcu_dereference_rtnl(t->trie);
640
641 if (!n)
642 return NULL;
643
644 if (IS_LEAF(n)) /* trie is just a leaf */
645 - return (struct leaf *) n;
646 + return n;
647
648 return leaf_walk_rcu(n, NULL);
649 }
650
651 -static struct leaf *trie_nextleaf(struct leaf *l)
652 +static struct tnode *trie_nextleaf(struct tnode *l)
653 {
654 - struct rt_trie_node *c = (struct rt_trie_node *) l;
655 - struct tnode *p = node_parent_rcu(c);
656 + struct tnode *p = node_parent_rcu(l);
657
658 if (!p)
659 return NULL; /* trie with just one leaf */
660
661 - return leaf_walk_rcu(p, c);
662 + return leaf_walk_rcu(p, l);
663 }
664
665 -static struct leaf *trie_leafindex(struct trie *t, int index)
666 +static struct tnode *trie_leafindex(struct trie *t, int index)
667 {
668 - struct leaf *l = trie_firstleaf(t);
669 + struct tnode *l = trie_firstleaf(t);
670
671 while (l && index-- > 0)
672 l = trie_nextleaf(l);
673 @@ -1775,7 +1738,7 @@ static struct leaf *trie_leafindex(struc
674 int fib_table_flush(struct fib_table *tb)
675 {
676 struct trie *t = (struct trie *) tb->tb_data;
677 - struct leaf *l, *ll = NULL;
678 + struct tnode *l, *ll = NULL;
679 int found = 0;
680
681 for (l = trie_firstleaf(t); l; l = trie_nextleaf(l)) {
682 @@ -1840,7 +1803,7 @@ static int fn_trie_dump_fa(t_key key, in
683 return skb->len;
684 }
685
686 -static int fn_trie_dump_leaf(struct leaf *l, struct fib_table *tb,
687 +static int fn_trie_dump_leaf(struct tnode *l, struct fib_table *tb,
688 struct sk_buff *skb, struct netlink_callback *cb)
689 {
690 struct leaf_info *li;
691 @@ -1876,7 +1839,7 @@ static int fn_trie_dump_leaf(struct leaf
692 int fib_table_dump(struct fib_table *tb, struct sk_buff *skb,
693 struct netlink_callback *cb)
694 {
695 - struct leaf *l;
696 + struct tnode *l;
697 struct trie *t = (struct trie *) tb->tb_data;
698 t_key key = cb->args[2];
699 int count = cb->args[3];
700 @@ -1922,7 +1885,7 @@ void __init fib_trie_init(void)
701 0, SLAB_PANIC, NULL);
702
703 trie_leaf_kmem = kmem_cache_create("ip_fib_trie",
704 - max(sizeof(struct leaf),
705 + max(sizeof(struct tnode),
706 sizeof(struct leaf_info)),
707 0, SLAB_PANIC, NULL);
708 }
709 @@ -1965,7 +1928,7 @@ struct fib_trie_iter {
710 unsigned int depth;
711 };
712
713 -static struct rt_trie_node *fib_trie_get_next(struct fib_trie_iter *iter)
714 +static struct tnode *fib_trie_get_next(struct fib_trie_iter *iter)
715 {
716 struct tnode *tn = iter->tnode;
717 unsigned int cindex = iter->index;
718 @@ -1979,7 +1942,7 @@ static struct rt_trie_node *fib_trie_get
719 iter->tnode, iter->index, iter->depth);
720 rescan:
721 while (cindex < (1<<tn->bits)) {
722 - struct rt_trie_node *n = tnode_get_child_rcu(tn, cindex);
723 + struct tnode *n = tnode_get_child_rcu(tn, cindex);
724
725 if (n) {
726 if (IS_LEAF(n)) {
727 @@ -1987,7 +1950,7 @@ rescan:
728 iter->index = cindex + 1;
729 } else {
730 /* push down one level */
731 - iter->tnode = (struct tnode *) n;
732 + iter->tnode = n;
733 iter->index = 0;
734 ++iter->depth;
735 }
736 @@ -1998,7 +1961,7 @@ rescan:
737 }
738
739 /* Current node exhausted, pop back up */
740 - p = node_parent_rcu((struct rt_trie_node *)tn);
741 + p = node_parent_rcu(tn);
742 if (p) {
743 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
744 tn = p;
745 @@ -2010,10 +1973,10 @@ rescan:
746 return NULL;
747 }
748
749 -static struct rt_trie_node *fib_trie_get_first(struct fib_trie_iter *iter,
750 +static struct tnode *fib_trie_get_first(struct fib_trie_iter *iter,
751 struct trie *t)
752 {
753 - struct rt_trie_node *n;
754 + struct tnode *n;
755
756 if (!t)
757 return NULL;
758 @@ -2023,7 +1986,7 @@ static struct rt_trie_node *fib_trie_get
759 return NULL;
760
761 if (IS_TNODE(n)) {
762 - iter->tnode = (struct tnode *) n;
763 + iter->tnode = n;
764 iter->index = 0;
765 iter->depth = 1;
766 } else {
767 @@ -2037,7 +2000,7 @@ static struct rt_trie_node *fib_trie_get
768
769 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
770 {
771 - struct rt_trie_node *n;
772 + struct tnode *n;
773 struct fib_trie_iter iter;
774
775 memset(s, 0, sizeof(*s));
776 @@ -2045,7 +2008,6 @@ static void trie_collect_stats(struct tr
777 rcu_read_lock();
778 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
779 if (IS_LEAF(n)) {
780 - struct leaf *l = (struct leaf *)n;
781 struct leaf_info *li;
782
783 s->leaves++;
784 @@ -2053,18 +2015,17 @@ static void trie_collect_stats(struct tr
785 if (iter.depth > s->maxdepth)
786 s->maxdepth = iter.depth;
787
788 - hlist_for_each_entry_rcu(li, &l->list, hlist)
789 + hlist_for_each_entry_rcu(li, &n->list, hlist)
790 ++s->prefixes;
791 } else {
792 - const struct tnode *tn = (const struct tnode *) n;
793 int i;
794
795 s->tnodes++;
796 - if (tn->bits < MAX_STAT_DEPTH)
797 - s->nodesizes[tn->bits]++;
798 + if (n->bits < MAX_STAT_DEPTH)
799 + s->nodesizes[n->bits]++;
800
801 - for (i = 0; i < (1<<tn->bits); i++)
802 - if (!tn->child[i])
803 + for (i = 0; i < tnode_child_length(n); i++)
804 + if (!rcu_access_pointer(n->child[i]))
805 s->nullpointers++;
806 }
807 }
808 @@ -2088,7 +2049,7 @@ static void trie_show_stats(struct seq_f
809 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
810
811 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
812 - bytes = sizeof(struct leaf) * stat->leaves;
813 + bytes = sizeof(struct tnode) * stat->leaves;
814
815 seq_printf(seq, "\tPrefixes: %u\n", stat->prefixes);
816 bytes += sizeof(struct leaf_info) * stat->prefixes;
817 @@ -2109,7 +2070,7 @@ static void trie_show_stats(struct seq_f
818 seq_putc(seq, '\n');
819 seq_printf(seq, "\tPointers: %u\n", pointers);
820
821 - bytes += sizeof(struct rt_trie_node *) * pointers;
822 + bytes += sizeof(struct tnode *) * pointers;
823 seq_printf(seq, "Null ptrs: %u\n", stat->nullpointers);
824 seq_printf(seq, "Total size: %u kB\n", (bytes + 1023) / 1024);
825 }
826 @@ -2163,7 +2124,7 @@ static int fib_triestat_seq_show(struct
827 seq_printf(seq,
828 "Basic info: size of leaf:"
829 " %Zd bytes, size of tnode: %Zd bytes.\n",
830 - sizeof(struct leaf), sizeof(struct tnode));
831 + sizeof(struct tnode), sizeof(struct tnode));
832
833 for (h = 0; h < FIB_TABLE_HASHSZ; h++) {
834 struct hlist_head *head = &net->ipv4.fib_table_hash[h];
835 @@ -2202,7 +2163,7 @@ static const struct file_operations fib_
836 .release = single_release_net,
837 };
838
839 -static struct rt_trie_node *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
840 +static struct tnode *fib_trie_get_idx(struct seq_file *seq, loff_t pos)
841 {
842 struct fib_trie_iter *iter = seq->private;
843 struct net *net = seq_file_net(seq);
844 @@ -2214,7 +2175,7 @@ static struct rt_trie_node *fib_trie_get
845 struct fib_table *tb;
846
847 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
848 - struct rt_trie_node *n;
849 + struct tnode *n;
850
851 for (n = fib_trie_get_first(iter,
852 (struct trie *) tb->tb_data);
853 @@ -2243,7 +2204,7 @@ static void *fib_trie_seq_next(struct se
854 struct fib_table *tb = iter->tb;
855 struct hlist_node *tb_node;
856 unsigned int h;
857 - struct rt_trie_node *n;
858 + struct tnode *n;
859
860 ++*pos;
861 /* next node in same table */
862 @@ -2329,29 +2290,26 @@ static inline const char *rtn_type(char
863 static int fib_trie_seq_show(struct seq_file *seq, void *v)
864 {
865 const struct fib_trie_iter *iter = seq->private;
866 - struct rt_trie_node *n = v;
867 + struct tnode *n = v;
868
869 if (!node_parent_rcu(n))
870 fib_table_print(seq, iter->tb);
871
872 if (IS_TNODE(n)) {
873 - struct tnode *tn = (struct tnode *) n;
874 - __be32 prf = htonl(tn->key);
875 + __be32 prf = htonl(n->key);
876
877 - seq_indent(seq, iter->depth-1);
878 + seq_indent(seq, iter->depth - 1);
879 seq_printf(seq, " +-- %pI4/%d %d %d %d\n",
880 - &prf, tn->pos, tn->bits, tn->full_children,
881 - tn->empty_children);
882 -
883 + &prf, n->pos, n->bits, n->full_children,
884 + n->empty_children);
885 } else {
886 - struct leaf *l = (struct leaf *) n;
887 struct leaf_info *li;
888 - __be32 val = htonl(l->key);
889 + __be32 val = htonl(n->key);
890
891 seq_indent(seq, iter->depth);
892 seq_printf(seq, " |-- %pI4\n", &val);
893
894 - hlist_for_each_entry_rcu(li, &l->list, hlist) {
895 + hlist_for_each_entry_rcu(li, &n->list, hlist) {
896 struct fib_alias *fa;
897
898 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
899 @@ -2401,9 +2359,9 @@ struct fib_route_iter {
900 t_key key;
901 };
902
903 -static struct leaf *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
904 +static struct tnode *fib_route_get_idx(struct fib_route_iter *iter, loff_t pos)
905 {
906 - struct leaf *l = NULL;
907 + struct tnode *l = NULL;
908 struct trie *t = iter->main_trie;
909
910 /* use cache location of last found key */
911 @@ -2448,7 +2406,7 @@ static void *fib_route_seq_start(struct
912 static void *fib_route_seq_next(struct seq_file *seq, void *v, loff_t *pos)
913 {
914 struct fib_route_iter *iter = seq->private;
915 - struct leaf *l = v;
916 + struct tnode *l = v;
917
918 ++*pos;
919 if (v == SEQ_START_TOKEN) {
920 @@ -2494,7 +2452,7 @@ static unsigned int fib_flag_trans(int t
921 */
922 static int fib_route_seq_show(struct seq_file *seq, void *v)
923 {
924 - struct leaf *l = v;
925 + struct tnode *l = v;
926 struct leaf_info *li;
927
928 if (v == SEQ_START_TOKEN) {