Re: Atomic operations

[Paulo César Pereira de Andrade]

Em sex., 9 de set. de 2022 às 17:48, Marc Nieper-Wißkirchen
<marc.nieper+gnu@gmail.com> escreveu:
>
> Dear Paulo,

  Hi Marc,

> I just want to say that I got your exciting message; I should have time to 
> look into your work in more detail next week.

  I would like some feedback about it. At first, I believe should add support
for the boolean result argument being also an argument, just to avoid
surprises, or, make it very clear in the documentation that arguments
must be unique (initial docs already say so).

  Also, the most common usage should be cas(result, address, old_val, new_val)
where old_val is zero, so, could create a cas0 interface as well.

  Maybe should also add some way to hint the code might be in a spin loop.
For x86* it would be the pause instruction:
https://www.intel.com/content/www/us/en/develop/documentation/cpp-compiler-developer-guide-and-reference/top/compiler-reference/intrinsics/intrinsics-for-sse2/miscellaneous-functions-and-intrinsics/pause-intrinsic.html
  Otherwise, could make a "fallback" that calls sched_yield; possibly
better if left for the logic creating jit, as save/restore registers state
is not simple, and code generation would make sure to save any
value it needs during the function call. At least for Linux, it should
be just a syscall and could be inlined in jit.

> Thanks a lot,
>
> Marc
>
> Am Do., 8. Sept. 2022 um 21:59 Uhr schrieb Paulo César Pereira de Andrade 
> <paulo.cesar.pereira.de.andrade@gmail.com>:
>>
>> Em qui., 1 de set. de 2022 às 18:18, Paulo César Pereira de Andrade
>> <paulo.cesar.pereira.de.andrade@gmail.com> escreveu:
>>
>>   Hi Marc,
>>
>> > Em sex., 12 de ago. de 2022 às 08:15, Paulo César Pereira de Andrade
>> > <paulo.cesar.pereira.de.andrade@gmail.com> escreveu:
>> > >
>> > > Em qui., 11 de ago. de 2022 às 17:52, Marc Nieper-Wißkirchen
>> > > <marc.nieper+gnu@gmail.com> escreveu:
>> > >
>> > >   Hi Marc,
>> > >
>> > > > PS: This document may be helpful as well: 
>> > > > https://www.cl.cam.ac.uk/~pes20/cpp/cpp0xmappings.html.
>> >
>> >   My idea is to keep at least the first implementation as simple
>> > as possible.
>> >
>> > >   Right now, my idea of what should be done would be to have a
>> > > jit_casr(bool_return_in_register, address_in_register,
>> > > new_value_in_register, old_value_in_register);
>> > >
>> > >   It would need a new pattern of 4 registers instruction, as only
>> > > the first one is modified. The current qmul* and qdiv* ones put
>> > > result in the first two register arguments.
>> > >
>> > >   And while at that, also have a:
>> > >
>> > > jit_tasr(old_value_in_register, address_in_register, 
>> > > new_value_in_register);
>> > >
>> > >   Likely can have the _c, _s, _i, and _l modifiers, or have only a 32
>> > > bit variant.
>> >
>> >   At first "test and set" is only cheap on x86*, and would require very 
>> > complex
>> > code, and even loops on some architectures. It should also not be friendly 
>> > to
>> > cache and end up wasting too much cpu.
>> > https://godbolt.org/z/WPsPzv66c
>> >
>> > >   Very few cpus should not have some construct for it. For those, we 
>> > > just add
>> > > a software fallback with some kind of spin lock. In either case,  we 
>> > > "cheat" and
>> > > look at what assembly gcc generates or the kernel uses for the
>> > > equivalent construct.
>> >
>> >   For the moment I am considering only a:
>> >
>> > jit_casr(jit_int32_t bool_reg_return, jit_int32_t address, jit_int32_t
>> > old_val, jit_int32_t new_val);
>>
>>   Please check 
>> https://git.savannah.gnu.org/cgit/lightning.git/commit/?id=d5a7c8e4ad719e84dbb4904c532f906a1ef5a77b
>> [Implement a simple compare and swap atomic operation.]
>>
>>   At first I would not like to implement something like gcc libatomic
>> or libatomic_ops as inline jit generation. It would be way too complex
>> and very difficult to ensure it would be bug free.
>>
>> > where:
>> > * bool_reg_return would be true if it did swap, false otherwise;
>> >   any loop, until it returns true would need to be explicitly generated.
>> >   This also makes it easier to implement a "try lock" logic.
>> > * address is the address in a register
>> > * old_val is the expected old value in a register
>> > * new_val is the expected new value in a register
>> >
>> > could implement a jit_casi where the address argument could be an
>> > immediate value.
>> > At first I would avoid it, because it likely would need a temporary,
>> > and better to
>> > have the code implementing any loop choosing what register to use for
>> > the address,
>> > and it might still be required temporaries on some architectures even
>> > receiving all
>> > arguments in registers.
>> >
>> >   About pairs, it is in my low priority TODO complex numbers support :-)
>> >
>> > >   About the ABA problem, we ignore it. Just have some note, describe the 
>> > > issue
>> > > and how to avoid it. I would suggest using it with the 
>> > > address_in_register value
>> > > as a special lock, not the actual variable.
>>
>>   At first it implements jit_cas{r,i}(result, address, old, new) where
>> result is a
>> register to store the boolean result, address is a register or an immediate
>> with the machine address of the value/lock, old is the old value to test, and
>> new is the value to set the contents of the address if it holds the old 
>> value.
>>
>>   Because it only returns true if the value was changed, frequently a loop 
>> must
>> be done until acquiring the lock, *or* if the code can be generated in
>> a very smart
>> way, it can do something else and try again later, to avoid wasting cpu time.
>>
>>   A fallback is implemented with pthreads. It is very expensive, but for now
>> only used in the first implementation, or on ports where it cannot be 
>> properly
>> tested, as there is no real hardware access, or no smp hardware access.
>>
>> Thanks,
>> Paulo