On Mon, 2012-04-30 at 06:11 -0500, Daniel Santos wrote:
>
> So as long as our struct rbtree_relationship is a compile-time
> constant, the generated code will look pretty much (if not exactly)
> like that of the example code in rbtree.h. Please let me know what
> you think. I've tested this in a userspace program, but haven't fully
> stress tested it in kernelspace yet.
Right, this ought to work.
I'm not sure the root_offset thing is worth it though, passing in the
rb_root pointer isn't much of a hassle, in fact I'd expect to pass rb
related pointers to a function called rbtree_insert().
Also, using a macro to create the rbtree_relationship thing would make
it easier. Something like:
RB_RELATION(struct mouse, node, name, name_cmp);
I'd think you'd also want to provide an insertion variant that does the
leftmost thing, that's used in several places, and you'd also need one
for the augmented rb-tree.
On Tue, 2012-05-01 at 13:20 +0200, Peter Zijlstra wrote:
> On Mon, 2012-04-30 at 06:11 -0500, Daniel Santos wrote:
> >
> > So as long as our struct rbtree_relationship is a compile-time
> > constant, the generated code will look pretty much (if not exactly)
> > like that of the example code in rbtree.h. Please let me know what
> > you think. I've tested this in a userspace program, but haven't fully
> > stress tested it in kernelspace yet.
>
> Right, this ought to work.
>
> I'm not sure the root_offset thing is worth it though, passing in the
> rb_root pointer isn't much of a hassle, in fact I'd expect to pass rb
> related pointers to a function called rbtree_insert().
>
> Also, using a macro to create the rbtree_relationship thing would make
> it easier. Something like:
>
> RB_RELATION(struct mouse, node, name, name_cmp);
>
> I'd think you'd also want to provide an insertion variant that does the
> leftmost thing, that's used in several places, and you'd also need one
> for the augmented rb-tree.
Something like the below,.. I wanted to add typechecking to
__RB_RELS_KEY and __RB_RELS_LEFT like:
#define __RB_RELS_KEY(_node_type, _node, _key) \
(typecheck(struct rb_node *, &((_node_type *)NULL)->_node), \
__REL_OFFSET(_node_type, _node, _key))
#define __RB_RELS_LEFT(_root_type, _root, _left) \
(typecheck(struct rb_root *, &((_root_type *)NULL)->_root), \
typecheck(struct rb_node *, ((_root_type *)NULL)->_left), \
__REL_OFFSET(_root_type, _root, _left))
But I didn't find a way to make GCC like that.
The below compiles, I haven't looked at the generated asm, nor booted
the thing.
---
include/linux/rbtree.h | 84 ++++++++++++++++++++++++++++++++++++++++++++++++
kernel/sched/fair.c | 51 ++++++-----------------------
2 files changed, 93 insertions(+), 42 deletions(-)
diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..2a5f803 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -96,6 +96,8 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
#include <linux/kernel.h>
#include <linux/stddef.h>
+#include <linux/typecheck.h>
+#include <linux/bug.h>
struct rb_node
{
@@ -174,4 +176,86 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
*rb_link = node;
}
+struct rbtree_relations {
+ size_t key_offset;
+ size_t left_offset;
+
+ bool (*less)(const void *a, const void *b);
+};
+
+#define __REL_OFFSET(_t, _f1, _f2) \
+ (offsetof(_t, _f2) - offsetof(_t, _f1))
+
+#define __RB_RELS_KEY(_node_type, _node, _key) \
+ __REL_OFFSET(_node_type, _node, _key)
+
+#define __RB_RELS_LEFT(_root_type, _root, _left) \
+ __REL_OFFSET(_root_type, _root, _left)
+
+#define RB_RELATIONS(_node_type, _node, _key, _less) \
+ (const struct rbtree_relations){ \
+ .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
+ .less = (bool (*)(const void *, const void *))_less, \
+ }
+
+#define RB_RELATIONS_LEFT(_root_type, _root, _left, _node_type, _node, _key, _less) \
+ (const struct rbtree_relations){ \
+ .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
+ .left_offset = __RB_RELS_LEFT(_root_type, _root, _left), \
+ .less = (bool (*)(const void *, const void *))_less, \
+ }
+
+static __always_inline
+const void *__rb_node_to_key(const struct rbtree_relations *rel, struct rb_node *node)
+{
+ BUILD_BUG_ON(!__builtin_constant_p(rel->key_offset));
+ return (const void *)((char *)node + rel->key_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_left(const struct rbtree_relations *rel, struct rb_root *root)
+{
+ BUILD_BUG_ON(!__builtin_constant_p(rel->left_offset));
+ return (struct rb_node **)((char *)root + rel->left_offset);
+}
+
+static __always_inline
+void rbtree_insert(struct rb_root *root, struct rb_node *node,
+ const struct rbtree_relations *rel)
+{
+ struct rb_node **p = &root->rb_node;
+ struct rb_node *parent = NULL;
+ const void *key = __rb_node_to_key(rel, node);
+ int leftmost = 1;
+
+ while (*p) {
+ parent = *p;
+ if (rel->less(key, __rb_node_to_key(rel, *p)))
+ p = &(*p)->rb_left;
+ else {
+ p = &(*p)->rb_right;
+ leftmost = 0;
+ }
+ }
+
+ if (rel->left_offset && leftmost)
+ *__rb_root_to_left(rel, root) = node;
+
+ rb_link_node(node, parent, p);
+ rb_insert_color(node, root);
+}
+
+static __always_inline
+void rbtree_remove(struct rb_root *root, struct rb_node *node,
+ const struct rbtree_relations *rel)
+{
+ if (rel->left_offset) {
+ struct rb_node **left = __rb_root_to_left(rel, root);
+
+ if (*left == node)
+ *left = rb_next(node);
+ }
+ rb_erase(node, root);
+}
+
#endif /* _LINUX_RBTREE_H */
diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e955364..81424a9 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -441,8 +441,8 @@ static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
return min_vruntime;
}
-static inline int entity_before(struct sched_entity *a,
- struct sched_entity *b)
+static inline bool entity_before(struct sched_entity *a,
+ struct sched_entity *b)
{
return (s64)(a->vruntime - b->vruntime) < 0;
}
@@ -472,55 +472,22 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
#endif
}
+static const struct rbtree_relations fair_tree_rels =
+ RB_RELATIONS_LEFT(struct cfs_rq, tasks_timeline, rb_leftmost,
+ struct sched_entity, run_node, vruntime,
+ entity_before);
+
/*
* Enqueue an entity into the rb-tree:
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
- struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
- struct rb_node *parent = NULL;
- struct sched_entity *entry;
- int leftmost = 1;
-
- /*
- * Find the right place in the rbtree:
- */
- while (*link) {
- parent = *link;
- entry = rb_entry(parent, struct sched_entity, run_node);
- /*
- * We dont care about collisions. Nodes with
- * the same key stay together.
- */
- if (entity_before(se, entry)) {
- link = &parent->rb_left;
- } else {
- link = &parent->rb_right;
- leftmost = 0;
- }
- }
-
- /*
- * Maintain a cache of leftmost tree entries (it is frequently
- * used):
- */
- if (leftmost)
- cfs_rq->rb_leftmost = &se->run_node;
-
- rb_link_node(&se->run_node, parent, link);
- rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
+ rbtree_insert(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
}
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
- if (cfs_rq->rb_leftmost == &se->run_node) {
- struct rb_node *next_node;
-
- next_node = rb_next(&se->run_node);
- cfs_rq->rb_leftmost = next_node;
- }
-
- rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
+ rbtree_remove(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
}
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
Thanks for examining this! I don't see any major problems with omitting
the root node offset & accompanying mechanisms. However, first consider
it's purpose: the idea is to define a relationship between two
structures and then call generic functions to manipulate them. Removing
the root node offset reduces the scope and complexity of the generic
rbtree interface, but also eliminates an abstraction mechanism, which
can be desirable at times. None the less, there are many cases where a
struct rb_root is used as a stand-alone variable, and even though it
could still be used by passing zero for the root_node offset, It would
appear to be chaff most (almost all?) of the time, so I can see that you
are right about this.
On to naming, I think it's probably better to prefix all of these
functions with "rb_" rather than "rbtree_" (as I had done), partially
for brevity, but mostly for consistency.
Next, is the issue of rather or not duplicate keys are allowed, which I
didn't think about when I wrote my code. For my purposes, I cannot have
duplicate keys, so I coded it that way. As I see it, the interface
should support both. Again, I think it better to have a single inline
function that will support duplicate keys or not depending upon a
compile-time constant fed to it. This adds complexity to the actual
insert function while reducing complexity in the interface (number of
functions) and sources. As long as gcc behaves, the generated code will
be exactly what is needed and no more (else, we go with adding separate
insert functions for duplicate keys allowed and not). On top of that, I
tried to leave it up to the caller as to rather or not they wanted their
"insert without duplicates" function to replace an object with a
matching key or not -- I guess some of this depends on what is needed,
but it would seem to make sense to leave that functionality in as well,
as long as it doesn't generated any extra instructions when it isn't needed.
Finally, as for augmented rbtrees, I'm not familiar with them, but I
just read an LWN article about them and they sound cool! Not only that,
they sound like an excellent candidate for this type of genericizing.
Had I known about them before, I would have used them in some other
(userspace) code where I'm using the linux rbtree implementation. So
I'll play with this tomorrow.
As a side note, I had originally tried to combine the search & insert
implementation into a single function that expanded differently
depending upon how it was called (again, with compile-time constants)
but it became it too ugly, so I split it out.
Daniel
PS: the BUILD_BUG_ON macro is really cool, thanks for showing that to me!
On 05/01/2012 11:00 AM, Peter Zijlstra wrote:
> On Tue, 2012-05-01 at 13:20 +0200, Peter Zijlstra wrote:
>> On Mon, 2012-04-30 at 06:11 -0500, Daniel Santos wrote:
>>> So as long as our struct rbtree_relationship is a compile-time
>>> constant, the generated code will look pretty much (if not exactly)
>>> like that of the example code in rbtree.h. Please let me know what
>>> you think. I've tested this in a userspace program, but haven't fully
>>> stress tested it in kernelspace yet.
>> Right, this ought to work.
>>
>> I'm not sure the root_offset thing is worth it though, passing in the
>> rb_root pointer isn't much of a hassle, in fact I'd expect to pass rb
>> related pointers to a function called rbtree_insert().
>>
>> Also, using a macro to create the rbtree_relationship thing would make
>> it easier. Something like:
>>
>> RB_RELATION(struct mouse, node, name, name_cmp);
>>
>> I'd think you'd also want to provide an insertion variant that does the
>> leftmost thing, that's used in several places, and you'd also need one
>> for the augmented rb-tree.
> Something like the below,.. I wanted to add typechecking to
> __RB_RELS_KEY and __RB_RELS_LEFT like:
>
> #define __RB_RELS_KEY(_node_type, _node, _key) \
> (typecheck(struct rb_node *, &((_node_type *)NULL)->_node), \
> __REL_OFFSET(_node_type, _node, _key))
>
> #define __RB_RELS_LEFT(_root_type, _root, _left) \
> (typecheck(struct rb_root *, &((_root_type *)NULL)->_root), \
> typecheck(struct rb_node *, ((_root_type *)NULL)->_left), \
> __REL_OFFSET(_root_type, _root, _left))
>
> But I didn't find a way to make GCC like that.
>
> The below compiles, I haven't looked at the generated asm, nor booted
> the thing.
>
> ---
> include/linux/rbtree.h | 84 ++++++++++++++++++++++++++++++++++++++++++++++++
> kernel/sched/fair.c | 51 ++++++-----------------------
> 2 files changed, 93 insertions(+), 42 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 033b507..2a5f803 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -96,6 +96,8 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
>
> #include <linux/kernel.h>
> #include <linux/stddef.h>
> +#include <linux/typecheck.h>
> +#include <linux/bug.h>
>
> struct rb_node
> {
> @@ -174,4 +176,86 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
> *rb_link = node;
> }
>
> +struct rbtree_relations {
> + size_t key_offset;
> + size_t left_offset;
> +
> + bool (*less)(const void *a, const void *b);
> +};
> +
> +#define __REL_OFFSET(_t, _f1, _f2) \
> + (offsetof(_t, _f2) - offsetof(_t, _f1))
> +
> +#define __RB_RELS_KEY(_node_type, _node, _key) \
> + __REL_OFFSET(_node_type, _node, _key)
> +
> +#define __RB_RELS_LEFT(_root_type, _root, _left) \
> + __REL_OFFSET(_root_type, _root, _left)
> +
> +#define RB_RELATIONS(_node_type, _node, _key, _less) \
> + (const struct rbtree_relations){ \
> + .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
> + .less = (bool (*)(const void *, const void *))_less, \
> + }
> +
> +#define RB_RELATIONS_LEFT(_root_type, _root, _left, _node_type, _node, _key, _less) \
> + (const struct rbtree_relations){ \
> + .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
> + .left_offset = __RB_RELS_LEFT(_root_type, _root, _left), \
> + .less = (bool (*)(const void *, const void *))_less, \
> + }
> +
> +static __always_inline
> +const void *__rb_node_to_key(const struct rbtree_relations *rel, struct rb_node *node)
> +{
> + BUILD_BUG_ON(!__builtin_constant_p(rel->key_offset));
> + return (const void *)((char *)node + rel->key_offset);
> +}
> +
> +static __always_inline
> +struct rb_node **__rb_root_to_left(const struct rbtree_relations *rel, struct rb_root *root)
> +{
> + BUILD_BUG_ON(!__builtin_constant_p(rel->left_offset));
> + return (struct rb_node **)((char *)root + rel->left_offset);
> +}
> +
> +static __always_inline
> +void rbtree_insert(struct rb_root *root, struct rb_node *node,
> + const struct rbtree_relations *rel)
> +{
> + struct rb_node **p = &root->rb_node;
> + struct rb_node *parent = NULL;
> + const void *key = __rb_node_to_key(rel, node);
> + int leftmost = 1;
> +
> + while (*p) {
> + parent = *p;
> + if (rel->less(key, __rb_node_to_key(rel, *p)))
> + p = &(*p)->rb_left;
> + else {
> + p = &(*p)->rb_right;
> + leftmost = 0;
> + }
> + }
> +
> + if (rel->left_offset && leftmost)
> + *__rb_root_to_left(rel, root) = node;
> +
> + rb_link_node(node, parent, p);
> + rb_insert_color(node, root);
> +}
> +
> +static __always_inline
> +void rbtree_remove(struct rb_root *root, struct rb_node *node,
> + const struct rbtree_relations *rel)
> +{
> + if (rel->left_offset) {
> + struct rb_node **left = __rb_root_to_left(rel, root);
> +
> + if (*left == node)
> + *left = rb_next(node);
> + }
> + rb_erase(node, root);
> +}
> +
> #endif /* _LINUX_RBTREE_H */
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e955364..81424a9 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -441,8 +441,8 @@ static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
> return min_vruntime;
> }
>
> -static inline int entity_before(struct sched_entity *a,
> - struct sched_entity *b)
> +static inline bool entity_before(struct sched_entity *a,
> + struct sched_entity *b)
> {
> return (s64)(a->vruntime - b->vruntime) < 0;
> }
> @@ -472,55 +472,22 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
> #endif
> }
>
> +static const struct rbtree_relations fair_tree_rels =
> + RB_RELATIONS_LEFT(struct cfs_rq, tasks_timeline, rb_leftmost,
> + struct sched_entity, run_node, vruntime,
> + entity_before);
> +
> /*
> * Enqueue an entity into the rb-tree:
> */
> static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
> - struct rb_node *parent = NULL;
> - struct sched_entity *entry;
> - int leftmost = 1;
> -
> - /*
> - * Find the right place in the rbtree:
> - */
> - while (*link) {
> - parent = *link;
> - entry = rb_entry(parent, struct sched_entity, run_node);
> - /*
> - * We dont care about collisions. Nodes with
> - * the same key stay together.
> - */
> - if (entity_before(se, entry)) {
> - link = &parent->rb_left;
> - } else {
> - link = &parent->rb_right;
> - leftmost = 0;
> - }
> - }
> -
> - /*
> - * Maintain a cache of leftmost tree entries (it is frequently
> - * used):
> - */
> - if (leftmost)
> - cfs_rq->rb_leftmost = &se->run_node;
> -
> - rb_link_node(&se->run_node, parent, link);
> - rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
> + rbtree_insert(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
> }
>
> static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - if (cfs_rq->rb_leftmost == &se->run_node) {
> - struct rb_node *next_node;
> -
> - next_node = rb_next(&se->run_node);
> - cfs_rq->rb_leftmost = next_node;
> - }
> -
> - rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
> + rbtree_remove(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
> }
>
> struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
>
> --
> To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
> the body of a message to [email protected]
> More majordomo info at http://vger.kernel.org/majordomo-info.html
> Please read the FAQ at http://www.tux.org/lkml/
>
--
Daniel
"Just because you go to church on Sunday, it doesn't absolve you from
where you put your dick during the week" -- Michele Q.
After working with this a bit more and thinking about it more, I've come
to a few conclusions. First off, my original approach (aside from not
supporting leftmost or duplicate keys) created an alternate paradigm
that I think you may have misunderstood (granted, it's lacking in some
areas). The concept is a mechanism to interact with an rb-tree
interface where you directly "talk your types" and leave the details to
the interface. That is, once you setup your struct rb_relationship, you
don't mess with the struct rb_node and struct rb_root members of your
structs again (in theory). As long as everything goes well in the
compiler, all of the overhead for this abstraction is completely
compiled out. Thus,
rbtree_insert(&my_container->some_objects, &my_object->rb_node, rel);
generates the exact same code as
rbtree_insert(my_container, my_object, rel);
where the initial section of rbtree_insert() contains this:
struct rb_root *root = __rb_to_root(container, rel);
struct rb_node *node = __rb_to_node(obj, rel);
Being that the root_offset and node_offset members are compile-time
constants and the _rb_to_xxx() static inlines simply do pointer
arithmetic. Either way, the compiler must take the address of your
struct and perform an access with an offset. So none of this should be
a performance issue. One serious flaw in my eyes is the lack of type
safety and the expectation of the implementor to pass the correct
types. I've thought about this and I think it should be addressed with
a macro somehow.
But what the real issue here is interface. My proposal isn't
consistient with the interface in rb_tree.h, I guess that's why I
thought to put it in a separate file and use a different function
prefix: rbtree_ instead of rb_. However, I guess the real questions are:
* Can an interface be designed perfectly enough that users can perform
all functionality only passing pointers to their actual containers &
objects and still have zero overhead for doing so? (my proposal only
addresses part of it)
* Should an interface... ^^ (the above)?
* Is this a paradigm that can be accepted?
I don't consider myself a serious power C programmer, I'm mainly from
the OO, Java, C++, metaprogramming arena, which I'm sure is why I tend
to think in abstractions and figuring out what I can force the compiler
to do. If you try to think in terms of databases, the struct
rb_relationship is like the DDL that describes the relationship &
constraints between two entities. This is my updated struct to cover
leftmost & non-unique keys:
struct rb_relationship {
size_t root_offset;
size_t left_offset;
size_t node_offset;
size_t key_offset;
long (*compare)(const void *a, const void *b);
int unique;
};
Alternately, I can add this to rbtree.h and remove the
object-abstraction, using something similar to Peter's proposal (the
struct rb_relationship only specifies offsets from struct rb_node to the
key and struct rb_root to the "leftmost" pointer), but this means
abandoning a certain level of abstraction that may actually be good as
it removes a layer of details from the code that uses rbtrees, keeping
sources tidier and supporting encapsulation.
Daniel
On 05/01/2012 11:00 AM, Peter Zijlstra wrote:
>
> Something like the below,.. I wanted to add typechecking to
> __RB_RELS_KEY and __RB_RELS_LEFT like:
>
> #define __RB_RELS_KEY(_node_type, _node, _key) \
> (typecheck(struct rb_node *, &((_node_type *)NULL)->_node), \
> __REL_OFFSET(_node_type, _node, _key))
>
> #define __RB_RELS_LEFT(_root_type, _root, _left) \
> (typecheck(struct rb_root *, &((_root_type *)NULL)->_root), \
> typecheck(struct rb_node *, ((_root_type *)NULL)->_left), \
> __REL_OFFSET(_root_type, _root, _left))
>
> But I didn't find a way to make GCC like that.
>
> The below compiles, I haven't looked at the generated asm, nor booted
> the thing.
>
> ---
> include/linux/rbtree.h | 84 ++++++++++++++++++++++++++++++++++++++++++++++++
> kernel/sched/fair.c | 51 ++++++-----------------------
> 2 files changed, 93 insertions(+), 42 deletions(-)
>
> diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
> index 033b507..2a5f803 100644
> --- a/include/linux/rbtree.h
> +++ b/include/linux/rbtree.h
> @@ -96,6 +96,8 @@ static inline struct page * rb_insert_page_cache(struct inode * inode,
>
> #include <linux/kernel.h>
> #include <linux/stddef.h>
> +#include <linux/typecheck.h>
> +#include <linux/bug.h>
>
> struct rb_node
> {
> @@ -174,4 +176,86 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
> *rb_link = node;
> }
>
> +struct rbtree_relations {
> + size_t key_offset;
> + size_t left_offset;
> +
> + bool (*less)(const void *a, const void *b);
> +};
> +
> +#define __REL_OFFSET(_t, _f1, _f2) \
> + (offsetof(_t, _f2) - offsetof(_t, _f1))
> +
> +#define __RB_RELS_KEY(_node_type, _node, _key) \
> + __REL_OFFSET(_node_type, _node, _key)
> +
> +#define __RB_RELS_LEFT(_root_type, _root, _left) \
> + __REL_OFFSET(_root_type, _root, _left)
> +
> +#define RB_RELATIONS(_node_type, _node, _key, _less) \
> + (const struct rbtree_relations){ \
> + .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
> + .less = (bool (*)(const void *, const void *))_less, \
> + }
> +
> +#define RB_RELATIONS_LEFT(_root_type, _root, _left, _node_type, _node, _key, _less) \
> + (const struct rbtree_relations){ \
> + .key_offset = __RB_RELS_KEY(_node_type, _node, _key), \
> + .left_offset = __RB_RELS_LEFT(_root_type, _root, _left), \
> + .less = (bool (*)(const void *, const void *))_less, \
> + }
> +
> +static __always_inline
> +const void *__rb_node_to_key(const struct rbtree_relations *rel, struct rb_node *node)
> +{
> + BUILD_BUG_ON(!__builtin_constant_p(rel->key_offset));
> + return (const void *)((char *)node + rel->key_offset);
> +}
> +
> +static __always_inline
> +struct rb_node **__rb_root_to_left(const struct rbtree_relations *rel, struct rb_root *root)
> +{
> + BUILD_BUG_ON(!__builtin_constant_p(rel->left_offset));
> + return (struct rb_node **)((char *)root + rel->left_offset);
> +}
> +
> +static __always_inline
> +void rbtree_insert(struct rb_root *root, struct rb_node *node,
> + const struct rbtree_relations *rel)
> +{
> + struct rb_node **p = &root->rb_node;
> + struct rb_node *parent = NULL;
> + const void *key = __rb_node_to_key(rel, node);
> + int leftmost = 1;
> +
> + while (*p) {
> + parent = *p;
> + if (rel->less(key, __rb_node_to_key(rel, *p)))
> + p = &(*p)->rb_left;
> + else {
> + p = &(*p)->rb_right;
> + leftmost = 0;
> + }
> + }
> +
> + if (rel->left_offset && leftmost)
> + *__rb_root_to_left(rel, root) = node;
> +
> + rb_link_node(node, parent, p);
> + rb_insert_color(node, root);
> +}
> +
> +static __always_inline
> +void rbtree_remove(struct rb_root *root, struct rb_node *node,
> + const struct rbtree_relations *rel)
> +{
> + if (rel->left_offset) {
> + struct rb_node **left = __rb_root_to_left(rel, root);
> +
> + if (*left == node)
> + *left = rb_next(node);
> + }
> + rb_erase(node, root);
> +}
> +
> #endif /* _LINUX_RBTREE_H */
> diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
> index e955364..81424a9 100644
> --- a/kernel/sched/fair.c
> +++ b/kernel/sched/fair.c
> @@ -441,8 +441,8 @@ static inline u64 min_vruntime(u64 min_vruntime, u64 vruntime)
> return min_vruntime;
> }
>
> -static inline int entity_before(struct sched_entity *a,
> - struct sched_entity *b)
> +static inline bool entity_before(struct sched_entity *a,
> + struct sched_entity *b)
> {
> return (s64)(a->vruntime - b->vruntime) < 0;
> }
> @@ -472,55 +472,22 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
> #endif
> }
>
> +static const struct rbtree_relations fair_tree_rels =
> + RB_RELATIONS_LEFT(struct cfs_rq, tasks_timeline, rb_leftmost,
> + struct sched_entity, run_node, vruntime,
> + entity_before);
> +
> /*
> * Enqueue an entity into the rb-tree:
> */
> static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
> - struct rb_node *parent = NULL;
> - struct sched_entity *entry;
> - int leftmost = 1;
> -
> - /*
> - * Find the right place in the rbtree:
> - */
> - while (*link) {
> - parent = *link;
> - entry = rb_entry(parent, struct sched_entity, run_node);
> - /*
> - * We dont care about collisions. Nodes with
> - * the same key stay together.
> - */
> - if (entity_before(se, entry)) {
> - link = &parent->rb_left;
> - } else {
> - link = &parent->rb_right;
> - leftmost = 0;
> - }
> - }
> -
> - /*
> - * Maintain a cache of leftmost tree entries (it is frequently
> - * used):
> - */
> - if (leftmost)
> - cfs_rq->rb_leftmost = &se->run_node;
> -
> - rb_link_node(&se->run_node, parent, link);
> - rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
> + rbtree_insert(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
> }
>
> static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
> {
> - if (cfs_rq->rb_leftmost == &se->run_node) {
> - struct rb_node *next_node;
> -
> - next_node = rb_next(&se->run_node);
> - cfs_rq->rb_leftmost = next_node;
> - }
> -
> - rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
> + rbtree_remove(&cfs_rq->tasks_timeline, &se->run_node, &fair_tree_rels);
> }
>
> struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
>
I've been working on this more and have gone through several
iterations. I have a small problem: my mechanism will never inline the
key compare function call since it calls it by pointer. I'm not sure if
this is dictated in the C specification or if it's just something gcc
can't currently detect as a compile-time constant and optimize out.
Every other option specified via the struct rb_relationship is getting
nicely optimized, removing unused code, etc.
Here is the current feature set (all optimized out when not used):
* leftmost - keep a pointer to the leftmost (lowest value) node cached
in your container struct (thanks Peter)
* rightmost - ditto for rightmost (greatest value)
* unique or non-unique keys with some minor tuning options
* relative searches - when you already have a node that is likely near
another one you want to search for
* augmented / interval tree support (not yet tested)
So back to the problem, as I see it here are my options:
1. Create a header file where you #define your parameters and include it
to define your search, insert & remove functions. Example:
#define RBTREE_CONTAINER_TYPE struct my_container
#define RBTREE_CONTAINER_ROOT rb_root /* struct rb_root member */
#define RBTREE_CONTAINER_LEFTMOST leftmost /* struct rb_node *member */
#define RBTREE_CONTAINER_RIGHTMOST /* none */
#define RBTREE_OBJECT_TYPE struct my_obj
#define RBTREE_OBJECT_NODE rb_node /* struct rb_node member */
#define RBTREE_OBJECT_KEY mykey
#define RBTREE_KEY_COMPARE compare_my_key
#define etc...
#include <linux/grbtree.h> /* expands parameters where needed and then
#undefs them. */
2. Use a big ugly macro to define them. Example:
RB_DEFINE_CORE(struct my_container, rb_root, etc...) /* expands to all
function implementations */
3. Accept the compare function call overhead for search & insert
functions and keep them normal (i.e., __always_inline, non-preprocessor)
generic functions.
Here are the benefits of each, as I see it:
Debugging information will still point you to a real line of code
1. Yes, 2. No, 3. Yes
Type safety implemented (you pass pointers to your container & object
structs directly rather than node pointers)
1. Yes, 2. Yes, 3. No
Maximum efficiency (no function calls to inline-ables like compare and
augmented)
1. Yes, 2. Yes, 3. No
Relies primarily upon:
1. cpp, 2. cpp, 3. cc
To me, the first option seems like it makes the most sense, although I
despise heavy use of the preprocessor (it would be sweet if ANSI came
out with a C templates standard). Attached is my current working
version which implements approach 3 as described above. It has a
GRB_DEFINE_INTERFACE() macro, but it only defines a type a type-safe
interface and doesn't fix the compare function not inlined problem.
(Much of comment docs are out of date too.)
Thanks in advance.
Daniel