Improve GamepadSeqLock impl

content/common/gamepad_seqlock.h

Index: content/common/gamepad_seqlock.h
===================================================================
--- content/common/gamepad_seqlock.h	(revision 112429)
+++ content/common/gamepad_seqlock.h	(working copy)
@@ -6,41 +6,116 @@
 #define CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
 
 #include "base/atomicops.h"
-#include "base/threading/platform_thread.h"
-#include "content/common/content_export.h"
 
 namespace content {
 
 // This SeqLock handles only *one* writer and multiple readers. It may be
-// suitable for low-contention with relatively infrequent writes, and many
-// readers. See:
+// suitable for high read frequency scenarios and is especially useful in shared
+// memory environment. See for the basic idea:
 //   http://en.wikipedia.org/wiki/Seqlock
-//   http://www.concurrencykit.org/doc/ck_sequence.html
-// This implementation is based on ck_sequence.h from http://concurrencykit.org.
-//
-// Currently, this is used in only one location. It may make sense to
-// generalize with a higher-level construct that owns both the lock and the
-// data buffer, if it is to be used more widely.
-//
-// You must be very careful not to operate on potentially inconsistent read
-// buffers. If the read must be retry'd, the data in the read buffer could
-// contain any random garbage. e.g., contained pointers might be
-// garbage, or indices could be out of range. Probably the only suitable thing
-// to do during the read loop is to make a copy of the data, and operate on it
-// only after the read was found to be consistent.
-class CONTENT_EXPORT GamepadSeqLock {
+// However, this implementation is an improved lock-free variant.
+// The SeqLock can hold only POD fully-embed data (no pointers
+// to satellite data), copies are done with memcpy.
+template<typename T>
+class GamepadSeqLock {
  public:
   GamepadSeqLock();
-  base::subtle::Atomic32 ReadBegin();
-  bool ReadRetry(base::subtle::Atomic32 version);
-  void WriteBegin();
-  void WriteEnd();
+  void ReadTo(T* obj);
+  void Write(T const& obj);
 
  private:
-  base::subtle::Atomic32 sequence_;
+  typedef base::subtle::Atomic32 Atomic32;
+  typedef char static_assert_size[sizeof(T) % sizeof(Atomic32) ? -1 : 1];
+  static size_t const kSize = sizeof(T) / sizeof(Atomic32);
+  static size_t const kEntries = 2;
+  struct Entry {
+    Atomic32 sequence_;
+    // Both writer and readers work with the array concurrently,
+    // so it must be accessed with atomic operations.
+    Atomic32 data_[kSize];
+  };
+  Atomic32 current_;
+  Entry entries_[kEntries];
   DISALLOW_COPY_AND_ASSIGN(GamepadSeqLock);
 };
 
+template<typename T>
+GamepadSeqLock<T>::GamepadSeqLock()
+  : current_(0) {
+  memset(entries_, 0, sizeof(entries_));
+}
+
+// The algorithm works as follows.
+// The SeqLock contains 2 user objects - a current and a non-current.
+// The object roles can be swapped by incrementing the current_ variable.
+// Initially both objects are consistent, that is, their sequence_%2 == 0.
+// A writer proceeds as follows. First, it marks the non-current object
+// as inconsistent by incrementing it's sequence_ (the sequence_ becomes odd).
+// Then it mutates the object. Then marks it as consistent by incrementing
+// it's sequence_ once again (the sequence_ is even now). And finally swaps
+// the object roles, that is, the object becomes current.
+// Such disipline establishes an important property - the current object
+// is always consistent and contains the most recent data.
+// Readers proceed as follows. First, determine what is the current object,
+// remember it's seqence, check that the sequence is even
+// (the object is consistent), copy out the object, verify that
+// the sequence is not changed. If any of the checks fail, a reader works
+// with a non-current object (current object is always consistent), so it
+// just retries from the beginning. Thus readers are completely lock-free,
+// that is, a reader retries iff a writer has accomplished a write operation
+// during reading (only constant sequence of writes can stall readers,
+// a stalled writer can't block readers).
+
+template<typename T>
+void GamepadSeqLock<T>::ReadTo(T* obj) {
+  using base::subtle::NoBarrier_Load;
+  using base::subtle::Acquire_Load;
+  using base::subtle::MemoryBarrier;
+  for (;;) {
+    // Determine the current object.
+    Atomic32 cur = Acquire_Load(&current_);
+    Entry* ent = &entries_[cur % kEntries];
+    Atomic32 seq = Acquire_Load(&ent->sequence_);  // membar #LoadLoad
+    // If the counter is even, then the object is not already current,
+    // no need to yield, just retry (the current object is consistent).
+    if (seq % 2)
+      continue;
+    // Breaks strict-aliasing rules.
+    Atomic32* dst = reinterpret_cast<Atomic32*>(obj);
+    // Copy out the entry.
+    for (size_t i = 0; i < kSize; ++i)
+      dst[i] = NoBarrier_Load(&ent->data_[i]);
+    MemoryBarrier();  // membar #LoadLoad
+    Atomic32 seq2 = NoBarrier_Load(&ent->sequence_);
+    // If the counter is changed, then we've read inconsistent data,
+    // no need to yield, just retry (the current object is consistent).
+    if (seq2 != seq)
+      continue;
+    break;
+  }
+}
+
+template<typename T>
+void GamepadSeqLock<T>::Write(T const& obj) {
+  using base::subtle::NoBarrier_Store;
+  using base::subtle::Release_Store;
+  using base::subtle::MemoryBarrier;
+  // Get the non current object...
+  Entry* ent = &entries_[(current_ + 1) % kEntries];
+  // ... and mark it as inconsistent.
+  NoBarrier_Store(&ent->sequence_, ent->sequence_ + 1);
+  MemoryBarrier();  // membar #StoreStore
+  // Breaks strict-aliasing rules.
+  Atomic32 const* src = reinterpret_cast<Atomic32 const*>(&obj);
+  // Copy in the entry.
+  for (size_t i = 0; i < kSize; ++i)
+    NoBarrier_Store(&ent->data_[i], src[i]);
+  // Mark the object as consistent again.
+  Release_Store(&ent->sequence_, ent->sequence_ + 1);  // membar #StoreStore
+  // Switch the current object.

[jbates, 2011/12/08 01:02:36]

The reason for having both of these stores with a memory barrier is a bit
subtle. After thinking it through, it looks like it's necessary to avoid
spinning in the reader thread on line 82. (I was thinking it would be nice to
reduce the number of memory barriers for simplicity and performance, such as
store current_; store ent->sequence_; barrier; but it looks like that could lead
to spinning in the reader thread if the writer was swapped out between the
stores.)

[dvyukov, 2011/12/08 09:28:12]

Missed memory fences usually only increase complexity :) It's much easier to
reason when reorderings are restricted.
As for performance, store-release is completely free on x86. The fences that we
want to remove for performance reasons are on lines 88 and 107. The former can
easily increase reading cost 10x. However it is unsolvable with current atomic
API (to solve that we need either load-load/store-store fences or
ReleaseLoads_Load and AcquireStores_Store) - all are no-ops on x86).

+  Release_Store(&current_, current_ + 1);
+}
+
 }  // namespace content
 
 #endif  // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_