Repository: allegro/bigcache
Pull request #266 (2021-02-11 21:37:40)

The size encoded in a entry header contains the header it self.
As #253 has pointed out, it is impossible to create an entry of arbitrary size in the byte queue. Basically, the problem is that at the points where the header gets larger, one number is skipped. This can lead to errors in the new allocation of a byte queue.

To solve this, the header size is included in the number that is encoded. This allows creating entries with arbitrary dimensions. For example, we have 127 bytes (1 header, 126 data), 128bytes (2 header, 126 data), and 129 bytes(2 header, 127 data).

As a benefit, we can reduce some calculations, and the code gets more straightforward. 
The only downside is that the maximum entry size reduces from `4294967296` to `4294967291` bytes. In my belief, nothing too dramatic that gets in v3 with uint64, even a more minor problem. 

Fabianexe: @KaixuanYu @janisz 
user3415653: Any news here? Sometimes we get this error, so a fix would be nice.
janisz: @Fabianexe Could you rebase?
@cristaloleg Could you take a look?
panmari: Anything else needed here? I'd love to see this merged.
panmari: On HEAD, I'm still seeing the error `panic: runtime error: index out of range [7] with length 0` with the trace 

```
encoding/binary.littleEndian.Uint64(...)
encoding/binary/binary.go:77
bigcache/bigcache.readTimestampFromEntry(...)
bigcache/encoding.go:58
bigcache/bigcache.(*cacheShard).onEvict(0xc008d6e008?, {0xc27fe50e69?, 0x1c6b0668dbacaecc?, 0x0?}, 0x5593c1f7d065?, 0xc031bc5888?)
bigcache/shard.go:271 +0x65
bigcache/bigcache.(*cacheShard).set(0xc008d6e000, {0xc0510a08a0, 0x25}, 0x1c6b0668dbacaecc, {0x0, 0x0, 0x25?})
bigcache/shard.go:134 +0x197
bigcache/bigcache.(*BigCache).Set(0xc002a149c0, {0xc0510a08a0, 0x25}, {0x0, 0x0, 0x0})
```

What's blocking here? Do you want me to do some more evaluation before merging?
codecov-commenter: # [Codecov](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) Report
> Merging [#266](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (866d8e7) into [master](https://codecov.io/gh/allegro/bigcache/commit/0c7635518190a7d4053a104bb329b98837727eeb?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) (0c76355) will **increase** coverage by `0.77%`.
> The diff coverage is `76.00%`.

[![Impacted file tree graph](https://codecov.io/gh/allegro/bigcache/pull/266/graphs/tree.svg?width=650&height=150&src=pr&token=NRx0gXD6he&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)

```diff
@@            Coverage Diff             @@
##           master     #266      +/-   ##
==========================================
+ Coverage   88.45%   89.22%   +0.77%     
==========================================
  Files          15       15              
  Lines         762      761       -1     
==========================================
+ Hits          674      679       +5     
+ Misses         73       69       -4     
+ Partials       15       13       -2     
```


| [Impacted Files](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None) | Coverage Δ | |
|---|---|---|
| [queue/bytes\_queue.go](https://codecov.io/gh/allegro/bigcache/pull/266/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-cXVldWUvYnl0ZXNfcXVldWUuZ28=) | `92.00% <76.00%> (+1.52%)` | :arrow_up: |
| [shard.go](https://codecov.io/gh/allegro/bigcache/pull/266/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None#diff-c2hhcmQuZ28=) | `88.49% <0.00%> (+1.58%)` | :arrow_up: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None). Last update [0c76355...866d8e7](https://codecov.io/gh/allegro/bigcache/pull/266?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=None).


Patch:
diff --git a/queue/bytes_queue.go b/queue/bytes_queue.go
index b8e0435..3ef0f6d 100644
--- a/queue/bytes_queue.go
+++ b/queue/bytes_queue.go
@@ -38,19 +38,23 @@ type queueError struct {
 	message string
 }
 
-// getUvarintSize returns the number of bytes to encode x in uvarint format
-func getUvarintSize(x uint32) int {
-	if x < 128 {
-		return 1
-	} else if x < 16384 {
-		return 2
-	} else if x < 2097152 {
-		return 3
-	} else if x < 268435456 {
-		return 4
-	} else {
-		return 5
+// getNeededSize returns the number of bytes an entry of length need in the queue
+func getNeededSize(length int) int {
+	var header int
+	switch {
+	case length < 127: // 1<<7-1
+		header = 1
+	case length < 16382: // 1<<14-2
+		header = 2
+	case length < 2097149: // 1<<21 -3
+		header = 3
+	case length < 268435452: // 1<<28 -4
+		header = 4
+	default:
+		header = 5
 	}
+
+	return length + header
 }
 
 // NewBytesQueue initialize new bytes queue.
@@ -82,22 +86,21 @@ func (q *BytesQueue) Reset() {
 // Push copies entry at the end of queue and moves tail pointer. Allocates more space if needed.
 // Returns index for pushed data or error if maximum size queue limit is reached.
 func (q *BytesQueue) Push(data []byte) (int, error) {
-	dataLen := len(data)
-	headerEntrySize := getUvarintSize(uint32(dataLen))
+	neededSize := getNeededSize(len(data))
 
-	if !q.canInsertAfterTail(dataLen + headerEntrySize) {
-		if q.canInsertBeforeHead(dataLen + headerEntrySize) {
+	if !q.canInsertAfterTail(neededSize) {
+		if q.canInsertBeforeHead(neededSize) {
 			q.tail = leftMarginIndex
-		} else if q.capacity+headerEntrySize+dataLen >= q.maxCapacity && q.maxCapacity > 0 {
+		} else if q.capacity+neededSize >= q.maxCapacity && q.maxCapacity > 0 {
 			return -1, &queueError{"Full queue. Maximum size limit reached."}
 		} else {
-			q.allocateAdditionalMemory(dataLen + headerEntrySize)
+			q.allocateAdditionalMemory(neededSize)
 		}
 	}
 
 	index := q.tail
 
-	q.push(data, dataLen)
+	q.push(data, neededSize)
 
 	return index, nil
 }
@@ -120,9 +123,8 @@ func (q *BytesQueue) allocateAdditionalMemory(minimum int) {
 
 		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)
+				// created slice is slightly larger then need but this is fine after only the needed bytes are copied
+				q.push(make([]byte, q.head-q.tail), q.head-q.tail)
 			}
 
 			q.head = leftMarginIndex
@@ -141,7 +143,7 @@ func (q *BytesQueue) push(data []byte, len int) {
 	headerEntrySize := binary.PutUvarint(q.headerBuffer, uint64(len))
 	q.copy(q.headerBuffer, headerEntrySize)
 
-	q.copy(data, len)
+	q.copy(data, len-headerEntrySize)
 
 	if q.tail > q.head {
 		q.rightMargin = q.tail
@@ -159,13 +161,12 @@ func (q *BytesQueue) copy(data []byte, len int) {
 
 // Pop reads the oldest entry from queue and moves head pointer to the next one
 func (q *BytesQueue) Pop() ([]byte, error) {
-	data, headerEntrySize, err := q.peek(q.head)
+	data, blockSize, err := q.peek(q.head)
 	if err != nil {
 		return nil, err
 	}
-	size := len(data)
 
-	q.head += headerEntrySize + size
+	q.head += blockSize
 	q.count--
 
 	if q.head == q.rightMargin {
@@ -238,7 +239,7 @@ func (q *BytesQueue) peek(index int) ([]byte, int, error) {
 	}
 
 	blockSize, n := binary.Uvarint(q.array[index:])
-	return q.array[index+n : index+n+int(blockSize)], n, nil
+	return q.array[index+n : index+int(blockSize)], int(blockSize), nil
 }
 
 // canInsertAfterTail returns true if it's possible to insert an entry of size of need after the tail of the queue


Test patch:
diff --git a/queue/bytes_queue_test.go b/queue/bytes_queue_test.go
index 6518c28..81dd107 100644
--- a/queue/bytes_queue_test.go
+++ b/queue/bytes_queue_test.go
@@ -224,6 +224,31 @@ func TestAllocateAdditionalSpaceForInsufficientFreeFragmentedSpaceWhereTailIsBef
 	assertEqual(t, blob('d', 40), pop(queue))
 }
 
+func TestAllocateAdditionalSpaceForInsufficientFreeFragmentedSpaceWhereTailIsBeforeHead128(t *testing.T) {
+	t.Parallel()
+
+	// given
+	queue := NewBytesQueue(200, 0, false)
+
+	// when
+	queue.Push(blob('a', 30))  //  header + entry + left margin = 32 bytes
+	queue.Push(blob('b', 1))   // 32 + 128 + 1 = 161 bytes
+	queue.Push(blob('b', 125)) // 32 + 128 + 1 = 161 bytes
+	queue.Push(blob('c', 20))  //  160 + 20 + 1 = 182
+	queue.Pop()                // space freed at the beginning
+	queue.Pop()                // free 2 bytes
+	queue.Pop()                // free 126
+	queue.Push(blob('d', 30))  // 31 bytes used at the beginning, tail pointer is before head pointer, now free space is 128 bytes
+	queue.Push(blob('e', 160)) // invoke allocateAdditionalMemory but fill 127 bytes free space (It should be 128 bytes, but 127 are filled, leaving one byte unfilled)
+
+	// then
+	assertEqual(t, 400, queue.Capacity())
+	assertEqual(t, blob('d', 30), pop(queue))
+	assertEqual(t, blob(0, 126), pop(queue))  //126 bytes data with 2bytes header only possible as empty entry
+	assertEqual(t, blob('c', 20), pop(queue)) //The data is not expected
+	assertEqual(t, blob('e', 160), pop(queue))
+}
+
 func TestUnchangedEntriesIndexesAfterAdditionalMemoryAllocationWhereTailIsBeforeHead(t *testing.T) {
 	t.Parallel()