On Oct 18, 2007, at 2:31 PM, Joerg Sonnenberger wrote:

> The first concern is that the code doesn't allow "type safe" usage. I
> have a set of wrapping code that avoids this by creating inline glue
> for a very small cost. IMO this is necessary feature before actual
> wide-spread use.

The lack of type safety doesn't really bother me.  This would be no  
different for generic hash table routines, etc.  In any case, we're  
written in C, and void * is what we get if we don't want wrappers  
(which increase code size) or code duplication (which increases code  
size).

> The second concern is the use of the sentinel nodes. Having done the  
> rb
> tree myself I'm sure that they save very little actual code and might
> have even increased the size.

Again, sentinel nodes don't bother me.  And, as documented in the  
code, using them enables a couple of clever optimizations.  Matt  
designed that rb code to be used for a MIPS pmap module, and wanted it  
to be small and fast, and shaving cycles was a primary concern.

> The third concern is generality. The only use of sys/tree.h in the
> kernel is uvm right now and that does some nasty things with  
> RB_AUGMENT.
> We can't replace that with the current rb_moved. If we want to have a
> single copy in the tree, we need a callback whenever a child of a node
> changes. That adds a conditional to a lot of branches though.

Having a callback could take a separate path (i.e. duplicate some  
small amount of code within rb.c itself).  That said, it seems like  
uvm_map.c could compute that information lazily, thus eliminating the  
need for the "augment" altogether, and actually improving performance  
(you only need to know a sub-tree's available space when attempting to  
allocate from the map, so why constantly recompute it when e.g.  
removing mappings?)

> The last concern is about memory usage. If doing all the above, only  
> two
> bits of storage are needed for each node (color and position). I think
> that should be merged into the parent pointer. Based on my own tests,
> this is approximately free on i386 as the bitfield access is as bad as
> modifying the parent pointer and the parent pointer needs to be  
> changed
> in most cases already.

My memory usage concern is more about code size rather than data size.

-- thorpej