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