• How to write a semaphore with futexes

    From Bonita Montero@Bonita.Montero@gmail.com to comp.lang.c++ on Tue Nov 10 17:40:58 2026
    From Newsgroup: comp.lang.c++

    I wanted to write a semaphore with a futex. I incremented a counter
    and did the notify. Oh the other side I did a wait and after the wait
    I do a decrement of the counter if it was non-zero, otherwise I wait
    again.
    The problem with that is that is that I want to wake up another thread
    and immediatly wait on the same semaphore on the notifying side it's
    very likely that the notifying thread eats up its own notify and the
    other thread doesn't consume the notify. This doesn't happen with com-
    pletely kernel-managed semaphores.
    So it is possible to write a semaphore with a futex without this limi-
    tation ?
    And: Chris, this isn't a question eligible for short-circuited toughts.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Tue Nov 10 13:32:04 2026
    From Newsgroup: comp.lang.c++

    On 11/10/2026 8:40 AM, Bonita Montero wrote:
    I wanted to write a semaphore with a futex. I incremented a counter
    and did the notify. Oh the other side I did a wait and after the wait
    I do a decrement of the counter if it was non-zero, otherwise I wait
    again.
    The problem with that is that is that I want to wake up another thread
    and immediatly wait on the same semaphore on the notifying side it's
    very likely that the notifying thread eats up its own notify and the
    other thread doesn't consume the notify. This doesn't happen with com- pletely kernel-managed semaphores.
    So it is possible to write a semaphore with a futex without this limi-
    tation ?
    And: Chris, this isn't a question eligible for short-circuited toughts.


    Fwiw, why not use a kernel semaphore as a slow path? Is this just for fun?
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Bonita Montero@Bonita.Montero@gmail.com to comp.lang.c++ on Wed Nov 11 08:06:25 2026
    From Newsgroup: comp.lang.c++

    Am 10.11.2026 um 22:32 schrieb Chris M. Thomasson:

    Fwiw, why not use a kernel semaphore as a slow path? Is this just for fun?

    Because signalling or waiting on a semaphore can fail, whereas a futex
    only has invalid parameters error codes. I need a solution that is like
    a futes in that sense.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Wed Nov 11 14:12:59 2026
    From Newsgroup: comp.lang.c++

    On 11/10/2026 11:06 PM, Bonita Montero wrote:
    Am 10.11.2026 um 22:32 schrieb Chris M. Thomasson:

    Fwiw, why not use a kernel semaphore as a slow path? Is this just for
    fun?

    Because signalling or waiting on a semaphore can fail, whereas a futex
    only has invalid parameters error codes. I need a solution that is like
    a futes in that sense.


    I see. A fun failure on a sem_wait is EINTR.

    https://pubs.opengroup.org/onlinepubs/007908799/xsh/sem_wait.html

    I have seen a lot of code that fails to handle it.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Wed Nov 11 14:15:37 2026
    From Newsgroup: comp.lang.c++

    On 11/10/2026 11:06 PM, Bonita Montero wrote:
    Am 10.11.2026 um 22:32 schrieb Chris M. Thomasson:

    Fwiw, why not use a kernel semaphore as a slow path? Is this just for
    fun?

    Because signalling or waiting on a semaphore can fail, whereas a futex
    only has invalid parameters error codes. I need a solution that is like
    a futes in that sense.


    Iirc, Joe had some rather neat logic for a cancel on a benaphore. This
    was around 20 years ago... God, I wonder if I can find the post over on
    c.p.t I might look for it later on tonight.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Bonita Montero@Bonita.Montero@gmail.com to comp.lang.c++ on Wed Nov 11 23:47:05 2026
    From Newsgroup: comp.lang.c++

    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Wed Nov 11 15:05:43 2026
    From Newsgroup: comp.lang.c++

    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    About resources, if the futex is using a multex for the slow path it
    would never run out of resources simply because they are created up
    front before anything in the user program runs, or a large one in the
    kernel at os boot. For a futex slow path they, on some impls I have
    seen, hash the address into an index for a kernel object, a wait queue
    iirc. Akin to the multex hashing addresses into mutexes.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From boltar@boltar@caprica.universe to comp.lang.c++ on Thu Nov 12 16:41:06 2026
    From Newsgroup: comp.lang.c++

    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar function frankly deserves what they get.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Ross Finlayson@ross.a.finlayson@gmail.com to comp.lang.c++ on Thu Nov 12 11:35:24 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar function frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(), push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and using conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and pop_front, that should return an error if EWOULDBLOCK, then that it can
    park in a syscall when the queue's empty, so that it idles in park with
    0% CPU. Then pushing items onto the queue should change it back to non-blocking.

    So, when it's running it should be un-blocked, and appends must be non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.




    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Thu Nov 12 11:59:48 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    Now. For a FIFO reversing the XCHG, done. Now, there is the classic MPMC
    lock free queue. Iirc, I think there is a way to specialize it on the
    single consumer case.

    To make this be able to wait, ahh... The wonderful eventcount comes into
    play here. It can be created with a futex or other means. Its basically
    a "condition variable" for lock/wait-free.

    Have you ever used them before?



    push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and using conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and pop_front, that should return an error if EWOULDBLOCK, then that it can
    park in a syscall when the queue's empty, so that it idles in park with
    0% CPU. Then pushing items onto the queue should change it back to non-blocking.

    So, when it's running it should be un-blocked, and appends must be non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.






    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Thu Nov 12 12:05:37 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now, this
    can get almost "too" much work for a thread that pops a huge number of
    nodes. But, we can distribute the MPSC to try to balance the load. Using
    a single XCHG for the single consumer is basically the best we can get.




    Now. For a FIFO reversing the XCHG, done. Now, there is the classic MPMC lock free queue. Iirc, I think there is a way to specialize it on the
    single consumer case.

    To make this be able to wait, ahh... The wonderful eventcount comes into play here. It can be created with a futex or other means. Its basically
    a "condition variable" for lock/wait-free.

    Have you ever used them before?



    push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and using
    conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and
    pop_front, that should return an error if EWOULDBLOCK, then that it can
    park in a syscall when the queue's empty, so that it idles in park with
    0% CPU. Then pushing items onto the queue should change it back to
    non-blocking.

    So, when it's running it should be un-blocked, and appends must be
    non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.







    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Ross Finlayson@ross.a.finlayson@gmail.com to comp.lang.c++ on Thu Nov 12 13:40:03 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 12:05 PM, Chris M. Thomasson wrote:
    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now, this
    can get almost "too" much work for a thread that pops a huge number of
    nodes. But, we can distribute the MPSC to try to balance the load. Using
    a single XCHG for the single consumer is basically the best we can get.




    Now. For a FIFO reversing the XCHG, done. Now, there is the classic
    MPMC lock free queue. Iirc, I think there is a way to specialize it on
    the single consumer case.

    To make this be able to wait, ahh... The wonderful eventcount comes
    into play here. It can be created with a futex or other means. Its
    basically a "condition variable" for lock/wait-free.

    Have you ever used them before?



    push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and using >>> conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and
    pop_front, that should return an error if EWOULDBLOCK, then that it can
    park in a syscall when the queue's empty, so that it idles in park with
    0% CPU. Then pushing items onto the queue should change it back to
    non-blocking.

    So, when it's running it should be un-blocked, and appends must be
    non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.









    Hm. There are 1000 "logical" producers, subjects, say, of a topic,
    from 3 or 4 threads, and it's usually figured that these will all
    be pinned to one core, since the idea is that the entire process they're
    in has thusly affinity of their memory, and that the process-group
    scales in processes about kernel resources per-process
    and these kinds of things.

    It's figured that items are 64B or 128B, i.e., cache-lines or
    cache-lines-pairs size, and that the heap backing the queue is of 4KiB
    i.e. PAGE_SIZE size pages. Or, the items may be larger, yet, fixed-size.


    It's only a FIFO, so, there's only push (push_back) and pop (pop_front) relevant.

    The queue may grow or is unbounded, bounded by RAM, in user-space,
    it's not a ring buffer.

    When there's activity on the system, the queue will likely be non-empty,
    yet when the activity is low, it can go in and out of idle.
    When the activity is idle, it shall block in park and not be scheduled
    by the CPU, the single thread that consumes it.



    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Ross Finlayson@ross.a.finlayson@gmail.com to comp.lang.c++ on Thu Nov 12 17:37:51 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 01:40 PM, Ross Finlayson wrote:
    On 11/12/2026 12:05 PM, Chris M. Thomasson wrote:
    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now, this
    can get almost "too" much work for a thread that pops a huge number of
    nodes. But, we can distribute the MPSC to try to balance the load. Using
    a single XCHG for the single consumer is basically the best we can get.




    Now. For a FIFO reversing the XCHG, done. Now, there is the classic
    MPMC lock free queue. Iirc, I think there is a way to specialize it on
    the single consumer case.

    To make this be able to wait, ahh... The wonderful eventcount comes
    into play here. It can be created with a futex or other means. Its
    basically a "condition variable" for lock/wait-free.

    Have you ever used them before?



    push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and
    using
    conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and
    pop_front, that should return an error if EWOULDBLOCK, then that it can >>>> park in a syscall when the queue's empty, so that it idles in park with >>>> 0% CPU. Then pushing items onto the queue should change it back to
    non-blocking.

    So, when it's running it should be un-blocked, and appends must be
    non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.









    Hm. There are 1000 "logical" producers, subjects, say, of a topic,
    from 3 or 4 threads, and it's usually figured that these will all
    be pinned to one core, since the idea is that the entire process they're
    in has thusly affinity of their memory, and that the process-group
    scales in processes about kernel resources per-process
    and these kinds of things.

    It's figured that items are 64B or 128B, i.e., cache-lines or cache-lines-pairs size, and that the heap backing the queue is of 4KiB
    i.e. PAGE_SIZE size pages. Or, the items may be larger, yet, fixed-size.


    It's only a FIFO, so, there's only push (push_back) and pop (pop_front) relevant.

    The queue may grow or is unbounded, bounded by RAM, in user-space,
    it's not a ring buffer.

    When there's activity on the system, the queue will likely be non-empty,
    yet when the activity is low, it can go in and out of idle.
    When the activity is idle, it shall block in park and not be scheduled
    by the CPU, the single thread that consumes it.




    I figure it can be a POSIX pipe (this is the target) with depth 1,
    non-blocking on the put side and ignoring errors, blocking on the
    get side and shifting out of park, producers push to the queue and push
    to the pipe, consumer pops the queue then parks on the pipe, pretty simple.

    Then another one is an SPSC queue, and an array of those, say 1000-wide,
    a queue of PAGE_SIZE buffers with perhaps a tag of timestamp, reading
    those from the network then decrypting and
    decompressing them then incremental-parsing them, then, to pop
    those off, yet, that's the same thread on both sides so it doesn't
    need any synchronization at all.



    These days it's all the rage this "io_uring" since "epoll",
    idea seeming to be "let's get these naughty syscalls out
    of our code and just shove it right in the kernel, now we're
    blazing fast", and, it's like, that's squeezing the balloon.
    And it's like, "so, what happens when limits that b.t.w. the
    kernel doesn't advertise" and it's like, "oh, they just get
    dropped, that's a kernel problem not our code". Hmm....



    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From boltar@boltar@caprica.universe to comp.lang.c++ on Fri Nov 13 10:07:24 2026
    From Newsgroup: comp.lang.c++

    On Thu, 12 Nov 2026 11:35:24 -0800
    Ross Finlayson <ross.a.finlayson@gmail.com> gabbled:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar function >> frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(), >push_back, pretty much must use compare-and-swap the only atomic

    Blah blah.

    Sorry, what's your point exactly? That people shouldn't bother reading the
    man page about a function or whatever other documentation is available before they try to use it?

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Ross Finlayson@ross.a.finlayson@gmail.com to comp.lang.c++ on Fri Nov 13 04:50:08 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 02:07 AM, boltar@caprica.universe wrote:
    On Thu, 12 Nov 2026 11:35:24 -0800
    Ross Finlayson <ross.a.finlayson@gmail.com> gabbled:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),
    push_back, pretty much must use compare-and-swap the only atomic

    Blah blah.

    Sorry, what's your point exactly? That people shouldn't bother reading the man page about a function or whatever other documentation is available
    before
    they try to use it?


    Ah, good old linear thinking.

    Basically looking to make sense of the great circle of things,
    of course a lot depends on "the stability of fact", vis-a-vis
    something like Magritte's "The Treachery of Images" vis-a-vis
    "The Empire of Light", point being that I've already read the
    man pages most of them. (Man pages, RFC's, standards & specifications,
    like from ITU and ISO.)

    So, my point is a sort of retro approach to simple and practical
    systems, to live in a world of modern systems, since the logical
    and abstract is about things like "C, C++, and POSIX", in a world
    of "many-core hyper-virtualized containerized boxes", and about
    things like "Internet protocols" and "distributed systems".


    The idea is to write what are of the good old specifications
    in the good old code, with modern expectations of the runtime.

    Then, the code should also be well-designed and written from
    the beginning to cover the relevant surface of the runtime,
    while having the nice abstraction and these sorts of things.


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Ross Finlayson@ross.a.finlayson@gmail.com to comp.lang.c++ on Fri Nov 13 05:49:24 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 04:50 AM, Ross Finlayson wrote:
    On 11/13/2026 02:07 AM, boltar@caprica.universe wrote:
    On Thu, 12 Nov 2026 11:35:24 -0800
    Ross Finlayson <ross.a.finlayson@gmail.com> gabbled:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),
    push_back, pretty much must use compare-and-swap the only atomic

    Blah blah.

    Sorry, what's your point exactly? That people shouldn't bother reading
    the
    man page about a function or whatever other documentation is available
    before
    they try to use it?


    Ah, good old linear thinking.

    Basically looking to make sense of the great circle of things,
    of course a lot depends on "the stability of fact", vis-a-vis
    something like Magritte's "The Treachery of Images" vis-a-vis
    "The Empire of Light", point being that I've already read the
    man pages most of them. (Man pages, RFC's, standards & specifications,
    like from ITU and ISO.)

    So, my point is a sort of retro approach to simple and practical
    systems, to live in a world of modern systems, since the logical
    and abstract is about things like "C, C++, and POSIX", in a world
    of "many-core hyper-virtualized containerized boxes", and about
    things like "Internet protocols" and "distributed systems".


    The idea is to write what are of the good old specifications
    in the good old code, with modern expectations of the runtime.

    Then, the code should also be well-designed and written from
    the beginning to cover the relevant surface of the runtime,
    while having the nice abstraction and these sorts of things.



    Of course "the only current documentation is the source",
    and it's so that anybody who ever ran doxygen on their code
    the first time were probably very happy with their results,
    about things like "literate programming", and "thinking like
    a library author", that the "code understanding" is much
    facilitated by elegant, declarative, purposeful code,
    that said what I'm interested in are reference implementations
    of standards in a composable way, that happen for example to
    be demonstrably complete and making best use of the resources
    responsibly. "Good actors."




    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Joseph Seigh@jseigh_es00@xemaps.com to comp.lang.c++ on Fri Nov 13 09:44:25 2026
    From Newsgroup: comp.lang.c++

    On 11/12/26 3:05 PM, Chris M. Thomasson wrote:
    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:


    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now, this
    can get almost "too" much work for a thread that pops a huge number of nodes. But, we can distribute the MPSC to try to balance the load. Using
    a single XCHG for the single consumer is basically the best we can get.


    You don't need to do an XCHG. You have a single consumer. It owns the
    queue. It just needs to do a load of the queue tail pointer and just
    process the queue. Of course it needs to keep track of things like the
    last tail pointer value it read so it knows when it has processed all
    the new nodes. It may also want to defer deallocating the node
    referenced by the tail pointer to avoid the ABA problem.

    You could do the XCHG if you wanted a way for the consumer to indicate
    it was going to block and needed to be woken up. There are other
    ways that don't need this logic so it's a design choice.



    Now. For a FIFO reversing the XCHG, done. Now, there is the classic
    MPMC lock free queue. Iirc, I think there is a way to specialize it on
    the single consumer case.

    It's unlikely anyone has program logic that requires FIFO, what little
    of it is actually observable. You really care about forward progress guarantees. As long as the consumer keeps up with the producers, you
    should be ok doing batches in LIFO order. If not, you have other
    problems.

    And if you drop the FIFO requirement then you could just have multiple consumers doing XCHG on the queue tail pointer.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From boltar@boltar@caprica.universe to comp.lang.c++ on Fri Nov 13 15:46:32 2026
    From Newsgroup: comp.lang.c++

    On Fri, 13 Nov 2026 04:50:08 -0800
    Ross Finlayson <ross.a.finlayson@gmail.com> gabbled:
    On 11/13/2026 02:07 AM, boltar@caprica.universe wrote:
    Sorry, what's your point exactly? That people shouldn't bother reading the >> man page about a function or whatever other documentation is available
    before
    they try to use it?


    Ah, good old linear thinking.

    Basically looking to make sense of the great circle of things,
    of course a lot depends on "the stability of fact", vis-a-vis
    something like Magritte's "The Treachery of Images" vis-a-vis

    Spare us your cut and pasted AI slop.


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 15:12:37 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    On 11/12/26 3:05 PM, Chris M. Thomasson wrote:
    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:


    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now,
    this can get almost "too" much work for a thread that pops a huge
    number of nodes. But, we can distribute the MPSC to try to balance the
    load. Using a single XCHG for the single consumer is basically the
    best we can get.


    You don't need to do an XCHG.-a You have a single consumer.-a It owns the queue.-a It just needs to do a load of the queue tail pointer and just process the queue.-a Of course it needs to keep track of things like the
    last tail pointer value it read so it knows when it has processed all
    the new nodes.-a It may also want to defer deallocating the node
    referenced by the tail pointer to avoid the ABA problem.

    That should work fine. Well, I need to take another look at:

    https://cs.rochester.edu/research/synchronization/pseudocode/queues.html


    You could do the XCHG if you wanted a way for the consumer to indicate
    it was going to block and needed to be woken up.-a There are other
    ways that don't need this logic so it's a design choice.

    Big time! Eventcounts are fun. Actually, a futex itself might be able to
    be used here.


    Now. For a FIFO reversing the XCHG, done. Now, there is the classic
    MPMC lock free queue. Iirc, I think there is a way to specialize it
    on the single consumer case.

    It's unlikely anyone has program logic that requires FIFO, what little
    of it is actually observable.-a You really care about forward progress guarantees.-a As long as the consumer keeps up with the producers, you
    should be ok doing batches in LIFO order.-a If not, you have other
    problems.

    True.


    And if you drop the FIFO requirement then you could just have multiple consumers doing XCHG on the queue tail pointer.

    That's ideal.

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 15:16:58 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    [...]

    I have not had time to search for your interesting old cancel method for
    the fast semaphore on c.p.t, basically a benaphore iirc. Can you find it?
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 15:18:52 2026
    From Newsgroup: comp.lang.c++

    On 11/12/2026 1:40 PM, Ross Finlayson wrote:
    On 11/12/2026 12:05 PM, Chris M. Thomasson wrote:
    On 11/12/2026 11:59 AM, Chris M. Thomasson wrote:
    On 11/12/2026 11:35 AM, Ross Finlayson wrote:
    On 11/12/2026 08:41 AM, boltar@caprica.universe wrote:
    On Wed, 11 Nov 2026 15:05:43 -0800
    "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com> gabbled:
    On 11/11/2026 2:47 PM, Bonita Montero wrote:
    Am 11.11.2026 um 23:12 schrieb Chris M. Thomasson:

    I see. A fun failure on a sem_wait is EINTR.

    That's not a out of recources error and it is recoverable.

    Its scary though when people fail to know about it.

    Anyone who doesn't read the man page before they use an unfamiliar
    function
    frankly deserves what they get.



    Here's one for you.

    So, I want a MPSC queue, multiple-producer single-consumer queue,
    producers on the order of 1000, with that appends to the queue push(),

    A 1000? You have a 1000 cores handy? ;^)

    Fwiw, a MPSC LIFO is pretty straightforward. A CAS for the push and a
    single XCHG for the pop. Adding multiple nodes is easy. push the head
    and tail.

    I should clarify that a single XCHG for the pop is basically flushing
    the whole list. But its easy. So, if that works for you fine. Now, this
    can get almost "too" much work for a thread that pops a huge number of
    nodes. But, we can distribute the MPSC to try to balance the load. Using
    a single XCHG for the single consumer is basically the best we can get.




    Now. For a FIFO reversing the XCHG, done. Now, there is the classic
    MPMC lock free queue. Iirc, I think there is a way to specialize it on
    the single consumer case.

    To make this be able to wait, ahh... The wonderful eventcount comes
    into play here. It can be created with a futex or other means. Its
    basically a "condition variable" for lock/wait-free.

    Have you ever used them before?



    push_back, pretty much must use compare-and-swap the only atomic
    primitive on the chip, though for example with having a buffer and
    using
    conditional-move after compare-and-swap to copy items into the buffer
    then appending multiple items from the buffer atomically. Then, the
    consumer, should have a non-blocking peek() and pop(), peek_front and
    pop_front, that should return an error if EWOULDBLOCK, then that it can >>>> park in a syscall when the queue's empty, so that it idles in park with >>>> 0% CPU. Then pushing items onto the queue should change it back to
    non-blocking.

    So, when it's running it should be un-blocked, and appends must be
    non-blocking, when it's empty, then it should block to "park".

    In C and C++ and in POSIX, how's this.









    Hm. There are 1000 "logical" producers, subjects, say, of a topic,
    from 3 or 4 threads, and it's usually figured that these will all
    be pinned to one core, since the idea is that the entire process they're
    in has thusly affinity of their memory, and that the process-group
    scales in processes about kernel resources per-process
    and these kinds of things.

    It's figured that items are 64B or 128B, i.e., cache-lines or cache-lines-pairs size, and that the heap backing the queue is of 4KiB
    i.e. PAGE_SIZE size pages. Or, the items may be larger, yet, fixed-size.


    It's only a FIFO, so, there's only push (push_back) and pop (pop_front) relevant.

    The queue may grow or is unbounded, bounded by RAM, in user-space,
    it's not a ring buffer.

    When there's activity on the system, the queue will likely be non-empty,
    yet when the activity is low, it can go in and out of idle.
    When the activity is idle, it shall block in park and not be scheduled
    by the CPU, the single thread that consumes it.




    An eventcount would work for you there. Or perhaps a raw futex, that is
    more low level.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 15:33:13 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    [...]
    And if you drop the FIFO requirement then you could just have multiple consumers doing XCHG on the queue tail pointer.


    Fwiw, here is some older experimental code of mine for a waitable lifo
    using a futex. I never had the time to code it up in Relacy:

    This is a little C++20 test using a futex to allow one to wait on a
    lock-free stack. The main stack logic is in struct ct_stack. Well, can
    you get to compile and run? Thanks...

    I still need to check my algorithm out in Relacy. I think it might be
    able to model futex.


    My code:
    ______________________________________
    #include <iostream>
    #include <thread>
    #include <atomic>
    #include <algorithm>
    #include <cassert>


    #define CT_THREAD_N (42)
    #define CT_WORK_N (10000000)
    #define CT_WAIT ((ct_node*)0xDEADBEEF)


    struct ct_node
    {
    ct_node* m_next = { nullptr };

    ct_node()
    {
    //std::cout << "(" << this << ")::ct_node::ct_node()\n";
    }

    ~ct_node()
    {
    //std::cout << "(" << this << ")::ct_node::~ct_node()\n";
    }
    };


    struct ct_stack
    {
    std::atomic<ct_node*> m_head = { nullptr };

    void
    push(
    ct_node* node
    ) {
    ct_node* head = m_head.load(std::memory_order_relaxed);

    do
    {
    if (head == CT_WAIT)
    {
    node->m_next = nullptr;
    }

    else
    {
    node->m_next = head;
    }

    } while (! m_head.compare_exchange_weak(
    head,
    node,
    std::memory_order_release)
    );

    if (head == CT_WAIT)
    {
    // slow path...
    m_head.notify_one();
    }
    }

    ct_node*
    flush_wait()
    {
    ct_node* head = nullptr;

    for (;;)
    {
    head = m_head.exchange(nullptr, std::memory_order_acquire);

    while (! head || head == CT_WAIT)
    {
    // slow path...
    head = m_head.exchange(CT_WAIT, std::memory_order_acquire);

    if (! head || head == CT_WAIT)
    {
    m_head.wait(CT_WAIT, std::memory_order_relaxed);
    continue;
    }
    }

    break;
    }

    assert(head && head != CT_WAIT);

    return head;
    }
    };


    struct ct_work : public ct_node
    {
    unsigned long m_state = { 0 };
    };


    struct ct_shared
    {
    ct_stack m_stack_in;
    ct_stack m_stack_out;

    ct_shared()
    {
    std::cout << "ct_shared::ct_shared()\n" << std::endl;
    }

    ~ct_shared()
    {
    assert(! m_stack_in.m_head || m_stack_in.m_head == CT_WAIT);
    assert(! m_stack_out.m_head || m_stack_out.m_head == CT_WAIT);

    std::cout << "ct_shared::~ct_shared()\n" << std::endl;
    }
    };


    void
    ct_thread(
    ct_shared& shared
    ) {
    unsigned long state = 0;

    while (! state)
    {
    ct_work* head = (ct_work*)shared.m_stack_in.flush_wait();

    while (head)
    {
    ct_work* next = (ct_work*)head->m_next;

    if (head->m_state == 666)
    {
    // Shutdown detected...
    state = 1;
    shared.m_stack_in.push(head);
    }

    else
    {
    shared.m_stack_out.push(head);
    }

    head = next;
    }
    }

    //std::cout << "shutdown..." << std::endl;
    }


    int
    main()
    {
    {
    std::cout << "Futex Stack Test\n";
    std::cout << "by: Chris M. Thomasson\n";
    std::cout << "version: (0.0.1)\n";
    std::cout << "_________________________________\n" << std::endl;
    }

    unsigned long g_ct_work_alloations = 0;
    unsigned long g_ct_work_dealloations = 0;

    {
    std::cout << "CT_THREAD_N = " << CT_THREAD_N << std::endl;
    std::cout << "CT_WORK_N = " << CT_WORK_N << std::endl;
    std::cout << "CT_WAIT = " << CT_WAIT << std::endl;
    }

    {
    ct_shared shared = { };

    std::thread threads[CT_THREAD_N];

    std::cout << "\nLaunching threads...\n" << std::endl;

    for (unsigned long i = 0; i < CT_THREAD_N; ++i)
    {
    threads[i] = std::thread(ct_thread, std::ref(shared));
    }

    //std::this_thread::sleep_for(std::chrono::seconds(2));

    std::cout << "\nGenerate work...\n" << std::endl;

    // Generate work...
    {
    for (unsigned long i = 0; i < CT_WORK_N; ++i)
    {
    shared.m_stack_in.push(new ct_work);
    ++g_ct_work_alloations;
    }
    }

    // Wait for work...
    {
    unsigned long wn = 0;

    while (wn < CT_WORK_N)
    {
    ct_work* head = (ct_work*)shared.m_stack_out.flush_wait();

    while (head)
    {
    ct_work* next = (ct_work*)head->m_next;
    delete head;
    ++g_ct_work_dealloations;
    ++wn;
    head = next;
    }
    }
    }

    std::cout << "\nCompleted all work!\n" << std::endl;
    std::cout << "Sending shutdown state...\n" << std::endl;

    // Send shutdown state...
    {
    for (unsigned long i = 0; i < CT_THREAD_N; ++i)
    {
    ct_work* w = new ct_work;
    ++g_ct_work_alloations;
    w->m_state = 666;
    shared.m_stack_in.push(w);
    }
    }

    // Join threads...
    {
    for (unsigned long i = 0; i < CT_THREAD_N; ++i)
    {
    threads[i].join();
    }
    }

    std::cout << "\nThreads joined...\n" << std::endl;

    // Dump shutdown state...
    std::cout << "Dump shutdown state...\n" << std::endl;

    {
    ct_work* head = (ct_work*)shared.m_stack_in.m_head.load(std::memory_order_relaxed);
    shared.m_stack_in.m_head = nullptr;

    while (head)
    {
    ct_work* next = (ct_work*)head->m_next;
    delete head;
    ++g_ct_work_dealloations;
    head = next;
    }
    }

    std::cout << "\nShutdown complete!\n" << std::endl;
    }

    // Sanity check...
    {
    std::cout << "g_ct_work_alloations = " << g_ct_work_alloations
    << "\n";
    std::cout << "g_ct_work_dealloations = " <<
    g_ct_work_dealloations << std::endl;

    if (g_ct_work_alloations != g_ct_work_dealloations)
    {
    std::cout << "Pardon my French, but shit!!!!!!!!!!!!!! NOT GOOD\n" << std::endl;
    std::cout << "DAMN IT!!!! Grrrrr\n" << std::endl;
    }
    }

    std::cout << "\nFin!\n" << std::endl;

    return 0;
    }
    ______________________________________




    My output:
    _______________________
    Futex Stack Test
    by: Chris M. Thomasson
    version: (0.0.1)
    _________________________________

    CT_THREAD_N = 42
    CT_WORK_N = 10000000
    CT_WAIT = 00000000DEADBEEF
    ct_shared::ct_shared()


    Launching threads...


    Generate work...


    Completed all work!

    Sending shutdown state...


    Threads joined...

    Dump shutdown state...


    Shutdown complete!

    ct_shared::~ct_shared()

    g_ct_work_alloations = 10000042
    g_ct_work_dealloations = 10000042

    Fin!
    _______________________


    Well, any luck?

    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sat Nov 14 16:43:38 2026
    From Newsgroup: comp.lang.c++

    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    [...]
    It's unlikely anyone has program logic that requires FIFO, what little
    of it is actually observable.-a You really care about forward progress guarantees.-a As long as the consumer keeps up with the producers, you
    should be ok doing batches in LIFO order.-a If not, you have other
    problems.

    And if you drop the FIFO requirement then you could just have multiple consumers doing XCHG on the queue tail pointer.

    If the "FIFO" was removed, then its _really_ easy:

    No DWCAS, a standard LIFO stack, the single consumer takes them all.
    Does its work. There is no ABA, no deferred reclamation. It just works.
    And for waiting on empty conditions? eventcount, or a futex with a wait
    bit for the node pointers.

    Also, like you said FIFO wrt MP is basically iffy anyway.


    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Joseph Seigh@jseigh_es00@xemaps.com to comp.lang.c++ on Sun Nov 15 14:52:04 2026
    From Newsgroup: comp.lang.c++

    On 11/14/26 6:16 PM, Chris M. Thomasson wrote:
    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    [...]

    I have not had time to search for your interesting old cancel method for
    the fast semaphore on c.p.t, basically a benaphore iirc. Can you find it?

    Probably the one using bits 63-1 as the count and bit 0 as a cancel
    flag, 1 = active, 0 = canceled. Who uses semaphores? They're not
    especially useful.
    --- Synchronet 3.22a-Linux NewsLink 1.2
  • From Chris M. Thomasson@chris.m.thomasson.1@gmail.com to comp.lang.c++ on Sun Nov 15 12:36:38 2026
    From Newsgroup: comp.lang.c++

    On 11/15/2026 11:52 AM, Joseph Seigh wrote:
    On 11/14/26 6:16 PM, Chris M. Thomasson wrote:
    On 11/13/2026 6:44 AM, Joseph Seigh wrote:
    [...]

    I have not had time to search for your interesting old cancel method
    for the fast semaphore on c.p.t, basically a benaphore iirc. Can you
    find it?

    Probably the one using bits 63-1 as the count and bit 0 as a cancel
    flag, 1 = active, 0 = canceled.

    No, I "think" that was for your old 63 atomic counter on a 32 bit
    system? Back on an old x86 group, iirc. God its been a while.


    Who uses semaphores?-a They're not
    especially useful.

    ;^)

    It was an old one where you showed a fast semaphore (basically a
    benaphore, iirc). You had a function, iirc, called process_cancels or something.
    --- Synchronet 3.22a-Linux NewsLink 1.2