Hi @nvanbenschoten,

This is quite interesting. And thanks for the super detailed description and debugging.

I see the bug and I can reproduce it with the following unit test:

func TestIssue39186(t *testing.T) {
	var data uint64
	ready := make(chan bool, 1)
	finalized := make(chan bool, 1)
	var wg sync.WaitGroup
	wg.Add(2)
	runtime.SetFinalizer(new([10]int), func(*[10]int) {
		wg.Done()
		finalized <- true
	})
	runtime.GC()
	go func() {
		data = 1
		ready <- true
	}()
	go func() {
		<-ready
		<-finalized
		wg.Done()
	}()
	wg.Wait()
	if data != 1 {
		t.Fatal("no data")
	}
}

Both as the race:

==================
WARNING: DATA RACE
Read at 0x00c0000161b8 by goroutine 79:
  runtime/race_test.TestIssue39186()
      /src/go/src/runtime/race/race_test.go:275 +0x223
  testing.tRunner()
      /src/go/src/testing/testing.go:991 +0x1eb

Previous write at 0x00c0000161b8 by goroutine 8:
  runtime/race_test.TestIssue39186.func2()
      /src/go/src/runtime/race/race_test.go:261 +0x38

Goroutine 79 (running) created at:
  testing.(*T).Run()
      /src/go/src/testing/testing.go:1042 +0x660
  testing.runTests.func1()
      /src/go/src/testing/testing.go:1284 +0xa6
  testing.tRunner()
      /src/go/src/testing/testing.go:991 +0x1eb
  testing.runTests()
      /src/go/src/testing/testing.go:1282 +0x527
  testing.(*M).Run()
      /src/go/src/testing/testing.go:1199 +0x2ff
  main.main()
      _testmain.go:66 +0x223

Goroutine 8 (finished) created at:
  runtime/race_test.TestIssue39186()
      /src/go/src/runtime/race/race_test.go:260 +0x1a7
  testing.tRunner()
      /src/go/src/testing/testing.go:991 +0x1eb
==================

and as violation of your check:

/tmp/go-stress744268477
FATAL: ThreadSanitizer CHECK failed: ./gotsan.cpp:568 "((clk_[i])) <= ((ce.epoch))" (0x4006, 0x4003)

/tmp/go-stress622856440
FATAL: ThreadSanitizer CHECK failed: ./gotsan.cpp:568 "((clk_[i])) <= ((ce.epoch))" (0xa006, 0xa005)

But it's not easy to trigger still, I used:

$ go test -c -race ./runtime/race && nice stress -p=64 ./race.test -test.run=TestIssue39186 -test.count=100

Thinking what's the best way to fix this.

Besides fixing __tsan_finalizer_goroutine itself, there are some interesting options:

1. Remove __tsan_finalizer_goroutine. I think the guaranteed semantics are (or should be):

• SetFinalizer happens-before the finalizer execution
• KeepAlive happens-before the finalizer execution (?)
• any explicit synchronization in user code involving the finalizer
  So we could remove __tsan_finalizer_goroutine and instead do more traditional release/acquire in SetFinalizer/KeepAlive.
  FWIW Java has similar "weak" guarantees for finalizers (for good reasons), for all the gory details see:
  https://www.hboehm.info/misc_slides/java_finalizers.pdf

2. Run __tsan_finalizer_goroutine during STW in GC before it makes the next batch of finalizer ready to run. This will naturally serialize __tsan_finalizer_goroutine execution and should provide enough synchronization.

Thanks for taking a look @dvyukov. I'm very glad to see that you were able to find a smaller reproduction.

Run __tsan_finalizer_goroutine during STW in GC before it makes the next batch of finalizer ready to run. This will naturally serialize __tsan_finalizer_goroutine execution and should provide enough synchronization.

This is how I assumed things were working for a while. Making this change would simplify the interactions here significantly, along with the implementation of __tsan_finalizer_goroutine / __tsan::AcquireGlobal because that function would no longer need to make any effort to handle concurrently running threads.

The downside of this approach is that it pushes the burden of synchronization on to the caller of AcquireGlobal. I don't know exactly how you view the programmatic interface of the ThreadSanitizer runtime library (e.g. is this a specialized hook for Go or something more general?), but this change would complicate that interface.

There's also the concern that iterating over each active thread is not instantaneous, as evidenced by the fact that we were able to race with the process. That indicates that this might be too expensive of an operation to add to stop the world pauses in GC, even if this will only fire when the race detector is enabled. Then again, the race detector already has such large runtime overhead that this may be in the noise.

So we could remove __tsan_finalizer_goroutine and instead do more traditional release/acquire in SetFinalizer/KeepAlive

I prefer an option like this because it moves the causality tracking closer to the minimum guarantees provided by the memory model.

That said, I don't think I understand how this would work. It seems like we'd need to establish a happens-before edge with any time that the object was still reachable, even if the object itself wasn't being directly manipulated. For instance, we might have a slice of objects on the heap. I would expect that any memory access I perform provably before that slice has become unreachable will have a happens-before edge to the finalizers of each of these objects. I don't know how that's possible to do efficiently because it's not even clear which memory address to synchronize on, and I assume that's why __tsan_finalizer_goroutine was added in the first place. That allows us to use the GC's understanding of reachability to establish these happens-before edges, even if this does result in significant over-synchronization.

FWIW Java has similar "weak" guarantees for finalizers (for good reasons), for all the gory details see: https://www.hboehm.info/misc_slides/java_finalizers.pdf

This was an enlightening read. I hope we don't go too far in that direction. The need to synchronize internal memory accesses in a single-threaded application because of the subtle reachability rules seems unnecessarily antagonistic.

I don't know what to do here, I just want to comment that runtime.KeepAlive is in effect a compiler intrinsic. It just changes the lifetime information for the object. If we want runtime.KeepAlive to do some sort of synchronization with the race detector, then it seems to me that we want that same synchronization to occur on any access to the object, since any access will keep the object alive.

When I look at @dvyukov 's test case, it seems that the assignment to data happens before the send on ready happens before the receive from ready happens before the call to wg.Done happens before the return from wg.Wait happens before the read of data. So I'm not sure what the finalizer has to do with this. But I don't actually understand what the problem is.

So I'm not sure what the finalizer has to do with this. But I don't actually understand what the problem is.

The finalizer is key here because its call to __tsan_finalizer_goroutine is faulty in that it establishes a happens-before edge from all other goroutines to the finalizer goroutine. However, it does so in an unsynchronized manner which allows the resulting vector clock in the finalizer goroutine to enter an inconsistent state. For instance, consider the following sequence of events:

g1: [1, 0], g2: [0, 1]
-- __tsan_finalizer_goroutine reads g1's local clock, observes 1
-- g1 ticks clock & reads from data @ [2, 0]
g1: [3, 0], g2: [1, 1] -- g2 acquires              (+ ticks clock)
g1: [3, 0], g2: [3, 2] -- g1 releases, g2 acquires (+ ticks clock). last_acquire_ = 2.
g1: [3, 0], g2: [3, 3] -- g2 ticks clock
-- __tsan_finalizer_goroutine reads g2's local clock, observes 3

g_finalizer: [1, 3] 

If this inconsistent clock state is merged into a synchronization element (the WaitGroup in the test case), then a future release operation which is necessary to establish the "call to wg.Done happens before the return from wg.Wait happens" link may be ignored due to this optimization. Continuing our example:

s_wg: [0, 0]
s_wg: [1, 3] -- g_finalizer releases into s_wg when calling wg.Done
s_wg: [1, 3] -- g2 releases into s_wg when calling wg.Done
-- g2's clock is [3, 3], but causality is not propagated because last_acquire_ (2) < 3.

g3: [0, 0]
g3: [1, 3] -- g3 acquires from s_wg when wg.Wait completes
-- g3 writes to data @ [1, 3]. [2, 0] does not happen-before [1, 3]. Data race detected!

So we could disable the optimization, but more likely, we want to prevent these inconsistent vector clock states from becoming possible.

I don't know exactly how you view the programmatic interface of the ThreadSanitizer runtime library (e.g. is this a specialized hook for Go or something more general?), but this change would complicate that interface.

It's pretty much tied to it's few real users. We don't try to solve all of the world's problems with it.
We can change it or introduce a new function as necessary. I've notified Java folks as well, most likely the Java interface is equally affected:
https://mail.openjdk.java.net/pipermail/tsan-dev/2020-May/000429.html

That said, I don't think I understand how this would work. It seems like we'd need to establish a happens-before edge with any time that the object was still reachable, even if the object itself wasn't being directly manipulated. For instance, we might have a slice of objects on the heap. I would expect that any memory access I perform provably before that slice has become unreachable will have a happens-before edge to the finalizers of each of these objects.

No. That's the point. We don't need to explain this to tsan, because this synchronization does not exist. Check out the presentation again ;)

Finalizers introduce concurrency
   Synchronize!
Finalizers can run earlier than you think!
   Synchronize!

We need to explain to tsan only synchronization that actually does exist in real life (that's why I explicitly mentioned only SetFinalizer/KeepAlive). Consider we have:

*p = foo
*y = bar

Now consider that the second store make an object unreachable and the first store stores to something transitively reachable from that object.
To provide the guarantee you are assuming is there, compiler would need to enforce program order for all stores (no optimizations possible). Moreover, with a better implementation (e.g. maybe the new async preemption is enough), compiler would also need to inject memory barriers between all stores as well to ensure that if a concurrent GC schedules a finalizer, it will observe all stores properly. This is unbearably expensive. That's why there is simply no such guarantee. In Java it's very explicit, in Go it does not seem to be documented that well, but I believe Go simply can't realistically provide such a guarantee.

I don't know what to do here, I just want to comment that runtime.KeepAlive is in effect a compiler intrinsic. It just changes the lifetime information for the object. If we want runtime.KeepAlive to do some sort of synchronization with the race detector, then it seems to me that we want that same synchronization to occur on any access to the object, since any access will keep the object alive.

See my reply above:
#39186 (comment)

runtime.KeepAlive should provide such synchronization to be useful.
Today nothing special may be required (no-op on implementation) level because GC includes STW. But I believe on semantic level, KeepAlive should synchronize with the finalizer.

Otherwise os package use of finalizers would be broken (and majority of code that uses finalizers):

func (f *File) readdirnames(n int) (names []string, err error) {
	if f.dirinfo == nil {
		f.dirinfo = new(dirInfo)
		f.dirinfo.buf = make([]byte, blockSize)
...
			runtime.KeepAlive(f)

func (file *file) close() error {
	if file.dirinfo != nil {
		file.dirinfo.close()
	}

Consider there is no synchronization between KeepAlive and the finalizer. Now the finalizer is not guaranteed to observe file.dirinfo != nil even though it was set. And if it observes file.dirinfo != nil, it may not properly observe contents of *file.dirinfo.

Now re "same synchronization to occur on any access to the object" part. This is too costly to provide. Simply infeasible. See the Java paper. Such synchronization should not be guaranteed.
But since we have KeepAlive, it actually solves the problem. If one does:

		f.dirinfo = new(dirInfo)
	        runtime.KeepAlive(f)

This now guarantees that if this code run, the finalizer will properly observe f.dirinfo.
And if we ever need any actual hardware synchronization (e.g. when GC becomes even more concurrent), KeepAlive will be the place to add it . So it may be the natural place to add race detection annotation as well.

Proposed fix:
https://reviews.llvm.org/D80474
@nvanbenschoten do you mind reviewing it? I think you are the best qualified to meaningfully review the fix logic.

I agree that it seems infeasible to synchronize between any access of the object and the finalizer.

But semantically speaking, it seems to me that any access to the object really does happen before the execution of the finalizer, in exactly the same way that any call to runtime.KeepAlive happens before the execution of the finalizer. If the last use of f is to set the dirinfo field, then the finalizer must reliably see the value set in the dirinfo field.

If the last use of f is to set the dirinfo field, then the finalizer must reliably see the value set in the dirinfo field.

The question is: is it guaranteed to see *dirinfo values? That is, all indirectly accessible values.
If not, then it becomes very hard to use finalizers correctly (fd.dirinfo is broken).
If yes, it would impose pretty hard limitations on compilation (can't say about gc, but gcc and llvm don't provide them) and potentially hardware synchronization in future.

Personally, I think finalizers are required to see the *dirinfo values.

I think that implies that a compiler can't consider a variable to be dead until all memory stores made before the last access of that variable have been emitted. That in itself is not a major restriction; it just adjusts the liveness map of the function.

At execution time it implies that there must be a synchronization barrier between an object being considered dead and the object's finalizer being run. Fortunately I think we already have that in the current garbage collector, via the brief stop-the-world phases. It's true that we'll have to keep this in mind as we keep adjusting the garbage collector. But since we make no promises as to how soon we will run a finalizer, I don't think it's a hard promise to keep.

No doubt I am missing some things.

it just adjusts the liveness map of the function.

Are you sure it's enough? I think it must restrict order of operations themselves. Even if we have a pointer slot live, if it already contains nil, it won't help.

I don't see how this could be a problem. How could there be a point in the program where we still have a pending write to an object, but we no longer have a pointer to it? I could see the hardware doing that, but the compiler can't.

I don't see how this could be a problem. How could there be a point in the program where we still have a pending write to an object, but we no longer have a pointer to it? I could see the hardware doing that, but the compiler can't.

Not the object, but something transitively reachable from the object that finalizer uses.
E.g. *f.dirinfo here:

func (f *File) readdirnames(n int) (names []string, err error) {
	// If this file has no dirinfo, create one.
	if f.dirinfo == nil {
		f.dirinfo = new(dirInfo)
		// The buffer must be at least a block long.
		f.dirinfo.buf = make([]byte, blockSize)
	}
	d := f.dirinfo

	size := n
	if size <= 0 {
		size = 100
		n = -1
	}

	names = make([]string, 0, size) // Empty with room to grow.
	for n != 0 {
		// Refill the buffer if necessary
		if d.bufp >= d.nbuf {
			d.bufp = 0
			var errno error
			d.nbuf, errno = f.pfd.ReadDirent(d.buf)
			runtime.KeepAlive(f)
			if errno != nil {
				return names, wrapSyscallError("readdirent", errno)
			}
			if d.nbuf <= 0 {
				break // EOF
			}
		}

		// Drain the buffer
		var nb, nc int
		nb, nc, names = syscall.ParseDirent(d.buf[d.bufp:d.nbuf], n, names)
		d.bufp += nb
		n -= nc
	}
	if n >= 0 && len(names) == 0 {
		return names, io.EOF
	}
	return names, nil
}

func (file *file) close() error {
	if file == nil {
		return syscall.EINVAL
	}
	if file.dirinfo != nil {
		file.dirinfo.close()
	}

Just so I understand, you're worried about:

  f := new(...)
  runtime.SetFinalizer(f, ...)
  p := new(...)
  f.p = p
  p.x = 7
  runtime.KeepAlive(f) // last use of f

You're worried that the finalizer might not see f.p.x == 7?

I don't think that's a problem in the current compiler, as runtime.KeepAlive is modeled as a write operation, and will not be reordered with other writes. (GC does not reorder writes at all.)

Without the runtime.KeepAlive, this code might not see f.p.x == 7, and we should report a race, because the finalizer could happen before the p.x = 7 statement.

Exactly. runtime.KeepAlive is what provides synchronization with the finalizer and what makes the code correct. I was worried about the claim that any access to the object provides the same synchronization as KeepAlive e.g. in:

  f := new(...)
  runtime.SetFinalizer(f, ...)
  p := new(...)
  p.x = 7
  f.p = p

gc is not the only compiler that compiles Go code.

f := new(...)
runtime.SetFinalizer(f, ...)
p := new(...)
p.x = 7
f.p = p

Yes, if the compiler reorders the last two writes, and it does not extend the lifetime of f until after the now-last p.x = 7 statement, then we have a problem.
So store-reordering optimizations are certainly possible, they just need to keep some sense of the pre-reordered liveness map around.

f := new(...)
runtime.SetFinalizer(f, ...)
p := new(...)
f.p = p
// f can't die here, even though it looks like it does
p.x = 7
// f has to die (at least) here

Is that saying the same thing that Ian said? I think so. I hope so.

As Ian mentioned, reordering by the hardware shouldn't matter - the stop-the-world at the start of the GC (and allocating black during GC?) should save us.

they just need to keep some sense of the pre-reordered liveness map around.

Not just maps, but also values. Consider the example here:
#39186 (comment)
If we have a value live, but it's nil, it doesn't help much. Which effectively means no reordering, no?

Yes, you need the value of f live somewhere where I noted. Not the variable f.
The variable could have been overwritten, sure.
So when reordering stores, the lifetime of the values of the pointers being stored to cannot shrink. The value of each pointer must live on somewhere (not necessarily in f, just somewhere marked live) until at least its original source location.

But doesn't it effectively mean no reordering? If for:

*p = foo
*y = bar

compiler would need to generate on reordering:

oldy := *y
*y = bar
*p = foo
_ = oldy

It looks reasonable to simply prohibit write reordering at this point (probably won't be profitable: more instructions, bringing cache line in potentially shared state, more registers consumed).

And we don't do this today, right? Which means we do not give this guarantee. Which means we can as well never give it because there is no code that relies on it (theoretically).

Also brings interesting concerns for write-only memory. In such cases we cannot preserve the value, and the write is the end of life.

*p = foo
*y = bar

Ah, now I see what the issue is. The last pointer to the object being finalized is overwritten, not just dropped. It might not live in a live map (i.e. be on the stack) anywhere where we can extend its lifetime.

So we execute *y = bar, making our object unreachable, then we get interrupted and GC is run. GC decides to schedule the finalizer and it runs before the goroutine that is about to execute *p = foo ever gets scheduled.

This would be hard to do in the current garbage collector - you have to time it just right or the write barrier will prevent collection of the overwritten pointer. But not impossible, I guess.

The preemptive scheduler makes this worse by making everywhere a safe point. Before that, only call sites are safe points so we need only prevent reordering writes across calls.

So yes, it looks like this would prevent reordering writes where at least one of them is a pointer write? Or we have to mark such reorderings as unsafe points, perhaps?

FTR tsan fix is merged in llvm/llvm-project@4408eee

Thanks for merging the fix @dvyukov. I see that this issue is marked under the go1.16 milestone. Is it too late in the 1.15 release cycle to rebuild the .syso files in src/runtime/race to pick up this patch?

As far as I know this is not a new problem in 1.15, so at this point in the release process the fix should wait until 1.16. Sorry.

Got it, thanks for the update. Then as far as I'm concerned, this issue can be closed. I'll defer to you on whether we should keep it open to track the proposed changes to the role of finalizers in the memory model.

Seems like we should at least keep this open to rebuild the .syso files for the 1.16 release.

/cc @randall77 Is there something to do here for Go 1.16?

Sure, Dmitry V. outlined a few possibilities. I haven't put much thought into how hard it would be.

@randall77 Following up on this as a 1.16 release blocker. What are the next steps here?

Someone has to understand whether Dmitry V's tsan fix described here fixes the OP's issue. If it does, we just need a rebuild of the .syso files, which I can do when we get a bit closer to the freeze.

There are some other issues lurking around this thread also, not sure what to do about those. Because we don't reorder writes at the moment, there may not be anything to do, other than maybe a comment somewhere about never reordering writes due to this issue.

@dvyukov @nvanbenschoten @randall77 since we’ve landed a fix, do we just need to update the .syso files now?

@andybons That's my understanding. The fix that landed upstream in LLVM's tsan should resolve this bug once included in the .syso files.

Got it. Thanks. @randall77 leaving up to you.

I'm going to wait 2 weeks to make sure there's nothing else coming for tsan. Then I'll rebuild the .syso files.

@randall77 , 2 week ping. :)

Change https://golang.org/cl/264082 mentions this issue: runtime/race: update race .syso files