On 12/8/2023 8:25 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/8/2023 2:59 PM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 12/6/2023 7:01 AM, MitchAlsup wrote:
>>>>>
>>>> How about this, C11:
>>>> ____________________________
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>> #include <assert.h>
>>>> #include <stdatomic.h>
>>>
>>>
>>>> struct ct_node
>>>> {
>>>>      struct ct_node* m_next;
>>>> };
>>>
>>>
>>>> int
>>>> main(void)
>>>> {
>>>>      printf("ct_c_atomic_test...nn");
>>>>      fflush(stdout);
>>>
>>>>      {
>>>>          _Atomic(struct ct_node*) shared = NULL;
>>>
>>>>          struct ct_node local = { NULL };
>>>
>>>>          struct ct_node* result_0 = atomic_exchange(&shared, &local);
>>>
>>>>          assert(!result_0);
>>>
>>>>          struct ct_node* result_1 = atomic_exchange(&shared, NULL);
>>>
>>>>          assert(result_1 == &local);
>>>>      }
>>>
>>>>      printf("completed!nn");
>>>
>>>>      return 0;
>>>> }
>>>> ____________________________
>>>
>>>> ?
>>>
>>>
>>> It should be approximately::
>>>
>>> main:
>>>      ENTER        R0,R0,#16
>>>      LEA        R1,#"ct_c_atomic_test...nn"    //
>>> printf("ct_c_atomic_test...nn");
>>>      CALL        printf
>>>      MOV        R1,#1            // fflush(stdout);
>>>      CALL        fflush
>>>
>>>      MOV        R2,#0            // shared       = NULL;    //
>>> pointer = 0; ?!?
>>>      ST        R2,[SP,8]        // local.m_next = NULL;
>>>                          // for the life of me I can't see why the
>>>                          // below code does not just SIGSEGV.
>>> //..............................................// But I ignore
>>> that.....
>
>> Actually, I am wondering why you "seem" think that it would have any
>> chance of SIGSEGV? The atomic exchanges are legit, all the memory
>> references are legit, no problem. Akin to, pseudo-code:
>> _________________
>> atomic<word*> shared = nullptr;
>> word local = 123;
>> word* x = shared.exchange(&local);
>> assert(x == nullptr);
>> word* y = shared.exchange(nullptr);
>> assert(y == &local);
>> _________________
>
> Why does _Atomic(struct ct_node*) shared = NULL; not set the shared
> pointer to zero (NULL) ?? Apparently you are setting something at where
> it is pointing to NULL; so how does shared get to be a pointer to
> something ??
>
>> Iirc, keep in mind that default membar is seq_cst in C/C++11. Unless I
>> foobar'ed it, it looks fine to me. :^)
>
>
>>>      ADD        R5,SP,#8        // &local;
>>>      LD        R3,[R2].lock        // atomic_exchange(&shared
>>>      ST        R5,[R2].lock        // atomic_exchange(&shared  =
>>> &local);
>>> //    ST        R3,[SP,8]        // local = atomic_exchange();    //
>>> dead
>>>
>>>      BEQ0        R3,assert1        // assert(!result_0);
>>>
>>>                          // NULL = atomic_exchange(); is dead
>>>      LD        R3,[R2].lock        // atomic_exchange(&shared
>>>      ST        #0,[R2].lock        // atomic_exchange(&shared  =  NULL);
>>>                          // R4 = result_1
>>>
>>>                          // R5 already has &[sp+8]
>>>      CMP        R4,R3,R5        // assert(result_1 == &local);
>>>                          // last use R5, R3, R2
>>>      BEQ        R4,assert2
>>>
>>>      LEA        R1,#"completed!nn"    // printf("completed!nn");
>>>      CALL        printf
>>>      MOV        R1,#0            // return 0;
>>>      EXIT        R0,R0,#16
>
>
>> Ahhh! I need to examine this. Fwiw, MSVC has C11 atomic, but no
>> threads. What fun! ;^o
>
> You will find My 66000 ATOMICs to be a lot thinner that competing ISAs.
>
> I looked at ARM ASM for this and ARM has converted the LD.lock;ST.lock
> into a test-and-test-and-set loop. esm has automagic looping if there
> is no interference check (BI), so::
>
>      LD        R3,[R2].lock
> // long number of cycles achieving sequential consistency and the value
> // to be delivered to a register
>      ST        R5,[R2[.lock    ---   // must fail
>                                   |   // automagically
>      LD        R3,[r2].lock  <----/   // try again
> // fewer cycles
>      ST        R5,[R2[.lock           // greater chance of success
>
> If interference is detected making ST.lock unperformable, then control
> reverts to the LD.lock. Now, we are already sequentially consistent
> so the LD is performed and made visible externally with intent to write.
>
> Oh, and BTW: this adds no state that across context switches--all
> context switches cause the event to fail and control reverts to the
> control point prior to context switching.
>
> If you really do want test-and-test-and-set functionality::
>
> Label:
>      LD        R3,[R2]
>      BC        some_condition,R3,Label
>      LD        R3,[R2].lock
>      ST        R5,[R2[.lock
>
>
>> Afaict, PellesC has full C11 atomics, threads and membars.

First of all, think of a simple atomic exchange, ala RMW, LOCK XCHG wrt
x86, fine... The atomic shared thing here is the word*:

word* shared = nullptr;

Okay, the shared pointer is equal to nullptr.

Lets create a local word:

word local = 123;

This local word is equal to 123.

Lets LOCK XCHG them:

word* previous = atomic_exchange(&shared, &local);

previous better damn well equal nullptr, and shared better be a pointer
to local!

See?

On 12/8/2023 8:25 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/8/2023 2:59 PM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 12/6/2023 7:01 AM, MitchAlsup wrote:
>>>>>
>>>> How about this, C11:
>>>> ____________________________
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>> #include <assert.h>
>>>> #include <stdatomic.h>
>>>
>>>
>>>> struct ct_node
>>>> {
>>>>      struct ct_node* m_next;
>>>> };
>>>
>>>
>>>> int
>>>> main(void)
>>>> {
>>>>      printf("ct_c_atomic_test...nn");
>>>>      fflush(stdout);
>>>
>>>>      {
>>>>          _Atomic(struct ct_node*) shared = NULL;
>>>
>>>>          struct ct_node local = { NULL };
>>>
>>>>          struct ct_node* result_0 = atomic_exchange(&shared, &local);
>>>
>>>>          assert(!result_0);
>>>
>>>>          struct ct_node* result_1 = atomic_exchange(&shared, NULL);
>>>
>>>>          assert(result_1 == &local);
>>>>      }
>>>
>>>>      printf("completed!nn");
>>>
>>>>      return 0;
>>>> }
>>>> ____________________________
>>>
>>>> ?
>>>
>>>
>>> It should be approximately::
>>>
>>> main:
>>>      ENTER        R0,R0,#16
>>>      LEA        R1,#"ct_c_atomic_test...nn"    //
>>> printf("ct_c_atomic_test...nn");
>>>      CALL        printf
>>>      MOV        R1,#1            // fflush(stdout);
>>>      CALL        fflush
>>>
>>>      MOV        R2,#0            // shared       = NULL;    //
>>> pointer = 0; ?!?
>>>      ST        R2,[SP,8]        // local.m_next = NULL;
>>>                          // for the life of me I can't see why the
>>>                          // below code does not just SIGSEGV.
>>> //..............................................// But I ignore
>>> that.....
>
>> Actually, I am wondering why you "seem" think that it would have any
>> chance of SIGSEGV? The atomic exchanges are legit, all the memory
>> references are legit, no problem. Akin to, pseudo-code:
>> _________________
>> atomic<word*> shared = nullptr;
>> word local = 123;
>> word* x = shared.exchange(&local);
>> assert(x == nullptr);
>> word* y = shared.exchange(nullptr);
>> assert(y == &local);
>> _________________
>
> Why does _Atomic(struct ct_node*) shared = NULL; not set the shared
> pointer to zero (NULL) ?? Apparently you are setting something at where
> it is pointing to NULL; so how does shared get to be a pointer to
> something ??
>
>> Iirc, keep in mind that default membar is seq_cst in C/C++11. Unless I
>> foobar'ed it, it looks fine to me. :^)
>
>
>>>      ADD        R5,SP,#8        // &local;
>>>      LD        R3,[R2].lock        // atomic_exchange(&shared
>>>      ST        R5,[R2].lock        // atomic_exchange(&shared  =

Humm... Okay, lets start small here... How would you code up
atomic_exchange all by itself, as a standalone function?

say an atomic type would be say, word*:

So, atomic_exchange would be:

word* atomic_exchange(word**, word*)

as a prototype where atomic_exchange is analogous to the RMW in x86 aka
LOCK XCHG. What would that function alone look like in your system?

>>> &local);
>>> //    ST        R3,[SP,8]        // local = atomic_exchange();    //
>>> dead
>>>
>>>      BEQ0        R3,assert1        // assert(!result_0);
>>>
>>>                          // NULL = atomic_exchange(); is dead
>>>      LD        R3,[R2].lock        // atomic_exchange(&shared
>>>      ST        #0,[R2].lock        // atomic_exchange(&shared  =  NULL);
>>>                          // R4 = result_1
>>>
>>>                          // R5 already has &[sp+8]
>>>      CMP        R4,R3,R5        // assert(result_1 == &local);
>>>                          // last use R5, R3, R2
>>>      BEQ        R4,assert2
>>>
>>>      LEA        R1,#"completed!nn"    // printf("completed!nn");
>>>      CALL        printf
>>>      MOV        R1,#0            // return 0;
>>>      EXIT        R0,R0,#16
>
>
>> Ahhh! I need to examine this. Fwiw, MSVC has C11 atomic, but no
>> threads. What fun! ;^o
>
> You will find My 66000 ATOMICs to be a lot thinner that competing ISAs.
>
> I looked at ARM ASM for this and ARM has converted the LD.lock;ST.lock
> into a test-and-test-and-set loop. esm has automagic looping if there
> is no interference check (BI), so::
>
>      LD        R3,[R2].lock
> // long number of cycles achieving sequential consistency and the value
> // to be delivered to a register
>      ST        R5,[R2[.lock    ---   // must fail
>                                   |   // automagically
>      LD        R3,[r2].lock  <----/   // try again
> // fewer cycles
>      ST        R5,[R2[.lock           // greater chance of success
>
> If interference is detected making ST.lock unperformable, then control
> reverts to the LD.lock. Now, we are already sequentially consistent
> so the LD is performed and made visible externally with intent to write.
>
> Oh, and BTW: this adds no state that across context switches--all
> context switches cause the event to fail and control reverts to the
> control point prior to context switching.
>
> If you really do want test-and-test-and-set functionality::
>
> Label:
>      LD        R3,[R2]
>      BC        some_condition,R3,Label
>      LD        R3,[R2].lock
>      ST        R5,[R2[.lock
>
>
>> Afaict, PellesC has full C11 atomics, threads and membars.

On 12/8/2023 10:54 PM, Chris M. Thomasson wrote:
> On 12/8/2023 8:25 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
[...]

Code up the function atomic_exchange, then my code works in your system
as is. That is one easy way to start... ;^)

MitchAlsup wrote:

> Chris M. Thomasson wrote:

Having written::

>     LD        R3,[R2].lock
> // long number of cycles achieving sequential consistency and the value
> // to be delivered to a register
> ST R5,[R2[.lock --- // must fail
> | // automagically
> LD R3,[r2].lock <----/ // try again
> // fewer cycles
> ST R5,[R2[.lock // greater chance of success

It occurs to me that the magic control transfer to LD.lock arrives
with the notion the previous ATOMIC event has failed and that this
second execution of LD.lock should simply wait for the cache line
{as if performing a LD without the .lock and without the attempt to
obtain write permission, and when the cache line arrives, chase it
with a Coherent Invalidate:: performing the test-and-test-and-set
paradigm without actually encoding the paradigm in instructions}.

This should eliminate most of the desire for test-and-test-and-set
explicitly in the instruction stream.

> If you really do want test-and-test-and-set functionality::

> Label:
>     LD        R3,[R2]
>     BC some_condition,R3,Label
>     LD        R3,[R2].lock
> ST R5,[R2[.lock

Chris M. Thomasson wrote:

>

> How about this, C11:
> ____________________________
> #include <stdio.h>
> #include <stdlib.h>
> #include <assert.h>
> #include <stdatomic.h>

Can you provide a reference to stdatomic.h that discusses how the functions are
supposed to work at the HW level rather than at the SW level.

mitchalsup@aol.com (MitchAlsup) writes:
>Chris M. Thomasson wrote:
>
>>
>
>> How about this, C11:
>> ____________________________
>> #include <stdio.h>
>> #include <stdlib.h>
>> #include <assert.h>
>> #include <stdatomic.h>
>
>Can you provide a reference to stdatomic.h that discusses how the functions are
>supposed to work at the HW level rather than at the SW level.

As I understand it, such a reference doesn't exist. The C++ standard
simply defines the guarantees the application can expect from the
implementation (compiler + OS).

The C11/C++11 Standard language version is here:

https://en.cppreference.com/w/cpp/header/stdatomic.h

GCC's version:

https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

Scott Lurndal wrote:

> mitchalsup@aol.com (MitchAlsup) writes:
>>Chris M. Thomasson wrote:
>>
>>>
>>
>>> How about this, C11:
>>> ____________________________
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <assert.h>
>>> #include <stdatomic.h>
>>
>>Can you provide a reference to stdatomic.h that discusses how the functions are
>>supposed to work at the HW level rather than at the SW level.

> As I understand it, such a reference doesn't exist. The C++ standard
> simply defines the guarantees the application can expect from the
> implementation (compiler + OS).

> The C11/C++11 Standard language version is here:

> https://en.cppreference.com/w/cpp/header/stdatomic.h

> GCC's version:

> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

This one is much better.

On 12/10/2023 12:08 PM, Scott Lurndal wrote:
> mitchalsup@aol.com (MitchAlsup) writes:
>> Chris M. Thomasson wrote:
>>
>>>
>>
>>> How about this, C11:
>>> ____________________________
>>> #include <stdio.h>
>>> #include <stdlib.h>
>>> #include <assert.h>
>>> #include <stdatomic.h>
>>
>> Can you provide a reference to stdatomic.h that discusses how the functions are
>> supposed to work at the HW level rather than at the SW level.
>
> As I understand it, such a reference doesn't exist.

I think so. An atomic exchange can be implemented with an atomic RMW
exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.

> The C++ standard
> simply defines the guarantees the application can expect from the
> implementation (compiler + OS).
>
> The C11/C++11 Standard language version is here:
>
> https://en.cppreference.com/w/cpp/header/stdatomic.h
>
> GCC's version:
>
> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

Chris M. Thomasson wrote:

> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>> mitchalsup@aol.com (MitchAlsup) writes:
>>> Chris M. Thomasson wrote:
>>>
>>>>
>>>
>>>> How about this, C11:
>>>> ____________________________
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>> #include <assert.h>
>>>> #include <stdatomic.h>
>>>
>>> Can you provide a reference to stdatomic.h that discusses how the functions are
>>> supposed to work at the HW level rather than at the SW level.
>>
>> As I understand it, such a reference doesn't exist.

> I think so. An atomic exchange can be implemented with an atomic RMW
> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.

More like::

An Atomic Exchange has to reach a point of sequential consistency (which
may entail a MEMBAR on machines with relaxed memory ordering) before
the address of the exchanged container is made visible to the system.
The exchange is performed in such a way that the stored value is visible
to the system prior to any other access to that container is made visible
to the system (this may also require an MEMBAR on systems with relaxed
memory orderings.)

>> The C++ standard
>> simply defines the guarantees the application can expect from the
>> implementation (compiler + OS).
>>
>> The C11/C++11 Standard language version is here:
>>
>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>>
>> GCC's version:
>>
>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

On 12/10/2023 4:15 PM, Chris M. Thomasson wrote:
> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>> mitchalsup@aol.com (MitchAlsup) writes:
>>> Chris M. Thomasson wrote:
>>>
>>>>
>>>
>>>> How about this, C11:
>>>> ____________________________
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>> #include <assert.h>
>>>> #include <stdatomic.h>
>>>
>>> Can you provide a reference to stdatomic.h that discusses how the
>>> functions are
>>> supposed to work at the HW level rather than at the SW level.
>>
>> As I understand it, such a reference doesn't exist.
>
> I think so. An atomic exchange can be implemented with an atomic RMW
> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.
[...]

Also, fwiw, atomic exchange can be implemented using various hashed
locking schemes. This would require is_lock_free to return false:

https://cplusplus.com/reference/atomic/atomic/is_lock_free/

On 12/10/2023 4:30 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>>> mitchalsup@aol.com (MitchAlsup) writes:
>>>> Chris M. Thomasson wrote:
>>>>
>>>>>
>>>>
>>>>> How about this, C11:
>>>>> ____________________________
>>>>> #include <stdio.h>
>>>>> #include <stdlib.h>
>>>>> #include <assert.h>
>>>>> #include <stdatomic.h>
>>>>
>>>> Can you provide a reference to stdatomic.h that discusses how the
>>>> functions are
>>>> supposed to work at the HW level rather than at the SW level.
>>>
>>> As I understand it, such a reference doesn't exist.
>
>> I think so. An atomic exchange can be implemented with an atomic RMW
>> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.
>
> More like::
>
> An Atomic Exchange has to reach a point of sequential consistency (which
> may entail a MEMBAR on machines with relaxed memory ordering) before
> the address of the exchanged container is made visible to the system.

Not really... Atomic exchange can be implemented in relaxed form wrt no
memory barriers in sight. Just as long as it does its job, an atomic
swap. On the SPARC I had to decorate atomic exchange with the correct
membars to get the job done. The weakest I could get away with...

> The exchange is performed in such a way that the stored value is visible
> to the system prior to any other access to that container is made visible
> to the system (this may also require an MEMBAR on systems with relaxed
> memory orderings.)

>
>>> The C++ standard
>>> simply defines the guarantees the application can expect from the
>>> implementation (compiler + OS).
>>>
>>> The C11/C++11 Standard language version is here:
>>>
>>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>>>
>>> GCC's version:
>>>
>>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

Chris M. Thomasson wrote:

> On 12/10/2023 4:30 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
>>
>>> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>>>> mitchalsup@aol.com (MitchAlsup) writes:
>>>>> Chris M. Thomasson wrote:
>>>>>
>>>>>>
>>>>>
>>>>>> How about this, C11:
>>>>>> ____________________________
>>>>>> #include <stdio.h>
>>>>>> #include <stdlib.h>
>>>>>> #include <assert.h>
>>>>>> #include <stdatomic.h>
>>>>>
>>>>> Can you provide a reference to stdatomic.h that discusses how the
>>>>> functions are
>>>>> supposed to work at the HW level rather than at the SW level.
>>>>
>>>> As I understand it, such a reference doesn't exist.
>>
>>> I think so. An atomic exchange can be implemented with an atomic RMW
>>> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.
>>
>> More like::
>>
>> An Atomic Exchange has to reach a point of sequential consistency (which
>> may entail a MEMBAR on machines with relaxed memory ordering) before
>> the address of the exchanged container is made visible to the system.

> Not really... Atomic exchange can be implemented in relaxed form wrt no
> memory barriers in sight. Just as long as it does its job, an atomic
> swap. On the SPARC I had to decorate atomic exchange with the correct
> membars to get the job done. The weakest I could get away with...

Ok, then write the paragraph I tried to write with sufficient detail that
a CPU designer, who knows nothing of software, can read but cannot misunderstand.
Fit all necessary sequencing, barriers, timing, ... needed such that any CPU
sequence designer will achieve a successful atomic_exchange over all his
(or her !) designs.

>> The exchange is performed in such a way that the stored value is visible
>> to the system prior to any other access to that container is made visible
>> to the system (this may also require an MEMBAR on systems with relaxed
>> memory orderings.)

>>
>>>> The C++ standard
>>>> simply defines the guarantees the application can expect from the
>>>> implementation (compiler + OS).
>>>>
>>>> The C11/C++11 Standard language version is here:
>>>>
>>>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>>>>
>>>> GCC's version:
>>>>
>>>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

On 12/10/2023 4:50 PM, Chris M. Thomasson wrote:
> On 12/10/2023 4:30 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
>>
>>> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>>>> mitchalsup@aol.com (MitchAlsup) writes:
>>>>> Chris M. Thomasson wrote:
>>>>>
>>>>>>
>>>>>
>>>>>> How about this, C11:
>>>>>> ____________________________
>>>>>> #include <stdio.h>
>>>>>> #include <stdlib.h>
>>>>>> #include <assert.h>
>>>>>> #include <stdatomic.h>
>>>>>
>>>>> Can you provide a reference to stdatomic.h that discusses how the
>>>>> functions are
>>>>> supposed to work at the HW level rather than at the SW level.
>>>>
>>>> As I understand it, such a reference doesn't exist.
>>
>>> I think so. An atomic exchange can be implemented with an atomic RMW
>>> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.
>>
>> More like::
>>
>> An Atomic Exchange has to reach a point of sequential consistency (which
>> may entail a MEMBAR on machines with relaxed memory ordering) before
>> the address of the exchanged container is made visible to the system.
>
> Not really... Atomic exchange can be implemented in relaxed form wrt no
> memory barriers in sight. Just as long as it does its job, an atomic
> swap. On the SPARC I had to decorate atomic exchange with the correct
> membars to get the job done.

I should say I had to use the most relaxed membar scheme I could wrt the
requirements of the lock/wait free algorithm I was working with,
creating, ect... naked atomic exchange is a real thing. Naked in the
sense of no implied membars!

> The weakest I could get away with...
>
>
>
>
>> The exchange is performed in such a way that the stored value is visible
>> to the system prior to any other access to that container is made visible
>> to the system (this may also require an MEMBAR on systems with relaxed
>> memory orderings.)
>
>
>
>
>>
>>>> The C++ standard
>>>> simply defines the guarantees the application can expect from the
>>>> implementation (compiler + OS).
>>>>
>>>> The C11/C++11 Standard language version is here:
>>>>
>>>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>>>>
>>>> GCC's version:
>>>>
>>>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
>

On 12/10/2023 5:20 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/10/2023 4:30 PM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 12/10/2023 12:08 PM, Scott Lurndal wrote:
>>>>> mitchalsup@aol.com (MitchAlsup) writes:
>>>>>> Chris M. Thomasson wrote:
>>>>>>
>>>>>>>
>>>>>>
>>>>>>> How about this, C11:
>>>>>>> ____________________________
>>>>>>> #include <stdio.h>
>>>>>>> #include <stdlib.h>
>>>>>>> #include <assert.h>
>>>>>>> #include <stdatomic.h>
>>>>>>
>>>>>> Can you provide a reference to stdatomic.h that discusses how the
>>>>>> functions are
>>>>>> supposed to work at the HW level rather than at the SW level.
>>>>>
>>>>> As I understand it, such a reference doesn't exist.
>>>
>>>> I think so. An atomic exchange can be implemented with an atomic RMW
>>>> exchange (LOCK XCHG), CAS (cmpxchg), or even LL/SC.
>>>
>>> More like::
>>>
>>> An Atomic Exchange has to reach a point of sequential consistency (which
>>> may entail a MEMBAR on machines with relaxed memory ordering) before
>>> the address of the exchanged container is made visible to the system.
>
>> Not really... Atomic exchange can be implemented in relaxed form wrt
>> no memory barriers in sight. Just as long as it does its job, an
>> atomic swap. On the SPARC I had to decorate atomic exchange with the
>> correct membars to get the job done. The weakest I could get away with...
>
> Ok, then write the paragraph I tried to write with sufficient detail that
> a CPU designer, who knows nothing of software, can read but cannot
> misunderstand.
> Fit all necessary sequencing, barriers, timing, ... needed such that any
> CPU
> sequence designer will achieve a successful atomic_exchange over all his
> (or her !) designs.
>
>>> The exchange is performed in such a way that the stored value is visible
>>> to the system prior to any other access to that container is made
>>> visible
>>> to the system (this may also require an MEMBAR on systems with relaxed
>>> memory orderings.)

Think of different ways to implement LOCK XCHG. Two come to mind, a
pessimistic lock based scheme, ala intel, or a more opportunistic method
akin to LL/SC?

lock based version, pseudo code typed in the newsreader, hope I did not
make a damn mistake:
______________________________
word*
atomic_exchange(
word** origin,
word* xchg
){
hash_lock(origin);

// RMW
word* original = *origin;
*origin = xchg;

hash_unlock(origin);

return original;
} ______________________________

That is one way to do it using a hashed locking scheme.

>
>
>
>
>>>
>>>>> The C++ standard
>>>>> simply defines the guarantees the application can expect from the
>>>>> implementation (compiler + OS).
>>>>>
>>>>> The C11/C++11 Standard language version is here:
>>>>>
>>>>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>>>>>
>>>>> GCC's version:
>>>>>
>>>>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html

On 10/12/2023 23:58, MitchAlsup wrote:
> Scott Lurndal wrote:
>
>> mitchalsup@aol.com (MitchAlsup) writes:
>>> Chris M. Thomasson wrote:
>>>
>>>>
>>>
>>>> How about this, C11:
>>>> ____________________________
>>>> #include <stdio.h>
>>>> #include <stdlib.h>
>>>> #include <assert.h>
>>>> #include <stdatomic.h>
>>>
>>> Can you provide a reference to stdatomic.h that discusses how the
>>> functions are
>>> supposed to work at the HW level rather than at the SW level.
>
>> As I understand it, such a reference doesn't exist.   The C++ standard
>> simply defines the guarantees the application can expect from the
>> implementation (compiler + OS).
>
>> The C11/C++11 Standard language version is here:
>
>> https://en.cppreference.com/w/cpp/header/stdatomic.h
>
>> GCC's version:
>
>> https://gcc.gnu.org/onlinedocs/gcc/_005f_005fatomic-Builtins.html
>
> This one is much better.

Other links that might be of use or interest from gcc include:

<https://gcc.gnu.org/wiki/MemoryModel>
<https://gcc.gnu.org/wiki/Atomic/GCCMM>
<https://gcc.gnu.org/wiki/Atomic/C11>
<https://gcc.gnu.org/wiki/Atomic>
<https://gcc.gnu.org/wiki/Atomic/GCCMM/Optimizations>

<https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html>

Chris M. Thomasson wrote:

> On 12/10/2023 5:20 PM, MitchAlsup wrote:
>>
> ______________________________
> word*
> atomic_exchange(
> word** origin,
> word* xchg
> ){
> hash_lock(origin);

> // RMW
> word* original = *origin;
> *origin = xchg;

> hash_unlock(origin);

> return original;
> }
> ______________________________

As written, and assuming hash_lock() and hash_unlock are function calls
that guarentee the atomicity of the exchange::

atomic_exchange:
ENTER R28,R0,#24
MOV R30,R1
MOV R29,R2

CALL hash_lock

LD R28,[R30]
ST R29,[R30

MOV R1,R30
CALL hash_unlock

MOV R1,R28
EXIT R28,R0,#24

But I suspect that hash_{[un]lock} is not a function call but a macro
that offsets into the structure and performs a LL while un performs
the SC. Here is an example where we do not even use the value in the
addressed memory container, but simply monitor the cache line for
interference; In which case we get::

atomic_exchange:
PRE #19,[R1+lock].lock

LD R3,[R1]
ST R2,[R1]

PUSH #3,[R1+lock].lock

MOV R1,R3
RET

If interference is detected, control automagically reverts to PRE
#19 specifies Write permission and L1 cache.

The PUSH #3 does not change the value in the location, just releases
the lock and leaves the line in L1 cache. Interference is detected
when some other resource requests write permission {and is at higher
priority}.

Let us see how interference plays out::

atomic_exchange:

PRE #19,[R1+lock].lock // control-point = .
LD R3,[R1]
ST R2,[R1]
{ repeat
PUSH #3,[R1+lock].lock -fails----
| // IP = control-point
PRE #19,[R1+lock].lock -arrives-/

LD R3,[R1]
ST R2,[R1]
} any numbers of times
PUSH #3,[R1+lock].lock -succ----
|
MOV R1,R3 -arrives-/
RET
_____________________________________________________________________

By majority vote, the .lock notation is being retired and the Lock
designation is obtained by concattenating an L on the end of the
memory reference nmemonic::

LDmem Rd,[Rb...].lock
becomes:
LDmemL Rd,[Rb...]
etcetera.

On 12/14/2023 12:55 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/10/2023 5:20 PM, MitchAlsup wrote:
>>>
>> ______________________________
>> word*
>> atomic_exchange(
>>    word** origin,
>>    word* xchg
>> ){
>>     hash_lock(origin);
>
>>       // RMW
>>       word* original = *origin;
>>       *origin = xchg;
>
>>     hash_unlock(origin);
>
>>     return original;
>> }
>> ______________________________
>
> As written, and assuming hash_lock() and hash_unlock are function calls
> that guarentee the atomicity of the exchange::
[...]

Fwiw, my example of atomic exchange using locking is taking into account
one of my previous experiments that hashes addresses into indexes into a
mutex table. The mutex table is completely separated from the user logic.

https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
(read all)

This is one way to implement C++ atomics using locks! This would require
me to report that the impl is not lock-free vis is_lock_free and some
other places.

Now, this is a locked version. The wait free version on x86 would be
LOCK XCHG.

Chris M. Thomasson wrote:

> On 12/14/2023 12:55 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
>>
>>> On 12/10/2023 5:20 PM, MitchAlsup wrote:
>>>>
>>> ______________________________
>>> word*
>>> atomic_exchange(
>>>    word** origin,
>>>    word* xchg
>>> ){
>>>     hash_lock(origin);
>>
>>>       // RMW
>>>       word* original = *origin;
>>>       *origin = xchg;
>>
>>>     hash_unlock(origin);
>>
>>>     return original;
>>> }
>>> ______________________________
>>
>> As written, and assuming hash_lock() and hash_unlock are function calls
>> that guarentee the atomicity of the exchange::
> [...]

> Fwiw, my example of atomic exchange using locking is taking into account
> one of my previous experiments that hashes addresses into indexes into a
> mutex table. The mutex table is completely separated from the user logic.

> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
> (read all)

> This is one way to implement C++ atomics using locks! This would require
> me to report that the impl is not lock-free vis is_lock_free and some
> other places.

So would you assign the # define ATOMIC_BOOL_LOCK_FREE a 1 (sometimes lock
free) or 2 (always lock free) or 0 (not lock free)

> Now, this is a locked version. The wait free version on x86 would be
> LOCK XCHG.

On 12/14/2023 8:15 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/14/2023 12:55 PM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 12/10/2023 5:20 PM, MitchAlsup wrote:
>>>>>
>>>> ______________________________
>>>> word*
>>>> atomic_exchange(
>>>>    word** origin,
>>>>    word* xchg
>>>> ){
>>>>     hash_lock(origin);
>>>
>>>>       // RMW
>>>>       word* original = *origin;
>>>>       *origin = xchg;
>>>
>>>>     hash_unlock(origin);
>>>
>>>>     return original;
>>>> }
>>>> ______________________________
>>>
>>> As written, and assuming hash_lock() and hash_unlock are function calls
>>> that guarentee the atomicity of the exchange::
>> [...]
>
>> Fwiw, my example of atomic exchange using locking is taking into
>> account one of my previous experiments that hashes addresses into
>> indexes into a mutex table. The mutex table is completely separated
>> from the user logic.
>
>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>> (read all)
>
>> This is one way to implement C++ atomics using locks! This would
>> require me to report that the impl is not lock-free vis is_lock_free
>> and some other places.
>
> So would you assign the # define ATOMIC_BOOL_LOCK_FREE a 1 (sometimes
> lock free) or 2 (always lock free) or 0 (not lock free)

Good question Mitch! :^)

I would simply have to set it to 0 simply because it is using one my
hash locking schemes wrt the context, it is not lock-free. Sometimes
lock-free can be potentially an "adaptive" lock-free algo, that strives
to be lock-free but can "choose" to block in the kernel during certain
times... The lock-free has its mind set on trying to avoid the kernel.
However, since it can potentially hit a path that goes into a kernel
wait, well, sometimes lock-free can be in order.... This would be
sometimes lock-free. However, if you want to use it in a signal handler,
it better damn well be 100% lock-free, at least! Wait-free fine, ect...

>
>> Now, this is a locked version. The wait free version on x86 would be
>> LOCK XCHG.

On 12/14/2023 8:58 PM, Chris M. Thomasson wrote:
> On 12/14/2023 8:15 PM, MitchAlsup wrote:
>> Chris M. Thomasson wrote:
>>
>>> On 12/14/2023 12:55 PM, MitchAlsup wrote:
>>>> Chris M. Thomasson wrote:
>>>>
>>>>> On 12/10/2023 5:20 PM, MitchAlsup wrote:
>>>>>>
>>>>> ______________________________
>>>>> word*
>>>>> atomic_exchange(
>>>>>    word** origin,
>>>>>    word* xchg
>>>>> ){
>>>>>     hash_lock(origin);
>>>>
>>>>>       // RMW
>>>>>       word* original = *origin;
>>>>>       *origin = xchg;
>>>>
>>>>>     hash_unlock(origin);
>>>>
>>>>>     return original;
>>>>> }
>>>>> ______________________________
>>>>
>>>> As written, and assuming hash_lock() and hash_unlock are function calls
>>>> that guarentee the atomicity of the exchange::
>>> [...]
>>
>>> Fwiw, my example of atomic exchange using locking is taking into
>>> account one of my previous experiments that hashes addresses into
>>> indexes into a mutex table. The mutex table is completely separated
>>> from the user logic.
>>
>>> https://groups.google.com/g/comp.lang.c++/c/sV4WC_cBb9Q/m/5JRwvhpVCAAJ
>>> (read all)
>>
>>> This is one way to implement C++ atomics using locks! This would
>>> require me to report that the impl is not lock-free vis is_lock_free
>>> and some other places.
>>
>> So would you assign the # define ATOMIC_BOOL_LOCK_FREE a 1 (sometimes
>> lock free) or 2 (always lock free) or 0 (not lock free)
>
> Good question Mitch! :^)
>
> I would simply have to set it to 0 simply because it is using one my
> hash locking schemes wrt the context, it is not lock-free. Sometimes
> lock-free can be potentially an "adaptive" lock-free algo, that strives
> to be lock-free but can "choose" to block in the kernel during certain
> times... The lock-free has its mind set on trying to avoid the kernel.
> However, since it can potentially hit a path that goes into a kernel
> wait, well, sometimes lock-free can be in order.... This would be
> sometimes lock-free. However, if you want to use it in a signal handler,
> it better damn well be 100% lock-free, at least! Wait-free fine, ect...
>
>>
>>> Now, this is a locked version. The wait free version on x86 would be
>>> LOCK XCHG.
>

Striving for lock/wait-free instead of blocking in the kernel! Well, I
got my set on that!

https://youtu.be/6ZwjdGSqO0k

:^)

On 12/6/2023 7:29 PM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/6/2023 7:01 AM, MitchAlsup wrote:
>>> Chris M. Thomasson wrote:
>>>
>>>> On 12/5/2023 6:21 PM, MitchAlsup wrote:
>>>>> Chris M. Thomasson wrote:
>>>>>
>>>>>> On 12/5/2023 3:25 PM, MitchAlsup wrote:
>>>>>>> Chris M. Thomasson wrote:
>>>>>> [...]
>>>>>>> I have a 99% functional C compiler that runs many Fortran
>>>>>>> programs, but
>>>>>>> C++ is a way bigger language {constructors, destructors,
>>>>>>> try-throw-catch,
>>>>>>> their version of ATOMICs, threading, .....}
>>>>>
>>>>>> A C11 compiler that knows about membars and atomics? Fwiw, check
>>>>>> this out:
>>>>>
>>>>> Where does it mention a My 66000 ISA target ?? That is the only ISA
>>>>> I am
>>>>> spending time in.........
>>>>>
>>>>>> http://www.smorgasbordet.com/pellesc
>>>>>
>>>>>> [...]
>>>
>>>> I was just wondering if your C compiler handles C11? If so, that
>>>> would be great!!!!
>>>
>>>
>>> It handles whatever the current CLANG front end handles.
>
>> A proposal?
>> https://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/p0233r5.pdf :^)
>
> Under 2.3. Pros and Cons
> <snip>
> The main disadvantage of the hazard pointers method is that each
> traversal incurs a store-load
> memory order fence, when using the method's basic form (without blocking
> or using system
> support such as sys_membarrier()).
>
> The transition from {sequential to causal*} consistency appears to take
> place at the
> subsequent memory reference . There are 2 cases to
> consider::
> a) ST.lock remains in the execution window
> b) ST.lock has retired
[...]

It's that damn Store to Load memory order requirement. There are ways
around it wrt current arch's, dec alpha aside for a moment... I
mentioned one of them in this thread.

Chris M. Thomasson wrote:

> On 12/6/2023 7:29 PM, MitchAlsup wrote:
>>
>> The main disadvantage of the hazard pointers method is that each
>> traversal incurs a store-load
>> memory order fence, when using the method's basic form (without blocking
>> or using system
>> support such as sys_membarrier()).
>>
>> The transition from {sequential to causal*} consistency appears to take
>> place at the
>> subsequent memory reference . There are 2 cases to
>> consider::
>> a) ST.lock remains in the execution window
>> b) ST.lock has retired
> [...]

> It's that damn Store to Load memory order requirement. There are ways
> around it wrt current arch's, dec alpha aside for a moment... I
> mentioned one of them in this thread.

I learned very early, that getting ATOMICs right is vastly more important
than making them fast. And getting memory order done properly is paramount.

On 12/15/2023 9:15 AM, MitchAlsup wrote:
> Chris M. Thomasson wrote:
>
>> On 12/6/2023 7:29 PM, MitchAlsup wrote:
>>>
>>> The main disadvantage of the hazard pointers method is that each
>>> traversal incurs a store-load
>>> memory order fence, when using the method's basic form (without
>>> blocking or using system
>>> support such as sys_membarrier()).
>>>
>>> The transition from {sequential to causal*} consistency appears to
>>> take place at the
>>> subsequent memory reference . There are 2 cases to
>>> consider::
>>> a) ST.lock remains in the execution window
>>> b) ST.lock has retired
>> [...]
>
>> It's that damn Store to Load memory order requirement. There are ways
>> around it wrt current arch's, dec alpha aside for a moment... I
>> mentioned one of them in this thread.
>
>
> I learned very early, that getting ATOMICs right is vastly more important
> than making them fast. And getting memory order done properly is paramount.

Yup. Getting the atomics right is first on the list, indeed. Wrt memory
order, I usually make everything std::memory_order_seq_cst first! Okay,
get it working... Now, lets ponder on and experiment with trying to
reduce the memory order to its weakest point before things no longer
work... Fwiw, there are some tools out there that be fairly beneficial.
One of them was written by one of my friends from way back over on
comp.programming.threads:

https://github.com/dvyukov/relacy

This is pretty nice, well, according to me. :^)