policy.go 6.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179
  1. /*
  2. Copyright 2019 The Kubernetes Authors.
  3. Licensed under the Apache License, Version 2.0 (the "License");
  4. you may not use this file except in compliance with the License.
  5. You may obtain a copy of the License at
  6. http://www.apache.org/licenses/LICENSE-2.0
  7. Unless required by applicable law or agreed to in writing, software
  8. distributed under the License is distributed on an "AS IS" BASIS,
  9. WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  10. See the License for the specific language governing permissions and
  11. limitations under the License.
  12. */
  13. package topologymanager
  14. import (
  15. "k8s.io/klog"
  16. "k8s.io/kubernetes/pkg/kubelet/cm/topologymanager/bitmask"
  17. )
  18. // Policy interface for Topology Manager Pod Admit Result
  19. type Policy interface {
  20. // Returns Policy Name
  21. Name() string
  22. // Returns a merged TopologyHint based on input from hint providers
  23. // and a Pod Admit Handler Response based on hints and policy type
  24. Merge(providersHints []map[string][]TopologyHint) (TopologyHint, bool)
  25. }
  26. // Merge a TopologyHints permutation to a single hint by performing a bitwise-AND
  27. // of their affinity masks. The hint shall be preferred if all hits in the permutation
  28. // are preferred.
  29. func mergePermutation(numaNodes []int, permutation []TopologyHint) TopologyHint {
  30. // Get the NUMANodeAffinity from each hint in the permutation and see if any
  31. // of them encode unpreferred allocations.
  32. preferred := true
  33. defaultAffinity, _ := bitmask.NewBitMask(numaNodes...)
  34. var numaAffinities []bitmask.BitMask
  35. for _, hint := range permutation {
  36. // Only consider hints that have an actual NUMANodeAffinity set.
  37. if hint.NUMANodeAffinity == nil {
  38. numaAffinities = append(numaAffinities, defaultAffinity)
  39. } else {
  40. numaAffinities = append(numaAffinities, hint.NUMANodeAffinity)
  41. }
  42. if !hint.Preferred {
  43. preferred = false
  44. }
  45. }
  46. // Merge the affinities using a bitwise-and operation.
  47. mergedAffinity := bitmask.And(defaultAffinity, numaAffinities...)
  48. // Build a mergedHint from the merged affinity mask, indicating if an
  49. // preferred allocation was used to generate the affinity mask or not.
  50. return TopologyHint{mergedAffinity, preferred}
  51. }
  52. func filterProvidersHints(providersHints []map[string][]TopologyHint) [][]TopologyHint {
  53. // Loop through all hint providers and save an accumulated list of the
  54. // hints returned by each hint provider. If no hints are provided, assume
  55. // that provider has no preference for topology-aware allocation.
  56. var allProviderHints [][]TopologyHint
  57. for _, hints := range providersHints {
  58. // If hints is nil, insert a single, preferred any-numa hint into allProviderHints.
  59. if len(hints) == 0 {
  60. klog.Infof("[topologymanager] Hint Provider has no preference for NUMA affinity with any resource")
  61. allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}})
  62. continue
  63. }
  64. // Otherwise, accumulate the hints for each resource type into allProviderHints.
  65. for resource := range hints {
  66. if hints[resource] == nil {
  67. klog.Infof("[topologymanager] Hint Provider has no preference for NUMA affinity with resource '%s'", resource)
  68. allProviderHints = append(allProviderHints, []TopologyHint{{nil, true}})
  69. continue
  70. }
  71. if len(hints[resource]) == 0 {
  72. klog.Infof("[topologymanager] Hint Provider has no possible NUMA affinities for resource '%s'", resource)
  73. allProviderHints = append(allProviderHints, []TopologyHint{{nil, false}})
  74. continue
  75. }
  76. allProviderHints = append(allProviderHints, hints[resource])
  77. }
  78. }
  79. return allProviderHints
  80. }
  81. func mergeFilteredHints(numaNodes []int, filteredHints [][]TopologyHint) TopologyHint {
  82. // Set the default affinity as an any-numa affinity containing the list
  83. // of NUMA Nodes available on this machine.
  84. defaultAffinity, _ := bitmask.NewBitMask(numaNodes...)
  85. // Set the bestHint to return from this function as {nil false}.
  86. // This will only be returned if no better hint can be found when
  87. // merging hints from each hint provider.
  88. bestHint := TopologyHint{defaultAffinity, false}
  89. iterateAllProviderTopologyHints(filteredHints, func(permutation []TopologyHint) {
  90. // Get the NUMANodeAffinity from each hint in the permutation and see if any
  91. // of them encode unpreferred allocations.
  92. mergedHint := mergePermutation(numaNodes, permutation)
  93. // Only consider mergedHints that result in a NUMANodeAffinity > 0 to
  94. // replace the current bestHint.
  95. if mergedHint.NUMANodeAffinity.Count() == 0 {
  96. return
  97. }
  98. // If the current bestHint is non-preferred and the new mergedHint is
  99. // preferred, always choose the preferred hint over the non-preferred one.
  100. if mergedHint.Preferred && !bestHint.Preferred {
  101. bestHint = mergedHint
  102. return
  103. }
  104. // If the current bestHint is preferred and the new mergedHint is
  105. // non-preferred, never update bestHint, regardless of mergedHint's
  106. // narowness.
  107. if !mergedHint.Preferred && bestHint.Preferred {
  108. return
  109. }
  110. // If mergedHint and bestHint has the same preference, only consider
  111. // mergedHints that have a narrower NUMANodeAffinity than the
  112. // NUMANodeAffinity in the current bestHint.
  113. if !mergedHint.NUMANodeAffinity.IsNarrowerThan(bestHint.NUMANodeAffinity) {
  114. return
  115. }
  116. // In all other cases, update bestHint to the current mergedHint
  117. bestHint = mergedHint
  118. })
  119. return bestHint
  120. }
  121. // Iterate over all permutations of hints in 'allProviderHints [][]TopologyHint'.
  122. //
  123. // This procedure is implemented as a recursive function over the set of hints
  124. // in 'allproviderHints[i]'. It applies the function 'callback' to each
  125. // permutation as it is found. It is the equivalent of:
  126. //
  127. // for i := 0; i < len(providerHints[0]); i++
  128. // for j := 0; j < len(providerHints[1]); j++
  129. // for k := 0; k < len(providerHints[2]); k++
  130. // ...
  131. // for z := 0; z < len(providerHints[-1]); z++
  132. // permutation := []TopologyHint{
  133. // providerHints[0][i],
  134. // providerHints[1][j],
  135. // providerHints[2][k],
  136. // ...
  137. // providerHints[-1][z]
  138. // }
  139. // callback(permutation)
  140. func iterateAllProviderTopologyHints(allProviderHints [][]TopologyHint, callback func([]TopologyHint)) {
  141. // Internal helper function to accumulate the permutation before calling the callback.
  142. var iterate func(i int, accum []TopologyHint)
  143. iterate = func(i int, accum []TopologyHint) {
  144. // Base case: we have looped through all providers and have a full permutation.
  145. if i == len(allProviderHints) {
  146. callback(accum)
  147. return
  148. }
  149. // Loop through all hints for provider 'i', and recurse to build the
  150. // the permutation of this hint with all hints from providers 'i++'.
  151. for j := range allProviderHints[i] {
  152. iterate(i+1, append(accum, allProviderHints[i][j]))
  153. }
  154. }
  155. iterate(0, []TopologyHint{})
  156. }