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
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
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.
15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
16 Signed-off-by: David S. Miller <davem@davemloft.net>
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;
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];
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
35 -struct rt_trie_node {
39 - struct tnode __rcu *parent;
40 - struct rcu_head rcu;
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;
52 + /* The fields in this struct are valid if bits > 0 (TNODE) */
54 + unsigned int full_children; /* KEYLENGTH bits needed */
55 + unsigned int empty_children; /* KEYLENGTH bits needed */
56 + struct tnode __rcu *child[0];
58 + /* This list pointer if valid if bits == 0 (LEAF) */
59 + struct hlist_head list;
64 @@ -154,15 +138,15 @@ struct trie_stat {
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;
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,
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)
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)
91 - rcu_assign_pointer(node->parent, ptr);
93 + rcu_assign_pointer(n->parent, tp);
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
99 * caller must hold RTNL
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)
104 BUG_ON(i >= tnode_child_length(tn));
106 @@ -215,7 +199,7 @@ static inline struct rt_trie_node *tnode
108 * caller must hold RCU read lock or RTNL
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)
113 BUG_ON(i >= tnode_child_length(tn));
115 @@ -340,11 +324,11 @@ static inline void alias_free_mem_rcu(st
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 *))
122 static void __node_free_rcu(struct rcu_head *head)
124 - struct rt_trie_node *n = container_of(head, struct rt_trie_node, rcu);
125 + struct tnode *n = container_of(head, struct tnode, rcu);
128 kmem_cache_free(trie_leaf_kmem, n);
129 @@ -395,9 +379,9 @@ static void tnode_free_flush(void)
133 -static struct leaf *leaf_new(t_key key)
134 +static struct tnode *leaf_new(t_key key)
136 - struct leaf *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
137 + struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
140 /* set key and pos to reflect full key value
141 @@ -444,7 +428,7 @@ static struct tnode *tnode_new(t_key key
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);
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
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)
157 return n && IS_TNODE(n) && (n->pos == (tn->pos + tn->bits));
160 static inline void put_child(struct tnode *tn, int i,
161 - struct rt_trie_node *n)
164 tnode_put_child_reorg(tn, i, n, -1);
166 @@ -469,10 +453,10 @@ static inline void put_child(struct tnod
167 * Update the value of full_children and empty_children.
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,
174 - struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
175 + struct tnode *chi = rtnl_dereference(tn->child[i]);
178 BUG_ON(i >= 1<<tn->bits);
179 @@ -499,10 +483,9 @@ static void tnode_put_child_reorg(struct
183 -static struct rt_trie_node *resize(struct trie *t, struct tnode *tn)
184 +static struct tnode *resize(struct trie *t, struct tnode *tn)
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;
192 @@ -614,7 +597,7 @@ static struct rt_trie_node *resize(struc
194 /* Return if at least one inflate is run */
195 if (max_work != MAX_WORK)
196 - return (struct rt_trie_node *) tn;
200 * Halve as long as the number of empty children in this
201 @@ -650,13 +633,13 @@ no_children:
205 - return (struct rt_trie_node *) tn;
210 static void tnode_clean_free(struct tnode *tn)
212 - struct rt_trie_node *tofree;
213 + struct tnode *tofree;
216 for (i = 0; i < tnode_child_length(tn); i++) {
217 @@ -667,10 +650,10 @@ static void tnode_clean_free(struct tnod
221 -static struct tnode *inflate(struct trie *t, struct tnode *tn)
222 +static struct tnode *inflate(struct trie *t, struct tnode *oldtnode)
224 - struct tnode *oldtnode = tn;
225 - int olen = tnode_child_length(tn);
226 + int olen = tnode_child_length(oldtnode);
230 pr_debug("In inflate\n");
231 @@ -690,11 +673,8 @@ static struct tnode *inflate(struct trie
232 for (i = 0; i < olen; i++) {
235 - inode = (struct tnode *) tnode_get_child(oldtnode, i);
238 - inode->pos == oldtnode->pos + oldtnode->bits &&
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;
245 @@ -711,33 +691,29 @@ static struct tnode *inflate(struct trie
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);
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;
268 /* A leaf or an internal node with skipped bits */
270 - if (IS_LEAF(node) || (node->pos > (tn->pos + tn->bits - 1))) {
271 + if (!tnode_full(oldtnode, inode)) {
273 - tkey_extract_bits(node->key, oldtnode->pos, oldtnode->bits + 1),
275 + tkey_extract_bits(inode->key, tn->pos, tn->bits),
280 /* An internal node with two children */
281 - inode = (struct tnode *) node;
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
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);
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);
301 @@ -796,12 +772,11 @@ nomem:
302 return ERR_PTR(-ENOMEM);
305 -static struct tnode *halve(struct trie *t, struct tnode *tn)
306 +static struct tnode *halve(struct trie *t, struct tnode *oldtnode)
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;
313 - int olen = tnode_child_length(tn);
315 pr_debug("In halve\n");
317 @@ -830,7 +805,7 @@ static struct tnode *halve(struct trie *
321 - put_child(tn, i/2, (struct rt_trie_node *)newn);
322 + put_child(tn, i/2, newn);
326 @@ -855,7 +830,7 @@ static struct tnode *halve(struct trie *
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 */
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)
342 struct hlist_head *head = &l->list;
343 struct leaf_info *li;
344 @@ -883,7 +858,7 @@ static struct leaf_info *find_leaf_info(
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)
351 struct leaf_info *li = find_leaf_info(l, plen);
353 @@ -915,32 +890,25 @@ static void insert_leaf_info(struct hlis
355 /* rcu_read_lock needs to be hold by caller from readside */
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)
363 - struct rt_trie_node *n;
366 - n = rcu_dereference_rtnl(t->trie);
367 + struct tnode *n = rcu_dereference_rtnl(t->trie);
370 while (n && IS_TNODE(n)) {
371 - tn = (struct tnode *) n;
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,
387 /* Case we have found a leaf. Compare prefixes */
389 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key))
390 - return (struct leaf *)n;
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);
402 - tnode_put_child_reorg(tp, cindex,
403 - (struct rt_trie_node *)tn, wasfull);
404 + tnode_put_child_reorg(tp, cindex, tn, wasfull);
406 tp = node_parent(tn);
408 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
409 + rcu_assign_pointer(t->trie, tn);
413 @@ -973,9 +940,9 @@ static void trie_rebalance(struct trie *
415 /* Handle last (top) tnode */
417 - tn = (struct tnode *)resize(t, tn);
418 + tn = resize(t, tn);
420 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
421 + rcu_assign_pointer(t->trie, tn);
425 @@ -985,8 +952,8 @@ static struct list_head *fib_insert_node
428 struct tnode *tp = NULL, *tn = NULL;
429 - struct rt_trie_node *n;
434 struct list_head *fa_head = NULL;
435 struct leaf_info *li;
436 @@ -1014,17 +981,15 @@ static struct list_head *fib_insert_node
439 while (n && IS_TNODE(n)) {
440 - tn = (struct tnode *) n;
442 - if (tkey_sub_equals(tn->key, pos, tn->pos-pos, key)) {
444 - pos = tn->pos + tn->bits;
445 - n = tnode_get_child(tn,
446 + if (tkey_sub_equals(n->key, pos, n->pos-pos, key)) {
448 + pos = n->pos + n->bits;
449 + n = tnode_get_child(n,
450 tkey_extract_bits(key,
456 - BUG_ON(n && node_parent(n) != tn);
457 + BUG_ON(n && node_parent(n) != tp);
461 @@ -1040,14 +1005,13 @@ static struct list_head *fib_insert_node
462 /* Case 1: n is a leaf. Compare prefixes */
464 if (n != NULL && IS_LEAF(n) && tkey_equals(key, n->key)) {
465 - l = (struct leaf *) n;
466 li = leaf_info_new(plen);
472 - insert_leaf_info(&l->list, li);
473 + insert_leaf_info(&n->list, li);
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 */
481 - node_set_parent((struct rt_trie_node *)l, tp);
482 + node_set_parent(l, tp);
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);
488 /* Case 3: n is a LEAF or a TNODE and the key doesn't match. */
490 @@ -1094,17 +1058,17 @@ static struct list_head *fib_insert_node
494 - node_set_parent((struct rt_trie_node *)tn, tp);
495 + node_set_parent(tn, tp);
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);
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);
507 - rcu_assign_pointer(t->trie, (struct rt_trie_node *)tn);
508 + rcu_assign_pointer(t->trie, tn);
512 @@ -1134,7 +1098,7 @@ int fib_table_insert(struct fib_table *t
513 u8 tos = cfg->fc_tos;
521 @@ -1292,7 +1256,7 @@ err:
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)
530 @@ -1365,7 +1329,7 @@ int fib_table_lookup(struct fib_table *t
531 struct trie_use_stats __percpu *stats = t->stats;
534 - struct rt_trie_node *n;
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
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);
548 - pn = (struct tnode *) n;
553 @@ -1412,13 +1376,13 @@ int fib_table_lookup(struct fib_table *t
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);
564 - cn = (struct tnode *)n;
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;
573 - pn = (struct tnode *)n; /* Descend */
574 + pn = n; /* Descend */
578 @@ -1557,7 +1521,7 @@ EXPORT_SYMBOL_GPL(fib_table_lookup);
580 * Remove the leaf and return parent.
582 -static void trie_leaf_remove(struct trie *t, struct leaf *l)
583 +static void trie_leaf_remove(struct trie *t, struct tnode *l)
585 struct tnode *tp = node_parent(l);
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;
593 struct leaf_info *li;
596 @@ -1682,7 +1646,7 @@ static int trie_flush_list(struct list_h
600 -static int trie_flush_leaf(struct leaf *l)
601 +static int trie_flush_leaf(struct tnode *l)
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.
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)
614 @@ -1720,47 +1684,46 @@ static struct leaf *leaf_walk_rcu(struct
618 - return (struct leaf *) c;
621 /* Rescan start scanning in new node */
622 - p = (struct tnode *) c;
627 /* Node empty, walk back up to parent */
628 - c = (struct rt_trie_node *) p;
630 } while ((p = node_parent_rcu(c)) != NULL);
632 return NULL; /* Root of trie */
635 -static struct leaf *trie_firstleaf(struct trie *t)
636 +static struct tnode *trie_firstleaf(struct trie *t)
638 - struct tnode *n = (struct tnode *)rcu_dereference_rtnl(t->trie);
639 + struct tnode *n = rcu_dereference_rtnl(t->trie);
644 if (IS_LEAF(n)) /* trie is just a leaf */
645 - return (struct leaf *) n;
648 return leaf_walk_rcu(n, NULL);
651 -static struct leaf *trie_nextleaf(struct leaf *l)
652 +static struct tnode *trie_nextleaf(struct tnode *l)
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);
659 return NULL; /* trie with just one leaf */
661 - return leaf_walk_rcu(p, c);
662 + return leaf_walk_rcu(p, l);
665 -static struct leaf *trie_leafindex(struct trie *t, int index)
666 +static struct tnode *trie_leafindex(struct trie *t, int index)
668 - struct leaf *l = trie_firstleaf(t);
669 + struct tnode *l = trie_firstleaf(t);
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)
676 struct trie *t = (struct trie *) tb->tb_data;
677 - struct leaf *l, *ll = NULL;
678 + struct tnode *l, *ll = NULL;
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
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)
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)
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);
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);
709 @@ -1965,7 +1928,7 @@ struct fib_trie_iter {
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)
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);
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);
727 @@ -1987,7 +1950,7 @@ rescan:
728 iter->index = cindex + 1;
730 /* push down one level */
731 - iter->tnode = (struct tnode *) n;
736 @@ -1998,7 +1961,7 @@ rescan:
739 /* Current node exhausted, pop back up */
740 - p = node_parent_rcu((struct rt_trie_node *)tn);
741 + p = node_parent_rcu(tn);
743 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
745 @@ -2010,10 +1973,10 @@ rescan:
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,
753 - struct rt_trie_node *n;
758 @@ -2023,7 +1986,7 @@ static struct rt_trie_node *fib_trie_get
762 - iter->tnode = (struct tnode *) n;
767 @@ -2037,7 +2000,7 @@ static struct rt_trie_node *fib_trie_get
769 static void trie_collect_stats(struct trie *t, struct trie_stat *s)
771 - struct rt_trie_node *n;
773 struct fib_trie_iter iter;
775 memset(s, 0, sizeof(*s));
776 @@ -2045,7 +2008,6 @@ static void trie_collect_stats(struct tr
778 for (n = fib_trie_get_first(&iter, t); n; n = fib_trie_get_next(&iter)) {
780 - struct leaf *l = (struct leaf *)n;
781 struct leaf_info *li;
784 @@ -2053,18 +2015,17 @@ static void trie_collect_stats(struct tr
785 if (iter.depth > s->maxdepth)
786 s->maxdepth = iter.depth;
788 - hlist_for_each_entry_rcu(li, &l->list, hlist)
789 + hlist_for_each_entry_rcu(li, &n->list, hlist)
792 - const struct tnode *tn = (const struct tnode *) n;
796 - if (tn->bits < MAX_STAT_DEPTH)
797 - s->nodesizes[tn->bits]++;
798 + if (n->bits < MAX_STAT_DEPTH)
799 + s->nodesizes[n->bits]++;
801 - for (i = 0; i < (1<<tn->bits); i++)
803 + for (i = 0; i < tnode_child_length(n); i++)
804 + if (!rcu_access_pointer(n->child[i]))
808 @@ -2088,7 +2049,7 @@ static void trie_show_stats(struct seq_f
809 seq_printf(seq, "\tMax depth: %u\n", stat->maxdepth);
811 seq_printf(seq, "\tLeaves: %u\n", stat->leaves);
812 - bytes = sizeof(struct leaf) * stat->leaves;
813 + bytes = sizeof(struct tnode) * stat->leaves;
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
819 seq_printf(seq, "\tPointers: %u\n", pointers);
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);
826 @@ -2163,7 +2124,7 @@ static int fib_triestat_seq_show(struct
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));
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,
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)
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;
847 hlist_for_each_entry_rcu(tb, head, tb_hlist) {
848 - struct rt_trie_node *n;
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;
857 - struct rt_trie_node *n;
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)
865 const struct fib_trie_iter *iter = seq->private;
866 - struct rt_trie_node *n = v;
867 + struct tnode *n = v;
869 if (!node_parent_rcu(n))
870 fib_table_print(seq, iter->tb);
873 - struct tnode *tn = (struct tnode *) n;
874 - __be32 prf = htonl(tn->key);
875 + __be32 prf = htonl(n->key);
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);
883 + &prf, n->pos, n->bits, n->full_children,
884 + n->empty_children);
886 - struct leaf *l = (struct leaf *) n;
887 struct leaf_info *li;
888 - __be32 val = htonl(l->key);
889 + __be32 val = htonl(n->key);
891 seq_indent(seq, iter->depth);
892 seq_printf(seq, " |-- %pI4\n", &val);
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;
898 list_for_each_entry_rcu(fa, &li->falh, fa_list) {
899 @@ -2401,9 +2359,9 @@ struct fib_route_iter {
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)
906 - struct leaf *l = NULL;
907 + struct tnode *l = NULL;
908 struct trie *t = iter->main_trie;
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)
914 struct fib_route_iter *iter = seq->private;
915 - struct leaf *l = v;
916 + struct tnode *l = v;
919 if (v == SEQ_START_TOKEN) {
920 @@ -2494,7 +2452,7 @@ static unsigned int fib_flag_trans(int t
922 static int fib_route_seq_show(struct seq_file *seq, void *v)
924 - struct leaf *l = v;
925 + struct tnode *l = v;
926 struct leaf_info *li;
928 if (v == SEQ_START_TOKEN) {