resam72
commented
5 months ago i get the same issue here is a sample code that shows this
in this code i'm trying to implement a kind of MFU cache
i'm using the KCounter where the KCounter.value is the frequency of the KCounter.key
the tree holds only N keys with the highest frequency , when there is no more room left the key with the minimal frequency will be dropped
const maxCacheSize = 3
type KCounter struct {
key string
value int
}
func (t KCounter) Less(than llrb.Item) bool {
counter := than.(KCounter)
if t.key < counter.key {
return true
}
return t.value < counter.value
}
func Test_A(t *testing.T) {
put := func(t *llrb.LLRB, itemByKey map[string]KCounter, kc KCounter) bool {
item, ok := itemByKey[kc.key]
if ok {
//update the value by re-inserting it
t.Delete(item)
t.ReplaceOrInsert(kc)
itemByKey[kc.key] = kc
return true
}
if t.Len() >= maxCacheSize {
smallestItem := t.Min().(KCounter)
if kc.value < smallestItem.value {
//dont add group that have values that are smaller than the smallest elem in tree
return false
}
t.DeleteMin()
}
t.ReplaceOrInsert(kc)
itemByKey[kc.key] = kc
return true
}
itemByKey := make(map[string]KCounter)
tree := llrb.New()
for i := 0; i < 100000; i++ {
put(tree, itemByKey, KCounter{strconv.Itoa(i % 20), i % 10})
}
}this result in
panic: runtime error: invalid memory address or nil pointer dereference [recovered]
panic: runtime error: invalid memory address or nil pointer dereference
[signal SIGSEGV: segmentation violation code=0x2 addr=0x20 pc=0x102c393dc]
goroutine 35 [running]:
testing.tRunner.func1.2({0x102f08580, 0x10323fb40})
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1545 +0x1c4
testing.tRunner.func1()
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1548 +0x360
panic({0x102f08580?, 0x10323fb40?})
/opt/homebrew/opt/go/libexec/src/runtime/panic.go:914 +0x218
github.com/petar/GoLLRB/llrb.flip(...)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:417
github.com/petar/GoLLRB/llrb.moveRedRight(0x140000e6b18?)
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:434 +0x2c
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000991e8?, 0x1400009c510, {0x102f80818, 0x14000099d40})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:361 +0x2a4
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000e6c18?, 0x1400009c510, {0x102f80818, 0x14000099d40})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x14000099d40?, 0x1400009c780, {0x102f80818, 0x14000099d40})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).delete(0x140000e6d01?, 0x1400009c780, {0x102f80818, 0x14000099d40})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:372 +0x354
github.com/petar/GoLLRB/llrb.(*LLRB).Delete(0x140001ebdc8, {0x102f80818?, 0x14000099d40?})
/Users/igadassi/.gvm/pkgsets/go1.21.7/global/pkg/mod/github.com/petar/!go!l!l!r!b@v0.0.0-20210522233825-ae3b015fd3e9/llrb/llrb.go:328 +0x38
xdr.panw/ipl/internal/dml/cronus/throttler.Test_frequentKeyCounterTracker1.func1(0x140001ebdc8, 0x103177850?, {{0x102e1242d, 0x1}, 0x8})
/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:325 +0xa0
xdr.panw/ipl/internal/dml/cronus/throttler.Test_frequentKeyCounterTracker1(0x1?)
/Users/igadassi/gonzo/src/xdr.panw/ipl/internal/dml/cronus/throttler/throttler_test.go:348 +0xe0
testing.tRunner(0x1400008a820, 0x102f7d1f0)
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1595 +0xe8
created by testing.(*T).Run in goroutine 1
/opt/homebrew/opt/go/libexec/src/testing/testing.go:1648 +0x33c
Process finished with the exit code 1
I've ran into a case where the delete code path appears to panic within the llrb package:
It seems that
moveRedRightrequires both the left and right children to exist https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L432, but here only the right child is tested https://github.com/petar/GoLLRB/blob/master/llrb/llrb.go#L359-L362?