Generic rbtree search & insert cores

Generic rbtree search & insert cores

[Daniel Santos]

[-- Attachment #1: Type: text/plain, Size: 1620 bytes --]

I believe I've solved the problem of having generic search & insert cores in C.  Attached is my current working version of rbtree_ext.h.  While I've included an example in my documentation, here's a quickie:

/* Header File */
#include <linux/rbtree_ext.h>

struct house {
    struct rb_root mice;
};

struct mouse {
    struct rb_node node;
    const char*    name;
};

extern struct mouse *find_mouse(struct house *house, const char *name);
extern struct mouse *put_mouse_in_house(struct house *house,
                    struct mouse *mouse);

/* Implementation File */
#include "myheader.h"

static inline int name_cmp(const char **a, const char **b) {
    return strcmp(*a, *b);
}

static const struct rbtree_relationship rel_house_to_mouse = {
    .root_offset = offsetof(struct house, mice),
    .node_offset = offsetof(struct mouse, node),
    .key_offset  = offsetof(struct mouse, name),
    .compare     = (int(*)(const void*, const void*))name_cmp;
};

/* inline expansion occurs here and our object file doesn't bloat */
struct mouse *find_mouse(struct house *house, const char *name) {
    return rbtree_find(house, name, &rel_house_to_mouse);
}

struct mouse *put_mouse_in_house(struct house *house, struct mouse *mouse) {
    return rbtree_insert(house, mouse, 1, &rel_house_to_mouse);
}

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.

Daniel


[-- Attachment #2: rbtree_ext.h --]
[-- Type: text/x-chdr, Size: 10179 bytes --]

/*
 * Red Black Tree Extensions
 *
 * Copyright (C) 2012  Daniel Santos <daniel.santos@pobox.com>
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2 of the License, or
 * (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; if not, write to the Free Software
 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
 * USA.
 */

/*
 * Red Black Tree Extensions (brtree_ext.h) extends upon Andrea Arcangeli's
 * rbtree implementation adding the ability to define relationships between
 * containers and their contents (see struct rbtree_relationship) and feeding
 * those relationships to generic find and insert functions. By using
 * compile-time constant instances of struct rbtree_relationship and a single
 * instantiation of the static inline find & insert functions, gcc will
 * generate code that is exactly as efficient as if you had implemented your
 * own file & insert functions (as explained in rbtree.h) without the source
 * bloat and added complexity.  Further, by wrapping the static inline find &
 * insert functions in singular (non-inline) functions, type-safety can be
 * achived while preventing the bloat of inline expansion.
 *
 * For example, see rbtree_find.
 */
#ifndef _LINUX_RBTREE_EXT_H
#define _LINUX_RBTREE_EXT_H

#include <linux/rbtree.h>

/* Testing the member of a struct with __builtin_constant_p only works in gcc
 * 3.5.0 and later.
 */
#if defined(__GNUC__) && defined(__OPTIMIZE__)		\
	&& ((__GNUC__ == 3 && __GNUC_MINOR__ >= 5) || (__GNUC__ > 3))
#define CHOKE_IF_NOT_COMPILE_TIME_CONST(exp)		\
do {							\
	extern void __not_constant_linktime_error(void);\
	if (!__builtin_constant_p(exp))			\
		__not_constant_linktime_error();	\
} while (0)
#else
#define CHOKE_IF_NOT_COMPILE_TIME_CONST(exp)
#endif


#define __rbtree_toroot(o) ((struct rb_root *)((char *)(o) + rel->root_offset))
#define __rbtree_tonode(o) ((struct rb_node *)((char *)(o) + rel->node_offset))
#define __rbtree_tokey(o)  ((const void *)    ((char *)(o) + rel->key_offset))
#define __rbtree_fromnode(o) ((char *)(o) - rel->node_offset)

/**
 * struct rbtree_relationship - Defines relationship between a container and
 *                      the objects it contains.
 * @root_offset:        Offset of container's struct rb_root member.
 * @node_offset:        Offset of object's struct rb_node member.
 * @key_offset:         Offset of object's key member.
 * @compare:            Compare function for objects -- should be an inline
 *                      function in the same translation unit for proper
 *                      optimization.
 *
 * Instances of struct rbtree_relationship should be compile-time constants if
 * you want good performance.
 */
struct rbtree_relationship {
	size_t root_offset;
	size_t node_offset;
	size_t key_offset;
	int (*compare)(const void *a, const void *b);
};

/**
 * __rbtree_find() - Searches a red black tree.
 * @container:  Container to search.
 * @key:        Pointer to the key you want to find.
 * @rel:        Pointer to the (preferrably compile-time constant)
 *              relationship definition.
 *
 * See rbtree_find.
 *
 * You should use rbtree_find() instead of this function unless you need to
 * pass rel as a runtime value (this will degrade performance and bloat code
 * size somewhat).
 *
 * See rbtree_find for sample code.
 */
static inline void *__rbtree_find(void *container,
				  const void *key,
				  const struct rbtree_relationship *rel)
{
	const struct rb_node *n    = __rbtree_toroot(container)->rb_node;

	while (n) {
		const char *obj = __rbtree_fromnode(n);
		int diff        = rel->compare(__rbtree_tokey(obj), key);

		if (diff > 0)
			n = n->rb_right;
		else if (diff < 0)
			n = n->rb_left;
		else
			return (void *)obj;
	}

	return 0;
}

/**
 * rbtree_find() - Searches a red black tree.
 * @container:  Container to search.
 * @key:        Pointer to the key you want to find.
 * @rel:        Pointer to the compile-time constant relationship definition.
 *
 * On success, returns a pointer to the object (not the struct rb_node), NULL
 * otherwise. If rel is not a compile-time constant, a link-time error will
 * be generated.
 *
 * If your code calls this function from more than one place, it is highly
 * recommended that you wrap this function in a non-inline function. Not doing
 * will can result in either object code bloat or slower searches. You have
 * been advised!  Even if you are calling it from one place, wrapping it in a
 * type-specific function improves type-safety.
 *
 * Egg Sample:
 *
 * // Header File
 *
 * struct house {
 *     struct rb_root mice;
 * };
 *
 * struct mouse {
 *     struct rb_node node;
 *     struct rb_root lice;
 *     const char*    name;
 * };
 *
 * struct louse {
 *     struct rb_node node;
 *     const char*    name;
 * };
 *
 * extern struct mouse *find_mouse(struct house *house, const char *name);
 * extern struct mouse *put_mouse_in_house(struct house *house,
 *                                         struct mouse *mouse);
 *
 * extern struct louse *find_louse(struct mouse *mouse, const char *name);
 * extern struct louse *put_louse_on_mouse(struct mouse *mouse,
 *                                         struct louse *louse);
 *
 * // Implementation File
 *
 * static inline int name_cmp(const char **a, const char **b) {
 *     return strcmp(*a, *b);
 * }
 *
 * static const struct rbtree_relationship rel_house_to_mouse = {
 *     .root_offset = offsetof(struct house, mice),
 *     .node_offset = offsetof(struct mouse, node),
 *     .key_offset  = offsetof(struct mouse, name),
 *     .compare     = (int(*)(const void*, const void*))name_cmp;
 * };
 *
 * static const struct rbtree_relationship rel_mouse_to_louse = {
 *     .root_offset = offsetof(struct mouse, lice),
 *     .node_offset = offsetof(struct louse, node),
 *     .key_offset  = offsetof(struct louse, name),
 *     .compare     = (int(*)(const void*, const void*))name_cmp;
 * };
 *
 * struct mouse *find_mouse(struct house *house, const char *name) {
 *     return rbtree_find(house, name, &rel_house_to_mouse);
 * }
 *
 * struct mouse *put_mouse_in_house(struct house *house, struct mouse *mouse) {
 *     return rbtree_insert(house, mouse, 1, &rel_house_to_mouse);
 * }
 *
 * // ditto for find_louse() and put_louse_on_mouse()
 *
 */
static __always_inline void *rbtree_find(void *container,
					 const void *key,
					 const struct rbtree_relationship *rel)
{
	CHOKE_IF_NOT_COMPILE_TIME_CONST(rel->root_offset);
	return __rbtree_find(container, key, rel);
}

/**
 * __rbtree_insert() - Inserts an object into a container.
 * @container:  Pointer to the container.
 * @obj:        Pointer to the new object to insert.
 * @replace:    Rather or not to replace an existing object.
 * @rel:        Pointer to the (preferably compile-time constant) relationship
 *              definition.
 *
 * See rbtree_insert.
 *
 * You should use rbtree_insert() instead of this function unless you need to
 * pass rel as a runtime value (which will degrade performance and bloat code
 * size).
 */
static inline void *__rbtree_insert(void *container,
				    void *obj,
				    const int replace,
				    const struct rbtree_relationship *rel)
{
	struct rb_root *root   = __rbtree_toroot(container);
	struct rb_node **p     = &root->rb_node;
	struct rb_node *parent = NULL;
	struct rb_node *node   = __rbtree_tonode(obj);
	const void *key        = __rbtree_tokey(obj);

	while (*p) {
		char *thisobj = __rbtree_fromnode(*p);
		int diff      = rel->compare(__rbtree_tokey(thisobj), key);
		parent        = *p;

		if (diff > 0)
			p = &(*p)->rb_right;
		else if (diff < 0)
			p = &(*p)->rb_left;
		else {
			if (replace)
				rb_replace_node(*p, node, root);
			return thisobj;
		}
	}

	rb_link_node(node, parent, p);
	rb_insert_color(node, root);

	return 0;
}


/**
 * __rbtree_insert() - Inserts an object into a container.
 * @container:  Pointer to the container.
 * @obj:        Pointer to the new object to insert.
 * @replace:    Compile-time constant indicating rather or not the
 *              implementation should replace an existing object.
 * @rel:        Pointer to the compile-time constant relationship definition.
 *
 * If an object with the same key already exists and replace is non-zero,
 * then it is replaced with obj; if replace is zero, then no change is made.
 * In either case, a pointer to the existing object is returned. Note that
 * return values are pointers to the objects themselves, not to the struct
 * rb_node.
 *
 * If no object with the same key exists, then obj is inserted and NULL is
 * returned.
 *
 * If either rel or replace are not a compile-time constants, a link-time
 * error will be generated.
 *
 * See rbtree_find for example.
 */
static __always_inline void *rbtree_insert(void *container,
					   void *obj,
					   const int replace,
					   const struct rbtree_relationship *rel)
{
	CHOKE_IF_NOT_COMPILE_TIME_CONST(rel->root_offset);
	CHOKE_IF_NOT_COMPILE_TIME_CONST(replace);
	return __rbtree_insert(container, obj, replace, rel);
}

/**
 * __rbtree_replace() - minor wrapper to rb_replace_node
 */
static inline void __rbtree_replace(void *container,
				    void *victim,
				    void *newobj,
				    const struct rbtree_relationship *rel)
{
	rb_replace_node(__rbtree_tonode(victim),
			__rbtree_tonode(newobj),
			__rbtree_toroot(container));
}

/**
 * rbtree_replace() - minor wrapper to rb_replace_node
 */
static __always_inline void rbtree_replace(void *container,
					   void *victim,
					   void *newobj,
					   const struct rbtree_relationship *rel)
{
	CHOKE_IF_NOT_COMPILE_TIME_CONST(rel->root_offset);
	__rbtree_replace(container, victim, newobj, rel);
}

#endif /* _LINUX_RBTREE_EXT_H */

Re: Generic rbtree search & insert cores

[Peter Zijlstra]

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.

Re: Generic rbtree search & insert cores

[Peter Zijlstra]

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)

Re: Generic rbtree search & insert cores

[Daniel Santos]

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 majordomo@vger.kernel.org
> 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.

Re: Generic rbtree search & insert cores

[Daniel Santos]

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)
>

Request feedback please: generic rbtree search, insert & remove (with leftmost, augmented, etc.)

[Daniel Santos]

[-- Attachment #1: Type: text/plain, Size: 2898 bytes --]

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



[-- Attachment #2: generic_rbtree.patch --]
[-- Type: text/x-patch, Size: 21147 bytes --]

diff --git a/include/linux/grbtree.h b/include/linux/grbtree.h
new file mode 100644
index 0000000..06f40cf
--- /dev/null
+++ b/include/linux/grbtree.h
@@ -0,0 +1,597 @@
+/*
+ * Generic Red Black Tree Extensions
+ *
+ * Copyright (C) 2012  Daniel Santos <daniel.santos@pobox.com>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software
+ * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301,
+ * USA.
+ */
+
+/**
+ * DOC: Generic Red Black Tree Extensions
+ *
+ * Generic Red Black Tree Extensions extends upon Andrea Arcangeli's original
+ * rbtree implementation adding the ability to generically define
+ * relationships between containers and their contents (see struct
+ * grb_relationship) and feeding that definition to generic function
+ * implementations. By using a compile-time constant instance of struct
+ * grb_relationship and a single instantiation of the static inline find &
+ * insert functions, gcc will generate code that is exactly as efficient as if
+ * you had implemented your own find & insert functions (as explained in the
+ * rbtree documentation) without the source bloat and added complexity.
+ * Further, by wrapping calls to the generic (__always_inline) functions in
+ * singular (non-inline) functions, type-safety can be achieved while
+ * preventing the bloat of inline expansion.
+ *
+ * The struct grb_relationship object should be thought of as a database's DDL
+ * (Data Definition Language) that defines the relationship between two
+ * tables: primary & foreign keys, unique constraints, sort ordering, tuning
+ * hints, etc. (although in practice, some of those are specified when making
+ * SQL queries).  It also specifies extended features you're using, like
+ * rather or not your container caches a pointer to the leftmost node in the
+ * tree -- enabling them in the generic function implementations or ensuring
+ * that they are compiled-out if you are not.
+ *
+ * It is important to understand that while grbtree extends upon rbtree's
+ * functionality, it uses a different interface paradigm: where rbtree's
+ * interface deals with the types struct rb_root and rb_node, grbtree is
+ * concerned with your containers and their objects and is designed to
+ * relegate the overhead for such genericity to the compiler.  So rather than
+ * passing a pointer to the struct rb_node or rb_root member of your
+ * container or object, you will simply pass a pointer to your container or
+ * object its self, likewise for return values.
+ *
+ * Because C does not (yet) support templates, this all means that the generic
+ * function accept and return void *pointers, killing type safety.  To
+ * restore type safety, its reccomeded you either wrap all calls to generic
+ * functions in your own type-specific function (inline or not) or use the
+ * unholy (but sufficient) GRB_DEFINE_INTERFACE() macro to have this done for
+ * you.
+ *
+ * Egg Sample:
+ *
+ * struct house {
+ *     struct rb_root mice;
+ * };
+ *
+ * struct mouse {
+ *     struct rb_node node;
+ *     const char*    name;
+ * };
+ *
+ * static __always_inline long name_cmp(const char **a, const char **b) {
+ *     return strcmp(*a, *b);
+ * }
+ *
+ * static const struct grb_relationship rel_house_to_mouse =
+ * GRB_RELATIONHIP(struct house, mice, / * noleft * /, / * noright * /,
+ *                 struct mouse, node, name, name_cmp,
+ *                 1, 0, 1, 0);
+ *
+ * struct mouse *find_mouse(struct house *house, const char *name) {
+ *     return rb_find(house, name, &rel_house_to_mouse);
+ * }
+ *
+ * struct mouse *put_mouse_in_house(struct house *house, struct mouse *mouse) {
+ *     return rb_insert(house, mouse, &rel_house_to_mouse);
+ * }
+ *
+ *
+ */
+#ifndef _LINUX_GRBTREE_H
+#define _LINUX_GRBTREE_H
+
+#include <linux/rbtree.h>
+
+typedef long (*rb_compare_f)(const void *a, const void *b);
+
+/* will submit this for include/linux/bug.h after I verify working gcc
+ * versions better and fully document caveats
+ */
+/**
+ * BUILD_BUG_ON_NON_CONST_STRUCT - break compile if a struct member is not a
+ *                                 compile-time constant
+ * @exp: struct member to test for compile-time constness
+ *
+ * If you have some code that depends upon struct instance being a compile-
+ * time constant (or more specifically one or more of its members), then you
+ * can use this macro to trigger a BUILD_BUG if it is not.  Note that one
+ * member of a struct instrance can be determined a compile-time constant by
+ * gcc and not another.
+ *
+ * Caveats: TODO
+ */
+#if defined(__OPTIMIZE__) && (__GNUC__ > 4 || __GNUC__ == 4 && __GNUC_MINOR__ >= 1)
+#define BUILD_BUG_ON_NON_CONST_STRUCT(exp) \
+	BUILD_BUG_ON(!__builtin_constant_p(exp))
+#else
+#define BUILD_BUG_ON_NON_CONST_STRUCT(exp)
+#endif
+
+
+#define __JUNK junk,
+#define _iff_empty(test_or_junk, t, f) __iff_empty(test_or_junk, t, f)
+#define __iff_empty(__ignored1, __ignored2, result, ...) result
+
+/**
+ * IFF_EMPTY() - Expands to the second argument when the first is empty, the
+ *               third if non-empty.
+ * test:         An argument to test for emptiness.
+ * on_true:      A value to expand to if test is empty.
+ * on_false:     A value to expand to if test is non-empty.
+ *
+ * Examples:
+ * IFF_EMPTY(a, b, c) = c
+ * IFF_EMPTY( , b, c) = b
+ * IFF_EMPTY( ,  , c) = (nothing)
+ */
+#define IFF_EMPTY(test, t, f) _iff_empty(__JUNK##test, t, f)
+
+/**
+ * IS_EMPTY() - test if a pre-processor argument is empty.
+ * arg:         An argument (empty or non-empty)
+ *
+ * If empty, expands to 1, 0 otherwise.
+ */
+#define IS_EMPTY(arg)	IFF_EMPTY(arg, 1, 0)
+
+/**
+ * OPT_OFFSETOF() - return the offsetof for the supplied expression, or zero
+ *                  if m is an empty argument.
+ * type:            struct/union type
+ * m:               (optional) struct member name
+ *
+ * Since any offsetof can return zero if the specified member is the first in
+ * the struct/union, you should also check if the argument is empty separately
+ * with IS_EMPTY(m).
+ */
+#define OPT_OFFSETOF(type, m) ((size_t) &((*((type *)0)) IFF_EMPTY(m,,.m)))
+
+
+/**
+ * struct grb_relationship - Defines relationship between a container and
+ *                      the objects it contains.
+ * @root_offset:        Offset of container's struct rb_root member.
+ * @has_left:           Non-zero if the container has a leftmost member, zero
+ *                      otherwise.
+ * @has_right:          Non-zero if the container has a rightmost member, zero
+ *                      otherwise.
+ * @left_offset:        (Used only if has_left.) Offset of the container's
+ *                      struct rb_node *leftmost member for storing a pointer
+ *                      to the leftmost node in the tree, which is kept
+ *                      updated as inserts and deletions are made.
+ * @right_offset:       Same as left_offset, except for right side of tree.
+ * @node_offset:        Offset of object's struct rb_node member.
+ * @key_offset:         Offset of object's key member.
+ * @compare:            Compare function for object keys -- should be an
+ *                      inline function in the same translation unit for
+ *                      proper optimization, although this is the only field
+ *                      that isn't required to be a compile-time constant.
+ *                      The compare function should accept pointers to the key
+ *                      type and return long.
+ * @unique:             Zero if duplicate keys are allowed, non-zero otherwise.
+ * @tune_many_dupes:    (Used only if !unique.) Tune searches & inserts when
+ *                      not using unique keys and many duplilcates are likely.
+ * @ins_replace:        (Used only if unique.) Rather or not the __grb_insert
+ *                      function should replace existing objects.
+ * @is_augmented:       Rather or this is an augmented rbtree (and the
+ *                      augmented is non-null)
+ * @augmented:          Not yet implemented (pointer to rb_augmented_f function)
+ *
+ * Instances of struct grb_relationship should be compile-time constants (or
+ * rather, the value of its members).
+ *
+ * Note: If your container stores the leftmost or rightmost, you must use the
+ * generic __rb_remove to keep them current.
+ */
+struct grb_relationship {
+	long root_offset;
+	int has_left;
+	int has_right;
+	long left_offset;
+	long right_offset;
+	long node_offset;
+	long key_offset;
+	rb_compare_f compare;
+	int unique;
+	int tune_many_dupes;
+	int ins_replace;
+	int is_augmented;
+	rb_augment_f augmented;
+};
+
+static __always_inline
+struct rb_root *__grb_to_root(const void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->root_offset);
+	return (struct rb_root *)((char *)ptr + rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **__grb_to_left(void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON(!rel->has_left);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->left_offset);
+	return (struct rb_node **)((char *)ptr + rel->left_offset);
+}
+
+static __always_inline
+struct rb_node **__grb_to_right(void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON(!rel->has_right);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->right_offset);
+	return (struct rb_node **)((char *)ptr + rel->right_offset);
+}
+
+static __always_inline
+struct rb_node *__grb_to_node(const void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset);
+	return (struct rb_node *)((char *)ptr + rel->node_offset);
+}
+
+static __always_inline
+const void *__grb_to_key(const void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->key_offset);
+	return (const void *)((const char *)ptr + rel->key_offset);
+}
+
+static __always_inline
+const void *__grb_node_to_key(const void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->key_offset);
+	return (const void *)((const char *)ptr - rel->node_offset + rel->key_offset);
+}
+
+static __always_inline
+char *__grb_node_to_obj(const void *ptr, const struct grb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->node_offset);
+	return ((char *)ptr - rel->node_offset);
+}
+
+/**
+ * grb_find_down_from - search a tree (normally) starting from the specified node
+ */
+static __always_inline
+void *grb_find_down_from(const struct rb_node *node,
+			 const void *key,
+			 const struct grb_relationship *rel)
+{
+	while (node) {
+		int diff = rel->compare(__grb_node_to_key(node, rel), key);
+
+		if (diff > 0)
+			node = node->rb_right;
+		else if (diff < 0)
+			node = node->rb_left;
+		else
+			return __grb_node_to_obj(node, rel);
+	}
+
+	return 0;
+}
+
+/**
+ * grb_find_up_from - search a tree climbing upwards, starting at the 'from'
+ *                    object and then descending (if needed) to find a
+ *                    matching object or no match.
+ */
+static __always_inline
+void *grb_find_up_from(const void *from,
+		       const void *key,
+		       const struct grb_relationship *rel)
+{
+	const struct rb_node *node = __grb_to_node(from, rel);
+	long diff = rel->compare(__grb_node_to_key(node, rel), key);
+	int go_left = diff < 0;
+
+	if (!diff)
+		return (void *)from;
+
+	while ((node = rb_parent(node))) {
+		diff = rel->compare(__grb_node_to_key(node, rel), key);
+
+		if (!diff)
+			return __grb_node_to_obj(node, rel);
+		else if (go_left ? diff > 0 : diff < 0)
+			return grb_find_down_from(node, key, rel);
+	}
+
+	return 0;
+}
+
+/**
+ * grb_find() - Searches a red black tree.
+ * @container:  Container to search.
+ * @key:        Pointer to the key you want to find.
+ * @rel:        Pointer to the compile-time constant relationship definition.
+ *
+ * On success, returns a pointer to the object (not the struct rb_node), NULL
+ * otherwise. If rel is not a compile-time constant, a link-time error will
+ * be generated.
+ *
+ * If your code calls this function from more than one place, it is highly
+ * recommended that you wrap this function in a non-inline function to avoid
+ * object code bloat. You have been advised!  Even if you are calling it from
+ * one place, wrapping it in a type-specific function (inline or otherwise)
+ * improves type-safety.
+ *
+ *
+ */
+static __always_inline
+void *grb_find(const void *container,
+	       const void *key,
+	       const struct grb_relationship *rel)
+{
+	return grb_find_down_from(__grb_to_root(container, rel)->rb_node, key,
+				  rel);
+}
+
+/**
+ * grb_insert() - Inserts an object into a container.
+ * @container:  Pointer to the container.
+ * @obj:        Pointer to the new object to insert.
+ * @rel:        Pointer to the compile-time constant relationship definition.
+ *
+ * If an object with the same key already exists and rel->ins_replace is non-zero,
+ * then it is replaced with obj; if rel->ins_replace is zero, then no change is made.
+ * In either case, a pointer to the existing object is returned. Note that
+ * return values are pointers to the objects themselves, not to the struct
+ * rb_node.
+ *
+ * If no object with the same key exists, then obj is inserted and NULL is
+ * returned.
+ *
+ * See rb_find for example.
+ */
+static __always_inline
+void *grb_insert(void *container,
+		 void *obj,
+		 const struct grb_relationship *rel)
+{
+	struct rb_root *root   = __grb_to_root(container, rel);
+	struct rb_node **p     = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct rb_node *node   = __grb_to_node(obj, rel);
+	void *ret              = NULL;
+	const void *key        = __grb_to_key(obj, rel);
+	int rightmost          = 1;
+	int leftmost           = 1;
+
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_left);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_right);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->unique);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->tune_many_dupes);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->ins_replace);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->is_augmented);
+
+	while (*p) {
+		int diff = rel->compare(__grb_node_to_key(*p, rel), key);
+		parent   = *p;
+
+		if (diff > 0) {
+			p = &(*p)->rb_right;
+			if (rel->has_left)
+				leftmost = 0;
+		/* if keys are not unique, we can skip additional tests,
+		 * although it will be slower if there are often duplicate
+		 * keys, so rel->tune_many_dupes will dictate how we
+		 * behave.
+		 */
+		} else if ((!rel->unique && !rel->tune_many_dupes) || diff < 0) {
+			p = &(*p)->rb_left;
+			if (rel->has_right)
+				rightmost = 0;
+		} else
+			break;
+	}
+
+	if (rel->has_left && leftmost)
+		*__grb_to_left(container, rel) = node;
+	if (rel->has_right && rightmost)
+		*__grb_to_right(container, rel) = node;
+
+	if (rel->unique && *p) {
+		ret = __grb_node_to_obj(*p, rel);
+		if (rel->ins_replace)
+			rb_replace_node(*p, node, root);
+	} else {
+		rb_link_node(node, parent, p);
+		rb_insert_color(node, root);
+	}
+
+	if (rel->is_augmented)
+		rb_augment_insert(node, rel->augmented, NULL);
+
+	return ret;
+}
+
+static __always_inline
+void grb_remove(void *container,
+		void *obj,
+		const struct grb_relationship *rel)
+{
+	struct rb_root *root   = __grb_to_root(container, rel);
+	struct rb_node *node   = __grb_to_node(obj, rel);
+	struct rb_node *deepest;
+
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_right);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->has_left);
+	BUILD_BUG_ON_NON_CONST_STRUCT(rel->is_augmented);
+
+	if (rel->is_augmented)
+		deepest = rb_augment_erase_begin(node);
+
+	if (rel->has_left) {
+		struct rb_node **left = __grb_to_left(container, rel);
+
+		if (*left == node)
+			*left = rb_next(node);
+	}
+
+	if (rel->has_right) {
+		struct rb_node **right = __grb_to_right(container, rel);
+
+		if (*right == node)
+			*right = rb_prev(node);
+	}
+
+	rb_erase(node, root);
+
+	if (rel->is_augmented)
+		rb_augment_erase_end(deepest, rel->augmented, NULL);
+}
+
+/**
+ * GRB_RELATIONHIP - Define the relationship bewteen a container with a
+ *                   struct rb_root member, and the objects it contains.
+ * cont_type:       .
+ * root:            .
+ * left:            .
+ * right:           .
+ * obj_type:        .
+ * node:            .
+ * key:             .
+ * compare:         .
+ * unique:          .
+ * tune_many_dupes: .
+ * ins_replace:     .
+ * augmented:       .
+ */
+#define GRB_RELATIONHIP(						\
+		cont_type, root, left, right,				\
+		obj_type, node, key, _compare,				\
+		_unique, _tune_many_dupes, _ins_replace, _augmented) {	\
+	.root_offset     = offsetof(cont_type, root),			\
+	.has_left        = !IS_EMPTY(left),				\
+	.has_right       = !IS_EMPTY(right),				\
+	.left_offset     = OPT_OFFSETOF(cont_type, left),		\
+	.right_offset    = OPT_OFFSETOF(cont_type, right),		\
+	.node_offset     = offsetof(obj_type, node),			\
+	.key_offset      = offsetof(obj_type, key),			\
+	.compare         = (rb_compare_f)_compare,			\
+	.unique          = _unique,					\
+	.tune_many_dupes = _tune_many_dupes,				\
+	.ins_replace     = _ins_replace,				\
+	.is_augmented    = !IS_EMPTY(left),				\
+	.augmented       = IFF_EMPTY(_augmented, 0, _augmented),	\
+}
+
+#define __GRB_DEFINE_INTERFACE(						\
+	rel_var, insert_func, find_func, remove_func, 			\
+	cont_type, root, left, right,					\
+	obj_type, node, key, compare,					\
+	unique, tune_many_dupes, ins_replace, augmented,		\
+	insert_func_mod, find_func_mod)					\
+static const struct grb_relationship rel_var = GRB_RELATIONHIP(		\
+	cont_type, root, left, right,					\
+	obj_type, node, key, compare,					\
+	unique, tune_many_dupes, ins_replace, augmented);		\
+									\
+insert_func_mod								\
+obj_type *insert_func(cont_type *container, obj_type *obj) {		\
+	return (obj_type *)grb_insert(container, obj, &rel_var);	\
+}									\
+									\
+find_func_mod								\
+obj_type *find_func(const cont_type *container,				\
+		    const typeof(((obj_type *)0)->key) *key) {		\
+	return (obj_type *)grb_find(container, key, &rel_var);		\
+}									\
+									\
+static __always_inline							\
+void remove_func(cont_type *container, obj_type *obj) {			\
+	grb_remove(container, obj, &rel_var);				\
+}									\
+
+/** GRB_DEFINE_INTERFACE - Defines a struct grb_relationship object and
+ *                         type-safe inteface functions.
+ * prefix:          .
+ * cont_type:       .
+ * root:            .
+ * left:            .
+ * right:           .
+ * obj_type:        .
+ * node:            .
+ * key:             .
+ * compare:         .
+ * unique:          .
+ * tune_many_dupes: .
+ * ins_replace:     .
+ * augmented:       .
+ * insert_func_mod: .
+ * find_func_mod:   .
+ */
+#define GRB_DEFINE_INTERFACE(prefix, ...)\
+__GRB_DEFINE_INTERFACE(			\
+	prefix ## rel,			\
+	prefix ## insert,		\
+	prefix ## find,			\
+	prefix ## remove,		\
+	__VA_ARGS__)
+
+
+/** GRB_DEFINE_INTERFACE_OBJ  - A cute way to contain the type-safe interface
+ *                              in a single object, but killing inline-ability.
+ * interface_name:  name of your interface object
+ * cont_type:       .
+ * root:            .
+ * left:            .
+ * right:           .
+ * obj_type:        .
+ * node:            .
+ * key:             .
+ * compare:         .
+ * unique:          .
+ * tune_many_dupes: .
+ * ins_replace:     .
+ * augmented:       .
+ */
+#define GRB_DEFINE_INTERFACE_OBJ(					\
+	interface_name,							\
+	cont_type, root, left, right,					\
+	obj_type, node, key, compare,					\
+	unique, tune_many_dupes, ins_replace, augmented)		\
+static const struct {							\
+	struct grb_relationship rel;					\
+	obj_type *(*insert)(cont_type *c, obj_type *o,			\
+			    const struct grb_relationship *rel);	\
+	obj_type   *(*find)(const cont_type *c,				\
+			    const typeof(((obj_type *)0)->key) *key,	\
+			    const struct grb_relationship *rel);	\
+	void      (*remove)(cont_type *c, obj_type *o,			\
+			    const struct grb_relationship *rel);	\
+} interface_name = {							\
+.rel = GRB_RELATIONHIP(							\
+	cont_type, root, left, right,					\
+	obj_type, node, key, compare,					\
+	unique, tune_many_dupes, ins_replace, augmented),		\
+									\
+.insert  = (obj_type *(*)(cont_type *,					\
+			  obj_type *,					\
+			  const struct grb_relationship *))grb_insert,	\
+.find    = (obj_type *(*)(const cont_type *,				\
+			  const typeof(((obj_type *)0)->key) *,		\
+			  const struct grb_relationship *))grb_find,	\
+.remove  = (void      (*)(cont_type *, obj_type *,			\
+			  const struct grb_relationship *))grb_remove,	\
+};
+
+
+
+#endif	/* _LINUX_GRBTREE_H */