diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-30 10:04:09 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-30 10:04:09 -0600 |
commit | cdc2df19c59965149e11c3a5710458c626ea0668 (patch) | |
tree | 2e0bafd99a433d7271bf42e68ab1b5c1eba99e2b /lib/containers/lrucache.go | |
parent | 0b092a27122fcf19479d6cdeae5f7c9493d9741a (diff) | |
parent | 94aa0ec3e9f7145cdf177ad6f6d3d8b7d5bdbef7 (diff) |
Merge branch 'lukeshu/node-cache'
Diffstat (limited to 'lib/containers/lrucache.go')
-rw-r--r-- | lib/containers/lrucache.go | 36 |
1 files changed, 22 insertions, 14 deletions
diff --git a/lib/containers/lrucache.go b/lib/containers/lrucache.go index d2aff41..5c51435 100644 --- a/lib/containers/lrucache.go +++ b/lib/containers/lrucache.go @@ -60,30 +60,37 @@ type lruCache[K comparable, V any] struct { // Blocking primitives ///////////////////////////////////////////////////////// -// Because of pinning, there might not actually be an available entry -// for us to use/evict. If we need an entry to use or evict, we'll -// call waitForAvail to block until there is en entry that is either -// unused or evictable. We'll give waiters FIFO priority. +// waitForAvail is called before storing something into the cache. +// This is nescessary because if the cache is full and all entries are +// pinned, then we won't have to store the entry until something gets +// unpinned ("Release()d"). func (c *lruCache[K, V]) waitForAvail() { if !(c.unused.IsEmpty() && c.evictable.IsEmpty()) { + // There is already an available `lruEntry` that we + // can either use or evict. return } ch := make(chan struct{}) c.waiters.Store(&LinkedListEntry[chan struct{}]{Value: ch}) c.mu.Unlock() - <-ch - c.mu.Lock() + <-ch // receive the lock from .Release() + if c.unused.IsEmpty() && c.evictable.IsEmpty() { + panic(fmt.Errorf("should not happen: waitForAvail is returning, but nothing is available")) + } } -// notifyAvail is called when an entry becomes unused or evictable, -// and wakes up the highest-priority .waitForAvail() waiter (if there -// is one). -func (c *lruCache[K, V]) notifyAvail() { +// unlockAndNotifyAvail is called when an entry becomes unused or +// evictable, and wakes up the highest-priority .waitForAvail() waiter +// (if there is one). +func (c *lruCache[K, V]) unlockAndNotifyAvail() { waiter := c.waiters.Oldest if waiter == nil { + c.mu.Unlock() return } c.waiters.Delete(waiter) + // We don't actually unlock, we're "transferring" the lock to + // the waiter. close(waiter.Value) } @@ -169,8 +176,8 @@ func (c *lruCache[K, V]) Delete(k K) { c.evictable.Delete(entry) c.unused.Store(entry) - // No need to call c.notifyAvail(); if we were able to delete - // it, it was already available. + // No need to call c.unlockAndNotifyAvail(); if we were able + // to delete it, it was already available. c.mu.Unlock() } @@ -178,7 +185,6 @@ func (c *lruCache[K, V]) Delete(k K) { // Release implements the 'Cache' interface. func (c *lruCache[K, V]) Release(k K) { c.mu.Lock() - defer c.mu.Unlock() entry := c.byName[k] if entry == nil || entry.Value.refs <= 0 { @@ -194,7 +200,9 @@ func (c *lruCache[K, V]) Release(k K) { } else { c.evictable.Store(entry) } - c.notifyAvail() + c.unlockAndNotifyAvail() + } else { + c.mu.Unlock() } } |