panic: runtime error: index out of range using Ascend iterator

[missionsix]

I'm hitting a Index error using Ascend to walk the tree.

panic: runtime error: index out of range

goroutine 20 [running]:
github.com/google/btree.(*node).iterate(0xc420115d00, 0x1, 0x0, 0x0, 0x0, 0x0, 0x440000, 0xc42008ef00, 0x300000002)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:524 +0x7df
github.com/google/btree.(*node).iterate(0xc4201780c0, 0x1, 0x0, 0x0, 0x0, 0x0, 0xc420030000, 0xc42008ef00, 0xc4200b00d8)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc4201f4e00, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0xc42008ed08)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc420382900, 0x1, 0x0, 0x0, 0x0, 0x0, 0xc420080000, 0xc42008ef00, 0xc4200100a0)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc4207c14c0, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0xc420103200)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc420d11e40, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0x0)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*node).iterate(0xc423456040, 0x1, 0x0, 0x0, 0x0, 0x0, 0x0, 0xc42008ef00, 0x0)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:512 +0x519
github.com/google/btree.(*BTree).Ascend(0xc420132020, 0xc42008ef00)
        /media/scratch/demo/go/src/github.com/google/btree/btree.go:777 +0x5b
main.stage.func1(0xc420018330, 0xc4201280c0, 0x5a6520, 0xc4201180c0, 0xc420128060, 0xc420116100)
        /media/scratch/demo/demo.go:166 +0x28a
created by main.stage
        /media/scratch/demo/demo.go:130 +0xd3

My stage function is putting O(0.5M) object pointers into the BTree:

Sketched implementation:

const (
    BTREE_DEGREE = 7
)

type myTreeItem struct {
    Object *myObject
    Order int
}

func (a myTreeItem) Less(b btree.Item) bool {
    return a.Order < b.Order
}

processChannel := make(chan *myObject, 1000)
bt := btree.New(BTREE_DEGREE)

// Insert Objects
order := 0
for obj := range objects {
    ci := &myTreeItem{
        Object: obj,
        Order: order,
    }
    i := bt.ReplaceOrInsert(ci)
    order += 1
}

// Traverse
bt.Ascend(func (i btree.Item) bool {
    processChannel <- i.(*myTreeItem).Object
    return true
})

Any ideas?

[missionsix]

> [unrecovered-panic] runtime.startpanic() /usr/lib/go-1.10/src/runtime/panic.go:588 (hits goroutine(34):1 total:1) (PC: 0x438cd0)
Warning: debugging optimized function
        runtime.curg._panic.arg: interface {}(string) "runtime error: index out of range"
   583:         }
   584:         return nil
   585: }
   586:
   587: //go:nosplit
=> 588: func startpanic() {
   589:         systemstack(startpanic_m)
   590: }
   591:
   592: //go:nosplit
   593: func dopanic(unused int) {

(dlv) frame 3
> [unrecovered-panic] runtime.startpanic() /usr/lib/go-1.10/src/runtime/panic.go:588 (hits goroutine(34):1 total:1) (PC: 0x438cd0)
Warning: debugging optimized function
Frame 3: ./go/src/github.com/google/btree/btree.go:524 (PC: 4c58ef)
   519:                         }
   520:                         hit = true
   521:                         if stop != nil && !n.items[i].Less(stop) {
   522:                                 return hit, false
   523:                         }
=> 524:                         if !iter(n.items[i]) {
   525:                                 return hit, false
   526:                         }
   527:                 }
   528:                 if len(n.children) > 0 {
   529:                         if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter); !ok {
(dlv) p i
3
(dlv) p n
*github.com/google/btree.node {
        items: github.com/google/btree.items len: 3, cap: 8, [
                ...,
                ...,
                ...,
        ],
        children: github.com/google/btree.children len: 4, cap: 8, [
                *(*github.com/google/btree.node)(0xc4200b0840),
                *(*github.com/google/btree.node)(0xc424796840),
                *(*github.com/google/btree.node)(0xc42477f340),
                *(*github.com/google/btree.node)(0xc42477ecc0),
        ],
        cow: *github.com/google/btree.copyOnWriteContext {
                freelist: *(*github.com/google/btree.FreeList)(0xc42012e000),},}

(dlv) p n.items
github.com/google/btree.items len: 3, cap: 8, [
        *main.commitItem {
                Commit: *(*gopkg.in/libgit2/git2go%2ev26.Commit)(0xc424789580),
                Order: 514673,},
        *main.commitItem {
                Commit: *(*gopkg.in/libgit2/git2go%2ev26.Commit)(0xc424783720),
                Order: 514430,},
        *main.commitItem {
                Commit: *(*gopkg.in/libgit2/git2go%2ev26.Commit)(0xc42477b8c0),
                Order: 514187,},
]
(dlv) p i
3

[missionsix]

This may have been a usage error.

I was attempting to remove entries from the btree while iterating, filtering them out via processChannel.

This isn't threadsafe?

[gconnell]

Hey, sorry I didn't see this earlier.

You're correct in your diagnosis. The btree is safe for concurrent access if all such access is reads/iterates. However, it (including reads) must be protected externally if any writes/deletes occur.