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@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
