From owner-freebsd-hackers@FreeBSD.ORG Mon Mar 16 20:43:22 2015 Return-Path: Delivered-To: freebsd-hackers@freebsd.org Received: from mx1.freebsd.org (mx1.freebsd.org [8.8.178.115]) (using TLSv1.2 with cipher AECDH-AES256-SHA (256/256 bits)) (No client certificate requested) by hub.freebsd.org (Postfix) with ESMTPS id 5F285CBE for ; Mon, 16 Mar 2015 20:43:22 +0000 (UTC) Received: from mail-wg0-x22d.google.com (mail-wg0-x22d.google.com [IPv6:2a00:1450:400c:c00::22d]) (using TLSv1.2 with cipher ECDHE-RSA-AES128-GCM-SHA256 (128/128 bits)) (Client CN "smtp.gmail.com", Issuer "Google Internet Authority G2" (verified OK)) by mx1.freebsd.org (Postfix) with ESMTPS id E6BD8157 for ; Mon, 16 Mar 2015 20:43:21 +0000 (UTC) Received: by wggv3 with SMTP id v3so49718392wgg.1 for ; Mon, 16 Mar 2015 13:43:20 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20120113; h=mime-version:sender:in-reply-to:references:date:message-id:subject :from:to:cc:content-type; bh=/ohlXEbg1LChplFaR3UbuCO1fCzAu3lL1ETLJZ3MHhk=; b=UxIU2v772ukm01qrLIqXiHXWMZcUmMdILbknezVyJ57nzbN+ddZrZOngUA18qg6oY1 84s+inZIUwiTvoqQWoDP1BD5DIte3Q/yfXVetANtJF3RZU9lPDW2wH7dlhUfyDi9nPkI pNgLpCQt8FTqssrM1Qi5CKip2gH2Ag5tWDk1+TbgzBqRkTpIxrTKvQ3Y0cxVEQTQMkYv j1solKkPvdC1976fiGnu78YWuqlnUs1eVe3hyptsLYF7ds7RZ5g1YjfzL0IeeX2GKUSj nTOGhVypbkt1hBq4CuN/raIFayqKokvEAd+pR+a5wq6cAnHrx5XlpU6NzZYHzN8P/TsW oisQ== MIME-Version: 1.0 X-Received: by 10.180.126.38 with SMTP id mv6mr20583971wib.22.1426538600362; Mon, 16 Mar 2015 13:43:20 -0700 (PDT) Sender: asomers@gmail.com Received: by 10.194.17.129 with HTTP; Mon, 16 Mar 2015 13:43:20 -0700 (PDT) In-Reply-To: References: Date: Mon, 16 Mar 2015 14:43:20 -0600 X-Google-Sender-Auth: gluNyB5r6Zoi2YwQsZ-zKqcWMkA Message-ID: Subject: Re: Hash table in FreeBSD kernel? From: Alan Somers To: Yue Chen Content-Type: text/plain; charset=UTF-8 Cc: "freebsd-hackers@freebsd.org" X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.18-1 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 16 Mar 2015 20:43:22 -0000 On Mon, Mar 16, 2015 at 1:18 PM, Yue Chen 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 /* memcmp,strlen */ > > #include /* ptrdiff_t */ > > #include /* exit() */ /* malloc() */ > > ===================================================================== > > I use: > > #include /* memcmp */ > > #include > > typedef __ptrdiff_t ptrdiff_t; > > #include > > #include /* 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