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         const 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, GFP_KERNEL);
  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         struct rhash_head *he, __rcu **pprev;
  87
  88         pprev = elem->cookie;
  89         he = rht_dereference((*pprev), priv);
  90
  91         rhashtable_remove_pprev(priv, he, pprev, GFP_KERNEL);
  92
  93         synchronize_rcu();
  94         kfree(he);
  95 }
  96
  97 static int nft_hash_get(const struct nft_set *set, struct nft_set_elem *elem)
  98 {
  99         const struct rhashtable *priv = nft_set_priv(set);
 100         const struct bucket_table *tbl = rht_dereference_rcu(priv->tbl, priv);
 101         struct rhash_head __rcu * const *pprev;
 102         struct nft_hash_elem *he;
 103         u32 h;
 104
 105         h = rhashtable_hashfn(priv, &elem->key, set->klen);
 106         pprev = &tbl->buckets[h];
 107         rht_for_each_entry_rcu(he, tbl->buckets[h], node) {
 108                 if (nft_data_cmp(&he->key, &elem->key, set->klen)) {
 109                         pprev = &he->node.next;
 110                         continue;
 111                 }
 112
 113                 elem->cookie = (void *)pprev;
 114                 elem->flags = 0;
 115                 if (set->flags & NFT_SET_MAP)
 116                         nft_data_copy(&elem->data, he->data);
 117                 return 0;
 118         }
 119         return -ENOENT;
 120 }
 121
 122 static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
 123                           struct nft_set_iter *iter)
 124 {
 125         const struct rhashtable *priv = nft_set_priv(set);
 126         const struct bucket_table *tbl;
 127         const struct nft_hash_elem *he;
 128         struct nft_set_elem elem;
 129         unsigned int i;
 130
 131         tbl = rht_dereference_rcu(priv->tbl, priv);
 132         for (i = 0; i < tbl->size; i++) {
 133                 rht_for_each_entry_rcu(he, tbl->buckets[i], node) {
 134                         if (iter->count < iter->skip)
 135                                 goto cont;
 136
 137                         memcpy(&elem.key, &he->key, sizeof(elem.key));
 138                         if (set->flags & NFT_SET_MAP)
 139                                 memcpy(&elem.data, he->data, sizeof(elem.data));
 140                         elem.flags = 0;
 141
 142                         iter->err = iter->fn(ctx, set, iter, &elem);
 143                         if (iter->err < 0)
 144                                 return;
 145 cont:
 146                         iter->count++;
 147                 }
 148         }
 149 }
 150
 151 static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
 152 {
 153         return sizeof(struct rhashtable);
 154 }
 155
 156 #ifdef CONFIG_PROVE_LOCKING
 157 static int lockdep_nfnl_lock_is_held(void)
 158 {
 159         return lockdep_nfnl_is_held(NFNL_SUBSYS_NFTABLES);
 160 }
 161 #endif
 162
 163 static int nft_hash_init(const struct nft_set *set,
 164                          const struct nft_set_desc *desc,
 165                          const struct nlattr * const tb[])
 166 {
 167         struct rhashtable *priv = nft_set_priv(set);
 168         struct rhashtable_params params = {
 169                 .nelem_hint = desc->size ? : NFT_HASH_ELEMENT_HINT,
 170                 .head_offset = offsetof(struct nft_hash_elem, node),
 171                 .key_offset = offsetof(struct nft_hash_elem, key),
 172                 .key_len = set->klen,
 173                 .hashfn = jhash,
 174                 .grow_decision = rht_grow_above_75,
 175                 .shrink_decision = rht_shrink_below_30,
 176 #ifdef CONFIG_PROVE_LOCKING
 177                 .mutex_is_held = lockdep_nfnl_lock_is_held,
 178 #endif
 179         };
 180
 181         return rhashtable_init(priv, &params);
 182 }
 183
 184 static void nft_hash_destroy(const struct nft_set *set)
 185 {
 186         const struct rhashtable *priv = nft_set_priv(set);
 187         const struct bucket_table *tbl = priv->tbl;
 188         struct nft_hash_elem *he, *next;
 189         unsigned int i;
 190
 191         for (i = 0; i < tbl->size; i++) {
 192                 for (he = rht_entry(tbl->buckets[i], struct nft_hash_elem, node);
 193                      he != NULL; he = next) {
 194                         next = rht_entry(he->node.next, struct nft_hash_elem, node);
 195                         nft_hash_elem_destroy(set, he);
 196                 }
 197         }
 198         rhashtable_destroy(priv);
 199 }
 200
 201 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 202                               struct nft_set_estimate *est)
 203 {
 204         unsigned int esize;
 205
 206         esize = sizeof(struct nft_hash_elem);
 207         if (features & NFT_SET_MAP)
 208                 esize += FIELD_SIZEOF(struct nft_hash_elem, data[0]);
 209
 210         if (desc->size) {
 211                 est->size = sizeof(struct rhashtable) +
 212                             roundup_pow_of_two(desc->size * 4 / 3) *
 213                             sizeof(struct nft_hash_elem *) +
 214                             desc->size * esize;
 215         } else {
 216                 /* Resizing happens when the load drops below 30% or goes
 217                  * above 75%. The average of 52.5% load (approximated by 50%)
 218                  * is used for the size estimation of the hash buckets,
 219                  * meaning we calculate two buckets per element.
 220                  */
 221                 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
 222         }
 223
 224         est->class = NFT_SET_CLASS_O_1;
 225
 226         return true;
 227 }
 228
 229 static struct nft_set_ops nft_hash_ops __read_mostly = {
 230         .privsize       = nft_hash_privsize,
 231         .estimate       = nft_hash_estimate,
 232         .init           = nft_hash_init,
 233         .destroy        = nft_hash_destroy,
 234         .get            = nft_hash_get,
 235         .insert         = nft_hash_insert,
 236         .remove         = nft_hash_remove,
 237         .lookup         = nft_hash_lookup,
 238         .walk           = nft_hash_walk,
 239         .features       = NFT_SET_MAP,
 240         .owner          = THIS_MODULE,
 241 };
 242
 243 static int __init nft_hash_module_init(void)
 244 {
 245         return nft_register_set(&nft_hash_ops);
 246 }
 247
 248 static void __exit nft_hash_module_exit(void)
 249 {
 250         nft_unregister_set(&nft_hash_ops);
 251 }
 252
 253 module_init(nft_hash_module_init);
 254 module_exit(nft_hash_module_exit);
 255
 256 MODULE_LICENSE("GPL");
 257 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 258 MODULE_ALIAS_NFT_SET();