Repository: allegro/bigcache
Pull request #251 (2020-10-30 17:38:01)

Fix a bug that obscures the byte queue when it is full and is extended
Hi,
On searching for the reason for the panics in the current version where versions pre 2.2 works well, I think I have found the cause. 
With PR #207 it gets possible that the byte queen is full and `q.tail == q.head`. However, in the `allocateAdditionalMemory` method, the condition for resetting head and tail is `q.tail < q.head`. Thus the tail and head are not changed, and the byte queen is obscured after it. An example that leads to panic in the old logic is shown in the test `TestPushEntryAfterAllocateAdditionMemoryInFull`.

This is a different reason for panics then #236, so I am not sure which of the reported panic ( #226 #234 #235 ) is caused by this bug.

janisz: LGTM

I've tested it with test included in #234 but it does not solve that issues

<details>

```go
package bigcache

import (
	"math/rand"
	"runtime"
	"strconv"
	"testing"
	"time"
)

const (
	entries = 3000
	repeats = 1000
)

var valBig = append(make([]byte, 100*1024), 1)
var valMed = append(make([]byte, 1024), 1)
var valSmall = append(make([]byte, 2), 1)

func getValue() []byte {
	x := rand.Float64()
	if x < 0.7 {
		return valSmall
	} else if x < 0.9 {
		return valMed
	}
	return valBig
}

// https://github.com/allegro/bigcache/issues/234#issuecomment-673895517
func Test_issue_234(t *testing.T) {
	t.Log("Number of entries: ", entries)
	printAllocs(t)
	rand.Seed(1)

	config := Config{
		Shards:             128,
		LifeWindow:         time.Hour,
		CleanWindow:        time.Second,
		MaxEntriesInWindow: entries,
		MaxEntrySize:       1024,
		Verbose:            true,
		HardMaxCacheSize:   128,
		OnRemoveWithReason: func(key string, entry []byte, reason RemoveReason) {
			t.Log("Evicted:", len(entry), " reason: ", reason)
		},
	}

	bigcache, err := NewBigCache(config)
	if err != nil {
		panic(err)
	}
	for i := 0; i < repeats; i++ {
		printAllocs(t)
		for j := 0; j < entries; j++ {
			key := strconv.FormatInt(int64(j), 10)
			err := bigcache.Set(key, getValue())
			if err != nil {
				t.Fatal(err)
			}
		}
	}
}

func printAllocs(t *testing.T) {
	var m runtime.MemStats
	runtime.ReadMemStats(&m)
	t.Logf("Alloc: %6d MB \n", m.Alloc/1e6)
}
```
</details>
Fabianexe: @janisz 
I have relooked at the test that you suggested. 
This is a related but a little different bug.
By reallocating the byte queen, an artificial entry is added to close the gap between the head and tail. This artificial entry could have no content. This is fine for the byte queen, but by calling Pop this entry is published to the shard, and this shard then expects content.
I have pushed a fix for this bug as well. Simple set the minimum size for such entry to 17 (size+timestamp+hash).

A more minimalistic test for the bug from #234 is:

```
package bigcache

import (
	"testing"
	"time"
)

// https://github.com/allegro/bigcache/issues/234#issuecomment-673895517
func Test_issue_234(t *testing.T) {

	config := Config{
		Shards:             1,
		LifeWindow:         time.Hour,
		MaxEntriesInWindow: 900,
		MaxEntrySize:       1024,
		Verbose:            true,
		HardMaxCacheSize:   1,
		OnRemoveWithReason: func(key string, entry []byte, reason RemoveReason) {
			t.Log("Evicted:", len(entry), " reason: ", reason)
		},
	}

	bigcache, _ := NewBigCache(config)
	bigcache.Set("1", make([]byte, 400*1024))
	bigcache.Set("2", make([]byte, 400*1024))
	bigcache.Set("3", make([]byte, 400*1024-1))
	bigcache.Set("4", make([]byte, 100*1024))
	bigcache.Set("5", make([]byte, 400*1024))
}
```
janisz: @mxplusb @cristaloleg Can you look at this? 

Patch:
diff --git a/queue/bytes_queue.go b/queue/bytes_queue.go
index 184c1e8..b8e0435 100644
--- a/queue/bytes_queue.go
+++ b/queue/bytes_queue.go
@@ -8,7 +8,7 @@ import (
 
 const (
 	// Number of bytes to encode 0 in uvarint format
-	minimumHeaderSize = 1
+	minimumHeaderSize = 17 // 1 byte blobsize + timestampSizeInBytes + hashSizeInBytes
 	// Bytes before left margin are not used. Zero index means element does not exist in queue, useful while reading slice from index
 	leftMarginIndex = 1
 )
@@ -118,10 +118,13 @@ func (q *BytesQueue) allocateAdditionalMemory(minimum int) {
 	if leftMarginIndex != q.rightMargin {
 		copy(q.array, oldArray[:q.rightMargin])
 
-		if q.tail < q.head {
-			headerEntrySize := getUvarintSize(uint32(q.head - q.tail))
-			emptyBlobLen := q.head - q.tail - headerEntrySize
-			q.push(make([]byte, emptyBlobLen), emptyBlobLen)
+		if q.tail <= q.head {
+			if q.tail != q.head {
+				headerEntrySize := getUvarintSize(uint32(q.head - q.tail))
+				emptyBlobLen := q.head - q.tail - headerEntrySize
+				q.push(make([]byte, emptyBlobLen), emptyBlobLen)
+			}
+
 			q.head = leftMarginIndex
 			q.tail = q.rightMargin
 		}


Test patch:
diff --git a/queue/bytes_queue_test.go b/queue/bytes_queue_test.go
index 545bf7d..6518c28 100644
--- a/queue/bytes_queue_test.go
+++ b/queue/bytes_queue_test.go
@@ -389,8 +389,6 @@ func TestPushEntryAfterAllocateAdditionMemory(t *testing.T) {
 	queue.Push([]byte("aaa"))
 	queue.Push([]byte("bb"))
 	queue.Pop()
-	queue.Push([]byte("c"))
-	queue.Push([]byte("d"))
 
 	// allocate more memory
 	assertEqual(t, 9, queue.Capacity())
@@ -402,6 +400,30 @@ func TestPushEntryAfterAllocateAdditionMemory(t *testing.T) {
 	noError(t, err)
 }
 
+func TestPushEntryAfterAllocateAdditionMemoryInFull(t *testing.T) {
+	t.Parallel()
+
+	// given
+	queue := NewBytesQueue(9, 40, true)
+
+	// when
+	queue.Push([]byte("aaa"))
+	queue.Push([]byte("bb"))
+	_, err := queue.Pop()
+	noError(t, err)
+
+	queue.Push([]byte("c"))
+	queue.Push([]byte("d"))
+	queue.Push([]byte("e"))
+	_, err = queue.Pop()
+	noError(t, err)
+	_, err = queue.Pop()
+	noError(t, err)
+	queue.Push([]byte("fff"))
+	_, err = queue.Pop()
+	noError(t, err)
+}
+
 func pop(queue *BytesQueue) []byte {
 	entry, err := queue.Pop()
 	if err != nil {