1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
2 Date: Thu, 22 Jan 2015 15:51:14 -0800
3 Subject: [PATCH] fib_trie: Fix RCU bug and merge similar bits of inflate/halve
5 This patch addresses two issues.
7 The first issue is the fact that I believe I had the RCU freeing sequence
8 slightly out of order. As a result we could get into an issue if a caller
9 went into a child of a child of the new node, then backtraced into the to be
10 freed parent, and then attempted to access a child of a child that may have
11 been consumed in a resize of one of the new nodes children. To resolve this I
12 have moved the resize after we have freed the oldtnode. The only side effect
13 of this is that we will now be calling resize on more nodes in the case of
14 inflate due to the fact that we don't have a good way to test to see if a
15 full_tnode on the new node was there before or after the allocation. This
16 should have minimal impact however since the node should already be
17 correctly size so it is just the cost of calling should_inflate that we
18 will be taking on the node which is only a couple of cycles.
20 The second issue is the fact that inflate and halve were essentially doing
21 the same thing after the new node was added to the trie replacing the old
22 one. As such it wasn't really necessary to keep the code in both functions
23 so I have split it out into two other functions, called replace and
26 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
27 Signed-off-by: David S. Miller <davem@davemloft.net>
30 --- a/net/ipv4/fib_trie.c
31 +++ b/net/ipv4/fib_trie.c
32 @@ -396,8 +396,30 @@ static void put_child(struct tnode *tn,
33 rcu_assign_pointer(tn->child[i], n);
36 -static void put_child_root(struct tnode *tp, struct trie *t,
37 - t_key key, struct tnode *n)
38 +static void update_children(struct tnode *tn)
42 + /* update all of the child parent pointers */
43 + for (i = tnode_child_length(tn); i;) {
44 + struct tnode *inode = tnode_get_child(tn, --i);
49 + /* Either update the children of a tnode that
50 + * already belongs to us or update the child
51 + * to point to ourselves.
53 + if (node_parent(inode) == tn)
54 + update_children(inode);
56 + node_set_parent(inode, tn);
60 +static inline void put_child_root(struct tnode *tp, struct trie *t,
61 + t_key key, struct tnode *n)
64 put_child(tp, get_index(key, tp), n);
65 @@ -434,10 +456,35 @@ static void tnode_free(struct tnode *tn)
69 +static void replace(struct trie *t, struct tnode *oldtnode, struct tnode *tn)
71 + struct tnode *tp = node_parent(oldtnode);
74 + /* setup the parent pointer out of and back into this node */
75 + NODE_INIT_PARENT(tn, tp);
76 + put_child_root(tp, t, tn->key, tn);
78 + /* update all of the child parent pointers */
79 + update_children(tn);
81 + /* all pointers should be clean so we are done */
82 + tnode_free(oldtnode);
84 + /* resize children now that oldtnode is freed */
85 + for (i = tnode_child_length(tn); i;) {
86 + struct tnode *inode = tnode_get_child(tn, --i);
88 + /* resize child node */
89 + if (tnode_full(tn, inode))
94 static int inflate(struct trie *t, struct tnode *oldtnode)
96 - struct tnode *inode, *node0, *node1, *tn, *tp;
97 - unsigned long i, j, k;
102 pr_debug("In inflate\n");
103 @@ -446,13 +493,18 @@ static int inflate(struct trie *t, struc
107 + /* prepare oldtnode to be freed */
108 + tnode_free_init(oldtnode);
110 /* Assemble all of the pointers in our cluster, in this case that
111 * represents all of the pointers out of our allocated nodes that
112 * point to existing tnodes and the links between our allocated
115 for (i = tnode_child_length(oldtnode), m = 1u << tn->pos; i;) {
116 - inode = tnode_get_child(oldtnode, --i);
117 + struct tnode *inode = tnode_get_child(oldtnode, --i);
118 + struct tnode *node0, *node1;
119 + unsigned long j, k;
123 @@ -464,6 +516,9 @@ static int inflate(struct trie *t, struc
127 + /* drop the node in the old tnode free list */
128 + tnode_free_append(oldtnode, inode);
130 /* An internal node with two children */
131 if (inode->bits == 1) {
132 put_child(tn, 2 * i + 1, tnode_get_child(inode, 1));
133 @@ -488,9 +543,9 @@ static int inflate(struct trie *t, struc
134 node1 = tnode_new(inode->key | m, inode->pos, inode->bits - 1);
137 - tnode_free_append(tn, node1);
138 + node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
140 - node0 = tnode_new(inode->key & ~m, inode->pos, inode->bits - 1);
141 + tnode_free_append(tn, node1);
144 tnode_free_append(tn, node0);
145 @@ -512,53 +567,9 @@ static int inflate(struct trie *t, struc
146 put_child(tn, 2 * i, node0);
149 - /* setup the parent pointer into and out of this node */
150 - tp = node_parent(oldtnode);
151 - NODE_INIT_PARENT(tn, tp);
152 - put_child_root(tp, t, tn->key, tn);
153 + /* setup the parent pointers into and out of this node */
154 + replace(t, oldtnode, tn);
156 - /* prepare oldtnode to be freed */
157 - tnode_free_init(oldtnode);
159 - /* update all child nodes parent pointers to route to us */
160 - for (i = tnode_child_length(oldtnode); i;) {
161 - inode = tnode_get_child(oldtnode, --i);
163 - /* A leaf or an internal node with skipped bits */
164 - if (!tnode_full(oldtnode, inode)) {
165 - node_set_parent(inode, tn);
169 - /* drop the node in the old tnode free list */
170 - tnode_free_append(oldtnode, inode);
172 - /* fetch new nodes */
173 - node1 = tnode_get_child(tn, 2 * i + 1);
174 - node0 = tnode_get_child(tn, 2 * i);
176 - /* bits == 1 then node0 and node1 represent inode's children */
177 - if (inode->bits == 1) {
178 - node_set_parent(node1, tn);
179 - node_set_parent(node0, tn);
183 - /* update parent pointers in child node's children */
184 - for (k = tnode_child_length(inode), j = k / 2; j;) {
185 - node_set_parent(tnode_get_child(inode, --k), node1);
186 - node_set_parent(tnode_get_child(inode, --j), node0);
187 - node_set_parent(tnode_get_child(inode, --k), node1);
188 - node_set_parent(tnode_get_child(inode, --j), node0);
191 - /* resize child nodes */
196 - /* we completed without error, prepare to free old node */
197 - tnode_free(oldtnode);
200 /* all pointers should be clean so we are done */
201 @@ -568,7 +579,7 @@ nomem:
203 static int halve(struct trie *t, struct tnode *oldtnode)
205 - struct tnode *tn, *tp, *inode, *node0, *node1;
209 pr_debug("In halve\n");
210 @@ -577,14 +588,18 @@ static int halve(struct trie *t, struct
214 + /* prepare oldtnode to be freed */
215 + tnode_free_init(oldtnode);
217 /* Assemble all of the pointers in our cluster, in this case that
218 * represents all of the pointers out of our allocated nodes that
219 * point to existing tnodes and the links between our allocated
222 for (i = tnode_child_length(oldtnode); i;) {
223 - node1 = tnode_get_child(oldtnode, --i);
224 - node0 = tnode_get_child(oldtnode, --i);
225 + struct tnode *node1 = tnode_get_child(oldtnode, --i);
226 + struct tnode *node0 = tnode_get_child(oldtnode, --i);
227 + struct tnode *inode;
229 /* At least one of the children is empty */
230 if (!node1 || !node0) {
231 @@ -609,34 +624,8 @@ static int halve(struct trie *t, struct
232 put_child(tn, i / 2, inode);
235 - /* setup the parent pointer out of and back into this node */
236 - tp = node_parent(oldtnode);
237 - NODE_INIT_PARENT(tn, tp);
238 - put_child_root(tp, t, tn->key, tn);
240 - /* prepare oldtnode to be freed */
241 - tnode_free_init(oldtnode);
243 - /* update all of the child parent pointers */
244 - for (i = tnode_child_length(tn); i;) {
245 - inode = tnode_get_child(tn, --i);
247 - /* only new tnodes will be considered "full" nodes */
248 - if (!tnode_full(tn, inode)) {
249 - node_set_parent(inode, tn);
253 - /* Two nonempty children */
254 - node_set_parent(tnode_get_child(inode, 1), inode);
255 - node_set_parent(tnode_get_child(inode, 0), inode);
257 - /* resize child node */
261 - /* all pointers should be clean so we are done */
262 - tnode_free(oldtnode);
263 + /* setup the parent pointers into and out of this node */
264 + replace(t, oldtnode, tn);