aboutsummaryrefslogtreecommitdiffstats
path: root/net/ipv4/fib_trie.c
diff options
context:
space:
mode:
authorEric Dumazet <eric.dumazet@gmail.com>2011-03-31 04:51:35 -0400
committerDavid S. Miller <davem@davemloft.net>2011-03-31 04:51:35 -0400
commit0a5c047507aaaf00519921336d19c0f8f5f9f363 (patch)
treed0ba4aaef5ad841a8725079c0624ff184a6c6564 /net/ipv4/fib_trie.c
parentab392d2d6d4e2e50502985eead545b44ee58802c (diff)
fib: add __rcu annotations
Add __rcu annotations and lockdep checks. Add const qualifiers node_parent() and node_parent_rcu() can use rcu_dereference_index_check() Signed-off-by: Eric Dumazet <eric.dumazet@gmail.com> Signed-off-by: David S. Miller <davem@davemloft.net>
Diffstat (limited to 'net/ipv4/fib_trie.c')
-rw-r--r--net/ipv4/fib_trie.c103
1 files changed, 58 insertions, 45 deletions
diff --git a/net/ipv4/fib_trie.c b/net/ipv4/fib_trie.c
index b92c86f6e9b3..b9d1f33e5e04 100644
--- a/net/ipv4/fib_trie.c
+++ b/net/ipv4/fib_trie.c
@@ -126,7 +126,7 @@ struct tnode {
126 struct work_struct work; 126 struct work_struct work;
127 struct tnode *tnode_free; 127 struct tnode *tnode_free;
128 }; 128 };
129 struct rt_trie_node *child[0]; 129 struct rt_trie_node __rcu *child[0];
130}; 130};
131 131
132#ifdef CONFIG_IP_FIB_TRIE_STATS 132#ifdef CONFIG_IP_FIB_TRIE_STATS
@@ -151,7 +151,7 @@ struct trie_stat {
151}; 151};
152 152
153struct trie { 153struct trie {
154 struct rt_trie_node *trie; 154 struct rt_trie_node __rcu *trie;
155#ifdef CONFIG_IP_FIB_TRIE_STATS 155#ifdef CONFIG_IP_FIB_TRIE_STATS
156 struct trie_use_stats stats; 156 struct trie_use_stats stats;
157#endif 157#endif
@@ -177,16 +177,29 @@ static const int sync_pages = 128;
177static struct kmem_cache *fn_alias_kmem __read_mostly; 177static struct kmem_cache *fn_alias_kmem __read_mostly;
178static struct kmem_cache *trie_leaf_kmem __read_mostly; 178static struct kmem_cache *trie_leaf_kmem __read_mostly;
179 179
180static inline struct tnode *node_parent(struct rt_trie_node *node) 180/*
181 * caller must hold RTNL
182 */
183static inline struct tnode *node_parent(const struct rt_trie_node *node)
181{ 184{
182 return (struct tnode *)(node->parent & ~NODE_TYPE_MASK); 185 unsigned long parent;
186
187 parent = rcu_dereference_index_check(node->parent, lockdep_rtnl_is_held());
188
189 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
183} 190}
184 191
185static inline struct tnode *node_parent_rcu(struct rt_trie_node *node) 192/*
193 * caller must hold RCU read lock or RTNL
194 */
195static inline struct tnode *node_parent_rcu(const struct rt_trie_node *node)
186{ 196{
187 struct tnode *ret = node_parent(node); 197 unsigned long parent;
198
199 parent = rcu_dereference_index_check(node->parent, rcu_read_lock_held() ||
200 lockdep_rtnl_is_held());
188 201
189 return rcu_dereference_rtnl(ret); 202 return (struct tnode *)(parent & ~NODE_TYPE_MASK);
190} 203}
191 204
192/* Same as rcu_assign_pointer 205/* Same as rcu_assign_pointer
@@ -198,18 +211,24 @@ static inline void node_set_parent(struct rt_trie_node *node, struct tnode *ptr)
198 node->parent = (unsigned long)ptr | NODE_TYPE(node); 211 node->parent = (unsigned long)ptr | NODE_TYPE(node);
199} 212}
200 213
201static inline struct rt_trie_node *tnode_get_child(struct tnode *tn, unsigned int i) 214/*
215 * caller must hold RTNL
216 */
217static inline struct rt_trie_node *tnode_get_child(const struct tnode *tn, unsigned int i)
202{ 218{
203 BUG_ON(i >= 1U << tn->bits); 219 BUG_ON(i >= 1U << tn->bits);
204 220
205 return tn->child[i]; 221 return rtnl_dereference(tn->child[i]);
206} 222}
207 223
208static inline struct rt_trie_node *tnode_get_child_rcu(struct tnode *tn, unsigned int i) 224/*
225 * caller must hold RCU read lock or RTNL
226 */
227static inline struct rt_trie_node *tnode_get_child_rcu(const struct tnode *tn, unsigned int i)
209{ 228{
210 struct rt_trie_node *ret = tnode_get_child(tn, i); 229 BUG_ON(i >= 1U << tn->bits);
211 230
212 return rcu_dereference_rtnl(ret); 231 return rcu_dereference_rtnl(tn->child[i]);
213} 232}
214 233
215static inline int tnode_child_length(const struct tnode *tn) 234static inline int tnode_child_length(const struct tnode *tn)
@@ -487,7 +506,7 @@ static inline void put_child(struct trie *t, struct tnode *tn, int i,
487static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n, 506static void tnode_put_child_reorg(struct tnode *tn, int i, struct rt_trie_node *n,
488 int wasfull) 507 int wasfull)
489{ 508{
490 struct rt_trie_node *chi = tn->child[i]; 509 struct rt_trie_node *chi = rtnl_dereference(tn->child[i]);
491 int isfull; 510 int isfull;
492 511
493 BUG_ON(i >= 1<<tn->bits); 512 BUG_ON(i >= 1<<tn->bits);
@@ -665,7 +684,7 @@ one_child:
665 for (i = 0; i < tnode_child_length(tn); i++) { 684 for (i = 0; i < tnode_child_length(tn); i++) {
666 struct rt_trie_node *n; 685 struct rt_trie_node *n;
667 686
668 n = tn->child[i]; 687 n = rtnl_dereference(tn->child[i]);
669 if (!n) 688 if (!n)
670 continue; 689 continue;
671 690
@@ -679,6 +698,20 @@ one_child:
679 return (struct rt_trie_node *) tn; 698 return (struct rt_trie_node *) tn;
680} 699}
681 700
701
702static void tnode_clean_free(struct tnode *tn)
703{
704 int i;
705 struct tnode *tofree;
706
707 for (i = 0; i < tnode_child_length(tn); i++) {
708 tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
709 if (tofree)
710 tnode_free(tofree);
711 }
712 tnode_free(tn);
713}
714
682static struct tnode *inflate(struct trie *t, struct tnode *tn) 715static struct tnode *inflate(struct trie *t, struct tnode *tn)
683{ 716{
684 struct tnode *oldtnode = tn; 717 struct tnode *oldtnode = tn;
@@ -755,8 +788,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn)
755 inode = (struct tnode *) node; 788 inode = (struct tnode *) node;
756 789
757 if (inode->bits == 1) { 790 if (inode->bits == 1) {
758 put_child(t, tn, 2*i, inode->child[0]); 791 put_child(t, tn, 2*i, rtnl_dereference(inode->child[0]));
759 put_child(t, tn, 2*i+1, inode->child[1]); 792 put_child(t, tn, 2*i+1, rtnl_dereference(inode->child[1]));
760 793
761 tnode_free_safe(inode); 794 tnode_free_safe(inode);
762 continue; 795 continue;
@@ -797,8 +830,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn)
797 830
798 size = tnode_child_length(left); 831 size = tnode_child_length(left);
799 for (j = 0; j < size; j++) { 832 for (j = 0; j < size; j++) {
800 put_child(t, left, j, inode->child[j]); 833 put_child(t, left, j, rtnl_dereference(inode->child[j]));
801 put_child(t, right, j, inode->child[j + size]); 834 put_child(t, right, j, rtnl_dereference(inode->child[j + size]));
802 } 835 }
803 put_child(t, tn, 2*i, resize(t, left)); 836 put_child(t, tn, 2*i, resize(t, left));
804 put_child(t, tn, 2*i+1, resize(t, right)); 837 put_child(t, tn, 2*i+1, resize(t, right));
@@ -808,18 +841,8 @@ static struct tnode *inflate(struct trie *t, struct tnode *tn)
808 tnode_free_safe(oldtnode); 841 tnode_free_safe(oldtnode);
809 return tn; 842 return tn;
810nomem: 843nomem:
811 { 844 tnode_clean_free(tn);
812 int size = tnode_child_length(tn); 845 return ERR_PTR(-ENOMEM);
813 int j;
814
815 for (j = 0; j < size; j++)
816 if (tn->child[j])
817 tnode_free((struct tnode *)tn->child[j]);
818
819 tnode_free(tn);
820
821 return ERR_PTR(-ENOMEM);
822 }
823} 846}
824 847
825static struct tnode *halve(struct trie *t, struct tnode *tn) 848static struct tnode *halve(struct trie *t, struct tnode *tn)
@@ -890,18 +913,8 @@ static struct tnode *halve(struct trie *t, struct tnode *tn)
890 tnode_free_safe(oldtnode); 913 tnode_free_safe(oldtnode);
891 return tn; 914 return tn;
892nomem: 915nomem:
893 { 916 tnode_clean_free(tn);
894 int size = tnode_child_length(tn); 917 return ERR_PTR(-ENOMEM);
895 int j;
896
897 for (j = 0; j < size; j++)
898 if (tn->child[j])
899 tnode_free((struct tnode *)tn->child[j]);
900
901 tnode_free(tn);
902
903 return ERR_PTR(-ENOMEM);
904 }
905} 918}
906 919
907/* readside must use rcu_read_lock currently dump routines 920/* readside must use rcu_read_lock currently dump routines
@@ -1033,7 +1046,7 @@ static struct list_head *fib_insert_node(struct trie *t, u32 key, int plen)
1033 t_key cindex; 1046 t_key cindex;
1034 1047
1035 pos = 0; 1048 pos = 0;
1036 n = t->trie; 1049 n = rtnl_dereference(t->trie);
1037 1050
1038 /* If we point to NULL, stop. Either the tree is empty and we should 1051 /* If we point to NULL, stop. Either the tree is empty and we should
1039 * just put a new leaf in if, or we have reached an empty child slot, 1052 * just put a new leaf in if, or we have reached an empty child slot,
@@ -1756,7 +1769,7 @@ static struct leaf *leaf_walk_rcu(struct tnode *p, struct rt_trie_node *c)
1756 continue; 1769 continue;
1757 1770
1758 if (IS_LEAF(c)) { 1771 if (IS_LEAF(c)) {
1759 prefetch(p->child[idx]); 1772 prefetch(rcu_dereference_rtnl(p->child[idx]));
1760 return (struct leaf *) c; 1773 return (struct leaf *) c;
1761 } 1774 }
1762 1775
@@ -2272,7 +2285,7 @@ static void *fib_trie_seq_next(struct seq_file *seq, void *v, loff_t *pos)
2272 2285
2273 /* walk rest of this hash chain */ 2286 /* walk rest of this hash chain */
2274 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1); 2287 h = tb->tb_id & (FIB_TABLE_HASHSZ - 1);
2275 while ( (tb_node = rcu_dereference(tb->tb_hlist.next)) ) { 2288 while ((tb_node = rcu_dereference(hlist_next_rcu(&tb->tb_hlist)))) {
2276 tb = hlist_entry(tb_node, struct fib_table, tb_hlist); 2289 tb = hlist_entry(tb_node, struct fib_table, tb_hlist);
2277 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data); 2290 n = fib_trie_get_first(iter, (struct trie *) tb->tb_data);
2278 if (n) 2291 if (n)