1/*
2Copyright 2019 The Kubernetes Authors.
3
4Licensed under the Apache License, Version 2.0 (the "License");
5you may not use this file except in compliance with the License.
6You may obtain a copy of the License at
7
8    http://www.apache.org/licenses/LICENSE-2.0
9
10Unless required by applicable law or agreed to in writing, software
11distributed under the License is distributed on an "AS IS" BASIS,
12WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13See the License for the specific language governing permissions and
14limitations under the License.
15*/
16
17package cache
18
19import (
20	"fmt"
21
22	v1 "k8s.io/api/core/v1"
23	"k8s.io/apimachinery/pkg/util/sets"
24	"k8s.io/kubernetes/pkg/scheduler/framework"
25)
26
27// Snapshot is a snapshot of cache NodeInfo and NodeTree order. The scheduler takes a
28// snapshot at the beginning of each scheduling cycle and uses it for its operations in that cycle.
29type Snapshot struct {
30	// nodeInfoMap a map of node name to a snapshot of its NodeInfo.
31	nodeInfoMap map[string]*framework.NodeInfo
32	// nodeInfoList is the list of nodes as ordered in the cache's nodeTree.
33	nodeInfoList []*framework.NodeInfo
34	// havePodsWithAffinityNodeInfoList is the list of nodes with at least one pod declaring affinity terms.
35	havePodsWithAffinityNodeInfoList []*framework.NodeInfo
36	// havePodsWithRequiredAntiAffinityNodeInfoList is the list of nodes with at least one pod declaring
37	// required anti-affinity terms.
38	havePodsWithRequiredAntiAffinityNodeInfoList []*framework.NodeInfo
39	generation                                   int64
40}
41
42var _ framework.SharedLister = &Snapshot{}
43
44// NewEmptySnapshot initializes a Snapshot struct and returns it.
45func NewEmptySnapshot() *Snapshot {
46	return &Snapshot{
47		nodeInfoMap: make(map[string]*framework.NodeInfo),
48	}
49}
50
51// NewSnapshot initializes a Snapshot struct and returns it.
52func NewSnapshot(pods []*v1.Pod, nodes []*v1.Node) *Snapshot {
53	nodeInfoMap := createNodeInfoMap(pods, nodes)
54	nodeInfoList := make([]*framework.NodeInfo, 0, len(nodeInfoMap))
55	havePodsWithAffinityNodeInfoList := make([]*framework.NodeInfo, 0, len(nodeInfoMap))
56	havePodsWithRequiredAntiAffinityNodeInfoList := make([]*framework.NodeInfo, 0, len(nodeInfoMap))
57	for _, v := range nodeInfoMap {
58		nodeInfoList = append(nodeInfoList, v)
59		if len(v.PodsWithAffinity) > 0 {
60			havePodsWithAffinityNodeInfoList = append(havePodsWithAffinityNodeInfoList, v)
61		}
62		if len(v.PodsWithRequiredAntiAffinity) > 0 {
63			havePodsWithRequiredAntiAffinityNodeInfoList = append(havePodsWithRequiredAntiAffinityNodeInfoList, v)
64		}
65	}
66
67	s := NewEmptySnapshot()
68	s.nodeInfoMap = nodeInfoMap
69	s.nodeInfoList = nodeInfoList
70	s.havePodsWithAffinityNodeInfoList = havePodsWithAffinityNodeInfoList
71	s.havePodsWithRequiredAntiAffinityNodeInfoList = havePodsWithRequiredAntiAffinityNodeInfoList
72
73	return s
74}
75
76// createNodeInfoMap obtains a list of pods and pivots that list into a map
77// where the keys are node names and the values are the aggregated information
78// for that node.
79func createNodeInfoMap(pods []*v1.Pod, nodes []*v1.Node) map[string]*framework.NodeInfo {
80	nodeNameToInfo := make(map[string]*framework.NodeInfo)
81	for _, pod := range pods {
82		nodeName := pod.Spec.NodeName
83		if _, ok := nodeNameToInfo[nodeName]; !ok {
84			nodeNameToInfo[nodeName] = framework.NewNodeInfo()
85		}
86		nodeNameToInfo[nodeName].AddPod(pod)
87	}
88	imageExistenceMap := createImageExistenceMap(nodes)
89
90	for _, node := range nodes {
91		if _, ok := nodeNameToInfo[node.Name]; !ok {
92			nodeNameToInfo[node.Name] = framework.NewNodeInfo()
93		}
94		nodeInfo := nodeNameToInfo[node.Name]
95		nodeInfo.SetNode(node)
96		nodeInfo.ImageStates = getNodeImageStates(node, imageExistenceMap)
97	}
98	return nodeNameToInfo
99}
100
101// getNodeImageStates returns the given node's image states based on the given imageExistence map.
102func getNodeImageStates(node *v1.Node, imageExistenceMap map[string]sets.String) map[string]*framework.ImageStateSummary {
103	imageStates := make(map[string]*framework.ImageStateSummary)
104
105	for _, image := range node.Status.Images {
106		for _, name := range image.Names {
107			imageStates[name] = &framework.ImageStateSummary{
108				Size:     image.SizeBytes,
109				NumNodes: len(imageExistenceMap[name]),
110			}
111		}
112	}
113	return imageStates
114}
115
116// createImageExistenceMap returns a map recording on which nodes the images exist, keyed by the images' names.
117func createImageExistenceMap(nodes []*v1.Node) map[string]sets.String {
118	imageExistenceMap := make(map[string]sets.String)
119	for _, node := range nodes {
120		for _, image := range node.Status.Images {
121			for _, name := range image.Names {
122				if _, ok := imageExistenceMap[name]; !ok {
123					imageExistenceMap[name] = sets.NewString(node.Name)
124				} else {
125					imageExistenceMap[name].Insert(node.Name)
126				}
127			}
128		}
129	}
130	return imageExistenceMap
131}
132
133// NodeInfos returns a NodeInfoLister.
134func (s *Snapshot) NodeInfos() framework.NodeInfoLister {
135	return s
136}
137
138// NumNodes returns the number of nodes in the snapshot.
139func (s *Snapshot) NumNodes() int {
140	return len(s.nodeInfoList)
141}
142
143// List returns the list of nodes in the snapshot.
144func (s *Snapshot) List() ([]*framework.NodeInfo, error) {
145	return s.nodeInfoList, nil
146}
147
148// HavePodsWithAffinityList returns the list of nodes with at least one pod with inter-pod affinity
149func (s *Snapshot) HavePodsWithAffinityList() ([]*framework.NodeInfo, error) {
150	return s.havePodsWithAffinityNodeInfoList, nil
151}
152
153// HavePodsWithRequiredAntiAffinityList returns the list of nodes with at least one pod with
154// required inter-pod anti-affinity
155func (s *Snapshot) HavePodsWithRequiredAntiAffinityList() ([]*framework.NodeInfo, error) {
156	return s.havePodsWithRequiredAntiAffinityNodeInfoList, nil
157}
158
159// Get returns the NodeInfo of the given node name.
160func (s *Snapshot) Get(nodeName string) (*framework.NodeInfo, error) {
161	if v, ok := s.nodeInfoMap[nodeName]; ok && v.Node() != nil {
162		return v, nil
163	}
164	return nil, fmt.Errorf("nodeinfo not found for node name %q", nodeName)
165}
166