linux-kernel - Re: [PATCH v5] hashtable: introduce a small and naive hashtable

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <50562D06.2040304@gmail.com>
Date:	Sun, 16 Sep 2012 21:48:22 +0200
From:	Sasha Levin <levinsasha928@...il.com>
To:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
CC:	torvalds@...ux-foundation.org, tj@...nel.org,
	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	rostedt@...dmis.org, ebiederm@...ssion.com, neilb@...e.de,
	bfields@...ldses.org, ejt@...hat.com, snitzer@...hat.com,
	edumazet@...gle.com, josh@...htriplett.org,
	David.Laight@...lab.com, rmallon@...il.com, palves@...hat.com
Subject: Re: [PATCH v5] hashtable: introduce a small and naive hashtable

On 09/16/2012 09:33 PM, Mathieu Desnoyers wrote:
>> How would you create a dynamic hashtable with this code to begin with?
> With a var. sized array in a structure, e.g.:
> 
> struct hashtable {
>         size_t len;
>         struct hlist_head t[];
> };
> 
> Then create a hash table allocation function, and turn both hash_empty
> and hash_init into functions that take a struct simplehash pointer as
> parameter. The downside is to consume extra space (especially because
> the array always has a power of 2 len), but the nice thing is that we
> could use this code with a kmalloc'd/vmalloc'd hash table.
> 
> I'm not saying we need to do it (due to the space consumption downside),
> but that we should at least document this limitation.

We've gone through the process of attempting to support dynamic hashtables in
the previous versions of this patch, this turned to complicate the code a lot
beyond simply changing the array of hlist_heads into the struct you proposed, so
it was decided to not support dynamic hashtables at this point at all.

I thought we've agreed that non-dynamically allocated hashtables are widespread
enough to have a dedicated abstraction of their own, and further hashtable
implementations may introduce their own API for that.

We can ofcourse open that for discussion again, but I'd rather not go back and
forth adding support for dynamic hashtables and removing it again.


Thanks,
Sasha
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@...r.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/