CPUMANAGER: spread CPUs across cores using topology

Project: kubernetes/kubernetes | Language: Go | Concepts: algorithmic-optimization, data-structures, testing-strategy | Difficulty: mid
Link: https://github.com/kubernetes/kubernetes/pull/140766

The problem

The CPUManager in Kubernetes had a bug in its "spread CPUs across cores" mode: it selected CPUs for workloads based on logical CPU numbering, not on the actual physical topology. On many systems, this meant that sibling hyperthreads from the same physical core could be allocated before using other available cores, reducing the effectiveness of CPU isolation and performance.

Why it's non-trivial

A naive fix might just sort CPU IDs differently or shuffle the selection order, but that wouldn't guarantee that CPUs are spread out across as many physical cores as possible. The logic must account for real hardware topology (sockets, cores, threads) and handle a variety of layouts, including non-contiguous or non-standard CPU numbering, multiple sockets, and varying numbers of threads per core.

The approach

The core change is in sortAvailableCPUsSpread(). The new algorithm explicitly walks the topology to pick one CPU per core in a round-robin fashion, rather than just sorting by CPU ID.

Old code (simplified):

-		cpus := a.details.CPUsInSockets(socket).UnsortedList()
-		sort.Ints(cpus)
-		result = append(result, cpus...)

Previously, CPUs in each socket were just sorted numerically and appended, which could group sibling threads from the same core together.

New code:

+		cores := a.details.CoresInSockets(socket).UnsortedList()
+		// Deliberately sorted by free-CPU count instead of sortAvailableCores():
+		// sortAvailableCores() performs NUMA ranking, but spread mode at
+		// this stage only cares about physical-core coverage.
+		a.sort(cores, a.details.CPUsInCores)
+		cpusPerCore := make([][]int, 0, len(cores))
+		maxCPUsPerCore := 0
+		for _, core := range cores {
+			cpus := a.details.CPUsInCores(core).List()
+			cpusPerCore = append(cpusPerCore, cpus)
+			if len(cpus) > maxCPUsPerCore {
+				maxCPUsPerCore = len(cpus)
+			}
+		}
+		for cpuIndex := 0; cpuIndex < maxCPUsPerCore; cpuIndex++ {
+			for _, cpus := range cpusPerCore {
+				if cpuIndex < len(cpus) {
+					result = append(result, cpus[cpuIndex])
+				}
+			}
+		}

This code:

• Finds all cores in a socket.
• Sorts them by number of free CPUs (not by NUMA affinity, which is intentionally ignored for spreading).
• Builds a list of available CPUs per core.
• Selects CPUs round-robin: first one CPU from each core, then the second from each (if present), and so on. This ensures that sibling threads are only used after every physical core has contributed a CPU.

Testing improvements:

A comprehensive new table-driven test was added:

+func TestCPUAccumulatorFreeCPUsSpreadRoundRobin(t *testing.T) {
+	// ...
+	testCases := []struct {
+		description   string
+		topo          *topology.CPUTopology
+		availableCPUs cpuset.CPUSet
+		expect        []int
+	}{
+		// Synthetic topology: contiguous sibling CPU IDs, not representative of known hardware.
+		{
+			description: "contiguous sibling CPU IDs",
+			topo: &topology.CPUTopology{
+				NumCPUs:    8,
+				NumSockets: 1,
+				NumCores:   4,
+				CPUDetails: map[int]topology.CPUInfo{
+					0: {CoreID: 0, SocketID: 0, NUMANodeID: 0},
+					1: {CoreID: 0, SocketID: 0, NUMANodeID: 0},
+					2: {CoreID: 1, SocketID: 0, NUMANodeID: 0},
+					3: {CoreID: 1, SocketID: 0, NUMANodeID: 0},
+					4: {CoreID: 2, SocketID: 0, NUMANodeID: 0},
+					5: {CoreID: 2, SocketID: 0, NUMANodeID: 0},
+					6: {CoreID: 3, SocketID: 0, NUMANodeID: 0},
+					7: {CoreID: 3, SocketID: 0, NUMANodeID: 0},
+				},
+			},
+			availableCPUs: cpuset.New(0, 1, 2, 3, 4, 5, 6, 7),
+			expect:        []int{0, 2, 4, 6, 1, 3, 5, 7},
+		},
+		// ... (other cases for interleaved IDs, arbitrary numbering, multi-socket, partial cores, >2 threads/core, multi-NUMA)
+	}
+	// ...
+}

This test covers a variety of synthetic and realistic CPU topologies, ensuring the new logic works regardless of CPU numbering or hardware layout.

Updated expectations in existing tests:

-			mustParseCPUSet(t, "0-2,9-10,13-14,21-22,25-26,33"),
+			cpuset.New(0, 50, 57, 58, 71, 72, 79, 80, 87, 88, 95, 96),

This reflects the new, correct behavior: CPUs are now spread across physical cores, not packed onto as few as possible.

From the review thread

The round-robin-across-cores logic reads clearly and correctly handles cores with differing numbers of available CPUs (the cpuIndex < len(cpus) guard). Left a couple of non-blocking inline comments below.

One scope question following @ffromani's earlier note on #140688 about auditing other naive sort.Ints() call sites: the remaining one in sortAvailableCPUsPacked() sorts CPUs within a single core, where numbering order is harmless, so I think it's fine to leave. Could you confirm in the PR description that you audited the rest of the allocation path and this spread fix was the only topology-relevant offender? That closes the loop on Francesco's request to handle them in one PR.

thanks for the fix, LGTM with some minor improvements in the tests

Takeaways

• Always use actual hardware topology, not logical numbering, when allocating resources that map to physical components (like CPU cores).
• When designing algorithms for hardware resource allocation, test against a variety of synthetic and real-world topologies, including edge cases (non-contiguous IDs, multi-socket, variable threads per core).
• Document intentional divergences from related code paths (e.g., ignoring NUMA affinity for spreading) to prevent future accidental "fixes" that would break the intended behavior.