[netfilter-cvslog] r3853 - in trunk/patch-o-matic-ng/set: .
linux/Documentation linux/include/linux/netfilter_ipv4
linux/net/ipv4/netfilter linux-2.6/include/linux/netfilter_ipv4
linux-2.6/net/ipv4/netfilter
kadlec at netfilter.org
kadlec at netfilter.org
Mon Apr 11 09:48:39 CEST 2005
Author: kadlec at netfilter.org
Date: 2005-04-11 09:48:39 +0200 (Mon, 11 Apr 2005)
New Revision: 3853
Added:
trunk/patch-o-matic-ng/set/linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h
trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/ip_set_iptree.c
trunk/patch-o-matic-ng/set/linux/include/linux/netfilter_ipv4/ip_set_iptree.h
trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/ip_set_iptree.c
Modified:
trunk/patch-o-matic-ng/set/help
trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Kconfig.ladd
trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Makefile.ladd_2
trunk/patch-o-matic-ng/set/linux/Documentation/Configure.help.ladd
trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Config.in.ladd
trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Makefile.ladd
Log:
iptree set type added
Modified: trunk/patch-o-matic-ng/set/help
===================================================================
--- trunk/patch-o-matic-ng/set/help 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/help 2005-04-11 07:48:39 UTC (rev 3853)
@@ -3,7 +3,7 @@
address/network address/port has its bit set in/added to the given set.
It also provides a SET target, which can be used to add or remove the
addresses/ports of a packet to/from a set. The currently supported types
-of the sets are: ipmap, macipmap, portmap and iphash. It is possible
-to chain sets together by binding.
+of the sets are: ipmap, macipmap, portmap, iphash, nethash and iptree.
+It is possible to chain sets together by binding.
The userspace program ipset(8) is required to define and setup IP sets.
Modified: trunk/patch-o-matic-ng/set/linux/Documentation/Configure.help.ladd
===================================================================
--- trunk/patch-o-matic-ng/set/linux/Documentation/Configure.help.ladd 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux/Documentation/Configure.help.ladd 2005-04-11 07:48:39 UTC (rev 3853)
@@ -61,3 +61,10 @@
If you want to compile it as a module, say M here and read
<file:Documentation/modules.txt>. If unsure, say `N'.
+iptree set type support
+CONFIG_IP_NF_SET_IPTREE
+ This option adds the iptree set type support.
+
+ If you want to compile it as a module, say M here and read
+ <file:Documentation/modules.txt>. If unsure, say `N'.
+
Added: trunk/patch-o-matic-ng/set/linux/include/linux/netfilter_ipv4/ip_set_iptree.h
===================================================================
--- trunk/patch-o-matic-ng/set/linux/include/linux/netfilter_ipv4/ip_set_iptree.h 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux/include/linux/netfilter_ipv4/ip_set_iptree.h 2005-04-11 07:48:39 UTC (rev 3853)
@@ -0,0 +1,39 @@
+#ifndef __IP_SET_IPTREE_H
+#define __IP_SET_IPTREE_H
+
+#include <linux/netfilter_ipv4/ip_set.h>
+
+#define SETTYPE_NAME "iptree"
+#define MAX_RANGE 0x0000FFFF
+
+struct ip_set_iptreed {
+ unsigned long expires[255]; /* x.x.x.ADDR */
+};
+
+struct ip_set_iptreec {
+ struct ip_set_iptreed *tree[255]; /* x.x.ADDR.* */
+};
+
+struct ip_set_iptreeb {
+ struct ip_set_iptreec *tree[255]; /* x.ADDR.*.* */
+};
+
+struct ip_set_iptree {
+ unsigned int timeout;
+ unsigned int gc_interval;
+#ifdef __KERNEL__
+ struct timer_list gc;
+ struct ip_set_iptreeb *tree[255]; /* ADDR.*.*.* */
+#endif
+};
+
+struct ip_set_req_iptree_create {
+ unsigned int timeout;
+};
+
+struct ip_set_req_iptree {
+ ip_set_ip_t ip;
+ unsigned int timeout;
+};
+
+#endif /* __IP_SET_IPTREE_H */
Modified: trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Config.in.ladd
===================================================================
--- trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Config.in.ladd 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Config.in.ladd 2005-04-11 07:48:39 UTC (rev 3853)
@@ -11,4 +11,5 @@
dep_tristate ' macipmap set type support' CONFIG_IP_NF_SET_MACIPMAP $CONFIG_IP_NF_SET
dep_tristate ' iphash set type support' CONFIG_IP_NF_SET_IPHASH $CONFIG_IP_NF_SET
dep_tristate ' nethash set type support' CONFIG_IP_NF_SET_NETHASH $CONFIG_IP_NF_SET
+ dep_tristate ' iptree set type support' CONFIG_IP_NF_SET_IPTREE $CONFIG_IP_NF_SET
fi
Modified: trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Makefile.ladd
===================================================================
--- trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Makefile.ladd 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/Makefile.ladd 2005-04-11 07:48:39 UTC (rev 3853)
@@ -10,3 +10,4 @@
obj-$(CONFIG_IP_NF_SET_MACIPMAP) += ip_set_macipmap.o
obj-$(CONFIG_IP_NF_SET_IPHASH) += ip_set_iphash.o
obj-$(CONFIG_IP_NF_SET_NETHASH) += ip_set_nethash.o
+obj-$(CONFIG_IP_NF_SET_IPTREE) += ip_set_iptree.o
Added: trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/ip_set_iptree.c
===================================================================
--- trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/ip_set_iptree.c 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux/net/ipv4/netfilter/ip_set_iptree.c 2005-04-11 07:48:39 UTC (rev 3853)
@@ -0,0 +1,509 @@
+/* Copyright (C) 2005 Jozsef Kadlecsik <kadlec at blackhole.kfki.hu>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+/* Kernel module implementing an IP set type: the iptree type */
+
+#include <linux/module.h>
+#include <linux/ip.h>
+#include <linux/skbuff.h>
+#include <linux/slab.h>
+#include <linux/delay.h>
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ip_set.h>
+#include <linux/errno.h>
+#include <asm/uaccess.h>
+#include <asm/bitops.h>
+#include <linux/spinlock.h>
+
+#include <linux/netfilter_ipv4/ip_set_iptree.h>
+
+/* Garbage collection interval in seconds: */
+#define IPTREE_GC_TIME 5*60
+/* Sleep so many milliseconds before trying again
+ * to delete the gc timer at destroying a set */
+#define IPTREE_DESTROY_SLEEP 100
+
+static kmem_cache_t *branch_cachep;
+static kmem_cache_t *leaf_cachep;
+
+#define ABCD(a,b,c,d,addrp) do { \
+ a = ((unsigned char *)addrp)[3]; \
+ b = ((unsigned char *)addrp)[2]; \
+ c = ((unsigned char *)addrp)[1]; \
+ d = ((unsigned char *)addrp)[0]; \
+} while (0)
+
+#define TESTIP_WALK(map, elem, branch) do { \
+ if ((map)->tree[elem]) { \
+ branch = (map)->tree[elem]; \
+ } else \
+ return 0; \
+} while (0)
+
+static inline int
+__testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DP("%u %u %u %u timeout %u", a, b, c, d, map->timeout);
+ TESTIP_WALK(map, a, btree);
+ TESTIP_WALK(btree, b, ctree);
+ TESTIP_WALK(ctree, c, dtree);
+ DP("%lu %lu", dtree->expires[d], jiffies);
+ return !!(map->timeout ? (dtree->expires[d] > jiffies)
+ : dtree->expires[d]);
+}
+
+static int
+testip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ return __testip(set, req->ip, hash_ip);
+}
+
+static int
+testip_kernel(struct ip_set *set,
+ const struct sk_buff *skb,
+ u_int32_t flags,
+ ip_set_ip_t *hash_ip)
+{
+ int res;
+
+ DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
+ flags & IPSET_SRC ? "SRC" : "DST",
+ NIPQUAD(skb->nh.iph->saddr),
+ NIPQUAD(skb->nh.iph->daddr));
+
+ res = __testip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ hash_ip);
+ return (res < 0 ? 0 : res);
+}
+
+#define ADDIP_WALK(map, elem, branch, type, cachep) do { \
+ if ((map)->tree[elem]) { \
+ DP("found %u", elem); \
+ branch = (map)->tree[elem]; \
+ } else { \
+ branch = (type *) \
+ kmem_cache_alloc(cachep, GFP_KERNEL); \
+ if (branch == NULL) \
+ return -ENOMEM; \
+ memset(branch, 0, sizeof(*branch)); \
+ (map)->tree[elem] = branch; \
+ DP("alloc %u", elem); \
+ } \
+} while (0)
+
+static inline int
+__addip(struct ip_set *set, ip_set_ip_t ip, unsigned int timeout,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DP("%u %u %u %u timeout %u", a, b, c, d, timeout);
+ ADDIP_WALK(map, a, btree, struct ip_set_iptreeb, branch_cachep);
+ ADDIP_WALK(btree, b, ctree, struct ip_set_iptreec, branch_cachep);
+ ADDIP_WALK(ctree, c, dtree, struct ip_set_iptreed, leaf_cachep);
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies))
+ return -EEXIST;
+ dtree->expires[d] = map->timeout ? (timeout * HZ + jiffies) : 1;
+ DP("%u %lu", d, dtree->expires[d]);
+ return 0;
+}
+
+static int
+addip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ DP("%u.%u.%u.%u %u", HIPQUAD(req->ip), req->timeout);
+ return __addip(set, req->ip,
+ req->timeout ? req->timeout : map->timeout,
+ hash_ip);
+}
+
+static int
+addip_kernel(struct ip_set *set, const struct sk_buff *skb,
+ u_int32_t flags, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+
+ return __addip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ map->timeout,
+ hash_ip);
+}
+
+#define DELIP_WALK(map, elem, branch) do { \
+ if ((map)->tree[elem]) { \
+ branch = (map)->tree[elem]; \
+ } else \
+ return -EEXIST; \
+} while (0)
+
+static inline int
+__delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DELIP_WALK(map, a, btree);
+ DELIP_WALK(btree, b, ctree);
+ DELIP_WALK(ctree, c, dtree);
+
+ if (dtree->expires[d]) {
+ dtree->expires[d] = 0;
+ return 0;
+ }
+ return -EEXIST;
+}
+
+static int
+delip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ return __delip(set, req->ip, hash_ip);
+}
+
+static int
+delip_kernel(struct ip_set *set, const struct sk_buff *skb,
+ u_int32_t flags, ip_set_ip_t *hash_ip)
+{
+ return __delip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ hash_ip);
+}
+
+#define LOOP_WALK_BEGIN(map, i, branch) \
+ for (i = 0; i < 255; i++) { \
+ if (!(map)->tree[i]) \
+ continue; \
+ branch = (map)->tree[i]
+
+#define LOOP_WALK_END }
+
+static void ip_tree_gc(unsigned long ul_set)
+{
+ struct ip_set *set = (void *) ul_set;
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ unsigned char i,j,k;
+
+ i = j = k = 0;
+ DP("gc: %s", set->name);
+ write_lock_bh(&set->lock);
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]) {
+ DP("gc: %u %u %u %u: expires %lu jiffies %lu",
+ a, b, c, d,
+ dtree->expires[d], jiffies);
+ if (map->timeout
+ && time_before(dtree->expires[d], jiffies))
+ dtree->expires[d] = 0;
+ else
+ k = 1;
+ }
+ }
+ if (k == 0) {
+ DP("gc: %s: leaf %u %u %u empty",
+ set->name, a, b, c);
+ kmem_cache_free(leaf_cachep, dtree);
+ ctree->tree[c] = NULL;
+ } else {
+ DP("gc: %s: leaf %u %u %u not empty",
+ set->name, a, b, c);
+ j = 1;
+ k = 0;
+ }
+ LOOP_WALK_END;
+ if (j == 0) {
+ DP("gc: %s: branch %u %u empty",
+ set->name, a, b);
+ kmem_cache_free(branch_cachep, ctree);
+ btree->tree[b] = NULL;
+ } else {
+ DP("gc: %s: branch %u %u not empty",
+ set->name, a, b);
+ i = 1;
+ j = k = 0;
+ }
+ LOOP_WALK_END;
+ if (i == 0) {
+ DP("gc: %s: branch %u empty",
+ set->name, a);
+ kmem_cache_free(branch_cachep, btree);
+ map->tree[a] = NULL;
+ } else {
+ DP("gc: %s: branch %u not empty",
+ set->name, a);
+ i = j = k = 0;
+ }
+ LOOP_WALK_END;
+ write_unlock_bh(&set->lock);
+
+ map->gc.expires = jiffies + map->gc_interval * HZ;
+ add_timer(&map->gc);
+}
+
+static int create(struct ip_set *set, const void *data, size_t size)
+{
+ struct ip_set_req_iptree_create *req =
+ (struct ip_set_req_iptree_create *) data;
+ struct ip_set_iptree *map;
+
+ if (size != sizeof(struct ip_set_req_iptree_create)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree_create),
+ size);
+ return -EINVAL;
+ }
+
+ map = kmalloc(sizeof(struct ip_set_iptree), GFP_KERNEL);
+ if (!map) {
+ DP("out of memory for %d bytes",
+ sizeof(struct ip_set_iptree));
+ return -ENOMEM;
+ }
+ memset(map, 0, sizeof(*map));
+ map->timeout = req->timeout;
+ set->data = map;
+
+ /* If there is no timeout for the entries,
+ * we still have to call gc because delete
+ * do not clean up empty branches */
+ map->gc_interval = IPTREE_GC_TIME;
+ init_timer(&map->gc);
+ map->gc.data = (unsigned long) set;
+ map->gc.function = ip_tree_gc;
+ map->gc.expires = jiffies + map->gc_interval * HZ;
+ add_timer(&map->gc);
+
+ return 0;
+}
+
+static void __flush(struct ip_set_iptree *map)
+{
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned int a,b,c;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ kmem_cache_free(leaf_cachep, dtree);
+ LOOP_WALK_END;
+ kmem_cache_free(branch_cachep, ctree);
+ LOOP_WALK_END;
+ kmem_cache_free(branch_cachep, btree);
+ LOOP_WALK_END;
+}
+
+static void destroy(struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+
+ while (!del_timer(&map->gc))
+ msleep(IPTREE_DESTROY_SLEEP);
+ __flush(map);
+ kfree(map);
+ set->data = NULL;
+}
+
+static void flush(struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ unsigned int timeout = map->timeout;
+
+ __flush(map);
+ memset(map, 0, sizeof(*map));
+ map->timeout = timeout;
+}
+
+static void list_header(const struct ip_set *set, void *data)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_req_iptree_create *header =
+ (struct ip_set_req_iptree_create *) data;
+
+ header->timeout = map->timeout;
+}
+
+static int list_members_size(const struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ unsigned int count = 0;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies))
+ count++;
+ }
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+
+ DP("members %u", count);
+ return (count * sizeof(struct ip_set_req_iptree));
+}
+
+static void list_members(const struct ip_set *set, void *data)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ size_t offset = 0;
+ struct ip_set_req_iptree *entry;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies)) {
+ entry = (struct ip_set_req_iptree *)(data + offset);
+ entry->ip = ((a << 24) | (b << 16) | (c << 8) | d);
+ entry->timeout = !map->timeout ? 0
+ : (dtree->expires[d] - jiffies)/HZ;
+ offset += sizeof(struct ip_set_req_iptree);
+ }
+ }
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+}
+
+static struct ip_set_type ip_set_iptree = {
+ .typename = SETTYPE_NAME,
+ .typecode = IPSET_TYPE_IP,
+ .protocol_version = IP_SET_PROTOCOL_VERSION,
+ .create = &create,
+ .destroy = &destroy,
+ .flush = &flush,
+ .reqsize = sizeof(struct ip_set_req_iptree),
+ .addip = &addip,
+ .addip_kernel = &addip_kernel,
+ .delip = &delip,
+ .delip_kernel = &delip_kernel,
+ .testip = &testip,
+ .testip_kernel = &testip_kernel,
+ .header_size = sizeof(struct ip_set_req_iptree_create),
+ .list_header = &list_header,
+ .list_members_size = &list_members_size,
+ .list_members = &list_members,
+ .me = THIS_MODULE,
+};
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Jozsef Kadlecsik <kadlec at blackhole.kfki.hu>");
+MODULE_DESCRIPTION("iptree type of IP sets");
+
+static int __init init(void)
+{
+ int ret;
+
+ branch_cachep = kmem_cache_create("ip_set_iptree_branches",
+ sizeof(struct ip_set_iptreeb),
+ 0, 0, NULL, NULL);
+ if (!branch_cachep) {
+ printk(KERN_ERR "Unable to create ip_set_iptree_branches slab cache\n");
+ ret = -ENOMEM;
+ goto out;
+ }
+ leaf_cachep = kmem_cache_create("ip_set_iptree_leaves",
+ sizeof(struct ip_set_iptreed),
+ 0, 0, NULL, NULL);
+ if (!leaf_cachep) {
+ printk(KERN_ERR "Unable to create ip_set_iptree_leaves slab cache\n");
+ ret = -ENOMEM;
+ goto free_branch;
+ }
+ ret = ip_set_register_set_type(&ip_set_iptree);
+ if (ret == 0)
+ goto out;
+
+ kmem_cache_destroy(leaf_cachep);
+ free_branch:
+ kmem_cache_destroy(branch_cachep);
+ out:
+ return ret;
+}
+
+static void __exit fini(void)
+{
+ /* FIXME: possible race with ip_set_create() */
+ ip_set_unregister_set_type(&ip_set_iptree);
+ kmem_cache_destroy(leaf_cachep);
+ kmem_cache_destroy(branch_cachep);
+}
+
+module_init(init);
+module_exit(fini);
Added: trunk/patch-o-matic-ng/set/linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h
===================================================================
--- trunk/patch-o-matic-ng/set/linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux-2.6/include/linux/netfilter_ipv4/ip_set_iptree.h 2005-04-11 07:48:39 UTC (rev 3853)
@@ -0,0 +1,39 @@
+#ifndef __IP_SET_IPTREE_H
+#define __IP_SET_IPTREE_H
+
+#include <linux/netfilter_ipv4/ip_set.h>
+
+#define SETTYPE_NAME "iptree"
+#define MAX_RANGE 0x0000FFFF
+
+struct ip_set_iptreed {
+ unsigned long expires[255]; /* x.x.x.ADDR */
+};
+
+struct ip_set_iptreec {
+ struct ip_set_iptreed *tree[255]; /* x.x.ADDR.* */
+};
+
+struct ip_set_iptreeb {
+ struct ip_set_iptreec *tree[255]; /* x.ADDR.*.* */
+};
+
+struct ip_set_iptree {
+ unsigned int timeout;
+ unsigned int gc_interval;
+#ifdef __KERNEL__
+ struct timer_list gc;
+ struct ip_set_iptreeb *tree[255]; /* ADDR.*.*.* */
+#endif
+};
+
+struct ip_set_req_iptree_create {
+ unsigned int timeout;
+};
+
+struct ip_set_req_iptree {
+ ip_set_ip_t ip;
+ unsigned int timeout;
+};
+
+#endif /* __IP_SET_IPTREE_H */
Modified: trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Kconfig.ladd
===================================================================
--- trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Kconfig.ladd 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Kconfig.ladd 2005-04-11 07:48:39 UTC (rev 3853)
@@ -71,6 +71,14 @@
To compile it as a module, choose M here. If unsure, say N.
+config IP_NF_SET_IPTREE
+ tristate "iptree set support"
+ depends on IP_NF_SET
+ help
+ This option adds the iptree set type support.
+
+ To compile it as a module, choose M here. If unsure, say N.
+
config IP_NF_MATCH_SET
tristate "set match support"
depends on IP_NF_SET
Modified: trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Makefile.ladd_2
===================================================================
--- trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Makefile.ladd_2 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/Makefile.ladd_2 2005-04-11 07:48:39 UTC (rev 3853)
@@ -8,3 +8,4 @@
obj-$(CONFIG_IP_NF_SET_MACIPMAP) += ip_set_macipmap.o
obj-$(CONFIG_IP_NF_SET_IPHASH) += ip_set_iphash.o
obj-$(CONFIG_IP_NF_SET_NETHASH) += ip_set_nethash.o
+obj-$(CONFIG_IP_NF_SET_IPTREE) += ip_set_iptree.o
Added: trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/ip_set_iptree.c
===================================================================
--- trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/ip_set_iptree.c 2005-04-11 07:44:47 UTC (rev 3852)
+++ trunk/patch-o-matic-ng/set/linux-2.6/net/ipv4/netfilter/ip_set_iptree.c 2005-04-11 07:48:39 UTC (rev 3853)
@@ -0,0 +1,509 @@
+/* Copyright (C) 2005 Jozsef Kadlecsik <kadlec at blackhole.kfki.hu>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+/* Kernel module implementing an IP set type: the iptree type */
+
+#include <linux/module.h>
+#include <linux/ip.h>
+#include <linux/skbuff.h>
+#include <linux/slab.h>
+#include <linux/delay.h>
+#include <linux/netfilter_ipv4/ip_tables.h>
+#include <linux/netfilter_ipv4/ip_set.h>
+#include <linux/errno.h>
+#include <asm/uaccess.h>
+#include <asm/bitops.h>
+#include <linux/spinlock.h>
+
+#include <linux/netfilter_ipv4/ip_set_iptree.h>
+
+/* Garbage collection interval in seconds: */
+#define IPTREE_GC_TIME 5*60
+/* Sleep so many milliseconds before trying again
+ * to delete the gc timer at destroying a set */
+#define IPTREE_DESTROY_SLEEP 100
+
+static kmem_cache_t *branch_cachep;
+static kmem_cache_t *leaf_cachep;
+
+#define ABCD(a,b,c,d,addrp) do { \
+ a = ((unsigned char *)addrp)[3]; \
+ b = ((unsigned char *)addrp)[2]; \
+ c = ((unsigned char *)addrp)[1]; \
+ d = ((unsigned char *)addrp)[0]; \
+} while (0)
+
+#define TESTIP_WALK(map, elem, branch) do { \
+ if ((map)->tree[elem]) { \
+ branch = (map)->tree[elem]; \
+ } else \
+ return 0; \
+} while (0)
+
+static inline int
+__testip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DP("%u %u %u %u timeout %u", a, b, c, d, map->timeout);
+ TESTIP_WALK(map, a, btree);
+ TESTIP_WALK(btree, b, ctree);
+ TESTIP_WALK(ctree, c, dtree);
+ DP("%lu %lu", dtree->expires[d], jiffies);
+ return !!(map->timeout ? (dtree->expires[d] > jiffies)
+ : dtree->expires[d]);
+}
+
+static int
+testip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ return __testip(set, req->ip, hash_ip);
+}
+
+static int
+testip_kernel(struct ip_set *set,
+ const struct sk_buff *skb,
+ u_int32_t flags,
+ ip_set_ip_t *hash_ip)
+{
+ int res;
+
+ DP("flag: %s src: %u.%u.%u.%u dst: %u.%u.%u.%u",
+ flags & IPSET_SRC ? "SRC" : "DST",
+ NIPQUAD(skb->nh.iph->saddr),
+ NIPQUAD(skb->nh.iph->daddr));
+
+ res = __testip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ hash_ip);
+ return (res < 0 ? 0 : res);
+}
+
+#define ADDIP_WALK(map, elem, branch, type, cachep) do { \
+ if ((map)->tree[elem]) { \
+ DP("found %u", elem); \
+ branch = (map)->tree[elem]; \
+ } else { \
+ branch = (type *) \
+ kmem_cache_alloc(cachep, GFP_KERNEL); \
+ if (branch == NULL) \
+ return -ENOMEM; \
+ memset(branch, 0, sizeof(*branch)); \
+ (map)->tree[elem] = branch; \
+ DP("alloc %u", elem); \
+ } \
+} while (0)
+
+static inline int
+__addip(struct ip_set *set, ip_set_ip_t ip, unsigned int timeout,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DP("%u %u %u %u timeout %u", a, b, c, d, timeout);
+ ADDIP_WALK(map, a, btree, struct ip_set_iptreeb, branch_cachep);
+ ADDIP_WALK(btree, b, ctree, struct ip_set_iptreec, branch_cachep);
+ ADDIP_WALK(ctree, c, dtree, struct ip_set_iptreed, leaf_cachep);
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies))
+ return -EEXIST;
+ dtree->expires[d] = map->timeout ? (timeout * HZ + jiffies) : 1;
+ DP("%u %lu", d, dtree->expires[d]);
+ return 0;
+}
+
+static int
+addip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ DP("%u.%u.%u.%u %u", HIPQUAD(req->ip), req->timeout);
+ return __addip(set, req->ip,
+ req->timeout ? req->timeout : map->timeout,
+ hash_ip);
+}
+
+static int
+addip_kernel(struct ip_set *set, const struct sk_buff *skb,
+ u_int32_t flags, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+
+ return __addip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ map->timeout,
+ hash_ip);
+}
+
+#define DELIP_WALK(map, elem, branch) do { \
+ if ((map)->tree[elem]) { \
+ branch = (map)->tree[elem]; \
+ } else \
+ return -EEXIST; \
+} while (0)
+
+static inline int
+__delip(struct ip_set *set, ip_set_ip_t ip, ip_set_ip_t *hash_ip)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+
+ *hash_ip = ip;
+ ABCD(a, b, c, d, hash_ip);
+ DELIP_WALK(map, a, btree);
+ DELIP_WALK(btree, b, ctree);
+ DELIP_WALK(ctree, c, dtree);
+
+ if (dtree->expires[d]) {
+ dtree->expires[d] = 0;
+ return 0;
+ }
+ return -EEXIST;
+}
+
+static int
+delip(struct ip_set *set, const void *data, size_t size,
+ ip_set_ip_t *hash_ip)
+{
+ struct ip_set_req_iptree *req =
+ (struct ip_set_req_iptree *) data;
+
+ if (size != sizeof(struct ip_set_req_iptree)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree),
+ size);
+ return -EINVAL;
+ }
+ return __delip(set, req->ip, hash_ip);
+}
+
+static int
+delip_kernel(struct ip_set *set, const struct sk_buff *skb,
+ u_int32_t flags, ip_set_ip_t *hash_ip)
+{
+ return __delip(set,
+ ntohl(flags & IPSET_SRC ? skb->nh.iph->saddr
+ : skb->nh.iph->daddr),
+ hash_ip);
+}
+
+#define LOOP_WALK_BEGIN(map, i, branch) \
+ for (i = 0; i < 255; i++) { \
+ if (!(map)->tree[i]) \
+ continue; \
+ branch = (map)->tree[i]
+
+#define LOOP_WALK_END }
+
+static void ip_tree_gc(unsigned long ul_set)
+{
+ struct ip_set *set = (void *) ul_set;
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ unsigned char i,j,k;
+
+ i = j = k = 0;
+ DP("gc: %s", set->name);
+ write_lock_bh(&set->lock);
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]) {
+ DP("gc: %u %u %u %u: expires %lu jiffies %lu",
+ a, b, c, d,
+ dtree->expires[d], jiffies);
+ if (map->timeout
+ && time_before(dtree->expires[d], jiffies))
+ dtree->expires[d] = 0;
+ else
+ k = 1;
+ }
+ }
+ if (k == 0) {
+ DP("gc: %s: leaf %u %u %u empty",
+ set->name, a, b, c);
+ kmem_cache_free(leaf_cachep, dtree);
+ ctree->tree[c] = NULL;
+ } else {
+ DP("gc: %s: leaf %u %u %u not empty",
+ set->name, a, b, c);
+ j = 1;
+ k = 0;
+ }
+ LOOP_WALK_END;
+ if (j == 0) {
+ DP("gc: %s: branch %u %u empty",
+ set->name, a, b);
+ kmem_cache_free(branch_cachep, ctree);
+ btree->tree[b] = NULL;
+ } else {
+ DP("gc: %s: branch %u %u not empty",
+ set->name, a, b);
+ i = 1;
+ j = k = 0;
+ }
+ LOOP_WALK_END;
+ if (i == 0) {
+ DP("gc: %s: branch %u empty",
+ set->name, a);
+ kmem_cache_free(branch_cachep, btree);
+ map->tree[a] = NULL;
+ } else {
+ DP("gc: %s: branch %u not empty",
+ set->name, a);
+ i = j = k = 0;
+ }
+ LOOP_WALK_END;
+ write_unlock_bh(&set->lock);
+
+ map->gc.expires = jiffies + map->gc_interval * HZ;
+ add_timer(&map->gc);
+}
+
+static int create(struct ip_set *set, const void *data, size_t size)
+{
+ struct ip_set_req_iptree_create *req =
+ (struct ip_set_req_iptree_create *) data;
+ struct ip_set_iptree *map;
+
+ if (size != sizeof(struct ip_set_req_iptree_create)) {
+ ip_set_printk("data length wrong (want %d, have %d)",
+ sizeof(struct ip_set_req_iptree_create),
+ size);
+ return -EINVAL;
+ }
+
+ map = kmalloc(sizeof(struct ip_set_iptree), GFP_KERNEL);
+ if (!map) {
+ DP("out of memory for %d bytes",
+ sizeof(struct ip_set_iptree));
+ return -ENOMEM;
+ }
+ memset(map, 0, sizeof(*map));
+ map->timeout = req->timeout;
+ set->data = map;
+
+ /* If there is no timeout for the entries,
+ * we still have to call gc because delete
+ * do not clean up empty branches */
+ map->gc_interval = IPTREE_GC_TIME;
+ init_timer(&map->gc);
+ map->gc.data = (unsigned long) set;
+ map->gc.function = ip_tree_gc;
+ map->gc.expires = jiffies + map->gc_interval * HZ;
+ add_timer(&map->gc);
+
+ return 0;
+}
+
+static void __flush(struct ip_set_iptree *map)
+{
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned int a,b,c;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ kmem_cache_free(leaf_cachep, dtree);
+ LOOP_WALK_END;
+ kmem_cache_free(branch_cachep, ctree);
+ LOOP_WALK_END;
+ kmem_cache_free(branch_cachep, btree);
+ LOOP_WALK_END;
+}
+
+static void destroy(struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+
+ while (!del_timer(&map->gc))
+ msleep(IPTREE_DESTROY_SLEEP);
+ __flush(map);
+ kfree(map);
+ set->data = NULL;
+}
+
+static void flush(struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ unsigned int timeout = map->timeout;
+
+ __flush(map);
+ memset(map, 0, sizeof(*map));
+ map->timeout = timeout;
+}
+
+static void list_header(const struct ip_set *set, void *data)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_req_iptree_create *header =
+ (struct ip_set_req_iptree_create *) data;
+
+ header->timeout = map->timeout;
+}
+
+static int list_members_size(const struct ip_set *set)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ unsigned int count = 0;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies))
+ count++;
+ }
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+
+ DP("members %u", count);
+ return (count * sizeof(struct ip_set_req_iptree));
+}
+
+static void list_members(const struct ip_set *set, void *data)
+{
+ struct ip_set_iptree *map = (struct ip_set_iptree *) set->data;
+ struct ip_set_iptreeb *btree;
+ struct ip_set_iptreec *ctree;
+ struct ip_set_iptreed *dtree;
+ unsigned char a,b,c,d;
+ size_t offset = 0;
+ struct ip_set_req_iptree *entry;
+
+ LOOP_WALK_BEGIN(map, a, btree);
+ LOOP_WALK_BEGIN(btree, b, ctree);
+ LOOP_WALK_BEGIN(ctree, c, dtree);
+ for (d = 0; d < 255; d++) {
+ if (dtree->expires[d]
+ && (!map->timeout || dtree->expires[d] > jiffies)) {
+ entry = (struct ip_set_req_iptree *)(data + offset);
+ entry->ip = ((a << 24) | (b << 16) | (c << 8) | d);
+ entry->timeout = !map->timeout ? 0
+ : (dtree->expires[d] - jiffies)/HZ;
+ offset += sizeof(struct ip_set_req_iptree);
+ }
+ }
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+ LOOP_WALK_END;
+}
+
+static struct ip_set_type ip_set_iptree = {
+ .typename = SETTYPE_NAME,
+ .typecode = IPSET_TYPE_IP,
+ .protocol_version = IP_SET_PROTOCOL_VERSION,
+ .create = &create,
+ .destroy = &destroy,
+ .flush = &flush,
+ .reqsize = sizeof(struct ip_set_req_iptree),
+ .addip = &addip,
+ .addip_kernel = &addip_kernel,
+ .delip = &delip,
+ .delip_kernel = &delip_kernel,
+ .testip = &testip,
+ .testip_kernel = &testip_kernel,
+ .header_size = sizeof(struct ip_set_req_iptree_create),
+ .list_header = &list_header,
+ .list_members_size = &list_members_size,
+ .list_members = &list_members,
+ .me = THIS_MODULE,
+};
+
+MODULE_LICENSE("GPL");
+MODULE_AUTHOR("Jozsef Kadlecsik <kadlec at blackhole.kfki.hu>");
+MODULE_DESCRIPTION("iptree type of IP sets");
+
+static int __init init(void)
+{
+ int ret;
+
+ branch_cachep = kmem_cache_create("ip_set_iptree_branches",
+ sizeof(struct ip_set_iptreeb),
+ 0, 0, NULL, NULL);
+ if (!branch_cachep) {
+ printk(KERN_ERR "Unable to create ip_set_iptree_branches slab cache\n");
+ ret = -ENOMEM;
+ goto out;
+ }
+ leaf_cachep = kmem_cache_create("ip_set_iptree_leaves",
+ sizeof(struct ip_set_iptreed),
+ 0, 0, NULL, NULL);
+ if (!leaf_cachep) {
+ printk(KERN_ERR "Unable to create ip_set_iptree_leaves slab cache\n");
+ ret = -ENOMEM;
+ goto free_branch;
+ }
+ ret = ip_set_register_set_type(&ip_set_iptree);
+ if (ret == 0)
+ goto out;
+
+ kmem_cache_destroy(leaf_cachep);
+ free_branch:
+ kmem_cache_destroy(branch_cachep);
+ out:
+ return ret;
+}
+
+static void __exit fini(void)
+{
+ /* FIXME: possible race with ip_set_create() */
+ ip_set_unregister_set_type(&ip_set_iptree);
+ kmem_cache_destroy(leaf_cachep);
+ kmem_cache_destroy(branch_cachep);
+}
+
+module_init(init);
+module_exit(fini);
More information about the netfilter-cvslog
mailing list