Re: Futex Stack Test...

On 5/8/2025 2:11 AM, Bonita Montero wrote:

Am 04.05.2025 um 03:57 schrieb Chris M. Thomasson:
 

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.

 Very interesting! I'm just going to believe this without having thought
it through. This ultimately means that when memory allocators clean up
foreign releases from a lock-free stack, they don't need DWCAS to do so.
 

It only works if you remove all of the nodes, aka flush (pop_all). Not pop_one. If you intermix the two, then pop_one will still have the memory issue where a node can be prematurely deleted. This is besides the ABA problem, a completely different problem.
SEH on the pop_one, or some other means, would still be needed if you delete nodes. If you only pop_all, then that eliminates ABA and the memory issue. Now, iirc way back, around 20 years ago. I think I remember reading about some interesting issues about using CAS on a word that is part of a DWCAS anchor. So, some pseudo-code:
struct dwcas_anchor
{
     word* head;
     word aba;
};
And using CAS on the dwcas_anchor::head. Keep in mind that ABA does not need to be updated if we remove all the nodes. Actually, pushing a node does not need to update ABA. Only the pop_one's. Iirc, this makes things tricky on the pop_one side. Iirc, aba needs be read first. Ummm... Take a look at some of my older code. I had to program this in ASM back then, lol:
https://web.archive.org/web/20060214112345/http://appcore.home.comcast.net/appcore/src/cpu/i686/ac_i686_gcc_asm.html
https://web.archive.org/web/20060214112539/http://appcore.home.comcast.net/appcore/src/cpu/i686/ac_i686_masm_asm.html
.align 16
.globl ac_i686_stack_mpmc_push_cas
ac_i686_stack_mpmc_push_cas:
   movl 4(%esp), %edx
   movl (%edx), %eax
   movl 8(%esp), %ecx
ac_i686_stack_mpmc_push_cas_retry:
   movl %eax, (%ecx)
   lock cmpxchgl %ecx, (%edx)
   jne ac_i686_stack_mpmc_push_cas_retry
ret
.align 16
.globl np_ac_i686_stack_mpmc_pop_dwcas
np_ac_i686_stack_mpmc_pop_dwcas:
   pushl %esi
   pushl %ebx
   movl 12(%esp), %esi
   movl 4(%esi), %edx
   movl (%esi), %eax
np_ac_i686_stack_mpmc_pop_dwcas_retry:
   test %eax, %eax
   je np_ac_i686_stack_mpmc_pop_dwcas_fail
   movl (%eax), %ebx
   leal 1(%edx), %ecx
   lock cmpxchg8b (%esi)
   jne np_ac_i686_stack_mpmc_pop_dwcas_retry
np_ac_i686_stack_mpmc_pop_dwcas_fail:
   popl %ebx
   popl %esi
ret