graph.go

Documentation: k8s.io/kubernetes/pkg/controller/garbagecollector

     1  /*
     2  Copyright 2016 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 garbagecollector
    18  
    19  import (
    20  	"fmt"
    21  	"sync"
    22  
    23  	"github.com/go-logr/logr"
    24  
    25  	metav1 "k8s.io/apimachinery/pkg/apis/meta/v1"
    26  	"k8s.io/apimachinery/pkg/types"
    27  )
    28  
    29  type objectReference struct {
    30  	metav1.OwnerReference
    31  	// This is needed by the dynamic client
    32  	Namespace string
    33  }
    34  
    35  // String is used when logging an objectReference in text format.
    36  func (s objectReference) String() string {
    37  	return fmt.Sprintf("[%s/%s, namespace: %s, name: %s, uid: %s]", s.APIVersion, s.Kind, s.Namespace, s.Name, s.UID)
    38  }
    39  
    40  // MarshalLog is used when logging an objectReference in JSON format.
    41  func (s objectReference) MarshalLog() interface{} {
    42  	return struct {
    43  		Name       string    `json:"name"`
    44  		Namespace  string    `json:"namespace"`
    45  		APIVersion string    `json:"apiVersion"`
    46  		UID        types.UID `json:"uid"`
    47  	}{
    48  		Namespace:  s.Namespace,
    49  		Name:       s.Name,
    50  		APIVersion: s.APIVersion,
    51  		UID:        s.UID,
    52  	}
    53  }
    54  
    55  var _ fmt.Stringer = objectReference{}
    56  var _ logr.Marshaler = objectReference{}
    57  
    58  // The single-threaded GraphBuilder.processGraphChanges() is the sole writer of the
    59  // nodes. The multi-threaded GarbageCollector.attemptToDeleteItem() reads the nodes.
    60  // WARNING: node has different locks on different fields. setters and getters
    61  // use the respective locks, so the return values of the getters can be
    62  // inconsistent.
    63  type node struct {
    64  	identity objectReference
    65  	// dependents will be read by the orphan() routine, we need to protect it with a lock.
    66  	dependentsLock sync.RWMutex
    67  	// dependents are the nodes that have node.identity as a
    68  	// metadata.ownerReference.
    69  	dependents map[*node]struct{}
    70  	// this is set by processGraphChanges() if the object has non-nil DeletionTimestamp
    71  	// and has the FinalizerDeleteDependents.
    72  	deletingDependents     bool
    73  	deletingDependentsLock sync.RWMutex
    74  	// this records if the object's deletionTimestamp is non-nil.
    75  	beingDeleted     bool
    76  	beingDeletedLock sync.RWMutex
    77  	// this records if the object was constructed virtually and never observed via informer event
    78  	virtual     bool
    79  	virtualLock sync.RWMutex
    80  	// when processing an Update event, we need to compare the updated
    81  	// ownerReferences with the owners recorded in the graph.
    82  	owners []metav1.OwnerReference
    83  }
    84  
    85  // clone() must only be called from the single-threaded GraphBuilder.processGraphChanges()
    86  func (n *node) clone() *node {
    87  	c := &node{
    88  		identity:           n.identity,
    89  		dependents:         make(map[*node]struct{}, len(n.dependents)),
    90  		deletingDependents: n.deletingDependents,
    91  		beingDeleted:       n.beingDeleted,
    92  		virtual:            n.virtual,
    93  		owners:             make([]metav1.OwnerReference, 0, len(n.owners)),
    94  	}
    95  	for dep := range n.dependents {
    96  		c.dependents[dep] = struct{}{}
    97  	}
    98  	for _, owner := range n.owners {
    99  		c.owners = append(c.owners, owner)
   100  	}
   101  	return c
   102  }
   103  
   104  // An object is on a one way trip to its final deletion if it starts being
   105  // deleted, so we only provide a function to set beingDeleted to true.
   106  func (n *node) markBeingDeleted() {
   107  	n.beingDeletedLock.Lock()
   108  	defer n.beingDeletedLock.Unlock()
   109  	n.beingDeleted = true
   110  }
   111  
   112  func (n *node) isBeingDeleted() bool {
   113  	n.beingDeletedLock.RLock()
   114  	defer n.beingDeletedLock.RUnlock()
   115  	return n.beingDeleted
   116  }
   117  
   118  func (n *node) markObserved() {
   119  	n.virtualLock.Lock()
   120  	defer n.virtualLock.Unlock()
   121  	n.virtual = false
   122  }
   123  func (n *node) isObserved() bool {
   124  	n.virtualLock.RLock()
   125  	defer n.virtualLock.RUnlock()
   126  	return !n.virtual
   127  }
   128  
   129  func (n *node) markDeletingDependents() {
   130  	n.deletingDependentsLock.Lock()
   131  	defer n.deletingDependentsLock.Unlock()
   132  	n.deletingDependents = true
   133  }
   134  
   135  func (n *node) isDeletingDependents() bool {
   136  	n.deletingDependentsLock.RLock()
   137  	defer n.deletingDependentsLock.RUnlock()
   138  	return n.deletingDependents
   139  }
   140  
   141  func (n *node) addDependent(dependent *node) {
   142  	n.dependentsLock.Lock()
   143  	defer n.dependentsLock.Unlock()
   144  	n.dependents[dependent] = struct{}{}
   145  }
   146  
   147  func (n *node) deleteDependent(dependent *node) {
   148  	n.dependentsLock.Lock()
   149  	defer n.dependentsLock.Unlock()
   150  	delete(n.dependents, dependent)
   151  }
   152  
   153  func (n *node) dependentsLength() int {
   154  	n.dependentsLock.RLock()
   155  	defer n.dependentsLock.RUnlock()
   156  	return len(n.dependents)
   157  }
   158  
   159  // Note that this function does not provide any synchronization guarantees;
   160  // items could be added to or removed from ownerNode.dependents the moment this
   161  // function returns.
   162  func (n *node) getDependents() []*node {
   163  	n.dependentsLock.RLock()
   164  	defer n.dependentsLock.RUnlock()
   165  	var ret []*node
   166  	for dep := range n.dependents {
   167  		ret = append(ret, dep)
   168  	}
   169  	return ret
   170  }
   171  
   172  // blockingDependents returns the dependents that are blocking the deletion of
   173  // n, i.e., the dependent that has an ownerReference pointing to n, and
   174  // the BlockOwnerDeletion field of that ownerReference is true.
   175  // Note that this function does not provide any synchronization guarantees;
   176  // items could be added to or removed from ownerNode.dependents the moment this
   177  // function returns.
   178  func (n *node) blockingDependents() []*node {
   179  	dependents := n.getDependents()
   180  	var ret []*node
   181  	for _, dep := range dependents {
   182  		for _, owner := range dep.owners {
   183  			if owner.UID == n.identity.UID && owner.BlockOwnerDeletion != nil && *owner.BlockOwnerDeletion {
   184  				ret = append(ret, dep)
   185  			}
   186  		}
   187  	}
   188  	return ret
   189  }
   190  
   191  // ownerReferenceCoordinates returns an owner reference containing only the coordinate fields
   192  // from the input reference (uid, name, kind, apiVersion)
   193  func ownerReferenceCoordinates(ref metav1.OwnerReference) metav1.OwnerReference {
   194  	return metav1.OwnerReference{
   195  		UID:        ref.UID,
   196  		Name:       ref.Name,
   197  		Kind:       ref.Kind,
   198  		APIVersion: ref.APIVersion,
   199  	}
   200  }
   201  
   202  // ownerReferenceMatchesCoordinates returns true if all of the coordinate fields match
   203  // between the two references (uid, name, kind, apiVersion)
   204  func ownerReferenceMatchesCoordinates(a, b metav1.OwnerReference) bool {
   205  	return a.UID == b.UID && a.Name == b.Name && a.Kind == b.Kind && a.APIVersion == b.APIVersion
   206  }
   207  
   208  // String renders node as a string using fmt. Acquires a read lock to ensure the
   209  // reflective dump of dependents doesn't race with any concurrent writes.
   210  func (n *node) String() string {
   211  	n.dependentsLock.RLock()
   212  	defer n.dependentsLock.RUnlock()
   213  	return fmt.Sprintf("%#v", n)
   214  }
   215  
   216  type concurrentUIDToNode struct {
   217  	uidToNodeLock sync.RWMutex
   218  	uidToNode     map[types.UID]*node
   219  }
   220  
   221  func (m *concurrentUIDToNode) Write(node *node) {
   222  	m.uidToNodeLock.Lock()
   223  	defer m.uidToNodeLock.Unlock()
   224  	m.uidToNode[node.identity.UID] = node
   225  }
   226  
   227  func (m *concurrentUIDToNode) Read(uid types.UID) (*node, bool) {
   228  	m.uidToNodeLock.RLock()
   229  	defer m.uidToNodeLock.RUnlock()
   230  	n, ok := m.uidToNode[uid]
   231  	return n, ok
   232  }
   233  
   234  func (m *concurrentUIDToNode) Delete(uid types.UID) {
   235  	m.uidToNodeLock.Lock()
   236  	defer m.uidToNodeLock.Unlock()
   237  	delete(m.uidToNode, uid)
   238  }
   239
View as plain text