On Tue, Mar 04, 2014 at 04:21:51PM +0100, Patrick McHardy wrote: > The hash set type is very broken and was never meant to be merged in this > state. Missing RCU synchronization on element removal, leaking chain > refcounts when used as a verdict map, races during lookups, a fixed table > size are probably just some of the problems. Luckily it is currently > never chosen by the kernel when the rbtree type is also available. > > Rewrite it to be usable. > > The new implementation supports automatic hash table resizing using RCU, > based on Paul McKenney's and Josh Triplett's algorithm "Optimized Resizing > For RCU-Protected Hash Tables" described in [1]. > > Resizing doesn't require a second list head in the elements, it works by > chosing a hash function that remaps elements to a predictable set of buckets, > only resizing by integral factors and > > - during expansion: linking new buckets to the old bucket that contains > elements for any of the new buckets, thereby creating imprecise chains, > then incrementally seperating the elements until the new buckets only > contain elements that hash directly to them. > > - during shrinking: linking the hash chains of all old buckets that hash > to the same new bucket to form a single chain. > > Expansion requires at most the number of elements in the longest hash chain > grace periods, shrinking requires a single grace period. > > Due to the requirement of having hash chains/elements linked to multiple > buckets during resizing, homemade single linked lists are used instead of > the existing list helpers, that don't support this in a clean fashion. > As a side effect, the amount of memory required per element is reduced by > one pointer. > > Expansion is triggered when the load factors exceeds 75%, shrinking when > the load factor goes below 30%. Both operations are allowed to fail and > will be retried on the next insertion or removal if their respective > conditions still hold. Applied, thanks Patrick. -- 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
