Re: [PATCH v6 1/2] xen/domain: unify domain ID allocation

[Julien Grall <julien@xxxxxxx>]

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, dmkhn@xxxxxxxxx wrote:
> On Fri, May 16, 2025 at 08:43:35AM +0000, 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 the the rangeset structure).
Lastly, as you pointed out this is requiring dynamic allocation. Which 
means domid_alloc() could now fail because Xen is out of memory. This 
feels a little be odd to have domid_alloc() returning -ENOMEM.
BTW, I noticed in your code you are using:

ASSERT(!rangeset_add_singleton(...))

In production build, ASSERTs() behaves like a NOP:

#define ASSERT(p) do { if ( 0 && (p) ) {} } while (0)

So rangeset_add_singleton() would not be called at all. This is also not 
the right way to handle failure that can happen at runtime. Instead, the 
error should be propagated.
Overall, I think a bitmap is more suitable to keep track of the domids 
allocated.
To make clear, I think increase the binary by 4KB is fine in this case. 
If someone is really concern of the increase, they would most likely not 
try to run 4KB domains, so we could potentially introduce 
CONFIG_MAX_DOMAIN to reduce the bitmap size and the number of domains 
(it is not a ask for this series).
Cheers,

--
Julien Grall