aboutsummaryrefslogtreecommitdiffstats
path: root/net
diff options
context:
space:
mode:
authorStephen Hemminger <shemminger@linux-foundation.org>2007-08-10 18:22:13 -0400
committerDavid S. Miller <davem@sunset.davemloft.net>2007-10-10 19:48:01 -0400
commit0680191642c27c81c9be4557d9c6aa3487c15f69 (patch)
treef855b0f46b006be011cc720c343e3484c4b63825 /net
parent13dae426318aae073028a4b3bd493104a991e800 (diff)
[IPV4] fib_trie: cleanup
Try this out: * replace macro's with inlines * get rid of places doing multiple evaluations of NODE_PARENT [akpm@linux-foundation.org: rcu_dereference wants an lval] Signed-off-by: Andrew Morton <akpm@linux-foundation.org> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net')
-rw-r--r--net/ipv4/fib_trie.c68
1 files changed, 36 insertions, 32 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index 9ca786a6fd3c..f28f9f5f240c 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -93,15 +93,8 @@ typedef unsigned int t_key;
93#define T_TNODE 0 93#define T_TNODE 0
94#define T_LEAF 1 94#define T_LEAF 1
95#define NODE_TYPE_MASK 0x1UL 95#define NODE_TYPE_MASK 0x1UL
96#define NODE_PARENT(node) \
97 ((struct tnode *)rcu_dereference(((node)->parent & ~NODE_TYPE_MASK)))
98
99#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK) 96#define NODE_TYPE(node) ((node)->parent & NODE_TYPE_MASK)
100 97
101#define NODE_SET_PARENT(node, ptr) \
102 rcu_assign_pointer((node)->parent, \
103 ((unsigned long)(ptr)) | NODE_TYPE(node))
104
105#define IS_TNODE(n) (!(n->parent & T_LEAF)) 98#define IS_TNODE(n) (!(n->parent & T_LEAF))
106#define IS_LEAF(n) (n->parent & T_LEAF) 99#define IS_LEAF(n) (n->parent & T_LEAF)
107 100
@@ -174,6 +167,19 @@ static void tnode_free(struct tnode *tn);
174static struct kmem_cache *fn_alias_kmem __read_mostly; 167static struct kmem_cache *fn_alias_kmem __read_mostly;
175static struct trie *trie_local = NULL, *trie_main = NULL; 168static struct trie *trie_local = NULL, *trie_main = NULL;
176 169
170static inline struct tnode *node_parent(struct node *node)
171{
172 struct tnode *ret;
173
174 ret = (struct tnode *)(node->parent & ~NODE_TYPE_MASK);
175 return rcu_dereference(ret);
176}
177
178static inline void node_set_parent(struct node *node, struct tnode *ptr)
179{
180 rcu_assign_pointer(node->parent,
181 (unsigned long)ptr | NODE_TYPE(node));
182}
177 183
178/* rcu_read_lock needs to be hold by caller from readside */ 184/* rcu_read_lock needs to be hold by caller from readside */
179 185
@@ -446,7 +452,7 @@ static void tnode_put_child_reorg(struct tnode *tn, int i, struct node *n, int w
446 tn->full_children++; 452 tn->full_children++;
447 453
448 if (n) 454 if (n)
449 NODE_SET_PARENT(n, tn); 455 node_set_parent(n, tn);
450 456
451 rcu_assign_pointer(tn->child[i], n); 457 rcu_assign_pointer(tn->child[i], n);
452} 458}
@@ -481,7 +487,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
481 continue; 487 continue;
482 488
483 /* compress one level */ 489 /* compress one level */
484 NODE_SET_PARENT(n, NULL); 490 node_set_parent(n, NULL);
485 tnode_free(tn); 491 tnode_free(tn);
486 return n; 492 return n;
487 } 493 }
@@ -636,7 +642,7 @@ static struct node *resize(struct trie *t, struct tnode *tn)
636 642
637 /* compress one level */ 643 /* compress one level */
638 644
639 NODE_SET_PARENT(n, NULL); 645 node_set_parent(n, NULL);
640 tnode_free(tn); 646 tnode_free(tn);
641 return n; 647 return n;
642 } 648 }
@@ -961,24 +967,21 @@ fib_find_node(struct trie *t, u32 key)
961static struct node *trie_rebalance(struct trie *t, struct tnode *tn) 967static struct node *trie_rebalance(struct trie *t, struct tnode *tn)
962{ 968{
963 int wasfull; 969 int wasfull;
964 t_key cindex, key; 970 t_key cindex, key = tn->key;
965 struct tnode *tp = NULL; 971 struct tnode *tp;
966
967 key = tn->key;
968 972
969 while (tn != NULL && NODE_PARENT(tn) != NULL) { 973 while (tn != NULL && (tp = node_parent((struct node *)tn)) != NULL) {
970
971 tp = NODE_PARENT(tn);
972 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 974 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
973 wasfull = tnode_full(tp, tnode_get_child(tp, cindex)); 975 wasfull = tnode_full(tp, tnode_get_child(tp, cindex));
974 tn = (struct tnode *) resize (t, (struct tnode *)tn); 976 tn = (struct tnode *) resize (t, (struct tnode *)tn);
975 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull); 977 tnode_put_child_reorg((struct tnode *)tp, cindex,(struct node*)tn, wasfull);
976 978
977 if (!NODE_PARENT(tn)) 979 tp = node_parent((struct node *) tn);
980 if (!tp)
978 break; 981 break;
979 982 tn = tp;
980 tn = NODE_PARENT(tn);
981 } 983 }
984
982 /* Handle last (top) tnode */ 985 /* Handle last (top) tnode */
983 if (IS_TNODE(tn)) 986 if (IS_TNODE(tn))
984 tn = (struct tnode*) resize(t, (struct tnode *)tn); 987 tn = (struct tnode*) resize(t, (struct tnode *)tn);
@@ -1031,7 +1034,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1031 pos = tn->pos + tn->bits; 1034 pos = tn->pos + tn->bits;
1032 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits)); 1035 n = tnode_get_child(tn, tkey_extract_bits(key, tn->pos, tn->bits));
1033 1036
1034 BUG_ON(n && NODE_PARENT(n) != tn); 1037 BUG_ON(n && node_parent(n) != tn);
1035 } else 1038 } else
1036 break; 1039 break;
1037 } 1040 }
@@ -1083,7 +1086,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1083 if (t->trie && n == NULL) { 1086 if (t->trie && n == NULL) {
1084 /* Case 2: n is NULL, and will just insert a new leaf */ 1087 /* Case 2: n is NULL, and will just insert a new leaf */
1085 1088
1086 NODE_SET_PARENT(l, tp); 1089 node_set_parent((struct node *)l, tp);
1087 1090
1088 cindex = tkey_extract_bits(key, tp->pos, tp->bits); 1091 cindex = tkey_extract_bits(key, tp->pos, tp->bits);
1089 put_child(t, (struct tnode *)tp, cindex, (struct node *)l); 1092 put_child(t, (struct tnode *)tp, cindex, (struct node *)l);
@@ -1114,7 +1117,7 @@ fib_insert_node(struct trie *t, int *err, u32 key, int plen)
1114 goto err; 1117 goto err;
1115 } 1118 }
1116 1119
1117 NODE_SET_PARENT(tn, tp); 1120 node_set_parent((struct node *)tn, tp);
1118 1121
1119 missbit = tkey_extract_bits(key, newpos, 1); 1122 missbit = tkey_extract_bits(key, newpos, 1);
1120 put_child(t, tn, missbit, (struct node *)l); 1123 put_child(t, tn, missbit, (struct node *)l);
@@ -1495,12 +1498,13 @@ backtrace:
1495 if (chopped_off <= pn->bits) { 1498 if (chopped_off <= pn->bits) {
1496 cindex &= ~(1 << (chopped_off-1)); 1499 cindex &= ~(1 << (chopped_off-1));
1497 } else { 1500 } else {
1498 if (NODE_PARENT(pn) == NULL) 1501 struct tnode *parent = node_parent((struct node *) pn);
1502 if (!parent)
1499 goto failed; 1503 goto failed;
1500 1504
1501 /* Get Child's index */ 1505 /* Get Child's index */
1502 cindex = tkey_extract_bits(pn->key, NODE_PARENT(pn)->pos, NODE_PARENT(pn)->bits); 1506 cindex = tkey_extract_bits(pn->key, parent->pos, parent->bits);
1503 pn = NODE_PARENT(pn); 1507 pn = parent;
1504 chopped_off = 0; 1508 chopped_off = 0;
1505 1509
1506#ifdef CONFIG_IP_FIB_TRIE_STATS 1510#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -1536,7 +1540,7 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1536 check_tnode(tn); 1540 check_tnode(tn);
1537 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits)); 1541 n = tnode_get_child(tn ,tkey_extract_bits(key, tn->pos, tn->bits));
1538 1542
1539 BUG_ON(n && NODE_PARENT(n) != tn); 1543 BUG_ON(n && node_parent(n) != tn);
1540 } 1544 }
1541 l = (struct leaf *) n; 1545 l = (struct leaf *) n;
1542 1546
@@ -1551,7 +1555,7 @@ static int trie_leaf_remove(struct trie *t, t_key key)
1551 t->revision++; 1555 t->revision++;
1552 t->size--; 1556 t->size--;
1553 1557
1554 tp = NODE_PARENT(n); 1558 tp = node_parent(n);
1555 tnode_free((struct tnode *) n); 1559 tnode_free((struct tnode *) n);
1556 1560
1557 if (tp) { 1561 if (tp) {
@@ -1703,7 +1707,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1703 1707
1704 p = (struct tnode*) trie; /* Start */ 1708 p = (struct tnode*) trie; /* Start */
1705 } else 1709 } else
1706 p = (struct tnode *) NODE_PARENT(c); 1710 p = node_parent(c);
1707 1711
1708 while (p) { 1712 while (p) {
1709 int pos, last; 1713 int pos, last;
@@ -1740,7 +1744,7 @@ static struct leaf *nextleaf(struct trie *t, struct leaf *thisleaf)
1740up: 1744up:
1741 /* No more children go up one step */ 1745 /* No more children go up one step */
1742 c = (struct node *) p; 1746 c = (struct node *) p;
1743 p = (struct tnode *) NODE_PARENT(p); 1747 p = node_parent(c);
1744 } 1748 }
1745 return NULL; /* Ready. Root of trie */ 1749 return NULL; /* Ready. Root of trie */
1746} 1750}
@@ -2043,7 +2047,7 @@ rescan:
2043 } 2047 }
2044 2048
2045 /* Current node exhausted, pop back up */ 2049 /* Current node exhausted, pop back up */
2046 p = NODE_PARENT(tn); 2050 p = node_parent((struct node *)tn);
2047 if (p) { 2051 if (p) {
2048 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1; 2052 cindex = tkey_extract_bits(tn->key, p->pos, p->bits)+1;
2049 tn = p; 2053 tn = p;
@@ -2317,7 +2321,7 @@ static int fib_trie_seq_show(struct seq_file *seq, void *v)
2317 if (v == SEQ_START_TOKEN) 2321 if (v == SEQ_START_TOKEN)
2318 return 0; 2322 return 0;
2319 2323
2320 if (!NODE_PARENT(n)) { 2324 if (!node_parent(n)) {
2321 if (iter->trie == trie_local) 2325 if (iter->trie == trie_local)
2322 seq_puts(seq, "<local>:\n"); 2326 seq_puts(seq, "<local>:\n");
2323 else 2327 else