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

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

--- ai12s/ai12-0234-1.txt	2019/03/12 04:55:53	1.15
+++ ai12s/ai12-0234-1.txt	2019/03/15 05:39:29	1.16
@@ -1,4 +1,4 @@
-!standard C.6.1(0)                                  19-03-11  AI12-0234-1/06
+!standard C.6.1(0)                                  19-03-14  AI12-0234-1/07
 !standard C.6.2(0)
 !class Amendment 17-06-09
 !status Amendment 1-2012 19-03-11
@@ -84,7 +84,8 @@
 
 Static Semantics
 
-The following language-defined library package exists:
+The library package System.Atomic_Operations has the
+following declaration:
 
 package System.Atomic_Operations
    with Pure, Nonblocking is
@@ -117,7 +118,7 @@
 
 Static Semantics
 
-The library package System.Atomic_Operations.Exchange has the
+The generic library package System.Atomic_Operations.Exchange has the
 following declaration:
 
 generic
@@ -142,12 +143,19 @@
 Atomic_Exchange atomically assigns the value of Value to Item, and returns
 the previous value of Item.
 
-Atomic_Compare_And_Exchange compares the value of Item with the
-value of Prior. If equal, the operation is a read-modify-write
-operation that assigns the value of Prior to Item. If they are
-not equal, the operation is a read and the value of Item is
-assigned to Prior. If Prior is assigned to Item then True is 
-returned. Otherwise, False is returned.
+Atomic_Compare_And_Exchange first evaluates the value of Prior.
+Atomic_Compare_And_Exchange then performs the following steps 
+as part of a single indivisible operation:
+ 
+  * evaluates the value of Item;
+  * compares the value of Item with the value of Prior;
+  * if equal, assigns Item the value of Desired;
+  * otherwise, makes no change to the value of Item.
+ 
+After these steps, if the value of Item and Prior did not 
+match, Prior is assigned the original value of Item, and the 
+function returns False.
+Otherwise, Prior is unaffected and the function returns True.
 
 Examples
 
@@ -273,6 +281,119 @@
 We could add a separate call in the future that exposes the Weak parameter,
 if there is enough need for such a capability.
 
+!corrigendum C.6.1
+
+@dinsc
+
+The library package System.Atomic_Operations is the parent of a set of child
+units that provide facilities for manipulating objects of atomic types
+and for supporting lock-free synchronization.
+The subprograms of this subsystem are Intrinsic subprograms (see 6.3.1)
+in order to provide convenient access to machine operations that can
+provide these capabilities if they are available in the target environment.
+
+@s8<@i<Static Semantics>>
+
+The library package System.Atomic_Operations has the
+following declaration:
+
+@xcode<@b<package> System.Atomic_Operations
+   @b<with> Pure, Nonblocking @b<is>
+@b<end> System.Atomic_Operations;>
+
+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 @i<lock-free> if the subprogram
+is guaranteed to return from the call while keeping the processor of
+the logical thread of control busy for the duration of the call.
+
+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, and Is_Lock_Free returns False otherwise.
+
+!corrigendum C.6.2
+
+@dinsc
+
+The language-defined generic package System.Atomic_Operations.Exchange
+provides the following operations:
+
+@xbullet<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.>
+
+@xbullet<To atomically update the value of an atomic object, and then
+return the value that the atomic object had just prior to the update.>
+
+@s8<@i<Static Semantics>>
+
+The generic library package System.Atomic_Operations.Exchange has the
+following declaration:
+
+@xcode<@b<generic>
+   @b<type> Atomic_Type @b<is private with> Atomic;
+@b<package> System.Atomic_Operations.Exchange
+   @b<with> Pure, Nonblocking @b<is>>
+
+@xcode<   @b<function> Atomic_Exchange (Item  : @b<aliased in out> Atomic_Type;
+                             Value : Atomic_Type) @b<return> Atomic_Type
+     @b<with> Convention =@> Intrinsic;>
+
+@xcode<   @b<function> Atomic_Compare_And_Exchange (Item    : @b<aliased in out> Atomic_Type;
+                                         Prior   : @b<aliased in out> Atomic_Type;
+                                         Desired : Atomic_Type) @b<return> Boolean
+     @b<with> Convention =@> Intrinsic;>
+
+@xcode<   @b<function> Is_Lock_Free (Item : @b<aliased> Atomic_Type) @b<return> Boolean
+     @b<with> Convention =@> Intrinsic;>
+
+@xcode<@b<end> System.Atomic_Operations.Exchange;>
+
+Atomic_Exchange atomically assigns the value of Value to Item, and returns
+the previous value of Item.
+
+Atomic_Compare_And_Exchange first evaluates the value of Prior.
+Atomic_Compare_And_Exchange then performs the following steps 
+as part of a single indivisible operation:
+ 
+@xbullet<evaluates the value of Item;>
+@xbullet<compares the value of Item with the value of Prior;>
+@xbullet<if equal, assigns Item the value of Desired;>
+@xbullet<otherwise, makes no change to the value of Item.>
+ 
+After these steps, if the value of Item and Prior did not 
+match, Prior is assigned the original value of Item, and the 
+function returns False.
+Otherwise, Prior is unaffected and the function returns True.
+
+@s8<@i<Examples>>
+
+@i<Example of a spin lock using Atomic_Exchange:>
+
+@xcode<@b<type> Atomic_Boolean @b<is new> Boolean @b<with> Atomic;
+@b<package> Exchange @b<is new>
+   Atomic_Operations.Exchange (Atomic_Type =@> Atomic_Boolean);>
+
+@xcode<Lock : @b<aliased> Atomic_Boolean := False;>
+
+@xcode<...>
+
+@xcode<@b<begin> -- @ft<@i<Some critical section, trying to get the lock:>>>
+
+@xcode<   -- @ft<@i<Obtain the lock>>
+   @b<while> Exchange.Atomic_Exchange (Item =@> Lock, Value =@> True) @b<loop>
+      @b<null>;
+   @b<end loop>;>
+
+@xcode<  ... -- @ft<@i<Do stuff>>>
+
+@xcode<  Lock := False; -- @ft<@i<Release the lock>>
+@b<end>;>
+
+
 !ASIS
 
 No ASIS effect.
@@ -3461,3 +3582,136 @@
 
 ****************************************************************
 
+From: Jean-Pierre Rosen
+Sent: Tuesday, March 12, 2019   9:03 AM
+
+> The current wording (after today's changes) is:
+> 
+>    Atomic_Compare_And_Exchange compares the value of Item with the
+>    value of Prior. If equal, the operation is a read-modify-write
+>    operation that assigns the value of [Prior]{Desired} to Item. If they are
+>    not equal, the operation is a read and the value of Item is
+>    assigned to Prior. If Prior is assigned to Item then True is
+>    returned. Otherwise, False is returned.
+
+[Editor's note: This correction is only one of two mistakes, but it is OBE.]
+
+****************************************************************
+
+From: Tullio Vardanega
+Sent: Tuesday, March 12, 2019  12:58 PM
+
+Unfortunately, the notion of "read-modify-write" is established in the world
+of lock-free processing, with a meaning that is determined bottom-up by what
+the hardware can do in that regard, and that has been shown to have the 
+required algebraic properties.
+The sense of atomicity in it is that the write either succeeds or never 
+happened, which is not how I understand "atomic" in Ada.
+Rendering all this magic in programming language terms is going to require 
+some gymnastics :(
+
+****************************************************************
+
+From: Tucker Taft
+Sent: Tuesday, March 12, 2019   1:45 PM
+
+> My understanding is that Value and Desired parameters are just values 
+> and are not treated atomically. This is definitely the case if the 
+> actual type for Atomic_Type is an elementary type.
+
+Agreed.
+ 
+> But what happens if Atomic_Type is a composite type? In that case, 
+> parameter passing is by-reference, and thus Value and Desired seem to 
+> require atomic reads. It's unlikely that any hardware operations 
+> actually do such an operation atomically (the read would be separate 
+> from the rest of operation, meaning the entire operation wouldn't 
+> quite be atomic), and we probably don't want to insist that they are 
+> atomic WRT to the rest of the operation anyway.
+> 
+> Do we need to say something about this case, in particular, that the 
+> reads of Value/Desired are atomic but possibly separate from the rest 
+> of the operation.
+
+I don't see why.  These are values that are not expected to be changing.
+It is probably a bit odd that these are atomic at all, but it would be a
+pain to have to pass in both an atomic and a non-atomic type.   
+ 
+> Actually, the problem seems to be the reverse. We never say what part 
+> of the Compare_and_Swap operation is performed atomically. It can't be 
+> intended to perform *all* of it that way -- I note that the Intel 
+> instruction only takes one address, so there can only be one parameter 
+> (Item) whose operations are fully atomic. The "Desired" and "Prior" 
+> parameters are in registers, so their reads and writes clearly are 
+> separate from the core instruction. The wording doesn't seem to make 
+> this distinction (which has to be done for the by-reference case at a minimum).
+> 
+> The current wording (after today's changes) is:
+> 
+>  Atomic_Compare_And_Exchange compares the value of Item with the  
+> value of Prior. If equal, the operation is a read-modify-write  
+> operation that assigns the value of Prior to Item. If they are  not 
+> equal, the operation is a read and the value of Item is  assigned to 
+> Prior. If Prior is assigned to Item then True is  returned. Otherwise, 
+> False is returned.
+> 
+> I don't know what a "read-modify-write" operation is, in normative Ada 
+> terms. Maybe we should just describe it as "atomic"? Not sure if 
+> that's enough. (This is somewhat a problem with the test-and-set and 
+> arithmetic operations as well, they're described as being "atomic" -- 
+> we probably need to somehow describe what is indivisible and what 
+> isn't. However, in those cases the parameters are guaranteed to be 
+> by-copy unless declared "aliased", so it should be clear that the 
+> values are not managed atomically.)
+> 
+> Thoughts? Ideas? Randy's lost it? ;-)
+
+I agree that the dynamic semantics ought to identify the steps that are 
+performed without any interruption allowed.  Perhaps the following:
+
+Atomic_Compare_And_Exchange first evaluates the value of Prior.
+Atomic_Compare_And_Exchange then performs the following steps as part of a 
+single indivisible operation:
+
+  * evaluates the value of Item;
+  * compares the value of Item with the value of Prior;
+  * if equal, assigns Item the value of Prior;
+  * otherwise, makes no change to the value of Item;
+
+After these steps, if the value of Item and Prior did not match, Prior is 
+assigned the original value of Item, and the function returns False.
+Otherwise, Prior is unaffected and the function returns True.
+
+****************************************************************
+
+From: Randy Brukardt
+Sent: Thursday, March 14, 2019   6:50 PM
+
+...
+> I agree that the dynamic semantics ought to identify the steps that 
+> are performed without any interruption allowed.
+> Perhaps the following:
+> 
+> Atomic_Compare_And_Exchange first evaluates the value of Prior.
+> Atomic_Compare_And_Exchange then performs the following steps as part 
+> of a single indivisible operation:
+> 
+>   * evaluates the value of Item;
+>   * compares the value of Item with the value of Prior;
+>   * if equal, assigns Item the value of Prior;
+>   * otherwise, makes no change to the value of Item;
+> 
+> After these steps, if the value of Item and Prior did not match, Prior 
+> is assigned the original value of Item, and the function returns 
+> False.
+> Otherwise, Prior is unaffected and the function returns True.
+
+This looks good, other than that you copied my error vis-a-vis using "Prior"
+everywhere. The third bullet should say
+   "if equal, assigns Item the value of Desired;"
+
+[At least, presuming the original description was correct. It certainly can't 
+be the case that the third parameter isn't used at all, so the above makes 
+the most sense.]
+
+****************************************************************

Questions? Ask the ACAA Technical Agent