123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179 |
- /*
- 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"
- )
- // Policy interface for Topology Manager Pod Admit Result
- type Policy interface {
- // Returns Policy Name
- Name() string
- // Returns a merged TopologyHint based on input from hint providers
- // and a Pod Admit Handler Response based on hints and policy type
- Merge(providersHints []map[string][]TopologyHint) (TopologyHint, bool)
- }
- // Merge a TopologyHints permutation to a single hint by performing a bitwise-AND
- // of their affinity masks. The hint shall be preferred if all hits in the permutation
- // are preferred.
- func mergePermutation(numaNodes []int, permutation []TopologyHint) TopologyHint {
- // Get the NUMANodeAffinity from each hint in the permutation and see if any
- // of them encode unpreferred allocations.
- preferred := true
- defaultAffinity, _ := bitmask.NewBitMask(numaNodes...)
- var numaAffinities []bitmask.BitMask
- for _, hint := range permutation {
- // Only consider hints that have an actual NUMANodeAffinity set.
- if hint.NUMANodeAffinity == nil {
- numaAffinities = append(numaAffinities, defaultAffinity)
- } else {
- numaAffinities = append(numaAffinities, hint.NUMANodeAffinity)
- }
- if !hint.Preferred {
- preferred = false
- }
- }
- // Merge the affinities using a bitwise-and operation.
- mergedAffinity := bitmask.And(defaultAffinity, numaAffinities...)
- // Build a mergedHint from the merged affinity mask, indicating if an
- // preferred allocation was used to generate the affinity mask or not.
- return TopologyHint{mergedAffinity, preferred}
- }
- func filterProvidersHints(providersHints []map[string][]TopologyHint) [][]TopologyHint {
- // 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])
- }
- }
- return allProviderHints
- }
- func mergeFilteredHints(numaNodes []int, filteredHints [][]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...)
- // Set the bestHint to return from this function as {nil false}.
- // This will only be returned if no better hint can be found when
- // merging hints from each hint provider.
- bestHint := TopologyHint{defaultAffinity, false}
- iterateAllProviderTopologyHints(filteredHints, func(permutation []TopologyHint) {
- // Get the NUMANodeAffinity from each hint in the permutation and see if any
- // of them encode unpreferred allocations.
- mergedHint := mergePermutation(numaNodes, permutation)
- // 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
- }
- // 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{})
- }
|