Range() returns inconsistent results due to race condition with Set/Touch

[jahough]

Range returns inconsistent results due to race condition with Set/Touch

Summary

Range can skip items when called concurrently with Set or Touch, resulting in an incomplete iteration over cache entries. The number of items visited varies between calls even when no entries are being added or expiring.

How

Range iterates the internal LRU linked list front-to-back, but releases the mutex between each iteration step (cache.go#L598):

for item := c.items.lru.Front(); ...; item = item.Next() {
    expired := i.isExpiredUnsafe()
    c.items.mu.RUnlock()  // lock released here                                                                                                                                                                                                  
    if !expired && !fn(i) {                                                                                                                                                                                                                      
        return                                                                                                                                                                                                                                   
    }                                                                                                                                                                                                                                            
    c.items.mu.RLock()    // re-acquired here
}

While the lock is released, Set() and Touch are free to acquire the write lock.
Both of these internally call get() which ultimately invokes c.items.lru.MoveToFront(elem) (https://github.com/jellydator/ttlcache/blob/v3.4.0/cache.go#L231).
This moves elements that are ahead of the iterator to the front of the list (behind the iterator's current position), causing Range() to skip them.

Steps to Reproduce

Invoke Set() or Touch() within the provided function to Range() so that we can simulate concurrent behaviors in between lock releases:

func main() {
	c := ttlcache.New[string, int](
		ttlcache.WithTTL[string, int](1 * time.Hour),
	)

	c.Set("key1", 1, ttlcache.DefaultTTL)
	c.Set("key2", 2, ttlcache.DefaultTTL)
	c.Set("key3", 3, ttlcache.DefaultTTL)
	c.Set("key4", 4, ttlcache.DefaultTTL)

	c.Range(func(item *ttlcache.Item[string, int]) bool {
		fmt.Println(item.Key())

		if item.Value() == 4 {
			c.Set("key3", 3, ttlcache.DefaultTTL)
		}

		return true
	})
}

Yields the following output:

key4
key2
key1

key3 is incorrectly omitted from the output.

Version

jellydator/ttlcache/v3 v3.4.0