Date: Mon, 16 Mar 2015 14:43:20 -0600 From: Alan Somers <asomers@freebsd.org> To: Yue Chen <ycyc321@gmail.com> Cc: "freebsd-hackers@freebsd.org" <freebsd-hackers@freebsd.org> Subject: Re: Hash table in FreeBSD kernel? Message-ID: <CAOtMX2jDN5yRu48T3inj-G3bhm9=70WYqO47CF_u69P2jmpGzg@mail.gmail.com> In-Reply-To: <CAKtBrB4czEv29u-t-Hi09vus8tbACew363nqSvWd1z04oL8kXA@mail.gmail.com> References: <CAKtBrB4czEv29u-t-Hi09vus8tbACew363nqSvWd1z04oL8kXA@mail.gmail.com>
next in thread | previous in thread | raw e-mail | index | archive | help
On Mon, Mar 16, 2015 at 1:18 PM, Yue Chen <ycyc321@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
Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?CAOtMX2jDN5yRu48T3inj-G3bhm9=70WYqO47CF_u69P2jmpGzg>