Re: [PATCH v5 0/25] Generic Red-Black Trees (still WIP)

[Daniel Santos <danielfsantos@att.net>]

Hmm, looks like I've had some type of mailer problem as this message
didn't appear on LKML :(  I hope this one goes through, but sorry my
patches aren't properly grouped.

On 09/25/2012 06:24 PM, Daniel Santos wrote:
> First I want to apologize for not being able to work on this over most of the
> summer. I see that some other changes are happening with red-black and
> interval trees in the kernel which look good.  This patch set is based on v3.5
> and is not adjusted for many of the changes in Michel Lespinasse's patches.
> This is still WIP as I have added a good deal of new test code and made a fair
> number of performance tweaks, but I needed to get something out for review
> again to keep this thing rolling.
>
> 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 augmented / interval tree support
> o type-safe wrapper interface available via pre-processor macro
>
> Outstanding Issues
> ==================
> General
> -------
> o Need to change comments at head of rbtree.h.
> o Need something in Documents to explain generic rbtrees.
> o Descriptions for new KConfig values incomplete.
> 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, although the option to build it has
>   already been added to KConfig.
> o Userspace selftest's Makefile should run modules_prepare in KERNELDIR.
> o Validation in self-tests doesn't yet cover tests for
>   - insert_near
>   - find_{first,last,next,prev}
> o Selftest scripts need better portability.
> o It would be nice to have some fault-injection in test code to verify that
>   CONFIG_DEBUG_RBTREE and CONFIG_DEBUG_RBTREE_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 */
> 	const rb_augment_f augment;
> 	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, augment,
> 	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,
> 	/* no augment */,
> 	,,,)
>
> 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,
> 	/* no augment */,
> 	,,,)
>
>
> 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.
>
> 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 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.
>