Revert "util/lru: replace container/list with a custom ring implementation"danderson/lru-rollback

Suspected memory leak in the new LRU implementation, and we could not immediately find
the fault.

Updates tailscale/corp#14747

This reverts commit 0909e90890d96dfe2f60b37f6ad3cc8bb80077af.

1 files changed, 38 insertions, 87 deletions

diff --git a/util/lru/lru.go b/util/lru/lru.go
index db77859a4..a6790cd46 100644
--- a/util/lru/lru.go
+++ b/util/lru/lru.go
@@ -4,6 +4,10 @@
 // Package lru contains a typed Least-Recently-Used cache.
 package lru
 
+import (
+	"container/list"
+)
+
 // Cache is container type keyed by K, storing V, optionally evicting the least
 // recently used items if a maximum size is exceeded.
 //
@@ -18,27 +22,14 @@ type Cache[K comparable, V any] struct {
 	// an item is evicted. Zero means no limit.
 	MaxEntries int
 
-	// head is a ring of LRU values. head points to the most recently
-	// used element, head.prev is the least recently used.
-	//
-	// An LRU is technically a simple list rather than a ring, but
-	// implementing it as a ring makes the list manipulation
-	// operations more regular, because the first/last positions in
-	// the list stop being special.
-	//
-	// head is nil when the LRU is empty.
-	head *entry[K, V]
-	// lookup is a map of all the LRU entries contained in
-	// head. lookup and head always contain exactly the same elements;
-	// lookup is just there to allow O(1) lookups of keys.
-	lookup map[K]*entry[K, V]
+	ll *list.List
+	m  map[K]*list.Element // of *entry[K,V]
 }
 
-// entry is an entry of Cache.
+// entry is the element type for the container/list.Element.
 type entry[K comparable, V any] struct {
-	prev, next *entry[K, V]
-	key        K
-	value      V
+	key   K
+	value V
 }
 
 // Set adds or replaces a value to the cache, set or updating its associated
@@ -47,18 +38,19 @@ type entry[K comparable, V any] struct {
 // If MaxEntries is non-zero and the length of the cache is greater
 // after any addition, the least recently used value is evicted.
 func (c *Cache[K, V]) Set(key K, value V) {
-	if c.lookup == nil {
-		c.lookup = make(map[K]*entry[K, V])
+	if c.m == nil {
+		c.m = make(map[K]*list.Element)
+		c.ll = list.New()
 	}
-	if ent, ok := c.lookup[key]; ok {
-		c.moveToFront(ent)
-		ent.value = value
+	if ee, ok := c.m[key]; ok {
+		c.ll.MoveToFront(ee)
+		ee.Value.(*entry[K, V]).value = value
 		return
 	}
-	ent := c.newAtFront(key, value)
-	c.lookup[key] = ent
+	ele := c.ll.PushFront(&entry[K, V]{key, value})
+	c.m[key] = ele
 	if c.MaxEntries != 0 && c.Len() > c.MaxEntries {
-		c.deleteOldest()
+		c.DeleteOldest()
 	}
 }
 
@@ -79,14 +71,14 @@ func (c *Cache[K, V]) Contains(key K) bool {
 	return ok
 }
 
-// GetOk looks up a key's value from the cache, also reporting whether
-// it was present.
+// GetOk looks up a key's value from the cache, also reporting
+// whether it was present.
 //
 // If found, key is moved to the front of the LRU.
 func (c *Cache[K, V]) GetOk(key K) (value V, ok bool) {
-	if ent, hit := c.lookup[key]; hit {
-		c.moveToFront(ent)
-		return ent.value, true
+	if ele, hit := c.m[key]; hit {
+		c.ll.MoveToFront(ele)
+		return ele.Value.(*entry[K, V]).value, true
 	}
 	var zero V
 	return zero, false
@@ -99,8 +91,8 @@ func (c *Cache[K, V]) GetOk(key K) (value V, ok bool) {
 // LRU. This should mostly be used for non-intrusive debug inspection
 // of the cache.
 func (c *Cache[K, V]) PeekOk(key K) (value V, ok bool) {
-	if ent, hit := c.lookup[key]; hit {
-		return ent.value, true
+	if ele, hit := c.m[key]; hit {
+		return ele.Value.(*entry[K, V]).value, true
 	}
 	var zero V
 	return zero, false
@@ -108,66 +100,25 @@ func (c *Cache[K, V]) PeekOk(key K) (value V, ok bool) {
 
 // Delete removes the provided key from the cache if it was present.
 func (c *Cache[K, V]) Delete(key K) {
-	if ent, ok := c.lookup[key]; ok {
-		c.deleteElement(ent)
+	if e, ok := c.m[key]; ok {
+		c.deleteElement(e)
 	}
 }
 
-// DeleteOldest removes the item from the cache that was least
-// recently accessed. It is a no-op if the cache is empty.
+// DeleteOldest removes the item from the cache that was least recently
+// accessed. It is a no-op if the cache is empty.
 func (c *Cache[K, V]) DeleteOldest() {
-	if c.head != nil {
-		c.deleteOldest()
+	if c.ll != nil {
+		if e := c.ll.Back(); e != nil {
+			c.deleteElement(e)
+		}
 	}
 }
 
-// Len returns the number of items in the cache.
-func (c *Cache[K, V]) Len() int { return len(c.lookup) }
-
-// newAtFront creates a new LRU entry using key and value, and inserts
-// it at the front of c.head.
-func (c *Cache[K, V]) newAtFront(key K, value V) *entry[K, V] {
-	ret := &entry[K, V]{key: key, value: value}
-	if c.head == nil {
-		ret.prev = ret
-		ret.next = ret
-	} else {
-		ret.next = c.head
-		ret.prev = c.head.prev
-		c.head.prev.next = ret
-		c.head.prev = ret
-	}
-	c.head = ret
-	return ret
+func (c *Cache[K, V]) deleteElement(e *list.Element) {
+	c.ll.Remove(e)
+	delete(c.m, e.Value.(*entry[K, V]).key)
 }
 
-// moveToFront moves ent, which must be an existing element of the
-// cache, to the front of c.head.
-func (c *Cache[K, V]) moveToFront(ent *entry[K, V]) {
-	if c.head == ent {
-		return
-	}
-	ent.prev.next = ent.next
-	ent.next.prev = ent.prev
-	ent.prev = c.head.prev
-	ent.next = c.head
-	c.head.prev.next = ent
-	c.head.prev = ent
-	c.head = ent
-}
-
-// deleteOldest removes the oldest entry in the cache. It panics if
-// there are no entries in the cache.
-func (c *Cache[K, V]) deleteOldest() { c.deleteElement(c.head.prev) }
-
-// deleteElement removes ent from the cache. ent must be an existing
-// current element of the cache.
-func (c *Cache[K, V]) deleteElement(ent *entry[K, V]) {
-	if ent.next == ent {
-		c.head = nil
-	} else {
-		ent.next.prev = ent.prev
-		ent.prev.next = ent.next
-	}
-	delete(c.lookup, ent.key)
-}
+// Len returns the number of items in the cache.
+func (c *Cache[K, V]) Len() int { return len(c.m) }