!standard C.6.4(0) 19-03-09 AI12-0321-1/02
!standard C.6.5(0)
!class Amendment 19-03-07
!status work item 19-03-07
!status received 19-03-07
!priority Low
!difficulty Easy
!subject Support for Arithmetic Atomic Operations and Test and Set
!summary
!problem
On multiprocessor platforms, relying on locks for synchronization can be
problematic. One issue is that while a task is blocked, it can be difficult or
impossible to offer guarantees for progress. Other problems associated with
locks includes deadlock, livelock, and priority inversion. Locking can also be a
significant detriment to performance, and reduce opportunities for parallelism.
Lock-free data structures guarantee system-wide progress, while wait-free data
structures, in addition to being lock-free, also guarantee per-thread progresss.
Lock-free data structures can also be used to improve performance by increasing
the amount of time spent executing in parallel since access to the data
structure does not need to be serialised.
AI12-0234-1 provides access to swap and compare-and-swap operations, but there
are other useful operations that could be provided as atomic primitives.
Atomic arithmetic, such as being able to atomically increment an atomic
counter is a common use for atomic operations. Another common need in this
area is to create spin-locks in user space via test and set instructions.
Ada should provide some simple primitives that can be mapped to hardware
instructions that allow such updates to perform as expected.
!proposal
This proposal depends on AI12-0234-1, which defines the parent package
Ada.Atomic_Operations.
The solution is to provide a set of standard library calls that map to commonly
available atomic hardware instructions such as test and set, and atomic
increment. These subprograms are to be intrinsic calls.
The libraries are generic libraries in order to support operations on discrete
types of different sizes, and we require that the actual types for the generics
be atomic types, so that Ada's semantics of atomic types can be associated
with these primitive operations.
!wording
C.6.4 The Package System.Atomic_Operations.Test_And_Set
The language-defined package System.Atomic_Operations.Test_And_Set
provides an operation to atomically set and clear an atomic flag object.
Static Semantics
The library package System.Atomic_Operations.Test_And_Set has the
following declaration:
package System.Atomic_Operations.Test_And_Set
with Pure, Nonblocking is
type Test_And_Set_Flag is mod
with Atomic, Default_Value => 0, Size => ;
function Atomic_Test_And_Set
(Item : aliased in out Test_And_Set_Flag) return Boolean
with Convention => Intrinsic;
procedure Atomic_Clear
(Item : aliased in out Test_And_Set_Flag)
with Convention => Intrinsic;
function Is_Lock_Free
(Item : aliased Test_And_Set_Flag) return Boolean
with Convention => Intrinsic;
end System.Atomic_Operations.Test_And_Set;
Test_And_Set_Flag represents the state of an atomic flag object.
An atomic flag object can either be considered to be set or cleared.
Atomic_Test_And_Set performs an atomic test-and-set operation on Item.
Item is set to some implementation defined nonzero "set" value and the
return value is true if and only if the previous contents were "set".
Atomic_Clear performs an atomic clear operation on Item. After the
operation, Item contains 0. This call should be used in conjunction with
Atomic_Test_And_Set.
C.6.5 The Package System.Atomic_Operations.Arithmetic
The language-defined package System.Atomic_Operations.Arithmetic
provides operations to perform arithmetic atomically on objects of
modular types.
Static Semantics
The library package System.Atomic_Operations.Arithmetic has the
following declaration:
generic
type Atomic_Type is range <> with Atomic;
package System.Atomic_Operations.Arithmetic
with Pure, Nonblocking is
procedure Atomic_Add (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Subtract (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Bitwise_And (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Bitwise_Or (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Xor (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
function Atomic_Fetch_And_Add
(Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Convention => Intrinsic;
function Atomic_Fetch_And_Subtract
(Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Convention => Intrinsic;
function Atomic_Fetch_And_Bitwise_And
(Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Convention => Intrinsic;
function Atomic_Fetch_And_Bitwise_Or
(Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Convention => Intrinsic;
function Atomic_Fetch_And_Xor
(Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Convention => Intrinsic;
function Is_Lock_Free (Item : aliased Atomic_Type) return Boolean
with Convention => Intrinsic;
end System.Atomic_Operations.Arithmetic;
The following procedures perform the operation suggested by the name.
i.e. Item := Item op Value;
procedure Atomic_Add (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Intrinsic;
procedure Atomic_Subtract (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Intrinsic;
procedure Atomic_Bitwise_And (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Intrinsic;
procedure Atomic_Bitwise_Or (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Intrinsic;
procedure Atomic_Xor (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Intrinsic;
The following functions perform the operation suggested by the name,
and return the value that had previously been in Item.
i.e. Tmp := Item; Item := Item op Value; return Tmp;
function Atomic_Fetch_And_Add (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
function Atomic_Fetch_And_Subtract (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
function Atomic_Fetch_And_Bitwise_And (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
function Atomic_Fetch_And_Bitwise_Or (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
function Atomic_Fetch_And_Xor (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
!discussion
The approach taken to improving support for lock free data structures is to
provide a set of libraries of low level atomic primitives similar to the library
that is provided by gcc for C and C++.
The library of intrinsic primitives might be of interest to those wishing to
implement specific lock free algorithms, particularly if porting those applications
from other languages.
It was considered whether modular arithmetic functions should be provided.
While it is possible, the routines would be trickier to write because
in the cases where the modulus of the modular types is not a multiple of
System.Storage_Unit. For such cases, updating an atomic variable might
need to include a write back to the the atomic variable to handle the
wrap around. With signed arithmetic, we need to generate Constraint_Error
for overflow checks, so checking for overflow is needed. But if
extra performance is needed, those checks can be suppressed.
!ASIS
No ASIS effect.
!ACATS test
An ACATS C-Test is needed to check that the new capabilities are supported.
!appendix
From: Brad Moore
Sent: Thursday, March 07, 2019 6:03 PM
Here is my first draft for a new AI on additional atomic operations.
This content was split off from AI12-0234-1.
[This is version /01 of this AI - Editor.]
I eliminated functions that did not seem to be needed, such as atomic load,
atomic store, and atomic fences.
I also eliminated the signed arithmetic package. The modular arithmetic better
maps to the underlying calls, since the signed onces would need to support
detection of arithmetic overflow, which the underlying gcc instrinsic functions
do not do. We could add signed arithmetic functions in the future if the need
was great enough.
****************************************************************
From: Brad Moore
Sent: Saturday, March 09, 2019 1:51 PM
Here is an update to AI12-0321-1 [This is version /02 of the AI - Editor.]
The main changes are;
- Atomic_Exchange was pulled out of this AI, and moved to AI12-234-1
- The child packages of Atomic_Operations, are rooted under package System, rather than package Ada.
- Wording was moved to follow section C.6, Shared Variable Control
- The functions of the form
Atomic_xxx_And_Fetch were removed.
The C standard only defines Atomic_Fetch_And_xxx functions, and it didn't seem
like it was worth providing both forms.
- The following procedures were added to Atomic_Operations.Arithmetic
procedure Atomic_Add (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Subtract (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Bitwise_And (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Bitwise_Or (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
procedure Atomic_Xor (Item : aliased in out Atomic_Type;
Value : Atomic_Type)
with Convention => Intrinsic;
This is because all the other functions return the original value before the
operation was applied, and in many cases, the user will not need these values.
This can simplify the implementation of the calls, and more optimal performance.
- The call
function Atomic_Fetch_And_Nand (Item : aliased in out Atomic_Type;
Value : Atomic_Type) return Atomic_Type
with Intrinsic;
Was removed. The C11 standard does not define this function, and it doesn't seem
likely that there is a great need to perform atomic nands.
If such a need materializes, we could add it in the future.
- Is_Lock_Free was added to the Test_And_Set child package and the Arithmetic
child package.
- The generic formal type for the Atomic_Operations.Arithmetic package was
changed from a modular generic formal type to a signed arithmetic generic
formal type.
This is because it was perceived that supporting atomic updates for modular
types where the modulus is not a multiple of the storage unit, is trickier, and
possibly requiring loops involving compare and swap.
Using signed arithmetic means there is a need to check for arithmetic overflow,
but that can be done without looping, and if performance is an issue, the
overflow checks can be suppressed.
****************************************************************