1 /* 2 Copyright 2019 The Kubernetes Authors. 3 4 Licensed under the Apache License, Version 2.0 (the "License"); 5 you may not use this file except in compliance with the License. 6 You may obtain a copy of the License at 7 8 http://www.apache.org/licenses/LICENSE-2.0 9 10 Unless required by applicable law or agreed to in writing, software 11 distributed under the License is distributed on an "AS IS" BASIS, 12 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 See the License for the specific language governing permissions and 14 limitations under the License. 15 */ 16 17 package topologymanager 18 19 import ( 20 "k8s.io/klog/v2" 21 "k8s.io/kubernetes/pkg/kubelet/cm/topologymanager/bitmask" 22 ) 23 24 // Policy interface for Topology Manager Pod Admit Result 25 type Policy interface { 26 // Returns Policy Name 27 Name() string 28 // Returns a merged TopologyHint based on input from hint providers 29 // and a Pod Admit Handler Response based on hints and policy type 30 Merge(providersHints []map[string][]TopologyHint) (TopologyHint, bool) 31 } 32 33 // Merge a TopologyHints permutation to a single hint by performing a bitwise-AND 34 // of their affinity masks. The hint shall be preferred if all hits in the permutation 35 // are preferred. 36 func mergePermutation(defaultAffinity bitmask.BitMask, permutation []TopologyHint) TopologyHint { 37 // Get the NUMANodeAffinity from each hint in the permutation and see if any 38 // of them encode unpreferred allocations. 39 preferred := true 40 var numaAffinities []bitmask.BitMask 41 for _, hint := range permutation { 42 // Only consider hints that have an actual NUMANodeAffinity set. 43 if hint.NUMANodeAffinity != nil { 44 numaAffinities = append(numaAffinities, hint.NUMANodeAffinity) 45 // Only mark preferred if all affinities are equal. 46 if !hint.NUMANodeAffinity.IsEqual(numaAffinities[0]) { 47 preferred = false 48 } 49 } 50 // Only mark preferred if all affinities are preferred. 51 if !hint.Preferred { 52 preferred = false 53 } 54 } 55 56 // Merge the affinities using a bitwise-and operation. 57 mergedAffinity := bitmask.And(defaultAffinity, numaAffinities...) 58 // Build a mergedHint from the merged affinity mask, setting preferred as 59 // appropriate based on the logic above. 60 return TopologyHint{mergedAffinity, preferred} 61 } 62 63 func filterProvidersHints(providersHints []map[string][]TopologyHint) [][]TopologyHint { 64 // Loop through all hint providers and save an accumulated list of the 65 // hints returned by each hint provider. If no hints are provided, assume 66 // that provider has no preference for topology-aware allocation. 67 var allProviderHints [][]TopologyHint 68 for _, hints := range providersHints { 69 // If hints is nil, insert a single, preferred any-numa hint into allProviderHints. 70 if len(hints) == 0 { 71 klog.InfoS("Hint Provider has no preference for NUMA affinity with any resource") 72 allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}}) 73 continue 74 } 75 76 // Otherwise, accumulate the hints for each resource type into allProviderHints. 77 for resource := range hints { 78 if hints[resource] == nil { 79 klog.InfoS("Hint Provider has no preference for NUMA affinity with resource", "resource", resource) 80 allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}}) 81 continue 82 } 83 84 if len(hints[resource]) == 0 { 85 klog.InfoS("Hint Provider has no possible NUMA affinities for resource", "resource", resource) 86 allProviderHints = append(allProviderHints, []TopologyHint{{nil, false}}) 87 continue 88 } 89 90 allProviderHints = append(allProviderHints, hints[resource]) 91 } 92 } 93 return allProviderHints 94 } 95 96 func narrowestHint(hints []TopologyHint) *TopologyHint { 97 if len(hints) == 0 { 98 return nil 99 } 100 var narrowestHint *TopologyHint 101 for i := range hints { 102 if hints[i].NUMANodeAffinity == nil { 103 continue 104 } 105 if narrowestHint == nil { 106 narrowestHint = &hints[i] 107 } 108 if hints[i].NUMANodeAffinity.IsNarrowerThan(narrowestHint.NUMANodeAffinity) { 109 narrowestHint = &hints[i] 110 } 111 } 112 return narrowestHint 113 } 114 115 func maxOfMinAffinityCounts(filteredHints [][]TopologyHint) int { 116 maxOfMinCount := 0 117 for _, resourceHints := range filteredHints { 118 narrowestHint := narrowestHint(resourceHints) 119 if narrowestHint == nil { 120 continue 121 } 122 if narrowestHint.NUMANodeAffinity.Count() > maxOfMinCount { 123 maxOfMinCount = narrowestHint.NUMANodeAffinity.Count() 124 } 125 } 126 return maxOfMinCount 127 } 128 129 type HintMerger struct { 130 NUMAInfo *NUMAInfo 131 Hints [][]TopologyHint 132 // Set bestNonPreferredAffinityCount to help decide which affinity mask is 133 // preferred amongst all non-preferred hints. We calculate this value as 134 // the maximum of the minimum affinity counts supplied for any given hint 135 // provider. In other words, prefer a hint that has an affinity mask that 136 // includes all of the NUMA nodes from the provider that requires the most 137 // NUMA nodes to satisfy its allocation. 138 BestNonPreferredAffinityCount int 139 CompareNUMAAffinityMasks func(candidate *TopologyHint, current *TopologyHint) (best *TopologyHint) 140 } 141 142 func NewHintMerger(numaInfo *NUMAInfo, hints [][]TopologyHint, policyName string, opts PolicyOptions) HintMerger { 143 compareNumaAffinityMasks := func(current, candidate *TopologyHint) *TopologyHint { 144 // If current and candidate bitmasks are the same, prefer current hint. 145 if candidate.NUMANodeAffinity.IsEqual(current.NUMANodeAffinity) { 146 return current 147 } 148 149 // Otherwise compare the hints, based on the policy options provided 150 var best bitmask.BitMask 151 if (policyName != PolicySingleNumaNode) && opts.PreferClosestNUMA { 152 best = numaInfo.Closest(current.NUMANodeAffinity, candidate.NUMANodeAffinity) 153 } else { 154 best = numaInfo.Narrowest(current.NUMANodeAffinity, candidate.NUMANodeAffinity) 155 } 156 if best.IsEqual(current.NUMANodeAffinity) { 157 return current 158 } 159 return candidate 160 } 161 162 merger := HintMerger{ 163 NUMAInfo: numaInfo, 164 Hints: hints, 165 BestNonPreferredAffinityCount: maxOfMinAffinityCounts(hints), 166 CompareNUMAAffinityMasks: compareNumaAffinityMasks, 167 } 168 169 return merger 170 } 171 172 func (m HintMerger) compare(current *TopologyHint, candidate *TopologyHint) *TopologyHint { 173 // Only consider candidates that result in a NUMANodeAffinity > 0 to 174 // replace the current bestHint. 175 if candidate.NUMANodeAffinity.Count() == 0 { 176 return current 177 } 178 179 // If no current bestHint is set, return the candidate as the bestHint. 180 if current == nil { 181 return candidate 182 } 183 184 // If the current bestHint is non-preferred and the candidate hint is 185 // preferred, always choose the preferred hint over the non-preferred one. 186 if !current.Preferred && candidate.Preferred { 187 return candidate 188 } 189 190 // If the current bestHint is preferred and the candidate hint is 191 // non-preferred, never update the bestHint, regardless of how 192 // the candidate hint's affinity mask compares to the current 193 // hint's affinity mask. 194 if current.Preferred && !candidate.Preferred { 195 return current 196 } 197 198 // If the current bestHint and the candidate hint are both preferred, 199 // then only consider fitter NUMANodeAffinity 200 if current.Preferred && candidate.Preferred { 201 return m.CompareNUMAAffinityMasks(current, candidate) 202 203 } 204 205 // The only case left is if the current best bestHint and the candidate 206 // hint are both non-preferred. In this case, try and find a hint whose 207 // affinity count is as close to (but not higher than) the 208 // bestNonPreferredAffinityCount as possible. To do this we need to 209 // consider the following cases and react accordingly: 210 // 211 // 1. current.NUMANodeAffinity.Count() > bestNonPreferredAffinityCount 212 // 2. current.NUMANodeAffinity.Count() == bestNonPreferredAffinityCount 213 // 3. current.NUMANodeAffinity.Count() < bestNonPreferredAffinityCount 214 // 215 // For case (1), the current bestHint is larger than the 216 // bestNonPreferredAffinityCount, so updating to fitter mergeHint 217 // is preferred over staying where we are. 218 // 219 // For case (2), the current bestHint is equal to the 220 // bestNonPreferredAffinityCount, so we would like to stick with what 221 // we have *unless* the candidate hint is also equal to 222 // bestNonPreferredAffinityCount and it is fitter. 223 // 224 // For case (3), the current bestHint is less than 225 // bestNonPreferredAffinityCount, so we would like to creep back up to 226 // bestNonPreferredAffinityCount as close as we can. There are three 227 // cases to consider here: 228 // 229 // 3a. candidate.NUMANodeAffinity.Count() > bestNonPreferredAffinityCount 230 // 3b. candidate.NUMANodeAffinity.Count() == bestNonPreferredAffinityCount 231 // 3c. candidate.NUMANodeAffinity.Count() < bestNonPreferredAffinityCount 232 // 233 // For case (3a), we just want to stick with the current bestHint 234 // because choosing a new hint that is greater than 235 // bestNonPreferredAffinityCount would be counter-productive. 236 // 237 // For case (3b), we want to immediately update bestHint to the 238 // candidate hint, making it now equal to bestNonPreferredAffinityCount. 239 // 240 // For case (3c), we know that *both* the current bestHint and the 241 // candidate hint are less than bestNonPreferredAffinityCount, so we 242 // want to choose one that brings us back up as close to 243 // bestNonPreferredAffinityCount as possible. There are three cases to 244 // consider here: 245 // 246 // 3ca. candidate.NUMANodeAffinity.Count() > current.NUMANodeAffinity.Count() 247 // 3cb. candidate.NUMANodeAffinity.Count() < current.NUMANodeAffinity.Count() 248 // 3cc. candidate.NUMANodeAffinity.Count() == current.NUMANodeAffinity.Count() 249 // 250 // For case (3ca), we want to immediately update bestHint to the 251 // candidate hint because that will bring us closer to the (higher) 252 // value of bestNonPreferredAffinityCount. 253 // 254 // For case (3cb), we want to stick with the current bestHint because 255 // choosing the candidate hint would strictly move us further away from 256 // the bestNonPreferredAffinityCount. 257 // 258 // Finally, for case (3cc), we know that the current bestHint and the 259 // candidate hint are equal, so we simply choose the fitter of the 2. 260 261 // Case 1 262 if current.NUMANodeAffinity.Count() > m.BestNonPreferredAffinityCount { 263 return m.CompareNUMAAffinityMasks(current, candidate) 264 } 265 // Case 2 266 if current.NUMANodeAffinity.Count() == m.BestNonPreferredAffinityCount { 267 if candidate.NUMANodeAffinity.Count() != m.BestNonPreferredAffinityCount { 268 return current 269 } 270 return m.CompareNUMAAffinityMasks(current, candidate) 271 } 272 // Case 3a 273 if candidate.NUMANodeAffinity.Count() > m.BestNonPreferredAffinityCount { 274 return current 275 } 276 // Case 3b 277 if candidate.NUMANodeAffinity.Count() == m.BestNonPreferredAffinityCount { 278 return candidate 279 } 280 281 // Case 3ca 282 if candidate.NUMANodeAffinity.Count() > current.NUMANodeAffinity.Count() { 283 return candidate 284 } 285 // Case 3cb 286 if candidate.NUMANodeAffinity.Count() < current.NUMANodeAffinity.Count() { 287 return current 288 } 289 290 // Case 3cc 291 return m.CompareNUMAAffinityMasks(current, candidate) 292 293 } 294 295 func (m HintMerger) Merge() TopologyHint { 296 defaultAffinity := m.NUMAInfo.DefaultAffinityMask() 297 298 var bestHint *TopologyHint 299 iterateAllProviderTopologyHints(m.Hints, func(permutation []TopologyHint) { 300 // Get the NUMANodeAffinity from each hint in the permutation and see if any 301 // of them encode unpreferred allocations. 302 mergedHint := mergePermutation(defaultAffinity, permutation) 303 304 // Compare the current bestHint with the candidate mergedHint and 305 // update bestHint if appropriate. 306 bestHint = m.compare(bestHint, &mergedHint) 307 }) 308 309 if bestHint == nil { 310 bestHint = &TopologyHint{defaultAffinity, false} 311 } 312 313 return *bestHint 314 } 315 316 // Iterate over all permutations of hints in 'allProviderHints [][]TopologyHint'. 317 // 318 // This procedure is implemented as a recursive function over the set of hints 319 // in 'allproviderHints[i]'. It applies the function 'callback' to each 320 // permutation as it is found. It is the equivalent of: 321 // 322 // for i := 0; i < len(providerHints[0]); i++ 323 // 324 // for j := 0; j < len(providerHints[1]); j++ 325 // for k := 0; k < len(providerHints[2]); k++ 326 // ... 327 // for z := 0; z < len(providerHints[-1]); z++ 328 // permutation := []TopologyHint{ 329 // providerHints[0][i], 330 // providerHints[1][j], 331 // providerHints[2][k], 332 // ... 333 // providerHints[-1][z] 334 // } 335 // callback(permutation) 336 func iterateAllProviderTopologyHints(allProviderHints [][]TopologyHint, callback func([]TopologyHint)) { 337 // Internal helper function to accumulate the permutation before calling the callback. 338 var iterate func(i int, accum []TopologyHint) 339 iterate = func(i int, accum []TopologyHint) { 340 // Base case: we have looped through all providers and have a full permutation. 341 if i == len(allProviderHints) { 342 callback(accum) 343 return 344 } 345 346 // Loop through all hints for provider 'i', and recurse to build the 347 // permutation of this hint with all hints from providers 'i++'. 348 for j := range allProviderHints[i] { 349 iterate(i+1, append(accum, allProviderHints[i][j])) 350 } 351 } 352 iterate(0, []TopologyHint{}) 353 } 354