[PATCH v2 1/3] [RFC] Generic Red-Black Trees

[PATCH v2 1/3] [RFC] Generic Red-Black Trees

[Daniel Santos]

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

Well, I'm running on 3.4 patched with this generic rb tree
implementation in the fair scheduler (although these are slightly
cleaned up, so I still need to boot this version to make sure there's no
last minute snafus).  So I finally settled on a mechanism for the
type-safety, even though it's a big macro (not my first choice), it's
the mechanism that works on all versions of gcc that still matter.

This is still preliminary.  I have a user-space test program (that just
compiles the rbtree.h in userspace) and a test module that I want to
refine to do profiling & stress tests so that performance can be easily
checked on various architectures & compilers.  So here's the outstanding
list:

* insert_near not finished (low priority)
* find_near not yet tested
* augmented not yet tested



[-- Attachment #2: 0006-linux-bug.h-Add-BUILD_BUG_ON_NON_CONST-macros.patch --]
[-- Type: text/x-patch, Size: 3096 bytes --]

>From 4a82526de53ab66c5ec5c36cfd93d1efed431cf0 Mon Sep 17 00:00:00 2001
From: Daniel Santos <daniel.santos@pobox.com>
Date: Fri, 4 May 2012 00:09:10 -0500
Subject: linux/bug.h: Add BUILD_BUG_ON_NON_CONST macros

---
 include/linux/bug.h |   62 +++++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 62 insertions(+), 0 deletions(-)

diff --git a/include/linux/bug.h b/include/linux/bug.h
index 72961c3..9352ff3 100644
--- a/include/linux/bug.h
+++ b/include/linux/bug.h
@@ -56,6 +56,68 @@ extern int __build_bug_on_failed;
 	} while(0)
 #endif
 
+
+/**
+ * BUILD_BUG_ON_NON_CONST - break compile if expression cannot be determined
+ *                          to be a compile-time constant.
+ * @exp: value to test for compile-time constness
+ *
+ * __builtin_constant_p() is a work in progress and is broken in various ways
+ * on various versions of gcc and optimization levels. It can fail, even when
+ * gcc otherwise determines that the expression is compile-time constant when
+ * performing actual optimizations and thus, compile out the value anyway. Do
+ * not use this macro for struct members or dereferenced pointers and arrays,
+ * as these are broken in many versions of gcc -- use BUILD_BUG_ON_NON_CONST2
+ * instead.
+ *
+ * As long as you are passing a variable delcared const (and not modified),
+ * this macro should never fail.
+ */
+#ifdef __OPTIMIZE__
+#define BUILD_BUG_ON_NON_CONST(exp) \
+	BUILD_BUG_ON(!__builtin_constant_p(exp))
+#else
+#define BUILD_BUG_ON_NON_CONST(exp)
+#endif
+
+
+/**
+ * BUILD_BUG_ON_NON_CONST2 - break compile if expression cannot be determined
+ *                           to be a compile-time constant.
+ * @exp: value to test for compile-time constness
+ *
+ * Use this macro instead of BUILD_BUG_ON_NON_CONST when testing struct
+ * members or dereferenced arrays and pointers.
+ *
+ * Gory Details:
+ *
+ * Normal primitive variables
+ * - global non-static non-const values are never compile-time constants (but
+ *   you should already know that)
+ * - all const values (global/local, non/static) should never fail this test
+ *   (3.4+)
+ * - global non-static const broken until 4.2 (-O1 broken until 4.4)
+ * - local static non-const broken until 4.2 (-O1 broken until 4.3)
+ * - local non-static non-const broken until 4.0
+ *
+ * Dereferencing pointers & arrays
+ * - all static const derefs broken until 4.4 (except arrays at -O2 or better,
+ *   which are fixed in 4.2)
+ * - global non-static const pointer derefs always fail (<=4.7)
+ * - local non-static const derefs broken until 4.3, except for array derefs
+ *   to a zero value, which works from 4.0+
+ * - local static non-const pointers always fail (<=4.7)
+ * - local static non-const arrays broken until 4.4
+ * - local non-static non-const arrays broken until 4.0 (unless zero deref,
+ *   works in 3.4+)
+ */
+#if __GNUC__ > 4 || __GNUC__ == 4 &&  __GNUC_MINOR__ >= 4
+#define BUILD_BUG_ON_NON_CONST2(exp) BUILD_BUG_ON_NON_CONST(exp)
+#else
+#define BUILD_BUG_ON_NON_CONST2(exp)
+#endif
+
+
 /**
  * BUILD_BUG - break compile if used.
  *
-- 
1.7.3.4

[PATCH v2 2/3] [RFC] Generic Red-Black Trees

[Daniel Santos]

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



[-- Attachment #2: 0007-Generic-search-insert-for-Red-Black-Trees.patch --]
[-- Type: text/x-patch, Size: 19958 bytes --]

>From 5d71e7b4bc2b43f40568e0493b65332218dce0ba Mon Sep 17 00:00:00 2001
From: Daniel Santos <daniel.santos@pobox.com>
Date: Thu, 31 May 2012 17:43:24 -0500
Subject: Generic search & insert for Red-Black Trees

---
 include/linux/rbtree.h |  623 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 files changed, 623 insertions(+), 0 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 033b507..1133682 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
 {
@@ -148,6 +150,7 @@ extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
 
 typedef void (*rb_augment_f)(struct rb_node *node, void *data);
+typedef long (*rb_compare_f)(const void *a, const void *b);
 
 extern void rb_augment_insert(struct rb_node *node,
 			      rb_augment_f func, void *data);
@@ -174,4 +177,624 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
 	*rb_link = node;
 }
 
+
+#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.
+ * @t:           A value to expand to if test is empty.
+ * @f:           A value to expand to if test is non-empty.
+ *
+ * Caveats:
+ * IFF_EMPTY isn't perfect.  The test parmater must either be empty or a valid
+ * pre-processor token as well as result in a valid token when pasted to the
+ * end of a word.
+ *
+ * Valid Examples:
+ * IFF_EMPTY(a, b, c) = c
+ * IFF_EMPTY( , b, c) = b
+ * IFF_EMPTY( ,  , c) = (nothing)
+ *
+ * Invalid Examples:
+ * IFF_EMPTY(.,  b, c)
+ * IFF_EMPTY(+,  b, c)
+ */
+#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.  See IFF_EMPTY() for caveats &
+ * limitations.
+ */
+#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)))
+
+
+enum rb_flags {
+	RB_HAS_LEFTMOST	   = 0x00000001,
+	RB_HAS_RIGHTMOST   = 0x00000002,
+	RB_UNIQUE_KEYS	   = 0x00000004,
+	RB_INSERT_REPLACES = 0x00000008,
+	RB_ALL_FLAGS	   = RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
+			   | RB_UNIQUE_KEYS | RB_INSERT_REPLACES,
+};
+
+/**
+ * struct rb_relationship - Defines relationship between a container and
+ *                      the objects it contains.
+ * @root_offset:        Offset of container's struct rb_root member.
+ * @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.
+ * @flags:              TODO
+ *
+ * Instances of struct rb_relationship should be compile-time constants (or
+ * rather, the value of its members).
+ */
+struct rb_relationship {
+	long root_offset;
+	long left_offset;
+	long right_offset;
+	long node_offset;
+	long key_offset;
+	int flags;
+};
+
+static __always_inline
+struct rb_root *__rb_to_root(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	return (struct rb_root *)((char *)ptr + rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_left(void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON(!(rel->flags & RB_HAS_LEFTMOST));
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->left_offset);
+	return (struct rb_node **)((char *)ptr - rel->root_offset
+					       + rel->left_offset);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_right(void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON(!(rel->flags & RB_HAS_RIGHTMOST));
+	BUILD_BUG_ON_NON_CONST2(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->right_offset);
+	return (struct rb_node **)((char *)ptr - rel->root_offset
+					       + rel->right_offset);
+}
+
+static __always_inline
+const void *__rb_node_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+	return (const void *)((const char *)ptr - rel->node_offset
+						+ rel->key_offset);
+}
+
+static __always_inline
+char *__rb_node_to_obj(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	return (char *)ptr - rel->node_offset;
+}
+
+/* not used anymore */
+#if 0
+static __always_inline
+struct rb_node *__rb_to_node(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->node_offset);
+	return (struct rb_node *)((char *)ptr + rel->node_offset);
+}
+
+static __always_inline
+const void *__rb_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST2(rel->key_offset);
+	return (const void *)((const char *)ptr + rel->key_offset);
+}
+
+#endif
+
+/** __rb_find -
+ *
+ */
+static __always_inline
+struct rb_node *__rb_find(
+		struct rb_node *node,
+		const void *key,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare)
+{
+	while (node) {
+		long diff = compare(key, __rb_node_to_key(node, rel));
+
+		if (diff > 0)
+			node = node->rb_right;
+		else if (diff < 0)
+			node = node->rb_left;
+		else
+			return node;
+	}
+
+	return 0;
+}
+
+
+static __always_inline
+struct rb_node *rb_find(
+	struct rb_root *root,
+	const void *key,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare)
+{
+	return __rb_find(root->rb_node, key, rel, compare);
+}
+
+enum rb_find_subtree_match {
+	RB_MATCH_NONE		= 0,
+	RB_MATCH_IMMEDIATE	= 2,
+	RB_MATCH_LEFT		= -1,
+	RB_MATCH_RIGHT		= 1,
+};
+
+
+/**
+ * rb_find_subtree - Locate the subtree that contains the specified key (if it
+ * 		     exists) starting from a specific node traversing upwards.
+ *
+ */
+static __always_inline
+struct rb_node *__rb_find_subtree(
+		struct rb_node *from,
+		const void *key,
+		int *matched,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare)
+{
+	struct rb_node *prev = from;
+	struct rb_node *node = rb_parent(from);
+	long diff;
+
+	if (!node) {
+		*matched = RB_MATCH_NONE;
+		return prev;
+	}
+
+	diff = compare(key, __rb_node_to_key(node, rel));
+
+	if (diff > 0) {
+		while (1) {
+			prev = node;
+			node = rb_parent(prev);
+			if (!node)
+				break;
+
+			diff = compare(key, __rb_node_to_key(node, rel));
+			if (diff < 0)
+				break;
+			else if (!diff) {
+				*matched = RB_MATCH_LEFT;
+				return node;
+			}
+		}
+		*matched = RB_MATCH_NONE;
+		return prev->rb_left;
+	} else if (diff < 0) {
+		while (1) {
+			prev = node;
+			node = rb_parent(prev);
+			if (!node)
+				break;
+
+			diff = compare(key, __rb_node_to_key(node, rel));
+			if (diff > 0)
+				break;
+			else if (!diff) {
+				*matched = RB_MATCH_RIGHT;
+				return node;
+			}
+		}
+		*matched = RB_MATCH_NONE;
+		return prev->rb_right;
+	}
+
+	*matched = RB_MATCH_IMMEDIATE;
+	return node;
+}
+
+static __always_inline
+struct rb_node *rb_find_near(
+	struct rb_node *from,
+	const void *key,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare)
+{
+	int matched;
+	struct rb_node *subtree;
+
+	subtree = __rb_find_subtree(from, key, &matched, rel, compare);
+
+	if (matched) {
+		return subtree;
+	}
+
+	return __rb_find(subtree, key, rel, compare);
+}
+
+static __always_inline
+struct rb_node *__rb_insert_epilogue(
+	struct rb_root *root,
+	struct rb_node *parent,
+	struct rb_node *node,
+	struct rb_node *found,
+	struct rb_node **rb_link,
+	const struct rb_relationship *rel,
+	const rb_augment_f augmented) {
+
+	if ((rel->flags & RB_UNIQUE_KEYS) && found) {
+		/* if replacing, we will still need to call do augmented */
+		if (rel->flags & RB_INSERT_REPLACES)
+			rb_replace_node(found, node, root);
+		/* otherwise, we can bail */
+		else
+			goto exit;
+	} else {
+		rb_link_node(node, parent, rb_link);
+		rb_insert_color(node, root);
+	}
+
+	if (augmented)	/* TODO: check verify which versions of gcc compile this out */
+		rb_augment_insert(node, augmented, NULL);
+
+exit:
+	return found;
+}
+
+
+/**
+ * rb_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
+struct rb_node *rb_insert(
+	struct rb_root *root,
+	struct rb_node *node,
+	const struct rb_relationship *rel,
+	const rb_compare_f compare,
+	const rb_augment_f augmented)
+{
+	struct rb_node **p     = &root->rb_node;
+	struct rb_node *parent = NULL;
+	const void *key        = __rb_node_to_key(node, rel);
+	int leftmost           = 1;
+	int rightmost          = 1;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+	BUG_ON((rel->flags & RB_INSERT_REPLACES)
+		 && !(rel->flags & RB_UNIQUE_KEYS));
+
+	while (*p) {
+		long diff = compare(key, __rb_node_to_key(*p, rel));
+		parent    = *p;
+
+		if (diff > 0) {
+			p = &(*p)->rb_right;
+			if (rel->flags & RB_HAS_LEFTMOST)
+				leftmost = 0;
+		} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+			p = &(*p)->rb_left;
+			if (rel->flags & RB_HAS_RIGHTMOST)
+				rightmost = 0;
+		} else
+			break;
+	}
+
+	if ((rel->flags & RB_HAS_LEFTMOST) && leftmost) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+
+		if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *left == *p)
+			*left = node;
+	}
+	if ((rel->flags & RB_HAS_RIGHTMOST) && rightmost) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+
+		if (!(rel->flags & RB_INSERT_REPLACES) || !(*p) || *right == *p)
+			*right = node;
+	}
+
+	return __rb_insert_epilogue(root, parent, node, *p, p, rel, augmented);
+}
+
+static __always_inline
+struct rb_node *rb_insert_near(
+		struct rb_root *root,
+		struct rb_node *start,
+		struct rb_node *node,
+		const struct rb_relationship *rel,
+		const rb_compare_f compare,
+		const rb_augment_f augmented)
+{
+
+	return 0;
+/* TODO: not yet finished */
+#if 0
+	const void *key        = __rb_node_to_key(node, rel);
+	struct rb_node **p     = &start;
+	struct rb_node *parent = NULL;
+	struct rb_node *ret;
+	int matched;
+	long diff;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+	ret = __rb_find_subtree(start, key, &matched, rel, compare);
+
+	if (!matched) {
+		while (*p) {
+			diff   = compare(__rb_node_to_key(*p, rel), key);
+			parent = *p;
+
+			if (diff > 0) {
+				p = &(*p)->rb_right;
+			} else if (!(rel->flags & RB_UNIQUE_KEYS) || diff < 0) {
+				p = &(*p)->rb_left;
+			} else
+				break;
+		}
+		ret = *p;
+	} else {
+		/* FIXME: p will not be correctly set to point to the parent's
+		 * rb_left or rb_right member here when it's passed as
+		 * __rb_insert_epilogue()'s rb_link parameter.
+		 */
+		if (rel->flags & (RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST)) {
+			if ((rel->flags & RB_HAS_LEFTMOST)) {
+				struct rb_node **left = __rb_root_to_left(root, rel);
+				if (*left == ret) {
+					*left = node;
+				}
+			}
+
+			if ((rel->flags & RB_HAS_RIGHTMOST)) {
+				struct rb_node **right = __rb_root_to_right(root, rel);
+				if (*right == ret) {
+					*right = node;
+				}
+			}
+		}
+	}
+
+	if (rel->flags & RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST) {
+
+	}
+
+	if ((rel->flags & RB_HAS_LEFTMOST)) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+		if (!*left || (*left == parent && diff < 0)) {
+			*left = node;
+		}
+	}
+
+	if ((rel->flags & RB_HAS_RIGHTMOST)) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+		if ((*right == parent && diff > 0) || !*right) {
+			*right = node;
+		}
+	}
+
+	return __rb_insert_epilogue(root, parent, node, ret, p, rel, augmented);
+#endif
+}
+
+static __always_inline
+void rb_remove(
+	struct rb_root *root,
+	struct rb_node *node,
+	const struct rb_relationship *rel,
+	const rb_augment_f augmented)
+{
+	struct rb_node *deepest = NULL;
+
+	BUILD_BUG_ON_NON_CONST2(rel->flags);
+
+	if (augmented)
+		deepest = rb_augment_erase_begin(node);
+
+	if (rel->flags & RB_HAS_LEFTMOST) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+
+		if (*left == node)
+			*left = rb_next(node);
+	}
+
+	if (rel->flags & RB_HAS_RIGHTMOST) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+
+		if (*right == node)
+			*right = rb_prev(node);
+	}
+
+	rb_erase(node, root);
+
+	if (augmented)
+		rb_augment_erase_end(deepest, augmented, NULL);
+}
+
+
+/**
+ * RB_RELATIONHIP - Define the relationship bewteen a container with a
+ *                  struct rb_root member, and the objects it contains.
+ * @cont_type: container type
+ * @root:      container's struct rb_root member name
+ * @left:      (optional) if the container needs a pointer to the tree's
+ *             leftmost (smallest) object, then specify the container's struct
+ *             rb_node *leftmost member.  Otherwise, leave this parameter
+ *             empty.
+ * @right:     (optional) same as left, but for the rightmost (largest)
+ * @obj_type:  the type of object stored in container
+ * @node:      the struct rb_node memeber of the object
+ * @key:       the key member of the object
+ * @flags      see rb_flags.  Note: you do not have to specify RB_HAS_LEFTMOST
+ *             or RB_HAS_RIGHTMOST as these will be added automatically if the
+ *             left or right parameter (respectively) is non-empty
+ */
+#define RB_RELATIONHIP(							\
+		cont_type, root, left, right,				\
+		obj_type, node, key,					\
+		_flags) {						\
+	.root_offset     = offsetof(cont_type, root),			\
+	.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),			\
+	.flags           = (_flags)					\
+			 | IFF_EMPTY(left , 0, RB_HAS_LEFTMOST)		\
+			 | IFF_EMPTY(right, 0, RB_HAS_RIGHTMOST),	\
+}
+
+/**
+ * RB_DEFINE_INTERFACE - Defines a complete interface for a relationship
+ *                       between container and object including a struct
+ *                       rb_relationship and an interface of type-safe wrapper
+ *                       functions.
+ * @prefix:    name for the relationship (see explanation below)
+ * @cont_type: container type
+ * @root:      container's struct rb_root member name
+ * @left:      (optional) if the container needs a pointer to the tree's
+ *             leftmost (smallest) object, then specify the container's struct
+ *             rb_node *leftmost member.  Otherwise, leave this parameter
+ *             empty.
+ * @right:     (optional) same as left, but for the rightmost (largest)
+ * @obj_type:  the type of object stored in container
+ * @node:      the struct rb_node memeber of the object
+ * @key:       the key member of the object
+ * @flags      see rb_flags.  Note: you do not have to specify RB_HAS_LEFTMOST
+ *             or RB_HAS_RIGHTMOST as these will be added automatically if the
+ *             left or right parameter (respectively) is non-empty
+ * @compare:   pointer to key rb_compare_f function to compare keys.  Function
+ *             will be cast to and called as type long (*)(const void *a, const
+ *             void *b), hence type-safety is lost (FIXME: can this be improved
+ *             at all?).
+ * @augmented: pointer to the rb_augment_f or zero if tree is not augmented.
+ *
+ * This macro can be delcared in the global scope of either a source or header
+ * file and will generate a static const struct rb_relationship variable named
+ * prefix##_rel as well as similarly named (i.e., prefix##_##func_name)
+ * type-safe wrapper functions for find, find_near, insert, insert_near and
+ * remove.  If these function names are not sufficient, you can use the
+ * __RB_DEFINE_INTERFACE macro to specify them explicitly.
+ *
+ * The compare function will be passed pointers to the key members of two
+ * objects.  If your compare function needs access to other members of your
+ * struct (e.g., compound keys, etc.) , you can use the rb_entry macro to
+ * access other members.  However, if you use this mechanism, your find
+ * function must always pass it's key parameter as a pointer to the key member
+ * of an object of type obj_type, since the compare function is used for both
+ * inserts and lookups.
+ */
+#define RB_DEFINE_INTERFACE(prefix, ...)\
+__RB_DEFINE_INTERFACE(			\
+	prefix ## _rel,			\
+	prefix ## _insert,		\
+	prefix ## _insert_near,		\
+	prefix ## _find,		\
+	prefix ## _find_near,		\
+	prefix ## _remove,		\
+	__VA_ARGS__)
+
+
+#define __RB_DEFINE_INTERFACE(						\
+	rel_var, insert, insert_near, find, find_near, remove,		\
+	cont_type, root, left, right,					\
+	obj_type, node, key,						\
+	flags, compare, augmented)					\
+static const struct rb_relationship rel_var = RB_RELATIONHIP(		\
+	cont_type, root, left, right,					\
+	obj_type, node, key,						\
+	flags);								\
+									\
+static __always_inline							\
+obj_type *insert(cont_type *cont, obj_type *obj)			\
+{									\
+	struct rb_node *ret = rb_insert(				\
+			&cont->root, &obj->node, &rel_var,		\
+			(const rb_compare_f)compare, augmented);	\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *insert_near(cont_type *cont, obj_type *near, obj_type *obj)	\
+{									\
+	struct rb_node *ret = rb_insert_near(				\
+			&cont->root, &near->node, &obj->node, &rel_var,	\
+			(const rb_compare_f)compare, augmented);	\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *find(cont_type *cont,						\
+	       const typeof(((obj_type *)0)->key) *_key)		\
+{									\
+	struct rb_node *ret = rb_find(					\
+			&cont->root, _key, &rel_var,			\
+			(const rb_compare_f)compare);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *find_near(obj_type *near,					\
+		    const typeof(((obj_type *)0)->key) *_key)		\
+{									\
+	struct rb_node *ret = rb_find_near(				\
+			&near->node, _key, &rel_var,			\
+			(const rb_compare_f)compare);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+void remove(cont_type *cont, obj_type *obj)				\
+{									\
+	rb_remove(&cont->root, &obj->node, &rel_var, augmented);	\
+}									\
+
 #endif	/* _LINUX_RBTREE_H */
-- 
1.7.3.4

[PATCH v2 3/3] [RFC] Generic Red-Black Trees

[Daniel Santos]

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

I've put a few performance notes in comments.  Specifically, I'm curious
if an inline function that expands to 128+ bytes like this should
possibly be wrapped in an __attribute__((flatten))
__attribute__((noinline)) function to force full expansion in one place
and then prevent it from getting inlined elsewhere (to keep the
generated code size down).

[-- Attachment #2: 0008-Use-generic-rbtree-impl-in-fair-scheduler.patch --]
[-- Type: text/x-patch, Size: 3359 bytes --]

>From 599576c4f48c97fe5e6f0cfa4e31d9dbb22ea043 Mon Sep 17 00:00:00 2001
From: Daniel Santos <daniel.santos@pobox.com>
Date: Thu, 31 May 2012 17:49:53 -0500
Subject: Use generic rbtree impl in fair scheduler

---
 kernel/sched/fair.c |   76 +++++++++++++++++++++++---------------------------
 1 files changed, 35 insertions(+), 41 deletions(-)

diff --git a/kernel/sched/fair.c b/kernel/sched/fair.c
index e955364..64e8c29 100644
--- a/kernel/sched/fair.c
+++ b/kernel/sched/fair.c
@@ -447,6 +447,19 @@ static inline int entity_before(struct sched_entity *a,
 	return (s64)(a->vruntime - b->vruntime) < 0;
 }
 
+static inline long compare_vruntime(u64 *a, u64 *b)
+{
+#if __BITS_PER_LONG >= 64
+	return (long)((s64)*a - (s64)*b);
+#else
+/* this is hacky -- we wont use this for rbtree lookups, only inserts, and
+ * since our relationship is defined as non-unique, we only need to return
+ * positive if a > b and any other value means less than.
+ */
+	return (long)(*a > *b);
+#endif
+}
+
 static void update_min_vruntime(struct cfs_rq *cfs_rq)
 {
 	u64 vruntime = cfs_rq->min_vruntime;
@@ -472,57 +485,38 @@ static void update_min_vruntime(struct cfs_rq *cfs_rq)
 #endif
 }
 
+RB_DEFINE_INTERFACE(
+	fair_tree,
+	struct cfs_rq, tasks_timeline, rb_leftmost, /* no rightmost */,
+	struct sched_entity, run_node, vruntime,
+	0, compare_vruntime, 0)
+
+#ifndef __flatten
+#define __flatten __attribute__((flatten))
+#endif
+
 /*
- * Enqueue an entity into the rb-tree:
+ * Enqueue an entity into the rb-tree:(these are wrappers so that inline
+ * expansion happens in only one place)
+ *
+ * NOTE: When compiling under gcc 4.5 and 4.6 (amd64), it decided to inline
+ * these anyway.  I would be interested in profiling this as-is and declaring
+ * each function __flatten noinline (forcing all in-lining in the function, but
+ * preventing them from being inlined themselves).  Also, it may not do this on
+ * other archs where the (not sure, gcc docs don't seem to say anything about
+ * arch influence).
  */
 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);
+	fair_tree_insert(cfs_rq, se);
 }
 
 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);
+	fair_tree_remove(cfs_rq, se);
 }
 
+
 struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
 {
 	struct rb_node *left = cfs_rq->rb_leftmost;
-- 
1.7.3.4

Re: [PATCH v2 1/3] [RFC] Generic Red-Black Trees

[Daniel Santos]

Oh yeah, so the patch set I sent boots & runs fine.  I've also noticed
that I have a few outdated doc-comments and a mistake in the
doc-comments for
the BUILD_BUG_ON_NON_CONST2() macro, under the "Normal Variables"
section, the text "global non-static const broken until 4.2 (-O1 broken
until 4.4)" contradicts the earlier statement that all const values
should never fail. This only applies to floats (but not doubles), which
we don't have to worry about in the kernel anyway. (incidentally, their
behavior under __builtin_constant_p() varies quite a bit until gcc 4.4,
where it's fine)

It was important for me to figure out what was and wasn't working with
__builtin_constant_p(), and in what versions of gcc because this
implementation relies heavily on the compiler optimizing out code based
upon values pass to it via a const struct pointer.  Also, I was looking
for other possibilities, as I continued discovered broken (improperly
optimized) scenarios.

Daniel

Re: [PATCH v2 1/3] [RFC] Generic Red-Black Trees (performance notes)

[Daniel Santos]

I've done a bit more analysis of the generated code of
kernel/sched/fair.c (patched) under three versions of gcc.

gcc-4.5.3
* 48 bytes larger
* one instance of a (const_flag & ENUM_VALUE) fails to compile out
* compare function not inlined

gcc-4.6.2
* same size
* ANDed constants compiled out
* compare function inlined

gcc-4.7.0:
* 64 bytes smaller - __enqueue_entity() reduced by 16 bytes (2 byte
smaller and saved some padding, so essentially the same), I'm not sure
where the other 48 bytes came from, I'm guessing just alignment changes
from using different registers (smaller opcodes).

So in summary, the results on 4.5 are worse, but not "horrible".  The
problems are fixed in 4.6 and later.

There's still lots of other scenarios to test.

Daniel