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