1/* 2Copyright 2017 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 history 18 19import ( 20 "bytes" 21 "context" 22 "encoding/json" 23 "fmt" 24 "hash/fnv" 25 "sort" 26 "strconv" 27 28 apps "k8s.io/api/apps/v1" 29 appsinformers "k8s.io/client-go/informers/apps/v1" 30 clientset "k8s.io/client-go/kubernetes" 31 appslisters "k8s.io/client-go/listers/apps/v1" 32 hashutil "k8s.io/kubernetes/pkg/util/hash" 33 34 apiequality "k8s.io/apimachinery/pkg/api/equality" 35 "k8s.io/apimachinery/pkg/api/errors" 36 metav1 "k8s.io/apimachinery/pkg/apis/meta/v1" 37 "k8s.io/apimachinery/pkg/labels" 38 "k8s.io/apimachinery/pkg/runtime" 39 "k8s.io/apimachinery/pkg/types" 40 41 "k8s.io/apimachinery/pkg/runtime/schema" 42 "k8s.io/apimachinery/pkg/util/rand" 43 "k8s.io/client-go/tools/cache" 44 "k8s.io/client-go/util/retry" 45) 46 47// ControllerRevisionHashLabel is the label used to indicate the hash value of a ControllerRevision's Data. 48const ControllerRevisionHashLabel = "controller.kubernetes.io/hash" 49 50// ControllerRevisionName returns the Name for a ControllerRevision in the form prefix-hash. If the length 51// of prefix is greater than 223 bytes, it is truncated to allow for a name that is no larger than 253 bytes. 52func ControllerRevisionName(prefix string, hash string) string { 53 if len(prefix) > 223 { 54 prefix = prefix[:223] 55 } 56 57 return fmt.Sprintf("%s-%s", prefix, hash) 58} 59 60// NewControllerRevision returns a ControllerRevision with a ControllerRef pointing to parent and indicating that 61// parent is of parentKind. The ControllerRevision has labels matching template labels, contains Data equal to data, and 62// has a Revision equal to revision. The collisionCount is used when creating the name of the ControllerRevision 63// so the name is likely unique. If the returned error is nil, the returned ControllerRevision is valid. If the 64// returned error is not nil, the returned ControllerRevision is invalid for use. 65func NewControllerRevision(parent metav1.Object, 66 parentKind schema.GroupVersionKind, 67 templateLabels map[string]string, 68 data runtime.RawExtension, 69 revision int64, 70 collisionCount *int32) (*apps.ControllerRevision, error) { 71 labelMap := make(map[string]string) 72 for k, v := range templateLabels { 73 labelMap[k] = v 74 } 75 cr := &apps.ControllerRevision{ 76 ObjectMeta: metav1.ObjectMeta{ 77 Labels: labelMap, 78 OwnerReferences: []metav1.OwnerReference{*metav1.NewControllerRef(parent, parentKind)}, 79 }, 80 Data: data, 81 Revision: revision, 82 } 83 hash := HashControllerRevision(cr, collisionCount) 84 cr.Name = ControllerRevisionName(parent.GetName(), hash) 85 cr.Labels[ControllerRevisionHashLabel] = hash 86 return cr, nil 87} 88 89// HashControllerRevision hashes the contents of revision's Data using FNV hashing. If probe is not nil, the byte value 90// of probe is added written to the hash as well. The returned hash will be a safe encoded string to avoid bad words. 91func HashControllerRevision(revision *apps.ControllerRevision, probe *int32) string { 92 hf := fnv.New32() 93 if len(revision.Data.Raw) > 0 { 94 hf.Write(revision.Data.Raw) 95 } 96 if revision.Data.Object != nil { 97 hashutil.DeepHashObject(hf, revision.Data.Object) 98 } 99 if probe != nil { 100 hf.Write([]byte(strconv.FormatInt(int64(*probe), 10))) 101 } 102 return rand.SafeEncodeString(fmt.Sprint(hf.Sum32())) 103} 104 105// SortControllerRevisions sorts revisions by their Revision. 106func SortControllerRevisions(revisions []*apps.ControllerRevision) { 107 sort.Stable(byRevision(revisions)) 108} 109 110// EqualRevision returns true if lhs and rhs are either both nil, or both point to non-nil ControllerRevisions that 111// contain semantically equivalent data. Otherwise this method returns false. 112func EqualRevision(lhs *apps.ControllerRevision, rhs *apps.ControllerRevision) bool { 113 var lhsHash, rhsHash *uint32 114 if lhs == nil || rhs == nil { 115 return lhs == rhs 116 } 117 if hs, found := lhs.Labels[ControllerRevisionHashLabel]; found { 118 hash, err := strconv.ParseInt(hs, 10, 32) 119 if err == nil { 120 lhsHash = new(uint32) 121 *lhsHash = uint32(hash) 122 } 123 } 124 if hs, found := rhs.Labels[ControllerRevisionHashLabel]; found { 125 hash, err := strconv.ParseInt(hs, 10, 32) 126 if err == nil { 127 rhsHash = new(uint32) 128 *rhsHash = uint32(hash) 129 } 130 } 131 if lhsHash != nil && rhsHash != nil && *lhsHash != *rhsHash { 132 return false 133 } 134 return bytes.Equal(lhs.Data.Raw, rhs.Data.Raw) && apiequality.Semantic.DeepEqual(lhs.Data.Object, rhs.Data.Object) 135} 136 137// FindEqualRevisions returns all ControllerRevisions in revisions that are equal to needle using EqualRevision as the 138// equality test. The returned slice preserves the order of revisions. 139func FindEqualRevisions(revisions []*apps.ControllerRevision, needle *apps.ControllerRevision) []*apps.ControllerRevision { 140 var eq []*apps.ControllerRevision 141 for i := range revisions { 142 if EqualRevision(revisions[i], needle) { 143 eq = append(eq, revisions[i]) 144 } 145 } 146 return eq 147} 148 149// byRevision implements sort.Interface to allow ControllerRevisions to be sorted by Revision. 150type byRevision []*apps.ControllerRevision 151 152func (br byRevision) Len() int { 153 return len(br) 154} 155 156// Less breaks ties first by creation timestamp, then by name 157func (br byRevision) Less(i, j int) bool { 158 if br[i].Revision == br[j].Revision { 159 if br[j].CreationTimestamp.Equal(&br[i].CreationTimestamp) { 160 return br[i].Name < br[j].Name 161 } 162 return br[j].CreationTimestamp.After(br[i].CreationTimestamp.Time) 163 } 164 return br[i].Revision < br[j].Revision 165} 166 167func (br byRevision) Swap(i, j int) { 168 br[i], br[j] = br[j], br[i] 169} 170 171// Interface provides an interface allowing for management of a Controller's history as realized by recorded 172// ControllerRevisions. An instance of Interface can be retrieved from NewHistory. Implementations must treat all 173// pointer parameters as "in" parameter, and they must not be mutated. 174type Interface interface { 175 // ListControllerRevisions lists all ControllerRevisions matching selector and owned by parent or no other 176 // controller. If the returned error is nil the returned slice of ControllerRevisions is valid. If the 177 // returned error is not nil, the returned slice is not valid. 178 ListControllerRevisions(parent metav1.Object, selector labels.Selector) ([]*apps.ControllerRevision, error) 179 // CreateControllerRevision attempts to create the revision as owned by parent via a ControllerRef. If name 180 // collision occurs, collisionCount (incremented each time collision occurs except for the first time) is 181 // added to the hash of the revision and it is renamed using ControllerRevisionName. Implementations may 182 // cease to attempt to retry creation after some number of attempts and return an error. If the returned 183 // error is not nil, creation failed. If the returned error is nil, the returned ControllerRevision has been 184 // created. 185 // Callers must make sure that collisionCount is not nil. An error is returned if it is. 186 CreateControllerRevision(parent metav1.Object, revision *apps.ControllerRevision, collisionCount *int32) (*apps.ControllerRevision, error) 187 // DeleteControllerRevision attempts to delete revision. If the returned error is not nil, deletion has failed. 188 DeleteControllerRevision(revision *apps.ControllerRevision) error 189 // UpdateControllerRevision updates revision such that its Revision is equal to newRevision. Implementations 190 // may retry on conflict. If the returned error is nil, the update was successful and returned ControllerRevision 191 // is valid. If the returned error is not nil, the update failed and the returned ControllerRevision is invalid. 192 UpdateControllerRevision(revision *apps.ControllerRevision, newRevision int64) (*apps.ControllerRevision, error) 193 // AdoptControllerRevision attempts to adopt revision by adding a ControllerRef indicating that the parent 194 // Object of parentKind is the owner of revision. If revision is already owned, an error is returned. If the 195 // resource patch fails, an error is returned. If no error is returned, the returned ControllerRevision is 196 // valid. 197 AdoptControllerRevision(parent metav1.Object, parentKind schema.GroupVersionKind, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) 198 // ReleaseControllerRevision attempts to release parent's ownership of revision by removing parent from the 199 // OwnerReferences of revision. If an error is returned, parent remains the owner of revision. If no error is 200 // returned, the returned ControllerRevision is valid. 201 ReleaseControllerRevision(parent metav1.Object, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) 202} 203 204// NewHistory returns an instance of Interface that uses client to communicate with the API Server and lister to list 205// ControllerRevisions. This method should be used to create an Interface for all scenarios other than testing. 206func NewHistory(client clientset.Interface, lister appslisters.ControllerRevisionLister) Interface { 207 return &realHistory{client, lister} 208} 209 210// NewFakeHistory returns an instance of Interface that uses informer to create, update, list, and delete 211// ControllerRevisions. This method should be used to create an Interface for testing purposes. 212func NewFakeHistory(informer appsinformers.ControllerRevisionInformer) Interface { 213 return &fakeHistory{informer.Informer().GetIndexer(), informer.Lister()} 214} 215 216type realHistory struct { 217 client clientset.Interface 218 lister appslisters.ControllerRevisionLister 219} 220 221func (rh *realHistory) ListControllerRevisions(parent metav1.Object, selector labels.Selector) ([]*apps.ControllerRevision, error) { 222 // List all revisions in the namespace that match the selector 223 history, err := rh.lister.ControllerRevisions(parent.GetNamespace()).List(selector) 224 if err != nil { 225 return nil, err 226 } 227 var owned []*apps.ControllerRevision 228 for i := range history { 229 ref := metav1.GetControllerOfNoCopy(history[i]) 230 if ref == nil || ref.UID == parent.GetUID() { 231 owned = append(owned, history[i]) 232 } 233 234 } 235 return owned, err 236} 237 238func (rh *realHistory) CreateControllerRevision(parent metav1.Object, revision *apps.ControllerRevision, collisionCount *int32) (*apps.ControllerRevision, error) { 239 if collisionCount == nil { 240 return nil, fmt.Errorf("collisionCount should not be nil") 241 } 242 243 // Clone the input 244 clone := revision.DeepCopy() 245 246 // Continue to attempt to create the revision updating the name with a new hash on each iteration 247 for { 248 hash := HashControllerRevision(revision, collisionCount) 249 // Update the revisions name 250 clone.Name = ControllerRevisionName(parent.GetName(), hash) 251 ns := parent.GetNamespace() 252 created, err := rh.client.AppsV1().ControllerRevisions(ns).Create(context.TODO(), clone, metav1.CreateOptions{}) 253 if errors.IsAlreadyExists(err) { 254 exists, err := rh.client.AppsV1().ControllerRevisions(ns).Get(context.TODO(), clone.Name, metav1.GetOptions{}) 255 if err != nil { 256 return nil, err 257 } 258 if bytes.Equal(exists.Data.Raw, clone.Data.Raw) { 259 return exists, nil 260 } 261 *collisionCount++ 262 continue 263 } 264 return created, err 265 } 266} 267 268func (rh *realHistory) UpdateControllerRevision(revision *apps.ControllerRevision, newRevision int64) (*apps.ControllerRevision, error) { 269 clone := revision.DeepCopy() 270 err := retry.RetryOnConflict(retry.DefaultBackoff, func() error { 271 if clone.Revision == newRevision { 272 return nil 273 } 274 clone.Revision = newRevision 275 updated, updateErr := rh.client.AppsV1().ControllerRevisions(clone.Namespace).Update(context.TODO(), clone, metav1.UpdateOptions{}) 276 if updateErr == nil { 277 return nil 278 } 279 if updated != nil { 280 clone = updated 281 } 282 if updated, err := rh.lister.ControllerRevisions(clone.Namespace).Get(clone.Name); err == nil { 283 // make a copy so we don't mutate the shared cache 284 clone = updated.DeepCopy() 285 } 286 return updateErr 287 }) 288 return clone, err 289} 290 291func (rh *realHistory) DeleteControllerRevision(revision *apps.ControllerRevision) error { 292 return rh.client.AppsV1().ControllerRevisions(revision.Namespace).Delete(context.TODO(), revision.Name, metav1.DeleteOptions{}) 293} 294 295type objectForPatch struct { 296 Metadata objectMetaForPatch `json:"metadata"` 297} 298 299// objectMetaForPatch define object meta struct for patch operation 300type objectMetaForPatch struct { 301 OwnerReferences []metav1.OwnerReference `json:"ownerReferences"` 302 UID types.UID `json:"uid"` 303} 304 305func (rh *realHistory) AdoptControllerRevision(parent metav1.Object, parentKind schema.GroupVersionKind, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) { 306 blockOwnerDeletion := true 307 isController := true 308 // Return an error if the revision is not orphan 309 if owner := metav1.GetControllerOfNoCopy(revision); owner != nil { 310 return nil, fmt.Errorf("attempt to adopt revision owned by %v", owner) 311 } 312 addControllerPatch := objectForPatch{ 313 Metadata: objectMetaForPatch{ 314 UID: revision.UID, 315 OwnerReferences: []metav1.OwnerReference{{ 316 APIVersion: parentKind.GroupVersion().String(), 317 Kind: parentKind.Kind, 318 Name: parent.GetName(), 319 UID: parent.GetUID(), 320 Controller: &isController, 321 BlockOwnerDeletion: &blockOwnerDeletion, 322 }}, 323 }, 324 } 325 patchBytes, err := json.Marshal(&addControllerPatch) 326 if err != nil { 327 return nil, err 328 } 329 // Use strategic merge patch to add an owner reference indicating a controller ref 330 return rh.client.AppsV1().ControllerRevisions(parent.GetNamespace()).Patch(context.TODO(), revision.GetName(), 331 types.StrategicMergePatchType, patchBytes, metav1.PatchOptions{}) 332} 333 334func (rh *realHistory) ReleaseControllerRevision(parent metav1.Object, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) { 335 // Use strategic merge patch to add an owner reference indicating a controller ref 336 released, err := rh.client.AppsV1().ControllerRevisions(revision.GetNamespace()).Patch(context.TODO(), revision.GetName(), 337 types.StrategicMergePatchType, 338 []byte(fmt.Sprintf(`{"metadata":{"ownerReferences":[{"$patch":"delete","uid":"%s"}],"uid":"%s"}}`, parent.GetUID(), revision.UID)), metav1.PatchOptions{}) 339 340 if err != nil { 341 if errors.IsNotFound(err) { 342 // We ignore deleted revisions 343 return nil, nil 344 } 345 if errors.IsInvalid(err) { 346 // We ignore cases where the parent no longer owns the revision or where the revision has no 347 // owner. 348 return nil, nil 349 } 350 } 351 return released, err 352} 353 354type fakeHistory struct { 355 indexer cache.Indexer 356 lister appslisters.ControllerRevisionLister 357} 358 359func (fh *fakeHistory) ListControllerRevisions(parent metav1.Object, selector labels.Selector) ([]*apps.ControllerRevision, error) { 360 history, err := fh.lister.ControllerRevisions(parent.GetNamespace()).List(selector) 361 if err != nil { 362 return nil, err 363 } 364 365 var owned []*apps.ControllerRevision 366 for i := range history { 367 ref := metav1.GetControllerOf(history[i]) 368 if ref == nil || ref.UID == parent.GetUID() { 369 owned = append(owned, history[i]) 370 } 371 372 } 373 return owned, err 374} 375 376func (fh *fakeHistory) addRevision(revision *apps.ControllerRevision) (*apps.ControllerRevision, error) { 377 key, err := cache.DeletionHandlingMetaNamespaceKeyFunc(revision) 378 if err != nil { 379 return nil, err 380 } 381 obj, found, err := fh.indexer.GetByKey(key) 382 if err != nil { 383 return nil, err 384 } 385 if found { 386 foundRevision := obj.(*apps.ControllerRevision) 387 return foundRevision, errors.NewAlreadyExists(apps.Resource("controllerrevision"), revision.Name) 388 } 389 return revision, fh.indexer.Update(revision) 390} 391 392func (fh *fakeHistory) CreateControllerRevision(parent metav1.Object, revision *apps.ControllerRevision, collisionCount *int32) (*apps.ControllerRevision, error) { 393 if collisionCount == nil { 394 return nil, fmt.Errorf("collisionCount should not be nil") 395 } 396 397 // Clone the input 398 clone := revision.DeepCopy() 399 clone.Namespace = parent.GetNamespace() 400 401 // Continue to attempt to create the revision updating the name with a new hash on each iteration 402 for { 403 hash := HashControllerRevision(revision, collisionCount) 404 // Update the revisions name and labels 405 clone.Name = ControllerRevisionName(parent.GetName(), hash) 406 created, err := fh.addRevision(clone) 407 if errors.IsAlreadyExists(err) { 408 *collisionCount++ 409 continue 410 } 411 return created, err 412 } 413} 414 415func (fh *fakeHistory) DeleteControllerRevision(revision *apps.ControllerRevision) error { 416 key, err := cache.DeletionHandlingMetaNamespaceKeyFunc(revision) 417 if err != nil { 418 return err 419 } 420 obj, found, err := fh.indexer.GetByKey(key) 421 if err != nil { 422 return err 423 } 424 if !found { 425 return errors.NewNotFound(apps.Resource("controllerrevisions"), revision.Name) 426 } 427 return fh.indexer.Delete(obj) 428} 429 430func (fh *fakeHistory) UpdateControllerRevision(revision *apps.ControllerRevision, newRevision int64) (*apps.ControllerRevision, error) { 431 clone := revision.DeepCopy() 432 clone.Revision = newRevision 433 return clone, fh.indexer.Update(clone) 434} 435 436func (fh *fakeHistory) AdoptControllerRevision(parent metav1.Object, parentKind schema.GroupVersionKind, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) { 437 if owner := metav1.GetControllerOf(revision); owner != nil { 438 return nil, fmt.Errorf("attempt to adopt revision owned by %v", owner) 439 } 440 key, err := cache.DeletionHandlingMetaNamespaceKeyFunc(revision) 441 if err != nil { 442 return nil, err 443 } 444 _, found, err := fh.indexer.GetByKey(key) 445 if err != nil { 446 return nil, err 447 } 448 if !found { 449 return nil, errors.NewNotFound(apps.Resource("controllerrevisions"), revision.Name) 450 } 451 clone := revision.DeepCopy() 452 clone.OwnerReferences = append(clone.OwnerReferences, *metav1.NewControllerRef(parent, parentKind)) 453 return clone, fh.indexer.Update(clone) 454} 455 456func (fh *fakeHistory) ReleaseControllerRevision(parent metav1.Object, revision *apps.ControllerRevision) (*apps.ControllerRevision, error) { 457 key, err := cache.DeletionHandlingMetaNamespaceKeyFunc(revision) 458 if err != nil { 459 return nil, err 460 } 461 _, found, err := fh.indexer.GetByKey(key) 462 if err != nil { 463 return nil, err 464 } 465 if !found { 466 return nil, nil 467 } 468 clone := revision.DeepCopy() 469 refs := clone.OwnerReferences 470 clone.OwnerReferences = nil 471 for i := range refs { 472 if refs[i].UID != parent.GetUID() { 473 clone.OwnerReferences = append(clone.OwnerReferences, refs[i]) 474 } 475 } 476 return clone, fh.indexer.Update(clone) 477} 478