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