lib: Resizable, Scalable, Concurrent Hash Table
authorThomas Graf <tgraf@suug.ch>
Sat, 2 Aug 2014 09:47:44 +0000 (11:47 +0200)
committerDavid S. Miller <davem@davemloft.net>
Sun, 3 Aug 2014 02:49:38 +0000 (19:49 -0700)
commit7e1e77636e36075ebf118298855268468f1028e8
treea885e78ba5cb99f939b45e0de86ace05f23515f7
parentd39a9ffce7f14b494391da982b8cefa311dae0f6
lib: Resizable, Scalable, Concurrent Hash Table

Generic implementation of a resizable, scalable, concurrent hash table
based on [0]. The implementation supports both, fixed size keys specified
via an offset and length, or arbitrary keys via own hash and compare
functions.

Lookups are lockless and protected as RCU read side critical sections.
Automatic growing/shrinking based on user configurable watermarks is
available while allowing concurrent lookups to take place.

Objects to be hashed must include a struct rhash_head. The reason for not
using the existing struct hlist_head is that the expansion and shrinking
will have two buckets point to a single entry which would lead in obscure
reverse chaining behaviour.

Code includes a boot selftest if CONFIG_TEST_RHASHTABLE is defined.

[0] https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf

Signed-off-by: Thomas Graf <tgraf@suug.ch>
Reviewed-by: Nikolay Aleksandrov <nikolay@redhat.com>
Signed-off-by: David S. Miller <davem@davemloft.net>
include/linux/rhashtable.h [new file with mode: 0644]
lib/Kconfig.debug
lib/Makefile
lib/rhashtable.c [new file with mode: 0644]