{"id":3065,"date":"2011-03-25T10:51:27","date_gmt":"2011-03-25T14:51:27","guid":{"rendered":"http:\/\/esr.ibiblio.org\/?p=3065"},"modified":"2014-03-17T07:31:05","modified_gmt":"2014-03-17T11:31:05","slug":"bookend-consistency","status":"publish","type":"post","link":"http:\/\/esr.ibiblio.org\/?p=3065","title":{"rendered":"Bookend consistency"},"content":{"rendered":"<p>I&#8217;ve been thinking recently about writing a shared-memory export for gpsd.  The JSON-over-sockets client interface we have is very powerful and flexible, but more than is needed when network access to the server is not required.  For embedded deployments, in particular &#8211; it would be useful to have a lower-overhead way of shipping results to clients.<\/p>\n<p>Consequently, I&#8217;ve been thinking about coherence techniques for shared memory.  In this particular case, we have one writer (gpsd) and multiple readers (the application clients). Updates to the shared-memory segment are long enough that writes aren&#8217;t guaranteed atomicity. It is permissible for a client to miss an update if it&#8217;s not inspecting the segment frequently enough, but required that after a read from the segment the client can always tell when it has a coherent update (as opposed to having read the segment while a write is in progress).<\/p>\n<p>The obvious way to ensure update coherence would be with a semaphore.  But a technique that is non-blocking and wait-free would be preferable.  I have invented a method I call &#8220;bookend consistency&#8221;.  I present it here for public critique, also because I&#8217;m curious whether any of my commenters can identify it with a known, published algorithm.  It was inspired by a vague, distant memory of pioneering work by Butler Lampson on lock-free algorithms.<\/p>\n<p><!--more--><\/p>\n<p>Suppose we have a structure <b>struct payload_t<\/b> containing our update.  The beginning of the technique is to wrap it in a structure that surrounds it with bookends, like this:<\/p>\n<pre lang=\"C\">\r\nstruct wrapper_t {\r\n    int bookend1;\r\n    struct payload_t payload;\r\n    int bookend2;\r\n}\r\n<\/pre>\n<p>The writer&#8217;s side of the technique is this: Initialize both bookends to zero. On each write, increment the bookends.  Then copy the wrapper structure to the shared-memory segment byte-by-byte, <em>starting with the last byte and backing down to the first<\/em>.<\/p>\n<p>The reader&#8217;s side is simpler: Copy the structure out of the shared-memory segment in normal (first-byte to last) order.  Look at the bookends.  If both have the same value, you have a coherent update. If they differ, you must back off and retry the read.<\/p>\n<p>The reason this technique works is that if the shared-memory segment is in a mixed state (update in progress) the reversed-order write guarantees that bookend2 will be greater than bookend1 until the read is complete.  For the reader, on the other hand, forward copy guarantees that it can&#8217;t be fooled about the value of either bookend.  <\/p>\n<p>(Thomas Zerucha &lt;tz@mich.com&gt; corrected my original proposal by exhibiting a case where you get inconsistency if the write copy is not in reverse order.)<\/p>\n<p>The technique is robust in the face of interrupts to the copy operations, but depends on nothing in the software or hardware stack beneath C reordering the reads and writes in the copies.  A good place to begin ensuring this property is by declaring the pointer to the shared-memory segment &#8216;volatile&#8217;; this will tell your compiler that locations accessed through it may change asynchronously and it should not cache them or mess with operation order.<\/p>\n<p>There are issues with what the underlying hardware might be doing, however.  There are two levels to worry about: instruction reordering in the processor and strange memory-controller optimizations.  The latter we can probably forestall by putting <a href=\"http:\/\/en.wikipedia.org\/wiki\/Memory_barrier\">memory barriers<\/a> before and after the copy loops.<\/p>\n<p>One thing <em>not<\/em> to worry about is multiprocessor cache coherence.  MP systems pretty much have to guarantee interprocessor cache coherency, otherwise common instruction sequences like writes to memory-mapped devices would have undefined behavior. (For the same reason, MP systems have to limit instruction reordering.)<\/p>\n<p>If you use memcpy(3) for forward copy, any modern compiler is likely to optimize it to a single-instruction copy or a phrase like X86 REP MOVS that won&#8217;t be reordered.  The point of maximum vulnerability will be in the reverse copy.  The iffiest case would be a single-processor system doing really aggressive instruction reordering that an MP can&#8217;t risk.  I doubt this is a practical problem, however, as byte-copy loops are so dead-simple that they&#8217;re unlikely targets for reordering.  <\/p>\n","protected":false},"excerpt":{"rendered":"<p>I&#8217;ve been thinking recently about writing a shared-memory export for gpsd. The JSON-over-sockets client interface we have is very powerful and flexible, but more than is needed when network access to the server is not required. For embedded deployments, in particular &#8211; it would be useful to have a lower-overhead way of shipping results to&hellip; <a class=\"more-link\" href=\"http:\/\/esr.ibiblio.org\/?p=3065\">Continue reading <span class=\"screen-reader-text\">Bookend consistency<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[13],"tags":[],"class_list":["post-3065","post","type-post","status-publish","format-standard","hentry","category-software","entry"],"_links":{"self":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/3065","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=3065"}],"version-history":[{"count":5,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/3065\/revisions"}],"predecessor-version":[{"id":3070,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=\/wp\/v2\/posts\/3065\/revisions\/3070"}],"wp:attachment":[{"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=3065"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=3065"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/esr.ibiblio.org\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=3065"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}