1 /* SPDX-License-Identifier: GPL-2.0-only */ 2 /* Copyright (C) 2013 Jozsef Kadlecsik <kadlec@netfilter.org> */ 3 4 #ifndef _IP_SET_HASH_GEN_H 5 #define _IP_SET_HASH_GEN_H 6 7 #include <linux/rcupdate.h> 8 #include <linux/rcupdate_wait.h> 9 #include <linux/jhash.h> 10 #include <linux/types.h> 11 #include <linux/netfilter/nfnetlink.h> 12 #include <linux/netfilter/ipset/ip_set.h> 13 14 #define __ipset_dereference(p) \ 15 rcu_dereference_protected(p, 1) 16 #define ipset_dereference_nfnl(p) \ 17 rcu_dereference_protected(p, \ 18 lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET)) 19 #define ipset_dereference_set(p, set) \ 20 rcu_dereference_protected(p, \ 21 lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET) || \ 22 lockdep_is_held(&(set)->lock)) 23 #define ipset_dereference_bh_nfnl(p) \ 24 rcu_dereference_bh_check(p, \ 25 lockdep_nfnl_is_held(NFNL_SUBSYS_IPSET)) 26 27 /* Hashing which uses arrays to resolve clashing. The hash table is resized 28 * (doubled) when searching becomes too long. 29 * Internally jhash is used with the assumption that the size of the 30 * stored data is a multiple of sizeof(u32). 31 * 32 * Readers and resizing 33 * 34 * Resizing can be triggered by userspace command only, and those 35 * are serialized by the nfnl mutex. During resizing the set is 36 * read-locked, so the only possible concurrent operations are 37 * the kernel side readers. Those must be protected by proper RCU locking. 38 */ 39 40 /* Number of elements to store in an initial array block */ 41 #define AHASH_INIT_SIZE 2 42 /* Max number of elements to store in an array block */ 43 #define AHASH_MAX_SIZE (6 * AHASH_INIT_SIZE) 44 /* Max muber of elements in the array block when tuned */ 45 #define AHASH_MAX_TUNED 64 46 #define AHASH_MAX(h) ((h)->bucketsize) 47 48 /* A hash bucket */ 49 struct hbucket { 50 struct rcu_head rcu; /* for call_rcu */ 51 /* Which positions are used in the array */ 52 DECLARE_BITMAP(used, AHASH_MAX_TUNED); 53 u8 size; /* size of the array */ 54 u8 pos; /* position of the first free entry */ 55 unsigned char value[] /* the array of the values */ 56 __aligned(__alignof__(u64)); 57 }; 58 59 /* Region size for locking == 2^HTABLE_REGION_BITS */ 60 #define HTABLE_REGION_BITS 10 61 #define ahash_numof_locks(htable_bits) \ 62 ((htable_bits) < HTABLE_REGION_BITS ? 1 \ 63 : jhash_size((htable_bits) - HTABLE_REGION_BITS)) 64 #define ahash_sizeof_regions(htable_bits) \ 65 (ahash_numof_locks(htable_bits) * sizeof(struct ip_set_region)) 66 #define ahash_region(n) \ 67 ((n) / jhash_size(HTABLE_REGION_BITS)) 68 #define ahash_bucket_start(h, htable_bits) \ 69 ((htable_bits) < HTABLE_REGION_BITS ? 0 \ 70 : (h) * jhash_size(HTABLE_REGION_BITS)) 71 #define ahash_bucket_end(h, htable_bits) \ 72 ((htable_bits) < HTABLE_REGION_BITS ? jhash_size(htable_bits) \ 73 : ((h) + 1) * jhash_size(HTABLE_REGION_BITS)) 74 75 struct htable_gc { 76 struct delayed_work dwork; 77 struct ip_set *set; /* Set the gc belongs to */ 78 u32 region; /* Last gc run position */ 79 }; 80 81 /* The hash table: the table size stored here in order to make resizing easy */ 82 struct htable { 83 atomic_t ref; /* References for resizing */ 84 atomic_t uref; /* References for dumping and gc */ 85 u8 htable_bits; /* size of hash table == 2^htable_bits */ 86 u32 maxelem; /* Maxelem per region */ 87 struct ip_set_region *hregion; /* Region locks and ext sizes */ 88 struct hbucket __rcu *bucket[]; /* hashtable buckets */ 89 }; 90 91 #define hbucket(h, i) ((h)->bucket[i]) 92 #define ext_size(n, dsize) \ 93 (sizeof(struct hbucket) + (n) * (dsize)) 94 95 #ifndef IPSET_NET_COUNT 96 #define IPSET_NET_COUNT 1 97 #endif 98 99 /* Book-keeping of the prefixes added to the set */ 100 struct net_prefixes { 101 u32 nets[IPSET_NET_COUNT]; /* number of elements for this cidr */ 102 u8 cidr[IPSET_NET_COUNT]; /* the cidr value */ 103 }; 104 105 /* Compute the hash table size */ 106 static size_t 107 htable_size(u8 hbits) 108 { 109 size_t hsize; 110 111 /* We must fit both into u32 in jhash and INT_MAX in kvmalloc_node() */ 112 if (hbits > 31) 113 return 0; 114 hsize = jhash_size(hbits); 115 if ((INT_MAX - sizeof(struct htable)) / sizeof(struct hbucket *) 116 < hsize) 117 return 0; 118 119 return hsize * sizeof(struct hbucket *) + sizeof(struct htable); 120 } 121 122 #ifdef IP_SET_HASH_WITH_NETS 123 #if IPSET_NET_COUNT > 1 124 #define __CIDR(cidr, i) (cidr[i]) 125 #else 126 #define __CIDR(cidr, i) (cidr) 127 #endif 128 129 /* cidr + 1 is stored in net_prefixes to support /0 */ 130 #define NCIDR_PUT(cidr) ((cidr) + 1) 131 #define NCIDR_GET(cidr) ((cidr) - 1) 132 133 #ifdef IP_SET_HASH_WITH_NETS_PACKED 134 /* When cidr is packed with nomatch, cidr - 1 is stored in the data entry */ 135 #define DCIDR_PUT(cidr) ((cidr) - 1) 136 #define DCIDR_GET(cidr, i) (__CIDR(cidr, i) + 1) 137 #else 138 #define DCIDR_PUT(cidr) (cidr) 139 #define DCIDR_GET(cidr, i) __CIDR(cidr, i) 140 #endif 141 142 #define INIT_CIDR(cidr, host_mask) \ 143 DCIDR_PUT(((cidr) ? NCIDR_GET(cidr) : host_mask)) 144 145 #ifdef IP_SET_HASH_WITH_NET0 146 /* cidr from 0 to HOST_MASK value and c = cidr + 1 */ 147 #define NLEN (HOST_MASK + 1) 148 #define CIDR_POS(c) ((c) - 1) 149 #else 150 /* cidr from 1 to HOST_MASK value and c = cidr + 1 */ 151 #define NLEN HOST_MASK 152 #define CIDR_POS(c) ((c) - 2) 153 #endif 154 155 #else 156 #define NLEN 0 157 #endif /* IP_SET_HASH_WITH_NETS */ 158 159 #define SET_ELEM_EXPIRED(set, d) \ 160 (SET_WITH_TIMEOUT(set) && \ 161 ip_set_timeout_expired(ext_timeout(d, set))) 162 163 #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) 164 static const union nf_inet_addr onesmask = { 165 .all[0] = 0xffffffff, 166 .all[1] = 0xffffffff, 167 .all[2] = 0xffffffff, 168 .all[3] = 0xffffffff 169 }; 170 171 static const union nf_inet_addr zeromask = {}; 172 #endif 173 174 #endif /* _IP_SET_HASH_GEN_H */ 175 176 #ifndef MTYPE 177 #error "MTYPE is not defined!" 178 #endif 179 180 #ifndef HTYPE 181 #error "HTYPE is not defined!" 182 #endif 183 184 #ifndef HOST_MASK 185 #error "HOST_MASK is not defined!" 186 #endif 187 188 /* Family dependent templates */ 189 190 #undef ahash_data 191 #undef mtype_data_equal 192 #undef mtype_do_data_match 193 #undef mtype_data_set_flags 194 #undef mtype_data_reset_elem 195 #undef mtype_data_reset_flags 196 #undef mtype_data_netmask 197 #undef mtype_data_list 198 #undef mtype_data_next 199 #undef mtype_elem 200 201 #undef mtype_ahash_destroy 202 #undef mtype_ext_cleanup 203 #undef mtype_add_cidr 204 #undef mtype_del_cidr 205 #undef mtype_ahash_memsize 206 #undef mtype_flush 207 #undef mtype_destroy 208 #undef mtype_same_set 209 #undef mtype_kadt 210 #undef mtype_uadt 211 212 #undef mtype_add 213 #undef mtype_del 214 #undef mtype_test_cidrs 215 #undef mtype_test 216 #undef mtype_uref 217 #undef mtype_resize 218 #undef mtype_ext_size 219 #undef mtype_resize_ad 220 #undef mtype_head 221 #undef mtype_list 222 #undef mtype_gc_do 223 #undef mtype_gc 224 #undef mtype_gc_init 225 #undef mtype_cancel_gc 226 #undef mtype_variant 227 #undef mtype_data_match 228 229 #undef htype 230 #undef HKEY 231 232 #define mtype_data_equal IPSET_TOKEN(MTYPE, _data_equal) 233 #ifdef IP_SET_HASH_WITH_NETS 234 #define mtype_do_data_match IPSET_TOKEN(MTYPE, _do_data_match) 235 #else 236 #define mtype_do_data_match(d) 1 237 #endif 238 #define mtype_data_set_flags IPSET_TOKEN(MTYPE, _data_set_flags) 239 #define mtype_data_reset_elem IPSET_TOKEN(MTYPE, _data_reset_elem) 240 #define mtype_data_reset_flags IPSET_TOKEN(MTYPE, _data_reset_flags) 241 #define mtype_data_netmask IPSET_TOKEN(MTYPE, _data_netmask) 242 #define mtype_data_list IPSET_TOKEN(MTYPE, _data_list) 243 #define mtype_data_next IPSET_TOKEN(MTYPE, _data_next) 244 #define mtype_elem IPSET_TOKEN(MTYPE, _elem) 245 246 #define mtype_ahash_destroy IPSET_TOKEN(MTYPE, _ahash_destroy) 247 #define mtype_ext_cleanup IPSET_TOKEN(MTYPE, _ext_cleanup) 248 #define mtype_add_cidr IPSET_TOKEN(MTYPE, _add_cidr) 249 #define mtype_del_cidr IPSET_TOKEN(MTYPE, _del_cidr) 250 #define mtype_ahash_memsize IPSET_TOKEN(MTYPE, _ahash_memsize) 251 #define mtype_flush IPSET_TOKEN(MTYPE, _flush) 252 #define mtype_destroy IPSET_TOKEN(MTYPE, _destroy) 253 #define mtype_same_set IPSET_TOKEN(MTYPE, _same_set) 254 #define mtype_kadt IPSET_TOKEN(MTYPE, _kadt) 255 #define mtype_uadt IPSET_TOKEN(MTYPE, _uadt) 256 257 #define mtype_add IPSET_TOKEN(MTYPE, _add) 258 #define mtype_del IPSET_TOKEN(MTYPE, _del) 259 #define mtype_test_cidrs IPSET_TOKEN(MTYPE, _test_cidrs) 260 #define mtype_test IPSET_TOKEN(MTYPE, _test) 261 #define mtype_uref IPSET_TOKEN(MTYPE, _uref) 262 #define mtype_resize IPSET_TOKEN(MTYPE, _resize) 263 #define mtype_ext_size IPSET_TOKEN(MTYPE, _ext_size) 264 #define mtype_resize_ad IPSET_TOKEN(MTYPE, _resize_ad) 265 #define mtype_head IPSET_TOKEN(MTYPE, _head) 266 #define mtype_list IPSET_TOKEN(MTYPE, _list) 267 #define mtype_gc_do IPSET_TOKEN(MTYPE, _gc_do) 268 #define mtype_gc IPSET_TOKEN(MTYPE, _gc) 269 #define mtype_gc_init IPSET_TOKEN(MTYPE, _gc_init) 270 #define mtype_cancel_gc IPSET_TOKEN(MTYPE, _cancel_gc) 271 #define mtype_variant IPSET_TOKEN(MTYPE, _variant) 272 #define mtype_data_match IPSET_TOKEN(MTYPE, _data_match) 273 274 #ifndef HKEY_DATALEN 275 #define HKEY_DATALEN sizeof(struct mtype_elem) 276 #endif 277 278 #define htype MTYPE 279 280 #define HKEY(data, initval, htable_bits) \ 281 ({ \ 282 const u32 *__k = (const u32 *)data; \ 283 u32 __l = HKEY_DATALEN / sizeof(u32); \ 284 \ 285 BUILD_BUG_ON(HKEY_DATALEN % sizeof(u32) != 0); \ 286 \ 287 jhash2(__k, __l, initval) & jhash_mask(htable_bits); \ 288 }) 289 290 /* The generic hash structure */ 291 struct htype { 292 struct htable __rcu *table; /* the hash table */ 293 struct htable_gc gc; /* gc workqueue */ 294 u32 maxelem; /* max elements in the hash */ 295 u32 initval; /* random jhash init value */ 296 #ifdef IP_SET_HASH_WITH_MARKMASK 297 u32 markmask; /* markmask value for mark mask to store */ 298 #endif 299 u8 bucketsize; /* max elements in an array block */ 300 #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) 301 u8 netmask; /* netmask value for subnets to store */ 302 union nf_inet_addr bitmask; /* stores bitmask */ 303 #endif 304 struct list_head ad; /* Resize add|del backlist */ 305 struct mtype_elem next; /* temporary storage for uadd */ 306 #ifdef IP_SET_HASH_WITH_NETS 307 struct net_prefixes nets[NLEN]; /* book-keeping of prefixes */ 308 #endif 309 }; 310 311 /* ADD|DEL entries saved during resize */ 312 struct mtype_resize_ad { 313 struct list_head list; 314 enum ipset_adt ad; /* ADD|DEL element */ 315 struct mtype_elem d; /* Element value */ 316 struct ip_set_ext ext; /* Extensions for ADD */ 317 struct ip_set_ext mext; /* Target extensions for ADD */ 318 u32 flags; /* Flags for ADD */ 319 }; 320 321 #ifdef IP_SET_HASH_WITH_NETS 322 /* Network cidr size book keeping when the hash stores different 323 * sized networks. cidr == real cidr + 1 to support /0. 324 */ 325 static void 326 mtype_add_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n) 327 { 328 int i, j; 329 330 spin_lock_bh(&set->lock); 331 /* Add in increasing prefix order, so larger cidr first */ 332 for (i = 0, j = -1; i < NLEN && h->nets[i].cidr[n]; i++) { 333 if (j != -1) { 334 continue; 335 } else if (h->nets[i].cidr[n] < cidr) { 336 j = i; 337 } else if (h->nets[i].cidr[n] == cidr) { 338 h->nets[CIDR_POS(cidr)].nets[n]++; 339 goto unlock; 340 } 341 } 342 if (j != -1) { 343 for (; i > j; i--) 344 h->nets[i].cidr[n] = h->nets[i - 1].cidr[n]; 345 } 346 h->nets[i].cidr[n] = cidr; 347 h->nets[CIDR_POS(cidr)].nets[n] = 1; 348 unlock: 349 spin_unlock_bh(&set->lock); 350 } 351 352 static void 353 mtype_del_cidr(struct ip_set *set, struct htype *h, u8 cidr, u8 n) 354 { 355 u8 i, j, net_end = NLEN - 1; 356 357 spin_lock_bh(&set->lock); 358 for (i = 0; i < NLEN; i++) { 359 if (h->nets[i].cidr[n] != cidr) 360 continue; 361 h->nets[CIDR_POS(cidr)].nets[n]--; 362 if (h->nets[CIDR_POS(cidr)].nets[n] > 0) 363 goto unlock; 364 for (j = i; j < net_end && h->nets[j].cidr[n]; j++) 365 h->nets[j].cidr[n] = h->nets[j + 1].cidr[n]; 366 h->nets[j].cidr[n] = 0; 367 goto unlock; 368 } 369 unlock: 370 spin_unlock_bh(&set->lock); 371 } 372 #endif 373 374 /* Calculate the actual memory size of the set data */ 375 static size_t 376 mtype_ahash_memsize(const struct htype *h, const struct htable *t) 377 { 378 return sizeof(*h) + sizeof(*t) + ahash_sizeof_regions(t->htable_bits); 379 } 380 381 /* Get the ith element from the array block n */ 382 #define ahash_data(n, i, dsize) \ 383 ((struct mtype_elem *)((n)->value + ((i) * (dsize)))) 384 385 static void 386 mtype_ext_cleanup(struct ip_set *set, struct hbucket *n) 387 { 388 int i; 389 u8 pos = smp_load_acquire(&n->pos); 390 391 for (i = 0; i < pos; i++) 392 if (test_bit(i, n->used)) 393 ip_set_ext_destroy(set, ahash_data(n, i, set->dsize)); 394 } 395 396 /* Flush a hash type of set: destroy all elements */ 397 static void 398 mtype_flush(struct ip_set *set) 399 { 400 struct htype *h = set->data; 401 struct htable *t; 402 struct hbucket *n; 403 u32 r, i; 404 405 t = ipset_dereference_nfnl(h->table); 406 for (r = 0; r < ahash_numof_locks(t->htable_bits); r++) { 407 spin_lock_bh(&t->hregion[r].lock); 408 for (i = ahash_bucket_start(r, t->htable_bits); 409 i < ahash_bucket_end(r, t->htable_bits); i++) { 410 n = __ipset_dereference(hbucket(t, i)); 411 if (!n) 412 continue; 413 if (set->extensions & IPSET_EXT_DESTROY) 414 mtype_ext_cleanup(set, n); 415 /* FIXME: use slab cache */ 416 rcu_assign_pointer(hbucket(t, i), NULL); 417 kfree_rcu(n, rcu); 418 } 419 t->hregion[r].ext_size = 0; 420 t->hregion[r].elements = 0; 421 spin_unlock_bh(&t->hregion[r].lock); 422 } 423 #ifdef IP_SET_HASH_WITH_NETS 424 memset(h->nets, 0, sizeof(h->nets)); 425 #endif 426 } 427 428 /* Destroy the hashtable part of the set */ 429 static void 430 mtype_ahash_destroy(struct ip_set *set, struct htable *t, bool ext_destroy) 431 { 432 struct hbucket *n; 433 u32 i; 434 435 for (i = 0; i < jhash_size(t->htable_bits); i++) { 436 n = (__force struct hbucket *)hbucket(t, i); 437 if (!n) 438 continue; 439 if (set->extensions & IPSET_EXT_DESTROY && ext_destroy) 440 mtype_ext_cleanup(set, n); 441 /* FIXME: use slab cache */ 442 kfree(n); 443 } 444 445 ip_set_free(t->hregion); 446 ip_set_free(t); 447 } 448 449 /* Destroy a hash type of set */ 450 static void 451 mtype_destroy(struct ip_set *set) 452 { 453 struct htype *h = set->data; 454 struct list_head *l, *lt; 455 456 mtype_ahash_destroy(set, (__force struct htable *)h->table, true); 457 list_for_each_safe(l, lt, &h->ad) { 458 list_del(l); 459 kfree(l); 460 } 461 kfree(h); 462 463 set->data = NULL; 464 } 465 466 static bool 467 mtype_same_set(const struct ip_set *a, const struct ip_set *b) 468 { 469 const struct htype *x = a->data; 470 const struct htype *y = b->data; 471 472 /* Resizing changes htable_bits, so we ignore it */ 473 return x->maxelem == y->maxelem && 474 a->timeout == b->timeout && 475 #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) 476 nf_inet_addr_cmp(&x->bitmask, &y->bitmask) && 477 #endif 478 #ifdef IP_SET_HASH_WITH_MARKMASK 479 x->markmask == y->markmask && 480 #endif 481 a->extensions == b->extensions; 482 } 483 484 static void 485 mtype_gc_do(struct ip_set *set, struct htype *h, struct htable *t, u32 r) 486 { 487 struct hbucket *n, *tmp; 488 struct mtype_elem *data; 489 u32 i, j, d; 490 size_t dsize = set->dsize; 491 #ifdef IP_SET_HASH_WITH_NETS 492 u8 k; 493 #endif 494 u8 pos, htable_bits = t->htable_bits; 495 496 spin_lock_bh(&t->hregion[r].lock); 497 for (i = ahash_bucket_start(r, htable_bits); 498 i < ahash_bucket_end(r, htable_bits); i++) { 499 n = __ipset_dereference(hbucket(t, i)); 500 if (!n) 501 continue; 502 pos = smp_load_acquire(&n->pos); 503 for (j = 0, d = 0; j < pos; j++) { 504 if (!test_bit(j, n->used)) { 505 d++; 506 continue; 507 } 508 data = ahash_data(n, j, dsize); 509 if (!ip_set_timeout_expired(ext_timeout(data, set))) 510 continue; 511 pr_debug("expired %u/%u\n", i, j); 512 clear_bit(j, n->used); 513 smp_mb__after_atomic(); 514 #ifdef IP_SET_HASH_WITH_NETS 515 for (k = 0; k < IPSET_NET_COUNT; k++) 516 mtype_del_cidr(set, h, 517 NCIDR_PUT(DCIDR_GET(data->cidr, k)), 518 k); 519 #endif 520 t->hregion[r].elements--; 521 ip_set_ext_destroy(set, data); 522 d++; 523 } 524 if (d >= AHASH_INIT_SIZE) { 525 if (d >= n->size) { 526 t->hregion[r].ext_size -= 527 ext_size(n->size, dsize); 528 rcu_assign_pointer(hbucket(t, i), NULL); 529 kfree_rcu(n, rcu); 530 continue; 531 } 532 tmp = kzalloc(sizeof(*tmp) + 533 (n->size - AHASH_INIT_SIZE) * dsize, 534 GFP_ATOMIC); 535 if (!tmp) 536 /* Still try to delete expired elements. */ 537 continue; 538 tmp->size = n->size - AHASH_INIT_SIZE; 539 for (j = 0, d = 0; j < pos; j++) { 540 if (!test_bit(j, n->used)) 541 continue; 542 data = ahash_data(n, j, dsize); 543 memcpy(tmp->value + d * dsize, 544 data, dsize); 545 set_bit(d, tmp->used); 546 d++; 547 } 548 tmp->pos = d; 549 t->hregion[r].ext_size -= 550 ext_size(AHASH_INIT_SIZE, dsize); 551 rcu_assign_pointer(hbucket(t, i), tmp); 552 kfree_rcu(n, rcu); 553 } 554 } 555 spin_unlock_bh(&t->hregion[r].lock); 556 } 557 558 static void 559 mtype_gc(struct work_struct *work) 560 { 561 struct htable_gc *gc; 562 struct ip_set *set; 563 struct htype *h; 564 struct htable *t; 565 u32 r, numof_locks; 566 unsigned int next_run; 567 568 gc = container_of(work, struct htable_gc, dwork.work); 569 set = gc->set; 570 h = set->data; 571 572 spin_lock_bh(&set->lock); 573 t = ipset_dereference_set(h->table, set); 574 atomic_inc(&t->uref); 575 numof_locks = ahash_numof_locks(t->htable_bits); 576 r = gc->region++; 577 if (r >= numof_locks) { 578 r = gc->region = 0; 579 } 580 next_run = (IPSET_GC_PERIOD(set->timeout) * HZ) / numof_locks; 581 if (next_run < HZ/10) 582 next_run = HZ/10; 583 spin_unlock_bh(&set->lock); 584 585 mtype_gc_do(set, h, t, r); 586 587 if (atomic_dec_and_test(&t->uref) && atomic_read(&t->ref)) { 588 pr_debug("Table destroy after resize by expire: %p\n", t); 589 mtype_ahash_destroy(set, t, false); 590 } 591 592 queue_delayed_work(system_power_efficient_wq, &gc->dwork, next_run); 593 594 } 595 596 static void 597 mtype_gc_init(struct htable_gc *gc) 598 { 599 INIT_DEFERRABLE_WORK(&gc->dwork, mtype_gc); 600 queue_delayed_work(system_power_efficient_wq, &gc->dwork, HZ); 601 } 602 603 static void 604 mtype_cancel_gc(struct ip_set *set) 605 { 606 struct htype *h = set->data; 607 608 if (SET_WITH_TIMEOUT(set)) 609 disable_delayed_work_sync(&h->gc.dwork); 610 } 611 612 static int 613 mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext, 614 struct ip_set_ext *mext, u32 flags); 615 static int 616 mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext, 617 struct ip_set_ext *mext, u32 flags); 618 619 /* Resize a hash: create a new hash table with doubling the hashsize 620 * and inserting the elements to it. Repeat until we succeed or 621 * fail due to memory pressures. 622 */ 623 static int 624 mtype_resize(struct ip_set *set, bool retried) 625 { 626 struct htype *h = set->data; 627 struct htable *t, *orig; 628 u8 pos, htable_bits; 629 size_t hsize, dsize = set->dsize; 630 #ifdef IP_SET_HASH_WITH_NETS 631 u8 flags; 632 struct mtype_elem *tmp; 633 #endif 634 struct mtype_elem *data; 635 struct mtype_elem *d; 636 struct hbucket *n, *m; 637 struct list_head *l, *lt; 638 struct mtype_resize_ad *x; 639 u32 i, j, r, nr, key; 640 int ret; 641 642 #ifdef IP_SET_HASH_WITH_NETS 643 tmp = kmalloc(dsize, GFP_KERNEL); 644 if (!tmp) 645 return -ENOMEM; 646 #endif 647 orig = ipset_dereference_bh_nfnl(h->table); 648 htable_bits = orig->htable_bits; 649 650 retry: 651 ret = 0; 652 htable_bits++; 653 if (!htable_bits) 654 goto hbwarn; 655 hsize = htable_size(htable_bits); 656 if (!hsize) 657 goto hbwarn; 658 t = ip_set_alloc(hsize); 659 if (!t) { 660 ret = -ENOMEM; 661 goto out; 662 } 663 t->hregion = ip_set_alloc(ahash_sizeof_regions(htable_bits)); 664 if (!t->hregion) { 665 ip_set_free(t); 666 ret = -ENOMEM; 667 goto out; 668 } 669 t->htable_bits = htable_bits; 670 t->maxelem = h->maxelem / ahash_numof_locks(htable_bits); 671 for (i = 0; i < ahash_numof_locks(htable_bits); i++) 672 spin_lock_init(&t->hregion[i].lock); 673 674 /* There can't be another parallel resizing, 675 * but dumping, gc, kernel side add/del are possible 676 */ 677 orig = ipset_dereference_bh_nfnl(h->table); 678 atomic_set(&orig->ref, 1); 679 atomic_inc(&orig->uref); 680 pr_debug("attempt to resize set %s from %u to %u, t %p\n", 681 set->name, orig->htable_bits, htable_bits, orig); 682 for (r = 0; r < ahash_numof_locks(orig->htable_bits); r++) { 683 /* Expire may replace a hbucket with another one */ 684 rcu_read_lock_bh(); 685 for (i = ahash_bucket_start(r, orig->htable_bits); 686 i < ahash_bucket_end(r, orig->htable_bits); i++) { 687 n = __ipset_dereference(hbucket(orig, i)); 688 if (!n) 689 continue; 690 pos = smp_load_acquire(&n->pos); 691 for (j = 0; j < pos; j++) { 692 if (!test_bit_acquire(j, n->used)) 693 continue; 694 data = ahash_data(n, j, dsize); 695 if (SET_ELEM_EXPIRED(set, data)) 696 continue; 697 #ifdef IP_SET_HASH_WITH_NETS 698 /* We have readers running parallel with us, 699 * so the live data cannot be modified. 700 */ 701 flags = 0; 702 memcpy(tmp, data, dsize); 703 data = tmp; 704 mtype_data_reset_flags(data, &flags); 705 #endif 706 key = HKEY(data, h->initval, htable_bits); 707 m = __ipset_dereference(hbucket(t, key)); 708 nr = ahash_region(key); 709 if (!m) { 710 m = kzalloc(sizeof(*m) + 711 AHASH_INIT_SIZE * dsize, 712 GFP_ATOMIC); 713 if (!m) { 714 ret = -ENOMEM; 715 goto cleanup; 716 } 717 m->size = AHASH_INIT_SIZE; 718 t->hregion[nr].ext_size += 719 ext_size(AHASH_INIT_SIZE, 720 dsize); 721 RCU_INIT_POINTER(hbucket(t, key), m); 722 } else if (m->pos >= m->size) { 723 struct hbucket *ht; 724 725 if (m->size >= AHASH_MAX(h)) { 726 ret = -EAGAIN; 727 } else { 728 ht = kzalloc(sizeof(*ht) + 729 (m->size + AHASH_INIT_SIZE) 730 * dsize, 731 GFP_ATOMIC); 732 if (!ht) 733 ret = -ENOMEM; 734 } 735 if (ret < 0) 736 goto cleanup; 737 memcpy(ht, m, sizeof(struct hbucket) + 738 m->size * dsize); 739 ht->size = m->size + AHASH_INIT_SIZE; 740 t->hregion[nr].ext_size += 741 ext_size(AHASH_INIT_SIZE, 742 dsize); 743 kfree(m); 744 m = ht; 745 RCU_INIT_POINTER(hbucket(t, key), ht); 746 } 747 d = ahash_data(m, m->pos, dsize); 748 memcpy(d, data, dsize); 749 set_bit(m->pos++, m->used); 750 t->hregion[nr].elements++; 751 #ifdef IP_SET_HASH_WITH_NETS 752 mtype_data_reset_flags(d, &flags); 753 #endif 754 } 755 } 756 rcu_read_unlock_bh(); 757 } 758 759 /* There can't be any other writer. */ 760 rcu_assign_pointer(h->table, t); 761 762 /* Give time to other readers of the set */ 763 synchronize_rcu(); 764 765 pr_debug("set %s resized from %u (%p) to %u (%p)\n", set->name, 766 orig->htable_bits, orig, t->htable_bits, t); 767 /* Add/delete elements processed by the SET target during resize. 768 * Kernel-side add cannot trigger a resize and userspace actions 769 * are serialized by the mutex. 770 */ 771 list_for_each_safe(l, lt, &h->ad) { 772 x = list_entry(l, struct mtype_resize_ad, list); 773 if (x->ad == IPSET_ADD) { 774 mtype_add(set, &x->d, &x->ext, &x->mext, x->flags); 775 } else { 776 mtype_del(set, &x->d, NULL, NULL, 0); 777 } 778 list_del(l); 779 kfree(l); 780 } 781 /* If there's nobody else using the table, destroy it */ 782 if (atomic_dec_and_test(&orig->uref)) { 783 pr_debug("Table destroy by resize %p\n", orig); 784 mtype_ahash_destroy(set, orig, false); 785 } 786 787 out: 788 #ifdef IP_SET_HASH_WITH_NETS 789 kfree(tmp); 790 #endif 791 return ret; 792 793 cleanup: 794 rcu_read_unlock_bh(); 795 atomic_set(&orig->ref, 0); 796 atomic_dec(&orig->uref); 797 mtype_ahash_destroy(set, t, false); 798 if (ret == -EAGAIN) 799 goto retry; 800 goto out; 801 802 hbwarn: 803 /* In case we have plenty of memory :-) */ 804 pr_warn("Cannot increase the hashsize of set %s further\n", set->name); 805 ret = -IPSET_ERR_HASH_FULL; 806 goto out; 807 } 808 809 /* Get the current number of elements and ext_size in the set */ 810 static void 811 mtype_ext_size(struct ip_set *set, u32 *elements, size_t *ext_size) 812 { 813 struct htype *h = set->data; 814 const struct htable *t; 815 struct hbucket *n; 816 struct mtype_elem *data; 817 u32 i, j, r; 818 u8 pos; 819 820 t = rcu_dereference_bh(h->table); 821 for (r = 0; r < ahash_numof_locks(t->htable_bits); r++) { 822 for (i = ahash_bucket_start(r, t->htable_bits); 823 i < ahash_bucket_end(r, t->htable_bits); i++) { 824 n = rcu_dereference_bh(hbucket(t, i)); 825 if (!n) 826 continue; 827 pos = smp_load_acquire(&n->pos); 828 for (j = 0; j < pos; j++) { 829 if (!test_bit_acquire(j, n->used)) 830 continue; 831 data = ahash_data(n, j, set->dsize); 832 if (!SET_ELEM_EXPIRED(set, data)) 833 (*elements)++; 834 } 835 } 836 *ext_size += t->hregion[r].ext_size; 837 } 838 } 839 840 /* Add an element to a hash and update the internal counters when succeeded, 841 * otherwise report the proper error code. 842 */ 843 static int 844 mtype_add(struct ip_set *set, void *value, const struct ip_set_ext *ext, 845 struct ip_set_ext *mext, u32 flags) 846 { 847 struct htype *h = set->data; 848 struct htable *t; 849 const struct mtype_elem *d = value; 850 struct mtype_elem *data; 851 struct hbucket *n, *old = ERR_PTR(-ENOENT); 852 int i, j = -1, ret; 853 bool flag_exist = flags & IPSET_FLAG_EXIST; 854 bool deleted = false, forceadd = false, reuse = false; 855 u32 r, key, multi = 0, elements, maxelem; 856 u8 npos = 0; 857 858 rcu_read_lock_bh(); 859 t = rcu_dereference_bh(h->table); 860 key = HKEY(value, h->initval, t->htable_bits); 861 r = ahash_region(key); 862 atomic_inc(&t->uref); 863 elements = t->hregion[r].elements; 864 maxelem = t->maxelem; 865 if (elements >= maxelem) { 866 u32 e; 867 if (SET_WITH_TIMEOUT(set)) { 868 rcu_read_unlock_bh(); 869 mtype_gc_do(set, h, t, r); 870 rcu_read_lock_bh(); 871 } 872 maxelem = h->maxelem; 873 elements = 0; 874 for (e = 0; e < ahash_numof_locks(t->htable_bits); e++) 875 elements += t->hregion[e].elements; 876 if (elements >= maxelem && SET_WITH_FORCEADD(set)) 877 forceadd = true; 878 } 879 rcu_read_unlock_bh(); 880 881 spin_lock_bh(&t->hregion[r].lock); 882 n = rcu_dereference_bh(hbucket(t, key)); 883 if (!n) { 884 if (forceadd || elements >= maxelem) 885 goto set_full; 886 old = NULL; 887 n = kzalloc(sizeof(*n) + AHASH_INIT_SIZE * set->dsize, 888 GFP_ATOMIC); 889 if (!n) { 890 ret = -ENOMEM; 891 goto unlock; 892 } 893 n->size = AHASH_INIT_SIZE; 894 t->hregion[r].ext_size += 895 ext_size(AHASH_INIT_SIZE, set->dsize); 896 goto copy_elem; 897 } 898 npos = smp_load_acquire(&n->pos); 899 for (i = 0; i < npos; i++) { 900 if (!test_bit(i, n->used)) { 901 /* Reuse first deleted entry */ 902 if (j == -1) { 903 deleted = reuse = true; 904 j = i; 905 } 906 continue; 907 } 908 data = ahash_data(n, i, set->dsize); 909 if (mtype_data_equal(data, d, &multi)) { 910 if (flag_exist || SET_ELEM_EXPIRED(set, data)) { 911 /* Just the extensions could be overwritten */ 912 j = i; 913 goto overwrite_extensions; 914 } 915 ret = -IPSET_ERR_EXIST; 916 goto unlock; 917 } 918 /* Reuse first timed out entry */ 919 if (SET_ELEM_EXPIRED(set, data) && j == -1) { 920 j = i; 921 reuse = true; 922 } 923 } 924 if (reuse || forceadd) { 925 if (j == -1) 926 j = 0; 927 data = ahash_data(n, j, set->dsize); 928 if (!deleted) { 929 #ifdef IP_SET_HASH_WITH_NETS 930 for (i = 0; i < IPSET_NET_COUNT; i++) 931 mtype_del_cidr(set, h, 932 NCIDR_PUT(DCIDR_GET(data->cidr, i)), 933 i); 934 #endif 935 ip_set_ext_destroy(set, data); 936 t->hregion[r].elements--; 937 } 938 goto copy_data; 939 } 940 if (elements >= maxelem) 941 goto set_full; 942 /* Create a new slot */ 943 if (npos >= n->size) { 944 #ifdef IP_SET_HASH_WITH_MULTI 945 if (h->bucketsize >= AHASH_MAX_TUNED) 946 goto set_full; 947 else if (h->bucketsize <= multi) 948 h->bucketsize += AHASH_INIT_SIZE; 949 #endif 950 if (n->size >= AHASH_MAX(h)) { 951 /* Trigger rehashing */ 952 mtype_data_next(&h->next, d); 953 ret = -EAGAIN; 954 goto resize; 955 } 956 old = n; 957 n = kzalloc(sizeof(*n) + 958 (old->size + AHASH_INIT_SIZE) * set->dsize, 959 GFP_ATOMIC); 960 if (!n) { 961 ret = -ENOMEM; 962 goto unlock; 963 } 964 memcpy(n, old, sizeof(struct hbucket) + 965 old->size * set->dsize); 966 n->size = old->size + AHASH_INIT_SIZE; 967 t->hregion[r].ext_size += 968 ext_size(AHASH_INIT_SIZE, set->dsize); 969 } 970 971 copy_elem: 972 j = npos++; 973 data = ahash_data(n, j, set->dsize); 974 copy_data: 975 t->hregion[r].elements++; 976 #ifdef IP_SET_HASH_WITH_NETS 977 for (i = 0; i < IPSET_NET_COUNT; i++) 978 mtype_add_cidr(set, h, NCIDR_PUT(DCIDR_GET(d->cidr, i)), i); 979 #endif 980 memcpy(data, d, sizeof(struct mtype_elem)); 981 overwrite_extensions: 982 #ifdef IP_SET_HASH_WITH_NETS 983 mtype_data_set_flags(data, flags); 984 #endif 985 if (SET_WITH_COUNTER(set)) 986 ip_set_init_counter(ext_counter(data, set), ext); 987 if (SET_WITH_COMMENT(set)) 988 ip_set_init_comment(set, ext_comment(data, set), ext); 989 if (SET_WITH_SKBINFO(set)) 990 ip_set_init_skbinfo(ext_skbinfo(data, set), ext); 991 /* Must come last for the case when timed out entry is reused */ 992 if (SET_WITH_TIMEOUT(set)) 993 ip_set_timeout_set(ext_timeout(data, set), ext->timeout); 994 smp_mb__before_atomic(); 995 /* Ensure all data writes are visible before updating position */ 996 smp_store_release(&n->pos, npos); 997 set_bit(j, n->used); 998 if (old != ERR_PTR(-ENOENT)) { 999 rcu_assign_pointer(hbucket(t, key), n); 1000 if (old) 1001 kfree_rcu(old, rcu); 1002 } 1003 ret = 0; 1004 resize: 1005 spin_unlock_bh(&t->hregion[r].lock); 1006 if (atomic_read(&t->ref) && ext->target) { 1007 /* Resize is in process and kernel side add, save values */ 1008 struct mtype_resize_ad *x; 1009 1010 x = kzalloc_obj(struct mtype_resize_ad, GFP_ATOMIC); 1011 if (!x) 1012 /* Don't bother */ 1013 goto out; 1014 x->ad = IPSET_ADD; 1015 memcpy(&x->d, value, sizeof(struct mtype_elem)); 1016 memcpy(&x->ext, ext, sizeof(struct ip_set_ext)); 1017 memcpy(&x->mext, mext, sizeof(struct ip_set_ext)); 1018 x->flags = flags; 1019 spin_lock_bh(&set->lock); 1020 list_add_tail(&x->list, &h->ad); 1021 spin_unlock_bh(&set->lock); 1022 } 1023 goto out; 1024 1025 set_full: 1026 if (net_ratelimit()) 1027 pr_warn("Set %s is full, maxelem %u reached\n", 1028 set->name, maxelem); 1029 ret = -IPSET_ERR_HASH_FULL; 1030 unlock: 1031 spin_unlock_bh(&t->hregion[r].lock); 1032 out: 1033 if (atomic_dec_and_test(&t->uref) && atomic_read(&t->ref)) { 1034 pr_debug("Table destroy after resize by add: %p\n", t); 1035 mtype_ahash_destroy(set, t, false); 1036 } 1037 return ret; 1038 } 1039 1040 /* Delete an element from the hash and free up space if possible. 1041 */ 1042 static int 1043 mtype_del(struct ip_set *set, void *value, const struct ip_set_ext *ext, 1044 struct ip_set_ext *mext, u32 flags) 1045 { 1046 struct htype *h = set->data; 1047 struct htable *t; 1048 const struct mtype_elem *d = value; 1049 struct mtype_elem *data; 1050 struct hbucket *n; 1051 struct mtype_resize_ad *x = NULL; 1052 int i, j, k, r, ret = -IPSET_ERR_EXIST; 1053 u32 key, multi = 0; 1054 size_t dsize = set->dsize; 1055 u8 pos; 1056 1057 /* Userspace add and resize is excluded by the mutex. 1058 * Kernespace add does not trigger resize. 1059 */ 1060 rcu_read_lock_bh(); 1061 t = rcu_dereference_bh(h->table); 1062 key = HKEY(value, h->initval, t->htable_bits); 1063 r = ahash_region(key); 1064 atomic_inc(&t->uref); 1065 rcu_read_unlock_bh(); 1066 1067 spin_lock_bh(&t->hregion[r].lock); 1068 n = rcu_dereference_bh(hbucket(t, key)); 1069 if (!n) 1070 goto out; 1071 pos = smp_load_acquire(&n->pos); 1072 for (i = 0, k = 0; i < pos; i++) { 1073 if (!test_bit(i, n->used)) { 1074 k++; 1075 continue; 1076 } 1077 data = ahash_data(n, i, dsize); 1078 if (!mtype_data_equal(data, d, &multi)) 1079 continue; 1080 if (SET_ELEM_EXPIRED(set, data)) 1081 goto out; 1082 1083 ret = 0; 1084 clear_bit(i, n->used); 1085 smp_mb__after_atomic(); 1086 if (i + 1 == pos) 1087 smp_store_release(&n->pos, --pos); 1088 t->hregion[r].elements--; 1089 #ifdef IP_SET_HASH_WITH_NETS 1090 for (j = 0; j < IPSET_NET_COUNT; j++) 1091 mtype_del_cidr(set, h, 1092 NCIDR_PUT(DCIDR_GET(d->cidr, j)), j); 1093 #endif 1094 ip_set_ext_destroy(set, data); 1095 1096 if (atomic_read(&t->ref) && ext->target) { 1097 /* Resize is in process and kernel side del, 1098 * save values 1099 */ 1100 x = kzalloc_obj(struct mtype_resize_ad, GFP_ATOMIC); 1101 if (x) { 1102 x->ad = IPSET_DEL; 1103 memcpy(&x->d, value, 1104 sizeof(struct mtype_elem)); 1105 x->flags = flags; 1106 } 1107 } 1108 for (; i < pos; i++) { 1109 if (!test_bit(i, n->used)) 1110 k++; 1111 } 1112 if (k == pos) { 1113 t->hregion[r].ext_size -= ext_size(n->size, dsize); 1114 rcu_assign_pointer(hbucket(t, key), NULL); 1115 kfree_rcu(n, rcu); 1116 } else if (k >= AHASH_INIT_SIZE) { 1117 struct hbucket *tmp = kzalloc(sizeof(*tmp) + 1118 (n->size - AHASH_INIT_SIZE) * dsize, 1119 GFP_ATOMIC); 1120 if (!tmp) 1121 goto out; 1122 tmp->size = n->size - AHASH_INIT_SIZE; 1123 for (j = 0, k = 0; j < pos; j++) { 1124 if (!test_bit(j, n->used)) 1125 continue; 1126 data = ahash_data(n, j, dsize); 1127 memcpy(tmp->value + k * dsize, data, dsize); 1128 set_bit(k, tmp->used); 1129 k++; 1130 } 1131 tmp->pos = k; 1132 t->hregion[r].ext_size -= 1133 ext_size(AHASH_INIT_SIZE, dsize); 1134 rcu_assign_pointer(hbucket(t, key), tmp); 1135 kfree_rcu(n, rcu); 1136 } 1137 goto out; 1138 } 1139 1140 out: 1141 spin_unlock_bh(&t->hregion[r].lock); 1142 if (x) { 1143 spin_lock_bh(&set->lock); 1144 list_add(&x->list, &h->ad); 1145 spin_unlock_bh(&set->lock); 1146 } 1147 if (atomic_dec_and_test(&t->uref) && atomic_read(&t->ref)) { 1148 pr_debug("Table destroy after resize by del: %p\n", t); 1149 mtype_ahash_destroy(set, t, false); 1150 } 1151 return ret; 1152 } 1153 1154 static int 1155 mtype_data_match(struct mtype_elem *data, const struct ip_set_ext *ext, 1156 struct ip_set_ext *mext, struct ip_set *set, u32 flags) 1157 { 1158 if (!ip_set_match_extensions(set, ext, mext, flags, data)) 1159 return 0; 1160 /* nomatch entries return -ENOTEMPTY */ 1161 return mtype_do_data_match(data); 1162 } 1163 1164 #ifdef IP_SET_HASH_WITH_NETS 1165 /* Special test function which takes into account the different network 1166 * sizes added to the set 1167 */ 1168 static int 1169 mtype_test_cidrs(struct ip_set *set, struct mtype_elem *d, 1170 const struct ip_set_ext *ext, 1171 struct ip_set_ext *mext, u32 flags) 1172 { 1173 struct htype *h = set->data; 1174 struct htable *t = rcu_dereference_bh(h->table); 1175 struct hbucket *n; 1176 struct mtype_elem *data; 1177 #if IPSET_NET_COUNT == 2 1178 struct mtype_elem orig = *d; 1179 int ret, i, j = 0, k; 1180 #else 1181 int ret, i, j = 0; 1182 #endif 1183 u32 key, multi = 0; 1184 u8 pos; 1185 1186 pr_debug("test by nets\n"); 1187 for (; j < NLEN && h->nets[j].cidr[0] && !multi; j++) { 1188 #if IPSET_NET_COUNT == 2 1189 mtype_data_reset_elem(d, &orig); 1190 mtype_data_netmask(d, NCIDR_GET(h->nets[j].cidr[0]), false); 1191 for (k = 0; k < NLEN && h->nets[k].cidr[1] && !multi; 1192 k++) { 1193 mtype_data_netmask(d, NCIDR_GET(h->nets[k].cidr[1]), 1194 true); 1195 #else 1196 mtype_data_netmask(d, NCIDR_GET(h->nets[j].cidr[0])); 1197 #endif 1198 key = HKEY(d, h->initval, t->htable_bits); 1199 n = rcu_dereference_bh(hbucket(t, key)); 1200 if (!n) 1201 continue; 1202 pos = smp_load_acquire(&n->pos); 1203 for (i = 0; i < pos; i++) { 1204 if (!test_bit_acquire(i, n->used)) 1205 continue; 1206 data = ahash_data(n, i, set->dsize); 1207 if (!mtype_data_equal(data, d, &multi)) 1208 continue; 1209 ret = mtype_data_match(data, ext, mext, set, flags); 1210 if (ret != 0) 1211 return ret; 1212 #ifdef IP_SET_HASH_WITH_MULTI 1213 /* No match, reset multiple match flag */ 1214 multi = 0; 1215 #endif 1216 } 1217 #if IPSET_NET_COUNT == 2 1218 } 1219 #endif 1220 } 1221 return 0; 1222 } 1223 #endif 1224 1225 /* Test whether the element is added to the set */ 1226 static int 1227 mtype_test(struct ip_set *set, void *value, const struct ip_set_ext *ext, 1228 struct ip_set_ext *mext, u32 flags) 1229 { 1230 struct htype *h = set->data; 1231 struct htable *t; 1232 struct mtype_elem *d = value; 1233 struct hbucket *n; 1234 struct mtype_elem *data; 1235 int i, ret = 0; 1236 u32 key, multi = 0; 1237 u8 pos; 1238 1239 rcu_read_lock_bh(); 1240 t = rcu_dereference_bh(h->table); 1241 #ifdef IP_SET_HASH_WITH_NETS 1242 /* If we test an IP address and not a network address, 1243 * try all possible network sizes 1244 */ 1245 for (i = 0; i < IPSET_NET_COUNT; i++) 1246 if (DCIDR_GET(d->cidr, i) != HOST_MASK) 1247 break; 1248 if (i == IPSET_NET_COUNT) { 1249 ret = mtype_test_cidrs(set, d, ext, mext, flags); 1250 goto out; 1251 } 1252 #endif 1253 1254 key = HKEY(d, h->initval, t->htable_bits); 1255 n = rcu_dereference_bh(hbucket(t, key)); 1256 if (!n) { 1257 ret = 0; 1258 goto out; 1259 } 1260 pos = smp_load_acquire(&n->pos); 1261 for (i = 0; i < pos; i++) { 1262 if (!test_bit_acquire(i, n->used)) 1263 continue; 1264 data = ahash_data(n, i, set->dsize); 1265 if (!mtype_data_equal(data, d, &multi)) 1266 continue; 1267 ret = mtype_data_match(data, ext, mext, set, flags); 1268 if (ret != 0) 1269 goto out; 1270 } 1271 out: 1272 rcu_read_unlock_bh(); 1273 return ret; 1274 } 1275 1276 /* Reply a HEADER request: fill out the header part of the set */ 1277 static int 1278 mtype_head(struct ip_set *set, struct sk_buff *skb) 1279 { 1280 struct htype *h = set->data; 1281 const struct htable *t; 1282 struct nlattr *nested; 1283 size_t memsize; 1284 u32 elements = 0; 1285 size_t ext_size = 0; 1286 u8 htable_bits; 1287 1288 rcu_read_lock_bh(); 1289 t = rcu_dereference_bh(h->table); 1290 mtype_ext_size(set, &elements, &ext_size); 1291 memsize = mtype_ahash_memsize(h, t) + ext_size + set->ext_size; 1292 htable_bits = t->htable_bits; 1293 rcu_read_unlock_bh(); 1294 1295 nested = nla_nest_start(skb, IPSET_ATTR_DATA); 1296 if (!nested) 1297 goto nla_put_failure; 1298 if (nla_put_net32(skb, IPSET_ATTR_HASHSIZE, 1299 htonl(jhash_size(htable_bits))) || 1300 nla_put_net32(skb, IPSET_ATTR_MAXELEM, htonl(h->maxelem))) 1301 goto nla_put_failure; 1302 #ifdef IP_SET_HASH_WITH_BITMASK 1303 /* if netmask is set to anything other than HOST_MASK we know that the user supplied netmask 1304 * and not bitmask. These two are mutually exclusive. */ 1305 if (h->netmask == HOST_MASK && !nf_inet_addr_cmp(&onesmask, &h->bitmask)) { 1306 if (set->family == NFPROTO_IPV4) { 1307 if (nla_put_ipaddr4(skb, IPSET_ATTR_BITMASK, h->bitmask.ip)) 1308 goto nla_put_failure; 1309 } else if (set->family == NFPROTO_IPV6) { 1310 if (nla_put_ipaddr6(skb, IPSET_ATTR_BITMASK, &h->bitmask.in6)) 1311 goto nla_put_failure; 1312 } 1313 } 1314 #endif 1315 #ifdef IP_SET_HASH_WITH_NETMASK 1316 if (h->netmask != HOST_MASK && nla_put_u8(skb, IPSET_ATTR_NETMASK, h->netmask)) 1317 goto nla_put_failure; 1318 #endif 1319 #ifdef IP_SET_HASH_WITH_MARKMASK 1320 if (nla_put_u32(skb, IPSET_ATTR_MARKMASK, h->markmask)) 1321 goto nla_put_failure; 1322 #endif 1323 if (set->flags & IPSET_CREATE_FLAG_BUCKETSIZE) { 1324 if (nla_put_u8(skb, IPSET_ATTR_BUCKETSIZE, h->bucketsize) || 1325 nla_put_net32(skb, IPSET_ATTR_INITVAL, htonl(h->initval))) 1326 goto nla_put_failure; 1327 } 1328 if (nla_put_net32(skb, IPSET_ATTR_REFERENCES, htonl(set->ref)) || 1329 nla_put_net32(skb, IPSET_ATTR_MEMSIZE, htonl(memsize)) || 1330 nla_put_net32(skb, IPSET_ATTR_ELEMENTS, htonl(elements))) 1331 goto nla_put_failure; 1332 if (unlikely(ip_set_put_flags(skb, set))) 1333 goto nla_put_failure; 1334 nla_nest_end(skb, nested); 1335 1336 return 0; 1337 nla_put_failure: 1338 return -EMSGSIZE; 1339 } 1340 1341 /* Make possible to run dumping parallel with resizing */ 1342 static void 1343 mtype_uref(struct ip_set *set, struct netlink_callback *cb, bool start) 1344 { 1345 struct htype *h = set->data; 1346 struct htable *t; 1347 1348 if (start) { 1349 rcu_read_lock_bh(); 1350 t = ipset_dereference_bh_nfnl(h->table); 1351 atomic_inc(&t->uref); 1352 cb->args[IPSET_CB_PRIVATE] = (unsigned long)t; 1353 rcu_read_unlock_bh(); 1354 } else if (cb->args[IPSET_CB_PRIVATE]) { 1355 t = (struct htable *)cb->args[IPSET_CB_PRIVATE]; 1356 if (atomic_dec_and_test(&t->uref) && atomic_read(&t->ref)) { 1357 pr_debug("Table destroy after resize " 1358 " by dump: %p\n", t); 1359 mtype_ahash_destroy(set, t, false); 1360 } 1361 cb->args[IPSET_CB_PRIVATE] = 0; 1362 } 1363 } 1364 1365 /* Reply a LIST/SAVE request: dump the elements of the specified set */ 1366 static int 1367 mtype_list(const struct ip_set *set, 1368 struct sk_buff *skb, struct netlink_callback *cb) 1369 { 1370 const struct htable *t; 1371 struct nlattr *atd, *nested; 1372 const struct hbucket *n; 1373 const struct mtype_elem *e; 1374 u32 first = cb->args[IPSET_CB_ARG0]; 1375 /* We assume that one hash bucket fills into one page */ 1376 void *incomplete; 1377 int i, ret = 0; 1378 u8 pos; 1379 1380 atd = nla_nest_start(skb, IPSET_ATTR_ADT); 1381 if (!atd) 1382 return -EMSGSIZE; 1383 1384 pr_debug("list hash set %s\n", set->name); 1385 t = (const struct htable *)cb->args[IPSET_CB_PRIVATE]; 1386 /* Expire may replace a hbucket with another one */ 1387 rcu_read_lock(); 1388 for (; cb->args[IPSET_CB_ARG0] < jhash_size(t->htable_bits); 1389 cb->args[IPSET_CB_ARG0]++) { 1390 cond_resched_rcu(); 1391 incomplete = skb_tail_pointer(skb); 1392 n = rcu_dereference(hbucket(t, cb->args[IPSET_CB_ARG0])); 1393 pr_debug("cb->arg bucket: %lu, t %p n %p\n", 1394 cb->args[IPSET_CB_ARG0], t, n); 1395 if (!n) 1396 continue; 1397 pos = smp_load_acquire(&n->pos); 1398 for (i = 0; i < pos; i++) { 1399 if (!test_bit_acquire(i, n->used)) 1400 continue; 1401 e = ahash_data(n, i, set->dsize); 1402 if (SET_ELEM_EXPIRED(set, e)) 1403 continue; 1404 pr_debug("list hash %lu hbucket %p i %u, data %p\n", 1405 cb->args[IPSET_CB_ARG0], n, i, e); 1406 nested = nla_nest_start(skb, IPSET_ATTR_DATA); 1407 if (!nested) { 1408 if (cb->args[IPSET_CB_ARG0] == first) { 1409 nla_nest_cancel(skb, atd); 1410 ret = -EMSGSIZE; 1411 goto out; 1412 } 1413 goto nla_put_failure; 1414 } 1415 if (mtype_data_list(skb, e)) 1416 goto nla_put_failure; 1417 if (ip_set_put_extensions(skb, set, e, true)) 1418 goto nla_put_failure; 1419 nla_nest_end(skb, nested); 1420 } 1421 } 1422 nla_nest_end(skb, atd); 1423 /* Set listing finished */ 1424 cb->args[IPSET_CB_ARG0] = 0; 1425 1426 goto out; 1427 1428 nla_put_failure: 1429 nlmsg_trim(skb, incomplete); 1430 if (unlikely(first == cb->args[IPSET_CB_ARG0])) { 1431 pr_warn("Can't list set %s: one bucket does not fit into a message. Please report it!\n", 1432 set->name); 1433 cb->args[IPSET_CB_ARG0] = 0; 1434 ret = -EMSGSIZE; 1435 } else { 1436 nla_nest_end(skb, atd); 1437 } 1438 out: 1439 rcu_read_unlock(); 1440 return ret; 1441 } 1442 1443 static int 1444 IPSET_TOKEN(MTYPE, _kadt)(struct ip_set *set, const struct sk_buff *skb, 1445 const struct xt_action_param *par, 1446 enum ipset_adt adt, struct ip_set_adt_opt *opt); 1447 1448 static int 1449 IPSET_TOKEN(MTYPE, _uadt)(struct ip_set *set, struct nlattr *tb[], 1450 enum ipset_adt adt, u32 *lineno, u32 flags, 1451 bool retried); 1452 1453 static const struct ip_set_type_variant mtype_variant = { 1454 .kadt = mtype_kadt, 1455 .uadt = mtype_uadt, 1456 .adt = { 1457 [IPSET_ADD] = mtype_add, 1458 [IPSET_DEL] = mtype_del, 1459 [IPSET_TEST] = mtype_test, 1460 }, 1461 .destroy = mtype_destroy, 1462 .flush = mtype_flush, 1463 .head = mtype_head, 1464 .list = mtype_list, 1465 .uref = mtype_uref, 1466 .resize = mtype_resize, 1467 .same_set = mtype_same_set, 1468 .cancel_gc = mtype_cancel_gc, 1469 .region_lock = true, 1470 }; 1471 1472 #ifdef IP_SET_EMIT_CREATE 1473 static int 1474 IPSET_TOKEN(HTYPE, _create)(struct net *net, struct ip_set *set, 1475 struct nlattr *tb[], u32 flags) 1476 { 1477 u32 hashsize = IPSET_DEFAULT_HASHSIZE, maxelem = IPSET_DEFAULT_MAXELEM; 1478 #ifdef IP_SET_HASH_WITH_MARKMASK 1479 u32 markmask; 1480 #endif 1481 u8 hbits; 1482 #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) 1483 int ret __attribute__((unused)) = 0; 1484 u8 netmask = set->family == NFPROTO_IPV4 ? 32 : 128; 1485 union nf_inet_addr bitmask = onesmask; 1486 #endif 1487 size_t hsize; 1488 struct htype *h; 1489 struct htable *t; 1490 u32 i; 1491 1492 pr_debug("Create set %s with family %s\n", 1493 set->name, set->family == NFPROTO_IPV4 ? "inet" : "inet6"); 1494 1495 #ifdef IP_SET_PROTO_UNDEF 1496 if (set->family != NFPROTO_UNSPEC) 1497 return -IPSET_ERR_INVALID_FAMILY; 1498 #else 1499 if (!(set->family == NFPROTO_IPV4 || set->family == NFPROTO_IPV6)) 1500 return -IPSET_ERR_INVALID_FAMILY; 1501 #endif 1502 1503 if (unlikely(!ip_set_optattr_netorder(tb, IPSET_ATTR_HASHSIZE) || 1504 !ip_set_optattr_netorder(tb, IPSET_ATTR_MAXELEM) || 1505 !ip_set_optattr_netorder(tb, IPSET_ATTR_TIMEOUT) || 1506 !ip_set_optattr_netorder(tb, IPSET_ATTR_CADT_FLAGS))) 1507 return -IPSET_ERR_PROTOCOL; 1508 1509 #ifdef IP_SET_HASH_WITH_MARKMASK 1510 /* Separated condition in order to avoid directive in argument list */ 1511 if (unlikely(!ip_set_optattr_netorder(tb, IPSET_ATTR_MARKMASK))) 1512 return -IPSET_ERR_PROTOCOL; 1513 1514 markmask = 0xffffffff; 1515 if (tb[IPSET_ATTR_MARKMASK]) { 1516 markmask = ntohl(nla_get_be32(tb[IPSET_ATTR_MARKMASK])); 1517 if (markmask == 0) 1518 return -IPSET_ERR_INVALID_MARKMASK; 1519 } 1520 #endif 1521 1522 #ifdef IP_SET_HASH_WITH_NETMASK 1523 if (tb[IPSET_ATTR_NETMASK]) { 1524 netmask = nla_get_u8(tb[IPSET_ATTR_NETMASK]); 1525 1526 if ((set->family == NFPROTO_IPV4 && netmask > 32) || 1527 (set->family == NFPROTO_IPV6 && netmask > 128) || 1528 netmask == 0) 1529 return -IPSET_ERR_INVALID_NETMASK; 1530 1531 /* we convert netmask to bitmask and store it */ 1532 if (set->family == NFPROTO_IPV4) 1533 bitmask.ip = ip_set_netmask(netmask); 1534 else 1535 ip6_netmask(&bitmask, netmask); 1536 } 1537 #endif 1538 1539 #ifdef IP_SET_HASH_WITH_BITMASK 1540 if (tb[IPSET_ATTR_BITMASK]) { 1541 /* bitmask and netmask do the same thing, allow only one of these options */ 1542 if (tb[IPSET_ATTR_NETMASK]) 1543 return -IPSET_ERR_BITMASK_NETMASK_EXCL; 1544 1545 if (set->family == NFPROTO_IPV4) { 1546 ret = ip_set_get_ipaddr4(tb[IPSET_ATTR_BITMASK], &bitmask.ip); 1547 if (ret || !bitmask.ip) 1548 return -IPSET_ERR_INVALID_NETMASK; 1549 } else if (set->family == NFPROTO_IPV6) { 1550 ret = ip_set_get_ipaddr6(tb[IPSET_ATTR_BITMASK], &bitmask); 1551 if (ret || ipv6_addr_any(&bitmask.in6)) 1552 return -IPSET_ERR_INVALID_NETMASK; 1553 } 1554 1555 if (nf_inet_addr_cmp(&bitmask, &zeromask)) 1556 return -IPSET_ERR_INVALID_NETMASK; 1557 } 1558 #endif 1559 1560 if (tb[IPSET_ATTR_HASHSIZE]) { 1561 hashsize = ip_set_get_h32(tb[IPSET_ATTR_HASHSIZE]); 1562 if (hashsize < IPSET_MIMINAL_HASHSIZE) 1563 hashsize = IPSET_MIMINAL_HASHSIZE; 1564 } 1565 1566 if (tb[IPSET_ATTR_MAXELEM]) 1567 maxelem = ip_set_get_h32(tb[IPSET_ATTR_MAXELEM]); 1568 1569 hsize = sizeof(*h); 1570 h = kzalloc(hsize, GFP_KERNEL); 1571 if (!h) 1572 return -ENOMEM; 1573 1574 /* Compute htable_bits from the user input parameter hashsize. 1575 * Assume that hashsize == 2^htable_bits, 1576 * otherwise round up to the first 2^n value. 1577 */ 1578 hbits = fls(hashsize - 1); 1579 hsize = htable_size(hbits); 1580 if (hsize == 0) { 1581 kfree(h); 1582 return -ENOMEM; 1583 } 1584 t = ip_set_alloc(hsize); 1585 if (!t) { 1586 kfree(h); 1587 return -ENOMEM; 1588 } 1589 t->hregion = ip_set_alloc(ahash_sizeof_regions(hbits)); 1590 if (!t->hregion) { 1591 ip_set_free(t); 1592 kfree(h); 1593 return -ENOMEM; 1594 } 1595 h->gc.set = set; 1596 for (i = 0; i < ahash_numof_locks(hbits); i++) 1597 spin_lock_init(&t->hregion[i].lock); 1598 h->maxelem = maxelem; 1599 #if defined(IP_SET_HASH_WITH_NETMASK) || defined(IP_SET_HASH_WITH_BITMASK) 1600 h->bitmask = bitmask; 1601 h->netmask = netmask; 1602 #endif 1603 #ifdef IP_SET_HASH_WITH_MARKMASK 1604 h->markmask = markmask; 1605 #endif 1606 if (tb[IPSET_ATTR_INITVAL]) 1607 h->initval = ntohl(nla_get_be32(tb[IPSET_ATTR_INITVAL])); 1608 else 1609 get_random_bytes(&h->initval, sizeof(h->initval)); 1610 h->bucketsize = AHASH_MAX_SIZE; 1611 if (tb[IPSET_ATTR_BUCKETSIZE]) { 1612 h->bucketsize = nla_get_u8(tb[IPSET_ATTR_BUCKETSIZE]); 1613 if (h->bucketsize < AHASH_INIT_SIZE) 1614 h->bucketsize = AHASH_INIT_SIZE; 1615 else if (h->bucketsize > AHASH_MAX_SIZE) 1616 h->bucketsize = AHASH_MAX_SIZE; 1617 else if (h->bucketsize % 2) 1618 h->bucketsize += 1; 1619 } 1620 t->htable_bits = hbits; 1621 t->maxelem = h->maxelem / ahash_numof_locks(hbits); 1622 RCU_INIT_POINTER(h->table, t); 1623 1624 INIT_LIST_HEAD(&h->ad); 1625 set->data = h; 1626 #ifndef IP_SET_PROTO_UNDEF 1627 if (set->family == NFPROTO_IPV4) { 1628 #endif 1629 set->variant = &IPSET_TOKEN(HTYPE, 4_variant); 1630 set->dsize = ip_set_elem_len(set, tb, 1631 sizeof(struct IPSET_TOKEN(HTYPE, 4_elem)), 1632 __alignof__(struct IPSET_TOKEN(HTYPE, 4_elem))); 1633 #ifndef IP_SET_PROTO_UNDEF 1634 } else { 1635 set->variant = &IPSET_TOKEN(HTYPE, 6_variant); 1636 set->dsize = ip_set_elem_len(set, tb, 1637 sizeof(struct IPSET_TOKEN(HTYPE, 6_elem)), 1638 __alignof__(struct IPSET_TOKEN(HTYPE, 6_elem))); 1639 } 1640 #endif 1641 set->timeout = IPSET_NO_TIMEOUT; 1642 if (tb[IPSET_ATTR_TIMEOUT]) { 1643 set->timeout = ip_set_timeout_uget(tb[IPSET_ATTR_TIMEOUT]); 1644 #ifndef IP_SET_PROTO_UNDEF 1645 if (set->family == NFPROTO_IPV4) 1646 #endif 1647 IPSET_TOKEN(HTYPE, 4_gc_init)(&h->gc); 1648 #ifndef IP_SET_PROTO_UNDEF 1649 else 1650 IPSET_TOKEN(HTYPE, 6_gc_init)(&h->gc); 1651 #endif 1652 } 1653 pr_debug("create %s hashsize %u (%u) maxelem %u: %p(%p)\n", 1654 set->name, jhash_size(t->htable_bits), 1655 t->htable_bits, h->maxelem, set->data, t); 1656 1657 return 0; 1658 } 1659 #endif /* IP_SET_EMIT_CREATE */ 1660 1661 #undef HKEY_DATALEN 1662