[Click] Multithreaded HashMaps

[springbo at cs.wisc.edu]

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
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashmaptest.cc
Type: application/octet-stream
Size: 367 bytes
Desc: not available
Url : https://pdos.csail.mit.edu/pipermail/click/attachments/20080409/454d1626/attachment.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashmaptest.hh
Type: application/octet-stream
Size: 1537 bytes
Desc: not available
Url : https://pdos.csail.mit.edu/pipermail/click/attachments/20080409/454d1626/attachment-0001.obj 
-------------- next part --------------
A non-text attachment was scrubbed...
Name: hashmap.patch
Type: application/octet-stream
Size: 1039 bytes
Desc: not available
Url : https://pdos.csail.mit.edu/pipermail/click/attachments/20080409/454d1626/attachment-0002.obj