Re: [PATCH 1/5] xen/sched: rtds: add global-EDF utilization admission control

[Juergen Gross <jgross@xxxxxxxx>]

On 26.08.26 06:57, Furkan Caliskan wrote:
> RTDS has no admission control: nothing stops the sum of all admitted
> units' (budget/period) reservations in a cpupool from exceeding
> what its pCPUs can actually provide. Once that happens, none of the
> EDF deadline guarantees this scheduler is built around still hold
> for the units sharing that pool.
>
> Introduce admission control to prevent this: reject a reservation
> whenever admitting it would push a cpupool's units over its capacity.
> Track a running utilization total per cpupool, and enforce it in
> rt_alloc_udata()/rt_free_udata(), the paired lifecycle hooks for a
> unit's creation and destruction. This catches the default
> period/budget every new unit gets.
>
> Utilization is represented as a fixed-point value: budget is
> left shifted by RTDS_UTIL_SHIFT (20 bits) and divided by period.
> A plain "(budget << RTDS_UTIL_SHIFT) / period" risks overflowing
> the multiply for large enough budgets. Rather than widen the
> arithmetic to tolerate any input, the input itself is bounded:
> rt_validate_params() rejects any budget above RTDS_MAX_BUDGET,
> chosen as the largest value that can be left-shifted by
> RTDS_UTIL_SHIFT without overflowing 64 bits, so the shift in
> rt_unit_utilization() can never overflow.
>
> A cpupool's capacity rt_utilization_cap() scales with the number of
> scheduling resources in it. It is calculated as:
> (number of sched_resources * RTDS_UTIL_SCALE * RTDS_UTIL_CAP_PCT / 100),
> where RTDS_UTIL_CAP_PCT controls how much of that capacity can
> actually be reserved; at 100% (its current value), all of it can be.
>
> Signed-off-by: Furkan Caliskan <frn1furkan10@xxxxxxxxx>
> ---
>   xen/common/sched/rt.c | 105 +++++++++++++++++++++++++++++++++++++++++-
>   1 file changed, 104 insertions(+), 1 deletion(-)
>
> diff --git a/xen/common/sched/rt.c b/xen/common/sched/rt.c
> index 0e9f04ea72..9126320801 100644
> --- a/xen/common/sched/rt.c
> +++ b/xen/common/sched/rt.c
> @@ -114,6 +114,24 @@
>    */
>   #define RTDS_MAX_PRIORITY_LEVEL (~0U)
>   
> +/*
> + * Fixed-point scale for utilization (budget/period)
> + */
> +#define RTDS_UTIL_SHIFT     20
> +#define RTDS_UTIL_SCALE     (1ULL << RTDS_UTIL_SHIFT)
> +
> +/*
> + * Largest budget safe to left-shift by RTDS_UTIL_SHIFT without
> + * overflowing 64 bits. Enforced in rt_validate_params().
> + */
> +#define RTDS_MAX_BUDGET_BITS  (64 - RTDS_UTIL_SHIFT)
> +#define RTDS_MAX_BUDGET       ((1ULL << RTDS_MAX_BUDGET_BITS) - 1)
> +
> +/*
> + * % of a cpupool's sched_resource capacity admitted units may sum up to.
> + */
> +#define RTDS_UTIL_CAP_PCT   100
> +
>   /*
>    * UPDATE_LIMIT_SHIFT: a constant used in rt_update_deadline(). When finding
>    * the next deadline, performing addition could be faster if the difference
> @@ -195,6 +213,9 @@ struct rt_private {
>       struct list_head replq;     /* ordered list of units that need 
> replenishment */
>   
>       cpumask_t tickled;          /* cpus been tickled */
> +
> +    /* Sum of admitted units' (budget/period), scaled by RTDS_UTIL_SCALE */
> +    uint64_t utilization;
>   };
>   
>   /*
> @@ -635,6 +656,54 @@ replq_reinsert(const struct scheduler *ops, struct rt_unit 
> *svc)
>           set_timer(&rt_priv(ops)->repl_timer, rearm_svc->cur_deadline);
>   }
>   
> +/*
> + * budget << RTDS_UTIL_SHIFT can't overflow: rt_validate_params()
> + * caps budget at RTDS_MAX_BUDGET. period == 0 means "no
> + * reservation" (a unit being removed), not an error.
> + */
> +static uint64_t
> +rt_unit_utilization(s_time_t period, s_time_t budget)
> +{
> +    if ( period <= 0 )
> +        return 0;
> +
> +    return ((uint64_t)budget << RTDS_UTIL_SHIFT) / (uint64_t)period;
> +}
> +
> +/*
> + * Utilization capacity of the cpupool domain d resides in.
> + */
> +static uint64_t
> +rt_utilization_cap(const struct domain *d)
> +{
> +    unsigned int cpus = cpumask_weight(cpupool_domain_master_cpumask(d));
> +
> +    return (uint64_t)cpus * RTDS_UTIL_SCALE * RTDS_UTIL_CAP_PCT / 100;
> +}
> +
> +/*
> + * Replaces a unit's reservation and updates prv->utilization
> + * to match. Growth that would push utilization over the
> + * cpupool's cap is refused. Removing a unit or shrinking
> + * a unit's reservation always succeed.
> + */
> +static int
> +rt_admission_test(struct rt_private *prv, const struct domain *d,
> +                  s_time_t old_period, s_time_t old_budget,
> +                  s_time_t new_period, s_time_t new_budget)
I think the function name isn't appropriate. The function doesn't test only, it
is setting the utilization, too.

What about rt_try_set_utilization() instead? And make the return type bool
(true on success).

> +{
> +    uint64_t old_util = rt_unit_utilization(old_period, old_budget);
> +    uint64_t new_util = rt_unit_utilization(new_period, new_budget);
> +    uint64_t total    = prv->utilization - old_util + new_util;
> +
> +    if ( new_util > old_util && total > rt_utilization_cap(d) )
> +        return -EINVAL;
> +
> +    prv->utilization = total;
> +
> +    return 0;
> +}
> +
>   /*
>    * Pick a valid resource for the unit vc
>    * Valid resource of an unit is intesection of unit's affinity
> @@ -864,6 +933,7 @@ rt_free_domdata(const struct scheduler *ops, void *data)
>   static void * cf_check
>   rt_alloc_udata(const struct scheduler *ops, struct sched_unit *unit, void *dd)
>   {
> +    struct rt_private *prv = rt_priv(ops);
>       struct rt_unit *svc;
>   
>       /* Allocate per-UNIT info */
> @@ -881,9 +951,30 @@ rt_alloc_udata(const struct scheduler *ops, struct 
> sched_unit *unit, void *dd)
>       __set_bit(__RTDS_extratime, &svc->flags);
>       svc->priority_level = 0;
>       svc->period = RTDS_DEFAULT_PERIOD;
> +
>       if ( !is_idle_unit(unit) )
> +    {
> +        unsigned long flags;
> +        int rc;
> +
>           svc->budget = RTDS_DEFAULT_BUDGET;
>   
> +        spin_lock_irqsave(&prv->lock, flags);
> +        rc = rt_admission_test(prv, unit->domain, 0, 0,
> +                                svc->period, svc->budget);
> +        spin_unlock_irqrestore(&prv->lock, flags);
> +
> +        if ( rc )
> +        {
> +            printk(XENLOG_WARNING
> +                   "RTDS: ADMISSION CONTROL: refusing unit %u of d%d,"
> +                   " would exceed utilization capacity of the cpupool\n",
> +                   unit->unit_id, unit->domain->domain_id);
> +            xfree(svc);
> +            return NULL;
> +        }
> +    }
> +
>       SCHED_STAT_CRANK(unit_alloc);
>   
>       return svc;
> @@ -892,8 +983,19 @@ rt_alloc_udata(const struct scheduler *ops, struct 
> sched_unit *unit, void *dd)
>   static void cf_check
>   rt_free_udata(const struct scheduler *ops, void *priv)
>   {
> +    struct rt_private *prv = rt_priv(ops);
>       struct rt_unit *svc = priv;
>   
> +    if ( svc && !is_idle_unit(svc->unit) )
> +    {
> +        unsigned long flags;
> +
> +        spin_lock_irqsave(&prv->lock, flags);
> +        rt_admission_test(prv, svc->unit->domain,
> +                           svc->period, svc->budget, 0, 0);
This use case clearly shows you are not only testing. :-)

> +        spin_unlock_irqrestore(&prv->lock, flags);
> +    }
> +
>       xfree(svc);
>   }
>   
> @@ -1389,7 +1491,8 @@ rt_validate_params(const struct xen_domctl_sched_rtds *rtds,
>       s_time_t b = MICROSECS(rtds->budget);
>   
>       if ( p < RTDS_MIN_PERIOD || p > RTDS_MAX_PERIOD ||
> -         b < RTDS_MIN_BUDGET || b > p )
> +         b < RTDS_MIN_BUDGET || b > p ||
> +         b > (s_time_t)RTDS_MAX_BUDGET )
>           return -EINVAL;
>   
>       *period = p;

Juergen

Attachment: OpenPGP_0xB0DE9DD628BF132F.asc
Description: OpenPGP public key

Attachment: OpenPGP_signature.asc
Description: OpenPGP digital signature