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