CODEWITHSUNDEEP
godeadlock
Leo Zhang
Leo Zhang

Reputation: 3230

How to prevent deadlock in recursive function?

I have a recursive function that I will lock and mutate its internal state, however, it causes a deadlock. How can I implement such a recursive function without deadlock?

package main

import (
    "fmt"
    "sync"
)

type runner struct {
    sync.Mutex
    value int
}

func (r *runner) decrement() {
    r.Lock()
    defer r.Unlock()
    if r.value == 0 {
        return
    }
    r.value--
    r.decrement()
}

func main() {
    r := runner{
        value: 10,
    }

    r.decrement()

    fmt.Printf("r: %v\n", r.value)
}

Expect running the above code would print r: 0, but actually got deadlock:

fatal error: all goroutines are asleep - deadlock!

Upvotes: 1

Views: 1396

Answers (1)

Chris Heald
Chris Heald

Reputation: 62668

The typical solution to this kind of problem is a reentrant mutex. However, Russ Cox of the Go team has a good argument as to why reentrant mutexes are a bad idea.

In this case, you don't want to defer your unlock. Instead, you should lock and unlock the minimal sections necessary.

func (r *runner) decrement() {
    r.Lock()
    if r.value == 0 {
        r.Unlock()
        return
    }
    r.value--
    r.Unlock()
    r.decrement()
}

This solves two problems: one, it (marginally) improves the ability of your code to run concurrently by not taking locks for things which don't need locking, and two, it ensures that if you re-enter decrement(), there isn't an outstanding lock that will result in a deadlock.

Upvotes: 1

Related Questions