mirror of
https://github.com/k3s-io/kubernetes.git
synced 2025-07-27 21:47:07 +00:00
347 lines
12 KiB
Go
347 lines
12 KiB
Go
/*
|
|
Copyright 2018 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 node
|
|
|
|
import (
|
|
"encoding/json"
|
|
"fmt"
|
|
"reflect"
|
|
"sort"
|
|
"testing"
|
|
|
|
"github.com/stretchr/testify/assert"
|
|
|
|
corev1 "k8s.io/api/core/v1"
|
|
metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
|
|
"k8s.io/apimachinery/pkg/types"
|
|
)
|
|
|
|
func TestDeleteEdges_locked(t *testing.T) {
|
|
cases := []struct {
|
|
desc string
|
|
fromType vertexType
|
|
toType vertexType
|
|
toNamespace string
|
|
toName string
|
|
start *Graph
|
|
expect *Graph
|
|
}{
|
|
{
|
|
// single edge from a configmap to a node, will delete edge and orphaned configmap
|
|
desc: "edges and source orphans are deleted, destination orphans are preserved",
|
|
fromType: configMapVertexType,
|
|
toType: nodeVertexType,
|
|
toNamespace: "",
|
|
toName: "node1",
|
|
start: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap2")
|
|
nodeVertex := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex, nodeVertex))
|
|
return g
|
|
}(),
|
|
expect: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap2")
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
return g
|
|
}(),
|
|
},
|
|
{
|
|
// two edges from the same configmap to distinct nodes, will delete one of the edges
|
|
desc: "edges are deleted, non-orphans and destination orphans are preserved",
|
|
fromType: configMapVertexType,
|
|
toType: nodeVertexType,
|
|
toNamespace: "",
|
|
toName: "node2",
|
|
start: func() *Graph {
|
|
g := NewGraph()
|
|
nodeVertex1 := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
nodeVertex2 := g.getOrCreateVertex_locked(nodeVertexType, "", "node2")
|
|
configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex1, nodeVertex1))
|
|
g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex2, nodeVertex2))
|
|
return g
|
|
}(),
|
|
expect: func() *Graph {
|
|
g := NewGraph()
|
|
nodeVertex1 := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node2")
|
|
configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex1, nodeVertex1))
|
|
return g
|
|
}(),
|
|
},
|
|
{
|
|
desc: "no edges to delete",
|
|
fromType: configMapVertexType,
|
|
toType: nodeVertexType,
|
|
toNamespace: "",
|
|
toName: "node1",
|
|
start: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
return g
|
|
}(),
|
|
expect: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
return g
|
|
}(),
|
|
},
|
|
{
|
|
desc: "destination vertex does not exist",
|
|
fromType: configMapVertexType,
|
|
toType: nodeVertexType,
|
|
toNamespace: "",
|
|
toName: "node1",
|
|
start: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
return g
|
|
}(),
|
|
expect: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
|
|
return g
|
|
}(),
|
|
},
|
|
{
|
|
desc: "source vertex type doesn't exist",
|
|
fromType: configMapVertexType,
|
|
toType: nodeVertexType,
|
|
toNamespace: "",
|
|
toName: "node1",
|
|
start: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
return g
|
|
}(),
|
|
expect: func() *Graph {
|
|
g := NewGraph()
|
|
g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
|
|
return g
|
|
}(),
|
|
},
|
|
}
|
|
for _, c := range cases {
|
|
t.Run(c.desc, func(t *testing.T) {
|
|
c.start.deleteEdges_locked(c.fromType, c.toType, c.toNamespace, c.toName)
|
|
|
|
// Note: We assert on substructures (graph.Nodes(), graph.Edges()) because the graph tracks
|
|
// freed IDs for reuse, which results in an irrelevant inequality between start and expect.
|
|
|
|
// sort the nodes by ID
|
|
// (the slices we get back are from map iteration, where order is not guaranteed)
|
|
expectNodes := c.expect.graph.Nodes()
|
|
sort.Slice(expectNodes, func(i, j int) bool {
|
|
return expectNodes[i].ID() < expectNodes[j].ID()
|
|
})
|
|
startNodes := c.start.graph.Nodes()
|
|
sort.Slice(startNodes, func(i, j int) bool {
|
|
return startNodes[i].ID() < startNodes[j].ID()
|
|
})
|
|
assert.Equal(t, expectNodes, startNodes)
|
|
|
|
// sort the edges by from ID, then to ID
|
|
// (the slices we get back are from map iteration, where order is not guaranteed)
|
|
expectEdges := c.expect.graph.Edges()
|
|
sort.Slice(expectEdges, func(i, j int) bool {
|
|
if expectEdges[i].From().ID() == expectEdges[j].From().ID() {
|
|
return expectEdges[i].To().ID() < expectEdges[j].To().ID()
|
|
}
|
|
return expectEdges[i].From().ID() < expectEdges[j].From().ID()
|
|
})
|
|
startEdges := c.start.graph.Edges()
|
|
sort.Slice(startEdges, func(i, j int) bool {
|
|
if startEdges[i].From().ID() == startEdges[j].From().ID() {
|
|
return startEdges[i].To().ID() < startEdges[j].To().ID()
|
|
}
|
|
return startEdges[i].From().ID() < startEdges[j].From().ID()
|
|
})
|
|
assert.Equal(t, expectEdges, startEdges)
|
|
|
|
// vertices is a recursive map, no need to sort
|
|
assert.Equal(t, c.expect.vertices, c.start.vertices)
|
|
})
|
|
}
|
|
}
|
|
|
|
func TestIndex(t *testing.T) {
|
|
g := NewGraph()
|
|
g.destinationEdgeThreshold = 3
|
|
|
|
a := NewAuthorizer(g, nil, nil)
|
|
|
|
addPod := func(podNumber, nodeNumber int) {
|
|
t.Helper()
|
|
nodeName := fmt.Sprintf("node%d", nodeNumber)
|
|
podName := fmt.Sprintf("pod%d", podNumber)
|
|
pod := &corev1.Pod{
|
|
ObjectMeta: metav1.ObjectMeta{Name: podName, Namespace: "ns", UID: types.UID(fmt.Sprintf("pod%duid1", podNumber))},
|
|
Spec: corev1.PodSpec{
|
|
NodeName: nodeName,
|
|
ServiceAccountName: "sa1",
|
|
DeprecatedServiceAccount: "sa1",
|
|
Volumes: []corev1.Volume{
|
|
{Name: "volume1", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm1"}}}},
|
|
{Name: "volume2", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm2"}}}},
|
|
{Name: "volume3", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm3"}}}},
|
|
},
|
|
},
|
|
}
|
|
g.AddPod(pod)
|
|
if ok, err := a.hasPathFrom(nodeName, configMapVertexType, "ns", "cm1"); err != nil || !ok {
|
|
t.Errorf("expected path from %s to cm1, got %v, %v", nodeName, ok, err)
|
|
}
|
|
}
|
|
|
|
toString := func(id int) string {
|
|
for _, namespaceName := range g.vertices {
|
|
for _, nameVertex := range namespaceName {
|
|
for _, vertex := range nameVertex {
|
|
if vertex.id == id {
|
|
return vertex.String()
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return ""
|
|
}
|
|
expectGraph := func(expect map[string][]string) {
|
|
t.Helper()
|
|
actual := map[string][]string{}
|
|
for _, node := range g.graph.Nodes() {
|
|
sortedTo := []string{}
|
|
for _, to := range g.graph.From(node) {
|
|
sortedTo = append(sortedTo, toString(to.ID()))
|
|
}
|
|
sort.Strings(sortedTo)
|
|
actual[toString(node.ID())] = sortedTo
|
|
}
|
|
if !reflect.DeepEqual(expect, actual) {
|
|
e, _ := json.MarshalIndent(expect, "", " ")
|
|
a, _ := json.MarshalIndent(actual, "", " ")
|
|
t.Errorf("expected graph:\n%s\ngot:\n%s", string(e), string(a))
|
|
}
|
|
}
|
|
expectIndex := func(expect map[string][]string) {
|
|
t.Helper()
|
|
actual := map[string][]string{}
|
|
for from, to := range g.destinationEdgeIndex {
|
|
sortedValues := []string{}
|
|
for member, count := range to.members {
|
|
sortedValues = append(sortedValues, fmt.Sprintf("%s=%d", toString(member), count))
|
|
}
|
|
sort.Strings(sortedValues)
|
|
actual[toString(from)] = sortedValues
|
|
}
|
|
if !reflect.DeepEqual(expect, actual) {
|
|
e, _ := json.MarshalIndent(expect, "", " ")
|
|
a, _ := json.MarshalIndent(actual, "", " ")
|
|
t.Errorf("expected index:\n%s\ngot:\n%s", string(e), string(a))
|
|
}
|
|
}
|
|
|
|
for i := 1; i <= g.destinationEdgeThreshold; i++ {
|
|
addPod(i, i)
|
|
if i < g.destinationEdgeThreshold {
|
|
// if we're under the threshold, no index expected
|
|
expectIndex(map[string][]string{})
|
|
}
|
|
}
|
|
expectGraph(map[string][]string{
|
|
"node:node1": {},
|
|
"node:node2": {},
|
|
"node:node3": {},
|
|
"pod:ns/pod1": {"node:node1"},
|
|
"pod:ns/pod2": {"node:node2"},
|
|
"pod:ns/pod3": {"node:node3"},
|
|
"configmap:ns/cm1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
|
|
"configmap:ns/cm2": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
|
|
"configmap:ns/cm3": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
|
|
"serviceAccount:ns/sa1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
|
|
})
|
|
expectIndex(map[string][]string{
|
|
"configmap:ns/cm1": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm2": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm3": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"serviceAccount:ns/sa1": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
})
|
|
|
|
// delete one to drop below the threshold
|
|
g.DeletePod("pod1", "ns")
|
|
expectGraph(map[string][]string{
|
|
"node:node2": {},
|
|
"node:node3": {},
|
|
"pod:ns/pod2": {"node:node2"},
|
|
"pod:ns/pod3": {"node:node3"},
|
|
"configmap:ns/cm1": {"pod:ns/pod2", "pod:ns/pod3"},
|
|
"configmap:ns/cm2": {"pod:ns/pod2", "pod:ns/pod3"},
|
|
"configmap:ns/cm3": {"pod:ns/pod2", "pod:ns/pod3"},
|
|
"serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3"},
|
|
})
|
|
expectIndex(map[string][]string{})
|
|
|
|
// add two to get above the threshold
|
|
addPod(1, 1)
|
|
addPod(4, 1)
|
|
expectGraph(map[string][]string{
|
|
"node:node1": {},
|
|
"node:node2": {},
|
|
"node:node3": {},
|
|
"pod:ns/pod1": {"node:node1"},
|
|
"pod:ns/pod2": {"node:node2"},
|
|
"pod:ns/pod3": {"node:node3"},
|
|
"pod:ns/pod4": {"node:node1"},
|
|
"configmap:ns/cm1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"configmap:ns/cm2": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"configmap:ns/cm3": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"serviceAccount:ns/sa1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
})
|
|
expectIndex(map[string][]string{
|
|
"configmap:ns/cm1": {"node:node1=2", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm2": {"node:node1=2", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm3": {"node:node1=2", "node:node2=1", "node:node3=1"},
|
|
"serviceAccount:ns/sa1": {"node:node1=2", "node:node2=1", "node:node3=1"},
|
|
})
|
|
|
|
// delete one to remain above the threshold
|
|
g.DeletePod("pod1", "ns")
|
|
expectGraph(map[string][]string{
|
|
"node:node1": {},
|
|
"node:node2": {},
|
|
"node:node3": {},
|
|
"pod:ns/pod2": {"node:node2"},
|
|
"pod:ns/pod3": {"node:node3"},
|
|
"pod:ns/pod4": {"node:node1"},
|
|
"configmap:ns/cm1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"configmap:ns/cm2": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"configmap:ns/cm3": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
"serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
|
|
})
|
|
expectIndex(map[string][]string{
|
|
"configmap:ns/cm1": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm2": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"configmap:ns/cm3": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
"serviceAccount:ns/sa1": {"node:node1=1", "node:node2=1", "node:node3=1"},
|
|
})
|
|
}
|