RE: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.

[Dan Magenheimer <dan.magenheimer@oracle.com>]

> From: Xen patchbot-unstable [mailto:patchbot@xen.org]
> Sent: Tuesday, May 10, 2011 9:40 PM
> To: xen-changelog@lists.xensource.com
> Subject: [Xen-changelog] [xen-unstable] Update radix-tree.[ch] from
> upstream Linux to gain RCU awareness.
> 
> # HG changeset patch
> # User Keir Fraser <keir@xen.org>
> # Date 1304929523 -3600
> # Node ID 44bfebf40b2bb7f219333ef5bf97eb7493592cdc
> # Parent  4b0692880dfa557d4e1537c7a58c412c1286a416
> Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
> 
> We still leave behind features we don't need such as tagged nodes.
> 
> Other changes:
>  - Allow callers to define their own node alloc routines.
>  - Only allocate per-node rcu_head when using the default RCU-safe
>    alloc routines.
>  - Keep our own radix_tree_destroy().
> 
> In future it may also be worth getting rid of the complex and
> pointless special-casing of radix-tree height==0, in which a single
> data item can be stored directly in radix_tree_root. It introduces a
> whole lot of special cases and complicates RCU handling. If we get rid
> of it we can reclaim the 'indirect pointer' tag in bit 0 of every slot
> entry.
> 
> Signed-off-by: Keir Fraser <keir@xen.org>

Thanks for handling this.  A couple thoughts worth noting:

I'm not sure the height=0 special-casing is pointless.  IIRC, a
radix-tree node contains 64 pointers (512 bytes).  When trees containing
a single item are common, 512 bytes may be a relatively large overhead
For tmem, each tree contains pages from a file, many files on
many filesystems are less than one-page, and, when compressed that
one page may be represented by far less than 4096 bytes, so avoiding
the overhead is a big win.

While I like your improvements avoiding the extra args passed on each
insert/delete, I'm not sure for tmem the tradeoff is a good one.
A basic assumption of tmem is that memory is constrained and
CPU cycles are abundant.  While we've all been trained to avoid
passing parameters when possible to reduce CPU overhead,
the world is changing.  If radix-tree.c is used in Xen in the future
for non-tmem high-frequency inserts/deletes, your CPU optimization
is probably best, but for tmem I think it's a net loss as now
each radix tree (and there may be thousands or millions in a
large tmem-enabled Xen system) "wastes" 24 bytes.

Thanks,
Dan