Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 18:21 +0200, Sasha Levin wrote: > On 09/06/2012 06:00 PM, Steven Rostedt wrote: > >> > I think that that code doesn't make sense. The users of hlist_for_each_* > >> > aren't > >> > supposed to be changing the loop cursor. > > I totally agree. Modifying the 'node' pointer is just asking for issues. > > Yes that is error prone, but not due to the double loop. It's due to the > > modifying of the node pointer that is used internally by the loop > > counter. Don't do that :-) > > While we're on this subject, I haven't actually seen hlist_for_each_entry() > code > that even *touches* 'pos'. > > Will people yell at me loudly if I change the prototype of those macros to be: > > hlist_for_each_entry(tpos, head, member) > > (Dropping the 'pos' parameter), and updating anything that calls those macros > to > drop it as well? If 'pos' is no longer used in the macro, I don't see any reason for keeping it around. -- Steve -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote: > On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote: > > * Sasha Levin (levinsasha...@gmail.com) wrote: > >> On 09/06/2012 06:00 PM, Steven Rostedt wrote: > > I think that that code doesn't make sense. The users of > > hlist_for_each_* aren't > > supposed to be changing the loop cursor. > >>> I totally agree. Modifying the 'node' pointer is just asking for issues. > >>> Yes that is error prone, but not due to the double loop. It's due to the > >>> modifying of the node pointer that is used internally by the loop > >>> counter. Don't do that :-) > >> > >> While we're on this subject, I haven't actually seen > >> hlist_for_each_entry() code > >> that even *touches* 'pos'. > >> > >> Will people yell at me loudly if I change the prototype of those macros to > >> be: > >> > >>hlist_for_each_entry(tpos, head, member) > >> > >> (Dropping the 'pos' parameter), and updating anything that calls those > >> macros to > >> drop it as well? > > > > I think the intent there is to keep hlist macros and list macros > > slightly in sync. Given those are vastly used, I'm not sure you want to > > touch them. But hey, that's just my 2 cents. > > Actually, the corresponding list macro looks like this: > > list_for_each_entry(pos, head, member) > > With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *). > Changing hlist macro will make them both look as follows: > > hlist_for_each_entry(pos, head, member) > list_for_each_entry(pos, head, member) > > So following this suggesting will actually bring them back to sync... > > The only issue I can see is that as you've said, they're used almost > everywhere, > so doing something to change that will require some coordination. if this brings hlist and list in sync, then it looks like an improvement. It might be good to propose this change as a separate patchset. Thanks, Mathieu > > > Thanks, > Sasha -- Mathieu Desnoyers Operating System Efficiency R 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote: > * Sasha Levin (levinsasha...@gmail.com) wrote: >> On 09/06/2012 06:00 PM, Steven Rostedt wrote: > I think that that code doesn't make sense. The users of hlist_for_each_* > aren't > supposed to be changing the loop cursor. >>> I totally agree. Modifying the 'node' pointer is just asking for issues. >>> Yes that is error prone, but not due to the double loop. It's due to the >>> modifying of the node pointer that is used internally by the loop >>> counter. Don't do that :-) >> >> While we're on this subject, I haven't actually seen hlist_for_each_entry() >> code >> that even *touches* 'pos'. >> >> Will people yell at me loudly if I change the prototype of those macros to >> be: >> >> hlist_for_each_entry(tpos, head, member) >> >> (Dropping the 'pos' parameter), and updating anything that calls those >> macros to >> drop it as well? > > I think the intent there is to keep hlist macros and list macros > slightly in sync. Given those are vastly used, I'm not sure you want to > touch them. But hey, that's just my 2 cents. Actually, the corresponding list macro looks like this: list_for_each_entry(pos, head, member) With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *). Changing hlist macro will make them both look as follows: hlist_for_each_entry(pos, head, member) list_for_each_entry(pos, head, member) So following this suggesting will actually bring them back to sync... The only issue I can see is that as you've said, they're used almost everywhere, so doing something to change that will require some coordination. Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote: > On 09/06/2012 06:00 PM, Steven Rostedt wrote: > >> > I think that that code doesn't make sense. The users of hlist_for_each_* > >> > aren't > >> > supposed to be changing the loop cursor. > > I totally agree. Modifying the 'node' pointer is just asking for issues. > > Yes that is error prone, but not due to the double loop. It's due to the > > modifying of the node pointer that is used internally by the loop > > counter. Don't do that :-) > > While we're on this subject, I haven't actually seen hlist_for_each_entry() > code > that even *touches* 'pos'. > > Will people yell at me loudly if I change the prototype of those macros to be: > > hlist_for_each_entry(tpos, head, member) > > (Dropping the 'pos' parameter), and updating anything that calls those macros > to > drop it as well? I think the intent there is to keep hlist macros and list macros slightly in sync. Given those are vastly used, I'm not sure you want to touch them. But hey, that's just my 2 cents. Thanks, Mathieu > > > Thanks, > Sasha -- Mathieu Desnoyers Operating System Efficiency R 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 09/06/2012 06:00 PM, Steven Rostedt wrote: >> > I think that that code doesn't make sense. The users of hlist_for_each_* >> > aren't >> > supposed to be changing the loop cursor. > I totally agree. Modifying the 'node' pointer is just asking for issues. > Yes that is error prone, but not due to the double loop. It's due to the > modifying of the node pointer that is used internally by the loop > counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? Thanks, Sasha -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 17:49 +0200, Sasha Levin wrote:
>
> > Looks reasonable. However, it would break (or rather, not break) on
> > code like this:
> >
> > hash_for_each_entry(...) {
> > if (...) {
> > foo(node);
> > node = NULL;
ug, I didn't even notice this. Ignore my last email :-p
/me needs to wake-up a bit more.
> > 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.
I totally agree. Modifying the 'node' pointer is just asking for issues.
Yes that is error prone, but not due to the double loop. It's due to the
modifying of the node pointer that is used internally by the loop
counter. Don't do that :-)
>
> 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.
I agree, the double loop itself is not error prone. If you are modifying
'node' you had better know what the hell you are doing.
Actually, it may be something that is legitimate. That is, if you want
to skip to the next bucket, just set node to NULL and do the break (as
Josh had done). This would break if the macro loop changed later on, but
hey, like I said, it's error prone ;-) If you really want to do that,
then hand coding the double loop would be a better bet. IOW, don't use
the macro loop.
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 = >records[pg->index];
>\
> pg && rec == >records[pg->index];
>\
> pg = pg->next)
>\
> for (rec = pg->records; rec < >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, [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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 07:55 -0700, Josh Triplett wrote:
> > 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, [bkt], member)
> >
>
> 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.
We've already had this conversation ;-) A guess a big comment is in
order:
/*
* NOTE! Although this is a double loop, 'break' still works because of
*the 'node == NULL' condition in the outer loop. On break of
*the inner loop, node will be !NULL, and the outer loop will
*exit as well.
*/
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 = >records[pg->index];
> >> > \
> >> > pg && rec == >records[pg->index];
> >> > \
> >> > pg = pg->next)
> >> > \
> >> > for (rec = pg->records; rec < >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, [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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
RE: [PATCH v3 01/17] 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, [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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) 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 = >records[pg->index]; > >> > \ > >> > pg && rec == >records[pg->index]; > >> > \ > >> > pg = pg->next) > >> > \ > >> > for (rec = pg->records; rec < >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, [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? This sounds good. Unless I'm missing something too. Thanks! Mathieu > > > Thanks, > Sasha -- Mathieu Desnoyers Operating System Efficiency R 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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, [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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 = >records[pg->index]; >> > \ >> > pg && rec == >records[pg->index]; >> > \ >> > pg = pg->next) >> > \ >> > for (rec = pg->records; rec < >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, [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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) 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? This sounds good. Unless I'm missing something too. Thanks! Mathieu Thanks, Sasha -- Mathieu Desnoyers Operating System Efficiency RD 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
RE: [PATCH v3 01/17] 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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 07:55 -0700, Josh Triplett wrote:
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)
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.
We've already had this conversation ;-) A guess a big comment is in
order:
/*
* NOTE! Although this is a double loop, 'break' still works because of
*the 'node == NULL' condition in the outer loop. On break of
*the inner loop, node will be !NULL, and the outer loop will
*exit as well.
*/
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 17:49 +0200, Sasha Levin wrote:
Looks reasonable. However, it would break (or rather, not break) on
code like this:
hash_for_each_entry(...) {
if (...) {
foo(node);
node = NULL;
ug, I didn't even notice this. Ignore my last email :-p
/me needs to wake-up a bit more.
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.
I totally agree. Modifying the 'node' pointer is just asking for issues.
Yes that is error prone, but not due to the double loop. It's due to the
modifying of the node pointer that is used internally by the loop
counter. Don't do that :-)
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.
I agree, the double loop itself is not error prone. If you are modifying
'node' you had better know what the hell you are doing.
Actually, it may be something that is legitimate. That is, if you want
to skip to the next bucket, just set node to NULL and do the break (as
Josh had done). This would break if the macro loop changed later on, but
hey, like I said, it's error prone ;-) If you really want to do that,
then hand coding the double loop would be a better bet. IOW, don't use
the macro loop.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 09/06/2012 06:00 PM, Steven Rostedt wrote: I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. I totally agree. Modifying the 'node' pointer is just asking for issues. Yes that is error prone, but not due to the double loop. It's due to the modifying of the node pointer that is used internally by the loop counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? Thanks, Sasha -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote: On 09/06/2012 06:00 PM, Steven Rostedt wrote: I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. I totally agree. Modifying the 'node' pointer is just asking for issues. Yes that is error prone, but not due to the double loop. It's due to the modifying of the node pointer that is used internally by the loop counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? I think the intent there is to keep hlist macros and list macros slightly in sync. Given those are vastly used, I'm not sure you want to touch them. But hey, that's just my 2 cents. Thanks, Mathieu Thanks, Sasha -- Mathieu Desnoyers Operating System Efficiency RD 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote: * Sasha Levin (levinsasha...@gmail.com) wrote: On 09/06/2012 06:00 PM, Steven Rostedt wrote: I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. I totally agree. Modifying the 'node' pointer is just asking for issues. Yes that is error prone, but not due to the double loop. It's due to the modifying of the node pointer that is used internally by the loop counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? I think the intent there is to keep hlist macros and list macros slightly in sync. Given those are vastly used, I'm not sure you want to touch them. But hey, that's just my 2 cents. Actually, the corresponding list macro looks like this: list_for_each_entry(pos, head, member) With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *). Changing hlist macro will make them both look as follows: hlist_for_each_entry(pos, head, member) list_for_each_entry(pos, head, member) So following this suggesting will actually bring them back to sync... The only issue I can see is that as you've said, they're used almost everywhere, so doing something to change that will require some coordination. Thanks, Sasha -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote: On 09/06/2012 06:50 PM, Mathieu Desnoyers wrote: * Sasha Levin (levinsasha...@gmail.com) wrote: On 09/06/2012 06:00 PM, Steven Rostedt wrote: I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. I totally agree. Modifying the 'node' pointer is just asking for issues. Yes that is error prone, but not due to the double loop. It's due to the modifying of the node pointer that is used internally by the loop counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? I think the intent there is to keep hlist macros and list macros slightly in sync. Given those are vastly used, I'm not sure you want to touch them. But hey, that's just my 2 cents. Actually, the corresponding list macro looks like this: list_for_each_entry(pos, head, member) With 'pos' being the equivalent of 'tpos' in the hlist macros (the type *). Changing hlist macro will make them both look as follows: hlist_for_each_entry(pos, head, member) list_for_each_entry(pos, head, member) So following this suggesting will actually bring them back to sync... The only issue I can see is that as you've said, they're used almost everywhere, so doing something to change that will require some coordination. if this brings hlist and list in sync, then it looks like an improvement. It might be good to propose this change as a separate patchset. Thanks, Mathieu Thanks, Sasha -- Mathieu Desnoyers Operating System Efficiency RD 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Thu, 2012-09-06 at 18:21 +0200, Sasha Levin wrote: On 09/06/2012 06:00 PM, Steven Rostedt wrote: I think that that code doesn't make sense. The users of hlist_for_each_* aren't supposed to be changing the loop cursor. I totally agree. Modifying the 'node' pointer is just asking for issues. Yes that is error prone, but not due to the double loop. It's due to the modifying of the node pointer that is used internally by the loop counter. Don't do that :-) While we're on this subject, I haven't actually seen hlist_for_each_entry() code that even *touches* 'pos'. Will people yell at me loudly if I change the prototype of those macros to be: hlist_for_each_entry(tpos, head, member) (Dropping the 'pos' parameter), and updating anything that calls those macros to drop it as well? If 'pos' is no longer used in the macro, I don't see any reason for keeping it around. -- Steve -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Tue, 2012-09-04 at 23:58 +0100, Pedro Alves wrote: > Not true. The comma operator introduces a sequence point. It's the comma > that separates function parameters that doesn't guarantee ordering. Bah! C language is almost as confusing as English. -- Steve -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 == >records[pg->index]. But > if ftrace_pages_start is NULL, the rec = >records[pg->index] will > fault. Right. > > You could do something like rec = 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 -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Tue, 2012-09-04 at 22:51 +0100, Pedro Alves wrote:
> 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 = >records[pg->index];
> \
> pg && rec == >records[pg->index];
> \
> pg = pg->next)
> \
> for (rec = pg->records; rec < >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'.
>
Ah, I missed the condition with the rec == >records[pg->index]. But
if ftrace_pages_start is NULL, the rec = >records[pg->index] will
fault.
You could do something like rec = pg ? >records[pg->index] : NULL,
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;".
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 = >records[pg->index];
\
pg && rec == >records[pg->index];
\
pg = pg->next)
\
for (rec = pg->records; rec < >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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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 = >records[pg->index];
> >> \
> >> pg && rec == >records[pg->index];
> >> \
> >> pg = pg->next)
> >> \
> >> for (rec = pg->records; rec < >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.
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 = >records[pg->index];
>> \
>> pg && rec == >records[pg->index];
>> \
>> pg = pg->next)
>> \
>> for (rec = pg->records; rec < >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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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 = >records[pg->index];
>\
> pg && rec == >records[pg->index];
>\
> pg = pg->next)
>\
> for (rec = pg->records; rec < >records[pg->index]; rec++)
>
Yeah, but why bother? It's hidden in a macro, and the extra '{ }' shows
that this is something "special".
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Pedro Alves (pal...@redhat.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, [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 = >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 = >records[pg->index];\
> > pg && rec == >records[pg->index]; \
> > pg = pg->next) { \
> > int _i; \
> > for (_i = 0; _i < pg->index; _i++) {\
> > rec = >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 = >records[pg->index];
>\
> pg && rec == >records[pg->index];
>\
> pg = pg->next)
>\
> for (rec = pg->records; rec < >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 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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, [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 = >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 = >records[pg->index];\
> pg && rec == >records[pg->index]; \
> pg = pg->next) { \
> int _i; \
> for (_i = 0; _i < pg->index; _i++) {\
> rec = >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 = >records[pg->index];
\
pg && rec == >records[pg->index];
\
pg = pg->next)
\
for (rec = pg->records; rec < >records[pg->index]; rec++)
--
Pedro Alves
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Steven Rostedt (rost...@goodmis.org) 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, [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
Yes. It's worth noting that it is a do_each_thread() /
while_each_thread() pair.
> and ftrace does this as well.
> Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
Same here.
>
> 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).
Good point.
So would changing hash_for_each_size() to a
do_each_hash_size()/while_each_hash_size() make it clearer that this
contains a double-loop ? (along with an appropriate comment about
break).
Thanks,
Mathieu
>
> -- Steve
>
>
--
Mathieu Desnoyers
Operating System Efficiency R 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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, [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 = >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 = >records[pg->index];\
pg && rec == >records[pg->index]; \
pg = pg->next) { \
int _i; \
for (_i = 0; _i < pg->index; _i++) {\
rec = >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
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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, [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).
-- Steve
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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).
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Steven Rostedt (rost...@goodmis.org) 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
Yes. It's worth noting that it is a do_each_thread() /
while_each_thread() pair.
and ftrace does this as well.
Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
Same here.
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).
Good point.
So would changing hash_for_each_size() to a
do_each_hash_size()/while_each_hash_size() make it clearer that this
contains a double-loop ? (along with an appropriate comment about
break).
Thanks,
Mathieu
-- Steve
--
Mathieu Desnoyers
Operating System Efficiency RD 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Pedro Alves (pal...@redhat.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 RD 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
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.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Tue, 2012-09-04 at 22:51 +0100, Pedro Alves wrote:
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'.
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.
You could do something like rec = pg ? pg-records[pg-index] : NULL,
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;.
-- Steve
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] 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 -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On Tue, 2012-09-04 at 23:58 +0100, Pedro Alves wrote: Not true. The comma operator introduces a sequence point. It's the comma that separates function parameters that doesn't guarantee ordering. Bah! C language is almost as confusing as English. -- Steve -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Mathieu Desnoyers (mathieu.desnoy...@efficios.com) wrote:
> * Sasha Levin (levinsasha...@gmail.com) wrote:
> > On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > > * Sasha Levin (levinsasha...@gmail.com) wrote:
> > >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > >>> * Tejun Heo (t...@kernel.org) wrote:
> > Hello,
> >
> > On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > > Thats the thing, the amount of things of things you can do with a
> > > given bucket
> > > is very limited. You can't add entries to any point besides the head
> > > (without
> > > walking the entire list).
> >
> > Kinda my point. We already have all the hlist*() interface to deal
> > with such cases. Having something which is evidently the trivial
> > hlist hashtable and advertises as such in the interface can be
> > helpful. I think we need that more than we need anything fancy.
> >
> > Heh, this is a debate about which one is less insignificant. I can
> > see your point. I'd really like to hear what others think on this.
> >
> > Guys, do we want something which is evidently trivial hlist hashtable
> > which can use hlist_*() API directly or do we want something better
> > encapsulated?
> > >>>
> > >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> > >>> understandable API and implementation, for use-cases where one would be
> > >>> tempted to reimplement his own trivial hash table anyway. So here
> > >>> exposing hlist internals, with which kernel developers are already
> > >>> familiar, seems like a good approach in my opinion, because hiding stuff
> > >>> behind new abstraction might make the target users go away.
> > >>>
> > >>> Then, as we see the need, we can eventually merge a more elaborate hash
> > >>> table with poneys and whatnot, but I would expect that the trivial hash
> > >>> table implementation would still be useful. There are of course very
> > >>> compelling reasons to use a more featureful hash table: automatic
> > >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > >>> for a trivial implementation. Its primary strong points being:
> > >>>
> > >>> - it's trivially understandable, so anyone how want to be really sure
> > >>> they won't end up debugging the hash table instead of their
> > >>> work-in-progress code can have a full understanding of it,
> > >>> - it has few dependencies, which makes it easier to understand and
> > >>> easier to use in some contexts (e.g. early boot).
> > >>>
> > >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> > >>> table, and honestly I would rather prefer that this trivial hash table
> > >>> stays trivial. A more elaborate hash table should probably come as a
> > >>> separate API.
> > >>>
> > >>> Thanks,
> > >>>
> > >>> Mathieu
> > >>>
> > >>
> > >> Alright, let's keep it simple then.
> > >>
> > >> I do want to keep the hash_for_each[rcu,safe] family though.
> > >
> > > Just a thought: if the API offered by the simple hash table focus on
> > > providing a mechanism to find the hash bucket to which belongs the hash
> > > chain containing the key looked up, and then expects the user to use the
> > > hlist API to iterate on the chain (with or without the hlist _rcu
> > > variant), then it might seem consistent that a helper providing
> > > iteration over the entire table would actually just provide iteration on
> > > all buckets, and let the user call the hlist for each iterator for each
> > > node within the bucket, e.g.:
> > >
> > > struct hlist_head *head;
> > > struct hlist_node *pos;
> > >
> > > hash_for_each_bucket(ht, head) {
> > > hlist_for_each(pos, head) {
> > > ...
> > > }
> > > }
> > >
> > > That way you only have to provide one single macro
> > > (hash_for_each_bucket), and rely on the already existing:
> > >
> > > - hlist_for_each_entry
> > > - hlist_for_each_safe
> > > - hlist_for_each_entry_rcu
> > > - hlist_for_each_safe_rcu
> > > .
> > >
> > > and various flavors that can appear in the future without duplicating
> > > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > > versions of the hash_for_each_bucket macro.
> > >
> > > Thoughts ?
> >
> > In my opinion, the downside here is that it'll require 2 function calls and
> > 2
> > levels of nesting for a simple hash iteration.
>
> Those are macros, not functions. No function call is required. But I see
> your point about nesting.
>
> >
> > hash_for_each_bucket() will always be followed by an iteration of that
> > bucket, so splitting a hash_for_each() which does both into 2
> > different functions which will almost always must be called in that
> > given order sounds unintuitive to me.
> >
> > It's also just 3 different possible iterators:
> >
> > - hlist_for_each_entry
> > - hlist_for_each_entry_safe
> > - hlist_for_each_entry_rcu
>
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
> On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> > * Sasha Levin (levinsasha...@gmail.com) wrote:
> >> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> >>> * Tejun Heo (t...@kernel.org) wrote:
> Hello,
>
> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> > Thats the thing, the amount of things of things you can do with a given
> > bucket
> > is very limited. You can't add entries to any point besides the head
> > (without
> > walking the entire list).
>
> Kinda my point. We already have all the hlist*() interface to deal
> with such cases. Having something which is evidently the trivial
> hlist hashtable and advertises as such in the interface can be
> helpful. I think we need that more than we need anything fancy.
>
> Heh, this is a debate about which one is less insignificant. I can
> see your point. I'd really like to hear what others think on this.
>
> Guys, do we want something which is evidently trivial hlist hashtable
> which can use hlist_*() API directly or do we want something better
> encapsulated?
> >>>
> >>> My 2 cents, FWIW: I think this specific effort should target a trivially
> >>> understandable API and implementation, for use-cases where one would be
> >>> tempted to reimplement his own trivial hash table anyway. So here
> >>> exposing hlist internals, with which kernel developers are already
> >>> familiar, seems like a good approach in my opinion, because hiding stuff
> >>> behind new abstraction might make the target users go away.
> >>>
> >>> Then, as we see the need, we can eventually merge a more elaborate hash
> >>> table with poneys and whatnot, but I would expect that the trivial hash
> >>> table implementation would still be useful. There are of course very
> >>> compelling reasons to use a more featureful hash table: automatic
> >>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
> >>> for a trivial implementation. Its primary strong points being:
> >>>
> >>> - it's trivially understandable, so anyone how want to be really sure
> >>> they won't end up debugging the hash table instead of their
> >>> work-in-progress code can have a full understanding of it,
> >>> - it has few dependencies, which makes it easier to understand and
> >>> easier to use in some contexts (e.g. early boot).
> >>>
> >>> So I'm in favor of not overdoing the abstraction for this trivial hash
> >>> table, and honestly I would rather prefer that this trivial hash table
> >>> stays trivial. A more elaborate hash table should probably come as a
> >>> separate API.
> >>>
> >>> Thanks,
> >>>
> >>> Mathieu
> >>>
> >>
> >> Alright, let's keep it simple then.
> >>
> >> I do want to keep the hash_for_each[rcu,safe] family though.
> >
> > Just a thought: if the API offered by the simple hash table focus on
> > providing a mechanism to find the hash bucket to which belongs the hash
> > chain containing the key looked up, and then expects the user to use the
> > hlist API to iterate on the chain (with or without the hlist _rcu
> > variant), then it might seem consistent that a helper providing
> > iteration over the entire table would actually just provide iteration on
> > all buckets, and let the user call the hlist for each iterator for each
> > node within the bucket, e.g.:
> >
> > struct hlist_head *head;
> > struct hlist_node *pos;
> >
> > hash_for_each_bucket(ht, head) {
> > hlist_for_each(pos, head) {
> > ...
> > }
> > }
> >
> > That way you only have to provide one single macro
> > (hash_for_each_bucket), and rely on the already existing:
> >
> > - hlist_for_each_entry
> > - hlist_for_each_safe
> > - hlist_for_each_entry_rcu
> > - hlist_for_each_safe_rcu
> > .
> >
> > and various flavors that can appear in the future without duplicating
> > this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> > versions of the hash_for_each_bucket macro.
> >
> > Thoughts ?
>
> In my opinion, the downside here is that it'll require 2 function calls and 2
> levels of nesting for a simple hash iteration.
Those are macros, not functions. No function call is required. But I see
your point about nesting.
>
> hash_for_each_bucket() will always be followed by an iteration of that
> bucket, so splitting a hash_for_each() which does both into 2
> different functions which will almost always must be called in that
> given order sounds unintuitive to me.
>
> It's also just 3 different possible iterators:
>
> - hlist_for_each_entry
> - hlist_for_each_entry_safe
> - hlist_for_each_entry_rcu
>
> So I think that it's a good price to pay - 2 extra macro definitions
> in the header to save a macro call + nesting level in each place that
> uses a hashtable.
I must admin I don't care that much one way or another.
Thanks,
Mathieu
>
>
> Thanks,
> Sasha
>
> > Thanks,
> >
>
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
> * Sasha Levin (levinsasha...@gmail.com) wrote:
>> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
>>> * Tejun Heo (t...@kernel.org) wrote:
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> Thats the thing, the amount of things of things you can do with a given
> bucket
> is very limited. You can't add entries to any point besides the head
> (without
> walking the entire list).
Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.
Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.
Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?
>>>
>>> My 2 cents, FWIW: I think this specific effort should target a trivially
>>> understandable API and implementation, for use-cases where one would be
>>> tempted to reimplement his own trivial hash table anyway. So here
>>> exposing hlist internals, with which kernel developers are already
>>> familiar, seems like a good approach in my opinion, because hiding stuff
>>> behind new abstraction might make the target users go away.
>>>
>>> Then, as we see the need, we can eventually merge a more elaborate hash
>>> table with poneys and whatnot, but I would expect that the trivial hash
>>> table implementation would still be useful. There are of course very
>>> compelling reasons to use a more featureful hash table: automatic
>>> resize, RT-aware updates, scalable updates, etc... but I see a purpose
>>> for a trivial implementation. Its primary strong points being:
>>>
>>> - it's trivially understandable, so anyone how want to be really sure
>>> they won't end up debugging the hash table instead of their
>>> work-in-progress code can have a full understanding of it,
>>> - it has few dependencies, which makes it easier to understand and
>>> easier to use in some contexts (e.g. early boot).
>>>
>>> So I'm in favor of not overdoing the abstraction for this trivial hash
>>> table, and honestly I would rather prefer that this trivial hash table
>>> stays trivial. A more elaborate hash table should probably come as a
>>> separate API.
>>>
>>> Thanks,
>>>
>>> Mathieu
>>>
>>
>> Alright, let's keep it simple then.
>>
>> I do want to keep the hash_for_each[rcu,safe] family though.
>
> Just a thought: if the API offered by the simple hash table focus on
> providing a mechanism to find the hash bucket to which belongs the hash
> chain containing the key looked up, and then expects the user to use the
> hlist API to iterate on the chain (with or without the hlist _rcu
> variant), then it might seem consistent that a helper providing
> iteration over the entire table would actually just provide iteration on
> all buckets, and let the user call the hlist for each iterator for each
> node within the bucket, e.g.:
>
> struct hlist_head *head;
> struct hlist_node *pos;
>
> hash_for_each_bucket(ht, head) {
> hlist_for_each(pos, head) {
> ...
> }
> }
>
> That way you only have to provide one single macro
> (hash_for_each_bucket), and rely on the already existing:
>
> - hlist_for_each_entry
> - hlist_for_each_safe
> - hlist_for_each_entry_rcu
> - hlist_for_each_safe_rcu
> .
>
> and various flavors that can appear in the future without duplicating
> this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
> versions of the hash_for_each_bucket macro.
>
> Thoughts ?
In my opinion, the downside here is that it'll require 2 function calls and 2
levels of nesting for a simple hash iteration.
hash_for_each_bucket() will always be followed by an iteration of that bucket,
so splitting a hash_for_each() which does both into 2 different functions which
will almost always must be called in that given order sounds unintuitive to me.
It's also just 3 different possible iterators:
- hlist_for_each_entry
- hlist_for_each_entry_safe
- hlist_for_each_entry_rcu
So I think that it's a good price to pay - 2 extra macro definitions in the
header to save a macro call + nesting level in each place that uses a hashtable.
Thanks,
Sasha
> Thanks,
>
> Mathieu
>
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
> On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
> > * Tejun Heo (t...@kernel.org) wrote:
> >> Hello,
> >>
> >> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
> >>> Thats the thing, the amount of things of things you can do with a given
> >>> bucket
> >>> is very limited. You can't add entries to any point besides the head
> >>> (without
> >>> walking the entire list).
> >>
> >> Kinda my point. We already have all the hlist*() interface to deal
> >> with such cases. Having something which is evidently the trivial
> >> hlist hashtable and advertises as such in the interface can be
> >> helpful. I think we need that more than we need anything fancy.
> >>
> >> Heh, this is a debate about which one is less insignificant. I can
> >> see your point. I'd really like to hear what others think on this.
> >>
> >> Guys, do we want something which is evidently trivial hlist hashtable
> >> which can use hlist_*() API directly or do we want something better
> >> encapsulated?
> >
> > My 2 cents, FWIW: I think this specific effort should target a trivially
> > understandable API and implementation, for use-cases where one would be
> > tempted to reimplement his own trivial hash table anyway. So here
> > exposing hlist internals, with which kernel developers are already
> > familiar, seems like a good approach in my opinion, because hiding stuff
> > behind new abstraction might make the target users go away.
> >
> > Then, as we see the need, we can eventually merge a more elaborate hash
> > table with poneys and whatnot, but I would expect that the trivial hash
> > table implementation would still be useful. There are of course very
> > compelling reasons to use a more featureful hash table: automatic
> > resize, RT-aware updates, scalable updates, etc... but I see a purpose
> > for a trivial implementation. Its primary strong points being:
> >
> > - it's trivially understandable, so anyone how want to be really sure
> > they won't end up debugging the hash table instead of their
> > work-in-progress code can have a full understanding of it,
> > - it has few dependencies, which makes it easier to understand and
> > easier to use in some contexts (e.g. early boot).
> >
> > So I'm in favor of not overdoing the abstraction for this trivial hash
> > table, and honestly I would rather prefer that this trivial hash table
> > stays trivial. A more elaborate hash table should probably come as a
> > separate API.
> >
> > Thanks,
> >
> > Mathieu
> >
>
> Alright, let's keep it simple then.
>
> I do want to keep the hash_for_each[rcu,safe] family though.
Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:
struct hlist_head *head;
struct hlist_node *pos;
hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}
That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:
- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.
and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.
Thoughts ?
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency R 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote: > * Tejun Heo (t...@kernel.org) wrote: >> Hello, >> >> On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: >>> Thats the thing, the amount of things of things you can do with a given >>> bucket >>> is very limited. You can't add entries to any point besides the head >>> (without >>> walking the entire list). >> >> Kinda my point. We already have all the hlist*() interface to deal >> with such cases. Having something which is evidently the trivial >> hlist hashtable and advertises as such in the interface can be >> helpful. I think we need that more than we need anything fancy. >> >> Heh, this is a debate about which one is less insignificant. I can >> see your point. I'd really like to hear what others think on this. >> >> Guys, do we want something which is evidently trivial hlist hashtable >> which can use hlist_*() API directly or do we want something better >> encapsulated? > > My 2 cents, FWIW: I think this specific effort should target a trivially > understandable API and implementation, for use-cases where one would be > tempted to reimplement his own trivial hash table anyway. So here > exposing hlist internals, with which kernel developers are already > familiar, seems like a good approach in my opinion, because hiding stuff > behind new abstraction might make the target users go away. > > Then, as we see the need, we can eventually merge a more elaborate hash > table with poneys and whatnot, but I would expect that the trivial hash > table implementation would still be useful. There are of course very > compelling reasons to use a more featureful hash table: automatic > resize, RT-aware updates, scalable updates, etc... but I see a purpose > for a trivial implementation. Its primary strong points being: > > - it's trivially understandable, so anyone how want to be really sure > they won't end up debugging the hash table instead of their > work-in-progress code can have a full understanding of it, > - it has few dependencies, which makes it easier to understand and > easier to use in some contexts (e.g. early boot). > > So I'm in favor of not overdoing the abstraction for this trivial hash > table, and honestly I would rather prefer that this trivial hash table > stays trivial. A more elaborate hash table should probably come as a > separate API. > > Thanks, > > Mathieu > Alright, let's keep it simple then. I do want to keep the hash_for_each[rcu,safe] family though. -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
* Tejun Heo (t...@kernel.org) wrote:
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
Thats the thing, the amount of things of things you can do with a given
bucket
is very limited. You can't add entries to any point besides the head
(without
walking the entire list).
Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.
Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.
Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?
My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.
Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:
- it's trivially understandable, so anyone how want to be really sure
they won't end up debugging the hash table instead of their
work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
easier to use in some contexts (e.g. early boot).
So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.
Thanks,
Mathieu
Alright, let's keep it simple then.
I do want to keep the hash_for_each[rcu,safe] family though.
Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:
struct hlist_head *head;
struct hlist_node *pos;
hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}
That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:
- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.
and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.
Thoughts ?
In my opinion, the downside here is that it'll require 2 function calls and 2
levels of nesting for a simple hash iteration.
Those are macros, not functions. No function call is required. But I see
your point about nesting.
hash_for_each_bucket() will always be followed by an iteration of that
bucket, so splitting a hash_for_each() which does both into 2
different functions which will almost always must be called in that
given order sounds unintuitive to me.
It's also just 3 different possible iterators:
- hlist_for_each_entry
- hlist_for_each_entry_safe
- hlist_for_each_entry_rcu
So I think that it's a good price to pay - 2 extra macro definitions
in the header to save a macro call + nesting level in each place that
uses a hashtable.
I must admin I don't care that much one way or another.
Thanks,
Mathieu
Thanks,
Sasha
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency RD 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Mathieu Desnoyers (mathieu.desnoy...@efficios.com) wrote:
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
* Tejun Heo (t...@kernel.org) wrote:
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
Thats the thing, the amount of things of things you can do with a
given bucket
is very limited. You can't add entries to any point besides the head
(without
walking the entire list).
Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.
Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.
Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?
My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.
Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:
- it's trivially understandable, so anyone how want to be really sure
they won't end up debugging the hash table instead of their
work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
easier to use in some contexts (e.g. early boot).
So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.
Thanks,
Mathieu
Alright, let's keep it simple then.
I do want to keep the hash_for_each[rcu,safe] family though.
Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:
struct hlist_head *head;
struct hlist_node *pos;
hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}
That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:
- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.
and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.
Thoughts ?
In my opinion, the downside here is that it'll require 2 function calls and
2
levels of nesting for a simple hash iteration.
Those are macros, not functions. No function call is required. But I see
your point about nesting.
hash_for_each_bucket() will always be followed by an iteration of that
bucket, so splitting a hash_for_each() which does both into 2
different functions which will almost always must be called in that
given order sounds unintuitive to me.
It's also just 3 different possible iterators:
- hlist_for_each_entry
- hlist_for_each_entry_safe
- hlist_for_each_entry_rcu
So I think that it's a good price to pay - 2 extra macro definitions
in the header to save a macro call + nesting level in each place that
uses a hashtable.
I must admin I don't care that much one way or another.
Looking again at:
+#define hash_for_each_size(name, bits, bkt, node, obj, member)
\
+ for (bkt = 0; bkt HASH_SIZE(bits); bkt++)
\
+
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote: * Tejun Heo (t...@kernel.org) wrote: Hello, On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: Thats the thing, the amount of things of things you can do with a given bucket is very limited. You can't add entries to any point besides the head (without walking the entire list). Kinda my point. We already have all the hlist*() interface to deal with such cases. Having something which is evidently the trivial hlist hashtable and advertises as such in the interface can be helpful. I think we need that more than we need anything fancy. Heh, this is a debate about which one is less insignificant. I can see your point. I'd really like to hear what others think on this. Guys, do we want something which is evidently trivial hlist hashtable which can use hlist_*() API directly or do we want something better encapsulated? My 2 cents, FWIW: I think this specific effort should target a trivially understandable API and implementation, for use-cases where one would be tempted to reimplement his own trivial hash table anyway. So here exposing hlist internals, with which kernel developers are already familiar, seems like a good approach in my opinion, because hiding stuff behind new abstraction might make the target users go away. Then, as we see the need, we can eventually merge a more elaborate hash table with poneys and whatnot, but I would expect that the trivial hash table implementation would still be useful. There are of course very compelling reasons to use a more featureful hash table: automatic resize, RT-aware updates, scalable updates, etc... but I see a purpose for a trivial implementation. Its primary strong points being: - it's trivially understandable, so anyone how want to be really sure they won't end up debugging the hash table instead of their work-in-progress code can have a full understanding of it, - it has few dependencies, which makes it easier to understand and easier to use in some contexts (e.g. early boot). So I'm in favor of not overdoing the abstraction for this trivial hash table, and honestly I would rather prefer that this trivial hash table stays trivial. A more elaborate hash table should probably come as a separate API. Thanks, Mathieu Alright, let's keep it simple then. I do want to keep the hash_for_each[rcu,safe] family though. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
* Tejun Heo (t...@kernel.org) wrote:
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
Thats the thing, the amount of things of things you can do with a given
bucket
is very limited. You can't add entries to any point besides the head
(without
walking the entire list).
Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.
Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.
Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?
My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.
Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:
- it's trivially understandable, so anyone how want to be really sure
they won't end up debugging the hash table instead of their
work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
easier to use in some contexts (e.g. early boot).
So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.
Thanks,
Mathieu
Alright, let's keep it simple then.
I do want to keep the hash_for_each[rcu,safe] family though.
Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:
struct hlist_head *head;
struct hlist_node *pos;
hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}
That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:
- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.
and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.
Thoughts ?
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency RD 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 majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/28/2012 12:11 PM, Mathieu Desnoyers wrote:
* Sasha Levin (levinsasha...@gmail.com) wrote:
On 08/25/2012 06:24 AM, Mathieu Desnoyers wrote:
* Tejun Heo (t...@kernel.org) wrote:
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
Thats the thing, the amount of things of things you can do with a given
bucket
is very limited. You can't add entries to any point besides the head
(without
walking the entire list).
Kinda my point. We already have all the hlist*() interface to deal
with such cases. Having something which is evidently the trivial
hlist hashtable and advertises as such in the interface can be
helpful. I think we need that more than we need anything fancy.
Heh, this is a debate about which one is less insignificant. I can
see your point. I'd really like to hear what others think on this.
Guys, do we want something which is evidently trivial hlist hashtable
which can use hlist_*() API directly or do we want something better
encapsulated?
My 2 cents, FWIW: I think this specific effort should target a trivially
understandable API and implementation, for use-cases where one would be
tempted to reimplement his own trivial hash table anyway. So here
exposing hlist internals, with which kernel developers are already
familiar, seems like a good approach in my opinion, because hiding stuff
behind new abstraction might make the target users go away.
Then, as we see the need, we can eventually merge a more elaborate hash
table with poneys and whatnot, but I would expect that the trivial hash
table implementation would still be useful. There are of course very
compelling reasons to use a more featureful hash table: automatic
resize, RT-aware updates, scalable updates, etc... but I see a purpose
for a trivial implementation. Its primary strong points being:
- it's trivially understandable, so anyone how want to be really sure
they won't end up debugging the hash table instead of their
work-in-progress code can have a full understanding of it,
- it has few dependencies, which makes it easier to understand and
easier to use in some contexts (e.g. early boot).
So I'm in favor of not overdoing the abstraction for this trivial hash
table, and honestly I would rather prefer that this trivial hash table
stays trivial. A more elaborate hash table should probably come as a
separate API.
Thanks,
Mathieu
Alright, let's keep it simple then.
I do want to keep the hash_for_each[rcu,safe] family though.
Just a thought: if the API offered by the simple hash table focus on
providing a mechanism to find the hash bucket to which belongs the hash
chain containing the key looked up, and then expects the user to use the
hlist API to iterate on the chain (with or without the hlist _rcu
variant), then it might seem consistent that a helper providing
iteration over the entire table would actually just provide iteration on
all buckets, and let the user call the hlist for each iterator for each
node within the bucket, e.g.:
struct hlist_head *head;
struct hlist_node *pos;
hash_for_each_bucket(ht, head) {
hlist_for_each(pos, head) {
...
}
}
That way you only have to provide one single macro
(hash_for_each_bucket), and rely on the already existing:
- hlist_for_each_entry
- hlist_for_each_safe
- hlist_for_each_entry_rcu
- hlist_for_each_safe_rcu
.
and various flavors that can appear in the future without duplicating
this API. So you won't even have to create _rcu, _safe, nor _safe_rcu
versions of the hash_for_each_bucket macro.
Thoughts ?
In my opinion, the downside here is that it'll require 2 function calls and 2
levels of nesting for a simple hash iteration.
hash_for_each_bucket() will always be followed by an iteration of that bucket,
so splitting a hash_for_each() which does both into 2 different functions which
will almost always must be called in that given order sounds unintuitive to me.
It's also just 3 different possible iterators:
- hlist_for_each_entry
- hlist_for_each_entry_safe
- hlist_for_each_entry_rcu
So I think that it's a good price to pay - 2 extra macro definitions in the
header to save a macro call + nesting level in each place that uses a hashtable.
Thanks,
Sasha
Thanks,
Mathieu
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Tejun Heo (t...@kernel.org) wrote: > Hello, > > On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: > > Thats the thing, the amount of things of things you can do with a given > > bucket > > is very limited. You can't add entries to any point besides the head > > (without > > walking the entire list). > > Kinda my point. We already have all the hlist*() interface to deal > with such cases. Having something which is evidently the trivial > hlist hashtable and advertises as such in the interface can be > helpful. I think we need that more than we need anything fancy. > > Heh, this is a debate about which one is less insignificant. I can > see your point. I'd really like to hear what others think on this. > > Guys, do we want something which is evidently trivial hlist hashtable > which can use hlist_*() API directly or do we want something better > encapsulated? My 2 cents, FWIW: I think this specific effort should target a trivially understandable API and implementation, for use-cases where one would be tempted to reimplement his own trivial hash table anyway. So here exposing hlist internals, with which kernel developers are already familiar, seems like a good approach in my opinion, because hiding stuff behind new abstraction might make the target users go away. Then, as we see the need, we can eventually merge a more elaborate hash table with poneys and whatnot, but I would expect that the trivial hash table implementation would still be useful. There are of course very compelling reasons to use a more featureful hash table: automatic resize, RT-aware updates, scalable updates, etc... but I see a purpose for a trivial implementation. Its primary strong points being: - it's trivially understandable, so anyone how want to be really sure they won't end up debugging the hash table instead of their work-in-progress code can have a full understanding of it, - it has few dependencies, which makes it easier to understand and easier to use in some contexts (e.g. early boot). So I'm in favor of not overdoing the abstraction for this trivial hash table, and honestly I would rather prefer that this trivial hash table stays trivial. A more elaborate hash table should probably come as a separate API. Thanks, Mathieu -- Mathieu Desnoyers Operating System Efficiency R 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: > Thats the thing, the amount of things of things you can do with a given bucket > is very limited. You can't add entries to any point besides the head (without > walking the entire list). Kinda my point. We already have all the hlist*() interface to deal with such cases. Having something which is evidently the trivial hlist hashtable and advertises as such in the interface can be helpful. I think we need that more than we need anything fancy. Heh, this is a debate about which one is less insignificant. I can see your point. I'd really like to hear what others think on this. Guys, do we want something which is evidently trivial hlist hashtable which can use hlist_*() API directly or do we want something better encapsulated? Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
>> Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place >> yet >> that needed direct access to the bucket itself. > > Because whole hash table walking is much less common and we can avoid > another full set of iterators. I don't agree. Out of 32 places which now use a hashtable iterator of some kind, 12 of them (38%) walk the entire table. The thing is that usually data structures are indexable by more than one key, so usually hashtables are fully walked in cold paths to look for different keys. Take kernel/workqueue.c for example: There are 4 places which do a key lookup (find_worker_executing_work()) and 3 places which fully walk the entire table (for_each_busy_worker()). >> This basically means 11 macros/functions that would let us have full >> encapsulation and will make it very easy for future implementations to work >> with >> this API instead of making up a new one. It's also not significantly (+~2-3) >> more than the ones you listed. > > I'm not sure whether full encapsulation is a good idea for trivial > hashtable. For higher level stuff, sure but at this level I think > benefits coming from known obvious implementation can be larger. > e.g. suppose the caller knows certain entries to be way colder than > others and wants to put them at the end of the chain. Thats the thing, the amount of things of things you can do with a given bucket is very limited. You can't add entries to any point besides the head (without walking the entire list). Basically you can do only two things with a bucket: - Add something to it at a very specific place. - Walk it So I don't understand whats the point in exposing the internal structure of the hashtable if there's nothing significant that can be gained from it by the user. > > So, I think implmenting the minimal set of helpers which reflect the > underlying trivial implementation explicitly could actually be better > even when discounting the reduced number of wrappers. > > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, On Fri, Aug 24, 2012 at 10:53:45PM +0200, Sasha Levin wrote: > Yup, but we could be using the same API for dynamic non-resizable and static > if > we go with the DECLARE/hash_init. We could switch between them (and other > implementations) without having to change the code. I think it's better to stick with the usual conventions. > > * DECLARE/DEFINE > > * hash_head() > > * hash_for_each_head() > > * hash_add*() > > * hash_for_each_possible*() > * hash_for_each*() ? > > Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place > yet > that needed direct access to the bucket itself. Because whole hash table walking is much less common and we can avoid another full set of iterators. > This basically means 11 macros/functions that would let us have full > encapsulation and will make it very easy for future implementations to work > with > this API instead of making up a new one. It's also not significantly (+~2-3) > more than the ones you listed. I'm not sure whether full encapsulation is a good idea for trivial hashtable. For higher level stuff, sure but at this level I think benefits coming from known obvious implementation can be larger. e.g. suppose the caller knows certain entries to be way colder than others and wants to put them at the end of the chain. So, I think implmenting the minimal set of helpers which reflect the underlying trivial implementation explicitly could actually be better even when discounting the reduced number of wrappers. Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/24/2012 10:33 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote: >>> If this implementation is about the common trivial case, why not just >>> have the usual DECLARE/DEFINE_HASHTABLE() combination? >> >> When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() >> look? > > Hmmm? DECLARE/DEFINE are usually for static ones. Yup, but we could be using the same API for dynamic non-resizable and static if we go with the DECLARE/hash_init. We could switch between them (and other implementations) without having to change the code. >>> I don't know. If we stick to the static (or even !resize dymaic) >>> straight-forward hash - and we need something like that - I don't see >>> what the full encapsulation buys us other than a lot of trivial >>> wrappers. >> >> Which macros do you consider as trivial within the current API? >> >> Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and >> get_bucket(), but it would make the life of anyone who wants a slightly >> different hashtable a hell. > > Wouldn't the following be enough to get most of the benefits? > > * DECLARE/DEFINE > * hash_head() > * hash_for_each_head() > * hash_add*() > * hash_for_each_possible*() * hash_for_each*() ? Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet that needed direct access to the bucket itself. Consider the following list: - DECLARE - hash_init - hash_add - hash_del - hash_hashed - hash_for_each_[rcu, safe] - hash_for_each_possible[rcu, safe] This basically means 11 macros/functions that would let us have full encapsulation and will make it very easy for future implementations to work with this API instead of making up a new one. It's also not significantly (+~2-3) more than the ones you listed. >> I think that right now the only real trivial wrapper is hash_hashed(), and I >> think it's a price worth paying to have a single hashtable API instead of >> fragmenting it when more implementations come along. > > I'm not objecting strongly against full encapsulation but having this > many thin wrappers makes me scratch my head. > > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote: > > If this implementation is about the common trivial case, why not just > > have the usual DECLARE/DEFINE_HASHTABLE() combination? > > When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() > look? Hmmm? DECLARE/DEFINE are usually for static ones. > > I don't know. If we stick to the static (or even !resize dymaic) > > straight-forward hash - and we need something like that - I don't see > > what the full encapsulation buys us other than a lot of trivial > > wrappers. > > Which macros do you consider as trivial within the current API? > > Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and > get_bucket(), but it would make the life of anyone who wants a slightly > different hashtable a hell. Wouldn't the following be enough to get most of the benefits? * DECLARE/DEFINE * hash_head() * hash_for_each_head() * hash_add*() * hash_for_each_possible*() > I think that right now the only real trivial wrapper is hash_hashed(), and I > think it's a price worth paying to have a single hashtable API instead of > fragmenting it when more implementations come along. I'm not objecting strongly against full encapsulation but having this many thin wrappers makes me scratch my head. Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/24/2012 09:59 PM, Tejun Heo wrote: > Hello, Sasha. > > On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote: >>> I think this is problematic. It looks exactly like other existing >>> DEFINE macros yet what its semantics is different. I don't think >>> that's a good idea. >> >> I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. > > If this implementation is about the common trivial case, why not just > have the usual DECLARE/DEFINE_HASHTABLE() combination? When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look? >>> So, I think it would be best to keep this one as straight-forward and >>> trivial as possible. Helper macros to help its users are fine but >>> let's please not go for full encapsulation. >> >> What if we cut off the dynamic allocated (but not resizable) hashtable out >> for >> the moment, and focus on the most common statically allocated hashtable case? >> >> The benefits would be: >> >> - Getting rid of all the _size() macros, which will make the amount of >> helpers >> here reasonable. >> - Dynamically allocated hashtable can be easily added as a separate >> implementation using the same API. We already have some of those in the >> kernel... > > It seems we have enough of this static usage and solving the static > case first shouldn't hinder the dynamic (!resize) case later, so, > yeah, sounds good to me. > >> - When that's ready, I feel it's a shame to lose full encapsulation just >> due to >> hash_hashed(). > > I don't know. If we stick to the static (or even !resize dymaic) > straight-forward hash - and we need something like that - I don't see > what the full encapsulation buys us other than a lot of trivial > wrappers. Which macros do you consider as trivial within the current API? Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and get_bucket(), but it would make the life of anyone who wants a slightly different hashtable a hell. I think that right now the only real trivial wrapper is hash_hashed(), and I think it's a price worth paying to have a single hashtable API instead of fragmenting it when more implementations come along. Thanks, Sasha > > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote: > > I think this is problematic. It looks exactly like other existing > > DEFINE macros yet what its semantics is different. I don't think > > that's a good idea. > > I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. If this implementation is about the common trivial case, why not just have the usual DECLARE/DEFINE_HASHTABLE() combination? > > So, I think it would be best to keep this one as straight-forward and > > trivial as possible. Helper macros to help its users are fine but > > let's please not go for full encapsulation. > > What if we cut off the dynamic allocated (but not resizable) hashtable out for > the moment, and focus on the most common statically allocated hashtable case? > > The benefits would be: > > - Getting rid of all the _size() macros, which will make the amount of > helpers > here reasonable. > - Dynamically allocated hashtable can be easily added as a separate > implementation using the same API. We already have some of those in the > kernel... It seems we have enough of this static usage and solving the static case first shouldn't hinder the dynamic (!resize) case later, so, yeah, sounds good to me. > - When that's ready, I feel it's a shame to lose full encapsulation just due > to > hash_hashed(). I don't know. If we stick to the static (or even !resize dymaic) straight-forward hash - and we need something like that - I don't see what the full encapsulation buys us other than a lot of trivial wrappers. Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/23/2012 10:04 PM, Tejun Heo wrote: > Hello, Sasha. > > On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote: >>> I think the almost trivial nature of hlist hashtables makes this a bit >>> tricky and I'm not very sure but having this combinatory explosion is >>> a bit dazzling when the same functionality can be achieved by simply >>> combining operations which are already defined and named considering >>> hashtable. I'm not feeling too strong about this tho. What do others >>> think? >> >> I'm thinking that this hashtable API will have 2 purposes: First, it would >> prevent the excessive duplication of hashtable implementations all around >> the code. >> >> Second, it will allow more easily interchangeable hashtable implementations >> to >> find their way into the kernel. There are several maintainers who would be >> happy >> to see dynamically sized RCU hashtable, and I'm guessing that several more >> variants could be added based on needs in specific modules. >> >> The second reason is why several things you've mentioned look the way they >> are: >> >> - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since >> initialization for other hashtables may be more complicated than the static >> initialization for this implementation, which means that any place that used >> DEFINE_HASHTABLE() and didn't do hash_init() will be buggy. > > I think this is problematic. It looks exactly like other existing > DEFINE macros yet what its semantics is different. I don't think > that's a good idea. I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. >> I'm actually tempted in hiding hlist completely from hashtable users, >> probably >> by simply defining a hash_head/hash_node on top of the hlist_ counterparts. > > I think that it would be best to keep this one simple & obvious, which > already has enough in-kernel users to justify its existence. There > are significant benefits in being trivially understandable and > expectable. If we want more advanced ones - say resizing, hybrid or > what not, let's make that a separate one. No need to complicate the > common straight-forward case for that. > > So, I think it would be best to keep this one as straight-forward and > trivial as possible. Helper macros to help its users are fine but > let's please not go for full encapsulation. What if we cut off the dynamic allocated (but not resizable) hashtable out for the moment, and focus on the most common statically allocated hashtable case? The benefits would be: - Getting rid of all the _size() macros, which will make the amount of helpers here reasonable. - Dynamically allocated hashtable can be easily added as a separate implementation using the same API. We already have some of those in the kernel... - When that's ready, I feel it's a shame to lose full encapsulation just due to hash_hashed(). Thanks, Sasha > > Thanks. > -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/23/2012 10:04 PM, Tejun Heo wrote: Hello, Sasha. On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote: I think the almost trivial nature of hlist hashtables makes this a bit tricky and I'm not very sure but having this combinatory explosion is a bit dazzling when the same functionality can be achieved by simply combining operations which are already defined and named considering hashtable. I'm not feeling too strong about this tho. What do others think? I'm thinking that this hashtable API will have 2 purposes: First, it would prevent the excessive duplication of hashtable implementations all around the code. Second, it will allow more easily interchangeable hashtable implementations to find their way into the kernel. There are several maintainers who would be happy to see dynamically sized RCU hashtable, and I'm guessing that several more variants could be added based on needs in specific modules. The second reason is why several things you've mentioned look the way they are: - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since initialization for other hashtables may be more complicated than the static initialization for this implementation, which means that any place that used DEFINE_HASHTABLE() and didn't do hash_init() will be buggy. I think this is problematic. It looks exactly like other existing DEFINE macros yet what its semantics is different. I don't think that's a good idea. I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. I'm actually tempted in hiding hlist completely from hashtable users, probably by simply defining a hash_head/hash_node on top of the hlist_ counterparts. I think that it would be best to keep this one simple obvious, which already has enough in-kernel users to justify its existence. There are significant benefits in being trivially understandable and expectable. If we want more advanced ones - say resizing, hybrid or what not, let's make that a separate one. No need to complicate the common straight-forward case for that. So, I think it would be best to keep this one as straight-forward and trivial as possible. Helper macros to help its users are fine but let's please not go for full encapsulation. What if we cut off the dynamic allocated (but not resizable) hashtable out for the moment, and focus on the most common statically allocated hashtable case? The benefits would be: - Getting rid of all the _size() macros, which will make the amount of helpers here reasonable. - Dynamically allocated hashtable can be easily added as a separate implementation using the same API. We already have some of those in the kernel... - When that's ready, I feel it's a shame to lose full encapsulation just due to hash_hashed(). Thanks, Sasha Thanks. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote: I think this is problematic. It looks exactly like other existing DEFINE macros yet what its semantics is different. I don't think that's a good idea. I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. If this implementation is about the common trivial case, why not just have the usual DECLARE/DEFINE_HASHTABLE() combination? So, I think it would be best to keep this one as straight-forward and trivial as possible. Helper macros to help its users are fine but let's please not go for full encapsulation. What if we cut off the dynamic allocated (but not resizable) hashtable out for the moment, and focus on the most common statically allocated hashtable case? The benefits would be: - Getting rid of all the _size() macros, which will make the amount of helpers here reasonable. - Dynamically allocated hashtable can be easily added as a separate implementation using the same API. We already have some of those in the kernel... It seems we have enough of this static usage and solving the static case first shouldn't hinder the dynamic (!resize) case later, so, yeah, sounds good to me. - When that's ready, I feel it's a shame to lose full encapsulation just due to hash_hashed(). I don't know. If we stick to the static (or even !resize dymaic) straight-forward hash - and we need something like that - I don't see what the full encapsulation buys us other than a lot of trivial wrappers. Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/24/2012 09:59 PM, Tejun Heo wrote: Hello, Sasha. On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote: I think this is problematic. It looks exactly like other existing DEFINE macros yet what its semantics is different. I don't think that's a good idea. I can switch that to be DECLARE_HASHTABLE() if the issue is semantics. If this implementation is about the common trivial case, why not just have the usual DECLARE/DEFINE_HASHTABLE() combination? When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look? So, I think it would be best to keep this one as straight-forward and trivial as possible. Helper macros to help its users are fine but let's please not go for full encapsulation. What if we cut off the dynamic allocated (but not resizable) hashtable out for the moment, and focus on the most common statically allocated hashtable case? The benefits would be: - Getting rid of all the _size() macros, which will make the amount of helpers here reasonable. - Dynamically allocated hashtable can be easily added as a separate implementation using the same API. We already have some of those in the kernel... It seems we have enough of this static usage and solving the static case first shouldn't hinder the dynamic (!resize) case later, so, yeah, sounds good to me. - When that's ready, I feel it's a shame to lose full encapsulation just due to hash_hashed(). I don't know. If we stick to the static (or even !resize dymaic) straight-forward hash - and we need something like that - I don't see what the full encapsulation buys us other than a lot of trivial wrappers. Which macros do you consider as trivial within the current API? Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and get_bucket(), but it would make the life of anyone who wants a slightly different hashtable a hell. I think that right now the only real trivial wrapper is hash_hashed(), and I think it's a price worth paying to have a single hashtable API instead of fragmenting it when more implementations come along. Thanks, Sasha Thanks. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote: If this implementation is about the common trivial case, why not just have the usual DECLARE/DEFINE_HASHTABLE() combination? When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look? Hmmm? DECLARE/DEFINE are usually for static ones. I don't know. If we stick to the static (or even !resize dymaic) straight-forward hash - and we need something like that - I don't see what the full encapsulation buys us other than a lot of trivial wrappers. Which macros do you consider as trivial within the current API? Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and get_bucket(), but it would make the life of anyone who wants a slightly different hashtable a hell. Wouldn't the following be enough to get most of the benefits? * DECLARE/DEFINE * hash_head() * hash_for_each_head() * hash_add*() * hash_for_each_possible*() I think that right now the only real trivial wrapper is hash_hashed(), and I think it's a price worth paying to have a single hashtable API instead of fragmenting it when more implementations come along. I'm not objecting strongly against full encapsulation but having this many thin wrappers makes me scratch my head. Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 08/24/2012 10:33 PM, Tejun Heo wrote: Hello, Sasha. On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote: If this implementation is about the common trivial case, why not just have the usual DECLARE/DEFINE_HASHTABLE() combination? When we add the dynamic non-resizable support, how would DEFINE_HASHTABLE() look? Hmmm? DECLARE/DEFINE are usually for static ones. Yup, but we could be using the same API for dynamic non-resizable and static if we go with the DECLARE/hash_init. We could switch between them (and other implementations) without having to change the code. I don't know. If we stick to the static (or even !resize dymaic) straight-forward hash - and we need something like that - I don't see what the full encapsulation buys us other than a lot of trivial wrappers. Which macros do you consider as trivial within the current API? Basically this entire thing could be reduced to DEFINE/DECLARE_HASHTABLE and get_bucket(), but it would make the life of anyone who wants a slightly different hashtable a hell. Wouldn't the following be enough to get most of the benefits? * DECLARE/DEFINE * hash_head() * hash_for_each_head() * hash_add*() * hash_for_each_possible*() * hash_for_each*() ? Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet that needed direct access to the bucket itself. Consider the following list: - DECLARE - hash_init - hash_add - hash_del - hash_hashed - hash_for_each_[rcu, safe] - hash_for_each_possible[rcu, safe] This basically means 11 macros/functions that would let us have full encapsulation and will make it very easy for future implementations to work with this API instead of making up a new one. It's also not significantly (+~2-3) more than the ones you listed. I think that right now the only real trivial wrapper is hash_hashed(), and I think it's a price worth paying to have a single hashtable API instead of fragmenting it when more implementations come along. I'm not objecting strongly against full encapsulation but having this many thin wrappers makes me scratch my head. Thanks. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, On Fri, Aug 24, 2012 at 10:53:45PM +0200, Sasha Levin wrote: Yup, but we could be using the same API for dynamic non-resizable and static if we go with the DECLARE/hash_init. We could switch between them (and other implementations) without having to change the code. I think it's better to stick with the usual conventions. * DECLARE/DEFINE * hash_head() * hash_for_each_head() * hash_add*() * hash_for_each_possible*() * hash_for_each*() ? Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet that needed direct access to the bucket itself. Because whole hash table walking is much less common and we can avoid another full set of iterators. This basically means 11 macros/functions that would let us have full encapsulation and will make it very easy for future implementations to work with this API instead of making up a new one. It's also not significantly (+~2-3) more than the ones you listed. I'm not sure whether full encapsulation is a good idea for trivial hashtable. For higher level stuff, sure but at this level I think benefits coming from known obvious implementation can be larger. e.g. suppose the caller knows certain entries to be way colder than others and wants to put them at the end of the chain. So, I think implmenting the minimal set of helpers which reflect the underlying trivial implementation explicitly could actually be better even when discounting the reduced number of wrappers. Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Why do we need hash_head/hash_for_each_head()? I haven't stumbled on a place yet that needed direct access to the bucket itself. Because whole hash table walking is much less common and we can avoid another full set of iterators. I don't agree. Out of 32 places which now use a hashtable iterator of some kind, 12 of them (38%) walk the entire table. The thing is that usually data structures are indexable by more than one key, so usually hashtables are fully walked in cold paths to look for different keys. Take kernel/workqueue.c for example: There are 4 places which do a key lookup (find_worker_executing_work()) and 3 places which fully walk the entire table (for_each_busy_worker()). This basically means 11 macros/functions that would let us have full encapsulation and will make it very easy for future implementations to work with this API instead of making up a new one. It's also not significantly (+~2-3) more than the ones you listed. I'm not sure whether full encapsulation is a good idea for trivial hashtable. For higher level stuff, sure but at this level I think benefits coming from known obvious implementation can be larger. e.g. suppose the caller knows certain entries to be way colder than others and wants to put them at the end of the chain. Thats the thing, the amount of things of things you can do with a given bucket is very limited. You can't add entries to any point besides the head (without walking the entire list). Basically you can do only two things with a bucket: - Add something to it at a very specific place. - Walk it So I don't understand whats the point in exposing the internal structure of the hashtable if there's nothing significant that can be gained from it by the user. So, I think implmenting the minimal set of helpers which reflect the underlying trivial implementation explicitly could actually be better even when discounting the reduced number of wrappers. Thanks. -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: Thats the thing, the amount of things of things you can do with a given bucket is very limited. You can't add entries to any point besides the head (without walking the entire list). Kinda my point. We already have all the hlist*() interface to deal with such cases. Having something which is evidently the trivial hlist hashtable and advertises as such in the interface can be helpful. I think we need that more than we need anything fancy. Heh, this is a debate about which one is less insignificant. I can see your point. I'd really like to hear what others think on this. Guys, do we want something which is evidently trivial hlist hashtable which can use hlist_*() API directly or do we want something better encapsulated? Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
* Tejun Heo (t...@kernel.org) wrote: Hello, On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote: Thats the thing, the amount of things of things you can do with a given bucket is very limited. You can't add entries to any point besides the head (without walking the entire list). Kinda my point. We already have all the hlist*() interface to deal with such cases. Having something which is evidently the trivial hlist hashtable and advertises as such in the interface can be helpful. I think we need that more than we need anything fancy. Heh, this is a debate about which one is less insignificant. I can see your point. I'd really like to hear what others think on this. Guys, do we want something which is evidently trivial hlist hashtable which can use hlist_*() API directly or do we want something better encapsulated? My 2 cents, FWIW: I think this specific effort should target a trivially understandable API and implementation, for use-cases where one would be tempted to reimplement his own trivial hash table anyway. So here exposing hlist internals, with which kernel developers are already familiar, seems like a good approach in my opinion, because hiding stuff behind new abstraction might make the target users go away. Then, as we see the need, we can eventually merge a more elaborate hash table with poneys and whatnot, but I would expect that the trivial hash table implementation would still be useful. There are of course very compelling reasons to use a more featureful hash table: automatic resize, RT-aware updates, scalable updates, etc... but I see a purpose for a trivial implementation. Its primary strong points being: - it's trivially understandable, so anyone how want to be really sure they won't end up debugging the hash table instead of their work-in-progress code can have a full understanding of it, - it has few dependencies, which makes it easier to understand and easier to use in some contexts (e.g. early boot). So I'm in favor of not overdoing the abstraction for this trivial hash table, and honestly I would rather prefer that this trivial hash table stays trivial. A more elaborate hash table should probably come as a separate API. Thanks, Mathieu -- Mathieu Desnoyers Operating System Efficiency RD 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 majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote: > > I think the almost trivial nature of hlist hashtables makes this a bit > > tricky and I'm not very sure but having this combinatory explosion is > > a bit dazzling when the same functionality can be achieved by simply > > combining operations which are already defined and named considering > > hashtable. I'm not feeling too strong about this tho. What do others > > think? > > I'm thinking that this hashtable API will have 2 purposes: First, it would > prevent the excessive duplication of hashtable implementations all around the > code. > > Second, it will allow more easily interchangeable hashtable implementations to > find their way into the kernel. There are several maintainers who would be > happy > to see dynamically sized RCU hashtable, and I'm guessing that several more > variants could be added based on needs in specific modules. > > The second reason is why several things you've mentioned look the way they > are: > > - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since > initialization for other hashtables may be more complicated than the static > initialization for this implementation, which means that any place that used > DEFINE_HASHTABLE() and didn't do hash_init() will be buggy. I think this is problematic. It looks exactly like other existing DEFINE macros yet what its semantics is different. I don't think that's a good idea. > I'm actually tempted in hiding hlist completely from hashtable users, probably > by simply defining a hash_head/hash_node on top of the hlist_ counterparts. I think that it would be best to keep this one simple & obvious, which already has enough in-kernel users to justify its existence. There are significant benefits in being trivially understandable and expectable. If we want more advanced ones - say resizing, hybrid or what not, let's make that a separate one. No need to complicate the common straight-forward case for that. So, I think it would be best to keep this one as straight-forward and trivial as possible. Helper macros to help its users are fine but let's please not go for full encapsulation. Thanks. -- tejun -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha. On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote: I think the almost trivial nature of hlist hashtables makes this a bit tricky and I'm not very sure but having this combinatory explosion is a bit dazzling when the same functionality can be achieved by simply combining operations which are already defined and named considering hashtable. I'm not feeling too strong about this tho. What do others think? I'm thinking that this hashtable API will have 2 purposes: First, it would prevent the excessive duplication of hashtable implementations all around the code. Second, it will allow more easily interchangeable hashtable implementations to find their way into the kernel. There are several maintainers who would be happy to see dynamically sized RCU hashtable, and I'm guessing that several more variants could be added based on needs in specific modules. The second reason is why several things you've mentioned look the way they are: - No DEFINE_HASHTABLE(): I wanted to force the use of hash_init() since initialization for other hashtables may be more complicated than the static initialization for this implementation, which means that any place that used DEFINE_HASHTABLE() and didn't do hash_init() will be buggy. I think this is problematic. It looks exactly like other existing DEFINE macros yet what its semantics is different. I don't think that's a good idea. I'm actually tempted in hiding hlist completely from hashtable users, probably by simply defining a hash_head/hash_node on top of the hlist_ counterparts. I think that it would be best to keep this one simple obvious, which already has enough in-kernel users to justify its existence. There are significant benefits in being trivially understandable and expectable. If we want more advanced ones - say resizing, hybrid or what not, let's make that a separate one. No need to complicate the common straight-forward case for that. So, I think it would be best to keep this one as straight-forward and trivial as possible. Helper macros to help its users are fine but let's please not go for full encapsulation. Thanks. -- tejun -- To unsubscribe from this list: send the line unsubscribe linux-kernel in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hi Tejun,
On 08/22/2012 08:01 PM, Tejun Heo wrote:
> Hello, Sasha.
>
> On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
>> +#define DEFINE_HASHTABLE(name, bits)
>> \
>> +struct hlist_head name[HASH_SIZE(bits)];
>
> Shouldn't this be something like the following?
>
> #define DEFINE_HASHTABLE(name, bits) \
> struct hlist_head name[HASH_SIZE(bits)] = \
> { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
>
> Also, given that the declaration isn't non-trivial, you'll probably
> want a matching DECLARE_HASHTABLE() macro too.
I figured we might do a DEFINE_HASHTABLE() to prevent the need from using
hash_init() on hashtables defined this way, but I preferred not to since we may
end up wanting a more complex initialization (I'll explain why extensively
below).
>> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
>> kernels. */
>> +#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
>> hash_long((val), (bits)))
>
> Why is the branching condition sizeof(val) == 4 instead of <= 4?
No reason, will fix.
> Also, no biggie but why isn't this macro in caps?
I had this plan in my mind to move it into linux/hash.h at some stage later, and
the API there uses low caps even for macros (hash_long()).
>> +/**
>> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
>> + * @hashtable: hashtable to add to
>> + * @bits: bit count used for hashing
>> + * @node: the hlist_node of the object to be added
>> + * @key: the key of the object to be added
>> + */
>> +#define hash_add_rcu_size(hashtable, bits, node, key)
>> \
>> +hlist_add_head_rcu(node, [hash_min(key, bits)]);
>> +
>> +/**
>> + * hash_add_rcu - add an object to a rcu enabled hashtable
>> + * @hashtable: hashtable to add to
>> + * @node: the hlist_node of the object to be added
>> + * @key: the key of the object to be added
>> + */
>> +#define hash_add_rcu(hashtable, node, key)
>> \
>> +hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
>
> Or maybe we're better off with hash_head_size() and hash_head()? I'll
> expand on it later. Please bear with me.
>
>> +/**
>> + * hash_hashed - check whether an object is in any hashtable
>> + * @node: the hlist_node of the object to be checked
>> + */
>> +#define hash_hashed(node) (!hlist_unhashed(node))
>
> As the 'h' in hlist* stand for hash anyway and I think this type of
> thin wrappers tend to obfuscate more than anything else.
>
>> +/**
>> + * hash_del - remove an object from a hashtable
>> + * @node: hlist_node of the object to remove
>> + */
>> +static inline void hash_del(struct hlist_node *node)
>> +{
>> +hlist_del_init(node);
>> +}
>> +
>> +/**
>> + * hash_del_rcu - remove an object from a rcu enabled hashtable
>> + * @node: hlist_node of the object to remove
>> + */
>> +static inline void hash_del_rcu(struct hlist_node *node)
>> +{
>> +hlist_del_init_rcu(node);
>> +}
>
> If we do that, we can remove all these thin wrappers.
>
>> +#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, [bkt], member)
> ..
>> +#define hash_for_each(name, bkt, node, obj, member)
>> \
>> +hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)
>> \
>> +for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
>> \
>> +hlist_for_each_entry_rcu(obj, node, [bkt], member)
> ...
>> +#define hash_for_each_rcu(name, bkt, node, obj, member)
>> \
>> +hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
> ...
>> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)
>> \
>> +for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
>> \
>> +hlist_for_each_entry_safe(obj, node, tmp, [bkt], member)
> ...
>> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member)
>> \
>> +hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,
>> \
>> +tmp, obj, member)
> ...
>> +#define hash_for_each_possible_size(name, obj, bits, node, member, key)
>> \
>> +hlist_for_each_entry(obj, node, [hash_min(key, bits)], member)
> ...
>> +#define hash_for_each_possible(name, obj, node, member, key)
>> \
>> +hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member,
>> key)
> ...
>> +#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key)
>> \
>> +hlist_for_each_entry_rcu(obj, node, [hash_min(key, bits)],
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 23/08/12 04:01, Tejun Heo wrote:
> Hello, Sasha.
>
> On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
>> +#define DEFINE_HASHTABLE(name, bits)
>> \
>> +struct hlist_head name[HASH_SIZE(bits)];
>
> Shouldn't this be something like the following?
>
> #define DEFINE_HASHTABLE(name, bits) \
> struct hlist_head name[HASH_SIZE(bits)] = \
> { [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
>
> Also, given that the declaration isn't non-trivial, you'll probably
> want a matching DECLARE_HASHTABLE() macro too.
>
>> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
>> kernels. */
>> +#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
>> hash_long((val), (bits)))
>
> Why is the branching condition sizeof(val) == 4 instead of <= 4?
> Also, no biggie but why isn't this macro in caps?
It should probably use gcc's statement expression extensions to prevent
side-effect issues with the arguments:
#define hash_min ({ \
sizeof(val) <= 4 ? \
hash_32(val, bits) :\
hash_long(val, bits)); \
})
~Ryan
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha.
On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
> +#define DEFINE_HASHTABLE(name, bits) \
> + struct hlist_head name[HASH_SIZE(bits)];
Shouldn't this be something like the following?
#define DEFINE_HASHTABLE(name, bits)\
struct hlist_head name[HASH_SIZE(bits)] = \
{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.
> +/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
> kernels. */
> +#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
> hash_long((val), (bits)))
Why is the branching condition sizeof(val) == 4 instead of <= 4?
Also, no biggie but why isn't this macro in caps?
> +/**
> + * hash_add_size - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_size(hashtable, bits, node, key)
> \
> + hlist_add_head(node, [hash_min(key, bits)]);
> +
> +/**
> + * hash_add - add an object to a hashtable
> + * @hashtable: hashtable to add to
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add(hashtable, node, key)
> \
> + hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
It would be nice if the comments actually say something which can
differentiate the two. Ditto for rcu variants.
> +/**
> + * hash_add_rcu_size - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @bits: bit count used for hashing
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu_size(hashtable, bits, node, key)
> \
> + hlist_add_head_rcu(node, [hash_min(key, bits)]);
> +
> +/**
> + * hash_add_rcu - add an object to a rcu enabled hashtable
> + * @hashtable: hashtable to add to
> + * @node: the hlist_node of the object to be added
> + * @key: the key of the object to be added
> + */
> +#define hash_add_rcu(hashtable, node, key)
> \
> + hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
Or maybe we're better off with hash_head_size() and hash_head()? I'll
expand on it later. Please bear with me.
> +/**
> + * hash_hashed - check whether an object is in any hashtable
> + * @node: the hlist_node of the object to be checked
> + */
> +#define hash_hashed(node) (!hlist_unhashed(node))
As the 'h' in hlist* stand for hash anyway and I think this type of
thin wrappers tend to obfuscate more than anything else.
> +/**
> + * hash_del - remove an object from a hashtable
> + * @node: hlist_node of the object to remove
> + */
> +static inline void hash_del(struct hlist_node *node)
> +{
> + hlist_del_init(node);
> +}
> +
> +/**
> + * hash_del_rcu - remove an object from a rcu enabled hashtable
> + * @node: hlist_node of the object to remove
> + */
> +static inline void hash_del_rcu(struct hlist_node *node)
> +{
> + hlist_del_init_rcu(node);
> +}
If we do that, we can remove all these thin wrappers.
> +#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, [bkt], member)
..
> +#define hash_for_each(name, bkt, node, obj, member)
> \
> + hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)
> \
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> \
> + hlist_for_each_entry_rcu(obj, node, [bkt], member)
...
> +#define hash_for_each_rcu(name, bkt, node, obj, member)
> \
> + hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
...
> +#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)
> \
> + for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
> \
> + hlist_for_each_entry_safe(obj, node, tmp, [bkt], member)
...
> +#define hash_for_each_safe(name, bkt, node, tmp, obj, member)
> \
> + hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,
> \
> + tmp, obj, member)
...
> +#define hash_for_each_possible_size(name, obj, bits, node, member, key)
> \
> + hlist_for_each_entry(obj, node, [hash_min(key, bits)], member)
...
> +#define hash_for_each_possible(name, obj, node, member,
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hello, Sasha.
On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
+#define DEFINE_HASHTABLE(name, bits) \
+ struct hlist_head name[HASH_SIZE(bits)];
Shouldn't this be something like the following?
#define DEFINE_HASHTABLE(name, bits)\
struct hlist_head name[HASH_SIZE(bits)] = \
{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
kernels. */
+#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
hash_long((val), (bits)))
Why is the branching condition sizeof(val) == 4 instead of = 4?
Also, no biggie but why isn't this macro in caps?
+/**
+ * hash_add_size - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_size(hashtable, bits, node, key)
\
+ hlist_add_head(node, hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key)
\
+ hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
It would be nice if the comments actually say something which can
differentiate the two. Ditto for rcu variants.
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key)
\
+ hlist_add_head_rcu(node, hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key)
\
+ hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
Or maybe we're better off with hash_head_size() and hash_head()? I'll
expand on it later. Please bear with me.
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the struct hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
As the 'h' in hlist* stand for hash anyway and I think this type of
thin wrappers tend to obfuscate more than anything else.
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+ hlist_del_init(node);
+}
+
+/**
+ * hash_del_rcu - remove an object from a rcu enabled hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del_rcu(struct hlist_node *node)
+{
+ hlist_del_init_rcu(node);
+}
If we do that, we can remove all these thin wrappers.
+#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)
..
+#define hash_for_each(name, bkt, node, obj, member)
\
+ hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
...
+#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)
\
+ for (bkt = 0; bkt HASH_SIZE(bits); bkt++)
\
+ hlist_for_each_entry_rcu(obj, node, name[bkt], member)
...
+#define hash_for_each_rcu(name, bkt, node, obj, member)
\
+ hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
...
+#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)
\
+ for (bkt = 0; bkt HASH_SIZE(bits); bkt++)
\
+ hlist_for_each_entry_safe(obj, node, tmp, name[bkt], member)
...
+#define hash_for_each_safe(name, bkt, node, tmp, obj, member)
\
+ hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,
\
+ tmp, obj, member)
...
+#define hash_for_each_possible_size(name, obj, bits, node, member, key)
\
+ hlist_for_each_entry(obj, node, name[hash_min(key, bits)], member)
...
+#define hash_for_each_possible(name, obj, node, member, key)
\
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
On 23/08/12 04:01, Tejun Heo wrote:
Hello, Sasha.
On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
+#define DEFINE_HASHTABLE(name, bits)
\
+struct hlist_head name[HASH_SIZE(bits)];
Shouldn't this be something like the following?
#define DEFINE_HASHTABLE(name, bits) \
struct hlist_head name[HASH_SIZE(bits)] = \
{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
kernels. */
+#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
hash_long((val), (bits)))
Why is the branching condition sizeof(val) == 4 instead of = 4?
Also, no biggie but why isn't this macro in caps?
It should probably use gcc's statement expression extensions to prevent
side-effect issues with the arguments:
#define hash_min ({ \
sizeof(val) = 4 ? \
hash_32(val, bits) :\
hash_long(val, bits)); \
})
~Ryan
--
To unsubscribe from this list: send the line unsubscribe linux-kernel in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v3 01/17] hashtable: introduce a small and naive hashtable
Hi Tejun,
On 08/22/2012 08:01 PM, Tejun Heo wrote:
Hello, Sasha.
On Wed, Aug 22, 2012 at 04:26:56AM +0200, Sasha Levin wrote:
+#define DEFINE_HASHTABLE(name, bits)
\
+struct hlist_head name[HASH_SIZE(bits)];
Shouldn't this be something like the following?
#define DEFINE_HASHTABLE(name, bits) \
struct hlist_head name[HASH_SIZE(bits)] = \
{ [0 ... HASH_SIZE(bits) - 1] = HLIST_HEAD_INIT };
Also, given that the declaration isn't non-trivial, you'll probably
want a matching DECLARE_HASHTABLE() macro too.
I figured we might do a DEFINE_HASHTABLE() to prevent the need from using
hash_init() on hashtables defined this way, but I preferred not to since we may
end up wanting a more complex initialization (I'll explain why extensively
below).
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit
kernels. */
+#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
hash_long((val), (bits)))
Why is the branching condition sizeof(val) == 4 instead of = 4?
No reason, will fix.
Also, no biggie but why isn't this macro in caps?
I had this plan in my mind to move it into linux/hash.h at some stage later, and
the API there uses low caps even for macros (hash_long()).
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key)
\
+hlist_add_head_rcu(node, hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key)
\
+hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
Or maybe we're better off with hash_head_size() and hash_head()? I'll
expand on it later. Please bear with me.
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the struct hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
As the 'h' in hlist* stand for hash anyway and I think this type of
thin wrappers tend to obfuscate more than anything else.
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+hlist_del_init(node);
+}
+
+/**
+ * hash_del_rcu - remove an object from a rcu enabled hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del_rcu(struct hlist_node *node)
+{
+hlist_del_init_rcu(node);
+}
If we do that, we can remove all these thin wrappers.
+#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)
..
+#define hash_for_each(name, bkt, node, obj, member)
\
+hash_for_each_size(name, HASH_BITS(name), bkt, node, obj, member)
...
+#define hash_for_each_rcu_size(name, bits, bkt, node, obj, member)
\
+for (bkt = 0; bkt HASH_SIZE(bits); bkt++)
\
+hlist_for_each_entry_rcu(obj, node, name[bkt], member)
...
+#define hash_for_each_rcu(name, bkt, node, obj, member)
\
+hash_for_each_rcu_size(name, HASH_BITS(name), bkt, node, obj, member)
...
+#define hash_for_each_safe_size(name, bits, bkt, node, tmp, obj, member)
\
+for (bkt = 0; bkt HASH_SIZE(bits); bkt++)
\
+hlist_for_each_entry_safe(obj, node, tmp, name[bkt], member)
...
+#define hash_for_each_safe(name, bkt, node, tmp, obj, member)
\
+hash_for_each_safe_size(name, HASH_BITS(name), bkt, node,
\
+tmp, obj, member)
...
+#define hash_for_each_possible_size(name, obj, bits, node, member, key)
\
+hlist_for_each_entry(obj, node, name[hash_min(key, bits)], member)
...
+#define hash_for_each_possible(name, obj, node, member, key)
\
+hash_for_each_possible_size(name, obj, HASH_BITS(name), node, member,
key)
...
+#define hash_for_each_possible_rcu_size(name, obj, bits, node, member, key)
\
+hlist_for_each_entry_rcu(obj, node, name[hash_min(key, bits)], member)
...
+#define hash_for_each_possible_rcu(name, obj, node, member, key)
\
+hash_for_each_possible_rcu_size(name, obj,
[PATCH v3 01/17] hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by: Sasha Levin
---
include/linux/hashtable.h | 291 +
1 files changed, 291 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 000..d2d6ed0
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,291 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include
+#include
+#include
+#include
+#include
+
+#define DEFINE_HASHTABLE(name, bits) \
+ struct hlist_head name[HASH_SIZE(bits)];
+
+#define HASH_SIZE(bits) (1 << (bits))
+#define HASH_BITS(name) (ilog2(ARRAY_SIZE(name)))
+#define HASH_REQUIRED_SIZE(bits) (sizeof(struct hlist_head) * HASH_SIZE(bits))
+
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels.
*/
+#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
hash_long((val), (bits)))
+
+/**
+ * hash_init_size - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ * @bits: bit count of hashing function
+ *
+ * Initializes a hash table with 2**bits buckets.
+ */
+static inline void hash_init_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i < HASH_SIZE(bits); i++)
+ INIT_HLIST_HEAD(hashtable + i);
+}
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ *
+ * Calculates the size of the hashtable from the given parameter, otherwise
+ * same as hash_init_size.
+ */
+#define hash_init(name) hash_init_size(name, HASH_BITS(name))
+
+/**
+ * hash_add_size - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_size(hashtable, bits, node, key)
\
+ hlist_add_head(node, [hash_min(key, bits)]);
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key)
\
+ hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key)
\
+ hlist_add_head_rcu(node, [hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key)
\
+ hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
+
+/**
+ * hash_empty_size - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ * @bits: bit count used for hashing
+ */
+static inline bool hash_empty_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i < HASH_SIZE(bits); i++)
+ if (!hlist_empty([i]))
+ return false;
+
+ return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ */
+#define hash_empty(name) hash_empty_size(name, HASH_BITS(name))
+
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+ hlist_del_init(node);
+}
+
+/**
+ * hash_del_rcu - remove an object from a rcu enabled hashtable
+ * @node: hlist_node of the object to remove
+ */
+static inline void hash_del_rcu(struct hlist_node *node)
+{
+ hlist_del_init_rcu(node);
+}
+
+/**
+ * hash_for_each_size - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the list_head to use as a loop cursor for each entry
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node within the struct
+ */
+#define hash_for_each_size(name, bits, bkt, node, obj, member)
\
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++)
[PATCH v3 01/17] hashtable: introduce a small and naive hashtable
This hashtable implementation is using hlist buckets to provide a simple
hashtable to prevent it from getting reimplemented all over the kernel.
Signed-off-by: Sasha Levin levinsasha...@gmail.com
---
include/linux/hashtable.h | 291 +
1 files changed, 291 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
new file mode 100644
index 000..d2d6ed0
--- /dev/null
+++ b/include/linux/hashtable.h
@@ -0,0 +1,291 @@
+/*
+ * Hash table implementation
+ * (C) 2012 Sasha Levin levinsasha...@gmail.com
+ */
+
+#ifndef _LINUX_HASHTABLE_H
+#define _LINUX_HASHTABLE_H
+
+#include linux/list.h
+#include linux/types.h
+#include linux/kernel.h
+#include linux/hash.h
+#include linux/rculist.h
+
+#define DEFINE_HASHTABLE(name, bits) \
+ struct hlist_head name[HASH_SIZE(bits)];
+
+#define HASH_SIZE(bits) (1 (bits))
+#define HASH_BITS(name) (ilog2(ARRAY_SIZE(name)))
+#define HASH_REQUIRED_SIZE(bits) (sizeof(struct hlist_head) * HASH_SIZE(bits))
+
+/* Use hash_32 when possible to allow for fast 32bit hashing in 64bit kernels.
*/
+#define hash_min(val, bits) ((sizeof(val)==4) ? hash_32((val), (bits)) :
hash_long((val), (bits)))
+
+/**
+ * hash_init_size - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ * @bits: bit count of hashing function
+ *
+ * Initializes a hash table with 2**bits buckets.
+ */
+static inline void hash_init_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i HASH_SIZE(bits); i++)
+ INIT_HLIST_HEAD(hashtable + i);
+}
+
+/**
+ * hash_init - initialize a hash table
+ * @hashtable: hashtable to be initialized
+ *
+ * Calculates the size of the hashtable from the given parameter, otherwise
+ * same as hash_init_size.
+ */
+#define hash_init(name) hash_init_size(name, HASH_BITS(name))
+
+/**
+ * hash_add_size - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_size(hashtable, bits, node, key)
\
+ hlist_add_head(node, hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add - add an object to a hashtable
+ * @hashtable: hashtable to add to
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add(hashtable, node, key)
\
+ hash_add_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_add_rcu_size - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @bits: bit count used for hashing
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu_size(hashtable, bits, node, key)
\
+ hlist_add_head_rcu(node, hashtable[hash_min(key, bits)]);
+
+/**
+ * hash_add_rcu - add an object to a rcu enabled hashtable
+ * @hashtable: hashtable to add to
+ * @node: the struct hlist_node of the object to be added
+ * @key: the key of the object to be added
+ */
+#define hash_add_rcu(hashtable, node, key)
\
+ hash_add_rcu_size(hashtable, HASH_BITS(hashtable), node, key)
+
+/**
+ * hash_hashed - check whether an object is in any hashtable
+ * @node: the struct hlist_node of the object to be checked
+ */
+#define hash_hashed(node) (!hlist_unhashed(node))
+
+/**
+ * hash_empty_size - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ * @bits: bit count used for hashing
+ */
+static inline bool hash_empty_size(struct hlist_head *hashtable, int bits)
+{
+ int i;
+
+ for (i = 0; i HASH_SIZE(bits); i++)
+ if (!hlist_empty(hashtable[i]))
+ return false;
+
+ return true;
+}
+
+/**
+ * hash_empty - check whether a hashtable is empty
+ * @hashtable: hashtable to check
+ */
+#define hash_empty(name) hash_empty_size(name, HASH_BITS(name))
+
+/**
+ * hash_del - remove an object from a hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del(struct hlist_node *node)
+{
+ hlist_del_init(node);
+}
+
+/**
+ * hash_del_rcu - remove an object from a rcu enabled hashtable
+ * @node: struct hlist_node of the object to remove
+ */
+static inline void hash_del_rcu(struct hlist_node *node)
+{
+ hlist_del_init_rcu(node);
+}
+
+/**
+ * hash_for_each_size - iterate over a hashtable
+ * @name: hashtable to iterate
+ * @bits: bit count of hashing function of the hashtable
+ * @bkt: integer to use as bucket loop cursor
+ * @node: the struct list_head to use as a loop cursor for each entry
+ * @obj: the type * to use as a loop cursor for each entry
+ * @member: the name of the hlist_node
