[ovs-dev] [PATCH net-next 1/3] lib: Resizable, Scalable, Concurrent Hash Table
nikolay at redhat.com
Sat Aug 2 10:32:41 UTC 2014
On 08/02/2014 11:47 AM, Thomas Graf wrote:
> Generic implementation of a resizable, scalable, concurrent hash table
> based on . The implementation supports both, fixed size keys specified
> via an offset and length, or arbitrary keys via own hash and compare
> 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.
>  https://www.usenix.org/legacy/event/atc11/tech/final_files/Triplett.pdf
> Signed-off-by: Thomas Graf <tgraf at suug.ch>
> include/linux/rhashtable.h | 213 ++++++++++++
> lib/Kconfig.debug | 8 +
> lib/Makefile | 2 +-
> lib/rhashtable.c | 797 +++++++++++++++++++++++++++++++++++++++++++++
> 4 files changed, 1019 insertions(+), 1 deletion(-)
> create mode 100644 include/linux/rhashtable.h
> create mode 100644 lib/rhashtable.c
Reviewed-by: Nikolay Aleksandrov <nikolay at redhat.com>
More information about the dev