* RE: [PATCH] libiptc.c blob parser
2006-06-24 12:06 ` Jesper Dangaard Brouer
@ 2006-06-24 15:57 ` Paul C. Diem
2006-06-24 21:09 ` Paul C. Diem
1 sibling, 0 replies; 6+ messages in thread
From: Paul C. Diem @ 2006-06-24 15:57 UTC (permalink / raw)
To: Jesper Dangaard Brouer; +Cc: netfilter-devel
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
^ permalink raw reply [flat|nested] 6+ messages in thread* RE: [PATCH] libiptc.c blob parser
2006-06-24 12:06 ` Jesper Dangaard Brouer
2006-06-24 15:57 ` Paul C. Diem
@ 2006-06-24 21:09 ` Paul C. Diem
2006-07-07 4:21 ` Patrick McHardy
1 sibling, 1 reply; 6+ messages in thread
From: Paul C. Diem @ 2006-06-24 21:09 UTC (permalink / raw)
To: Jesper Dangaard Brouer; +Cc: netfilter-devel
The patch I posted earlier assumed that the rule's chain was the last one on
the chain list and used the 32-bit comefrom field to hold the offset of the
chain list entry.
This improved patch uses the chain_iterator_cur handle field to more
accurately get the chain, uses the counters field cast as a pointer to hold
a pointer directly to the chain list entry and only bothers to load the
pointer for the first rule in each chain (since that's the only one we need
it in).
Paul C. Diem
PCDiem@FoxValley.net
diff -Nurp --exclude '*.d' iptables-1.3.5-org/libiptc/libiptc.c
iptables-1.3.5/libiptc/libiptc.c
--- iptables-1.3.5-org/libiptc/libiptc.c 2006-01-30 02:43:09.000000000 -0600
+++ iptables-1.3.5/libiptc/libiptc.c 2006-06-24 15:59:28.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 pointer to the chain entry in the ipt
+* entry counters 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 **)&e->counters;
+#endif
+/*-PCD*/
return NULL;
}
@@ -494,6 +504,16 @@ new_rule:
r->index = *num;
r->offset = offset;
memcpy(r->entry, e, e->next_offset);
+/*+PCD
+* Load a pointer to the chain entry into the ipt entry
+* counters field for use by iptcc_find_chain_by_offset
+* in the second pass.
+*/
+ if (h->chain_iterator_cur->num_rules == 0) {
+ struct chain_head ** chain_head_ptr_ptr = (struct chain_head
**)&e->counters;
+ *chain_head_ptr_ptr = h->chain_iterator_cur;
+ }
+/*-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
^ permalink raw reply [flat|nested] 6+ messages in thread