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

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 <[email protected]>
---
 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)
+{
+    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);
+        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;
-- 
2.34.1