diff options
author | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-27 21:52:36 -0600 |
---|---|---|
committer | Luke Shumaker <lukeshu@lukeshu.com> | 2023-03-27 21:52:36 -0600 |
commit | 0b10349e804d72d6123297228ae450cf85b5fd8d (patch) | |
tree | bebe8ad8911644ae0ed2b09ec920f80a02a8b27f | |
parent | c5db0982b631418b2383f4ad84b3b6d537e75219 (diff) |
more feedback
-rw-r--r-- | lib/caching/arcache.go | 62 |
1 files changed, 37 insertions, 25 deletions
diff --git a/lib/caching/arcache.go b/lib/caching/arcache.go index 5eca93c..39bf794 100644 --- a/lib/caching/arcache.go +++ b/lib/caching/arcache.go @@ -226,12 +226,14 @@ type arCache[K comparable, V any] struct { // Before getting to the meaty ARC stuff, let's get some // boring/simple synchronization/blocking primitives out of the way: -// 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 an entry that is either -// unused or evictable. We'll give waiters FIFO priority. +// waitForEval 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 *arCache[K, V]) waitForAvail() { if !(c.recentLive.IsEmpty() && c.frequentLive.IsEmpty() && c.unusedLive.IsEmpty()) { + // There is already an available `arcLiveEntry` that + // we can either use or evict. return } ch := make(chan struct{}) @@ -241,7 +243,7 @@ func (c *arCache[K, V]) waitForAvail() { c.mu.Lock() } -// notifyAvail is called when an entry becomes unused or evictable, +// notifyAvail is called when an entry gets unpinned ("Release()d"), // and wakes up the highest-priority .waitForAvail() waiter (if there // is one). func (c *arCache[K, V]) notifyAvail() { @@ -280,9 +282,9 @@ func (c *arCache[K, V]) notifyOfDel(entry *LinkedListEntry[arcLiveEntry[K, V]]) // // from DBL(2c): // -// - 0 ≤ |L₁|+|L₂| ≤ 2c -// - 0 ≤ |L₁| ≤ c -// - 0 ≤ |L₂| ≤ 2c +// • 0 ≤ |L₁|+|L₂| ≤ 2c +// • 0 ≤ |L₁| ≤ c +// • 0 ≤ |L₂| ≤ 2c // // from Π(c): // @@ -291,22 +293,27 @@ func (c *arCache[K, V]) notifyOfDel(entry *LinkedListEntry[arcLiveEntry[K, V]]) // deletion, this implementation doesn't actually belong to // Π(c). // -// - A.1: The lists T₁, B₁, T₂, and B₂ are all mutually +// • A.1: The lists T₁, B₁, T₂, and B₂ are all mutually // disjoint. -// - (not true) A.2: If |L₁|+|L₂| < c, then both B₁ and B₂ are +// • (not true) A.2: If |L₁|+|L₂| < c, then both B₁ and B₂ are // empty. But supporting "delete" invalidates this! -// - (not true) A.3: If |L₁|+|L₂| ≥ c, then |T₁|+|T₂| = c. But +// • (not true) A.3: If |L₁|+|L₂| ≥ c, then |T₁|+|T₂| = c. But // supporting "delete" invalidates this! -// - A.4(a): Either (T₁ or B₁ is empty), or (the LRU page in T₁ +// • A.4(a): Either (T₁ or B₁ is empty), or (the LRU page in T₁ // is more recent than the MRU page in B₁). -// - A.4(b): Either (T₂ or B₂ is empty), or (the LRU page in T₂ +// • A.4(b): Either (T₂ or B₂ is empty), or (the LRU page in T₂ // is more recent than the MRU page in B₂). -// - A.5: |T₁∪T₂| is the set of pages that would be maintained +// • A.5: |T₁∪T₂| is the set of pages that would be maintained // by the cache policy π(c). // +// The algorithm presented in the paper relies on A.2 and A.3 in +// order to be correct; the algorithm had to be adjusted in +// order to behave properly without relying on on those two +// invariants. +// // from FRC(p, c): // -// - 0 ≤ p ≤ c +// • 0 ≤ p ≤ c // // OK, at the beginning I said that ARC(c) is most reasonably // understood in terms of DBL(2c); to that end, we'll have two @@ -315,9 +322,11 @@ func (c *arCache[K, V]) notifyOfDel(entry *LinkedListEntry[arcLiveEntry[K, V]]) // and the "arcReplace" policy that is used when ARC(c) has a // cache-miss but DBL(2c) wouldn't have (and within dblReplace). -// dblReplace is the DBL(2c) replacement policy. It returns an entry -// that is not in any list, that the main algorithm should store the -// value in to and place in the appropriate list. +// dblReplace is the DBL(2c) replacement policy. +// +// It returns an entry that is not in any list (c.recentPinned, +// c.recentLive, c.frequentPinned, c.frequentLive, or c.unusedLive), +// and is ready to be stored in to a list by the caller. func (c *arCache[K, V]) dblReplace() *LinkedListEntry[arcLiveEntry[K, V]] { c.waitForAvail() @@ -386,15 +395,18 @@ func (c *arCache[K, V]) dblReplace() *LinkedListEntry[arcLiveEntry[K, V]] { } } -// arcReplace is the ARC(c) replacement policy. It returns an entry -// that is not in any list, that the main algorithm should store the -// value in to and place in the appropriate list. +// arcReplace is the ARC(c) replacement policy. +// +// It returns an entry that is not in any list (c.recentPinned, +// c.recentLive, c.frequentPinned, c.frequentLive, or c.unusedLive), +// and is ready to be stored in to a list by the caller. // -// `ghostEntry` is the entry that the eviction (if one is performed) -// should be recorded in to. It is still present in its old list (in -// case an eviction is not performed). +// The `ghostEntry` argument is the entry that the eviction (if one is +// performed) should be recorded in to. It is still present in its +// old list (in case an eviction is not performed). // -// `arbitrary` is arbitrary, see the quote about it below. +// The `arbitrary` argument is arbitrary, see the quote about it +// below. func (c *arCache[K, V]) arcReplace(ghostEntry *LinkedListEntry[arcGhostEntry[K]], arbitrary bool) *LinkedListEntry[arcLiveEntry[K, V]] { c.waitForAvail() |