include/linux/netfilter/ipset/ip_set_ahash.h

   1 #ifndef _IP_SET_AHASH_H
   2 #define _IP_SET_AHASH_H
   3
   4 #include <linux/rcupdate.h>
   5 #include <linux/jhash.h>
   6 #include <linux/netfilter/ipset/ip_set_timeout.h>
   7
   8 #define CONCAT(a, b, c)         a##b##c
   9 #define TOKEN(a, b, c)          CONCAT(a, b, c)
  10
  11 #define type_pf_next            TOKEN(TYPE, PF, _elem)
  12
  13 /* Hashing which uses arrays to resolve clashing. The hash table is resized
  14  * (doubled) when searching becomes too long.
  15  * Internally jhash is used with the assumption that the size of the
  16  * stored data is a multiple of sizeof(u32). If storage supports timeout,
  17  * the timeout field must be the last one in the data structure - that field
  18  * is ignored when computing the hash key.
  19  *
  20  * Readers and resizing
  21  *
  22  * Resizing can be triggered by userspace command only, and those
  23  * are serialized by the nfnl mutex. During resizing the set is
  24  * read-locked, so the only possible concurrent operations are
  25  * the kernel side readers. Those must be protected by proper RCU locking.
  26  */
  27
  28 /* Number of elements to store in an initial array block */
  29 #define AHASH_INIT_SIZE                 4
  30 /* Max number of elements to store in an array block */
  31 #define AHASH_MAX_SIZE                  (3*AHASH_INIT_SIZE)
  32
  33 /* Max number of elements can be tuned */
  34 #ifdef IP_SET_HASH_WITH_MULTI
  35 #define AHASH_MAX(h)                    ((h)->ahash_max)
  36
  37 static inline u8
  38 tune_ahash_max(u8 curr, u32 multi)
  39 {
  40         u32 n;
  41
  42         if (multi < curr)
  43                 return curr;
  44
  45         n = curr + AHASH_INIT_SIZE;
  46         /* Currently, at listing one hash bucket must fit into a message.
  47          * Therefore we have a hard limit here.
  48          */
  49         return n > curr && n <= 64 ? n : curr;
  50 }
  51 #define TUNE_AHASH_MAX(h, multi)        \
  52         ((h)->ahash_max = tune_ahash_max((h)->ahash_max, multi))
  53 #else
  54 #define AHASH_MAX(h)                    AHASH_MAX_SIZE
  55 #define TUNE_AHASH_MAX(h, multi)
  56 #endif
  57
  58 /* A hash bucket */
  59 struct hbucket {
  60         void *value;            /* the array of the values */
  61         u8 size;                /* size of the array */
  62         u8 pos;                 /* position of the first free entry */
  63 };
  64
  65 /* The hash table: the table size stored here in order to make resizing easy */
  66 struct htable {
  67         u8 htable_bits;         /* size of hash table == 2^htable_bits */
  68         struct hbucket bucket[0]; /* hashtable buckets */
  69 };
  70
  71 #define hbucket(h, i)           (&((h)->bucket[i]))
  72
  73 /* Book-keeping of the prefixes added to the set */
  74 struct ip_set_hash_nets {
  75         u8 cidr;                /* the different cidr values in the set */
  76         u32 nets;               /* number of elements per cidr */
  77 };
  78
  79 /* The generic ip_set hash structure */
  80 struct ip_set_hash {
  81         struct htable *table;   /* the hash table */
  82         u32 maxelem;            /* max elements in the hash */
  83         u32 elements;           /* current element (vs timeout) */
  84         u32 initval;            /* random jhash init value */
  85         u32 timeout;            /* timeout value, if enabled */
  86         struct timer_list gc;   /* garbage collection when timeout enabled */
  87         struct type_pf_next next; /* temporary storage for uadd */
  88 #ifdef IP_SET_HASH_WITH_MULTI
  89         u8 ahash_max;           /* max elements in an array block */
  90 #endif
  91 #ifdef IP_SET_HASH_WITH_NETMASK
  92         u8 netmask;             /* netmask value for subnets to store */
  93 #endif
  94 #ifdef IP_SET_HASH_WITH_RBTREE
  95         struct rb_root rbtree;
  96 #endif
  97 #ifdef IP_SET_HASH_WITH_NETS
  98         struct ip_set_hash_nets nets[0]; /* book-keeping of prefixes */
  99 #endif
 100 };
 101
 102 static size_t
 103 htable_size(u8 hbits)
 104 {
 105         size_t hsize;
 106
 107         /* We must fit both into u32 in jhash and size_t */
 108         if (hbits > 31)
 109                 return 0;
 110         hsize = jhash_size(hbits);
 111         if ((((size_t)-1) - sizeof(struct htable))/sizeof(struct hbucket)
 112             < hsize)
 113                 return 0;
 114
 115         return hsize * sizeof(struct hbucket) + sizeof(struct htable);
 116 }
 117
 118 /* Compute htable_bits from the user input parameter hashsize */
 119 static u8
 120 htable_bits(u32 hashsize)
 121 {
 122         /* Assume that hashsize == 2^htable_bits */
 123         u8 bits = fls(hashsize - 1);
 124         if (jhash_size(bits) != hashsize)
 125                 /* Round up to the first 2^n value */
 126                 bits = fls(hashsize);
 127
 128         return bits;
 129 }
 130
 131 #ifdef IP_SET_HASH_WITH_NETS
 132 #ifdef IP_SET_HASH_WITH_NETS_PACKED
 133 /* When cidr is packed with nomatch, cidr - 1 is stored in the entry */
 134 #define CIDR(cidr)      (cidr + 1)
 135 #else
 136 #define CIDR(cidr)      (cidr)
 137 #endif
 138
 139 #define SET_HOST_MASK(family)   (family == AF_INET ? 32 : 128)
 140
 141 /* Network cidr size book keeping when the hash stores different
 142  * sized networks */
 143 static void
 144 add_cidr(struct ip_set_hash *h, u8 cidr, u8 host_mask)
 145 {
 146         u8 i;
 147
 148         ++h->nets[cidr-1].nets;
 149
 150         pr_debug("add_cidr added %u: %u\n", cidr, h->nets[cidr-1].nets);
 151
 152         if (h->nets[cidr-1].nets > 1)
 153                 return;
 154
 155         /* New cidr size */
 156         for (i = 0; i < host_mask && h->nets[i].cidr; i++) {
 157                 /* Add in increasing prefix order, so larger cidr first */
 158                 if (h->nets[i].cidr < cidr)
 159                         swap(h->nets[i].cidr, cidr);
 160         }
 161         if (i < host_mask)
 162                 h->nets[i].cidr = cidr;
 163 }
 164
 165 static void
 166 del_cidr(struct ip_set_hash *h, u8 cidr, u8 host_mask)
 167 {
 168         u8 i;
 169
 170         --h->nets[cidr-1].nets;
 171
 172         pr_debug("del_cidr deleted %u: %u\n", cidr, h->nets[cidr-1].nets);
 173
 174         if (h->nets[cidr-1].nets != 0)
 175                 return;
 176
 177         /* All entries with this cidr size deleted, so cleanup h->cidr[] */
 178         for (i = 0; i < host_mask - 1 && h->nets[i].cidr; i++) {
 179                 if (h->nets[i].cidr == cidr)
 180                         h->nets[i].cidr = cidr = h->nets[i+1].cidr;
 181         }
 182         h->nets[i - 1].cidr = 0;
 183 }
 184 #endif
 185
 186 /* Destroy the hashtable part of the set */
 187 static void
 188 ahash_destroy(struct htable *t)
 189 {
 190         struct hbucket *n;
 191         u32 i;
 192
 193         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 194                 n = hbucket(t, i);
 195                 if (n->size)
 196                         /* FIXME: use slab cache */
 197                         kfree(n->value);
 198         }
 199
 200         ip_set_free(t);
 201 }
 202
 203 /* Calculate the actual memory size of the set data */
 204 static size_t
 205 ahash_memsize(const struct ip_set_hash *h, size_t dsize, u8 host_mask)
 206 {
 207         u32 i;
 208         struct htable *t = h->table;
 209         size_t memsize = sizeof(*h)
 210                          + sizeof(*t)
 211 #ifdef IP_SET_HASH_WITH_NETS
 212                          + sizeof(struct ip_set_hash_nets) * host_mask
 213 #endif
 214                          + jhash_size(t->htable_bits) * sizeof(struct hbucket);
 215
 216         for (i = 0; i < jhash_size(t->htable_bits); i++)
 217                         memsize += t->bucket[i].size * dsize;
 218
 219         return memsize;
 220 }
 221
 222 /* Flush a hash type of set: destroy all elements */
 223 static void
 224 ip_set_hash_flush(struct ip_set *set)
 225 {
 226         struct ip_set_hash *h = set->data;
 227         struct htable *t = h->table;
 228         struct hbucket *n;
 229         u32 i;
 230
 231         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 232                 n = hbucket(t, i);
 233                 if (n->size) {
 234                         n->size = n->pos = 0;
 235                         /* FIXME: use slab cache */
 236                         kfree(n->value);
 237                 }
 238         }
 239 #ifdef IP_SET_HASH_WITH_NETS
 240         memset(h->nets, 0, sizeof(struct ip_set_hash_nets)
 241                            * SET_HOST_MASK(set->family));
 242 #endif
 243         h->elements = 0;
 244 }
 245
 246 /* Destroy a hash type of set */
 247 static void
 248 ip_set_hash_destroy(struct ip_set *set)
 249 {
 250         struct ip_set_hash *h = set->data;
 251
 252         if (with_timeout(h->timeout))
 253                 del_timer_sync(&h->gc);
 254
 255         ahash_destroy(h->table);
 256 #ifdef IP_SET_HASH_WITH_RBTREE
 257         rbtree_destroy(&h->rbtree);
 258 #endif
 259         kfree(h);
 260
 261         set->data = NULL;
 262 }
 263
 264 #endif /* _IP_SET_AHASH_H */
 265
 266 #ifndef HKEY_DATALEN
 267 #define HKEY_DATALEN    sizeof(struct type_pf_elem)
 268 #endif
 269
 270 #define HKEY(data, initval, htable_bits)                        \
 271 (jhash2((u32 *)(data), HKEY_DATALEN/sizeof(u32), initval)       \
 272         & jhash_mask(htable_bits))
 273
 274 #define CONCAT(a, b, c)         a##b##c
 275 #define TOKEN(a, b, c)          CONCAT(a, b, c)
 276
 277 /* Type/family dependent function prototypes */
 278
 279 #define type_pf_data_equal      TOKEN(TYPE, PF, _data_equal)
 280 #define type_pf_data_isnull     TOKEN(TYPE, PF, _data_isnull)
 281 #define type_pf_data_copy       TOKEN(TYPE, PF, _data_copy)
 282 #define type_pf_data_zero_out   TOKEN(TYPE, PF, _data_zero_out)
 283 #define type_pf_data_netmask    TOKEN(TYPE, PF, _data_netmask)
 284 #define type_pf_data_list       TOKEN(TYPE, PF, _data_list)
 285 #define type_pf_data_tlist      TOKEN(TYPE, PF, _data_tlist)
 286 #define type_pf_data_next       TOKEN(TYPE, PF, _data_next)
 287 #define type_pf_data_flags      TOKEN(TYPE, PF, _data_flags)
 288 #ifdef IP_SET_HASH_WITH_NETS
 289 #define type_pf_data_match      TOKEN(TYPE, PF, _data_match)
 290 #else
 291 #define type_pf_data_match(d)   1
 292 #endif
 293
 294 #define type_pf_elem            TOKEN(TYPE, PF, _elem)
 295 #define type_pf_telem           TOKEN(TYPE, PF, _telem)
 296 #define type_pf_data_timeout    TOKEN(TYPE, PF, _data_timeout)
 297 #define type_pf_data_expired    TOKEN(TYPE, PF, _data_expired)
 298 #define type_pf_data_timeout_set TOKEN(TYPE, PF, _data_timeout_set)
 299
 300 #define type_pf_elem_add        TOKEN(TYPE, PF, _elem_add)
 301 #define type_pf_add             TOKEN(TYPE, PF, _add)
 302 #define type_pf_del             TOKEN(TYPE, PF, _del)
 303 #define type_pf_test_cidrs      TOKEN(TYPE, PF, _test_cidrs)
 304 #define type_pf_test            TOKEN(TYPE, PF, _test)
 305
 306 #define type_pf_elem_tadd       TOKEN(TYPE, PF, _elem_tadd)
 307 #define type_pf_del_telem       TOKEN(TYPE, PF, _ahash_del_telem)
 308 #define type_pf_expire          TOKEN(TYPE, PF, _expire)
 309 #define type_pf_tadd            TOKEN(TYPE, PF, _tadd)
 310 #define type_pf_tdel            TOKEN(TYPE, PF, _tdel)
 311 #define type_pf_ttest_cidrs     TOKEN(TYPE, PF, _ahash_ttest_cidrs)
 312 #define type_pf_ttest           TOKEN(TYPE, PF, _ahash_ttest)
 313
 314 #define type_pf_resize          TOKEN(TYPE, PF, _resize)
 315 #define type_pf_tresize         TOKEN(TYPE, PF, _tresize)
 316 #define type_pf_flush           ip_set_hash_flush
 317 #define type_pf_destroy         ip_set_hash_destroy
 318 #define type_pf_head            TOKEN(TYPE, PF, _head)
 319 #define type_pf_list            TOKEN(TYPE, PF, _list)
 320 #define type_pf_tlist           TOKEN(TYPE, PF, _tlist)
 321 #define type_pf_same_set        TOKEN(TYPE, PF, _same_set)
 322 #define type_pf_kadt            TOKEN(TYPE, PF, _kadt)
 323 #define type_pf_uadt            TOKEN(TYPE, PF, _uadt)
 324 #define type_pf_gc              TOKEN(TYPE, PF, _gc)
 325 #define type_pf_gc_init         TOKEN(TYPE, PF, _gc_init)
 326 #define type_pf_variant         TOKEN(TYPE, PF, _variant)
 327 #define type_pf_tvariant        TOKEN(TYPE, PF, _tvariant)
 328
 329 /* Flavour without timeout */
 330
 331 /* Get the ith element from the array block n */
 332 #define ahash_data(n, i)        \
 333         ((struct type_pf_elem *)((n)->value) + (i))
 334
 335 /* Add an element to the hash table when resizing the set:
 336  * we spare the maintenance of the internal counters. */
 337 static int
 338 type_pf_elem_add(struct hbucket *n, const struct type_pf_elem *value,
 339                  u8 ahash_max, u32 cadt_flags)
 340 {
 341         struct type_pf_elem *data;
 342
 343         if (n->pos >= n->size) {
 344                 void *tmp;
 345
 346                 if (n->size >= ahash_max)
 347                         /* Trigger rehashing */
 348                         return -EAGAIN;
 349
 350                 tmp = kzalloc((n->size + AHASH_INIT_SIZE)
 351                               * sizeof(struct type_pf_elem),
 352                               GFP_ATOMIC);
 353                 if (!tmp)
 354                         return -ENOMEM;
 355                 if (n->size) {
 356                         memcpy(tmp, n->value,
 357                                sizeof(struct type_pf_elem) * n->size);
 358                         kfree(n->value);
 359                 }
 360                 n->value = tmp;
 361                 n->size += AHASH_INIT_SIZE;
 362         }
 363         data = ahash_data(n, n->pos++);
 364         type_pf_data_copy(data, value);
 365 #ifdef IP_SET_HASH_WITH_NETS
 366         /* Resizing won't overwrite stored flags */
 367         if (cadt_flags)
 368                 type_pf_data_flags(data, cadt_flags);
 369 #endif
 370         return 0;
 371 }
 372
 373 /* Resize a hash: create a new hash table with doubling the hashsize
 374  * and inserting the elements to it. Repeat until we succeed or
 375  * fail due to memory pressures. */
 376 static int
 377 type_pf_resize(struct ip_set *set, bool retried)
 378 {
 379         struct ip_set_hash *h = set->data;
 380         struct htable *t, *orig = h->table;
 381         u8 htable_bits = orig->htable_bits;
 382         const struct type_pf_elem *data;
 383         struct hbucket *n, *m;
 384         u32 i, j;
 385         int ret;
 386
 387 retry:
 388         ret = 0;
 389         htable_bits++;
 390         pr_debug("attempt to resize set %s from %u to %u, t %p\n",
 391                  set->name, orig->htable_bits, htable_bits, orig);
 392         if (!htable_bits) {
 393                 /* In case we have plenty of memory :-) */
 394                 pr_warning("Cannot increase the hashsize of set %s further\n",
 395                            set->name);
 396                 return -IPSET_ERR_HASH_FULL;
 397         }
 398         t = ip_set_alloc(sizeof(*t)
 399                          + jhash_size(htable_bits) * sizeof(struct hbucket));
 400         if (!t)
 401                 return -ENOMEM;
 402         t->htable_bits = htable_bits;
 403
 404         read_lock_bh(&set->lock);
 405         for (i = 0; i < jhash_size(orig->htable_bits); i++) {
 406                 n = hbucket(orig, i);
 407                 for (j = 0; j < n->pos; j++) {
 408                         data = ahash_data(n, j);
 409                         m = hbucket(t, HKEY(data, h->initval, htable_bits));
 410                         ret = type_pf_elem_add(m, data, AHASH_MAX(h), 0);
 411                         if (ret < 0) {
 412                                 read_unlock_bh(&set->lock);
 413                                 ahash_destroy(t);
 414                                 if (ret == -EAGAIN)
 415                                         goto retry;
 416                                 return ret;
 417                         }
 418                 }
 419         }
 420
 421         rcu_assign_pointer(h->table, t);
 422         read_unlock_bh(&set->lock);
 423
 424         /* Give time to other readers of the set */
 425         synchronize_rcu_bh();
 426
 427         pr_debug("set %s resized from %u (%p) to %u (%p)\n", set->name,
 428                  orig->htable_bits, orig, t->htable_bits, t);
 429         ahash_destroy(orig);
 430
 431         return 0;
 432 }
 433
 434 static inline void
 435 type_pf_data_next(struct ip_set_hash *h, const struct type_pf_elem *d);
 436
 437 /* Add an element to a hash and update the internal counters when succeeded,
 438  * otherwise report the proper error code. */
 439 static int
 440 type_pf_add(struct ip_set *set, void *value, u32 timeout, u32 flags)
 441 {
 442         struct ip_set_hash *h = set->data;
 443         struct htable *t;
 444         const struct type_pf_elem *d = value;
 445         struct hbucket *n;
 446         int i, ret = 0;
 447         u32 key, multi = 0;
 448         u32 cadt_flags = flags >> 16;
 449
 450         if (h->elements >= h->maxelem) {
 451                 if (net_ratelimit())
 452                         pr_warning("Set %s is full, maxelem %u reached\n",
 453                                    set->name, h->maxelem);
 454                 return -IPSET_ERR_HASH_FULL;
 455         }
 456
 457         rcu_read_lock_bh();
 458         t = rcu_dereference_bh(h->table);
 459         key = HKEY(value, h->initval, t->htable_bits);
 460         n = hbucket(t, key);
 461         for (i = 0; i < n->pos; i++)
 462                 if (type_pf_data_equal(ahash_data(n, i), d, &multi)) {
 463 #ifdef IP_SET_HASH_WITH_NETS
 464                         if (flags & IPSET_FLAG_EXIST)
 465                                 /* Support overwriting just the flags */
 466                                 type_pf_data_flags(ahash_data(n, i),
 467                                                    cadt_flags);
 468 #endif
 469                         ret = -IPSET_ERR_EXIST;
 470                         goto out;
 471                 }
 472         TUNE_AHASH_MAX(h, multi);
 473         ret = type_pf_elem_add(n, value, AHASH_MAX(h), cadt_flags);
 474         if (ret != 0) {
 475                 if (ret == -EAGAIN)
 476                         type_pf_data_next(h, d);
 477                 goto out;
 478         }
 479
 480 #ifdef IP_SET_HASH_WITH_NETS
 481         add_cidr(h, CIDR(d->cidr), HOST_MASK);
 482 #endif
 483         h->elements++;
 484 out:
 485         rcu_read_unlock_bh();
 486         return ret;
 487 }
 488
 489 /* Delete an element from the hash: swap it with the last element
 490  * and free up space if possible.
 491  */
 492 static int
 493 type_pf_del(struct ip_set *set, void *value, u32 timeout, u32 flags)
 494 {
 495         struct ip_set_hash *h = set->data;
 496         struct htable *t = h->table;
 497         const struct type_pf_elem *d = value;
 498         struct hbucket *n;
 499         int i;
 500         struct type_pf_elem *data;
 501         u32 key, multi = 0;
 502
 503         key = HKEY(value, h->initval, t->htable_bits);
 504         n = hbucket(t, key);
 505         for (i = 0; i < n->pos; i++) {
 506                 data = ahash_data(n, i);
 507                 if (!type_pf_data_equal(data, d, &multi))
 508                         continue;
 509                 if (i != n->pos - 1)
 510                         /* Not last one */
 511                         type_pf_data_copy(data, ahash_data(n, n->pos - 1));
 512
 513                 n->pos--;
 514                 h->elements--;
 515 #ifdef IP_SET_HASH_WITH_NETS
 516                 del_cidr(h, CIDR(d->cidr), HOST_MASK);
 517 #endif
 518                 if (n->pos + AHASH_INIT_SIZE < n->size) {
 519                         void *tmp = kzalloc((n->size - AHASH_INIT_SIZE)
 520                                             * sizeof(struct type_pf_elem),
 521                                             GFP_ATOMIC);
 522                         if (!tmp)
 523                                 return 0;
 524                         n->size -= AHASH_INIT_SIZE;
 525                         memcpy(tmp, n->value,
 526                                n->size * sizeof(struct type_pf_elem));
 527                         kfree(n->value);
 528                         n->value = tmp;
 529                 }
 530                 return 0;
 531         }
 532
 533         return -IPSET_ERR_EXIST;
 534 }
 535
 536 #ifdef IP_SET_HASH_WITH_NETS
 537
 538 /* Special test function which takes into account the different network
 539  * sizes added to the set */
 540 static int
 541 type_pf_test_cidrs(struct ip_set *set, struct type_pf_elem *d, u32 timeout)
 542 {
 543         struct ip_set_hash *h = set->data;
 544         struct htable *t = h->table;
 545         struct hbucket *n;
 546         const struct type_pf_elem *data;
 547         int i, j = 0;
 548         u32 key, multi = 0;
 549         u8 host_mask = SET_HOST_MASK(set->family);
 550
 551         pr_debug("test by nets\n");
 552         for (; j < host_mask && h->nets[j].cidr && !multi; j++) {
 553                 type_pf_data_netmask(d, h->nets[j].cidr);
 554                 key = HKEY(d, h->initval, t->htable_bits);
 555                 n = hbucket(t, key);
 556                 for (i = 0; i < n->pos; i++) {
 557                         data = ahash_data(n, i);
 558                         if (type_pf_data_equal(data, d, &multi))
 559                                 return type_pf_data_match(data);
 560                 }
 561         }
 562         return 0;
 563 }
 564 #endif
 565
 566 /* Test whether the element is added to the set */
 567 static int
 568 type_pf_test(struct ip_set *set, void *value, u32 timeout, u32 flags)
 569 {
 570         struct ip_set_hash *h = set->data;
 571         struct htable *t = h->table;
 572         struct type_pf_elem *d = value;
 573         struct hbucket *n;
 574         const struct type_pf_elem *data;
 575         int i;
 576         u32 key, multi = 0;
 577
 578 #ifdef IP_SET_HASH_WITH_NETS
 579         /* If we test an IP address and not a network address,
 580          * try all possible network sizes */
 581         if (CIDR(d->cidr) == SET_HOST_MASK(set->family))
 582                 return type_pf_test_cidrs(set, d, timeout);
 583 #endif
 584
 585         key = HKEY(d, h->initval, t->htable_bits);
 586         n = hbucket(t, key);
 587         for (i = 0; i < n->pos; i++) {
 588                 data = ahash_data(n, i);
 589                 if (type_pf_data_equal(data, d, &multi))
 590                         return type_pf_data_match(data);
 591         }
 592         return 0;
 593 }
 594
 595 /* Reply a HEADER request: fill out the header part of the set */
 596 static int
 597 type_pf_head(struct ip_set *set, struct sk_buff *skb)
 598 {
 599         const struct ip_set_hash *h = set->data;
 600         struct nlattr *nested;
 601         size_t memsize;
 602
 603         read_lock_bh(&set->lock);
 604         memsize = ahash_memsize(h, with_timeout(h->timeout)
 605                                         ? sizeof(struct type_pf_telem)
 606                                         : sizeof(struct type_pf_elem),
 607                                 set->family == AF_INET ? 32 : 128);
 608         read_unlock_bh(&set->lock);
 609
 610         nested = ipset_nest_start(skb, IPSET_ATTR_DATA);
 611         if (!nested)
 612                 goto nla_put_failure;
 613         NLA_PUT_NET32(skb, IPSET_ATTR_HASHSIZE,
 614                       htonl(jhash_size(h->table->htable_bits)));
 615         NLA_PUT_NET32(skb, IPSET_ATTR_MAXELEM, htonl(h->maxelem));
 616 #ifdef IP_SET_HASH_WITH_NETMASK
 617         if (h->netmask != HOST_MASK)
 618                 NLA_PUT_U8(skb, IPSET_ATTR_NETMASK, h->netmask);
 619 #endif
 620         NLA_PUT_NET32(skb, IPSET_ATTR_REFERENCES, htonl(set->ref - 1));
 621         NLA_PUT_NET32(skb, IPSET_ATTR_MEMSIZE, htonl(memsize));
 622         if (with_timeout(h->timeout))
 623                 NLA_PUT_NET32(skb, IPSET_ATTR_TIMEOUT, htonl(h->timeout));
 624         ipset_nest_end(skb, nested);
 625
 626         return 0;
 627 nla_put_failure:
 628         return -EMSGSIZE;
 629 }
 630
 631 /* Reply a LIST/SAVE request: dump the elements of the specified set */
 632 static int
 633 type_pf_list(const struct ip_set *set,
 634              struct sk_buff *skb, struct netlink_callback *cb)
 635 {
 636         const struct ip_set_hash *h = set->data;
 637         const struct htable *t = h->table;
 638         struct nlattr *atd, *nested;
 639         const struct hbucket *n;
 640         const struct type_pf_elem *data;
 641         u32 first = cb->args[2];
 642         /* We assume that one hash bucket fills into one page */
 643         void *incomplete;
 644         int i;
 645
 646         atd = ipset_nest_start(skb, IPSET_ATTR_ADT);
 647         if (!atd)
 648                 return -EMSGSIZE;
 649         pr_debug("list hash set %s\n", set->name);
 650         for (; cb->args[2] < jhash_size(t->htable_bits); cb->args[2]++) {
 651                 incomplete = skb_tail_pointer(skb);
 652                 n = hbucket(t, cb->args[2]);
 653                 pr_debug("cb->args[2]: %lu, t %p n %p\n", cb->args[2], t, n);
 654                 for (i = 0; i < n->pos; i++) {
 655                         data = ahash_data(n, i);
 656                         pr_debug("list hash %lu hbucket %p i %u, data %p\n",
 657                                  cb->args[2], n, i, data);
 658                         nested = ipset_nest_start(skb, IPSET_ATTR_DATA);
 659                         if (!nested) {
 660                                 if (cb->args[2] == first) {
 661                                         nla_nest_cancel(skb, atd);
 662                                         return -EMSGSIZE;
 663                                 } else
 664                                         goto nla_put_failure;
 665                         }
 666                         if (type_pf_data_list(skb, data))
 667                                 goto nla_put_failure;
 668                         ipset_nest_end(skb, nested);
 669                 }
 670         }
 671         ipset_nest_end(skb, atd);
 672         /* Set listing finished */
 673         cb->args[2] = 0;
 674
 675         return 0;
 676
 677 nla_put_failure:
 678         nlmsg_trim(skb, incomplete);
 679         ipset_nest_end(skb, atd);
 680         if (unlikely(first == cb->args[2])) {
 681                 pr_warning("Can't list set %s: one bucket does not fit into "
 682                            "a message. Please report it!\n", set->name);
 683                 cb->args[2] = 0;
 684                 return -EMSGSIZE;
 685         }
 686         return 0;
 687 }
 688
 689 static int
 690 type_pf_kadt(struct ip_set *set, const struct sk_buff * skb,
 691              const struct xt_action_param *par,
 692              enum ipset_adt adt, const struct ip_set_adt_opt *opt);
 693 static int
 694 type_pf_uadt(struct ip_set *set, struct nlattr *tb[],
 695              enum ipset_adt adt, u32 *lineno, u32 flags, bool retried);
 696
 697 static const struct ip_set_type_variant type_pf_variant = {
 698         .kadt   = type_pf_kadt,
 699         .uadt   = type_pf_uadt,
 700         .adt    = {
 701                 [IPSET_ADD] = type_pf_add,
 702                 [IPSET_DEL] = type_pf_del,
 703                 [IPSET_TEST] = type_pf_test,
 704         },
 705         .destroy = type_pf_destroy,
 706         .flush  = type_pf_flush,
 707         .head   = type_pf_head,
 708         .list   = type_pf_list,
 709         .resize = type_pf_resize,
 710         .same_set = type_pf_same_set,
 711 };
 712
 713 /* Flavour with timeout support */
 714
 715 #define ahash_tdata(n, i) \
 716         (struct type_pf_elem *)((struct type_pf_telem *)((n)->value) + (i))
 717
 718 static inline u32
 719 type_pf_data_timeout(const struct type_pf_elem *data)
 720 {
 721         const struct type_pf_telem *tdata =
 722                 (const struct type_pf_telem *) data;
 723
 724         return tdata->timeout;
 725 }
 726
 727 static inline bool
 728 type_pf_data_expired(const struct type_pf_elem *data)
 729 {
 730         const struct type_pf_telem *tdata =
 731                 (const struct type_pf_telem *) data;
 732
 733         return ip_set_timeout_expired(tdata->timeout);
 734 }
 735
 736 static inline void
 737 type_pf_data_timeout_set(struct type_pf_elem *data, u32 timeout)
 738 {
 739         struct type_pf_telem *tdata = (struct type_pf_telem *) data;
 740
 741         tdata->timeout = ip_set_timeout_set(timeout);
 742 }
 743
 744 static int
 745 type_pf_elem_tadd(struct hbucket *n, const struct type_pf_elem *value,
 746                   u8 ahash_max, u32 cadt_flags, u32 timeout)
 747 {
 748         struct type_pf_elem *data;
 749
 750         if (n->pos >= n->size) {
 751                 void *tmp;
 752
 753                 if (n->size >= ahash_max)
 754                         /* Trigger rehashing */
 755                         return -EAGAIN;
 756
 757                 tmp = kzalloc((n->size + AHASH_INIT_SIZE)
 758                               * sizeof(struct type_pf_telem),
 759                               GFP_ATOMIC);
 760                 if (!tmp)
 761                         return -ENOMEM;
 762                 if (n->size) {
 763                         memcpy(tmp, n->value,
 764                                sizeof(struct type_pf_telem) * n->size);
 765                         kfree(n->value);
 766                 }
 767                 n->value = tmp;
 768                 n->size += AHASH_INIT_SIZE;
 769         }
 770         data = ahash_tdata(n, n->pos++);
 771         type_pf_data_copy(data, value);
 772         type_pf_data_timeout_set(data, timeout);
 773 #ifdef IP_SET_HASH_WITH_NETS
 774         /* Resizing won't overwrite stored flags */
 775         if (cadt_flags)
 776                 type_pf_data_flags(data, cadt_flags);
 777 #endif
 778         return 0;
 779 }
 780
 781 /* Delete expired elements from the hashtable */
 782 static void
 783 type_pf_expire(struct ip_set_hash *h)
 784 {
 785         struct htable *t = h->table;
 786         struct hbucket *n;
 787         struct type_pf_elem *data;
 788         u32 i;
 789         int j;
 790
 791         for (i = 0; i < jhash_size(t->htable_bits); i++) {
 792                 n = hbucket(t, i);
 793                 for (j = 0; j < n->pos; j++) {
 794                         data = ahash_tdata(n, j);
 795                         if (type_pf_data_expired(data)) {
 796                                 pr_debug("expired %u/%u\n", i, j);
 797 #ifdef IP_SET_HASH_WITH_NETS
 798                                 del_cidr(h, CIDR(data->cidr), HOST_MASK);
 799 #endif
 800                                 if (j != n->pos - 1)
 801                                         /* Not last one */
 802                                         type_pf_data_copy(data,
 803                                                 ahash_tdata(n, n->pos - 1));
 804                                 n->pos--;
 805                                 h->elements--;
 806                         }
 807                 }
 808                 if (n->pos + AHASH_INIT_SIZE < n->size) {
 809                         void *tmp = kzalloc((n->size - AHASH_INIT_SIZE)
 810                                             * sizeof(struct type_pf_telem),
 811                                             GFP_ATOMIC);
 812                         if (!tmp)
 813                                 /* Still try to delete expired elements */
 814                                 continue;
 815                         n->size -= AHASH_INIT_SIZE;
 816                         memcpy(tmp, n->value,
 817                                n->size * sizeof(struct type_pf_telem));
 818                         kfree(n->value);
 819                         n->value = tmp;
 820                 }
 821         }
 822 }
 823
 824 static int
 825 type_pf_tresize(struct ip_set *set, bool retried)
 826 {
 827         struct ip_set_hash *h = set->data;
 828         struct htable *t, *orig = h->table;
 829         u8 htable_bits = orig->htable_bits;
 830         const struct type_pf_elem *data;
 831         struct hbucket *n, *m;
 832         u32 i, j;
 833         int ret;
 834
 835         /* Try to cleanup once */
 836         if (!retried) {
 837                 i = h->elements;
 838                 write_lock_bh(&set->lock);
 839                 type_pf_expire(set->data);
 840                 write_unlock_bh(&set->lock);
 841                 if (h->elements <  i)
 842                         return 0;
 843         }
 844
 845 retry:
 846         ret = 0;
 847         htable_bits++;
 848         if (!htable_bits) {
 849                 /* In case we have plenty of memory :-) */
 850                 pr_warning("Cannot increase the hashsize of set %s further\n",
 851                            set->name);
 852                 return -IPSET_ERR_HASH_FULL;
 853         }
 854         t = ip_set_alloc(sizeof(*t)
 855                          + jhash_size(htable_bits) * sizeof(struct hbucket));
 856         if (!t)
 857                 return -ENOMEM;
 858         t->htable_bits = htable_bits;
 859
 860         read_lock_bh(&set->lock);
 861         for (i = 0; i < jhash_size(orig->htable_bits); i++) {
 862                 n = hbucket(orig, i);
 863                 for (j = 0; j < n->pos; j++) {
 864                         data = ahash_tdata(n, j);
 865                         m = hbucket(t, HKEY(data, h->initval, htable_bits));
 866                         ret = type_pf_elem_tadd(m, data, AHASH_MAX(h), 0,
 867                                                 type_pf_data_timeout(data));
 868                         if (ret < 0) {
 869                                 read_unlock_bh(&set->lock);
 870                                 ahash_destroy(t);
 871                                 if (ret == -EAGAIN)
 872                                         goto retry;
 873                                 return ret;
 874                         }
 875                 }
 876         }
 877
 878         rcu_assign_pointer(h->table, t);
 879         read_unlock_bh(&set->lock);
 880
 881         /* Give time to other readers of the set */
 882         synchronize_rcu_bh();
 883
 884         ahash_destroy(orig);
 885
 886         return 0;
 887 }
 888
 889 static int
 890 type_pf_tadd(struct ip_set *set, void *value, u32 timeout, u32 flags)
 891 {
 892         struct ip_set_hash *h = set->data;
 893         struct htable *t = h->table;
 894         const struct type_pf_elem *d = value;
 895         struct hbucket *n;
 896         struct type_pf_elem *data;
 897         int ret = 0, i, j = AHASH_MAX(h) + 1;
 898         bool flag_exist = flags & IPSET_FLAG_EXIST;
 899         u32 key, multi = 0;
 900         u32 cadt_flags = flags >> 16;
 901
 902         if (h->elements >= h->maxelem)
 903                 /* FIXME: when set is full, we slow down here */
 904                 type_pf_expire(h);
 905         if (h->elements >= h->maxelem) {
 906                 if (net_ratelimit())
 907                         pr_warning("Set %s is full, maxelem %u reached\n",
 908                                    set->name, h->maxelem);
 909                 return -IPSET_ERR_HASH_FULL;
 910         }
 911
 912         rcu_read_lock_bh();
 913         t = rcu_dereference_bh(h->table);
 914         key = HKEY(d, h->initval, t->htable_bits);
 915         n = hbucket(t, key);
 916         for (i = 0; i < n->pos; i++) {
 917                 data = ahash_tdata(n, i);
 918                 if (type_pf_data_equal(data, d, &multi)) {
 919                         if (type_pf_data_expired(data) || flag_exist)
 920                                 /* Just timeout value may be updated */
 921                                 j = i;
 922                         else {
 923                                 ret = -IPSET_ERR_EXIST;
 924                                 goto out;
 925                         }
 926                 } else if (j == AHASH_MAX(h) + 1 &&
 927                            type_pf_data_expired(data))
 928                         j = i;
 929         }
 930         if (j != AHASH_MAX(h) + 1) {
 931                 data = ahash_tdata(n, j);
 932 #ifdef IP_SET_HASH_WITH_NETS
 933                 del_cidr(h, CIDR(data->cidr), HOST_MASK);
 934                 add_cidr(h, CIDR(d->cidr), HOST_MASK);
 935 #endif
 936                 type_pf_data_copy(data, d);
 937                 type_pf_data_timeout_set(data, timeout);
 938 #ifdef IP_SET_HASH_WITH_NETS
 939                 type_pf_data_flags(data, cadt_flags);
 940 #endif
 941                 goto out;
 942         }
 943         TUNE_AHASH_MAX(h, multi);
 944         ret = type_pf_elem_tadd(n, d, AHASH_MAX(h), cadt_flags, timeout);
 945         if (ret != 0) {
 946                 if (ret == -EAGAIN)
 947                         type_pf_data_next(h, d);
 948                 goto out;
 949         }
 950
 951 #ifdef IP_SET_HASH_WITH_NETS
 952         add_cidr(h, CIDR(d->cidr), HOST_MASK);
 953 #endif
 954         h->elements++;
 955 out:
 956         rcu_read_unlock_bh();
 957         return ret;
 958 }
 959
 960 static int
 961 type_pf_tdel(struct ip_set *set, void *value, u32 timeout, u32 flags)
 962 {
 963         struct ip_set_hash *h = set->data;
 964         struct htable *t = h->table;
 965         const struct type_pf_elem *d = value;
 966         struct hbucket *n;
 967         int i;
 968         struct type_pf_elem *data;
 969         u32 key, multi = 0;
 970
 971         key = HKEY(value, h->initval, t->htable_bits);
 972         n = hbucket(t, key);
 973         for (i = 0; i < n->pos; i++) {
 974                 data = ahash_tdata(n, i);
 975                 if (!type_pf_data_equal(data, d, &multi))
 976                         continue;
 977                 if (type_pf_data_expired(data))
 978                         return -IPSET_ERR_EXIST;
 979                 if (i != n->pos - 1)
 980                         /* Not last one */
 981                         type_pf_data_copy(data, ahash_tdata(n, n->pos - 1));
 982
 983                 n->pos--;
 984                 h->elements--;
 985 #ifdef IP_SET_HASH_WITH_NETS
 986                 del_cidr(h, CIDR(d->cidr), HOST_MASK);
 987 #endif
 988                 if (n->pos + AHASH_INIT_SIZE < n->size) {
 989                         void *tmp = kzalloc((n->size - AHASH_INIT_SIZE)
 990                                             * sizeof(struct type_pf_telem),
 991                                             GFP_ATOMIC);
 992                         if (!tmp)
 993                                 return 0;
 994                         n->size -= AHASH_INIT_SIZE;
 995                         memcpy(tmp, n->value,
 996                                n->size * sizeof(struct type_pf_telem));
 997                         kfree(n->value);
 998                         n->value = tmp;
 999                 }
1000                 return 0;
1001         }
1002
1003         return -IPSET_ERR_EXIST;
1004 }
1005
1006 #ifdef IP_SET_HASH_WITH_NETS
1007 static int
1008 type_pf_ttest_cidrs(struct ip_set *set, struct type_pf_elem *d, u32 timeout)
1009 {
1010         struct ip_set_hash *h = set->data;
1011         struct htable *t = h->table;
1012         struct type_pf_elem *data;
1013         struct hbucket *n;
1014         int i, j = 0;
1015         u32 key, multi = 0;
1016         u8 host_mask = SET_HOST_MASK(set->family);
1017
1018         for (; j < host_mask && h->nets[j].cidr && !multi; j++) {
1019                 type_pf_data_netmask(d, h->nets[j].cidr);
1020                 key = HKEY(d, h->initval, t->htable_bits);
1021                 n = hbucket(t, key);
1022                 for (i = 0; i < n->pos; i++) {
1023                         data = ahash_tdata(n, i);
1024 #ifdef IP_SET_HASH_WITH_MULTI
1025                         if (type_pf_data_equal(data, d, &multi)) {
1026                                 if (!type_pf_data_expired(data))
1027                                         return type_pf_data_match(data);
1028                                 multi = 0;
1029                         }
1030 #else
1031                         if (type_pf_data_equal(data, d, &multi) &&
1032                             !type_pf_data_expired(data))
1033                                 return type_pf_data_match(data);
1034 #endif
1035                 }
1036         }
1037         return 0;
1038 }
1039 #endif
1040
1041 static int
1042 type_pf_ttest(struct ip_set *set, void *value, u32 timeout, u32 flags)
1043 {
1044         struct ip_set_hash *h = set->data;
1045         struct htable *t = h->table;
1046         struct type_pf_elem *data, *d = value;
1047         struct hbucket *n;
1048         int i;
1049         u32 key, multi = 0;
1050
1051 #ifdef IP_SET_HASH_WITH_NETS
1052         if (CIDR(d->cidr) == SET_HOST_MASK(set->family))
1053                 return type_pf_ttest_cidrs(set, d, timeout);
1054 #endif
1055         key = HKEY(d, h->initval, t->htable_bits);
1056         n = hbucket(t, key);
1057         for (i = 0; i < n->pos; i++) {
1058                 data = ahash_tdata(n, i);
1059                 if (type_pf_data_equal(data, d, &multi) &&
1060                     !type_pf_data_expired(data))
1061                         return type_pf_data_match(data);
1062         }
1063         return 0;
1064 }
1065
1066 static int
1067 type_pf_tlist(const struct ip_set *set,
1068               struct sk_buff *skb, struct netlink_callback *cb)
1069 {
1070         const struct ip_set_hash *h = set->data;
1071         const struct htable *t = h->table;
1072         struct nlattr *atd, *nested;
1073         const struct hbucket *n;
1074         const struct type_pf_elem *data;
1075         u32 first = cb->args[2];
1076         /* We assume that one hash bucket fills into one page */
1077         void *incomplete;
1078         int i;
1079
1080         atd = ipset_nest_start(skb, IPSET_ATTR_ADT);
1081         if (!atd)
1082                 return -EMSGSIZE;
1083         for (; cb->args[2] < jhash_size(t->htable_bits); cb->args[2]++) {
1084                 incomplete = skb_tail_pointer(skb);
1085                 n = hbucket(t, cb->args[2]);
1086                 for (i = 0; i < n->pos; i++) {
1087                         data = ahash_tdata(n, i);
1088                         pr_debug("list %p %u\n", n, i);
1089                         if (type_pf_data_expired(data))
1090                                 continue;
1091                         pr_debug("do list %p %u\n", n, i);
1092                         nested = ipset_nest_start(skb, IPSET_ATTR_DATA);
1093                         if (!nested) {
1094                                 if (cb->args[2] == first) {
1095                                         nla_nest_cancel(skb, atd);
1096                                         return -EMSGSIZE;
1097                                 } else
1098                                         goto nla_put_failure;
1099                         }
1100                         if (type_pf_data_tlist(skb, data))
1101                                 goto nla_put_failure;
1102                         ipset_nest_end(skb, nested);
1103                 }
1104         }
1105         ipset_nest_end(skb, atd);
1106         /* Set listing finished */
1107         cb->args[2] = 0;
1108
1109         return 0;
1110
1111 nla_put_failure:
1112         nlmsg_trim(skb, incomplete);
1113         ipset_nest_end(skb, atd);
1114         if (unlikely(first == cb->args[2])) {
1115                 pr_warning("Can't list set %s: one bucket does not fit into "
1116                            "a message. Please report it!\n", set->name);
1117                 cb->args[2] = 0;
1118                 return -EMSGSIZE;
1119         }
1120         return 0;
1121 }
1122
1123 static const struct ip_set_type_variant type_pf_tvariant = {
1124         .kadt   = type_pf_kadt,
1125         .uadt   = type_pf_uadt,
1126         .adt    = {
1127                 [IPSET_ADD] = type_pf_tadd,
1128                 [IPSET_DEL] = type_pf_tdel,
1129                 [IPSET_TEST] = type_pf_ttest,
1130         },
1131         .destroy = type_pf_destroy,
1132         .flush  = type_pf_flush,
1133         .head   = type_pf_head,
1134         .list   = type_pf_tlist,
1135         .resize = type_pf_tresize,
1136         .same_set = type_pf_same_set,
1137 };
1138
1139 static void
1140 type_pf_gc(unsigned long ul_set)
1141 {
1142         struct ip_set *set = (struct ip_set *) ul_set;
1143         struct ip_set_hash *h = set->data;
1144
1145         pr_debug("called\n");
1146         write_lock_bh(&set->lock);
1147         type_pf_expire(h);
1148         write_unlock_bh(&set->lock);
1149
1150         h->gc.expires = jiffies + IPSET_GC_PERIOD(h->timeout) * HZ;
1151         add_timer(&h->gc);
1152 }
1153
1154 static void
1155 type_pf_gc_init(struct ip_set *set)
1156 {
1157         struct ip_set_hash *h = set->data;
1158
1159         init_timer(&h->gc);
1160         h->gc.data = (unsigned long) set;
1161         h->gc.function = type_pf_gc;
1162         h->gc.expires = jiffies + IPSET_GC_PERIOD(h->timeout) * HZ;
1163         add_timer(&h->gc);
1164         pr_debug("gc initialized, run in every %u\n",
1165                  IPSET_GC_PERIOD(h->timeout));
1166 }
1167
1168 #undef HKEY_DATALEN
1169 #undef HKEY
1170 #undef type_pf_data_equal
1171 #undef type_pf_data_isnull
1172 #undef type_pf_data_copy
1173 #undef type_pf_data_zero_out
1174 #undef type_pf_data_netmask
1175 #undef type_pf_data_list
1176 #undef type_pf_data_tlist
1177 #undef type_pf_data_next
1178 #undef type_pf_data_flags
1179 #undef type_pf_data_match
1180
1181 #undef type_pf_elem
1182 #undef type_pf_telem
1183 #undef type_pf_data_timeout
1184 #undef type_pf_data_expired
1185 #undef type_pf_data_timeout_set
1186
1187 #undef type_pf_elem_add
1188 #undef type_pf_add
1189 #undef type_pf_del
1190 #undef type_pf_test_cidrs
1191 #undef type_pf_test
1192
1193 #undef type_pf_elem_tadd
1194 #undef type_pf_del_telem
1195 #undef type_pf_expire
1196 #undef type_pf_tadd
1197 #undef type_pf_tdel
1198 #undef type_pf_ttest_cidrs
1199 #undef type_pf_ttest
1200
1201 #undef type_pf_resize
1202 #undef type_pf_tresize
1203 #undef type_pf_flush
1204 #undef type_pf_destroy
1205 #undef type_pf_head
1206 #undef type_pf_list
1207 #undef type_pf_tlist
1208 #undef type_pf_same_set
1209 #undef type_pf_kadt
1210 #undef type_pf_uadt
1211 #undef type_pf_gc
1212 #undef type_pf_gc_init
1213 #undef type_pf_variant
1214 #undef type_pf_tvariant