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... -- 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
