GoDDaR detects and fixes deadlocks in concurrent Go programs
Automatically Detecting and Fixing Deadlocks in Go Code with GoDDaR
Programming LanguagesDistributed, Parallel, and Cluster ComputingSoftware Engineering
Summary
Programs written in the Go language use multiple threads, called goroutines, that can sometimes get stuck waiting for each other forever, a problem called deadlock. Go's current tools only catch total deadlocks when everything stops, missing cases where only some threads are blocked. The authors developed GoDDaR, which can find these hidden deadlocks in the code before running it. It also suggests changes to fix the deadlocks automatically by analyzing communication patterns between threads.
What this means in practice
- •For go software developers: Identify and repair complex deadlocks in Go code automatically to improve concurrent program reliability.
- •For static analysis tool developers: Incorporate GoDDaR’s symbolic analysis and fix-suggestion techniques to enhance deadlock detection and repair capabilities.
Authors
Gustavo Feio, Jorge Coelho, Miguel Flor, João M. Lourenço, António Ravara
Abstract
The Go programming language provides a lightweight abstraction for concurrent programming through goroutines, which are prone to deadlocks. Go includes a runtime detector that aborts execution when all threads are blocked (a global deadlock). However, due to nondeterministic thread scheduling, this runtime mechanism only detects global deadlocks that manifest during execution and cannot identify partial deadlocks, where a subset of goroutines is permanently blocked while at least one remains runnable. Statically detecting local deadlocks is essential for developing dependable concurrent software. While several tools statically detect deadlocks in concurrent programs, few assist developers in fixing them. Detecting and resolving partial deadlocks requires reasoning about complex interleavings and communication patterns, an inherently challenging task. In this paper, we present GoDDaR, a tool that detects unobserved global or partial deadlocks in Go programs and suggests concrete fixes. GoDDaR translates Go source code into an intermediate representation reflecting message-passing communication events and composition patterns. Partial deadlocks are identified through symbolic analysis over this representation. To resolve detected deadlocks, our algorithms transform the intermediate representation to eliminate problematic synchronization patterns, allowing GoDDaR to generate fix suggestions for the original Go source code as a diff. We evaluate GoDDaR on a benchmark suite of representative deadlock examples from literature and git repositories to validate algorithm correctness and compare performance against the state of the art. Results demonstrate that GoDDaR is competitive with top approaches in partial deadlock detection and advances the state of the art in automated deadlock fixing.