Improve GamepadSeqLock impl

content/common/gamepad_seqlock.h

Index: content/common/gamepad_seqlock.h
===================================================================
--- content/common/gamepad_seqlock.h	(revision 113580)
+++ 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) {

[darin (slow to review), 2011/12/08 22:10:48]

nit: Can't this be a non-template helper function that just takes an Atomic32*
pointer?

It would probably be good to make GamepadSeqLock<T> inherit from
GamepadSeqLockBase that is non-templatized.  Then, implement the
GamepadSeqLockBase methods in a .cc file.  I'd also declare the
GamepadSeqLockBase class in the content::internal:: namespace.

[dvyukov, 2011/12/13 13:46:20]

Done.

+  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) {

[darin (slow to review), 2011/12/08 22:10:48]

Ditto.

[dvyukov, 2011/12/13 13:46:20]

Done.

+  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.
+  Release_Store(&current_, current_ + 1);
+}
+
 }  // namespace content
 
 #endif  // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_