Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
On Sun, May 18, 2025 at 10:52:24AM +0200, Jan Beulich wrote: > On 16.05.2025 04:04, dm...@proton.me wrote: > > From: Denis Mukhin > > > > Currently, hypervisor code has two different non-system domain ID allocation > > implementations: > > > > (a) Sequential IDs allocation in dom0less Arm code based on > > max_init_domid; > > > > (b) Sequential IDs allocation in XEN_DOMCTL_createdomain; does not use > > max_init_domid (both Arm and x86). > > > > It makes sense to have a common helper code for such task across > > architectures > > (Arm and x86) and between dom0less / toolstack domU allocation. > > > > Wrap the domain ID allocation as an arch-independent function domid_alloc() > > in > > common/domain.c based on rangeset. > > > > Allocation algorithm: > > - If an explicit domain ID is provided, verify its availability and > > use it if ID is not used; > > - Otherwise, perform an exhaustive search starting from the end of the used > > domain ID range. domid_alloc() guarantees that two subsequent calls will > > result in different IDs allocation. > While you properly retain original logic now, the above is not an accurate > description thereof, imo. To search "from the end" usually is understood as > a backwards search. Whereas what you mean is that the search starts off where > the last one finished, wrapping around when hitting the end of the valid > range. I have updated the description in v7: https://lore.kernel.org/xen-devel/20250519192306.1364471-2-dmuk...@ford.com/ > > Jan >
Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
On 16.05.2025 04:04, dm...@proton.me wrote: > From: Denis Mukhin > > Currently, hypervisor code has two different non-system domain ID allocation > implementations: > > (a) Sequential IDs allocation in dom0less Arm code based on max_init_domid; > > (b) Sequential IDs allocation in XEN_DOMCTL_createdomain; does not use > max_init_domid (both Arm and x86). > > It makes sense to have a common helper code for such task across architectures > (Arm and x86) and between dom0less / toolstack domU allocation. > > Wrap the domain ID allocation as an arch-independent function domid_alloc() in > common/domain.c based on rangeset. > > Allocation algorithm: > - If an explicit domain ID is provided, verify its availability and > use it if ID is not used; > - Otherwise, perform an exhaustive search starting from the end of the used > domain ID range. domid_alloc() guarantees that two subsequent calls will > result in different IDs allocation. While you properly retain original logic now, the above is not an accurate description thereof, imo. To search "from the end" usually is understood as a backwards search. Whereas what you mean is that the search starts off where the last one finished, wrapping around when hitting the end of the valid range. Jan
Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
On Fri, May 16, 2025 at 09:35:35PM +0100, Julien Grall wrote:
> Hi Denis and Teddy,
>
> I haven't looked at the rest of the series. Just answering
> to the discussion between both of you.
>
> On 16/05/2025 19:06, dm...@proton.me wrote:
> > On Fri, May 16, 2025 at 08:43:35AM +, Teddy Astie wrote:
> >>> diff --git a/xen/common/device-tree/dom0less-build.c
> >>> b/xen/common/device-tree/dom0less-build.c
> >>> index 2c56f13771..9236dbae11 100644
> >>> --- a/xen/common/device-tree/dom0less-build.c
> >>> +++ b/xen/common/device-tree/dom0less-build.c
> >>> @@ -850,15 +850,13 @@ void __init create_domUs(void)
> >>>struct xen_domctl_createdomain d_cfg = {0};
> >>>unsigned int flags = 0U;
> >>>bool has_dtb = false;
> >>> +domid_t domid;
> >>>uint32_t val;
> >>>int rc;
> >>>
> >>>if ( !dt_device_is_compatible(node, "xen,domain") )
> >>>continue;
> >>>
> >>> -if ( (max_init_domid + 1) >= DOMID_FIRST_RESERVED )
> >>> -panic("No more domain IDs available\n");
> >>> -
> >>>d_cfg.max_evtchn_port = 1023;
> >>>d_cfg.max_grant_frames = -1;
> >>>d_cfg.max_maptrack_frames = -1;
> >>> @@ -981,7 +979,11 @@ void __init create_domUs(void)
> >>> * very important to use the pre-increment operator to call
> >>> * domain_create() with a domid > 0. (domid == 0 is reserved
> >>> for Dom0)
> >>> */
> >>> -d = domain_create(++max_init_domid, &d_cfg, flags);
> >>> +domid = domid_alloc(++max_init_domid);
> >>> +if ( domid == DOMID_INVALID )
> >>> +panic("Error allocating ID for domain %s\n",
> >>> dt_node_name(node));
> >>> +
> >>> +d = domain_create(domid, &d_cfg, flags);
> >>>if ( IS_ERR(d) )
> >>>panic("Error creating domain %s (rc = %ld)\n",
> >>> dt_node_name(node), PTR_ERR(d));
> >>> diff --git a/xen/common/domain.c b/xen/common/domain.c
> >>> index abf1969e60..0ba3cdc47d 100644
> >>> --- a/xen/common/domain.c
> >>> +++ b/xen/common/domain.c
> >>> @@ -66,6 +66,74 @@ DEFINE_RCU_READ_LOCK(domlist_read_lock);
> >>>static struct domain *domain_hash[DOMAIN_HASH_SIZE];
> >>>struct domain *domain_list;
> >>>
> >>> +/* Non-system domain ID allocator. */
> >>> +static DEFINE_SPINLOCK(domid_lock);
> >>> +static struct rangeset *domid_rangeset;
> >>> +static unsigned int domid_last;
> >>> +
> >>> +void __init domid_init(void)
> >>> +{
> >>> +domid_rangeset = rangeset_new(NULL, "domid",
> >>> RANGESETF_prettyprint_hex);
> >>> +if ( !domid_rangeset )
> >>> +panic("cannot allocate domain ID rangeset\n");
> >>> +
> >>> +rangeset_limit(domid_rangeset, DOMID_FIRST_RESERVED);
> >>> +}
> >>> +
> >>> +/*
> >>> + * Allocate new non-system domain ID based on the hint.
> >>> + *
> >>> + * If hint is outside of valid [0..DOMID_FIRST_RESERVED - 1] range of
> >>> IDs,
> >>> + * perform an exhaustive search starting from the end of the used domain
> >>> ID
> >>> + * range.
> >>> + */
> >>> +domid_t domid_alloc(domid_t domid)
> >>> +{
> >>> +spin_lock(&domid_lock);
> >>> +
> >>> +if ( domid < DOMID_FIRST_RESERVED )
> >>> +{
> >>> +if ( rangeset_contains_singleton(domid_rangeset, domid) )
> >>> +domid = DOMID_INVALID;
> >>> +}
> >>> +else
> >>> +{
> >>> +for ( domid = domid_last + 1; domid != domid_last; domid++ )
> >>> +{
> >>> +if ( domid == DOMID_FIRST_RESERVED )
> >>> +domid = 0;
> >>> +
> >>> +if ( !rangeset_contains_singleton(domid_rangeset, domid) )
> >>> +break;
> >>> +}
> >>> +
> >>> +if ( domid == domid_last )
> >>> +domid = DOMID_INVALID;
> >>> +}
> >>> +
> >>> +if ( domid != DOMID_INVALID )
> >>> +{
> >>> +ASSERT(!rangeset_add_singleton(domid_rangeset, domid));
> >>> +
> >>> +if ( domid != domid_last )
> >>> +domid_last = domid;
> >>> +}
> >>> +
> >>> +spin_unlock(&domid_lock);
> >>> +
> >>> +return domid;
> >>> +}
> >>
> >> It's mostly a matter of implementation choice, but I am not really fan
> >> of relying on rangesets, which to me are meant for address ranges or
> >> something similar but at least large.
> >>
> >> I would rather rely on a bitmap using find_first_zero_bit+set_bit which
> >> avoids doing a per-domid test, and may be simpler overall. The bitmap
> >> size for 0x3FF0 domains is almost 4KB, which looks acceptable.
>
> I guess you meant 0x7FF0?
>
> >>
> >> I don't know what other thinks.
> >
> > Thanks for taking a look!
> >
> > TBH, I was initially considering using a bitmap. But then I chose use
> > rangesets
> > because statically defined bitmap will increase the binary size, which may
> > be
> > indesirable; and for dynamic allocation, rangeset has all convenience APIs
> > implemented...
>
> The bitmap helpers have been
Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
Hi Denis and Teddy,
I haven't looked at the rest of the series. Just answering
to the discussion between both of you.
On 16/05/2025 19:06, dm...@proton.me wrote:
On Fri, May 16, 2025 at 08:43:35AM +, Teddy Astie wrote:
diff --git a/xen/common/device-tree/dom0less-build.c
b/xen/common/device-tree/dom0less-build.c
index 2c56f13771..9236dbae11 100644
--- a/xen/common/device-tree/dom0less-build.c
+++ b/xen/common/device-tree/dom0less-build.c
@@ -850,15 +850,13 @@ void __init create_domUs(void)
struct xen_domctl_createdomain d_cfg = {0};
unsigned int flags = 0U;
bool has_dtb = false;
+domid_t domid;
uint32_t val;
int rc;
if ( !dt_device_is_compatible(node, "xen,domain") )
continue;
-if ( (max_init_domid + 1) >= DOMID_FIRST_RESERVED )
-panic("No more domain IDs available\n");
-
d_cfg.max_evtchn_port = 1023;
d_cfg.max_grant_frames = -1;
d_cfg.max_maptrack_frames = -1;
@@ -981,7 +979,11 @@ void __init create_domUs(void)
* very important to use the pre-increment operator to call
* domain_create() with a domid > 0. (domid == 0 is reserved for
Dom0)
*/
-d = domain_create(++max_init_domid, &d_cfg, flags);
+domid = domid_alloc(++max_init_domid);
+if ( domid == DOMID_INVALID )
+panic("Error allocating ID for domain %s\n", dt_node_name(node));
+
+d = domain_create(domid, &d_cfg, flags);
if ( IS_ERR(d) )
panic("Error creating domain %s (rc = %ld)\n",
dt_node_name(node), PTR_ERR(d));
diff --git a/xen/common/domain.c b/xen/common/domain.c
index abf1969e60..0ba3cdc47d 100644
--- a/xen/common/domain.c
+++ b/xen/common/domain.c
@@ -66,6 +66,74 @@ DEFINE_RCU_READ_LOCK(domlist_read_lock);
static struct domain *domain_hash[DOMAIN_HASH_SIZE];
struct domain *domain_list;
+/* Non-system domain ID allocator. */
+static DEFINE_SPINLOCK(domid_lock);
+static struct rangeset *domid_rangeset;
+static unsigned int domid_last;
+
+void __init domid_init(void)
+{
+domid_rangeset = rangeset_new(NULL, "domid", RANGESETF_prettyprint_hex);
+if ( !domid_rangeset )
+panic("cannot allocate domain ID rangeset\n");
+
+rangeset_limit(domid_rangeset, DOMID_FIRST_RESERVED);
+}
+
+/*
+ * Allocate new non-system domain ID based on the hint.
+ *
+ * If hint is outside of valid [0..DOMID_FIRST_RESERVED - 1] range of IDs,
+ * perform an exhaustive search starting from the end of the used domain ID
+ * range.
+ */
+domid_t domid_alloc(domid_t domid)
+{
+spin_lock(&domid_lock);
+
+if ( domid < DOMID_FIRST_RESERVED )
+{
+if ( rangeset_contains_singleton(domid_rangeset, domid) )
+domid = DOMID_INVALID;
+}
+else
+{
+for ( domid = domid_last + 1; domid != domid_last; domid++ )
+{
+if ( domid == DOMID_FIRST_RESERVED )
+domid = 0;
+
+if ( !rangeset_contains_singleton(domid_rangeset, domid) )
+break;
+}
+
+if ( domid == domid_last )
+domid = DOMID_INVALID;
+}
+
+if ( domid != DOMID_INVALID )
+{
+ASSERT(!rangeset_add_singleton(domid_rangeset, domid));
+
+if ( domid != domid_last )
+domid_last = domid;
+}
+
+spin_unlock(&domid_lock);
+
+return domid;
+}
It's mostly a matter of implementation choice, but I am not really fan
of relying on rangesets, which to me are meant for address ranges or
something similar but at least large.
I would rather rely on a bitmap using find_first_zero_bit+set_bit which
avoids doing a per-domid test, and may be simpler overall. The bitmap
size for 0x3FF0 domains is almost 4KB, which looks acceptable.
I guess you meant 0x7FF0?
I don't know what other thinks.
Thanks for taking a look!
TBH, I was initially considering using a bitmap. But then I chose use rangesets
because statically defined bitmap will increase the binary size, which may be
indesirable; and for dynamic allocation, rangeset has all convenience APIs
implemented...
The bitmap helpers have been optimized for fast lookup and insertion.
They could also potentially be used lockless.
On the other hand, the rangeset is a linear search from start. So for
instance, AFAIU, "rangeset_contains_singleton()" will start looking up
from the first range until it found the highest range lower or
containing the singleton. It also contains an internal read-write lock.
So we are taking two locks now.
This means the loop:
> for ( domid = domid_last + 1; domid != domid_last; domid++ )
>[...]
>if ( !rangeset_contains_singleton(...) )
is going to be fairly ineffient. I haven't check whether we can do
better with the rangeset.
Also, the overhead of a range is actually quite high if the domain IDs
are not contiguous (for Arm 64-bit, it is 16-byte per range and 72-byte
for th
Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
On Fri, May 16, 2025 at 08:43:35AM +, Teddy Astie wrote:
> Hello,
>
> Le 16/05/2025 à 04:06, dm...@proton.me a écrit :
> > From: Denis Mukhin
> >
> > Currently, hypervisor code has two different non-system domain ID allocation
> > implementations:
> >
> >(a) Sequential IDs allocation in dom0less Arm code based on
> > max_init_domid;
> >
> >(b) Sequential IDs allocation in XEN_DOMCTL_createdomain; does not use
> >max_init_domid (both Arm and x86).
> >
> > It makes sense to have a common helper code for such task across
> > architectures
> > (Arm and x86) and between dom0less / toolstack domU allocation.
> >
> > Wrap the domain ID allocation as an arch-independent function domid_alloc()
> > in
> > common/domain.c based on rangeset.
> >
> > Allocation algorithm:
> > - If an explicit domain ID is provided, verify its availability and
> >use it if ID is not used;
> > - Otherwise, perform an exhaustive search starting from the end of the used
> >domain ID range. domid_alloc() guarantees that two subsequent calls will
> >result in different IDs allocation.
> >
> > Initialize the domain IDs rangeset from the new domid_init() which is called
> > from arch setup code.
> >
> > Also, remove is_free_domid() helper as it is not needed now.
> >
> > No functional change intended.
> >
> > Signed-off-by: Denis Mukhin
> > ---
> > Changes since v5:
> > - rebased
> > ---
> > xen/arch/arm/domain_build.c | 17 --
> > xen/arch/arm/setup.c| 2 +
> > xen/arch/x86/setup.c| 13 +++--
> > xen/common/device-tree/dom0less-build.c | 10 ++--
> > xen/common/domain.c | 70 +
> > xen/common/domctl.c | 41 ++-
> > xen/include/xen/domain.h| 4 ++
> > 7 files changed, 107 insertions(+), 50 deletions(-)
> >
> > diff --git a/xen/arch/arm/domain_build.c b/xen/arch/arm/domain_build.c
> > index b189a7cfae..e9d563c269 100644
> > --- a/xen/arch/arm/domain_build.c
> > +++ b/xen/arch/arm/domain_build.c
> > @@ -2010,6 +2010,7 @@ void __init create_dom0(void)
> > .grant_opts = XEN_DOMCTL_GRANT_version(opt_gnttab_max_version),
> > };
> > unsigned int flags = CDF_privileged | CDF_hardware;
> > +domid_t domid;
> > int rc;
> >
> > /* The vGIC for DOM0 is exactly emulating the hardware GIC */
> > @@ -2034,19 +2035,25 @@ void __init create_dom0(void)
> > if ( !llc_coloring_enabled )
> > flags |= CDF_directmap;
> >
> > -dom0 = domain_create(0, &dom0_cfg, flags);
> > +domid = domid_alloc(0);
> > +if ( domid == DOMID_INVALID )
> > +panic("Error allocating domain ID 0\n");
> > +
> > +dom0 = domain_create(domid, &dom0_cfg, flags);
> > if ( IS_ERR(dom0) )
> > -panic("Error creating domain 0 (rc = %ld)\n", PTR_ERR(dom0));
> > +panic("Error creating domain %d (rc = %ld)\n", domid,
> > PTR_ERR(dom0));
> >
> > if ( llc_coloring_enabled && (rc = dom0_set_llc_colors(dom0)) )
> > -panic("Error initializing LLC coloring for domain 0 (rc = %d)\n",
> > rc);
> > +panic("Error initializing LLC coloring for domain %pd (rc = %d)\n",
> > + dom0, rc);
> >
> > if ( alloc_dom0_vcpu0(dom0) == NULL )
> > -panic("Error creating domain 0 vcpu0\n");
> > +panic("Error creating domain %pdv0\n", dom0);
> >
> > rc = construct_dom0(dom0);
> > if ( rc )
> > -panic("Could not set up DOM0 guest OS (rc = %d)\n", rc);
> > +panic("Could not set up guest OS for domain %pd (rc = %d)\n",
> > + dom0, rc);
> >
> > set_xs_domain(dom0);
> > }
> > diff --git a/xen/arch/arm/setup.c b/xen/arch/arm/setup.c
> > index 10b46d0684..c3959e8d8e 100644
> > --- a/xen/arch/arm/setup.c
> > +++ b/xen/arch/arm/setup.c
> > @@ -418,6 +418,8 @@ void asmlinkage __init start_xen(unsigned long
> > fdt_paddr)
> >
> > timer_init();
> >
> > +domid_init();
> > +
> > init_idle_domain();
> >
> > rcu_init();
> > diff --git a/xen/arch/x86/setup.c b/xen/arch/x86/setup.c
> > index 2518954124..02f665f520 100644
> > --- a/xen/arch/x86/setup.c
> > +++ b/xen/arch/x86/setup.c
> > @@ -1030,8 +1030,11 @@ static struct domain *__init create_dom0(struct
> > boot_info *bi)
> > if ( iommu_enabled )
> > dom0_cfg.flags |= XEN_DOMCTL_CDF_iommu;
> >
> > -/* Create initial domain. Not d0 for pvshim. */
> > -bd->domid = get_initial_domain_id();
> > +/* Allocate initial domain ID. Not d0 for pvshim. */
> > +bd->domid = domid_alloc(get_initial_domain_id());
> > +if ( bd->domid == DOMID_INVALID )
> > +panic("Error allocating domain ID %d\n", get_initial_domain_id());
> > +
> > d = domain_create(bd->domid, &dom0_cfg,
> > pv_shim ? 0 : CDF_privileged | CDF_hardware);
> > if ( IS_ERR(d) )
> > @@ -1063,7 +1066,7 @@ static struct domain *__init create_dom0(struc
Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation
Hello,
Le 16/05/2025 à 04:06, dm...@proton.me a écrit :
> From: Denis Mukhin
>
> Currently, hypervisor code has two different non-system domain ID allocation
> implementations:
>
>(a) Sequential IDs allocation in dom0less Arm code based on max_init_domid;
>
>(b) Sequential IDs allocation in XEN_DOMCTL_createdomain; does not use
>max_init_domid (both Arm and x86).
>
> It makes sense to have a common helper code for such task across architectures
> (Arm and x86) and between dom0less / toolstack domU allocation.
>
> Wrap the domain ID allocation as an arch-independent function domid_alloc() in
> common/domain.c based on rangeset.
>
> Allocation algorithm:
> - If an explicit domain ID is provided, verify its availability and
>use it if ID is not used;
> - Otherwise, perform an exhaustive search starting from the end of the used
>domain ID range. domid_alloc() guarantees that two subsequent calls will
>result in different IDs allocation.
>
> Initialize the domain IDs rangeset from the new domid_init() which is called
> from arch setup code.
>
> Also, remove is_free_domid() helper as it is not needed now.
>
> No functional change intended.
>
> Signed-off-by: Denis Mukhin
> ---
> Changes since v5:
> - rebased
> ---
> xen/arch/arm/domain_build.c | 17 --
> xen/arch/arm/setup.c| 2 +
> xen/arch/x86/setup.c| 13 +++--
> xen/common/device-tree/dom0less-build.c | 10 ++--
> xen/common/domain.c | 70 +
> xen/common/domctl.c | 41 ++-
> xen/include/xen/domain.h| 4 ++
> 7 files changed, 107 insertions(+), 50 deletions(-)
>
> diff --git a/xen/arch/arm/domain_build.c b/xen/arch/arm/domain_build.c
> index b189a7cfae..e9d563c269 100644
> --- a/xen/arch/arm/domain_build.c
> +++ b/xen/arch/arm/domain_build.c
> @@ -2010,6 +2010,7 @@ void __init create_dom0(void)
> .grant_opts = XEN_DOMCTL_GRANT_version(opt_gnttab_max_version),
> };
> unsigned int flags = CDF_privileged | CDF_hardware;
> +domid_t domid;
> int rc;
>
> /* The vGIC for DOM0 is exactly emulating the hardware GIC */
> @@ -2034,19 +2035,25 @@ void __init create_dom0(void)
> if ( !llc_coloring_enabled )
> flags |= CDF_directmap;
>
> -dom0 = domain_create(0, &dom0_cfg, flags);
> +domid = domid_alloc(0);
> +if ( domid == DOMID_INVALID )
> +panic("Error allocating domain ID 0\n");
> +
> +dom0 = domain_create(domid, &dom0_cfg, flags);
> if ( IS_ERR(dom0) )
> -panic("Error creating domain 0 (rc = %ld)\n", PTR_ERR(dom0));
> +panic("Error creating domain %d (rc = %ld)\n", domid, PTR_ERR(dom0));
>
> if ( llc_coloring_enabled && (rc = dom0_set_llc_colors(dom0)) )
> -panic("Error initializing LLC coloring for domain 0 (rc = %d)\n",
> rc);
> +panic("Error initializing LLC coloring for domain %pd (rc = %d)\n",
> + dom0, rc);
>
> if ( alloc_dom0_vcpu0(dom0) == NULL )
> -panic("Error creating domain 0 vcpu0\n");
> +panic("Error creating domain %pdv0\n", dom0);
>
> rc = construct_dom0(dom0);
> if ( rc )
> -panic("Could not set up DOM0 guest OS (rc = %d)\n", rc);
> +panic("Could not set up guest OS for domain %pd (rc = %d)\n",
> + dom0, rc);
>
> set_xs_domain(dom0);
> }
> diff --git a/xen/arch/arm/setup.c b/xen/arch/arm/setup.c
> index 10b46d0684..c3959e8d8e 100644
> --- a/xen/arch/arm/setup.c
> +++ b/xen/arch/arm/setup.c
> @@ -418,6 +418,8 @@ void asmlinkage __init start_xen(unsigned long fdt_paddr)
>
> timer_init();
>
> +domid_init();
> +
> init_idle_domain();
>
> rcu_init();
> diff --git a/xen/arch/x86/setup.c b/xen/arch/x86/setup.c
> index 2518954124..02f665f520 100644
> --- a/xen/arch/x86/setup.c
> +++ b/xen/arch/x86/setup.c
> @@ -1030,8 +1030,11 @@ static struct domain *__init create_dom0(struct
> boot_info *bi)
> if ( iommu_enabled )
> dom0_cfg.flags |= XEN_DOMCTL_CDF_iommu;
>
> -/* Create initial domain. Not d0 for pvshim. */
> -bd->domid = get_initial_domain_id();
> +/* Allocate initial domain ID. Not d0 for pvshim. */
> +bd->domid = domid_alloc(get_initial_domain_id());
> +if ( bd->domid == DOMID_INVALID )
> +panic("Error allocating domain ID %d\n", get_initial_domain_id());
> +
> d = domain_create(bd->domid, &dom0_cfg,
> pv_shim ? 0 : CDF_privileged | CDF_hardware);
> if ( IS_ERR(d) )
> @@ -1063,7 +1066,7 @@ static struct domain *__init create_dom0(struct
> boot_info *bi)
>
> if ( (strlen(acpi_param) == 0) && acpi_disabled )
> {
> -printk("ACPI is disabled, notifying Domain 0 (acpi=off)\n");
> +printk("ACPI is disabled, notifying domain %pd (acpi=off)\n", d);
> safe_strcpy(acpi_param, "off");
> }
>
> @@ -1078,7 +1
