Module suggestion: Atomic operations

Module suggestion: Atomic operations

[Marc Nieper-Wißkirchen]

[-- Attachment #1: Type: text/plain, Size: 794 bytes --]

C11 has introduced atomic types and atomic operations.  When they are not
available, one can use locks/mutexes instead.

It would be nice if there was a Gnulib module that abstracts over this,
much like the threadlib module and friends abstract over a specific
threading implementation.

What I am thinking of is the following: Given a type T, a new Gnulib module
atomic allows the declaration of an atomic version of type T.  This is
straightforward on a platform that has <stdatomic.h>.  Otherwise the atomic
version of T would be a struct consisting of an object of type T together
with a lock.

The rest of the module would then provide some simple atomic primitives
like fetch_and_add, etc. that are either mapped to the C11 stdatomic
counterparts or are implemented using the lock.

Marc

[-- Attachment #2: Type: text/html, Size: 1404 bytes --]

Re: Module suggestion: Atomic operations

[Bruno Haible]

Hi Marc,

> C11 has introduced atomic types and atomic operations.  When they are not
> available, one can use locks/mutexes instead.
> 
> It would be nice if there was a Gnulib module that abstracts over this,
> much like the threadlib module and friends abstract over a specific
> threading implementation.
> 
> What I am thinking of is the following: Given a type T, a new Gnulib module
> atomic allows the declaration of an atomic version of type T.  This is
> straightforward on a platform that has <stdatomic.h>.  Otherwise the atomic
> version of T would be a struct consisting of an object of type T together
> with a lock.
> 
> The rest of the module would then provide some simple atomic primitives
> like fetch_and_add, etc. that are either mapped to the C11 stdatomic
> counterparts or are implemented using the lock.

Yes, given that the platform support for these atomic types/operations is
increasing, it would accelerate the adoption if there was a Gnulib module,
like you describe it. Program developers could then adopt <stdatomic.h>
without losing portability to a number of platforms.

Personally I'm not very motivated to work on that (because in most algorithms
I've seen, mutexes/locks are the way to go, and because I find the memory_order
stuff hard to understand). But if you want to work on that, it will be
welcome!

Bruno

Re: Module suggestion: Atomic operations

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am So., 24. Mai 2020 um 22:54 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> Yes, given that the platform support for these atomic types/operations is
> increasing, it would accelerate the adoption if there was a Gnulib module,
> like you describe it. Program developers could then adopt <stdatomic.h>
> without losing portability to a number of platforms.

So, you mean that Gnulib should try to provide <stdatomic.h> in case
it is not available? I have to think about it whether this can ever
work (and in an efficient way).

When I raised the question, I was more thinking of a custom interface
that abstracts both over <stdatomic.h> and some other implementation
with explicit mutexes, much like the tls module abstracts over C11's
TLS and some other implementations, like the pthread one.

One problem with <stdatomic.h> as given is that atomic values have no
destructors. Thus, we cannot simply attach locks to them in a pre-C11
implementation because there is no place to destroy the locks. Thus,
we would have to work with a pool of locks shared by all atomic
variables. But when to set up the pool?

A module atomic with a header "atomic.h" could implement an interface
that has destructors (which are mapped to no-ops when <stdatomic.h> is
available).

> Personally I'm not very motivated to work on that (because in most algorithms
> I've seen, mutexes/locks are the way to go, and because I find the memory_order
> stuff hard to understand). But if you want to work on that, it will be
> welcome!

I should wait for the copyright assignment first. As for the
memory_order things. A first version of the module may map everything
to memory_order_seq_cst, which is safe but not always the most
efficient.

Marc

Re: Module suggestion: Atomic operations

[Bruno Haible]

Hi Marc,

> One problem with <stdatomic.h> as given is that atomic values have no
> destructors. Thus, we cannot simply attach locks to them in a pre-C11
> implementation because there is no place to destroy the locks.

Ah...

> Thus, we would have to work with a pool of locks shared by all atomic
> variables. But when to set up the pool?

Pools have the drawback that they add a configuration requirement on the
application: What is the default size of the pool? When to increase the
pool size? By how much? When to shrink the pool? The developer would have
determine good answers to this, but 5 years later or under specific
circumstances the answers may not be good enough. (*)

Therefore, I would avoid pools, unless strictly necessary for performance
reasons. And if you need pools already in the design phase, you've been
doing a mistake.

> A module atomic with a header "atomic.h" could implement an interface
> that has destructors (which are mapped to no-ops when <stdatomic.h> is
> available).

Yes, that's the better way to approach it, then.

Bruno

(*) A very good example is the "pool of registers" design in the SPARC
    architecture, with the sliding register windows. In the later SPARC
    processors, they have been nothing but a source of complexity.

Re: Module suggestion: Atomic operations

[Marc Nieper-Wißkirchen]

Hi Bruno,

Am Mo., 25. Mai 2020 um 09:24 Uhr schrieb Bruno Haible <bruno@clisp.org>:

> Pools have the drawback that they add a configuration requirement on the
> application: What is the default size of the pool? When to increase the
> pool size? By how much? When to shrink the pool? The developer would have
> determine good answers to this, but 5 years later or under specific
> circumstances the answers may not be good enough. (*)

For general types, the gcc (and clang) implementations use general
locks coming from a pool. (In the gcc case, see libatomic and,
especially, libat_lock_n.) Nevertheless, I agree with you that a pool
is suboptimal.

> Yes, that's the better way to approach it, then.

There is one problem with providing some emulation with Posix locks,
though. At least one type in <stdatomic.h> is guaranteed to be
lock-free, the atomic flag. Since C18, it can be used in signal
handlers, where Posix locks won't work because they are not
async-safe. Moreover, <stdatomic.h> provides memory fences, which I
don't know how to emulate in general and which also seem to be crucial
in signal handlers of multithreaded applications.

It seems to me that a substitute of <stdatomic.h> needs to know a bit
about the underlying compiler (so that builtins can be used) or the
underlying architecture (for example, x86 does not need memory fences
with the release or acquire memory order. Unfortunately, my knowledge
about other compilers than gcc or other architectures than x86 is
limited. I could provide the skeleton of a substitute, but it would
need other people to add their architectures.

Marc

Re: Module suggestion: Atomic operations

[Bruno Haible]

Hi Marc,

> At least one type in <stdatomic.h> is guaranteed to be
> lock-free, the atomic flag. Since C18, it can be used in signal
> handlers, where Posix locks won't work because they are not
> async-safe. Moreover, <stdatomic.h> provides memory fences, which I
> don't know how to emulate in general and which also seem to be crucial
> in signal handlers of multithreaded applications.
> 
> It seems to me that a substitute of <stdatomic.h> needs to know a bit
> about the underlying compiler (so that builtins can be used) or the
> underlying architecture (for example, x86 does not need memory fences
> with the release or acquire memory order. Unfortunately, my knowledge
> about other compilers than gcc or other architectures than x86 is
> limited. I could provide the skeleton of a substitute, but it would
> need other people to add their architectures.

Once things become compiler and architecture dependent, there are a
lot of (compiler, architecture) pairs to support. Using gcc/clang unless
mentioned otherwise:

  - i386: Linux, Solaris, macOS, Hurd, FreeBSD, NetBSD, OpenBSD, Haiku,
          Cygwin, mingw,
  - i386: Solaris (cc)
  - i386: Windows (MSVC)

  - x86_64: Linux, Solaris, macOS, FreeBSD, NetBSD, OpenBSD, Haiku,
            Cygwin, mingw,
  - x86_64: Solaris (cc)
  - x86_64: Windows (MSVC)
  - x86_64: Linux with x32 ABI (CC="gcc -mx32")

  - m68k: Linux

  - mips: Linux 32-bit, little-endian and big-endian
  - mips: Linux n32, little-endian and big-endian
  - mips: Linux 64-bit, little-endian and big-endian
  - mips: IRIX 6.5 (CC="gcc -mabi=n32")

  - sparc: Linux, Solaris, NetBSD
  - sparc: Solaris (cc)

  - sparc64: Linux, Solaris, NetBSD
  - sparc64: Solaris (cc)

  - alpha: Linux

  - hppa: Linux

  - arm: Linux

  - arm64: Linux, FreeBSD

  - powerpc: Linux, macOS, AIX
  - powerpc: AIX (xlc)

  - powerpc64: Linux (little-endian and big-endian), AIX
  - powerpc64: AIX (xlc)

  - ia64: Linux

  - s390: Linux

  - s390x: Linux

  - riscv32: Linux with ilp32d ABI.
  - riscv64: Linux with lp64d ABI.

It is a *lot* of work, alone to test these. If you have special code for
each of these platforms, we won't be done with it in any reasonable time.
Therefore it's essential, IMO, to use platform independent code as far as
possible.

Compiler builtins (of gcc and clang), like you suggest, are a good way to
support a large number of the platforms. But you also have to find a
solution for
  - Solaris (cc)
  - Windows (MSVC)
  - AIX (xlc)

For some of these, you can get an account on a test machine, see [1].

I agree that atomic flags and memory barriers are the essential ones (and
maybe hardest) to support.

You can leave testing to others, once the code is expected to work and
once you have provided good unit tests.

Bruno

[1] https://gitlab.com/ghwiki/gnow-how/-/wikis/Platforms/Machines

Re: Module suggestion: Atomic operations

[Bruno Haible]

Marc Nieper-Wißkirchen wrote in
<https://lists.gnu.org/archive/html/bug-gnulib/2020-05/msg00289.html>:
> C11 has introduced atomic types and atomic operations.  When they are not
> available, one can use locks/mutexes instead.
> 
> It would be nice if there was a Gnulib module that abstracts over this,
> much like the threadlib module and friends abstract over a specific
> threading implementation.

Practically speaking, the GCC built-ins available since GCC 4.1, and then
later extended on GCC 4.7, fulfill most of the needs regarding atomics. Only
AIX and SUNpro C on Solaris need to be handled on a case-by-case basis.

Bruno