FAQ Search Today's Posts Mark Forums Read
» Video Reviews

» Linux Archive

Linux-archive is a website aiming to archive linux email lists and to make them easily accessible for linux users/developers.


» Sponsor

» Partners

» Sponsor

Go Back   Linux Archive > Redhat > Device-mapper Development

 
 
LinkBack Thread Tools
 
Old 09-04-2012, 04:30 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

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.

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 04:40 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

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++)

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 05:21 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

On 09/04/2012 06:17 PM, Steven Rostedt wrote:
> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
>
>> 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++)
>>
>
> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
> that this is something "special".

The point of both changes is that there's nothing special in the end
at all. It all just works...

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 09:51 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

On 09/04/2012 09:59 PM, Steven Rostedt wrote:
> On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
>> On 09/04/2012 06:17 PM, Steven Rostedt wrote:
>>> On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
>>>
>>>> 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++)
>>>>
>>>
>>> Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
>>> that this is something "special".
>>
>> The point of both changes is that there's nothing special in the end
>> at all. It all just works...
>>
>
> It would still fail on a 'break'. The 'while' macro tells us that it is
> special, because in the end, it wont work.

Please explain why it would fail on a 'break'.

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-04-2012, 10:58 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

On 09/04/2012 11:41 PM, Steven Rostedt wrote:
> Ah, I missed the condition with the rec == &pg->records[pg->index]. But
> if ftrace_pages_start is NULL, the rec = &pg->records[pg->index] will
> fault.

Right.

>
> You could do something like rec = pg ? &pg->records[pg->index] : NULL,

Right.

> but IIRC, the comma operator does not guarantee order evaluation. That
> is, the compiler is allowed to process "a , b" as "b; a;" and not "a;
> b;".

Not true. The comma operator introduces a sequence point. It's the comma
that separates function parameters that doesn't guarantee ordering.

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-06-2012, 01:53 PM
Sasha Levin
 
Default hashtable: introduce a small and naive hashtable

On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>> #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.

So I think that for the hash iterator it might actually be simpler.

My solution to making 'break' work in the iterator is:

for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
hlist_for_each_entry(obj, node, &name[bkt], member)

We initialize our node loop cursor with NULL in the external loop, and the
external loop will have a new condition to loop while that cursor is NULL.

My logic is that we can only 'break' when we are iterating over an object in the
internal loop. If we're iterating over an object in that loop then 'node != NULL'.

This way, if we broke from within the internal loop, the external loop will see
node as not NULL, and so it will stop looping itself. On the other hand, if the
internal loop has actually ended, then node will be NULL, and the outer loop
will keep running.

Is there anything I've missed?


Thanks,
Sasha

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-06-2012, 02:19 PM
Pedro Alves
 
Default hashtable: introduce a small and naive hashtable

On 09/06/2012 02:53 PM, Sasha Levin wrote:

> So I think that for the hash iterator it might actually be simpler.
>
> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)
>
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
>
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
>
> Is there anything I've missed?

Looks right to me, from a cursory look at hlist_for_each_entry. That's exactly
what I meant with this most often being trivial when the inner loop's iterator
is a pointer that goes NULL at the end.

--
Pedro Alves

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-06-2012, 02:36 PM
"David Laight"
 
Default hashtable: introduce a small and naive hashtable

> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node ==
NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)

I'd take a look at the generated code.
Might come out a bit better if the condition is changed to:
node == NULL && bkt < HASH_SIZE(name)
you might find the compiler always optimises out the
node == NULL comparison.
(It might anyway, but switching the order gives it a better
chance.)

David




--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-06-2012, 02:55 PM
Josh Triplett
 
Default hashtable: introduce a small and naive hashtable

On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote:
> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
> >> #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.
>
> So I think that for the hash iterator it might actually be simpler.
>
> My solution to making 'break' work in the iterator is:
>
> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
> hlist_for_each_entry(obj, node, &name[bkt], member)
>
> We initialize our node loop cursor with NULL in the external loop, and the
> external loop will have a new condition to loop while that cursor is NULL.
>
> My logic is that we can only 'break' when we are iterating over an object in the
> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>
> This way, if we broke from within the internal loop, the external loop will see
> node as not NULL, and so it will stop looping itself. On the other hand, if the
> internal loop has actually ended, then node will be NULL, and the outer loop
> will keep running.
>
> Is there anything I've missed?

Looks reasonable. However, it would break (or rather, not break) on
code like this:

hash_for_each_entry(...) {
if (...) {
foo(node);
node = NULL;
break;
}
}

Hiding the double loop still seems error-prone.

- Josh Triplett

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 
Old 09-06-2012, 03:49 PM
Sasha Levin
 
Default hashtable: introduce a small and naive hashtable

On 09/06/2012 04:55 PM, Josh Triplett wrote:
> On Thu, Sep 06, 2012 at 03:53:58PM +0200, Sasha Levin wrote:
>> On 09/04/2012 07:01 PM, Mathieu Desnoyers wrote:
>>>> #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.
>>
>> So I think that for the hash iterator it might actually be simpler.
>>
>> My solution to making 'break' work in the iterator is:A code like that doesn
>>
>> for (bkt = 0, node = NULL; bkt < HASH_SIZE(name) && node == NULL; bkt++)
>> hlist_for_each_entry(obj, node, &name[bkt], member)
>>
>> We initialize our node loop cursor with NULL in the external loop, and the
>> external loop will have a new condition to loop while that cursor is NULL.
>>
>> My logic is that we can only 'break' when we are iterating over an object in the
>> internal loop. If we're iterating over an object in that loop then 'node != NULL'.
>>
>> This way, if we broke from within the internal loop, the external loop will see
>> node as not NULL, and so it will stop looping itself. On the other hand, if the
>> internal loop has actually ended, then node will be NULL, and the outer loop
>> will keep running.
>>
>> Is there anything I've missed?
>
> Looks reasonable. However, it would break (or rather, not break) on
> code like this:
>
> hash_for_each_entry(...) {
> if (...) {
> foo(node);
> node = NULL;
> break;
> }
> }
>
> Hiding the double loop still seems error-prone.

I think that that code doesn't make sense. The users of hlist_for_each_* aren't
supposed to be changing the loop cursor.

We have three options here:

1. Stuff everything into a single for(). While not too difficult, it will make
the readability of the code difficult as it will force us to abandon using
hlist_for_each_* macros.

2. Over-complicate everything, and check for 'node == NULL && obj &&
obj->member.next == NULL' instead. That one will fail only if the user has
specifically set the object as the last object in the list and the node as NULL.

3. Use 2 loops which might not work properly if the user does something odd,
with a big fat warning above them.


To sum it up, I'd rather go with 3 and let anyone who does things he shouldn't
be doing break.


Thanks,
Sasha

--
dm-devel mailing list
dm-devel@redhat.com
https://www.redhat.com/mailman/listinfo/dm-devel
 

Thread Tools




All times are GMT. The time now is 02:18 AM.

VBulletin, Copyright ©2000 - 2014, Jelsoft Enterprises Ltd.
Content Relevant URLs by vBSEO ©2007, Crawlability, Inc.
Copyright 2007 - 2008, www.linux-archive.org