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@comx.dk>
Signed-off-by: Patrick McHardy <kaber@trash.net>

0 files changed, 0 insertions, 0 deletions