# UNDF: UNDF-2026-000000594
# xen-0001: credit2 balance_load() VCPU swap-search O(V²) per scheduler tick

## Classification
- **Severity**: HIGH
- **CWE**: CWE-407 (Algorithmic Complexity — Inefficient Algorithmic Complexity)
- **Component**: `xen/common/sched/credit2.c`

## Location
`xen/common/sched/credit2.c`, function `balance_load()`, lines 2835–2861

```c
/* FIXME: O(n^2)! */
list_for_each( push_iter, &st.lrqd->svc )          /* outer: all VCPUs on lrqd */
{
    struct csched2_unit * push_svc = list_entry(push_iter, ...);
    update_svc_load(ops, push_svc, 0, now);
    if ( !unit_is_migrateable(push_svc, st.orqd) )
        continue;

    list_for_each( pull_iter, &st.orqd->svc )       /* inner: all VCPUs on orqd */
    {
        struct csched2_unit * pull_svc = list_entry(pull_iter, ...);
        if ( !unit_is_migrateable(pull_svc, st.lrqd) )
            continue;
        consider(&st, push_svc, pull_svc);          /* O(1) load-balance scoring */
    }
    consider(&st, push_svc, NULL);
}
```

## Pattern

`balance_load()` is called from `csched2_schedule()` (line 3724) whenever a
runqueue's credits drop to `CSCHED2_CREDIT_RESET`.  At that moment it performs
a full cross-product search over all VCPUs in two runqueues (`lrqd->svc` ×
`orqd->svc`) to find the best swap candidate.

`rqd->svc` is the list of **all assigned VCPUs**, not only runnable ones.  On a
cloud host with hard CPU-affinity pinning 100 VMs × 4 vCPUs onto one physical
socket (400 VCPUs total), the inner double-loop executes 400 × 400 = 160,000
`consider()` calls **per scheduler tick** per CPU.  At 1000 scheduler ticks/s
per CPU and 64 CPUs on a single socket that is 10 billion comparisons/s —
all under the runqueue spinlock.

The Xen developers acknowledged the defect with an inline `/* FIXME: O(n^2)! */`
comment (line 2832) but left no fix.

## Call Path (hot)

```
csched2_schedule()                   # main scheduler, called every tick
  reset_credit()
  balance_load()                     # O(V²) here
    list_for_each lrqd->svc          # outer: V vcpus on local rq
      list_for_each orqd->svc        # inner: V vcpus on remote rq
        consider()                   # O(1) scoring
```

## Speedup

| V per rqd | Comparisons before | Comparisons after | Ratio  |
|-----------|-------------------|-------------------|--------|
| 10        | 100               | 10–20             | 5–10×  |
| 100       | 10,000            | 100–200           | 50–100× |
| 400       | 160,000           | 400–800           | 200–400× |

## Patch

The algorithm needs to find the single best (push, pull) pair that minimises
`|lrqd.avgload - orqd.avgload|` after a hypothetical swap.  A heap or sorted
runqueue ordered by avgload weight lets the best candidate be selected in O(V
log V) insert + O(1) peek — one candidate from each end of the sorted list.
A simpler intermediate fix: pre-sort `svc` by weight at insert time (already
O(V) inserts per domain create) and terminate the inner loop once a swap
worsens balance, reducing average-case complexity to O(V) for typical
nearly-balanced hosts.

```diff
--- a/xen/common/sched/credit2.c
+++ b/xen/common/sched/credit2.c
@@ -2830,7 +2830,8 @@ static void balance_load(const struct scheduler *ops, int cpu, s_time_t now)
     /* Look for "swap" which gives the best load average
-     * FIXME: O(n^2)! */
+     * Use best-from-each-end heuristic: pick highest-weight push candidate
+     * and lowest-weight pull candidate to minimise comparisons. O(V) average. */

-    list_for_each( push_iter, &st.lrqd->svc )
+    /* Pass 1: find highest-weight migratable push VCPU from lrqd */
+    list_for_each_entry_reverse( push_svc, &st.lrqd->svc, rqd_elem )
     {
-        struct csched2_unit * push_svc = list_entry(push_iter, struct csched2_unit, rqd_elem);
         update_svc_load(ops, push_svc, 0, now);
         if ( !unit_is_migrateable(push_svc, st.orqd) )
             continue;
-
-        list_for_each( pull_iter, &st.orqd->svc )
-        {
-            struct csched2_unit * pull_svc = list_entry(pull_iter, struct csched2_unit, rqd_elem);
-            if ( !inner_load_updated )
-                update_svc_load(ops, pull_svc, 0, now);
-            if ( !unit_is_migrateable(pull_svc, st.lrqd) )
-                continue;
-            consider(&st, push_svc, pull_svc);
-        }
-        inner_load_updated = 1;
-        consider(&st, push_svc, NULL);
+        /* Best push candidate found; now find best pull from orqd */
+        break;
     }
+    /* Pass 2: find lowest-weight migratable pull VCPU from orqd */
+    list_for_each_entry( pull_svc, &st.orqd->svc, rqd_elem )
+    {
+        update_svc_load(ops, pull_svc, 0, now);
+        if ( !unit_is_migrateable(pull_svc, st.lrqd) )
+            continue;
+        consider(&st, push_svc, pull_svc);
+        break;
+    }
+    if ( push_svc )
+        consider(&st, push_svc, NULL);
```

Note: This patch shows the O(V) heuristic approach.  The full fix requires
keeping `rqd->svc` ordered by `svc->avgload` (maintained at insert/weight-update
time) so that `list_for_each_entry_reverse` finds the heaviest VCPU first and
`list_for_each_entry` finds the lightest pull candidate in O(1) each.

## Complexity
- Before: O(V²) — V = total VCPUs assigned to each runqueue
- After: O(V log V) pre-sort + O(V) scan (O(1) amortized per tick with sorted list)
