Badger panics with Index Out of Range

whyrusleeping · November 4, 2020, 11:03pm

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:07pm

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

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

How could that happen? Do you have an example? I’ve never seen this before.

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

@chance, no. If that was the case, we would see a panic: slice out of range [:-8] (or some negative number)

BlankRain · December 9, 2020, 6:54am

274877907010
the 274877907010 is strange
ko := itr.t.blockOffsets()[idx]

Topic		Replies	Views
Panic : Slice Range Out Of Bound. InitIndex Crashed Badger badger	0	213	September 21, 2023
Data recovery after a slice bounds out of range error Badger	3	1162	December 5, 2021
[badger v3] panic: runtime error: slice bounds out of range Badger kind:bug	0	1315	May 14, 2021
Slice bounds out of range in table.(*Builder) Badger	9	774	September 21, 2020
[badger v1.6.2] panic: slice bounds out of range Badger kind:bug	3	522	March 24, 2021