yushuailong opened a new pull request, #20391: URL: https://github.com/apache/nuttx/pull/20391
## Summary `nxsched_collect_deadlock()` can omit the thread whose outgoing wait edge closes a deadlock cycle, even when the caller provides enough output space for every cycle member. This directly affects `dump_deadlock()`, which uses an eight-element array (`DEADLOCK_MAX == 8`). For example, consider an eight-thread cycle with an eight-element output array: ``` T0 -> T1 -> T2 -> T3 -> T4 -> T5 -> T6 -> T7 -> T0 ``` The old collector checks whether the current thread's holder was already seen before storing the current thread. When the traversal reaches T7, it detects that T7's holder is T0 and commits T0 through T6 before T7 is stored. A later traversal starting from T7 has only one output slot remaining. Because the output array is also used as temporary traversal storage, the old algorithm cannot walk the complete cycle again and discards the temporary entry. The final result therefore contains only seven PIDs even though the supplied capacity is sufficient for all eight cycle members. Using the output array for both temporary traversal state and final results can also discard a candidate cycle when the remaining capacity is smaller than its traversal path, include threads that only lead into a cycle, and return duplicate PIDs. This change treats mutex ownership as a wait-for graph in which each waiting thread has at most one outgoing edge. Floyd's cycle detection algorithm is used to locate the exact cycle without consuming output capacity. The collector then copies only the actual cycle members and skips cycles that have already been collected. ## Impact - New feature: NO. This fixes the existing mutex deadlock diagnostic. - User impact: The deadlock diagnostic reports the actual cycle participants. Normal scheduling behavior is unchanged. - Build impact: NO. - Hardware impact: NO. The implementation is architecture independent. - Documentation impact: YES. The API comment and truncation semantics are clarified. - Security impact: NO. - Compatibility impact: No API or ABI impact. Diagnostic output is corrected to exclude duplicate PIDs and threads that only lead into a cycle. PID ordering is not guaranteed. - Runtime impact: Normal mutex and scheduling paths are unchanged. The additional traversal is only used by `nxsched_collect_deadlock()`, currently from the assertion deadlock dump when `CONFIG_ARCH_DEADLOCKDUMP` is enabled. The implementation uses constant auxiliary memory and has O(N^2) worst-case diagnostic scan time. ## Testing I confirm that the change was verified on a local setup and works as intended. - Build host: macOS 27.0, arm64 - Compiler: Apple clang 21.0.0 - Target: `sim:nsh` - Configuration: `CONFIG_ARCH_DEADLOCKDUMP=y` A local test constructed an eight-thread mutex cycle and passed an eight-element output array, matching the `DEADLOCK_MAX` value used by `dump_deadlock()`: ``` T0 -> T1 -> T2 -> T3 -> T4 -> T5 -> T6 -> T7 -> T0 ``` Testing log before the change: ``` eight-cycle capacity=8: count=7 pids=5,6,7,8,9,10,11 FAIL: expected all eight cycle members exit=1 ``` The old implementation omitted PID 12 even though the output array had enough space for all eight deadlocked threads. Testing log after the change: ``` eight-cycle capacity=8: count=8 pids=5,6,7,8,9,10,11,12 PASS: expected all eight cycle members exit=0 ``` Additional local test cases verified that: - Threads that only lead into a deadlock cycle are excluded. - Acyclic mutex wait chains are excluded. - Duplicate PIDs are not returned. - Insufficient output capacity produces a valid truncated result. - A zero-capacity call returns zero. An end-to-end fatal assertion was also triggered from a kernel thread after constructing the eight-thread cycle. The assertion deadlock dump reported all eight cycle members: ``` eight-cycle capacity=8: count=8 pids=5,6,7,8,9,10,11,12 PASS: expected all eight cycle members Triggering kernel-thread PANIC for end-to-end deadlock dump... dump_assert_info: Assertion failed panic: at file: :0 task: deadlock-panic process: Kernel dump_deadlock: Deadlock detected dump_deadlock: deadlock pid: 12 dump_deadlock: deadlock pid: 11 dump_deadlock: deadlock pid: 10 dump_deadlock: deadlock pid: 9 dump_deadlock: deadlock pid: 8 dump_deadlock: deadlock pid: 7 dump_deadlock: deadlock pid: 6 dump_deadlock: deadlock pid: 5 ``` ## PR verification Self-Check - [x] This PR introduces only one functional change. - [x] I have updated all required description fields above. - [x] My PR adheres to the contributing guidelines and coding standard. - [ ] My PR is still work in progress. - [x] My PR is ready for review and can be safely merged into the codebase. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
