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