summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorJesper Dangaard Brouer <hawk@comx.dk>2007-11-28 08:40:26 +0000
committerPatrick McHardy <kaber@trash.net>2007-11-28 08:40:26 +0000
commitd8cb787ab44e9d2de4fd3b04fcaa370c9918fc5d (patch)
treee4824f9e346db25ff0c1fc90a2c02fda7a454fd3
parente29da4e9610ab376593e50a44efba874a533dfe0 (diff)
iptables/libiptc perf issue: Sorting chain during pull-out
Performance optimize scalability issue: Sorting chain during pull-out give worst-case runtime O(Chains2). When pulling out the blob, every chain name is inserted alphabetically into a linked list (by function iptc_insert_chain()). The problem with this approach is that the chain names delivered in the blob is already sorted (as we push it back to the kernel sorted). This cause chain parsing to always process every element in the chain list and finish with a tail add. Causing worst-case runtime O(C2/2) for alphabetically sorting of chains. The patch solves this by only calling iptc_insert_chain() when creating new chains. Signed-off-by: Jesper Dangaard Brouer <hawk@comx.dk>
-rw-r--r--libiptc/libiptc.c6
1 files changed, 3 insertions, 3 deletions
diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index 472b81e0..e7ffb01b 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -420,8 +420,8 @@ static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
c->head_offset = offset;
c->index = *num;
- iptc_insert_chain(h, c);
-
+ list_add_tail(&c->list, &h->chains); /* Its already sorted */
+
h->chain_iterator_cur = c;
}
@@ -1791,7 +1791,7 @@ TC_CREATE_CHAIN(const IPT_CHAINLABEL chain, TC_HANDLE_T *handle)
}
DEBUGP("Creating chain `%s'\n", chain);
- list_add_tail(&c->list, &(*handle)->chains);
+ iptc_insert_chain(*handle, c); /* Insert sorted */
set_changed(*handle);