Summary of Linux Kernel Mechanisms Atomic Variables of Kernel Mutual Exclusion Technology (36)

Article directory

1 Atomic variable

Atomic variables are used to implement mutually exclusive access to integers, and are often used to implement counters.

For example, we write a line of code to add 1 to the variable a, and the [compiler compiles] the code into 3 assembly instructions: (1) Load
the variable a from [memory into a register.]
(2) Increment the value of the [register] Increment the value of the [register] by 1.
(3) Write the value of the register back to memory.

In a uniprocessor system, if both process 1 and process 2 execute the operation of incrementing variable a by 1, the following execution sequence may occur: The
expected result is that the value of variable a is incremented by 2 after process 1 and process 2 are executed, but because Before process 1 writes the new value of variable a back to memory, the process scheduler schedules process 2, and process 2 reads the old value of variable a from memory, causing the value of variable a to only increase by 1 after process 1 and process 2 are executed.

In a multiprocessor system, if processor 1 and processor 2 both perform the operation of incrementing variable a by 1, the following execution sequence may occur: the
expected result is that the value of variable a is incremented after processor 1 and processor 2 have finished executing 2, but because processor 2 reads the old value of variable a from memory before processor 1 writes the new value of variable a back to memory, the value of variable a only increases by 1 after processor 1 and processor 2 are executed. .

Atomic variables can solve this problem, making 3 operations into one atomic operation.

The kernel defines three kinds of atomic variables:
(1) Integer atomic variables, the data type is atomic_t.

include/linux/types.h
typedef struct {
    int counter;
} atomic_t;

(2) Long integer atomic variable, the data type is atomic_long_t.
(3) 64-bit integer atomic variable, the data type is atomic64_t.

The following uses integer atomic variables as an example to illustrate how to use them. The way to initialize a static atomic variable is as follows:

atomic_t <name> = ATOMIC_INIT(n);

The way to dynamically initialize atomic variables on the fly is as follows:

atomic_set(v, i);

Initialize the value of the atomic variable v to i.

Commonly used atomic variable operation functions are as follows:
(1) atomic_read(v)
reads the value of atomic variable v.

(2) atomic_add_return(i, v)
adds i to the value of the atomic variable v and returns the new value.

(3) atomic_add(i, v)
adds i to the value of the atomic variable v.

(4) atomic_inc(v)
adds 1 to the value of the atomic variable v.

(5) int atomic_add_unless(atomic_t *v, int a, int u);
if the value of the atomic variable v is not u, then add a to the value of the atomic variable v and return 1, otherwise return 0.

(6) atomic_inc_not_zero(v)
If the value of atomic variable v is not 0, then add 1 to the value of atomic variable v and return 1, otherwise return 0.

(7) atomic_sub_return(i, v)
subtracts i from the value of the atomic variable v, and returns the new value.

(8) atomic_sub_and_test(i, v)
subtract i from the value of atomic variable v, test whether the new value is 0, if it is 0, return true.

(9) atomic_sub(i, v)
subtract i from the value of the atomic variable v.

(10) atomic_dec(v)
subtracts 1 from the value of the atomic variable v.

(11) atomic_cmpxchg(v, old, new)
performs atomic comparison and exchange. If the value of atomic variable v is equal to old, then set the value of atomic variable v to new. The return value is always the old value of the atomic variable v.

1.1 Atomic Variable Implementation for ARM64 Processors

Atomic variables require special instruction support for various processor architectures, the ARM64 processor provides the following instructions.
(1) Exclusive load instruction ldxr (Load Exclusive Register).
(2) Exclusive storage instruction stxr (Store Exclusive Register).

An exclusive load instruction loads 32-bit or 64-bit data from memory into a register, marking the accessed physical address as an exclusive access.

The format of the exclusive load instruction to load 32-bit data is:

ldxr <Wt>, [<Xn|SP>{,#0}]

: 32-bit general-purpose register for storing data.

: 64-bit general-purpose register Xn or stack pointer register, which stores the reference address.

0: Offset, can only be 0, can be omitted. The virtual address of a variable is the base address plus the offset.

Exclusive store instructions store 32-bit or 64-bit data from a register into memory, checking whether the target memory address is marked for exclusive access. If it is an exclusive access, it is stored in memory and a status value of 0 is returned to indicate that the store is successful; otherwise, it is not stored in memory and 1 is returned.

The format of the exclusive store instruction to store 32-bit data is:

stxr <Ws>, <Wt>, [<Xn|SP>{,#0}]

: 32-bit general-purpose register, used to store the returned status value. Returns 0 if the storage is successful, 1 otherwise.
: 32-bit general-purpose register for storing data.
: 64-bit general-purpose register Xn or stack pointer register, which stores the reference address.

0: Offset, can only be 0, can be omitted. The virtual address of a variable is the base address plus the offset.

For example, the function of the function atomic_add(i, v) is to add i to the value of the atomic variable v. The implementation of the ARM64 architecture is as follows:

arch/arm64/include/asm/atomic_ll_sc.h
   static inline void atomic_add(int i, atomic_t *v)
   {
    unsigned long tmp;
    int result;   

    asm volatile("// atomic_add \n"                    \
   "   prfm   pstl1strm, %2\n"                         \
   "1:   ldxr   %w0, %2\n"                             \
   "   " add "   %w0, %w0, %w3\n"                      \
  "   stxr   %w1, %w0, %2\n"                          \
  "   cbnz   %w1, 1b"                                 \
   : "=&r" (result), "=&r" (tmp), "+Q" (v->counter)   \
   : "Ir" (i));
  }

1) Use the exclusive load instruction to load the value of the atomic variable v into a 32-bit register.
2) Add i to the value of the register.
3) Use the exclusive store instruction to write the value of the register to the atomic variable v.
4) If the exclusive store instruction returns 1, indicating that the store fails, then go back to the 8th line of code to execute again.

In very large systems with many processors and intense competition, using exclusive load instructions and exclusive store instructions may require many retries to succeed, resulting in poor performance. [The ARM] v8.1 standard implements Large System Extensions (LSE), specially designed atomic instructions, and provides the atomic addition instruction stdd: first load 32-bit or 64-bit data from memory into a register, and then add a register to the register. Specify the value and write the result back to memory.

The format of the atomic addition instruction stdd operating on 32-bit data is:

stadd <Ws>, [<Xn|SP>]

: 32-bit general-purpose register to store the value to be added.
: 64-bit general-purpose register Xn or stack pointer register, which stores the virtual address of the variable.

The function atomic_add(i, v) implemented using the atomic addition instruction stdd is as follows:

arch/arm64/include/asm/atomic_lse.h
static inline void atomic_add(int i, atomic_t *v)
{
      register int w0 asm ("w0") = i;
      register atomic_t *x1 asm ("x1") = v;

      asm volatile(" stadd    %w[i], %[v]\n"     \
      : [i] "+r" (w0), [v] "+Q" (v->counter)   \
      : "r" (x1)                               \
      : );
}

Leave a Comment

Your email address will not be published. Required fields are marked *