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/workqueue.h>
  19 #include <linux/rhashtable.h>
  20 #include <linux/netfilter.h>
  21 #include <linux/netfilter/nf_tables.h>
  22 #include <net/netfilter/nf_tables.h>
  23
  24 /* We target a hash table size of 4, element hint is 75% of final size */
  25 #define NFT_HASH_ELEMENT_HINT 3
  26
  27 struct nft_hash {
  28         struct rhashtable               ht;
  29         struct delayed_work             gc_work;
  30 };
  31
  32 struct nft_hash_elem {
  33         struct rhash_head               node;
  34         struct nft_set_ext              ext;
  35 };
  36
  37 struct nft_hash_cmp_arg {
  38         const struct nft_set            *set;
  39         const struct nft_data           *key;
  40         u8                              genmask;
  41 };
  42
  43 static const struct rhashtable_params nft_hash_params;
  44
  45 static inline u32 nft_hash_key(const void *data, u32 len, u32 seed)
  46 {
  47         const struct nft_hash_cmp_arg *arg = data;
  48
  49         return jhash(arg->key, len, seed);
  50 }
  51
  52 static inline u32 nft_hash_obj(const void *data, u32 len, u32 seed)
  53 {
  54         const struct nft_hash_elem *he = data;
  55
  56         return jhash(nft_set_ext_key(&he->ext), len, seed);
  57 }
  58
  59 static inline int nft_hash_cmp(struct rhashtable_compare_arg *arg,
  60                                const void *ptr)
  61 {
  62         const struct nft_hash_cmp_arg *x = arg->key;
  63         const struct nft_hash_elem *he = ptr;
  64
  65         if (nft_data_cmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
  66                 return 1;
  67         if (nft_set_elem_expired(&he->ext))
  68                 return 1;
  69         if (!nft_set_elem_active(&he->ext, x->genmask))
  70                 return 1;
  71         return 0;
  72 }
  73
  74 static bool nft_hash_lookup(const struct nft_set *set,
  75                             const struct nft_data *key,
  76                             const struct nft_set_ext **ext)
  77 {
  78         struct nft_hash *priv = nft_set_priv(set);
  79         const struct nft_hash_elem *he;
  80         struct nft_hash_cmp_arg arg = {
  81                 .genmask = nft_genmask_cur(read_pnet(&set->pnet)),
  82                 .set     = set,
  83                 .key     = key,
  84         };
  85
  86         he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
  87         if (he != NULL)
  88                 *ext = &he->ext;
  89
  90         return !!he;
  91 }
  92
  93 static int nft_hash_insert(const struct nft_set *set,
  94                            const struct nft_set_elem *elem)
  95 {
  96         struct nft_hash *priv = nft_set_priv(set);
  97         struct nft_hash_elem *he = elem->priv;
  98         struct nft_hash_cmp_arg arg = {
  99                 .genmask = nft_genmask_next(read_pnet(&set->pnet)),
 100                 .set     = set,
 101                 .key     = &elem->key,
 102         };
 103
 104         return rhashtable_lookup_insert_key(&priv->ht, &arg, &he->node,
 105                                             nft_hash_params);
 106 }
 107
 108 static void nft_hash_activate(const struct nft_set *set,
 109                               const struct nft_set_elem *elem)
 110 {
 111         struct nft_hash_elem *he = elem->priv;
 112
 113         nft_set_elem_change_active(set, &he->ext);
 114         nft_set_elem_clear_busy(&he->ext);
 115 }
 116
 117 static void *nft_hash_deactivate(const struct nft_set *set,
 118                                  const 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                 .genmask = nft_genmask_next(read_pnet(&set->pnet)),
 124                 .set     = set,
 125                 .key     = &elem->key,
 126         };
 127
 128         rcu_read_lock();
 129         he = rhashtable_lookup_fast(&priv->ht, &arg, nft_hash_params);
 130         if (he != NULL) {
 131                 if (!nft_set_elem_mark_busy(&he->ext))
 132                         nft_set_elem_change_active(set, &he->ext);
 133                 else
 134                         he = NULL;
 135         }
 136         rcu_read_unlock();
 137
 138         return he;
 139 }
 140
 141 static void nft_hash_remove(const struct nft_set *set,
 142                             const struct nft_set_elem *elem)
 143 {
 144         struct nft_hash *priv = nft_set_priv(set);
 145         struct nft_hash_elem *he = elem->priv;
 146
 147         rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
 148 }
 149
 150 static void nft_hash_walk(const struct nft_ctx *ctx, const struct nft_set *set,
 151                           struct nft_set_iter *iter)
 152 {
 153         struct nft_hash *priv = nft_set_priv(set);
 154         struct nft_hash_elem *he;
 155         struct rhashtable_iter hti;
 156         struct nft_set_elem elem;
 157         u8 genmask = nft_genmask_cur(read_pnet(&set->pnet));
 158         int err;
 159
 160         err = rhashtable_walk_init(&priv->ht, &hti);
 161         iter->err = err;
 162         if (err)
 163                 return;
 164
 165         err = rhashtable_walk_start(&hti);
 166         if (err && err != -EAGAIN) {
 167                 iter->err = err;
 168                 goto out;
 169         }
 170
 171         while ((he = rhashtable_walk_next(&hti))) {
 172                 if (IS_ERR(he)) {
 173                         err = PTR_ERR(he);
 174                         if (err != -EAGAIN) {
 175                                 iter->err = err;
 176                                 goto out;
 177                         }
 178
 179                         continue;
 180                 }
 181
 182                 if (iter->count < iter->skip)
 183                         goto cont;
 184                 if (nft_set_elem_expired(&he->ext))
 185                         goto cont;
 186                 if (!nft_set_elem_active(&he->ext, genmask))
 187                         goto cont;
 188
 189                 elem.priv = he;
 190
 191                 iter->err = iter->fn(ctx, set, iter, &elem);
 192                 if (iter->err < 0)
 193                         goto out;
 194
 195 cont:
 196                 iter->count++;
 197         }
 198
 199 out:
 200         rhashtable_walk_stop(&hti);
 201         rhashtable_walk_exit(&hti);
 202 }
 203
 204 static void nft_hash_gc(struct work_struct *work)
 205 {
 206         struct nft_set *set;
 207         struct nft_hash_elem *he;
 208         struct nft_hash *priv;
 209         struct nft_set_gc_batch *gcb = NULL;
 210         struct rhashtable_iter hti;
 211         int err;
 212
 213         priv = container_of(work, struct nft_hash, gc_work.work);
 214         set  = nft_set_container_of(priv);
 215
 216         err = rhashtable_walk_init(&priv->ht, &hti);
 217         if (err)
 218                 goto schedule;
 219
 220         err = rhashtable_walk_start(&hti);
 221         if (err && err != -EAGAIN)
 222                 goto out;
 223
 224         while ((he = rhashtable_walk_next(&hti))) {
 225                 if (IS_ERR(he)) {
 226                         if (PTR_ERR(he) != -EAGAIN)
 227                                 goto out;
 228                         continue;
 229                 }
 230
 231                 if (!nft_set_elem_expired(&he->ext))
 232                         continue;
 233                 if (nft_set_elem_mark_busy(&he->ext))
 234                         continue;
 235
 236                 gcb = nft_set_gc_batch_check(set, gcb, GFP_ATOMIC);
 237                 if (gcb == NULL)
 238                         goto out;
 239                 rhashtable_remove_fast(&priv->ht, &he->node, nft_hash_params);
 240                 atomic_dec(&set->nelems);
 241                 nft_set_gc_batch_add(gcb, he);
 242         }
 243 out:
 244         rhashtable_walk_stop(&hti);
 245         rhashtable_walk_exit(&hti);
 246
 247         nft_set_gc_batch_complete(gcb);
 248 schedule:
 249         queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 250                            nft_set_gc_interval(set));
 251 }
 252
 253 static unsigned int nft_hash_privsize(const struct nlattr * const nla[])
 254 {
 255         return sizeof(struct nft_hash);
 256 }
 257
 258 static const struct rhashtable_params nft_hash_params = {
 259         .head_offset            = offsetof(struct nft_hash_elem, node),
 260         .hashfn                 = nft_hash_key,
 261         .obj_hashfn             = nft_hash_obj,
 262         .obj_cmpfn              = nft_hash_cmp,
 263         .automatic_shrinking    = true,
 264 };
 265
 266 static int nft_hash_init(const struct nft_set *set,
 267                          const struct nft_set_desc *desc,
 268                          const struct nlattr * const tb[])
 269 {
 270         struct nft_hash *priv = nft_set_priv(set);
 271         struct rhashtable_params params = nft_hash_params;
 272         int err;
 273
 274         params.nelem_hint = desc->size ?: NFT_HASH_ELEMENT_HINT;
 275         params.key_len    = set->klen;
 276
 277         err = rhashtable_init(&priv->ht, &params);
 278         if (err < 0)
 279                 return err;
 280
 281         INIT_DEFERRABLE_WORK(&priv->gc_work, nft_hash_gc);
 282         if (set->flags & NFT_SET_TIMEOUT)
 283                 queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 284                                    nft_set_gc_interval(set));
 285         return 0;
 286 }
 287
 288 static void nft_hash_elem_destroy(void *ptr, void *arg)
 289 {
 290         nft_set_elem_destroy((const struct nft_set *)arg, ptr);
 291 }
 292
 293 static void nft_hash_destroy(const struct nft_set *set)
 294 {
 295         struct nft_hash *priv = nft_set_priv(set);
 296
 297         cancel_delayed_work_sync(&priv->gc_work);
 298         rhashtable_free_and_destroy(&priv->ht, nft_hash_elem_destroy,
 299                                     (void *)set);
 300 }
 301
 302 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 303                               struct nft_set_estimate *est)
 304 {
 305         unsigned int esize;
 306
 307         esize = sizeof(struct nft_hash_elem);
 308         if (desc->size) {
 309                 est->size = sizeof(struct nft_hash) +
 310                             roundup_pow_of_two(desc->size * 4 / 3) *
 311                             sizeof(struct nft_hash_elem *) +
 312                             desc->size * esize;
 313         } else {
 314                 /* Resizing happens when the load drops below 30% or goes
 315                  * above 75%. The average of 52.5% load (approximated by 50%)
 316                  * is used for the size estimation of the hash buckets,
 317                  * meaning we calculate two buckets per element.
 318                  */
 319                 est->size = esize + 2 * sizeof(struct nft_hash_elem *);
 320         }
 321
 322         est->class = NFT_SET_CLASS_O_1;
 323
 324         return true;
 325 }
 326
 327 static struct nft_set_ops nft_hash_ops __read_mostly = {
 328         .privsize       = nft_hash_privsize,
 329         .elemsize       = offsetof(struct nft_hash_elem, ext),
 330         .estimate       = nft_hash_estimate,
 331         .init           = nft_hash_init,
 332         .destroy        = nft_hash_destroy,
 333         .insert         = nft_hash_insert,
 334         .activate       = nft_hash_activate,
 335         .deactivate     = nft_hash_deactivate,
 336         .remove         = nft_hash_remove,
 337         .lookup         = nft_hash_lookup,
 338         .walk           = nft_hash_walk,
 339         .features       = NFT_SET_MAP | NFT_SET_TIMEOUT,
 340         .owner          = THIS_MODULE,
 341 };
 342
 343 static int __init nft_hash_module_init(void)
 344 {
 345         return nft_register_set(&nft_hash_ops);
 346 }
 347
 348 static void __exit nft_hash_module_exit(void)
 349 {
 350         nft_unregister_set(&nft_hash_ops);
 351 }
 352
 353 module_init(nft_hash_module_init);
 354 module_exit(nft_hash_module_exit);
 355
 356 MODULE_LICENSE("GPL");
 357 MODULE_AUTHOR("Patrick McHardy <kaber@trash.net>");
 358 MODULE_ALIAS_NFT_SET();