[Click] Multithreaded HashMaps

[Beyers Cronje]

Sweet! Thanks for this Eddie.

I've run into the freelist multithread issue in userland Click before and
ended up using g++'s implementation. For interest sake I also tested
google's sparse/dense hash map implementation and in my environment g++'s
outperformed both sparse/dense hash maps.

Nice to be able to chuck it out and run native Click template again! I will
let you know if I pick up any issues.

Beyers

On Sun, Apr 13, 2008 at 6:39 PM, Eddie Kohler <kohler at cs.ucla.edu> wrote:

> 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
> _______________________________________________
> click mailing list
> click at amsterdam.lcs.mit.edu
> https://amsterdam.lcs.mit.edu/mailman/listinfo/click
>