There are quite a few places in the kernel which implement a hashtable
in a very similar way. Instead of having implementations of a hashtable
all over the kernel, we can re-use the code.
Since it looks like all the major issues we're addressed in the RFC phase
and no major issues were raised with this patch set, I'd be happy to see
this getting merged so that work could continue on different aspects of
the hashtable. Some interesting directions include:
- Introducing a dynamic RCU hashtable such as the one Mathieu Desnoyers
wrote about out in the userspace RCU.
- Replacing the rest of the the kernel structures which use the same basec
hashtable construct to use this new interface.
- Same as above, but for non-obvious places (for example, I'm looking into
using the hashtable to store KVM vcpus instead of the linked list being used
there now - this should help performance with a large amount of vcpus).
Changes since v2:
- Documentation improvements from Mathieu Desnoyers.
- Converted the SUNRPC audit code to use hashtables as well. Since that code
requires a dynamic hashtable this shows off the _size() API usage.
Changes since v1:
- Added missing hash_init in rds and lockd.
- Addressed the userns comments by Eric Biederman.
- Ran a small test to confirm hash_32 does a good job for low key
values (1-10000), which showed it did - this resulted in no changes to the
code.
Sasha Levin (17):
hashtable: introduce a small and naive hashtable
userns: use new hashtable implementation
mm,ksm: use new hashtable implementation
workqueue: use new hashtable implementation
mm/huge_memory: use new hashtable implementation
tracepoint: use new hashtable implementation
net,9p: use new hashtable implementation
block,elevator: use new hashtable implementation
SUNRPC/cache: use new hashtable implementation
dlm: use new hashtable implementation
net,l2tp: use new hashtable implementation
dm: use new hashtable implementation
lockd: use new hashtable implementation
net,rds: use new hashtable implementation
openvswitch: use new hashtable implementation
tracing output: use new hashtable implementation
SUNRPC: use new hashtable implementation in auth
block/blk.h | 2 +-
block/elevator.c | 23 +--
drivers/md/dm-snap.c | 24 +--
drivers/md/persistent-data/dm-block-manager.c | 1 -
.../persistent-data/dm-persistent-data-internal.h | 19 --
.../md/persistent-data/dm-transaction-manager.c | 30 +--
fs/dlm/lowcomms.c | 47 +---
fs/lockd/svcsubs.c | 66 +++--
include/linux/elevator.h | 5 +-
include/linux/hashtable.h | 291 ++++++++++++++++++++
kernel/trace/trace_output.c | 20 +-
kernel/tracepoint.c | 27 +-
kernel/user.c | 33 +--
kernel/workqueue.c | 86 +-----
mm/huge_memory.c | 57 +---
mm/ksm.c | 33 +--
net/9p/error.c | 21 +-
net/l2tp/l2tp_core.c | 134 ++++------
net/l2tp/l2tp_core.h | 8 +-
net/l2tp/l2tp_debugfs.c | 19 +-
net/openvswitch/vport.c | 30 +--
net/rds/bind.c | 28 ++-
net/rds/connection.c | 102 +++----
net/sunrpc/auth.c | 45 ++--
net/sunrpc/cache.c | 20 +-
25 files changed, 617 insertions(+), 554 deletions(-)
delete mode 100644 drivers/md/persistent-data/dm-persistent-data-internal.h
create mode 100644 include/linux/hashtable.h
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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 <redacted>
---
include/linux/hashtable.h | 291 +++++++++++++++++++++++++++++++++++++++++++++
1 files changed, 291 insertions(+), 0 deletions(-)
create mode 100644 include/linux/hashtable.h
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.
And also all these. We'd only need hash_for_each_head() and
hash_head(). hash_for_each_possible*() could be nice for convenience,
I suppose.
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?
Also, can you please audit the comments on top of each macro? They
have wrong names and don't differentiate the different variants very
well.
Thanks.
--
tejun
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.
quoted
+/* 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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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).
quoted
+/* 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()).
quoted
+/**
+ * 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.
quoted
+/**
+ * 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.
quoted
+/**
+ * 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.
And also all these. We'd only need hash_for_each_head() and
hash_head(). hash_for_each_possible*() could be nice for convenience,
I suppose.
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.
- hash_hashed(): Different hashtable implementations may not use hlist, so
letting them assume that doing hlist operations on hashtable objects is wrong.
- Lack of hash_head(): I didn't want to expose the internal structure of the
hashtable to the user. This might make it hard to implement hashtables that
resize themselves if we let the user hold a bucket in his hands.
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.
Now, I know that I mention a lot of these hashtables that might or might not be
added later on in the kernel, this is mostly due to the interest in dynamic
resizable hashtables which was shown during the RFC, and the fact that there is
a solid implementation of a dynamic RCU hashtable in urcu which might be a great
benefit in the kernel as well (I'm also looking at it while working on this
hashtable to verify that both could share an API in the future).
Regarding the amount of new macros, we can address this by splitting off any
dynamic elements into a new hashtable type. This will let us reduce quite a lot
of macros (removing all the _size() ones at least).
Also, can you please audit the comments on top of each macro? They
have wrong names and don't differentiate the different variants very
well.
Sure, sorry about that.
Thanks,
Sasha
Thanks.
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Hello, Sasha.
On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Hello, Sasha.
On Thu, Aug 23, 2012 at 02:24:32AM +0200, Sasha Levin wrote:
quoted
quoted
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.
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Hello, Sasha.
On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
quoted
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?
quoted
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
Hello, Sasha.
On Fri, Aug 24, 2012 at 09:47:19PM +0200, Sasha Levin wrote:
quoted
quoted
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?
quoted
quoted
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.
quoted
- 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-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello, Sasha.
On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
quoted
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.
quoted
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
Hello, Sasha.
On Fri, Aug 24, 2012 at 10:11:55PM +0200, Sasha Levin wrote:
quoted
quoted
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.
quoted
quoted
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.
quoted
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.
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.
* 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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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()).
quoted
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.
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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&D Consultant
EfficiOS Inc.
http://www.efficios.com
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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
quoted
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
Hello,
On Sat, Aug 25, 2012 at 12:59:25AM +0200, Sasha Levin wrote:
quoted
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.
quoted
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++) \
+ 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.
Thanks,
Mathieu
Thanks,
Mathieu
quoted
Thanks,
Sasha
quoted
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-04 15:35:54
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
From: Pedro Alves <hidden> Date: 2012-09-04 16:31:14
On 09/04/2012 04:35 PM, Steven Rostedt wrote:
On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
quoted
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
From: Pedro Alves <hidden> Date: 2012-09-04 16:40:56
On 09/04/2012 05:30 PM, Pedro Alves wrote:
On 09/04/2012 04:35 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
* Pedro Alves (palves-H+wXaHxf7aLQT0dZR+AlfA@public.gmane.org) wrote:
On 09/04/2012 05:30 PM, Pedro Alves wrote:
quoted
On 09/04/2012 04:35 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
quoted
Looking again at:
+#define hash_for_each_size(name, bits, bkt, node, obj, member) \
+ for (bkt = 0; bkt < HASH_SIZE(bits); bkt++) \
+ hlist_for_each_entry(obj, node, &name[bkt], member)
you will notice that a "break" or "continue" in the inner loop will not
affect the outer loop, which is certainly not what the programmer would
expect!
I advise strongly against creating such error-prone construct.
A few existing loop macros do this. But they require a do { } while ()
approach, and all have a comment.
It's used by do_each_thread() in sched.h and ftrace does this as well.
Look at kernel/trace/ftrace.c at do_for_each_ftrace_rec().
Yes it breaks 'break' but it does not break 'continue' as it would just
go to the next item that would have been found (like a normal for
would).
/*
* This is a double for. Do not use 'break' to break out of the loop,
* you must use a goto.
*/
#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start; pg; pg = pg->next) { \
int _____i; \
for (_____i = 0; _____i < pg->index; _____i++) { \
rec = &pg->records[_____i];
You can make 'break' also work as expected if you can embed a little knowledge
of the inner loop's condition in the outer loop's condition. Sometimes it's
trivial, most often when the inner loop's iterator is a pointer that goes
NULL at the end, but other times not so much. Something like (completely untested):
#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
pg && rec == &pg->records[pg->index]; \
pg = pg->next) { \
int _____i; \
for (_____i = 0; _____i < pg->index; _____i++) { \
rec = &pg->records[_____i];
(other variants possible)
IOW, the outer loop only iterates if the inner loop completes. If there's
a break in the inner loop, then the outer loop breaks too. Of course, it
all depends on whether the generated code looks sane or hideous, if
the uses of the macro care for it over bug avoidance.
BTW, you can also go a step further and remove the need to close with double }},
with something like:
#define do_for_each_ftrace_rec(pg, rec) \
for (pg = ftrace_pages_start, rec = &pg->records[pg->index]; \
pg && rec == &pg->records[pg->index]; \
pg = pg->next) \
for (rec = pg->records; rec < &pg->records[pg->index]; rec++)
Maybe in some cases there might be ways to combine the two loops into
one ? I'm not seeing exactly how to do it for this one, but it should
not be impossible. If the inner loop condition can be moved to the outer
loop, and if we use (blah ? loop1_conf : loop2_cond) to test for
different conditions depending on the context, and do the same for the
3rd argument of the for() loop. The details elude me for now though, so
maybe it's complete non-sense ;)
It might not be that useful for do_for_each_ftrace_rec, but if we can do
it for the hash table iterator, it might be worth it.
Thanks,
Mathieu
--
Mathieu Desnoyers
Operating System Efficiency R&D Consultant
EfficiOS Inc.
http://www.efficios.com
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
From: Pedro Alves <hidden> Date: 2012-09-06 14:20:40
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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 R&D Consultant
EfficiOS Inc.
http://www.efficios.com
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-06 15:11:39
On Thu, 2012-09-06 at 07:55 -0700, Josh Triplett wrote:
quoted
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
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
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-06 16:00:13
On Thu, 2012-09-06 at 17:49 +0200, Sasha Levin wrote:
quoted
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.
quoted
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-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
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
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&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-06 17:15:49
On Thu, 2012-09-06 at 18:21 +0200, Sasha Levin wrote:
On 09/06/2012 06:00 PM, Steven Rostedt wrote:
quoted
quoted
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-04 17:17:16
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
From: Pedro Alves <hidden> Date: 2012-09-04 17:21:51
On 09/04/2012 06:17 PM, Steven Rostedt wrote:
On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-04 20:59:12
On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
On 09/04/2012 06:17 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
quoted
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
From: Pedro Alves <hidden> Date: 2012-09-04 21:51:50
On 09/04/2012 09:59 PM, Steven Rostedt wrote:
On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
quoted
On 09/04/2012 06:17 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
quoted
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
From: Steven Rostedt <rostedt@goodmis.org> Date: 2012-09-04 22:41:56
On Tue, 2012-09-04 at 22:51 +0100, Pedro Alves wrote:
On 09/04/2012 09:59 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-09-04 at 18:21 +0100, Pedro Alves wrote:
quoted
On 09/04/2012 06:17 PM, Steven Rostedt wrote:
quoted
On Tue, 2012-09-04 at 17:40 +0100, Pedro Alves wrote:
quoted
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
From: Pedro Alves <hidden> Date: 2012-09-04 22:58:55
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, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
* Steven Rostedt (rostedt-nx8X9YLhiw1AfugRpC6u6w@public.gmane.org) wrote:
On Tue, 2012-08-28 at 19:00 -0400, Mathieu Desnoyers wrote:
quoted
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 R&D Consultant
EfficiOS Inc.
http://www.efficios.com
--
To unsubscribe from this list: send the line "unsubscribe linux-nfs" in
the body of a message to majordomo-u79uwXL29TY76Z2rM5mHXA@public.gmane.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Switch to using the new hashtable implementation to store user structs.
This reduces the amount of generic unrelated code in kernel/user.c.
Signed-off-by: Sasha Levin <redacted>
---
kernel/user.c | 33 +++++++++++++--------------------
1 files changed, 13 insertions(+), 20 deletions(-)
@@ -196,17 +192,14 @@ out_unlock:staticint__inituid_cache_init(void){-intn;-uid_cachep=kmem_cache_create("uid_cache",sizeof(structuser_struct),0,SLAB_HWCACHE_ALIGN|SLAB_PANIC,NULL);-for(n=0;n<UIDHASH_SZ;++n)-INIT_HLIST_HEAD(uidhash_table+n);+hash_init(uidhash_table);/* Insert the root user immediately (init already runs as root) */spin_lock_irq(&uidhash_lock);-uid_hash_insert(&root_user,uidhashentry(GLOBAL_ROOT_UID));+uid_hash_insert(&root_user);spin_unlock_irq(&uidhash_lock);return0;
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>
Switch ksm to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the ksm module.
Signed-off-by: Sasha Levin <redacted>
---
mm/ksm.c | 33 +++++++++++++++------------------
1 files changed, 15 insertions(+), 18 deletions(-)
Switch workqueues to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the workqueues.
Signed-off-by: Sasha Levin <redacted>
---
kernel/workqueue.c | 86 +++++++++-------------------------------------------
1 files changed, 15 insertions(+), 71 deletions(-)
@@ -82,8 +83,6 @@ enum {NR_WORKER_POOLS=2,/* # worker pools per gcwq */BUSY_WORKER_HASH_ORDER=6,/* 64 pointers */-BUSY_WORKER_HASH_SIZE=1<<BUSY_WORKER_HASH_ORDER,-BUSY_WORKER_HASH_MASK=BUSY_WORKER_HASH_SIZE-1,MAX_IDLE_WORKERS_RATIO=4,/* 1/4 of busy can be idle */IDLE_WORKER_TIMEOUT=300*HZ,/* keep idle ones for 5 mins */
@@ -180,7 +179,7 @@ struct global_cwq {unsignedintflags;/* L: GCWQ_* flags *//* workers are chained either in busy_hash or pool idle_list */-structhlist_headbusy_hash[BUSY_WORKER_HASH_SIZE];+DEFINE_HASHTABLE(busy_hash,BUSY_WORKER_HASH_ORDER);/* L: hash of busy workers */structworker_poolpools[2];/* normal and highpri pools */
@@ -288,8 +287,7 @@ EXPORT_SYMBOL_GPL(system_nrt_freezable_wq);(pool)<&(gcwq)->pools[NR_WORKER_POOLS];(pool)++)#define for_each_busy_worker(worker, i, pos, gcwq) \-for(i=0;i<BUSY_WORKER_HASH_SIZE;i++)\-hlist_for_each_entry(worker,pos,&gcwq->busy_hash[i],hentry)+hash_for_each(gcwq->busy_hash,i,pos,worker,hentry)staticinlineint__next_gcwq_cpu(intcpu,conststructcpumask*mask,unsignedintsw)
@@ -845,63 +843,6 @@ static inline void worker_clr_flags(struct worker *worker, unsigned int flags)}/**-*busy_worker_head-returnthebusyhashheadforawork-*@gcwq:gcwqofinterest-*@work:worktobehashed-*-*Returnhashheadof@gcwqfor@work.-*-*CONTEXT:-*spin_lock_irq(gcwq->lock).-*-*RETURNS:-*Pointertothehashhead.-*/-staticstructhlist_head*busy_worker_head(structglobal_cwq*gcwq,-structwork_struct*work)-{-constintbase_shift=ilog2(sizeof(structwork_struct));-unsignedlongv=(unsignedlong)work;--/* simple shift and fold hash, do we need something better? */-v>>=base_shift;-v+=v>>BUSY_WORKER_HASH_ORDER;-v&=BUSY_WORKER_HASH_MASK;--return&gcwq->busy_hash[v];-}--/**-*__find_worker_executing_work-findworkerwhichisexecutingawork-*@gcwq:gcwqofinterest-*@bwh:hashheadasreturnedbybusy_worker_head()-*@work:worktofindworkerfor-*-*Findaworkerwhichisexecuting@workon@gcwq.@bwhshouldbe-*thehashheadobtainedbycallingbusy_worker_head()withthesame-*work.-*-*CONTEXT:-*spin_lock_irq(gcwq->lock).-*-*RETURNS:-*Pointertoworkerwhichisexecuting@workiffound,NULL-*otherwise.-*/-staticstructworker*__find_worker_executing_work(structglobal_cwq*gcwq,-structhlist_head*bwh,-structwork_struct*work)-{-structworker*worker;-structhlist_node*tmp;--hlist_for_each_entry(worker,tmp,bwh,hentry)-if(worker->current_work==work)-returnworker;-returnNULL;-}--/***find_worker_executing_work-findworkerwhichisexecutingawork*@gcwq:gcwqofinterest*@work:worktofindworkerfor
@@ -3855,7 +3801,6 @@ out_unlock:staticint__initinit_workqueues(void){unsignedintcpu;-inti;/* make sure we have enough bits for OFFQ CPU number */BUILD_BUG_ON((1LU<<(BITS_PER_LONG-WORK_OFFQ_CPU_SHIFT))<
@@ -3873,8 +3818,7 @@ static int __init init_workqueues(void)gcwq->cpu=cpu;gcwq->flags|=GCWQ_DISASSOCIATED;-for(i=0;i<BUSY_WORKER_HASH_SIZE;i++)-INIT_HLIST_HEAD(&gcwq->busy_hash[i]);+hash_init(gcwq->busy_hash);for_each_worker_pool(pool,gcwq){pool->gcwq=gcwq;
On Wed, Aug 22, 2012 at 04:26:59AM +0200, Sasha Levin wrote:
Switch workqueues to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the workqueues.
Signed-off-by: Sasha Levin <redacted>
Switch tracepoints to use the new hashtable implementation. This reduces the amount of
generic unrelated code in the tracepoints.
Signed-off-by: Sasha Levin <redacted>
---
kernel/tracepoint.c | 27 +++++++++++----------------
1 files changed, 11 insertions(+), 16 deletions(-)
--
1.7.8.6
--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to majordomo@kvack.org. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"dont@kvack.org"> email@kvack.org </a>