How can this pattern result in a deadlock?

Question

I have a (LRU) cache object and I encounter a deadlock... How is this possible?

  type cache struct {
    mutex *sync.Mutex
    ...
  }

  func (this *cache) Init() {  // guaranteed to be called once, in main()
    this.mutex = &sync.Mutex{}
  }

  func (this *cache) f1() {
     // Pattern for accessing mute, at the top of any function of 'cache' where needed.
     this.mutex.Lock()
     defer this.mutex.Unlock()
     ...
  }


  func (this *cache) f2() {
     this.mutex.Lock()
     defer this.mutex.Unlock()
     ...
  }

In every function mutex appears, it is accessed with this pattern only. And yet... I get a deadlock. How come this is possible?

Note: This code has been running on a production server for 10 months and it is the first time I get that.

EDIT: so f1() can call (indirectly) f2() to get a deadlock based on the answers. True but in my code this doesn't happen, so I really wonder

Is f1 guaranteed to exit? Does it call other functions that lock the mutex? — captncraig, Jul 25 '17 at 14:38
Deadlock may easily occur if one method of `cache` calls another method, and both contain the `Lock()` call. — icza, Jul 25 '17 at 14:39
As above, depends on what `f1()` does. Also, you don't need to create a new mutex and use `Init()`. Simply use `sync.Mutex` instead of `*sync,Mutex` in your struct as the zero value by design is a valid unlocked mutex. — Martin Campbell, Jul 25 '17 at 14:42
Have you run this under the race detector? I'm not sure if it can detect possible multiple lock attempts, but it may reveal something... — Milo Christiansen, Jul 25 '17 at 14:42
@MiloChristiansen thanks, but race detector didn't output anything — Thomas, Jul 25 '17 at 15:07
@captncraig I have actually f1, f2, f3, but they are pretty easy and 100% sure they don't call each others somehow — Thomas, Jul 25 '17 at 15:08
@Thomas It's not a requirement that the methods directly call each other. It may be `cache.f1()` calls `foo()` which is a "standalone" function, and if `foo()` calls `cache.f2()`, we're at the same deadlock. See edited answer. If even no such transitive calls exist in your code, then you need to post an [mcve], else it becomes off-topic. — icza, Jul 25 '17 at 15:09
How are you observing "deadlock"? Is the app crashing with the "all goroutines are asleep" message, or are things just not responding, or what? What are your actual symptoms here? — captncraig, Jul 25 '17 at 15:11
We really don't have enough info to help you. If you can share a reproducable example, we can help. Alternately, I highly recommend [this package](https://godoc.org/github.com/hashicorp/golang-lru) as a reliable, goroutine safe lru. — captncraig, Jul 25 '17 at 15:35

icza · Accepted Answer · 2017-07-25T15:31:50.147

Deadlock may easily occur if one method of cache calls another method, and both contain the Lock() call.

See this example:

func (this *cache) f1() {
    this.mutex.Lock()
    defer this.mutex.Unlock()
    this.f2()
}

func (this *cache) f2() {
    this.mutex.Lock()
    defer this.mutex.Unlock()
}

func main() {
    c := &cache{}
    c.Init()
    c.f1()
    fmt.Println("Hello, playground")
}

Output (try it on the Go Playground):

fatal error: all goroutines are asleep - deadlock!

goroutine 1 [semacquire]:
sync.runtime_SemacquireMutex(0x1040a12c, 0x8)
    /usr/local/go/src/runtime/sema.go:62 +0x40
sync.(*Mutex).Lock(0x1040a128, 0x10429f5c)
    /usr/local/go/src/sync/mutex.go:87 +0xa0
main.(*cache).f2(0x10429f94, 0x1100c0)
    /tmp/sandbox647646735/main.go:23 +0x40
main.(*cache).f1(0x10429f94, 0xdf6e0)
    /tmp/sandbox647646735/main.go:19 +0xa0
main.main()
    /tmp/sandbox647646735/main.go:30 +0x60

Note that there does not need to have a direct call from one method to the other, it may also be a transitive call. For example cache.f1() may call foo() which may be a "standalone" function, and if foo() calls cache.f2(), we're at the same deadlock.

Improvements:

Don't name your receiver this, it is not idiomatic. You may simply call it c. Read more about it here: In Go is naming the receiver variable 'self' misleading or good practice?

You may embed mutexes, making it convenient to use and eliminate the need for initialization. Read more about it here: When do you embed mutex in struct in Go?

type cache struct {
    sync.Mutex
}

func (c *cache) f1() {
    c.Lock()
    defer c.Unlock()
    c.f2()
}

func (c *cache) f2() {
    c.Lock()
    defer c.Unlock()
}

func main() {
    c := &cache{}
    c.f1()
    fmt.Println("Hello, playground")
}

Of course this also causes a deadlock. Try it on the Go Playground. Also note that this inherently exposes the mutex (as the embedded type starts with lowecae letter), so anyone will be able to call the Lock() and Unlock() methods. Depends on case whether this is a problem.

It exposes the mutex only at the package level, since it's not exported. Correct? Just clarifing for the OP since it could be confusing otherwise. — reticentroot, Jul 25 '17 at 16:46
@reticentroot No, that is not true. Inside a package, all package-level identifiers are visible. Outside of it, only exported identifiers. The type `cache` itself is not exported, but for example if an exported function returns a value of type `cache` or `*cache`, its `Lock()` method can be called by anyone. — icza, Jul 25 '17 at 16:52
Ahh yes your right the mutex is embedded, you could circumvent that by using an unexported member of type mutex. Of course initialization would have to taken care of again... So I guess that's where good documentation comes in lol. Can it be abstracted in anyway to "hide" the lock? — reticentroot, Jul 25 '17 at 16:56
@reticentroot In some cases it can be, e.g. you use a non-pointer field, but make sure you use a pointer to the wrapped struct to avoid accidentally copying the mutex, and make sure the field is addressable as the address is needed to call the `Lock()` and `Unlock()` methods which have pointer receivers. This is possible without initialization as the zero value of `sync.Mutex` is a valid, unlocked mutex. — icza, Jul 25 '17 at 17:03

How can this pattern result in a deadlock?

1 Answers1