Implement a latched RB-tree in order to get unconditional RCU/lockless
lookups.
Cc: Mathieu Desnoyers <[email protected]>
Cc: "Paul E. McKenney" <[email protected]>
Cc: Oleg Nesterov <[email protected]>
Cc: Michel Lespinasse <[email protected]>
Cc: Andrea Arcangeli <[email protected]>
Cc: David Woodhouse <[email protected]>
Cc: Rik van Riel <[email protected]>
Signed-off-by: Peter Zijlstra (Intel) <[email protected]>
---
include/linux/rbtree_latch.h | 223 +++++++++++++++++++++++++++++++++++++++++++
1 file changed, 223 insertions(+)
--- /dev/null
+++ b/include/linux/rbtree_latch.h
@@ -0,0 +1,223 @@
+/*
+ * Latched RB-trees
+ *
+ * Copyright (C) 2015 Intel Corp., Peter Zijlstra <[email protected]>
+ *
+ * Since RB-trees have non atomic modifications they're not immediately suited
+ * for RCU/lockless queries. Even though we made RB tree lookups non-fatal for
+ * lockless lookups; we cannot guarantee they return a correct result.
+ *
+ * The simplest solution is a seqlock + rb-tree, this will allow lockless
+ * lookups; but has the constraint (inherent to the seqlock) that read sides
+ * cannot nest in write sides.
+ *
+ * If we need to allow unconditional lookups (say as required for NMI context
+ * usage) we need a more complex setup; this data structure provides this by
+ * employing the latch technique -- see @raw_write_seqcount_latch -- to
+ * implement a latched RB-tree which does allow for unconditional lookups by
+ * virtue of always having (at least) one stable copy of the tree.
+ *
+ * However, while we have the guarantee that there is at all times one stable
+ * copy, this does not guarantee an iteration will not observe modifications.
+ * What might have been a stable copy at the start of the iteration, need not
+ * remain so for the duration of the iteration.
+ *
+ * Therefore, this does require a lockless RB-tree iteration to be non-fatal;
+ * see the comment in lib/rbtree.c. Note however that we only require the first
+ * condition -- not seeing partial stores -- because the latch thing isolates
+ * us from loops. If we were to interrupt a modification the lookup would be
+ * pointed at the stable tree and complete while the modification was halted.
+ */
+
+#ifndef RB_TREE_LATCH_H
+#define RB_TREE_LATCH_H
+
+#include <linux/rbtree.h>
+#include <linux/seqlock.h>
+
+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 latch_tree_root {
+ seqcount_t seq;
+ struct rb_root tree[2];
+};
+
+/**
+ * latch_tree_ops - operators to define the tree order
+ * @less: used for insertion; provides the (partial) order between two elements.
+ * @comp: used for lookups; provides the order between the search key and an element.
+ *
+ * The operators are related like:
+ *
+ * comp(a->key,b) < 0 := less(a,b)
+ * comp(a->key,b) > 0 := less(b,a)
+ * comp(a->key,b) == 0 := !less(a,b) && !less(b,a)
+ *
+ * If these operators define a partial order on the elements we make no
+ * guarantee on which of the elements matching the key is found. See
+ * latch_tree_find().
+ */
+struct latch_tree_ops {
+ bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b);
+ int (*comp)(void *key, struct latch_tree_node *b);
+};
+
+static __always_inline void
+__lt_insert(struct latch_tree_node *ltn, struct rb_root *root,
+ bool (*less)(struct latch_tree_node *a, struct latch_tree_node *b))
+{
+ struct rb_node **link = &root->rb_node;
+ struct rb_node *parent = NULL;
+ struct latch_tree_node *ltp;
+
+ while (*link) {
+ parent = *link;
+ ltp = container_of(parent, struct latch_tree_node, node);
+
+ if (less(ltn, ltp))
+ link = &parent->rb_left;
+ else
+ link = &parent->rb_right;
+ }
+
+ rb_link_node_rcu(<n->node, parent, link);
+ rb_insert_color(<n->node, root);
+}
+
+static __always_inline void
+__lt_erase(struct latch_tree_node *ltn, struct rb_root *root)
+{
+ rb_erase(<n->node, root);
+}
+
+static __always_inline struct latch_tree_node *
+__lt_find(void *key, struct rb_root *root,
+ int (*comp)(void *key, struct latch_tree_node *ltn))
+{
+ struct rb_node *n = rcu_dereference_raw(root->rb_node);
+ struct latch_tree_node *ltn;
+ int c;
+
+ while (n) {
+ ltn = container_of(n, struct latch_tree_node, node);
+ c = comp(key, ltn);
+
+ if (c < 0)
+ n = rcu_dereference_raw(n->rb_left);
+ else if (c > 0)
+ n = rcu_dereference_raw(n->rb_right);
+ else
+ return ltn;
+ }
+
+ return NULL;
+}
+
+/**
+ * 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
+ * @ops: operators defining the node order
+ *
+ * Initializes @nodes private pointer with @priv; which typically is a back
+ * pointer to the containing structure, used by @ops to find the search key.
+ *
+ * Then it inserts @nodes into @root in an ordered fashion such that we can
+ * always observe one complete tree. See the comment for
+ * raw_write_seqcount_latch().
+ *
+ * The inserts use rcu_assign_pointer() to publish the element such that
+ * both the @priv pointer values in @nodes as the tree structure is stored
+ * before we can observe the new @nodes.
+ *
+ * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
+ * serialized.
+ */
+static __always_inline void
+latch_tree_insert(struct latch_tree_nodes *nodes,
+ struct latch_tree_root *root,
+ void *priv,
+ const struct latch_tree_ops *ops)
+{
+ nodes->node[0].priv = nodes->node[1].priv = priv;
+
+ raw_write_seqcount_latch(&root->seq);
+ __lt_insert(&nodes->node[0], &root->tree[0], ops->less);
+ raw_write_seqcount_latch(&root->seq);
+ __lt_insert(&nodes->node[1], &root->tree[1], ops->less);
+}
+
+/**
+ * latch_tree_erase() - removes @nodes from the trees @root
+ * @nodes: nodes to remote
+ * @root: trees to remove @nodes from
+ * @ops: operators defining the node order
+ *
+ * Removes @nodes from the trees @root in an ordered fashion such that we can
+ * always observe one complete tree. See the comment for
+ * raw_write_seqcount_latch().
+ *
+ * It is assumed that @nodes will observe one RCU quiescent state before being
+ * reused of freed.
+ *
+ * All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
+ * serialized.
+ */
+static __always_inline void
+latch_tree_erase(struct latch_tree_nodes *nodes,
+ struct latch_tree_root *root,
+ const struct latch_tree_ops *ops)
+{
+ raw_write_seqcount_latch(&root->seq);
+ __lt_erase(&nodes->node[0], &root->tree[0]);
+ raw_write_seqcount_latch(&root->seq);
+ __lt_erase(&nodes->node[1], &root->tree[1]);
+}
+
+/**
+ * latch_tree_find() - find the node matching @key in the trees @root
+ * @key: search key
+ * @root: trees to search for @key
+ * @ops: operators defining the node order
+ *
+ * Does a lockless lookup in the trees @root for the node matching @key.
+ *
+ * It is assumed that this is called while holding the appropriate RCU read
+ * side lock.
+ *
+ * If the operators define a partial order on the elements (there are multiple
+ * elements which have the same key value) it is undefined which of these
+ * elements will be found. Nor is it possible to iterate the tree to find
+ * further elements with the same key value.
+ *
+ * Returns: a pointer to the node matching @key or NULL.
+ */
+static __always_inline struct latch_tree_node *
+latch_tree_find(void *key, struct latch_tree_root *root,
+ const struct latch_tree_ops *ops)
+{
+ struct latch_tree_node *node;
+ unsigned int seq;
+
+ do {
+ seq = raw_read_seqcount(&root->seq);
+ node = __lt_find(key, &root->tree[seq & 1], ops->comp);
+ } while (read_seqcount_retry(&root->seq, seq));
+
+ return node;
+}
+
+#endif /* RB_TREE_LATCH_H */
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_core<n_init can't share the same ->less() 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.
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.
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.
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_node mtn_core;
+ struct mod_tree_node mtn_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 <linux/seqlock.h>
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 = <r->tree[idx];
struct rb_node **link = &root->rb_node;
+ struct rb_node *node = <n->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(<n->node, parent, link);
- rb_insert_color(<n->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(<n->node, root);
+ rb_erase(<n->node[idx], <r->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
+ * @root: trees to insert @node into
* @ops: operators defining the node order
*
- * Initializes @nodes private pointer with @priv; which typically is a back
- * pointer to the containing structure, used by @ops to find the search key.
+ * It inserts @node into @root in an ordered fashion such that we can always
+ * observe one complete tree. See the comment for raw_write_seqcount_latch().
*
- * Then it inserts @nodes into @root in an ordered fashion such that we can
- * always observe one complete tree. See the comment for
- * raw_write_seqcount_latch().
- *
- * The inserts use rcu_assign_pointer() to publish the element such that
- * both the @priv pointer values in @nodes as the tree structure is stored
- * before we can observe the new @nodes.
+ * The inserts use rcu_assign_pointer() to publish the element such that the
+ * tree structure is stored before we can observe the new @node.
*
* All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
* serialized.
*/
static __always_inline void
-latch_tree_insert(struct latch_tree_nodes *nodes,
+latch_tree_insert(struct latch_tree_node *node,
struct latch_tree_root *root,
- void *priv,
const struct latch_tree_ops *ops)
{
- nodes->node[0].priv = nodes->node[1].priv = priv;
-
raw_write_seqcount_latch(&root->seq);
- __lt_insert(&nodes->node[0], &root->tree[0], ops->less);
+ __lt_insert(node, root, 0, ops->less);
raw_write_seqcount_latch(&root->seq);
- __lt_insert(&nodes->node[1], &root->tree[1], ops->less);
+ __lt_insert(node, root, 1, ops->less);
}
/**
- * latch_tree_erase() - removes @nodes from the trees @root
- * @nodes: nodes to remote
- * @root: trees to remove @nodes from
+ * latch_tree_erase() - removes @node from the trees @root
+ * @node: nodes to remote
+ * @root: trees to remove @node from
* @ops: operators defining the node order
*
- * Removes @nodes from the trees @root in an ordered fashion such that we can
+ * Removes @node from the trees @root in an ordered fashion such that we can
* always observe one complete tree. See the comment for
* raw_write_seqcount_latch().
*
- * It is assumed that @nodes will observe one RCU quiescent state before being
+ * It is assumed that @node will observe one RCU quiescent state before being
* reused of freed.
*
* All modifications (latch_tree_insert, latch_tree_remove) are assumed to be
* serialized.
*/
static __always_inline void
-latch_tree_erase(struct latch_tree_nodes *nodes,
+latch_tree_erase(struct latch_tree_node *node,
struct latch_tree_root *root,
const struct latch_tree_ops *ops)
{
raw_write_seqcount_latch(&root->seq);
- __lt_erase(&nodes->node[0], &root->tree[0]);
+ __lt_erase(node, root, 0);
raw_write_seqcount_latch(&root->seq);
- __lt_erase(&nodes->node[1], &root->tree[1]);
+ __lt_erase(node, root, 1);
}
/**
@@ -214,7 +203,7 @@ latch_tree_find(void *key, struct latch_
do {
seq = raw_read_seqcount(&root->seq);
- node = __lt_find(key, &root->tree[seq & 1], ops->comp);
+ node = __lt_find(key, root, seq & 1, ops->comp);
} while (read_seqcount_retry(&root->seq, seq));
return node;
--- a/kernel/module.c
+++ b/kernel/module.c
@@ -119,22 +119,24 @@ static LIST_HEAD(modules);
static __always_inline unsigned long __mod_tree_val(struct latch_tree_node *n)
{
- struct module *mod = n->priv;
+ struct mod_tree_node *mtn = container_of(n, struct mod_tree_node, node);
+ struct module *mod = mtn->mod;
- if (n >= mod->ltn_init.node)
+ if (unlikely(mtn == &mod->mtn_init))
return (unsigned long)mod->module_init;
- else
- return (unsigned long)mod->module_core;
+
+ return (unsigned long)mod->module_core;
}
static __always_inline unsigned long __mod_tree_size(struct latch_tree_node *n)
{
- struct module *mod = n->priv;
+ struct mod_tree_node *mtn = container_of(n, struct mod_tree_node, node);
+ struct module *mod = mtn->mod;
- if (n >= mod->ltn_init.node)
+ if (unlikely(mtn == &mod->mtn_init))
return (unsigned long)mod->init_size;
- else
- return (unsigned long)mod->core_size;
+
+ return (unsigned long)mod->core_size;
}
static __always_inline bool
@@ -174,20 +176,23 @@ static struct latch_tree_root mod_tree _
*/
static void mod_tree_insert(struct module *mod)
{
- latch_tree_insert(&mod->ltn_core, &mod_tree, mod, &mod_tree_ops);
+ mod->mtn_core.mod = mod;
+ mod->mtn_init.mod = mod;
+
+ latch_tree_insert(&mod->mtn_core.node, &mod_tree, &mod_tree_ops);
if (mod->init_size)
- latch_tree_insert(&mod->ltn_init, &mod_tree, mod, &mod_tree_ops);
+ latch_tree_insert(&mod->mtn_init.node, &mod_tree, &mod_tree_ops);
}
static void mod_tree_remove_init(struct module *mod)
{
if (mod->init_size)
- latch_tree_erase(&mod->ltn_init, &mod_tree, &mod_tree_ops);
+ latch_tree_erase(&mod->mtn_init.node, &mod_tree, &mod_tree_ops);
}
static void mod_tree_remove(struct module *mod)
{
- latch_tree_erase(&mod->ltn_core, &mod_tree, &mod_tree_ops);
+ latch_tree_erase(&mod->mtn_core.node, &mod_tree, &mod_tree_ops);
mod_tree_remove_init(mod);
}
@@ -196,8 +201,10 @@ static struct module *mod_find(unsigned
struct latch_tree_node *ltn;
ltn = latch_tree_find((void *)addr, &mod_tree, &mod_tree_ops);
+ if (!ltn)
+ return NULL;
- return ltn ? ltn->priv : NULL;
+ return container_of(ltn, struct mod_tree_node, node)->mod;
}
#else /* !(PERF_EVENTS || TRACING) */
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.
On Thu, Apr 9, 2015 at 5:13 AM, Peter Zijlstra <[email protected]> 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
On Thu, Apr 09, 2015 at 09:31:16AM -0700, Linus Torvalds wrote:
> On Thu, Apr 9, 2015 at 5:13 AM, Peter Zijlstra <[email protected]> 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.
On Thu, Apr 9, 2015 at 9:59 AM, Peter Zijlstra <[email protected]> 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
On Thu, Apr 9, 2015 at 10:12 AM, Linus Torvalds
<[email protected]> 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