Re: [PATCH 2/2] Fix scalability performance issue during initial ruleset parsing.

[Patrick McHardy <kaber@trash.net>]

Jesper Dangaard Brouer wrote:
>  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.

Nice work, and clever :) Applied, thanks.