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: Dan Magenheimer <dan.magenheimer@xxxxxxxxxx>
Subject: [Xen-devel] Re: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
From: Keir Fraser <keir.xen@xxxxxxxxx>
Date: Wed, 11 May 2011 22:48:44 +0100
Cc: xen-devel@xxxxxxxxxxxxxxxxxxx, Jan Beulich <JBeulich@xxxxxxxxxx>
Delivery-date: Wed, 11 May 2011 14:49:51 -0700
Dkim-signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:user-agent:date:subject:from:to:cc:message-id :thread-topic:thread-index:in-reply-to:mime-version:content-type :content-transfer-encoding; bh=U0rd0heRUhK24/c3+hKEMy1bzz8lO6mwGuDMaZPjlak=; b=pawHbvvz3Fs0mcmV0iM7jv9MqT1R9PZoltDRHJP83px6l4fxypXDXdIoDkcLobw8t9 idvTEtn9F6oIxvSqGt9qbCe8+DNIPAXqSp2McKKqinERi6TScjtug63VzrUlpqyDINdB RuhWkahmSZrZymxP5F4YJzlqYQ3XOQXJ0+UcA=
Domainkey-signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=user-agent:date:subject:from:to:cc:message-id:thread-topic :thread-index:in-reply-to:mime-version:content-type :content-transfer-encoding; b=G5uIhCCBaI3vqfDG79JUeSVJOr/YQh8SHBoDcOEzFI926H6JhY8YCIUfxYbvsFFhGx UGqZ7z88qjk85jK81m3QQni2hAzE0IbtHXp1TDjpe4Uyln7I+AJAtaypDtUUU7xfNHG4 GGCj10+Qecb6h7NQze/RRLalz32JX04TSBloY=
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
In-reply-to: <cb995867-f37b-420c-ac27-cf4e57bc059c@default>
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>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
Thread-index: AcwQJTLbADqmLaRtfECwnjDhPiQleA==
Thread-topic: Update radix-tree.[ch] from upstream Linux to gain RCU awareness.
User-agent: Microsoft-Entourage/
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.

 -- Keir

Xen-devel mailing list

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