RE: [PATCH] libiptc.c blob parser

["Paul C. Diem" <PCDiem@FoxValley.net>]

Sorry, I'm not familiar yet with submitting patches. I had to create a
second tree from the original tarball and build it in order to get diff
output that didn't list a bunch of unrelated files. Here's the diff -Nurp
output with the leading notices about changed images (ip6tables, iptables,
iptables-restore, etc) removed:

Paul C. Diem
PCDiem@FoxValley.net

diff -Nurp --exclude '*.o' --exclude '*.so' iptables-1.3.5/libiptc/libiptc.c
iptables-1.3.5-new/libiptc/libiptc.c
--- iptables-1.3.5/libiptc/libiptc.c	2006-01-30 02:43:09.000000000 -0600
+++ iptables-1.3.5-new/libiptc/libiptc.c	2006-06-23 20:37:53.000000000 -0500
@@ -307,6 +307,11 @@ static struct rule_head *iptcc_get_rule_
 static struct chain_head *
 iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
 {
+/*+PCD
+* Modification to use the offset to the chain entry in the ipt
+* entry comefrom field as loaded by iptcc_find_chain_by_offset.
+*/
+#if 0
 	struct list_head *pos;

 	if (list_empty(&handle->chains))
@@ -317,6 +322,11 @@ iptcc_find_chain_by_offset(TC_HANDLE_T h
 		if (offset >= c->head_offset && offset <= c->foot_offset)
 			return c;
 	}
+#else
+      STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char
*)handle->entries->entrytable + offset));
+      return (struct chain_head *)((char *)e + e->comefrom);
+#endif
+/*-PCD*/

 	return NULL;
 }
@@ -494,6 +504,12 @@ new_rule:
 		r->index = *num;
 		r->offset = offset;
 		memcpy(r->entry, e, e->next_offset);
+/*+PCD
+* Load the offset to the chain entry relative to the
+* ipt entry into the ipt entry comefrom field.
+*/
+              e->comefrom = (char *)h->chains.prev - (char *)e;
+/*-PCD*/
 		r->counter_map.maptype = COUNTER_MAP_NORMAL_MAP;
 		r->counter_map.mappos = r->index;

----------------------------------------------------------------------------
-----------------------------------------
-----Original Message-----
From: netfilter-devel-bounces@lists.netfilter.org
[mailto:netfilter-devel-bounces@lists.netfilter.org]On Behalf Of Jesper
Dangaard Brouer
Sent: Saturday, June 24, 2006 7:07 AM
To: Paul C. Diem
Cc: netfilter-devel@lists.netfilter.org
Subject: Re: [PATCH] libiptc.c blob parser


Hi Paul

To confirm, I have notized the same issus.  I wrote to Harald but he has
not responded yet. So, I guess I'll follow up on this one... Nice to hear
the you have solved the issue.

First of all, could you please produce a proper patch!? (diff -Nurp)
So that we can see whats going on...

Here is my post to Harald:
-------
Sent:  	 Mon 6/19/2006 16:14
Subject: Performance work on libiptc

Hi Harald

I hope you can help me out.  I have a performance issue with iptables
which I have tracked down to the libiptc parsing.

I would like to solve it, but need some help with the data structures.

  There is a scalability/performance issue in libiptc.c, when parsing
  the ruleset blob.  The problem lies in the "Second pass" (of func
  parse_table) where the userchain jump targets are fixed/corrected.

  The "Second pass" loop has a bad worstcase run time of O(C*R).

  For each rule "R" with a IPTCC_R_JUMP target, func
  iptcc_find_chain_by_offset searches through the chain list "C"
  (worstcase hitting the last one).

  In my real life production system I have R=4492 and C=2238, giving a
  worstcase loop of 10.053.096.

Basically, we need to make "iptcc_find_chain_by_offset" smarter... do you
have any proposals?
------

I simply tracked down the problem using gprof.

gprof output:
+-----
Each sample counts as 0.000999001 seconds.
   %   cumulative   self              self     total
  time   seconds   seconds    calls  ms/call  ms/call  name
  77.99      0.20     0.20     4492     0.04     0.04
iptcc_find_chain_by_offset
  20.46      0.25     0.05     2238     0.02     0.02  iptc_insert_chain
   1.16      0.26     0.00    16218     0.00     0.00  cache_add_entry
   0.39      0.26     0.00        1     1.00   258.74  parse_table
   0.00      0.26     0.00    13982     0.00     0.00  iptcc_alloc_rule
   0.00      0.26     0.00     2239     0.00     0.00  __iptcc_p_del_policy
   0.00      0.26     0.00     2238     0.00     0.02  __iptcc_p_add_chain
   0.00      0.26     0.00     2238     0.00     0.00
iptcc_alloc_chain_head
   0.00      0.26     0.00     2238     0.00     0.00  iptcc_delete_rule
   0.00      0.26     0.00        1     0.00     0.00  add_command
   0.00      0.26     0.00        1     0.00     0.00  alloc_handle
   0.00      0.26     0.00        1     0.00     0.00  clear_rule_matches
   0.00      0.26     0.00        1     0.00   258.74  do_command
   0.00      0.26     0.00        1     0.00     0.00  find_target
   0.00      0.26     0.00        1     0.00     0.00  free_opts
   0.00      0.26     0.00        1     0.00     0.00  generic_opt_check
   0.00      0.26     0.00        1     0.00     0.00  iptc_create_chain
   0.00      0.26     0.00        1     0.00   258.74  iptc_init
   0.00      0.26     0.00        1     0.00     0.00  iptc_strerror
   0.00      0.26     0.00        1     0.00     0.00  iptcc_find_label
+-----

Cheers,
   Jesper Brouer

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


On Fri, 23 Jun 2006, Paul C. Diem wrote:

> We have about 30,000 mangle table rules in about 8,000 chains. iptc_init
> takes about 10 seconds just to load and parse the table. The problem is
the
> second parse phase that iterates through every chain and every rule
> searching for the offset of the target for every jump rule.
>
> I've applied the following small patch that loads the offset of the chain
> entry into the comefrom field of the first rule ipt entry in each
> user-defined chain in the first pass. This comefrom field is then used in
> the second pass to easily locate the target chain. This minor change has
> reduced the load time of our mangle table to 1 second.
>
> Paul C. Diem
> PCDiem@FoxValley.net
>
> 309a310,314
>> /*+PCD
>> * Modification to use the offset to the chain entry in the ipt
>> * entry comefrom field as loaded by iptcc_find_chain_by_offset.
>> */
>> #if 0
> 319a325,329
>> #else
>> 	STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char *)handle->entries->entrytable
> + offset));
>> 	return (struct chain_head *)((char *)e + e->comefrom);
>> #endif
>> /*-PCD*/
> 496a507,512
>> /*+PCD
>> * Load the offset to the chain entry relative to the
>> * ipt entry into the ipt entry comefrom field.
>> */
>> 		e->comefrom = (char *)h->chains.prev - (char *)e;
>> /*-PCD*/
>
>



--
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.394 / Virus Database: 268.9.3/374 - Release Date: 6/23/2006