Re: 2*(void *) atomic swap?

[Dennis Ferguson <dennis.c.ferguson%gmail.com@localhost>]

On 30 Jul, 2015, at 01:53 , Maxime Villard <max%M00nBSD.net@localhost> wrote:
> Do we have a magic function that can perform two atomic_swap_ptr()
> atomically?

I don't think you can have a portable function like that.  x86 and
IBM mainframes now have instructions for 2-pointer CAS which could
be used for this, but they exist only because they fix the ABA problems
associated with the single pointer CAS instructions those machines
relied on and which older models are limited to.  Machines that
implement ll/sc instead never had the ABA problem (they may have
problems with livelock, but there are other hardware mitigations for
that) so they had no reason to want double-wide versions and hence don't
do them.

It is unfortunate that NetBSD is limited to single-pointer CAS as
its fundamental (portable) synchronization primitive, but that's
really all you can count on hardware support for over the whole range
of machines it runs on.  I have an implementation of a lockless,
non-blocking multiple-producer, multiple-consumer queue that uses
hazard pointers to avoid the ABA problem which is 4500 lines of
code long and too complicated to want to actually use; if it could
rely on ll/sc and/or double-wide CAS it would be 200 lines of code
instead and maybe even useful.

The only way I have found to handle atomic operations on pointers
which algorithmically need to point at one of several structure types
or array lengths (when you can't store the distinguishing information
in the structure being pointed at) is the low order bits of the pointer.
While the strict non-portability of this makes one wince, as a practical
matter it does work on the machines NetBSD runs on.  If the variation
you need to deal with can't be represented in a small number of bits,
however, it clearly doesn't help.  On the other hand, it is only for
data structures where read-only accesses are common and modifications
are relatively rarer that there is an unambiguous performance benefit
to avoiding (reader) locks, and sometimes you just can't avoid a lock
regardless.

Dennis Ferguson