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 {
  27         struct rhashtable               ht;
  28 };
  29
  30 struct nft_hash_elem {
  31         struct rhash_head               node;
  32         struct nft_set_ext              ext;
  33 };
  34
  35 struct nft_hash_cmp_arg {
  36         const struct nft_set            *set;
  37         const struct nft_data           *key;
  38 };
  39
  40 static const struct rhashtable_params nft_hash_params;
  41
  42 static inline u32 nft_hash_key(const void *data, u32 len, u32 seed)
  43 {
  44         const struct nft_hash_cmp_arg *arg = data;
  45
  46         return jhash(arg->key, len, seed);
  47 }
  48
  49 static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed)
  50 {
  51         const struct nft_hash_elem *he = data;
  52
  53         return jhash(nft_set_ext_key(&he->ext), len, seed);
  54 }
  55
  56 static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg,
  57                                const void *ptr)
  58 {
  59         const struct nft_hash_cmp_arg *x = arg->key;
  60         const struct nft_hash_elem *he = ptr;
  61
  62         if (nft_data_cmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
  63                 return 1;
  64         return 0;
  65 }
  66
  67 static bool nft_hash_lookup(const struct nft_set *set,
  68                             const struct nft_data *key,
  69                             struct nft_data *data)
  70 {
  71         struct nft_hash *priv = nft_set_priv(set);
  72         const struct nft_hash_elem *he;
  73         struct nft_hash_cmp_arg arg = {
  74                 .set     = set,
  75                 .key     = key,
  76         };
  77
  78         he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
  79         if (he && set->flags & NFT_SET_MAP)
  80                 nft_data_copy(data, nft_set_ext_data(&he->ext));
  81
  82         return !!he;
  83 }
  84
  85 static int nft_hash_insert(const struct nft_set *set,
  86                            const struct nft_set_elem *elem)
  87 {
  88         struct nft_hash *priv = nft_set_priv(set);
  89         struct nft_hash_elem *he = elem->priv;
  90         struct nft_hash_cmp_arg arg = {
  91                 .set     = set,
  92                 .key     = &elem->key,
  93         };
  94
  95         return rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node,
  96                                             nft_hash_params);
  97 }
  98
  99 static void nft_hash_elem_destroy(const struct nft_set *set,
 100                                   struct nft_hash_elem *he)
 101 {
 102         nft_data_uninit(nft_set_ext_key(&he->ext), NFT_DATA_VALUE);
 103         if (set->flags & NFT_SET_MAP)
 104                 nft_data_uninit(nft_set_ext_data(&he->ext), set->dtype);
 105         kfree(he);
 106 }
 107
 108 static void nft_hash_remove(const struct nft_set *set,
 109                             const struct nft_set_elem *elem)
 110 {
 111         struct nft_hash *priv = nft_set_priv(set);
 112
 113         rhashtable_remove_fast(&priv->ht, elem->cookie, nft_hash_params);
 114         synchronize_rcu();
 115         kfree(elem->cookie);
 116 }
 117
 118 static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem)
 119 {
 120         struct nft_hash *priv = nft_set_priv(set);
 121         struct nft_hash_elem *he;
 122         struct nft_hash_cmp_arg arg = {
 123                 .set     = set,
 124                 .key     = &elem->key,
 125         };
 126
 127         he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
 128         if (!he)
 129                 return -ENOENT;
 130
 131         elem->priv = he;
 132
 133         return 0;
 134 }
 135
 136 static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
 137                           struct nft_set_iter *iter)
 138 {
 139         struct nft_hash *priv = nft_set_priv(set);
 140         struct nft_hash_elem *he;
 141         struct rhashtable_iter hti;
 142         struct nft_set_elem elem;
 143         int err;
 144
 145         err = rhashtable_walk_init(&priv->ht, &hti);
 146         iter->err = err;
 147         if (err)
 148                 return;
 149
 150         err = rhashtable_walk_start(&hti);
 151         if (err && err != -EAGAIN) {
 152                 iter->err = err;
 153                 goto out;
 154         }
 155
 156         while ((he = rhashtable_walk_next(&hti))) {
 157                 if (IS_ERR(he)) {
 158                         err = PTR_ERR(he);
 159                         if (err != -EAGAIN) {
 160                                 iter->err = err;
 161                                 goto out;
 162                         }
 163
 164                         continue;
 165                 }
 166
 167                 if (iter->count < iter->skip)
 168                         goto cont;
 169
 170                 elem.priv = he;
 171
 172                 iter->err = iter->fn(ctx, set, iter, &elem);
 173                 if (iter->err < 0)
 174                         goto out;
 175
 176 cont:
 177                 iter->count++;
 178         }
 179
 180 out:
 181         rhashtable_walk_stop(&hti);
 182         rhashtable_walk_exit(&hti);
 183 }
 184
 185 static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
 186 {
 187         return sizeof(struct nft_hash);
 188 }
 189
 190 static const struct rhashtable_params nft_hash_params = {
 191         .head_offset            = offsetof(struct nft_hash_elem, node),
 192         .hashfn                 = nft_hash_key,
 193         .obj_hashfn             = nft_hash_obj,
 194         .obj_cmpfn              = nft_hash_cmp,
 195         .automatic_shrinking    = true,
 196 };
 197
 198 static int nft_hash_init(const struct nft_set *set,
 199                          const struct nft_set_desc *desc,
 200                          const struct nlattr * const tb[])
 201 {
 202         struct nft_hash *priv = nft_set_priv(set);
 203         struct rhashtable_params params = nft_hash_params;
 204
 205         params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT;
 206         params.key_len    = set->klen;
 207
 208         return rhashtable_init(&priv->ht, &params);
 209 }
 210
 211 static void nft_free_element(void *ptr, void *arg)
 212 {
 213         nft_hash_elem_destroy((const struct nft_set *)arg, ptr);
 214 }
 215
 216 static void nft_hash_destroy(const struct nft_set *set)
 217 {
 218         struct nft_hash *priv = nft_set_priv(set);
 219
 220         rhashtable_free_and_destroy(&priv->ht, nft_free_element, (void *)set);
 221 }
 222
 223 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 224                               struct nft_set_estimate *est)
 225 {
 226         unsigned int esize;
 227
 228         esize = sizeof(struct nft_hash_elem);
 229         if (desc->size) {
 230                 est->size = sizeof(struct nft_hash) +
 231                             roundup_pow_of_two(desc->size * 4 / 3) *
 232                             sizeof(struct nft_hash_elem *) +
 233                             desc->size * esize;
 234         } else {
 235                 /* Resizing happens when the load drops below 30% or goes
 236                  * above 75%. The average of 52.5% load (approximated by 50%)
 237                  * is used for the size estimation of the hash buckets,
 238                  * meaning we calculate two buckets per element.
 239                  */
 240                 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
 241         }
 242
 243         est->class = NFT_SET_CLASS_O_1;
 244
 245         return true;
 246 }
 247
 248 static struct nft_set_ops nft_hash_ops __read_mostly = {
 249         .privsize       = nft_hash_privsize,
 250         .elemsize       = offsetof(struct nft_hash_elem, ext),
 251         .estimate       = nft_hash_estimate,
 252         .init           = nft_hash_init,
 253         .destroy        = nft_hash_destroy,
 254         .get            = nft_hash_get,
 255         .insert         = nft_hash_insert,
 256         .remove         = nft_hash_remove,
 257         .lookup         = nft_hash_lookup,
 258         .walk           = nft_hash_walk,
 259         .features       = NFT_SET_MAP,
 260         .owner          = THIS_MODULE,
 261 };
 262
 263 static int __init nft_hash_module_init(void)
 264 {
 265         return nft_register_set(&nft_hash_ops);
 266 }
 267
 268 static void __exit nft_hash_module_exit(void)
 269 {
 270         nft_unregister_set(&nft_hash_ops);
 271 }
 272
 273 module_init(nft_hash_module_init);
 274 module_exit(nft_hash_module_exit);
 275
 276 MODULE_LICENSE("GPL");
 277 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 278 MODULE_ALIAS_NFT_SET();