This is an archived copy of the Xen.org mailing list, which we have preserved to ensure that existing links to archives are not broken. The live archive, which contains the latest emails, can be found at http://lists.xen.org/
Home Products Support Community News


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

To: Keir Fraser <keir.xen@xxxxxxxxx>
Subject: [Xen-devel] RE: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
From: Dan Magenheimer <dan.magenheimer@xxxxxxxxxx>
Date: Wed, 11 May 2011 15:12:02 -0700 (PDT)
Cc: xen-devel@xxxxxxxxxxxxxxxxxxx, Jan Beulich <JBeulich@xxxxxxxxxx>
Delivery-date: Wed, 11 May 2011 15:14:21 -0700
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
In-reply-to: <C9F0C2CC.1A2CC%keir.xen@xxxxxxxxx>
List-help: <mailto:xen-devel-request@lists.xensource.com?subject=help>
List-id: Xen developer discussion <xen-devel.lists.xensource.com>
List-post: <mailto:xen-devel@lists.xensource.com>
List-subscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=subscribe>
List-unsubscribe: <http://lists.xensource.com/mailman/listinfo/xen-devel>, <mailto:xen-devel-request@lists.xensource.com?subject=unsubscribe>
References: <cb995867-f37b-420c-ac27-cf4e57bc059c@default C9F0C2CC.1A2CC%keir.xen@xxxxxxxxx>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
> From: Keir Fraser [mailto:keir.xen@xxxxxxxxx]
> Subject: Re: Update radix-tree.[ch] from upstream Linux to gain RCU
> awareness.
> On 11/05/2011 21:38, "Dan Magenheimer" <dan.magenheimer@xxxxxxxxxx>
> 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.

Xen-devel mailing list

<Prev in Thread] Current Thread [Next in Thread>