CVS difference for ai12s/ai12-0234-1.txt

Differences between 1.12 and version 1.13
Log of other versions for file ai12s/ai12-0234-1.txt

--- ai12s/ai12-0234-1.txt	2019/03/09 05:27:45	1.12
+++ ai12s/ai12-0234-1.txt	2019/03/10 01:34:26	1.13
@@ -1,4 +1,6 @@
-!standard A.19(0)                                      19-03-07  AI12-0234-1/04
+!standard C.6.1(0)                                  19-03-09  AI12-0234-1/05
+!standard C.6.2(0)
+!standard C.6.3(0)
 !class Amendment 17-06-09
 !status work item 17-06-09
 !status received 17-05-19
@@ -9,16 +11,15 @@
 
 !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
-progress.
+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 progress.
+
 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.
@@ -41,18 +42,27 @@
 Ada should provide a way to more portably insert
 Compare-And-Swap instructions into an application.
 
+Another related capability is to simply swap the value of an atomic
+variable with another value. That is, write to an atomic variable,
+and atomically retrieve the original value of the variable before the
+write operation. Such a capability can be useful for creating Spin-Locks,
+for example. Ada should provide a way to more portably insert Swap
+instructions into an application?
+
 !proposal
 
-The solution is to provide a standard library call that maps to commonly
-available atomic hardware instructions that perform compare and swap
-operations. This subprogram is to be an intrinsic call. If the target
-architecture does not support compare-and-swap instructions, then
-the subprogram is implemented to produce the same result using
-proper synchronization for concurrent access.
+The solution is to provide a couple of standard library calls that map
+to commonly available atomic hardware instructions; One of which that
+performs atomic compare and swap operations, and the other of which
+that performs atomic swap operations. These subprograms are to be
+intrinsic calls. If the target architecture does not support these
+operations with simple machine instructions, then the subprograms are
+implemented to produce the same result using proper synchronization for
+concurrent access.
 
 The library is a generic function in order to support operations on
 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
+be atomic types, so that Ada's semantics of atomic types can be associated
 with this primitive operation.
 
 This proposal depends on the ability to specify the Atomic aspect for a generic
@@ -61,7 +71,7 @@
 
 !wording
 
-A.19 Atomic Operations
+C.6.1 Atomic Operations
 
 This clause presents the specifications of the package Atomic_Operations and
 its child packages, which provide facilities for manipulating
@@ -70,101 +80,116 @@
 in order to provide convenient access to machine operations that can
 provide these capabilities if they are available in the target environment.
 
-A.19.1  The Package Atomic_Operations
+C.6.2  The Package System.Atomic_Operations
 
-The library package Ada.Atomic_Operations is the parent of a set of child units
-that provide facilities for manipulating objects of atomic types.
+The library package System.Atomic_Operations is the parent of a set of child
+units that provide facilities for manipulating objects of atomic types.
 
 Static Semantics
 
 The following language-defined library package exists:
 
-package Ada.Atomic_Operations
+package System.Atomic_Operations
    with Pure, Nonblocking is
-end Ada.Atomic_Operations;
+end System.Atomic_Operations;
 
-Ada.Atomic_Operations serves as the parent of other language-defined library
+System.Atomic_Operations serves as the parent of other language-defined library
 units that manipulate atomic objects; its declaration is empty.
+
+A call to a subprogram is said to be *lock-free* if the subprogram
+is guaranteed to return from the call while keeping the processor of
+logical thread of control busy for the duration of the call.
 
-A.19.2  The Generic Function Atomic_Operations.Atomic_Compare_And_Exchange
+In each child package, a function Is_Lock_Free(...) is provided to check
+whether the operations of the child package can all be provided lock-free
+for a given object. Is_Lock_Free returns True if operations defined in
+the child package are lock-free when applied to the
+object denoted by Item, otherwise Is_LocK_Free returns False.
+
+C.6.3  The Generic Package System.Atomic_Operations.Exchange
+
+The language-defined generic package System.Atomic_Operations.Exchange
+provides the following operations:
+
+  - To atomically compare the value of two atomic objects, and update the first
+    atomic object with a desired value if both objects were found to be equal,
+    or otherwise update the second object with the value of the first object.
 
-The language-defined generic function
-Atomic_Operations.Atomic_Compare_And_Exchange provides an operation to
-atomically compare the value of two atomic objects, and update the first atomic
-object with a desired value if both objects were found to be equal, or otherwise
-update the second object with the value of the first object.
+  - To atomically update the value of an atomic object, and then
+    return the value that the atomic object had just prior to the update.
 
 Static Semantics
 
 The library function Ada.Atomic_Operations.Atomic_Compare_And_Exchange has the
 following declaration:
 
+The library package System.Atomic_Operations.Exchange has the
+following declaration:
+
 generic
    type Atomic_Type is private with Atomic;
-function Ada.Atomic_Operations.Atomic_Compare_And_Exchange
-     (Item     : aliased in out Atomic_Type;
-      Expected : aliased in out Atomic_Type;
-      Desired  :                Atomic_Type) return Boolean
-   with Nonblocking, Global => null, Convention => Intrinsic;
-
-Compares the value denoted by Item with the value denoted by Expected.
-If equal, the operation is a read-modify-write operation that writes
-the value denoted by Desired into Item. If they are not equal, the operation
-is a read and the value denoted by Item is written into Expected.
-If Desired is written into Item then True is returned. Otherwise, False is
-returned.
+package System.Atomic_Operations.Exchange
+   with Pure, Nonblocking is
 
-A.19.3  The Generic Function Atomic_Operations.Is_Lock_Free
+   function Atomic_Exchange (Item  : aliased in out Atomic_Type;
+                             Value : Atomic_Type) return Atomic_Type
+     with Convention => Intrinsic;
 
-A call to a subprogram is said to be *lock-free* if the subprogram
-is guaranteed to return from the call while keeping the processor of
-logical thread of control busy for the duration of the call.
+   function Atomic_Compare_And_Exchange (Item     : aliased in out Atomic_Type;
+                                         Expected : aliased in out Atomic_Type;
+                                         Desired  : Atomic_Type) return Boolean
+     with Convention => Intrinsic;
 
-The language-defined generic function Ada.Atomic_Operations.Is_Lock_Free
-provides an operation to test whether the operations of the other child units
-of Atomic_Operations are lock-free operations when applied to a specific
-object of an atomic type.
+   function Is_Lock_Free (Item : aliased Atomic_Type) return Boolean
+     with Convention => Intrinsic;
 
-Static Semantics
+end Atomic_Operations.Exchange;
 
-The library function Ada.Atomic_Operations.Is_Lock_Free has the
-following declaration:
+Atomic_Exchange writes the value denoted by Value into Item, and returns
+the previous value denoted by Item.
 
-generic
-   type Atomic_Type is private; -- with Atomic;
-function Ada.Atomic_Operations.Is_Lock_Free
-  (Item : aliased Atomic_Type) return Boolean
-  with Nonblocking, Global => null, Convention => Intrinsic
-
-function Is_Lock_Free (Item : aliased Atomic_Type) return Boolean
-with Convention => Intrinsic;
-
-Returns true if operations defined in other child units of Atomic_Operations
-are lock-free when applied to the object denoted by Item.
-
-NOTES
-Some target environments do not always support lock-free machine operations
-for objects of a certain size.
-For example, a 64 bit target environment might support atomic lock-free
-operations on objects that are 64 bits in size, but when executed on a
-32 bit target environment, such machine operations may not be available,
-and the calls to Atomic_Compare_And_Exchange would need to switch over
-to a locking implementation.
+Atomic_Compare_And_Exchange compares the value denoted by Item with the
+value denoted by Expected. If equal, the operation is a read-modify-write
+operation that writes the value denoted by Desired into Item. If they are
+not equal, the operation is a read and the value denoted by Item is
+written into Expected.
+If Desired is written into Item then True is returned. Otherwise, False is returned.
+
+Examples
+
+Example of a spinlock using Atomic_Exchange
+
+type Atomic_Boolean is new Boolean with Atomic;
+package Exchange is new Atomic_Operations.Exchange (Atomic_Type => Atomic_Boolean);
+
+Lock : aliased Atomic_Boolean := False;
+
+...
 
-Similarly, the alignment of an object may determine whether lock free
-operations may be applied.
+begin --  Some critical section, trying to get the lock:
 
+  --  Obtain the Spinlock
+  while (Exchange.Atomic_Exchange (Item => Lock, Value => Atomic_Boolean(True))
+  loop
+     null;
+  end loop
+
+  ... -- do stuff
+
+  lock := False; -- Release the lock
+end;
+
 !discussion
 
-The solution needs to be generic, in order to work with different
+The solution needs to be generic in order to work with different
 atomic types. For that to make sense, it is necessary to allow aspect Atomic
 to be given on the formal type, in order to require any actual type is indeed
 atomic. The alternative of just saying that if the type is not atomic, then the
 operation isn't either, seems error-prone.
 
 Many lock free algorithms involve atomic primitives such as compare and swap
-instructions or load and store instuctions. Most target platforms provide some
-form of machine instructions in this category.
+instructions. Most target platforms provide some form of machine instructions
+in this category.
 
 However, most target architectures have limits on the size of objects that
 can be mapped to hardware machine instructions. Furthermore, some target
@@ -180,8 +205,9 @@
 lock-free instructions may be used on some architectures.
 
 To allow the programmer to query the implementation to determine if
-the operations declared in child units of Ada.Atomic_Operations can be
-executed as lock-free calls, a generic function is provided: Is_Lock_Free.
+the operations declared in child units of System.Atomic_Operations can be
+executed as lock-free calls, an additional function is provided in each
+of the child packages: Is_Lock_Free.
 
 The gcc intrinsic libraries also provide a call to determine if the
 target environment always provides lock-free versions of the calls, for
@@ -253,17 +279,6 @@
 We could add a separate call in the future that exposes the Weak parameter,
 if there is enough need for such a capability.
 
-It was considered whether Atomic_Compare_And_Exchange should be a function
-in a generic package, along with potentially an Atomic_Exchange function.
-
-There are the only two functions that likely could be grouped together
-in the same package. It seemed better to not group these together,
-as they are typically used for different purposes. There also is a third
-function in this category, Test_And_Set, but that would need to be a separate
-child package because it does not need to be generic. It seems like a
-better design to have these as 3 capabilities as separate child units
-for these reasons.
-
 !ASIS
 
 No ASIS effect.
@@ -3301,28 +3316,58 @@
 From: Brad Moore
 Sent: Friday, March 8, 2019  12:55 AM
 
-> 
+>
 > ...
 >> A.19 Atomic Operations
-> 
-> I haven't mentioned this before, but A.19 is Ada.Locales in Ada 2012. 
+>
+> I haven't mentioned this before, but A.19 is Ada.Locales in Ada 2012.
 > It's not a very good choice for the number of a new clause. :-)
-> 
+>
 > More seriously...
-> 
->> The library package Ada.Atomic_Operations is the parent of a set of 
->> child units that provide facilities for manipulating objects of 
+>
+>> The library package Ada.Atomic_Operations is the parent of a set of
+>> child units that provide facilities for manipulating objects of
 >> atomic types.
-> 
-> Shouldn't this package be a child of System? And in Annex C (since 
+>
+> Shouldn't this package be a child of System? And in Annex C (since
 > that's where Atomic is defined, after all).
-> 
-> So I'd suggest defining this in C.6.1 and later subclauses (since it's 
-> related to atomic), and have it be a child of System (it's only useful 
+>
+> So I'd suggest defining this in C.6.1 and later subclauses (since it's
+> related to atomic), and have it be a child of System (it's only useful
 > for rather low-level programming).
+
+That sounds good to me Randy. Definitely a better locale for this stuff, so
+to speak.... :-)
+
+****************************************************************
+
+From: Brad Moore
+Sent: Saturday, March 9, 2019  12:47 PM
+
+Here is an update to AI12-0234-1. [This is version /05 of the AI - Editor.]
+
+The main differences are;
+
+- As per Randy's suggestions, moved these packages an child packages under
+package System, rather than package Ada, and moved the wording sections to Annex
+C, just after the existing section C.6, Shared Variable Control, which seems
+much more appropriate place for this stuff.
+
+- Changed the generic function Atomic_Compare_And_Exchange into a generic
+package that contains two functions,
+
+    Atomic_Compare_And_Exchange, and Atomic_Exchange.
+
+Atomic_Exchange was previously split off into the new AI, but it seems more
+appropriate to include it here in this AI, since it is in the same package as
+Atomic_Compare_And_Exchange, and they have similar capabilities.
+
+- Instead of a generic Is_Lock_Free function that needs to be instantiated
+separately, there is an Is_Lock_Free function that will be in each of the child
+packages of System.Atomic_Operations. This allows a programmer to query if the
+target environment allows the functions to be implemented lock-free.
 
-That sounds good to me Randy. Definitely a better locale for this stuff, so 
-to speak.... :-) 
+- Added an example of a spinlock using Atomic_Exchange
 
 ****************************************************************
 

Questions? Ask the ACAA Technical Agent