graph_test.go

Documentation: k8s.io/kubernetes/plugin/pkg/auth/authorizer/node

     1  /*
     2  Copyright 2018 The Kubernetes Authors.
     3  
     4  Licensed under the Apache License, Version 2.0 (the "License");
     5  you may not use this file except in compliance with the License.
     6  You may obtain a copy of the License at
     7  
     8      http://www.apache.org/licenses/LICENSE-2.0
     9  
    10  Unless required by applicable law or agreed to in writing, software
    11  distributed under the License is distributed on an "AS IS" BASIS,
    12  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
    13  See the License for the specific language governing permissions and
    14  limitations under the License.
    15  */
    16  
    17  package node
    18  
    19  import (
    20  	"encoding/json"
    21  	"fmt"
    22  	"reflect"
    23  	"sort"
    24  	"testing"
    25  
    26  	"github.com/stretchr/testify/assert"
    27  
    28  	corev1 "k8s.io/api/core/v1"
    29  	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
    30  	"k8s.io/apimachinery/pkg/types"
    31  )
    32  
    33  func TestDeleteEdges_locked(t *testing.T) {
    34  	cases := []struct {
    35  		desc        string
    36  		fromType    vertexType
    37  		toType      vertexType
    38  		toNamespace string
    39  		toName      string
    40  		start       *Graph
    41  		expect      *Graph
    42  	}{
    43  		{
    44  			// single edge from a configmap to a node, will delete edge and orphaned configmap
    45  			desc:        "edges and source orphans are deleted, destination orphans are preserved",
    46  			fromType:    configMapVertexType,
    47  			toType:      nodeVertexType,
    48  			toNamespace: "",
    49  			toName:      "node1",
    50  			start: func() *Graph {
    51  				g := NewGraph()
    52  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap2")
    53  				nodeVertex := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
    54  				configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
    55  				g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex, nodeVertex))
    56  				return g
    57  			}(),
    58  			expect: func() *Graph {
    59  				g := NewGraph()
    60  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap2")
    61  				g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
    62  				return g
    63  			}(),
    64  		},
    65  		{
    66  			// two edges from the same configmap to distinct nodes, will delete one of the edges
    67  			desc:        "edges are deleted, non-orphans and destination orphans are preserved",
    68  			fromType:    configMapVertexType,
    69  			toType:      nodeVertexType,
    70  			toNamespace: "",
    71  			toName:      "node2",
    72  			start: func() *Graph {
    73  				g := NewGraph()
    74  				nodeVertex1 := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
    75  				nodeVertex2 := g.getOrCreateVertex_locked(nodeVertexType, "", "node2")
    76  				configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
    77  				g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex1, nodeVertex1))
    78  				g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex2, nodeVertex2))
    79  				return g
    80  			}(),
    81  			expect: func() *Graph {
    82  				g := NewGraph()
    83  				nodeVertex1 := g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
    84  				g.getOrCreateVertex_locked(nodeVertexType, "", "node2")
    85  				configmapVertex := g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
    86  				g.graph.SetEdge(newDestinationEdge(configmapVertex, nodeVertex1, nodeVertex1))
    87  				return g
    88  			}(),
    89  		},
    90  		{
    91  			desc:        "no edges to delete",
    92  			fromType:    configMapVertexType,
    93  			toType:      nodeVertexType,
    94  			toNamespace: "",
    95  			toName:      "node1",
    96  			start: func() *Graph {
    97  				g := NewGraph()
    98  				g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
    99  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
   100  				return g
   101  			}(),
   102  			expect: func() *Graph {
   103  				g := NewGraph()
   104  				g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
   105  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
   106  				return g
   107  			}(),
   108  		},
   109  		{
   110  			desc:        "destination vertex does not exist",
   111  			fromType:    configMapVertexType,
   112  			toType:      nodeVertexType,
   113  			toNamespace: "",
   114  			toName:      "node1",
   115  			start: func() *Graph {
   116  				g := NewGraph()
   117  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
   118  				return g
   119  			}(),
   120  			expect: func() *Graph {
   121  				g := NewGraph()
   122  				g.getOrCreateVertex_locked(configMapVertexType, "namespace1", "configmap1")
   123  				return g
   124  			}(),
   125  		},
   126  		{
   127  			desc:        "source vertex type doesn't exist",
   128  			fromType:    configMapVertexType,
   129  			toType:      nodeVertexType,
   130  			toNamespace: "",
   131  			toName:      "node1",
   132  			start: func() *Graph {
   133  				g := NewGraph()
   134  				g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
   135  				return g
   136  			}(),
   137  			expect: func() *Graph {
   138  				g := NewGraph()
   139  				g.getOrCreateVertex_locked(nodeVertexType, "", "node1")
   140  				return g
   141  			}(),
   142  		},
   143  	}
   144  	for _, c := range cases {
   145  		t.Run(c.desc, func(t *testing.T) {
   146  			c.start.deleteEdges_locked(c.fromType, c.toType, c.toNamespace, c.toName)
   147  
   148  			// Note: We assert on substructures (graph.Nodes(), graph.Edges()) because the graph tracks
   149  			// freed IDs for reuse, which results in an irrelevant inequality between start and expect.
   150  
   151  			// sort the nodes by ID
   152  			// (the slices we get back are from map iteration, where order is not guaranteed)
   153  			expectNodes := c.expect.graph.Nodes()
   154  			sort.Slice(expectNodes, func(i, j int) bool {
   155  				return expectNodes[i].ID() < expectNodes[j].ID()
   156  			})
   157  			startNodes := c.start.graph.Nodes()
   158  			sort.Slice(startNodes, func(i, j int) bool {
   159  				return startNodes[i].ID() < startNodes[j].ID()
   160  			})
   161  			assert.Equal(t, expectNodes, startNodes)
   162  
   163  			// sort the edges by from ID, then to ID
   164  			// (the slices we get back are from map iteration, where order is not guaranteed)
   165  			expectEdges := c.expect.graph.Edges()
   166  			sort.Slice(expectEdges, func(i, j int) bool {
   167  				if expectEdges[i].From().ID() == expectEdges[j].From().ID() {
   168  					return expectEdges[i].To().ID() < expectEdges[j].To().ID()
   169  				}
   170  				return expectEdges[i].From().ID() < expectEdges[j].From().ID()
   171  			})
   172  			startEdges := c.start.graph.Edges()
   173  			sort.Slice(startEdges, func(i, j int) bool {
   174  				if startEdges[i].From().ID() == startEdges[j].From().ID() {
   175  					return startEdges[i].To().ID() < startEdges[j].To().ID()
   176  				}
   177  				return startEdges[i].From().ID() < startEdges[j].From().ID()
   178  			})
   179  			assert.Equal(t, expectEdges, startEdges)
   180  
   181  			// vertices is a recursive map, no need to sort
   182  			assert.Equal(t, c.expect.vertices, c.start.vertices)
   183  		})
   184  	}
   185  }
   186  
   187  func TestIndex(t *testing.T) {
   188  	g := NewGraph()
   189  	g.destinationEdgeThreshold = 3
   190  
   191  	a := NewAuthorizer(g, nil, nil)
   192  
   193  	addPod := func(podNumber, nodeNumber int) {
   194  		t.Helper()
   195  		nodeName := fmt.Sprintf("node%d", nodeNumber)
   196  		podName := fmt.Sprintf("pod%d", podNumber)
   197  		pod := &corev1.Pod{
   198  			ObjectMeta: metav1.ObjectMeta{Name: podName, Namespace: "ns", UID: types.UID(fmt.Sprintf("pod%duid1", podNumber))},
   199  			Spec: corev1.PodSpec{
   200  				NodeName:                 nodeName,
   201  				ServiceAccountName:       "sa1",
   202  				DeprecatedServiceAccount: "sa1",
   203  				Volumes: []corev1.Volume{
   204  					{Name: "volume1", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm1"}}}},
   205  					{Name: "volume2", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm2"}}}},
   206  					{Name: "volume3", VolumeSource: corev1.VolumeSource{ConfigMap: &corev1.ConfigMapVolumeSource{LocalObjectReference: corev1.LocalObjectReference{Name: "cm3"}}}},
   207  				},
   208  			},
   209  		}
   210  		g.AddPod(pod)
   211  		if ok, err := a.hasPathFrom(nodeName, configMapVertexType, "ns", "cm1"); err != nil || !ok {
   212  			t.Errorf("expected path from %s to cm1, got %v, %v", nodeName, ok, err)
   213  		}
   214  	}
   215  
   216  	toString := func(id int) string {
   217  		for _, namespaceName := range g.vertices {
   218  			for _, nameVertex := range namespaceName {
   219  				for _, vertex := range nameVertex {
   220  					if vertex.id == id {
   221  						return vertex.String()
   222  					}
   223  				}
   224  			}
   225  		}
   226  		return ""
   227  	}
   228  	expectGraph := func(expect map[string][]string) {
   229  		t.Helper()
   230  		actual := map[string][]string{}
   231  		for _, node := range g.graph.Nodes() {
   232  			sortedTo := []string{}
   233  			for _, to := range g.graph.From(node) {
   234  				sortedTo = append(sortedTo, toString(to.ID()))
   235  			}
   236  			sort.Strings(sortedTo)
   237  			actual[toString(node.ID())] = sortedTo
   238  		}
   239  		if !reflect.DeepEqual(expect, actual) {
   240  			e, _ := json.MarshalIndent(expect, "", "  ")
   241  			a, _ := json.MarshalIndent(actual, "", "  ")
   242  			t.Errorf("expected graph:\n%s\ngot:\n%s", string(e), string(a))
   243  		}
   244  	}
   245  	expectIndex := func(expect map[string][]string) {
   246  		t.Helper()
   247  		actual := map[string][]string{}
   248  		for from, to := range g.destinationEdgeIndex {
   249  			sortedValues := []string{}
   250  			for member, count := range to.members {
   251  				sortedValues = append(sortedValues, fmt.Sprintf("%s=%d", toString(member), count))
   252  			}
   253  			sort.Strings(sortedValues)
   254  			actual[toString(from)] = sortedValues
   255  		}
   256  		if !reflect.DeepEqual(expect, actual) {
   257  			e, _ := json.MarshalIndent(expect, "", "  ")
   258  			a, _ := json.MarshalIndent(actual, "", "  ")
   259  			t.Errorf("expected index:\n%s\ngot:\n%s", string(e), string(a))
   260  		}
   261  	}
   262  
   263  	for i := 1; i <= g.destinationEdgeThreshold; i++ {
   264  		addPod(i, i)
   265  		if i < g.destinationEdgeThreshold {
   266  			// if we're under the threshold, no index expected
   267  			expectIndex(map[string][]string{})
   268  		}
   269  	}
   270  	expectGraph(map[string][]string{
   271  		"node:node1":            {},
   272  		"node:node2":            {},
   273  		"node:node3":            {},
   274  		"pod:ns/pod1":           {"node:node1"},
   275  		"pod:ns/pod2":           {"node:node2"},
   276  		"pod:ns/pod3":           {"node:node3"},
   277  		"configmap:ns/cm1":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
   278  		"configmap:ns/cm2":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
   279  		"configmap:ns/cm3":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
   280  		"serviceAccount:ns/sa1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3"},
   281  	})
   282  	expectIndex(map[string][]string{
   283  		"configmap:ns/cm1":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   284  		"configmap:ns/cm2":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   285  		"configmap:ns/cm3":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   286  		"serviceAccount:ns/sa1": {"node:node1=1", "node:node2=1", "node:node3=1"},
   287  	})
   288  
   289  	// delete one to drop below the threshold
   290  	g.DeletePod("pod1", "ns")
   291  	expectGraph(map[string][]string{
   292  		"node:node2":            {},
   293  		"node:node3":            {},
   294  		"pod:ns/pod2":           {"node:node2"},
   295  		"pod:ns/pod3":           {"node:node3"},
   296  		"configmap:ns/cm1":      {"pod:ns/pod2", "pod:ns/pod3"},
   297  		"configmap:ns/cm2":      {"pod:ns/pod2", "pod:ns/pod3"},
   298  		"configmap:ns/cm3":      {"pod:ns/pod2", "pod:ns/pod3"},
   299  		"serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3"},
   300  	})
   301  	expectIndex(map[string][]string{})
   302  
   303  	// add two to get above the threshold
   304  	addPod(1, 1)
   305  	addPod(4, 1)
   306  	expectGraph(map[string][]string{
   307  		"node:node1":            {},
   308  		"node:node2":            {},
   309  		"node:node3":            {},
   310  		"pod:ns/pod1":           {"node:node1"},
   311  		"pod:ns/pod2":           {"node:node2"},
   312  		"pod:ns/pod3":           {"node:node3"},
   313  		"pod:ns/pod4":           {"node:node1"},
   314  		"configmap:ns/cm1":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   315  		"configmap:ns/cm2":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   316  		"configmap:ns/cm3":      {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   317  		"serviceAccount:ns/sa1": {"pod:ns/pod1", "pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   318  	})
   319  	expectIndex(map[string][]string{
   320  		"configmap:ns/cm1":      {"node:node1=2", "node:node2=1", "node:node3=1"},
   321  		"configmap:ns/cm2":      {"node:node1=2", "node:node2=1", "node:node3=1"},
   322  		"configmap:ns/cm3":      {"node:node1=2", "node:node2=1", "node:node3=1"},
   323  		"serviceAccount:ns/sa1": {"node:node1=2", "node:node2=1", "node:node3=1"},
   324  	})
   325  
   326  	// delete one to remain above the threshold
   327  	g.DeletePod("pod1", "ns")
   328  	expectGraph(map[string][]string{
   329  		"node:node1":            {},
   330  		"node:node2":            {},
   331  		"node:node3":            {},
   332  		"pod:ns/pod2":           {"node:node2"},
   333  		"pod:ns/pod3":           {"node:node3"},
   334  		"pod:ns/pod4":           {"node:node1"},
   335  		"configmap:ns/cm1":      {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   336  		"configmap:ns/cm2":      {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   337  		"configmap:ns/cm3":      {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   338  		"serviceAccount:ns/sa1": {"pod:ns/pod2", "pod:ns/pod3", "pod:ns/pod4"},
   339  	})
   340  	expectIndex(map[string][]string{
   341  		"configmap:ns/cm1":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   342  		"configmap:ns/cm2":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   343  		"configmap:ns/cm3":      {"node:node1=1", "node:node2=1", "node:node3=1"},
   344  		"serviceAccount:ns/sa1": {"node:node1=1", "node:node2=1", "node:node3=1"},
   345  	})
   346  }
   347
View as plain text