{"id":96835,"date":"2017-08-17T07:00:00","date_gmt":"2017-08-17T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=96835"},"modified":"2019-03-13T01:15:24","modified_gmt":"2019-03-13T08:15:24","slug":"20170817-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20170817-00\/?p=96835","title":{"rendered":"The Alpha AXP, part 9: The memory model and atomic memory operations"},"content":{"rendered":"

The Alpha AXP has a notoriously weak memory model. When a processor writes to memory, the result becomes visible to other processors eventually, but there are very few constraints beyond that. <\/p>\n

For example, writes can become visible out of order. One processor writes a value to a location, and then writes a value to another location, and another processor can observe the second write without the first. Similarly, reads can complete out of order. One processor reads a value from a location, then reads from another location, and the result could be that the second read happens before the first.¹ <\/p>\n

Assume that memory locations x<\/var> and y<\/var> are both initially zero. The following sequence of operations is valid. <\/p>\n\n\n\n\n\n
Processor 1<\/th>\nProcessor 2<\/th>\n<\/tr>\n
write 1 to x<\/var><\/td>\nread y<\/var> yields 1<\/td>\n<\/tr>\n
<\/td>\nMB<\/code> (memory barrier)<\/td>\n<\/tr>\n
write 1 to y<\/var><\/td>\nread x<\/var> yields 0<\/td>\n<\/tr>\n<\/table>\n

The memory barrier instruction MB<\/code> instructs the processor to make all previous loads and stores complete to memory before starting any new loads and stores. However, it doesn’t force other processors to do anything; other processors can still complete their memory operations out of order, and that’s what happened in the above example. <\/p>\n

Similarly, the following sequence is also legal: <\/p>\n\n\n\n\n\n
Processor 1<\/th>\nProcessor 2<\/th>\n<\/tr>\n
write 1 to x<\/var><\/td>\nread y<\/var> yields 1<\/td>\n<\/tr>\n
MB<\/code> (memory barrier)<\/td>\n<\/td>\n<\/tr>\n
write 1 to y<\/var><\/td>\nread x<\/var> yields 0<\/td>\n<\/tr>\n<\/table>\n

This is also legal because the memory barrier on processor 1 ensures that the value of x<\/var> gets updated before the value of y<\/var>, but it doesn’t prevent processor 2 from performing the reads out of order. <\/p>\n

In order to prevent x<\/var> and y<\/var> from appearing to be updated out of order, both<\/i> sides need to issue memory barriers. Processor 1 needs a memory barrier to ensure that the write to x<\/var> happens before the write to y<\/var>, and processor 2 needs a memory barrier to ensure that the read from y<\/var> happens before the read from x<\/var>. <\/p>\n

Okay, onward to atomic operations. <\/p>\n

Performing atomic operations on memory requires the help of two new pairs of instructions: <\/p>\n

\n    LDL_L   Ra, disp16(Rb)  ; load locked\n    LDQ_L   Ra, disp16(Rb)\n\n    STL_C   Ra, disp16(Rb)  ; store conditional\n    STQ_C   Ra, disp16(Rb)\n<\/pre>\n
The load locked<\/i> instruction performs a traditional read from memory, but also sets the lock_<\/var>flag<\/var> and memorizes the physical address in phys_locked<\/var>. The processor monitors for any changes to that physical address from any processor, and if a change is detected,² the lock_<\/var>flag<\/var> is cleared. <\/p>\n
The lock_<\/var>flag<\/var> is also cleared by a variety of other conditions, most notably when the processor returns from kernel mode back to user mode. This means that any hardware interrupt or trap (such as a page fault, or executing an emulated instruction) will clear the lock_<\/var>flag<\/var>. It is recommended that operating systems allow at least 40 instructions to execute between timer interrupts. <\/p>\n
You can later do a store conditional<\/i> operation which will store a value to a memory address, provided the lock_<\/var>flag<\/var> is still set. If so, then the source register is set to 1. If not, then the source register is set to 0 and the memory is left unmodified. Regardless of the result, the lock_<\/var>flag<\/var> is cleared. <\/p>\n
A typical atomic increment looks like this: <\/p>\n
\nretry:\n    LDL_L   t1, (t0)        ; load locked\n    ADDL    t1, #1, t1      ; increment value\n    STL_C   t1, (t0)        ; store conditional\n                            ; t1 = 1 if store was successful\n    BEQ     t1, failed      ; jump if store failed\n    ... continue execution ...\n\nfailed:\n    BR      zero, retry     ; try again\n<\/pre>\n
In the case where the store failed, we jump forward, and then back. Recall that conditional jumps backward are predicted taken, and conditional jumps forward are predicted not taken. If we had simply jumped backward on failure, then the processor would have a branch prediction miss in the common case that there is no contention. <\/p>\n
Note that the above sequence does not impose any memory ordering. In practice, you will see a MB<\/code> before and\/or after the atomic sequence in order to enforce acquire and\/or release semantics. <\/p>\n
There are a number of practical rules regarding the LDx<\/u>_L<\/code> and STx<\/u>_C<\/code> instructions. The most important ones are these: <\/p>\n