target/linux/generic/patches-3.18/080-20-fib_trie-Fix-RCU-bug-and-merge-similar-bits-of-infla.patch

   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
   4
   5 This patch addresses two issues.
   6
   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.
  19
  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
  24 update_children.
  25
  26 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  27 Signed-off-by: David S. Miller <davem@davemloft.net>
  28 ---
  29
  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);
  34  }
  35
  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)
  39 +{
  40 +       unsigned long i;
  41 +
  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);
  45 +
  46 +               if (!inode)
  47 +                       continue;
  48 +
  49 +               /* Either update the children of a tnode that
  50 +                * already belongs to us or update the child
  51 +                * to point to ourselves.
  52 +                */
  53 +               if (node_parent(inode) == tn)
  54 +                       update_children(inode);
  55 +               else
  56 +                       node_set_parent(inode, tn);
  57 +       }
  58 +}
  59 +
  60 +static inline void put_child_root(struct tnode *tp, struct trie *t,
  61 +                                 t_key key, struct tnode *n)
  62  {
  63         if (tp)
  64                 put_child(tp, get_index(key, tp), n);
  65 @@ -434,10 +456,35 @@ static void tnode_free(struct tnode *tn)
  66         }
  67  }
  68
  69 +static void replace(struct trie *t, struct tnode *oldtnode, struct tnode *tn)
  70 +{
  71 +       struct tnode *tp = node_parent(oldtnode);
  72 +       unsigned long i;
  73 +
  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);
  77 +
  78 +       /* update all of the child parent pointers */
  79 +       update_children(tn);
  80 +
  81 +       /* all pointers should be clean so we are done */
  82 +       tnode_free(oldtnode);
  83 +
  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);
  87 +
  88 +               /* resize child node */
  89 +               if (tnode_full(tn, inode))
  90 +                       resize(t, inode);
  91 +       }
  92 +}
  93 +
  94  static int inflate(struct trie *t, struct tnode *oldtnode)
  95  {
  96 -       struct tnode *inode, *node0, *node1, *tn, *tp;
  97 -       unsigned long i, j, k;
  98 +       struct tnode *tn;
  99 +       unsigned long i;
 100         t_key m;
 101
 102         pr_debug("In inflate\n");
 103 @@ -446,13 +493,18 @@ static int inflate(struct trie *t, struc
 104         if (!tn)
 105                 return -ENOMEM;
 106
 107 +       /* prepare oldtnode to be freed */
 108 +       tnode_free_init(oldtnode);
 109 +
 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
 113          * nodes.
 114          */
 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;
 120
 121                 /* An empty child */
 122                 if (inode == NULL)
 123 @@ -464,6 +516,9 @@ static int inflate(struct trie *t, struc
 124                         continue;
 125                 }
 126
 127 +               /* drop the node in the old tnode free list */
 128 +               tnode_free_append(oldtnode, inode);
 129 +
 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);
 135                 if (!node1)
 136                         goto nomem;
 137 -               tnode_free_append(tn, node1);
 138 +               node0 = tnode_new(inode->key, inode->pos, inode->bits - 1);
 139
 140 -               node0 = tnode_new(inode->key & ~m, inode->pos, inode->bits - 1);
 141 +               tnode_free_append(tn, node1);
 142                 if (!node0)
 143                         goto nomem;
 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);
 147         }
 148
 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);
 155
 156 -       /* prepare oldtnode to be freed */
 157 -       tnode_free_init(oldtnode);
 158 -
 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);
 162 -
 163 -               /* A leaf or an internal node with skipped bits */
 164 -               if (!tnode_full(oldtnode, inode)) {
 165 -                       node_set_parent(inode, tn);
 166 -                       continue;
 167 -               }
 168 -
 169 -               /* drop the node in the old tnode free list */
 170 -               tnode_free_append(oldtnode, inode);
 171 -
 172 -               /* fetch new nodes */
 173 -               node1 = tnode_get_child(tn, 2 * i + 1);
 174 -               node0 = tnode_get_child(tn, 2 * i);
 175 -
 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);
 180 -                       continue;
 181 -               }
 182 -
 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);
 189 -               }
 190 -
 191 -               /* resize child nodes */
 192 -               resize(t, node1);
 193 -               resize(t, node0);
 194 -       }
 195 -
 196 -       /* we completed without error, prepare to free old node */
 197 -       tnode_free(oldtnode);
 198         return 0;
 199  nomem:
 200         /* all pointers should be clean so we are done */
 201 @@ -568,7 +579,7 @@ nomem:
 202
 203  static int halve(struct trie *t, struct tnode *oldtnode)
 204  {
 205 -       struct tnode *tn, *tp, *inode, *node0, *node1;
 206 +       struct tnode *tn;
 207         unsigned long i;
 208
 209         pr_debug("In halve\n");
 210 @@ -577,14 +588,18 @@ static int halve(struct trie *t, struct
 211         if (!tn)
 212                 return -ENOMEM;
 213
 214 +       /* prepare oldtnode to be freed */
 215 +       tnode_free_init(oldtnode);
 216 +
 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
 220          * nodes.
 221          */
 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;
 228
 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);
 233         }
 234
 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);
 239 -
 240 -       /* prepare oldtnode to be freed */
 241 -       tnode_free_init(oldtnode);
 242 -
 243 -       /* update all of the child parent pointers */
 244 -       for (i = tnode_child_length(tn); i;) {
 245 -               inode = tnode_get_child(tn, --i);
 246 -
 247 -               /* only new tnodes will be considered "full" nodes */
 248 -               if (!tnode_full(tn, inode)) {
 249 -                       node_set_parent(inode, tn);
 250 -                       continue;
 251 -               }
 252 -
 253 -               /* Two nonempty children */
 254 -               node_set_parent(tnode_get_child(inode, 1), inode);
 255 -               node_set_parent(tnode_get_child(inode, 0), inode);
 256 -
 257 -               /* resize child node */
 258 -               resize(t, inode);
 259 -       }
 260 -
 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);
 265
 266         return 0;
 267  }