This is an automated email from the ASF dual-hosted git repository.
xiaoxiang781216 pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
The following commit(s) were added to refs/heads/master by this push:
new 31f3857cb41 sched: Fix deadlock cycle collection.
31f3857cb41 is described below
commit 31f3857cb41ebd4b561e5fe40a8ec31d5ebd6d98
Author: yushuailong <[email protected]>
AuthorDate: Mon Sep 28 21:26:02 2026 +0800
sched: Fix deadlock cycle collection.
Use Floyd cycle detection on the mutex wait-for chain so only threads that
actually participate in a cycle are reported. This avoids omitting the last
cycle member and incorrectly including threads that merely lead into a deadlock.
Also handle empty output buffers and document truncation semantics.
Assisted-by: OpenAI Codex
Signed-off-by: yushuailong <[email protected]>
---
include/nuttx/sched.h | 9 ++--
sched/misc/deadlock.c | 144 ++++++++++++++++++++++++++++++++++++--------------
2 files changed, 108 insertions(+), 45 deletions(-)
diff --git a/include/nuttx/sched.h b/include/nuttx/sched.h
index 390bb00a99a..09916b833d6 100644
--- a/include/nuttx/sched.h
+++ b/include/nuttx/sched.h
@@ -1611,14 +1611,15 @@ pid_t nxsched_getppid(void);
* Name: nxsched_collect_deadlock
*
* Description:
- * Check if there is a deadlock and get the thread pid of the deadlock.
+ * Find mutex deadlocks and collect the IDs of participating threads.
*
* Input parameters:
- * pid - The array to store the thread pid of the deadlock.
- * count - The size of the pid array.
+ * pid - The array to store deadlocked thread IDs.
+ * count - The maximum number of thread IDs to store.
*
* Returned Value:
- * The number of thread deadlocks.
+ * The number of thread IDs stored in pid. A return value equal to count
+ * may indicate that the result was truncated.
*
****************************************************************************/
diff --git a/sched/misc/deadlock.c b/sched/misc/deadlock.c
index 68dd7798404..0f8e350d1ac 100644
--- a/sched/misc/deadlock.c
+++ b/sched/misc/deadlock.c
@@ -68,72 +68,128 @@ static FAR mutex_t *getmutex(FAR struct tcb_s *tcb)
}
/****************************************************************************
- * Name: collect_deadlock
+ * Name: deadlock_next
****************************************************************************/
-static void collect_deadlock(FAR struct tcb_s *tcb, FAR void *arg)
+static FAR struct tcb_s *deadlock_next(FAR struct tcb_s *tcb)
{
- FAR struct deadlock_info_s *info = arg;
FAR mutex_t *mutex;
- size_t index;
+ pid_t holder;
mutex = getmutex(tcb);
if (mutex == NULL)
{
- return;
+ return NULL;
}
- /* Check previous deadlock holder list. */
+ holder = nxmutex_get_holder(mutex);
+ if (holder < 0)
+ {
+ return NULL;
+ }
- for (index = 0; index < info->holdercnt; index++)
+ return nxsched_get_tcb(holder);
+}
+
+/****************************************************************************
+ * Name: find_deadlock_cycle
+ ****************************************************************************/
+
+static FAR struct tcb_s *find_deadlock_cycle(FAR struct tcb_s *tcb)
+{
+ FAR struct tcb_s *slow = tcb;
+ FAR struct tcb_s *fast = tcb;
+
+ /* Each thread has at most one outgoing edge in the mutex wait-for graph.
+ * Use Floyd's algorithm to determine whether the chain contains a cycle.
+ */
+
+ do
{
- if (info->holders[index] == tcb->pid)
+ slow = deadlock_next(slow);
+ fast = deadlock_next(fast);
+ if (fast != NULL)
{
- return;
+ fast = deadlock_next(fast);
+ }
+
+ if (slow == NULL || fast == NULL)
+ {
+ return NULL;
}
}
+ while (slow != fast);
- /* Append the holders for this tcb to list. */
+ /* Then locate the first TCB in the cycle. */
- for (index = info->holdercnt; index < info->arraylen; index++)
+ slow = tcb;
+ while (slow != fast)
{
- pid_t holder;
- size_t i;
+ slow = deadlock_next(slow);
+ fast = deadlock_next(fast);
+ }
- holder = nxmutex_get_holder(mutex);
- if (holder < 0)
- {
- break;
- }
+ return slow;
+}
- /* Check if this holder is already held. */
+/****************************************************************************
+ * Name: deadlock_contains
+ ****************************************************************************/
- for (i = info->holdercnt; i < index; i++)
+static bool deadlock_contains(FAR const struct deadlock_info_s *info,
+ pid_t pid)
+{
+ size_t index;
+
+ for (index = 0; index < info->holdercnt; index++)
+ {
+ if (info->holders[index] == pid)
{
- if (info->holders[i] == holder)
- {
- info->holdercnt = index;
- return;
- }
+ return true;
}
+ }
- /* Add holder to list and continue to holder's holder. */
+ return false;
+}
- info->holders[index] = tcb->pid;
- tcb = nxsched_get_tcb(holder);
- mutex = getmutex(tcb);
- if (mutex == NULL)
- {
- /* If this holder isn't waiting for mutex, it's over. */
+/****************************************************************************
+ * Name: collect_deadlock
+ ****************************************************************************/
- break;
- }
+static void collect_deadlock(FAR struct tcb_s *tcb, FAR void *arg)
+{
+ FAR struct deadlock_info_s *info = arg;
+ FAR struct tcb_s *entry;
+ FAR struct tcb_s *current;
+
+ if (info->holdercnt >= info->arraylen ||
+ deadlock_contains(info, tcb->pid))
+ {
+ return;
}
- /* If no deadlock, clear the holders of this tcb. */
+ entry = find_deadlock_cycle(tcb);
+ if (entry == NULL || deadlock_contains(info, entry->pid))
+ {
+ return;
+ }
+
+ /* Only copy TCBs which are members of the cycle. Threads which merely
+ * wait on a deadlocked thread are not themselves part of the deadlock.
+ */
+
+ current = entry;
+ do
+ {
+ if (info->holdercnt >= info->arraylen)
+ {
+ return;
+ }
- memset(&info->holders[info->holdercnt], 0,
- (info->arraylen - info->holdercnt) * sizeof(pid_t));
+ info->holders[info->holdercnt++] = current->pid;
+ current = deadlock_next(current);
+ }
+ while (current != entry);
}
/****************************************************************************
@@ -144,14 +200,15 @@ static void collect_deadlock(FAR struct tcb_s *tcb, FAR
void *arg)
* Name: nxsched_collect_deadlock
*
* Description:
- * Check if there is a deadlock and get the thread pid of the deadlock.
+ * Find mutex deadlocks and collect the IDs of participating threads.
*
* Input parameters:
- * pid - The array to store the thread pid of the deadlock.
- * count - The size of the pid array.
+ * pid - The array to store deadlocked thread IDs.
+ * count - The maximum number of thread IDs to store.
*
* Returned Value:
- * The number of thread deadlocks.
+ * The number of thread IDs stored in pid. A return value equal to count
+ * may indicate that the result was truncated.
*
****************************************************************************/
@@ -159,6 +216,11 @@ size_t nxsched_collect_deadlock(FAR pid_t *pid, size_t
count)
{
struct deadlock_info_s info;
+ if (pid == NULL || count == 0)
+ {
+ return 0;
+ }
+
info.holders = pid;
info.arraylen = count;
info.holdercnt = 0;
