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