[Click] Multithreaded HashMaps

[Eddie Kohler]

Hi Kevin,

Thanks very much for this patch.  Definitely a problem -- that's why 
IPRewriter elements had defined their own HashMap_Arenas.

But the problem is the basic design.  The more I think about it the more 
pointless it seems to share freelists.  Also the many find(), findp(), 
find_force(), find_pair_force() methods annoy.

I've checked in a new template, HashTable, which will replace HashMap.  Unlike 
HashMap it is closer to standard behavior, faster, and documented.

http://www.read.cs.ucla.edu/click/doxygen/classHashTable.html

Most of Click has been switched to use HashTable.  Regression tests run 
successfully, but of course there could be problems.  Let us know.

Eddie


springbo at cs.wisc.edu wrote:
> Hello,
> 
> The freelist handling for HashMaps is currently not thread-safe. For
> multithreaded applications in the case two elements are using the same
> HashMap_Arena it is possible for the HashMap_Arena's freelist (_free) to
> reach an inconsistent state. Kernel level click manifests this as a
> general protection fault.
> 
> Attached is an element (HashMapTest) which can be used to elict the bug.
> See hashmaptest.hh comments for details.
> 
> Also attached is a first pass solution for the problem. It simply adds
> locking to the HashMap_Arena class. This adds locking overhead but
> continues to allow multiple hashmaps to share freelists. Another potential
> solution would be to remove freelist sharing among hashmaps.
> 
> Thanks!
> Kevin Springborn
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click