Opensource internals

Anding the NUMA Bitmasks: How the Topology Manager Merges Three Providers

13 min read Jay Hubbert

The kubelet's topology manager merges hints from the CPU, memory and device managers by bitwise-AND of NUMA affinity bitmasks, enumerating the Cartesian product of all provider hints.

TL;DR: The topology manager gathers hints from every hint provider — the CPU manager, the memory manager, the device manager — and merges them by bitwise AND of the NUMA affinity bitmasks. The intersection is the only set of NUMA nodes that satisfies all providers at once. Because the merge space is the Cartesian product of every provider’s hint list, the code enumerates the permutations recursively. The subtle part is the score aggregation: a Score of 0 does not mean “zero utilization”, it means “no signal”, so only hints with an affinity and a non-zero score are averaged.

Topology-aware allocation on a NUMA machine is a constraint satisfaction problem. The CPU manager wants the pod’s CPUs on one node. The memory manager wants its memory on one node. The device manager wants the GPU on a node that is also the one with the CPUs. Each of these is a partial answer: a set of acceptable NUMA nodes. The topology manager’s job is to intersect them.

The obvious implementation of “intersect these sets” is to materialise the sets and intersect them pairwise. Kubernetes does not do that, for a reason that becomes obvious once you look at the data structures: the affinity is already a bitmask, and the intersection of bitmasks is a single machine instruction.

The bitmask

The affinity is a uint64, one bit per NUMA node:

go 
// pkg/kubelet/cm/topologymanager/bitmask/bitmask.go:45
type bitMask uint64

and the setter enforces the range:

go 
// pkg/kubelet/cm/topologymanager/bitmask/bitmask.go:64
func (s *bitMask) Add(bits ...int) error {
	mask := *s
	for _, i := range bits {
		if i < 0 || i >= 64 {
			return fmt.Errorf("bit number must be in range 0-63")
		}
		mask |= 1 << uint64(i)
	}
	*s = mask
	return nil
}

bit number must be in range 0-63. A machine with 65 NUMA nodes cannot be represented. In practice the topology manager refuses to start long before that, because of a different explosion.

The Cartesian product

Each provider returns a list of hints — one per resource it manages, each with its own affinity mask and its own preferred flag. Merging them means trying every combination, which the code does with a recursive generator:

go 
// pkg/kubelet/cm/topologymanager/policy.go:377
func iterateAllProviderTopologyHints(allProviderHints [][]TopologyHint, callback func([]TopologyHint)) {
	// Internal helper function to accumulate the permutation before calling the callback.
	var iterate func(i int, accum []TopologyHint)
	iterate = func(i int, accum []TopologyHint) {
		// Base case: we have looped through all providers and have a full permutation.
		if i == len(allProviderHints) {
			callback(accum)
			return
		}

		// Loop through all hints for provider 'i', and recurse to build the
		// permutation of this hint with all hints from providers 'i++'.
		for j := range allProviderHints[i] {
			iterate(i+1, append(accum, allProviderHints[i][j]))
		}
	}
	iterate(0, []TopologyHint{})
}

The growth is multiplicative: with three providers offering 8 hints each, that is 512 permutations to consider per admission. This is exactly why the number of NUMA nodes is capped:

go 
// pkg/kubelet/cm/topologymanager/topology_manager.go:32
const (
	// defaultMaxAllowableNUMANodes specifies the maximum number of NUMA Nodes that
	// the TopologyManager supports on the underlying machine.
	//
	// At present, having more than this number of NUMA Nodes will result in a
	// state explosion when trying to enumerate possible NUMAAffinity masks and
	// generate hints for them. As such, if more NUMA Nodes than this are
	// present on a machine and the TopologyManager is enabled, an error will
	// be returned and the TopologyManager will not be loaded.
	defaultMaxAllowableNUMANodes = 8

Eight NUMA nodes by default. Not because the bitmask cannot hold more, but because the enumeration cannot. The check is at startup:

go 
// pkg/kubelet/cm/topologymanager/topology_manager.go:206
	if topologyPolicyName != PolicyNone && len(numaInfo.Nodes) > opts.MaxAllowableNUMANodes {
		return nil, fmt.Errorf("unsupported on machines with more than %v NUMA Nodes", opts.MaxAllowableNUMANodes)
	}

The max-allowable-numa-nodes policy option can raise the limit above 8 — lowering it below 8 is rejected outright, raising it is allowed with a warning (pkg/kubelet/cm/topologymanager/policy_options.go:89).

The merge

Each permutation is merged into a single hint by ANDing the masks:

go 
// pkg/kubelet/cm/topologymanager/policy.go:71
func mergePermutation(logger klog.Logger, defaultAffinity bitmask.BitMask, permutation []TopologyHint) TopologyHint {
	// Get the NUMANodeAffinity from each hint in the permutation and see if any
	// of them encode unpreferred allocations.
	preferred := true
	var numaAffinities []bitmask.BitMask
	for _, hint := range permutation {
		// Only consider hints that have an actual NUMANodeAffinity set.
		if hint.NUMANodeAffinity != nil {
			numaAffinities = append(numaAffinities, hint.NUMANodeAffinity)
			// Only mark preferred if all affinities are equal.
			if !hint.NUMANodeAffinity.IsEqual(numaAffinities[0]) {
				preferred = false
			}
		}
		// Only mark preferred if all affinities are preferred.
		if !hint.Preferred {
			preferred = false
		}
	}

	// Merge the affinities using a bitwise-and operation.
	mergedAffinity := bitmask.And(defaultAffinity, numaAffinities...)

Two subtleties. First, defaultAffinity — the mask of all NUMA nodes on the machine — is ANDed in as well, so a hint can never escape the machine’s real topology. Second, the “preferred” flag requires all the affinities in the permutation to be equal, not just non-empty. If the CPU manager says “node 0” and the memory manager says “node 1”, the AND is empty and the merged hint is not preferred.

The merged affinity can legitimately be empty (zero bits): that means “no single NUMA node satisfies everyone”, which is a real outcome the policy decides what to do with.

The score: zero is not zero

This is the part that catches people out. The merged hint carries a Score — a packing-efficiency signal — and the aggregation looks wrong at first glance:

go 
// pkg/kubelet/cm/topologymanager/policy.go:53
func aggregateHintScores(permutation []TopologyHint) (int64, bool) {
	var sum int64
	var count int64
	for _, hint := range permutation {
		if hint.NUMANodeAffinity != nil && hint.Score > 0 {
			sum += hint.Score
			count++
		}
	}
	if count == 0 {
		return 0, false
	}
	return sum / count, true
}

A Score of 0 means “no signal”. It does not mean “the NUMA node is completely empty” — which would be zero percent utilization, the best possible packing. If you averaged zeros in, a provider with nothing to say would drag every merged score toward zero, and a merge of {0, 0, 90} would score 30 instead of 90. The count == 0 early return handles the case where nobody has a signal: the merged score is 0 and hasScores is false.

The doc comment above the function states the rule outright: “Only hints with an affinity and a non-zero Score are counted: Score 0 means ’no signal’, not ‘zero utilization’”. It also notes the arithmetic detail — “we use integer division that truncates towards zero. For example, scores of 40 and 81 aggregate to 60.”

The score itself comes from a shared helper that all three resource managers use, so their numbers stay comparable:

go 
// pkg/kubelet/cm/topologymanager/score.go:31
func UtilizationScore(allocatable, assigned int64) int64 {
	if allocatable <= 0 {
		return 0
	}
	return max(1, assigned*100/allocatable)
}

max(1, ...) is the important bit. If anything is allocatable, the score is at least 1 — so a score of 0 unambiguously means “no signal”, and 0 and 1 are not neighbouring values. Without the floor, a nearly-empty NUMA node would score 0 and be indistinguishable from “no opinion”. The comment on UtilizationScore also says the score “does not drive hint selection” — it is informational. The preferred flag and the affinity width do the deciding.

Picking the best permutation

The merger walks every permutation, merges it, and keeps the best:

go 
// pkg/kubelet/cm/topologymanager/policy.go:336
func (m HintMerger) Merge(logger klog.Logger) TopologyHint {
	defaultAffinity := m.NUMAInfo.DefaultAffinityMask()

	var bestHint *TopologyHint
	iterateAllProviderTopologyHints(m.Hints, func(permutation []TopologyHint) {
		// Get the NUMANodeAffinity from each hint in the permutation and see if any
		// of them encode unpreferred allocations.
		mergedHint := mergePermutation(logger, defaultAffinity, permutation)

		// Compare the current bestHint with the candidate mergedHint and
		// update bestHint if appropriate.
		bestHint = m.compare(bestHint, &mergedHint)
	})

	if bestHint == nil {
		bestHint = &TopologyHint{NUMANodeAffinity: defaultAffinity, Preferred: false}
	}

	return *bestHint
}

The comparison is a strict priority ordering. The very first check rejects any candidate whose affinity is empty — an empty affinity means the AND eliminated every node, so no allocation satisfies this permutation. Rejected here, a wider-but-viable hint beats a narrower-but-impossible one. Then preferred always beats non-preferred, in both directions:

go 
// pkg/kubelet/cm/topologymanager/policy.go:213
func (m HintMerger) compare(current *TopologyHint, candidate *TopologyHint) *TopologyHint {
	// Only consider candidates that result in a NUMANodeAffinity > 0 to
	// replace the current bestHint.
	if candidate.NUMANodeAffinity.Count() == 0 {
		return current
	}

	// If no current bestHint is set, return the candidate as the bestHint.
	if current == nil {
		return candidate
	}

	// If the current bestHint is non-preferred and the candidate hint is
	// preferred, always choose the preferred hint over the non-preferred one.
	if !current.Preferred && candidate.Preferred {
		return candidate
	}

Between two preferred hints, the tie-break is the affinity mask, and it depends on the policy:

go 
// pkg/kubelet/cm/topologymanager/policy.go:184
	compareNumaAffinityMasks := func(current, candidate *TopologyHint) *TopologyHint {
		// If current and candidate bitmasks are the same, prefer current hint.
		if candidate.NUMANodeAffinity.IsEqual(current.NUMANodeAffinity) {
			return current
		}

		// Otherwise compare the hints, based on the policy options provided
		var best bitmask.BitMask
		if (policyName != PolicySingleNumaNode) && opts.PreferClosestNUMA {
			best = numaInfo.Closest(current.NUMANodeAffinity, candidate.NUMANodeAffinity)
		} else {
			best = numaInfo.Narrowest(current.NUMANodeAffinity, candidate.NUMANodeAffinity)
		}

Narrowest is the default — pick the mask with fewer bits set. But with the prefer-closest-numa-nodes policy option, and only for policies other than single-numa-node, the tie-break becomes NUMA distance:

go 
// pkg/kubelet/cm/topologymanager/numa_info.go:68
func (n *NUMAInfo) Closest(m1 bitmask.BitMask, m2 bitmask.BitMask) bitmask.BitMask {
	// If the length of both bitmasks aren't the same, choose the one that is narrowest.
	if m1.Count() != m2.Count() {
		return n.Narrowest(m1, m2)
	}

	m1Distance := n.NUMADistances.CalculateAverageFor(m1)
	m2Distance := n.NUMADistances.CalculateAverageFor(m2)
	// If average distance is the same, take bitmask with more lower-number bits set.
	if m1Distance == m2Distance {
		if m1.IsLessThan(m2) {
			return m1
		}
		return m2
	}

The rule is the hardware one: a NUMA node’s distance to itself is 10, to a sibling node 20, and to a remote node 30 or more. Two masks of equal width are compared by their average distance, and the mask whose nodes are closest to the reader wins — allocating across distant NUMA nodes means crossing the interconnect. This option requires cadvisor to report node distances, and it is explicitly not supported on Windows (pkg/kubelet/cm/topologymanager/numa_info.go:44).

The three policies

All three policies share the merge machinery; they differ in the admission decision.

Best-effort always admits. It is the fallback and it never rejects:

go 
// pkg/kubelet/cm/topologymanager/policy_best_effort.go:41
func (p *bestEffortPolicy) canAdmitPodResult(_ *TopologyHint) bool {
	return true
}

Best-effort still computes a merged hint — the hint is passed to the resource managers so they try to align — but an unalignable pod is admitted anyway, with a CPU allocation that spans NUMA nodes and a memory allocation that is interleaved.

Restricted admits only a preferred hint:

go 
// pkg/kubelet/cm/topologymanager/policy_restricted.go:39
func (p *restrictedPolicy) canAdmitPodResult(hint *TopologyHint) bool {
	return hint.Preferred
}

This is the important one. “Preferred” means every provider in the winning permutation agreed on the same affinity mask — so the pod’s CPUs, memory and devices all land on one NUMA node. A pod that cannot be aligned that way is rejected with a TopologyAffinityError, whose message is deliberately vague — “Resources cannot be allocated with Topology locality” — because the kubelet cannot tell you which provider conflicted.

Single-numa-node filters first, then admits. It restricts the hint space to hints with exactly one bit set before merging:

go 
// pkg/kubelet/cm/topologymanager/policy_single_numa_node.go:46
func filterSingleNumaHints(allResourcesHints [][]TopologyHint) [][]TopologyHint {
	var filteredResourcesHints [][]TopologyHint
	for _, oneResourceHints := range allResourcesHints {
		var filtered []TopologyHint
		for _, hint := range oneResourceHints {
			if hint.NUMANodeAffinity == nil && hint.Preferred {
				filtered = append(filtered, hint)
			}
			if hint.NUMANodeAffinity != nil && hint.NUMANodeAffinity.Count() == 1 && hint.Preferred {
				filtered = append(filtered, hint)
			}
		}
		filteredResourcesHints = append(filteredResourcesHints, filtered)
	}
	return filteredResourcesHints
}

Note the hint.Preferred condition on both branches — only hints the provider considers good survive the filter. A provider that says “I could do nodes 0, 1 or 2, and I don’t care” is filtered out entirely, because its preferred hints are the ones with a single bit.

And then there is the collapse back to nil:

go 
// pkg/kubelet/cm/topologymanager/policy_single_numa_node.go:71
	if bestHint.NUMANodeAffinity.IsEqual(p.numaInfo.DefaultAffinityMask()) {
		bestHint = TopologyHint{NUMANodeAffinity: nil, Preferred: bestHint.Preferred}
	}

If the merged affinity came out equal to all NUMA nodes on the machine, that means no provider actually constrained anything, so the hint collapses to nil — “no topology preference”. The nil affinity is the signal downstream that says “do not restrict this pod to a NUMA node”.

The provider normalisation. Before any of this, the hints are normalised. A provider that returns nothing for a resource is not a veto — it is an absence of opinion. Three distinct cases exist, and they are not the same: no hints at all for the provider → a nil-affinity preferred hint (“I do not care”); no hints for a specific resource → also nil-affinity preferred; and the provider has hints for a resource but they are all empty → a nil-affinity hint that is not preferred (“I have an opinion, and the opinion is that I cannot satisfy this here”). That third case is why the merge’s preferred computation distinguishes nil affinity from a non-preferred nil affinity. The normalisation is filterProvidersHints (pkg/kubelet/cm/topologymanager/policy.go:104).

The best-non-preferred tie-break. When two hints are both non-preferred, the merger picks the one that is least bad — the one that covers the most NUMA nodes without exceeding what the strictest provider can satisfy. maxOfMinAffinityCounts (pkg/kubelet/cm/topologymanager/policy.go:156) computes that bound: for each provider, the smallest affinity it offers, then the largest of those across providers. The field comment spells out the intent — “prefer a hint that has an affinity mask that includes all of the NUMA nodes from the provider that requires the most NUMA nodes to satisfy its allocation.”

Wrapping up

The one thing to remember: the topology manager intersects providers by bitwise-AND of their NUMA affinity bitmasks (pkg/kubelet/cm/topologymanager/policy.go:71), enumerating the full Cartesian product of provider hints recursively (pkg/kubelet/cm/topologymanager/policy.go:377). A Score of 0 means “no signal”, not “zero utilization” — that is why UtilizationScore floors at 1 whenever anything is allocatable, and why aggregateHintScores skips zero-score hints.

The part people get wrong: that the topology manager is a soft optimisation. Under restricted or single-numa-node, a pod that cannot be aligned is rejected with a TopologyAffinityError (“Resources cannot be allocated with Topology locality”), and the kubelet does not tell you which provider conflicted. If a pod is stuck in ContainerCreating on a NUMA machine, check whether the CPU manager’s exclusive-CPU reservation and the device manager’s GPU placement can actually be satisfied on the same node — not on two different nodes.

What to go do about it: the policy is set with the kubelet’s --topology-manager-policy flag (none, best-effort, restricted, single-numa-node) and the scope with --topology-manager-scope (container or pod). Use pod scope if you want the whole pod’s resources aligned together rather than each container separately. On multi-NUMA hardware prefer single-numa-node with the prefer-closest-numa-nodes option to get distance-aware tie-breaks (Linux only — it needs cadvisor node distances). And watch the container_aligned_compute_resources and container_aligned_compute_resources_failure kubelet metrics: a rising failure counter under restricted means the merge is producing empty affinities, which almost always means the CPU and device managers are disagreeing about which node to use.

KubernetesInternalsKubelet