cmd/bpa-operator/vendor/k8s.io/client-go/tools/cache/expiration_cache.go

   1 /*
   2 Copyright 2014 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 cache
  18
  19 import (
  20         "sync"
  21         "time"
  22
  23         "k8s.io/apimachinery/pkg/util/clock"
  24         "k8s.io/klog"
  25 )
  26
  27 // ExpirationCache implements the store interface
  28 //      1. All entries are automatically time stamped on insert
  29 //              a. The key is computed based off the original item/keyFunc
  30 //              b. The value inserted under that key is the timestamped item
  31 //      2. Expiration happens lazily on read based on the expiration policy
  32 //      a. No item can be inserted into the store while we're expiring
  33 //                 *any* item in the cache.
  34 //      3. Time-stamps are stripped off unexpired entries before return
  35 // Note that the ExpirationCache is inherently slower than a normal
  36 // threadSafeStore because it takes a write lock every time it checks if
  37 // an item has expired.
  38 type ExpirationCache struct {
  39         cacheStorage     ThreadSafeStore
  40         keyFunc          KeyFunc
  41         clock            clock.Clock
  42         expirationPolicy ExpirationPolicy
  43         // expirationLock is a write lock used to guarantee that we don't clobber
  44         // newly inserted objects because of a stale expiration timestamp comparison
  45         expirationLock sync.Mutex
  46 }
  47
  48 // ExpirationPolicy dictates when an object expires. Currently only abstracted out
  49 // so unittests don't rely on the system clock.
  50 type ExpirationPolicy interface {
  51         IsExpired(obj *timestampedEntry) bool
  52 }
  53
  54 // TTLPolicy implements a ttl based ExpirationPolicy.
  55 type TTLPolicy struct {
  56         //       >0: Expire entries with an age > ttl
  57         //      <=0: Don't expire any entry
  58         Ttl time.Duration
  59
  60         // Clock used to calculate ttl expiration
  61         Clock clock.Clock
  62 }
  63
  64 // IsExpired returns true if the given object is older than the ttl, or it can't
  65 // determine its age.
  66 func (p *TTLPolicy) IsExpired(obj *timestampedEntry) bool {
  67         return p.Ttl > 0 && p.Clock.Since(obj.timestamp) > p.Ttl
  68 }
  69
  70 // timestampedEntry is the only type allowed in a ExpirationCache.
  71 type timestampedEntry struct {
  72         obj       interface{}
  73         timestamp time.Time
  74 }
  75
  76 // getTimestampedEntry returns the timestampedEntry stored under the given key.
  77 func (c *ExpirationCache) getTimestampedEntry(key string) (*timestampedEntry, bool) {
  78         item, _ := c.cacheStorage.Get(key)
  79         if tsEntry, ok := item.(*timestampedEntry); ok {
  80                 return tsEntry, true
  81         }
  82         return nil, false
  83 }
  84
  85 // getOrExpire retrieves the object from the timestampedEntry if and only if it hasn't
  86 // already expired. It holds a write lock across deletion.
  87 func (c *ExpirationCache) getOrExpire(key string) (interface{}, bool) {
  88         // Prevent all inserts from the time we deem an item as "expired" to when we
  89         // delete it, so an un-expired item doesn't sneak in under the same key, just
  90         // before the Delete.
  91         c.expirationLock.Lock()
  92         defer c.expirationLock.Unlock()
  93         timestampedItem, exists := c.getTimestampedEntry(key)
  94         if !exists {
  95                 return nil, false
  96         }
  97         if c.expirationPolicy.IsExpired(timestampedItem) {
  98                 klog.V(4).Infof("Entry %v: %+v has expired", key, timestampedItem.obj)
  99                 c.cacheStorage.Delete(key)
 100                 return nil, false
 101         }
 102         return timestampedItem.obj, true
 103 }
 104
 105 // GetByKey returns the item stored under the key, or sets exists=false.
 106 func (c *ExpirationCache) GetByKey(key string) (interface{}, bool, error) {
 107         obj, exists := c.getOrExpire(key)
 108         return obj, exists, nil
 109 }
 110
 111 // Get returns unexpired items. It purges the cache of expired items in the
 112 // process.
 113 func (c *ExpirationCache) Get(obj interface{}) (interface{}, bool, error) {
 114         key, err := c.keyFunc(obj)
 115         if err != nil {
 116                 return nil, false, KeyError{obj, err}
 117         }
 118         obj, exists := c.getOrExpire(key)
 119         return obj, exists, nil
 120 }
 121
 122 // List retrieves a list of unexpired items. It purges the cache of expired
 123 // items in the process.
 124 func (c *ExpirationCache) List() []interface{} {
 125         items := c.cacheStorage.List()
 126
 127         list := make([]interface{}, 0, len(items))
 128         for _, item := range items {
 129                 obj := item.(*timestampedEntry).obj
 130                 if key, err := c.keyFunc(obj); err != nil {
 131                         list = append(list, obj)
 132                 } else if obj, exists := c.getOrExpire(key); exists {
 133                         list = append(list, obj)
 134                 }
 135         }
 136         return list
 137 }
 138
 139 // ListKeys returns a list of all keys in the expiration cache.
 140 func (c *ExpirationCache) ListKeys() []string {
 141         return c.cacheStorage.ListKeys()
 142 }
 143
 144 // Add timestamps an item and inserts it into the cache, overwriting entries
 145 // that might exist under the same key.
 146 func (c *ExpirationCache) Add(obj interface{}) error {
 147         c.expirationLock.Lock()
 148         defer c.expirationLock.Unlock()
 149
 150         key, err := c.keyFunc(obj)
 151         if err != nil {
 152                 return KeyError{obj, err}
 153         }
 154         c.cacheStorage.Add(key, &timestampedEntry{obj, c.clock.Now()})
 155         return nil
 156 }
 157
 158 // Update has not been implemented yet for lack of a use case, so this method
 159 // simply calls `Add`. This effectively refreshes the timestamp.
 160 func (c *ExpirationCache) Update(obj interface{}) error {
 161         return c.Add(obj)
 162 }
 163
 164 // Delete removes an item from the cache.
 165 func (c *ExpirationCache) Delete(obj interface{}) error {
 166         c.expirationLock.Lock()
 167         defer c.expirationLock.Unlock()
 168         key, err := c.keyFunc(obj)
 169         if err != nil {
 170                 return KeyError{obj, err}
 171         }
 172         c.cacheStorage.Delete(key)
 173         return nil
 174 }
 175
 176 // Replace will convert all items in the given list to TimestampedEntries
 177 // before attempting the replace operation. The replace operation will
 178 // delete the contents of the ExpirationCache `c`.
 179 func (c *ExpirationCache) Replace(list []interface{}, resourceVersion string) error {
 180         c.expirationLock.Lock()
 181         defer c.expirationLock.Unlock()
 182         items := make(map[string]interface{}, len(list))
 183         ts := c.clock.Now()
 184         for _, item := range list {
 185                 key, err := c.keyFunc(item)
 186                 if err != nil {
 187                         return KeyError{item, err}
 188                 }
 189                 items[key] = &timestampedEntry{item, ts}
 190         }
 191         c.cacheStorage.Replace(items, resourceVersion)
 192         return nil
 193 }
 194
 195 // Resync will touch all objects to put them into the processing queue
 196 func (c *ExpirationCache) Resync() error {
 197         return c.cacheStorage.Resync()
 198 }
 199
 200 // NewTTLStore creates and returns a ExpirationCache with a TTLPolicy
 201 func NewTTLStore(keyFunc KeyFunc, ttl time.Duration) Store {
 202         return &ExpirationCache{
 203                 cacheStorage:     NewThreadSafeStore(Indexers{}, Indices{}),
 204                 keyFunc:          keyFunc,
 205                 clock:            clock.RealClock{},
 206                 expirationPolicy: &TTLPolicy{ttl, clock.RealClock{}},
 207         }
 208 }