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 */
102 /* Compute htable_bits from the user input parameter hashsize */
104 htable_bits(u32 hashsize
)
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
);
115 #ifdef IP_SET_HASH_WITH_NETS
117 #define SET_HOST_MASK(family) (family == AF_INET ? 32 : 128)
119 /* Network cidr size book keeping when the hash stores different
122 add_cidr(struct ip_set_hash
*h
, u8 cidr
, u8 host_mask
)
126 ++h
->nets
[cidr
-1].nets
;
128 pr_debug("add_cidr added %u: %u\n", cidr
, h
->nets
[cidr
-1].nets
);
130 if (h
->nets
[cidr
-1].nets
> 1)
134 for (i
= 0; i
< host_mask
&& h
->nets
[i
].cidr
; i
++) {
135 /* Add in increasing prefix order, so larger cidr first */
136 if (h
->nets
[i
].cidr
< cidr
)
137 swap(h
->nets
[i
].cidr
, cidr
);
140 h
->nets
[i
].cidr
= cidr
;
144 del_cidr(struct ip_set_hash
*h
, u8 cidr
, u8 host_mask
)
148 --h
->nets
[cidr
-1].nets
;
150 pr_debug("del_cidr deleted %u: %u\n", cidr
, h
->nets
[cidr
-1].nets
);
152 if (h
->nets
[cidr
-1].nets
!= 0)
155 /* All entries with this cidr size deleted, so cleanup h->cidr[] */
156 for (i
= 0; i
< host_mask
- 1 && h
->nets
[i
].cidr
; i
++) {
157 if (h
->nets
[i
].cidr
== cidr
)
158 h
->nets
[i
].cidr
= cidr
= h
->nets
[i
+1].cidr
;
160 h
->nets
[i
- 1].cidr
= 0;
164 /* Destroy the hashtable part of the set */
166 ahash_destroy(struct htable
*t
)
171 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
174 /* FIXME: use slab cache */
181 /* Calculate the actual memory size of the set data */
183 ahash_memsize(const struct ip_set_hash
*h
, size_t dsize
, u8 host_mask
)
186 struct htable
*t
= h
->table
;
187 size_t memsize
= sizeof(*h
)
189 #ifdef IP_SET_HASH_WITH_NETS
190 + sizeof(struct ip_set_hash_nets
) * host_mask
192 + jhash_size(t
->htable_bits
) * sizeof(struct hbucket
);
194 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++)
195 memsize
+= t
->bucket
[i
].size
* dsize
;
200 /* Flush a hash type of set: destroy all elements */
202 ip_set_hash_flush(struct ip_set
*set
)
204 struct ip_set_hash
*h
= set
->data
;
205 struct htable
*t
= h
->table
;
209 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
212 n
->size
= n
->pos
= 0;
213 /* FIXME: use slab cache */
217 #ifdef IP_SET_HASH_WITH_NETS
218 memset(h
->nets
, 0, sizeof(struct ip_set_hash_nets
)
219 * SET_HOST_MASK(set
->family
));
224 /* Destroy a hash type of set */
226 ip_set_hash_destroy(struct ip_set
*set
)
228 struct ip_set_hash
*h
= set
->data
;
230 if (with_timeout(h
->timeout
))
231 del_timer_sync(&h
->gc
);
233 ahash_destroy(h
->table
);
234 #ifdef IP_SET_HASH_WITH_RBTREE
235 rbtree_destroy(&h
->rbtree
);
242 #endif /* _IP_SET_AHASH_H */
245 #define HKEY_DATALEN sizeof(struct type_pf_elem)
248 #define HKEY(data, initval, htable_bits) \
249 (jhash2((u32 *)(data), HKEY_DATALEN/sizeof(u32), initval) \
250 & jhash_mask(htable_bits))
252 #define CONCAT(a, b, c) a##b##c
253 #define TOKEN(a, b, c) CONCAT(a, b, c)
255 /* Type/family dependent function prototypes */
257 #define type_pf_data_equal TOKEN(TYPE, PF, _data_equal)
258 #define type_pf_data_isnull TOKEN(TYPE, PF, _data_isnull)
259 #define type_pf_data_copy TOKEN(TYPE, PF, _data_copy)
260 #define type_pf_data_zero_out TOKEN(TYPE, PF, _data_zero_out)
261 #define type_pf_data_netmask TOKEN(TYPE, PF, _data_netmask)
262 #define type_pf_data_list TOKEN(TYPE, PF, _data_list)
263 #define type_pf_data_tlist TOKEN(TYPE, PF, _data_tlist)
264 #define type_pf_data_next TOKEN(TYPE, PF, _data_next)
266 #define type_pf_elem TOKEN(TYPE, PF, _elem)
267 #define type_pf_telem TOKEN(TYPE, PF, _telem)
268 #define type_pf_data_timeout TOKEN(TYPE, PF, _data_timeout)
269 #define type_pf_data_expired TOKEN(TYPE, PF, _data_expired)
270 #define type_pf_data_timeout_set TOKEN(TYPE, PF, _data_timeout_set)
272 #define type_pf_elem_add TOKEN(TYPE, PF, _elem_add)
273 #define type_pf_add TOKEN(TYPE, PF, _add)
274 #define type_pf_del TOKEN(TYPE, PF, _del)
275 #define type_pf_test_cidrs TOKEN(TYPE, PF, _test_cidrs)
276 #define type_pf_test TOKEN(TYPE, PF, _test)
278 #define type_pf_elem_tadd TOKEN(TYPE, PF, _elem_tadd)
279 #define type_pf_del_telem TOKEN(TYPE, PF, _ahash_del_telem)
280 #define type_pf_expire TOKEN(TYPE, PF, _expire)
281 #define type_pf_tadd TOKEN(TYPE, PF, _tadd)
282 #define type_pf_tdel TOKEN(TYPE, PF, _tdel)
283 #define type_pf_ttest_cidrs TOKEN(TYPE, PF, _ahash_ttest_cidrs)
284 #define type_pf_ttest TOKEN(TYPE, PF, _ahash_ttest)
286 #define type_pf_resize TOKEN(TYPE, PF, _resize)
287 #define type_pf_tresize TOKEN(TYPE, PF, _tresize)
288 #define type_pf_flush ip_set_hash_flush
289 #define type_pf_destroy ip_set_hash_destroy
290 #define type_pf_head TOKEN(TYPE, PF, _head)
291 #define type_pf_list TOKEN(TYPE, PF, _list)
292 #define type_pf_tlist TOKEN(TYPE, PF, _tlist)
293 #define type_pf_same_set TOKEN(TYPE, PF, _same_set)
294 #define type_pf_kadt TOKEN(TYPE, PF, _kadt)
295 #define type_pf_uadt TOKEN(TYPE, PF, _uadt)
296 #define type_pf_gc TOKEN(TYPE, PF, _gc)
297 #define type_pf_gc_init TOKEN(TYPE, PF, _gc_init)
298 #define type_pf_variant TOKEN(TYPE, PF, _variant)
299 #define type_pf_tvariant TOKEN(TYPE, PF, _tvariant)
301 /* Flavour without timeout */
303 /* Get the ith element from the array block n */
304 #define ahash_data(n, i) \
305 ((struct type_pf_elem *)((n)->value) + (i))
307 /* Add an element to the hash table when resizing the set:
308 * we spare the maintenance of the internal counters. */
310 type_pf_elem_add(struct hbucket
*n
, const struct type_pf_elem
*value
,
313 if (n
->pos
>= n
->size
) {
316 if (n
->size
>= ahash_max
)
317 /* Trigger rehashing */
320 tmp
= kzalloc((n
->size
+ AHASH_INIT_SIZE
)
321 * sizeof(struct type_pf_elem
),
326 memcpy(tmp
, n
->value
,
327 sizeof(struct type_pf_elem
) * n
->size
);
331 n
->size
+= AHASH_INIT_SIZE
;
333 type_pf_data_copy(ahash_data(n
, n
->pos
++), value
);
337 /* Resize a hash: create a new hash table with doubling the hashsize
338 * and inserting the elements to it. Repeat until we succeed or
339 * fail due to memory pressures. */
341 type_pf_resize(struct ip_set
*set
, bool retried
)
343 struct ip_set_hash
*h
= set
->data
;
344 struct htable
*t
, *orig
= h
->table
;
345 u8 htable_bits
= orig
->htable_bits
;
346 const struct type_pf_elem
*data
;
347 struct hbucket
*n
, *m
;
354 pr_debug("attempt to resize set %s from %u to %u, t %p\n",
355 set
->name
, orig
->htable_bits
, htable_bits
, orig
);
357 /* In case we have plenty of memory :-) */
358 return -IPSET_ERR_HASH_FULL
;
359 t
= ip_set_alloc(sizeof(*t
)
360 + jhash_size(htable_bits
) * sizeof(struct hbucket
));
363 t
->htable_bits
= htable_bits
;
365 read_lock_bh(&set
->lock
);
366 for (i
= 0; i
< jhash_size(orig
->htable_bits
); i
++) {
367 n
= hbucket(orig
, i
);
368 for (j
= 0; j
< n
->pos
; j
++) {
369 data
= ahash_data(n
, j
);
370 m
= hbucket(t
, HKEY(data
, h
->initval
, htable_bits
));
371 ret
= type_pf_elem_add(m
, data
, AHASH_MAX(h
));
373 read_unlock_bh(&set
->lock
);
382 rcu_assign_pointer(h
->table
, t
);
383 read_unlock_bh(&set
->lock
);
385 /* Give time to other readers of the set */
386 synchronize_rcu_bh();
388 pr_debug("set %s resized from %u (%p) to %u (%p)\n", set
->name
,
389 orig
->htable_bits
, orig
, t
->htable_bits
, t
);
396 type_pf_data_next(struct ip_set_hash
*h
, const struct type_pf_elem
*d
);
398 /* Add an element to a hash and update the internal counters when succeeded,
399 * otherwise report the proper error code. */
401 type_pf_add(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
403 struct ip_set_hash
*h
= set
->data
;
405 const struct type_pf_elem
*d
= value
;
410 if (h
->elements
>= h
->maxelem
)
411 return -IPSET_ERR_HASH_FULL
;
414 t
= rcu_dereference_bh(h
->table
);
415 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
417 for (i
= 0; i
< n
->pos
; i
++)
418 if (type_pf_data_equal(ahash_data(n
, i
), d
, &multi
)) {
419 ret
= -IPSET_ERR_EXIST
;
422 TUNE_AHASH_MAX(h
, multi
);
423 ret
= type_pf_elem_add(n
, value
, AHASH_MAX(h
));
426 type_pf_data_next(h
, d
);
430 #ifdef IP_SET_HASH_WITH_NETS
431 add_cidr(h
, d
->cidr
, HOST_MASK
);
435 rcu_read_unlock_bh();
439 /* Delete an element from the hash: swap it with the last element
440 * and free up space if possible.
443 type_pf_del(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
445 struct ip_set_hash
*h
= set
->data
;
446 struct htable
*t
= h
->table
;
447 const struct type_pf_elem
*d
= value
;
450 struct type_pf_elem
*data
;
453 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
455 for (i
= 0; i
< n
->pos
; i
++) {
456 data
= ahash_data(n
, i
);
457 if (!type_pf_data_equal(data
, d
, &multi
))
461 type_pf_data_copy(data
, ahash_data(n
, n
->pos
- 1));
465 #ifdef IP_SET_HASH_WITH_NETS
466 del_cidr(h
, d
->cidr
, HOST_MASK
);
468 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
469 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
470 * sizeof(struct type_pf_elem
),
474 n
->size
-= AHASH_INIT_SIZE
;
475 memcpy(tmp
, n
->value
,
476 n
->size
* sizeof(struct type_pf_elem
));
483 return -IPSET_ERR_EXIST
;
486 #ifdef IP_SET_HASH_WITH_NETS
488 /* Special test function which takes into account the different network
489 * sizes added to the set */
491 type_pf_test_cidrs(struct ip_set
*set
, struct type_pf_elem
*d
, u32 timeout
)
493 struct ip_set_hash
*h
= set
->data
;
494 struct htable
*t
= h
->table
;
496 const struct type_pf_elem
*data
;
499 u8 host_mask
= SET_HOST_MASK(set
->family
);
501 pr_debug("test by nets\n");
502 for (; j
< host_mask
&& h
->nets
[j
].cidr
&& !multi
; j
++) {
503 type_pf_data_netmask(d
, h
->nets
[j
].cidr
);
504 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
506 for (i
= 0; i
< n
->pos
; i
++) {
507 data
= ahash_data(n
, i
);
508 if (type_pf_data_equal(data
, d
, &multi
))
516 /* Test whether the element is added to the set */
518 type_pf_test(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
520 struct ip_set_hash
*h
= set
->data
;
521 struct htable
*t
= h
->table
;
522 struct type_pf_elem
*d
= value
;
524 const struct type_pf_elem
*data
;
528 #ifdef IP_SET_HASH_WITH_NETS
529 /* If we test an IP address and not a network address,
530 * try all possible network sizes */
531 if (d
->cidr
== SET_HOST_MASK(set
->family
))
532 return type_pf_test_cidrs(set
, d
, timeout
);
535 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
537 for (i
= 0; i
< n
->pos
; i
++) {
538 data
= ahash_data(n
, i
);
539 if (type_pf_data_equal(data
, d
, &multi
))
545 /* Reply a HEADER request: fill out the header part of the set */
547 type_pf_head(struct ip_set
*set
, struct sk_buff
*skb
)
549 const struct ip_set_hash
*h
= set
->data
;
550 struct nlattr
*nested
;
553 read_lock_bh(&set
->lock
);
554 memsize
= ahash_memsize(h
, with_timeout(h
->timeout
)
555 ? sizeof(struct type_pf_telem
)
556 : sizeof(struct type_pf_elem
),
557 set
->family
== AF_INET
? 32 : 128);
558 read_unlock_bh(&set
->lock
);
560 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
562 goto nla_put_failure
;
563 NLA_PUT_NET32(skb
, IPSET_ATTR_HASHSIZE
,
564 htonl(jhash_size(h
->table
->htable_bits
)));
565 NLA_PUT_NET32(skb
, IPSET_ATTR_MAXELEM
, htonl(h
->maxelem
));
566 #ifdef IP_SET_HASH_WITH_NETMASK
567 if (h
->netmask
!= HOST_MASK
)
568 NLA_PUT_U8(skb
, IPSET_ATTR_NETMASK
, h
->netmask
);
570 NLA_PUT_NET32(skb
, IPSET_ATTR_REFERENCES
, htonl(set
->ref
- 1));
571 NLA_PUT_NET32(skb
, IPSET_ATTR_MEMSIZE
, htonl(memsize
));
572 if (with_timeout(h
->timeout
))
573 NLA_PUT_NET32(skb
, IPSET_ATTR_TIMEOUT
, htonl(h
->timeout
));
574 ipset_nest_end(skb
, nested
);
581 /* Reply a LIST/SAVE request: dump the elements of the specified set */
583 type_pf_list(const struct ip_set
*set
,
584 struct sk_buff
*skb
, struct netlink_callback
*cb
)
586 const struct ip_set_hash
*h
= set
->data
;
587 const struct htable
*t
= h
->table
;
588 struct nlattr
*atd
, *nested
;
589 const struct hbucket
*n
;
590 const struct type_pf_elem
*data
;
591 u32 first
= cb
->args
[2];
592 /* We assume that one hash bucket fills into one page */
596 atd
= ipset_nest_start(skb
, IPSET_ATTR_ADT
);
599 pr_debug("list hash set %s\n", set
->name
);
600 for (; cb
->args
[2] < jhash_size(t
->htable_bits
); cb
->args
[2]++) {
601 incomplete
= skb_tail_pointer(skb
);
602 n
= hbucket(t
, cb
->args
[2]);
603 pr_debug("cb->args[2]: %lu, t %p n %p\n", cb
->args
[2], t
, n
);
604 for (i
= 0; i
< n
->pos
; i
++) {
605 data
= ahash_data(n
, i
);
606 pr_debug("list hash %lu hbucket %p i %u, data %p\n",
607 cb
->args
[2], n
, i
, data
);
608 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
610 if (cb
->args
[2] == first
) {
611 nla_nest_cancel(skb
, atd
);
614 goto nla_put_failure
;
616 if (type_pf_data_list(skb
, data
))
617 goto nla_put_failure
;
618 ipset_nest_end(skb
, nested
);
621 ipset_nest_end(skb
, atd
);
622 /* Set listing finished */
628 nlmsg_trim(skb
, incomplete
);
629 ipset_nest_end(skb
, atd
);
630 if (unlikely(first
== cb
->args
[2])) {
631 pr_warning("Can't list set %s: one bucket does not fit into "
632 "a message. Please report it!\n", set
->name
);
640 type_pf_kadt(struct ip_set
*set
, const struct sk_buff
* skb
,
641 const struct xt_action_param
*par
,
642 enum ipset_adt adt
, const struct ip_set_adt_opt
*opt
);
644 type_pf_uadt(struct ip_set
*set
, struct nlattr
*tb
[],
645 enum ipset_adt adt
, u32
*lineno
, u32 flags
, bool retried
);
647 static const struct ip_set_type_variant type_pf_variant
= {
648 .kadt
= type_pf_kadt
,
649 .uadt
= type_pf_uadt
,
651 [IPSET_ADD
] = type_pf_add
,
652 [IPSET_DEL
] = type_pf_del
,
653 [IPSET_TEST
] = type_pf_test
,
655 .destroy
= type_pf_destroy
,
656 .flush
= type_pf_flush
,
657 .head
= type_pf_head
,
658 .list
= type_pf_list
,
659 .resize
= type_pf_resize
,
660 .same_set
= type_pf_same_set
,
663 /* Flavour with timeout support */
665 #define ahash_tdata(n, i) \
666 (struct type_pf_elem *)((struct type_pf_telem *)((n)->value) + (i))
669 type_pf_data_timeout(const struct type_pf_elem
*data
)
671 const struct type_pf_telem
*tdata
=
672 (const struct type_pf_telem
*) data
;
674 return tdata
->timeout
;
678 type_pf_data_expired(const struct type_pf_elem
*data
)
680 const struct type_pf_telem
*tdata
=
681 (const struct type_pf_telem
*) data
;
683 return ip_set_timeout_expired(tdata
->timeout
);
687 type_pf_data_timeout_set(struct type_pf_elem
*data
, u32 timeout
)
689 struct type_pf_telem
*tdata
= (struct type_pf_telem
*) data
;
691 tdata
->timeout
= ip_set_timeout_set(timeout
);
695 type_pf_elem_tadd(struct hbucket
*n
, const struct type_pf_elem
*value
,
696 u8 ahash_max
, u32 timeout
)
698 struct type_pf_elem
*data
;
700 if (n
->pos
>= n
->size
) {
703 if (n
->size
>= ahash_max
)
704 /* Trigger rehashing */
707 tmp
= kzalloc((n
->size
+ AHASH_INIT_SIZE
)
708 * sizeof(struct type_pf_telem
),
713 memcpy(tmp
, n
->value
,
714 sizeof(struct type_pf_telem
) * n
->size
);
718 n
->size
+= AHASH_INIT_SIZE
;
720 data
= ahash_tdata(n
, n
->pos
++);
721 type_pf_data_copy(data
, value
);
722 type_pf_data_timeout_set(data
, timeout
);
726 /* Delete expired elements from the hashtable */
728 type_pf_expire(struct ip_set_hash
*h
)
730 struct htable
*t
= h
->table
;
732 struct type_pf_elem
*data
;
736 for (i
= 0; i
< jhash_size(t
->htable_bits
); i
++) {
738 for (j
= 0; j
< n
->pos
; j
++) {
739 data
= ahash_tdata(n
, j
);
740 if (type_pf_data_expired(data
)) {
741 pr_debug("expired %u/%u\n", i
, j
);
742 #ifdef IP_SET_HASH_WITH_NETS
743 del_cidr(h
, data
->cidr
, HOST_MASK
);
747 type_pf_data_copy(data
,
748 ahash_tdata(n
, n
->pos
- 1));
753 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
754 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
755 * sizeof(struct type_pf_telem
),
758 /* Still try to delete expired elements */
760 n
->size
-= AHASH_INIT_SIZE
;
761 memcpy(tmp
, n
->value
,
762 n
->size
* sizeof(struct type_pf_telem
));
770 type_pf_tresize(struct ip_set
*set
, bool retried
)
772 struct ip_set_hash
*h
= set
->data
;
773 struct htable
*t
, *orig
= h
->table
;
774 u8 htable_bits
= orig
->htable_bits
;
775 const struct type_pf_elem
*data
;
776 struct hbucket
*n
, *m
;
780 /* Try to cleanup once */
783 write_lock_bh(&set
->lock
);
784 type_pf_expire(set
->data
);
785 write_unlock_bh(&set
->lock
);
794 /* In case we have plenty of memory :-) */
795 return -IPSET_ERR_HASH_FULL
;
796 t
= ip_set_alloc(sizeof(*t
)
797 + jhash_size(htable_bits
) * sizeof(struct hbucket
));
800 t
->htable_bits
= htable_bits
;
802 read_lock_bh(&set
->lock
);
803 for (i
= 0; i
< jhash_size(orig
->htable_bits
); i
++) {
804 n
= hbucket(orig
, i
);
805 for (j
= 0; j
< n
->pos
; j
++) {
806 data
= ahash_tdata(n
, j
);
807 m
= hbucket(t
, HKEY(data
, h
->initval
, htable_bits
));
808 ret
= type_pf_elem_tadd(m
, data
, AHASH_MAX(h
),
809 type_pf_data_timeout(data
));
811 read_unlock_bh(&set
->lock
);
820 rcu_assign_pointer(h
->table
, t
);
821 read_unlock_bh(&set
->lock
);
823 /* Give time to other readers of the set */
824 synchronize_rcu_bh();
832 type_pf_tadd(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
834 struct ip_set_hash
*h
= set
->data
;
835 struct htable
*t
= h
->table
;
836 const struct type_pf_elem
*d
= value
;
838 struct type_pf_elem
*data
;
839 int ret
= 0, i
, j
= AHASH_MAX(h
) + 1;
840 bool flag_exist
= flags
& IPSET_FLAG_EXIST
;
843 if (h
->elements
>= h
->maxelem
)
844 /* FIXME: when set is full, we slow down here */
846 if (h
->elements
>= h
->maxelem
)
847 return -IPSET_ERR_HASH_FULL
;
850 t
= rcu_dereference_bh(h
->table
);
851 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
853 for (i
= 0; i
< n
->pos
; i
++) {
854 data
= ahash_tdata(n
, i
);
855 if (type_pf_data_equal(data
, d
, &multi
)) {
856 if (type_pf_data_expired(data
) || flag_exist
)
859 ret
= -IPSET_ERR_EXIST
;
862 } else if (j
== AHASH_MAX(h
) + 1 &&
863 type_pf_data_expired(data
))
866 if (j
!= AHASH_MAX(h
) + 1) {
867 data
= ahash_tdata(n
, j
);
868 #ifdef IP_SET_HASH_WITH_NETS
869 del_cidr(h
, data
->cidr
, HOST_MASK
);
870 add_cidr(h
, d
->cidr
, HOST_MASK
);
872 type_pf_data_copy(data
, d
);
873 type_pf_data_timeout_set(data
, timeout
);
876 TUNE_AHASH_MAX(h
, multi
);
877 ret
= type_pf_elem_tadd(n
, d
, AHASH_MAX(h
), timeout
);
880 type_pf_data_next(h
, d
);
884 #ifdef IP_SET_HASH_WITH_NETS
885 add_cidr(h
, d
->cidr
, HOST_MASK
);
889 rcu_read_unlock_bh();
894 type_pf_tdel(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
896 struct ip_set_hash
*h
= set
->data
;
897 struct htable
*t
= h
->table
;
898 const struct type_pf_elem
*d
= value
;
901 struct type_pf_elem
*data
;
904 key
= HKEY(value
, h
->initval
, t
->htable_bits
);
906 for (i
= 0; i
< n
->pos
; i
++) {
907 data
= ahash_tdata(n
, i
);
908 if (!type_pf_data_equal(data
, d
, &multi
))
910 if (type_pf_data_expired(data
))
911 return -IPSET_ERR_EXIST
;
914 type_pf_data_copy(data
, ahash_tdata(n
, n
->pos
- 1));
918 #ifdef IP_SET_HASH_WITH_NETS
919 del_cidr(h
, d
->cidr
, HOST_MASK
);
921 if (n
->pos
+ AHASH_INIT_SIZE
< n
->size
) {
922 void *tmp
= kzalloc((n
->size
- AHASH_INIT_SIZE
)
923 * sizeof(struct type_pf_telem
),
927 n
->size
-= AHASH_INIT_SIZE
;
928 memcpy(tmp
, n
->value
,
929 n
->size
* sizeof(struct type_pf_telem
));
936 return -IPSET_ERR_EXIST
;
939 #ifdef IP_SET_HASH_WITH_NETS
941 type_pf_ttest_cidrs(struct ip_set
*set
, struct type_pf_elem
*d
, u32 timeout
)
943 struct ip_set_hash
*h
= set
->data
;
944 struct htable
*t
= h
->table
;
945 struct type_pf_elem
*data
;
949 u8 host_mask
= SET_HOST_MASK(set
->family
);
951 for (; j
< host_mask
&& h
->nets
[j
].cidr
&& !multi
; j
++) {
952 type_pf_data_netmask(d
, h
->nets
[j
].cidr
);
953 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
955 for (i
= 0; i
< n
->pos
; i
++) {
956 data
= ahash_tdata(n
, i
);
957 if (type_pf_data_equal(data
, d
, &multi
))
958 return !type_pf_data_expired(data
);
966 type_pf_ttest(struct ip_set
*set
, void *value
, u32 timeout
, u32 flags
)
968 struct ip_set_hash
*h
= set
->data
;
969 struct htable
*t
= h
->table
;
970 struct type_pf_elem
*data
, *d
= value
;
975 #ifdef IP_SET_HASH_WITH_NETS
976 if (d
->cidr
== SET_HOST_MASK(set
->family
))
977 return type_pf_ttest_cidrs(set
, d
, timeout
);
979 key
= HKEY(d
, h
->initval
, t
->htable_bits
);
981 for (i
= 0; i
< n
->pos
; i
++) {
982 data
= ahash_tdata(n
, i
);
983 if (type_pf_data_equal(data
, d
, &multi
))
984 return !type_pf_data_expired(data
);
990 type_pf_tlist(const struct ip_set
*set
,
991 struct sk_buff
*skb
, struct netlink_callback
*cb
)
993 const struct ip_set_hash
*h
= set
->data
;
994 const struct htable
*t
= h
->table
;
995 struct nlattr
*atd
, *nested
;
996 const struct hbucket
*n
;
997 const struct type_pf_elem
*data
;
998 u32 first
= cb
->args
[2];
999 /* We assume that one hash bucket fills into one page */
1003 atd
= ipset_nest_start(skb
, IPSET_ATTR_ADT
);
1006 for (; cb
->args
[2] < jhash_size(t
->htable_bits
); cb
->args
[2]++) {
1007 incomplete
= skb_tail_pointer(skb
);
1008 n
= hbucket(t
, cb
->args
[2]);
1009 for (i
= 0; i
< n
->pos
; i
++) {
1010 data
= ahash_tdata(n
, i
);
1011 pr_debug("list %p %u\n", n
, i
);
1012 if (type_pf_data_expired(data
))
1014 pr_debug("do list %p %u\n", n
, i
);
1015 nested
= ipset_nest_start(skb
, IPSET_ATTR_DATA
);
1017 if (cb
->args
[2] == first
) {
1018 nla_nest_cancel(skb
, atd
);
1021 goto nla_put_failure
;
1023 if (type_pf_data_tlist(skb
, data
))
1024 goto nla_put_failure
;
1025 ipset_nest_end(skb
, nested
);
1028 ipset_nest_end(skb
, atd
);
1029 /* Set listing finished */
1035 nlmsg_trim(skb
, incomplete
);
1036 ipset_nest_end(skb
, atd
);
1037 if (unlikely(first
== cb
->args
[2])) {
1038 pr_warning("Can't list set %s: one bucket does not fit into "
1039 "a message. Please report it!\n", set
->name
);
1046 static const struct ip_set_type_variant type_pf_tvariant
= {
1047 .kadt
= type_pf_kadt
,
1048 .uadt
= type_pf_uadt
,
1050 [IPSET_ADD
] = type_pf_tadd
,
1051 [IPSET_DEL
] = type_pf_tdel
,
1052 [IPSET_TEST
] = type_pf_ttest
,
1054 .destroy
= type_pf_destroy
,
1055 .flush
= type_pf_flush
,
1056 .head
= type_pf_head
,
1057 .list
= type_pf_tlist
,
1058 .resize
= type_pf_tresize
,
1059 .same_set
= type_pf_same_set
,
1063 type_pf_gc(unsigned long ul_set
)
1065 struct ip_set
*set
= (struct ip_set
*) ul_set
;
1066 struct ip_set_hash
*h
= set
->data
;
1068 pr_debug("called\n");
1069 write_lock_bh(&set
->lock
);
1071 write_unlock_bh(&set
->lock
);
1073 h
->gc
.expires
= jiffies
+ IPSET_GC_PERIOD(h
->timeout
) * HZ
;
1078 type_pf_gc_init(struct ip_set
*set
)
1080 struct ip_set_hash
*h
= set
->data
;
1083 h
->gc
.data
= (unsigned long) set
;
1084 h
->gc
.function
= type_pf_gc
;
1085 h
->gc
.expires
= jiffies
+ IPSET_GC_PERIOD(h
->timeout
) * HZ
;
1087 pr_debug("gc initialized, run in every %u\n",
1088 IPSET_GC_PERIOD(h
->timeout
));
1093 #undef type_pf_data_equal
1094 #undef type_pf_data_isnull
1095 #undef type_pf_data_copy
1096 #undef type_pf_data_zero_out
1097 #undef type_pf_data_list
1098 #undef type_pf_data_tlist
1101 #undef type_pf_telem
1102 #undef type_pf_data_timeout
1103 #undef type_pf_data_expired
1104 #undef type_pf_data_netmask
1105 #undef type_pf_data_timeout_set
1107 #undef type_pf_elem_add
1110 #undef type_pf_test_cidrs
1113 #undef type_pf_elem_tadd
1114 #undef type_pf_expire
1117 #undef type_pf_ttest_cidrs
1118 #undef type_pf_ttest
1120 #undef type_pf_resize
1121 #undef type_pf_tresize
1122 #undef type_pf_flush
1123 #undef type_pf_destroy
1126 #undef type_pf_tlist
1127 #undef type_pf_same_set
1131 #undef type_pf_gc_init
1132 #undef type_pf_variant
1133 #undef type_pf_tvariant