/
policy_best_effort.go
199 lines (169 loc) · 7.2 KB
/
policy_best_effort.go
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
/*
Copyright 2019 The Kubernetes Authors.
Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at
http://www.apache.org/licenses/LICENSE-2.0
Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
package topologymanager
import (
"k8s.io/klog"
"k8s.io/kubernetes/pkg/kubelet/cm/topologymanager/bitmask"
"k8s.io/kubernetes/pkg/kubelet/lifecycle"
)
type bestEffortPolicy struct {
//List of NUMA Nodes available on the underlying machine
numaNodes []int
}
var _ Policy = &bestEffortPolicy{}
// PolicyBestEffort policy name.
const PolicyBestEffort string = "best-effort"
// NewBestEffortPolicy returns best-effort policy.
func NewBestEffortPolicy(numaNodes []int) Policy {
return &bestEffortPolicy{numaNodes: numaNodes}
}
func (p *bestEffortPolicy) Name() string {
return PolicyBestEffort
}
func (p *bestEffortPolicy) canAdmitPodResult(hint *TopologyHint) lifecycle.PodAdmitResult {
return lifecycle.PodAdmitResult{
Admit: true,
}
}
func (p *bestEffortPolicy) Merge(providersHints []map[string][]TopologyHint) (TopologyHint, lifecycle.PodAdmitResult) {
hint := mergeProvidersHints(p, p.numaNodes, providersHints)
admit := p.canAdmitPodResult(&hint)
return hint, admit
}
// Iterate over all permutations of hints in 'allProviderHints [][]TopologyHint'.
//
// This procedure is implemented as a recursive function over the set of hints
// in 'allproviderHints[i]'. It applies the function 'callback' to each
// permutation as it is found. It is the equivalent of:
//
// for i := 0; i < len(providerHints[0]); i++
// for j := 0; j < len(providerHints[1]); j++
// for k := 0; k < len(providerHints[2]); k++
// ...
// for z := 0; z < len(providerHints[-1]); z++
// permutation := []TopologyHint{
// providerHints[0][i],
// providerHints[1][j],
// providerHints[2][k],
// ...
// providerHints[-1][z]
// }
// callback(permutation)
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
// 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{})
}
// Merge the hints from all hint providers to find the best one.
func mergeProvidersHints(policy Policy, numaNodes []int, providersHints []map[string][]TopologyHint) TopologyHint {
// Set the default affinity as an any-numa affinity containing the list
// of NUMA Nodes available on this machine.
defaultAffinity, _ := bitmask.NewBitMask(numaNodes...)
// Loop through all hint providers and save an accumulated list of the
// hints returned by each hint provider. If no hints are provided, assume
// that provider has no preference for topology-aware allocation.
var allProviderHints [][]TopologyHint
for _, hints := range providersHints {
// If hints is nil, insert a single, preferred any-numa hint into allProviderHints.
if len(hints) == 0 {
klog.Infof("[topologymanager] Hint Provider has no preference for NUMA affinity with any resource")
allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}})
continue
}
// Otherwise, accumulate the hints for each resource type into allProviderHints.
for resource := range hints {
if hints[resource] == nil {
klog.Infof("[topologymanager] Hint Provider has no preference for NUMA affinity with resource '%s'", resource)
allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}})
continue
}
if len(hints[resource]) == 0 {
klog.Infof("[topologymanager] Hint Provider has no possible NUMA affinities for resource '%s'", resource)
allProviderHints = append(allProviderHints, []TopologyHint{{nil, false}})
continue
}
allProviderHints = append(allProviderHints, hints[resource])
}
}
// Iterate over all permutations of hints in 'allProviderHints'. Merge the
// hints in each permutation by taking the bitwise-and of their affinity masks.
// Return the hint with the narrowest NUMANodeAffinity of all merged
// permutations that have at least one NUMA ID set. If no merged mask can be
// found that has at least one NUMA ID set, return the 'defaultAffinity'.
bestHint := TopologyHint{defaultAffinity, false}
iterateAllProviderTopologyHints(allProviderHints, func(permutation []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 {
if hint.NUMANodeAffinity == nil {
numaAffinities = append(numaAffinities, defaultAffinity)
} else {
numaAffinities = append(numaAffinities, hint.NUMANodeAffinity)
}
if !hint.Preferred {
preferred = false
}
// Special case PolicySingleNumaNode to only prefer hints where
// all providers have a single NUMA affinity set.
if policy != nil && policy.Name() == PolicySingleNumaNode && hint.NUMANodeAffinity != nil && hint.NUMANodeAffinity.Count() > 1 {
preferred = false
}
}
// Merge the affinities using a bitwise-and operation.
mergedAffinity, _ := bitmask.NewBitMask(numaNodes...)
mergedAffinity.And(numaAffinities...)
// Build a mergedHintfrom the merged affinity mask, indicating if an
// preferred allocation was used to generate the affinity mask or not.
mergedHint := TopologyHint{mergedAffinity, preferred}
// Only consider mergedHints that result in a NUMANodeAffinity > 0 to
// replace the current bestHint.
if mergedHint.NUMANodeAffinity.Count() == 0 {
return
}
// If the current bestHint is non-preferred and the new mergedHint is
// preferred, always choose the preferred hint over the non-preferred one.
if mergedHint.Preferred && !bestHint.Preferred {
bestHint = mergedHint
return
}
// If the current bestHint is preferred and the new mergedHint is
// non-preferred, never update bestHint, regardless of mergedHint's
// narowness.
if !mergedHint.Preferred && bestHint.Preferred {
return
}
// If mergedHint and bestHint has the same preference, only consider
// mergedHints that have a narrower NUMANodeAffinity than the
// NUMANodeAffinity in the current bestHint.
if !mergedHint.NUMANodeAffinity.IsNarrowerThan(bestHint.NUMANodeAffinity) {
return
}
// In all other cases, update bestHint to the current mergedHint
bestHint = mergedHint
})
return bestHint
}