unlock unlimited code runs for $79, limited time →
NOSSLETTER.techLIVE
back to OSSpedia
kubernetes/kubernetes
mid8/10
data-structuresalgorithmic-optimization

[CPUManager] Skip partially acquired cores during full cores allocation

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

The problem

CPUManager's allocation logic incorrectly assumed that all cores, sockets, and uncore caches have the same number of CPUs, using integer division to determine group sizes. On modern hybrid or asymmetric CPU topologies (e.g., CPUs with a mix of core types or chips), this can result in wrong allocation decisions, such as treating partially used cores as fully available or miscounting CPUs per core/socket/uncore.

Why it's non-trivial

A naive fix might just adjust the division, but that doesn't address the root issue: real-world systems can have non-uniform numbers of CPUs per core, socket, or uncore cache. Relying on average or integer division fails when the topology is heterogeneous, leading to incorrect resource accounting and potentially breaking CPU isolation guarantees.

The approach

1. Remove integer division-based group size calculations, use actual topology data instead

Previously, the code used functions like CPUsPerCore(), CPUsPerSocket(), and CPUsPerUncore() that performed integer division to determine how many CPUs are in each group. These were replaced with queries to the actual topology data structure.

Example: Fixing isCoreFree and isSocketFree

-func (a *cpuAccumulator) isSocketFree(socketID int) bool {
-	return a.details.CPUsInSockets(socketID).Size() == a.topo.CPUsPerSocket()
+func (a *cpuAccumulator) isSocketFree(socketID int) bool {
+	return a.details.CPUsInSockets(socketID).Size() == a.topo.CPUDetails.CPUsInSockets(socketID).Size()
 }

Annotation:
Instead of comparing the number of free CPUs in a socket to an average (which could be wrong on asymmetric systems), this compares to the actual number of CPUs in that specific socket.

-func (a *cpuAccumulator) isCoreFree(coreID int) bool {
-	return a.details.CPUsInCores(coreID).Size() == a.topo.CPUsPerCore()
+func (a *cpuAccumulator) isCoreFree(coreID int) bool {
+	return a.details.CPUsInCores(coreID).Size() == a.topo.CPUDetails.CPUsInCores(coreID).Size()
 }

Annotation:
Same as above, but for cores: always use the actual count from the topology.

2. Remove now-unnecessary average-based helper functions

The PR removes the CPUsPerSocket and CPUsPerUncore functions, as their logic is now replaced by direct queries to the topology's CPUDetails mapping.

-// CPUsPerSocket returns the number of logical CPUs are associated with
-// each socket.
-func (topo *CPUTopology) CPUsPerSocket() int {
-	if topo.NumSockets == 0 {
-		return 0
-	}
-	return topo.NumCPUs / topo.NumSockets
-}
-
-// CPUsPerUncore returns the number of logicial CPUs that are associated with
-// each UncoreCache
-func (topo *CPUTopology) CPUsPerUncore() int {
-	if topo.NumUncoreCache == 0 {
-		return 0
-	}
-	return topo.NumCPUs / topo.NumUncoreCache
-}

Annotation:
These functions used integer division, which is unsafe on hybrid/asymmetric topologies. They are now deleted.

3. Update allocation logic to use per-instance counts

-func (a *cpuAccumulator) takeUncoreCache() {
-	numCPUsInUncore := a.topo.CPUsPerUncore()
-	for _, uncore := range a.sortAvailableUncoreCaches() {
+func (a *cpuAccumulator) takeUncoreCache() {
+	for _, uncore := range a.sortAvailableUncoreCaches() {
+		numCPUsInUncore := a.topo.CPUDetails.CPUsInUncoreCaches(uncore).Size()
 		// take full UncoreCache if the CPUs needed is greater than free UncoreCache size
 		if a.needsAtLeast(numCPUsInUncore) {
 			a.takeFullUncore()
 		}

Annotation:
Now, for each uncore cache, the code checks the actual number of CPUs associated with it, not an average.

4. Add new test topologies and test cases

The PR adds complex, realistic CPU topologies (e.g., Intel hybrid, AMD mixed-chip) to the test suite and new test cases that would fail with the old logic but pass with the new approach.

+	/*
+		Topology from Intel Core i7-14700
+		CPU(s):                28
+		On-line CPU(s) list:   0-27
+		Thread(s) per core:    2/1
+		Core(s) per socket:    20
+		Socket(s):             1
+		NUMA node(s):          1
+	*/
+	topoSingleSocketSingleNumaPerSocketPCoreHTECoreST = &topology.CPUTopology{
+		...
+	}

Annotation:
This adds a hybrid topology with both hyperthreaded and single-threaded cores.

+	/*
+		Topology from AMD EPYC 9005
+		CPU(s):                96
+		On-line CPU(s) list:   0-95
+		Thread(s) per core:    2
+		Socket(s):             2
+		Core(s) per socket:    16/32
+		NUMA node(s):          4
+	*/
+	topoDualSocketMultiNumaPerSocketMixedChips = &topology.CPUTopology{
+		...
+	}

Annotation:
This adds a topology with sockets of different core counts, which would break the old integer division logic.

From the review thread

The code looks good, passes tests and adds a new topology to use in future tests.
That's good all good,

but I would consider expanding this PR to cover:

  1. CPUsPerCore() is used also in takePartialUncore() and that function won't work also in hybrid topology
  2. CPUsPerCore() is also used in static policy for enforcing SMTA alignment and for launching takeByTopologyNUMADistributed with proper cpuGroupSize
  3. isSocketFree uses CPUsPerSocket() which also includes integer division. Probably setups with 2 sockets containing different chipsets are not popular, but possible if both chipsets belong to same family. CPUsPerSocket() can be easily changed to a.topo.CPUDetails.CPUsInSockets(socketID).Size() and after that function can be removed completely as it's not used anywhere else.
  4. takeUncoreCache() uses CPUsPerUncore() -the 3rd function using integer division. The code:
	numCPUsInUncore := a.topo.CPUsPerUncore()
	for _, uncore := range a.sortAvailableUncoreCaches() {
		// take full UncoreCache if the CPUs needed is greater than free UncoreCache size
		if a.needsAtLeast(numCPUsInUncore) {
			a.takeFullUncore()
		}
		[...]

can be changed to use particular number of CPUs with common uncore instead of average:

	for _, uncore := range a.sortAvailableUncoreCaches() {
		// take full UncoreCache if the CPUs needed is greater than free UncoreCache size
		numCPUsInUncore := a.topo.CPUDetails.CPUsInUncoreCaches(uncore).Size()
		if a.needsAtLeast(numCPUsInUncore) {
			a.takeFullUncore()
		}
		[...]

and after that CPUsPerUncore() can also be removed as not used anymore. Situation with multiple uncores having different number of CPUs is also not so popular, but e.g.
AMD EPYC 9005 can have a combination of Zen5 (8 cores, 16 CPUs) and Zen5c (16 cores, 32 CPUs) chips. They also allow to configure nnumber of NUMA nodes (and uncore caches), so you can get a setup with {NUMA0: 16CPUs (Zen5); NUMA1:16CPUs (Zen5); NUMA2: 32 CPUs (Zen5c); NUMA3: 32 CPUs (Zen5c)}

Removing all usages of CPUsPerCore would be hard. and would definitely require some consultation with sig node community on how to handle CPU allocations in asymmetric typologies.

I didn't find a ready answer in KEPs that introduced FullPhysicalCPUsOnly or SMTAlignment. Asymmetric topologies were not considered there. See 2626 and 4177

They were not because at time (esp. for 2626) a proper fix would require

  1. a complete overhaul of the topology reporting and representation
  2. (not directly relevant but still related) the ability to differentiate allocation request and result.

So IMO let's fix the issue with current approach and move rest of the work to separate PR (maybe also KEP for discussion with community first).

Indeed, if we can improve without big refactoring, let's do that.

Takeaways

  • Do not assume uniform hardware topology; always query the actual structure when possible.
    Integer division or averages can be dangerously wrong on modern, heterogeneous systems.

  • Remove abstractions that hide real-world complexity if they lead to incorrect behavior.
    Helper functions that "simplify" topology by averaging can cause subtle bugs; prefer direct data access.

  • When fixing allocation logic, add realistic test cases that would fail under the old assumptions.
    Tests based on real hardware topologies help prevent regressions and ensure correctness across diverse environments.