[PATCH 2/2] iptables/libiptc perf issue: Finding jump chains is suboptimal

[PATCH 2/2] iptables/libiptc perf issue: Finding jump chains is suboptimal

[Jesper Dangaard Brouer]

Performance optimize scalability issue:
   Finding jump chains is suboptimal O(Chain*Rules).

The problem is that the chain list is searched lineary for each rule
with a jump target.

The problem lies in the "second pass" (of function parse_table) where
the userchain jump targets are found. For each rule "R" with a
IPTCC_R_JUMP target, function iptcc_find_chain_by_offset searches
through the chains "C" in the chain list (worst-case hitting the last one).

The "second pass" loop has a bad worst-case run time of O(C*R).

The solution idea is based upon Paul C. Diem's patch.

The patch solves this by using the blob data structure as a kind of
hash table.  The "comefrom" field of the "entry" struct, is used to
store a pointer to chain it belongs to.  Modifying the "entry" struct
in the blob, should not pose a problem, because its modified after a
copy of it have been stored in rule->entry.

In cache_add_entry(): is the "comefrom" field of the "entry" struct
modified.

In iptcc_find_chain_by_offset(): is the lineary search replaced by a
direct lookup that returns the chain pointer O(1).

Cc: Paul C. Diem <PCDiem@FoxValley.net>
Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
---
 libiptc/libiptc.c |   23 +++++++++++++++++++----
 1 files changed, 19 insertions(+), 4 deletions(-)

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index e7ffb01..e611178 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -307,13 +307,20 @@ static struct rule_head *iptcc_get_rule_num_reverse(struct chain_head *c,
 static struct chain_head *
 iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
 {
-	struct list_head *pos;
-
 	if (list_empty(&handle->chains))
 		return NULL;
 
-	list_for_each(pos, &handle->chains) {
-		struct chain_head *c = list_entry(pos, struct chain_head, list);
+	/* Find the entry pointed to by offset */
+	STRUCT_ENTRY * e = iptcb_offset2entry(handle, offset);
+
+	/* When parsing the blob (in cache_add_entry), the entry
+	   field comefrom has been modified to contain a pointer
+	   to the chain it belongs to.
+	*/
+	struct chain_head *c = (struct chain_head *)e->comefrom;
+
+	if (c) {
+		/* Extra verifying step*/
 		if (offset >= c->head_offset && offset <= c->foot_offset)
 			return c;
 	}
@@ -494,6 +501,14 @@ new_rule:
 		r->index = *num;
 		r->offset = offset;
 		memcpy(r->entry, e, e->next_offset);
+
+		/*
+		  Modify the blob entry to contain a pointer to the
+		  chain it belongs to.  Needed later to resolve jump
+		  targets faster (used in iptcc_find_chain_by_offset)
+		*/
+		e->comefrom = (unsigned int)h->chain_iterator_cur;
+
 		r->counter_map.maptype = COUNTER_MAP_NORMAL_MAP;
 		r->counter_map.mappos = r->index;
 

Re: [PATCH 2/2] iptables/libiptc perf issue: Finding jump chains is suboptimal

[Patrick McHardy]

Jesper Dangaard Brouer wrote:
> Performance optimize scalability issue:
>    Finding jump chains is suboptimal O(Chain*Rules).
> 
> diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
> index e7ffb01..e611178 100644
> --- a/libiptc/libiptc.c
> +++ b/libiptc/libiptc.c
> @@ -307,13 +307,20 @@ static struct rule_head *iptcc_get_rule_num_reverse(struct chain_head *c,
>  static struct chain_head *
>  iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
>  {
> -	struct list_head *pos;
> -
>  	if (list_empty(&handle->chains))
>  		return NULL;
>  
> -	list_for_each(pos, &handle->chains) {
> -		struct chain_head *c = list_entry(pos, struct chain_head, list);
> +	/* Find the entry pointed to by offset */
> +	STRUCT_ENTRY * e = iptcb_offset2entry(handle, offset);
> +
> +	/* When parsing the blob (in cache_add_entry), the entry
> +	   field comefrom has been modified to contain a pointer
> +	   to the chain it belongs to.
> +	*/
> +	struct chain_head *c = (struct chain_head *)e->comefrom;


As you mentioned in your other mail, this unfortunately doesn't
work on 64 bit since comefrom is an unsigned int and thus can't
hold a pointer. What might work (though pretty ugly) is splitting
up the pointer between nfcache and comefrom. This might need some
changes to the deletion code to make sure nfcache is not compared
on deletion.