CV-Bowen opened a new pull request, #22009:
URL: https://github.com/apache/nuttx/pull/22009
## Summary
Add `include/nuttx/mpsc.h`, an intrusive multi-producer/single-consumer
lock-free linked-list queue based on Dmitry Vyukov's stub-sentinel
algorithm.
- Producers serialise through one atomic exchange on the tail; enqueue is
wait-free (one release xchg plus one release store), with local IRQs
disabled across that two-step publish to bound the same-core transient
window.
- The consumer walks from head; dequeue is lock-free, one acquire load in
the common case, and re-enqueues the embedded stub when the list is about
to drain. Returning NULL means empty *or* a producer mid-publish;
`mpsc_dequeue_spin()` / `mpsc_dequeue_yield()` hide the transient and
return NULL only when the queue is genuinely empty.
- `MPSC_INIT` / `MPSC_DEFINE` / `MPSC_DECLARE`, nodes embedded in the user
structure and recovered with `container_of()`, descriptor cache-line
padded so the producer-shared tail and consumer-private head do not share
a line.
There is no in-tree user yet.
`include/nuttx/mpsc.h: report empty only when the stub is the only node`
fixes `mpsc_empty()`, which reported empty one node early: it compared the
consumer cursor with the tail, and `mpsc_dequeue()` leaves `head` on the
node after the one it returns. With four nodes queued, `mpsc_empty()`
returned true after three dequeues while the fourth node was still
dequeueable, so `mpsc_dequeue_spin()`/`mpsc_dequeue_yield()` could return
NULL one node early. The queue is empty only once the consumer is back on
the stub and no producer is mid-publish.
Depends on #21843 (`atomic_ptr_t`) and #21895 (`irq_save`/`irq_restore`),
both merged.
## Impact
New header only; nothing includes it yet. No Kconfig, build or ABI change
to existing code.
## Testing
Host: Ubuntu 22.04.5 LTS x86_64; sim: gcc 13.1.0; qemu-armv8a:
aarch64-none-elf-gcc 12.2.1, QEMU 10.2.1
No in-tree user, so the queue was exercised by a probe that temporarily
replaced `apps/testing/libc/atomic/atomic_main.c` (not part of this PR).
It checks, single-threaded, empty/enqueue/dequeue ordering, that the stub
is recycled and the queue stays reusable, and that `mpsc_empty()` reports
empty exactly when the last node has been returned; then runs 4 producers
of 4000 nodes each against one consumer, verifying all 16000 nodes come
out, per-producer FIFO order holds, and the drain signal from all four
producers is observed.
| tree | result |
|---|---|
| master + commit 1 only | `FAIL line 59: !mpsc_empty(&q)` after the third
of four dequeues; probe reports 1 failure |
| master + this PR | 0 failures, `drained 16000/16000` |
`CONFIG_TESTING_ATOMIC=y` on `sim:nsh`:
```
./nuttx
nsh> atomic
```
<details><summary>Probe source (drop-in for
testing/libc/atomic/atomic_main.c)</summary>
```c
/* Out-of-tree probe for include/nuttx/mpsc.h (replaces atomic_main.c).
*
* Two parts: single-threaded FIFO and stub-recycling checks, then an
* M-producer / 1-consumer stress run.
*/
#include <nuttx/config.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <stdint.h>
#include <pthread.h>
#include <unistd.h>
#include <nuttx/mpsc.h>
#define NPROD 4
#define PER_PROD 4000
#define TOTAL (NPROD * PER_PROD)
static int g_fail;
#define CHECK(c) \
do { if (!(c)) { printf("FAIL line %d: %s\n", __LINE__, #c); g_fail++; } }
while (0)
struct item_s
{
struct mpsc_node_s node;
unsigned int prod;
unsigned int seq;
};
/* ---------------------------------------------------------------------- */
static void test_single_thread(void)
{
static struct mpsc_queue_s q = MPSC_INIT(q);
static struct item_s items[4];
FAR struct mpsc_node_s *n;
int i;
CHECK(mpsc_empty(&q));
CHECK(mpsc_dequeue(&q) == NULL);
CHECK(mpsc_empty(&q));
for (i = 0; i < 4; i++)
{
mpsc_enqueue(&q, &items[i].node);
CHECK(!mpsc_empty(&q));
}
for (i = 0; i < 4; i++)
{
n = mpsc_dequeue(&q);
CHECK(n == &items[i].node);
if (i < 3)
{
CHECK(!mpsc_empty(&q));
}
}
/* All four consumed: the queue is empty again. */
CHECK(mpsc_empty(&q));
CHECK(mpsc_dequeue(&q) == NULL);
CHECK(mpsc_empty(&q));
/* Interleaved: enqueue after a drain must still be FIFO. */
mpsc_enqueue(&q, &items[0].node);
CHECK(mpsc_dequeue(&q) == &items[0].node);
mpsc_enqueue(&q, &items[1].node);
mpsc_enqueue(&q, &items[2].node);
CHECK(mpsc_dequeue_spin(&q) == &items[1].node);
CHECK(mpsc_dequeue_yield(&q) == &items[2].node);
CHECK(mpsc_dequeue_yield(&q) == NULL);
}
/* ---------------------------------------------------------------------- */
static struct mpsc_queue_s g_q = MPSC_INIT(g_q);
static struct item_s g_items[TOTAL];
static volatile int g_start;
static volatile int g_done;
static FAR void *producer(FAR void *arg)
{
unsigned int prod = (unsigned int)(uintptr_t)arg;
struct item_s *it = &g_items[prod * PER_PROD];
int i;
while (!g_start)
{
sched_yield();
}
for (i = 0; i < PER_PROD; i++)
{
it[i].prod = prod;
it[i].seq = i;
mpsc_enqueue(&g_q, &it[i].node);
}
__atomic_add_fetch(&g_done, 1, __ATOMIC_SEQ_CST);
return NULL;
}
static void test_multi_producer(void)
{
pthread_t th[NPROD];
unsigned int next[NPROD];
FAR struct mpsc_node_s *node;
struct item_s *it;
int drained = 0;
int idle = 0;
int i;
memset(next, 0, sizeof(next));
g_start = 0;
g_done = 0;
for (i = 0; i < NPROD; i++)
{
CHECK(pthread_create(&th[i], NULL, producer,
(FAR void *)(uintptr_t)i) == 0);
}
g_start = 1;
while (drained < TOTAL)
{
node = mpsc_dequeue(&g_q);
it = (FAR struct item_s *)node;
if (it == NULL)
{
/* Retry while a producer may still be running; give up only
* once every producer has finished and the queue stayed empty.
*/
if (__atomic_load_n(&g_done, __ATOMIC_SEQ_CST) == NPROD &&
++idle > 100000)
{
break;
}
if (__atomic_load_n(&g_done, __ATOMIC_SEQ_CST) < NPROD)
{
idle = 0;
sched_yield();
}
continue;
}
idle = 0;
drained++;
/* Per-producer FIFO must be preserved */
if (it->prod >= NPROD || it->seq != next[it->prod])
{
printf("FAIL order: prod=%u seq=%u expected=%u\n",
it->prod, it->seq, next[it->prod]);
g_fail++;
break;
}
next[it->prod] = it->seq + 1;
}
printf("drained %d/%d\n", drained, TOTAL);
CHECK(drained == TOTAL);
for (i = 0; i < NPROD; i++)
{
CHECK(next[i] == PER_PROD);
pthread_join(th[i], NULL);
}
/* Drain must leave the queue empty and reusable. */
CHECK(mpsc_dequeue(&g_q) == NULL);
CHECK(mpsc_empty(&g_q));
mpsc_enqueue(&g_q, &g_items[0].node);
CHECK(mpsc_dequeue(&g_q) == &g_items[0].node);
}
/* ---------------------------------------------------------------------- */
int main(int argc, FAR char *argv[])
{
printf("sizeof(struct mpsc_queue_s)=%zu\n", sizeof(struct mpsc_queue_s));
test_single_thread();
test_multi_producer();
printf("mpsc probe: %s (%d failures)\n", g_fail ? "FAIL" : "PASS", g_fail);
return g_fail;
}
```
</details>
<details><summary>Output with commit 1 only</summary>
```
sizeof(struct mpsc_queue_s)=192
FAIL line 59: !mpsc_empty(&q)
drained 16000/16000
mpsc probe: FAIL (1 failures)
```
</details>
<details><summary>Output with this PR</summary>
```
sizeof(struct mpsc_queue_s)=192
drained 16000/16000
mpsc probe: PASS (0 failures)
```
</details>
No regression in rpmsg: sim:rpserver/rpproxy and
qemu-armv8a:rpserver/rpproxy boot and pass the fixed rpmsg cases (dump, ping,
rpmsgfs; 15/15). qemu-armv8a was built with LIBC_ENVPATH and BINFMT_CHECKEXEC
disabled, which current master needs for nxinit to start nsh there; unrelated
to this change.
--
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]