/
nodetype.go
153 lines (139 loc) · 4.41 KB
/
nodetype.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
package schedulerobjects
import (
"github.com/segmentio/fasthash/fnv1a"
"golang.org/x/exp/maps"
"golang.org/x/exp/slices"
v1 "k8s.io/api/core/v1"
)
type (
taintsFilterFunc func(*v1.Taint) bool
labelsFilterFunc func(key, value string) bool
)
func NewNodeType(taints []v1.Taint, labels map[string]string, indexedTaints map[string]interface{}, indexedLabels map[string]interface{}) *NodeType {
if taints == nil {
taints = make([]v1.Taint, 0)
}
if labels == nil {
labels = make(map[string]string)
}
// Filter out any taints that should not be indexed.
if indexedTaints != nil {
taints = getFilteredTaints(taints, func(t *v1.Taint) bool {
_, ok := indexedTaints[t.Key]
return ok
})
} else {
// The default is to index all taints.
taints = slices.Clone(taints)
}
// Sort taints to ensure node type id is consistent regardless of
// the order in which taints are set on the node.
slices.SortFunc(taints, func(a, b v1.Taint) int {
if a.Key < b.Key {
return -1
} else if a.Key > b.Key {
return 1
} else {
return 0
}
}) // TODO: Use less ambiguous sorting.
// Filter out any labels that should not be indexed.
if indexedLabels != nil {
labels = getFilteredLabels(labels, func(key, _ string) bool {
_, ok := indexedLabels[key]
return ok
})
} else {
// The default is to not index any labels.
labels = make(map[string]string)
}
// Get the indexed labels that are not set to create indexes for unset labels.
unsetIndexedLabels := make(map[string]string)
for key := range indexedLabels {
if _, ok := labels[key]; !ok {
unsetIndexedLabels[key] = "" // Only the key is used.
}
}
return &NodeType{
Id: nodeTypeIdFromTaintsAndLabels(taints, labels, unsetIndexedLabels),
Taints: taints,
Labels: labels,
UnsetIndexedLabels: unsetIndexedLabels,
}
}
// nodeTypeIdFromTaintsAndLabels generates a id unique for each combination of taints, labels, and unset labels.
// The id is based on the fnv1a hash. Hash collisions do not affect correctness, only the efficiency of sorting out nodes.
//
// We separate taints/labels by $, labels and values by =, and and groups by &,
// since these characters are not allowed in taints and labels; see
// https://kubernetes.io/docs/concepts/overview/working-with-objects/labels/#syntax-and-character-set
// https://man.archlinux.org/man/community/kubectl/kubectl-taint.1.en
func nodeTypeIdFromTaintsAndLabels(taints []v1.Taint, labels, unsetIndexedLabels map[string]string) uint64 {
// TODO: We should test this function to ensure there are no collisions. And that the string is never empty.
h := fnv1a.Init64
for _, taint := range taints {
h = fnv1a.AddString64(h, taint.Key)
h = fnv1a.AddString64(h, "=")
h = fnv1a.AddString64(h, taint.Value)
h = fnv1a.AddString64(h, ":")
h = fnv1a.AddString64(h, string(taint.Effect))
h = fnv1a.AddString64(h, "$")
}
h = fnv1a.AddString64(h, "&")
ls := maps.Keys(labels)
slices.Sort(ls)
for _, label := range ls {
value := labels[label]
h = fnv1a.AddString64(h, label)
h = fnv1a.AddString64(h, "=")
h = fnv1a.AddString64(h, value)
h = fnv1a.AddString64(h, "$")
}
h = fnv1a.AddString64(h, "&")
ls = maps.Keys(unsetIndexedLabels)
slices.Sort(ls)
for _, label := range ls {
h = fnv1a.AddString64(h, label)
h = fnv1a.AddString64(h, "$")
}
return h
}
// getFilteredTaints returns a list of taints satisfying the filter predicate.
func getFilteredTaints(taints []v1.Taint, inclusionFilter taintsFilterFunc) []v1.Taint {
if inclusionFilter == nil {
return taints
}
filteredTaints := []v1.Taint{}
for _, taint := range taints {
if !inclusionFilter(&taint) {
continue
}
filteredTaints = append(filteredTaints, taint)
}
return filteredTaints
}
// getFilteredLabels returns a map of labels satisfying the filter predicate.
func getFilteredLabels(labels map[string]string, inclusionFilter labelsFilterFunc) map[string]string {
if inclusionFilter == nil {
return labels
}
filteredLabels := make(map[string]string)
for key, value := range labels {
if !inclusionFilter(key, value) {
continue
}
filteredLabels[key] = value
}
return filteredLabels
}
func (nodeType *NodeType) DeepCopy() *NodeType {
if nodeType == nil {
return nil
}
return &NodeType{
Id: nodeType.Id,
Taints: slices.Clone(nodeType.Taints),
Labels: maps.Clone(nodeType.Labels),
UnsetIndexedLabels: maps.Clone(nodeType.UnsetIndexedLabels),
}
}