--- ai12s/ai12-0321-1.txt 2019/03/08 07:21:04 1.2 +++ ai12s/ai12-0321-1.txt 2019/03/10 01:52:31 1.3 @@ -1,10 +1,11 @@ -!standard A.19(0) 19-03-07 AI12-0321-1/01 +!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, Test and Set, and Atomic Exchange +!subject Support for Arithmetic Atomic Operations and Test and Set !summary !problem @@ -22,12 +23,12 @@ 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. +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. +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. @@ -38,10 +39,8 @@ 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. +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 @@ -50,44 +49,18 @@ !wording -A.19.3 The Generic Function Atomic_Operations.Atomic_Exchange +C.6.4 The Package System.Atomic_Operations.Test_And_Set -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 +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 Ada.Atomic_Operations.Test_And_Set has the +The library package System.Atomic_Operations.Test_And_Set has the following declaration: -package Ada.Atomic_Operations.Test_And_Set with Pure, Nonblocking -is +package System.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>; @@ -99,72 +72,58 @@ 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 Ada.Atomic_Operations.Test_And_Set; +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. -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; +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". -Performs an atomic clear operation on Item. After the operation, Item -contains 0. This call should be used in conjunction with +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. -A.19.4 The Package Atomic_Operations.Arithmetic +C.6.5 The Package System.Atomic_Operations.Arithmetic -The language-defined package 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 Ada.Atomic_Operations.Arithmetic has the +The library package System.Atomic_Operations.Arithmetic has the following declaration: generic - type Atomic_Type is mod <> with Atomic; -package Ada.Atomic_Operations.Arithmetic with Pure, Nonblocking -is + type Atomic_Type is range <> with Atomic; +package System.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 + procedure Atomic_Add (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Convention => Intrinsic; - function Atomic_Bitwise_And_And_Fetch - (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Subtract (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Convention => Intrinsic; - function Atomic_Bitwise_Or_And_Fetch - (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Bitwise_And (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Convention => Intrinsic; - function Atomic_Xor_And_Fetch - (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Bitwise_Or (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Convention => Intrinsic; - function Atomic_Nand_And_Fetch - (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Xor (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Convention => Intrinsic; function Atomic_Fetch_And_Add @@ -192,39 +151,32 @@ 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 + function Is_Lock_Free (Item : aliased Atomic_Type) return Boolean with Convention => Intrinsic; -end Atomic_Operations.Arithmetic; +end System.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; +The following procedures perform the operation suggested by the name. + i.e. Item := Item op Value; - function Atomic_Add_And_Fetch (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type - with Convention => Intrinsic; + procedure Atomic_Add (Item : aliased in out Atomic_Type; + Value : Atomic_Type) + with 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; + procedure Atomic_Subtract (Item : aliased in out Atomic_Type; + Value : Atomic_Type) + with Intrinsic; - function Atomic_Bitwise_Or_And_Fetch (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Bitwise_And (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Intrinsic; - function Atomic_Xor_And_Fetch (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Bitwise_Or (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Intrinsic; - function Atomic_Nand_And_Fetch (Item : aliased in out Atomic_Type; - Value : Atomic_Type) return Atomic_Type + procedure Atomic_Xor (Item : aliased in out Atomic_Type; + Value : Atomic_Type) with Intrinsic; The following functions perform the operation suggested by the name, @@ -251,11 +203,7 @@ 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 @@ -263,20 +211,17 @@ 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 +implement specific lock free algorithms, particularly if porting those applications from other languages. -It was considered whether signed arithmetic functions should be provided. +It was considered whether modular 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. +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 @@ -304,5 +249,79 @@ 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. + +**************************************************************** -**************************************************************** \ No newline at end of file

Questions? Ask the ACAA Technical Agent