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 static int lockdep_nfnl_lock_is_held(void)
 157 {
 158         return lockdep_nfnl_is_held(NFNL_SUBSYS_NFTABLES);
 159 }
 160
 161 static int nft_hash_init(const struct nft_set *set,
 162                          const struct nft_set_desc *desc,
 163                          const struct nlattr * const tb[])
 164 {
 165         struct rhashtable *priv = nft_set_priv(set);
 166         struct rhashtable_params params = {
 167                 .nelem_hint = desc->size ? : NFT_HASH_ELEMENT_HINT,
 168                 .head_offset = offsetof(struct nft_hash_elem, node),
 169                 .key_offset = offsetof(struct nft_hash_elem, key),
 170                 .key_len = set->klen,
 171                 .hashfn = jhash,
 172                 .grow_decision = rht_grow_above_75,
 173                 .shrink_decision = rht_shrink_below_30,
 174                 .mutex_is_held = lockdep_nfnl_lock_is_held,
 175         };
 176
 177         return rhashtable_init(priv, &params);
 178 }
 179
 180 static void nft_hash_destroy(const struct nft_set *set)
 181 {
 182         const struct rhashtable *priv = nft_set_priv(set);
 183         const struct bucket_table *tbl = priv->tbl;
 184         struct nft_hash_elem *he, *next;
 185         unsigned int i;
 186
 187         for (i = 0; i < tbl->size; i++) {
 188                 for (he = rht_entry(tbl->buckets[i], struct nft_hash_elem, node);
 189                      he != NULL; he = next) {
 190                         next = rht_entry(he->node.next, struct nft_hash_elem, node);
 191                         nft_hash_elem_destroy(set, he);
 192                 }
 193         }
 194         rhashtable_destroy(priv);
 195 }
 196
 197 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 198                               struct nft_set_estimate *est)
 199 {
 200         unsigned int esize;
 201
 202         esize = sizeof(struct nft_hash_elem);
 203         if (features & NFT_SET_MAP)
 204                 esize += FIELD_SIZEOF(struct nft_hash_elem, data[0]);
 205
 206         if (desc->size) {
 207                 est->size = sizeof(struct rhashtable) +
 208                             roundup_pow_of_two(desc->size * 4 / 3) *
 209                             sizeof(struct nft_hash_elem *) +
 210                             desc->size * esize;
 211         } else {
 212                 /* Resizing happens when the load drops below 30% or goes
 213                  * above 75%. The average of 52.5% load (approximated by 50%)
 214                  * is used for the size estimation of the hash buckets,
 215                  * meaning we calculate two buckets per element.
 216                  */
 217                 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
 218         }
 219
 220         est->class = NFT_SET_CLASS_O_1;
 221
 222         return true;
 223 }
 224
 225 static struct nft_set_ops nft_hash_ops __read_mostly = {
 226         .privsize       = nft_hash_privsize,
 227         .estimate       = nft_hash_estimate,
 228         .init           = nft_hash_init,
 229         .destroy        = nft_hash_destroy,
 230         .get            = nft_hash_get,
 231         .insert         = nft_hash_insert,
 232         .remove         = nft_hash_remove,
 233         .lookup         = nft_hash_lookup,
 234         .walk           = nft_hash_walk,
 235         .features       = NFT_SET_MAP,
 236         .owner          = THIS_MODULE,
 237 };
 238
 239 static int __init nft_hash_module_init(void)
 240 {
 241         return nft_register_set(&nft_hash_ops);
 242 }
 243
 244 static void __exit nft_hash_module_exit(void)
 245 {
 246         nft_unregister_set(&nft_hash_ops);
 247 }
 248
 249 module_init(nft_hash_module_init);
 250 module_exit(nft_hash_module_exit);
 251
 252 MODULE_LICENSE("GPL");
 253 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 254 MODULE_ALIAS_NFT_SET();