[PATCH 0/3] Further speedup of iptables when modifying an existing ruleset

[PATCH 0/3] Further speedup of iptables when modifying an existing ruleset

[Thomas Jacob]

This version includes the coding style changes, but still employs the macro
to implement the binary interval search.

[PATCH 1/3] Speed up verdict to chain_head mapping by using binary search

[Thomas Jacob]

Signed-off-by: Thomas Jacob <jacob@internet24.de>
---
 libiptc/libiptc.c |  199 +++++++++++++++++++++++++++++++++++++++++++++++++++--
 1 files changed, 192 insertions(+), 7 deletions(-)

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index d0f51b4..e0c44c3 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -126,6 +126,26 @@ struct chain_head
 	unsigned int foot_offset;	/* offset in rule blob */
 };
 
+/* Max. number of chain_head per offsets chunk */
+#define OFFSETS_CHUNK_SIZE (1024)
+
+struct offsets_create_chunk
+{
+	struct list_head list;
+
+	unsigned int head_offset; /* of first entry */
+	unsigned int foot_offset; /* of last entry */
+
+	unsigned int num_entries; /* #entries */
+	struct chain_head * entries[OFFSETS_CHUNK_SIZE]; /* order by offset */
+};
+
+struct offsets_lookup_table
+{
+	unsigned int num_entries; /* #entries */
+	struct offsets_create_chunk ** entries; /* order by offset */
+};
+
 STRUCT_TC_HANDLE
 {
 	int changed;			 /* Have changes been made? */
@@ -140,6 +160,9 @@ STRUCT_TC_HANDLE
 	struct chain_head **chain_index;   /* array for fast chain list access*/
 	unsigned int        chain_index_sz;/* size of chain index array */
 
+	struct list_head            offsets_create_list; /* array chunks created during data acquisition */
+	struct offsets_lookup_table offsets_search;      /* final offsets search array */
+
 	STRUCT_GETINFO info;
 	STRUCT_GET_ENTRIES *entries;
 };
@@ -568,6 +591,61 @@ static int iptcc_chain_index_delete_chain(struct chain_head *c, TC_HANDLE_T h)
 
 
 /**********************************************************************
+ * iptc offsets index utility functions
+ **********************************************************************/
+
+/* Create offsets lookup table from the chunk list */
+static int iptcc_offsets_index_create(TC_HANDLE_T h)
+{
+	struct offsets_create_chunk * chunk;
+	unsigned int total_number=0;
+
+	/* First pass: count non-empty chunks and set their ranges */
+	list_for_each_entry(chunk, &h->offsets_create_list, list) {
+		if (chunk->num_entries>0) {
+			total_number++;
+			chunk->head_offset = chunk->entries[0]->head_offset;
+			chunk->foot_offset = chunk->entries[chunk->num_entries-1]->foot_offset;
+		}
+	}
+
+	/* No chains->nothing to assign */
+	if (total_number==0)
+		return 1;
+
+	h->offsets_search.entries = malloc(sizeof(struct offsets_create_chunk *)*total_number);
+	if (!h->offsets_search.entries)
+		return -ENOMEM;
+
+	/* Second pass: fill chunk table */
+	unsigned int i=0;
+	list_for_each_entry(chunk, &h->offsets_create_list, list)
+		if (chunk->num_entries>0)
+			h->offsets_search.entries[i++] = chunk;
+
+	h->offsets_search.num_entries = total_number;
+
+	return 1;
+}
+
+/* Free offsets lookup table AND the individual chunks */
+static void iptcc_offsets_index_free(TC_HANDLE_T h)
+{
+	struct offsets_create_chunk * chunk, *tmp;
+
+	if (h->offsets_search.num_entries>0) {
+		free(h->offsets_search.entries);
+		h->offsets_search.num_entries=0;
+	}
+
+	list_for_each_entry_safe(chunk, tmp, &h->offsets_create_list, list)
+		free(chunk);
+
+	INIT_LIST_HEAD(&h->offsets_create_list);
+}
+
+
+/**********************************************************************
  * iptc cache utility functions (iptcc_*)
  **********************************************************************/
 
@@ -625,6 +703,67 @@ iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
 	return NULL;
 }
 
+
+/*
+ * Fast membership check on order arrays of inclusive intervals
+ *  ( based on http://en.wikipedia.org/wiki/Binary_search )
+ *
+ * value: value to search for
+ * array: array of struct points
+ * left: struct attribute denoting left inclusive range limiter in array items
+ * right: struct attribute denoting left inclusive range limiter in array items
+ * size: number of items in array
+ * low, high, mid: temporary int variables
+ * result: index of range that contains value, or -1 if not found
+ */
+
+#define binary_array_range_search(value, array, left, right, size, low, high, mid, result) \
+	low = 0; \
+	high = size; \
+	result = -1; \
+	while(low<=high) \
+	{ \
+		mid = (low + high) / 2; \
+		if ((array)[mid]->left > value) \
+			high = mid - 1; \
+		else if ((array)[mid]->right < value) \
+			low = mid + 1; \
+		else { \
+			if ((array)[mid]->left <= value && value <= (array)[mid]->right) \
+				result = mid; \
+			break; \
+		} \
+	}
+
+/* Returns chain head if found, otherwise NULL. */
+static struct chain_head *
+iptcc_find_chain_by_offset_fast(TC_HANDLE_T handle, unsigned int offset)
+{
+	int low,high,mid,result;
+
+	if (handle->offsets_search.num_entries==0)
+		return NULL;
+
+	/* find the chunk */
+	binary_array_range_search(offset, handle->offsets_search.entries, head_offset, foot_offset,
+			handle->offsets_search.num_entries, low, high, mid, result);
+
+	if (result<0)
+		return NULL;
+
+	/* find chain in chunk */
+	struct chain_head ** chunk_chains =  handle->offsets_search.entries[result]->entries;
+	unsigned int num_entries = handle->offsets_search.entries[result]->num_entries;
+
+	binary_array_range_search(offset, chunk_chains, head_offset, foot_offset,
+			num_entries, low, high, mid, result);
+
+	if (result<0)
+		return NULL;
+
+	return chunk_chains[result];
+}
+
 /* Returns chain head if found, otherwise NULL. */
 static struct chain_head *
 iptcc_find_label(const char *name, TC_HANDLE_T handle)
@@ -720,6 +859,19 @@ static void iptcc_delete_rule(struct rule_head *r)
  * RULESET PARSER (blob -> cache)
  **********************************************************************/
 
+/* Allocate another offsets chunk and append it to list */
+static int __iptcc_p_new_offsets_chunk(TC_HANDLE_T h)
+{
+	struct offsets_create_chunk * new_chunk = malloc(sizeof(struct offsets_create_chunk));
+
+	if (new_chunk) {
+		new_chunk->num_entries=0;
+		list_add_tail(&new_chunk->list, &h->offsets_create_list);
+		return 1;
+	}
+	return -1;
+}
+
 /* Delete policy rule of previous chain, since cache doesn't contain
  * chain policy rules.
  * WARNING: This function has ugly design and relies on a lot of context, only
@@ -746,6 +898,19 @@ static int __iptcc_p_del_policy(TC_HANDLE_T h, unsigned int num)
 		h->chain_iterator_cur->foot_index = num;
 		h->chain_iterator_cur->foot_offset = pr->offset;
 
+		/* do we need a new offsets chunk? */
+		if (list_empty(&h->offsets_create_list) ||
+			list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list)->num_entries
+			>=OFFSETS_CHUNK_SIZE)
+			if (__iptcc_p_new_offsets_chunk(h)<0)
+				return -1;
+
+		/* add next chain to the current offsets chunk */
+		struct offsets_create_chunk * occ =
+			list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list);
+
+		occ->entries[occ->num_entries++]=h->chain_iterator_cur;
+
 		/* delete rule from cache */
 		iptcc_delete_rule(pr);
 		h->chain_iterator_cur->num_rules--;
@@ -799,13 +964,14 @@ static inline void iptc_insert_chain(TC_HANDLE_T h, struct chain_head *c)
 
 /* Another ugly helper function split out of cache_add_entry to make it less
  * spaghetti code */
-static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
+static int __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
 				unsigned int offset, unsigned int *num)
 {
 	struct list_head  *tail = h->chains.prev;
 	struct chain_head *ctail;
 
-	__iptcc_p_del_policy(h, *num);
+	if ((__iptcc_p_del_policy(h, *num))<0)
+		return -1;
 
 	c->head_offset = offset;
 	c->index = *num;
@@ -826,6 +992,8 @@ static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
 	}
 
 	h->chain_iterator_cur = c;
+
+	return 1;
 }
 
 /* main parser function: add an entry from the blob to the cache */
@@ -844,7 +1012,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 		/* This is the ERROR node at the end of the chain */
 		DEBUGP_C("%u:%u: end of table:\n", *num, offset);
 
-		__iptcc_p_del_policy(h, *num);
+		if ((__iptcc_p_del_policy(h, *num))<0) {
+			errno = -ENOMEM;
+			return -1;
+		}
 
 		h->chain_iterator_cur = NULL;
 		goto out_inc;
@@ -864,8 +1035,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 		}
 		h->num_chains++; /* New user defined chain */
 
-		__iptcc_p_add_chain(h, c, offset, num);
-
+		if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+			errno = -ENOMEM;
+			return -1;
+		}
 	} else if ((builtin = iptcb_ent_is_hook_entry(e, h)) != 0) {
 		struct chain_head *c =
 			iptcc_alloc_chain_head((char *)hooknames[builtin-1], 
@@ -879,7 +1052,10 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 
 		c->hooknum = builtin;
 
-		__iptcc_p_add_chain(h, c, offset, num);
+		if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+			errno = -ENOMEM;
+			return -1;
+		}
 
 		/* FIXME: this is ugly. */
 		goto new_rule;
@@ -955,6 +1131,10 @@ static int parse_table(TC_HANDLE_T h)
 		return -ENOMEM;
 	iptcc_chain_index_build(h);
 
+	/* Build the offsets lookup table */
+	if ((iptcc_offsets_index_create(h)) < 0)
+		return -ENOMEM;
+
 	/* Second pass: fixup parsed data from first pass */
 	list_for_each_entry(c, &h->chains, list) {
 		struct rule_head *r;
@@ -966,7 +1146,7 @@ static int parse_table(TC_HANDLE_T h)
 				continue;
 
 			t = (STRUCT_STANDARD_TARGET *)GET_TARGET(r->entry);
-			lc = iptcc_find_chain_by_offset(h, t->verdict);
+			lc = iptcc_find_chain_by_offset_fast(h, t->verdict);
 			if (!lc)
 				return -1;
 			r->jump = lc;
@@ -974,6 +1154,9 @@ static int parse_table(TC_HANDLE_T h)
 		}
 	}
 
+	/* Don't need these tables anymore after beyond point */
+	iptcc_offsets_index_free(h);
+
 	/* FIXME: sort chains */
 
 	return 1;
@@ -1193,6 +1376,8 @@ alloc_handle(const char *tablename, unsigned int size, unsigned int num_rules)
 	strcpy(h->entries->name, tablename);
 	h->entries->size = size;
 
+	INIT_LIST_HEAD(&h->offsets_create_list);
+
 	return h;
 
 out_free_handle:
-- 
1.5.4.3

[PATCH 2/3] Spelling

[Thomas Jacob]

Signed-off-by: Thomas Jacob <jacob@internet24.de>
---
 libiptc/libiptc.c |   12 ++++++------
 1 files changed, 6 insertions(+), 6 deletions(-)

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index e0c44c3..c77455a 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -160,8 +160,8 @@ STRUCT_TC_HANDLE
 	struct chain_head **chain_index;   /* array for fast chain list access*/
 	unsigned int        chain_index_sz;/* size of chain index array */
 
-	struct list_head            offsets_create_list; /* array chunks created during data acquisition */
-	struct offsets_lookup_table offsets_search;      /* final offsets search array */
+	struct list_head            offsets_create_list; /* Array chunks created during data acquisition */
+	struct offsets_lookup_table offsets_search;      /* Final offsets search array */
 
 	STRUCT_GETINFO info;
 	STRUCT_GET_ENTRIES *entries;
@@ -705,11 +705,11 @@ iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
 
 
 /*
- * Fast membership check on order arrays of inclusive intervals
+ * Fast membership check on ordered arrays of inclusive intervals
  *  ( based on http://en.wikipedia.org/wiki/Binary_search )
  *
  * value: value to search for
- * array: array of struct points
+ * array: array of struct pointers
  * left: struct attribute denoting left inclusive range limiter in array items
  * right: struct attribute denoting left inclusive range limiter in array items
  * size: number of items in array
@@ -744,14 +744,14 @@ iptcc_find_chain_by_offset_fast(TC_HANDLE_T handle, unsigned int offset)
 	if (handle->offsets_search.num_entries==0)
 		return NULL;
 
-	/* find the chunk */
+	/* Find the chunk that could contain an appropriate interval */
 	binary_array_range_search(offset, handle->offsets_search.entries, head_offset, foot_offset,
 			handle->offsets_search.num_entries, low, high, mid, result);
 
 	if (result<0)
 		return NULL;
 
-	/* find chain in chunk */
+	/* Find chain in chunk */
 	struct chain_head ** chunk_chains =  handle->offsets_search.entries[result]->entries;
 	unsigned int num_entries = handle->offsets_search.entries[result]->num_entries;
 
-- 
1.5.4.3

[PATCH 3/3] Coding style

[Thomas Jacob]

Signed-off-by: Thomas Jacob <jacob@internet24.de>
---
 libiptc/libiptc.c |  118 ++++++++++++++++++++++++++++++-----------------------
 1 files changed, 67 insertions(+), 51 deletions(-)

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index c77455a..b89522b 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -129,21 +129,22 @@ struct chain_head
 /* Max. number of chain_head per offsets chunk */
 #define OFFSETS_CHUNK_SIZE (1024)
 
-struct offsets_create_chunk
+struct offsets_chunk
 {
 	struct list_head list;
 
-	unsigned int head_offset; /* of first entry */
-	unsigned int foot_offset; /* of last entry */
+	unsigned int first_offset; /* head_offset of first entry */
+	unsigned int last_offset; /* foot_offset of last entry */
 
-	unsigned int num_entries; /* #entries */
-	struct chain_head * entries[OFFSETS_CHUNK_SIZE]; /* order by offset */
+	unsigned int num_entries;
+	/* ordered by offset */
+	struct chain_head *entries[OFFSETS_CHUNK_SIZE];
 };
 
 struct offsets_lookup_table
 {
-	unsigned int num_entries; /* #entries */
-	struct offsets_create_chunk ** entries; /* order by offset */
+	unsigned int num_entries;
+	struct offsets_chunk **entries; /* ordered by offset */
 };
 
 STRUCT_TC_HANDLE
@@ -160,8 +161,10 @@ STRUCT_TC_HANDLE
 	struct chain_head **chain_index;   /* array for fast chain list access*/
 	unsigned int        chain_index_sz;/* size of chain index array */
 
-	struct list_head            offsets_create_list; /* Array chunks created during data acquisition */
-	struct offsets_lookup_table offsets_search;      /* Final offsets search array */
+	/* Array chunks created during data acquisition */
+	struct list_head offsets_search_list;
+	/* Final offsets search array */
+	struct offsets_lookup_table offsets_search;
 
 	STRUCT_GETINFO info;
 	STRUCT_GET_ENTRIES *entries;
@@ -597,31 +600,35 @@ static int iptcc_chain_index_delete_chain(struct chain_head *c, TC_HANDLE_T h)
 /* Create offsets lookup table from the chunk list */
 static int iptcc_offsets_index_create(TC_HANDLE_T h)
 {
-	struct offsets_create_chunk * chunk;
-	unsigned int total_number=0;
+	struct offsets_chunk *ch;
+	unsigned int total_number = 0;
+	unsigned int i = 0;
 
 	/* First pass: count non-empty chunks and set their ranges */
-	list_for_each_entry(chunk, &h->offsets_create_list, list) {
-		if (chunk->num_entries>0) {
+	list_for_each_entry(ch, &h->offsets_search_list, list) {
+		if (ch->num_entries > 0) {
 			total_number++;
-			chunk->head_offset = chunk->entries[0]->head_offset;
-			chunk->foot_offset = chunk->entries[chunk->num_entries-1]->foot_offset;
+			ch->first_offset =
+				ch->entries[0]->head_offset;
+			ch->last_offset =
+				ch->entries[ch->num_entries - 1]->foot_offset;
 		}
 	}
 
 	/* No chains->nothing to assign */
-	if (total_number==0)
+	if (total_number == 0)
 		return 1;
 
-	h->offsets_search.entries = malloc(sizeof(struct offsets_create_chunk *)*total_number);
+	h->offsets_search.entries =
+		malloc(sizeof(struct offsets_chunk *)*total_number);
+
 	if (!h->offsets_search.entries)
 		return -ENOMEM;
 
 	/* Second pass: fill chunk table */
-	unsigned int i=0;
-	list_for_each_entry(chunk, &h->offsets_create_list, list)
-		if (chunk->num_entries>0)
-			h->offsets_search.entries[i++] = chunk;
+	list_for_each_entry(ch, &h->offsets_search_list, list)
+		if (ch->num_entries > 0)
+			h->offsets_search.entries[i++] = ch;
 
 	h->offsets_search.num_entries = total_number;
 
@@ -631,17 +638,17 @@ static int iptcc_offsets_index_create(TC_HANDLE_T h)
 /* Free offsets lookup table AND the individual chunks */
 static void iptcc_offsets_index_free(TC_HANDLE_T h)
 {
-	struct offsets_create_chunk * chunk, *tmp;
+	struct offsets_chunk *ch, *tmp;
 
-	if (h->offsets_search.num_entries>0) {
+	if (h->offsets_search.num_entries > 0) {
 		free(h->offsets_search.entries);
-		h->offsets_search.num_entries=0;
+		h->offsets_search.num_entries = 0;
 	}
 
-	list_for_each_entry_safe(chunk, tmp, &h->offsets_create_list, list)
-		free(chunk);
+	list_for_each_entry_safe(ch, tmp, &h->offsets_search_list, list)
+		free(ch);
 
-	INIT_LIST_HEAD(&h->offsets_create_list);
+	INIT_LIST_HEAD(&h->offsets_search_list);
 }
 
 
@@ -721,7 +728,7 @@ iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
 	low = 0; \
 	high = size; \
 	result = -1; \
-	while(low<=high) \
+	while(low <= high) \
 	{ \
 		mid = (low + high) / 2; \
 		if ((array)[mid]->left > value) \
@@ -740,25 +747,31 @@ static struct chain_head *
 iptcc_find_chain_by_offset_fast(TC_HANDLE_T handle, unsigned int offset)
 {
 	int low,high,mid,result;
+	struct chain_head **chunk_chains;
+	unsigned int num_entries;
 
-	if (handle->offsets_search.num_entries==0)
+	if (handle->offsets_search.num_entries == 0)
 		return NULL;
 
 	/* Find the chunk that could contain an appropriate interval */
-	binary_array_range_search(offset, handle->offsets_search.entries, head_offset, foot_offset,
-			handle->offsets_search.num_entries, low, high, mid, result);
+	binary_array_range_search(offset, handle->offsets_search.entries,
+			first_offset, last_offset,
+			handle->offsets_search.num_entries,
+			low, high, mid, result);
 
-	if (result<0)
+	if (result < 0)
 		return NULL;
 
 	/* Find chain in chunk */
-	struct chain_head ** chunk_chains =  handle->offsets_search.entries[result]->entries;
-	unsigned int num_entries = handle->offsets_search.entries[result]->num_entries;
+	chunk_chains = handle->offsets_search.entries[result]->entries;
+	num_entries = handle->offsets_search.entries[result]->num_entries;
 
-	binary_array_range_search(offset, chunk_chains, head_offset, foot_offset,
-			num_entries, low, high, mid, result);
+	binary_array_range_search(offset, chunk_chains,
+			head_offset, foot_offset,
+			num_entries,
+			low, high, mid, result);
 
-	if (result<0)
+	if (result < 0)
 		return NULL;
 
 	return chunk_chains[result];
@@ -862,11 +875,11 @@ static void iptcc_delete_rule(struct rule_head *r)
 /* Allocate another offsets chunk and append it to list */
 static int __iptcc_p_new_offsets_chunk(TC_HANDLE_T h)
 {
-	struct offsets_create_chunk * new_chunk = malloc(sizeof(struct offsets_create_chunk));
+	struct offsets_chunk *new_chunk = malloc(sizeof(struct offsets_chunk));
 
 	if (new_chunk) {
-		new_chunk->num_entries=0;
-		list_add_tail(&new_chunk->list, &h->offsets_create_list);
+		new_chunk->num_entries = 0;
+		list_add_tail(&new_chunk->list, &h->offsets_search_list);
 		return 1;
 	}
 	return -1;
@@ -878,6 +891,8 @@ static int __iptcc_p_new_offsets_chunk(TC_HANDLE_T h)
  * to be called from specific places within the parser */
 static int __iptcc_p_del_policy(TC_HANDLE_T h, unsigned int num)
 {
+	struct offsets_chunk *occ;
+
 	if (h->chain_iterator_cur) {
 		/* policy rule is last rule */
 		struct rule_head *pr = (struct rule_head *)
@@ -899,17 +914,18 @@ static int __iptcc_p_del_policy(TC_HANDLE_T h, unsigned int num)
 		h->chain_iterator_cur->foot_offset = pr->offset;
 
 		/* do we need a new offsets chunk? */
-		if (list_empty(&h->offsets_create_list) ||
-			list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list)->num_entries
-			>=OFFSETS_CHUNK_SIZE)
-			if (__iptcc_p_new_offsets_chunk(h)<0)
+		if (list_empty(&h->offsets_search_list) ||
+			list_entry(h->offsets_search_list.prev,
+				struct offsets_chunk, list)->num_entries
+			>= OFFSETS_CHUNK_SIZE)
+			if (__iptcc_p_new_offsets_chunk(h) < 0)
 				return -1;
 
 		/* add next chain to the current offsets chunk */
-		struct offsets_create_chunk * occ =
-			list_entry(h->offsets_create_list.prev, struct offsets_create_chunk, list);
+		occ = list_entry(h->offsets_search_list.prev,
+				struct offsets_chunk, list);
 
-		occ->entries[occ->num_entries++]=h->chain_iterator_cur;
+		occ->entries[occ->num_entries++] = h->chain_iterator_cur;
 
 		/* delete rule from cache */
 		iptcc_delete_rule(pr);
@@ -1012,7 +1028,7 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 		/* This is the ERROR node at the end of the chain */
 		DEBUGP_C("%u:%u: end of table:\n", *num, offset);
 
-		if ((__iptcc_p_del_policy(h, *num))<0) {
+		if ((__iptcc_p_del_policy(h, *num)) < 0) {
 			errno = -ENOMEM;
 			return -1;
 		}
@@ -1035,7 +1051,7 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 		}
 		h->num_chains++; /* New user defined chain */
 
-		if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+		if ((__iptcc_p_add_chain(h, c, offset, num)) < 0) {
 			errno = -ENOMEM;
 			return -1;
 		}
@@ -1052,7 +1068,7 @@ static int cache_add_entry(STRUCT_ENTRY *e,
 
 		c->hooknum = builtin;
 
-		if ((__iptcc_p_add_chain(h, c, offset, num))<0) {
+		if ((__iptcc_p_add_chain(h, c, offset, num)) < 0) {
 			errno = -ENOMEM;
 			return -1;
 		}
@@ -1376,7 +1392,7 @@ alloc_handle(const char *tablename, unsigned int size, unsigned int num_rules)
 	strcpy(h->entries->name, tablename);
 	h->entries->size = size;
 
-	INIT_LIST_HEAD(&h->offsets_create_list);
+	INIT_LIST_HEAD(&h->offsets_search_list);
 
 	return h;
 
-- 
1.5.4.3

Patches solving the same issue!?

[Jesper Dangaard Brouer]

I can see from the list that Thomas Jacob <jacob@internet24.de>, and I
have just posted patches solving the same issue.

I promised Patrick that I would work on this issue, and I did.

Its running on our production servers, and I planned to release the
patch today as it has proven stable on production.  I guess Thomas was
just slightly faster than me ;-)

It was actually already released in the CPAN module IPTables::libiptc
(ver.0.08 released 2008-06-16).


We both use binary search, but with two slightly different approaches.

- My patch uses the existing data structure, and the existing
  algorithm for binary searching.

- Thomas builds a new data structure and implements a new binary
  search algorithm.

I must give Thomas that this binary search algo (taken from wikipedia)
is much more compact than the existing one.

Guess I cannot judge what patch is the best, as I'm biased...

Re: Patches solving the same issue!?

[Thomas Jacob]

[-- Attachment #1: Type: text/plain, Size: 1870 bytes --]

Oops, sorry about that, I did notice your initial
set of speed up patches (that's why I was enthusiastically playing
around with large rule sets and became aware of the issue
in the first place), but evidently I didn't follow the
related thread very closely.

I am not familiar enough with the iptables code to decide
whether or not chains are always sorted by name in the kernel,
and thus will be sorted if you read them back, but if that's
the case, of course your method is better, as long as that's
always the case...

To be honest, I didn't really understand the chain_index code ;)

   
On Wed, Jul 02, 2008 at 10:57:31PM +0200, Jesper Dangaard Brouer wrote:
> 
> I can see from the list that Thomas Jacob <jacob@internet24.de>, and I
> have just posted patches solving the same issue.
> 
> I promised Patrick that I would work on this issue, and I did.
> 
> Its running on our production servers, and I planned to release the
> patch today as it has proven stable on production.  I guess Thomas was
> just slightly faster than me ;-)
> 
> It was actually already released in the CPAN module IPTables::libiptc
> (ver.0.08 released 2008-06-16).
> 
> 
> We both use binary search, but with two slightly different approaches.
> 
> - My patch uses the existing data structure, and the existing
>   algorithm for binary searching.
> 
> - Thomas builds a new data structure and implements a new binary
>   search algorithm.
> 
> I must give Thomas that this binary search algo (taken from wikipedia)
> is much more compact than the existing one.
> 
> Guess I cannot judge what patch is the best, as I'm biased...
> 
> --
> To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html

[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Patches solving the same issue!?

[Thomas Jacob]

[-- Attachment #1: Type: text/plain, Size: 2154 bytes --]

As addendum, your code runs just as fast, maybe
even a tad faster as mine, and obviously uses
less memory. Oh well...

On Wed, Jul 02, 2008 at 11:47:36PM +0200, Thomas Jacob wrote:
> Oops, sorry about that, I did notice your initial
> set of speed up patches (that's why I was enthusiastically playing
> around with large rule sets and became aware of the issue
> in the first place), but evidently I didn't follow the
> related thread very closely.
> 
> I am not familiar enough with the iptables code to decide
> whether or not chains are always sorted by name in the kernel,
> and thus will be sorted if you read them back, but if that's
> the case, of course your method is better, as long as that's
> always the case...
> 
> To be honest, I didn't really understand the chain_index code ;)
> 
>    
> On Wed, Jul 02, 2008 at 10:57:31PM +0200, Jesper Dangaard Brouer wrote:
> > 
> > I can see from the list that Thomas Jacob <jacob@internet24.de>, and I
> > have just posted patches solving the same issue.
> > 
> > I promised Patrick that I would work on this issue, and I did.
> > 
> > Its running on our production servers, and I planned to release the
> > patch today as it has proven stable on production.  I guess Thomas was
> > just slightly faster than me ;-)
> > 
> > It was actually already released in the CPAN module IPTables::libiptc
> > (ver.0.08 released 2008-06-16).
> > 
> > 
> > We both use binary search, but with two slightly different approaches.
> > 
> > - My patch uses the existing data structure, and the existing
> >   algorithm for binary searching.
> > 
> > - Thomas builds a new data structure and implements a new binary
> >   search algorithm.
> > 
> > I must give Thomas that this binary search algo (taken from wikipedia)
> > is much more compact than the existing one.
> > 
> > Guess I cannot judge what patch is the best, as I'm biased...
> > 
> > --
> > To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
> > the body of a message to majordomo@vger.kernel.org
> > More majordomo info at  http://vger.kernel.org/majordomo-info.html



[-- Attachment #2: Digital signature --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Patches solving the same issue!?

[Jesper Dangaard Brouer]

On Wed, 2 Jul 2008, Thomas Jacob wrote:

> I am not familiar enough with the iptables code to decide
> whether or not chains are always sorted by name in the kernel,
> and thus will be sorted if you read them back, but if that's
> the case, of course your method is better, as long as that's
> always the case...

It _is_ always the case that chains are sorted by name in the kernel, as 
libiptc puts them in sorted.

Thats also what the chain_index code depends upon (although I have build 
in a safe guard that sorts them if they are not).  There is also a safe 
guard for the offset binary search, but that simply reverts to the old 
(_slow_) search scheme.

If Patrick might want to change this in the future, he should consider 
your solution over mine.


> To be honest, I didn't really understand the chain_index code ;)

It actually some what resembels your idea, with arrays of chain_head 
pointers.  That points to the original chain list.  I don't build "chunks" 
as I don't want to find an exact match, just a place in the chain list to 
start the list search. This is choosen because I need to support chains 
deletes and creates.

Its more complicated because it needs to support chain deletes and 
creates.  And needs to scale, when many chains are added, which requires 
rebuilding the chain_index, but not too often...


BTW, I like your coding style, although it more compact that I would 
choose to write it...

Hilsen
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------

Re: Patches solving the same issue!?

[Thomas Jacob]

[-- Attachment #1: Type: text/plain, Size: 927 bytes --]

On Thu, 2008-07-03 at 12:53 +0200, Jesper Dangaard Brouer wrote:
> Thats also what the chain_index code depends upon (although I have build 
> in a safe guard that sorts them if they are not).  There is also a safe 
> guard for the offset binary search, but that simply reverts to the old 
> (_slow_) search scheme.

I see, so that's no problem either =>

 if (strcmp(c->name, ctail->name) > 0 ||
                    iptcc_is_builtin(ctail))
                        list_add_tail(&c->list, &h->chains);
                else {
                        iptc_insert_chain(h, c);/* Was not sorted */
                        h->sorted_offsets = 0;

The skip-list-like search infrastructure is also quite nice and
integrates well with the current code, once one understands what it does
anyway. So there is really no reason as to why my patch should be
preferred over yours ;-)


     Regards,
          Thomas

[-- Attachment #2: This is a digitally signed message part --]
[-- Type: application/pgp-signature, Size: 189 bytes --]

Re: Patches solving the same issue!?

[Patrick McHardy]

Jesper Dangaard Brouer wrote:
> I can see from the list that Thomas Jacob <jacob@internet24.de>, and I
> have just posted patches solving the same issue.
> 
> I promised Patrick that I would work on this issue, and I did.

Sorry, I'm forgetful sometimes :)

> Its running on our production servers, and I planned to release the
> patch today as it has proven stable on production.  I guess Thomas was
> just slightly faster than me ;-)
> 
> It was actually already released in the CPAN module IPTables::libiptc
> (ver.0.08 released 2008-06-16).
> 
> 
> We both use binary search, but with two slightly different approaches.
> 
> - My patch uses the existing data structure, and the existing
>   algorithm for binary searching.
> 
> - Thomas builds a new data structure and implements a new binary
>   search algorithm.
> 
> I must give Thomas that this binary search algo (taken from wikipedia)
> is much more compact than the existing one.
> 
> Guess I cannot judge what patch is the best, as I'm biased...

Me neither since you guys did all the work :)

Please work this out among yourselves. I think we should just pick
the faster one since both don't look very intrusive.

Re: Patches solving the same issue!?

[Thomas Jacob]

On Thu, 2008-07-03 at 14:42 +0200, Patrick McHardy wrote:
> Please work this out among yourselves. I think we should just pick
> the faster one since both don't look very intrusive.

Well, Jesper's version doesn't build any extra data-structures,
so you save time&space there, and the offsets stuff is really
only needed once, so the chain_index rebuilding penalty
doesn't play a role.

And since about 2/3s of time it takes to load my 50k Chains now
is system time, it's probably irrelevant whether
 0 + O(n * (log(n/40)+40)) is sometimes larger than O(n+n/1024) +
O(log(n)).

Mine vs. Jesper's:

iptables-restore  (50k chains, 120k rules), average for 10 runs:

User: 2.558 s - System: 8.672 s - Total : 11.222 s
vs
User: 2.622 s - System: 8.520 s - Total : 11.140 s


iptables -vnL SOMECHAIN (2 entries, with the above ruleset in kernel),
 average for 20 runs

User: .094 s - System: .363 s - Total : .455 s
vs
User: .085 s - System: .389 s - Total : .472 s

Those numbers are all within the standard deviations of each other,
so there is no difference for practical purposes, I think :-)

I would use Jesper's patch.

Re: Patches solving the same issue!?

[Patrick McHardy]

Thomas Jacob wrote:
> On Thu, 2008-07-03 at 14:42 +0200, Patrick McHardy wrote:
>> Please work this out among yourselves. I think we should just pick
>> the faster one since both don't look very intrusive.
> 
> Well, Jesper's version doesn't build any extra data-structures,
> so you save time&space there, and the offsets stuff is really
> only needed once, so the chain_index rebuilding penalty
> doesn't play a role.
> 
> And since about 2/3s of time it takes to load my 50k Chains now
> is system time, it's probably irrelevant whether
>  0 + O(n * (log(n/40)+40)) is sometimes larger than O(n+n/1024) +
> O(log(n)).
> 
> Mine vs. Jesper's:
> 
> iptables-restore  (50k chains, 120k rules), average for 10 runs:
> 
> User: 2.558 s - System: 8.672 s - Total : 11.222 s
> vs
> User: 2.622 s - System: 8.520 s - Total : 11.140 s
> 
> 
> iptables -vnL SOMECHAIN (2 entries, with the above ruleset in kernel),
>  average for 20 runs
> 
> User: .094 s - System: .363 s - Total : .455 s
> vs
> User: .085 s - System: .389 s - Total : .472 s
> 
> Those numbers are all within the standard deviations of each other,
> so there is no difference for practical purposes, I think :-)
> 
> I would use Jesper's patch.

OK, thanks for the numbers and sorting this out so peacefully :)

Re: Patches solving the same issue!?

[Jesper Dangaard Brouer]

On Thu, 3 Jul 2008, Patrick McHardy wrote:

> Thomas Jacob wrote:
>>
>>  I would use Jesper's patch.
>
> OK, thanks for the numbers and sorting this out so peacefully :)

Thanks, Thomas! :-)

Cheers,
   Jesper Brouer

--
-------------------------------------------------------------------
MSc. Master of Computer Science
Dept. of Computer Science, University of Copenhagen
Author of http://www.adsl-optimizer.dk
-------------------------------------------------------------------