Panic when using expirable cache

[kalafut]

When testing with an expirable.LRU, I've seen the crash below. I was using size=100 and expiration=1 second, and the access pattern was all around a single key. The test had a couple concurrent reads per second, and a write of the same key any time there was a cache miss. I'd reliably hit this panic after a few seconds.

panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x0 pc=0x102c011b8]

goroutine 21 [running]:
github.com/hashicorp/golang-lru/v2/internal.(*LruList[...]).Remove(...)
	/Users/kalafut/go/pkg/mod/github.com/hashicorp/golang-lru/v2@v2.0.7/internal/list.go:97
github.com/hashicorp/golang-lru/v2/expirable.(*LRU[...]).removeElement(0x140001c6ff0?, 0x1400020aea8?)
	/Users/kalafut/go/pkg/mod/github.com/hashicorp/golang-lru/v2@v2.0.7/expirable/expirable_lru.go:298 +0x28
github.com/hashicorp/golang-lru/v2/expirable.(*LRU[...]).deleteExpired(0x102fb2c20)
	/Users/kalafut/go/pkg/mod/github.com/hashicorp/golang-lru/v2@v2.0.7/expirable/expirable_lru.go:319 +0x20c
github.com/hashicorp/golang-lru/v2/expirable.NewLRU[...].func1()
	/Users/kalafut/go/pkg/mod/github.com/hashicorp/golang-lru/v2@v2.0.7/expirable/expirable_lru.go:90 +0xa0
created by github.com/hashicorp/golang-lru/v2/expirable.NewLRU[...] in goroutine 1
	/Users/kalafut/go/pkg/mod/github.com/hashicorp/golang-lru/v2@v2.0.7/expirable/expirable_lru.go:82 +0x2b8
exit status 2

[guerinoni]

Can you provide a test that replicates this behaviour? Something like

func TestLRUConcurrencyWithExpiration(t *testing.T) {
	// Create an LRU cache with size=100 and expiration=1 second
	lc := NewLRU[string, string](100, nil, 1*time.Second)

	var wg sync.WaitGroup
	// Number of iterations for the test loop
	const iterations = 1000

	// Function to perform concurrent operations on the LRU
	doConcurrentOps := func(key string) {
		defer wg.Done()

		// Simulate a cache miss and write
		val, ok := lc.Get(key)
		if !ok {
			lc.Add(key, fmt.Sprintf("val-%s", key))
		} else {
			t.Logf("Cache hit for key: %s, value: %s", key, val)
		}

		// Randomly perform other operations
		out, err := rand.Int(rand.Reader, big.NewInt(3))
		if err != nil {
			t.Fatal(err)
		}

		switch out.Int64() {
		case 0:
			lc.Remove(key)
		case 1:
			lc.GetOldest()
		case 2:
			// Perform a random access of another key
			out, err := rand.Int(rand.Reader, big.NewInt(100))
			if err != nil {
				t.Fatal(err)
			}
			randomKey := fmt.Sprintf("key-%d", out.Int64())
			lc.Get(randomKey)
		}
	}

	// Run the test for a single key with concurrent reads/writes
	key := "shared-key"
	start := time.Now()
	for time.Since(start) < 10*time.Second {
		for i := 0; i < iterations; i++ {
			wg.Add(1)
			go doConcurrentOps(key)
		}
		wg.Wait()
	}

	// Verify the cache state
	if size := lc.Len(); size > 100 {
		t.Errorf("Cache size exceeded limit: got %d, want <= 100", size)
	}
}

Or

func TestLRUConcurrencyWithExpiration(t *testing.T) {
	lc := NewLRU[string, string](100, nil, 1*time.Second)

	now := time.Now()
	for time.Since(now) < 10*time.Second {
		go func() { lc.Add(fmt.Sprintf("key-%d", getRand(t)), fmt.Sprintf("val-%d", getRand(t))) }()
		go func() { lc.Get(fmt.Sprintf("key-%d", getRand(t))) }()
		go func() { lc.GetOldest() }()
		go func() { lc.Remove(fmt.Sprintf("key-%d", getRand(t))) }()
	}
}

[kalafut]

Unfortunately I'm struggling to get this to happen now. I've not touched it in 4 months, and my little failing test program is no longer failing. I even downgraded Go. I'll try a few more things.

[guerinoni]

Keep me posted :D thanks

[ohalushchak-exadel]

fiber and other zero-allocation frameworks users - don't forget to copy the contents of your request if you want to use them outside of the request scope.

How to reproduce this panic:

package main

import (
	"fmt"
	"github.com/hashicorp/golang-lru/v2/expirable"
	"time"
	"unsafe"
)

func main() {
	ttl := 1 * time.Second
	lru := expirable.NewLRU(10, func(k string, _ struct{}) { fmt.Println(k + " expired") }, ttl)

	ba := []byte{49} // "1"

	lru.Add(UnsafeString(ba), struct{}{})

	ba[0] = 50 // "2"

	{ // not needed, just for debug
		_, ok := lru.Get("1")
		fmt.Println(ok) // false
		_, ok = lru.Get("2")
		fmt.Println(ok) // true
	}

	time.Sleep(ttl + ttl/5) // while sleeping the key expires and prints "2 expired"

	fmt.Println("i'm ok")

	time.Sleep(ttl * 2) // panics during sleep
}

// borrowed from gofiber
// UnsafeString returns a string pointer without allocation
func UnsafeString(b []byte) string {
	return unsafe.String(unsafe.SliceData(b), len(b))
}