[iptables] libiptc: fix scalability performance issue during initial ruleset parsing

[Patrick McHardy]

Gitweb:		http://git.netfilter.org/cgi-bin/gitweb.cgi?p=iptables.git;a=commit;h=4bae3f1001028ee283a5e1fcea4a561b0068f95d
commit 4bae3f1001028ee283a5e1fcea4a561b0068f95d
Author:     Jesper Dangaard Brouer <hawk at comx.dk>
AuthorDate: Thu Jul 3 20:31:42 2008 +0200
Commit:     Patrick McHardy <kaber at trash.net>
CommitDate: Thu Jul 3 20:31:42 2008 +0200

    libiptc: fix scalability performance issue during initial ruleset parsing
    
     Finding jump chains is slow 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 solution:
     in this patch is to speed up iptcc_find_chain_by_offset() by using
     binary search. Reducing complexity from O(C) to O(log C).
    
    Implementation:
     Its possible to use the same bsearch algorithm and data structure
     (chain_index), as used for chain name searching.
    
    How is that possible:
     One has to realize that the chains are both sorted by name and
     offsets, this is because the chains are already sorted in the ruleset
     from the kernel.
    
    Signed-off-by: Jesper Dangaard Brouer <hawk at comx.dk>
    Signed-off-by: Patrick McHardy <kaber at trash.net>

commit 526d3e138635e33773d1ca16477052a04f53f5bd
Author:     Jesper Dangaard Brouer <hawk at comx.dk>
AuthorDate: Thu Jul 3 20:29:34 2008 +0200
Commit:     Patrick McHardy <kaber at trash.net>
CommitDate: Thu Jul 3 20:29:34 2008 +0200

    libiptc: minor bugfix
    
    Minor bugfix, an extra check is needed if the tail element is a
    builtin chain, as builtin chains are not sorted.
    
    Signed-off-by: Jesper Dangaard Brouer <hawk at comx.dk>
    Signed-off-by: Patrick McHardy <kaber at trash.net>
       via  4bae3f1001028ee283a5e1fcea4a561b0068f95d (commit)
       via  526d3e138635e33773d1ca16477052a04f53f5bd (commit)
      from  55dffefc95151b5746a853c8ed71097d7b5a8575 (commit)

Those revisions listed above that are new to this repository have
not appeared on any other notification email; so we list those
revisions in full, below.

- Log -----------------------------------------------------------------
commit 4bae3f1001028ee283a5e1fcea4a561b0068f95d
Author: Jesper Dangaard Brouer <hawk at comx.dk>
Date:   Thu Jul 3 20:31:42 2008 +0200

    libiptc: fix scalability performance issue during initial ruleset parsing
    
     Finding jump chains is slow 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 solution:
     in this patch is to speed up iptcc_find_chain_by_offset() by using
     binary search. Reducing complexity from O(C) to O(log C).
    
    Implementation:
     Its possible to use the same bsearch algorithm and data structure
     (chain_index), as used for chain name searching.
    
    How is that possible:
     One has to realize that the chains are both sorted by name and
     offsets, this is because the chains are already sorted in the ruleset
     from the kernel.
    
    Signed-off-by: Jesper Dangaard Brouer <hawk at comx.dk>
    Signed-off-by: Patrick McHardy <kaber at trash.net>

commit 526d3e138635e33773d1ca16477052a04f53f5bd
Author: Jesper Dangaard Brouer <hawk at comx.dk>
Date:   Thu Jul 3 20:29:34 2008 +0200

    libiptc: minor bugfix
    
    Minor bugfix, an extra check is needed if the tail element is a
    builtin chain, as builtin chains are not sorted.
    
    Signed-off-by: Jesper Dangaard Brouer <hawk at comx.dk>
    Signed-off-by: Patrick McHardy <kaber at trash.net>

-----------------------------------------------------------------------

 libiptc/libiptc.c |  126 ++++++++++++++++++++++++++++++++++++++++++++++++-----
 1 files changed, 114 insertions(+), 12 deletions(-)
Minor bugfix, an extra check is needed if the tail element is a
builtin chain, as builtin chains are not sorted.

Signed-off-by: Jesper Dangaard Brouer <hawk at comx.dk>
Signed-off-by: Patrick McHardy <kaber at trash.net>

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index d0f51b4..ec5317b 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -819,7 +819,8 @@ static void __iptcc_p_add_chain(TC_HANDLE_T h, struct chain_head *c,
 		list_add_tail(&c->list, &h->chains);
 	else {
 		ctail = list_entry(tail, struct chain_head, list);
-		if (strcmp(c->name, ctail->name) > 0)
+		if (strcmp(c->name, ctail->name) > 0 ||
+		    iptcc_is_builtin(ctail))
 			list_add_tail(&c->list, &h->chains);/* Already sorted*/
 		else
 			iptc_insert_chain(h, c);/* Was not sorted */