Re: [PATCH] nfnetlink_queue: use hash table to speed up entry lookup

[Patrick McHardy <kaber@trash.net>]

Changli Gao wrote:
> use hash table to speed up entry lookup
> 
> A hash table is used to speed up entry lookup when the verdicts aren't received
> in order. The size of hash table can be specified by NFQA_CFG_QUEUE_HTBLSIZ.
> Its default value is 1. Reciprocal division is used to lower the cost of
> division, and the entry IDs are generated carefully to get fair entry
> distribution in the buckets of the hash table.

> +static u32 __get_uniq_id(struct nfqnl_instance *queue)
> +{
> +	u32 i;
> +
> +	for (i = 0; i < INT_MAX; i++) {
> +		queue->id_sequence += queue->id_increment;
> +		if (queue->id_sequence >= queue->id_limit) {
> +			if (++queue->id_offset >= queue->id_increment)
> +				queue->id_offset = 0;
> +			queue->id_sequence = queue->id_offset;
> +		}
> +		if (__find_entry(queue, queue->id_sequence) == NULL)
> +			return queue->id_sequence;

No freaking way. So you want to lower the overhead for your case
any everyone else has to pay the price? This means that every
existing user will now have to walk the entire queue of queued
packets for every new packet.

How about you start with something simple and try to optimize
later in case there are actually performance problems? That
probably means use a simple modulo operation for cases where
the hash table size is > 1.