Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 9, 2015 at 10:12 AM, Linus Torvalds
wrote:
>
> It's just unusual, which I think makes it slightly harder to read for
> a *human* just because it breaks the normal pattern of those things.
> But there's nothing technically wrong with it.
You could have written it as
static __always_inline struct latch_tree_node *
__lt_from_rb(struct rb_node *node, int idx)
{
return (void *)(node-idx);
}
which is actually shorter, but even if that container_of() use looks a
bit unusual, I think the container_of() shows more clearly what you
actually want. Plus it would be more reliable if you ever end up
adding any other fields to the struct latch_tree_node.
So I wouldn't actually suggest using that "(node-idx)" format. I think
it should result in the exact same code, though.
Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 9, 2015 at 9:59 AM, Peter Zijlstra wrote: > > I was a little surprised myself it worked, but its a constant after > all so it 'should'. Well, it should actually work for non-constants too, even when that 'idx' isn't inlined to one of the fixed constants. So even if this will ever hit the "seq & 1" case for lookup, it should all work. It's just an expression, after all. All that is really required is that you can do '&(x->y)' on it, where 'x' is the type, and 'y' is the "member". It's just unusual, which I think makes it slightly harder to read for a *human* just because it breaks the normal pattern of those things. But there's nothing technically wrong with it. Linus -- To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majord...@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 09, 2015 at 09:31:16AM -0700, Linus Torvalds wrote:
> On Thu, Apr 9, 2015 at 5:13 AM, Peter Zijlstra wrote:
> >
> > struct latch_tree_node {
> > + struct rb_node node[2];
> > };
> >
> > +static __always_inline struct latch_tree_node *
> > +__lt_from_rb(struct rb_node *node, int idx)
> > +{
> > + return container_of(node, struct latch_tree_node, node[idx]);
> > +}
>
> Ugh. That syntax of offset_of() worries me a bit, but some grepping
> shows that we already use this form of offset_of() in parts of the
> kernel, so I guess it's fine.
I was a little surprised myself it worked, but its a constant after
all so it 'should'.
> Even with that small "Ugh", I do have to admit to preferring this to
> having the back-pointer.
Yeah me too, I'll respin the patches proper after I've given it some
actual runtime too.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 9, 2015 at 5:13 AM, Peter Zijlstra wrote:
>
> struct latch_tree_node {
> + struct rb_node node[2];
> };
>
> +static __always_inline struct latch_tree_node *
> +__lt_from_rb(struct rb_node *node, int idx)
> +{
> + return container_of(node, struct latch_tree_node, node[idx]);
> +}
Ugh. That syntax of offset_of() worries me a bit, but some grepping
shows that we already use this form of offset_of() in parts of the
kernel, so I guess it's fine.
Even with that small "Ugh", I do have to admit to preferring this to
having the back-pointer.
Linus
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 09, 2015 at 02:13:36PM +0200, Peter Zijlstra wrote:
> +struct module;
> +
> +struct mod_tree_node {
> + struct latch_tree_node node;
> + struct module *mod;
> +};
The module pointer should be first in this structure.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 09, 2015 at 04:55:05PM +0800, Lai Jiangshan wrote:
> This sentence is talking about module.c not latch_tree.h. So I guess
> it is user(module.c)'s problem, not latch_tree.h's problem.
>
> The user(module.c) can wrap the struct latch_tree_nodes and add @priv.
OK, took me a while to figure out exactly what and how. You mean
something like this, right?
(compile tested only)
---
include/linux/module.h | 11 -
include/linux/rbtree_latch.h | 93 ++-
kernel/module.c | 33 +--
3 files changed, 70 insertions(+), 67 deletions(-)
--- a/include/linux/module.h
+++ b/include/linux/module.h
@@ -211,6 +211,13 @@ enum module_state {
MODULE_STATE_UNFORMED, /* Still setting it up. */
};
+struct module;
+
+struct mod_tree_node {
+ struct latch_tree_node node;
+ struct module *mod;
+};
+
struct module {
enum module_state state;
@@ -294,8 +301,8 @@ struct module {
* core.node[0] to be in the same cacheline as the above entries,
* we also assume ltn_init has a higher address than ltn_core.
*/
- struct latch_tree_nodes ltn_core;
- struct latch_tree_nodes ltn_init;
+ struct mod_tree_nodemtn_core;
+ struct mod_tree_nodemtn_init;
/* Size of RO sections of the module (text+rodata) */
unsigned int init_ro_size, core_ro_size;
--- a/include/linux/rbtree_latch.h
+++ b/include/linux/rbtree_latch.h
@@ -36,17 +36,7 @@
#include
struct latch_tree_node {
- /*
-* Because we have an array of two entries in struct latch_tree_nodes
-* it's not possible to use container_of() to get back to the
-* encapsulating structure; therefore we have to put in a back pointer.
-*/
- void*priv;
- struct rb_node node;
-};
-
-struct latch_tree_nodes {
- struct latch_tree_node node[2];
+ struct rb_node node[2];
};
struct latch_tree_root {
@@ -74,17 +64,25 @@ struct latch_tree_ops {
int (*comp)(void *key, struct latch_tree_node *b);
};
+static __always_inline struct latch_tree_node *
+__lt_from_rb(struct rb_node *node, int idx)
+{
+ return container_of(node, struct latch_tree_node, node[idx]);
+}
+
static __always_inline void
-__lt_insert(struct latch_tree_node *ltn, struct rb_root *root,
+__lt_insert(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx,
bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b))
{
+ struct rb_root *root = tree[idx];
struct rb_node **link = &root->rb_node;
+ struct rb_node *node = node[idx];
struct rb_node *parent = NULL;
struct latch_tree_node *ltp;
while (*link) {
parent = *link;
- ltp = container_of(parent, struct latch_tree_node, node);
+ ltp = __lt_from_rb(parent, idx);
if (less(ltn, ltp))
link = &parent->rb_left;
@@ -92,32 +90,32 @@ __lt_insert(struct latch_tree_node *ltn,
link = &parent->rb_right;
}
- rb_link_node_rcu(node, parent, link);
- rb_insert_color(node, root);
+ rb_link_node_rcu(node, parent, link);
+ rb_insert_color(node, root);
}
static __always_inline void
-__lt_erase(struct latch_tree_node *ltn, struct rb_root *root)
+__lt_erase(struct latch_tree_node *ltn, struct latch_tree_root *ltr, int idx)
{
- rb_erase(node, root);
+ rb_erase(node[idx], tree[idx]);
}
static __always_inline struct latch_tree_node *
-__lt_find(void *key, struct rb_root *root,
- int (*comp)(void *key, struct latch_tree_node *ltn))
+__lt_find(void *key, struct latch_tree_root *ltr, int idx,
+ int (*comp)(void *key, struct latch_tree_node *node))
{
- struct rb_node *n = rcu_dereference_raw(root->rb_node);
+ struct rb_node *node = rcu_dereference_raw(ltr->tree[idx].rb_node);
struct latch_tree_node *ltn;
int c;
- while (n) {
- ltn = container_of(n, struct latch_tree_node, node);
+ while (node) {
+ ltn = __lt_from_rb(node, idx);
c = comp(key, ltn);
if (c < 0)
- n = rcu_dereference_raw(n->rb_left);
+ node = rcu_dereference_raw(node->rb_left);
else if (c > 0)
- n = rcu_dereference_raw(n->rb_right);
+ node = rcu_dereference_raw(node->rb_right);
else
return ltn;
}
@@ -126,65 +124,56 @@ __lt_find(void *key, struct rb_root *roo
}
/**
- * latch_tree_insert() - insert @nodes into the trees @root
- * @nodes: nodes to insert
- * @root: trees to insert @nodes into
- * @priv: pointer to node private data
+ * latch_tree_insert() - insert @node into the trees @root
+ * @node: nodes to insert
+ * @roo
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On 04/09/2015 04:14 PM, Peter Zijlstra wrote:
> On Thu, Apr 09, 2015 at 04:09:07PM +0800, Lai Jiangshan wrote:
>> On 04/09/2015 12:48 AM, Peter Zijlstra wrote:
>>
>>> +
>>> +struct latch_tree_node {
>>> + /*
>>> +* Because we have an array of two entries in struct latch_tree_nodes
>>> +* it's not possible to use container_of() to get back to the
>>> +* encapsulating structure; therefore we have to put in a back pointer.
>>> +*/
>>> + void*priv;
>>> + struct rb_node node;
>>> +};
>>
>> I don't think @priv is strictly needed. It is possible to use container_of()
>> to go back. @priv is even not used in this file (except the initialization).
>>
>> First, we can use container_of() to find encapsulating structure from the
>> struct latch_tree_nodeS.
>>
>> Second, we can add a @idx to __lt_insert() and __lt_find(),
>
> insert yes, find no. Remember that both nodes are in the _same_ tree.
>
> There is no way of knowing if a tree node is an init or core node while
> iterating.
> .
>
This sentence is talking about module.c not latch_tree.h. So I guess
it is user(module.c)'s problem, not latch_tree.h's problem.
The user(module.c) can wrap the struct latch_tree_nodes and add @priv.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On Thu, Apr 09, 2015 at 04:09:07PM +0800, Lai Jiangshan wrote:
> On 04/09/2015 12:48 AM, Peter Zijlstra wrote:
>
> > +
> > +struct latch_tree_node {
> > + /*
> > +* Because we have an array of two entries in struct latch_tree_nodes
> > +* it's not possible to use container_of() to get back to the
> > +* encapsulating structure; therefore we have to put in a back pointer.
> > +*/
> > + void*priv;
> > + struct rb_node node;
> > +};
>
> I don't think @priv is strictly needed. It is possible to use container_of()
> to go back. @priv is even not used in this file (except the initialization).
>
> First, we can use container_of() to find encapsulating structure from the
> struct latch_tree_nodeS.
>
> Second, we can add a @idx to __lt_insert() and __lt_find(),
insert yes, find no. Remember that both nodes are in the _same_ tree.
There is no way of knowing if a tree node is an init or core node while
iterating.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
Re: [PATCH v4 6/9] rbtree: Implement generic latch_tree
On 04/09/2015 12:48 AM, Peter Zijlstra wrote:
> +
> +struct latch_tree_node {
> + /*
> + * Because we have an array of two entries in struct latch_tree_nodes
> + * it's not possible to use container_of() to get back to the
> + * encapsulating structure; therefore we have to put in a back pointer.
> + */
> + void*priv;
> + struct rb_node node;
> +};
I don't think @priv is strictly needed. It is possible to use container_of()
to go back. @priv is even not used in this file (except the initialization).
First, we can use container_of() to find encapsulating structure from the
struct latch_tree_nodeS.
Second, we can add a @idx to __lt_insert() and __lt_find(), thus we can
find the encapsulating latch_tree_nodes from rb_node or latch_tree_node.
and struct latch_tree_ops uses latch_tree_nodes instead.
Did I miss anything? If the @priv is possible to be removed, removing it will
simplify this file but it may add a little more code in the module.c where
the ltn_coreless() and ->comp() after.
If you do remove @priv, please also use rb_node instead of old latch_tree_node
and rename old latch_tree_nodes to latch_tree_node.
--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majord...@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/
