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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Date:	Wed, 09 May 2012 18:48:25 -0500
From:	Daniel Santos <danielfsantos@....net>
To:	daniel.santos@...ox.com, linux-kernel@...r.kernel.org
CC:	Peter Zijlstra <peterz@...radead.org>,
	Andrea Arcangeli <aarcange@...hat.com>
Subject: Request feedback please: generic rbtree search, insert & remove (with
 leftmost, augmented, etc.)

I've been working on this more and have gone through several
iterations.  I have a small problem: my mechanism will never inline the
key compare function call since it calls it by pointer.  I'm not sure if
this is dictated in the C specification or if it's just something gcc
can't currently detect as a compile-time constant and optimize out. 
Every other option specified via the struct rb_relationship is getting
nicely optimized, removing unused code, etc.

Here is the current feature set (all optimized out when not used):
* leftmost - keep a pointer to the leftmost (lowest value) node cached
in your container struct (thanks Peter)
* rightmost - ditto for rightmost (greatest value)
* unique or non-unique keys with some minor tuning options
* relative searches - when you already have a node that is likely near
another one you want to search for
* augmented / interval tree support (not yet tested)

So back to the problem, as I see it here are my options:
1. Create a header file where you #define your parameters and include it
to define your search, insert & remove functions.  Example:

#define RBTREE_CONTAINER_TYPE     struct my_container
#define RBTREE_CONTAINER_ROOT     rb_root       /* struct rb_root member */
#define RBTREE_CONTAINER_LEFTMOST leftmost      /* struct rb_node *member */
#define RBTREE_CONTAINER_RIGHTMOST              /* none */
#define RBTREE_OBJECT_TYPE        struct my_obj
#define RBTREE_OBJECT_NODE        rb_node       /* struct rb_node member */
#define RBTREE_OBJECT_KEY         mykey
#define RBTREE_KEY_COMPARE        compare_my_key
#define etc...
#include <linux/grbtree.h> /* expands parameters where needed and then
#undefs them. */

2. Use a big ugly macro to define them.  Example:
RB_DEFINE_CORE(struct my_container, rb_root, etc...) /* expands to all
function implementations */

3. Accept the compare function call overhead for search & insert
functions and keep them normal (i.e., __always_inline, non-preprocessor)
generic functions.

Here are the benefits of each, as I see it:
Debugging information will still point you to a real line of code
1. Yes, 2. No, 3. Yes

Type safety implemented (you pass pointers to your container & object
structs directly rather than node pointers)
1. Yes, 2. Yes, 3. No

Maximum efficiency (no function calls to inline-ables like compare and
augmented)
1. Yes, 2. Yes, 3. No

Relies primarily upon:
1. cpp, 2. cpp, 3. cc

To me, the first option seems like it makes the most sense, although I
despise heavy use of the preprocessor (it would be sweet if ANSI came
out with a C templates standard).  Attached is my current working
version which implements approach 3 as described above.  It has a
GRB_DEFINE_INTERFACE() macro, but it only defines a type a type-safe
interface and doesn't fix the compare function not inlined problem.
(Much of comment docs are out of date too.)

Thanks in advance.

Daniel

View attachment "generic_rbtree.patch" of type "text/x-patch" (21148 bytes)