target/linux/generic/patches-3.18/080-04-fib_trie-Merge-tnode_free-and-leaf_free-into-node_fr.patch

   1 From: Alexander Duyck <alexander.h.duyck@redhat.com>
   2 Date: Wed, 31 Dec 2014 10:55:41 -0800
   3 Subject: [PATCH] fib_trie: Merge tnode_free and leaf_free into node_free
   4
   5 Both the leaf and the tnode had an rcu_head in them, but they had them in
   6 slightly different places.  Since we now have them in the same spot and
   7 know that any node with bits == 0 is a leaf and the rest are either vmalloc
   8 or kmalloc tnodes depending on the value of bits it makes it easy to combine
   9 the functions and reduce overhead.
  10
  11 In addition I have taken advantage of the rcu_head pointer to go ahead and
  12 put together a simple linked list instead of using the tnode pointer as
  13 this way we can merge either type of structure for freeing.
  14
  15 Signed-off-by: Alexander Duyck <alexander.h.duyck@redhat.com>
  16 Signed-off-by: David S. Miller <davem@davemloft.net>
  17 ---
  18
  19 --- a/net/ipv4/fib_trie.c
  20 +++ b/net/ipv4/fib_trie.c
  21 @@ -95,15 +95,17 @@ struct tnode {
  22         unsigned char bits;             /* 2log(KEYLENGTH) bits needed */
  23         unsigned char pos;              /* 2log(KEYLENGTH) bits needed */
  24         struct tnode __rcu *parent;
  25 -       union {
  26 -               struct rcu_head rcu;
  27 -               struct tnode *tnode_free;
  28 -       };
  29 +       struct rcu_head rcu;
  30 +       /* everything above this comment must be the same as rt_trie_node */
  31         unsigned int full_children;     /* KEYLENGTH bits needed */
  32         unsigned int empty_children;    /* KEYLENGTH bits needed */
  33         struct rt_trie_node __rcu *child[0];
  34  };
  35
  36 +/* This struct represents the shared bits between tnode and leaf.  If any
  37 + * ordering is changed here is must also be updated in tnode and leaf as
  38 + * well.
  39 + */
  40  struct rt_trie_node {
  41         t_key key;
  42         unsigned char bits;
  43 @@ -118,6 +120,7 @@ struct leaf {
  44         unsigned char pos;
  45         struct tnode __rcu *parent;
  46         struct rcu_head rcu;
  47 +       /* everything above this comment must be the same as rt_trie_node */
  48         struct hlist_head list;
  49  };
  50
  51 @@ -163,7 +166,7 @@ static struct rt_trie_node *resize(struc
  52  static struct tnode *inflate(struct trie *t, struct tnode *tn);
  53  static struct tnode *halve(struct trie *t, struct tnode *tn);
  54  /* tnodes to free after resize(); protected by RTNL */
  55 -static struct tnode *tnode_free_head;
  56 +static struct callback_head *tnode_free_head;
  57  static size_t tnode_free_size;
  58
  59  /*
  60 @@ -336,17 +339,23 @@ static inline void alias_free_mem_rcu(st
  61         call_rcu(&fa->rcu, __alias_free_mem);
  62  }
  63
  64 -static void __leaf_free_rcu(struct rcu_head *head)
  65 -{
  66 -       struct leaf *l = container_of(head, struct leaf, rcu);
  67 -       kmem_cache_free(trie_leaf_kmem, l);
  68 -}
  69 +#define TNODE_KMALLOC_MAX \
  70 +       ilog2((PAGE_SIZE - sizeof(struct tnode)) / sizeof(struct rt_trie_node *))
  71
  72 -static inline void free_leaf(struct leaf *l)
  73 +static void __node_free_rcu(struct rcu_head *head)
  74  {
  75 -       call_rcu(&l->rcu, __leaf_free_rcu);
  76 +       struct rt_trie_node *n = container_of(head, struct rt_trie_node, rcu);
  77 +
  78 +       if (IS_LEAF(n))
  79 +               kmem_cache_free(trie_leaf_kmem, n);
  80 +       else if (n->bits <= TNODE_KMALLOC_MAX)
  81 +               kfree(n);
  82 +       else
  83 +               vfree(n);
  84  }
  85
  86 +#define node_free(n) call_rcu(&n->rcu, __node_free_rcu)
  87 +
  88  static inline void free_leaf_info(struct leaf_info *leaf)
  89  {
  90         kfree_rcu(leaf, rcu);
  91 @@ -360,43 +369,24 @@ static struct tnode *tnode_alloc(size_t
  92                 return vzalloc(size);
  93  }
  94
  95 -static void __tnode_free_rcu(struct rcu_head *head)
  96 -{
  97 -       struct tnode *tn = container_of(head, struct tnode, rcu);
  98 -       size_t size = sizeof(struct tnode) +
  99 -                     (sizeof(struct rt_trie_node *) << tn->bits);
 100 -
 101 -       if (size <= PAGE_SIZE)
 102 -               kfree(tn);
 103 -       else
 104 -               vfree(tn);
 105 -}
 106 -
 107 -static inline void tnode_free(struct tnode *tn)
 108 -{
 109 -       if (IS_LEAF(tn))
 110 -               free_leaf((struct leaf *) tn);
 111 -       else
 112 -               call_rcu(&tn->rcu, __tnode_free_rcu);
 113 -}
 114 -
 115  static void tnode_free_safe(struct tnode *tn)
 116  {
 117         BUG_ON(IS_LEAF(tn));
 118 -       tn->tnode_free = tnode_free_head;
 119 -       tnode_free_head = tn;
 120 -       tnode_free_size += sizeof(struct tnode) +
 121 -                          (sizeof(struct rt_trie_node *) << tn->bits);
 122 +       tn->rcu.next = tnode_free_head;
 123 +       tnode_free_head = &tn->rcu;
 124  }
 125
 126  static void tnode_free_flush(void)
 127  {
 128 -       struct tnode *tn;
 129 +       struct callback_head *head;
 130 +
 131 +       while ((head = tnode_free_head)) {
 132 +               struct tnode *tn = container_of(head, struct tnode, rcu);
 133 +
 134 +               tnode_free_head = head->next;
 135 +               tnode_free_size += offsetof(struct tnode, child[1 << tn->bits]);
 136
 137 -       while ((tn = tnode_free_head)) {
 138 -               tnode_free_head = tn->tnode_free;
 139 -               tn->tnode_free = NULL;
 140 -               tnode_free(tn);
 141 +               node_free(tn);
 142         }
 143
 144         if (tnode_free_size >= PAGE_SIZE * sync_pages) {
 145 @@ -437,7 +427,7 @@ static struct leaf_info *leaf_info_new(i
 146
 147  static struct tnode *tnode_new(t_key key, int pos, int bits)
 148  {
 149 -       size_t sz = sizeof(struct tnode) + (sizeof(struct rt_trie_node *) << bits);
 150 +       size_t sz = offsetof(struct tnode, child[1 << bits]);
 151         struct tnode *tn = tnode_alloc(sz);
 152         unsigned int shift = pos + bits;
 153
 154 @@ -666,15 +656,15 @@ no_children:
 155
 156  static void tnode_clean_free(struct tnode *tn)
 157  {
 158 +       struct rt_trie_node *tofree;
 159         int i;
 160 -       struct tnode *tofree;
 161
 162         for (i = 0; i < tnode_child_length(tn); i++) {
 163 -               tofree = (struct tnode *)rtnl_dereference(tn->child[i]);
 164 +               tofree = rtnl_dereference(tn->child[i]);
 165                 if (tofree)
 166 -                       tnode_free(tofree);
 167 +                       node_free(tofree);
 168         }
 169 -       tnode_free(tn);
 170 +       node_free(tn);
 171  }
 172
 173  static struct tnode *inflate(struct trie *t, struct tnode *tn)
 174 @@ -717,7 +707,7 @@ static struct tnode *inflate(struct trie
 175                                           inode->bits - 1);
 176
 177                         if (!right) {
 178 -                               tnode_free(left);
 179 +                               node_free(left);
 180                                 goto nomem;
 181                         }
 182
 183 @@ -1068,7 +1058,7 @@ static struct list_head *fib_insert_node
 184         li = leaf_info_new(plen);
 185
 186         if (!li) {
 187 -               free_leaf(l);
 188 +               node_free(l);
 189                 return NULL;
 190         }
 191
 192 @@ -1100,7 +1090,7 @@ static struct list_head *fib_insert_node
 193
 194                 if (!tn) {
 195                         free_leaf_info(li);
 196 -                       free_leaf(l);
 197 +                       node_free(l);
 198                         return NULL;
 199                 }
 200
 201 @@ -1580,7 +1570,7 @@ static void trie_leaf_remove(struct trie
 202         } else
 203                 RCU_INIT_POINTER(t->trie, NULL);
 204
 205 -       free_leaf(l);
 206 +       node_free(l);
 207  }
 208
 209  /*