From: "Paul C. Diem" Subject: RE: [PATCH] libiptc.c blob parser Date: Sat, 24 Jun 2006 10:57:50 -0500 Message-ID: References: Mime-Version: 1.0 Content-Type: text/plain; charset="windows-1250" Content-Transfer-Encoding: 7bit Cc: netfilter-devel@lists.netfilter.org Return-path: To: "Jesper Dangaard Brouer" In-Reply-To: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Sender: netfilter-devel-bounces@lists.netfilter.org Errors-To: netfilter-devel-bounces@lists.netfilter.org List-Id: netfilter-devel.vger.kernel.org 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