Low-Level Implementation of Atomic Operations in Linux Kernel (armv8-aarch64)

Typically, a line of code like a = a + 1 in our code translates to three assembly instructions:

ldr x0, &a
add x0,x0,#1
str x0,&a

That means (1) reading variable a from memory into register X0 (2) adding 1 to register X0 (3) writing X0 back to memory a

Since there are three instructions, concurrency is possible, which means the returned result may not be what is expected.

In the Linux kernel operating system, functions are provided to access atomic variables to solve the above issues. Some atomic operation APIs are as follows:

atomic_read
atomic_add_return(i,v)
atomic_add(i,v)
atomic_inc(v)
atomic_add_unless(v,a,u)
atomic_inc_not_zero(v)
atomic_sub_return(i,v)
atomic_sub_and_test(i,v)
atomic_sub(i,v)
atomic_dec(v)
atomic_cmpxchg(v,old,new)

So how does the operating system (which is just software) ensure atomic operations? (It still relies on hardware.) What is the hardware principle?

The above API functions ultimately call the macro <span>__lse_atomic_add_return##name</span>, where the core instruction is the <span>ldadd</span> instruction, which is part of the LSE (Large System Extension) feature introduced in armv8.1.

(linux/arch/arm64/include/asm/atomic_lse.h)

static inline int __lse_atomic_add_return##name(int i, atomic_t *v)  \
{                                 \
    u32 tmp;                         \
                                    \
    asm volatile(                     \
    __LSE_PREAMBLE                   \
    "    ldadd" #mb "    %w[i], %w[tmp], %[v]\n"  \
    "    add    %w[i], %w[i], %w[tmp]"    \
    : [i] "+r" (i), [v] "+Q" (v->counter), [tmp] "=&r" (tmp)  \
    : "r" (v)                        \
    : cl);                            \
                                    \
    return i;                        \
}

What if the system does not have the LSE extension, i.e., armv8.0? The implementation prototype is as follows, where the core instructions are <span>ldxr</span> and <span>stxr</span>.

(linux/arch/arm64/include/asm/atomic_ll_sc.h)

static inline void __ll_sc_atomic_##op(int i, atomic_t *v)\
{                                 \
    unsigned long tmp;                \
    int result;                      \
                                    \
    asm volatile("// atomic_" #op "\n"                \
    __LL_SC_FALLBACK(                \
"    prfm    pstl1strm, %2\n"                \
"1:    ldxr    %w0, %2\n"                \
"    " #asm_op "    %w0, %w0, %w3\n"                \
"    stxr    %w1, %w0, %2\n"                \
"    cbnz    %w1, 1b\n")                \
    : "=&r" (result), "=&r" (tmp), "+Q" (v->counter)        \
    : __stringify(constraint) "r" (i));                \
}

What about before armv8.0, such as armv7? The implementation is as follows, where the core instructions are <span>ldrex</span> and <span>strex</span>.

(linux/arch/arm/include/asm/atomic.h)

static inline void atomic_##op(int i, atomic_t *v)            \
{                                 \
    unsigned long tmp;                \
    int result;                      \
                                    \
    prefetchw(&v->counter);                \
    __asm__ __volatile__("@ atomic_" #op "\n"            \
"1:    ldrex    %0, [%3]\n"                \
"    " #asm_op "    %0, %0, %4\n"                \
"    strex    %1, %0, [%3]\n"                \
"    teq    %1, #0\n"                \
"    bne    1b"                        \
    : "=&r" (result), "=&r" (tmp), "+Qo" (v->counter)        \
    : "r" (&v->counter), "Ir" (i)                    \
    : "cc");                        \
}

Summary:

In the early days, atomic operations were implemented using the arm exclusive mechanism, where the exclusive-related instructions were <span>ldrex</span> and <span>strex</span>. However, after armv8, the exclusive mechanism’s instructions changed to <span>ldxr</span> and <span>stxr</span>. Due to the large number of processors in a big system and intense competition, using exclusive load and store instructions may require multiple attempts to succeed, leading to poor performance. To solve this problem, armv8.1 introduced atomic operation instructions like <span>ldadd</span>.