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 rhash_head               node;
  31         struct nft_set_ext              ext;
  32 };
  33
  34 struct nft_rhash_cmp_arg {
  35         const struct nft_set            *set;
  36         const u32                       *key;
  37         u8                              genmask;
  38 };
  39
  40 static inline u32 nft_rhash_key(const void *data, u32 len, u32 seed)
  41 {
  42         const struct nft_rhash_cmp_arg *arg = data;
  43
  44         return jhash(arg->key, len, seed);
  45 }
  46
  47 static inline u32 nft_rhash_obj(const void *data, u32 len, u32 seed)
  48 {
  49         const struct nft_rhash_elem *he = data;
  50
  51         return jhash(nft_set_ext_key(&he->ext), len, seed);
  52 }
  53
  54 static inline int nft_rhash_cmp(struct rhashtable_compare_arg *arg,
  55                                 const void *ptr)
  56 {
  57         const struct nft_rhash_cmp_arg *x = arg->key;
  58         const struct nft_rhash_elem *he = ptr;
  59
  60         if (memcmp(nft_set_ext_key(&he->ext), x->key, x->set->klen))
  61                 return 1;
  62         if (nft_set_elem_is_dead(&he->ext))
  63                 return 1;
  64         if (nft_set_elem_expired(&he->ext))
  65                 return 1;
  66         if (!nft_set_elem_active(&he->ext, x->genmask))
  67                 return 1;
  68         return 0;
  69 }
  70
  71 static const struct rhashtable_params nft_rhash_params = {
  72         .head_offset            = offsetof(struct nft_rhash_elem, node),
  73         .hashfn                 = nft_rhash_key,
  74         .obj_hashfn             = nft_rhash_obj,
  75         .obj_cmpfn              = nft_rhash_cmp,
  76         .automatic_shrinking    = true,
  77 };
  78
  79 INDIRECT_CALLABLE_SCOPE
  80 bool nft_rhash_lookup(const struct net *net, const struct nft_set *set,
  81                       const u32 *key, const struct nft_set_ext **ext)
  82 {
  83         struct nft_rhash *priv = nft_set_priv(set);
  84         const struct nft_rhash_elem *he;
  85         struct nft_rhash_cmp_arg arg = {
  86                 .genmask = nft_genmask_cur(net),
  87                 .set     = set,
  88                 .key     = key,
  89         };
  90
  91         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
  92         if (he != NULL)
  93                 *ext = &he->ext;
  94
  95         return !!he;
  96 }
  97
  98 static void *nft_rhash_get(const struct net *net, const struct nft_set *set,
  99                            const struct nft_set_elem *elem, unsigned int flags)
 100 {
 101         struct nft_rhash *priv = nft_set_priv(set);
 102         struct nft_rhash_elem *he;
 103         struct nft_rhash_cmp_arg arg = {
 104                 .genmask = nft_genmask_cur(net),
 105                 .set     = set,
 106                 .key     = elem->key.val.data,
 107         };
 108
 109         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 110         if (he != NULL)
 111                 return he;
 112
 113         return ERR_PTR(-ENOENT);
 114 }
 115
 116 static bool nft_rhash_update(struct nft_set *set, const u32 *key,
 117                              void *(*new)(struct nft_set *,
 118                                           const struct nft_expr *,
 119                                           struct nft_regs *regs),
 120                              const struct nft_expr *expr,
 121                              struct nft_regs *regs,
 122                              const struct nft_set_ext **ext)
 123 {
 124         struct nft_rhash *priv = nft_set_priv(set);
 125         struct nft_rhash_elem *he, *prev;
 126         struct nft_rhash_cmp_arg arg = {
 127                 .genmask = NFT_GENMASK_ANY,
 128                 .set     = set,
 129                 .key     = key,
 130         };
 131
 132         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 133         if (he != NULL)
 134                 goto out;
 135
 136         he = new(set, expr, regs);
 137         if (he == NULL)
 138                 goto err1;
 139
 140         prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
 141                                                 nft_rhash_params);
 142         if (IS_ERR(prev))
 143                 goto err2;
 144
 145         /* Another cpu may race to insert the element with the same key */
 146         if (prev) {
 147                 nft_set_elem_destroy(set, he, true);
 148                 atomic_dec(&set->nelems);
 149                 he = prev;
 150         }
 151
 152 out:
 153         *ext = &he->ext;
 154         return true;
 155
 156 err2:
 157         nft_set_elem_destroy(set, he, true);
 158         atomic_dec(&set->nelems);
 159 err1:
 160         return false;
 161 }
 162
 163 static int nft_rhash_insert(const struct net *net, const struct nft_set *set,
 164                             const struct nft_set_elem *elem,
 165                             struct nft_set_ext **ext)
 166 {
 167         struct nft_rhash *priv = nft_set_priv(set);
 168         struct nft_rhash_elem *he = elem->priv;
 169         struct nft_rhash_cmp_arg arg = {
 170                 .genmask = nft_genmask_next(net),
 171                 .set     = set,
 172                 .key     = elem->key.val.data,
 173         };
 174         struct nft_rhash_elem *prev;
 175
 176         prev = rhashtable_lookup_get_insert_key(&priv->ht, &arg, &he->node,
 177                                                 nft_rhash_params);
 178         if (IS_ERR(prev))
 179                 return PTR_ERR(prev);
 180         if (prev) {
 181                 *ext = &prev->ext;
 182                 return -EEXIST;
 183         }
 184         return 0;
 185 }
 186
 187 static void nft_rhash_activate(const struct net *net, const struct nft_set *set,
 188                                const struct nft_set_elem *elem)
 189 {
 190         struct nft_rhash_elem *he = elem->priv;
 191
 192         nft_set_elem_change_active(net, set, &he->ext);
 193 }
 194
 195 static bool nft_rhash_flush(const struct net *net,
 196                             const struct nft_set *set, void *priv)
 197 {
 198         struct nft_rhash_elem *he = priv;
 199
 200         nft_set_elem_change_active(net, set, &he->ext);
 201
 202         return true;
 203 }
 204
 205 static void *nft_rhash_deactivate(const struct net *net,
 206                                   const struct nft_set *set,
 207                                   const struct nft_set_elem *elem)
 208 {
 209         struct nft_rhash *priv = nft_set_priv(set);
 210         struct nft_rhash_elem *he;
 211         struct nft_rhash_cmp_arg arg = {
 212                 .genmask = nft_genmask_next(net),
 213                 .set     = set,
 214                 .key     = elem->key.val.data,
 215         };
 216
 217         rcu_read_lock();
 218         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 219         if (he)
 220                 nft_set_elem_change_active(net, set, &he->ext);
 221
 222         rcu_read_unlock();
 223
 224         return he;
 225 }
 226
 227 static void nft_rhash_remove(const struct net *net,
 228                              const struct nft_set *set,
 229                              const struct nft_set_elem *elem)
 230 {
 231         struct nft_rhash *priv = nft_set_priv(set);
 232         struct nft_rhash_elem *he = elem->priv;
 233
 234         rhashtable_remove_fast(&priv->ht, &he->node, nft_rhash_params);
 235 }
 236
 237 static bool nft_rhash_delete(const struct nft_set *set,
 238                              const u32 *key)
 239 {
 240         struct nft_rhash *priv = nft_set_priv(set);
 241         struct nft_rhash_cmp_arg arg = {
 242                 .genmask = NFT_GENMASK_ANY,
 243                 .set = set,
 244                 .key = key,
 245         };
 246         struct nft_rhash_elem *he;
 247
 248         he = rhashtable_lookup(&priv->ht, &arg, nft_rhash_params);
 249         if (he == NULL)
 250                 return false;
 251
 252         nft_set_elem_dead(&he->ext);
 253
 254         return true;
 255 }
 256
 257 static void nft_rhash_walk(const struct nft_ctx *ctx, struct nft_set *set,
 258                            struct nft_set_iter *iter)
 259 {
 260         struct nft_rhash *priv = nft_set_priv(set);
 261         struct nft_rhash_elem *he;
 262         struct rhashtable_iter hti;
 263         struct nft_set_elem elem;
 264
 265         rhashtable_walk_enter(&priv->ht, &hti);
 266         rhashtable_walk_start(&hti);
 267
 268         while ((he = rhashtable_walk_next(&hti))) {
 269                 if (IS_ERR(he)) {
 270                         if (PTR_ERR(he) != -EAGAIN) {
 271                                 iter->err = PTR_ERR(he);
 272                                 break;
 273                         }
 274
 275                         continue;
 276                 }
 277
 278                 if (iter->count < iter->skip)
 279                         goto cont;
 280                 if (!nft_set_elem_active(&he->ext, iter->genmask))
 281                         goto cont;
 282
 283                 elem.priv = he;
 284
 285                 iter->err = iter->fn(ctx, set, iter, &elem);
 286                 if (iter->err < 0)
 287                         break;
 288
 289 cont:
 290                 iter->count++;
 291         }
 292         rhashtable_walk_stop(&hti);
 293         rhashtable_walk_exit(&hti);
 294 }
 295
 296 static bool nft_rhash_expr_needs_gc_run(const struct nft_set *set,
 297                                         struct nft_set_ext *ext)
 298 {
 299         struct nft_set_elem_expr *elem_expr = nft_set_ext_expr(ext);
 300         struct nft_expr *expr;
 301         u32 size;
 302
 303         nft_setelem_expr_foreach(expr, elem_expr, size) {
 304                 if (expr->ops->gc &&
 305                     expr->ops->gc(read_pnet(&set->net), expr))
 306                         return true;
 307         }
 308
 309         return false;
 310 }
 311
 312 static void nft_rhash_gc(struct work_struct *work)
 313 {
 314         struct nftables_pernet *nft_net;
 315         struct nft_set *set;
 316         struct nft_rhash_elem *he;
 317         struct nft_rhash *priv;
 318         struct rhashtable_iter hti;
 319         struct nft_trans_gc *gc;
 320         struct net *net;
 321         u32 gc_seq;
 322
 323         priv = container_of(work, struct nft_rhash, gc_work.work);
 324         set  = nft_set_container_of(priv);
 325         net  = read_pnet(&set->net);
 326         nft_net = nft_pernet(net);
 327         gc_seq = READ_ONCE(nft_net->gc_seq);
 328
 329         if (nft_set_gc_is_pending(set))
 330                 goto done;
 331
 332         gc = nft_trans_gc_alloc(set, gc_seq, GFP_KERNEL);
 333         if (!gc)
 334                 goto done;
 335
 336         rhashtable_walk_enter(&priv->ht, &hti);
 337         rhashtable_walk_start(&hti);
 338
 339         while ((he = rhashtable_walk_next(&hti))) {
 340                 if (IS_ERR(he)) {
 341                         if (PTR_ERR(he) != -EAGAIN) {
 342                                 nft_trans_gc_destroy(gc);
 343                                 gc = NULL;
 344                                 goto try_later;
 345                         }
 346                         continue;
 347                 }
 348
 349                 /* Ruleset has been updated, try later. */
 350                 if (READ_ONCE(nft_net->gc_seq) != gc_seq) {
 351                         nft_trans_gc_destroy(gc);
 352                         gc = NULL;
 353                         goto try_later;
 354                 }
 355
 356                 if (nft_set_elem_is_dead(&he->ext))
 357                         goto dead_elem;
 358
 359                 if (nft_set_ext_exists(&he->ext, NFT_SET_EXT_EXPRESSIONS) &&
 360                     nft_rhash_expr_needs_gc_run(set, &he->ext))
 361                         goto needs_gc_run;
 362
 363                 if (!nft_set_elem_expired(&he->ext))
 364                         continue;
 365 needs_gc_run:
 366                 nft_set_elem_dead(&he->ext);
 367 dead_elem:
 368                 gc = nft_trans_gc_queue_async(gc, gc_seq, GFP_ATOMIC);
 369                 if (!gc)
 370                         goto try_later;
 371
 372                 nft_trans_gc_elem_add(gc, he);
 373         }
 374
 375         gc = nft_trans_gc_catchall(gc, gc_seq);
 376
 377 try_later:
 378         /* catchall list iteration requires rcu read side lock. */
 379         rhashtable_walk_stop(&hti);
 380         rhashtable_walk_exit(&hti);
 381
 382         if (gc)
 383                 nft_trans_gc_queue_async_done(gc);
 384
 385 done:
 386         queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 387                            nft_set_gc_interval(set));
 388 }
 389
 390 static u64 nft_rhash_privsize(const struct nlattr * const nla[],
 391                               const struct nft_set_desc *desc)
 392 {
 393         return sizeof(struct nft_rhash);
 394 }
 395
 396 static void nft_rhash_gc_init(const struct nft_set *set)
 397 {
 398         struct nft_rhash *priv = nft_set_priv(set);
 399
 400         queue_delayed_work(system_power_efficient_wq, &priv->gc_work,
 401                            nft_set_gc_interval(set));
 402 }
 403
 404 static int nft_rhash_init(const struct nft_set *set,
 405                           const struct nft_set_desc *desc,
 406                           const struct nlattr * const tb[])
 407 {
 408         struct nft_rhash *priv = nft_set_priv(set);
 409         struct rhashtable_params params = nft_rhash_params;
 410         int err;
 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
 435         nf_tables_set_elem_destroy(&rhash_ctx->ctx, rhash_ctx->set, ptr);
 436 }
 437
 438 static void nft_rhash_destroy(const struct nft_ctx *ctx,
 439                               const struct nft_set *set)
 440 {
 441         struct nft_rhash *priv = nft_set_priv(set);
 442         struct nft_rhash_ctx rhash_ctx = {
 443                 .ctx    = *ctx,
 444                 .set    = set,
 445         };
 446
 447         cancel_delayed_work_sync(&priv->gc_work);
 448         rhashtable_free_and_destroy(&priv->ht, nft_rhash_elem_destroy,
 449                                     (void *)&rhash_ctx);
 450 }
 451
 452 /* Number of buckets is stored in u32, so cap our result to 1U<<31 */
 453 #define NFT_MAX_BUCKETS (1U << 31)
 454
 455 static u32 nft_hash_buckets(u32 size)
 456 {
 457         u64 val = div_u64((u64)size * 4, 3);
 458
 459         if (val >= NFT_MAX_BUCKETS)
 460                 return NFT_MAX_BUCKETS;
 461
 462         return roundup_pow_of_two(val);
 463 }
 464
 465 static bool nft_rhash_estimate(const struct nft_set_desc *desc, u32 features,
 466                                struct nft_set_estimate *est)
 467 {
 468         est->size   = ~0;
 469         est->lookup = NFT_SET_CLASS_O_1;
 470         est->space  = NFT_SET_CLASS_O_N;
 471
 472         return true;
 473 }
 474
 475 struct nft_hash {
 476         u32                             seed;
 477         u32                             buckets;
 478         struct hlist_head               table[];
 479 };
 480
 481 struct nft_hash_elem {
 482         struct hlist_node               node;
 483         struct nft_set_ext              ext;
 484 };
 485
 486 INDIRECT_CALLABLE_SCOPE
 487 bool nft_hash_lookup(const struct net *net, const struct nft_set *set,
 488                      const u32 *key, const struct nft_set_ext **ext)
 489 {
 490         struct nft_hash *priv = nft_set_priv(set);
 491         u8 genmask = nft_genmask_cur(net);
 492         const struct nft_hash_elem *he;
 493         u32 hash;
 494
 495         hash = jhash(key, set->klen, priv->seed);
 496         hash = reciprocal_scale(hash, priv->buckets);
 497         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 498                 if (!memcmp(nft_set_ext_key(&he->ext), key, set->klen) &&
 499                     nft_set_elem_active(&he->ext, genmask)) {
 500                         *ext = &he->ext;
 501                         return true;
 502                 }
 503         }
 504         return false;
 505 }
 506
 507 static void *nft_hash_get(const struct net *net, const struct nft_set *set,
 508                           const struct nft_set_elem *elem, unsigned int flags)
 509 {
 510         struct nft_hash *priv = nft_set_priv(set);
 511         u8 genmask = nft_genmask_cur(net);
 512         struct nft_hash_elem *he;
 513         u32 hash;
 514
 515         hash = jhash(elem->key.val.data, set->klen, priv->seed);
 516         hash = reciprocal_scale(hash, priv->buckets);
 517         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 518                 if (!memcmp(nft_set_ext_key(&he->ext), elem->key.val.data, set->klen) &&
 519                     nft_set_elem_active(&he->ext, genmask))
 520                         return he;
 521         }
 522         return ERR_PTR(-ENOENT);
 523 }
 524
 525 INDIRECT_CALLABLE_SCOPE
 526 bool nft_hash_lookup_fast(const struct net *net,
 527                           const struct nft_set *set,
 528                           const u32 *key, const struct nft_set_ext **ext)
 529 {
 530         struct nft_hash *priv = nft_set_priv(set);
 531         u8 genmask = nft_genmask_cur(net);
 532         const struct nft_hash_elem *he;
 533         u32 hash, k1, k2;
 534
 535         k1 = *key;
 536         hash = jhash_1word(k1, priv->seed);
 537         hash = reciprocal_scale(hash, priv->buckets);
 538         hlist_for_each_entry_rcu(he, &priv->table[hash], node) {
 539                 k2 = *(u32 *)nft_set_ext_key(&he->ext)->data;
 540                 if (k1 == k2 &&
 541                     nft_set_elem_active(&he->ext, genmask)) {
 542                         *ext = &he->ext;
 543                         return true;
 544                 }
 545         }
 546         return false;
 547 }
 548
 549 static u32 nft_jhash(const struct nft_set *set, const struct nft_hash *priv,
 550                      const struct nft_set_ext *ext)
 551 {
 552         const struct nft_data *key = nft_set_ext_key(ext);
 553         u32 hash, k1;
 554
 555         if (set->klen == 4) {
 556                 k1 = *(u32 *)key;
 557                 hash = jhash_1word(k1, priv->seed);
 558         } else {
 559                 hash = jhash(key, set->klen, priv->seed);
 560         }
 561         hash = reciprocal_scale(hash, priv->buckets);
 562
 563         return hash;
 564 }
 565
 566 static int nft_hash_insert(const struct net *net, const struct nft_set *set,
 567                            const struct nft_set_elem *elem,
 568                            struct nft_set_ext **ext)
 569 {
 570         struct nft_hash_elem *this = elem->priv, *he;
 571         struct nft_hash *priv = nft_set_priv(set);
 572         u8 genmask = nft_genmask_next(net);
 573         u32 hash;
 574
 575         hash = nft_jhash(set, priv, &this->ext);
 576         hlist_for_each_entry(he, &priv->table[hash], node) {
 577                 if (!memcmp(nft_set_ext_key(&this->ext),
 578                             nft_set_ext_key(&he->ext), set->klen) &&
 579                     nft_set_elem_active(&he->ext, genmask)) {
 580                         *ext = &he->ext;
 581                         return -EEXIST;
 582                 }
 583         }
 584         hlist_add_head_rcu(&this->node, &priv->table[hash]);
 585         return 0;
 586 }
 587
 588 static void nft_hash_activate(const struct net *net, const struct nft_set *set,
 589                               const struct nft_set_elem *elem)
 590 {
 591         struct nft_hash_elem *he = elem->priv;
 592
 593         nft_set_elem_change_active(net, set, &he->ext);
 594 }
 595
 596 static bool nft_hash_flush(const struct net *net,
 597                            const struct nft_set *set, void *priv)
 598 {
 599         struct nft_hash_elem *he = priv;
 600
 601         nft_set_elem_change_active(net, set, &he->ext);
 602         return true;
 603 }
 604
 605 static void *nft_hash_deactivate(const struct net *net,
 606                                  const struct nft_set *set,
 607                                  const struct nft_set_elem *elem)
 608 {
 609         struct nft_hash *priv = nft_set_priv(set);
 610         struct nft_hash_elem *this = elem->priv, *he;
 611         u8 genmask = nft_genmask_next(net);
 612         u32 hash;
 613
 614         hash = nft_jhash(set, priv, &this->ext);
 615         hlist_for_each_entry(he, &priv->table[hash], node) {
 616                 if (!memcmp(nft_set_ext_key(&he->ext), &elem->key.val,
 617                             set->klen) &&
 618                     nft_set_elem_active(&he->ext, genmask)) {
 619                         nft_set_elem_change_active(net, set, &he->ext);
 620                         return he;
 621                 }
 622         }
 623         return NULL;
 624 }
 625
 626 static void nft_hash_remove(const struct net *net,
 627                             const struct nft_set *set,
 628                             const struct nft_set_elem *elem)
 629 {
 630         struct nft_hash_elem *he = elem->priv;
 631
 632         hlist_del_rcu(&he->node);
 633 }
 634
 635 static void nft_hash_walk(const struct nft_ctx *ctx, struct nft_set *set,
 636                           struct nft_set_iter *iter)
 637 {
 638         struct nft_hash *priv = nft_set_priv(set);
 639         struct nft_hash_elem *he;
 640         struct nft_set_elem elem;
 641         int i;
 642
 643         for (i = 0; i < priv->buckets; i++) {
 644                 hlist_for_each_entry_rcu(he, &priv->table[i], node) {
 645                         if (iter->count < iter->skip)
 646                                 goto cont;
 647                         if (!nft_set_elem_active(&he->ext, iter->genmask))
 648                                 goto cont;
 649
 650                         elem.priv = he;
 651
 652                         iter->err = iter->fn(ctx, set, iter, &elem);
 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);
 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 };