Deadlock during call to ShapeIndex.Iterator()

[gaston-haro]

This is the call chain for (s *ShapeIndex)

Call to s.Iterator
--> s.maybeApplyUpdates()
  --> Acquires s.mu.Lock()
    --> s.applyUpdatesInternal()
      --> s.updateFaceEdges()
        --> s.skipCellRange()
          --> s.updateEdges()
            --> s.Iterator()
              --> s.maybeApplyUpdates()
                --> Tries to acquire s.mu.Lock() --> DEADLOCK

I'm using version v0.0.0-20200319012246-673a6f80352d

[dsymonds]

Can you see if 050ea44 fixes this? If not, can you provide a reproduction case?

[gaston-haro]

I can check

[gaston-haro]

Problem still persists. To reproduce it is pretty simple:

index := s2.NewShapeIndex()
loop := s2.LoopFromPoints(points)
index.Add(loop)
index.Build()
other_loop := s2.LoopFromPoints(other_points)
index.Add(other_loop)
index.Build() // Deadlock

I'll provide full code later, I'm at work now.
(I'm not sure if this is dependant on the shapes themselves yet)

PS: I really don't think any of the recent changes fix this because the call chain that I described originally remains a valid execution path.

[rsned]

You are adding the same shape a second time to the index?

…

On Thu, Jul 30, 2020 at 6:31 AM Gastón Haro ***@***.***> wrote: Problem still persists. To reproduce it is pretty simple: index := s2.NewShapeIndex() loop := s2.LoopFromPoints(points) index.Add(loop) index.Build() other_loop := s2.LoopFromPoints(other_points) index.Add(other_loop) index.Add(loop) index.Build() // Deadlock I'll provide full code later, I'm at work now. (I'm not sure if this is dependant on the shapes themselves yet) — You are receiving this because you were assigned. Reply to this email directly, view it on GitHub <#67 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACBHGBBVS24MBPWVBHOHE3TR6FY2FANCNFSM4OV6WWUA> .

[gaston-haro]

You are adding the same shape a second time to the index?

No, new (and different) shapes.
PS: Sorry, I updated my previous comment there was an extra line. I see what you meant now.

[mdavis333]

I'm running into this issue as well:

github.com/golang/geo/s2.(*ShapeIndex).maybeApplyUpdates(0xc0001903f0)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:796 +0x75
github.com/golang/geo/s2.(*ShapeIndex).Iterator(0xc0001903f0, 0x70)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:635 +0x3d
github.com/golang/geo/s2.(*ShapeIndex).shrinkToFit(0xc0001903f0, 0xc003413ab0, 0xbfed3612dc5bff5d, 0xbfea84424eb463f1, 0xbfd3858dd3322fb9, 0xbfcea0866809b516, 0xbfcea9de6340bcac)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:947 +0xfb
github.com/golang/geo/s2.(*ShapeIndex).updateFaceEdges(0xc0001903f0, 0x4, 0xc000594000, 0x4b, 0x92, 0xc002c87200)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:922 +0x612
github.com/golang/geo/s2.(*ShapeIndex).applyUpdatesInternal(0xc0001903f0)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:824 +0x1f6
github.com/golang/geo/s2.(*ShapeIndex).maybeApplyUpdates(0xc0001903f0)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:797 +0x83
github.com/golang/geo/s2.(*ShapeIndex).Iterator(0xc0001903f0, 0xc0011107f3349c2c)
/go/pkg/mod/github.com/golang/geo@v0.0.0-20200319012246-673a6f80352d/s2/shapeindex.go:635 +0x3d

Even after patching the library to return an iterator without locking in the maybeApplyUpdates code path, Begin()-shapeindex.go:650 calls maybeApplyUpdates which will also cause a deadlock.

I'm open to submitting a fix, but it's not clear to me the best path forward. There's a TODO for replacing the mutex, so perhaps there's a planned update that will address this issue.

[gaston-haro]

Sorry I haven't found time to submit a minimal working example to reproduce the bug, but the way to go is pretty clear. Even by doing code inspection you realize the possibility of deadlock.

[hypirion]

After quickly looking at this issue because I got hit by it myself, I found out that solving this is a bit more effort than just avoiding the deadlock: Subsequent calls to Build (or anything that triggers an update) may trigger a call to absorbIndexCell, which some steps down the call stack depends on the tracker's lowerBound. That's not yet implemented:

geo/s2/shapeindex.go

Lines 537 to 540 in 740aa86

	// lowerBound returns the shapeID of the first entry x where x >= shapeID.
	func (t *tracker) lowerBound(shapeID int32) int32 {
	panic("not implemented")
	}

But looking at the original C++ source code, it shouldn't be too hard to port it (?):

https://github.com/google/s2geometry/blob/20ea540d81f4575a3fc0aea585aac611bcd03ede/src/s2/mutable_s2shape_index.cc#L432-L440