1 #ifndef _IP_SET_AHASH_H
2 #define _IP_SET_AHASH_H
4 #include <linux/rcupdate.h>
5 #include <linux/jhash.h>
6 #include <linux/netfilter/ipset/ip_set_timeout.h>
8 #define CONCAT(a, b, c) a##b##c
9 #define TOKEN(a, b, c) CONCAT(a, b, c)
11 #define type_pf_next TOKEN(TYPE, PF, _elem)
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.
20 * Readers and resizing
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.
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)
33 /* Max number of elements can be tuned */
34 #ifdef IP_SET_HASH_WITH_MULTI
35 #define AHASH_MAX(h) ((h)->ahash_max)
38 tune_ahash_max(u8 curr
, u32 multi
)
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.
49 return n
> curr
&& n
<= 64 ? n
: curr
;
51 #define TUNE_AHASH_MAX(h, multi) \
52 ((h)->ahash_max = tune_ahash_max((h)->ahash_max, multi))
54 #define AHASH_MAX(h) AHASH_MAX_SIZE
55 #define TUNE_AHASH_MAX(h, multi)
60 void *value
; /* the array of the values */
61 u8 size
; /* size of the array */
62 u8 pos
; /* position of the first free entry */
65 /* The hash table: the table size stored here in order to make resizing easy */
67 u8 htable_bits
; /* size of hash table == 2^htable_bits */
68 struct hbucket bucket
[0]; /* hashtable buckets */
71 #define hbucket(h, i) (&((h)->bucket[i]))
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 */
79 /* The generic ip_set hash structure */
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 */
91 #ifdef IP_SET_HASH_WITH_NETMASK
92 u8 netmask
; /* netmask value for subnets to store */
94 #ifdef IP_SET_HASH_WITH_RBTREE
95 struct rb_root rbtree
;
97 #ifdef IP_SET_HASH_WITH_NETS
98 struct ip_set_hash_nets nets
[0]; /* book-keeping of prefixes */
103 htable_size(u8 hbits
)
107 /* We must fit both into u32 in jhash and size_t */
110 hsize
= jhash_size(hbits
);
111 if ((((size_t)-1) - sizeof(struct htable
))/sizeof(struct hbucket
)
115 return hsize
* sizeof(struct hbucket
) + sizeof(struct htable
);
118 /* Compute htable_bits from the user input parameter hashsize */
120 htable_bits(u32 hashsize
)
122 /* Assume that hashsize == 2^htable_bits */
123 u8 bits
= fls(hashsize
- 1);
124 if (jhash_size(bits
) != hashsize
)
125 /* Round up to the first 2^n value */
126 bits
= fls(hashsize
);
131 #ifdef IP_SET_HASH_WITH_NETS
132 #ifdef IP_SET_HASH_WITH_NETS_PACKED
133 /* When cidr is packed with nomatch, cidr - 1 is stored in the entry */
134 #define CIDR(cidr) (cidr + 1)
136 #define CIDR(cidr) (cidr)
139 #define SET_HOST_MASK(family) (family == AF_INET ? 32 : 128)
140 #ifdef IP_SET_HASH_WITH_MULTI
141 #define NETS_LENGTH(family) (SET_HOST_MASK(family) + 1)
143 #define NETS_LENGTH(family) SET_HOST_MASK(family)
146 /* Network cidr size book keeping when the hash stores different
149 add_cidr(struct ip_set_hash
*h
, u8 cidr
, u8 nets_length
)
153 /* Add in increasing prefix order, so larger cidr first */
154 for (i
= 0, j
= -1; i
< nets_length
&& h
->nets
[i
].nets
; i
++) {
157 else if (h
->nets
[i
].cidr
< cidr
)
159 else if (h
->nets
[i
].cidr
== cidr
) {
166 h
->nets
[i
].cidr
= h
->nets
[i
- 1].cidr
;
167 h
->nets
[i
].nets
= h
->nets
[i
- 1].nets
;
170 h
->nets
[i
].cidr
= cidr
;
175 del_cidr(struct ip_set_hash
*h
, u8 cidr
, u8 nets_length
)
179 for (i
= 0; i
< nets_length
- 1 && h
->nets
[i
].cidr
!= cidr
; i
++)
183 if (h
->nets
[i
].nets
!= 0)
186 for (j
= i
; j
< nets_length
- 1 && h
->nets
[j
].nets
; j
++) {
187 h
->nets
[j
].cidr
= h
->nets
[j
+ 1].cidr
;
188 h
->nets
[j
].nets
= h
->nets
[j
+ 1].nets
;
192 #define NETS_LENGTH(family) 0
195 /* Destroy the hashtable part of the set */
197 ahash_destroy(struct htable
*t
)
202 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
205 /* FIXME: use slab cache */
212 /* Calculate the actual memory size of the set data */
214 ahash_memsize(const struct ip_set_hash
*h
, size_t dsize
, u8 nets_length
)
217 struct htable
*t
= h
->table
;
218 size_t memsize
= sizeof(*h
)
220 #ifdef IP_SET_HASH_WITH_NETS
221 + sizeof(struct ip_set_hash_nets
) * nets_length
223 + jhash_size(t
->htable_bits
) * sizeof(struct hbucket
);
225 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++)
226 memsize
+= t
->bucket
[i
].size
* dsize
;
231 /* Flush a hash type of set: destroy all elements */
233 ip_set_hash_flush(struct ip_set
*set
)
235 struct ip_set_hash
*h
= set
->data
;
236 struct htable
*t
= h
->table
;
240 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
243 n
->size
= n
->pos
= 0;
244 /* FIXME: use slab cache */
248 #ifdef IP_SET_HASH_WITH_NETS
249 memset(h
->nets
, 0, sizeof(struct ip_set_hash_nets
)
250 * NETS_LENGTH(set
->family
));
255 /* Destroy a hash type of set */
257 ip_set_hash_destroy(struct ip_set
*set
)
259 struct ip_set_hash
*h
= set
->data
;
261 if (with_timeout(h
->timeout
))
262 del_timer_sync(&h
->gc
);
264 ahash_destroy(h
->table
);
265 #ifdef IP_SET_HASH_WITH_RBTREE
266 rbtree_destroy(&h
->rbtree
);
273 #endif /* _IP_SET_AHASH_H */
276 #define HKEY_DATALEN sizeof(struct type_pf_elem)
279 #define HKEY(data, initval, htable_bits) \
280 (jhash2((u32 *)(data), HKEY_DATALEN/sizeof(u32), initval) \
281 & jhash_mask(htable_bits))
283 /* Type/family dependent function prototypes */
285 #define type_pf_data_equal TOKEN(TYPE, PF, _data_equal)
286 #define type_pf_data_isnull TOKEN(TYPE, PF, _data_isnull)
287 #define type_pf_data_copy TOKEN(TYPE, PF, _data_copy)
288 #define type_pf_data_zero_out TOKEN(TYPE, PF, _data_zero_out)
289 #define type_pf_data_netmask TOKEN(TYPE, PF, _data_netmask)
290 #define type_pf_data_list TOKEN(TYPE, PF, _data_list)
291 #define type_pf_data_tlist TOKEN(TYPE, PF, _data_tlist)
292 #define type_pf_data_next TOKEN(TYPE, PF, _data_next)
293 #define type_pf_data_flags TOKEN(TYPE, PF, _data_flags)
294 #define type_pf_data_reset_flags TOKEN(TYPE, PF, _data_reset_flags)
295 #ifdef IP_SET_HASH_WITH_NETS
296 #define type_pf_data_match TOKEN(TYPE, PF, _data_match)
298 #define type_pf_data_match(d) 1
301 #define type_pf_elem TOKEN(TYPE, PF, _elem)
302 #define type_pf_telem TOKEN(TYPE, PF, _telem)
303 #define type_pf_data_timeout TOKEN(TYPE, PF, _data_timeout)
304 #define type_pf_data_expired TOKEN(TYPE, PF, _data_expired)
305 #define type_pf_data_timeout_set TOKEN(TYPE, PF, _data_timeout_set)
307 #define type_pf_elem_add TOKEN(TYPE, PF, _elem_add)
308 #define type_pf_add TOKEN(TYPE, PF, _add)
309 #define type_pf_del TOKEN(TYPE, PF, _del)
310 #define type_pf_test_cidrs TOKEN(TYPE, PF, _test_cidrs)
311 #define type_pf_test TOKEN(TYPE, PF, _test)
313 #define type_pf_elem_tadd TOKEN(TYPE, PF, _elem_tadd)
314 #define type_pf_del_telem TOKEN(TYPE, PF, _ahash_del_telem)
315 #define type_pf_expire TOKEN(TYPE, PF, _expire)
316 #define type_pf_tadd TOKEN(TYPE, PF, _tadd)
317 #define type_pf_tdel TOKEN(TYPE, PF, _tdel)
318 #define type_pf_ttest_cidrs TOKEN(TYPE, PF, _ahash_ttest_cidrs)
319 #define type_pf_ttest TOKEN(TYPE, PF, _ahash_ttest)
321 #define type_pf_resize TOKEN(TYPE, PF, _resize)
322 #define type_pf_tresize TOKEN(TYPE, PF, _tresize)
323 #define type_pf_flush ip_set_hash_flush
324 #define type_pf_destroy ip_set_hash_destroy
325 #define type_pf_head TOKEN(TYPE, PF, _head)
326 #define type_pf_list TOKEN(TYPE, PF, _list)
327 #define type_pf_tlist TOKEN(TYPE, PF, _tlist)
328 #define type_pf_same_set TOKEN(TYPE, PF, _same_set)
329 #define type_pf_kadt TOKEN(TYPE, PF, _kadt)
330 #define type_pf_uadt TOKEN(TYPE, PF, _uadt)
331 #define type_pf_gc TOKEN(TYPE, PF, _gc)
332 #define type_pf_gc_init TOKEN(TYPE, PF, _gc_init)
333 #define type_pf_variant TOKEN(TYPE, PF, _variant)
334 #define type_pf_tvariant TOKEN(TYPE, PF, _tvariant)
336 /* Flavour without timeout */
338 /* Get the ith element from the array block n */
339 #define ahash_data(n, i) \
340 ((struct type_pf_elem *)((n)->value) + (i))
342 /* Add an element to the hash table when resizing the set:
343 * we spare the maintenance of the internal counters. */
345 type_pf_elem_add(struct hbucket
*n
, const struct type_pf_elem
*value
,
346 u8 ahash_max
, u32 cadt_flags
)
348 struct type_pf_elem
*data
;
350 if (n
->pos
>= n
->size
) {
353 if (n
->size
>= ahash_max
)
354 /* Trigger rehashing */
357 tmp
= kzalloc((n
->size
+ AHASH_INIT_SIZE
)
358 * sizeof(struct type_pf_elem
),
363 memcpy(tmp
, n
->value
,
364 sizeof(struct type_pf_elem
) * n
->size
);
368 n
->size
+= AHASH_INIT_SIZE
;
370 data
= ahash_data(n
, n
->pos
++);
371 type_pf_data_copy(data
, value
);
372 #ifdef IP_SET_HASH_WITH_NETS
373 /* Resizing won't overwrite stored flags */
375 type_pf_data_flags(data
, cadt_flags
);
380 /* Resize a hash: create a new hash table with doubling the hashsize
381 * and inserting the elements to it. Repeat until we succeed or
382 * fail due to memory pressures. */
384 type_pf_resize(struct ip_set
*set
, bool retried
)
386 struct ip_set_hash
*h
= set
->data
;
387 struct htable
*t
, *orig
= h
->table
;
388 u8 htable_bits
= orig
->htable_bits
;
389 struct type_pf_elem
*data
;
390 struct hbucket
*n
, *m
;
397 pr_debug("attempt to resize set %s from %u to %u, t %p\n",
398 set
->name
, orig
->htable_bits
, htable_bits
, orig
);
400 /* In case we have plenty of memory :-) */
401 pr_warning("Cannot increase the hashsize of set %s further\n",
403 return -IPSET_ERR_HASH_FULL
;
405 t
= ip_set_alloc(sizeof(*t
)
406 + jhash_size(htable_bits
) * sizeof(struct hbucket
));
409 t
->htable_bits
= htable_bits
;
411 read_lock_bh(&set
->lock
);
412 for (i
= 0; i
< jhash_size(orig
->htable_bits
); i
++) {
413 n
= hbucket(orig
, i
);
414 for (j
= 0; j
< n
->pos
; j
++) {
415 data
= ahash_data(n
, j
);
416 #ifdef IP_SET_HASH_WITH_NETS
418 type_pf_data_reset_flags(data
, &flags
);
420 m
= hbucket(t
, HKEY(data
, h
->initval
, htable_bits
));
421 ret
= type_pf_elem_add(m
, data
, AHASH_MAX(h
), flags
);
423 #ifdef IP_SET_HASH_WITH_NETS
424 type_pf_data_flags(data
, flags
);
426 read_unlock_bh(&set
->lock
);
435 rcu_assign_pointer(h
->table
, t
);
436 read_unlock_bh(&set
->lock
);
438 /* Give time to other readers of the set */
439 synchronize_rcu_bh();
441 pr_debug("set %s resized from %u (%p) to %u (%p)\n", set
->name
,
442 orig
->htable_bits
, orig
, t
->htable_bits
, t
);
449 type_pf_data_next(struct ip_set_hash
*h
, const struct type_pf_elem
*d
);
451 /* Add an element to a hash and update the internal counters when succeeded,
452 * otherwise report the proper error code. */
454 type_pf_add(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
456 struct ip_set_hash
*h
= set
->data
;
458 const struct type_pf_elem
*d
= value
;
462 u32 cadt_flags
= flags
>> 16;
464 if (h
->elements
>= h
->maxelem
) {
466 pr_warning("Set %s is full, maxelem %u reached\n",
467 set
->name
, h
->maxelem
);
468 return -IPSET_ERR_HASH_FULL
;
472 t
= rcu_dereference_bh(h
->table
);
473 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
475 for (i
= 0; i
< n
->pos
; i
++)
476 if (type_pf_data_equal(ahash_data(n
, i
), d
, &multi
)) {
477 #ifdef IP_SET_HASH_WITH_NETS
478 if (flags
& IPSET_FLAG_EXIST
)
479 /* Support overwriting just the flags */
480 type_pf_data_flags(ahash_data(n
, i
),
483 ret
= -IPSET_ERR_EXIST
;
486 TUNE_AHASH_MAX(h
, multi
);
487 ret
= type_pf_elem_add(n
, value
, AHASH_MAX(h
), cadt_flags
);
490 type_pf_data_next(h
, d
);
494 #ifdef IP_SET_HASH_WITH_NETS
495 add_cidr(h
, CIDR(d
->cidr
), NETS_LENGTH(set
->family
));
499 rcu_read_unlock_bh();
503 /* Delete an element from the hash: swap it with the last element
504 * and free up space if possible.
507 type_pf_del(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
509 struct ip_set_hash
*h
= set
->data
;
510 struct htable
*t
= h
->table
;
511 const struct type_pf_elem
*d
= value
;
514 struct type_pf_elem
*data
;
517 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
519 for (i
= 0; i
< n
->pos
; i
++) {
520 data
= ahash_data(n
, i
);
521 if (!type_pf_data_equal(data
, d
, &multi
))
525 type_pf_data_copy(data
, ahash_data(n
, n
->pos
- 1));
529 #ifdef IP_SET_HASH_WITH_NETS
530 del_cidr(h
, CIDR(d
->cidr
), NETS_LENGTH(set
->family
));
532 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
533 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
534 * sizeof(struct type_pf_elem
),
538 n
->size
-= AHASH_INIT_SIZE
;
539 memcpy(tmp
, n
->value
,
540 n
->size
* sizeof(struct type_pf_elem
));
547 return -IPSET_ERR_EXIST
;
550 #ifdef IP_SET_HASH_WITH_NETS
552 /* Special test function which takes into account the different network
553 * sizes added to the set */
555 type_pf_test_cidrs(struct ip_set
*set
, struct type_pf_elem
*d
, u32 timeout
)
557 struct ip_set_hash
*h
= set
->data
;
558 struct htable
*t
= h
->table
;
560 const struct type_pf_elem
*data
;
563 u8 nets_length
= NETS_LENGTH(set
->family
);
565 pr_debug("test by nets\n");
566 for (; j
< nets_length
&& h
->nets
[j
].nets
&& !multi
; j
++) {
567 type_pf_data_netmask(d
, h
->nets
[j
].cidr
);
568 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
570 for (i
= 0; i
< n
->pos
; i
++) {
571 data
= ahash_data(n
, i
);
572 if (type_pf_data_equal(data
, d
, &multi
))
573 return type_pf_data_match(data
);
580 /* Test whether the element is added to the set */
582 type_pf_test(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
584 struct ip_set_hash
*h
= set
->data
;
585 struct htable
*t
= h
->table
;
586 struct type_pf_elem
*d
= value
;
588 const struct type_pf_elem
*data
;
592 #ifdef IP_SET_HASH_WITH_NETS
593 /* If we test an IP address and not a network address,
594 * try all possible network sizes */
595 if (CIDR(d
->cidr
) == SET_HOST_MASK(set
->family
))
596 return type_pf_test_cidrs(set
, d
, timeout
);
599 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
601 for (i
= 0; i
< n
->pos
; i
++) {
602 data
= ahash_data(n
, i
);
603 if (type_pf_data_equal(data
, d
, &multi
))
604 return type_pf_data_match(data
);
609 /* Reply a HEADER request: fill out the header part of the set */
611 type_pf_head(struct ip_set
*set
, struct sk_buff
*skb
)
613 const struct ip_set_hash
*h
= set
->data
;
614 struct nlattr
*nested
;
617 read_lock_bh(&set
->lock
);
618 memsize
= ahash_memsize(h
, with_timeout(h
->timeout
)
619 ? sizeof(struct type_pf_telem
)
620 : sizeof(struct type_pf_elem
),
621 NETS_LENGTH(set
->family
));
622 read_unlock_bh(&set
->lock
);
624 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
626 goto nla_put_failure
;
627 if (nla_put_net32(skb
, IPSET_ATTR_HASHSIZE
,
628 htonl(jhash_size(h
->table
->htable_bits
))) ||
629 nla_put_net32(skb
, IPSET_ATTR_MAXELEM
, htonl(h
->maxelem
)))
630 goto nla_put_failure
;
631 #ifdef IP_SET_HASH_WITH_NETMASK
632 if (h
->netmask
!= HOST_MASK
&&
633 nla_put_u8(skb
, IPSET_ATTR_NETMASK
, h
->netmask
))
634 goto nla_put_failure
;
636 if (nla_put_net32(skb
, IPSET_ATTR_REFERENCES
, htonl(set
->ref
- 1)) ||
637 nla_put_net32(skb
, IPSET_ATTR_MEMSIZE
, htonl(memsize
)) ||
638 (with_timeout(h
->timeout
) &&
639 nla_put_net32(skb
, IPSET_ATTR_TIMEOUT
, htonl(h
->timeout
))))
640 goto nla_put_failure
;
641 ipset_nest_end(skb
, nested
);
648 /* Reply a LIST/SAVE request: dump the elements of the specified set */
650 type_pf_list(const struct ip_set
*set
,
651 struct sk_buff
*skb
, struct netlink_callback
*cb
)
653 const struct ip_set_hash
*h
= set
->data
;
654 const struct htable
*t
= h
->table
;
655 struct nlattr
*atd
, *nested
;
656 const struct hbucket
*n
;
657 const struct type_pf_elem
*data
;
658 u32 first
= cb
->args
[2];
659 /* We assume that one hash bucket fills into one page */
663 atd
= ipset_nest_start(skb
, IPSET_ATTR_ADT
);
666 pr_debug("list hash set %s\n", set
->name
);
667 for (; cb
->args
[2] < jhash_size(t
->htable_bits
); cb
->args
[2]++) {
668 incomplete
= skb_tail_pointer(skb
);
669 n
= hbucket(t
, cb
->args
[2]);
670 pr_debug("cb->args[2]: %lu, t %p n %p\n", cb
->args
[2], t
, n
);
671 for (i
= 0; i
< n
->pos
; i
++) {
672 data
= ahash_data(n
, i
);
673 pr_debug("list hash %lu hbucket %p i %u, data %p\n",
674 cb
->args
[2], n
, i
, data
);
675 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
677 if (cb
->args
[2] == first
) {
678 nla_nest_cancel(skb
, atd
);
681 goto nla_put_failure
;
683 if (type_pf_data_list(skb
, data
))
684 goto nla_put_failure
;
685 ipset_nest_end(skb
, nested
);
688 ipset_nest_end(skb
, atd
);
689 /* Set listing finished */
695 nlmsg_trim(skb
, incomplete
);
696 ipset_nest_end(skb
, atd
);
697 if (unlikely(first
== cb
->args
[2])) {
698 pr_warning("Can't list set %s: one bucket does not fit into "
699 "a message. Please report it!\n", set
->name
);
707 type_pf_kadt(struct ip_set
*set
, const struct sk_buff
*skb
,
708 const struct xt_action_param
*par
,
709 enum ipset_adt adt
, const struct ip_set_adt_opt
*opt
);
711 type_pf_uadt(struct ip_set
*set
, struct nlattr
*tb
[],
712 enum ipset_adt adt
, u32
*lineno
, u32 flags
, bool retried
);
714 static const struct ip_set_type_variant type_pf_variant
= {
715 .kadt
= type_pf_kadt
,
716 .uadt
= type_pf_uadt
,
718 [IPSET_ADD
] = type_pf_add
,
719 [IPSET_DEL
] = type_pf_del
,
720 [IPSET_TEST
] = type_pf_test
,
722 .destroy
= type_pf_destroy
,
723 .flush
= type_pf_flush
,
724 .head
= type_pf_head
,
725 .list
= type_pf_list
,
726 .resize
= type_pf_resize
,
727 .same_set
= type_pf_same_set
,
730 /* Flavour with timeout support */
732 #define ahash_tdata(n, i) \
733 (struct type_pf_elem *)((struct type_pf_telem *)((n)->value) + (i))
736 type_pf_data_timeout(const struct type_pf_elem
*data
)
738 const struct type_pf_telem
*tdata
=
739 (const struct type_pf_telem
*) data
;
741 return tdata
->timeout
;
745 type_pf_data_expired(const struct type_pf_elem
*data
)
747 const struct type_pf_telem
*tdata
=
748 (const struct type_pf_telem
*) data
;
750 return ip_set_timeout_expired(tdata
->timeout
);
754 type_pf_data_timeout_set(struct type_pf_elem
*data
, u32 timeout
)
756 struct type_pf_telem
*tdata
= (struct type_pf_telem
*) data
;
758 tdata
->timeout
= ip_set_timeout_set(timeout
);
762 type_pf_elem_tadd(struct hbucket
*n
, const struct type_pf_elem
*value
,
763 u8 ahash_max
, u32 cadt_flags
, u32 timeout
)
765 struct type_pf_elem
*data
;
767 if (n
->pos
>= n
->size
) {
770 if (n
->size
>= ahash_max
)
771 /* Trigger rehashing */
774 tmp
= kzalloc((n
->size
+ AHASH_INIT_SIZE
)
775 * sizeof(struct type_pf_telem
),
780 memcpy(tmp
, n
->value
,
781 sizeof(struct type_pf_telem
) * n
->size
);
785 n
->size
+= AHASH_INIT_SIZE
;
787 data
= ahash_tdata(n
, n
->pos
++);
788 type_pf_data_copy(data
, value
);
789 type_pf_data_timeout_set(data
, timeout
);
790 #ifdef IP_SET_HASH_WITH_NETS
791 /* Resizing won't overwrite stored flags */
793 type_pf_data_flags(data
, cadt_flags
);
798 /* Delete expired elements from the hashtable */
800 type_pf_expire(struct ip_set_hash
*h
, u8 nets_length
)
802 struct htable
*t
= h
->table
;
804 struct type_pf_elem
*data
;
808 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
810 for (j
= 0; j
< n
->pos
; j
++) {
811 data
= ahash_tdata(n
, j
);
812 if (type_pf_data_expired(data
)) {
813 pr_debug("expired %u/%u\n", i
, j
);
814 #ifdef IP_SET_HASH_WITH_NETS
815 del_cidr(h
, CIDR(data
->cidr
), nets_length
);
819 type_pf_data_copy(data
,
820 ahash_tdata(n
, n
->pos
- 1));
825 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
826 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
827 * sizeof(struct type_pf_telem
),
830 /* Still try to delete expired elements */
832 n
->size
-= AHASH_INIT_SIZE
;
833 memcpy(tmp
, n
->value
,
834 n
->size
* sizeof(struct type_pf_telem
));
842 type_pf_tresize(struct ip_set
*set
, bool retried
)
844 struct ip_set_hash
*h
= set
->data
;
845 struct htable
*t
, *orig
= h
->table
;
846 u8 htable_bits
= orig
->htable_bits
;
847 struct type_pf_elem
*data
;
848 struct hbucket
*n
, *m
;
852 /* Try to cleanup once */
855 write_lock_bh(&set
->lock
);
856 type_pf_expire(set
->data
, NETS_LENGTH(set
->family
));
857 write_unlock_bh(&set
->lock
);
865 pr_debug("attempt to resize set %s from %u to %u, t %p\n",
866 set
->name
, orig
->htable_bits
, htable_bits
, orig
);
868 /* In case we have plenty of memory :-) */
869 pr_warning("Cannot increase the hashsize of set %s further\n",
871 return -IPSET_ERR_HASH_FULL
;
873 t
= ip_set_alloc(sizeof(*t
)
874 + jhash_size(htable_bits
) * sizeof(struct hbucket
));
877 t
->htable_bits
= htable_bits
;
879 read_lock_bh(&set
->lock
);
880 for (i
= 0; i
< jhash_size(orig
->htable_bits
); i
++) {
881 n
= hbucket(orig
, i
);
882 for (j
= 0; j
< n
->pos
; j
++) {
883 data
= ahash_tdata(n
, j
);
884 #ifdef IP_SET_HASH_WITH_NETS
886 type_pf_data_reset_flags(data
, &flags
);
888 m
= hbucket(t
, HKEY(data
, h
->initval
, htable_bits
));
889 ret
= type_pf_elem_tadd(m
, data
, AHASH_MAX(h
), flags
,
890 ip_set_timeout_get(type_pf_data_timeout(data
)));
892 #ifdef IP_SET_HASH_WITH_NETS
893 type_pf_data_flags(data
, flags
);
895 read_unlock_bh(&set
->lock
);
904 rcu_assign_pointer(h
->table
, t
);
905 read_unlock_bh(&set
->lock
);
907 /* Give time to other readers of the set */
908 synchronize_rcu_bh();
916 type_pf_tadd(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
918 struct ip_set_hash
*h
= set
->data
;
919 struct htable
*t
= h
->table
;
920 const struct type_pf_elem
*d
= value
;
922 struct type_pf_elem
*data
;
923 int ret
= 0, i
, j
= AHASH_MAX(h
) + 1;
924 bool flag_exist
= flags
& IPSET_FLAG_EXIST
;
926 u32 cadt_flags
= flags
>> 16;
928 if (h
->elements
>= h
->maxelem
)
929 /* FIXME: when set is full, we slow down here */
930 type_pf_expire(h
, NETS_LENGTH(set
->family
));
931 if (h
->elements
>= h
->maxelem
) {
933 pr_warning("Set %s is full, maxelem %u reached\n",
934 set
->name
, h
->maxelem
);
935 return -IPSET_ERR_HASH_FULL
;
939 t
= rcu_dereference_bh(h
->table
);
940 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
942 for (i
= 0; i
< n
->pos
; i
++) {
943 data
= ahash_tdata(n
, i
);
944 if (type_pf_data_equal(data
, d
, &multi
)) {
945 if (type_pf_data_expired(data
) || flag_exist
)
946 /* Just timeout value may be updated */
949 ret
= -IPSET_ERR_EXIST
;
952 } else if (j
== AHASH_MAX(h
) + 1 &&
953 type_pf_data_expired(data
))
956 if (j
!= AHASH_MAX(h
) + 1) {
957 data
= ahash_tdata(n
, j
);
958 #ifdef IP_SET_HASH_WITH_NETS
959 del_cidr(h
, CIDR(data
->cidr
), NETS_LENGTH(set
->family
));
960 add_cidr(h
, CIDR(d
->cidr
), NETS_LENGTH(set
->family
));
962 type_pf_data_copy(data
, d
);
963 type_pf_data_timeout_set(data
, timeout
);
964 #ifdef IP_SET_HASH_WITH_NETS
965 type_pf_data_flags(data
, cadt_flags
);
969 TUNE_AHASH_MAX(h
, multi
);
970 ret
= type_pf_elem_tadd(n
, d
, AHASH_MAX(h
), cadt_flags
, timeout
);
973 type_pf_data_next(h
, d
);
977 #ifdef IP_SET_HASH_WITH_NETS
978 add_cidr(h
, CIDR(d
->cidr
), NETS_LENGTH(set
->family
));
982 rcu_read_unlock_bh();
987 type_pf_tdel(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
989 struct ip_set_hash
*h
= set
->data
;
990 struct htable
*t
= h
->table
;
991 const struct type_pf_elem
*d
= value
;
994 struct type_pf_elem
*data
;
997 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
999 for (i
= 0; i
< n
->pos
; i
++) {
1000 data
= ahash_tdata(n
, i
);
1001 if (!type_pf_data_equal(data
, d
, &multi
))
1003 if (type_pf_data_expired(data
))
1004 return -IPSET_ERR_EXIST
;
1005 if (i
!= n
->pos
- 1)
1007 type_pf_data_copy(data
, ahash_tdata(n
, n
->pos
- 1));
1011 #ifdef IP_SET_HASH_WITH_NETS
1012 del_cidr(h
, CIDR(d
->cidr
), NETS_LENGTH(set
->family
));
1014 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
1015 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
1016 * sizeof(struct type_pf_telem
),
1020 n
->size
-= AHASH_INIT_SIZE
;
1021 memcpy(tmp
, n
->value
,
1022 n
->size
* sizeof(struct type_pf_telem
));
1029 return -IPSET_ERR_EXIST
;
1032 #ifdef IP_SET_HASH_WITH_NETS
1034 type_pf_ttest_cidrs(struct ip_set
*set
, struct type_pf_elem
*d
, u32 timeout
)
1036 struct ip_set_hash
*h
= set
->data
;
1037 struct htable
*t
= h
->table
;
1038 struct type_pf_elem
*data
;
1042 u8 nets_length
= NETS_LENGTH(set
->family
);
1044 for (; j
< nets_length
&& h
->nets
[j
].nets
&& !multi
; j
++) {
1045 type_pf_data_netmask(d
, h
->nets
[j
].cidr
);
1046 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
1047 n
= hbucket(t
, key
);
1048 for (i
= 0; i
< n
->pos
; i
++) {
1049 data
= ahash_tdata(n
, i
);
1050 #ifdef IP_SET_HASH_WITH_MULTI
1051 if (type_pf_data_equal(data
, d
, &multi
)) {
1052 if (!type_pf_data_expired(data
))
1053 return type_pf_data_match(data
);
1057 if (type_pf_data_equal(data
, d
, &multi
) &&
1058 !type_pf_data_expired(data
))
1059 return type_pf_data_match(data
);
1068 type_pf_ttest(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
1070 struct ip_set_hash
*h
= set
->data
;
1071 struct htable
*t
= h
->table
;
1072 struct type_pf_elem
*data
, *d
= value
;
1077 #ifdef IP_SET_HASH_WITH_NETS
1078 if (CIDR(d
->cidr
) == SET_HOST_MASK(set
->family
))
1079 return type_pf_ttest_cidrs(set
, d
, timeout
);
1081 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
1082 n
= hbucket(t
, key
);
1083 for (i
= 0; i
< n
->pos
; i
++) {
1084 data
= ahash_tdata(n
, i
);
1085 if (type_pf_data_equal(data
, d
, &multi
) &&
1086 !type_pf_data_expired(data
))
1087 return type_pf_data_match(data
);
1093 type_pf_tlist(const struct ip_set
*set
,
1094 struct sk_buff
*skb
, struct netlink_callback
*cb
)
1096 const struct ip_set_hash
*h
= set
->data
;
1097 const struct htable
*t
= h
->table
;
1098 struct nlattr
*atd
, *nested
;
1099 const struct hbucket
*n
;
1100 const struct type_pf_elem
*data
;
1101 u32 first
= cb
->args
[2];
1102 /* We assume that one hash bucket fills into one page */
1106 atd
= ipset_nest_start(skb
, IPSET_ATTR_ADT
);
1109 for (; cb
->args
[2] < jhash_size(t
->htable_bits
); cb
->args
[2]++) {
1110 incomplete
= skb_tail_pointer(skb
);
1111 n
= hbucket(t
, cb
->args
[2]);
1112 for (i
= 0; i
< n
->pos
; i
++) {
1113 data
= ahash_tdata(n
, i
);
1114 pr_debug("list %p %u\n", n
, i
);
1115 if (type_pf_data_expired(data
))
1117 pr_debug("do list %p %u\n", n
, i
);
1118 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
1120 if (cb
->args
[2] == first
) {
1121 nla_nest_cancel(skb
, atd
);
1124 goto nla_put_failure
;
1126 if (type_pf_data_tlist(skb
, data
))
1127 goto nla_put_failure
;
1128 ipset_nest_end(skb
, nested
);
1131 ipset_nest_end(skb
, atd
);
1132 /* Set listing finished */
1138 nlmsg_trim(skb
, incomplete
);
1139 ipset_nest_end(skb
, atd
);
1140 if (unlikely(first
== cb
->args
[2])) {
1141 pr_warning("Can't list set %s: one bucket does not fit into "
1142 "a message. Please report it!\n", set
->name
);
1149 static const struct ip_set_type_variant type_pf_tvariant
= {
1150 .kadt
= type_pf_kadt
,
1151 .uadt
= type_pf_uadt
,
1153 [IPSET_ADD
] = type_pf_tadd
,
1154 [IPSET_DEL
] = type_pf_tdel
,
1155 [IPSET_TEST
] = type_pf_ttest
,
1157 .destroy
= type_pf_destroy
,
1158 .flush
= type_pf_flush
,
1159 .head
= type_pf_head
,
1160 .list
= type_pf_tlist
,
1161 .resize
= type_pf_tresize
,
1162 .same_set
= type_pf_same_set
,
1166 type_pf_gc(unsigned long ul_set
)
1168 struct ip_set
*set
= (struct ip_set
*) ul_set
;
1169 struct ip_set_hash
*h
= set
->data
;
1171 pr_debug("called\n");
1172 write_lock_bh(&set
->lock
);
1173 type_pf_expire(h
, NETS_LENGTH(set
->family
));
1174 write_unlock_bh(&set
->lock
);
1176 h
->gc
.expires
= jiffies
+ IPSET_GC_PERIOD(h
->timeout
) * HZ
;
1181 type_pf_gc_init(struct ip_set
*set
)
1183 struct ip_set_hash
*h
= set
->data
;
1186 h
->gc
.data
= (unsigned long) set
;
1187 h
->gc
.function
= type_pf_gc
;
1188 h
->gc
.expires
= jiffies
+ IPSET_GC_PERIOD(h
->timeout
) * HZ
;
1190 pr_debug("gc initialized, run in every %u\n",
1191 IPSET_GC_PERIOD(h
->timeout
));
1196 #undef type_pf_data_equal
1197 #undef type_pf_data_isnull
1198 #undef type_pf_data_copy
1199 #undef type_pf_data_zero_out
1200 #undef type_pf_data_netmask
1201 #undef type_pf_data_list
1202 #undef type_pf_data_tlist
1203 #undef type_pf_data_next
1204 #undef type_pf_data_flags
1205 #undef type_pf_data_reset_flags
1206 #undef type_pf_data_match
1209 #undef type_pf_telem
1210 #undef type_pf_data_timeout
1211 #undef type_pf_data_expired
1212 #undef type_pf_data_timeout_set
1214 #undef type_pf_elem_add
1217 #undef type_pf_test_cidrs
1220 #undef type_pf_elem_tadd
1221 #undef type_pf_del_telem
1222 #undef type_pf_expire
1225 #undef type_pf_ttest_cidrs
1226 #undef type_pf_ttest
1228 #undef type_pf_resize
1229 #undef type_pf_tresize
1230 #undef type_pf_flush
1231 #undef type_pf_destroy
1234 #undef type_pf_tlist
1235 #undef type_pf_same_set
1239 #undef type_pf_gc_init
1240 #undef type_pf_variant
1241 #undef type_pf_tvariant