linux-kernel - Re: [RFC 1/4] 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] [thread-next>] [day] [month] [year] [list]

Message-ID: <20120802174457.GA6251@jtriplet-mobl1>
Date:	Thu, 2 Aug 2012 10:44:57 -0700
From:	Josh Triplett <josh@...htriplett.org>
To:	Sasha Levin <levinsasha928@...il.com>
Cc:	Tejun Heo <tj@...nel.org>, torvalds@...ux-foundation.org,
	akpm@...ux-foundation.org, linux-kernel@...r.kernel.org,
	linux-mm@...ck.org, paul.gortmaker@...driver.com
Subject: Re: [RFC 1/4] hashtable: introduce a small and naive hashtable

On Thu, Aug 02, 2012 at 06:48:07PM +0200, Sasha Levin wrote:
> On 08/02/2012 06:15 PM, Josh Triplett wrote:
> > On Thu, Aug 02, 2012 at 03:04:19PM +0200, Sasha Levin wrote:
> >> On 08/02/2012 01:23 PM, Sasha Levin wrote:
> >>>> #define DEFINE_HASH_TABLE(name, length) struct hash_table name = { .count = length, .buckets = { [0 ... (length - 1)] = HLIST_HEAD_INIT } }
> >>> The limitation of this approach is that the struct hash_table variable must be 'static', which is a bit limiting - see for example the use of hashtable in 'struct user_namespace'.
> >>>
> >>
> >> What if we just use two possible decelerations? One of static structs and one for regular ones.
> >>
> >> struct hash_table {
> >>         size_t bits;
> >>         struct hlist_head buckets[];
> >> };
> >>
> >> #define DEFINE_HASHTABLE(name, bits)                                    \
> >>         union {                                                         \
> >>                 struct hash_table name;                                 \
> >>                 struct {                                                \
> >>                         size_t bits;                                    \
> > 
> > This shouldn't use "bits", since it'll get expanded to the macro
> > argument.
> > 
> >>                         struct hlist_head buckets[1 << bits];           \
> >>                 } __name;                                               \
> > 
> > __##name
> > 
> >>         }
> >>
> >> #define DEFINE_STATIC_HASHTABLE(name, bit)                              \
> >>         static struct hash_table name = { .bits = bit,                  \
> >>                 .buckets = { [0 ... (bit - 1)] = HLIST_HEAD_INIT } }
> > 
> > You probably wanted to change that to [0 ... ((1 << bit) - 1)] , to
> > match DEFINE_HASHTABLE.
> 
> I wrote it by hand and didn't compile test, will fix all of those.
> 
> > Since your definition of DEFINE_HASHTABLE would also work fine when used
> > statically, why not just always use that?
> > 
> > #define DEFINE_STATIC_HASHTABLE(name, bits) static DEFINE_HASHTABLE(name, bits) = { .name.bits = bits }
> 
> It will get defined fine, but it will be awkward to use. We'd need to pass anonymous union to all the functions that handle this hashtable, which isn't pretty.

No, it'll still use the anonymous union, so you'll still have a thing of
type "struct hash_table" with the given name, and you can use that name
with the hash-table functions.

- Josh Triplett

--
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/