net/netfilter/nft_hash.c

   1 /*
   2  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   3  *
   4  * This program is free software; you can redistribute it and/or modify
   5  * it under the terms of the GNU General Public License version 2 as
   6  * published by the Free Software Foundation.
   7  *
   8  * Development of this code funded by Astaro AG (http://www.astaro.com/)
   9  */
  10
  11 #include <linux/kernel.h>
  12 #include <linux/init.h>
  13 #include <linux/module.h>
  14 #include <linux/list.h>
  15 #include <linux/log2.h>
  16 #include <linux/jhash.h>
  17 #include <linux/netlink.h>
  18 #include <linux/rhashtable.h>
  19 #include <linux/netfilter.h>
  20 #include <linux/netfilter/nf_tables.h>
  21 #include <net/netfilter/nf_tables.h>
  22
  23 /* We target a hash table size of 4, element hint is 75% of final size */
  24 #define NFT_HASH_ELEMENT_HINT 3
  25
  26 struct nft_hash_elem {
  27         struct rhash_head               node;
  28         struct nft_data                 key;
  29         struct nft_data                 data[];
  30 };
  31
  32 static bool nft_hash_lookup(const struct nft_set *set,
  33                             const struct nft_data *key,
  34                             struct nft_data *data)
  35 {
  36         struct rhashtable *priv = nft_set_priv(set);
  37         const struct nft_hash_elem *he;
  38
  39         he = rhashtable_lookup(priv, key);
  40         if (he && set->flags & NFT_SET_MAP)
  41                 nft_data_copy(data, he->data);
  42
  43         return !!he;
  44 }
  45
  46 static int nft_hash_insert(const struct nft_set *set,
  47                            const struct nft_set_elem *elem)
  48 {
  49         struct rhashtable *priv = nft_set_priv(set);
  50         struct nft_hash_elem *he;
  51         unsigned int size;
  52
  53         if (elem->flags != 0)
  54                 return -EINVAL;
  55
  56         size = sizeof(*he);
  57         if (set->flags & NFT_SET_MAP)
  58                 size += sizeof(he->data[0]);
  59
  60         he = kzalloc(size, GFP_KERNEL);
  61         if (he == NULL)
  62                 return -ENOMEM;
  63
  64         nft_data_copy(&he->key, &elem->key);
  65         if (set->flags & NFT_SET_MAP)
  66                 nft_data_copy(he->data, &elem->data);
  67
  68         rhashtable_insert(priv, &he->node);
  69
  70         return 0;
  71 }
  72
  73 static void nft_hash_elem_destroy(const struct nft_set *set,
  74                                   struct nft_hash_elem *he)
  75 {
  76         nft_data_uninit(&he->key, NFT_DATA_VALUE);
  77         if (set->flags & NFT_SET_MAP)
  78                 nft_data_uninit(he->data, set->dtype);
  79         kfree(he);
  80 }
  81
  82 static void nft_hash_remove(const struct nft_set *set,
  83                             const struct nft_set_elem *elem)
  84 {
  85         struct rhashtable *priv = nft_set_priv(set);
  86
  87         rhashtable_remove(priv, elem->cookie);
  88         synchronize_rcu();
  89         kfree(elem->cookie);
  90 }
  91
  92 struct nft_compare_arg {
  93         const struct nft_set *set;
  94         struct nft_set_elem *elem;
  95 };
  96
  97 static bool nft_hash_compare(void *ptr, void *arg)
  98 {
  99         struct nft_hash_elem *he = ptr;
 100         struct nft_compare_arg *x = arg;
 101
 102         if (!nft_data_cmp(&he->key, &x->elem->key, x->set->klen)) {
 103                 x->elem->cookie = he;
 104                 x->elem->flags = 0;
 105                 if (x->set->flags & NFT_SET_MAP)
 106                         nft_data_copy(&x->elem->data, he->data);
 107
 108                 return true;
 109         }
 110
 111         return false;
 112 }
 113
 114 static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem)
 115 {
 116         struct rhashtable *priv = nft_set_priv(set);
 117         struct nft_compare_arg arg = {
 118                 .set = set,
 119                 .elem = elem,
 120         };
 121
 122         if (rhashtable_lookup_compare(priv, &elem->key,
 123                                       &nft_hash_compare, &arg))
 124                 return 0;
 125
 126         return -ENOENT;
 127 }
 128
 129 static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
 130                           struct nft_set_iter *iter)
 131 {
 132         struct rhashtable *priv = nft_set_priv(set);
 133         const struct nft_hash_elem *he;
 134         struct rhashtable_iter hti;
 135         struct nft_set_elem elem;
 136         int err;
 137
 138         err = rhashtable_walk_init(priv, &hti);
 139         iter->err = err;
 140         if (err)
 141                 return;
 142
 143         err = rhashtable_walk_start(&hti);
 144         if (err && err != -EAGAIN) {
 145                 iter->err = err;
 146                 goto out;
 147         }
 148
 149         while ((he = rhashtable_walk_next(&hti))) {
 150                 if (IS_ERR(he)) {
 151                         err = PTR_ERR(he);
 152                         if (err != -EAGAIN) {
 153                                 iter->err = err;
 154                                 goto out;
 155                         }
 156                 }
 157
 158                 if (iter->count < iter->skip)
 159                         goto cont;
 160
 161                 memcpy(&elem.key, &he->key, sizeof(elem.key));
 162                 if (set->flags & NFT_SET_MAP)
 163                         memcpy(&elem.data, he->data, sizeof(elem.data));
 164                 elem.flags = 0;
 165
 166                 iter->err = iter->fn(ctx, set, iter, &elem);
 167                 if (iter->err < 0)
 168                         goto out;
 169
 170 cont:
 171                 iter->count++;
 172         }
 173
 174 out:
 175         rhashtable_walk_stop(&hti);
 176         rhashtable_walk_exit(&hti);
 177 }
 178
 179 static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
 180 {
 181         return sizeof(struct rhashtable);
 182 }
 183
 184 static int nft_hash_init(const struct nft_set *set,
 185                          const struct nft_set_desc *desc,
 186                          const struct nlattr * const tb[])
 187 {
 188         struct rhashtable *priv = nft_set_priv(set);
 189         struct rhashtable_params params = {
 190                 .nelem_hint = desc->size ? : NFT_HASH_ELEMENT_HINT,
 191                 .head_offset = offsetof(struct nft_hash_elem, node),
 192                 .key_offset = offsetof(struct nft_hash_elem, key),
 193                 .key_len = set->klen,
 194                 .hashfn = jhash,
 195                 .grow_decision = rht_grow_above_75,
 196                 .shrink_decision = rht_shrink_below_30,
 197         };
 198
 199         return rhashtable_init(priv, &params);
 200 }
 201
 202 static void nft_hash_destroy(const struct nft_set *set)
 203 {
 204         struct rhashtable *priv = nft_set_priv(set);
 205         const struct bucket_table *tbl;
 206         struct nft_hash_elem *he;
 207         struct rhash_head *pos, *next;
 208         unsigned int i;
 209
 210         /* Stop an eventual async resizing */
 211         priv->being_destroyed = true;
 212         mutex_lock(&priv->mutex);
 213
 214         tbl = rht_dereference(priv->tbl, priv);
 215         for (i = 0; i < tbl->size; i++) {
 216                 rht_for_each_entry_safe(he, pos, next, tbl, i, node)
 217                         nft_hash_elem_destroy(set, he);
 218         }
 219         mutex_unlock(&priv->mutex);
 220
 221         rhashtable_destroy(priv);
 222 }
 223
 224 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 225                               struct nft_set_estimate *est)
 226 {
 227         unsigned int esize;
 228
 229         esize = sizeof(struct nft_hash_elem);
 230         if (features & NFT_SET_MAP)
 231                 esize += FIELD_SIZEOF(struct nft_hash_elem, data[0]);
 232
 233         if (desc->size) {
 234                 est->size = sizeof(struct rhashtable) +
 235                             roundup_pow_of_two(desc->size * 4 / 3) *
 236                             sizeof(struct nft_hash_elem *) +
 237                             desc->size * esize;
 238         } else {
 239                 /* Resizing happens when the load drops below 30% or goes
 240                  * above 75%. The average of 52.5% load (approximated by 50%)
 241                  * is used for the size estimation of the hash buckets,
 242                  * meaning we calculate two buckets per element.
 243                  */
 244                 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
 245         }
 246
 247         est->class = NFT_SET_CLASS_O_1;
 248
 249         return true;
 250 }
 251
 252 static struct nft_set_ops nft_hash_ops __read_mostly = {
 253         .privsize       = nft_hash_privsize,
 254         .estimate       = nft_hash_estimate,
 255         .init           = nft_hash_init,
 256         .destroy        = nft_hash_destroy,
 257         .get            = nft_hash_get,
 258         .insert         = nft_hash_insert,
 259         .remove         = nft_hash_remove,
 260         .lookup         = nft_hash_lookup,
 261         .walk           = nft_hash_walk,
 262         .features       = NFT_SET_MAP,
 263         .owner          = THIS_MODULE,
 264 };
 265
 266 static int __init nft_hash_module_init(void)
 267 {
 268         return nft_register_set(&nft_hash_ops);
 269 }
 270
 271 static void __exit nft_hash_module_exit(void)
 272 {
 273         nft_unregister_set(&nft_hash_ops);
 274 }
 275
 276 module_init(nft_hash_module_init);
 277 module_exit(nft_hash_module_exit);
 278
 279 MODULE_LICENSE("GPL");
 280 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 281 MODULE_ALIAS_NFT_SET();