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

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

> From: Keir Fraser [mailto:keir.xen@gmail.com]
> Subject: Re: Update radix-tree.[ch] from upstream Linux to gain RCU
> awareness.
> 
> 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.

True, the special casing could be handled in tmem.  (On the chance
that you decide to do this, the special case only applies if
the pgp_count is 1 AND the index of the page is zero.)  Note
also that tmem doesn't have a clue about the size of the file
and may frequently need to change between an object that only
has page index==0 in tmem and one that has more than that.
The net result is that you would simply be moving the special
casing and "automatic transformation" code from radix-tree to
tmem, for a net result of no advantage (AFAICT) and IMHO since
the code needs to be somewhere, it might as well be in radix-tree
since it is already there and debugged for Linux.