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