[go] cmd/dist: detect import cycles instead of deadlocking
Gerrit Bot (Gerrit)
Gerrit Bot has uploaded the change for review![]( "Open in Gerrit")
Commit message
cmd/dist: detect import cycles instead of deadlocking
## Summary
Previously, if there was an import cycle in the packages being built (e.g., package A imports B and B imports A), the build would deadlock with "all goroutines are asleep - deadlock!" because each package's goroutine would block waiting for the other to complete.
Now we detect import cycles before blocking on dependencies by tracking which packages each goroutine is waiting on and checking for cycles using depth-first search. When a cycle is detected, we report it with a clear message:
- Self-import: `import cycle: go/ast -> go/ast`
- Indirect cycle: `import cycle: go/ast -> go/scanner -> go/token -> go/ast`
## Test plan
- [x] Tested self-import cycle detection (go/ast imports go/ast)
- [x] Tested indirect import cycle detection (go/token imports go/ast, go/ast imports go/token)
- [x] Verified normal builds complete successfully
- [x] `all.bash` passes: ALL TESTS PASSED
Fixes #76439
Change diff
diff --git a/src/cmd/dist/build.go b/src/cmd/dist/build.go
index e4250e1..910338b 100644
--- a/src/cmd/dist/build.go
+++ b/src/cmd/dist/build.go
@@ -678,10 +678,46 @@
var installed = make(map[string]chan struct{})
var installedMu sync.Mutex
+// pkgDeps tracks the packages each package is waiting on.
+// It's used to detect import cycles that would cause deadlocks.
+var pkgDeps = make(map[string][]string)
+
func install(dir string) {
<-startInstall(dir)
}
+// checkInstallCycle checks if waiting for dep from pkg would create a cycle.
+// It returns the cycle path if a cycle is found, or nil otherwise.
+// installedMu must be held when calling this function.
+func checkInstallCycle(pkg, dep string) []string {
+ // DFS to find if dep transitively depends on pkg
+ visited := make(map[string]bool)
+ var path []string
+ var dfs func(p string) bool
+ dfs = func(p string) bool {
+ if p == pkg {
+ return true // Found cycle back to pkg
+ }
+ if visited[p] {
+ return false
+ }
+ visited[p] = true
+ path = append(path, p)
+ for _, d := range pkgDeps[p] {
+ if dfs(d) {
+ return true
+ }
+ }
+ path = path[:len(path)-1]
+ return false
+ }
+ if dfs(dep) {
+ // Return the cycle: pkg -> dep -> ... -> pkg
+ return append([]string{pkg}, path...)
+ }
+ return nil
+}
+
func startInstall(dir string) chan struct{} {
installedMu.Lock()
ch := installed[dir]
@@ -702,6 +738,13 @@
}
defer close(ch)
+ defer func() {
+ // Clean up pkgDeps when done to avoid holding references
+ // and to keep the cycle detection data structure clean.
+ installedMu.Lock()
+ delete(pkgDeps, pkg)
+ installedMu.Unlock()
+ }()
if pkg == "unsafe" {
return
@@ -883,13 +926,31 @@
}
sort.Strings(sortedImports)
+ // Start all dependency installations and collect the list of deps.
+ deps := make([]string, 0, len(importMap))
for _, dep := range importMap {
if dep == "C" {
fatalf("%s imports C", pkg)
}
+ deps = append(deps, dep)
startInstall(dep)
}
- for _, dep := range importMap {
+
+ // Check for import cycles before blocking on dependencies.
+ // We record that this package depends on deps, then check if any dep
+ // transitively depends on us, which would cause a deadlock.
+ installedMu.Lock()
+ pkgDeps[pkg] = deps
+ for _, dep := range deps {
+ if cycle := checkInstallCycle(pkg, dep); cycle != nil {
+ installedMu.Unlock()
+ fatalf("import cycle: %s", strings.Join(append(cycle, pkg), " -> "))
+ }
+ }
+ installedMu.Unlock()
+
+ // Wait for all dependencies to be installed.
+ for _, dep := range deps {
install(dep)
}
Change information
- M src/cmd/dist/build.go
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Gopher Robot added 1 comment![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. You have a long 263 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)
2. It looks like you are using markdown in the commit message. If so, please remove it. Be sure to double-check the plain text shown in the Gerrit commit message above for any markdown backticks, markdown links, or other markdown formatting.
Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gopher Robot (Gerrit)
Message from Gopher Robot![]( "Open in Gerrit")
Congratulations on opening your first change. Thank you for your contribution!
Next steps:
A maintainer will review your change and provide feedback. See
https://go.dev/doc/contribute#review for more info and tips to get your
patch through code review.
Most changes in the Go project go through a few rounds of revision. This can be
surprising to people new to the project. The careful, iterative review process
is our way of helping mentor contributors and ensuring that their contributions
have a lasting impact.
During May-July and Nov-Jan the Go project is in a code freeze, during which
little code gets reviewed or merged. If a reviewer responds with a comment like
R=go1.11 or adds a tag like "wait-release", it means that this CL will be
reviewed as part of the next development cycle. See https://go.dev/s/release
for more details.
Related details
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Matloob (Gerrit)
Michael Matloob added 2 comments![]( "Open in Gerrit")
I spotted some possible problems with your PR:
1. You have a long 263 character line in the commit message body. Please add line breaks to long lines that should be wrapped. Lines in the commit message body should be wrapped at ~76 characters unless needed for things like URLs or tables. (Note: GitHub might render long lines as soft-wrapped, so double-check in the Gerrit commit message shown above.)
2. It looks like you are using markdown in the commit message. If so, please remove it. Be sure to double-check the plain text shown in the Gerrit commit message above for any markdown backticks, markdown links, or other markdown formatting.Please address any problems by updating the GitHub PR.
When complete, mark this comment as 'Done' and click the [blue 'Reply' button](https://go.dev/wiki/GerritBot#i-left-a-reply-to-a-comment-in-gerrit-but-no-one-but-me-can-see-it) above. These findings are based on heuristics; if a finding does not apply, briefly reply here saying so.
To update the commit title or commit message body shown here in Gerrit, you must edit the GitHub PR title and PR description (the first comment) in the GitHub web interface using the 'Edit' button or 'Edit' menu entry there. Note: pushing a new commit to the PR will not automatically update the commit message used by Gerrit.
For more details, see:
- [how to update commit messages](https://go.dev/wiki/GerritBot/#how-does-gerritbot-determine-the-final-commit-message) for PRs imported into Gerrit.
- the Go project's [conventions for commit messages](https://go.dev/doc/contribute#commit_messages) that you should follow.
(In general for Gerrit code reviews, the change author is expected to [log in to Gerrit](https://go-review.googlesource.com/login/) with a Gmail or other Google account and then close out each piece of feedback by marking it as 'Done' if implemented as suggested or otherwise reply to each review comment. See the [Review](https://go.dev/doc/contribute#review) section of the Contributing Guide for details.)
Could you address these issues?
if cycle := checkInstallCycle(pkg, dep); cycle != nil {We're doing the check for each dependency in the graph, and each check visits all the nodes. The check is made harder by the concurrent aspect, but one option would be to pass in the import stack, and produce the error if the dependency is on the stack. That's essentially how the go command checks for cycles.
Related details
- Michael Matloob
Code-Review
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Funda Secgin (Gerrit)
Funda Secgin voted Code-Review+1![]( "Open in Gerrit")
| Code-Review | +1 |
Related details
- Michael Matloob
Code-Review
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
- Code-Review: +1 by Funda Secgin
Related details
- Funda Secgin
- Michael Matloob
Code-Review
No-Unresolved-Comments
No-Wait-Release
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Michael Matloob (Gerrit)
Michael Matloob added 1 comment![]( "Open in Gerrit")
Please add me back when this is ready for another round of review.
Related details
- Funda Secgin
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |
Gerrit Bot (Gerrit)
Gerrit Bot uploaded new patchset![]( "Open in Gerrit")
Related details
- Funda Secgin
Code-Review
No-Unresolved-Comments
Review-Enforcement
TryBots-Pass
| Inspect html for hidden footers to help with email filtering. To unsubscribe visit settings. |