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