tidwall / btree

B-tree implementation for Go
MIT License
1.06k stars 83 forks source link

possible panic when writing from multiple goroutines #32

Closed HeavyHorst closed 1 year ago

HeavyHorst commented 1 year ago

This code immediately panics on my system:

package main

import (
    "math/rand"
    "sync"
    "time"

    "github.com/tidwall/btree"
)

func main() {
    var s btree.Map[int, int]
    numGoroutines := 1000
    numInsertsPerGoroutine := 1_000_000 / numGoroutines

    //var l sync.Mutex
    var wg sync.WaitGroup

    for i := 0; i < numGoroutines; i++ {
        wg.Add(1)
        go func(goroutineIndex int) {
            s1 := rand.NewSource(time.Now().UnixNano())
            r1 := rand.New(s1)
            defer wg.Done()
            for j := 0; j < numInsertsPerGoroutine; j++ {
                key := r1.Intn(100_000_000_000)
                //l.Lock()
                s.Set(key, j)
                //l.Unlock()
            }
        }(i)
    }

    wg.Wait()
}
panic: runtime error: index out of range [9] with length 9

goroutine 8 [running]:
github.com/tidwall/btree.(*Map[...]).nodeSet(0x48b160, 0x0, {0xc00005d6b0?, 0x408cf8?})
        /home/rene/go/pkg/mod/github.com/tidwall/btree@v1.6.0/map.go:234 +0x6f1
github.com/tidwall/btree.(*Map[...]).Set(0x48b160, 0x13220dc334, 0xb)
        /home/rene/go/pkg/mod/github.com/tidwall/btree@v1.6.0/map.go:169 +0x6f
main.main.func1(0x0?)
        /home/rene/Code/btree/main.go:28 +0x1a5
created by main.main
        /home/rene/Code/btree/main.go:21 +0x4d
exit status 2
tidwall commented 1 year ago

The Btree and BtreeG types are thread-safe.

Map and Set are not.

A note should probably be added in the readme / docs.