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


RE: [Xen-devel] [PATCH 1/2, v2] x86: replace nr_irqs sized per-domain ar

To: Jan Beulich <JBeulich@xxxxxxxxxx>, Keir Fraser <keir@xxxxxxx>
Subject: RE: [Xen-devel] [PATCH 1/2, v2] x86: replace nr_irqs sized per-domain arrays with radix trees
From: Dan Magenheimer <dan.magenheimer@xxxxxxxxxx>
Date: Wed, 4 May 2011 09:13:26 -0700 (PDT)
Cc: xen-devel@xxxxxxxxxxxxxxxxxxx, Allen M Kay <allen.m.kay@xxxxxxxxx>
Delivery-date: Wed, 04 May 2011 09:14:57 -0700
Envelope-to: www-data@xxxxxxxxxxxxxxxxxxx
In-reply-to: <4DC11C1C020000780003F9DF@xxxxxxxxxxxxxxxxxx>
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: <4DC02878020000780003F690@xxxxxxxxxxxxxxxxxx> <C9E62D62.2CE08%keir@xxxxxxx 4DC11C1C020000780003F9DF@xxxxxxxxxxxxxxxxxx>
Sender: xen-devel-bounces@xxxxxxxxxxxxxxxxxxx
> From: Jan Beulich [mailto:JBeulich@xxxxxxxxxx]
> Subject: Re: [Xen-devel] [PATCH 1/2, v2] x86: replace nr_irqs sized
> per-domain arrays with radix trees
> >>> On 03.05.11 at 23:08, Keir Fraser <keir@xxxxxxx> wrote:
> > On 03/05/2011 15:08, "Jan Beulich" <JBeulich@xxxxxxxxxx> wrote:
> >
> >> It would seem possible to fold the two trees into one (making e.g.
> the
> >> emuirq bits stored in the upper half of the pointer), but I'm not
> >> certain that's worth it as it would make deletion of entries more
> >> cumbersome. Unless pirq-s and emuirq-s were mutually exclusive...
> >>
> >> v2: Split setup/teardown into two stages - (de-)allocation (tree
> node
> >> (de-)population) is done with just d->event_lock held (and hence
> >> interrupts enabled), while actual insertion/removal of translation
> data
> >> gets done with irq_desc's lock held (and interrupts disabled).
> >
> > This is mostly okay, because the only operations that occur with irqs
> > disabled are read-only on the radix-rtree structure itself, hence no
> > alloc/dealloc will happen. *However* those calls to
> > radix_tree_lookup[_slot]() are not synchronised wrt your calls to
> > radix_tree_{insert,delete}(). The latter hold d->event_lock, while
> the
> > former do not. Hence you need RCU and you need a new first patch in
> your
> > patch set to pull in a modern radix-tree.[ch] from upstream Linux.
> Right you are - I didn't pay attention to the tree internal nodes.
> Will take a few days though before I can get to this.

Jan, Keir --

If either of you are working on radix-tree.c in Xen, this lkml
post explains how the Xen version differs from the Linux upstream
version and (for tmem) why:


After some offlist discussion, for kztmem (later renamed "the new
zcache"), I ended up extracting the essence of the radix-tree data
structure and adapting it inline specifically for my in-kernel tmem
needs.  While I'm not a fan of duplicating code, this was an
expedient way to avoid a political quagmire.

Ideally, the Xen radix-tree.c would support both needs through some
kind of layering, but if your preference is to go to the upstream
Linux radix-tree.c, I can probably leverage my inlined-radix-tree
code into Xen tmem.c.  I don't expect it will be trivial though.


P.S. In case you are curious about looking at the end result for
tmem in Linux, see https://lkml.org/lkml/2010/12/7/294 and search
(case-insensitive) for instances of "objnode"... I'm sure you'll
see the resemblance to radix-tree.c.

Xen-devel mailing list