target/linux/generic/patches-3.18/080-22-fib_trie-Add-collapse-and-should_collapse-to-resize.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Thu, 22 Jan 2015 15:51:26 -0800
   3 Subject: [PATCH] fib_trie: Add collapse() and should_collapse() to resize
   4
   5 This patch really does two things.
   6
   7 First it pulls the logic for determining if we should collapse one node out
   8 of the tree and the actual code doing the collapse into a separate pair of
   9 functions.  This helps to make the changes to these areas more readable.
  10
  11 Second it encodes the upper 32b of the empty_children value onto the
  12 full_children value in the case of bits == KEYLENGTH.  By doing this we are
  13 able to handle the case of a 32b node where empty_children would appear to
  14 be 0 when it was actually 1ul << 32.
  15
  16 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  17 Signed-off-by: David S. Miller <davem@davemloft.net>
  18 ---
  19
  20 --- a/net/ipv4/fib_trie.c
  21 +++ b/net/ipv4/fib_trie.c
  22 @@ -83,7 +83,8 @@
  23
  24  #define MAX_STAT_DEPTH 32
  25
  26 -#define KEYLENGTH (8*sizeof(t_key))
  27 +#define KEYLENGTH      (8*sizeof(t_key))
  28 +#define KEY_MAX                ((t_key)~0)
  29
  30  typedef unsigned int t_key;
  31
  32 @@ -102,8 +103,8 @@ struct tnode {
  33         union {
  34                 /* The fields in this struct are valid if bits > 0 (TNODE) */
  35                 struct {
  36 -                       unsigned int full_children;  /* KEYLENGTH bits needed */
  37 -                       unsigned int empty_children; /* KEYLENGTH bits needed */
  38 +                       t_key empty_children; /* KEYLENGTH bits needed */
  39 +                       t_key full_children;  /* KEYLENGTH bits needed */
  40                         struct tnode __rcu *child[0];
  41                 };
  42                 /* This list pointer if valid if bits == 0 (LEAF) */
  43 @@ -302,6 +303,16 @@ static struct tnode *tnode_alloc(size_t
  44                 return vzalloc(size);
  45  }
  46
  47 +static inline void empty_child_inc(struct tnode *n)
  48 +{
  49 +       ++n->empty_children ? : ++n->full_children;
  50 +}
  51 +
  52 +static inline void empty_child_dec(struct tnode *n)
  53 +{
  54 +       n->empty_children-- ? : n->full_children--;
  55 +}
  56 +
  57  static struct tnode *leaf_new(t_key key)
  58  {
  59         struct tnode *l = kmem_cache_alloc(trie_leaf_kmem, GFP_KERNEL);
  60 @@ -335,7 +346,7 @@ static struct leaf_info *leaf_info_new(i
  61
  62  static struct tnode *tnode_new(t_key key, int pos, int bits)
  63  {
  64 -       size_t sz = offsetof(struct tnode, child[1 << bits]);
  65 +       size_t sz = offsetof(struct tnode, child[1ul << bits]);
  66         struct tnode *tn = tnode_alloc(sz);
  67         unsigned int shift = pos + bits;
  68
  69 @@ -348,8 +359,10 @@ static struct tnode *tnode_new(t_key key
  70                 tn->pos = pos;
  71                 tn->bits = bits;
  72                 tn->key = (shift < KEYLENGTH) ? (key >> shift) << shift : 0;
  73 -               tn->full_children = 0;
  74 -               tn->empty_children = 1<<bits;
  75 +               if (bits == KEYLENGTH)
  76 +                       tn->full_children = 1;
  77 +               else
  78 +                       tn->empty_children = 1ul << bits;
  79         }
  80
  81         pr_debug("AT %p s=%zu %zu\n", tn, sizeof(struct tnode),
  82 @@ -375,11 +388,11 @@ static void put_child(struct tnode *tn,
  83
  84         BUG_ON(i >= tnode_child_length(tn));
  85
  86 -       /* update emptyChildren */
  87 +       /* update emptyChildren, overflow into fullChildren */
  88         if (n == NULL && chi != NULL)
  89 -               tn->empty_children++;
  90 -       else if (n != NULL && chi == NULL)
  91 -               tn->empty_children--;
  92 +               empty_child_inc(tn);
  93 +       if (n != NULL && chi == NULL)
  94 +               empty_child_dec(tn);
  95
  96         /* update fullChildren */
  97         wasfull = tnode_full(tn, chi);
  98 @@ -630,6 +643,24 @@ static int halve(struct trie *t, struct
  99         return 0;
 100  }
 101
 102 +static void collapse(struct trie *t, struct tnode *oldtnode)
 103 +{
 104 +       struct tnode *n, *tp;
 105 +       unsigned long i;
 106 +
 107 +       /* scan the tnode looking for that one child that might still exist */
 108 +       for (n = NULL, i = tnode_child_length(oldtnode); !n && i;)
 109 +               n = tnode_get_child(oldtnode, --i);
 110 +
 111 +       /* compress one level */
 112 +       tp = node_parent(oldtnode);
 113 +       put_child_root(tp, t, oldtnode->key, n);
 114 +       node_set_parent(n, tp);
 115 +
 116 +       /* drop dead node */
 117 +       node_free(oldtnode);
 118 +}
 119 +
 120  static unsigned char update_suffix(struct tnode *tn)
 121  {
 122         unsigned char slen = tn->pos;
 123 @@ -729,10 +760,12 @@ static bool should_inflate(const struct
 124
 125         /* Keep root node larger */
 126         threshold *= tp ? inflate_threshold : inflate_threshold_root;
 127 -       used += tn->full_children;
 128         used -= tn->empty_children;
 129 +       used += tn->full_children;
 130
 131 -       return tn->pos && ((50 * used) >= threshold);
 132 +       /* if bits == KEYLENGTH then pos = 0, and will fail below */
 133 +
 134 +       return (used > 1) && tn->pos && ((50 * used) >= threshold);
 135  }
 136
 137  static bool should_halve(const struct tnode *tp, const struct tnode *tn)
 138 @@ -744,13 +777,29 @@ static bool should_halve(const struct tn
 139         threshold *= tp ? halve_threshold : halve_threshold_root;
 140         used -= tn->empty_children;
 141
 142 -       return (tn->bits > 1) && ((100 * used) < threshold);
 143 +       /* if bits == KEYLENGTH then used = 100% on wrap, and will fail below */
 144 +
 145 +       return (used > 1) && (tn->bits > 1) && ((100 * used) < threshold);
 146 +}
 147 +
 148 +static bool should_collapse(const struct tnode *tn)
 149 +{
 150 +       unsigned long used = tnode_child_length(tn);
 151 +
 152 +       used -= tn->empty_children;
 153 +
 154 +       /* account for bits == KEYLENGTH case */
 155 +       if ((tn->bits == KEYLENGTH) && tn->full_children)
 156 +               used -= KEY_MAX;
 157 +
 158 +       /* One child or none, time to drop us from the trie */
 159 +       return used < 2;
 160  }
 161
 162  #define MAX_WORK 10
 163  static void resize(struct trie *t, struct tnode *tn)
 164  {
 165 -       struct tnode *tp = node_parent(tn), *n = NULL;
 166 +       struct tnode *tp = node_parent(tn);
 167         struct tnode __rcu **cptr;
 168         int max_work = MAX_WORK;
 169
 170 @@ -764,14 +813,6 @@ static void resize(struct trie *t, struc
 171         cptr = tp ? &tp->child[get_index(tn->key, tp)] : &t->trie;
 172         BUG_ON(tn != rtnl_dereference(*cptr));
 173
 174 -       /* No children */
 175 -       if (tn->empty_children > (tnode_child_length(tn) - 1))
 176 -               goto no_children;
 177 -
 178 -       /* One child */
 179 -       if (tn->empty_children == (tnode_child_length(tn) - 1))
 180 -               goto one_child;
 181 -
 182         /* Double as long as the resulting node has a number of
 183          * nonempty nodes that are above the threshold.
 184          */
 185 @@ -807,19 +848,8 @@ static void resize(struct trie *t, struc
 186         }
 187
 188         /* Only one child remains */
 189 -       if (tn->empty_children == (tnode_child_length(tn) - 1)) {
 190 -               unsigned long i;
 191 -one_child:
 192 -               for (i = tnode_child_length(tn); !n && i;)
 193 -                       n = tnode_get_child(tn, --i);
 194 -no_children:
 195 -               /* compress one level */
 196 -               put_child_root(tp, t, tn->key, n);
 197 -               node_set_parent(n, tp);
 198 -
 199 -               /* drop dead node */
 200 -               tnode_free_init(tn);
 201 -               tnode_free(tn);
 202 +       if (should_collapse(tn)) {
 203 +               collapse(t, tn);
 204                 return;
 205         }
 206