net/netfilter/nft_set_hash.c

   1 // SPDX-License-Identifier: GPL-2.0-only
   2 /*
   3  * Copyright (c) 2008-2014 Patrick McHardy <kaber@trash.net>
   4  *
   5  * Development of this code funded by Astaro AG (http://www.astaro.com/)
   6  */
   7
   8 #include <linux/kernel.h>
   9 #include <linux/init.h>
  10 #include <linux/module.h>
  11 #include <linux/list.h>
  12 #include <linux/log2.h>
  13 #include <linux/jhash.h>
  14 #include <linux/netlink.h>
  15 #include <linux/workqueue.h>
  16 #include <linux/rhashtable.h>
  17 #include <linux/netfilter.h>
  18 #include <linux/netfilter/nf_tables.h>
  19 #include <net/netfilter/nf_tables_core.h>
  20
  21 /* We target a hash table size of 4, element hint is 75% of final size */
  22 #define NFT_RHASH_ELEMENT_HINT 3
  23
  24 struct nft_rhash {
  25         struct rhashtable               ht;
  26         struct delayed_work             gc_work;
  27 };
  28
  29 struct nft_rhash_elem {
  30         struct nft_elem_priv            priv;
  31         struct rhash_head               node;
  32         struct nft_set_ext              ext;
  33 };
  34
  35 struct nft_rhash_cmp_arg {
  36         const struct nft_set            *set;
  37         const u32                       *key;
  38         u8                              genmask;
  39 };
  40
  41 static inline u32 nft_rhash_key(const void *data, u32 len, u32 seed)
  42 {
  43         const struct nft_rhash_cmp_arg *arg = data;
  44
  45         return jhash(arg->key, len, seed);
  46 }
  47
  48 static inline u32 nft_rhash_obj(const void *data, u32 len, u32 seed)
  49 {
  50         const struct nft_rhash_elem *he = data;
  51
  52         return jhash(nft_set_ext_key(&he->ext), len, seed);
  53 }
  54
  55 static inline int nft_rhash_cmp(struct rhashtable_compare_arg *arg,
  56                                 const void *ptr)
  57 {
  58         const struct nft_rhash_cmp_arg *x = arg->key;
  59         const struct nft_rhash_elem *he = ptr;
  60
  61         if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
  62                 return 1;
  63         if (nft_set_elem_is_dead(&he->ext))
  64                 return 1;
  65         if (nft_set_elem_expired(&he->ext))
  66                 return 1;
  67         if (!nft_set_elem_active(&he->ext, x->genmask))
  68                 return 1;
  69         return 0;
  70 }
  71
  72 static const struct rhashtable_params nft_rhash_params = {
  73         .head_offset            = offsetof(struct nft_rhash_elem, node),
  74         .hashfn                 = nft_rhash_key,
  75         .obj_hashfn             = nft_rhash_obj,
  76         .obj_cmpfn              = nft_rhash_cmp,
  77         .automatic_shrinking    = true,
  78 };
  79
  80 INDIRECT_CALLABLE_SCOPE
  81 bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
  82                       const u32 *key, const struct nft_set_ext **ext)
  83 {
  84         struct nft_rhash *priv = nft_set_priv(set);
  85         const struct nft_rhash_elem *he;
  86         struct nft_rhash_cmp_arg arg = {
  87                 .genmask = nft_genmask_cur(net),
  88                 .set     = set,
  89                 .key     = key,
  90         };
  91
  92         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
  93         if (he != NULL)
  94                 *ext = &he->ext;
  95
  96         return !!he;
  97 }
  98
  99 static struct nft_elem_priv *
 100 nft_rhash_get(const struct net *net, const struct nft_set *set,
 101               const struct nft_set_elem *elem, unsigned int flags)
 102 {
 103         struct nft_rhash *priv = nft_set_priv(set);
 104         struct nft_rhash_elem *he;
 105         struct nft_rhash_cmp_arg arg = {
 106                 .genmask = nft_genmask_cur(net),
 107                 .set     = set,
 108                 .key     = elem->key.val.data,
 109         };
 110
 111         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 112         if (he != NULL)
 113                 return &he->priv;
 114
 115         return ERR_PTR(-ENOENT);
 116 }
 117
 118 static bool nft_rhash_update(struct nft_set *set, const u32 *key,
 119                              struct nft_elem_priv *
 120                                    (*new)(struct nft_set *,
 121                                           const struct nft_expr *,
 122                                           struct nft_regs *regs),
 123                              const struct nft_expr *expr,
 124                              struct nft_regs *regs,
 125                              const struct nft_set_ext **ext)
 126 {
 127         struct nft_rhash *priv = nft_set_priv(set);
 128         struct nft_rhash_elem *he, *prev;
 129         struct nft_elem_priv *elem_priv;
 130         struct nft_rhash_cmp_arg arg = {
 131                 .genmask = NFT_GENMASK_ANY,
 132                 .set     = set,
 133                 .key     = key,
 134         };
 135
 136         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 137         if (he != NULL)
 138                 goto out;
 139
 140         elem_priv = new(set, expr, regs);
 141         if (!elem_priv)
 142                 goto err1;
 143
 144         he = nft_elem_priv_cast(elem_priv);
 145         prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
 146                                                 nft_rhash_params);
 147         if (IS_ERR(prev))
 148                 goto err2;
 149
 150         /* Another cpu may race to insert the element with the same key */
 151         if (prev) {
 152                 nft_set_elem_destroy(set, &he->priv, true);
 153                 atomic_dec(&set->nelems);
 154                 he = prev;
 155         }
 156
 157 out:
 158         *ext = &he->ext;
 159         return true;
 160
 161 err2:
 162         nft_set_elem_destroy(set, &he->priv, true);
 163         atomic_dec(&set->nelems);
 164 err1:
 165         return false;
 166 }
 167
 168 static int nft_rhash_insert(const struct net *net, const struct nft_set *set,
 169                             const struct nft_set_elem *elem,
 170                             struct nft_set_ext **ext)
 171 {
 172         struct nft_rhash_elem *he = nft_elem_priv_cast(elem->priv);
 173         struct nft_rhash *priv = nft_set_priv(set);
 174         struct nft_rhash_cmp_arg arg = {
 175                 .genmask = nft_genmask_next(net),
 176                 .set     = set,
 177                 .key     = elem->key.val.data,
 178         };
 179         struct nft_rhash_elem *prev;
 180
 181         prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
 182                                                 nft_rhash_params);
 183         if (IS_ERR(prev))
 184                 return PTR_ERR(prev);
 185         if (prev) {
 186                 *ext = &prev->ext;
 187                 return -EEXIST;
 188         }
 189         return 0;
 190 }
 191
 192 static void nft_rhash_activate(const struct net *net, const struct nft_set *set,
 193                                struct nft_elem_priv *elem_priv)
 194 {
 195         struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
 196
 197         nft_set_elem_change_active(net, set, &he->ext);
 198 }
 199
 200 static void nft_rhash_flush(const struct net *net,
 201                             const struct nft_set *set,
 202                             struct nft_elem_priv *elem_priv)
 203 {
 204         struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
 205
 206         nft_set_elem_change_active(net, set, &he->ext);
 207 }
 208
 209 static struct nft_elem_priv *
 210 nft_rhash_deactivate(const struct net *net, const struct nft_set *set,
 211                      const struct nft_set_elem *elem)
 212 {
 213         struct nft_rhash *priv = nft_set_priv(set);
 214         struct nft_rhash_elem *he;
 215         struct nft_rhash_cmp_arg arg = {
 216                 .genmask = nft_genmask_next(net),
 217                 .set     = set,
 218                 .key     = elem->key.val.data,
 219         };
 220
 221         rcu_read_lock();
 222         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 223         if (he)
 224                 nft_set_elem_change_active(net, set, &he->ext);
 225
 226         rcu_read_unlock();
 227
 228         return &he->priv;
 229 }
 230
 231 static void nft_rhash_remove(const struct net *net,
 232                              const struct nft_set *set,
 233                              struct nft_elem_priv *elem_priv)
 234 {
 235         struct nft_rhash_elem *he = nft_elem_priv_cast(elem_priv);
 236         struct nft_rhash *priv = nft_set_priv(set);
 237
 238         rhashtable_remove_fast(&priv->ht, &he->node, nft_rhash_params);
 239 }
 240
 241 static bool nft_rhash_delete(const struct nft_set *set,
 242                              const u32 *key)
 243 {
 244         struct nft_rhash *priv = nft_set_priv(set);
 245         struct nft_rhash_cmp_arg arg = {
 246                 .genmask = NFT_GENMASK_ANY,
 247                 .set = set,
 248                 .key = key,
 249         };
 250         struct nft_rhash_elem *he;
 251
 252         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 253         if (he == NULL)
 254                 return false;
 255
 256         nft_set_elem_dead(&he->ext);
 257
 258         return true;
 259 }
 260
 261 static void nft_rhash_walk(const struct nft_ctx *ctx, struct nft_set *set,
 262                            struct nft_set_iter *iter)
 263 {
 264         struct nft_rhash *priv = nft_set_priv(set);
 265         struct nft_rhash_elem *he;
 266         struct rhashtable_iter hti;
 267
 268         rhashtable_walk_enter(&priv->ht, &hti);
 269         rhashtable_walk_start(&hti);
 270
 271         while ((he = rhashtable_walk_next(&hti))) {
 272                 if (IS_ERR(he)) {
 273                         if (PTR_ERR(he) != -EAGAIN) {
 274                                 iter->err = PTR_ERR(he);
 275                                 break;
 276                         }
 277
 278                         continue;
 279                 }
 280
 281                 if (iter->count < iter->skip)
 282                         goto cont;
 283                 if (!nft_set_elem_active(&he->ext, iter->genmask))
 284                         goto cont;
 285
 286                 iter->err = iter->fn(ctx, set, iter, &he->priv);
 287                 if (iter->err < 0)
 288                         break;
 289
 290 cont:
 291                 iter->count++;
 292         }
 293         rhashtable_walk_stop(&hti);
 294         rhashtable_walk_exit(&hti);
 295 }
 296
 297 static bool nft_rhash_expr_needs_gc_run(const struct nft_set *set,
 298                                         struct nft_set_ext *ext)
 299 {
 300         struct nft_set_elem_expr *elem_expr = nft_set_ext_expr(ext);
 301         struct nft_expr *expr;
 302         u32 size;
 303
 304         nft_setelem_expr_foreach(expr, elem_expr, size) {
 305                 if (expr->ops->gc &&
 306                     expr->ops->gc(read_pnet(&set->net), expr))
 307                         return true;
 308         }
 309
 310         return false;
 311 }
 312
 313 static void nft_rhash_gc(struct work_struct *work)
 314 {
 315         struct nftables_pernet *nft_net;
 316         struct nft_set *set;
 317         struct nft_rhash_elem *he;
 318         struct nft_rhash *priv;
 319         struct rhashtable_iter hti;
 320         struct nft_trans_gc *gc;
 321         struct net *net;
 322         u32 gc_seq;
 323
 324         priv = container_of(work, struct nft_rhash, gc_work.work);
 325         set  = nft_set_container_of(priv);
 326         net  = read_pnet(&set->net);
 327         nft_net = nft_pernet(net);
 328         gc_seq = READ_ONCE(nft_net->gc_seq);
 329
 330         if (nft_set_gc_is_pending(set))
 331                 goto done;
 332
 333         gc = nft_trans_gc_alloc(set, gc_seq, GFP_KERNEL);
 334         if (!gc)
 335                 goto done;
 336
 337         rhashtable_walk_enter(&priv->ht, &hti);
 338         rhashtable_walk_start(&hti);
 339
 340         while ((he = rhashtable_walk_next(&hti))) {
 341                 if (IS_ERR(he)) {
 342                         nft_trans_gc_destroy(gc);
 343                         gc = NULL;
 344                         goto try_later;
 345                 }
 346
 347                 /* Ruleset has been updated, try later. */
 348                 if (READ_ONCE(nft_net->gc_seq) != gc_seq) {
 349                         nft_trans_gc_destroy(gc);
 350                         gc = NULL;
 351                         goto try_later;
 352                 }
 353
 354                 if (nft_set_elem_is_dead(&he->ext))
 355                         goto dead_elem;
 356
 357                 if (nft_set_ext_exists(&he->ext, NFT_SET_EXT_EXPRESSIONS) &&
 358                     nft_rhash_expr_needs_gc_run(set, &he->ext))
 359                         goto needs_gc_run;
 360
 361                 if (!nft_set_elem_expired(&he->ext))
 362                         continue;
 363 needs_gc_run:
 364                 nft_set_elem_dead(&he->ext);
 365 dead_elem:
 366                 gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
 367                 if (!gc)
 368                         goto try_later;
 369
 370                 nft_trans_gc_elem_add(gc, he);
 371         }
 372
 373         gc = nft_trans_gc_catchall_async(gc, gc_seq);
 374
 375 try_later:
 376         /* catchall list iteration requires rcu read side lock. */
 377         rhashtable_walk_stop(&hti);
 378         rhashtable_walk_exit(&hti);
 379
 380         if (gc)
 381                 nft_trans_gc_queue_async_done(gc);
 382
 383 done:
 384         queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 385                            nft_set_gc_interval(set));
 386 }
 387
 388 static u64 nft_rhash_privsize(const struct nlattr * const nla[],
 389                               const struct nft_set_desc *desc)
 390 {
 391         return sizeof(struct nft_rhash);
 392 }
 393
 394 static void nft_rhash_gc_init(const struct nft_set *set)
 395 {
 396         struct nft_rhash *priv = nft_set_priv(set);
 397
 398         queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 399                            nft_set_gc_interval(set));
 400 }
 401
 402 static int nft_rhash_init(const struct nft_set *set,
 403                           const struct nft_set_desc *desc,
 404                           const struct nlattr * const tb[])
 405 {
 406         struct nft_rhash *priv = nft_set_priv(set);
 407         struct rhashtable_params params = nft_rhash_params;
 408         int err;
 409
 410         BUILD_BUG_ON(offsetof(struct nft_rhash_elem, priv) != 0);
 411
 412         params.nelem_hint = desc->size ?: NFT_RHASH_ELEMENT_HINT;
 413         params.key_len    = set->klen;
 414
 415         err = rhashtable_init(&priv->ht, &params);
 416         if (err < 0)
 417                 return err;
 418
 419         INIT_DEFERRABLE_WORK(&priv->gc_work, nft_rhash_gc);
 420         if (set->flags & (NFT_SET_TIMEOUT | NFT_SET_EVAL))
 421                 nft_rhash_gc_init(set);
 422
 423         return 0;
 424 }
 425
 426 struct nft_rhash_ctx {
 427         const struct nft_ctx    ctx;
 428         const struct nft_set    *set;
 429 };
 430
 431 static void nft_rhash_elem_destroy(void *ptr, void *arg)
 432 {
 433         struct nft_rhash_ctx *rhash_ctx = arg;
 434         struct nft_rhash_elem *he = ptr;
 435
 436         nf_tables_set_elem_destroy(&rhash_ctx->ctx, rhash_ctx->set, &he->priv);
 437 }
 438
 439 static void nft_rhash_destroy(const struct nft_ctx *ctx,
 440                               const struct nft_set *set)
 441 {
 442         struct nft_rhash *priv = nft_set_priv(set);
 443         struct nft_rhash_ctx rhash_ctx = {
 444                 .ctx    = *ctx,
 445                 .set    = set,
 446         };
 447
 448         cancel_delayed_work_sync(&priv->gc_work);
 449         rhashtable_free_and_destroy(&priv->ht, nft_rhash_elem_destroy,
 450                                     (void *)&rhash_ctx);
 451 }
 452
 453 /* Number of buckets is stored in u32, so cap our result to 1U<<31 */
 454 #define NFT_MAX_BUCKETS (1U << 31)
 455
 456 static u32 nft_hash_buckets(u32 size)
 457 {
 458         u64 val = div_u64((u64)size * 4, 3);
 459
 460         if (val >= NFT_MAX_BUCKETS)
 461                 return NFT_MAX_BUCKETS;
 462
 463         return roundup_pow_of_two(val);
 464 }
 465
 466 static bool nft_rhash_estimate(const struct nft_set_desc *desc, u32 features,
 467                                struct nft_set_estimate *est)
 468 {
 469         est->size   = ~0;
 470         est->lookup = NFT_SET_CLASS_O_1;
 471         est->space  = NFT_SET_CLASS_O_N;
 472
 473         return true;
 474 }
 475
 476 struct nft_hash {
 477         u32                             seed;
 478         u32                             buckets;
 479         struct hlist_head               table[];
 480 };
 481
 482 struct nft_hash_elem {
 483         struct nft_elem_priv            priv;
 484         struct hlist_node               node;
 485         struct nft_set_ext              ext;
 486 };
 487
 488 INDIRECT_CALLABLE_SCOPE
 489 bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
 490                      const u32 *key, const struct nft_set_ext **ext)
 491 {
 492         struct nft_hash *priv = nft_set_priv(set);
 493         u8 genmask = nft_genmask_cur(net);
 494         const struct nft_hash_elem *he;
 495         u32 hash;
 496
 497         hash = jhash(key, set->klen, priv->seed);
 498         hash = reciprocal_scale(hash, priv->buckets);
 499         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 500                 if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
 501                     nft_set_elem_active(&he->ext, genmask)) {
 502                         *ext = &he->ext;
 503                         return true;
 504                 }
 505         }
 506         return false;
 507 }
 508
 509 static struct nft_elem_priv *
 510 nft_hash_get(const struct net *net, const struct nft_set *set,
 511              const struct nft_set_elem *elem, unsigned int flags)
 512 {
 513         struct nft_hash *priv = nft_set_priv(set);
 514         u8 genmask = nft_genmask_cur(net);
 515         struct nft_hash_elem *he;
 516         u32 hash;
 517
 518         hash = jhash(elem->key.val.data, set->klen, priv->seed);
 519         hash = reciprocal_scale(hash, priv->buckets);
 520         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 521                 if (!memcmp(nft_set_ext_key(&he->ext), elem->key.val.data, set->klen) &&
 522                     nft_set_elem_active(&he->ext, genmask))
 523                         return &he->priv;
 524         }
 525         return ERR_PTR(-ENOENT);
 526 }
 527
 528 INDIRECT_CALLABLE_SCOPE
 529 bool nft_hash_lookup_fast(const struct net *net,
 530                           const struct nft_set *set,
 531                           const u32 *key, const struct nft_set_ext **ext)
 532 {
 533         struct nft_hash *priv = nft_set_priv(set);
 534         u8 genmask = nft_genmask_cur(net);
 535         const struct nft_hash_elem *he;
 536         u32 hash, k1, k2;
 537
 538         k1 = *key;
 539         hash = jhash_1word(k1, priv->seed);
 540         hash = reciprocal_scale(hash, priv->buckets);
 541         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 542                 k2 = *(u32 *)nft_set_ext_key(&he->ext)->data;
 543                 if (k1 == k2 &&
 544                     nft_set_elem_active(&he->ext, genmask)) {
 545                         *ext = &he->ext;
 546                         return true;
 547                 }
 548         }
 549         return false;
 550 }
 551
 552 static u32 nft_jhash(const struct nft_set *set, const struct nft_hash *priv,
 553                      const struct nft_set_ext *ext)
 554 {
 555         const struct nft_data *key = nft_set_ext_key(ext);
 556         u32 hash, k1;
 557
 558         if (set->klen == 4) {
 559                 k1 = *(u32 *)key;
 560                 hash = jhash_1word(k1, priv->seed);
 561         } else {
 562                 hash = jhash(key, set->klen, priv->seed);
 563         }
 564         hash = reciprocal_scale(hash, priv->buckets);
 565
 566         return hash;
 567 }
 568
 569 static int nft_hash_insert(const struct net *net, const struct nft_set *set,
 570                            const struct nft_set_elem *elem,
 571                            struct nft_set_ext **ext)
 572 {
 573         struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
 574         struct nft_hash *priv = nft_set_priv(set);
 575         u8 genmask = nft_genmask_next(net);
 576         u32 hash;
 577
 578         hash = nft_jhash(set, priv, &this->ext);
 579         hlist_for_each_entry(he, &priv->table[hash], node) {
 580                 if (!memcmp(nft_set_ext_key(&this->ext),
 581                             nft_set_ext_key(&he->ext), set->klen) &&
 582                     nft_set_elem_active(&he->ext, genmask)) {
 583                         *ext = &he->ext;
 584                         return -EEXIST;
 585                 }
 586         }
 587         hlist_add_head_rcu(&this->node, &priv->table[hash]);
 588         return 0;
 589 }
 590
 591 static void nft_hash_activate(const struct net *net, const struct nft_set *set,
 592                               struct nft_elem_priv *elem_priv)
 593 {
 594         struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
 595
 596         nft_set_elem_change_active(net, set, &he->ext);
 597 }
 598
 599 static void nft_hash_flush(const struct net *net,
 600                            const struct nft_set *set,
 601                            struct nft_elem_priv *elem_priv)
 602 {
 603         struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
 604
 605         nft_set_elem_change_active(net, set, &he->ext);
 606 }
 607
 608 static struct nft_elem_priv *
 609 nft_hash_deactivate(const struct net *net, const struct nft_set *set,
 610                     const struct nft_set_elem *elem)
 611 {
 612         struct nft_hash_elem *this = nft_elem_priv_cast(elem->priv), *he;
 613         struct nft_hash *priv = nft_set_priv(set);
 614         u8 genmask = nft_genmask_next(net);
 615         u32 hash;
 616
 617         hash = nft_jhash(set, priv, &this->ext);
 618         hlist_for_each_entry(he, &priv->table[hash], node) {
 619                 if (!memcmp(nft_set_ext_key(&he->ext), &elem->key.val,
 620                             set->klen) &&
 621                     nft_set_elem_active(&he->ext, genmask)) {
 622                         nft_set_elem_change_active(net, set, &he->ext);
 623                         return &he->priv;
 624                 }
 625         }
 626         return NULL;
 627 }
 628
 629 static void nft_hash_remove(const struct net *net,
 630                             const struct nft_set *set,
 631                             struct nft_elem_priv *elem_priv)
 632 {
 633         struct nft_hash_elem *he = nft_elem_priv_cast(elem_priv);
 634
 635         hlist_del_rcu(&he->node);
 636 }
 637
 638 static void nft_hash_walk(const struct nft_ctx *ctx, struct nft_set *set,
 639                           struct nft_set_iter *iter)
 640 {
 641         struct nft_hash *priv = nft_set_priv(set);
 642         struct nft_hash_elem *he;
 643         int i;
 644
 645         for (i = 0; i < priv->buckets; i++) {
 646                 hlist_for_each_entry_rcu(he, &priv->table[i], node) {
 647                         if (iter->count < iter->skip)
 648                                 goto cont;
 649                         if (!nft_set_elem_active(&he->ext, iter->genmask))
 650                                 goto cont;
 651
 652                         iter->err = iter->fn(ctx, set, iter, &he->priv);
 653                         if (iter->err < 0)
 654                                 return;
 655 cont:
 656                         iter->count++;
 657                 }
 658         }
 659 }
 660
 661 static u64 nft_hash_privsize(const struct nlattr * const nla[],
 662                              const struct nft_set_desc *desc)
 663 {
 664         return sizeof(struct nft_hash) +
 665                (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head);
 666 }
 667
 668 static int nft_hash_init(const struct nft_set *set,
 669                          const struct nft_set_desc *desc,
 670                          const struct nlattr * const tb[])
 671 {
 672         struct nft_hash *priv = nft_set_priv(set);
 673
 674         priv->buckets = nft_hash_buckets(desc->size);
 675         get_random_bytes(&priv->seed, sizeof(priv->seed));
 676
 677         return 0;
 678 }
 679
 680 static void nft_hash_destroy(const struct nft_ctx *ctx,
 681                              const struct nft_set *set)
 682 {
 683         struct nft_hash *priv = nft_set_priv(set);
 684         struct nft_hash_elem *he;
 685         struct hlist_node *next;
 686         int i;
 687
 688         for (i = 0; i < priv->buckets; i++) {
 689                 hlist_for_each_entry_safe(he, next, &priv->table[i], node) {
 690                         hlist_del_rcu(&he->node);
 691                         nf_tables_set_elem_destroy(ctx, set, &he->priv);
 692                 }
 693         }
 694 }
 695
 696 static bool nft_hash_estimate(const struct nft_set_desc *desc, u32 features,
 697                               struct nft_set_estimate *est)
 698 {
 699         if (!desc->size)
 700                 return false;
 701
 702         if (desc->klen == 4)
 703                 return false;
 704
 705         est->size   = sizeof(struct nft_hash) +
 706                       (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
 707                       (u64)desc->size * sizeof(struct nft_hash_elem);
 708         est->lookup = NFT_SET_CLASS_O_1;
 709         est->space  = NFT_SET_CLASS_O_N;
 710
 711         return true;
 712 }
 713
 714 static bool nft_hash_fast_estimate(const struct nft_set_desc *desc, u32 features,
 715                                    struct nft_set_estimate *est)
 716 {
 717         if (!desc->size)
 718                 return false;
 719
 720         if (desc->klen != 4)
 721                 return false;
 722
 723         est->size   = sizeof(struct nft_hash) +
 724                       (u64)nft_hash_buckets(desc->size) * sizeof(struct hlist_head) +
 725                       (u64)desc->size * sizeof(struct nft_hash_elem);
 726         est->lookup = NFT_SET_CLASS_O_1;
 727         est->space  = NFT_SET_CLASS_O_N;
 728
 729         return true;
 730 }
 731
 732 const struct nft_set_type nft_set_rhash_type = {
 733         .features       = NFT_SET_MAP | NFT_SET_OBJECT |
 734                           NFT_SET_TIMEOUT | NFT_SET_EVAL,
 735         .ops            = {
 736                 .privsize       = nft_rhash_privsize,
 737                 .elemsize       = offsetof(struct nft_rhash_elem, ext),
 738                 .estimate       = nft_rhash_estimate,
 739                 .init           = nft_rhash_init,
 740                 .gc_init        = nft_rhash_gc_init,
 741                 .destroy        = nft_rhash_destroy,
 742                 .insert         = nft_rhash_insert,
 743                 .activate       = nft_rhash_activate,
 744                 .deactivate     = nft_rhash_deactivate,
 745                 .flush          = nft_rhash_flush,
 746                 .remove         = nft_rhash_remove,
 747                 .lookup         = nft_rhash_lookup,
 748                 .update         = nft_rhash_update,
 749                 .delete         = nft_rhash_delete,
 750                 .walk           = nft_rhash_walk,
 751                 .get            = nft_rhash_get,
 752         },
 753 };
 754
 755 const struct nft_set_type nft_set_hash_type = {
 756         .features       = NFT_SET_MAP | NFT_SET_OBJECT,
 757         .ops            = {
 758                 .privsize       = nft_hash_privsize,
 759                 .elemsize       = offsetof(struct nft_hash_elem, ext),
 760                 .estimate       = nft_hash_estimate,
 761                 .init           = nft_hash_init,
 762                 .destroy        = nft_hash_destroy,
 763                 .insert         = nft_hash_insert,
 764                 .activate       = nft_hash_activate,
 765                 .deactivate     = nft_hash_deactivate,
 766                 .flush          = nft_hash_flush,
 767                 .remove         = nft_hash_remove,
 768                 .lookup         = nft_hash_lookup,
 769                 .walk           = nft_hash_walk,
 770                 .get            = nft_hash_get,
 771         },
 772 };
 773
 774 const struct nft_set_type nft_set_hash_fast_type = {
 775         .features       = NFT_SET_MAP | NFT_SET_OBJECT,
 776         .ops            = {
 777                 .privsize       = nft_hash_privsize,
 778                 .elemsize       = offsetof(struct nft_hash_elem, ext),
 779                 .estimate       = nft_hash_fast_estimate,
 780                 .init           = nft_hash_init,
 781                 .destroy        = nft_hash_destroy,
 782                 .insert         = nft_hash_insert,
 783                 .activate       = nft_hash_activate,
 784                 .deactivate     = nft_hash_deactivate,
 785                 .flush          = nft_hash_flush,
 786                 .remove         = nft_hash_remove,
 787                 .lookup         = nft_hash_lookup_fast,
 788                 .walk           = nft_hash_walk,
 789                 .get            = nft_hash_get,
 790         },
 791 };