Understanding go routine heap

[Yulrizka]

Dear gophers

I have discussion with my colleague about this code

func process() *foo {
    var result *foo

    var wg sync.WaitGroup
    wg.Add(1)
    go func() {
        defer wg.Done()
        result = &foo{1}
    }()

    wg.Wait()

    return result
}

He argues that this is heap race condition.
the result variable which lives on the heap of the go routine is not guaranteed to be synced to the result on the process func's thread.
The better approach would be using a channel instead. I may agree with him that probably using channel is better.
But I would like to understand the reasoning behind that.

I thought that `wg.Wait()` guaranteed that the process func's thread wait until go func is finsihed and sync everything so that the result variable is safe to return.

Probably I'm missing some knowledge about how go routine work.

1. Does the process func thread has separate heap than the go func? If so how does is sync?
2. From I read so far, when go routine needed a bigger stack, it allocates memory from the heap. So what happened for object that is allocated inside of the go routine once the go routine returns?

I there article of source that go into details about this I would love to read it :)

Warm regards,


[Jan Mercl]

On Sat, Aug 20, 2016 at 8:29 AM Yulrizka <yulr...@gmail.com> wrote:

> He argues that this is heap race condition. 

I don't know what is a heap race condition but the code is race free.

--

-j

[Dave Cheney]

I haven't run the code under the race detector (hint, do this and you'll have the official answer) but I don't believe wg.Wait creates a happens before event that ensures the assignment to result will be visible to other goroutine.

[Konstantin Shaposhnikov]

The code might be race free for the current Go implementation but I don't think this behaviour is documented. 

https://golang.org/ref/mem doesn't mention sync.WaitGroup at all. So wg.Done() doesn't necessarily happen before wg.Wait() returns and the effect of writing to "result" could be not visible after wg.Wait().

[gaurav]

I may be trying to suggest more than I properly understand, but looking at src for WaitGroup, 

- Done() calls and Add(-1) which in turn calls atomic.AddUint64() that should be a store-release

- Wait() calls a atomic.LoadUint64() that should be a load-acquire

So anything written before calling Done() should be visible after Wait() sees the effects of Done()

(even though everything above is undocumented)

[Marvin Renich]

* Konstantin Shaposhnikov <k.shapo...@gmail.com> [160820 06:34]:

> The code might be race free for the current Go implementation but I don't
> think this behaviour is documented.
>
> https://golang.org/ref/mem doesn't mention sync.WaitGroup at all. So
> wg.Done() doesn't necessarily happen before wg.Wait() returns and the
> effect of writing to "result" could be not visible after wg.Wait().

I don't believe that https://golang.org/ref/mem should necessarily be
required to mention every library routine that guarantees a
happens-before relationship. It should document the lowest-level
language features, and then the documentation for the library routines
should make a claim that their implementations guarantee such a
relationship.

For sync.WaitGroup, the documentation says "A WaitGroup waits for a
collection of goroutines to finish." For func (*WaitGroup) Wait, the
documentation says "Wait blocks until the WaitGroup counter is zero."
Perhaps the documentation should explicitly mention the Go Memory Model
and state that it is implemented in such a way that a happens-before
relationship exists, but what would be the purpose of WaitGroup if it
didn't guarantee such a relationship?

I believe the happens-before relationship is implied by the current
documentation and the intended use-case for WaitGroup, even if it is not
explicitly stated.

I agree with others in this thread who have stated that there is no race
condition. I disagree with the implication that WaitGroup, as
documented, could be implemented differently in such a way as to both
conform to the Go 1 compatibility promise and fail to provide an
appropriate happens-before relationship.

...Marvin

[Jan Mercl]

On Sat, Aug 20, 2016, 12:34 Konstantin Shaposhnikov <k.shapo...@gmail.com> wrote:

The code might be race free for the current Go implementation but I don't think this behaviour is documented. 

It does not have to. There's no way to implement the documented behavior of sync.Waitgroup such that it would not itself use and thus also provide synchronization (aka the HB ordering). 

https://golang.org/ref/mem doesn't mention sync.WaitGroup at all. So wg.Done() doesn't necessarily happen before wg.Wait() returns and the effect of writing to "result" could be not visible after wg.Wait().

Such Waitgroup would be useless.

--

-j

[T L]

On Saturday, August 20, 2016 at 2:29:41 PM UTC+8, Yulrizka wrote:

Dear gophers

I have discussion with my colleague about this code

func process() *foo {
    var result *foo

    var wg sync.WaitGroup
    wg.Add(1)
    go func() {
        defer wg.Done()
        result = &foo{1}
    }()

    wg.Wait()

    return result
}

He argues that this is heap race condition.
the result variable which lives on the heap of the go routine is not guaranteed to be synced to the result on the process func's thread.
The better approach would be using a channel instead. I may agree with him that probably using channel is better.
But I would like to understand the reasoning behind that.


If the program is not race free, then what is the meaningfulness of WaitGroup?


 

[Henrik Johansson]

Yes like Jan previously said. It is the very use case WaitGroup was developed for.

--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts...@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Joubin Houshyar]

Your firend is correct that using a WaitGroup here does not in anyway address concurrent access to the heap variable 'result'.

This modified example should clear it up:

package main

import (
    "fmt"
    "sync"
)

func main() {
    var i int
    for {
        r := process()
        if r.v == 8 {
            fmt.Printf("%d\n", i)
            panic("eight!")
        }
        i++
    }
}

type foo struct {
    v int

}

func process() *foo {
    var result *foo
    var wg sync.WaitGroup

    wg.Add(1)
    go func() {
        defer wg.Done()
        result = &foo{1}
    }()

    // race condition on result
    result = &foo{8}

    wg.Wait()
    return result
}

The issue here is the runtime scheduler and what execution order can occur before the go routine execution 'process' has been stopped at wg.Wait. So process can return a foo initiazed with either 1 or 8.

I think the general Go developer intuiton here is that the go routine will not run until the parent go routine has hit the wg.Wait (since there are no explicit IO or blocking instructions between the go func() and wg.Wait. However, using Go(1.7) the main loop will panic after as little as 1000 loops.

[Marvin Renich]

* Joubin Houshyar <jhou...@gmail.com> [160822 09:47]:

>
>
> On Saturday, August 20, 2016 at 2:29:41 AM UTC-4, Yulrizka wrote:
> > func process() *foo {
> > var result *foo
> >
> > var wg sync.WaitGroup
> > wg.Add(1)
> > go func() {
> > defer wg.Done()
> > result = &foo{1}
> > }()
> >
> > wg.Wait()
> >
> > return result
> > }
>

> Your firend is correct that using a WaitGroup here does not in anyway
> address concurrent access to the heap variable 'result'.
>
> This modified example should clear it up:
>

> func process() *foo {
> var result *foo
> var wg sync.WaitGroup
>
> wg.Add(1)
> go func() {
> defer wg.Done()
> result = &foo{1}
> }()
>
> // race condition on result
> result = &foo{8}
>
> wg.Wait()
> return result
> }
>
> The issue here is the runtime scheduler and what execution order can occur
> before the go routine execution 'process' has been stopped at wg.Wait. So
> process can return a foo initiazed with either 1 or 8.
>
> I think the general Go developer intuiton here is that the go routine will
> not run until the parent go routine has hit the wg.Wait (since there are no
> explicit IO or blocking instructions between the go func() and wg.Wait.
> However, using Go(1.7) the main loop will panic after as little as 1000
> loops.

In the original code given by the OP, there is only one assignment to
result (in the goroutine), and only one read from result (in the return
statement). The WaitGroup properly orders these statements, so there is
no race condition.

If the OP's friend was trying to say that there easily could be a race
condition if the code was modified to access result in process() after
the go stmt but before the Wait, he would be correct, or if the OP did
not post the full code that his friend was talking about, there might
also be a race condition in the code his friend saw.

But the WaitGroup in the originally posted code does properly order the
two accesses to result.

...Marvin

[Joubin Houshyar]

Didn't say there was.
 

 

If the OP's friend was trying to say that there easily could be a race
condition if the code was modified to access result in process() after
the go stmt but before the Wait, he would be correct, or if the OP did
not post the full code that his friend was talking about, there might
also be a race condition in the code his friend saw.

That's my assumption here.

But the WaitGroup in the originally posted code does properly order the
two accesses to result.

Didn't say it didn't.

...Marvin

[Marvin Renich]

* Joubin Houshyar <jhou...@gmail.com> [160822 12:36]:

> On Monday, August 22, 2016 at 10:27:06 AM UTC-4, Marvin Renich wrote:

> > * Joubin Houshyar <jhou...@gmail.com <javascript:>> [160822 09:47]:

> > >
> > > Your firend is correct that using a WaitGroup here does not in anyway
> > > address concurrent access to the heap variable 'result'.

I obviously (still) misunderstand what you are saying here. Taking the
OP's question at face value, and assuming that important details were
not left out, the OP's friend is simply wrong, and using the WaitGroup
does, indeed, address the concurrent access to the variable 'result'.

[Yulrizka]

Thank you for the explanation and the code sample

But the case here is indeed as Marvin explained, There is race condition.
But in my example, I make sure that wg done is to protect result pointer before calling it to caller.

with this structure some one could easily introduce a race condition if he tried to access the result pointer.

What I would like to understand if there is case that my snippet causes race condition.

This is my understanding.
1. Heap memory is shared between go rountine in the same process
2. main routine create a pointer to some struct on the heap (initially nil)
3. the go routine allocate memory on the heap for the `foo` struct
4. the go routine assign main's result pointer
5. wg.Done() ensure that step 4 is done before it released
6. process will always returns value generated by the go routine.

And I would like to make sure that my understanding of heap is correct. That is shared per process and there are no heap copying between go routine.

Thanks for the response so far, It is really interesting discussion for me :)

[T L]

On Tuesday, August 23, 2016 at 6:14:19 PM UTC+8, Yulrizka wrote:

Thank you for the explanation and the code sample

But the case here is indeed as Marvin explained, There is race condition.

Marvin says there is no race condition in your start comment.
 

[Yulrizka]

Ah sorry I've missed that in the email.

[Ian Lance Taylor]

On Tue, Aug 23, 2016 at 3:14 AM, Yulrizka <yulr...@gmail.com> wrote:
>
> But the case here is indeed as Marvin explained, There is race condition.
> But in my example, I make sure that wg done is to protect result pointer
> before calling it to caller.
>
> with this structure some one could easily introduce a race condition if he
> tried to access the result pointer.
>
> What I would like to understand if there is case that my snippet causes race
> condition.
>
> This is my understanding.
> 1. Heap memory is shared between go rountine in the same process
> 2. main routine create a pointer to some struct on the heap (initially nil)
> 3. the go routine allocate memory on the heap for the `foo` struct
> 4. the go routine assign main's result pointer
> 5. wg.Done() ensure that step 4 is done before it released
> 6. process will always returns value generated by the go routine.
>
> And I would like to make sure that my understanding of heap is correct. That
> is shared per process and there are no heap copying between go routine.

That is correct.

There is no race in the original program you sent because the wg.Done
acts as a store-release and the wg.Wait acts as a load-acquire.

Ian

[Daniel Fanjul]

Hi,

I still don't understand this issue completely.

Sure, the call to wg.Done() will "happen before" wg.Wait() finishes, but the assignment "result = &foo{1}" might still happen concurrently.

I think the problem is the semantics of the defer and the discussion is reduced completely to the question: is the assignment "result = &foo{1}" going to *happen before" the deferred called to "wg.Done()"?

I don't see any occurrence of 'defer' in https://golang.org/ref/mem nor a proper description in https://golang.org/ref/spec#Defer_statements, so I feel inclined to conclude this behavior is undefined by the spec.

Daniel.

[Jan Mercl]

On Wed, Nov 30, 2016 at 7:04 PM Daniel Fanjul <daniel.fan...@gmail.com> wrote:

> Sure, the call to wg.Done() will "happen before" wg.Wait() finishes, but the assignment "result = &foo{1}" might still happen concurrently.

>

> I think the problem is the semantics of the defer and the discussion is reduced completely to the question: is the assignment "result = &foo{1}" going to *happen before" the deferred called to "wg.Done()"?
> 
> I don't see any occurrence of 'defer' in https://golang.org/ref/mem nor a proper description in https://golang.org/ref/spec#Defer_statements, so I feel inclined to conclude this behavior is undefined by the spec.

The specs say that the defered function executes on return from the function where the defer statement is executed(1). The memory model specifies that "Within a single goroutine, reads and writes must behave as if they executed in the order specified by the program.". From (1) the order specified is the assignment followed by the defered function invocation (now actually calling wg.Done()), so the proper non-race condition is fully covered.

--

-j

[Daniel Fanjul]

That quote of the spec does not apply here, because there are no multiple reads and writes. There is one write to 'result' and one method call that will not read or write that 'result'.

[Ian Lance Taylor]

On Wed, Nov 30, 2016 at 10:04 AM, Daniel Fanjul
<daniel.fan...@gmail.com> wrote:
>
> I still don't understand this issue completely.
>
> Sure, the call to wg.Done() will "happen before" wg.Wait() finishes, but the
> assignment "result = &foo{1}" might still happen concurrently.
>
> I think the problem is the semantics of the defer and the discussion is
> reduced completely to the question: is the assignment "result = &foo{1}"
> going to *happen before" the deferred called to "wg.Done()"?

I am asserting that the wg.Done is a store-release and the wg.Wait is
a load-acquire.

> I don't see any occurrence of 'defer' in https://golang.org/ref/mem nor a
> proper description in https://golang.org/ref/spec#Defer_statements, so I
> feel inclined to conclude this behavior is undefined by the spec.

I don't see why the spec needs to say anything beyond what it already
says about defer statements.

What kind of statement do you think needs to be added?

Ian

[Daniel Fanjul]

Yes, I saw your assert and I trust it but I don't see how that answers my question.

There are 4 things that we expect to happen in order:

1) assignment to result,

2) call to wg.Done(),

3) call to wg.Wait(),

4) read of result.

So there is no race condition if we can prove:

A) that (1) happens before (2),

B) that (2) happens before (3),

C) and that (3) happens before (4).

I understand that B) is true, because of the WaitGroup spec and because of your assertion. I don't see how it affects the other two points.

I fail to prove A). How does the spec ensure that (1) happens before (2)? The spec would ensure it if both actions accessed the same variable, but they actually do not.

I would expect the spec to say something like "all statements of the function/method happens before the call to the deferred functions/methods, regardless the variables they may access"

Now I realize that I also fail to prove C). I am probably missing some obvious detail now. I am sorry if that is the case.

I would expect something like "all statements of the function/method happen before the read of the variable that holds the value to be returned, regardless the variables they may access"

[Ian Lance Taylor]

Why are A and C not covered by "Within a single goroutine, reads and

writes must behave as if they executed in the order specified by the

program"?

Ian

[Daniel Fanjul]

Case A: because there is a write and then a method call that does not touch that variable. The go memory model apply only to reads and writes of the same variables. So any possible reordering in this scenario fulfills "the reordering does not change the behavior within that goroutine as defined by the language specification". 

Case C: because there is a read and a method call that does not touch that variable. Same corollary.

[Ian Lance Taylor]

Would you apply the same argument to calls to the Lock and Unlock
methods of a sync.Mutex? After all, the original code could be
rewritten to use Lock and Unlock calls, and presumably that would be
OK.

If you agree with that, then I think it is sufficient to say that
WaitGroup is implemented using sync.Mutex.

Ian

[Daniel Fanjul]

I was going to answer no, but after a careful review of the go memory model section regarding locks, I am replying: yes, I would.

Because the memory model only specifies "happens before" restrictions between calls to Lock() and Unlock() and that is not this case.
"For any sync.Mutex or sync.RWMutex variable l and n < m, call n of l.Unlock() happens before call m of l.Lock() returns."
"For any call to l.RLock on a sync.RWMutex variable l, there is an n such that the l.RLock happens (returns) after call n to l.Unlock and the matching l.RUnlock happens before call n+1 to l.Lock."

The inner most goroutine would run the assignment and a call to l.Lock() or l.Unlock(). You can still swap the actions and "the [resulting] reordering does not change the behavior within that goroutine as defined by the language specification".

[Ian Lance Taylor]

On Wed, Nov 30, 2016 at 2:01 PM, Daniel Fanjul
<daniel.fan...@gmail.com> wrote:
> I was going to answer no, but after a careful review of the go memory model
> section regarding locks, I am replying: yes, I would.
>
> Because the memory model only specifies "happens before" restrictions
> between calls to Lock() and Unlock() and that is not this case.
> "For any sync.Mutex or sync.RWMutex variable l and n < m, call n of
> l.Unlock() happens before call m of l.Lock() returns."
> "For any call to l.RLock on a sync.RWMutex variable l, there is an n such
> that the l.RLock happens (returns) after call n to l.Unlock and the matching
> l.RUnlock happens before call n+1 to l.Lock."
>
> The inner most goroutine would run the assignment and a call to l.Lock() or
> l.Unlock(). You can still swap the actions and "the [resulting] reordering
> does not change the behavior within that goroutine as defined by the
> language specification".

OK, I think this is https://golang.org/issue/7948.

Ian

[Daniel Fanjul]

Err... I think you understood the opposite. 

A no answer would mean this is that issue. A yes answer means the mutex is still not enough. I said yes.

[Ian Lance Taylor]

On Wed, Nov 30, 2016 at 2:35 PM, Daniel Fanjul
<daniel.fan...@gmail.com> wrote:
> Err... I think you understood the opposite.
>
> A no answer would mean this is that issue. A yes answer means the mutex is
> still not enough. I said yes.

I understood that, but the only implication I could draw is that
mutexes are useless. Issue 7948 is about generally cleaning up the
memory model with respect to the sync package.

Ian

> On Wednesday, November 30, 2016 at 11:23:49 PM UTC+1, Ian Lance Taylor
> wrote:
>>
>> On Wed, Nov 30, 2016 at 2:01 PM, Daniel Fanjul
>> <daniel.fan...@gmail.com> wrote:
>> > I was going to answer no, but after a careful review of the go memory
>> > model
>> > section regarding locks, I am replying: yes, I would.
>> >
>> > Because the memory model only specifies "happens before" restrictions
>> > between calls to Lock() and Unlock() and that is not this case.
>> > "For any sync.Mutex or sync.RWMutex variable l and n < m, call n of
>> > l.Unlock() happens before call m of l.Lock() returns."
>> > "For any call to l.RLock on a sync.RWMutex variable l, there is an n
>> > such
>> > that the l.RLock happens (returns) after call n to l.Unlock and the
>> > matching
>> > l.RUnlock happens before call n+1 to l.Lock."
>> >
>> > The inner most goroutine would run the assignment and a call to l.Lock()
>> > or
>> > l.Unlock(). You can still swap the actions and "the [resulting]
>> > reordering
>> > does not change the behavior within that goroutine as defined by the
>> > language specification".
>>
>> OK, I think this is https://golang.org/issue/7948.
>>
>> Ian
>