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

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

--- ai12s/ai12-0234-1.txt	2018/04/14 04:51:07	1.4
+++ ai12s/ai12-0234-1.txt	2018/05/11 05:32:48	1.5
@@ -1,4 +1,4 @@
-!standard C.6(14/3)                                  17-06-09  AI12-0234-1/01
+!standard C.6(14/3)                                  18-05-05  AI12-0234-1/02
 !class Amendment 17-06-09
 !status work item 17-06-09
 !status received 17-05-19
@@ -9,24 +9,481 @@
 
 !problem
 
-Lock-free structures are all the rage these days. If one wanted to construct
+A very desirable property of an Ada program on a single core computer is that
+it can be guaranteed to be deadlock free, with no unbounded priority inversions
+when the priority ceiling protocol is applied. Unfortunately, this property
+can not be easily proven for multi-tasking Ada programs executing on a multicore 
+processor. This is because a lock must be obtained prior to executing a protected
+action. For instance, consider two protected objects that have protected
+procedures that in turn call a protected procedure of the other object. If task 
+A calls protected object P1, which calls a protected procedure of P2, while 
+task B calls protected object P2, which calls a protected procedure of P1, 
+deadlock is a possibility, since both tasks will have acquired locks to one of 
+the protected objects, while waiting endlessly for the lock of the other 
+protected object. If the protected objects were implemented with lock free 
+algorithms, or if it could be guaranteed that all tasks that interact with a
+protected object execute on the same processor, then this deadlocking could be 
+avoided. Should Ada provide mechanisms to guarantee that deadlocking will not 
+occur when a program is executing on a multicore processor?
+
+Further, lock-free structures are all the rage these days. If one wanted to construct
 such a structure in Ada, one might use Atomic objects. But Ada does not
 provide any compare-and-swap operation (or other read-write locked operations,
 like atomic increment). The RM has Implementation Advice that package
 Machine_Code include such operations - C.1(11-12), but that is the absolute
-opposite of a portable operation.
+opposite of a portable operation. Similarly, arithmetic operations on variables
+of atomic types cannot be expected to work properly if updates are occurring
+concurrently to the same variable. Something as simple as A := A + 1; cannot
+be trusted because after reading the value of A, another task might store a 
+different value into A, and storing the incremented value could overwrite the
+update performed by the other task. Should Ada provide some simple primitives
+that can be mapped to hardware instructions that allow such updates to perform
+as expected? -- Yes
 
 !proposal
 
-(See Summary.)
+One part of this proposal is to allow the CPU aspect to be specified on a declaration
+of a protected type, or a stand alone protected object. This ensures that
+all tasks that invoke protected actions of a protected object are executing
+on the same CPU, which implies that the runtime can be simpler without needing
+locks to be acquired, thus avoiding deadlock.
+
+Another part of the solution is to provide a set of standard library calls that
+maps to commonly available atomic hardware instructions such as compare and swap,
+and test and set. 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.
+
+We would like the libraries to be generic to support operations on discrete types
+of different sizes, and we would like to require that the actual types for the
+generics be atomic types, so that the semantics of atomic types can be associated
+with these primitive operations. However, Ada currently does not allow the Atomic
+aspect to be specified on generic formal types, so one part of this proposal is
+to change the rules to allow that.
 
 !wording
+
+Modify D.16 (7/3) to allow aspect CPU to be applied to a protected type
+ 
+For a task type (including the anonymous type of a single_task_declaration)
+{, protected type (including the anonymous type of a single_protected_declaration),} 
+or subprogram, the following language-defined representation aspect may be specified:
+
+Modify D.16 (8.a/3)
+Aspect Description for CPU: Processor on which a given task{, or calling task 
+for a protected type} should run.
+
+Modify D.16 (10/3)
+The CPU aspect shall not be specified on a task { or protected }interface type.
+
+Modify D.16 (11/4)
+The expression specified for the CPU aspect of a task { or protected }type is 
+evaluated each time an object of the [task] type is created (see 9.1 {and 9.4}). 
+The CPU value is then associated with the [task] object.
+
+Modify D.16 (14/3)
+{For a task, the}[The] CPU value determines the processor on which the task will 
+activate and execute; the task is said to be assigned to that processor. If 
+the CPU value is Not_A_Specific_CPU, then the task is not assigned to a processor. 
+A task without a CPU aspect specified will activate and execute on the same 
+processor as its activating task if the activating task is assigned a processor. 
+If the CPU value is not in the range of System.Multiprocessors.CPU_Range or is 
+greater than Number_Of_CPUs the task is defined to have failed, and it becomes a 
+completed task (see 9.2).
+
+{For a protected type, the CPU value determines the processor on which calling tasks
+will execute; the protected object is said to be assigned to that processor. If 
+the CPU value is Not_A_Specific_CPU, then the protected object is not assigned to 
+a processor. A call to a protected object that is assigned to a processor from a
+task that is not assigned a processor or is assigned a different processor 
+raises Program_Error.}
+
+D.16 Implementation Advice
+
+Starting a protected action on a protected object assigned to a processor should 
+be implemented without busy-waiting.
+
+AARM Reason: Busy-waiting is a form of lock and can be a source of deadlock.
+Busy-waiting is typically needed for starting protected actions on multiprocessors, 
+but if all tasks calling a protected object execute on the same CPU, this locking 
+isn't needed and the source of deadlock and associated overhead can be eliminated. 
+
+Modify J.15.9 (4/3)
+A CPU pragma is allowed only immediately within a task_definition, {protected_definition, }
+or the declarative_part of a subprogram_body.
+
+Modify J.15.9 (6/3)
+For an implementation that supports Annex D, a pragma CPU specifies the value of 
+the CPU aspect (see D.16). If the pragma appears in a task_definition, the 
+expression is associated with the aspect for the task type or single_task_declaration 
+that contains the pragma{. If the pragma appears in a protected_definition, the 
+expression is associated with the aspect for the protected type or 
+single_protected_declaration that contains the pragma. Otherwise}[; otherwise], 
+the expression is associated with the aspect for the subprogram that contains the pragma.
+
+Modify K.1 (15/3)
+CPU   Processor on which a given task {, or calling task 
+for a protected type} should run. See D.16.
+
+A.19 Atomic Operations
+
+This clause presents the specifications of the package Atomic_Operations and 
+several child packages, which provide facilities for atomically manipulating discrete
+types, and for creating lock-free data types.
+
+A.19.1  The Package Atomic_Operations
+
+The package Atomic_Operations is the root of the atomic operations subsystem.
+ 
+Static Semantics
+
+The library package Atomic_Operations has the following declaration: 
+
+package Ada.Atomic_Operations is
+
+   pragma Pure;
+
+   type Test_And_Set_Type is mod 2**8;
+
+   Atomic_Support_Error : exception;
+   
+   function Atomic_Test_And_Set (Item : aliased in out Test_And_Set_Type) return Boolean
+     with Convention => Intrinsic
+     with Post => Item /= 0;
+
+   procedure Atomic_Clear (Item : aliased in out Test_And_Set_Type)
+     with Convention => Intrinsic
+     with Post => Item = 0;
+
+   procedure Atomic_Thread_Fence
+     with Convention => Intrinsic;
+
+   procedure Atomic_Signal_Fence
+     with Convention => Intrinsic;
+   
+end Ada.Atomic_Operations;
+
+Test_And_Set_Type represents the resulting state of a call to Atomic_Test_And_Set.
+
+Atomic_Support_Error is raised during elaboration of a child package of 
+Ada.Atomic_Operations if the implementation cannot map the instantiation to
+atomic operations of the target system.
+
+function Atomic_Test_And_Set (Item : aliased in out Test_And_Set_Type) return Boolean
+  with Convention => Intrinsic;
+     
+Performs an atomic test-and-set operation on Item. Item is set to some
+implementation defined "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_Type)
+  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.
+
+procedure Atomic_Thread_Fence
+   with Convention => Intrinsic;
+
+This procedure acts as a synchronization fence between threads.
+
+procedure Atomic_Signal_Fence
+   with Convention => Intrinsic;
+
+This procedure acts as a synchronization fence between a thread and
+signal handlers in the same thead.
+   
+A.19.2  The Generic Package Atomic_Operations.Storage
+
+The language-defined generic package Atomic_Operations.Storage provides a set of
+operations for atomically loading, storing, and comparing storage associated with
+discrete types.
+
+generic
+   type Atomic_Type is (<>) with Atomic;
+package Ada.Atomic_Operations.Storage is
+
+   pragma Pure;
+
+   function Atomic_Load (From : aliased Atomic_Type) return Atomic_Type
+    with Convention => Intrinsic;
+
+   procedure Atomic_Store (Into  : aliased in out Atomic_Type;
+                           Value : Atomic_Type)
+    with Convention => Intrinsic;
+
+   function Atomic_Exchange (Item  : aliased in out Atomic_Type;
+                             Value : Atomic_Type) return Atomic_Type
+    with Convention => Intrinsic;
+
+   function Atomic_Compare_And_Exchange (Item     : aliased in out Atomic_Type;
+                                         Expected : aliased in out Atomic_Type;
+                                         Desired  : Atomic_Type;
+                                         Weak     : Boolean) return Boolean
+    with Convention => Intrinsic;
+
+   function Atomic_Always_Lock_Free return Boolean
+   with Convention => Intrinsic;
+
+   function Atomic_Always_Lock_Free (Item : aliased Atomic_Type) return Boolean
+     with Convention => Intrinsic;
+
+   function Atomic_Is_Lock_Free (Item : aliased Atomic_Type) return Boolean;
+
+end Ada.Atomic_Operations.Storage;
+
+function Atomic_Load (From : aliased Atomic_Type) return Atomic_Type
+with Convention => Intrinsic;
+
+Returns the value of From
+
+procedure Atomic_Store (Into  : aliased in out Atomic_Type;
+                        Value : Atomic_Type)
+with Convention => Intrinsic;
+
+Writes Value into Into
+
+function Atomic_Exchange (Item  : aliased in out Atomic_Type;
+                          Value : Atomic_Type) return Atomic_Type
+with Convention => Intrinsic;
+
+Writes Value into Item, and returns the previous value of Item.
+
+function Atomic_Compare_And_Exchange (Item     : aliased in out Atomic_Type;
+                                      Expected : aliased in out Atomic_Type;
+                                      Desired  : Atomic_Type;
+                                      Weak     : Boolean) return Boolean
+with Convention => Intrinsic;
+
+Compares the value of Item with the value of Expected. If equal, the
+operation is a read-modify-write operation that writes Desired into
+Item. If they are not equal, the operation is a read and the current
+contents of Item are written into Expected.
+Weak is true for weak compare_and_exchange, which may fail spuriously,
+and false for the strong variation, which never fails spuriously. Many
+targets only offer the strong variation and ignore the parameter.
+When in doubt, use the strong variation.
+If Desired is written into Item then True is returned. Otherwise, False is returned.
+
+function Atomic_Always_Lock_Free return Boolean
+with Convention => Intrinsic;
+
+Returns True if objects always generate lock-free atomic instructions for the 
+target architecture.
+
+function Atomic_Always_Lock_Free (Item : aliased Atomic_Type) return Boolean
+with Convention => Intrinsic;
 
-** TBD. The author is not going to try to propose anything here, as people
-more knowledgeable about common machine architectures should do that. He notes
-that he mainly is aware of test-and-set operations and never heard of
-compare-and-swap until this discussion. :-)
+Returns True if objects always generate lock-free atomic instructions for the 
+target architecture. Item may be used ot determine alignment. The compiler may 
+also ignore this parameter.
 
+function Atomic_Is_Lock_Free (Item : aliased Atomic_Type) return Boolean;
+Returns True if objects always generate lock-free atomic instructions
+for the target architecture. Item may be used ot determine alignment.
+The compiler may also ignore this parameter.
+
+A.19.2  The Generic Package Atomic_Operations.Signed_Arithmetic
+
+The language-defined generic package Atomic_Operations.Signed_Arithmetic 
+provides a set of operations for adding and subtracting values atomically to
+signed integer types.
+
+generic
+   type Atomic_Type is range <> with Atomic;
+package Ada.Atomic_Operations.Signed_Arithmetic is
+
+   pragma Pure;
+
+   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_Fetch_And_Add (Item  : aliased in out Atomic_Type;
+                                  Value : Atomic_Type) return Atomic_Type
+    with Convention => Intrinsic;
+
+   function Atomic_Fetch_And_Subtract (Item  : not null access Atomic_Type;
+                                       Value : Atomic_Type) return Atomic_Type
+    with Convention => Intrinsic;
+
+end Ada.Atomic_Operations.Signed_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 Intrinsic;
+
+function Atomic_Subtract_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;
+
+function Atomic_Fetch_And_Subtract (Item  : aliased in out Atomic_Type;
+                                    Value : Atomic_Type) return Atomic_Type;
+
+A.19.3  The Generic Package Atomic_Operations.Modular_Arithmetic
+
+The language-defined generic package Atomic_Operations.Modular_Arithmetic 
+provides a set of operations for atomically adding, subtracting, and  
+bitwise manipulation, for modular integer types.
+
+generic
+   type Atomic_Type is mod <> with Atomic;
+package Ada.Atomic_Operations.Modular_Arithmetic is
+
+   pragma Pure;
+
+   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;
+
+   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;
+
+end Ada.Atomic_Operations.Modular_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;
+
+Modify C.6 (6.1/3)  to allow aspect Atomic to be applied to a generic formal type
+
+ For an object_declaration, a component_declaration, or a 
+ {type (including a formal type)}[full_type_declaration], the following 
+ representation aspects may be specified:
+
+Modify C.6 (12/3)
+If an atomic object is passed as a parameter, then the formal parameter shall 
+either have an atomic type or allow pass by copy. If an atomic object is used as 
+an actual for a generic formal object of mode in out, then the type of the 
+generic formal object shall be atomic. If the prefix of an attribute_reference 
+for an Access attribute denotes an atomic object [(including a component)], then 
+the designated type of the resulting access type shall be atomic. {If a generic
+formal type is atomic, then the actual shall be atomic.} If an atomic type is 
+used as an actual for a generic formal derived type, then the ancestor of the 
+formal type shall be atomic. Corresponding rules apply to volatile objects and types. 
+
+In a generic instantiation the actual type corresponding to an atomic formal 
+scalar, private, derived, array, or access-to-object type shall be atomic;
+
+In addition to the places where Legality Rules normally apply
+(see 12.3), the above rule also apply in the private part of an
+instance of a generic unit.
+
+AARM Ramification: For a generic formal parameter to be atomic
+(thus, for this rule to apply), it has to explicitly specify aspect
+Atomic to be True. 
+
 !discussion
 
 It seems that the solution will need to be generic, in order to work with any
@@ -34,17 +491,169 @@
 to be given on a 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.
+
+There are at least three approaches to improving Ada's support for lock free 
+structures, all of which are compatible with each other, and provide their own
+benefits.
+
+From a real-time perspective, very efficient lock free data structures can in 
+theory be obtained in a straight forward manner when the Ravenscar Profile is 
+being applied, and when it is known that all use of a protected object is by 
+tasks that execute on the same processor. This is because each task is locked
+to execute on a specific CPU, and because the ceiling priority protocol is in
+place. If all use of a protected object is by tasks
+executing on the same CPU, then any task that is executing a protected action 
+cannot be preempted by another task wishing to call into the same protected object
+and therefore no locking is needed. But locking is needed to implement
+a protected object if a protected object can be accessed from tasks executing on
+multiple cores. Ada allows aspect CPU to be applied to a task desclaration to
+indicate which CPU a task of that type will execute on. The CPU aspect may also 
+be applied to a subprogram declaration, which could be applied to protected
+procedures, or protected functions, but not protected entries.
+
+It would be helpful if the CPU aspect could be applied to a protected type 
+declaration, or single protected object, which would imply that all calls to the
+protected object are via tasks that are executing on the same CPU.
+
+With such a specification in place, this would provide an indication to the
+implementation that locking is not needed, and that any overhead associated with
+locking, including space for the lock in memory and initialisation and 
+finalisation of the locks can be eliminated.
+
+Program_Error would be raised if a task executing on a CPU other than the one
+specified for the protected object attempts to execute a protected action of that
+protected object.
+
+We considered defining a Lock_Free aspect which could also be applied to a declaration 
+of the protected type or single protected object. The type of the Lock_Free aspect would 
+be Boolean, and it would be illegal to specify the Lock_Free aspect for an object or type
+if the compiler cannot guarantee indivisible updates.
+
+With CPU aspect and Lock_Free aspect being applicable to protected type 
+declarations, we could then have a new restriction, No_Locking, which specifies
+that each protected object that is not lock free is associated with the CPU of
+the task that created it. For Ravenscar, this would have the effect of assigning
+CPU to these declarations as that being the CPU associated with the environmental
+task.
+
+Having all protected objects assigned to specific CPU's would ensure that the
+program is free from Deadlock.
+
+To further support this notion, a new attribute, 'Lock_Free could be made available
+to query if the actual implementation is lock free.
+
+If a protected object is bound to a specific CPU, then the implementation of that
+protected object could be lock free, regardless whether the program has the 
+Ravenscar profile specified or not. Any tasks calling into that protected object
+would need to have the CPU aspect specified with a matching CPU value.
+
+If a protected object does not have the CPU aspect specified, but has the Lock_Free
+aspect applied, then there would need to be additional restrictions applied to that
+protected object to allow for a lock free implementation, to support needs of
+real time systems.
+
+Since lock free data structures involve retries when there is contention for the
+object, the number of retries needs to be bounded. To bound the execution time
+of a protected action we would want to disallow loop, goto, and procedure call
+statements in the protected actions of a lock free protected object. We would
+also want to disallow calls to non-static functions, and disallow quantified
+expressions, which are a form of looping construct.
+
+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 instruction of these category. A limitation of these instructions is 
+that they typically can only be applied to a single elementary integer type of
+1, 2, 4, or 8 bytes in size.
+
+To restrict a protected object so that it can fit to work with these atomic
+primitives, there would need to be further restrictions to contain the operation
+to a single memory location. In particular the following would not be allowed in
+a lock free protected operation;
+
+- Access to non-local variables. (Note: constants are OK)
+- Non Elementary parameters to the protected operations
+- Dereferencing of access values (i.e. Pointers)
+- Address clauses
+- Imported or exported entities
+- Allocators
+
+And lastly, to prevent instructions with external effect, we would want to
+disallow the use of Volatile variables within a lock free protected operation.
+
+It is worth noting that exceptions and exception handling would be allowable
+within lock free protected operations.
+
+One of the benefits of the Lock_Free aspect is that it provides flexibility of
+implementation. The implementation may choose to implement the Lock_Free aspect
+via the use of atomic primitives, but it may also decide to implement instead
+via the use of transactional memory approaches. Static analysis could be applied
+to determine which approach is better. For real time, this may involve determining
+the worst case execution time for the transaction. Whether the implementation
+decides to implement with a transactional memory approach or with atomic
+primitives, the choice is transparent to the client. In bounding the
+execution time, the worst case could be limited to the number of writes, N x
+the transaction time.
+
+This was discussed at a recent IRTAW, but it was noted that there are issues with
+transaction based approaches for use with real time, and the conclusion was that
+transaction based approach would likely not be wanted for use with Ada.
+
+It was felt that at the current time, defining the Lock_Free aspect
+would be premature, in part because of all the restrictions that would be needed. 
+While at least one compiler vendor has implemented this aspect,
+it was felt that more experience would be needed before standardising such a feature.
+
+A third approach to improving support for lock free data structures would be
+to provide a library of low level atomic primitives similar to the library
+that is provided by gcc for C and C++.
+
+The C and C++ memory model support several different memory orders. The most
+restrictive memory order is called sequentially consistent, where all threads
+are synchronised such that updates to shared variables are seen by all threads,
+and the order seen by all threads is the same. Due to the higher level of 
+synchronisation, this is also the most inefficient memory order, but it is the
+default memory order because it is the safest, and produces the least number
+of surprising results. Moving towards lower level of synchronisation,there are
+are memory orders called Acquire and Release, where essentially the synchronisation
+is limited to the threads involved in the atomic operations for a particular
+shared variable.  Relaxing the synchronisation even further is a memory order
+called Relaxed, where this synchronisation is not present. There are guarantees
+that a given thread will not see older values of variables once it has seen an
+update to a variable, but that is about the limit of the guarantees, other than
+that updates are seen in some sort of time bounded manner. Programmers using this
+memory order in theory should be able to write more efficient code, though it is
+can be much trickier to get code to work properly, since there are more unexpected
+behaviours due to the lack of synchronisation between threads. One other point
+that should be mentioned is that these atomic primitives would need to be 
+have the Intrinsic convention, because they can require the disabling of certain
+compiler optimisations, such as hoisting or sinking code across boundaries where
+atomic primitives are being used. For instance the Acquire/Release memory order
+has this requirement in particular.
+
+For the approach of this AI, if we were to go forward with providing a library of
+atomic primitives, it probably would be best to not bother with supporting the
+lower synchronisation memory orders, and instead provide a library which 
+implicitly assumes the sequentially consistent memory order, which is both safer
+to use, and easier to understand.
+
+As some final notes, the three approaches to lock freedom,
+
+ 1) Applying Aspect CPU to protected type declarations
+ 2) Allowing Lock_Free aspect to be applied to protected type declarations
+ 3) Providing a library of low level atomic primitives
+ 
+ Are all compatibile with each other, and in theory could all be supported. 
 
---
+For the real time community, the aspect CPU and related No_Locking restriction
+would likely be of most interest, and possibly the easiest to implement.
 
-Author's note: One thing I learned from this discussion is that at least some
-the literature uses "Lock-Free" to mean "free of deadlocks and livelocks"
-rather than the obvious meaning of "has no locks". Those are two wildly
-different things! Surely a tool could determine if a protected object is
-deadlock free; whether the implementation contains locks obviously out of the
-hands of tools. Moreover, almost all synchronized data has something that is
-acting like a lock (that is, some synchronization data); the exact form of
-that data should be irrelevant outside of performance concerns.
+The Lock_Free aspect allows implementations to choose between atomic primitives
+and transactional memory, which providing a safer interface that integerates
+better into the existing task synchronisation support.
+
+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.
 
 !ASIS
 
@@ -1630,5 +2239,142 @@
 Standardizing the Lock_Free aspect might be worth doing, but I don't believe 
 that addresses the main goal here, which is to provide atomic operations on 
 atomic objects.
+
+****************************************************************
+
+From: Brad Moore
+Sent: Saturday, May 5, 2018  5:30 PM
+
+Here is my first cut at AI12-0234-1, which provides better support for 
+lock-free programming in Ada. [This is version /02 of the AI - Editor.]
+
+The original title of this AI was Compare and Swap for Atomic objects, which
+was generalized to also provide other atomic operations, such as being able 
+to add or subtract values to integer types, and apply bitwise operations to 
+modular types atomically.
+
+The proposal has 4 new libraries.
+
+Atomic_Operations,
+Atomic_Operations.Storage,
+Atomic_Operations.Signed_Arithmetic,
+Atomic_Operations.Modular_Arithmetic
+
+The parent library is non-generic and includes some test and set based 
+operations, which do not require any user types.
+
+The other 3 libraries are generic libraries.
+
+The Storage library has a generic formal discrete type, and provide the 
+Compare and Swap, Load, Store, and Exchange capabilities.
+
+The Signed_Arithmetic has a generic formal signed integer type, and provides 
+variants of add and subtract. A Constraint error can be raised as expected if
+the operation overflows.
+
+The Modular_Arithmetic has a generic formal modular type, and in addition to 
+Add and subtract, also provides various bit manipulation calls that one might
+expect to use with a modular type. Overflow has wrap around semantics, and
+does not raise constraint_error, as one might expect.
+
+To specify that the generic formals are atomic types, I needed to change the 
+rules to allow the Atomic aspect to be specified on a generic formal, which 
+previously was not allowed.
+
+Finally, in addition, since protected objects on a single processor are 
+considered to be lock-free and deadlock free with appropriate use of the 
+ceiling priority protocol, this AI also extends the rules for the CPU aspect,
+so that it can be applied to protected type declarations. The compiler can 
+simplify the implementation for such protected types, since locking is not 
+needed, plus there is the added benefit of being deadlock free, which was 
+considered to be important by the attendees at the recent IRTAW, which 
+unanimously felt it was worth adding to the standard.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Friday, May 11, 2018  12:06 AM
+
+> The parent library is non-generic and includes some test and set based 
+> operations, which do not require any user types.
+
+Humm.
+
+>   type Test_And_Set_Type is mod 2**8;
+
+(1) Shouldn't this type be declared atomic (or at least volatile)? It's 
+beyond weird to do atomic operations on non-atomic objects. (It's also a
+substantial optimizer problem - an Ada optimizer knows to leave atomic objects
+alone, but that certainly isn't the case for other objects.)
+
+(2) 2**8 would be a very expensive type on the U2200 and various other unusual
+processors. Ada has never tied itself to 8-bit machines like Java. Shouldn't
+this type be based on the storage unit in System?
+
+...
+> To specify that the generic formals are atomic types, I needed to 
+> change the rules to allow the Atomic aspect to be specified on a 
+> generic formal, which previously was not allowed.
+
+I wonder if this should be done in a separate AI. It could get complex if 
+Steve discovers any more contract problems.
+
+> Modify C.6 (6.1/3)  to allow aspect Atomic to be applied to a generic 
+> formal type
+>
+> For an object_declaration, a component_declaration, or a {type 
+> (including a formal type)}[full_type_declaration], the following 
+> representation aspects may be specified:
+
+(1) This implies that Atomic can be specified in private types, extensions, 
+interfaces, incomplete types, yadda yadda yadda. The Legality Rules in 13.1 
+for representation aspects would prevent that, but those same rules also 
+would prevent use on formal types "unless otherwise specified". Seems 
+confused. I'd suggest just adding "formal_type_declaration" to the original 
+list and then there is no confusion nor any need for a parenthetical remark.
+
+  For an object_declaration, a component_declaration, {full_type_declartion},
+  or a {formal}[full]_type_declaration, the following representation aspects
+  may be specified:
+
+(2) This means all 6 aspects are getting allowed on formal types, even though 
+we only have need (and have rules!) for one. Is that really what we want? Do 
+we really want to mess around with Independent_Components in generics? Etc.
+
+>Modify C.6 (12/3)
+>If an atomic object is passed as a parameter, then the formal parameter 
+>shall either have an atomic type or allow pass by copy. If an atomic 
+>object is used as an actual for a generic formal object of mode in out, 
+>then the type of the generic formal object shall be atomic. If the 
+>prefix of an attribute_reference for an Access attribute denotes an 
+>atomic object [(including a component)], then the designated type of 
+>the resulting access type shall be atomic. {If a generic formal type is 
+>atomic, then the actual shall be atomic.} If an atomic type is used as 
+>an actual for a generic formal derived type, then the ancestor of the formal 
+>type shall be atomic. Corresponding rules apply to volatile objects and
+>types.
+>
+>In a generic instantiation the actual type corresponding to an atomic 
+>formal scalar, private, derived, array, or access-to-object type shall 
+>be atomic;
+
+Could you explain why you are saying this twice, once with an added sentence 
+in the original paragraph, and a second time with an added paragraph. It seems
+like the first added rule would be enough, but perhaps I missed some subtle 
+issue.
+
+> Finally, in addition, since protected objects on a single processor 
+> are considered to be lock-free and deadlock free with appropriate use 
+> of the ceiling priority protocol, this AI also extends the rules for 
+> the CPU aspect, so that it can be applied to protected type 
+> declarations. The compiler can simplify the implementation for such 
+> protected types, since locking is not needed, plus there is the added 
+> benefit of being deadlock free, which was considered to be important 
+> by the attendees at the recent IRTAW, which unanimously felt it was 
+> worth adding to the standard.
+
+This also seems like it ought to have been a separate AI, even more so than 
+the formal Atomic types. As you know, when AIs get too big, it's hard to make
+progress on them. And this topic is completely separate from the other issues.
 
 ****************************************************************

Questions? Ask the ACAA Technical Agent