Re: [PATCH 2/2] iptables/libiptc perf issue: Finding jump chains is suboptimal

[Patrick McHardy <kaber@trash.net>]

Jesper Dangaard Brouer wrote:
> Performance optimize scalability issue:
>    Finding jump chains is suboptimal O(Chain*Rules).
> 
> diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
> index e7ffb01..e611178 100644
> --- a/libiptc/libiptc.c
> +++ b/libiptc/libiptc.c
> @@ -307,13 +307,20 @@ static struct rule_head *iptcc_get_rule_num_reverse(struct chain_head *c,
>  static struct chain_head *
>  iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
>  {
> -	struct list_head *pos;
> -
>  	if (list_empty(&handle->chains))
>  		return NULL;
>  
> -	list_for_each(pos, &handle->chains) {
> -		struct chain_head *c = list_entry(pos, struct chain_head, list);
> +	/* Find the entry pointed to by offset */
> +	STRUCT_ENTRY * e = iptcb_offset2entry(handle, offset);
> +
> +	/* When parsing the blob (in cache_add_entry), the entry
> +	   field comefrom has been modified to contain a pointer
> +	   to the chain it belongs to.
> +	*/
> +	struct chain_head *c = (struct chain_head *)e->comefrom;


As you mentioned in your other mail, this unfortunately doesn't
work on 64 bit since comefrom is an unsigned int and thus can't
hold a pointer. What might work (though pretty ugly) is splitting
up the pointer between nfcache and comefrom. This might need some
changes to the deletion code to make sure nfcache is not compared
on deletion.