This is an automated email from the ASF dual-hosted git repository.
xiaoxiang pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/nuttx.git
commit 9dbb9b49c65ed738948f3047d44d871c195cf3d2
Author: ouyangxiangzhen <ouyangxiangz...@xiaomi.com>
AuthorDate: Wed Apr 16 19:44:35 2025 +0800
sched/wqueue: Change dq to list.
In NuttX, the dq and the list are two different implementations of the
double-linked list. Comparing to the dq, the list implementation has less
branch conditions such as checking whether the head or tail is NULL. In theory
and practice, the list is more friendly to the CPU pipeline. This commit
changed the dq to the list in the wqueue implementation.
Signed-off-by: ouyangxiangzhen <ouyangxiangz...@xiaomi.com>
---
include/nuttx/wqueue.h | 4 +--
libs/libc/wqueue/work_cancel.c | 29 ++---------------
libs/libc/wqueue/work_queue.c | 68 +++++++++++++--------------------------
libs/libc/wqueue/work_usrthread.c | 17 +++++-----
libs/libc/wqueue/wqueue.h | 7 ++--
sched/wqueue/kwork_cancel.c | 7 ++--
sched/wqueue/kwork_queue.c | 10 +++---
sched/wqueue/kwork_thread.c | 14 +++++---
sched/wqueue/wqueue.h | 8 ++---
9 files changed, 59 insertions(+), 105 deletions(-)
diff --git a/include/nuttx/wqueue.h b/include/nuttx/wqueue.h
index f964608fbb..59803faf6c 100644
--- a/include/nuttx/wqueue.h
+++ b/include/nuttx/wqueue.h
@@ -33,7 +33,7 @@
#include <stdint.h>
#include <nuttx/clock.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wdog.h>
/****************************************************************************
@@ -249,7 +249,7 @@ typedef CODE void (*worker_t)(FAR void *arg);
struct work_s
{
- struct dq_entry_s dq; /* Implements a double linked list */
+ struct list_node node; /* Implements a double linked list */
clock_t qtime; /* Time work queued */
union
{
diff --git a/libs/libc/wqueue/work_cancel.c b/libs/libc/wqueue/work_cancel.c
index 195f781a02..7d4188e974 100644
--- a/libs/libc/wqueue/work_cancel.c
+++ b/libs/libc/wqueue/work_cancel.c
@@ -65,8 +65,6 @@
static int work_qcancel(FAR struct usr_wqueue_s *wqueue,
FAR struct work_s *work)
{
- FAR dq_entry_t *prev = NULL;
- FAR dq_entry_t *curr;
int ret = -ENOENT;
int semcount;
@@ -83,37 +81,16 @@ static int work_qcancel(FAR struct usr_wqueue_s *wqueue,
if (work->worker != NULL)
{
- /* Search the work activelist for the target work. We can't
- * use dq_rem to do this because there are additional operations that
- * need to be done.
- */
-
- curr = wqueue->q.head;
- while (curr && curr != &work->dq)
- {
- prev = curr;
- curr = curr->flink;
- }
-
- /* Check if the work was found in the list. If not, then an OS
- * error has occurred because the work is marked active!
- */
-
- DEBUGASSERT(curr);
+ bool is_head = list_is_head(&wqueue->q, &work->node);
/* Now, remove the work from the work queue */
- if (prev)
- {
- /* Remove the work from mid- or end-of-queue */
+ list_delete(&work->node);
- dq_remafter(prev, &wqueue->q);
- }
- else
+ if (is_head)
{
/* Remove the work at the head of the queue */
- dq_remfirst(&wqueue->q);
nxsem_get_value(&wqueue->wake, &semcount);
if (semcount < 1)
{
diff --git a/libs/libc/wqueue/work_queue.c b/libs/libc/wqueue/work_queue.c
index 26b4acf9ff..23dd1535b0 100644
--- a/libs/libc/wqueue/work_queue.c
+++ b/libs/libc/wqueue/work_queue.c
@@ -32,7 +32,7 @@
#include <errno.h>
#include <nuttx/clock.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include "wqueue/wqueue.h"
@@ -76,9 +76,7 @@ static int work_qqueue(FAR struct usr_wqueue_s *wqueue,
FAR struct work_s *work, worker_t worker,
FAR void *arg, clock_t delay)
{
- FAR dq_entry_t *prev = NULL;
- FAR dq_entry_t *curr;
- sclock_t delta;
+ FAR struct work_s *curr;
int semcount;
/* Get exclusive access to the work queue */
@@ -91,55 +89,35 @@ static int work_qqueue(FAR struct usr_wqueue_s *wqueue,
work->arg = arg; /* Callback argument */
work->qtime = clock() + delay; /* Delay until work performed */
- /* Do the easy case first -- when the work queue is empty. */
+ /* Insert the work into the wait queue sorted by the expired time. */
- if (wqueue->q.head == NULL)
+ list_for_every_entry(&wqueue->q, curr, struct work_s, node)
{
- /* Add the watchdog to the head == tail of the queue. */
-
- dq_addfirst(&work->dq, &wqueue->q);
- nxsem_post(&wqueue->wake);
+ if (!clock_compare(curr->qtime, work->qtime))
+ {
+ break;
+ }
}
- /* There are other active watchdogs in the timer queue */
+ /* After the insertion, we do not violate the invariant that
+ * the wait queue is sorted by the expired time. Because
+ * curr->qtime > work->qtime.
+ * In the case of the wqueue is empty, we insert
+ * the work at the head of the wait queue.
+ */
- else
- {
- curr = wqueue->q.head;
+ list_add_before(&curr->node, &work->node);
- /* Check if the new work must be inserted before the curr. */
+ /* If the current work is the head of the wait queue.
+ * We should wake up the worker thread.
+ */
- do
- {
- delta = work->qtime - ((FAR struct work_s *)curr)->qtime;
- if (delta < 0)
- {
- break;
- }
-
- prev = curr;
- curr = curr->flink;
- }
- while (curr != NULL);
-
- /* Insert the new watchdog in the list */
-
- if (prev == NULL)
- {
- /* Insert the watchdog at the head of the list */
-
- dq_addfirst(&work->dq, &wqueue->q);
- nxsem_get_value(&wqueue->wake, &semcount);
- if (semcount < 1)
- {
- nxsem_post(&wqueue->wake);
- }
- }
- else
+ if (list_is_head(&wqueue->q, &work->node))
+ {
+ nxsem_get_value(&wqueue->wake, &semcount);
+ if (semcount < 1)
{
- /* Insert the watchdog in mid- or end-of-queue */
-
- dq_addafter(prev, &work->dq, &wqueue->q);
+ nxsem_post(&wqueue->wake);
}
}
diff --git a/libs/libc/wqueue/work_usrthread.c
b/libs/libc/wqueue/work_usrthread.c
index 791cfd3e3e..35aa739582 100644
--- a/libs/libc/wqueue/work_usrthread.c
+++ b/libs/libc/wqueue/work_usrthread.c
@@ -34,7 +34,7 @@
#include <assert.h>
#include <nuttx/clock.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include "wqueue/wqueue.h"
@@ -63,7 +63,7 @@
struct usr_wqueue_s g_usrwork =
{
- {NULL, NULL},
+ LIST_INITIAL_VALUE(g_usrwork.q),
NXMUTEX_INITIALIZER,
SEM_INITIALIZER(0),
};
@@ -91,7 +91,7 @@ struct usr_wqueue_s g_usrwork =
static void work_process(FAR struct usr_wqueue_s *wqueue)
{
- volatile FAR struct work_s *work;
+ FAR struct work_s *work;
worker_t worker;
FAR void *arg;
sclock_t elapsed;
@@ -116,9 +116,10 @@ static void work_process(FAR struct usr_wqueue_s *wqueue)
* so ourselves, and (2) there will be no changes to the work queue
*/
- work = (FAR struct work_s *)wqueue->q.head;
- while (work)
+ while (!list_is_empty(&wqueue->q))
{
+ work = list_first_entry(&wqueue->q, struct work_s, node);
+
/* Is this work ready? It is ready if there is no delay or if
* the delay has elapsed. is the time that the work was added
* to the work queue. Therefore a delay of equal or less than
@@ -133,7 +134,7 @@ static void work_process(FAR struct usr_wqueue_s *wqueue)
{
/* Remove the ready-to-execute work from the list */
- dq_remfirst(&wqueue->q);
+ list_delete(&work->node);
/* Extract the work description from the entry (in case the work
* instance by the re-used after it has been de-queued).
@@ -175,8 +176,6 @@ static void work_process(FAR struct usr_wqueue_s *wqueue)
return;
}
}
-
- work = (FAR struct work_s *)wqueue->q.head;
}
else
{
@@ -287,7 +286,7 @@ int work_usrstart(void)
/* Initialize the work queue */
- dq_init(&g_usrwork.q);
+ list_initialize(&g_usrwork.q);
#ifdef CONFIG_BUILD_PROTECTED
diff --git a/libs/libc/wqueue/wqueue.h b/libs/libc/wqueue/wqueue.h
index c262693b1f..eab017c612 100644
--- a/libs/libc/wqueue/wqueue.h
+++ b/libs/libc/wqueue/wqueue.h
@@ -33,6 +33,7 @@
#include <nuttx/mutex.h>
#include <nuttx/semaphore.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#if defined(CONFIG_LIBC_USRWORK) && !defined(__KERNEL__)
@@ -49,9 +50,9 @@
struct usr_wqueue_s
{
- struct dq_queue_s q; /* The queue of pending work */
- mutex_t lock; /* exclusive access to user-mode work queue */
- sem_t wake; /* The wake-up semaphore of the usrthread */
+ struct list_node q; /* The queue of pending work */
+ mutex_t lock; /* exclusive access to user-mode work queue */
+ sem_t wake; /* The wake-up semaphore of the usrthread */
};
/****************************************************************************
diff --git a/sched/wqueue/kwork_cancel.c b/sched/wqueue/kwork_cancel.c
index 89bec581bd..98d84b8065 100644
--- a/sched/wqueue/kwork_cancel.c
+++ b/sched/wqueue/kwork_cancel.c
@@ -31,7 +31,7 @@
#include <nuttx/irq.h>
#include <nuttx/arch.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include "wqueue/wqueue.h"
@@ -67,10 +67,7 @@ static int work_qcancel(FAR struct kwork_wqueue_s *wqueue,
bool sync,
work->worker = NULL;
wd_cancel(&work->u.timer);
- if (dq_inqueue((FAR dq_entry_t *)work, &wqueue->q))
- {
- dq_rem((FAR dq_entry_t *)work, &wqueue->q);
- }
+ list_delete(&work->node);
ret = OK;
}
diff --git a/sched/wqueue/kwork_queue.c b/sched/wqueue/kwork_queue.c
index 7af8e9800b..5c1f192c8a 100644
--- a/sched/wqueue/kwork_queue.c
+++ b/sched/wqueue/kwork_queue.c
@@ -33,7 +33,7 @@
#include <nuttx/irq.h>
#include <nuttx/arch.h>
#include <nuttx/clock.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include "wqueue/wqueue.h"
@@ -47,7 +47,7 @@
#define queue_work(wqueue, work) \
do \
{ \
- dq_addlast((FAR dq_entry_t *)(work), &(wqueue)->q); \
+ list_add_tail(&(wqueue)->q, &(work)->node); \
if ((wqueue)->wait_count > 0) /* There are threads waiting for sem. */ \
{ \
(wqueue)->wait_count--; \
@@ -165,10 +165,8 @@ int work_queue_period_wq(FAR struct kwork_wqueue_s *wqueue,
work->worker = NULL;
wd_cancel(&work->u.timer);
- if (dq_inqueue((FAR dq_entry_t *)work, &wqueue->q))
- {
- dq_rem((FAR dq_entry_t *)work, &wqueue->q);
- }
+
+ list_delete(&work->node);
}
if (work_is_canceling(wqueue->worker, wqueue->nthreads, work))
diff --git a/sched/wqueue/kwork_thread.c b/sched/wqueue/kwork_thread.c
index 19585f0b28..1320537fde 100644
--- a/sched/wqueue/kwork_thread.c
+++ b/sched/wqueue/kwork_thread.c
@@ -35,7 +35,7 @@
#include <assert.h>
#include <debug.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include <nuttx/kthread.h>
#include <nuttx/semaphore.h>
@@ -83,7 +83,7 @@
struct hp_wqueue_s g_hpwork =
{
- {NULL, NULL},
+ LIST_INITIAL_VALUE(g_hpwork.q),
SEM_INITIALIZER(0),
SEM_INITIALIZER(0),
SP_UNLOCKED,
@@ -97,7 +97,7 @@ struct hp_wqueue_s g_hpwork =
struct lp_wqueue_s g_lpwork =
{
- {NULL, NULL},
+ LIST_INITIAL_VALUE(g_lpwork.q),
SEM_INITIALIZER(0),
SEM_INITIALIZER(0),
SP_UNLOCKED,
@@ -162,8 +162,12 @@ static int work_thread(int argc, FAR char *argv[])
/* Remove the ready-to-execute work from the list */
- while ((work = (FAR struct work_s *)dq_remfirst(&wqueue->q)) != NULL)
+ while (!list_is_empty(&wqueue->q))
{
+ work = list_first_entry(&wqueue->q, struct work_s, node);
+
+ list_delete(&work->node);
+
if (work->worker == NULL)
{
continue;
@@ -345,7 +349,7 @@ FAR struct kwork_wqueue_s *work_queue_create(FAR const char
*name,
/* Initialize the work queue structure */
- dq_init(&wqueue->q);
+ list_initialize(&wqueue->q);
nxsem_init(&wqueue->sem, 0, 0);
nxsem_init(&wqueue->exsem, 0, 0);
wqueue->nthreads = nthreads;
diff --git a/sched/wqueue/wqueue.h b/sched/wqueue/wqueue.h
index 7d36cf0d9b..b9a6f1ceb2 100644
--- a/sched/wqueue/wqueue.h
+++ b/sched/wqueue/wqueue.h
@@ -33,7 +33,7 @@
#include <stdbool.h>
#include <nuttx/clock.h>
-#include <nuttx/queue.h>
+#include <nuttx/list.h>
#include <nuttx/wqueue.h>
#include <nuttx/spinlock.h>
@@ -66,7 +66,7 @@ struct kworker_s
struct kwork_wqueue_s
{
- struct dq_queue_s q; /* The queue of pending work */
+ struct list_node q; /* The queue of pending work */
sem_t sem; /* The counting semaphore of the wqueue */
sem_t exsem; /* Sync waiting for thread exit */
spinlock_t lock; /* Spinlock */
@@ -83,7 +83,7 @@ struct kwork_wqueue_s
#ifdef CONFIG_SCHED_HPWORK
struct hp_wqueue_s
{
- struct dq_queue_s q; /* The queue of pending work */
+ struct list_node q; /* The queue of pending work */
sem_t sem; /* The counting semaphore of the wqueue */
sem_t exsem; /* Sync waiting for thread exit */
spinlock_t lock; /* Spinlock */
@@ -104,7 +104,7 @@ struct hp_wqueue_s
#ifdef CONFIG_SCHED_LPWORK
struct lp_wqueue_s
{
- struct dq_queue_s q; /* The queue of pending work */
+ struct list_node q; /* The queue of pending work */
sem_t sem; /* The counting semaphore of the wqueue */
sem_t exsem; /* Sync waiting for thread exit */
spinlock_t lock; /* Spinlock */
