1 /* Copyright (C) 2005 Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>
3 * This program is free software; you can redistribute it and/or modify
4 * it under the terms of the GNU General Public License version 2 as
5 * published by the Free Software Foundation.
8 /* Kernel module implementing an IP set type: the iptree type */
10 #include <linux/module.h>
12 #include <linux/skbuff.h>
13 #include <linux/slab.h>
14 #include <linux/delay.h>
15 #include <linux/netfilter_ipv4/ip_tables.h>
16 #include <linux/netfilter_ipv4/ip_set.h>
17 #include <linux/errno.h>
18 #include <asm/uaccess.h>
19 #include <asm/bitops.h>
20 #include <linux/spinlock.h>
22 /* Backward compatibility */
27 #include <linux/netfilter_ipv4/ip_set_iptree.h>
29 /* Garbage collection interval in seconds: */
30 #define IPTREE_GC_TIME 5*60
31 /* Sleep so many milliseconds before trying again
32 * to delete the gc timer at destroying/flushing a set */
33 #define IPTREE_DESTROY_SLEEP 100
35 static kmem_cache_t *branch_cachep;
36 static kmem_cache_t *leaf_cachep;
38 #define ABCD(a,b,c,d,addrp) do { \
39 a = ((unsigned char *)addrp)[3]; \
40 b = ((unsigned char *)addrp)[2]; \
41 c = ((unsigned char *)addrp)[1]; \
42 d = ((unsigned char *)addrp)[0]; \
45 #define TESTIP_WALK(map, elem, branch) do { \
46 if ((map)->tree[elem]) { \
47 branch = (map)->tree[elem]; \
53 __testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
55 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
56 struct ip_set_iptreeb *btree;
57 struct ip_set_iptreec *ctree;
58 struct ip_set_iptreed *dtree;
59 unsigned char a,b,c,d;
62 ABCD(a, b, c, d, hash_ip);
63 DP("%u %u %u %u timeout %u", a, b, c, d, map->timeout);
64 TESTIP_WALK(map, a, btree);
65 TESTIP_WALK(btree, b, ctree);
66 TESTIP_WALK(ctree, c, dtree);
67 DP("%lu %lu", dtree->expires[d], jiffies);
68 return !!(map->timeout ? (time_after(dtree->expires[d], jiffies))
73 testip(struct ip_set *set, const void *data, size_t size,
76 struct ip_set_req_iptree *req =
77 (struct ip_set_req_iptree *) data;
79 if (size != sizeof(struct ip_set_req_iptree)) {
80 ip_set_printk("data length wrong (want %zu, have %zu)",
81 sizeof(struct ip_set_req_iptree),
85 return __testip(set, req->ip, hash_ip);
89 testip_kernel(struct ip_set *set,
90 const struct sk_buff *skb,
92 const u_int32_t *flags,
97 DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
98 flags[index] & IPSET_SRC ? "SRC" : "DST",
99 NIPQUAD(skb->nh.iph->saddr),
100 NIPQUAD(skb->nh.iph->daddr));
103 ntohl(flags[index] & IPSET_SRC
105 : skb->nh.iph->daddr),
107 return (res < 0 ? 0 : res);
110 #define ADDIP_WALK(map, elem, branch, type, cachep, flags) do { \
111 if ((map)->tree[elem]) { \
112 DP("found %u", elem); \
113 branch = (map)->tree[elem]; \
116 kmem_cache_alloc(cachep, flags); \
117 if (branch == NULL) \
119 memset(branch, 0, sizeof(*branch)); \
120 (map)->tree[elem] = branch; \
121 DP("alloc %u", elem); \
126 __addip(struct ip_set *set, ip_set_ip_t ip, unsigned int timeout,
127 ip_set_ip_t *hash_ip,
128 unsigned int __nocast flags)
130 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
131 struct ip_set_iptreeb *btree;
132 struct ip_set_iptreec *ctree;
133 struct ip_set_iptreed *dtree;
134 unsigned char a,b,c,d;
138 ABCD(a, b, c, d, hash_ip);
139 DP("%u %u %u %u timeout %u", a, b, c, d, timeout);
140 ADDIP_WALK(map, a, btree, struct ip_set_iptreeb, branch_cachep, flags);
141 ADDIP_WALK(btree, b, ctree, struct ip_set_iptreec, branch_cachep, flags);
142 ADDIP_WALK(ctree, c, dtree, struct ip_set_iptreed, leaf_cachep, flags);
143 if (dtree->expires[d]
144 && (!map->timeout || time_after(dtree->expires[d], jiffies)))
146 dtree->expires[d] = map->timeout ? (timeout * HZ + jiffies) : 1;
148 if (dtree->expires[d] == 0)
149 dtree->expires[d] = 1;
150 DP("%u %lu", d, dtree->expires[d]);
155 addip(struct ip_set *set, const void *data, size_t size,
156 ip_set_ip_t *hash_ip)
158 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
159 struct ip_set_req_iptree *req =
160 (struct ip_set_req_iptree *) data;
162 if (size != sizeof(struct ip_set_req_iptree)) {
163 ip_set_printk("data length wrong (want %zu, have %zu)",
164 sizeof(struct ip_set_req_iptree),
168 DP("%u.%u.%u.%u %u", HIPQUAD(req->ip), req->timeout);
169 return __addip(set, req->ip,
170 req->timeout ? req->timeout : map->timeout,
176 addip_kernel(struct ip_set *set,
177 const struct sk_buff *skb,
178 ip_set_ip_t *hash_ip,
179 const u_int32_t *flags,
182 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
185 ntohl(flags[index] & IPSET_SRC
187 : skb->nh.iph->daddr),
193 #define DELIP_WALK(map, elem, branch) do { \
194 if ((map)->tree[elem]) { \
195 branch = (map)->tree[elem]; \
201 __delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
203 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
204 struct ip_set_iptreeb *btree;
205 struct ip_set_iptreec *ctree;
206 struct ip_set_iptreed *dtree;
207 unsigned char a,b,c,d;
210 ABCD(a, b, c, d, hash_ip);
211 DELIP_WALK(map, a, btree);
212 DELIP_WALK(btree, b, ctree);
213 DELIP_WALK(ctree, c, dtree);
215 if (dtree->expires[d]) {
216 dtree->expires[d] = 0;
223 delip(struct ip_set *set, const void *data, size_t size,
224 ip_set_ip_t *hash_ip)
226 struct ip_set_req_iptree *req =
227 (struct ip_set_req_iptree *) data;
229 if (size != sizeof(struct ip_set_req_iptree)) {
230 ip_set_printk("data length wrong (want %zu, have %zu)",
231 sizeof(struct ip_set_req_iptree),
235 return __delip(set, req->ip, hash_ip);
239 delip_kernel(struct ip_set *set,
240 const struct sk_buff *skb,
241 ip_set_ip_t *hash_ip,
242 const u_int32_t *flags,
246 ntohl(flags[index] & IPSET_SRC
248 : skb->nh.iph->daddr),
252 #define LOOP_WALK_BEGIN(map, i, branch) \
253 for (i = 0; i < 256; i++) { \
254 if (!(map)->tree[i]) \
256 branch = (map)->tree[i]
258 #define LOOP_WALK_END }
260 static void ip_tree_gc(unsigned long ul_set)
262 struct ip_set *set = (void *) ul_set;
263 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
264 struct ip_set_iptreeb *btree;
265 struct ip_set_iptreec *ctree;
266 struct ip_set_iptreed *dtree;
267 unsigned int a,b,c,d;
271 DP("gc: %s", set->name);
272 write_lock_bh(&set->lock);
273 LOOP_WALK_BEGIN(map, a, btree);
274 LOOP_WALK_BEGIN(btree, b, ctree);
275 LOOP_WALK_BEGIN(ctree, c, dtree);
276 for (d = 0; d < 256; d++) {
277 if (dtree->expires[d]) {
278 DP("gc: %u %u %u %u: expires %lu jiffies %lu",
280 dtree->expires[d], jiffies);
282 && time_before(dtree->expires[d], jiffies))
283 dtree->expires[d] = 0;
289 DP("gc: %s: leaf %u %u %u empty",
291 kmem_cache_free(leaf_cachep, dtree);
292 ctree->tree[c] = NULL;
294 DP("gc: %s: leaf %u %u %u not empty",
301 DP("gc: %s: branch %u %u empty",
303 kmem_cache_free(branch_cachep, ctree);
304 btree->tree[b] = NULL;
306 DP("gc: %s: branch %u %u not empty",
313 DP("gc: %s: branch %u empty",
315 kmem_cache_free(branch_cachep, btree);
318 DP("gc: %s: branch %u not empty",
323 write_unlock_bh(&set->lock);
325 map->gc.expires = jiffies + map->gc_interval * HZ;
329 static inline void init_gc_timer(struct ip_set *set)
331 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
333 /* Even if there is no timeout for the entries,
334 * we still have to call gc because delete
335 * do not clean up empty branches */
336 map->gc_interval = IPTREE_GC_TIME;
337 init_timer(&map->gc);
338 map->gc.data = (unsigned long) set;
339 map->gc.function = ip_tree_gc;
340 map->gc.expires = jiffies + map->gc_interval * HZ;
344 static int create(struct ip_set *set, const void *data, size_t size)
346 struct ip_set_req_iptree_create *req =
347 (struct ip_set_req_iptree_create *) data;
348 struct ip_set_iptree *map;
350 if (size != sizeof(struct ip_set_req_iptree_create)) {
351 ip_set_printk("data length wrong (want %zu, have %zu)",
352 sizeof(struct ip_set_req_iptree_create),
357 map = kmalloc(sizeof(struct ip_set_iptree), GFP_KERNEL);
359 DP("out of memory for %d bytes",
360 sizeof(struct ip_set_iptree));
363 memset(map, 0, sizeof(*map));
364 map->timeout = req->timeout;
372 static void __flush(struct ip_set_iptree *map)
374 struct ip_set_iptreeb *btree;
375 struct ip_set_iptreec *ctree;
376 struct ip_set_iptreed *dtree;
379 LOOP_WALK_BEGIN(map, a, btree);
380 LOOP_WALK_BEGIN(btree, b, ctree);
381 LOOP_WALK_BEGIN(ctree, c, dtree);
382 kmem_cache_free(leaf_cachep, dtree);
384 kmem_cache_free(branch_cachep, ctree);
386 kmem_cache_free(branch_cachep, btree);
390 static void destroy(struct ip_set *set)
392 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
394 /* gc might be running */
395 while (!del_timer(&map->gc))
396 msleep(IPTREE_DESTROY_SLEEP);
402 static void flush(struct ip_set *set)
404 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
405 unsigned int timeout = map->timeout;
407 /* gc might be running */
408 while (!del_timer(&map->gc))
409 msleep(IPTREE_DESTROY_SLEEP);
411 memset(map, 0, sizeof(*map));
412 map->timeout = timeout;
417 static void list_header(const struct ip_set *set, void *data)
419 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
420 struct ip_set_req_iptree_create *header =
421 (struct ip_set_req_iptree_create *) data;
423 header->timeout = map->timeout;
426 static int list_members_size(const struct ip_set *set)
428 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
429 struct ip_set_iptreeb *btree;
430 struct ip_set_iptreec *ctree;
431 struct ip_set_iptreed *dtree;
432 unsigned int a,b,c,d;
433 unsigned int count = 0;
435 LOOP_WALK_BEGIN(map, a, btree);
436 LOOP_WALK_BEGIN(btree, b, ctree);
437 LOOP_WALK_BEGIN(ctree, c, dtree);
438 for (d = 0; d < 256; d++) {
439 if (dtree->expires[d]
440 && (!map->timeout || time_after(dtree->expires[d], jiffies)))
447 DP("members %u", count);
448 return (count * sizeof(struct ip_set_req_iptree));
451 static void list_members(const struct ip_set *set, void *data)
453 struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
454 struct ip_set_iptreeb *btree;
455 struct ip_set_iptreec *ctree;
456 struct ip_set_iptreed *dtree;
457 unsigned int a,b,c,d;
459 struct ip_set_req_iptree *entry;
461 LOOP_WALK_BEGIN(map, a, btree);
462 LOOP_WALK_BEGIN(btree, b, ctree);
463 LOOP_WALK_BEGIN(ctree, c, dtree);
464 for (d = 0; d < 256; d++) {
465 if (dtree->expires[d]
466 && (!map->timeout || time_after(dtree->expires[d], jiffies))) {
467 entry = (struct ip_set_req_iptree *)(data + offset);
468 entry->ip = ((a << 24) | (b << 16) | (c << 8) | d);
469 entry->timeout = !map->timeout ? 0
470 : (dtree->expires[d] - jiffies)/HZ;
471 offset += sizeof(struct ip_set_req_iptree);
479 static struct ip_set_type ip_set_iptree = {
480 .typename = SETTYPE_NAME,
481 .features = IPSET_TYPE_IP | IPSET_DATA_SINGLE,
482 .protocol_version = IP_SET_PROTOCOL_VERSION,
486 .reqsize = sizeof(struct ip_set_req_iptree),
488 .addip_kernel = &addip_kernel,
490 .delip_kernel = &delip_kernel,
492 .testip_kernel = &testip_kernel,
493 .header_size = sizeof(struct ip_set_req_iptree_create),
494 .list_header = &list_header,
495 .list_members_size = &list_members_size,
496 .list_members = &list_members,
500 MODULE_LICENSE("GPL");
501 MODULE_AUTHOR("Jozsef Kadlecsik <kadlec@blackhole.kfki.hu>");
502 MODULE_DESCRIPTION("iptree type of IP sets");
504 static int __init init(void)
508 branch_cachep = kmem_cache_create("ip_set_iptreeb",
509 sizeof(struct ip_set_iptreeb),
511 if (!branch_cachep) {
512 printk(KERN_ERR "Unable to create ip_set_iptreeb slab cache\n");
516 leaf_cachep = kmem_cache_create("ip_set_iptreed",
517 sizeof(struct ip_set_iptreed),
520 printk(KERN_ERR "Unable to create ip_set_iptreed slab cache\n");
524 ret = ip_set_register_set_type(&ip_set_iptree);
528 kmem_cache_destroy(leaf_cachep);
530 kmem_cache_destroy(branch_cachep);
535 static void __exit fini(void)
537 /* FIXME: possible race with ip_set_create() */
538 ip_set_unregister_set_type(&ip_set_iptree);
539 kmem_cache_destroy(leaf_cachep);
540 kmem_cache_destroy(branch_cachep);