[Release Blocker] AddHelper Slice index crash

[jarifibrahim]

Originally seen in hypermodeinc/dgraph#5752
The crash is seen on badger commit cddf7c0.
We added support for background compression/encryption in b13b927 which could be the reason for the crash.

panic: runtime error: slice bounds out of range [4172166119:1963281920]
goroutine 25348428 [running]:
github.com/dgraph-io/badger/v2/table.(*Builder).addHelper(0xc01fc8ccc0, 0xc154c416c0, 0x1c, 0x20, 0x440, 0x0, 0xc203897e8d, 0x55, 0xe7, 0x0, ...)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/table/builder.go:222 +0x4a1
github.com/dgraph-io/badger/v2/table.(*Builder).Add(0xc01fc8ccc0, 0xc154c416c0, 0x1c, 0x20, 0x440, 0x0, 0xc203897e8d, 0x55, 0xe7, 0x0, ...)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/table/builder.go:339 +0xe0
github.com/dgraph-io/badger/v2.(*levelsController).compactBuildTables(0xc000322070, 0x2, 0x1c394a0, 0xc02be6c820, 0xc0005d6960, 0xc0005d69c0, 0xc1225a9c40, 0x1, 0x1, 0xc1225a9c48, ...)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/levels.go:607 +0x92a
github.com/dgraph-io/badger/v2.(*levelsController).runCompactDef(0xc000322070, 0x2, 0x1c394a0, 0xc02be6c820, 0xc0005d6960, 0xc0005d69c0, 0xc1225a9c40, 0x1, 0x1, 0xc1225a9c48, ...)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/levels.go:835 +0xc6
github.com/dgraph-io/badger/v2.(*levelsController).doCompact(0xc000322070, 0x2, 0x3ff03c83ae800000, 0x0, 0x0, 0x0, 0x0, 0x0)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/levels.go:904 +0x4b7
github.com/dgraph-io/badger/v2.(*levelsController).runWorker(0xc000322070, 0xc0040d1800)
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/levels.go:365 +0x319
created by github.com/dgraph-io/badger/v2.(*levelsController).startCompact
        /root/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.0.1-rc1.0.20200421062606-cddf7c03451c/levels.go:340 +0x88

The issue isn't reproducible.

[jarifibrahim]

The crash happens because uint32 overflow. The following code is called for every new addition

badger/table/builder.go

Lines 223 to 226 in e013bfd

	if uint32(len(b.buf)) < b.sz+v.EncodedSize() {
	b.grow(v.EncodedSize())
	}
	b.sz += v.Encode(b.buf[b.sz:])

On line 241, we try to increase the size (len: 4172166119) by 50%

badger/table/builder.go

Lines 234 to 244 in e013bfd

	// grow increases the size of b.buf by atleast 50%.
	func (b *Builder) grow(n uint32) {
	l := uint32(len(b.buf))
	if n < l/2 {
	n = l / 2
	}
	b.bufLock.Lock()
	newBuf := make([]byte, l+n)
	copy(newBuf, b.buf)
	b.buf = newBuf
	b.bufLock.Unlock()

So

x := 4172166119
y := uint32(x + x/2)
y -> 1963281920

and the newly allocated slice by the grow function is less than the original slice (b.buf)

The maximum size of uint32 is around 4 GB. So the question is how could there be a single table of more than 4 GB?

[jarifibrahim]

I wasn't able to reproduce this issue after multiple attempts. I'm closing this as non-reproducible.

[minhaj-shakeel]

Github issues have been deprecated.
This issue has been moved to discuss. You can follow the conversation there and also subscribe to updates by changing your notification preferences.