Hash table in FreeBSD kernel?

[Alan Somers]

On Mon, Mar 16, 2015 at 1:18 PM, Yue Chen <ycyc321 at gmail.com> wrote:
> Dear all,
>
> Is there a good hash table implementation for FreeBSD kernel, x86_64? I
> tried "uthash", but encountered some memory problems (during HASH_FIND())
> when the entry number becomes large. The cause may be my replacements for
> the user-space header functions and types are incorrect.
>
> =====================================================================
>
> The userland functions/types need to be replaced:
>
> #include <string.h> /* memcmp,strlen */
>
> #include <stddef.h> /* ptrdiff_t */
>
> #include <stdlib.h> /* exit() */ /*  malloc()  */
>
> =====================================================================
>
> I use:
>
> #include <sys/systm.h>  /* memcmp */
>
> #include <sys/_types.h>
>
> typedef __ptrdiff_t ptrdiff_t;
>
> #include <sys/types.h>
>
> #include <sys/malloc.h>  /* the malloc()  */
>
> ------------------------------------------------------------------------------------------------------------------------
>
> size_t strlen(const char *str)
>
> {
>
>     const char *s;
>
>     for (s = str; *s; ++s);
>
>     return(s - str);
>
> }
>
> =====================================================================
>
> Any suggestions for using "uthash" in kernel, or any other alternatives
> that I can use? (the FreeBSD kernel's "hash32" function set seems only
> support 32-bit key hash)
>
> Best regards and thanks,
> Yue

hash32_buf is just a hash function, not a hash table.  And it's a bad
hash function; changing the last few bits of input will always change
the output by a multiple of 33.  Better hash functions are
jenkins_hash or fnv_32_buf and friends.  However, those are also just
hash functions.  Most kernel code that needs hash tables uses a fixed
size array of buckets with one of the above hash functions.  I'm not
aware of any in-kernel hash tables with a dynamic number of buckets.
It doesn't mean there aren't any, though.

-Alan