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>
1 file changed