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

[Keir Fraser <keir.xen@gmail.com>]

On 11/05/2011 21:38, "Dan Magenheimer" <dan.magenheimer@oracle.com> wrote:

> 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.

If this is critical, you simply shouldn't represent such small files with a
radix tree. I'm sure you could easily come up with some scheme to switch to
a single direct reference in the <= 1 page case, thus saving a whole
radix_tree_root structure (and a radix_tree_node structure if I do kill the
height=0 special case). I'd recommend changing the radix_tree_root inlined
structure in tmem_object_root into a pointer which points at a
radix_tree_root or a singleton page, discriminating between these two cases
perhaps on pgp_count.

 -- Keir