filter: CIDR-based filtering support

This patch adds CIDR-based filtering support. The current
implementation is O(n).

This patch also introduces the vector data type which is
used to store the IP address and the network mask.

Signed-off-by: Pablo Neira Ayuso <pablo@netfilter.org>

6 files changed, 313 insertions, 20 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 82f7dfe..64ed2b5 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -11,13 +11,13 @@ conntrack_LDADD = ../extensions/libct_proto_tcp.la ../extensions/libct_proto_udp
 conntrack_LDFLAGS = $(all_libraries) @LIBNETFILTER_CONNTRACK_LIBS@
 
 conntrackd_SOURCES = alarm.c main.c run.c hash.c queue.c rbtree.c \
-		    local.c log.c mcast.c netlink.c \
+		    local.c log.c mcast.c netlink.c vector.c \
 		    filter.c fds.c event.c \
 		    cache.c cache_iterators.c \
 		    cache_lifetime.c cache_timer.c cache_wt.c \
 		    sync-mode.c sync-alarm.c sync-ftfw.c sync-notrack.c \
 		    traffic_stats.c stats-mode.c \
-		    network.c \
+		    network.c cidr.c \
 		    build.c parse.c \
 		    read_config_yy.y read_config_lex.l
 
diff --git a/src/cidr.c b/src/cidr.c
new file mode 100644
index 0000000..d43dabc
--- /dev/null
+++ b/src/cidr.c
@@ -0,0 +1,59 @@
+/*
+ * (C) 2006-2008 by Pablo Neira Ayuso <pablo@netfilter.org>
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include <stdint.h>
+#include <string.h>
+#include <netinet/in.h>
+#include "cidr.h"
+
+/* returns the netmask in host byte order */
+uint32_t ipv4_cidr2mask_host(uint8_t cidr)
+{
+	return 0xFFFFFFFF << (32 - cidr);
+}
+
+/* returns the netmask in network byte order */
+uint32_t ipv4_cidr2mask_net(uint8_t cidr)
+{
+	return htonl(ipv4_cidr2mask_host(cidr));
+}
+
+void ipv6_cidr2mask_host(uint8_t cidr, uint32_t *res)
+{
+	int i, j;
+
+	memset(res, 0, sizeof(uint32_t)*4);
+	for (i = 0;  i < 4 && cidr > 32; i++) {
+		res[i] = 0xFFFFFFFF;
+		cidr -= 32;
+	}
+	res[i] = 0xFFFFFFFF << (32 - cidr);
+	for (j = i+1; j < 4; j++) {
+		res[j] = 0;
+	}
+}
+
+void ipv6_cidr2mask_net(uint8_t cidr, uint32_t *res)
+{
+	int i;
+
+	ipv6_cidr2mask_host(cidr, res);
+	for (i=0; i<4; i++)
+		res[i] = htonl(res[i]);
+}
+
diff --git a/src/filter.c b/src/filter.c
index f6da8bb..905d10f 100644
--- a/src/filter.c
+++ b/src/filter.c
@@ -20,12 +20,14 @@
 #include "bitops.h"
 #include "jhash.h"
 #include "hash.h"
+#include "vector.h"
 #include "conntrackd.h"
 #include "log.h"
 
 #include <libnetfilter_conntrack/libnetfilter_conntrack.h>
 #include <stdlib.h>
 #include <string.h>
+#include <errno.h>
 #include <limits.h>
 
 struct ct_filter {
@@ -34,6 +36,8 @@ struct ct_filter {
 	u_int16_t statemap[IPPROTO_MAX];
 	struct hashtable *h;
 	struct hashtable *h6;
+	struct vector *v;
+	struct vector *v6;
 };
 
 /* XXX: These should be configurable, better use a rb-tree */
@@ -95,6 +99,23 @@ struct ct_filter *ct_filter_create(void)
 		return NULL;
 	}
 
+	filter->v = vector_create(sizeof(struct ct_filter_netmask_ipv4));
+	if (!filter->v) {
+		free(filter->h6);
+		free(filter->h);
+		free(filter);
+		return NULL;
+	}
+
+	filter->v6 = vector_create(sizeof(struct ct_filter_netmask_ipv6));
+	if (!filter->v6) {
+		free(filter->v);
+		free(filter->h6);
+		free(filter->h);
+		free(filter);
+		return NULL;
+	}
+
 	for (i=0; i<CT_FILTER_MAX; i++)
 		filter->logic[i] = -1;
 
@@ -105,6 +126,8 @@ void ct_filter_destroy(struct ct_filter *filter)
 {
 	hashtable_destroy(filter->h);
 	hashtable_destroy(filter->h6);
+	vector_destroy(filter->v);
+	vector_destroy(filter->v6);
 	free(filter);
 }
 
@@ -147,6 +170,39 @@ int ct_filter_add_ip(struct ct_filter *filter, void *data, uint8_t family)
 	return 1;
 }
 
+static int cmp_ipv4_addr(const void *a, const void *b)
+{
+	return memcmp(a, b, sizeof(struct ct_filter_netmask_ipv4)) == 0;
+}
+
+static int cmp_ipv6_addr(const void *a, const void *b)
+{
+	return memcmp(a, b, sizeof(struct ct_filter_netmask_ipv6)) == 0;
+}
+
+int ct_filter_add_netmask(struct ct_filter *filter, void *data, uint8_t family)
+{
+	filter = __filter_alloc(filter);
+
+	switch(family) {
+		case AF_INET:
+			if (vector_iterate(filter->v, data, cmp_ipv4_addr)) {
+				errno = EEXIST;
+				return 0;
+			}
+			vector_add(filter->v, data);
+			break;
+		case AF_INET6:
+			if (vector_iterate(filter->v, data, cmp_ipv6_addr)) {
+				errno = EEXIST;
+				return 0;
+			}
+			vector_add(filter->v6, data);
+			break;
+	}
+	return 1;
+}
+
 void ct_filter_add_proto(struct ct_filter *f, int protonum)
 {
 	f = __filter_alloc(f);
@@ -176,6 +232,34 @@ __ct_filter_test_ipv6(struct ct_filter *f, struct nf_conntrack *ct)
 	        hashtable_test(f->h6, nfct_get_attr(ct, ATTR_REPL_IPV6_SRC)));
 }
 
+static int
+__ct_filter_test_mask4(const void *ptr, const void *ct)
+{
+	const struct ct_filter_netmask_ipv4 *elem = ptr;
+	const uint32_t src = nfct_get_attr_u32(ct, ATTR_ORIG_IPV4_SRC);
+	const uint32_t dst = nfct_get_attr_u32(ct, ATTR_REPL_IPV4_SRC);
+
+	return ((elem->ip & elem->mask) == (src & elem->mask) || 
+		(elem->ip & elem->mask) == (dst & elem->mask));
+}
+
+static int
+__ct_filter_test_mask6(const void *ptr, const void *ct)
+{
+	const struct ct_filter_netmask_ipv6 *elem = ptr;
+	const uint32_t *src = nfct_get_attr(ct, ATTR_ORIG_IPV6_SRC);
+	const uint32_t *dst = nfct_get_attr(ct, ATTR_REPL_IPV6_SRC);
+
+	return (((elem->ip[0] & elem->mask[0]) == (src[0] & elem->mask[0]) &&
+		 (elem->ip[1] & elem->mask[1]) == (src[1] & elem->mask[1]) &&
+		 (elem->ip[2] & elem->mask[2]) == (src[2] & elem->mask[2]) &&
+		 (elem->ip[3] & elem->mask[3]) == (src[3] & elem->mask[3])) ||
+		((elem->ip[0] & elem->mask[0]) == (dst[0] & elem->mask[0]) &&
+		 (elem->ip[1] & elem->mask[1]) == (dst[1] & elem->mask[1]) &&
+		 (elem->ip[2] & elem->mask[2]) == (dst[2] & elem->mask[2]) &&
+		 (elem->ip[3] & elem->mask[3]) == (dst[3] & elem->mask[3])));
+}
+
 static int __ct_filter_test_state(struct ct_filter *f, struct nf_conntrack *ct)
 {
 	uint16_t val = 0;
@@ -212,11 +296,17 @@ int ct_filter_check(struct ct_filter *f, struct nf_conntrack *ct)
 	if (f->logic[CT_FILTER_ADDRESS] != -1) {
 		switch(nfct_get_attr_u8(ct, ATTR_L3PROTO)) {
 		case AF_INET:
+			ret = vector_iterate(f->v, ct, __ct_filter_test_mask4);
+			if (ret ^ f->logic[CT_FILTER_ADDRESS])
+				return 0;
 			ret = __ct_filter_test_ipv4(f, ct);
 			if (ret ^ f->logic[CT_FILTER_ADDRESS])
 				return 0;
 			break;
 		case AF_INET6:
+			ret = vector_iterate(f->v6, ct, __ct_filter_test_mask6);
+			if (ret ^ f->logic[CT_FILTER_ADDRESS])
+				return 0;
 			ret = __ct_filter_test_ipv6(f, ct);
 			if (ret ^ f->logic[CT_FILTER_ADDRESS])
 				return 0;
diff --git a/src/read_config_lex.l b/src/read_config_lex.l
index cbb6ca8..67c95d3 100644
--- a/src/read_config_lex.l
+++ b/src/read_config_lex.l
@@ -36,14 +36,16 @@ is_on		[o|O][n|N]
 is_off		[o|O][f|F][f|F]
 integer		[0-9]+
 path		\/[^\"\n ]*
+ip4_cidr	\/[0-2]*[0-9]+
 ip4_end		[0-9]*[0-9]+
 ip4_part	[0-2]*{ip4_end}
-ip4		{ip4_part}\.{ip4_part}\.{ip4_part}\.{ip4_part}
+ip4		{ip4_part}\.{ip4_part}\.{ip4_part}\.{ip4_part}{ip4_cidr}?
 hex_255		[0-9a-fA-F]{1,4}
+ip6_cidr	\/[0-1]*[0-9]*[0-9]+
 ip6_part	{hex_255}":"?
 ip6_form1	{ip6_part}{0,16}"::"{ip6_part}{0,16}
 ip6_form2	({hex_255}":"){16}{hex_255}
-ip6		{ip6_form1}|{ip6_form2}
+ip6		{ip6_form1}{ip6_cidr}?|{ip6_form2}{ip6_cidr}?
 string		[a-zA-Z][a-zA-Z0-9\.]*
 persistent	[P|p][E|e][R|r][S|s][I|i][S|s][T|t][E|e][N|n][T|T]
 nack		[N|n][A|a][C|c][K|k]
diff --git a/src/read_config_yy.y b/src/read_config_yy.y
index 06ada52..32ddeff 100644
--- a/src/read_config_yy.y
+++ b/src/read_config_yy.y
@@ -26,6 +26,7 @@
 #include <errno.h>
 #include "conntrackd.h"
 #include "bitops.h"
+#include "cidr.h"
 #include <syslog.h>
 #include <libnetfilter_conntrack/libnetfilter_conntrack.h>
 #include <libnetfilter_conntrack/libnetfilter_conntrack_tcp.h>
@@ -780,27 +781,55 @@ filter_address_list :
 filter_address_item : T_IPV4_ADDR T_IP
 {
 	union inet_address ip;
+	char *slash;
+	unsigned int cidr = 32;
 
 	memset(&ip, 0, sizeof(union inet_address));
 
+	slash = strchr($2, '/');
+	if (slash) {
+		*slash = '\0';
+		cidr = atoi(slash+1);
+		if (cidr > 32) {
+			fprintf(stderr, "%s/%d is not a valid network, "
+					"ignoring\n", $2, cidr);
+			break;
+		}
+	}
+
 	if (!inet_aton($2, &ip.ipv4)) {
 		fprintf(stderr, "%s is not a valid IPv4, ignoring", $2);
 		break;
 	}
 
-	if (!ct_filter_add_ip(STATE(us_filter), &ip, AF_INET)) {
-		if (errno == EEXIST)
-			fprintf(stderr, "IP %s is repeated "
-					"in the ignore pool\n", $2);
-		if (errno == ENOSPC)
-			fprintf(stderr, "Too many IP in the ignore pool!\n");
+	if (slash && cidr < 32) {
+		/* network byte order */
+		struct ct_filter_netmask_ipv4 tmp = {
+			.ip = ip.ipv4,
+			.mask = ipv4_cidr2mask_net(cidr)
+		};
+
+		if (!ct_filter_add_netmask(STATE(us_filter), &tmp, AF_INET)) {
+			if (errno == EEXIST)
+				fprintf(stderr, "Netmask %s is repeated "
+						"in the ignore pool\n", $2);
+		}
+	} else {
+		if (!ct_filter_add_ip(STATE(us_filter), &ip, AF_INET)) {
+			if (errno == EEXIST)
+				fprintf(stderr, "IP %s is repeated "
+						"in the ignore pool\n", $2);
+			if (errno == ENOSPC)
+				fprintf(stderr, "Too many IP in the "
+						"ignore pool!\n");
+		}
 	}
-
 	__kernel_filter_start();
 
+	/* host byte order */
 	struct nfct_filter_ipv4 filter_ipv4 = {
-		.addr = htonl(ip.ipv4),
-		.mask = 0xffffffff,
+		.addr = ntohl(ip.ipv4),
+		.mask = ipv4_cidr2mask_host(cidr),
 	};
 
 	nfct_filter_add_attr(STATE(filter), NFCT_FILTER_SRC_IPV4, &filter_ipv4);
@@ -810,9 +839,22 @@ filter_address_item : T_IPV4_ADDR T_IP
 filter_address_item : T_IPV6_ADDR T_IP
 {
 	union inet_address ip;
+	char *slash;
+	int cidr;
 
 	memset(&ip, 0, sizeof(union inet_address));
 
+	slash = strchr($2, '/');
+	if (slash) {
+		*slash = '\0';
+		cidr = atoi(slash+1);
+		if (cidr > 128) {
+			fprintf(stderr, "%s/%d is not a valid network, "
+					"ignoring\n", $2, cidr);
+			break;
+		}
+	}
+
 #ifdef HAVE_INET_PTON_IPV6
 	if (inet_pton(AF_INET6, $2, &ip.ipv6) <= 0) {
 		fprintf(stderr, "%s is not a valid IPv6, ignoring", $2);
@@ -822,13 +864,25 @@ filter_address_item : T_IPV6_ADDR T_IP
 	fprintf(stderr, "Cannot find inet_pton(), IPv6 unsupported!");
 	break;
 #endif
-
-	if (!ct_filter_add_ip(STATE(us_filter), &ip, AF_INET6)) {
-		if (errno == EEXIST)
-			fprintf(stderr, "IP %s is repeated "
-					"in the ignore pool\n", $2);
-		if (errno == ENOSPC)
-			fprintf(stderr, "Too many IP in the ignore pool!\n");
+	if (slash && cidr < 128) {
+		struct ct_filter_netmask_ipv6 tmp;
+
+		memcpy(tmp.ip, ip.ipv6, sizeof(uint32_t)*4);
+		ipv6_cidr2mask_net(cidr, tmp.mask);
+		if (!ct_filter_add_netmask(STATE(us_filter), &tmp, AF_INET6)) {
+			if (errno == EEXIST)
+				fprintf(stderr, "Netmask %s is repeated "
+						"in the ignore pool\n", $2);
+		}
+	} else {
+		if (!ct_filter_add_ip(STATE(us_filter), &ip, AF_INET6)) {
+			if (errno == EEXIST)
+				fprintf(stderr, "IP %s is repeated "
+						"in the ignore pool\n", $2);
+			if (errno == ENOSPC)
+				fprintf(stderr, "Too many IP in the "
+						"ignore pool!\n");
+		}
 	}
 };
 
diff --git a/src/vector.c b/src/vector.c
new file mode 100644
index 0000000..c81e7ce
--- /dev/null
+++ b/src/vector.c
@@ -0,0 +1,88 @@
+/*
+ * (C) 2006-2008 by Pablo Neira Ayuso <pablo@netfilter.org>
+ * 
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
+ */
+
+#include "vector.h"
+
+#include <stdlib.h>
+#include <string.h>
+
+struct vector {
+	char *data;
+	unsigned int cur_elems;
+	unsigned int max_elems;
+	size_t size;
+};
+
+#define DEFAULT_VECTOR_MEMBERS	8
+#define DEFAULT_VECTOR_GROWTH	8
+
+struct vector *vector_create(size_t size)
+{
+	struct vector *v;
+
+	v = calloc(sizeof(struct vector), 1);
+	if (v == NULL)
+		return NULL;
+
+	v->size = size;
+	v->cur_elems = 0;
+	v->max_elems = DEFAULT_VECTOR_MEMBERS;
+
+	v->data = calloc(size * DEFAULT_VECTOR_MEMBERS, 1);
+	if (v->data == NULL) {
+		free(v);
+		return NULL;
+	}
+
+	return v;
+}
+
+void vector_destroy(struct vector *v)
+{
+	free(v->data);
+	free(v);
+}
+
+int vector_add(struct vector *v, void *data)
+{
+	if (v->cur_elems >= v->max_elems) {
+		v->max_elems += DEFAULT_VECTOR_GROWTH;
+		v->data = realloc(v->data, v->max_elems * v->size);
+		if (v->data == NULL) {
+			v->max_elems -= DEFAULT_VECTOR_GROWTH;
+			return -1;
+		}
+	}
+	memcpy(v->data + (v->size * v->cur_elems), data, v->size);
+	v->cur_elems++;
+	return 0;
+}
+
+int vector_iterate(struct vector *v,
+		   const void *data,
+		   int (*fcn)(const void *a, const void *b))
+{
+	unsigned int i;
+
+	for (i=0; i<v->cur_elems; i++) {
+		char *ptr = v->data + (v->size * i);
+		if (fcn(ptr, data))
+			return 1;
+	}
+	return 0;
+}