CODEWITHSUNDEEP
gomemory-leaks
Yu Liu
Yu Liu

Reputation: 33

memory leak in solution for Exercise: Equivalent Binary Trees?

(https://github.com/golang/tour/blob/master/solutions/binarytrees_quit.go) for Exercise: Equivalent Binary Trees Supposed we have two simple equivalent binary trees "1 3 5" and "2 3 5". When two goroutines "Walk" walks at leaf "1" and "2" concurrently, 

if v1 != v2 {
    return false
}

this condition in function Same will be true and

close(quit)

will run.

func walkImpl(t *tree.Tree, ch, quit chan int) {
    if t == nil {
        return
    }
    walkImpl(t.Left, ch, quit)
    select {
    case ch <- t.Value:
        // Value successfully sent.
    case <-quit:
        return
    }
    walkImpl(t.Right, ch, quit)
}

Channel "quit" will receive message and the second case of select statement will execute. And then it will go back to the upper level function "walkImpl" and keep on running the last line walkImpl(t.Right, ch, quit). So is there goroutine leak under the circumstance, cause channel "quit" is already read out, which can't be read again in the upper level? Function "Walk" also can't go back to "close" handler.

Upvotes: 3

Views: 240

Answers (1)

icza
icza

Reputation: 418257

When multiple goroutines are targeted with a cancellation signal, most often it is done by closing a channel, and not sending a value on the channel. Receiving from a closed channel can proceed immediately, no matter how many goroutines do that. A value sent on a channel can be received at most once, so it is not suitable to signal multiple goroutines with a value. Spec: Receive operator:

A receive operation on a closed channel can always proceed immediately, yielding the element type's zero value after any previously sent values have been received.

Now, if you close the quit channel, that does not guarantee your function will return immediately.

First, you recurse down to the left child without checking quit, which call will do the same (until a nil left child is reached).

Second, if a value can be sent on ch, then both cases are ready and thus select chooses one of them randomly, which may or may not be the quit case. For details, see How does select work when multiple channels are involved?

If you want to avoid these, you should add a non-blocking quit check as the first thing in your function:

func walkImpl(t *tree.Tree, ch, quit chan int) {
    select {
    case <-quit:
        return
    default: // This empty default makes it a non-blocking check
    }

    if t == nil {
        return
    }
    walkImpl(t.Left, ch, quit)
    select {
    case ch <- t.Value:
        // Value successfully sent.
    case <-quit:
        return
    }
    walkImpl(t.Right, ch, quit)
}

Now one could ask if we still need the quit case in the second select since we've already checked it first thing in walkImpl(). The answer is that you should keep that too, because if sending on ch would block (e.g. the consumer would be shut down when quit is closed), that send operation could block forever. This way (when quit is closed) it is guaranteed that the function returns.

Upvotes: 2

Related Questions