1/*
2Copyright 2018 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	"reflect"
21	"testing"
22
23	v1 "k8s.io/api/core/v1"
24	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
25)
26
27var allNodes = []*v1.Node{
28	// Node 0: a node without any region-zone label
29	{
30		ObjectMeta: metav1.ObjectMeta{
31			Name: "node-0",
32		},
33	},
34	// Node 1: a node with region label only
35	{
36		ObjectMeta: metav1.ObjectMeta{
37			Name: "node-1",
38			Labels: map[string]string{
39				v1.LabelTopologyRegion: "region-1",
40			},
41		},
42	},
43	// Node 2: a node with zone label only
44	{
45		ObjectMeta: metav1.ObjectMeta{
46			Name: "node-2",
47			Labels: map[string]string{
48				v1.LabelTopologyZone: "zone-2",
49			},
50		},
51	},
52	// Node 3: a node with proper region and zone labels
53	{
54		ObjectMeta: metav1.ObjectMeta{
55			Name: "node-3",
56			Labels: map[string]string{
57				v1.LabelTopologyRegion: "region-1",
58				v1.LabelTopologyZone:   "zone-2",
59			},
60		},
61	},
62	// Node 4: a node with proper region and zone labels
63	{
64		ObjectMeta: metav1.ObjectMeta{
65			Name: "node-4",
66			Labels: map[string]string{
67				v1.LabelTopologyRegion: "region-1",
68				v1.LabelTopologyZone:   "zone-2",
69			},
70		},
71	},
72	// Node 5: a node with proper region and zone labels in a different zone, same region as above
73	{
74		ObjectMeta: metav1.ObjectMeta{
75			Name: "node-5",
76			Labels: map[string]string{
77				v1.LabelTopologyRegion: "region-1",
78				v1.LabelTopologyZone:   "zone-3",
79			},
80		},
81	},
82	// Node 6: a node with proper region and zone labels in a new region and zone
83	{
84		ObjectMeta: metav1.ObjectMeta{
85			Name: "node-6",
86			Labels: map[string]string{
87				v1.LabelTopologyRegion: "region-2",
88				v1.LabelTopologyZone:   "zone-2",
89			},
90		},
91	},
92	// Node 7: a node with proper region and zone labels in a region and zone as node-6
93	{
94		ObjectMeta: metav1.ObjectMeta{
95			Name: "node-7",
96			Labels: map[string]string{
97				v1.LabelTopologyRegion: "region-2",
98				v1.LabelTopologyZone:   "zone-2",
99			},
100		},
101	},
102	// Node 8: a node with proper region and zone labels in a region and zone as node-6
103	{
104		ObjectMeta: metav1.ObjectMeta{
105			Name: "node-8",
106			Labels: map[string]string{
107				v1.LabelTopologyRegion: "region-2",
108				v1.LabelTopologyZone:   "zone-2",
109			},
110		},
111	},
112	// Node 9: a node with zone + region label and the deprecated zone + region label
113	{
114		ObjectMeta: metav1.ObjectMeta{
115			Name: "node-9",
116			Labels: map[string]string{
117				v1.LabelTopologyRegion:          "region-2",
118				v1.LabelTopologyZone:            "zone-2",
119				v1.LabelFailureDomainBetaRegion: "region-2",
120				v1.LabelFailureDomainBetaZone:   "zone-2",
121			},
122		},
123	},
124	// Node 10: a node with only the deprecated zone + region labels
125	{
126		ObjectMeta: metav1.ObjectMeta{
127			Name: "node-10",
128			Labels: map[string]string{
129				v1.LabelFailureDomainBetaRegion: "region-2",
130				v1.LabelFailureDomainBetaZone:   "zone-3",
131			},
132		},
133	},
134}
135
136func verifyNodeTree(t *testing.T, nt *nodeTree, expectedTree map[string][]string) {
137	expectedNumNodes := int(0)
138	for _, na := range expectedTree {
139		expectedNumNodes += len(na)
140	}
141	if numNodes := nt.numNodes; numNodes != expectedNumNodes {
142		t.Errorf("unexpected nodeTree.numNodes. Expected: %v, Got: %v", expectedNumNodes, numNodes)
143	}
144	if !reflect.DeepEqual(nt.tree, expectedTree) {
145		t.Errorf("The node tree is not the same as expected. Expected: %v, Got: %v", expectedTree, nt.tree)
146	}
147	if len(nt.zones) != len(expectedTree) {
148		t.Errorf("Number of zones in nodeTree.zones is not expected. Expected: %v, Got: %v", len(expectedTree), len(nt.zones))
149	}
150	for _, z := range nt.zones {
151		if _, ok := expectedTree[z]; !ok {
152			t.Errorf("zone %v is not expected to exist in nodeTree.zones", z)
153		}
154	}
155}
156
157func TestNodeTree_AddNode(t *testing.T) {
158	tests := []struct {
159		name         string
160		nodesToAdd   []*v1.Node
161		expectedTree map[string][]string
162	}{
163		{
164			name:         "single node no labels",
165			nodesToAdd:   allNodes[:1],
166			expectedTree: map[string][]string{"": {"node-0"}},
167		},
168		{
169			name:       "mix of nodes with and without proper labels",
170			nodesToAdd: allNodes[:4],
171			expectedTree: map[string][]string{
172				"":                     {"node-0"},
173				"region-1:\x00:":       {"node-1"},
174				":\x00:zone-2":         {"node-2"},
175				"region-1:\x00:zone-2": {"node-3"},
176			},
177		},
178		{
179			name:       "mix of nodes with and without proper labels and some zones with multiple nodes",
180			nodesToAdd: allNodes[:7],
181			expectedTree: map[string][]string{
182				"":                     {"node-0"},
183				"region-1:\x00:":       {"node-1"},
184				":\x00:zone-2":         {"node-2"},
185				"region-1:\x00:zone-2": {"node-3", "node-4"},
186				"region-1:\x00:zone-3": {"node-5"},
187				"region-2:\x00:zone-2": {"node-6"},
188			},
189		},
190		{
191			name:       "nodes also using deprecated zone/region label",
192			nodesToAdd: allNodes[9:],
193			expectedTree: map[string][]string{
194				"region-2:\x00:zone-2": {"node-9"},
195				"region-2:\x00:zone-3": {"node-10"},
196			},
197		},
198	}
199
200	for _, test := range tests {
201		t.Run(test.name, func(t *testing.T) {
202			nt := newNodeTree(nil)
203			for _, n := range test.nodesToAdd {
204				nt.addNode(n)
205			}
206			verifyNodeTree(t, nt, test.expectedTree)
207		})
208	}
209}
210
211func TestNodeTree_RemoveNode(t *testing.T) {
212	tests := []struct {
213		name          string
214		existingNodes []*v1.Node
215		nodesToRemove []*v1.Node
216		expectedTree  map[string][]string
217		expectError   bool
218	}{
219		{
220			name:          "remove a single node with no labels",
221			existingNodes: allNodes[:7],
222			nodesToRemove: allNodes[:1],
223			expectedTree: map[string][]string{
224				"region-1:\x00:":       {"node-1"},
225				":\x00:zone-2":         {"node-2"},
226				"region-1:\x00:zone-2": {"node-3", "node-4"},
227				"region-1:\x00:zone-3": {"node-5"},
228				"region-2:\x00:zone-2": {"node-6"},
229			},
230		},
231		{
232			name:          "remove a few nodes including one from a zone with multiple nodes",
233			existingNodes: allNodes[:7],
234			nodesToRemove: allNodes[1:4],
235			expectedTree: map[string][]string{
236				"":                     {"node-0"},
237				"region-1:\x00:zone-2": {"node-4"},
238				"region-1:\x00:zone-3": {"node-5"},
239				"region-2:\x00:zone-2": {"node-6"},
240			},
241		},
242		{
243			name:          "remove all nodes",
244			existingNodes: allNodes[:7],
245			nodesToRemove: allNodes[:7],
246			expectedTree:  map[string][]string{},
247		},
248		{
249			name:          "remove non-existing node",
250			existingNodes: nil,
251			nodesToRemove: allNodes[:5],
252			expectedTree:  map[string][]string{},
253			expectError:   true,
254		},
255	}
256
257	for _, test := range tests {
258		t.Run(test.name, func(t *testing.T) {
259			nt := newNodeTree(test.existingNodes)
260			for _, n := range test.nodesToRemove {
261				err := nt.removeNode(n)
262				if test.expectError == (err == nil) {
263					t.Errorf("unexpected returned error value: %v", err)
264				}
265			}
266			verifyNodeTree(t, nt, test.expectedTree)
267		})
268	}
269}
270
271func TestNodeTree_UpdateNode(t *testing.T) {
272	tests := []struct {
273		name          string
274		existingNodes []*v1.Node
275		nodeToUpdate  *v1.Node
276		expectedTree  map[string][]string
277	}{
278		{
279			name:          "update a node without label",
280			existingNodes: allNodes[:7],
281			nodeToUpdate: &v1.Node{
282				ObjectMeta: metav1.ObjectMeta{
283					Name: "node-0",
284					Labels: map[string]string{
285						v1.LabelTopologyRegion: "region-1",
286						v1.LabelTopologyZone:   "zone-2",
287					},
288				},
289			},
290			expectedTree: map[string][]string{
291				"region-1:\x00:":       {"node-1"},
292				":\x00:zone-2":         {"node-2"},
293				"region-1:\x00:zone-2": {"node-3", "node-4", "node-0"},
294				"region-1:\x00:zone-3": {"node-5"},
295				"region-2:\x00:zone-2": {"node-6"},
296			},
297		},
298		{
299			name:          "update the only existing node",
300			existingNodes: allNodes[:1],
301			nodeToUpdate: &v1.Node{
302				ObjectMeta: metav1.ObjectMeta{
303					Name: "node-0",
304					Labels: map[string]string{
305						v1.LabelTopologyRegion: "region-1",
306						v1.LabelTopologyZone:   "zone-2",
307					},
308				},
309			},
310			expectedTree: map[string][]string{
311				"region-1:\x00:zone-2": {"node-0"},
312			},
313		},
314		{
315			name:          "update non-existing node",
316			existingNodes: allNodes[:1],
317			nodeToUpdate: &v1.Node{
318				ObjectMeta: metav1.ObjectMeta{
319					Name: "node-new",
320					Labels: map[string]string{
321						v1.LabelTopologyRegion: "region-1",
322						v1.LabelTopologyZone:   "zone-2",
323					},
324				},
325			},
326			expectedTree: map[string][]string{
327				"":                     {"node-0"},
328				"region-1:\x00:zone-2": {"node-new"},
329			},
330		},
331	}
332
333	for _, test := range tests {
334		t.Run(test.name, func(t *testing.T) {
335			nt := newNodeTree(test.existingNodes)
336			var oldNode *v1.Node
337			for _, n := range allNodes {
338				if n.Name == test.nodeToUpdate.Name {
339					oldNode = n
340					break
341				}
342			}
343			if oldNode == nil {
344				oldNode = &v1.Node{ObjectMeta: metav1.ObjectMeta{Name: "nonexisting-node"}}
345			}
346			nt.updateNode(oldNode, test.nodeToUpdate)
347			verifyNodeTree(t, nt, test.expectedTree)
348		})
349	}
350}
351
352func TestNodeTree_List(t *testing.T) {
353	tests := []struct {
354		name           string
355		nodesToAdd     []*v1.Node
356		expectedOutput []string
357	}{
358		{
359			name:           "empty tree",
360			nodesToAdd:     nil,
361			expectedOutput: nil,
362		},
363		{
364			name:           "one node",
365			nodesToAdd:     allNodes[:1],
366			expectedOutput: []string{"node-0"},
367		},
368		{
369			name:           "four nodes",
370			nodesToAdd:     allNodes[:4],
371			expectedOutput: []string{"node-0", "node-1", "node-2", "node-3"},
372		},
373		{
374			name:           "all nodes",
375			nodesToAdd:     allNodes[:9],
376			expectedOutput: []string{"node-0", "node-1", "node-2", "node-3", "node-5", "node-6", "node-4", "node-7", "node-8"},
377		},
378	}
379
380	for _, test := range tests {
381		t.Run(test.name, func(t *testing.T) {
382			nt := newNodeTree(test.nodesToAdd)
383
384			output, err := nt.list()
385			if err != nil {
386				t.Fatal(err)
387			}
388			if !reflect.DeepEqual(output, test.expectedOutput) {
389				t.Errorf("unexpected output. Expected: %v, Got: %v", test.expectedOutput, output)
390			}
391		})
392	}
393}
394
395func TestNodeTree_List_Exhausted(t *testing.T) {
396	nt := newNodeTree(allNodes[:9])
397	nt.numNodes++
398	_, err := nt.list()
399	if err == nil {
400		t.Fatal("Expected an error from zone exhaustion")
401	}
402}
403
404func TestNodeTreeMultiOperations(t *testing.T) {
405	tests := []struct {
406		name           string
407		nodesToAdd     []*v1.Node
408		nodesToRemove  []*v1.Node
409		operations     []string
410		expectedOutput []string
411	}{
412		{
413			name:           "add and remove all nodes",
414			nodesToAdd:     allNodes[2:9],
415			nodesToRemove:  allNodes[2:9],
416			operations:     []string{"add", "add", "add", "remove", "remove", "remove"},
417			expectedOutput: nil,
418		},
419		{
420			name:           "add and remove some nodes",
421			nodesToAdd:     allNodes[2:9],
422			nodesToRemove:  allNodes[2:9],
423			operations:     []string{"add", "add", "add", "remove"},
424			expectedOutput: []string{"node-3", "node-4"},
425		},
426		{
427			name:           "remove three nodes",
428			nodesToAdd:     allNodes[2:9],
429			nodesToRemove:  allNodes[2:9],
430			operations:     []string{"add", "add", "add", "remove", "remove", "remove", "add"},
431			expectedOutput: []string{"node-5"},
432		},
433		{
434			name:           "add more nodes to an exhausted zone",
435			nodesToAdd:     append(allNodes[4:9:9], allNodes[3]),
436			nodesToRemove:  nil,
437			operations:     []string{"add", "add", "add", "add", "add", "add"},
438			expectedOutput: []string{"node-4", "node-5", "node-6", "node-3", "node-7", "node-8"},
439		},
440		{
441			name:           "remove zone and add new",
442			nodesToAdd:     append(allNodes[3:5:5], allNodes[6:8]...),
443			nodesToRemove:  allNodes[3:5],
444			operations:     []string{"add", "add", "remove", "add", "add", "remove"},
445			expectedOutput: []string{"node-6", "node-7"},
446		},
447	}
448
449	for _, test := range tests {
450		t.Run(test.name, func(t *testing.T) {
451			nt := newNodeTree(nil)
452			addIndex := 0
453			removeIndex := 0
454			for _, op := range test.operations {
455				switch op {
456				case "add":
457					if addIndex >= len(test.nodesToAdd) {
458						t.Error("more add operations than nodesToAdd")
459					} else {
460						nt.addNode(test.nodesToAdd[addIndex])
461						addIndex++
462					}
463				case "remove":
464					if removeIndex >= len(test.nodesToRemove) {
465						t.Error("more remove operations than nodesToRemove")
466					} else {
467						nt.removeNode(test.nodesToRemove[removeIndex])
468						removeIndex++
469					}
470				default:
471					t.Errorf("unknow operation: %v", op)
472				}
473			}
474			output, err := nt.list()
475			if err != nil {
476				t.Fatal(err)
477			}
478			if !reflect.DeepEqual(output, test.expectedOutput) {
479				t.Errorf("unexpected output. Expected: %v, Got: %v", test.expectedOutput, output)
480			}
481		})
482	}
483}
484