19.13 Low level operations

19.13.1 Low level atomic operations

Low level atomic operations are defined in all cases for a specific set of places. These places are listed in Places for low-level atomic operations:

Notes about atomic slot-value operations:

1. They ignore the MOP slot-value-using-class protocol and can only be used for :instance and :class allocated slots.
2. They are slower than the atomic operations on other types of object because they have to lock the instance. Normally it would be better to have a slot pointing to some other object (for example a structure) and do the atomic operations on that object.

The low level atomic operations implicitly ensure order of memory between operations in different threads.

The low level atomic operations are: atomic-push, atomic-pop, atomic-fixnum-incf, atomic-fixnum-decf, atomic-incf, atomic-decf, atomic-exchange and compare-and-swap.

Application of macros that are defined by define-atomic-modify-macro is also restricted to the places in Places for low-level atomic operations above, because they implicitly use low level atomic operations.

You can test whether a place is suitable for use with these operations by the predicate low-level-atomic-place-p.

19.13.2 Aids for implementing modification checks

The macros with-modification-check-macro and with-modification-change provide a way for a body of code to execute and check whether there was any "modification" during this execution, where modification is execution of some other piece of code. This is useful in situations when reading some data out of some data structure is more common than modification, and reading the data involves getting some values that need to be consistent. It makes it possible to ensure consistency of the values without a lock.

The checking code should be wrapped by the macro with-modification-check-macro, and the modifying code should be wrapped by the macro with-modification-change. They are associated by the fact that their modification-place argument is the same.

modification-place is a place as defined in Common Lisp (it does not need to be one of the places for atomic locking) which can receive a fixnum. It must be initialized to the fixnum 0. Note that the macros do not check this initialization, so if it is not initialized correctly then you will get an unpredictable behaviour. It must not be modified by any code except with-modification-change.

with-modification-check-macro defines a lexical macro (by macrolet) with the name macro-name which takes no arguments, and is used to check whether there was any change since the entering the body.

Note that these macros do not guard against errors that may occur because of changes to the data structures that are accessed, and do not create any locking between users of these macro. In particular, the modifying code will typically need to lock something too, and the checking code must do only operations that cannot fail because of modification in another thread.

19.13.2.1 Example modification check

(defstruct my-cache
  (modification-count 0)
  a
  b)
 
;; modifier code
(sys:with-modification-change
 (my-cache-modification-count cache)
 (setf (my-cache-a cache) (calculate-a-value ....)
       (my-cache-b cache) (calculate-b-value ....)))
 
;; reading code
(loop
  (sys:with-modification-check-macro
   my-cache-did-not-change-p (my-cache-modification-count cache)
   (let ((a (my-cache-a cache))
         (b (my-cache-b cache)))
     (when (my-cache-did-not-change-p)
       (return (values a b )))

Provided that all modification to the a and b slots of a my-cache object are done by the modifier code above, the return values of a and b in the reading code are guaranteed to have been set by the same setf invocation in the modifier code.

19.13.3 Ensuring order of memory between operations in different threads

A set of synchronization functions is provided which ensure order of memory between operations in different threads. These are ensure-loads-after-loads, ensure-memory-after-store, ensure-stores-after-memory and ensure-stores-after-stores.

Note: You should have a good understanding of multiprocessing issues at the CPU level to write code that actually needs these functions.

The effect of each of these functions is to ensure that all the operations of the first type (the word following the ensure-) that are in the program after the call to the function are executed after all the operations of the second type (last word in the function name) that are in the program before the call to the function.

Before or after "in the program" means the order that a programmer interpreting (correctly) the program would expect the operations to be executed. On a modern CPU this is not necessarily the same as the actual execution order. On a single CPU the end result is guaranteed to be the same, but on a computer with multiple CPU cores it is not.

An operation of type load is an operation that reads data from an object into a local variable. Typical load operations are car, cdr, svref, structure accessors, slot-value and getting the value of a symbol. A store operation is an operation that modifies data in an object. A memory operation is either a load or a store.

You need these functions when you need to synchronize between threads and you do not want to use the system supplied synchronization objects (19.4 Locks, mailboxes, 19.7.1 Condition variables, 19.7.3 Counting semaphores, 19.7.2 Synchronization barriers). In most cases you should try first to use a synchronization object. Using the synchronization functions described in this section is useful if you can identify a serious bottleneck in your code that can be optimized using them.

For simple cases you should consider whether with-modification-check-macro and with-modification-change gives you the functionality you need.

19.13.3.1 Example of ensuring order of memory

Suppose you have two code fragments, which may end up executed in parallel, and both of which access a global structure *gs*. The first fragment is a setter, and you can be sure that it is not executed in parallel to itself (normally because it actually runs while holding a lock):

(setf
  (my-structure-value-slot *gs*)   ; store1
  some-value)
(setf
  (my-structure-counter-slot *gs*) ; store2
  counter)

The second fragment is the reader. You want to guarantee that it gets a value that was stored after the counter reached some value (the counter value always increases). You may think that this will suffice:

(if (>=
     (my-structure-counter-slot *gs*) ; load1
     counter)
    (my-structure-value-slot *gs*)    ; load2
  (.. something else ...))

Programmatically, if the >= is true then store2 already occurred before load1, therefore store1 also occurred before load1, and load2 which happens after load1 must happen after store1.

On a single CPU that is true. On a computer with multiple CPU cores it can go wrong (that is, load2 can happen before store1) because of two possible reasons:

1. load2 may happen before load1.
2. store2 may happen before store1.

To guarantee that load2 happens after store1, both of these possibilities need to be dealt with. Thus the setter has to be:

(setf (my-structure-value-slot *gs*)   ; store1
      some-value)
(sys:ensure-stores-after-stores)       ; ensure store order
(setf (my-structure-counter-slot *gs*) ; store2
      (incf-counter))

and the reader has to be:

(if (> (my-structure-counter-slot *gs*) ; load1
       my-counter)
    (progn
      (sys:ensure-loads-after-loads)    ; ensure load order
      (my-structure-value-slot *gs*))   ; load2
  (.. something else ...))

Note that somehow both threads know about counter, and normally will have to synchronize the getting of its value too.