Re: [PATCH] netfilter: use idr instead of list to speed up packet lookup by id

[Patrick McHardy <kaber@trash.net>]

Eric Dumazet wrote:
> Le mercredi 07 avril 2010 à 13:48 +0200, Patrick McHardy a écrit :
>> Changli Gao wrote:
>>> use idr instead of list to speed up packet lookup by id.
>>>
>>> The current implementations of nfnetlink_queue, ip_queue and ip6_queue
>>> are all use list to save the packets queued. If the verdicts aren't
>>> received in order, the lookup for the corresponding packets isn't
>>> efficient. As the ids is generated and maintained in kernel, we can use
>>> idr to speed up the lookup. The side effect of this patch is fixing the
>>> potential id overlap in nfnetlink_queue.
>> I'm interested in how this affects performance for the vast majority
>> of users, which process messages in order. A simple hash table looks
>> like a better choice here since we know the maximum number of entries
>> in advance and also could have the user specify the desired hash size.
> 
> Yes, a hash table would be good, but cost 8 bytes per slot.
> 
> Changli, did you tried RBL tree ? It might fit better both your needs
> and Patrick concerns...

RB-trees OTOH cost 8 bytes extra per element. If we'd use a hash,
I think the size should be configurable by userspace and default
to 1 (simple list as used currently). That way only those people
actually processing packets out of order have to pay the price.
But an RB-tree would be fine too I guess.
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html