Badger panics with Index Out of Range

whyrusleeping · November 4, 2020, 11:09pm

Really annoying that you guys don’t use github issues anymore. Having to deal with this discourse nonsense is really frustrating. Its not letting me post another issue, So i’m just gonna dump it here and hope someone sees it:

What version of Go are you using ( `go version` )?

1.15.3

What operating system are you using?

Linux

What version of Badger are you using?

github.com/dgraph-io/badger/v2 v2.2007.2

Does this issue reproduce with the latest master?

Likely

Steps to Reproduce the issue

Not a clue.

What Badger options were set?

Defaults, with SyncWrites enabled, Truncate is enabled, and the value log threshold is set to 128.

What did you do?

Used badger

What did you expect to see?

My application not crash

What did you see instead?

My application crashed

Relevant stack trace:

panic: runtime error: slice bounds out of range [:274877907010] with capacity 80

goroutine 4320 [running]:
github.com/dgraph-io/badger/v2/y.CompareKeys(0xc287b90910, 0x400000004a, 0x50, 0xc320ba85a0, 0x4a, 0x4a, 0xffffffffffffffff)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/y/y.go:139 +0x145
github.com/dgraph-io/badger/v2/table.(*Iterator).seekFrom.func1(0x6ce, 0xc000800a00)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/table/iterator.go:244 +0x8c
sort.Search(0x43a5, 0xc025098c78, 0xc025098cc8)
	/usr/lib/go/src/sort/search.go:66 +0x58
github.com/dgraph-io/badger/v2/table.(*Iterator).seekFrom(0xc320ba6840, 0xc320ba85a0, 0x4a, 0x4a, 0x0)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/table/iterator.go:242 +0xfa
github.com/dgraph-io/badger/v2/table.(*Iterator).seek(...)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/table/iterator.go:275
github.com/dgraph-io/badger/v2/table.(*Iterator).Seek(0xc320ba6840, 0xc320ba85a0, 0x4a, 0x4a)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/table/iterator.go:385 +0x94
github.com/dgraph-io/badger/v2.(*levelHandler).get(0xc000800a80, 0xc320ba85a0, 0x4a, 0x4a, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, ...)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/level_handler.go:274 +0x23a
github.com/dgraph-io/badger/v2.(*levelsController).get(0xc0003e20e0, 0xc320ba85a0, 0x4a, 0x4a, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, ...)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/levels.go:1090 +0xe6
github.com/dgraph-io/badger/v2.(*DB).get(0xc001181000, 0xc320ba85a0, 0x4a, 0x4a, 0x0, 0x0, 0x0, 0x0, 0x0, 0x0, ...)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/db.go:693 +0x345
github.com/dgraph-io/badger/v2.(*Txn).Get(0xc320b8ef30, 0xc320ba8550, 0x42, 0x50, 0x42, 0x50, 0x4fb8b4a)
	/home/why/go/pkg/mod/github.com/dgraph-io/badger/v2@v2.2007.2/txn.go:471 +0xf0
github.com/ipfs/go-ds-badger2.(*txn).has(0xc025099150, 0xc320ba8500, 0x42, 0xc025099160, 0x5a12fb, 0x1070c0c74163)
	/home/why/go/pkg/mod/github.com/ipfs/go-ds-badger2@v0.1.1-0.20200708190120-187fc06f714e/datastore.go:526 +0x75
github.com/ipfs/go-ds-badger2.(*Datastore).Has(0xc205f4f260, 0xc320ba8500, 0x42, 0x0, 0x0, 0x0)
	/home/why/go/pkg/mod/github.com/ipfs/go-ds-badger2@v0.1.1-0.20200708190120-187fc06f714e/datastore.go:315 +0x14c

chewxy · November 4, 2020, 11:08pm

Sorry. Discourse/akismet marked you as spam. Which is why you were unable to post a different issue. I have moved it into its own issue.

ibrahim · November 5, 2020, 1:14pm

This is very interesting. The line that’s throwing the error is

github.com

dgraph-io/badger/blob/d5a25b83fbf4f3f61ff03a9202e36f5b75544426/y/y.go#L139


		return 0
	}
	return math.MaxUint64 - binary.BigEndian.Uint64(key[len(key)-8:])
}

// CompareKeys checks the key without timestamp and checks the timestamp if keyNoTs
// is same.
// a<timestamp> would be sorted higher than aa<timestamp> if we use bytes.compare
// All keys should have timestamp.
func CompareKeys(key1, key2 []byte) int {
	if cmp := bytes.Compare(key1[:len(key1)-8], key2[:len(key2)-8]); cmp != 0 {
		return cmp
	}
	return bytes.Compare(key1[len(key1)-8:], key2[len(key2)-8:])
}

// ParseKey parses the actual key from the key bytes.
func ParseKey(key []byte) []byte {
	if key == nil {
		return nil
	}

I don’t understand how this could panic. Another interesting thing I see in the stack trace is

y.CompareKeys(0xc287b90910, 0x400000004a, 0x50, ...)

The byte slice in questions has a length of 0x400000004a=274877907018 and a capacity of 0x50=80. So there is a bytes slice at address 0xc287b90910 which has a capacity of 80 but length 274877907018? This doesn’t make any sense. How can a go program generate a byte slice whose length is more than it’s capacity.

raulk · November 19, 2020, 11:23pm

@ibrahim I think you may see this when the underlying slice is mmapped.

chance · November 25, 2020, 7:20am

It could panic if the len of key1 or key2 is less than 8?

ibrahim · November 30, 2020, 12:49pm