===== Memory Model =====
Alpha has the weakest memory ordering model of any architecture Linux has supported. It influenced the design of the Linux kernel memory model, and is the reason ''READ_ONCE()'' is more expensive on Alpha than on other architectures.
The sections below cover the guarantees the architecture makes, the behavior of the hardware, and the code the compiler and the kernel emit. Statements are sourced from the [[documentation:references|Architecture Reference Manual]], from current Linux and GCC source, or from the compiler output reproduced below.
See also [[documentation:porting:unaligned_access|Unaligned Access]] and [[documentation:porting:byte_word_access|Byte and Word Access]].
==== Rules for user-space code ====
* **Use the C11 or C++11 atomics**, or GCC's ''%%__atomic%%'' builtins, rather than hand-written barriers. GCC emits the barriers Alpha needs for each memory order (see [[#what_gcc_emits|What GCC emits]]).
* **Never rely on a data dependency for ordering.** A load through a pointer that was just loaded may return stale data on Alpha (see [[#why_dependent_loads_reorder|Why dependent loads reorder]]). ''memory_order_consume'' is safe, because every implementation promotes it to ''memory_order_acquire''; code that uses a relaxed load and depends on the address dependency is not.
* **Keep atomic objects aligned.** Atomic operations are load-locked/store-conditional loops, and the kernel never emulates a misaligned ''LDx_L'' or ''STx_C'': a misaligned atomic object, for example in a packed structure, always raises ''SIGBUS''. See [[documentation:porting:unaligned_access|Unaligned Access]].
* **Expect sub-word atomics to be emulated.** Alpha's load-locked and store-conditional instructions operate only on longwords and quadwords. GCC implements atomic operations on 8-bit and 16-bit objects by operating on the aligned quadword that contains them, masking the other bytes. [(>[[https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/config/alpha/alpha.cc|gcc/config/alpha/alpha.cc]], GCC)] They are correct but slower, and contend with any other atomic variable in the same lock range, which is at least the containing quadword (see [[documentation:porting:byte_word_access#reservation_granularity|Reservation granularity]]). There is no 16-byte atomic instruction, so 16-byte atomic operations are not lock-free and are handled by ''libatomic'', which must be linked with ''-latomic''. [(>[[https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/config/alpha/sync.md|''gcc/config/alpha/sync.md'']], GCC)]
* **Follow the load-locked/store-conditional rules in inline assembly.** Only register-to-register integer instructions may appear between ''LDx_L'' and ''STx_C'', and no branch may be taken on the path from one to the other; a branch that abandons the sequence without executing the ''STx_C'' is permitted (see [[#load-locked_store-conditional|Load-Locked / Store-Conditional]]).
* **Execute ''CALL_PAL IMB'' after writing code.** A JIT compiler must make newly written instructions visible to the instruction stream; ''%%__builtin___clear_cache()%%'' emits the ''IMB''. [(>[[https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/config/alpha/alpha.md|''gcc/config/alpha/alpha.md'']], GCC)]
==== Permitted reorderings ====
^ Reordering ^ Alpha ^ x86 (TSO) ^ ARMv7 ^ SPARC TSO ^
| Store to store | Yes | No | Yes | No |
| Load to load | Yes | No | Yes | No |
| Load to store | Yes | No | Yes | No |
| Store to load | Yes | Yes | Yes | Yes |
| Dependent load to load | Yes | No | No | No |
The last row distinguishes Alpha from the others. Every other architecture guarantees that when a pointer is loaded and a second load is made through it, the second load observes memory at least as new as the first. Alpha does not.
==== Why dependent loads reorder ====
The kernel's ''Documentation/memory-barriers.txt'' names Alpha as the machine on which this reordering can actually be observed, and attributes it to the cache rather than to speculative execution: some Alpha implementations have a split data cache, whose two banks can be updated at different times. [(membar>[[https://www.kernel.org/doc/Documentation/memory-barriers.txt|''Documentation/memory-barriers.txt'']], Linux. See "AND THEN THERE'S THE ALPHA".)]
The two loads go to different cache banks, and the banks are updated independently. The dereferencing processor can see the new pointer from one bank while the old contents of the target are still live in another. The wording "some versions of the Alpha CPU" is significant: this is an implementation property that the architecture permits, not behavior exhibited by every Alpha.
The kernel's Alpha ''READ_ONCE()'' implementation cites the same explanation, which is given in more detail in chapter 15 of Paul McKenney's "perfbook". [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/rwonce.h|''arch/alpha/include/asm/rwonce.h'']], Linux)] [(>Paul E. McKenney, [[https://kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html|"Is Parallel Programming Hard, And, If So, What Can You Do About It?"]] ("perfbook"), chapter 15)]
==== Barrier instructions ====
Alpha has exactly two memory barrier instructions, plus a PALcode call for the instruction stream.
^ Instruction ^ Effect ^
| ''MB'' | Full barrier. All previous loads and stores access memory before any subsequent load or store does, as observed by other processors. |
| ''WMB'' | Write barrier. Writes before it complete before writes after it, and are not aggregated with them. Loads may cross it freely. |
| ''CALL_PAL IMB'' | Instruction memory barrier, for self-modifying or newly loaded code. |
There is no read barrier instruction: the binutils opcode table lists ''mb'' and ''wmb'' and nothing else of the kind. Linux therefore defines ''rmb()'' as a full ''mb'': [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/barrier.h|''arch/alpha/include/asm/barrier.h'']], Linux)]
#define mb() __asm__ __volatile__("mb": : :"memory")
#define rmb() __asm__ __volatile__("mb": : :"memory")
#define wmb() __asm__ __volatile__("wmb": : :"memory")
The Architecture Reference Manual is precise about what ''MB'' does and does not provide: [(arm2>{{wiki:documentation:references:alpha_architecture_reference_manual_2nd_edition.pdf?linkonly|Alpha AXP Architecture Reference Manual, Second Edition}}. Section 4.11 covers ''MB'', ''WMB'', ''LDx_L'' and ''STx_C''; Chapter 5 covers the memory model, atomic update of data structures (5.5), ordering considerations for shared data structures (5.5.4) and memory-mapped I/O (5.6.4.7).)]
Note that MB ensures serialization only; it does not necessarily accelerate the progress of memory operations.
and about what happens without ''WMB'': [(arm2)]
In the absence of a WMB instruction, stores to memory or non-memory-like regions can be aggregated and/or buffered and completed in any order.
==== The dependent load problem in practice ====
/* Thread A, the writer */
node->value = 42;
smp_wmb(); /* value store is visible before the pointer store */
list->head = node;
/* Thread B, the reader. BROKEN on Alpha. */
struct node *p = list->head;
int v = p->value; /* may read the pre-initialization contents */
Thread B needs a barrier between the two loads even though the second load depends on the first. The kernel once had a separate ''smp_read_barrier_depends()'' for this, an ''mb'' on Alpha and nothing elsewhere. Since Linux 4.15 Alpha's ''READ_ONCE()'' includes the barrier, [(>Peter Zijlstra, [[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=76ebbe78f7390aee075a7f3768af197ded1bdfbb|''76ebbe78f739'' "locking/barriers: Add implicit smp_read_barrier_depends() to READ_ONCE()"]], Linux v4.15)] and Linux 5.9 removed ''smp_read_barrier_depends()'' entirely. [(>Will Deacon, [[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=d6462858851549c62d73eaa14b31132b0f32d6b6|''d64628588515'' "alpha: Override READ_ONCE() with barriered implementation"]], Linux v5.9)] [(>Will Deacon, [[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=93fab07c22930c9ac4f01212fd92913c9a812f9f|''93fab07c2293'' "locking/barriers: Remove definitions for [smp_]read_barrier_depends()"]], Linux v5.9)] Only Alpha architecture code still needs to consider the problem explicitly. [(membar)]
What Alpha does today is a plain volatile load followed by a full ''mb'', whenever ''CONFIG_SMP'' is set: [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/rwonce.h|''arch/alpha/include/asm/rwonce.h'']], Linux)]
#define __READ_ONCE(x) \
({ \
__unqual_scalar_typeof(x) __x = \
(*(volatile typeof(__x) *)(&(x))); \
mb(); \
(typeof(x))__x; \
})
Because that barrier is already present, ''smp_load_acquire()'' on Alpha is defined as ''__READ_ONCE()'': [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/barrier.h|''arch/alpha/include/asm/barrier.h'']], Linux)]
#define __smp_load_acquire(p) \
({ \
compiletime_assert_atomic_type(*p); \
__READ_ONCE(*p); \
})
The porting consequence is that kernel code using ''READ_ONCE()'', ''rcu_dereference()'' or ''smp_load_acquire()'' is unaffected by the dependent-load problem, as is userspace code using C11 or C++11 atomics, where every implementation promotes ''memory_order_consume'' to ''memory_order_acquire''. Hand-written lock-free code that relies on data dependencies for ordering is incorrect on Alpha.
==== Load-Locked / Store-Conditional ====
Alpha has no atomic read-modify-write instruction. Every atomic operation is built from ''LDL_L''/''LDQ_L'' and ''STL_C''/''STQ_C''. ''STx_C'' writes 1 into its source register on success and 0 on failure, and clears the lock flag either way.
=== Forward progress rules ===
The Architecture Reference Manual places hard restrictions on what may appear between the load-locked and the store-conditional. These are correctness requirements rather than recommendations: [(arm2)]
* If any other memory access (LDx, LDQ_U, STx, STQ_U) is done on the given processor between the LDx_L and the STx_C, the sequence above may always fail on some implementations; hence, no useful program should do this.
* If a branch is taken between the LDx_L and the STx_C, the sequence above may always fail on some implementations; hence, no useful program should do this. (CMOVxx may be used to avoid branching.)
* If a subsetted instruction (for example, floating-point) is done between the LDx_L and the STx_C, the sequence above may always fail on some implementations, because of the Illegal Instruction Trap; hence, no useful program should do this.
* If a large number of instructions are executed between the LDx_L and the STx_C, the sequence above may always fail on some implementations, because of a timer interrupt always clearing the lock_flag before the sequence completes; hence, no useful program should do this.
* Hardware implementations are encouraged to lock no more than 128 bytes.
Only register-to-register integer work may appear between the two instructions.
=== Atomic increment ===
The kernel's implementation shows the idiom, including the branch layout: [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/atomic.h|''arch/alpha/include/asm/atomic.h'']], Linux)]
/*
* To get proper branch prediction for the main line, we must branch
* forward to code at the end of this object's .text section, then
* branch back to restart the operation.
*/
#define ATOMIC_OP(op, asm_op) \
static __inline__ void arch_atomic_##op(int i, atomic_t * v) \
{ \
unsigned long temp; \
__asm__ __volatile__( \
"1: ldl_l %0,%1\n" \
" " #asm_op " %0,%2,%0\n" \
" stl_c %0,%1\n" \
" beq %0,2f\n" \
".subsection 2\n" \
"2: br 1b\n" \
".previous" \
:"=&r" (temp), "=m" (v->counter) \
:"Ir" (i), "m" (v->counter)); \
} \
The retry path lives in ''.subsection 2'' so that both in-line conditional branches are forward branches, and are therefore predicted not taken. The Architecture Reference Manual makes the same point: [(arm2)]
Both conditional branches are forward branches, so they are properly predicted not to be taken (to match the common case of no contention for the lock).
This macro generates the //unordered// form. A fully ordered read-modify-write requires a barrier on both sides; Linux places them outside the assembly.
=== Compare and swap ===
static inline unsigned long
____cmpxchg_u32(volatile int *m, int old, int new)
{
unsigned long prev, cmp;
__asm__ __volatile__(
"1: ldl_l %0,%5\n"
" cmpeq %0,%3,%1\n"
" beq %1,2f\n"
" mov %4,%1\n"
" stl_c %1,%2\n"
" beq %1,3f\n"
"2:\n"
".subsection 2\n"
"3: br 1b\n"
".previous"
: "=&r"(prev), "=&r"(cmp), "=m"(*m)
: "r"((long) old), "r"(new), "m"(*m) : "memory");
return prev;
}
with the barriers wrapped around the whole thing: [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/cmpxchg.h|''arch/alpha/include/asm/cmpxchg.h'']], Linux)]
/*
* The leading and the trailing memory barriers guarantee that these
* operations are fully ordered.
*/
#define arch_cmpxchg(ptr, o, n) \
({ \
__typeof__(*(ptr)) __ret; \
__typeof__(*(ptr)) _o_ = (o); \
__typeof__(*(ptr)) _n_ = (n); \
smp_mb(); \
__ret = (__typeof__(*(ptr))) ____cmpxchg((ptr), \
(unsigned long)_o_, (unsigned long)_n_, sizeof(*(ptr)));\
smp_mb(); \
__ret; \
})
Because the barriers are outside, a //failing// ''cmpxchg()'' is still fully ordered. Hand-written CAS loops commonly branch out of the loop on mismatch and skip the trailing barrier.
On the mismatch path the reservation is abandoned, which the architecture permits: [(arm2)]
LDx_L and STx_C instructions need not be paired. In particular, an LDx_L may be followed by a conditional branch: on the fall-through path an STx_C is done, whereas on the taken path no matching STx_C is done.
==== Locks ====
Alpha has no load-acquire or store-release instruction. Acquire and release semantics are built out of ''MB''.
A spin-wait must not repeat the ''LDx_L'' itself. The Architecture Reference Manual: [(arm2)]
It would be a performance mistake to spin-wait by repeating the full LDQ_L..STQ_C sequence (to move the BLBS after the BEQ) because that sequence may repeatedly change the software lock_variable from "locked" to "locked," with each write causing extra access delays in all other caches that contain the lock_variable. In the extreme, spin-waits that contain writes may deadlock.
In the Linux implementation the contended spin loop at label ''2'' uses a plain ''ldl'' rather than ''ldl_l'': [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/spinlock.h|''arch/alpha/include/asm/spinlock.h'']], Linux)]
static inline void arch_spin_lock(arch_spinlock_t * lock)
{
long tmp;
__asm__ __volatile__(
"1: ldl_l %0,%1\n"
" bne %0,2f\n"
" lda %0,1\n"
" stl_c %0,%1\n"
" beq %0,2f\n"
" mb\n"
".subsection 2\n"
"2: ldl %0,%1\n"
" bne %0,2b\n"
" br 1b\n"
".previous"
: "=&r" (tmp), "=m" (lock->lock)
: "m"(lock->lock) : "memory");
}
static inline void arch_spin_unlock(arch_spinlock_t * lock)
{
mb();
lock->lock = 0;
}
As of Linux 7.3, Alpha has not been converted to qspinlock; the code above is the current implementation.
On barrier placement, the Architecture Reference Manual prescribes: [(arm2)]
MB (memory barrier #1)
WMB or MB (memory barrier #2)
The first memory barrier prevents any reads (from within the critical section) from being prefetched before the software lock is acquired; such prefetched reads would potentially contain stale data.
The second memory barrier prevents any writes (and reads if MB is used instead of WMB) from within the critical section from being delayed past the clearing of the software lock.
The acquire-side barrier must be ''MB''. A ''WMB'' on the release side orders only the critical section's stores before the unlock; its loads may still complete after the lock is released. ''WMB'' therefore suffices only if nothing depends on those loads completing inside the critical section. Linux uses a full ''mb()''.
==== Memory-Mapped I/O ====
Device registers are accessed through ''readl()'', ''writel()'' and the related accessors. On Alpha these already carry the necessary barriers, and ''writel_relaxed'' is defined as plain ''writel'': [(ioh>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/io.h|''arch/alpha/include/asm/io.h'']], Linux)]
extern inline u32 readl(const volatile void __iomem *addr)
{
u32 ret;
mb();
ret = __raw_readl(addr);
mb();
return ret;
}
extern inline void writel(u32 b, volatile void __iomem *addr)
{
mb();
__raw_writel(b, addr);
}
''writel()'' has a leading barrier and no trailing one. The asymmetry is deliberate: a barrier does not make a write to a device register complete: [(arm2)]
If an Alpha AXP processor writes a location that is a control register within an I/O device, then executes a memory barrier, then writes a location in memory (in a memory-like or non-memory-like region), the I/O device may be able to detect (via read access) the result of the memory write before receiving and responding to the write of its own control register.
In almost every case, a mechanism that ensures the completion of writes to control register locations within I/O devices is provided. The normal and strongly recommended mechanism is to read a location after writing it, which guarantees that the write is complete.
A device write is forced to complete by reading the register back. The kernel does this when setting the HAE register: [(ioh)]
alpha_mv.hae_cache = new_hae;
*alpha_mv.hae_register = new_hae;
mb();
/* Re-read to make sure it was written. */
new_hae = *alpha_mv.hae_register;
For a single processor accessing the //same// address, no barrier is needed at all. From the Architecture Reference Manual: [(arm2)]
A read to physical address x will always return the value written by the immediately preceding write to x in the processor issue sequence.
The exposure is ordering between //different// registers, and ordering as the device sees it across a bus bridge.
==== Instruction stream and TB invalidation ====
Writing instructions to memory does not make them visible to the instruction stream. The architecture requires ''CALL_PAL IMB'' whenever the instruction stream changes, and on a multiprocessor the operating system must arrange for every processor that may hold stale copies to do the same. [(arm2)] ''MB'' is not sufficient. User-space code gets the ''IMB'' from ''%%__builtin___clear_cache()%%'' (see [[#rules_for_user-space_code|Rules for user-space code]]).
Translation buffer invalidation is not an instruction either: under the OSF/1 PALcode that Linux uses, ''TBIA'', ''TBIS'' and related operations are the PALcode call ''CALL_PAL tbi'', with the operation selected by a register argument. [(>[[https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/tree/arch/alpha/include/asm/pal.h|''arch/alpha/include/asm/pal.h'']], Linux)]
==== What GCC emits ====
The output below is from ''alpha-unknown-linux-gnu-gcc 16.2.0'' at ''-O2''. The GP-relative address computation has been elided for readability.
_Atomic int flag;
void st_rel(void) { atomic_store_explicit(&flag, 1, memory_order_release); }
int ld_acq(void) { return atomic_load_explicit(&flag, memory_order_acquire); }
void st_sc(void) { atomic_store_explicit(&flag, 1, memory_order_seq_cst); }
void fence(void) { atomic_thread_fence(memory_order_seq_cst); }
st_rel: mb ; stl $2,flag($1) ; ret
ld_acq: ldl $0,flag($1) ; mb ; ret
st_sc: mb ; stl $2,flag($1) ; mb ; ret
fence: mb ; ret
Two points follow from this output:
* A release store emits ''MB'' before the store, not ''WMB''.
* GCC's Alpha back end has no ''WMB'' pattern, and ''mb'' is the only barrier it emits. The single barrier pattern in ''gcc/config/alpha/sync.md'' expands ''UNSPEC_MB'' to the string ''"mb"'', and no file in ''gcc/config/alpha/'' refers to ''wmb''. [(>[[https://gcc.gnu.org/git/?p=gcc.git;a=blob;f=gcc/config/alpha/sync.md|''gcc/config/alpha/sync.md'']], GCC)]
The legacy ''%%__sync%%'' builtins are full barriers by definition, and GCC brackets them accordingly:
faa: ; __sync_fetch_and_add(p, 1)
mb
$L10:
ldl_l $0,0($16)
addl $0,1,$1
stl_c $1,0($16)
beq $1,$L10
mb
ret $31,($26),1
cas: ; __sync_bool_compare_and_swap(p, old, new)
mb
$L12:
ldl_l $1,0($16)
cmpeq $1,$17,$0
beq $0,$L13
mov $18,$0
stl_c $0,0($16)
beq $0,$L12
$L13:
mb
ret $31,($26),1
At label ''$L13'' the trailing ''mb'' covers the failure path as well as the success path, matching the kernel's ''arch_cmpxchg()''.
==== Summary ====
^ Need ^ On Alpha ^
| Full barrier | ''MB'' |
| Write barrier | ''WMB'' (architecture only; GCC never emits it) |
| Read barrier | does not exist; use ''MB'' |
| Atomic read-modify-write | ''LDx_L''/''STx_C'' loop, with only register operates and no taken branch in between |
| Fully ordered RMW | ''MB'' before and after the loop |
| Publish a pointer, writer | ''WMB'' (or ''MB'') before the pointer store |
| Publish a pointer, reader | ''MB'' after the pointer load; in the kernel, ''READ_ONCE()'' supplies it |
| Acquire a lock | ''LDx_L''/''STx_C'' loop, spin on a plain ''LDx'', then ''MB'' |
| Release a lock | ''MB'' (''WMB'' permitted), then the clearing store |
| MMIO | ''readl()''/''writel()''; read back to force completion |
| Invalidate the TB | ''CALL_PAL tbi'', not an instruction |
| Invalidate the I-cache | ''CALL_PAL IMB'', not ''MB'' |
{{tag>documentation porting}}