libiptc.c blob parser
PATCH 1/1 libiptc.c blob parser
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
[email protected]
309a310,314
Quoted 5 lines
/*+PCD
* Modification to use the offset to the chain entry in the ipt
* entry comefrom field as loaded byiptcc_find_chain_by_offset. */
#if 0
319a325,329
Quoted 2 lines
#else STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char *)handle->entries->entrytable
+ offset));
Quoted 3 lines
return (struct chain_head *)((char *)e + e->comefrom);#endif
/*-PCD*/
496a507,512
Quoted 6 lines
/*+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*/
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
-------------------------------------------------------------------
Quoted 36 lines · Paul C. Diem
We have about 30,000 mangle table rules in about 8,000 chains.
iptc_inittakes 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
[email protected]309a310,314
Quoted 5 lines
/*+PCD
* Modification to use the offset to the chain entry in the ipt
* entry comefrom field as loaded byiptcc_find_chain_by_offset. */
#if 0319a325,329
Quoted 2 lines
#else STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char *)handle->entries->entrytable+ offset));
Quoted 3 lines
return (struct chain_head *)((char *)e + e->comefrom);#endif
/*-PCD*/496a507,512
Quoted 6 lines
/*+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*/
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
[email protected]
diff -Nurp --exclude '*.o' --exclude '*.so' iptables-1.3.5/libiptc/libiptc.c iptables-1.3.5-new/libiptc/libiptc.c
libiptc/libiptc.c +7 -0
@@ -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 hif (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: [email protected] [mailto:[email protected]]On Behalf Of Jesper Dangaard Brouer
Sent: Saturday, June 24, 2006 7:07 AM
To: Paul C. Diem
Cc: [email protected]
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.04iptcc_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
-------------------------------------------------------------------
Quoted 2 lines · Paul C. Diem
We have about 30,000 mangle table rules in about 8,000 chains.
iptc_inittakes about 10 seconds just to load and parse the table. The problem is
the
Quoted 18 lines
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
[email protected]309a310,314
Quoted 5 lines
/*+PCD
* Modification to use the offset to the chain entry in the ipt
* entry comefrom field as loaded byiptcc_find_chain_by_offset. */
#if 0
Quoted 16 lines
319a325,329
Quoted 2 lines
#else STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char *)handle->entries->entrytable+ offset));
Quoted 3 lines
return (struct chain_head *)((char *)e + e->comefrom);#endif
/*-PCD*/496a507,512
Quoted 6 lines
/*+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
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
[email protected]
diff -Nurp --exclude '*.d' iptables-1.3.5-org/libiptc/libiptc.c iptables-1.3.5/libiptc/libiptc.c
libiptc/libiptc.c +7 -0
@@ -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 hif (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: [email protected] [mailto:[email protected]]On Behalf Of Jesper Dangaard Brouer
Sent: Saturday, June 24, 2006 7:07 AM
To: Paul C. Diem
Cc: [email protected]
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.04iptcc_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
-------------------------------------------------------------------
Quoted 2 lines · Paul C. Diem
We have about 30,000 mangle table rules in about 8,000 chains.
iptc_inittakes about 10 seconds just to load and parse the table. The problem is
the
Quoted 18 lines
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
[email protected]309a310,314
Quoted 5 lines
/*+PCD
* Modification to use the offset to the chain entry in the ipt
* entry comefrom field as loaded byiptcc_find_chain_by_offset. */
#if 0
Quoted 16 lines
319a325,329
Quoted 2 lines
#else STRUCT_ENTRY * e = ((STRUCT_ENTRY *)((char *)handle->entries->entrytable+ offset));
Quoted 3 lines
return (struct chain_head *)((char *)e + e->comefrom);#endif
/*-PCD*/496a507,512
Quoted 6 lines
/*+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
Quoted 9 lines · Paul C. Diem
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_curhandle 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).
I'm not very familiar with that code, so I wonder how that affects the counter values if you specifially set them or use iptables-save --counters.
The counters field is used later on when committing. I went back to my original patch that loads/uses the self-relative offset to the chain entry into the comefrom. The only problem with that method is that it assumes the offset from the ipt blob entry to the chain entry is less than 2^31. This assume is fine on 32-bit architectures but I'm not sure about 64-but architectures.
Paul C. Diem
[email protected]
-----Original Message-----
From: [email protected] [mailto:[email protected]]On Behalf Of Patrick McHardy
Sent: Thursday, July 06, 2006 11:21 PM
To: Paul C. Diem
Cc: Jesper Dangaard Brouer; [email protected]
Subject: Re: [PATCH] libiptc.c blob parser
Quoted 1 line · Paul C. Diem
The patch I posted earlier assumed that the rule's chain was the last one
on
Quoted 1 line
the chain list and used the 32-bit comefrom field to hold the offset of
the
Quoted 4 lines
chain list entry.
This improved patch uses the
chain_iterator_curhandle field to more accurately get the chain, uses the counters field cast as a pointer to
hold
Quoted 2 lines
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
Quoted 1 line
it in).
I'm not very familiar with that code, so I wonder how that affects the counter values if you specifially set them or use iptables-save --counters.
--
No virus found in this incoming message.
Checked by AVG Free Edition.
Version: 7.1.394 / Virus Database: 268.9.9/382 - Release Date: 7/4/2006