Deutsch   English   Français   Italiano  
<vvj16e$22i35$1@dont-email.me>

View for Bookmarking (what is this?)
Look up another Usenet article

Path: news.eternal-september.org!eternal-september.org!.POSTED!not-for-mail
From: "Chris M. Thomasson" <chris.m.thomasson.1@gmail.com>
Newsgroups: comp.lang.c++
Subject: Re: Futex Stack Test...
Date: Thu, 8 May 2025 12:37:50 -0700
Organization: A noiseless patient Spider
Lines: 80
Message-ID: <vvj16e$22i35$1@dont-email.me>
References: <vp0g2q$1bu96$1@dont-email.me>
 <vv28lf$v2jv$1@raubtier-asyl.eternal-september.org>
 <vv3smk$2d66g$1@dont-email.me>
 <vv3ui8$2iqp0$1@raubtier-asyl.eternal-september.org>
 <vv40u4$2kni8$1@raubtier-asyl.eternal-september.org>
 <vv5ln8$26ei$1@dont-email.me>
 <vv5mn0$38ie$1@raubtier-asyl.eternal-september.org>
 <vv5shh$89nm$1@dont-email.me> <vv6hhn$rebo$1@dont-email.me>
 <vvhsgi$1lld7$1@raubtier-asyl.eternal-september.org>
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
Injection-Date: Thu, 08 May 2025 21:37:51 +0200 (CEST)
Injection-Info: dont-email.me; posting-host="9e97b8684de3ff7eb0c43ffec630b9d4";
	logging-data="2181221"; mail-complaints-to="abuse@eternal-september.org";	posting-account="U2FsdGVkX19GT5F5fsp8QFdmZ2zEHRpK5bt558J+ipU="
User-Agent: Mozilla Thunderbird
Cancel-Lock: sha1:AM7/6iTtPZowARrhprIUG55hlB8=
In-Reply-To: <vvhsgi$1lld7$1@raubtier-asyl.eternal-september.org>
Content-Language: en-US

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