{"id":98475,"date":"2018-04-10T07:00:00","date_gmt":"2018-04-10T21:00:00","guid":{"rendered":"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/?p=98475"},"modified":"2019-03-13T00:45:26","modified_gmt":"2019-03-13T07:45:26","slug":"20180410-00","status":"publish","type":"post","link":"https:\/\/devblogs.microsoft.com\/oldnewthing\/20180410-00\/?p=98475","title":{"rendered":"The MIPS R4000, part 7: Memory access (atomic)"},"content":{"rendered":"<p>Atomic memory access on the MIPS R4000 is performed with the load-linked and store-conditional instructions. This pattern shouldn&#8217;t be much of a surprise because <a HREF=\"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/20170817-00\/?p=96835\">we already encountered it on the Alpha AXP<\/a>. <\/p>\n<pre>\n    LL      rd, disp16(rs)  ; load linked\n    SC      rs, disp16(rd)  ; store conditional\n<\/pre>\n<p>The <code>LL<\/code> instruction loads a value from memory and monitors the memory address to see if another processor writes to it. The <code>SC<\/code> instruction stores the value to memory, provided there have been no writes&sup1; to the monitored memory address&sup2; and no exceptions have occurred.&sup3; If the store succeeds, then <var>rs<\/var> is set to one; otherwise it is set to zero. <\/p>\n<p>In both cases, the memory address must be word-aligned. <\/p>\n<p>The intended usage pattern is <\/p>\n<pre>\nretry:\n    LL      r1, disp16(r2)  ; load linked\n    ADDIU   r1, r1, 1       ; increment\n    SC      r1, disp16(r2)  ; store conditional\n    BEQ     r1, 0, retry    ; if failed, then retry\n    NOP                     ; (we'll learn about this later)\n<\/pre>\n<p>The state created by the <code>LL<\/code> is ephemeral, and the subsequent <code>SC<\/code> is permitted (but not required) to fail if any of the following occur prior to the <code>SC<\/code>: <\/p>\n<ul>\n<li>A memory access is performed.<\/li>\n<li>A branch is taken.<\/li>\n<li>More than 512 instructions are executed.<\/li>\n<\/ul>\n<p>Furthermore, after the <code>SC<\/code> (either successful or unsuccessful), all subsequent <code>SC<\/code> instructions are required to fail until a new <code>LL<\/code> is executed. <\/p>\n<p>If the <code>LL<\/code> from an address is followed by <code>SC<\/code> which does not write to the same address, then it is unspecified whether the <code>SC<\/code> succeeds. So don&#8217;t do that. <\/p>\n<p>It is legal to execute the <code>LL<\/code> instruction and not follow it with the <code>SC<\/code> instruction. This can happen if you want to perform a conditional atomic operation, and you discover that the condition is not met. <\/p>\n<p>Before and after the <code>LL<\/code>\/<code>SC<\/code> operation, you probably want to do a <\/p>\n<pre>\n    SYNC            ; memory barrier\n<\/pre>\n<p>All memory operations that precede the <code>SYNC<\/code> must complete before any operations that follow the <code>SYNC<\/code> can begin. <\/p>\n<p>Note that atomic operations are supported only on aligned words. For aligned sub-word objects, you can perform the atomic operation on the containing word. But if the object is not aligned, then you&#8217;re out of luck. <\/p>\n<p>Next time, we enter the exciting world of control transfer. That&#8217;s where the <code>NOP<\/code> above gets its moment to shine. <\/p>\n<p>&sup1; Note that if another processor writes the value that is already there back to the memory, or if there is an ABA condition where another processor changes the value, and then changes it back, then the conditional store will fail, even though the value in memory is the same value you started with. This is one cause for the mysterious case of the <a HREF=\"https:\/\/www.youtube.com\/watch?v=ZQFzMfHIxng#t=33m03s\"><code>compare_<\/code><code>exchange_<\/code><code>weak<\/code> spurious failure<\/a>. <\/p>\n<p>&sup2; The architecture permits implementations to be sloppy with the detection of a write. In particular, any modification on the same 4<a HREF=\"https:\/\/blogs.msdn.microsoft.com\/oldnewthing\/20090611-00\/?p=17933\">KB<\/a> page as the locked address is permitted to cause the subsequent store conditional instruction to fail. Mind you, an implementation that was this sloppy would not be a very good implementation, but it is technically legal. <\/p>\n<p>&sup3; This last clause is actually an operating system convention, not something inherent in the processor architecture. One of the things that kernel mode does before returning to user mode is execute the <code>SC<\/code> instruction with a scratch writable memory location. The <code>SC<\/code> might succeed, it might not, but it doesn&#8217;t matter. The reason for the <code>SC<\/code> is to ensure that if the next atomic memory operation performed by user-mode code is <code>SC<\/code>, then that operation <i>definitely<\/i> fails. This is important in the case where the interrupt occurred after the user-mode code performed the <code>LL<\/code> but before it could execute the subsequent <code>SC<\/code>. Without it, the <code>SC<\/code> in user mode might succeed accidentally. <\/p>\n","protected":false},"excerpt":{"rendered":"<p>Load and lock, erm, link.<\/p>\n","protected":false},"author":1069,"featured_media":111744,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"footnotes":""},"categories":[1],"tags":[25],"class_list":["post-98475","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-oldnewthing","tag-code"],"acf":[],"blog_post_summary":"<p>Load and lock, erm, link.<\/p>\n","_links":{"self":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/98475","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/users\/1069"}],"replies":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/comments?post=98475"}],"version-history":[{"count":0,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/posts\/98475\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media\/111744"}],"wp:attachment":[{"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/media?parent=98475"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/categories?post=98475"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/devblogs.microsoft.com\/oldnewthing\/wp-json\/wp\/v2\/tags?post=98475"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}