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]

Reply via email to