net/netfilter/ipset/ip_set_hash_gen.h

   1 /* Copyright (C) 2013 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
   2  *
   3  * This program is free software; you can redistribute it and/or modify
   4  * it under the terms of the GNU General Public License version 2 as
   5  * published by the Free Software Foundation.
   6  */
   7
   8 #ifndef _IP_SET_HASH_GEN_H
   9 #define _IP_SET_HASH_GEN_H
  10
  11 #include <linux/rcupdate.h>
  12 #include <linux/jhash.h>
  13 #include <linux/types.h>
  14 #include <linux/netfilter/ipset/ip_set_timeout.h>
  15
  16 #define __ipset_dereference_protected(p, c)     rcu_dereference_protected(p, c)
  17 #define ipset_dereference_protected(p, set) \
  18         __ipset_dereference_protected(p, spin_is_locked(&(set)->lock))
  19
  20 #define rcu_dereference_bh_nfnl(p)      rcu_dereference_bh_check(p, 1)
  21
  22 /* Hashing which uses arrays to resolve clashing. The hash table is resized
  23  * (doubled) when searching becomes too long.
  24  * Internally jhash is used with the assumption that the size of the
  25  * stored data is a multiple of sizeof(u32).
  26  *
  27  * Readers and resizing
  28  *
  29  * Resizing can be triggered by userspace command only, and those
  30  * are serialized by the nfnl mutex. During resizing the set is
  31  * read-locked, so the only possible concurrent operations are
  32  * the kernel side readers. Those must be protected by proper RCU locking.
  33  */
  34
  35 /* Number of elements to store in an initial array block */
  36 #define AHASH_INIT_SIZE                 4
  37 /* Max number of elements to store in an array block */
  38 #define AHASH_MAX_SIZE                  (3 * AHASH_INIT_SIZE)
  39 /* Max muber of elements in the array block when tuned */
  40 #define AHASH_MAX_TUNED                 64
  41
  42 /* Max number of elements can be tuned */
  43 #ifdef IP_SET_HASH_WITH_MULTI
  44 #define AHASH_MAX(h)                    ((h)->ahash_max)
  45
  46 static inline u8
  47 tune_ahash_max(u8 curr, u32 multi)
  48 {
  49         u32 n;
  50
  51         if (multi < curr)
  52                 return curr;
  53
  54         n = curr + AHASH_INIT_SIZE;
  55         /* Currently, at listing one hash bucket must fit into a message.
  56          * Therefore we have a hard limit here.
  57          */
  58         return n > curr && n <= AHASH_MAX_TUNED ? n : curr;
  59 }
  60
  61 #define TUNE_AHASH_MAX(h, multi)        \
  62         ((h)->ahash_max = tune_ahash_max((h)->ahash_max, multi))
  63 #else
  64 #define AHASH_MAX(h)                    AHASH_MAX_SIZE
  65 #define TUNE_AHASH_MAX(h, multi)
  66 #endif
  67
  68 /* A hash bucket */
  69 struct hbucket {
  70         struct rcu_head rcu;    /* for call_rcu_bh */
  71         /* Which positions are used in the array */
  72         DECLARE_BITMAP(used, AHASH_MAX_TUNED);
  73         u8 size;                /* size of the array */
  74         u8 pos;                 /* position of the first free entry */
  75         unsigned char value[0]; /* the array of the values */
  76 } __attribute__ ((aligned));
  77
  78 /* The hash table: the table size stored here in order to make resizing easy */
  79 struct htable {
  80         atomic_t ref;           /* References for resizing */
  81         atomic_t uref;          /* References for dumping */
  82         u8 htable_bits;         /* size of hash table == 2^htable_bits */
  83         struct hbucket __rcu *bucket[0]; /* hashtable buckets */
  84 };
  85
  86 #define hbucket(h, i)           ((h)->bucket[i])
  87
  88 #ifndef IPSET_NET_COUNT
  89 #define IPSET_NET_COUNT         1
  90 #endif
  91
  92 /* Book-keeping of the prefixes added to the set */
  93 struct net_prefixes {
  94         u32 nets[IPSET_NET_COUNT]; /* number of elements for this cidr */
  95         u8 cidr[IPSET_NET_COUNT];  /* the cidr value */
  96 };
  97
  98 /* Compute the hash table size */
  99 static size_t
 100 htable_size(u8 hbits)
 101 {
 102         size_t hsize;
 103
 104         /* We must fit both into u32 in jhash and size_t */
 105         if (hbits > 31)
 106                 return 0;
 107         hsize = jhash_size(hbits);
 108         if ((((size_t)-1) - sizeof(struct htable)) / sizeof(struct hbucket *)
 109             < hsize)
 110                 return 0;
 111
 112         return hsize * sizeof(struct hbucket *) + sizeof(struct htable);
 113 }
 114
 115 /* Compute htable_bits from the user input parameter hashsize */
 116 static u8
 117 htable_bits(u32 hashsize)
 118 {
 119         /* Assume that hashsize == 2^htable_bits */
 120         u8 bits = fls(hashsize - 1);
 121
 122         if (jhash_size(bits) != hashsize)
 123                 /* Round up to the first 2^n value */
 124                 bits = fls(hashsize);
 125
 126         return bits;
 127 }
 128
 129 #ifdef IP_SET_HASH_WITH_NETS
 130 #if IPSET_NET_COUNT > 1
 131 #define __CIDR(cidr, i)         (cidr[i])
 132 #else
 133 #define __CIDR(cidr, i)         (cidr)
 134 #endif
 135
 136 /* cidr + 1 is stored in net_prefixes to support /0 */
 137 #define NCIDR_PUT(cidr)         ((cidr) + 1)
 138 #define NCIDR_GET(cidr)         ((cidr) - 1)
 139
 140 #ifdef IP_SET_HASH_WITH_NETS_PACKED
 141 /* When cidr is packed with nomatch, cidr - 1 is stored in the data entry */
 142 #define DCIDR_PUT(cidr)         ((cidr) - 1)
 143 #define DCIDR_GET(cidr, i)      (__CIDR(cidr, i) + 1)
 144 #else
 145 #define DCIDR_PUT(cidr)         (cidr)
 146 #define DCIDR_GET(cidr, i)      __CIDR(cidr, i)
 147 #endif
 148
 149 #define INIT_CIDR(cidr, host_mask)      \
 150         DCIDR_PUT(((cidr) ? NCIDR_GET(cidr) : host_mask))
 151
 152 #define SET_HOST_MASK(family)   (family == AF_INET ? 32 : 128)
 153
 154 #ifdef IP_SET_HASH_WITH_NET0
 155 #define NLEN(family)            (SET_HOST_MASK(family) + 1)
 156 #else
 157 #define NLEN(family)            SET_HOST_MASK(family)
 158 #endif
 159
 160 #else
 161 #define NLEN(family)            0
 162 #endif /* IP_SET_HASH_WITH_NETS */
 163
 164 #endif /* _IP_SET_HASH_GEN_H */
 165
 166 /* Family dependent templates */
 167
 168 #undef ahash_data
 169 #undef mtype_data_equal
 170 #undef mtype_do_data_match
 171 #undef mtype_data_set_flags
 172 #undef mtype_data_reset_elem
 173 #undef mtype_data_reset_flags
 174 #undef mtype_data_netmask
 175 #undef mtype_data_list
 176 #undef mtype_data_next
 177 #undef mtype_elem
 178
 179 #undef mtype_ahash_destroy
 180 #undef mtype_ext_cleanup
 181 #undef mtype_add_cidr
 182 #undef mtype_del_cidr
 183 #undef mtype_ahash_memsize
 184 #undef mtype_flush
 185 #undef mtype_destroy
 186 #undef mtype_same_set
 187 #undef mtype_kadt
 188 #undef mtype_uadt
 189 #undef mtype
 190
 191 #undef mtype_add
 192 #undef mtype_del
 193 #undef mtype_test_cidrs
 194 #undef mtype_test
 195 #undef mtype_uref
 196 #undef mtype_expire
 197 #undef mtype_resize
 198 #undef mtype_head
 199 #undef mtype_list
 200 #undef mtype_gc
 201 #undef mtype_gc_init
 202 #undef mtype_variant
 203 #undef mtype_data_match
 204
 205 #undef HKEY
 206
 207 #define mtype_data_equal        IPSET_TOKEN(MTYPE, _data_equal)
 208 #ifdef IP_SET_HASH_WITH_NETS
 209 #define mtype_do_data_match     IPSET_TOKEN(MTYPE, _do_data_match)
 210 #else
 211 #define mtype_do_data_match(d)  1
 212 #endif
 213 #define mtype_data_set_flags    IPSET_TOKEN(MTYPE, _data_set_flags)
 214 #define mtype_data_reset_elem   IPSET_TOKEN(MTYPE, _data_reset_elem)
 215 #define mtype_data_reset_flags  IPSET_TOKEN(MTYPE, _data_reset_flags)
 216 #define mtype_data_netmask      IPSET_TOKEN(MTYPE, _data_netmask)
 217 #define mtype_data_list         IPSET_TOKEN(MTYPE, _data_list)
 218 #define mtype_data_next         IPSET_TOKEN(MTYPE, _data_next)
 219 #define mtype_elem              IPSET_TOKEN(MTYPE, _elem)
 220
 221 #define mtype_ahash_destroy     IPSET_TOKEN(MTYPE, _ahash_destroy)
 222 #define mtype_ext_cleanup       IPSET_TOKEN(MTYPE, _ext_cleanup)
 223 #define mtype_add_cidr          IPSET_TOKEN(MTYPE, _add_cidr)
 224 #define mtype_del_cidr          IPSET_TOKEN(MTYPE, _del_cidr)
 225 #define mtype_ahash_memsize     IPSET_TOKEN(MTYPE, _ahash_memsize)
 226 #define mtype_flush             IPSET_TOKEN(MTYPE, _flush)
 227 #define mtype_destroy           IPSET_TOKEN(MTYPE, _destroy)
 228 #define mtype_same_set          IPSET_TOKEN(MTYPE, _same_set)
 229 #define mtype_kadt              IPSET_TOKEN(MTYPE, _kadt)
 230 #define mtype_uadt              IPSET_TOKEN(MTYPE, _uadt)
 231 #define mtype                   MTYPE
 232
 233 #define mtype_add               IPSET_TOKEN(MTYPE, _add)
 234 #define mtype_del               IPSET_TOKEN(MTYPE, _del)
 235 #define mtype_test_cidrs        IPSET_TOKEN(MTYPE, _test_cidrs)
 236 #define mtype_test              IPSET_TOKEN(MTYPE, _test)
 237 #define mtype_uref              IPSET_TOKEN(MTYPE, _uref)
 238 #define mtype_expire            IPSET_TOKEN(MTYPE, _expire)
 239 #define mtype_resize            IPSET_TOKEN(MTYPE, _resize)
 240 #define mtype_head              IPSET_TOKEN(MTYPE, _head)
 241 #define mtype_list              IPSET_TOKEN(MTYPE, _list)
 242 #define mtype_gc                IPSET_TOKEN(MTYPE, _gc)
 243 #define mtype_gc_init           IPSET_TOKEN(MTYPE, _gc_init)
 244 #define mtype_variant           IPSET_TOKEN(MTYPE, _variant)
 245 #define mtype_data_match        IPSET_TOKEN(MTYPE, _data_match)
 246
 247 #ifndef MTYPE
 248 #error "MTYPE is not defined!"
 249 #endif
 250
 251 #ifndef HOST_MASK
 252 #error "HOST_MASK is not defined!"
 253 #endif
 254
 255 #ifndef HKEY_DATALEN
 256 #define HKEY_DATALEN            sizeof(struct mtype_elem)
 257 #endif
 258
 259 #define HKEY(data, initval, htable_bits)                        \
 260 (jhash2((u32 *)(data), HKEY_DATALEN / sizeof(u32), initval)     \
 261         & jhash_mask(htable_bits))
 262
 263 #ifndef htype
 264 #ifndef HTYPE
 265 #error "HTYPE is not defined!"
 266 #endif /* HTYPE */
 267 #define htype                   HTYPE
 268
 269 /* The generic hash structure */
 270 struct htype {
 271         struct htable __rcu *table; /* the hash table */
 272         u32 maxelem;            /* max elements in the hash */
 273         u32 elements;           /* current element (vs timeout) */
 274         u32 initval;            /* random jhash init value */
 275 #ifdef IP_SET_HASH_WITH_MARKMASK
 276         u32 markmask;           /* markmask value for mark mask to store */
 277 #endif
 278         struct timer_list gc;   /* garbage collection when timeout enabled */
 279         struct mtype_elem next; /* temporary storage for uadd */
 280 #ifdef IP_SET_HASH_WITH_MULTI
 281         u8 ahash_max;           /* max elements in an array block */
 282 #endif
 283 #ifdef IP_SET_HASH_WITH_NETMASK
 284         u8 netmask;             /* netmask value for subnets to store */
 285 #endif
 286 #ifdef IP_SET_HASH_WITH_NETS
 287         struct net_prefixes nets[0]; /* book-keeping of prefixes */
 288 #endif
 289 };
 290 #endif /* htype */
 291
 292 #ifdef IP_SET_HASH_WITH_NETS
 293 /* Network cidr size book keeping when the hash stores different
 294  * sized networks. cidr == real cidr + 1 to support /0.
 295  */
 296 static void
 297 mtype_add_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n)
 298 {
 299         int i, j;
 300
 301         /* Add in increasing prefix order, so larger cidr first */
 302         for (i = 0, j = -1; i < nets_length && h->nets[i].cidr[n]; i++) {
 303                 if (j != -1) {
 304                         continue;
 305                 } else if (h->nets[i].cidr[n] < cidr) {
 306                         j = i;
 307                 } else if (h->nets[i].cidr[n] == cidr) {
 308                         h->nets[cidr - 1].nets[n]++;
 309                         return;
 310                 }
 311         }
 312         if (j != -1) {
 313                 for (; i > j; i--)
 314                         h->nets[i].cidr[n] = h->nets[i - 1].cidr[n];
 315         }
 316         h->nets[i].cidr[n] = cidr;
 317         h->nets[cidr - 1].nets[n] = 1;
 318 }
 319
 320 static void
 321 mtype_del_cidr(struct htype *h, u8 cidr, u8 nets_length, u8 n)
 322 {
 323         u8 i, j, net_end = nets_length - 1;
 324
 325         for (i = 0; i < nets_length; i++) {
 326                 if (h->nets[i].cidr[n] != cidr)
 327                         continue;
 328                 h->nets[cidr - 1].nets[n]--;
 329                 if (h->nets[cidr - 1].nets[n] > 0)
 330                         return;
 331                 for (j = i; j < net_end && h->nets[j].cidr[n]; j++)
 332                         h->nets[j].cidr[n] = h->nets[j + 1].cidr[n];
 333                 h->nets[j].cidr[n] = 0;
 334                 return;
 335         }
 336 }
 337 #endif
 338
 339 /* Calculate the actual memory size of the set data */
 340 static size_t
 341 mtype_ahash_memsize(const struct htype *h, const struct htable *t,
 342                     u8 nets_length, size_t dsize)
 343 {
 344         u32 i;
 345         struct hbucket *n;
 346         size_t memsize = sizeof(*h) + sizeof(*t);
 347
 348 #ifdef IP_SET_HASH_WITH_NETS
 349         memsize += sizeof(struct net_prefixes) * nets_length;
 350 #endif
 351         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 352                 n = rcu_dereference_bh(hbucket(t, i));
 353                 if (!n)
 354                         continue;
 355                 memsize += sizeof(struct hbucket) + n->size * dsize;
 356         }
 357
 358         return memsize;
 359 }
 360
 361 /* Get the ith element from the array block n */
 362 #define ahash_data(n, i, dsize) \
 363         ((struct mtype_elem *)((n)->value + ((i) * (dsize))))
 364
 365 static void
 366 mtype_ext_cleanup(struct ip_set *set, struct hbucket *n)
 367 {
 368         int i;
 369
 370         for (i = 0; i < n->pos; i++)
 371                 if (test_bit(i, n->used))
 372                         ip_set_ext_destroy(set, ahash_data(n, i, set->dsize));
 373 }
 374
 375 /* Flush a hash type of set: destroy all elements */
 376 static void
 377 mtype_flush(struct ip_set *set)
 378 {
 379         struct htype *h = set->data;
 380         struct htable *t;
 381         struct hbucket *n;
 382         u32 i;
 383
 384         t = ipset_dereference_protected(h->table, set);
 385         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 386                 n = __ipset_dereference_protected(hbucket(t, i), 1);
 387                 if (!n)
 388                         continue;
 389                 if (set->extensions & IPSET_EXT_DESTROY)
 390                         mtype_ext_cleanup(set, n);
 391                 /* FIXME: use slab cache */
 392                 rcu_assign_pointer(hbucket(t, i), NULL);
 393                 kfree_rcu(n, rcu);
 394         }
 395 #ifdef IP_SET_HASH_WITH_NETS
 396         memset(h->nets, 0, sizeof(struct net_prefixes) * NLEN(set->family));
 397 #endif
 398         h->elements = 0;
 399 }
 400
 401 /* Destroy the hashtable part of the set */
 402 static void
 403 mtype_ahash_destroy(struct ip_set *set, struct htable *t, bool ext_destroy)
 404 {
 405         struct hbucket *n;
 406         u32 i;
 407
 408         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 409                 n = __ipset_dereference_protected(hbucket(t, i), 1);
 410                 if (!n)
 411                         continue;
 412                 if (set->extensions & IPSET_EXT_DESTROY && ext_destroy)
 413                         mtype_ext_cleanup(set, n);
 414                 /* FIXME: use slab cache */
 415                 kfree(n);
 416         }
 417
 418         ip_set_free(t);
 419 }
 420
 421 /* Destroy a hash type of set */
 422 static void
 423 mtype_destroy(struct ip_set *set)
 424 {
 425         struct htype *h = set->data;
 426
 427         if (SET_WITH_TIMEOUT(set))
 428                 del_timer_sync(&h->gc);
 429
 430         mtype_ahash_destroy(set,
 431                             __ipset_dereference_protected(h->table, 1), true);
 432         kfree(h);
 433
 434         set->data = NULL;
 435 }
 436
 437 static void
 438 mtype_gc_init(struct ip_set *set, void (*gc)(unsigned long ul_set))
 439 {
 440         struct htype *h = set->data;
 441
 442         init_timer(&h->gc);
 443         h->gc.data = (unsigned long)set;
 444         h->gc.function = gc;
 445         h->gc.expires = jiffies + IPSET_GC_PERIOD(set->timeout) * HZ;
 446         add_timer(&h->gc);
 447         pr_debug("gc initialized, run in every %u\n",
 448                  IPSET_GC_PERIOD(set->timeout));
 449 }
 450
 451 static bool
 452 mtype_same_set(const struct ip_set *a, const struct ip_set *b)
 453 {
 454         const struct htype *x = a->data;
 455         const struct htype *y = b->data;
 456
 457         /* Resizing changes htable_bits, so we ignore it */
 458         return x->maxelem == y->maxelem &&
 459                a->timeout == b->timeout &&
 460 #ifdef IP_SET_HASH_WITH_NETMASK
 461                x->netmask == y->netmask &&
 462 #endif
 463 #ifdef IP_SET_HASH_WITH_MARKMASK
 464                x->markmask == y->markmask &&
 465 #endif
 466                a->extensions == b->extensions;
 467 }
 468
 469 /* Delete expired elements from the hashtable */
 470 static void
 471 mtype_expire(struct ip_set *set, struct htype *h, u8 nets_length, size_t dsize)
 472 {
 473         struct htable *t;
 474         struct hbucket *n;
 475         struct mtype_elem *data;
 476         u32 i, j, d;
 477 #ifdef IP_SET_HASH_WITH_NETS
 478         u8 k;
 479 #endif
 480
 481         t = ipset_dereference_protected(h->table, set);
 482         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 483                 n = __ipset_dereference_protected(hbucket(t, i), 1);
 484                 if (!n)
 485                         continue;
 486                 for (j = 0, d = 0; j < n->pos; j++) {
 487                         if (!test_bit(j, n->used)) {
 488                                 d++;
 489                                 continue;
 490                         }
 491                         data = ahash_data(n, j, dsize);
 492                         if (ip_set_timeout_expired(ext_timeout(data, set))) {
 493                                 pr_debug("expired %u/%u\n", i, j);
 494                                 clear_bit(j, n->used);
 495                                 smp_mb__after_atomic();
 496 #ifdef IP_SET_HASH_WITH_NETS
 497                                 for (k = 0; k < IPSET_NET_COUNT; k++)
 498                                         mtype_del_cidr(h,
 499                                                 NCIDR_PUT(DCIDR_GET(data->cidr,
 500                                                                     k)),
 501                                                 nets_length, k);
 502 #endif
 503                                 ip_set_ext_destroy(set, data);
 504                                 h->elements--;
 505                                 d++;
 506                         }
 507                 }
 508                 if (d >= AHASH_INIT_SIZE) {
 509                         struct hbucket *tmp = kzalloc(sizeof(*tmp) +
 510                                         (n->size - AHASH_INIT_SIZE) * dsize,
 511                                         GFP_ATOMIC);
 512                         if (!tmp)
 513                                 /* Still try to delete expired elements */
 514                                 continue;
 515                         tmp->size = n->size - AHASH_INIT_SIZE;
 516                         for (j = 0, d = 0; j < n->pos; j++) {
 517                                 if (!test_bit(j, n->used))
 518                                         continue;
 519                                 data = ahash_data(n, j, dsize);
 520                                 memcpy(tmp->value + d * dsize, data, dsize);
 521                                 set_bit(j, tmp->used);
 522                                 d++;
 523                         }
 524                         tmp->pos = d;
 525                         rcu_assign_pointer(hbucket(t, i), tmp);
 526                         kfree_rcu(n, rcu);
 527                 }
 528         }
 529 }
 530
 531 static void
 532 mtype_gc(unsigned long ul_set)
 533 {
 534         struct ip_set *set = (struct ip_set *)ul_set;
 535         struct htype *h = set->data;
 536
 537         pr_debug("called\n");
 538         spin_lock_bh(&set->lock);
 539         mtype_expire(set, h, NLEN(set->family), set->dsize);
 540         spin_unlock_bh(&set->lock);
 541
 542         h->gc.expires = jiffies + IPSET_GC_PERIOD(set->timeout) * HZ;
 543         add_timer(&h->gc);
 544 }
 545
 546 /* Resize a hash: create a new hash table with doubling the hashsize
 547  * and inserting the elements to it. Repeat until we succeed or
 548  * fail due to memory pressures.
 549  */
 550 static int
 551 mtype_resize(struct ip_set *set, bool retried)
 552 {
 553         struct htype *h = set->data;
 554         struct htable *t, *orig;
 555         u8 htable_bits;
 556         size_t dsize = set->dsize;
 557 #ifdef IP_SET_HASH_WITH_NETS
 558         u8 flags;
 559         struct mtype_elem *tmp;
 560 #endif
 561         struct mtype_elem *data;
 562         struct mtype_elem *d;
 563         struct hbucket *n, *m;
 564         u32 i, j, key;
 565         int ret;
 566
 567 #ifdef IP_SET_HASH_WITH_NETS
 568         tmp = kmalloc(dsize, GFP_KERNEL);
 569         if (!tmp)
 570                 return -ENOMEM;
 571 #endif
 572         rcu_read_lock_bh();
 573         orig = rcu_dereference_bh_nfnl(h->table);
 574         htable_bits = orig->htable_bits;
 575         rcu_read_unlock_bh();
 576
 577 retry:
 578         ret = 0;
 579         htable_bits++;
 580         if (!htable_bits) {
 581                 /* In case we have plenty of memory :-) */
 582                 pr_warn("Cannot increase the hashsize of set %s further\n",
 583                         set->name);
 584                 ret = -IPSET_ERR_HASH_FULL;
 585                 goto out;
 586         }
 587         t = ip_set_alloc(htable_size(htable_bits));
 588         if (!t) {
 589                 ret = -ENOMEM;
 590                 goto out;
 591         }
 592         t->htable_bits = htable_bits;
 593
 594         spin_lock_bh(&set->lock);
 595         orig = __ipset_dereference_protected(h->table, 1);
 596         /* There can't be another parallel resizing, but dumping is possible */
 597         atomic_set(&orig->ref, 1);
 598         atomic_inc(&orig->uref);
 599         pr_debug("attempt to resize set %s from %u to %u, t %p\n",
 600                  set->name, orig->htable_bits, htable_bits, orig);
 601         for (i = 0; i < jhash_size(orig->htable_bits); i++) {
 602                 n = __ipset_dereference_protected(hbucket(orig, i), 1);
 603                 if (!n)
 604                         continue;
 605                 for (j = 0; j < n->pos; j++) {
 606                         if (!test_bit(j, n->used))
 607                                 continue;
 608                         data = ahash_data(n, j, dsize);
 609 #ifdef IP_SET_HASH_WITH_NETS
 610                         /* We have readers running parallel with us,
 611                          * so the live data cannot be modified.
 612                          */
 613                         flags = 0;
 614                         memcpy(tmp, data, dsize);
 615                         data = tmp;
 616                         mtype_data_reset_flags(data, &flags);
 617 #endif
 618                         key = HKEY(data, h->initval, htable_bits);
 619                         m = __ipset_dereference_protected(hbucket(t, key), 1);
 620                         if (!m) {
 621                                 m = kzalloc(sizeof(*m) +
 622                                             AHASH_INIT_SIZE * dsize,
 623                                             GFP_ATOMIC);
 624                                 if (!m) {
 625                                         ret = -ENOMEM;
 626                                         goto cleanup;
 627                                 }
 628                                 m->size = AHASH_INIT_SIZE;
 629                                 RCU_INIT_POINTER(hbucket(t, key), m);
 630                         } else if (m->pos >= m->size) {
 631                                 struct hbucket *ht;
 632
 633                                 if (m->size >= AHASH_MAX(h)) {
 634                                         ret = -EAGAIN;
 635                                 } else {
 636                                         ht = kzalloc(sizeof(*ht) +
 637                                                 (m->size + AHASH_INIT_SIZE)
 638                                                 * dsize,
 639                                                 GFP_ATOMIC);
 640                                         if (!ht)
 641                                                 ret = -ENOMEM;
 642                                 }
 643                                 if (ret < 0)
 644                                         goto cleanup;
 645                                 memcpy(ht, m, sizeof(struct hbucket) +
 646                                               m->size * dsize);
 647                                 ht->size = m->size + AHASH_INIT_SIZE;
 648                                 kfree(m);
 649                                 m = ht;
 650                                 RCU_INIT_POINTER(hbucket(t, key), ht);
 651                         }
 652                         d = ahash_data(m, m->pos, dsize);
 653                         memcpy(d, data, dsize);
 654                         set_bit(m->pos++, m->used);
 655 #ifdef IP_SET_HASH_WITH_NETS
 656                         mtype_data_reset_flags(d, &flags);
 657 #endif
 658                 }
 659         }
 660         rcu_assign_pointer(h->table, t);
 661
 662         spin_unlock_bh(&set->lock);
 663
 664         /* Give time to other readers of the set */
 665         synchronize_rcu_bh();
 666
 667         pr_debug("set %s resized from %u (%p) to %u (%p)\n", set->name,
 668                  orig->htable_bits, orig, t->htable_bits, t);
 669         /* If there's nobody else dumping the table, destroy it */
 670         if (atomic_dec_and_test(&orig->uref)) {
 671                 pr_debug("Table destroy by resize %p\n", orig);
 672                 mtype_ahash_destroy(set, orig, false);
 673         }
 674
 675 out:
 676 #ifdef IP_SET_HASH_WITH_NETS
 677         kfree(tmp);
 678 #endif
 679         return ret;
 680
 681 cleanup:
 682         atomic_set(&orig->ref, 0);
 683         atomic_dec(&orig->uref);
 684         spin_unlock_bh(&set->lock);
 685         mtype_ahash_destroy(set, t, false);
 686         if (ret == -EAGAIN)
 687                 goto retry;
 688         goto out;
 689 }
 690
 691 /* Add an element to a hash and update the internal counters when succeeded,
 692  * otherwise report the proper error code.
 693  */
 694 static int
 695 mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext,
 696           struct ip_set_ext *mext, u32 flags)
 697 {
 698         struct htype *h = set->data;
 699         struct htable *t;
 700         const struct mtype_elem *d = value;
 701         struct mtype_elem *data;
 702         struct hbucket *n, *old = ERR_PTR(-ENOENT);
 703         int i, j = -1;
 704         bool flag_exist = flags & IPSET_FLAG_EXIST;
 705         bool deleted = false, forceadd = false, reuse = false;
 706         u32 key, multi = 0;
 707
 708         if (h->elements >= h->maxelem) {
 709                 if (SET_WITH_TIMEOUT(set))
 710                         /* FIXME: when set is full, we slow down here */
 711                         mtype_expire(set, h, NLEN(set->family), set->dsize);
 712                 if (h->elements >= h->maxelem && SET_WITH_FORCEADD(set))
 713                         forceadd = true;
 714         }
 715
 716         t = ipset_dereference_protected(h->table, set);
 717         key = HKEY(value, h->initval, t->htable_bits);
 718         n = __ipset_dereference_protected(hbucket(t, key), 1);
 719         if (!n) {
 720                 if (forceadd) {
 721                         if (net_ratelimit())
 722                                 pr_warn("Set %s is full, maxelem %u reached\n",
 723                                         set->name, h->maxelem);
 724                         return -IPSET_ERR_HASH_FULL;
 725                 } else if (h->elements >= h->maxelem) {
 726                         goto set_full;
 727                 }
 728                 old = NULL;
 729                 n = kzalloc(sizeof(*n) + AHASH_INIT_SIZE * set->dsize,
 730                             GFP_ATOMIC);
 731                 if (!n)
 732                         return -ENOMEM;
 733                 n->size = AHASH_INIT_SIZE;
 734                 goto copy_elem;
 735         }
 736         for (i = 0; i < n->pos; i++) {
 737                 if (!test_bit(i, n->used)) {
 738                         /* Reuse first deleted entry */
 739                         if (j == -1) {
 740                                 deleted = reuse = true;
 741                                 j = i;
 742                         }
 743                         continue;
 744                 }
 745                 data = ahash_data(n, i, set->dsize);
 746                 if (mtype_data_equal(data, d, &multi)) {
 747                         if (flag_exist ||
 748                             (SET_WITH_TIMEOUT(set) &&
 749                              ip_set_timeout_expired(ext_timeout(data, set)))) {
 750                                 /* Just the extensions could be overwritten */
 751                                 j = i;
 752                                 goto overwrite_extensions;
 753                         }
 754                         return -IPSET_ERR_EXIST;
 755                 }
 756                 /* Reuse first timed out entry */
 757                 if (SET_WITH_TIMEOUT(set) &&
 758                     ip_set_timeout_expired(ext_timeout(data, set)) &&
 759                     j == -1) {
 760                         j = i;
 761                         reuse = true;
 762                 }
 763         }
 764         if (reuse || forceadd) {
 765                 data = ahash_data(n, j, set->dsize);
 766                 if (!deleted) {
 767 #ifdef IP_SET_HASH_WITH_NETS
 768                         for (i = 0; i < IPSET_NET_COUNT; i++)
 769                                 mtype_del_cidr(h,
 770                                         NCIDR_PUT(DCIDR_GET(data->cidr, i)),
 771                                         NLEN(set->family), i);
 772 #endif
 773                         ip_set_ext_destroy(set, data);
 774                         h->elements--;
 775                 }
 776                 goto copy_data;
 777         }
 778         if (h->elements >= h->maxelem)
 779                 goto set_full;
 780         /* Create a new slot */
 781         if (n->pos >= n->size) {
 782                 TUNE_AHASH_MAX(h, multi);
 783                 if (n->size >= AHASH_MAX(h)) {
 784                         /* Trigger rehashing */
 785                         mtype_data_next(&h->next, d);
 786                         return -EAGAIN;
 787                 }
 788                 old = n;
 789                 n = kzalloc(sizeof(*n) +
 790                             (old->size + AHASH_INIT_SIZE) * set->dsize,
 791                             GFP_ATOMIC);
 792                 if (!n)
 793                         return -ENOMEM;
 794                 memcpy(n, old, sizeof(struct hbucket) +
 795                        old->size * set->dsize);
 796                 n->size = old->size + AHASH_INIT_SIZE;
 797         }
 798
 799 copy_elem:
 800         j = n->pos++;
 801         data = ahash_data(n, j, set->dsize);
 802 copy_data:
 803         h->elements++;
 804 #ifdef IP_SET_HASH_WITH_NETS
 805         for (i = 0; i < IPSET_NET_COUNT; i++)
 806                 mtype_add_cidr(h, NCIDR_PUT(DCIDR_GET(d->cidr, i)),
 807                                NLEN(set->family), i);
 808 #endif
 809         memcpy(data, d, sizeof(struct mtype_elem));
 810 overwrite_extensions:
 811 #ifdef IP_SET_HASH_WITH_NETS
 812         mtype_data_set_flags(data, flags);
 813 #endif
 814         if (SET_WITH_COUNTER(set))
 815                 ip_set_init_counter(ext_counter(data, set), ext);
 816         if (SET_WITH_COMMENT(set))
 817                 ip_set_init_comment(ext_comment(data, set), ext);
 818         if (SET_WITH_SKBINFO(set))
 819                 ip_set_init_skbinfo(ext_skbinfo(data, set), ext);
 820         /* Must come last for the case when timed out entry is reused */
 821         if (SET_WITH_TIMEOUT(set))
 822                 ip_set_timeout_set(ext_timeout(data, set), ext->timeout);
 823         smp_mb__before_atomic();
 824         set_bit(j, n->used);
 825         if (old != ERR_PTR(-ENOENT)) {
 826                 rcu_assign_pointer(hbucket(t, key), n);
 827                 if (old)
 828                         kfree_rcu(old, rcu);
 829         }
 830
 831         return 0;
 832 set_full:
 833         if (net_ratelimit())
 834                 pr_warn("Set %s is full, maxelem %u reached\n",
 835                         set->name, h->maxelem);
 836         return -IPSET_ERR_HASH_FULL;
 837 }
 838
 839 /* Delete an element from the hash and free up space if possible.
 840  */
 841 static int
 842 mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext,
 843           struct ip_set_ext *mext, u32 flags)
 844 {
 845         struct htype *h = set->data;
 846         struct htable *t;
 847         const struct mtype_elem *d = value;
 848         struct mtype_elem *data;
 849         struct hbucket *n;
 850         int i, j, k, ret = -IPSET_ERR_EXIST;
 851         u32 key, multi = 0;
 852         size_t dsize = set->dsize;
 853
 854         t = ipset_dereference_protected(h->table, set);
 855         key = HKEY(value, h->initval, t->htable_bits);
 856         n = __ipset_dereference_protected(hbucket(t, key), 1);
 857         if (!n)
 858                 goto out;
 859         for (i = 0, k = 0; i < n->pos; i++) {
 860                 if (!test_bit(i, n->used)) {
 861                         k++;
 862                         continue;
 863                 }
 864                 data = ahash_data(n, i, dsize);
 865                 if (!mtype_data_equal(data, d, &multi))
 866                         continue;
 867                 if (SET_WITH_TIMEOUT(set) &&
 868                     ip_set_timeout_expired(ext_timeout(data, set)))
 869                         goto out;
 870
 871                 ret = 0;
 872                 clear_bit(i, n->used);
 873                 smp_mb__after_atomic();
 874                 if (i + 1 == n->pos)
 875                         n->pos--;
 876                 h->elements--;
 877 #ifdef IP_SET_HASH_WITH_NETS
 878                 for (j = 0; j < IPSET_NET_COUNT; j++)
 879                         mtype_del_cidr(h, NCIDR_PUT(DCIDR_GET(d->cidr, j)),
 880                                        NLEN(set->family), j);
 881 #endif
 882                 ip_set_ext_destroy(set, data);
 883
 884                 for (; i < n->pos; i++) {
 885                         if (!test_bit(i, n->used))
 886                                 k++;
 887                 }
 888                 if (n->pos == 0 && k == 0) {
 889                         rcu_assign_pointer(hbucket(t, key), NULL);
 890                         kfree_rcu(n, rcu);
 891                 } else if (k >= AHASH_INIT_SIZE) {
 892                         struct hbucket *tmp = kzalloc(sizeof(*tmp) +
 893                                         (n->size - AHASH_INIT_SIZE) * dsize,
 894                                         GFP_ATOMIC);
 895                         if (!tmp)
 896                                 goto out;
 897                         tmp->size = n->size - AHASH_INIT_SIZE;
 898                         for (j = 0, k = 0; j < n->pos; j++) {
 899                                 if (!test_bit(j, n->used))
 900                                         continue;
 901                                 data = ahash_data(n, j, dsize);
 902                                 memcpy(tmp->value + k * dsize, data, dsize);
 903                                 set_bit(j, tmp->used);
 904                                 k++;
 905                         }
 906                         tmp->pos = k;
 907                         rcu_assign_pointer(hbucket(t, key), tmp);
 908                         kfree_rcu(n, rcu);
 909                 }
 910                 goto out;
 911         }
 912
 913 out:
 914         return ret;
 915 }
 916
 917 static inline int
 918 mtype_data_match(struct mtype_elem *data, const struct ip_set_ext *ext,
 919                  struct ip_set_ext *mext, struct ip_set *set, u32 flags)
 920 {
 921         if (SET_WITH_COUNTER(set))
 922                 ip_set_update_counter(ext_counter(data, set),
 923                                       ext, mext, flags);
 924         if (SET_WITH_SKBINFO(set))
 925                 ip_set_get_skbinfo(ext_skbinfo(data, set),
 926                                    ext, mext, flags);
 927         return mtype_do_data_match(data);
 928 }
 929
 930 #ifdef IP_SET_HASH_WITH_NETS
 931 /* Special test function which takes into account the different network
 932  * sizes added to the set
 933  */
 934 static int
 935 mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d,
 936                  const struct ip_set_ext *ext,
 937                  struct ip_set_ext *mext, u32 flags)
 938 {
 939         struct htype *h = set->data;
 940         struct htable *t = rcu_dereference_bh(h->table);
 941         struct hbucket *n;
 942         struct mtype_elem *data;
 943 #if IPSET_NET_COUNT == 2
 944         struct mtype_elem orig = *d;
 945         int i, j = 0, k;
 946 #else
 947         int i, j = 0;
 948 #endif
 949         u32 key, multi = 0;
 950         u8 nets_length = NLEN(set->family);
 951
 952         pr_debug("test by nets\n");
 953         for (; j < nets_length && h->nets[j].cidr[0] && !multi; j++) {
 954 #if IPSET_NET_COUNT == 2
 955                 mtype_data_reset_elem(d, &orig);
 956                 mtype_data_netmask(d, NCIDR_GET(h->nets[j].cidr[0]), false);
 957                 for (k = 0; k < nets_length && h->nets[k].cidr[1] && !multi;
 958                      k++) {
 959                         mtype_data_netmask(d, NCIDR_GET(h->nets[k].cidr[1]),
 960                                            true);
 961 #else
 962                 mtype_data_netmask(d, NCIDR_GET(h->nets[j].cidr[0]));
 963 #endif
 964                 key = HKEY(d, h->initval, t->htable_bits);
 965                 n =  rcu_dereference_bh(hbucket(t, key));
 966                 if (!n)
 967                         continue;
 968                 for (i = 0; i < n->pos; i++) {
 969                         if (!test_bit(i, n->used))
 970                                 continue;
 971                         data = ahash_data(n, i, set->dsize);
 972                         if (!mtype_data_equal(data, d, &multi))
 973                                 continue;
 974                         if (SET_WITH_TIMEOUT(set)) {
 975                                 if (!ip_set_timeout_expired(
 976                                                 ext_timeout(data, set)))
 977                                         return mtype_data_match(data, ext,
 978                                                                 mext, set,
 979                                                                 flags);
 980 #ifdef IP_SET_HASH_WITH_MULTI
 981                                 multi = 0;
 982 #endif
 983                         } else
 984                                 return mtype_data_match(data, ext,
 985                                                         mext, set, flags);
 986                 }
 987 #if IPSET_NET_COUNT == 2
 988                 }
 989 #endif
 990         }
 991         return 0;
 992 }
 993 #endif
 994
 995 /* Test whether the element is added to the set */
 996 static int
 997 mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext,
 998            struct ip_set_ext *mext, u32 flags)
 999 {
1000         struct htype *h = set->data;
1001         struct htable *t;
1002         struct mtype_elem *d = value;
1003         struct hbucket *n;
1004         struct mtype_elem *data;
1005         int i, ret = 0;
1006         u32 key, multi = 0;
1007
1008         t = rcu_dereference_bh(h->table);
1009 #ifdef IP_SET_HASH_WITH_NETS
1010         /* If we test an IP address and not a network address,
1011          * try all possible network sizes
1012          */
1013         for (i = 0; i < IPSET_NET_COUNT; i++)
1014                 if (DCIDR_GET(d->cidr, i) != SET_HOST_MASK(set->family))
1015                         break;
1016         if (i == IPSET_NET_COUNT) {
1017                 ret = mtype_test_cidrs(set, d, ext, mext, flags);
1018                 goto out;
1019         }
1020 #endif
1021
1022         key = HKEY(d, h->initval, t->htable_bits);
1023         n = rcu_dereference_bh(hbucket(t, key));
1024         if (!n) {
1025                 ret = 0;
1026                 goto out;
1027         }
1028         for (i = 0; i < n->pos; i++) {
1029                 if (!test_bit(i, n->used))
1030                         continue;
1031                 data = ahash_data(n, i, set->dsize);
1032                 if (mtype_data_equal(data, d, &multi) &&
1033                     !(SET_WITH_TIMEOUT(set) &&
1034                       ip_set_timeout_expired(ext_timeout(data, set)))) {
1035                         ret = mtype_data_match(data, ext, mext, set, flags);
1036                         goto out;
1037                 }
1038         }
1039 out:
1040         return ret;
1041 }
1042
1043 /* Reply a HEADER request: fill out the header part of the set */
1044 static int
1045 mtype_head(struct ip_set *set, struct sk_buff *skb)
1046 {
1047         const struct htype *h = set->data;
1048         const struct htable *t;
1049         struct nlattr *nested;
1050         size_t memsize;
1051         u8 htable_bits;
1052
1053         rcu_read_lock_bh();
1054         t = rcu_dereference_bh_nfnl(h->table);
1055         memsize = mtype_ahash_memsize(h, t, NLEN(set->family), set->dsize);
1056         htable_bits = t->htable_bits;
1057         rcu_read_unlock_bh();
1058
1059         nested = ipset_nest_start(skb, IPSET_ATTR_DATA);
1060         if (!nested)
1061                 goto nla_put_failure;
1062         if (nla_put_net32(skb, IPSET_ATTR_HASHSIZE,
1063                           htonl(jhash_size(htable_bits))) ||
1064             nla_put_net32(skb, IPSET_ATTR_MAXELEM, htonl(h->maxelem)))
1065                 goto nla_put_failure;
1066 #ifdef IP_SET_HASH_WITH_NETMASK
1067         if (h->netmask != HOST_MASK &&
1068             nla_put_u8(skb, IPSET_ATTR_NETMASK, h->netmask))
1069                 goto nla_put_failure;
1070 #endif
1071 #ifdef IP_SET_HASH_WITH_MARKMASK
1072         if (nla_put_u32(skb, IPSET_ATTR_MARKMASK, h->markmask))
1073                 goto nla_put_failure;
1074 #endif
1075         if (nla_put_net32(skb, IPSET_ATTR_REFERENCES, htonl(set->ref - 1)) ||
1076             nla_put_net32(skb, IPSET_ATTR_MEMSIZE, htonl(memsize)))
1077                 goto nla_put_failure;
1078         if (unlikely(ip_set_put_flags(skb, set)))
1079                 goto nla_put_failure;
1080         ipset_nest_end(skb, nested);
1081
1082         return 0;
1083 nla_put_failure:
1084         return -EMSGSIZE;
1085 }
1086
1087 /* Make possible to run dumping parallel with resizing */
1088 static void
1089 mtype_uref(struct ip_set *set, struct netlink_callback *cb, bool start)
1090 {
1091         struct htype *h = set->data;
1092         struct htable *t;
1093
1094         if (start) {
1095                 rcu_read_lock_bh();
1096                 t = rcu_dereference_bh_nfnl(h->table);
1097                 atomic_inc(&t->uref);
1098                 cb->args[IPSET_CB_PRIVATE] = (unsigned long)t;
1099                 rcu_read_unlock_bh();
1100         } else if (cb->args[IPSET_CB_PRIVATE]) {
1101                 t = (struct htable *)cb->args[IPSET_CB_PRIVATE];
1102                 if (atomic_dec_and_test(&t->uref) && atomic_read(&t->ref)) {
1103                         /* Resizing didn't destroy the hash table */
1104                         pr_debug("Table destroy by dump: %p\n", t);
1105                         mtype_ahash_destroy(set, t, false);
1106                 }
1107                 cb->args[IPSET_CB_PRIVATE] = 0;
1108         }
1109 }
1110
1111 /* Reply a LIST/SAVE request: dump the elements of the specified set */
1112 static int
1113 mtype_list(const struct ip_set *set,
1114            struct sk_buff *skb, struct netlink_callback *cb)
1115 {
1116         const struct htable *t;
1117         struct nlattr *atd, *nested;
1118         const struct hbucket *n;
1119         const struct mtype_elem *e;
1120         u32 first = cb->args[IPSET_CB_ARG0];
1121         /* We assume that one hash bucket fills into one page */
1122         void *incomplete;
1123         int i, ret = 0;
1124
1125         atd = ipset_nest_start(skb, IPSET_ATTR_ADT);
1126         if (!atd)
1127                 return -EMSGSIZE;
1128
1129         pr_debug("list hash set %s\n", set->name);
1130         t = (const struct htable *)cb->args[IPSET_CB_PRIVATE];
1131         /* Expire may replace a hbucket with another one */
1132         rcu_read_lock();
1133         for (; cb->args[IPSET_CB_ARG0] < jhash_size(t->htable_bits);
1134              cb->args[IPSET_CB_ARG0]++) {
1135                 incomplete = skb_tail_pointer(skb);
1136                 n = rcu_dereference(hbucket(t, cb->args[IPSET_CB_ARG0]));
1137                 pr_debug("cb->arg bucket: %lu, t %p n %p\n",
1138                          cb->args[IPSET_CB_ARG0], t, n);
1139                 if (!n)
1140                         continue;
1141                 for (i = 0; i < n->pos; i++) {
1142                         if (!test_bit(i, n->used))
1143                                 continue;
1144                         e = ahash_data(n, i, set->dsize);
1145                         if (SET_WITH_TIMEOUT(set) &&
1146                             ip_set_timeout_expired(ext_timeout(e, set)))
1147                                 continue;
1148                         pr_debug("list hash %lu hbucket %p i %u, data %p\n",
1149                                  cb->args[IPSET_CB_ARG0], n, i, e);
1150                         nested = ipset_nest_start(skb, IPSET_ATTR_DATA);
1151                         if (!nested) {
1152                                 if (cb->args[IPSET_CB_ARG0] == first) {
1153                                         nla_nest_cancel(skb, atd);
1154                                         ret = -EMSGSIZE;
1155                                         goto out;
1156                                 }
1157                                 goto nla_put_failure;
1158                         }
1159                         if (mtype_data_list(skb, e))
1160                                 goto nla_put_failure;
1161                         if (ip_set_put_extensions(skb, set, e, true))
1162                                 goto nla_put_failure;
1163                         ipset_nest_end(skb, nested);
1164                 }
1165         }
1166         ipset_nest_end(skb, atd);
1167         /* Set listing finished */
1168         cb->args[IPSET_CB_ARG0] = 0;
1169
1170         goto out;
1171
1172 nla_put_failure:
1173         nlmsg_trim(skb, incomplete);
1174         if (unlikely(first == cb->args[IPSET_CB_ARG0])) {
1175                 pr_warn("Can't list set %s: one bucket does not fit into a message. Please report it!\n",
1176                         set->name);
1177                 cb->args[IPSET_CB_ARG0] = 0;
1178                 ret = -EMSGSIZE;
1179         } else {
1180                 ipset_nest_end(skb, atd);
1181         }
1182 out:
1183         rcu_read_unlock();
1184         return ret;
1185 }
1186
1187 static int
1188 IPSET_TOKEN(MTYPE, _kadt)(struct ip_set *set, const struct sk_buff *skb,
1189                           const struct xt_action_param *par,
1190                           enum ipset_adt adt, struct ip_set_adt_opt *opt);
1191
1192 static int
1193 IPSET_TOKEN(MTYPE, _uadt)(struct ip_set *set, struct nlattr *tb[],
1194                           enum ipset_adt adt, u32 *lineno, u32 flags,
1195                           bool retried);
1196
1197 static const struct ip_set_type_variant mtype_variant = {
1198         .kadt   = mtype_kadt,
1199         .uadt   = mtype_uadt,
1200         .adt    = {
1201                 [IPSET_ADD] = mtype_add,
1202                 [IPSET_DEL] = mtype_del,
1203                 [IPSET_TEST] = mtype_test,
1204         },
1205         .destroy = mtype_destroy,
1206         .flush  = mtype_flush,
1207         .head   = mtype_head,
1208         .list   = mtype_list,
1209         .uref   = mtype_uref,
1210         .resize = mtype_resize,
1211         .same_set = mtype_same_set,
1212 };
1213
1214 #ifdef IP_SET_EMIT_CREATE
1215 static int
1216 IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set,
1217                             struct nlattr *tb[], u32 flags)
1218 {
1219         u32 hashsize = IPSET_DEFAULT_HASHSIZE, maxelem = IPSET_DEFAULT_MAXELEM;
1220 #ifdef IP_SET_HASH_WITH_MARKMASK
1221         u32 markmask;
1222 #endif
1223         u8 hbits;
1224 #ifdef IP_SET_HASH_WITH_NETMASK
1225         u8 netmask;
1226 #endif
1227         size_t hsize;
1228         struct htype *h;
1229         struct htable *t;
1230
1231 #ifndef IP_SET_PROTO_UNDEF
1232         if (!(set->family == NFPROTO_IPV4 || set->family == NFPROTO_IPV6))
1233                 return -IPSET_ERR_INVALID_FAMILY;
1234 #endif
1235
1236 #ifdef IP_SET_HASH_WITH_MARKMASK
1237         markmask = 0xffffffff;
1238 #endif
1239 #ifdef IP_SET_HASH_WITH_NETMASK
1240         netmask = set->family == NFPROTO_IPV4 ? 32 : 128;
1241         pr_debug("Create set %s with family %s\n",
1242                  set->name, set->family == NFPROTO_IPV4 ? "inet" : "inet6");
1243 #endif
1244
1245         if (unlikely(!ip_set_optattr_netorder(tb, IPSET_ATTR_HASHSIZE) ||
1246                      !ip_set_optattr_netorder(tb, IPSET_ATTR_MAXELEM) ||
1247                      !ip_set_optattr_netorder(tb, IPSET_ATTR_TIMEOUT) ||
1248                      !ip_set_optattr_netorder(tb, IPSET_ATTR_CADT_FLAGS)))
1249                 return -IPSET_ERR_PROTOCOL;
1250 #ifdef IP_SET_HASH_WITH_MARKMASK
1251         /* Separated condition in order to avoid directive in argument list */
1252         if (unlikely(!ip_set_optattr_netorder(tb, IPSET_ATTR_MARKMASK)))
1253                 return -IPSET_ERR_PROTOCOL;
1254 #endif
1255
1256         if (tb[IPSET_ATTR_HASHSIZE]) {
1257                 hashsize = ip_set_get_h32(tb[IPSET_ATTR_HASHSIZE]);
1258                 if (hashsize < IPSET_MIMINAL_HASHSIZE)
1259                         hashsize = IPSET_MIMINAL_HASHSIZE;
1260         }
1261
1262         if (tb[IPSET_ATTR_MAXELEM])
1263                 maxelem = ip_set_get_h32(tb[IPSET_ATTR_MAXELEM]);
1264
1265 #ifdef IP_SET_HASH_WITH_NETMASK
1266         if (tb[IPSET_ATTR_NETMASK]) {
1267                 netmask = nla_get_u8(tb[IPSET_ATTR_NETMASK]);
1268
1269                 if ((set->family == NFPROTO_IPV4 && netmask > 32) ||
1270                     (set->family == NFPROTO_IPV6 && netmask > 128) ||
1271                     netmask == 0)
1272                         return -IPSET_ERR_INVALID_NETMASK;
1273         }
1274 #endif
1275 #ifdef IP_SET_HASH_WITH_MARKMASK
1276         if (tb[IPSET_ATTR_MARKMASK]) {
1277                 markmask = ntohl(nla_get_be32(tb[IPSET_ATTR_MARKMASK]));
1278
1279                 if (markmask == 0)
1280                         return -IPSET_ERR_INVALID_MARKMASK;
1281         }
1282 #endif
1283
1284         hsize = sizeof(*h);
1285 #ifdef IP_SET_HASH_WITH_NETS
1286         hsize += sizeof(struct net_prefixes) * NLEN(set->family);
1287 #endif
1288         h = kzalloc(hsize, GFP_KERNEL);
1289         if (!h)
1290                 return -ENOMEM;
1291
1292         h->maxelem = maxelem;
1293 #ifdef IP_SET_HASH_WITH_NETMASK
1294         h->netmask = netmask;
1295 #endif
1296 #ifdef IP_SET_HASH_WITH_MARKMASK
1297         h->markmask = markmask;
1298 #endif
1299         get_random_bytes(&h->initval, sizeof(h->initval));
1300         set->timeout = IPSET_NO_TIMEOUT;
1301
1302         hbits = htable_bits(hashsize);
1303         hsize = htable_size(hbits);
1304         if (hsize == 0) {
1305                 kfree(h);
1306                 return -ENOMEM;
1307         }
1308         t = ip_set_alloc(hsize);
1309         if (!t) {
1310                 kfree(h);
1311                 return -ENOMEM;
1312         }
1313         t->htable_bits = hbits;
1314         rcu_assign_pointer(h->table, t);
1315
1316         set->data = h;
1317 #ifndef IP_SET_PROTO_UNDEF
1318         if (set->family == NFPROTO_IPV4) {
1319 #endif
1320                 set->variant = &IPSET_TOKEN(HTYPE, 4_variant);
1321                 set->dsize = ip_set_elem_len(set, tb,
1322                                 sizeof(struct IPSET_TOKEN(HTYPE, 4_elem)));
1323 #ifndef IP_SET_PROTO_UNDEF
1324         } else {
1325                 set->variant = &IPSET_TOKEN(HTYPE, 6_variant);
1326                 set->dsize = ip_set_elem_len(set, tb,
1327                                 sizeof(struct IPSET_TOKEN(HTYPE, 6_elem)));
1328         }
1329 #endif
1330         if (tb[IPSET_ATTR_TIMEOUT]) {
1331                 set->timeout = ip_set_timeout_uget(tb[IPSET_ATTR_TIMEOUT]);
1332 #ifndef IP_SET_PROTO_UNDEF
1333                 if (set->family == NFPROTO_IPV4)
1334 #endif
1335                         IPSET_TOKEN(HTYPE, 4_gc_init)(set,
1336                                 IPSET_TOKEN(HTYPE, 4_gc));
1337 #ifndef IP_SET_PROTO_UNDEF
1338                 else
1339                         IPSET_TOKEN(HTYPE, 6_gc_init)(set,
1340                                 IPSET_TOKEN(HTYPE, 6_gc));
1341 #endif
1342         }
1343         pr_debug("create %s hashsize %u (%u) maxelem %u: %p(%p)\n",
1344                  set->name, jhash_size(t->htable_bits),
1345                  t->htable_bits, h->maxelem, set->data, t);
1346
1347         return 0;
1348 }
1349 #endif /* IP_SET_EMIT_CREATE */
1350
1351 #undef HKEY_DATALEN