Version 1.1 of ai12s/ai12-0321-1.txt

Unformatted version of ai12s/ai12-0321-1.txt version 1.1
Other versions for file ai12s/ai12-0321-1.txt

!standard A.19(0)          18-06-06 AI12-0234-1/03
!class Amendment 17-06-09
!status work item 17-06-09
!status received 17-05-19
!priority Low
!difficulty Easy
!subject Support for Arithmetic Atomic Operations, Test and Set, and Atomic Exchange
!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 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.
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 compare and swap, test and set, and atomic increment. These subprograms are to be intrinsic calls, and the generic libraries will assert an error if a particular target platform does not support such atomic operations.
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
A.19.3 The Generic Function Atomic_Operations.Atomic_Exchange
The language-defined generic function Atomic_Operations.Atomic_Exchange provides an operation to atomically exchange the values of two atomic objects.
Static Semantics
The library function Ada.Atomic_Operations.Atomic_Exchange has the following declaration:
generic type Atomic_Type is private with Atomic; function Ada.Atomic_Operations.Atomic_Exchange (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Nonblocking, Global => null, Convention => Intrinsic;
function Atomic_Exchange (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Boolean with Nonblocking, Global => null, Convention => Intrinsic;
Writes the value denoted by Value into Item, and returns the previous value denoted by Item.
A.19.3 The Package Atomic_Operations.Test_And_Set
The language-defined package Atomic_Operations.Test_And_Set provides an operation to atomically set and clear an atomic flag object.
Static Semantics
The library package Ada.Atomic_Operations.Test_And_Set has the following declaration:
package Ada.Atomic_Operations.Test_And_Set with Pure, Nonblocking is
type Test_And_Set_Flag is mod <implementation-defined> with Atomic, Default_Value => 0, Size => <Implementation-Defined>;
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;
end Ada.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.
function Atomic_Test_And_Set
(Item : aliased in out Test_And_Set_Flag) return Boolean with Convention => Intrinsic;
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".
procedure Atomic_Clear
(Item : aliased in out Test_And_Set_Flag) with Convention => Intrinsic;
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.
A.19.4 The Package Atomic_Operations.Arithmetic
The language-defined package Atomic_Operations.Arithmetic provides operations to perform arithmetic atomically on objects of modular types.
Static Semantics
The library package Ada.Atomic_Operations.Arithmetic has the following declaration:
generic type Atomic_Type is mod <> with Atomic; package Ada.Atomic_Operations.Arithmetic with Pure, Nonblocking is
function Atomic_Add_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Subtract_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Bitwise_And_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Bitwise_Or_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Xor_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Nand_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return 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 Atomic_Fetch_And_Nand (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
end Atomic_Operations.Arithmetic;
The following functions perform the operation suggested by the name, and return the result of the operation.
i.e. Item := Item op Value; return Item;
function Atomic_Add_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Subtract_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Bitwise_And_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Convention => Intrinsic;
function Atomic_Bitwise_Or_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Intrinsic;
function Atomic_Xor_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return Atomic_Type with Intrinsic;
function Atomic_Nand_And_Fetch (Item : aliased in out Atomic_Type; Value : Atomic_Type) return 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;
function Atomic_Fetch_And_Nand (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 algoriths, particularly if porting those applications from other languages.
It was considered whether signed arithmetic functions should be provided. While it is possible, the routines would be trickier to write because we would want Ada semantics on arithmetic overflow, which doesn't happen with the low-level gcc instrinsic functions. This would mean using the pre-fetch library calls to obtain the value before the operation, and then applying the operation again on a result variable in addition to the atomic variable, so that any overflow could be detected, and an exception raised. THe modular arithmetic functions are simpler, and can be simply mapped to the underlying calls, since arithmetic overflow handling is not needed. We could add signed arithmetic in the future, if the need is great enough.
!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.

****************************************************************

Questions? Ask the ACAA Technical Agent