runtime: incorrect synchronization around arena_used/h_spans during concurrent GC

[dvyukov]

Arena_used/h_spans updates during memory allocation are not synchronized with concurrent GC.
Consider that a thread grows heap and allocates a new object p and then writes p into an existing object or a global. Concurrent GC reaches the global and extracts pointer p, then it checks it against arena_start/arena_used, but it may not see the updated value of arena_used and thus ignore the object p unmarked and unscanned.
A similar senario can happen with h_spans: GC sees new value of arena_used but does not see the new value in h_spans[spanIdx].

This will probably work today on x86 due to conservative compiler that does not reorder memory accesses aggressively. But this should break on arm and power.

@RLH @aclements @rsc

[aclements]

I think this isn't actually a problem, though (if I'm right), it may be worth writing down the reason in the code.

Writing p into a global isn't a problem. We rescan globals during mark termination, which means we've stopped the world and synchronized with any other thread that may have changed arena_used or h_spans.

I claim it also isn't a problem if a thread writes p into a heap object. This will invoke the write barrier, which will publish p to the garbage collector by (eventually) putting a work buffer on the global work buffer list. The arena_used update happens before p is added to the local work buffer (*), which happens before the work buffer is pushed to the global list, which happens before the work buffer pop by the GC, which happens before GC observes p. Hence GC will observe a sufficiently up-to-date value of arena_used.

(*) Unless (maybe this is what you're getting at?), there was bad synchronization on p in the first place and the allocating thread and the thread that published p to the heap are different threads and p was obtained without establishing happens-before. But this would seem to be an extension of our policy of allowing memory safety violations when there are races in user code.

[dvyukov]

@aclements I have not looked at the GC code recently, but I would assume that GC threads are still able to discover pointers by means other than picking up write barrier buffers. And consequently something along the following lines should be possible. Thread 1 allocates an object O and updates arena_used/h_spans. Then thread 1 writes pointer to O into heap. Then GC thread discovers the pointer on its own (by following pointers from roots). GC thread sees the updates value of arena_used, so it starts processing the pointer. But GC thread does not see the updated value of h_spans, so when it consults the span table it finds a stale span on no span at all. At this point GC decided that the pointer is bogus and terminates the program.

[gopherbot]

CL https://golang.org/cl/10817 mentions this issue.

[dvyukov]

There are two other reincarnations of the multiprocessor ordering problem:

1. GC bitmap. It must be visible to GC threads along with the object.
2. Object zeroing. At least the zero state must be visible to GC threads. If GC will see values from the previous life of the object, it will crash or retain irrelevant objects.
   I think that both cases are solvable by issuing a @StoreStore barrier after object initialization (both zeroing and bitmap setup). On the reader side there is a data dependency on the pointer value, so only a data-dependent barrier is enough (which is no-op on everything except Alpha).
   This can also probably add very bad failure modes for user code with data races on pointers, as visibility over bitmap won't be propagated to GC threads.

[RLH]

GC bitmaps can be out of date, they just can't say an object is marked when
it isn't.
Isn't 2 an indication of a run of the mill race condition?

On Mon, Jun 8, 2015 at 9:51 AM, Dmitry Vyukov notifications@github.com
wrote:

There are two other reincarnations of the multiprocessor ordering problem:

1. GC bitmap. It must be visible to GC threads along with the object.
2. Object zeroing. At least the zero state must be visible to GC threads.
   If GC will see values from the previous life of the object, it will crash
   or retain irrelevant objects.
   I think that both cases are solvable by issuing a @StoreStore barrier
   after object initialization (both zeroing and bitmap setup). On the reader
   side there is a data dependency on the pointer value, so only a
   data-dependent barrier is enough (which is no-op on everything except
   Alpha).
   This can also probably add very bad failure modes for user code with data
   races on pointers, as visibility over bitmap won't be propagated to GC
   threads.

—
Reply to this email directly or view it on GitHub
#9984 (comment).

[dvyukov]

@RLH

GC bitmaps can be out of date, they just can't say an object is marked when it isn't.

They also can say a slot is not a pointer when it is a pointer.

Isn't 2 an indication of a run of the mill race condition?

I don't see why.

[RLH]

The GC won't look at bitmaps unless it either has the pointer returned by
the allocation or in a sweep after it has passed through a barrier. The GC
map information will be data dependent on the pointer returned, just like
the zeroing of the actual object.

On Mon, Jun 8, 2015 at 11:10 PM, Dmitry Vyukov notifications@github.com
wrote:

@RLH https://github.com/RLH

GC bitmaps can be out of date, they just can't say an object is marked
when it isn't.

They also can say a slot is not a pointer when it is a pointer.

Isn't 2 an indication of a run of the mill race condition?

I don't see why.

—
Reply to this email directly or view it on GitHub
#9984 (comment).

[dvyukov]

I don't follow, Rick.
What is "pointer returned by the allocation"?

I mean the scenario that I already described in:
#9984 (comment)

Namely:
Object at pointer P is free and contains garbage from the previous life.
Thread 1 allocates P and zeroes the object at P.
Thread 1 write pointer P into heap.
GC thread 2 independently discovers pointer P and starts scanning it.
Thread 2 reads a pointer from object pointed to by P.
Now, there is nothing that guarantees that thread 2 won't see the relic garbage in the pointer slot.
GC explodes on invalid pointer.

[RLH]

I agree we need a StoreStore barrier just before gcmalloc returns the
pointer. I don't see how the GC can independently discover such a pointer
without either a barrier which creates a happens-before edge or a data
dependency which should prevent the invalid pointer.

On Tue, Jun 9, 2015 at 10:42 AM, Dmitry Vyukov notifications@github.com
wrote:

I don't follow, Rick.
What is "pointer returned by the allocation"?

I mean the scenario that I already described in:
#9984 (comment)
#9984 (comment)

Namely:
Object at pointer P is free and contains garbage from the previous life.
Thread 1 allocates P and zeroes the object at P.
Thread 1 write pointer P into heap.
GC thread 2 independently discovers pointer P and starts scanning it.
Thread 2 reads a pointer from object pointed to by P.
Now, there is nothing that guarantees that thread 2 won't see the relic
garbage in the pointer slot.
GC explodes on invalid pointer.

—
Reply to this email directly or view it on GitHub
#9984 (comment).

[dvyukov]

I don't see how the GC can independently discover such a pointer
without either a barrier which creates a happens-before edge or a data
dependency which should prevent the invalid pointer.

Barriers are irrelevant here, because there is always a data dependency on pointer value for GC bitmap and object contents. Object contents are dependent on pointer value. GC bitmap address is dependent on pointer value.

Spans and anera_used are still broken, though.

[aclements]

I'm going to take a stab at arena_used based on the idea in your "Alpha barrier elimination trick" plus fixing places where we explicitly cache the value of arena_used (which is equivalent to really bad load reordering that will also happen on TSO :)

[dvyukov]

@aclements can you construct a test that crashes on TSO? that would be useful.

[aclements]

I think I was wrong about being able to trigger this on TSO for basically the reason I gave in #9984 (comment). scanobject/etc can observe a pointer that's in the heap but larger than the cached arena_used (adding a simple panic to scanobject can demonstrate this), but if the inheap check in write barrier is safe (which it seems to be on TSO with Russ' CL to fix the MapBits ordering problem), then any such pointer will have been marked by the write barrier that made the newly allocated object reachable, so it doesn't need to be marked by scanobject.

(Of course, this is still a problem on non-TSO, as you pointed out in #9984 (comment))