6.5 Atomic Operations

A family of atomic operations is added to optional Annex C Systems Programming by Compare-and-swap for atomic objects (AI12-0234), Support for Arithmetic Atomic Operations and Test and Set (AI12-0321) and Add a modular atomic arithmetic package (AI12-0364).

In systems where processors communicate via shared memory, there are two common methods of synchronisation. Thus "Compare-and-swap" atomically compares the contents of a memory location with a given value and, only if they are the same, modifies the contents of that memory location to a given new value. "Test-and-set" modifies the contents of a memory location and returns its old value in a single atomic operation. These can then be used to construct spin locks. Such instructions are often available in the hardware. This AI makes them available in a more portable manner, assuming of course that the underlying hardware provides them. Note that which instructions can be performed atomically can vary even between processors in the same family.

These AIs add a number of library packages, namely

System.Atomic_Operations.Test_And_Set,

and the generic packages

System.Atomic_Operations.Exchange,
System.Atomic_Operations.Integer_Arithmetic,
System.Atomic_Operations.Modular_Arithmetic

The last three packages are generic so that they can be instantiated with an actual of the appropriate size for the memory architecture in use.

Compare-and-swap (see RM C.6.2):

generic
   type Atomic_Type is private with Atomic;
package System.Atomic_Operations.Exchange
      with Pure, Nonblocking is
   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;
           Prior : aliased in out Atomic_Type;
           Desired : Atomic_Type) return Boolean
      with Convention => Intrinsic;
   function Is_Lock_Free (Item : aliased Atomic_Type)
          return Boolean
      with Convention => Intrinsic;
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. It 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.

Is_Lock_Free returns whether all the operations of the child package can be provided lock-free for a given object.

An example of a spin lock 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;

...

begin --  Some critical section, trying to get the lock:
   --  Acquire the lock
   while Exchange.Atomic_Exchange (Item => Lock, Value => True) loop
      null;
   end loop;
   ...    -- Do stuff
   Lock := False;    -- Release the lock
end;

For non-preemptive scheduling, it might be appropriate to call Ada.Dispatching.Yield rather than having a null statement.

Test-and-set (see RM C.6.3):

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>;
   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;
   function Is_Lock_Free
        (Item : aliased Test_And_Set_Flag) return Boolean
     with Convention => Intrinsic;
end System.Atomic_Operations.Test_And_Set;

Atomic_Test_And_Set performs an atomic test-and-set operation on Item. Item is set to some implementation-defined non-zero value. The function returns True if the previous contents were non-zero, and otherwise returns False.

Atomic_Clear performs an atomic clear operation on Item. After the operation, Item contains zero.

An example of a spin lock using Atomic_Test_And_Set:

begin --  Some critical section, trying to get the lock:
   --  Acquire the lock
   while Atomic_Test_And_Set (Item => Lock) loop
      null;
   end loop;
   ... -- Do stuff
  Atomic_Clear (Item => Lock); -- Release the lock
end;

Atomic arithmetic (see RM C.6.4):

generic
   type Atomic_Type is range <> with Atomic;
package System.Atomic_Operations.Integer_Arithmetic
      with Pure, Nonblocking is
   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;
   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 Is_Lock_Free (Item : aliased Atomic_Type)
                   return Boolean
     with Convention => Intrinsic;
end System.Atomic_Operations.Arithmetic;

As one might expect, Atomic_Add and Atomic_Subtract atomically perform add and subtract, whereas Atomic_Fetch_And_Add and Atomic_Fetch_And_Subtract additionally return the original value of the Item.

Modular arithmetic (see RM C.6.5):

In this case, the package

System.Atomic_Operations.Modular_Arithmetic

has the same declaration as

System.Atomic_Operations.Integer_Arithmetic,

except that the formal parameter is:

type Atomic_Type is mod <> with Atomic;