[PATCH v6 0/10] Generic Red-Black Trees

[PATCH v6 0/10] Generic Red-Black Trees

[Daniel Santos]

This patch set depends upon the following:
* Cleanup & new features for compiler*.h and bug.h
* kernel-doc bug fixes (for generating docs)

Summary
=======
This patch set improves on Andrea Arcangeli's original Red-Black Tree
implementation by adding generic search and insert functions with
complete support for:

o leftmost - keeps a pointer to the leftmost (lowest value) node cached
  in your container struct
o rightmost - ditto for rightmost (greatest value)
o count - optionally update an count variable when you perform inserts
  or deletes
o unique or non-unique keys
o find and insert "near" functions - when you already have a node that
  is likely near another one you want to search for
o type-safe wrapper interface available via pre-processor macro

Outstanding Issues
==================
General
-------
o Need something in Documents to explain generic rbtrees.
o Due to a bug in gcc's optimizer, extra instructions are generated in various
  places.  Pavel Pisa has provided me a possible work-around that should be
  examined more closely to see if it can be working in (Discussed in
  Performance section).
o Doc-comments are missing or out of date in some places for the new
  ins_compare field of struct rb_relationship (including at least one code
  example).

Selftests
---------
o In-kernel test module not completed.
o Userspace selftest's Makefile should run modules_prepare in KERNELDIR.
o Userspace selftest's Makefile also fairly sucks (doesn't properly check
  changes, etc -- I'm not a make guru)
o Validation in self-tests doesn't yet cover tests for
  - insert_near
  - find_{first,last,next,prev}
o Selftest scripts need better portability (maybe solved? we'll see)
o It would be nice to have some fault-injection in test code to verify that
  CONFIG_DEBUG_GRBTREE and CONFIG_DEBUG_GRBTREE_VALIDATE (and it's
  RB_VERIFY_INTEGRITY counterpart flag) catch the errors they are supposed to.

Undecided (Opinions Requested!)
-------------------------------
o With the exception of the rb_node & rb_root structs, "Layer 2" of the code
  (see below) completely abstracts away the underlying red-black tree
  mechanism.  The structs rb_node and rb_root can also be abstracted away via
  a typeset or some other mechanism. Thus, should the "Layer 2" code be
  separated from "Layer 1" and renamed "Generic Tree (gtree)" or some such,
  paving the way for an alternate tree implementation in the future?
o Do we need RB_INSERT_DUPE_RIGHT? (see the last patch)


Theory of Operation
===================
Historically, genericity in C meant function pointers, the overhead of a
function call and the inability of the compiler to optimize code across
the function call boundary.  GCC has been getting better and better at
optimization and determining when a value is a compile-time constant and
compiling it out.  As of gcc 4.6, it has finally reached a point where
it's possible to have generic search & insert cores that optimize
exactly as well as if they were hand-coded. (see also gcc man page:
-findirect-inlining)

This implementation actually consists of two layers written on top of the
existing rbtree implementation.

Layer 1: Type-Specific (But Not Type-Safe)
------------------------------------------
The first layer consists of enum rb_flags, struct rb_relationship and
some generic inline functions(see patch for doc comments).

enum rb_flags {
	RB_HAS_LEFTMOST		= 0x00000001,
	RB_HAS_RIGHTMOST	= 0x00000002,
	RB_HAS_COUNT		= 0x00000004,
	RB_UNIQUE_KEYS		= 0x00000008,
	RB_INSERT_REPLACES	= 0x00000010,
	RB_IS_AUGMENTED		= 0x00000040,
	RB_VERIFY_USAGE		= 0x00000080,
	RB_VERIFY_INTEGRITY	= 0x00000100
};

struct rb_relationship {
	ssize_t root_offset;
	ssize_t left_offset;
	ssize_t right_offset;
	ssize_t count_offset;
	ssize_t node_offset;
	ssize_t key_offset;
	int flags;
	const rb_compare_f compare;     /* comparitor for lookups */
	const rb_compare_f ins_compare; /* comparitor for inserts */
	unsigned key_size;
};

/* these function for use on all trees */
struct rb_node *rb_find(
		struct rb_root *root,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_find_near(
		struct rb_node *from,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_insert(
		struct rb_root *root,
		struct rb_node *node,
		const struct rb_relationship *rel);
struct rb_node *rb_insert_near(
		struct rb_root *root,
		struct rb_node *start,
		struct rb_node *node,
		const struct rb_relationship *rel);
void rb_remove(	struct rb_root *root,
		struct rb_node *node,
		const struct rb_relationship *rel);

/* these function for use on trees with non-unique keys */
struct rb_node *rb_find_first(
		struct rb_root *root,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_find_last(
		struct rb_root *root,
		const void *key,
		const struct rb_relationship *rel);
struct rb_node *rb_find_next(
		const struct rb_node *node,
		const struct rb_relationship *rel)
struct rb_node *rb_find_prev(
		const struct rb_node *node,
		const struct rb_relationship *rel)

Using this layer involves initializing a const struct rb_relationship
variable with compile-time constant values and feeding its "address" to
the generic inline functions.  The trick being, that (when gcc behaves
properly) it never creates a struct rb_relationship variable, stores an
initializer in the data section of the object file or passes a struct
rb_relationship pointer.  Instead, gcc "optimizes out" out the struct,
and uses the compile-time constant values to dictate how the inline
functions will expand.

Thus, this structure can be thought of both as a database's DDL (data
definition language), defining the relationship between two entities and the
template parameters to a C++ templatized function that controls how the
template function is instantiated.  This creates type-specific functions,
although type-safety is still not achieved (e.g., you can pass a pointer to
any rb_node you like).

To simplify usage, you can initialize your struct rb_relationship variable
with the RB_RELATIONSHIP macro, feeding it your types, member names and flags
and it will calculate the offsets for you.  See doc comments in patch for
examples of using this layer (either with or without the RB_RELATIONSHIP
macro).

Layer 2: Type-Safety
--------------------
In order to achieve type-safety of a generic interface in C, we must delve
deep into the darkened Swamps of The Preprocessor and confront the Prince of
Darkness himself: Big Ugly Macro.  To be fair, there is an alternative
solution (discussed in History & Design Goals), the so-called "x-macro" or
"supermacro" where you #define some pre-processor values and include an
unguarded header file.  With 17 parameters, I choose this solution for its
ease of use and brevity, but it's an area worth debate (some of which you can
find here if you wish: http://lwn.net/Articles/501876).

So this second layer allows you to use a single macro to define your
relationship as well as type-safe wrapper functions all in one go.

RB_DEFINE_INTERFACE(
	prefix,
	cont_type, root, left, right, count,
	obj_type, node, key,
	flags, compare, ins_compare,
	find_mod, insert_mod, find_near_mod, insert_near_mod)

To avoid needing multiple versions of the macro, we use a paradigm where
optional values can be left empty. (See RB_DEFINE_INTERFACE doc comments for
details.)  Thus, if your container doesn't need to know leftmost, you leave
the parameter empty.  Here's a quick example:

struct container {
	struct rb_root root;
	struct rb_node *leftmost;
	unsigned long count;
};

struct object {
	struct rb_node node;
	long key;
};

static inline long compare_long(const long *a, const long *b)
{
	return *a - *b;
}

RB_DEFINE_INTERFACE(
	my_objects,
	struct container, root, leftmost, /* no rightmost */, count,
	struct object, node, key,
	RB_UNIQUE_KEYS | RB_INSERT_REPLACES, compare_long, compare_long,
	,,,)

This will do some type-checking, create the struct rb_relationship and
the following static __always_inline wrapper functions. (Note that
"my_objects" is the prefix used in the example above.  It will be
whatever you pass as the first parameter to the RB_DEFINE_INTERFACE
macro.)

struct object *my_objects_find(
		struct container *cont,
		const typeof(((struct object *)0)->key) *_key);
struct object *my_objects_insert(
		struct container *cont,
		struct object *obj);
struct object *my_objects_find_near(
		struct object *near,
		const typeof(((struct object *)0)->key) *_key);
struct object *my_objects_insert_near(
		struct container *cont,
		struct object *near,
		struct object *obj);
void my_objects_remove(struct container *cont, struct object *obj);
struct object *my_objects_find_first(
		struct container *cont,
		const typeof(((struct object *)0)->key) *_key);
struct object *my_objects_find_last(
		struct container *cont,
		const typeof(((struct object *)0)->key) *_key);
struct object *my_objects_find_next(const struct object *obj);
struct object *my_objects_find_last(const struct object *obj);
struct object *my_objects_next(const struct object *obj);
struct object *my_objects_prev(const struct object *obj);
struct object *my_objects_first(struct container *cont);
struct object *my_objects_last(struct container *cont);

Each of these are each declared static __always_inline. However, you can
change the modifiers for the first four (find, insert, find_near and
insert_near) by populating any of the last 4 parameters with the function
modifiers of the respective function (when empty, they default to static
__always_inline).

Not only does this layer give you type-safety, it removes almost all of
the implementation details of the rbtree from the code using it, thus
making it easier to replace the underlying algorithm at some later
date.

Compare Functions
-----------------
Because equality is unimportant when doing inserts into a tree with duplicate
keys, struct rb_relationship's ins_compare field can be set to a greater-than
function for better performance. Using the example in the section above as a
model, this is what it would look like:

static inline long compare_long(const long *a, const long *b)
...
static inline long greater_long(const long *a, const long *b)
{
	return *a > *b;
}

RB_DEFINE_INTERFACE(
	my_objects,
	struct container, root, leftmost, /* no rightmost */, count,
	struct object, node, key,
	0, compare_long, greater_long,
	,,,)


History & Design Goals
======================
I've been through many iterations of various techniques searching for the
perfect "clean" implementation and finally settled on having a huge macro
expand to wrapper functions after exhausting all other alternatives. The trick
is that what one person considers a "clean" implementation is a bit of a value
judgment.  So by "clean", I mean balancing these requirements:

1.) minimal dependence on pre-processor
2.) avoiding pre-processor expanded code that will break debug
    information (backtraces)
3.) optimal encapsulation of the details of your rbtree in minimal
    source code (this is where you define the relationship between your
	container and contained objects, their types, keys, rather or not
	non-unique objects are allowed, etc.) -- preferably eliminating
	duplication of these details entirely.
4.) offering a complete feature-set in a single implementation (not
    multiple functions when various features are used)
5.) perfect optimization -- the generic function must be exactly as
    efficient as the hand-coded version

By those standards, the "cleanest" implementation I had come up with
actually used a different mechanism: defining an anonymous interface
struct something like this:

/* generic non-type-safe function */
static __always_inline void *__generic_func(void *obj);

struct {							\
        out_type *(*const func)(in_type *obj);			\
} name = {							\
        .func = (out_type *(*const)(in_type *obj))__generic_func;\
}

/* usage looks like this: */
DEFINE_INTERFACE(solution_a, struct something, struct something_else);
struct something *s;
struct something_else *se;
se = solution_a.func(s);

Sadly, while solution_a.func(s) optimizes perfectly in 4.6, it completely
bombed in 4.5 and prior -- the call by struct-member-function-pointer is never
inlined and nothing passed to it is every considered a compile-time constant
(again, see gcc's docs on -findirect-inline).  Because of the implementation
of the generic functions, this bloated the code unacceptably (3x larger).
Thus, I finally settled on the current RB_DEFINE_INTERFACE macro, which is
massive, but optimizes perfectly in 4.6+ and close enough in 4.5 and prior
(prior to 4.6, the compare function is never inlined).

The other alternative I briefly considered was to have a header file
that is only included after #defining all of these parameters, relying
primarily on cpp rather than cc & compile-time constants to fill in the
relationship details (the "x-macro" approach).  While this mechanism
would perform better on older compilers and never break backtraces, in
the end, I just couldn't stomach it.  Aside from that, it would make
using the interface almost as verbose as hand-coding it yourself.

Performance
===========
Here are the results of performance tests run on v5 of this patch set (against
v3.5 kernel) on an AMD Phenom 9850.  This is a reformatted version of what
tools/testing/selftests/grbtree/user/gen_report.sh outputs.  Test results vary
quite a bit dependent upon the selected features.

For all of these tests, I used the following parameters:
key range       0-4095
key type	u32
object_count    2048
repititions     131,072
node_size       24 bytes
object_size     32 bytes
total data size 65,536 bytes
num insertions	268,435,456

Below is a summary of the performance drop using generic rbtrees on various
ranges of compilers. (negative values are performance improvements)

GCC versions    Best    Worst
3.4 - 4.0	35%	80%
4.1 - 4.5	18%	23%
4.6 - 4.7	-7%	 5%

The tables below list the time in seconds it took to execute the tests on each
compiler and the difference between the generic and specific (i.e.,
hand-coded) test results (from v5 of patches against the 3.5 kernel).

Duplicate keys (no leftmost, rightmost or count)
Compiler       Generic Specific Performance Loss
gcc-3.4.6	33.41	18.78	77.94%
gcc-4.0.4	32.36	17.94	80.37%
gcc-4.1.2	23.11	17.76	30.14%
gcc-4.2.4	22.97	17.83	28.84%
gcc-4.3.6	23.07	17.78	29.79%
gcc-4.4.7	21.88	17.64	24.03%
gcc-4.5.4	21.75	17.54	23.99%
gcc-4.6.3	16.84	16.82	 0.10%
gcc-4.7.1	16.79	16.68	 0.66%

Duplicate keys, use leftmost (no rightmost or count)
Compiler       Generic Specific Performance Loss
gcc-3.4.6	33.54	22.57	48.63%
gcc-4.0.4	32.82	22.16	48.07%
gcc-4.1.2	27.30	22.77	19.93%
gcc-4.2.4	27.41	22.86	19.95%
gcc-4.3.6	28.65	23.03	24.38%
gcc-4.4.7	27.03	21.41	26.24%
gcc-4.5.4	26.69	22.48	18.71%
gcc-4.6.3	21.58	21.53	 0.24%
gcc-4.7.1	22.40	22.23	 0.77%

Duplicate keys, use leftmost, rightmost and count
Compiler       Generic Specific Performance Loss
gcc-3.4.6	33.49	22.70	47.52%
gcc-4.0.4	33.19	23.71	39.94%
gcc-4.1.2	29.03	23.76	22.18%
gcc-4.2.4	28.59	23.82	20.04%
gcc-4.3.6	29.69	23.94	24.01%
gcc-4.4.7	28.62	23.89	19.79%
gcc-4.5.4	28.73	23.54	22.04%
gcc-4.6.3	23.82	23.70	 0.51%
gcc-4.7.1	23.84	23.94	-0.40%

Unique keys (no leftmost, rightmost or count)
Compiler       Generic Specific Performance Loss
gcc-3.4.6	29.38	19.94	47.33%
gcc-4.0.4	28.85	21.14	36.48%
gcc-4.1.2	25.16	20.30	23.95%
gcc-4.2.4	25.26	20.50	23.23%
gcc-4.3.6	25.41	20.82	22.02%
gcc-4.4.7	26.12	20.68	26.33%
gcc-4.5.4	25.29	20.31	24.54%
gcc-4.6.3	21.57	20.35	 6.01%
gcc-4.7.1	20.98	20.20	 3.88%

Unique keys, use leftmost (no rightmost or count)
Compiler       Generic Specific Performance Loss
gcc-3.4.6	29.50	20.96	40.76%
gcc-4.0.4	28.93	20.90	38.41%
gcc-4.1.2	26.26	22.29	17.80%
gcc-4.2.4	25.49	22.05	15.61%
gcc-4.3.6	26.55	22.25	19.34%
gcc-4.4.7	28.90	22.24	29.92%
gcc-4.5.4	26.85	21.86	22.80%
gcc-4.6.3	22.95	22.06	 4.03%
gcc-4.7.1	22.56	21.48	 5.01%

Unique keys, use leftmost, rightmost and count
Compiler       Generic Specific Performance Loss
gcc-3.4.6	29.48	20.91	40.97%
gcc-4.0.4	29.37	21.72	35.20%
gcc-4.1.2	25.25	23.10	 9.29%
gcc-4.2.4	26.17	22.35	17.13%
gcc-4.3.6	26.34	22.30	18.10%
gcc-4.4.7	25.24	22.43	12.51%
gcc-4.5.4	25.58	23.07	10.89%
gcc-4.6.3	21.79	23.50	-7.29%
gcc-4.7.1	23.27	25.08	-7.22%


I've done an analysis of the gcc 4.7.1-generated code and discovered the
following flaws in the generic insert function.

1. Key of inserted object being read repeatedly. Instead of reading the value
   of the inserted key once, at the start of the function, the key is read
   prior to each comparision.  I'm guessing that this is because optimizer
   makes the faulty assumption that the value could change throughout the
   course of execution. This costs us one extra instruction each iteration of
   the loop as we search the tree (32-bit key).

     mov    0x18(%rax),%edx

   A work-around is in place to eliminate this problem on gcc 4.6.0 and later
   if your key size is 16, 32 or 64 bits, which manages to get gcc to store
   the key of the supplied object in a regsiter at the start of the function
   preventing us a performance loss of roughly 4%.

2. Due to gcc bug 3507 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=3507),
   this code:

     long diff = a - b;

     if (diff > 0)
         do_gt();
     else if (diff < 0)
         do_lt();
     else
         do_eq();

   Optimizes more poorly than this code:

     if (a > b)
         do_gt();
     else if (b < a)
         do_lt();
     else
         do_eq();

   So instead of the key compare happening like this (64-bit key):

     cmp    0x18(%rax),%rsi

   We get this:

     mov    %rsi,%rdx
     sub    0x18(%rax),%rdx
     cmp    $0x0,%rdx

   The results can be slightly worse when the key type isn't the same as long.
   With a signed 32-bit key (s32) on x86_64, gcc thinks it needs to convert
   the difference to a 64-bit long.

     mov    %esi,%edx
     sub    0x18(%rax),%edx
     movslq %edx,%rdx
     cmp    $0x0,%rdx

   Not only is this 2-3 extra instruction, it also uses one extra register,
   which in turn forces gcc to use an r8-15 register in other places, which
   requires larger opcodes. Also, this only occurs when using the normal
   compare function (doesn't occur when using 'greater').  So this affects
   inserts on trees with unique keys and all lookups.

Q&A
===
Q: Why did you add BUILD_BUG_ON_NON_CONST() and
   BUILD_BUG_ON_NON_CONST42()?
A: There were initially enough BUILD_BUG_ON(!__builtin_constant_p(arg))
   calls to warrant it having a macro for it.  However, I've since
   discovered that using __builtin_constant_p on a struct member did not
   behave very consistently, so after writing some test programs &
   scripts, and refining 200k+ test results, I graphed out basically
   where __builtin_constant_p() worked and didn't.  As it turns out,
   using it on struct members is fragile until gcc 4.2, so
   BUILD_BUG_ON_NON_CONST42() is intended for use with struct members.

Q: Why empty parameters?
   What is IFF_EMPTY() for?
   Why don't you just pass zero instead of an empty parameter?
A: Support for caching the left- & right-most nodes in the tree as well
   as maintaining a count variable are all optional.  Passing the offset
   value directly not only means more characters of code to use the
   RB_RELATIONSHIP and RB_DEFINE_INTERFACE macros (because now you'll
   have to invoke the offsetof macro, supplying your struct types
   again), but the offset may actually be zero, so passing zero as "I'm
   not using this feature" wont work.  (This is the reason why the flags
   RB_HAS_LEFTMOST, et. al. exist.)  Thus, you would also need to
   manually pass the appropriate rb_flag value to specify that you're
   using the feature.  All of this means more copy, paste & edit code
   that is error-prone and a maintenance nightmare.  This implementation
   allows the caller to pass the name of the struct member or leave the
   parameter empty to mean "I'm not using this feature", thus
   eliminating all of these other complications.

Q: Using huge macro like RB_DEFINE_INTERFACE prone to usage errors that
   create crappy error messages and have zero type-safety. (not really a
   question)
A: True.  However, much of this is mitigated by creating an
   __rb_sanity_check_##name function that is never called, but will
   generate meaningful error messages for most mistakes (incorrect
   struct member types, etc.)

Q: The traditional boolean comparitor passed to for sorted sets is a less_than
   function, why are you using 'greater than'?
A: This decision is purely for optimization purposes, as compare and
   greather_than are interchangable when we don't care about equality.
   However, this may become a moot point if we can't get gcc to properly
   optimize code using the compare function, and switch to a pair of
   equals/less functions.

Revision History
===============
New in v6:
o Rebased onto linux-next.
o Removed augmented suport which is now redundant.  This should give us a
  little speed back on those older compilers.
o Renamed CONFIG_RBTREE* to CONFIG_GRBTREE* to avoid conflicts with Michel
  Lespinasse's new code.
o Added support to selftests for a payload on the test objects to see how
  performance changes as the size of the objects grow.
o Various other enhancements to test code & scripts.
o Split up patch set into three smaller patch sets.

New in v5:
o Added a ability to specify a different compare function for inserts.  This
  is more efficient on trees with duplicate keys, since you can use a boolean
  "greater than" function.
o Added an optimization to generate better code where key size is 16, 32 or 64
  bits.
o Add test & validation framework (CONFIG_DEBUG_RBTREE and
  CONFIG_DEBUG_RBTREE_VALIDATE)
o Fixed bugs in kernel-doc so that API documentation generates correctly.
o Add userspace test program & scripts.
o Fixed a lot of typos
o Cleaned up and completed kernel-doc comments

New in v4:
o Added type-safe wrapper functions for rb_{next,prev,first,last}
  to RB_DEFINE_INTERFACE.  Naming is the same as other type-safe
  functions (e.g.,  prefix##_first wraps rb_first). (thanks Pavel Pisa
  for the suggestion)
o Added rb_find_{first,next,last,prev} (for non-unique trees) to find
  the first or last occurrence of a key and iterate through them.
  Type-safe wrapper functions also added to RB_DEFINE_INTERFACE. (thanks
  again Pavel Pisa)
o Added support for an unsigned long count member of the container
  struct that will be updated upon insertions & deletions.
o Improve sanity checks performed by RB_DEFINE_INTERFACE -- error
  messages are now more specific and clearer.  Type safety for compare
  function is now enforced.
o Completed implementation of insert_near (still untested).
o Completed testing for find_near.  Performance is something like
  O(log distance * 2 + 1), so if your start node is a bit closer than
  half way across the tree, find_near will be about the same speed as
  find. If it is further, it will be slower.  Either way, it is larger
  than a normal find (which should be taken into account), so should
  only be used when you are fairly certain your target objects is near
  the start.
o Added support for specifying modifiers for functions generated by
  RB_DEFINE_INTERFACE.  This adds 4 more parameters, but is probably
  better than forcing the user to write their own wrapper functions to
  macro-generated wrapper functions, just to change their function
  attributes.
o Added run-time versions of all of the __rb_xxx_to_xxx inline
  functions, for use in those conditions where someone may actually need
  to access these using a run-time struct rb_relatinoship value.
o Performed compile tests on gcc 3.4.6 - 4.7.0 and tweaked BUILD_BUG_ON*
  macros to not fail on any of these compilers.

New in v3:
o Moved compare & augment functions back into struct rb_relationship
  after discovering that calling them will be inlined in gcc 4.6+ if the
  function is flattened.
o Improved doc comments.
o Solved problem of compare function not being checked for
  type-correctness by adding a __sanity_check_##name() function to
  __RB_DEFINE_INTERFACE that generates usable errors when there's a type
  or member name problem in the macro parameters.  This is helpful since
  the errors produced when the RB_RELATIONSHIP macro expands were quite
  terrible.

New in v2:
o Added RB_RELATIONSHIP macro (thanks Peter Zijlstra for the
  suggestions).
o Added RB_DEFINE_INTERFACE macro.

[PATCH v6 1/10] rbtree.h: Generic Red-Black Trees

[Daniel Santos]

Add generic red-black tree code to rbtree.h.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 include/linux/rbtree.h | 1125 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 1123 insertions(+), 2 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 0022c1b..210ebeb 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -1,7 +1,8 @@
 /*
   Red Black Trees
   (C) 1999  Andrea Arcangeli <andrea@suse.de>
-  
+  (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
@@ -31,6 +32,7 @@
 
 #include <linux/kernel.h>
 #include <linux/stddef.h>
+#include <linux/bug.h>
 
 struct rb_node {
 	unsigned long  __rb_parent_color;
@@ -61,6 +63,7 @@ struct rb_root {
 extern void rb_insert_color(struct rb_node *, struct rb_root *);
 extern void rb_erase(struct rb_node *, struct rb_root *);
 
+typedef long (*rb_compare_f)(const void *a, const void *b);
 
 /* Find logical next and previous nodes in a tree */
 extern struct rb_node *rb_next(const struct rb_node *);
@@ -69,7 +72,7 @@ extern struct rb_node *rb_first(const struct rb_root *);
 extern struct rb_node *rb_last(const struct rb_root *);
 
 /* Fast replacement of a single node without remove/rebalance/add/rebalance */
-extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
+extern void rb_replace_node(struct rb_node *victim, struct rb_node *new,
 			    struct rb_root *root);
 
 static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
@@ -81,4 +84,1122 @@ 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 parameter 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
+ * @member:         (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, member) IFF_EMPTY(member, 0, offsetof(type, member))
+
+/**
+ * enum rb_flags - values for strct rb_relationship's flags
+ * @RB_HAS_LEFTMOST:	The container has a struct rb_node *leftmost member
+ * 			that will receive a pointer to the leftmost (smallest)
+ * 			object in the tree that is updated during inserts &
+ * 			deletions.
+ * @RB_HAS_RIGHTMOST:	Same as above (for right side of tree).
+ * @RB_HAS_COUNT:	The container has an unsigned long field that will
+ * 			receive updates of the object count in the tree.
+ * @RB_UNIQUE_KEYS:	The tree contains only unique values.
+ * @RB_INSERT_REPLACES:	When set, the rb_insert() will replace a value if it
+ * 			matches the supplied one (valid only when
+ * 			RB_UNIQUE_KEYS is set).
+ * @RB_ALL_FLAGS:	(internal use)
+ */
+
+enum rb_flags {
+	RB_HAS_LEFTMOST		= 0x00000001,
+	RB_HAS_RIGHTMOST	= 0x00000002,
+	RB_HAS_COUNT		= 0x00000004,
+	RB_UNIQUE_KEYS		= 0x00000008,
+	RB_INSERT_REPLACES	= 0x00000010,
+	RB_ALL_FLAGS		= RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
+			| RB_HAS_COUNT | 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 RB_HAS_LEFTMOST is set) 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.
+ * @count_offset: Offset of container's unsigned long count member.
+ * @node_offset:  Offset of object's struct rb_node member.
+ * @key_offset:   Offset of object's key member.
+ * @flags:        See enum rb_flags.
+ * @compare:      Pointer to key rb_compare_f function to compare keys.
+ *		  Although it will be cast to and called as type long (*)(const
+ *		  void *a, const void *b), you should declare it as accepting
+ *		  pointers to your key members, or sanity checks will fail.
+ *		  Further, it is optimal if the function is declared inline.
+ *
+ * Instances of struct rb_relationship should be compile-time constants (or
+ * rather, the value of its members).
+ */
+struct rb_relationship {
+	ssize_t root_offset;
+	ssize_t left_offset;
+	ssize_t right_offset;
+	ssize_t count_offset;
+	ssize_t node_offset;
+	ssize_t key_offset;
+	int flags;
+	const rb_compare_f compare;
+	const rb_compare_f ins_compare;
+	unsigned key_size;
+};
+
+#define __RB_PTR(type, ptr, offset) ((type *)((char *)(ptr) + (offset)))
+
+/* public conversion functions for use with run-time values */
+static __always_inline
+struct rb_root *rb_to_root(const void *ptr,
+			   const struct rb_relationship *rel)
+{
+	return __RB_PTR(struct rb_root, ptr, rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **rb_root_to_left(struct rb_root *root,
+				 const struct rb_relationship *rel)
+{
+	return __RB_PTR(struct rb_node *, root,
+			rel->left_offset - rel->root_offset);
+}
+
+static __always_inline
+struct rb_node **rb_root_to_right(struct rb_root *root,
+				  const struct rb_relationship *rel)
+{
+	return __RB_PTR(struct rb_node *, root,
+			rel->right_offset - rel->root_offset);
+}
+
+static __always_inline
+unsigned long *rb_root_to_count(struct rb_root *root,
+			       const struct rb_relationship *rel)
+{
+	return __RB_PTR(unsigned long, root,
+			rel->count_offset - rel->root_offset);
+}
+
+static __always_inline
+const void *rb_node_to_key(const struct rb_node *node,
+			   const struct rb_relationship *rel)
+{
+	return __RB_PTR(const void, node,
+			rel->key_offset - rel->node_offset);
+}
+
+static __always_inline
+void *rb_node_to_obj(const struct rb_node *node,
+		     const struct rb_relationship *rel)
+{
+	return __RB_PTR(void, node, -rel->node_offset);
+}
+
+static __always_inline
+struct rb_node *rb_to_node(const void *ptr, const struct rb_relationship *rel)
+{
+	return __RB_PTR(struct rb_node, ptr, rel->node_offset);
+}
+
+static __always_inline
+const void *rb_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	return __RB_PTR(const void, ptr, rel->key_offset);
+}
+
+
+/* checked conversion functions that will error on run-time values */
+static __always_inline
+struct rb_root *__rb_to_root(const void *ptr,
+			     const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->root_offset);
+	return rb_to_root(ptr, rel);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_left(struct rb_root *root,
+				   const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON42(!(rel->flags & RB_HAS_LEFTMOST));
+	BUILD_BUG_ON_NON_CONST42(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->left_offset);
+	return rb_root_to_left(root, rel);
+}
+
+static __always_inline
+struct rb_node **__rb_root_to_right(struct rb_root *root,
+				    const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON42(!(rel->flags & RB_HAS_RIGHTMOST));
+	BUILD_BUG_ON_NON_CONST42(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->right_offset);
+	return rb_root_to_right(root, rel);
+}
+
+static __always_inline
+unsigned long *__rb_root_to_count(struct rb_root *root,
+				  const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON42(!(rel->flags & RB_HAS_COUNT));
+	BUILD_BUG_ON_NON_CONST42(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->count_offset);
+	return rb_root_to_count(root, rel);
+}
+
+static __always_inline
+const void *__rb_node_to_key(const struct rb_node *node,
+			     const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->node_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->key_offset);
+	return rb_node_to_key(node, rel);
+}
+
+static __always_inline
+void *__rb_node_to_obj(const struct rb_node *node,
+		       const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->node_offset);
+	return rb_node_to_obj(node, rel);
+}
+
+static __always_inline
+struct rb_node *__rb_to_node(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->node_offset);
+	return rb_to_node(ptr, rel);
+}
+
+static __always_inline
+const void *__rb_to_key(const void *ptr, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->key_offset);
+	return rb_to_key(ptr, rel);
+}
+
+/**
+ * __rb_assert_good_rel() - Perform compile-time sanity checks on a struct
+ *			    rb_relationship.
+ * @rel:	Pointer to a const struct rb_relationship to check.
+ */
+static __always_inline
+void __rb_assert_good_rel(const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->flags);
+	BUILD_BUG_ON42(rel->flags & ~RB_ALL_FLAGS);
+
+	BUILD_BUG_ON_NON_CONST42(rel->root_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->node_offset);
+	BUILD_BUG_ON_NON_CONST42(rel->key_offset);
+
+	if (rel->flags & RB_HAS_LEFTMOST)
+		BUILD_BUG_ON_NON_CONST42(rel->count_offset);
+
+	if (rel->flags & RB_HAS_RIGHTMOST)
+		BUILD_BUG_ON_NON_CONST42(rel->right_offset);
+
+	if (rel->flags & RB_HAS_COUNT)
+		BUILD_BUG_ON_NON_CONST42(rel->left_offset);
+
+	/* Due to a bug in versions of gcc prior to 4.6, the following
+	 * expressions are always evalulated at run-time:
+	 *
+	 * (!(rel->flags & RB_UNIQUE_KEYS) && (rel->flags & RB_INSERT_REPLACES))
+	 *
+	 * The work-around for this bug is separate each bitwise AND test using
+	 * an if/else construct and evaluate only the last test with the
+	 * BUILD_BUG_ON macro.
+	 */
+
+	if (rel->flags & RB_INSERT_REPLACES)
+		BUILD_BUG_ON42(!(rel->flags & RB_UNIQUE_KEYS));
+}
+
+
+/**
+ * __rb_find() - Perform a (normal) search on a Red-Black Tree, starting at the
+ *		 specified node, traversing downward.
+ * @node:	Node (subtree) to start the search from.
+ * @key:	Pointer to a key to search for.
+ * @rel:	Pointer to the relationship definition constant.
+ */
+static __always_inline __flatten
+struct rb_node *__rb_find(
+		struct rb_node *node,
+		const void *key,
+		const struct rb_relationship *rel)
+{
+	__rb_assert_good_rel(rel);
+	while (node) {
+		long diff = rel->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;
+}
+
+/**
+ * rb_find() - Perform a (normal) search on a Red-Black Tree.
+ * @root:	Root of the tree.
+ * @key:	Pointer to a key to search for.
+ * @rel:	Pointer to the relationship definition constant.
+ */
+static __always_inline __flatten
+struct rb_node *rb_find(
+		struct rb_root *root,
+		const void *key,
+		const struct rb_relationship *rel)
+{
+	return __rb_find(root->rb_node, key, rel);
+}
+
+static __always_inline __flatten
+struct rb_node *__rb_find_first_last(
+		struct rb_node *node,
+		const void *key,
+		const struct rb_relationship *rel,
+		const int find_first)
+{
+	__rb_assert_good_rel(rel);
+
+	/* don't use this function on a tree with unique keys */
+	BUILD_BUG_ON42(rel->flags & RB_UNIQUE_KEYS);
+	BUILD_BUG_ON_NON_CONST(find_first);
+
+	while (node) {
+		long diff = rel->compare(key, __rb_node_to_key(node, rel));
+
+		if (diff > 0)
+			node = node->rb_right;
+		else if (diff < 0)
+			node = node->rb_left;
+		else {
+			if (find_first && node->rb_left)
+				node = node->rb_left;
+			else if (!find_first && node->rb_right)
+				node = node->rb_right;
+			else
+				return node;
+		}
+	}
+
+	return 0;
+}
+
+/**
+ * rb_find_first() - Search for first occurrence of key in a tree containing
+ * 		     non-unique keys.
+ * @root:	Root of the tree.
+ * @key:	Pointer to a key.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * This function is intended for use with trees containing non-unique keys.
+ * When called for trees with unique keys, it maps to __rb_find (a normal
+ * search).
+ */
+static __always_inline __flatten
+struct rb_node *rb_find_first(
+		struct rb_root *root,
+		const void *key,
+		const struct rb_relationship *rel)
+{
+	return __rb_find_first_last(root->rb_node, key, rel, 1);
+}
+
+/**
+ * rb_find_last() - Search for last occurrence of key in a tree containing
+ * 		    non-unique keys.
+ * @root:	Root of the tree.
+ * @key:	Pointer to a key.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * This function is intended for use with trees containing non-unique keys.
+ * When called for trees with unique keys, it maps to __rb_find (a normal
+ * search).
+ */
+static __always_inline __flatten
+struct rb_node *rb_find_last(
+		struct rb_root *root,
+		const void *key,
+		const struct rb_relationship *rel)
+{
+	return __rb_find_first_last(root->rb_node, key, rel, 0);
+}
+
+/**
+ * rb_find_next() - Locate the next node in a tree containing non-unique keys,
+ *		    whos key matches the supplied node.
+ * @node:	Node of the current object in the tree.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * Generally for use after calling rb_find_first().  Only valid for use with a
+ * tree with non-unique keys.
+ */
+static __always_inline __flatten
+struct rb_node *rb_find_next(
+		const struct rb_node *node,
+		const struct rb_relationship *rel)
+{
+	const void *key      = __rb_node_to_key(node, rel);
+	struct rb_node *next = rb_next(node);
+
+	/* don't use this function on a tree with unique keys */
+	BUILD_BUG_ON42(rel->flags & RB_UNIQUE_KEYS);
+	return (next && !rel->compare(key, __rb_node_to_key(next, rel)))
+	       ? next : NULL;
+}
+
+/**
+ * rb_find_prev() - Locate the previous node in a tree containing non-unique
+ *		    keys, whos key matches the supplied node.
+ * @node:	Node of the current object in the tree.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * Generally for use after calling rb_find_last().  Only valid for use with a
+ * tree with non-unique keys.
+ */
+static __always_inline __flatten
+struct rb_node *rb_find_prev(
+		const struct rb_node *node,
+		const struct rb_relationship *rel)
+{
+	const void *key      = __rb_node_to_key(node, rel);
+	struct rb_node *prev = rb_prev(node);
+
+	/* don't use this function on a tree with unique keys */
+	BUILD_BUG_ON42(rel->flags & RB_UNIQUE_KEYS);
+	return (prev && !rel->compare(key, __rb_node_to_key(prev, rel)))
+	       ? prev : NULL;
+}
+
+
+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) traversing upwards.
+ * @root:	Root of the tree
+ * @start:	Node to start from
+ * @key:	Key to search for
+ * @matched:	Pointer for a result value to be returned to (see enum
+ * 		rb_find_subtree_match)
+ * @ret_link:	Pointer for a link pointer to be returned
+ * @ret_parent:	Pointer for a parent pointer to be returned
+ * @rel:	A constant relationship definition
+ * @doing_insert: Rather or not we're doing an insert.
+ *
+ * Travels up a tree, starting from the specified node, until it locates the
+ * node (representing the subtree) under which the object (specified by key)
+ * can be located, or until that object its self is located.
+ *
+ * This function is used by find_near and insert_near, but behaves differently
+ * for each case (and perhaps could have been implemented as two separate
+ * functions). Specifically, when doing_insert is non-zero, it will set values
+ * in the location provided by populate ret_link & ret_parent.  Unused
+ * functionality when doing_insert is zero should be "compiled-out" in an
+ * optimized build.
+ */
+static __always_inline __flatten
+struct rb_node *__rb_find_subtree(
+		struct rb_root *root,
+		struct rb_node *start,
+		const void *key,
+		int *matched,
+		struct rb_node ***ret_link, /* wow, triple indirection.
+					       Am I smart or just nuts? */
+		struct rb_node **ret_parent,
+		const struct rb_relationship *rel,
+		const int doing_insert)
+{
+	struct rb_node *prev = start;
+	struct rb_node *node = rb_parent(start);
+	long diff;
+
+	__rb_assert_good_rel(rel);
+	BUILD_BUG_ON_NON_CONST(doing_insert);
+	BUG_ON(doing_insert && (!root || !ret_link || !ret_parent));
+
+	/* already at top of tree, so return start value */
+	if (!node) {
+		*matched = RB_MATCH_NONE;
+		if (doing_insert) {
+			*ret_link = &root->rb_node;
+			*ret_parent = **ret_link;
+		}
+		return start;
+	}
+
+	/* The first compare is just to figure out which direction up the tree
+	 * we're traveling.  When compare returns a value with a different
+	 * sign, we'll have found our subtree, or an exact match if zero.
+	 */
+	diff = rel->compare(key, __rb_node_to_key(node, rel));
+
+	if (diff) {
+		int go_left = diff < 0;
+		while (1) {
+			prev = node;
+			node = rb_parent(prev);
+			if (!node)
+				/* Reached top of tree.  In this case. rather
+				 * than having the top down search start from
+				 * the root, we'll start on the prev sibling
+				 * since we've already tested the root node, we
+				 * know that we don't need to go back the way
+				 * we came.
+				 */
+				break;
+
+			diff = rel->compare(key, __rb_node_to_key(node, rel));
+			if (go_left ? diff > 0 : diff < 0)
+				/* found the diverging node, so the child on
+				 * the opposite side (of prev) is the subtree
+				 * that will contain the key
+				 */
+				break;
+			else if (!diff) {
+				/* exact match */
+				*matched = go_left
+					 ? RB_MATCH_LEFT
+					 : RB_MATCH_RIGHT;
+
+				goto find_parent_link;
+			}
+		}
+
+		*matched = RB_MATCH_NONE;
+		if (doing_insert) {
+			*ret_parent = prev;
+			*ret_link = go_left ? &prev->rb_left : &prev->rb_right;
+			return **ret_link;
+		} else {
+			return go_left ? prev->rb_left : prev->rb_right;
+		}
+	}
+
+	/* start node's parent was an exact match */
+	*matched = RB_MATCH_IMMEDIATE;
+
+find_parent_link:
+	if (doing_insert) {
+		struct rb_node *parent = rb_parent(node);
+
+		if (!parent) {
+			*ret_link = &root->rb_node;
+			*ret_parent = **ret_link;
+		} else if (parent->rb_left == node) {
+			*ret_link = &parent->rb_left;
+			*ret_parent = parent;
+		} else if (parent->rb_right == node) {
+			*ret_link = &parent->rb_left;
+			*ret_parent = parent;
+		} else {
+			BUG();
+		}
+	}
+
+	return node;
+}
+
+/**
+ * rb_find_near() - Perform a search starting at the specified node instead of
+ *		    the top of the tree.
+ * @from:	Node to start search from
+ * @key:	Key to search for
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * Travels up the tree starting from the specified node and then back down
+ * again, searching for the object specified by key.  This function is larger
+ * than a normal search, but can yield better performance if the target object
+ * is near the supplied node. Performance is roughly O(log2(distance / 2) * 2
+ * + 1).
+ */
+static __always_inline __flatten
+struct rb_node *rb_find_near(
+		struct rb_node *from,
+		const void *key,
+		const struct rb_relationship *rel)
+{
+	int matched;
+	struct rb_node *subtree;
+
+	subtree = __rb_find_subtree(NULL, from, key, &matched, NULL, NULL,
+				    rel, 0);
+
+	if (matched)
+		return subtree;
+
+	return __rb_find(subtree, key, rel);
+}
+
+/* common insert epilogue used by rb_insert() and rb_insert_near() */
+static __always_inline __flatten
+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)
+{
+	if ((rel->flags & RB_UNIQUE_KEYS) && found) {
+		if (rel->flags & RB_INSERT_REPLACES)
+			rb_replace_node(found, node, root);
+		goto done;
+	} else {
+		rb_link_node(node, parent, rb_link);
+		rb_insert_color(node, root);
+	}
+
+	if ((rel->flags & RB_HAS_COUNT))
+		++*__rb_root_to_count(root, rel);
+
+done:
+	return found;
+}
+
+
+/**
+ * rb_insert() - Insert a node into a tree.
+ * @root:	Pointer to struct rb_root.
+ * @node:	Pointer to the node of the new object to insert.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * If an object with the same key already exists and RB_INSERT_REPLACES is set
+ * then it is replaced with new object node; if RB_INSERT_REPLACES is not set,
+ * then no change is made. In either case, a pointer to the existing object
+ * node is returned.
+ *
+ * If no object with the same key exists, then the new object node is inserted
+ * and NULL is returned.
+ */
+static __always_inline __flatten
+struct rb_node *rb_insert(
+		struct rb_root *root,
+		struct rb_node *node,
+		const struct rb_relationship *rel)
+{
+	struct rb_node **p     = &root->rb_node;
+	struct rb_node *parent = NULL;
+	const void * const key = __rb_node_to_key(node, rel);
+	int leftmost           = 1;
+	int rightmost          = 1;
+
+	/* optimization/hack good on gcc 4.6.0+, when -findirect-inline is able
+	 * to inline the compare function.  This manages to force gcc to put
+	 * the value of the key in a register, instead of retrieving it prior
+	 * to each compare.  The necessity of this hasn't been tested beyond
+	 * gcc 4.7.1.
+	 */
+#if GCC_VERSION >= 40600
+	u16 __maybe_unused key16;
+	u32 __maybe_unused key32;
+	u64 __maybe_unused key64;
+
+	if (rel->key_size == 2)
+		key16 = *(u16*)key;
+	else if (rel->key_size == 4)
+		key32 = *(u32*)key;
+	else if (rel->key_size == 8)
+		key64 = *(u64*)key;
+#endif
+
+	__rb_assert_good_rel(rel);
+
+
+	while (*p) {
+		long diff;
+		const void *cur_key = __rb_node_to_key(*p, rel);
+
+#if GCC_VERSION >= 40600
+		if (rel->key_size == 2)
+			diff = rel->ins_compare(&key16, cur_key);
+		else if (rel->key_size == 4)
+			diff = rel->ins_compare(&key32, cur_key);
+		else if (rel->key_size == 8)
+			diff = rel->ins_compare(&key64, cur_key);
+		else
+#endif
+			/* On gcc 4.5.x & prior, or for other key sizes, we
+			 * pass key ptr as a const void*, which tends to
+			 * optimize more poorly
+			 */
+			diff = rel->ins_compare(key, cur_key);
+
+		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);
+}
+
+/**
+ * rb_insert_near() - Perform an insert, but use the supplied start node to
+ *		      find the location for the new node.
+ * @root:	Pointer to struct rb_root.
+ * @start:	Node to start search for insert location from.
+ * @node:	Pointer to the node of the new object to insert.
+ * @rel:	Pointer to the relationship definition constant.
+ *
+ * This function is larger than rb_insert, but can yield better performance
+ * when the position where the new node is being is close to start. Performance
+ * is roughly O(log2(distance / 2) * 2 + 1).
+ */
+static __always_inline __flatten
+struct rb_node *rb_insert_near(
+		struct rb_root *root,
+		struct rb_node *start,
+		struct rb_node *node,
+		const struct rb_relationship *rel)
+{
+	const void *key = __rb_node_to_key(node, rel);
+	struct rb_node **p;
+	struct rb_node *parent;
+	struct rb_node *ret;
+	int matched;
+	long diff;
+
+	BUILD_BUG_ON_NON_CONST42(rel->flags);
+
+	ret = __rb_find_subtree(root, start, key, &matched, &p, &parent, rel,
+				1);
+
+	if (!matched) {
+		while (*p) {
+			diff   = rel->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;
+	}
+
+	/* the longer way to see if we're left- or right-most (since we aren't
+	 * starting from the top, we can't use the mechanism rb_insert()
+	 * does.)
+	 */
+	if (rel->flags & RB_HAS_LEFTMOST) {
+		struct rb_node **left = __rb_root_to_left(root, rel);
+		if (!*left || *left == ret ||
+				(*left == parent && &parent->rb_left == p))
+			*left = node;
+	}
+
+	if (rel->flags & RB_HAS_RIGHTMOST) {
+		struct rb_node **right = __rb_root_to_right(root, rel);
+		if (!*right || *right == ret ||
+				(*right == parent && &parent->rb_right == p))
+			*right = node;
+	}
+
+	return __rb_insert_epilogue(root, parent, node, ret, p, rel);
+}
+
+/**
+ * rb_remove() - Remove a node from an rbtree.
+ * @root:	Pointer to struct rb_root.
+ * @node:	Pointer to the node of the object to be removed.
+ * @rel:	Pointer to the relationship definition constant.
+ */
+static __always_inline __flatten
+void rb_remove(
+	struct rb_root *root,
+	struct rb_node *node,
+	const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST42(rel->flags);
+
+	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 ((rel->flags & RB_HAS_COUNT))
+		--*__rb_root_to_count(root, rel);
+}
+
+
+/**
+ * RB_RELATIONSHIP - Define the relationship between 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)
+ * @count:     (Optional) Name of container's unsigned long member that will be
+ *             updated with the number of objects in the tree.  Note that if
+ *             you add or remove objects from the tree without using the
+ *             generic functions, you must update this value yourself.
+ * @obj_type:  Type of object stored in container
+ * @node:      The struct rb_node member of the object
+ * @key:       The key member of the object
+ * @_flags:    see enum rb_flags.  Note: you do not have to specify
+ *             RB_HAS_LEFTMOST, RB_HAS_RIGHTMOST or RB_HAS_COUNT as these will be added automatically if their respective field is non-empty.
+ * @_compare:  Pointer to key rb_compare_f function to compare keys.
+ *             Although it will be cast to and called as type long (*)(const
+ *             void *a, const void *b), you should declare it as accepting
+ *             pointers to your key members, or sanity checks will fail.
+ *             Further, it is optimal if the function is declared inline.
+ * @_ins_compare:
+ *
+ * Example:
+ * struct my_container {
+ *     struct rb_root root;
+ *     unsigned int count;
+ *     struct rb_node *left;
+ * };
+ *
+ * struct my_object {
+ *     struct rb_node node;
+ *     int key;
+ * };
+ *
+ * static inline long compare_int(const int *a, const int *b)
+ * {
+ *     return *a - *b;
+ * }
+ *
+ * static inline long greater_int(const int *a, const int *b)
+ * {
+ *     return *a > *b;
+ * }
+ *
+ * static const struct rb_relationship my_rel = RB_RELATIONSHIP(
+ *     struct my_container, root, left, , count, // no rightmost
+ *     struct my_object, node, key,
+ *     0, compare_int, greater_int);
+ */
+#define RB_RELATIONSHIP(						\
+		cont_type, root, left, right, count,			\
+		obj_type, node, key,					\
+		_flags, _compare, _ins_compare) {			\
+	.root_offset	= offsetof(cont_type, root),			\
+	.left_offset	= OPT_OFFSETOF(cont_type, left),		\
+	.right_offset	= OPT_OFFSETOF(cont_type, right),		\
+	.count_offset	= OPT_OFFSETOF(cont_type, count),		\
+	.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)	\
+			| IFF_EMPTY(count,    0,  RB_HAS_COUNT),	\
+	.compare	= (const rb_compare_f) (_compare),		\
+	.ins_compare	= (const rb_compare_f) (_ins_compare),		\
+	.key_size	= sizeof(((obj_type *)0)->key)			\
+}
+
+/* compile-time type-validation functions used by __rb_sanity_check_##prefix */
+static inline void __rb_verify_root(struct rb_root *root) {}
+static inline void __rb_verify_left(struct rb_node * const *left) {}
+static inline void __rb_verify_right(struct rb_node * const *right) {}
+static inline void __rb_verify_count(const unsigned int *count) {}
+static inline void __rb_verify_node(struct rb_node *node) {}
+static inline void __rb_verify_compare_fn_ret(long *diff) {}
+static inline void __rb_verify_ins_compare_fn_ret(long *diff) {}
+
+/**
+ * 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:   see RB_RELATIONSHIP
+ * @root:        see RB_RELATIONSHIP
+ * @left:        see RB_RELATIONSHIP
+ * @right:       see RB_RELATIONSHIP
+ * @count:       see RB_RELATIONSHIP
+ * @obj_type:    see RB_RELATIONSHIP
+ * @node:        see RB_RELATIONSHIP
+ * @key:         see RB_RELATIONSHIP
+ * @flags:       see RB_RELATIONSHIP
+ * @compare:     see RB_RELATIONSHIP
+ * @ing_compare: see RB_RELATIONSHIP
+ * @insert_mod:      (Optional) Function modifiers for insert function,
+ *                   defaults to "static __always_inline" if left empty.
+ * @insert_near_mod: (Optional) Same as above, for insert_near.
+ * @find_mod:        (Optional) Same as above, for find.
+ * @find_near_mod:   (Optional) Same as above, for find_near.
+ *
+ * This macro can be declared 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 (else, you'll be screwed).
+ *
+ * Example:
+ * struct my_container {
+ *     struct rb_root root;
+ *     unsigned int count;
+ *     struct rb_node *left;
+ * };
+ *
+ * struct my_object {
+ *     struct rb_node node;
+ *     int key;
+ * };
+ *
+ * static inline long compare_int(const int *a, const int *b)
+ * {
+ *     return (long)*a - (long)*b;
+ * }
+ *
+ * RB_DEFINE_INTERFACE(
+ *     my_tree,
+ *     struct my_container, root, left, , count, // no rightmost
+ *     struct my_object, node, key,
+ *     0, compare_int,
+ *     ,                     // defaults for find
+ *     static __flatten,     // let gcc decide rather or not to inline insert()
+ *     ,                     // defaults on find_near
+ *     static __flatten noinline) // don't let gcc inline insert_near()
+ */
+#define RB_DEFINE_INTERFACE(						\
+	prefix,								\
+	cont_type, root, left, right, count,				\
+	obj_type, node, key,						\
+	flags, compare, ins_compare,					\
+	find_mod, insert_mod, find_near_mod, insert_near_mod)		\
+									\
+/* Compile-time sanity checks. You need not call this function for	\
+ * validation to occur.  We define __rb_sanity_check function first,	\
+ * so errors will (hopefully) get caught here and produce a more helpful\
+ * error message than a failure in the RB_RELATIONSHIP macro expansion.	\
+ */									\
+static inline __maybe_unused						\
+void __rb_sanity_check_ ## prefix(cont_type *cont, obj_type *obj)	\
+{									\
+	/* {,ins_}compare functions should take ptr to key member */	\
+	typeof((compare)(&obj->key, &obj->key)) _diff =			\
+			(compare)(&obj->key, &obj->key);		\
+	typeof((ins_compare)(&obj->key, &obj->key)) _ins_diff =		\
+			(ins_compare)(&obj->key, &obj->key);		\
+	__rb_verify_compare_fn_ret(&_diff);				\
+	__rb_verify_ins_compare_fn_ret(&_ins_diff);			\
+									\
+	/* validate types of container members */			\
+	__rb_verify_root(&cont->root);					\
+	__rb_verify_left (IFF_EMPTY(left  , 0, &cont->left));		\
+	__rb_verify_right(IFF_EMPTY(right , 0, &cont->right));		\
+	__rb_verify_count(IFF_EMPTY(count , 0, &cont->count));		\
+									\
+	/* validate types of object node */				\
+	__rb_verify_node(&obj->node);					\
+}									\
+									\
+static const struct rb_relationship prefix ## _rel =			\
+RB_RELATIONSHIP(							\
+	cont_type, root, left, right, count,				\
+	obj_type, node, key,						\
+	flags, compare, ins_compare);					\
+									\
+IFF_EMPTY(find_mod, static __always_inline, find_mod)			\
+obj_type *prefix ## _find(cont_type *cont,				\
+			  const typeof(((obj_type *)0)->key) *_key)	\
+{									\
+	struct rb_node *ret = rb_find(					\
+			&cont->root, _key, &prefix ## _rel);		\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+IFF_EMPTY(insert_mod, static __always_inline, insert_mod)		\
+obj_type *prefix ## _insert(cont_type *cont, obj_type *obj)		\
+{									\
+	struct rb_node *ret = rb_insert(				\
+			&cont->root, &obj->node, &prefix ## _rel);	\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+IFF_EMPTY(find_near_mod, static __always_inline, find_near_mod)		\
+obj_type *prefix ## _find_near(obj_type *near,				\
+		    const typeof(((obj_type *)0)->key) *_key)		\
+{									\
+	struct rb_node *ret = rb_find_near(				\
+			&near->node, _key, &prefix ## _rel);		\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+IFF_EMPTY(insert_near_mod, static __always_inline, insert_near_mod)	\
+obj_type *prefix ## _insert_near(cont_type *cont, obj_type *near,	\
+				 obj_type *obj)				\
+{									\
+	struct rb_node *ret = rb_insert_near(				\
+			&cont->root, &near->node, &obj->node,		\
+			&prefix ## _rel);				\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+void prefix ## _remove(cont_type *cont, obj_type *obj)			\
+{									\
+	rb_remove(&cont->root, &obj->node, &prefix ## _rel);		\
+}									\
+									\
+IFF_EMPTY(find_mod, static __always_inline, find_mod) __maybe_unused	\
+obj_type *prefix ## _find_first(cont_type *cont,			\
+			  const typeof(((obj_type *)0)->key) *_key)	\
+{									\
+	struct rb_node *ret = rb_find_first(				\
+			&cont->root, _key, &prefix ## _rel);		\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+IFF_EMPTY(find_mod, static __always_inline, find_mod) __maybe_unused	\
+obj_type *prefix ## _find_last(cont_type *cont,				\
+			  const typeof(((obj_type *)0)->key) *_key)	\
+{									\
+	struct rb_node *ret = rb_find_last(				\
+			&cont->root, _key, &prefix ## _rel);		\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *prefix ## _find_next(const obj_type *obj)			\
+{									\
+	struct rb_node *ret = rb_find_next(&obj->node, &prefix ## _rel);\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline							\
+obj_type *prefix ## _find_prev(const obj_type *obj)			\
+{									\
+	struct rb_node *ret = rb_find_prev(&obj->node, &prefix ## _rel);\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline obj_type *prefix ## _next(const obj_type *obj)	\
+{									\
+	struct rb_node *ret = rb_next(&obj->node);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline obj_type *prefix ## _prev(const obj_type *obj)	\
+{									\
+	struct rb_node *ret = rb_prev(&obj->node);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline obj_type *prefix ## _first(cont_type *cont)	\
+{									\
+	struct rb_node *ret = rb_first(&cont->root);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}									\
+									\
+static __always_inline obj_type *prefix ## _last(cont_type *cont)	\
+{									\
+	struct rb_node *ret = rb_last(&cont->root);			\
+	return ret ? rb_entry(ret, obj_type, node) : 0;			\
+}
+
 #endif	/* _LINUX_RBTREE_H */
-- 
1.7.3.4

[PATCH v6 2/10] rbtree.h: include kconfig.h

[Daniel Santos]

We shouldn't depend upon kernel.h including this for us.  However, this
also fixes some issues with compiling in userland (coming later).

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 include/linux/rbtree.h |    1 +
 1 files changed, 1 insertions(+), 0 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 210ebeb..48e325f 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -33,6 +33,7 @@
 #include <linux/kernel.h>
 #include <linux/stddef.h>
 #include <linux/bug.h>
+#include <linux/kconfig.h>
 
 struct rb_node {
 	unsigned long  __rb_parent_color;
-- 
1.7.3.4

[PATCH v6 3/10] Generate doc comments for rbtree.h in Kernel-API

[Daniel Santos]

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 Documentation/DocBook/kernel-api.tmpl |    3 +++
 1 files changed, 3 insertions(+), 0 deletions(-)

diff --git a/Documentation/DocBook/kernel-api.tmpl b/Documentation/DocBook/kernel-api.tmpl
index 00687ee..d270f1e 100644
--- a/Documentation/DocBook/kernel-api.tmpl
+++ b/Documentation/DocBook/kernel-api.tmpl
@@ -43,6 +43,9 @@
      <sect1><title>Doubly Linked Lists</title>
 !Iinclude/linux/list.h
      </sect1>
+     <sect1><title>Red-Black Trees</title>
+!Iinclude/linux/rbtree.h
+     </sect1>
   </chapter>
 
   <chapter id="libc">
-- 
1.7.3.4

[PATCH v6 4/10] rbtree.h: Add test & validation framework

[Daniel Santos]

This introduces the following .config variables:

DEBUG_GRBTREE
DEBUG_GRBTREE_VALIDATE

DEBUG_GRBTREE will enable the use of the following new flags in struct
rb_relationship's flags member. When DEBUG_GRBTREE is not enabled in the
config, these flags will evaluate to zero.

RB_VERIFY_USAGE - Perform additional checks to assure that nodes are not
inserted into more than one tree by mistake, but adds the requirement
that nodes are initialized (rb_debug_clear_node) prior to insertion.

RB_VERIFY_INTEGRITY - Perform exhaustive integrity checks on tree during
most manipulation & access functions (high run-time overhead)

Finally, the DEBUG_GRBTREE_VALIDATE .config variable will force-enable
the RB_VERIFY_INTEGRITY behavior on all trees.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 include/linux/rbtree.h |  153 ++++++++++++++++++++++++++++++++++++++++++++---
 lib/Kconfig.debug      |   22 +++++++-
 2 files changed, 164 insertions(+), 11 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 48e325f..5f10915 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -85,7 +85,6 @@ 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
@@ -134,6 +133,18 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
  */
 #define OPT_OFFSETOF(type, member) IFF_EMPTY(member, 0, offsetof(type, member))
 
+
+#define GRBTREE_DEBUG IS_ENABLED(DEBUG_GRBTREE)
+#define GRBTREE_VALIDATE IS_ENABLED(DEBUG_GRBTREE_VALIDATE)
+
+/* keep disabled debug code out of older compilers that fail to optimize out
+ * const struct member values */
+#if GRBTREE_DEBUG
+# define __RB_DEBUG_ENABLE_MASK 0xffffffff
+#else
+# define __RB_DEBUG_ENABLE_MASK 0
+#endif
+
 /**
  * enum rb_flags - values for strct rb_relationship's flags
  * @RB_HAS_LEFTMOST:	The container has a struct rb_node *leftmost member
@@ -147,18 +158,47 @@ static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
  * @RB_INSERT_REPLACES:	When set, the rb_insert() will replace a value if it
  * 			matches the supplied one (valid only when
  * 			RB_UNIQUE_KEYS is set).
+ * @RB_VERIFY_USAGE:	Perform checks upon node insertion for a small run-time
+ * 			overhead. This has other usage restrictions, so read
+ * 			the Description section before using. Available only
+ * 			when CONFIG_DEBUG_GRBTREE is enabled.
+ * @RB_VERIFY_INTEGRITY:Perform exauhstive integrity checks on most operations
+ * 			(large run-time overhead). Available only when
+ * 			CONFIG_DEBUG_GRBTREE is enabled.
  * @RB_ALL_FLAGS:	(internal use)
+ *
+ *
+ * When RB_VERIFY_USAGE is set in the relationship flags and
+ * CONFIG_DEBUG_GRBTREE is enabled, you will be required to initialize nodes
+ * with rb_debug_clear_node() prior to inserting them (which is normally not
+ * necessary).  Upon insertion (rb_insert and rb_insert_near), additional
+ * checks will be performed to verify that the node is properly initialized and
+ * does not belong to another tree.  Upon removal (rb_remove) the node is
+ * re-initialized, so calling rb_debug_clear_node() is only required when you
+ * originally create the node.  If you remove it and re-add it multiple times
+ * (or to multiple trees) you do not have to manually re-initialize it.  This
+ * causes a small run-time overhead.
+ *
+ * When RB_VERIFY_INTEGRITY is set and CONFIG_DEBUG_GRBTREE is enabled,
+ * validation of tree integrity will occur in most functions.  As the tree is
+ * traversed downward, each child's parent link will be verified.  When the
+ * tree is traversed upwards (__rb_find_subtree) each parent's left or right
+ * link (respective to the traversal) will be verified.  Finally, when
+ * iterating over a tree, the compare function will be called to verify the
+ * order of elements.  This has a high run-time overhead.
  */
-
 enum rb_flags {
 	RB_HAS_LEFTMOST		= 0x00000001,
 	RB_HAS_RIGHTMOST	= 0x00000002,
 	RB_HAS_COUNT		= 0x00000004,
 	RB_UNIQUE_KEYS		= 0x00000008,
 	RB_INSERT_REPLACES	= 0x00000010,
+	RB_VERIFY_USAGE		= 0x00000080 & __RB_DEBUG_ENABLE_MASK,
+	RB_VERIFY_INTEGRITY	= 0x00000100 & __RB_DEBUG_ENABLE_MASK,
 	RB_ALL_FLAGS		= RB_HAS_LEFTMOST | RB_HAS_RIGHTMOST
 			| RB_HAS_COUNT | RB_UNIQUE_KEYS
-			| RB_INSERT_REPLACES,
+			| RB_INSERT_REPLACES
+			| RB_VERIFY_USAGE | RB_VERIFY_INTEGRITY,
 };
 
 /**
@@ -257,7 +297,6 @@ const void *rb_to_key(const void *ptr, const struct rb_relationship *rel)
 	return __RB_PTR(const void, ptr, rel->key_offset);
 }
 
-
 /* checked conversion functions that will error on run-time values */
 static __always_inline
 struct rb_root *__rb_to_root(const void *ptr,
@@ -367,6 +406,87 @@ void __rb_assert_good_rel(const struct rb_relationship *rel)
 }
 
 
+
+#if GRBTREE_DEBUG
+/* debug functions */
+
+/*
+ * __rb_verify_parent - validate a child's parent link
+ */
+static inline
+void __rb_verify_parent(const rb_node *child, const rb_node *parent,
+			const struct rb_relationship *rel)
+{
+	if ((rel->flags & RB_VERIFY_INTEGRITY) || GRBTREE_VALIDATE) {
+		BUG_ON(rb_parent(child) != parent);
+	}
+}
+
+/*
+ * __rb_verify_child - validate a parent's right or left link
+ */
+static inline
+void __rb_verify_child(const rb_node *parent, const rb_node *child,
+		       const int is_left, const struct rb_relationship *rel)
+{
+	BUILD_BUG_ON_NON_CONST(is_left);
+	if ((rel->flags & RB_VERIFY_INTEGRITY) || GRBTREE_VALIDATE) {
+		const rb_node *ptr = is_left ? parent->rb_left : parent->right;
+		BUG_ON(ptr != child);
+	}
+}
+
+/*
+ * __rb_verify_less - call compare function and verify node order
+ */
+static inline
+void __rb_verify_less(const rb_node *a, const rb_node *b,
+		      const struct rb_relationship *rel)
+{
+	if ((rel->flags & RB_VERIFY_INTEGRITY) || GRBTREE_VALIDATE) {
+		/* if we're using non-unique keys, diff can be zero */
+		const long max_diff = (rel->flags & RB_UNIQUE_KEYS) ? -1 : 0;
+		long diff = rel->compare(__rb_node_to_key(a, rel),
+					 __rb_node_to_key(a, rel))
+		BUG_ON(diff > max_diff);
+	}
+}
+
+/*
+ * __rb_verify_node_cleared - verify a node has been initialized/cleared
+ */
+static inline
+void __rb_verify_node_cleared(const rb_node *node,
+			      const struct rb_relationship *rel)
+{
+	if ((rel->flags & RB_VERIFY_USAGE) || GRBTREE_VALIDATE) {
+		BUG_ON(node->rb_parent_color != (unsigned long)node);
+		BUG_ON(node->rb_left != NULL);
+		BUG_ON(node->rb_right != NULL);
+	}
+}
+
+/**
+ * rb_debug_clear_node - clear a node (enabled when GRBTREE_DEBUG is set)
+ */
+static inline
+void rb_debug_clear_node(rb_node *node)
+{
+	node->__rb_parent_color = (unsigned long)node;
+	node->rb_left = NULL;
+	node->rb_right = NULL;
+}
+
+
+#else /* GRBTREE_DEBUG */
+# define __rb_verify_parent(child, parent, rel)		((void) 0)
+# define __rb_verify_child(parent, child, is_left, rel)	((void) 0)
+# define __rb_verify_less(a, b, rel)			((void) 0)
+# define __rb_verify_node_cleared(node, rel)		((void) 0)
+# define rb_debug_clear_node(node)			((void) 0)
+#endif /* GRBTREE_DEBUG */
+
+
 /**
  * __rb_find() - Perform a (normal) search on a Red-Black Tree, starting at the
  *		 specified node, traversing downward.
@@ -384,11 +504,13 @@ struct rb_node *__rb_find(
 	while (node) {
 		long diff = rel->compare(key, __rb_node_to_key(node, rel));
 
-		if (diff > 0)
+		if (diff > 0) {
+			__rb_verify_parent(node->rb_right, node, rel);
 			node = node->rb_right;
-		else if (diff < 0)
+		} else if (diff < 0) {
+			__rb_verify_parent(node->rb_left, node, rel);
 			node = node->rb_left;
-		else
+		} else
 			return node;
 	}
 
@@ -426,11 +548,13 @@ struct rb_node *__rb_find_first_last(
 	while (node) {
 		long diff = rel->compare(key, __rb_node_to_key(node, rel));
 
-		if (diff > 0)
+		if (diff > 0) {
+			__rb_verify_parent(node->rb_right, node, rel);
 			node = node->rb_right;
-		else if (diff < 0)
+		} else if (diff < 0) {
+			__rb_verify_parent(node->rb_left, node, rel);
 			node = node->rb_left;
-		else {
+		} else {
 			if (find_first && node->rb_left)
 				node = node->rb_left;
 			else if (!find_first && node->rb_right)
@@ -767,6 +891,7 @@ struct rb_node *rb_insert(
 #endif
 
 	__rb_assert_good_rel(rel);
+	__rb_verify_node_cleared(node, rel);
 
 
 	while (*p) {
@@ -845,6 +970,7 @@ struct rb_node *rb_insert_near(
 	long diff;
 
 	BUILD_BUG_ON_NON_CONST42(rel->flags);
+	__rb_verify_node_cleared(node, rel);
 
 	ret = __rb_find_subtree(root, start, key, &matched, &p, &parent, rel,
 				1);
@@ -917,6 +1043,11 @@ void rb_remove(
 
 	if ((rel->flags & RB_HAS_COUNT))
 		--*__rb_root_to_count(root, rel);
+
+	/* When RB_VERIFY_USAGE enabled, we re-init node upon removal */
+	if (GRBTREE_DEBUG && (rel->flags & RB_VERIFY_USAGE)) {
+		rb_debug_clear_node(node);
+	}
 }
 
 
@@ -1182,12 +1313,14 @@ obj_type *prefix ## _find_prev(const obj_type *obj)			\
 static __always_inline obj_type *prefix ## _next(const obj_type *obj)	\
 {									\
 	struct rb_node *ret = rb_next(&obj->node);			\
+	__rb_verify_less(&obj->node, ret, &prefix ## _rel);		\
 	return ret ? rb_entry(ret, obj_type, node) : 0;			\
 }									\
 									\
 static __always_inline obj_type *prefix ## _prev(const obj_type *obj)	\
 {									\
 	struct rb_node *ret = rb_prev(&obj->node);			\
+	__rb_verify_less(ret, &obj->node, &prefix ## _rel);		\
 	return ret ? rb_entry(ret, obj_type, node) : 0;			\
 }									\
 									\
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index 42cd4d8..0f42fd5 100644
--- a/lib/Kconfig.debug
+++ b/lib/Kconfig.debug
@@ -747,7 +747,7 @@ config DEBUG_KOBJECT
 	depends on DEBUG_KERNEL
 	help
 	  If you say Y here, some extra kobject debugging messages will be sent
-	  to the syslog. 
+	  to the syslog.
 
 config DEBUG_HIGHMEM
 	bool "Highmem debugging"
@@ -868,6 +868,26 @@ config TEST_LIST_SORT
 
 	  If unsure, say N.
 
+config DEBUG_GRBTREE
+	bool "Debug generic red-black trees"
+	depends on DEBUG_KERNEL
+	help
+	  Enables debug checks to red-black trees.  Enabling this parameter
+	  causes flags RB_VERIFY_USAGE and RB_VERIFY_INTEGRITY to become
+	  useable (see rbtree.h for more details).
+
+	  If unsure, say N.
+
+config DEBUG_GRBTREE_VALIDATE
+	bool "Generic Red-black tree validation"
+	depends on DEBUG_GRBTREE
+	help
+	  Perform exahustive checks on all generic red-black tree operations.
+	  This is the same as enabling the RB_VERIFY_INTEGRITY flag for all
+	  generic red-black trees.
+
+	  If unsure, say N.
+
 config DEBUG_SG
 	bool "Debug SG table operations"
 	depends on DEBUG_KERNEL
-- 
1.7.3.4

[PATCH v6 5/10] rbtree.h: add doc comments for struct rb_node

[Daniel Santos]

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 include/linux/rbtree.h |   14 ++++++++++++++
 1 files changed, 14 insertions(+), 0 deletions(-)

diff --git a/include/linux/rbtree.h b/include/linux/rbtree.h
index 5f10915..c815b5e 100644
--- a/include/linux/rbtree.h
+++ b/include/linux/rbtree.h
@@ -35,6 +35,20 @@
 #include <linux/bug.h>
 #include <linux/kconfig.h>
 
+/**
+ * struct rb_node
+ * @__rb_parent_color: Contains the color in the lower 2 bits (although only
+ * 		       bit zero is currently used) and the address of the
+ * 		       parent in the rest (lower 2 bits of address should
+ * 		       always be zero on any arch supported).  If the node is
+ * 		       initialized and not a member of any tree, the parent
+ * 		       point to its self.  If the node belongs to a tree, but
+ * 		       is the root element, the parent will be NULL.
+ * 		       Otherwise, parent will always point to the parent node
+ * 		       in the tree.
+ * @rb_right:          Pointer to the right element.
+ * @rb_left:           Pointer to the left element.
+ */
 struct rb_node {
 	unsigned long  __rb_parent_color;
 	struct rb_node *rb_right;
-- 
1.7.3.4

[PATCH v6 6/10] selftest: Add generic tree self-test common code.

[Daniel Santos]

Self-test code for both performance and correctness testing. The files
tools/testing/selftests/grbtree/common.{h,c} contain code for use in
both the user- and kernel-space test program/module and depends upon a
few functions being made available by said.

The purpose of these tests is to verify correctness across compilers and
document the performance difference between the generic and hand-coded
red-black tree implementations on various compilers, which is identified
as critical for determining feasibility of adding this this tree
implementation to the kernel, as older compilers optimize the generic
code more poorly than its hand-coded counterpart.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 tools/testing/selftests/grbtree/common.c |  892 ++++++++++++++++++++++++++++++
 tools/testing/selftests/grbtree/common.h |  293 ++++++++++
 2 files changed, 1185 insertions(+), 0 deletions(-)
 create mode 100644 tools/testing/selftests/grbtree/common.c
 create mode 100644 tools/testing/selftests/grbtree/common.h

diff --git a/tools/testing/selftests/grbtree/common.c b/tools/testing/selftests/grbtree/common.c
new file mode 100644
index 0000000..f5383be
--- /dev/null
+++ b/tools/testing/selftests/grbtree/common.c
@@ -0,0 +1,892 @@
+/* common.c - generic red-black tree test functions for use in both kernel and
+ * user space.
+ * 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.
+ */
+
+#include "common.h"
+
+#define _CONCAT2(a, b) a ## b
+#define _CONCAT(a, b) _CONCAT2(a, b)
+
+
+const char *grbtest_type_desc[GRBTEST_TYPE_COUNT] = {
+	"insertion performance",
+	"insertion & deletion performance",
+	"insertion validation"
+};
+
+#if GRBTEST_BUILD_GENERIC
+/****************************************************************************
+ * Generic Implementation
+ */
+
+#define __GRBTEST_FLAGS						\
+	((GRBTEST_UNIQUE_KEYS ? RB_UNIQUE_KEYS : 0) |		\
+	 (GRBTEST_INSERT_REPLACES ? RB_INSERT_REPLACES : 0))
+
+
+
+static inline long compare_s8(const s8 *a, const s8 *b) {return *a - *b;}
+static inline long greater_s8(const s8 *a, const s8 *b) {return *a > *b;}
+
+static inline long compare_u8(const u8 *a, const u8 *b) {return (long)*a - (long)*b;}
+static inline long greater_u8(const u8 *a, const u8 *b) {return *a > *b;}
+
+static inline long compare_s16(const s16 *a, const s16 *b) {return *a - *b;}
+static inline long greater_s16(const s16 *a, const s16 *b) {return *a > *b;}
+
+static inline long compare_u16(const u16 *a, const u16 *b) {return (long)*a - (long)*b;}
+static inline long greater_u16(const u16 *a, const u16 *b) {return *a > *b;}
+
+static inline long compare_s32(const s32 *a, const s32 *b) {return *a - *b;}
+static inline long greater_s32(const s32 *a, const s32 *b) {return *a > *b;}
+
+static inline long compare_u32(const u32 *a, const u32 *b) {return (long)*a - (long)*b;}
+static inline long greater_u32(const u32 *a, const u32 *b) {return *a > *b;}
+
+static inline long compare_s64(const s64 *a, const s64 *b) {return *a - *b;}
+static inline long greater_s64(const s64 *a, const s64 *b) {return *a > *b;}
+
+static inline long compare_u64(const u64 *a, const u64 *b) {return *a - *b;}
+static inline long greater_u64(const u64 *a, const u64 *b) {return *a > *b;}
+
+
+RB_DEFINE_INTERFACE(
+	mytree,
+	struct container, tree,
+#if GRBTEST_USE_LEFTMOST
+	leftmost
+#endif
+	,
+#if GRBTEST_USE_RIGHTMOST
+	rightmost
+#endif
+	,
+#if GRBTEST_USE_COUNT
+	count
+#endif
+	,
+	struct object, node, key,
+	__GRBTEST_FLAGS, _CONCAT(compare_, GRBTEST_KEY_TYPE),
+#if GRBTEST_UNIQUE_KEYS
+	_CONCAT(compare_, GRBTEST_KEY_TYPE),
+#else
+	_CONCAT(greater_, GRBTEST_KEY_TYPE),
+#endif
+	static __flatten inline,	/* find */
+	static __flatten inline,	/* insert */
+	static __flatten inline,	/* find_near */
+	static __flatten inline);	/* insert_near */
+
+
+#else /* GRBTEST_BUILD_GENERIC */
+
+/****************************************************************************
+ * Hand-coded Implementation
+ *
+ * This section implements the find, insert & remove functions as one would do
+ * so were they hand-coding it, except that we use pre-processor to include (or
+ * omit) the various features & rules.
+ *
+ * In order to account for compilers that may fail to optimize out a simple
+ * if(0) or if(1) construct, we'll make sure that such extra code is not
+ * generated by using these ugly pre-processor #ifs in this "hand-coded"
+ * section.  This makes the code prety ugly, but is percieved as necessary by
+ * the author for correctness. TODO: Is this overkill?
+ */
+
+static __always_inline struct object *mytree_find(struct container *cont, GRBTEST_KEY_TYPE *key)
+{
+	struct rb_node *node = cont->tree.rb_node;
+
+	while (node) {
+		struct object *obj = container_of(node, struct object, node);
+		if (*key > obj->key) {
+			node = node->rb_right;
+		} else if (*key < obj->key) {
+			node = node->rb_left;
+		} else
+			return obj;
+	}
+
+	return 0;
+}
+
+static __always_inline struct object *mytree_insert(struct container *cont,
+					   struct object *obj)
+{
+	struct rb_root *root   = &cont->tree;
+	struct rb_node **p     = &root->rb_node;
+	struct rb_node *parent = NULL;
+	GRBTEST_KEY_TYPE key   = obj->key;
+#if GRBTEST_UNIQUE_KEYS
+	struct rb_node *found;
+#endif
+#if GRBTEST_USE_LEFTMOST
+	int leftmost           = 1;
+#endif
+#if GRBTEST_USE_RIGHTMOST
+	int rightmost          = 1;
+#endif
+
+	while (*p) {
+		parent = *p;
+		GRBTEST_KEY_TYPE cur_key = container_of(*p, struct object, node)->key;
+
+		if (key < cur_key) {
+			p = &(*p)->rb_left;
+#if GRBTEST_USE_RIGHTMOST
+			rightmost = 0;
+#endif
+/* if not using/enforcing unique keys, the below test is superflorous */
+#if GRBTEST_UNIQUE_KEYS
+		} else if (key > cur_key) {
+#else
+		} else {
+#endif /* GRBTEST_UNIQUE_KEYS */
+			p = &(*p)->rb_right;
+#if GRBTEST_USE_LEFTMOST
+			leftmost = 0;
+#endif
+		}
+/* again, if not using unique keys, the if/else is completed above, and we
+ * never exit the loop until we find a leaf
+ */
+#if GRBTEST_UNIQUE_KEYS
+		  else
+			break;
+#endif
+	}
+
+
+#if GRBTEST_USE_LEFTMOST
+	if (leftmost)
+		cont->leftmost = *p;
+#endif
+
+#if GRBTEST_USE_RIGHTMOST
+	if (rightmost)
+		cont->rightmost = *p;
+#endif
+
+#if GRBTEST_UNIQUE_KEYS
+	found = *p;
+	if (found) {
+#if GRBTEST_INSERT_REPLACES
+		rb_replace_node(found, &obj->node, root);
+#endif
+
+		return container_of(found, struct object, node);
+	} else
+#endif /* GRBTEST_UNIQUE_KEYS */
+	{
+		rb_link_node(&obj->node, parent, p);
+		rb_insert_color(&obj->node, root);
+	}
+
+#if GRBTEST_USE_COUNT
+	++cont->count;
+#endif
+
+	return NULL;
+}
+
+static __always_inline void mytree_remove(struct container *cont, struct object *obj)
+{
+	struct rb_node *node = &obj->node;
+
+#if GRBTEST_USE_LEFTMOST
+	if (cont->leftmost == node)
+		cont->leftmost = rb_next(node);
+#endif
+
+#if GRBTEST_USE_RIGHTMOST
+	if (cont->rightmost == node)
+		cont->rightmost = rb_prev(node);
+#endif
+
+	rb_erase(node, &cont->tree);
+
+#if GRBTEST_USE_COUNT
+	--cont->count;
+#endif
+}
+
+
+#endif /* GRBTEST_BUILD_GENERIC */
+
+
+
+/****************************************************************************
+ * Test functions
+ */
+
+#define VALIDATE_PARAM(fmt, param, test)			\
+do {								\
+	if (unlikely(!(test))) {				\
+		print_err(#param " invalid: %" #fmt " (" #test ")\n", \
+				param);				\
+		return -EINVAL;					\
+	}							\
+} while(0)
+
+long grbtest_init(struct grbtest_config *config)
+{
+	long i;
+	void *rnd_state;
+
+	VALIDATE_PARAM(u, config->pool_count, config->pool_count);
+	VALIDATE_PARAM(u, config->object_count, config->object_count);
+
+	config->seed = config->in_seed;
+	rnd_state = rand_init(&config->seed);
+	if (!rnd_state) {
+		print_err("failed to init random number generator\n");
+		return -ENOMEM;
+	}
+
+	/* if already initialized, cleanup and start over */
+	if(objects.pools) {
+		grbtest_cleanup();
+	}
+
+	objects.pools        = malloc(sizeof(struct object *) *
+			       config->pool_count);
+	objects.pool_count   = config->pool_count;
+	objects.object_count = config->object_count;
+	objects.pool_size    = sizeof(struct object) * config->object_count;
+
+	if (0) {
+	print_err("allocating %u pools of %u objects (%lu bytes) each for a "
+		  "total of %lu bytes of memory.\n",
+		  config->pool_count, config->object_count,
+		  (unsigned long)objects.pool_size,
+		  (unsigned long)(config->pool_count * objects.pool_size));
+	}
+
+	for (i = 0; i != config->pool_count; ++i) {
+		objects.pools[i] = mem_alloc(objects.pool_size);
+		if (unlikely(!objects.pools[i])) {
+			print_err("out of memory, you probably did something "
+				  "stupid...\n");
+			objects.pool_count = i;
+			grbtest_cleanup();
+			return -ENOMEM;
+		}
+	}
+
+	/* initialize objects in all pools */
+	for (i = 0; i < config->pool_count; ++i) {
+		struct object *p = objects.pools[i];
+		struct object *end = &p[objects.object_count];
+
+		if (!i) {
+			/* pool zero gets random keys */
+			for (; p != end; ++p)
+				init_object(p, rand() & config->key_mask);
+		} else {
+			/* remaining pools copy keys from pool zero */
+			const struct object *p0 = objects.pools[0];
+			for (; p != end; ++p, ++p0)
+				init_object(p, p0->key);
+		}
+	}
+
+	return 0;
+}
+
+void grbtest_cleanup()
+{
+	BUG_ON(!objects.pools);
+
+	while (objects.pool_count--)
+		mem_free(objects.pools[objects.pool_count]);
+	mem_free(objects.pools);
+
+	memset(&objects, 0, sizeof(objects));
+	objects.pools	     = NULL;
+	objects.pool_count   = 0;
+	objects.object_count = 0;
+	objects.pool_size    = 0;
+}
+
+long reset_objects(unsigned int pool_count) {
+	unsigned i;
+
+	VALIDATE_PARAM(u, pool_count, pool_count <= objects.pool_count);
+
+	for (i = 0; i < pool_count; ++i) {
+		struct object *p = objects.pools[i];
+		struct object *end = &p[objects.object_count];
+
+		for (; p != end; ++p) {
+			grbtest_init_node(&p->node);
+		}
+	}
+
+	return 0;
+}
+
+long grbtest_run_test(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont)
+{
+	grbtest_init_results(config, result);
+
+	switch (config->test) {
+		case GRBTEST_TYPE_INSERTION:
+			return grbtest_perftest(config, result, cont, 0);
+
+		case GRBTEST_TYPE_INSERTION_DELETION:
+			return grbtest_perftest(config, result, cont, 1);
+
+		case GRBTEST_TYPE_VALIDATE_INSERTIONS:
+			return grbtest_validate_insertion(config, result, cont);
+
+		default:
+			print_err("Invalid test specified");
+			return -1;
+	}
+}
+
+/* flatten needed for gcc 4.3.x, that otherwise fails to inline mytree_insert */
+__flatten
+long grbtest_perftest(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont,
+		int do_deletes)
+{
+	u64 start_time, end_time;
+	struct object *p, *start, *evicted;
+	const struct object *end;
+	unsigned i;
+	unsigned pool = 0;
+
+	VALIDATE_PARAM(u, pool, pool < objects.pool_count);
+	VALIDATE_PARAM(u, config->object_count, config->object_count
+		<= objects.object_count);
+
+	start = objects.pools[pool];
+	end = &objects.pools[pool][config->object_count];
+
+	if (!do_deletes) {
+		/* profile insertions with cheap container purge */
+
+		start_time = getCurTicks();
+		for (i = 0; i < config->reps; ++i) {
+			init_container(cont);
+
+			for (p = start; p != end; ++p) {
+				if (mytree_insert(cont, p))
+					++result->evictions;
+			}
+		}
+
+		result->insertion_time += (u64)(getCurTicks() - start_time);
+		result->insertions += config->reps * config->object_count;
+	} else {
+		/* profile insertions & deletions */
+
+		for (i = 0; i < config->reps; ++i) {
+			init_container(cont);
+
+			/* populate tree */
+			start_time = getCurTicks();
+			for (p = start; p != end; ++p) {
+				if ((evicted = mytree_insert(cont, p))) {
+					evicted->node.__rb_parent_color =
+						(unsigned long)&evicted->node;
+					++result->evictions;
+				}
+			}
+
+			end_time = getCurTicks();
+			result->insertion_time += (u64)(end_time - start_time);
+
+			/* remove items from tree */
+			start_time = end_time;
+			for (p = start; p != end; ++p) {
+				if (p->node.__rb_parent_color !=
+						(unsigned long)&p->node) {
+					mytree_remove(cont, p);
+					++result->deletions;
+				}
+			}
+
+			end_time = getCurTicks();
+			result->deletion_time += (u64)(end_time - start_time);
+
+			/* tree should now be empty */
+			BUG_ON(cont->tree.rb_node != NULL);
+		}
+		result->insertions = config->reps * config->object_count;
+	}
+
+	return 0;
+}
+
+
+long grbtest_validate_insertion(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont)
+{
+	struct object *p, *near;
+	struct object *start = objects.pools[0];
+	const struct object *end;
+	u64 start_time;
+	unsigned num_nodes;
+	unsigned pool = 0;
+
+	VALIDATE_PARAM(u, config->object_count, config->object_count
+		<= objects.object_count);
+	VALIDATE_PARAM(u, pool, pool < objects.pool_count);
+	/* currently ignored, pass zero for now */
+	VALIDATE_PARAM(u, config->reps, !config->reps);
+
+	start_time = getCurTicks();
+	for (num_nodes = 1; num_nodes <= config->object_count; ++num_nodes) {
+		end = &start[num_nodes];
+		init_container(cont);
+		reset_objects(1);
+
+		for (p = start; p != end; ++p) {
+			struct object *evicted = mytree_insert(cont, p);
+
+#if 0
+			if (evicted && (mytree_rel.flags & RB_UNIQUE_KEYS)
+				    && (mytree_rel.flags & RB_INSERT_REPLACES)) {
+#endif
+			if (evicted && GRBTEST_INSERT_REPLACES) {
+				++result->evictions;
+				grbtest_init_node(&evicted->node);
+			}
+		}
+
+		/* make sure we can find them */
+		for (p = start; p != end; ++p) {
+			struct object *found = mytree_find(cont, &p->key);
+
+			/* if the object is inserted, it should be there */
+			if (is_inserted(p)) {
+				BUG_ON(found != p);
+			/* otherwise, it was evicted and shouldn't be there */
+			} else {
+#if GRBTEST_BUILD_GENERIC
+				BUG_ON(!(mytree_rel.flags & RB_UNIQUE_KEYS));
+#else
+				BUG_ON(!GRBTEST_UNIQUE_KEYS);
+#endif
+				BUG_ON(found == p);
+			}
+		}
+
+		/* make sure we can find_near them */
+		for (near = start; near != end; ++near) {
+
+			/* we wont use a non-inserted object for a near search */
+			if (!is_inserted(near)) {
+#if GRBTEST_BUILD_GENERIC
+				BUG_ON(!(mytree_rel.flags & RB_UNIQUE_KEYS));
+#else
+				BUG_ON(!GRBTEST_UNIQUE_KEYS);
+#endif
+				continue;
+			}
+
+/* we're not doing find_near on hand-coded stuff */
+#if GRBTEST_BUILD_GENERIC
+			for (p = start; p != end; ++p) {
+				struct object *found =
+					mytree_find_near(near, &p->key);
+
+				if (is_inserted(p)) {
+					BUG_ON(found != p);
+				} else {
+					BUG_ON(!(mytree_rel.flags & RB_UNIQUE_KEYS));
+					BUG_ON(found == p);
+				}
+			}
+#endif /* GRBTEST_BUILD_GENERIC */
+		}
+
+		/* walk the tree and verify order using compare function */
+		for (near = start; near != end; ++near) {
+			// count objects
+			// count inserted objects using start -> end and make sure they match
+			// verify count field
+
+		}
+
+		/* now we'll delete them and make sure they are removed */
+		for (near = start; near != end; ++near) {
+
+		}
+
+	}
+	result->insertion_time += (u64)(getCurTicks() - start_time);
+
+	return 0;
+}
+
+
+/****************************************************************************
+ * Test result functions
+ */
+
+void grbtest_init_results(const struct grbtest_config *config,
+			  struct grbtest_result *result)
+{
+	memset(result, 0, sizeof(*result));
+	result->node_size   = sizeof(struct rb_node);
+	result->object_size = sizeof(struct object);
+	result->pool_size   = sizeof(struct object) * config->object_count;
+}
+
+void grbtest_print_result_header(const struct grbtest_config *config)
+{
+	const char *d = config->delimiter;
+	/* compile-time config */
+	print_msg("compiler%s",		d);
+	print_msg("key_type%s",		d);
+	print_msg("payload%s",		d);
+	print_msg("userland%s",		d);
+	print_msg("use_generic%s",	d);
+	print_msg("use_leftmost%s",	d);
+	print_msg("use_rightmost%s",	d);
+	print_msg("use_count%s",	d);
+	print_msg("unique_keys%s",	d);
+	print_msg("insert_replaces%s",	d);
+	print_msg("debug%s",		d);
+	print_msg("debug_validate%s",	d);
+	print_msg("arch%s",		d);
+	print_msg("arch_flags%s",	d);
+	print_msg("processor%s",	d);
+	print_msg("cc%s",		d);
+	print_msg("cflags%s",		d);
+
+	/* run-time config */
+	print_msg("test%s",		d);
+	print_msg("in_seed%s",		d);
+	print_msg("seed%s",		d);
+	print_msg("key_mask%s",		d);
+	print_msg("object_count%s",	d);
+	print_msg("pool_count%s",	d);
+	print_msg("reps%s",		d);
+	/* fields human_readable, delimiter, text_enclosure
+	 * and print_header omited */
+
+	/* result */
+	print_msg("node_size%s",	d);
+	print_msg("object_size%s",	d);
+	print_msg("pool_size%s",	d);
+	print_msg("insertions%s",	d);
+	print_msg("insertion_time%s",	d);
+	print_msg("evictions%s",	d);
+	print_msg("deletions%s",	d);
+	print_msg("deletion_time\n");
+}
+
+void grbtest_print_result_row(const struct grbtest_config *config,
+			      const struct grbtest_result *result)
+{
+	const char *d = config->delimiter;
+	const char *q = config->text_enclosure;
+
+	/* FIXME: Will formating u64 as "%llu" wont be correct on all
+	 * architectures?
+	 */
+	/* compile-time config */
+	print_msg("%s" GRBTEST_COMPILER "%s%s",			q, q, d);
+	print_msg("%s" __stringify(GRBTEST_KEY_TYPE) "%s%s",	q, q, d);
+	print_msg(__stringify(GRBTEST_PAYLOAD) "%s",		d);
+	print_msg(__stringify(GRBTEST_USERLAND) "%s",		d);
+	print_msg(__stringify(GRBTEST_BUILD_GENERIC) "%s",	d);
+	print_msg(__stringify(GRBTEST_USE_LEFTMOST) "%s",	d);
+	print_msg(__stringify(GRBTEST_USE_RIGHTMOST) "%s",	d);
+	print_msg(__stringify(GRBTEST_USE_COUNT) "%s",		d);
+	print_msg(__stringify(GRBTEST_UNIQUE_KEYS) "%s",	d);
+	print_msg(__stringify(GRBTEST_INSERT_REPLACES) "%s",	d);
+	print_msg(__stringify(config_enabled(CONFIG_DEBUG_GRBTREE)) "%s",		d);
+	print_msg(__stringify(config_enabled(CONFIG_DEBUG_GRBTREE_VALIDATE)) "%s",	d);
+	print_msg("%s" __stringify(GRBTEST_ARCH) "%s%s",	q, q, d);
+	print_msg("%s" __stringify(GRBTEST_ARCH_FLAGS) "%s%s",	q, q, d);
+	print_msg("%s" __stringify(GRBTEST_PROCESSOR) "%s%s",	q, q, d);
+	print_msg("%s" __stringify(GRBTEST_CC) "%s%s",		q, q, d);
+	print_msg("%s" __stringify(GRBTEST_CFLAGS) "%s%s",	q, q, d);
+
+	/* run-time config */
+	print_msg("%u%s",	config->test, d);
+	print_msg("%llu%s",	(unsigned long long)config->in_seed, d);
+	print_msg("%llu%s",	(unsigned long long)config->seed, d);
+	print_msg("%u%s",	config->key_mask, d);
+	print_msg("%u%s",	config->object_count, d);
+	print_msg("%u%s",	config->pool_count, d);
+	print_msg("%u%s",	config->reps, d);
+
+	/* result */
+	print_msg("%u%s",	result->node_size, d);
+	print_msg("%u%s",	result->object_size, d);
+	print_msg("%u%s",	result->pool_size, d);
+	print_msg("%llu%s",	(unsigned long long)result->insertions, d);
+	print_msg("%llu%s",	(unsigned long long)result->insertion_time, d);
+	print_msg("%llu%s",	(unsigned long long)result->evictions, d);
+	print_msg("%llu%s",	(unsigned long long)result->deletions, d);
+	print_msg("%llu\n",	(unsigned long long)result->deletion_time);
+}
+
+#if 0
+
+int retrieve_from_empty_container()
+{
+	return 0;
+}
+Requirements for Generic Red-Black Tree tests
+
+Correctness testing
+Input parameters
+max_nodes - maximum number of nodes to use for tests
+
+Create an array of max_nodes objects and initialize their keys to random values.
+Start from a tree with zero objects and perform lookups of non-existant objects (which should all return NULL).
+
+int num_nodes;
+int i;
+
+/* correctness tests */
+for (int num_nodes = 0; i < max_nodes; ++num_nodes) {
+	// clear tree
+	for (i = 0; i < num_nodes; ++ i) {
+		// insert nodes
+	}
+	// insert a node with an existing key and verify outcome
+	for (i = 0; i < num_nodes; ++i) {
+		// find object i and verify outcome
+		for (j = 0; j < num_nodes; ++j) {
+			// perform find_near starting at i, looking for j
+			// and verify outcome
+		}
+		// delete object i & verify
+		// re-insert object i & verify
+	}
+	for (i = 0; i < num_nodes; ++i) {
+		// delete node i
+		// search for node i and make sure we get nothing
+		// search for next node and make sure we get one
+	}
+	// verify that tree is empty
+
+	// insert node zero
+	for (i = 1; i < num_nodes; ++ i) {
+		// insert_near, using previous node as start
+	}
+	// verify tree
+
+	// repeat find tests above
+}
+
+/* performance tests */
+int reps;  /* number of times to repeat a test */
+for (int num_nodes = 0; i < max_nodes; ++num_nodes) {
+	for (rep = 0; rep < reps; ++rep) {
+		// clear tree
+		// get start time
+		for (i = 0; i < num_nodes; ++ i) {
+			// insert nodes
+		}
+		// get end time & add
+	}
+}
+// insertion test
+// insert near test (separate data for each size, for each node distance)
+// insert replace test
+// find test
+// find_near test (again, for each size, for each node distance)
+
+__attribute__((flatten))
+long run_test(unsigned int count) {
+	size_t buf_size = sizeof(struct object) * count;
+	struct container cont;
+	struct object *obj_pools[2];
+	struct object **tree_contents;
+	size_t pool_size;
+	int pool_in_use;
+	long i, j, k;
+	struct object *found;
+	struct rb_node *node;
+	long long start, end;
+
+	long long now = getCurTicks();
+
+	srand((now & 0xffffffff) ^ (now >> 32));
+
+	if (count < 1 || count > 0x1000000) { /* 16.8 million should be a reasonable limit */
+		return -1;
+	}
+
+	print_err("allocating two pools of %u objects each\n", count);
+
+	cont.tree      = RB_ROOT;
+	cont.count     = 0;
+	cont.leftmost  = 0;
+	cont.rightmost = 0;
+	pool_in_use      = 0;
+	obj_pools[0]     = (struct object *)malloc(buf_size);
+	obj_pools[1]     = (struct object *)malloc(buf_size);
+
+	fprintf(stderr, "initializing objects\n");
+
+	/* init a psudo-random using a real-random seed */
+//	get_random_bytes(&seed, sizeof(seed));
+//	prandom32_seed(&grbtest.rand, seed);
+
+	for (i = 0; i < 2; ++i) {
+		struct object *p = obj_pools[i];
+		struct object *end = &p[count];
+
+		for (; p != end; ++p) {
+			p->id = rand() & 0xfffff;
+			rb_init_node(&p->node);
+		}
+	}
+	pool_size = count;
+
+	for (j = 0; j < 2; ++j) {
+		struct object *pool = obj_pools[j];
+		start = getCurTicks();
+
+		for (i = count; i; ) {
+			struct object *new = &pool[--i];
+
+			mytree_insert(&cont, new);
+		}
+		pool_in_use ^= 1;
+		end = getCurTicks();
+		fprintf(stderr, "Inserted %u objects in %llu\n", count, end - start);
+	}
+
+	fprintf(stderr, "walking tree now...\n");
+	tree_contents = (struct object **)malloc(sizeof(void*) * cont.count);
+	start = getCurTicks();
+	for (i = 0, node = cont.leftmost; node; node = rb_next(node), ++i) {
+		tree_contents[i] = rb_entry(node, struct object, node);
+	}
+	end = getCurTicks();
+	fprintf(stderr, "Finished walking tree of %u in %llu\n", cont.count, end - start);
+
+	fprintf(stderr, "root = %p, count = %u\n", cont.tree.rb_node, cont.count);
+	//dumpNode(cont.tree.rb_node);
+
+	//dumpTree(&cont.tree, 16);
+	start = getCurTicks();
+#define NEAR_RANGE 8
+#if 0
+	for (i = 0; i < cont.count; ++i) {
+		for (j = 0; j < cont.count; ++j) {
+			found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+#else
+for (k = 0; k < 8; ++k) {
+	for (i = 0; i < cont.count; ++i) {
+		int max = i + NEAR_RANGE;
+		if (max > cont.count)
+			max = cont.count;
+		for (j = i > NEAR_RANGE ? i - NEAR_RANGE : 0;
+		     j < max; ++j) {
+			found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+}
+
+#endif
+	end = getCurTicks();
+	fprintf(stderr, "find_near duration = %llu\n", end - start);
+
+	start = getCurTicks();
+for (k = 0; k < 8; ++k) {
+	for (i = 0; i < cont.count; ++i) {
+		int max = i + NEAR_RANGE;
+		if (max > cont.count)
+			max = cont.count;
+		for (j = i > NEAR_RANGE ? i - NEAR_RANGE : 0;
+		     j < max; ++j) {
+			found = mytree_find(&cont, &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+}
+
+	end = getCurTicks();
+	fprintf(stderr, "find duration = %llu\n", end - start);
+
+	// cleanup
+
+	fprintf(stderr, "Forward iteration (%u objects)\n", cont.count);
+	for (node = cont.leftmost; node ; node = rb_next(node)) {
+		struct object *obj = (struct object *)__rb_node_to_obj(node, &mytree_rel);
+		//fprintf(stderr, "id = 0x%08x\n", obj->id);
+	}
+
+	fprintf(stderr, "Reverse iteration (%u objects)\n", cont.count);
+	for (node = cont.rightmost; node ; node = rb_prev(node)) {
+		struct object *obj = (struct object *)__rb_node_to_obj(node, &mytree_rel);
+		//fprintf(stderr, "id = 0x%08x\n", obj->id);
+	}
+
+
+	fprintf(stderr, "Starting cleanup, %u objects\n", cont.count);
+	while (cont.leftmost) {
+		struct object *obj = (struct object *)__rb_node_to_obj(cont.leftmost, &mytree_rel);
+		//fprintf(stderr, "Removing object at 0x%p id = 0x%04x\n", obj, obj->id);
+		mytree_remove(&cont, obj);
+		//--cont.count;
+	}
+
+	if(obj_pools[0]) {
+		free(obj_pools[0]);
+		free(obj_pools[1]);
+		obj_pools[0] = 0;
+		obj_pools[1] = 0;
+		free(tree_contents);
+	}
+	pool_in_use = 0;
+	cont.leftmost = 0;
+	cont.rightmost = 0;
+
+
+	fprintf(stderr, "Cleanup complete, %u objects left in container.\n", cont.count);
+
+	return 0;
+}
+#endif
diff --git a/tools/testing/selftests/grbtree/common.h b/tools/testing/selftests/grbtree/common.h
new file mode 100644
index 0000000..8a23dcc
--- /dev/null
+++ b/tools/testing/selftests/grbtree/common.h
@@ -0,0 +1,293 @@
+/* common.h - generic red-black tree test functions for use in both kernel and
+ * user space.
+ * 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.
+ */
+
+/**
+ * The following preprocessor variables should be defined to either 1 or 0 when
+ * compiling common.{c,h}
+ *
+ * GRBTEST_KEY_TYPE		FIXME: doc me
+ * GRBTEST_PAYLOAD		FIXME: doc me
+ * GRBTEST_USERLAND		If non-zero, compile for userspace, kernelspace
+ * 				otherwise.
+ * GRBTEST_BUILD_GENERIC	If non-zero, use generic implementation,
+ * 				otherwise, use hand-coded implementation.
+ * GRBTEST_USE_LEFTMOST		Maintain a pointer to the leftmost (smallest)
+ * 				in all insert & delete operations.
+ * GRBTEST_USE_RIGHTMOST	Same as above, except for rightmost (greatest)
+ * 				value
+ * GRBTEST_USE_COUNT		Maintain a count of objects in tree
+ * GRBTEST_UNIQUE_KEYS		If non-zero, tree contains only unique keys.
+ * GRBTEST_INSERT_REPLACES	Valid only if GRBTEST_UNIQUE_KEYS is non-zero.
+ * 				If non-zero, insert function will replace any
+ * 				existing object with the same key.
+ *
+ * The following preprocessor variables are generated automatically, either by the Makefile, the kernel's .config or in this header:
+ *
+ * GRBTEST_COMPILER
+ * CONFIG_DEBUG_RBTREE
+ * CONFIG_DEBUG_RBTREE_VALIDATE
+ * GRBTEST_CFLAGS
+ * GRBTEST_CC
+ */
+#ifndef _GRBTESTCOMMON_H
+#define _GRBTESTCOMMON_H
+
+#include <linux/rbtree.h>
+#include <linux/stringify.h>
+
+#ifndef GRBTEST_KEY_TYPE
+# error GRBTEST_KEY_TYPE not defined
+#endif
+#ifndef GRBTEST_PAYLOAD
+# error GRBTEST_PAYLOAD not defined
+#endif
+#ifndef GRBTEST_USERLAND
+# error GRBTEST_USERLAND not defined
+#endif
+#ifndef GRBTEST_BUILD_GENERIC
+# error GRBTEST_BUILD_GENERIC not defined
+#endif
+#ifndef GRBTEST_USE_LEFTMOST
+# error GRBTEST_USE_LEFTMOST not defined
+#endif
+#ifndef GRBTEST_USE_RIGHTMOST
+# error GRBTEST_USE_RIGHTMOST not defined
+#endif
+#ifndef GRBTEST_USE_COUNT
+# error GRBTEST_USE_COUNT not defined
+#endif
+#ifndef GRBTEST_UNIQUE_KEYS
+# error GRBTEST_UNIQUE_KEYS not defined
+#endif
+#ifndef GRBTEST_INSERT_REPLACES
+# error GRBTEST_INSERT_REPLACES not defined
+#endif
+
+#if 0
+#ifndef GRBTEST_COL_DELIMITER_STR
+# define GRBTEST_COL_DELIMITER_STR ","
+#endif
+#ifndef GRBTEST_ROW_DELIMITER_STR
+# define GRBTEST_ROW_DELIMITER_STR "\n"
+#endif
+#ifndef GRBTEST_OPEN_QUOTE_STR
+# define GRBTEST_OPEN_QUOTE_STR ""
+#endif
+#ifndef GRBTEST_CLOSE_QUOTE_STR
+# define GRBTEST_CLOSE_QUOTE_STR ""
+#endif
+#endif
+
+#ifdef __GNUC__
+# define GCC_VERSION_STR			\
+		__stringify(__GNUC__) "."	\
+		__stringify(__GNUC_MINOR__) "."	\
+		__stringify(__GNUC_PATCHLEVEL__)
+# ifdef __INTEL_COMPILER
+#  define GRBTEST_COMPILER "intel "		\
+		__stringify(__INTEL_COMPILER)	\
+		" (gcc-" GCC_VERSION_STR ")"
+# else
+#  define GRBTEST_COMPILER "gcc-" GCC_VERSION_STR
+# endif
+#else
+/* NOTE: Add support for other compilers here */
+# define GRBTEST_COMPILER "non-gcc"
+#endif
+
+
+/**
+ * grbtest_config - Returns a string describing the build configuration.
+ */
+static inline const char *grbtest_config(void)
+{
+	return
+		"compiler        " GRBTEST_COMPILER "\n"
+#if GRBTEST_BUILD_GENERIC
+		"type            generic\n"
+#else
+		"type            hand-coded\n"
+#endif
+		"key type        " __stringify(GRBTEST_KEY_TYPE) "\n"
+		"payload         char[" __stringify(GRBTEST_PAYLOAD) "]\n"
+		"use leftmost    " __stringify(GRBTEST_USE_LEFTMOST) "\n"
+		"use rightmost   " __stringify(GRBTEST_USE_RIGHTMOST) "\n"
+		"use count       " __stringify(GRBTEST_USE_COUNT) "\n"
+		"unique keys     " __stringify(GRBTEST_UNIQUE_KEYS) "\n"
+		"insert replaces " __stringify(GRBTEST_INSERT_REPLACES) "\n"
+		__stringify(config_enabled(CONFIG_DEBUG_GRBTREE)) "\n"
+		"DEBUG_RBTREE_VALIDATE "
+		__stringify(config_enabled(CONFIG_DEBUG_GRBTREE_VALIDATE)) "\n"
+		"CFLAGS          " __stringify(GRBTEST_CFLAGS) "\n"
+		"CC              " __stringify(GRBTEST_CC) "\n";
+}
+
+/* Functions provided by {module,user}/facilities.c for common.c */
+
+extern void facilities_init(void);
+extern u64 getCurTicks(void);
+extern void *rand_init(u64 *seed);
+
+//typedef unsigned int uint;
+
+
+#if GRBTEST_USERLAND
+#   define print_msg(...)	printf(__VA_ARGS__)
+#   define print_err(...)	fprintf(stderr, __VA_ARGS__)
+
+static inline void *mem_alloc(size_t size)	{return malloc(size);}
+static inline void mem_free(void *ptr)		{return free(ptr);}
+static inline u32 rand_get(void *state) 	{return rand();}
+static inline void rand_free(void *state)	{}
+
+#else /* GRBTEST_USERLAND */
+
+#    define print_msg(...) printk("grbtest: " __VA_ARGS__)
+#    define print_err(...) printk(KERN_ALERT "grbtest: " __VA_ARGS__)
+
+static inline void *mem_alloc(size_t size) {return kzalloc(size, GFP_KERNEL);}
+static inline void mem_free(void *ptr)	   {return kfree(ptr);}
+static inline u32 rand_get(struct rnd_state *state) {return prandom32(state);}
+static inline void rand_free(struct rnd_state *state) {kzfree(state);}
+
+#endif
+
+/****************************************************************************
+ * Structures
+ */
+
+struct object {
+	struct rb_node	node;
+	GRBTEST_KEY_TYPE key;
+	unsigned char	payload[GRBTEST_PAYLOAD];
+};
+
+struct container {
+	struct rb_root	tree;
+	unsigned int	count;
+	struct rb_node	*leftmost;
+	struct rb_node	*rightmost;
+	unsigned int	pool_in_use;
+};
+
+struct object_pools {
+	struct object	**pools;
+	unsigned int	pool_count;	/**< number of pools */
+	unsigned int	object_count;	/**< num objects in each pool */
+	size_t		pool_size;	/**< size of each pool in bytes */
+};
+
+enum grbtest_type {
+	GRBTEST_TYPE_INSERTION,
+	GRBTEST_TYPE_INSERTION_DELETION,
+	GRBTEST_TYPE_VALIDATE_INSERTIONS,
+	GRBTEST_TYPE_COUNT
+};
+
+extern const char *grbtest_type_desc[GRBTEST_TYPE_COUNT];
+
+struct grbtest_config {
+	enum grbtest_type test;
+	u64		  in_seed;
+	u64		  seed;
+	u32		  key_mask;
+	unsigned	  object_count;
+	unsigned	  pool_count;
+	unsigned	  reps;
+	int		  human_readable;
+	char		 *delimiter;
+	char		 *text_enclosure;
+	int		  print_header;
+};
+
+struct grbtest_result {
+	unsigned	node_size;
+	unsigned	object_size;
+	unsigned	pool_size;
+	u64		insertions;
+	u64		insertion_time;
+	u64		evictions;
+	u64		deletions;
+	u64		deletion_time;
+};
+
+/****************************************************************************
+ * Global data
+ */
+
+extern struct object_pools objects;
+
+
+static void inline init_container(struct container *cont)
+{
+	cont->tree	= RB_ROOT;
+	cont->count	= 0;
+	cont->leftmost	= 0;
+	cont->rightmost	= 0;
+}
+
+static inline void grbtest_init_node(struct rb_node *node)
+{
+	node->__rb_parent_color = (unsigned long)node;
+	node->rb_right = NULL;
+	node->rb_left = NULL;
+}
+
+static inline int grbtest_node_is_clear(const struct rb_node *node)
+{
+	return (node->__rb_parent_color == (unsigned long)node)
+	       && (node->rb_right == NULL)
+	       && (node->rb_left == NULL);
+}
+
+static inline void init_object(struct object *obj, GRBTEST_KEY_TYPE key)
+{
+	grbtest_init_node(&obj->node);
+	obj->key = key;
+}
+
+static int inline is_inserted(struct object *obj)
+{
+	return rb_parent(&obj->node) != &obj->node;
+}
+
+/* exported by common.c */
+extern long grbtest_init(struct grbtest_config *config);
+extern void grbtest_cleanup(void);
+extern long grbtest_run_test(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont);
+extern long grbtest_perftest(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont,
+		int do_deletes);
+extern long grbtest_validate_insertion(
+		struct grbtest_config *config,
+		struct grbtest_result *result,
+		struct container *cont);
+
+extern void grbtest_init_results(const struct grbtest_config *config,
+				 struct grbtest_result *result);
+extern void grbtest_print_result_header(const struct grbtest_config *config);
+extern void grbtest_print_result_row(const struct grbtest_config *config,
+				     const struct grbtest_result *result);
+
+#endif /* _GRBTESTCOMMON_H */
-- 
1.7.3.4

[PATCH v6 7/10] selftest: Add userspace test program.

[Daniel Santos]

Userspace test program using code from common.{c,h}.  Userspace
compliation is accomplished by ovreriding a few kernel headers in the
overrides directory.  This is an invasive hack (involving many internals
of kernel headers) that is expected to require fairly frequent
maintainence as kernel headers change.

The program grbtest can be run with -h option for help and outputs both
a human-readable format as well as a delimited text for more extensive
processing.

The exact behavior of the grbtest program depends upon the following
pre-processor variables, which the Makefile expects to be -Defined in a
CONFIG variable. Each variable should be assigned a value of 1 or 0, as
documented in common.h. If CONFIG is not set, a default is assigned in
the Makefile.

GRBTEST_KEY_TYPE
GRBTEST_PAYLOAD
GRBTEST_BUILD_GENERIC
GRBTEST_USE_LEFTMOST
GRBTEST_USE_RIGHTMOST
GRBTEST_USE_COUNT
GRBTEST_UNIQUE_KEYS
GRBTEST_INSERT_REPLACES

Generation of the resultant executable is also dependent upon the below
.config values.

DEBUG_GRBTREE
DEBUG_GRBTREE_VALIDATE

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 tools/testing/selftests/grbtree/user/Makefile      |   68 +++
 tools/testing/selftests/grbtree/user/facilities.c  |   58 ++
 tools/testing/selftests/grbtree/user/main.c        |  621 ++++++++++++++++++++
 .../grbtree/user/overrides/linux/export.h          |   31 +
 .../grbtree/user/overrides/linux/kernel.h          |   83 +++
 5 files changed, 861 insertions(+), 0 deletions(-)
 create mode 100644 tools/testing/selftests/grbtree/user/Makefile
 create mode 100644 tools/testing/selftests/grbtree/user/facilities.c
 create mode 100644 tools/testing/selftests/grbtree/user/main.c
 create mode 100644 tools/testing/selftests/grbtree/user/overrides/linux/export.h
 create mode 100644 tools/testing/selftests/grbtree/user/overrides/linux/kernel.h

diff --git a/tools/testing/selftests/grbtree/user/Makefile b/tools/testing/selftests/grbtree/user/Makefile
new file mode 100644
index 0000000..14380c2
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/Makefile
@@ -0,0 +1,68 @@
+# Default configuration (used if CONFIG not supplied)
+# See common.h for docs
+CONFIG ?= -DGRBTEST_KEY_TYPE=u32	\
+	  -DGRBTEST_PAYLOAD=0		\
+	  -DGRBTEST_BUILD_GENERIC=0	\
+	  -DGRBTEST_USE_LEFTMOST=1	\
+	  -DGRBTEST_USE_RIGHTMOST=1	\
+	  -DGRBTEST_USE_COUNT=1		\
+	  -DGRBTEST_UNIQUE_KEYS=1	\
+	  -DGRBTEST_INSERT_REPLACES=1
+
+ifeq ($(KERNELRELEASE),)
+    # Assume the source tree is where the running kernel was built
+    # You should set KERNELDIR in the environment if it's elsewhere
+    KERNELDIR ?= /lib/modules/$(shell uname -r)/build
+endif
+
+PWD := $(shell pwd)
+
+# The below KERNEL_ARCH works on x86_64, but hasn't been tested elsewhere
+# (e.g., x86 32-bit, ARM, etc.)
+KERNEL_ARCH	 = $(shell uname -m | sed 's/x86_64/x86/')
+
+# Kernel include directories
+KERNEL_INCLUDES	 = -I$(KERNELDIR)/include \
+		   -I$(KERNELDIR)/arch/$(KERNEL_ARCH)/include
+CPPFLAGS	+= -DGRBTEST_USERLAND=1 -D__KERNEL__ -I$(PWD)/.. \
+		   -I$(PWD)/overrides $(KERNEL_INCLUDES) $(CONFIG)
+WARN_FLAGS	 = -Wall -Wundef -Wstrict-prototypes -Wno-unused-variable \
+		   -Werror-implicit-function-declaration -Wno-trigraphs \
+		   -Wno-format-security -Wno-unused-variable
+# on gcc 4.3.6 and prior, we get some warnings for __rb_erase_color declared
+# inline after being called, so remove -Werror for now
+
+# Standard CFLAGS if not already set
+CFLAGS		?= -O2 -pipe
+# FIXME: breaks glibc
+#CFLAGS		+= -mno-see
+# TODO: Can get tese from KBUILD_CFLAGS in arch/<arch>/Makefile?
+#CFLAGS		+= -march=native -mno-mmx -mno-sse2 -mno-3dnow -mno-avx
+CFLAGS		+= $(WARN_FLAGS) -fno-strict-aliasing -fno-common \
+		   -fno-delete-null-pointer-checks
+CC		?= gcc
+CPPFLAGS	+= -DGRBTEST_CFLAGS="$(CFLAGS)" -DGRBTEST_CONFIG="$(CONFIG)" \
+		   -DGRBTEST_CC="$(CC)" \
+		   -DGRBTEST_ARCH="$(KERNEL_ARCH)" \
+		   -DGRBTEST_ARCH_FLAGS="-march=k8 -m64" \
+		   -DGRBTEST_PROCESSOR="$(shell uname -p)" \
+
+all: grbtest
+
+OBJ_FILES = main.o rbtree.o common.o facilities.o
+HEADER_FILES = $(KERNELDIR)/include/linux/rbtree.h ../common.h
+
+rbtree.c:
+	ln -s $(KERNELDIR)/lib/rbtree.c $(PWD)/rbtree.c
+
+common.c:
+	ln -s ../common.c common.c
+
+rbtree.o: rbtree.c $(KERNELDIR)/include/linux/rbtree.h
+
+grbtest: $(OBJ_FILES) $(HEADER_FILES)
+	$(CC) $(CFLAGS) $(OBJ_FILES) -o grbtest
+
+clean:
+	rm -f grbtest *.o rbtree.c common.c
+
diff --git a/tools/testing/selftests/grbtree/user/facilities.c b/tools/testing/selftests/grbtree/user/facilities.c
new file mode 100644
index 0000000..63c29aa
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/facilities.c
@@ -0,0 +1,58 @@
+/* facilities.c - userspace facilities used by common.c/h
+ * 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.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include "common.h"
+
+long run_test(unsigned int count);
+
+static struct timezone tz;
+
+void facilities_init(void)
+{
+	tz.tz_minuteswest = 0;
+	tz.tz_dsttime = 0;
+
+	memset(&objects, 0, sizeof(objects));
+}
+
+u64 getCurTicks(void) {
+	struct timeval now;
+	gettimeofday(&now, &tz);
+	return 1000000LL * now.tv_sec + now.tv_usec;
+}
+
+/* We aren't actually allocating anything here, unlike the kernelspace version
+ * but a null pointer means error, so we'll return one instead.
+ */
+void *rand_init(u64 *seed)
+{
+	BUG_ON(!seed);
+
+	if (!*seed)
+		*seed = getCurTicks();
+
+	/* reduce to 32 bits */
+	*seed = (*seed & 0xffffffff) ^ (*seed >> 32);
+	srand(*seed & 0xffffffff);
+
+	return (void*)1;
+}
diff --git a/tools/testing/selftests/grbtree/user/main.c b/tools/testing/selftests/grbtree/user/main.c
new file mode 100644
index 0000000..89132b8
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/main.c
@@ -0,0 +1,621 @@
+/* main.c - userspace generic red-black tree test program.
+ * 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.
+ */
+
+#include <stdio.h>
+#include <string.h>
+#include <stdlib.h>
+#include <sys/time.h>
+#include <getopt.h>
+#include <libgen.h>
+
+#include "common.h"
+
+long run_test(unsigned int count);
+
+struct timezone tz;
+struct object_pools objects;
+
+#define BAIL_ON_ERR(var, expr)			\
+do {						\
+	var = (expr);				\
+	if(IS_ERR_VALUE(var)) return var;	\
+} while(0)
+
+int process_args(struct grbtest_config *config, int argc, char *argv[]);
+void show_usage(void);
+void init_basename(void);
+void print_human_summary(const struct grbtest_config *config);
+void print_human_result(const struct grbtest_result *result);
+
+const char *argv0  = NULL;
+
+int main(int argc, char *argv[]) {
+	long		      ret;
+	struct grbtest_config config;
+	struct grbtest_result result;
+	struct container      cont;
+	char		     *argv0_copy = strdup(argv[0]);
+	argv0				 = basename(argv0_copy);
+
+	if (process_args(&config, argc, argv)) {
+		fprintf(stderr, "\n");
+		show_usage();
+		free(argv0_copy);
+		return -1;
+	}
+
+	facilities_init();
+	init_container(&cont);
+	grbtest_init_results(&config, &result);
+
+	BAIL_ON_ERR(ret, grbtest_init(&config));
+
+	if (config.human_readable)
+		print_human_summary(&config);
+	else if (config.print_header)
+		grbtest_print_result_header(&config);
+
+	grbtest_run_test(&config, &result, &cont);
+
+	if (config.human_readable)
+		print_human_result(&result);
+	else
+		grbtest_print_result_row(&config, &result);
+
+	grbtest_cleanup();
+	free(config.delimiter);
+	free(config.text_enclosure);
+	free(argv0_copy);
+
+	return 0;
+}
+
+void print_human_summary(const struct grbtest_config *config)
+{
+	unsigned long long in_seed = (unsigned long long)config->in_seed;
+	unsigned long long seed = (unsigned long long)config->seed;
+
+	print_msg("Build Configuration\n%s\n", grbtest_config());
+
+	print_msg(
+		"Execution Parameters\n"
+		"test            %u (%s)\n"
+		"in_seed         %llu (0x%llx)\n"
+		"seed            %llu (0x%llx)\n"
+		"key_mask        %u (0x%x)\n"
+		"count           %u (0x%x)\n"
+		"pool_count      %u\n"
+		"reps            %u (0x%x)\n"
+		"human_readable  %u\n"
+		"delimiter       %s\n"
+		"text_enclosure  %s\n"
+		"print_header    %u\n"
+		"\n",
+		config->test, grbtest_type_desc[config->test],
+		in_seed, in_seed,
+		seed, seed,
+		config->key_mask, config->key_mask,
+		config->object_count, config->object_count,
+		config->pool_count,
+		config->reps, config->reps,
+		config->human_readable,
+		config->delimiter,
+		config->text_enclosure,
+		config->print_header);
+
+	print_msg("Running test...");
+}
+
+void print_human_result(const struct grbtest_result *result)
+{
+	print_msg("completed!\n\n");
+	print_msg(
+		"Test Results\n"
+		"node_size        %u\n"
+		"object_size      %u\n"
+		"pool_size        %u\n"
+		"insertions       %llu\n"
+		"insertion_time   %llu\n"
+		"evictions        %llu\n"
+		"deletions        %llu\n"
+		"deletion_time    %llu\n",
+		result->node_size,
+		result->object_size,
+		result->pool_size,
+		(unsigned long long)result->insertions,
+		(unsigned long long)result->insertion_time,
+		(unsigned long long)result->evictions,
+		(unsigned long long)result->deletions,
+		(unsigned long long)result->deletion_time);
+
+}
+
+/**
+ * Determine base by prefix and offset to number. Uses standard rules
+ * (expressed in regex below):
+ * 0[xX][0-9a-fA-F]+ denotes a hexidecimal number
+ * 0[0-7]+           denotes an octal number
+ * (0|[1-9][0-9]*)   denotes a decimal number
+ */
+int get_param_base_and_start(const char **str)
+{
+	assert(*str);
+
+	/* Parse an "0x", "0X" or "0" -prefixed string, but not the string
+	 * "0" (which will be treated as base ten). */
+	if (**str == '0' && *(*str + 1)) {
+		++*str;
+		if (**str == 'x' || **str == 'X') {
+			++*str;
+			return 16;
+		} else {
+			return 8;
+		}
+	} else {
+		return 10;
+	}
+}
+
+/**
+ * @returns zero on success, non-zero if the string didn't represent a clean
+ *          number
+ *
+ * FIXME: wont be correct for u32 on platforms where sizeof(int) == 2
+ */
+int get_uint_param(const char *str, unsigned int *dest)
+{
+	const char *start = str;
+	char *endptr;
+	int base = get_param_base_and_start(&start);
+
+	*dest = strtoul(start, &endptr, base);
+	if (*endptr) {
+		fprintf(stderr, "bad number: %s\n", str);
+		exit (1);
+	}
+
+	return *endptr;
+}
+
+/**
+ * @returns zero on success, non-zero if the string didn't represent a clean
+ *          number
+ * FIXME: assumes u64 is unsigned long long
+ */
+int get_u64_param(const char *str, u64 *dest)
+{
+	char *endptr;
+	int base = get_param_base_and_start(&str);
+
+	*dest = strtoull(str, &endptr, base);
+	if (*endptr) {
+		fprintf(stderr, "bad number: %s\n", str);
+		exit (1);
+	}
+
+	return *endptr;
+}
+
+void show_usage()
+{
+	fprintf(stderr,
+"Usage: %s [options]\n"
+"Options:\n"
+"  -h,     --help    Show this help\n"
+"  -t=NUM, --test    The test to run\n"
+"                    0 Performance: Insert\n"
+"                    1 Performance: Insert & Delete\n"
+"                    2 Validation\n"
+"  -s=NUM, --seed    Seed for random key generation (zero to use current\n"
+"                    time)\n"
+"  -m=NUM, --keymask Bitmask for keys (key range)\n"
+"  -c=NUM, --count   Number of objects to use\n"
+"  -r=NUM, --reps    Number of times to repeat test(s)\n"
+"  -p=NUM, --pools   Number of pools of objects to use\n"
+"  -u,     --human   Output in human-readable form\n"
+"  -d=STR, --delim   Use the string STR to delimit fields\n"
+"  -H,     --header  Output a row header\n"
+"\n"
+"Fields:\n"
+"  compiler        the compiler used\n"
+"  use_generic     value of GRBTEST_BUILD_GENERIC\n"
+"  use_leftmost    value of GRBTEST_USE_LEFTMOST\n"
+"  use_rightmost   value of GRBTEST_USE_RIGHTMOST\n"
+"  use_count       value of GRBTEST_USE_COUNT\n"
+"  unique_keys     value of GRBTEST_UNIQUE_KEYS\n"
+"  insert_replaces value of GRBTEST_INSERT_REPLACES\n"
+"  debug           if CONFIG_DEBUG_RBTREE is enabled (.config)\n"
+"  debug_validate  if CONFIG_DEBUG_RBTREE_VALIDATE is enabled (.config)\n"
+"  test            \n"
+"  in_seed         input seed\n"
+"  seed            result seed (differs if supplied seed is zero)\n"
+"  key_mask        \n"
+"  object_count    number of objects used for test\n"
+"  pool_count      \n"
+"  reps            number of times test is repeated\n"
+"  node_size       sizeof(struct rb_node)\n"
+"  object_size     sizeof(struct object)\n"
+"  pool_size       \n"
+"  time            time in microseconds\n"
+"  insertions      number of insertions\n"
+"  deletions       number of deletions\n"
+"  evictions       number of evictions (Always zero if GRBTEST_UNIQUE_KEYS\n"
+"                  is not set. If GRBTEST_UNIQUE_KEYS is set, but\n"
+"                  GRBTEST_INSERT_REPLACES is not, this is the number of\n"
+"                  objects not inserted because a duplicate key already\n"
+"                  existed in the tree.)\n"
+"\n"
+"Example:\n"
+"%s -s 1 --reps 0x8000 --count 0x800 --keymask 0xfff\n"
+"\n",
+		argv0, argv0);
+}
+
+int process_args(struct grbtest_config *config, int argc, char *argv[])
+{
+	int c;
+
+	memset(config, 0, sizeof(*config));
+	config->test		= 0;
+	config->in_seed		= 0;
+	config->seed		= 0;
+	config->key_mask	= 0xff;
+	config->object_count	= 0x100;
+	config->pool_count	= 1;
+	config->reps		= 1;
+	config->human_readable	= 0;
+	config->delimiter	= strdup(",");
+	config->text_enclosure	= strdup("'");
+	config->print_header	= 0;
+
+	while (1) {
+		static struct option long_options[] = {
+			{"help",    no_argument,       0, 'h'},
+			{"test",    required_argument, 0, 't'},
+			{"seed",    required_argument, 0, 's'},
+			{"keymask", required_argument, 0, 'm'},
+			{"count",   required_argument, 0, 'c'},
+			{"reps",    required_argument, 0, 'r'},
+			{"pools",   required_argument, 0, 'p'},
+			{"human",   no_argument,       0, 'u'},
+			{"delim",   required_argument, 0, 'd'},
+			{"quote",   required_argument, 0, 'q'},
+			{"header",  no_argument,       0, 'H'},
+			{0,         0,                 0, 0}
+		};
+
+		/* getopt_long stores the option index here. */
+		int option_index = 0;
+		c = getopt_long(argc, argv, "ht:s:c:r:p:m:ud:q:H", long_options, &option_index);
+
+		/* Detect the end of the options. */
+		if (c == -1)
+		break;
+
+		switch (c) {
+		case 'h': show_usage();			exit(1);
+		case 't': get_uint_param(optarg, &config->test);	break;
+		case 's': get_u64_param(optarg, &config->in_seed);	break;
+		case 'm': get_uint_param(optarg, &config->key_mask);	break;
+		case 'c': get_uint_param(optarg, &config->object_count);break;
+		case 'r': get_uint_param(optarg, &config->reps);	break;
+		case 'p': get_uint_param(optarg, &config->pool_count);	break;
+		case 'u': config->human_readable = 1;			break;
+		case 'd': free(config->delimiter);
+			  config->delimiter = strdup(optarg);		break;
+		case 'q': free(config->text_enclosure);
+			  config->text_enclosure = strdup(optarg);	break;
+		case 'H': config->print_header = 1;			break;
+		default : return -1;
+		}
+	}
+
+	if (optind < argc) {
+		fprintf(stderr, "Invalid argument: %s\n", argv[optind]);
+		return -1;
+	}
+
+	if (config->test >= GRBTEST_TYPE_COUNT) {
+		fprintf(stderr, "Invalid test specified.\n");
+		return -1;
+	}
+
+	return 0;
+}
+
+
+
+#if 0
+/****************************************************************************
+ * rbtree & container-related functions
+ */
+
+static __always_inline long compare_long(const long *a, const long *b) {
+	return *a - *b;
+}
+
+static __always_inline long compare_u32(const u32 *a, const u32 *b) {
+	return (long)*a - (long)*b;
+}
+
+static inline void init_container(struct container *cunt) {
+	cunt->tree = RB_ROOT;
+	cunt->count = 0;
+}
+
+/****************************************************************************
+ * rb_relationship definition
+ */
+RB_DEFINE_INTERFACE(
+	mytree,
+	struct container, tree, leftmost, rightmost, count,
+	struct object, node, id,
+	RB_UNIQUE_KEYS | RB_INSERT_REPLACES, compare_u32, ,
+	,
+	static __flatten noinline,
+	static __flatten,
+	static __flatten __maybe_unused);
+
+void dumpNode(struct rb_node *node) {
+	fprintf(stderr, "rb_parent_color = 0x%lu (parent = 0x%p, color = %d)\n",
+		node->rb_parent_color, rb_parent(node), (int)rb_color(node));
+	fprintf(stderr, "rb_right        = %p\n", node->rb_right);
+	fprintf(stderr, "rb_left         = %p\n", node->rb_left);
+}
+
+void printObj(struct object *obj) {
+
+}
+
+struct obj_display {
+	struct object *o;
+	char text[64];
+};
+
+void populateDisp(struct rb_node *node, struct obj_display *disp_arr, unsigned *index, unsigned target_depth) {
+	struct rb_node *left = NULL;
+	struct rb_node *right = NULL;
+
+	if (target_depth == 0) {
+		struct obj_display *disp = &disp_arr[*index];
+
+		if (node) {
+			struct object *obj = rb_entry(node, struct object, node);
+			disp->o = obj;
+			snprintf(disp->text, sizeof(disp->text),
+				"%p=%02d", obj, obj->id);
+		} else {
+			disp->o = 0;
+			snprintf(disp->text, sizeof(disp->text),
+				"empty      ");
+		}
+		++(*index);
+	}
+
+	if (target_depth > 0) {
+		if (node) {
+			left = node->rb_left;
+			right = node->rb_right;
+		}
+		populateDisp(left, disp_arr, index, target_depth - 1);
+		populateDisp(right, disp_arr, index, target_depth - 1);
+	}
+}
+
+void dumpTree(struct rb_root *root, size_t obj_count) {
+	int max_depth = 5;
+	int max_nodes = 1 << max_depth;
+	unsigned index = 0u;
+	int i;
+	size_t item_text_size;
+	struct obj_display *disp = (struct obj_display *)malloc(max_nodes * sizeof(struct obj_display));
+
+	for (i = 0; i < max_depth; ++i) {
+		populateDisp(root->rb_node, disp, &index, i);
+	}
+	item_text_size = strlen(disp[0].text);
+
+	for (i = 0; i < max_nodes; ++i) {
+		if (i == 1 || i == 3 || i == 7 || i == 15 || i == 31) {
+			int bity;
+			fprintf(stderr, "\n");
+			for (bity = i + 1; !(bity & 32); bity <<= 1) {
+				const char spaces[257] = {[0 ... 255] = ' ', [256] = 0};
+				fprintf(stderr, "%s", &spaces[256 - item_text_size]);
+			}
+
+		} else {
+			fprintf(stderr, "  ");
+		}
+		fprintf(stderr, "%s", disp[i].text);
+	}
+	fprintf(stderr, "\n");
+
+}
+
+__attribute__((flatten))
+long run_test(unsigned int count) {
+	size_t buf_size = sizeof(struct object) * count;
+	struct container cont;
+	struct object *obj_pools[2];
+	struct object **tree_contents;
+	size_t pool_size;
+	int pool_in_use;
+	long i, j, k;
+	struct object *found;
+	struct rb_node *node;
+	long long start, end;
+
+	long long now = getCurTicks();
+
+	srand((now & 0xffffffff) ^ (now >> 32));
+
+	if (count < 1 || count > 0x1000000) { /* 16.8 million should be a reasonable limit */
+		return -1;
+	}
+
+	fprintf(stderr, "allocating two pools of %u objects each\n", count);
+
+	cont.tree      = RB_ROOT;
+	cont.count     = 0;
+	cont.leftmost  = 0;
+	cont.rightmost = 0;
+	pool_in_use      = 0;
+	obj_pools[0]     = (struct object *)malloc(buf_size);
+	obj_pools[1]     = (struct object *)malloc(buf_size);
+
+	fprintf(stderr, "initializing objects\n");
+
+	/* init a psudo-random using a real-random seed */
+//	get_random_bytes(&seed, sizeof(seed));
+//	prandom32_seed(&grbtest.rand, seed);
+
+	for (i = 0; i < 2; ++i) {
+		struct object *p = obj_pools[i];
+		struct object *end = &p[count];
+
+		for (; p != end; ++p) {
+			p->id = rand() & 0xfffff;
+			rb_init_node(&p->node);
+		}
+	}
+	pool_size = count;
+
+	for (j = 0; j < 2; ++j) {
+		struct object *pool = obj_pools[j];
+		start = getCurTicks();
+
+		for (i = count; i; ) {
+			struct object *new = &pool[--i];
+
+			mytree_insert(&cont, new);
+		}
+		pool_in_use ^= 1;
+		end = getCurTicks();
+		fprintf(stderr, "Inserted %u objects in %llu\n", count, end - start);
+	}
+
+	fprintf(stderr, "walking tree now...\n");
+	tree_contents = (struct object **)malloc(sizeof(void*) * cont.count);
+	start = getCurTicks();
+	for (i = 0, node = cont.leftmost; node; node = rb_next(node), ++i) {
+		tree_contents[i] = rb_entry(node, struct object, node);
+	}
+	end = getCurTicks();
+	fprintf(stderr, "Finished walking tree of %u in %llu\n", cont.count, end - start);
+
+	fprintf(stderr, "root = %p, count = %u\n", cont.tree.rb_node, cont.count);
+	//dumpNode(cont.tree.rb_node);
+
+	//dumpTree(&cont.tree, 16);
+	start = getCurTicks();
+#define NEAR_RANGE 8
+#if 0
+	for (i = 0; i < cont.count; ++i) {
+		for (j = 0; j < cont.count; ++j) {
+			found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+#else
+for (k = 0; k < 8; ++k) {
+	for (i = 0; i < cont.count; ++i) {
+		int max = i + NEAR_RANGE;
+		if (max > cont.count)
+			max = cont.count;
+		for (j = i > NEAR_RANGE ? i - NEAR_RANGE : 0;
+		     j < max; ++j) {
+			found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+}
+
+#endif
+	end = getCurTicks();
+	fprintf(stderr, "find_near duration = %llu\n", end - start);
+
+	start = getCurTicks();
+for (k = 0; k < 8; ++k) {
+	for (i = 0; i < cont.count; ++i) {
+		int max = i + NEAR_RANGE;
+		if (max > cont.count)
+			max = cont.count;
+		for (j = i > NEAR_RANGE ? i - NEAR_RANGE : 0;
+		     j < max; ++j) {
+			found = mytree_find(&cont, &tree_contents[j]->id);
+			if (found != tree_contents[j]) {
+				fprintf(stderr, "find_near found %p near %p (expected %p)\n",
+					found, tree_contents[i], tree_contents[j]);
+				found = mytree_find_near(tree_contents[i], &tree_contents[j]->id);
+			}
+		}
+	}
+}
+
+	end = getCurTicks();
+	fprintf(stderr, "find duration = %llu\n", end - start);
+
+	// cleanup
+
+	fprintf(stderr, "Forward iteration (%u objects)\n", cont.count);
+	for (node = cont.leftmost; node ; node = rb_next(node)) {
+		struct object *obj = (struct object *)__rb_node_to_obj(node, &mytree_rel);
+		//fprintf(stderr, "id = 0x%08x\n", obj->id);
+	}
+
+	fprintf(stderr, "Reverse iteration (%u objects)\n", cont.count);
+	for (node = cont.rightmost; node ; node = rb_prev(node)) {
+		struct object *obj = (struct object *)__rb_node_to_obj(node, &mytree_rel);
+		//fprintf(stderr, "id = 0x%08x\n", obj->id);
+	}
+
+
+	fprintf(stderr, "Starting cleanup, %u objects\n", cont.count);
+	while (cont.leftmost) {
+		struct object *obj = (struct object *)__rb_node_to_obj(cont.leftmost, &mytree_rel);
+		//fprintf(stderr, "Removing object at 0x%p id = 0x%04x\n", obj, obj->id);
+		mytree_remove(&cont, obj);
+		//--cont.count;
+	}
+
+	if(obj_pools[0]) {
+		free(obj_pools[0]);
+		free(obj_pools[1]);
+		obj_pools[0] = 0;
+		obj_pools[1] = 0;
+		free(tree_contents);
+	}
+	pool_in_use = 0;
+	cont.leftmost = 0;
+	cont.rightmost = 0;
+
+
+	fprintf(stderr, "Cleanup complete, %u objects left in container.\n", cont.count);
+
+	return 0;
+}
+#endif
diff --git a/tools/testing/selftests/grbtree/user/overrides/linux/export.h b/tools/testing/selftests/grbtree/user/overrides/linux/export.h
new file mode 100644
index 0000000..911be60
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/overrides/linux/export.h
@@ -0,0 +1,31 @@
+/* export.h userspace override hack
+ * 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.
+ *
+ * This file is an override hack for the file normally found at
+ * include/linux/export.h in the kernel tree.
+ */
+
+#ifndef _LINUX_EXPORT_H
+#define _LINUX_EXPORT_H
+
+#define EXPORT_SYMBOL(sym)
+#define EXPORT_SYMBOL_GPL(sym)
+#define EXPORT_SYMBOL_GPL_FUTURE(sym)
+#define EXPORT_UNUSED_SYMBOL(sym)
+#define EXPORT_UNUSED_SYMBOL_GPL(sym)
+
+#endif /* _LINUX_EXPORT_H */
diff --git a/tools/testing/selftests/grbtree/user/overrides/linux/kernel.h b/tools/testing/selftests/grbtree/user/overrides/linux/kernel.h
new file mode 100644
index 0000000..d696e78
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/overrides/linux/kernel.h
@@ -0,0 +1,83 @@
+/* kernel.h userspace override hack
+ * 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.
+ *
+ * This file is an override hack for the file normally found at
+ * include/linux/kernel.h in the kernel tree (not /usr) to allow you to compile
+ * some portions of the Linux kernel code in user-space and is expected to
+ * break fairly often as the internals of the kernel tree change.  It's
+ * designed for use with GNU libc and is generally not expected to work
+ * elsewhere as-is.
+ */
+
+#ifndef _LINUX_KERNEL_H
+#define _LINUX_KERNEL_H
+
+/* avoid warning: __always_inline defined in both /usr/include/sys/cdefs.h as
+ * well as linux/compiler.h.  So we include cdefs.h now, #undef it and let
+ * linux/compiler.h redefine it.
+ */
+#include <sys/cdefs.h>
+#if defined(__always_inline) && !defined(__LINUX_COMPILER_H)
+# undef __always_inline
+#endif
+#if defined(__attribute_const__) && !defined(__LINUX_COMPILER_H)
+# undef __attribute_const__
+#endif
+#include <linux/compiler.h>
+
+#include <assert.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include <errno.h>
+#include <string.h>
+#include <sys/types.h>
+#include <linux/err.h>
+#include <linux/bug.h>
+
+#ifndef __GNU_LIBRARY__
+# warning This file is a hack written to compile with the GNU C Library and \
+	  is not generally expected to work elsewhere.
+#endif
+
+/* glibc-backed versions of BUG{,_ON} */
+#undef BUG
+#undef BUG_ON
+#define BUG()		assert(0)
+#define BUG_ON(arg)	assert(!(arg))
+
+/**
+ * container_of - cast a member of a structure out to the containing structure
+ * @ptr:	the pointer to the member.
+ * @type:	the type of the container struct this is embedded in.
+ * @member:	the name of the member within the struct.
+ *
+ */
+#define container_of(ptr, type, member) ({			\
+	const typeof( ((type *)0)->member ) *__mptr = (ptr);	\
+	(type *)( (char *)__mptr - offsetof(type,member) );})
+
+typedef int8_t   s8;
+typedef uint8_t  u8;
+typedef int16_t  s16;
+typedef uint16_t u16;
+typedef int32_t  s32;
+typedef uint32_t u32;
+typedef int64_t  s64;
+typedef uint64_t u64;
+
+#endif /* _LINUX_KERNEL_H */
-- 
1.7.3.4

[PATCH v6 8/10] selftest: Add script to compile & run userspace test program

[Daniel Santos]

This is a basic script is designed to automate the testing process (for
a single compiler) and generate delimited text output suitable for later
processing. All test parameters can be supplied via the environment, or
defaults will be used for them. The following variables affect the
script and if not supplied, will have the these default values:

CC		"gcc"
KERNELDIR	"../../../../.."
CFLAGS		"-O2 -pipe -march=k8"
key_type	"u64"
payload		0
use_leftmost	0
use_rightmost	0
use_count	0
unique_keys	0
insert_replaces	0
test_num	0

reps		0x20000
count		0x800
keymask		0xfff

logfile		runtest.log
datafile	runtest.out

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 tools/testing/selftests/grbtree/user/runtest.sh |  122 +++++++++++++++++++++++
 1 files changed, 122 insertions(+), 0 deletions(-)
 create mode 100755 tools/testing/selftests/grbtree/user/runtest.sh

diff --git a/tools/testing/selftests/grbtree/user/runtest.sh b/tools/testing/selftests/grbtree/user/runtest.sh
new file mode 100755
index 0000000..b481ad3
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/runtest.sh
@@ -0,0 +1,122 @@
+#!/bin/bash
+
+# runtest.sh - script to compile and run userspace tests of gerneric red-black
+#              tree implementation for a single compiler.
+#
+# 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.
+
+die() {
+	echo "ERROR${@:+": "}$@" 1>&2
+	exit -1
+}
+
+set_var_default() {
+	(($# == 2)) || die "set_var_default takes two parameters, got $#: $@"
+
+	var="$1"
+	default_val="$2"
+	cur_val=$(eval echo "\$${var}")
+
+	if [[ -z "${cur_val}" ]]; then
+		eval ${var}=\"${default_val}\"
+	fi
+}
+
+# Variables affecting code generation
+set_var_default CC		gcc
+set_var_default KERNELDIR	"../../../../.."
+set_var_default CFLAGS		"-O2 -pipe -march=k8"
+# CONFIG parameters:
+set_var_default key_type	u64
+set_var_default payload		0
+set_var_default use_leftmost	0
+set_var_default use_rightmost	0
+set_var_default use_count	0
+set_var_default unique_keys	0
+set_var_default insert_replaces	0
+# For test_num, see grbtest -h
+set_var_default test_num	0
+
+# Variables passed to grbtest program
+set_var_default reps		0x20000
+set_var_default count		0x800
+set_var_default keymask		0xfff
+
+# Output files
+set_var_default logfile		runtest.log
+set_var_default datafile	runtest.out
+
+
+build_desc[0]="hand-coded"
+build_desc[1]="generic"
+
+. /etc/profile || die
+
+do_cpp() {
+	echo "$1" > /tmp/gnucver.$$.c || die
+	${CC} -E /tmp/gnucver.$$.c | grep -v '^#' | tr -d ' '
+	rm /tmp/gnucver.$$.c
+}
+
+gccverstr=$(do_cpp "__GNUC__.__GNUC_MINOR__.__GNUC_PATCHLEVEL__") || die
+
+execute_tests() {
+	for build_generic in 1 0; do
+		CONFIG=$(echo						\
+			-DGRBTEST_KEY_TYPE=${key_type}			\
+			-DGRBTEST_PAYLOAD=${payload}			\
+			-DGRBTEST_BUILD_GENERIC=${build_generic}	\
+			-DGRBTEST_USE_LEFTMOST=${use_leftmost}		\
+			-DGRBTEST_USE_RIGHTMOST=${use_rightmost}	\
+			-DGRBTEST_USE_COUNT=${use_count}		\
+			-DGRBTEST_UNIQUE_KEYS=${unique_keys}		\
+			-DGRBTEST_INSERT_REPLACES=${insert_replaces}
+		)
+
+		echo "********************************************************"
+		echo "Starting build at $(date '+%Y-%m-%d %H:%M:%S')..."
+		echo "  build_type = ${build_desc[${build_generic}]}"
+		echo "  compiler   = ${gccverstr}"
+		echo "  CFLAGS     = ${CFLAGS}"
+		echo "  KERNELDIR  = ${KERNELDIR}"
+		echo
+
+		#set -x
+		CC="${CC}"			\
+		CFLAGS="${CFLAGS}"		\
+		CONFIG="${CONFIG}"		\
+		KERNELDIR="${KERNELDIR}"	\
+		make clean all || die
+		set +x
+
+		echo
+		echo "Executing test..."
+		echo
+cp common.o prof/common-${build_desc[${build_generic}]}.o
+		./grbtest --seed 1		\
+			  --reps ${reps}	\
+			  --count ${count}	\
+			  --keymask ${keymask}	\
+			  --delim "|"		\
+			  --quote ""		\
+			  --test ${test_num} | tee -a "${datafile}"
+		echo
+		echo
+	done
+}
+
+execute_tests | tee -a ${logfile}
-- 
1.7.3.4

[PATCH v6 9/10] selftest: Add basic compiler iterator test script

[Daniel Santos]

A Gentoo-specific script (to be run by root) to iterate through all
installed compilers, execte runtest.sh script and collect the output
data.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 tools/testing/selftests/grbtree/user/runtests.sh |   52 ++++++++++++++++++++++
 1 files changed, 52 insertions(+), 0 deletions(-)
 create mode 100755 tools/testing/selftests/grbtree/user/runtests.sh

diff --git a/tools/testing/selftests/grbtree/user/runtests.sh b/tools/testing/selftests/grbtree/user/runtests.sh
new file mode 100755
index 0000000..d60ec99
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/runtests.sh
@@ -0,0 +1,52 @@
+#!/bin/bash
+
+# This script is designed for use on Gentoo systems, using gcc-config to
+# change the compiler and must be run as root. I'm lazy, so alter to fit your
+# system.
+
+#key_type_range=$(echo {u,s}{8,16,32,64})
+key_type_range="u32 u64"
+unique_style_range="0 1 2"
+add_ons_range="0 1 2"
+
+user=daniel
+outfile=runtests.$$.out
+
+die() {
+	echo "ERROR${@:+": "}$@" 1>&2
+	exit -1
+}
+
+
+rm -f runtest.log runtest.out
+
+if [[ -e ${outfile} ]]; then
+	echo "File ${outfile} exists, please move it out of the way."
+	exit
+fi
+
+for ((gcc_inst_num = 10; gcc_inst_num > 1; --gcc_inst_num)); do
+	gcc-config $gcc_inst_num || exit
+	. /etc/profile
+
+	for key_type in ${key_type_range}; do
+	for unique_style in ${unique_style_range}; do
+	for add_ons in ${add_ons_range}; do
+
+	nice -n -3 sudo -Hu ${user}			\
+		key_type=${key_type}			\
+		payload=0				\
+		use_leftmost=$((add_ons > 0))		\
+		use_rightmost=$((add_ons == 2))		\
+		use_count=$((add_ons == 2))		\
+		unique_keys=$((unique_style > 0))	\
+		insert_replaces=$((unique_style == 2))	\
+		reps=0x20000				\
+		./runtest.sh >> ${outfile} || die
+
+	done
+	done
+	done
+done
+gcc-config 10
+. /etc/profile
-- 
1.7.3.4

[PATCH v6 10/10] selftest: report generation script for test results

[Daniel Santos]

A script that uses sqlite to load test results and generates a report
showing differences in performance per compiler used.

Signed-off-by: Daniel Santos <daniel.santos@pobox.com>
---
 tools/testing/selftests/grbtree/user/gen_report.sh |  129 ++++++++++++++++++++
 1 files changed, 129 insertions(+), 0 deletions(-)
 create mode 100755 tools/testing/selftests/grbtree/user/gen_report.sh

diff --git a/tools/testing/selftests/grbtree/user/gen_report.sh b/tools/testing/selftests/grbtree/user/gen_report.sh
new file mode 100755
index 0000000..a0ab88a
--- /dev/null
+++ b/tools/testing/selftests/grbtree/user/gen_report.sh
@@ -0,0 +1,129 @@
+#!/bin/bash
+
+dbfile=results.$$.db
+datafile=runtest.out
+
+die() {
+	echo "ERROR${@:+": "}$@" 1>&2
+	exit -1
+}
+
+find_sqlite() {
+	for suffix in "" 4 3; do
+		which sqlite${suffix} 2> /dev/null && return 0
+	done
+	return 1
+}
+
+sqlite=$(find_sqlite) || die "failed to find sqlite"
+
+${sqlite} "${dbfile}" << asdf
+/* .echo on */
+.headers on
+create table if not exists grbtest_result (
+	compiler	varchar(255),
+	key_type	varchar(255),
+	payload		int,
+	userland	tinyint,
+	use_generic	tinyint,
+	use_leftmost	tinyint,
+	use_rightmost	tinyint,
+	use_count	tinyint,
+	unique_keys	tinyint,
+	insert_replaces	tinyint,
+	debug		tinyint,
+	debug_validate	tinyint,
+	arch		varchar(255),
+	arch_flags	varchar(255),
+	processor	varchar(255),
+	cc		varchar(255),
+	cflags		varchar(255),
+	test		tinyint,
+	in_seed		bigint,
+	seed		bigint,
+	key_mask	int,
+	object_count	int,
+	pool_count	int,
+	reps		bigint,
+	node_size	int,
+	object_size	int,
+	pool_size	int,
+	insertions	bigint,
+	insertion_time	bigint,
+	evictions	bigint,
+	deletions	bigint,
+	deletion_time	bigint
+);
+.separator |
+.import ${datafile} grbtest_result
+/* .mode column */
+select distinct
+	key_type,
+	payload,
+	userland,
+	use_leftmost,
+	use_rightmost,
+	use_count,
+	unique_keys,
+	insert_replaces,
+	debug,
+	debug_validate,
+	arch,
+	arch_flags,
+	processor,
+	cc,
+	test,
+	in_seed,
+	seed,
+	key_mask,
+	object_count,
+	pool_count,
+	reps,
+	node_size,
+	object_size,
+	pool_size,
+	insertions,
+	evictions,
+	deletions
+from grbtest_result;
+
+select distinct
+	a.compiler as 'Compiler',
+	a.key_type,
+	a.payload,
+	a.userland,
+	(case when a.use_leftmost then	  'L' else '.' end) ||
+	(case when a.use_rightmost then	  'R' else '.' end) ||
+	(case when a.use_count then	  'C' else '.' end) ||
+	(case when a.unique_keys then	  'U' else '.' end) ||
+	(case when a.insert_replaces then 'I' else '.' end) ||
+	(case when a.debug then		  'D' else '.' end) ||
+	(case when a.debug_validate then  'V' else '.' end)
+	as config,
+	a.insertion_time as 'Generic Insert Time',
+	b.insertion_time as 'Hand-Coded Insert Time',
+	1.0 * a.insertion_time / b.insertion_time - 1.0 as 'Insert Diff',
+	a.deletion_time as 'Generic Delete Time',
+	b.deletion_time as 'Hand-Coded Delete Time',
+	1.0 * a.deletion_time / b.deletion_time - 1.0 as 'Delete Diff'
+from
+	grbtest_result as a inner join grbtest_result as b on (
+		a.compiler		= b.compiler
+		AND a.key_type		= b.key_type
+		AND a.payload		= b.payload
+		AND a.userland		= b.userland
+		AND a.use_leftmost	= b.use_leftmost
+		AND a.use_rightmost	= b.use_rightmost
+		AND a.use_count		= b.use_count
+		AND a.unique_keys	= b.unique_keys
+		AND a.insert_replaces	= b.insert_replaces
+		AND a.debug		= b.debug
+		AND a.debug_validate	= b.debug_validate
+	)
+where
+	a.use_generic == 1
+	and b.use_generic = 0;
+asdf
+
+rm "${dbfile}"
+
-- 
1.7.3.4