Re: Futex Stack Test...

On 5/8/2025 3:46 PM, jseigh wrote:

On 5/3/25 21:57, Chris M. Thomasson wrote:

On 5/3/2025 12:58 PM, Chris M. Thomasson wrote:

On 5/3/2025 11:19 AM, Bonita Montero wrote:

Am 03.05.2025 um 20:02 schrieb Chris M. Thomasson:
>

Now, its fun to be able to get a lock-free stack with only single word exchange and cas, and have the ability to use it with a futex to allow one to wait on empty conditions.

>
Is a lock-free stack with a single word CAS really possible without an
ABA-problem ?

>
Will get back to you. Need to run a bunch of errands. If you omit single item pop, yup. It's also possible to get rid of the cas in push.

>
The ABA problem _and_ memory issue is only there in on the single node pop for a lock-free stack. If you just whack it with a nullptr aka flush _all_ nodes, then you are all right and ready to roll.
>
Actually, IBM had/has a nice write up of it in an appendix for the principles of operations iirc. I think it might of been in appendix 40 ish or something. God it's been a while since I read that Bonita. Then they have a rather nifty PLO, or perform locked operation, again iirc...
>
The futex is fun to use because it allows one to wait on an empty condition...
>
Actually, I remember Joe Seigh taking all the nodes in an exchange, reversing them, and BAM, its FIFO. ;^)
>

 Probably for a MPSC queue.  I don't the FIFO semantics would hold up
very well for MPMC queue.

:^)
Well, even with a MPMP FIFO queue without the pop_all reverse results type approach, it can go:
Thread A pushes say, 10 items:
item[0]
item[1]
...
Thread B pops item[0], gets interrupted, thread C pops item[1] and processes it before thread B got a chance to process item[0]? That can happen even without the pop_all/flush "trick"... Or, am I missing something Joe?