🐛 [Bug]: cache middleware: runtime error: index out of range [0] with length 0

[canbusio]

Bug Description

Use cache middleware to cache home page "/". Use CacheInvalidator to skip cache, got error: runtime error: index out of range [0] with length 0.

How to Reproduce

1.use cache middleware to cache home page "/". 2.do not visit "/" in browser, so there will not be any cache of it. 3.visit "/login" page to login, then CacheInvalidator would return true now. 4.visit "/". 5.got error.

Expected Behavior

When restart the program, not every page is cached, when user logged in visit no cache page, it should be open normal.

Fiber Version

v3.0.0-beta.3

Code Snippet (optional)

var WebCache_Home = cache.New(cache.Config{
    CacheInvalidator: auth.ValidateLogin,
    Expiration: 10 * time.Minute,
    KeyGenerator: func(c fiber.Ctx) string {
        cacheKey := "homeLogout"
        if auth.ValidateLogin(c){
            cacheKey = "homeLogin"
        }
        return cacheKey
    },
    StoreResponseHeaders: true,
    MaxBytes:             1 * 1024 * 1024,
})

app.Use("/:p<maxLen(0)>?", cache.WebCache_Home)
app.Get("/:p<maxLen(0)>?", user.HomeHandler)

Checklist:

• [X] I agree to follow Fiber's Code of Conduct.
• [X] I have checked for existing issues that describe my problem prior to opening this one.
• [X] I understand that improperly formatted bug reports may be closed without explanation.

[welcome[bot]]

Thanks for opening your first issue here! 🎉 Be sure to follow the issue template! If you need help or want to chat with us, join us on Discord https://gofiber.io/discord

[gaby]

@canbusio We need an example to replicate this, from your snippet we can't tell what is auth.ValidateLogin. is it using anything from the context to valdiate?

Cam yo share the runtime error logs

[ReneWerner87]

Does it make sense to have a maxLen 0 rule in the route?

[canbusio]

@canbusio We need an example to replicate this, from your snippet we can't tell what is auth.ValidateLogin. is it using anything from the context to valdiate?

Cam yo share the runtime error logs

Hi~

I tried again with auth.ValidateLogin codes bellow:

func ValidateLogin(c fiber.Ctx) bool {
    return true
}

And this "index out of range [0] with length 0" error can be reproduced.

By the way, when I remove "CacheInvalidator: auth.ValidateLogin", it works fine.

The full run time error log is like this:

panic: runtime error: index out of range [0] with length 0

goroutine 55 [running]:
github.com/gofiber/fiber/v3/middleware/cache.(*indexedHeap).remove(0xc0002e2db0?, 0xe?)
        /home//go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/middleware/cache/heap.go:86 +0xb8
github.com/gofiber/fiber/v3/middleware/cache.New.func4({0xb6fb78, 0xc00023a008})
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/middleware/cache/cache.go:129 +0x348
github.com/gofiber/fiber/v3.(*App).next(0xc000250008, 0xc00023a008)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/router.go:188 +0x1c2
github.com/gofiber/fiber/v3.(*DefaultCtx).Next(0xc0002100c0?)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/ctx.go:1036 +0x79
github.com/gofiber/fiber/v3/middleware/limiter.FixedWindow.New.func1({0xb6fb78, 0xc00023a008})
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/middleware/limiter/limiter_fixed.go:83 +0x1a7
github.com/gofiber/fiber/v3.(*App).next(0xc000250008, 0xc00023a008)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/router.go:188 +0x1c2
github.com/gofiber/fiber/v3.(*DefaultCtx).Next(0xc0000ee2a8?)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/ctx.go:1036 +0x79
flawer_leaf/internal/route.Setup.func1({0xb6fb78, 0xc00023a008})
        /home/user/Go/FlawerNext/Flawer_Leaf/internal/route/route.go:21 +0x24
github.com/gofiber/fiber/v3.(*App).next(0xc000250008, 0xc00023a008)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/router.go:188 +0x1c2
github.com/gofiber/fiber/v3.(*App).requestHandler(0xc000250008, 0x4ac7af?)
        /home/user/go/pkg/mod/github.com/gofiber/fiber/v3@v3.0.0-beta.3/router.go:236 +0x2f8
github.com/valyala/fasthttp.(*Server).serveConn(0xc0000f6248, {0xb69318, 0xc0002077c8})
        /home/user/go/pkg/mod/github.com/valyala/fasthttp@v1.55.0/server.go:2379 +0xe70
github.com/valyala/fasthttp.(*workerPool).workerFunc(0xc000144140, 0xc0002920e0)
        /home/user/go/pkg/mod/github.com/valyala/fasthttp@v1.55.0/workerpool.go:224 +0xa4
github.com/valyala/fasthttp.(*workerPool).getCh.func1()
        /home/user/go/pkg/mod/github.com/valyala/fasthttp@v1.55.0/workerpool.go:196 +0x32
created by github.com/valyala/fasthttp.(*workerPool).getCh in goroutine 83
        /home/user/go/pkg/mod/github.com/valyala/fasthttp@v1.55.0/workerpool.go:195 +0x190
exit status 2

[canbusio]

@ReneWerner87 cache config for home page only, if no maxLen 0, other page like /c/12345 would be mathed.

[ReneWerner87]

But you can use

app.All("/", cache.WebCache_Home)

with the same effect

[gaby]

@ReneWerner87 The heap in cache is using indexes without any checks:

https://github.com/gofiber/fiber/blob/main/middleware/cache/heap.go#L86

[ReneWerner87]

Ok, then we need an adjustment

[gaby]

Should be something like this?

func (h *indexedHeap) remove(idx int) (string, uint, error)
    if idx < 0 || idx >= len(h.indices) {
        return "", 0, ErrIndexOut0fRange
    }
    return h.removeInternal(h.indices[idx])
}

cache.go would need to be updated too. I'm still not sure why idx is not in indixes for this case.

[brunodmartins]

Can I work on this issue?

[gaby]

@brunodmartins Sure, basically the implementation of heap.go needs some updates. A lot of the functions are not checking idx first before making the call. There's also a concurrency issue. The remove function should look like this:

// Remove entry by index
func (h *indexedHeap) remove(idx int) (string, uint) {
    h.mu.Lock()
    defer h.mu.Unlock()
    if idx < 0 || idx >= len(h.indices) {
        return "", 0 // Return empty values if the index is out of bounds
    }
    return h.removeInternal(h.indices[idx])
}

This requires also updating the actual cache middleware, to take into account that 0 being returned. But this same issue is also present in other functions like removeinternal, etc.

[brunodmartins]

Thanks! I will review the code now! Any doubts I will return here =)

[gaby]

@brunodmartins This is a draft I have for heap.go, I never got into the changes needed to the cache middleware itself.

package cache

import (
    "container/heap"
    "sync"
)

type heapEntry struct {
    key   string
    exp   uint64
    bytes uint
    idx   int
}

// indexedHeap is a regular min-heap that allows finding
// elements in constant time. It does so by handing out special indices
// and tracking entry movement.
//
// indexdedHeap is used for quickly finding entries with the lowest
// expiration timestamp and deleting arbitrary entries.
type indexedHeap struct {
    // Slice the heap is built on
    entries []heapEntry
    // Mapping "index" to position in heap slice
    indices []int
    // Max index handed out
    maxidx int
    // Mutex for concurrent access
    mu sync.Mutex
}

func (h indexedHeap) Len() int {
    return len(h.entries)
}

func (h indexedHeap) Less(i, j int) bool {
    return h.entries[i].exp < h.entries[j].exp
}

func (h indexedHeap) Swap(i, j int) {
    h.entries[i], h.entries[j] = h.entries[j], h.entries[i]
    h.indices[h.entries[i].idx] = i
    h.indices[h.entries[j].idx] = j
}

func (h *indexedHeap) Push(x any) {
    h.mu.Lock()
    defer h.mu.Unlock()
    h.pushInternal(x.(heapEntry)) //nolint:forcetypeassert // Forced type assertion required to implement the heap.Interface interface
}

func (h *indexedHeap) Pop() any {
    h.mu.Lock()
    defer h.mu.Unlock()
    return h.popInternal()
}

func (h *indexedHeap) popInternal() any {
    n := len(h.entries)
    if n == 0 {
        return nil
    }
    entry := h.entries[n-1]
    h.entries = h.entries[:n-1]
    return entry
}

func (h *indexedHeap) pushInternal(entry heapEntry) {
    h.indices[entry.idx] = len(h.entries)
    h.entries = append(h.entries, entry)
}

// Returns index to track entry
func (h *indexedHeap) put(key string, exp uint64, bytes uint) int {
    h.mu.Lock()
    defer h.mu.Unlock()
    idx := 0
    if len(h.entries) < h.maxidx {
        // Steal index from previously removed entry
        // capacity > size is guaranteed
        n := len(h.entries)
        idx = h.entries[:n+1][n].idx
    } else {
        idx = h.maxidx
        h.maxidx++
        h.indices = append(h.indices, idx)
    }
    // Push manually to avoid allocation
    h.pushInternal(heapEntry{
        key: key, exp: exp, idx: idx, bytes: bytes,
    })
    heap.Fix(h, h.Len()-1)
    return idx
}

func (h *indexedHeap) removeInternal(realIdx int) (string, uint) {
    h.mu.Lock()
    defer h.mu.Unlock()
    if realIdx < 0 || realIdx >= len(h.entries) {
        return "", 0 // Return empty values if the index is out of bounds
    }
    x := heap.Remove(h, realIdx).(heapEntry) //nolint:forcetypeassert,errcheck // Forced type assertion required to implement the heap.Interface interface
    return x.key, x.bytes
}

// Remove entry by index
func (h *indexedHeap) remove(idx int) (string, uint) {
    h.mu.Lock()
    defer h.mu.Unlock()
    if idx < 0 || idx >= len(h.indices) {
        return "", 0 // Return empty values if the index is out of bounds
    }
    return h.removeInternal(h.indices[idx])
}

// Remove entry with lowest expiration time
func (h *indexedHeap) removeFirst() (string, uint) {
    h.mu.Lock()
    defer h.mu.Unlock()
    if len(h.entries) == 0 {
        return "", 0 // Return empty values if there are no entries
    }
    return h.removeInternal(0)
}

[brunodmartins]

@gaby I have found why the idx does not exist. The main reason is that on the given scenario by @canbusio , the cache always expire, due to the function ValidateLogin return always true. Removing it from the code, the error does not occur. Despite that, I investigated further and found out that, before we validate if the cache is expired, we are not really checking if the cache entry really exist.

cache.go

        // Get entry from pool
        e := manager.get(key)

        // Lock entry
        mux.Lock()

        // Get timestamp
        ts := atomic.LoadUint64(&timestamp)

        // Invalidate cache if requested
        if cfg.CacheInvalidator != nil && cfg.CacheInvalidator(c) && e != nil {
            e.exp = ts - 1
        }

        // Check if entry is expired
        if e.exp != 0 && ts >= e.exp {
            deleteKey(key)
            if cfg.MaxBytes > 0 {
                _, size := heap.remove(e.heapidx)
                storedBytes -= size
            }
        }

The call to manager.get instead of returning a nil in case not founding the entry, returns a new instance, making the rest of the previous call operate as if a real cache entry exist.

manager.go

    if it, _ = m.memory.Get(key).(*item); it == nil { //nolint:errcheck // We store nothing else in the pool
        it = m.acquire()
        return it
    }

To fix the issue, I changed the manager.get to return a nil in case the entry is not found, and modified the cache behavior to skip invalidation in case of a nil is returned. I will open a draft PR =)

[gaby]

@brunodmartins That's probably one issue, but the heap.go also has concurrency issues.