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