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

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

[Dan Magenheimer]

> 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

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

[Keir Fraser]

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

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

[Dan Magenheimer]

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