Repository: gonum/gonum (language: go)

Issue:
graph/iterator: segfault in graph/iterator.(*mapIter).next
with latest `go-tip`:
```
$> go version
go version devel go1.18-534dfb2aeb Tue Sep 28 03:21:58 2021 +0000 linux/amd64
```

I get the following segfault when running tests in `graph` (at 06c2c527):

```
FAIL	gonum.org/v1/gonum/graph/topo	0.649s
unexpected fault address 0x8000103
fatal error: fault
[signal SIGSEGV: segmentation violation code=0x1 addr=0x8000103 pc=0x40efaa]

goroutine 5 [running]:
runtime.throw({0x52c95f, 0x203000})
	/home/binet/sdk/go/src/runtime/panic.go:965 +0x71 fp=0xc000fdeaf8 sp=0xc000fdeac8 pc=0x4343d1
runtime.sigpanic()
	/home/binet/sdk/go/src/runtime/signal_unix.go:803 +0x305 fp=0xc000fdeb48 sp=0xc000fdeaf8 pc=0x448c05
runtime.mapiternext(0xc0001045c0)
	/home/binet/sdk/go/src/runtime/map.go:901 +0x18a fp=0xc000fdebb8 sp=0xc000fdeb48 pc=0x40efaa
runtime.mapiterinit(0x51f760, 0x1, 0xc000fdec40)
	/home/binet/sdk/go/src/runtime/map.go:849 +0x229 fp=0xc000fdebd8 sp=0xc000fdebb8 pc=0x40edc9
reflect.mapiterinit(0x40d067, 0x0, 0xc000fdec40)
	/home/binet/sdk/go/src/runtime/map.go:1361 +0x19 fp=0xc000fdec00 sp=0xc000fdebd8 pc=0x45df99
gonum.org/v1/gonum/graph/iterator.(*mapIter).next(0xc0001045d0)
	/home/binet/work/gonum/src/gonum.org/v1/gonum/graph/iterator/map.go:125 +0x5e fp=0xc000fdec20 sp=0xc000fdec00 pc=0x4f247e
gonum.org/v1/gonum/graph/iterator.(*NodesByEdge).Next(0xc000523200)
	/home/binet/work/gonum/src/gonum.org/v1/gonum/graph/iterator/nodes_map.go:149 +0x37 fp=0xc000fdec50 sp=0xc000fdec20 pc=0x4f2657
gonum.org/v1/gonum/graph/traverse.(*BreadthFirst).Walk(0xc000fdee70, {0x559d08, 0xc00053c1e0}, {0x557fe0, 0x600148}, 0xc000fdee08)
	/home/binet/work/gonum/src/gonum.org/v1/gonum/graph/traverse/traverse.go:72 +0x591 fp=0xc000fded18 sp=0xc000fdec50 pc=0x4f4db1
gonum.org/v1/gonum/graph/traverse.TestBreadthFirst(0xc0010a9a00)
	/home/binet/work/gonum/src/gonum.org/v1/gonum/graph/traverse/traverse_test.go:161 +0x299 fp=0xc000fdef70 sp=0xc000fded18 pc=0x4f5e39
testing.tRunner(0xc0010a9a00, 0x537660)
	/home/binet/sdk/go/src/testing/testing.go:1389 +0x102 fp=0xc000fdefc0 sp=0xc000fdef70 pc=0x4b67a2
testing.(*T).Run.func1()
	/home/binet/sdk/go/src/testing/testing.go:1436 +0x2a fp=0xc000fdefe0 sp=0xc000fdefc0 pc=0x4b766a
runtime.goexit()
	/home/binet/sdk/go/src/runtime/asm_amd64.s:1446 +0x1 fp=0xc000fdefe8 sp=0xc000fdefe0 pc=0x463021
created by testing.(*T).Run
	/home/binet/sdk/go/src/testing/testing.go:1436 +0x35f

goroutine 1 [chan receive]:
testing.(*T).Run(0xc0010a9860, {0x52ebe8, 0x4b6505}, 0x537660)
	/home/binet/sdk/go/src/testing/testing.go:1437 +0x37a
testing.runTests.func1(0xc0010a9860)
	/home/binet/sdk/go/src/testing/testing.go:1777 +0x6e
testing.tRunner(0xc0010a9860, 0xc00008dcd8)
	/home/binet/sdk/go/src/testing/testing.go:1389 +0x102
testing.runTests(0xc000128000, {0x61b180, 0x3, 0x3}, {0x7f15fac64108, 0x0, 0x620300})
	/home/binet/sdk/go/src/testing/testing.go:1775 +0x43f
testing.(*M).Run(0xc000128000)
	/home/binet/sdk/go/src/testing/testing.go:1663 +0x5d9
main.main()
	_testmain.go:75 +0x1aa
FAIL	gonum.org/v1/gonum/graph/traverse	0.319s
```

not sure whether that's a problem in `Gonum` or with `Go`.


Discussion / hints:

Fix patch:
diff --git a/graph/iterator/lines_map.go b/graph/iterator/lines_map.go
index 95959b3aa..384809f14 100644
--- a/graph/iterator/lines_map.go
+++ b/graph/iterator/lines_map.go
@@ -56,7 +56,7 @@ func (l *Lines) Line() graph.Line {
 func (l *Lines) Reset() {
 	l.curr = nil
 	l.pos = 0
-	l.iter.it = nil
+	l.iter.hiter = hiter{}
 }
 
 // LineSlice returns all the remaining lines in the iterator and advances
@@ -121,7 +121,7 @@ func (l *WeightedLines) WeightedLine() graph.WeightedLine {
 func (l *WeightedLines) Reset() {
 	l.curr = nil
 	l.pos = 0
-	l.iter.it = nil
+	l.iter.hiter = hiter{}
 }
 
 // WeightedLineSlice returns all the remaining lines in the iterator and advances
diff --git a/graph/iterator/map.go b/graph/iterator/map.go
index 613a614d2..1bf8f3e6b 100644
--- a/graph/iterator/map.go
+++ b/graph/iterator/map.go
@@ -19,14 +19,40 @@ import (
 
 // A mapIter is an iterator for ranging over a map.
 type mapIter struct {
-	m  *emptyInterface
-	it unsafe.Pointer
+	m     *emptyInterface
+	hiter hiter
 }
 
 type emptyInterface struct {
 	typ, word unsafe.Pointer
 }
 
+// hiter's structure matches runtime.hiter's structure.
+// Having a clone here allows us to embed a map iterator
+// inside type mapIter so that mapIters can be re-used
+// without doing any allocations.
+type hiter struct {
+	key         unsafe.Pointer
+	elem        unsafe.Pointer
+	t           unsafe.Pointer
+	h           unsafe.Pointer
+	buckets     unsafe.Pointer
+	bptr        unsafe.Pointer
+	overflow    *[]unsafe.Pointer
+	oldoverflow *[]unsafe.Pointer
+	startBucket uintptr
+	offset      uint8
+	wrapped     bool
+	B           uint8
+	i           uint8
+	bucket      uintptr
+	checkBucket uintptr
+}
+
+func (h hiter) initialized() bool {
+	return h.t != nil
+}
+
 // newMapIterNodes returns a range iterator for a map of nodes.
 // The returned mapIter must not have its line or weightedLine methods called.
 func newMapIterNodes(m map[int64]graph.Node) *mapIter {
@@ -75,77 +101,75 @@ func eface(i interface{}) *emptyInterface {
 
 // id returns the key of the iterator's current map entry.
 func (it *mapIter) id() int64 {
-	if it.it == nil {
+	if !it.hiter.initialized() {
 		panic("mapIter.id called before Next")
 	}
-	if mapiterkey(it.it) == nil {
+	if mapiterkey(&it.hiter) == nil {
 		panic("mapIter.id called on exhausted iterator")
 	}
-	return *(*int64)(mapiterkey(it.it))
+	return *(*int64)(mapiterkey(&it.hiter))
 }
 
 // node returns the value of the iterator's current map entry.
 func (it *mapIter) node() graph.Node {
-	if it.it == nil {
+	if !it.hiter.initialized() {
 		panic("mapIter.node called before next")
 	}
-	if mapiterkey(it.it) == nil {
+	if mapiterkey(&it.hiter) == nil {
 		panic("mapIter.node called on exhausted iterator")
 	}
-	return *(*graph.Node)(mapiterelem(it.it))
+	return *(*graph.Node)(mapiterelem(&it.hiter))
 }
 
 // line returns the value of the iterator's current map entry.
 func (it *mapIter) line() graph.Line {
-	if it.it == nil {
+	if !it.hiter.initialized() {
 		panic("mapIter.line called before next")
 	}
-	if mapiterkey(it.it) == nil {
+	if mapiterkey(&it.hiter) == nil {
 		panic("mapIter.line called on exhausted iterator")
 	}
-	return *(*graph.Line)(mapiterelem(it.it))
+	return *(*graph.Line)(mapiterelem(&it.hiter))
 }
 
 // weightedLine returns the value of the iterator's current map entry.
 func (it *mapIter) weightedLine() graph.WeightedLine {
-	if it.it == nil {
+	if !it.hiter.initialized() {
 		panic("mapIter.weightedLine called before next")
 	}
-	if mapiterkey(it.it) == nil {
+	if mapiterkey(&it.hiter) == nil {
 		panic("mapIter.weightedLine called on exhausted iterator")
 	}
-	return *(*graph.WeightedLine)(mapiterelem(it.it))
+	return *(*graph.WeightedLine)(mapiterelem(&it.hiter))
 }
 
 // next advances the map iterator and reports whether there is another
 // entry. It returns false when the iterator is exhausted; subsequent
 // calls to Key, Value, or next will panic.
 func (it *mapIter) next() bool {
-	if it.it == nil {
-		it.it = mapiterinit(it.m.typ, it.m.word)
+	if !it.hiter.initialized() {
+		mapiterinit(it.m.typ, it.m.word, &it.hiter)
 	} else {
-		if mapiterkey(it.it) == nil {
+		if mapiterkey(&it.hiter) == nil {
 			panic("mapIter.next called on exhausted iterator")
 		}
-		mapiternext(it.it)
+		mapiternext(&it.hiter)
 	}
-	return mapiterkey(it.it) != nil
+	return mapiterkey(&it.hiter) != nil
 }
 
-// m escapes into the return value, but the caller of mapiterinit
-// doesn't let the return value escape.
-//go:linkname mapiterinit reflect.mapiterinit
+//go:linkname mapiterinit runtime.mapiterinit
 //go:noescape
-func mapiterinit(t, m unsafe.Pointer) unsafe.Pointer
+func mapiterinit(t, m unsafe.Pointer, it *hiter)
 
 //go:linkname mapiterkey reflect.mapiterkey
 //go:noescape
-func mapiterkey(it unsafe.Pointer) (key unsafe.Pointer)
+func mapiterkey(it *hiter) (key unsafe.Pointer)
 
 //go:linkname mapiterelem reflect.mapiterelem
 //go:noescape
-func mapiterelem(it unsafe.Pointer) (elem unsafe.Pointer)
+func mapiterelem(it *hiter) (elem unsafe.Pointer)
 
 //go:linkname mapiternext reflect.mapiternext
 //go:noescape
-func mapiternext(it unsafe.Pointer)
+func mapiternext(it *hiter)
diff --git a/graph/iterator/nodes_map.go b/graph/iterator/nodes_map.go
index 029d59dd3..d8af8ba79 100644
--- a/graph/iterator/nodes_map.go
+++ b/graph/iterator/nodes_map.go
@@ -56,7 +56,7 @@ func (n *Nodes) Node() graph.Node {
 func (n *Nodes) Reset() {
 	n.curr = nil
 	n.pos = 0
-	n.iter.it = nil
+	n.iter.hiter = hiter{}
 }
 
 // NodeSlice returns all the remaining nodes in the iterator and advances
@@ -164,7 +164,7 @@ func (n *NodesByEdge) Node() graph.Node {
 func (n *NodesByEdge) Reset() {
 	n.curr = nil
 	n.pos = 0
-	n.iter.it = nil
+	n.iter.hiter = hiter{}
 }
 
 // NodeSlice returns all the remaining nodes in the iterator and advances
diff --git a/graph/iterator/nodes_map_safe.go b/graph/iterator/nodes_map_safe.go
index c3b551c00..3f3bca16d 100644
--- a/graph/iterator/nodes_map_safe.go
+++ b/graph/iterator/nodes_map_safe.go
@@ -61,6 +61,7 @@ func (n *Nodes) Node() graph.Node {
 func (n *Nodes) Reset() {
 	n.curr = nil
 	n.pos = 0
+	// TODO(kortschak): Use n.iter.Reset(n.nodes) when it is available and Go1.17 is no longer supported.
 	n.iter = n.nodes.MapRange()
 }
 


Test patch: