allegro / allegro/bigcache

Issue with BytesQueue.

Open
#262 1 comment 1 reaction 0 assignees View on GitHub
bug
Dominant language
Go
Stars
8.2k
Forks
614
Avg merge
5d 12h
Merged PRs (30d)
1

Description

I was going through the `bytes_queue.go` and have found some inconsistencies with the result. Below is a way to reproduce this issue :

There is test in `bytes_queue_test.go` :

```go
func TestUnchangedEntriesIndexesAfterAdditionalMemoryAllocationWhereTailIsBeforeHead(t *testing.T) {
t.Parallel()

// given
queue := NewBytesQueue(100, 0, false)

// when
queue.Push(blob('a', 70)) // header + entry + left margin = 72 bytes
index, _ := queue.Push(blob('b', 10)) // 72 + 10 + 1 = 83 bytes
queue.Pop() // space freed at the beginning
queue.Push(blob('c', 30)) // 31 bytes used at the beginning, tail pointer is before head pointer
newestIndex, _ := queue.Push(blob('d', 40)) // 41 bytes needed but no available in one segment, allocate new memory

// then
assertEqual(t, 200, queue.Capacity())
assertEqual(t, blob('b', 10), get(queue, index))
assertEqual(t, blob('d', 40), get(queue, newestIndex))
}
```

Now lets change this test and bit and add the following line :

```go
func TestUnchangedEntriesIndexesAfterAdditionalMemoryAllocationWhereTailIsBeforeHead(t *testing.T) {
t.Parallel()

// given
queue := NewBytesQueue(100, 0, false)

// when
queue.Push(blob('a', 70)) // header + entry + left margin = 72 bytes
index, _ := queue.Push(blob('b', 10)) // 72 + 10 + 1 = 83 bytes
queue.Pop() // space freed at the beginning
queue.Push(blob('c', 30)) // 31 bytes used at the beginning, tail pointer is before head pointer
newestIndex, _ := queue.Push(blob('d', 40)) // 41 bytes needed but no available in one segment, allocate new memory

// then
assertEqual(t, string(blob('b', 10)), string(pop(queue))) // THIS LINE ADDED
assertEqual(t, 200, queue.Capacity())
assertEqual(t, blob('b', 10), get(queue, index))
assertEqual(t, blob('d', 40), get(queue, newestIndex))
}
```

![Screen Shot 2021-01-17 at 12 04 20 PM](https://user-images.githubusercontent.com/77553735/104854553-230bbd80-58bc-11eb-8a87-15e09754212a.png)

As seen in the above screen shot, the expected string should be `blob('b',10)` and not `blob('c', 30)`.

I have pointed the bug happening in the `allocateAdditionalMemory` :

```go
if leftMarginIndex != q.rightMargin {
copy(q.array, oldArray[:q.rightMargin])

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 // Why are we doing this ?
q.tail = q.rightMargin
}
}
```

Ideally we should not be assigning `q.head = leftMarginIndex` this way you are actually breaking FIFO rules.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.