linux-kernel - Re: [PATCH v3 01/17] 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: <20120904170138.GB31934@Krystal>
Date:	Tue, 4 Sep 2012 13:01:38 -0400
From:	Mathieu Desnoyers <mathieu.desnoyers@...icios.com>
To:	Pedro Alves <palves@...hat.com>
Cc:	Steven Rostedt <rostedt@...dmis.org>,
	Sasha Levin <levinsasha928@...il.com>,
	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,
	davem@...emloft.net, mingo@...e.hu, ebiederm@...ssion.com,
	aarcange@...hat.com, ericvh@...il.com, netdev@...r.kernel.org,
	josh@...htriplett.org, eric.dumazet@...il.com, axboe@...nel.dk,
	agk@...hat.com, dm-devel@...hat.com, neilb@...e.de,
	ccaulfie@...hat.com, teigland@...hat.com,
	Trond.Myklebust@...app.com, bfields@...ldses.org,
	fweisbec@...il.com, jesse@...ira.com,
	venkat.x.venkatsubra@...cle.com, ejt@...hat.com,
	snitzer@...hat.com, edumazet@...gle.com, linux-nfs@...r.kernel.org,
	dev@...nvswitch.org, rds-devel@....oracle.com, lw@...fujitsu.com
Subject: Re: [PATCH v3 01/17] hashtable: introduce a small and naive
	hashtable

* Pedro Alves (palves@...hat.com) wrote:
> On 09/04/2012 05:30 PM, Pedro Alves wrote:
> > On 09/04/2012 04:35 PM, Steven Rostedt wrote:
> >> On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
> >>
> >>> Looking again at:
> >>>
> >>> +#define hash_for_each_size(name, bits, bkt, node, obj, member)                 \
> >>> +       for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)                             \
> >>> +               hlist_for_each_entry(obj, node, &name[bkt], member)
> >>>
> >>> you will notice that a "break" or "continue" in the inner loop will not
> >>> affect the outer loop, which is certainly not what the programmer would
> >>> expect!
> >>>
> >>> I advise strongly against creating such error-prone construct.
> >>>
> >>
> >> A few existing loop macros do this. But they require a do { } while ()
> >> approach, and all have a comment.
> >>
> >> It's used by do_each_thread() in sched.h and ftrace does this as well.
> >> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
> >>
> >> Yes it breaks 'break' but it does not break 'continue' as it would just
> >> go to the next item that would have been found (like a normal for
> >> would).
> > 
> > /*
> >  * This is a double for. Do not use 'break' to break out of the loop,
> >  * you must use a goto.
> >  */
> > #define do_for_each_ftrace_rec(pg, rec)                                 \
> >         for (pg = ftrace_pages_start; pg; pg = pg->next) {              \
> >                 int _____i;                                             \
> >                 for (_____i = 0; _____i < pg->index; _____i++) {        \
> >                         rec = &pg->records[_____i];
> > 
> > 
> > 
> > You can make 'break' also work as expected if you can embed a little knowledge
> > of the inner loop's condition in the outer loop's condition.  Sometimes it's
> > trivial, most often when the inner loop's iterator is a pointer that goes
> > NULL at the end, but other times not so much.  Something like (completely untested):
> > 
> > #define do_for_each_ftrace_rec(pg, rec)                                 \
> >         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];    \
> >              pg && rec == &pg->records[pg->index];                      \
> >              pg = pg->next) {                                           \
> >                 int _____i;                                             \
> >                 for (_____i = 0; _____i < pg->index; _____i++) {        \
> >                         rec = &pg->records[_____i];
> >
> > 
> > (other variants possible)
> > 
> > IOW, the outer loop only iterates if the inner loop completes.  If there's
> > a break in the inner loop, then the outer loop breaks too.  Of course, it
> > all depends on whether the generated code looks sane or hideous, if
> > the uses of the macro care for it over bug avoidance.
> > 
> 
> BTW, you can also go a step further and remove the need to close with double }},
> with something like:
> 
> #define do_for_each_ftrace_rec(pg, rec)                                          \
>         for (pg = ftrace_pages_start, rec = &pg->records[pg->index];             \
>              pg && rec == &pg->records[pg->index];                               \
>              pg = pg->next)                                                      \
>           for (rec = pg->records; rec < &pg->records[pg->index]; rec++)

Maybe in some cases there might be ways to combine the two loops into
one ? I'm not seeing exactly how to do it for this one, but it should
not be impossible. If the inner loop condition can be moved to the outer
loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
different conditions depending on the context, and do the same for the
3rd argument of the for() loop. The details elude me for now though, so
maybe it's complete non-sense ;)

It might not be that useful for do_for_each_ftrace_rec, but if we can do
it for the hash table iterator, it might be worth it.

Thanks,

Mathieu


-- 
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
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/