iptables/libiptc perf issue: Finding jump chains is suboptimal
PATCH 2/2 iptables/libiptc perf issue: Finding jump chains is suboptimal
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).
--- libiptc/libiptc.c | 23 +++++++++++++++++++---- 1 files changed, 19 insertions(+), 4 deletions(-)
libiptc/libiptc.c +19 -4
@@ -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;
Quoted 16 lines · Jesper Dangaard Brouer
Performance optimize scalability issue:
Finding jump chains is suboptimalO(Chain*Rules).libiptc/libiptc.c +0
-2@@ -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 ;
libiptc/libiptc.c static struct rule_head *iptcc_get_rule_num_reverse(struct chain_head *c, · line 320
Quoted 10 lines
libiptc/libiptc.c +8
-2-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.