Improve GamepadSeqLock impl

content/common/gamepad_seqlock.cc

Index: content/common/gamepad_seqlock.cc
===================================================================
--- content/common/gamepad_seqlock.cc	(revision 117420)
+++ content/common/gamepad_seqlock.cc	(working copy)
@@ -5,45 +5,81 @@
 #include "content/common/gamepad_seqlock.h"
 
 namespace content {
+namespace internal {
 
-GamepadSeqLock::GamepadSeqLock()
-  : sequence_(0) {
+GamepadSeqLockBase::GamepadSeqLockBase(Entry* entries, size_t size)
+  : size_(size)
+  , current_(0) {
+  const size_t entSize = sizeof(Entry) + sizeof(Atomic32) * size;
+  memset(entries, 0, kEntries * entSize);
+  for (size_t i = 0; i < kEntries; ++i)
+    entries_[i] = (Entry*)((char*)entries + i * entSize);

[jbates, 2012/02/17 23:29:52]

guidelines prohibit c-style casts I think.

[dvyukov, 2012/02/21 15:18:04]

Done.

 }
 
-base::subtle::Atomic32 GamepadSeqLock::ReadBegin() {
-  base::subtle::Atomic32 version;
+// 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).
+
+void GamepadSeqLockBase::ReadTo(Atomic32* obj) {
+  using base::subtle::NoBarrier_Load;
+  using base::subtle::Acquire_Load;
+  using base::subtle::MemoryBarrier;
   for (;;) {
-    version = base::subtle::NoBarrier_Load(&sequence_);
-
-    // If the counter is even, then the associated data might be in a
-    // consistent state, so we can try to read.
-    if ((version & 1) == 0)
-      break;
-
-    // Otherwise, the writer is in the middle of an update. Retry the read.
-    base::PlatformThread::YieldCurrentThread();
+    // 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;
+    // Copy out the entry.
+    for (size_t i = 0; i < size_; ++i)
+      obj[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;
   }
-  return version;
 }
 
-bool GamepadSeqLock::ReadRetry(base::subtle::Atomic32 version) {
-  // If the sequence number was updated then a read should be re-attempted.
-  // -- Load fence, read membarrier
-  return base::subtle::Release_Load(&sequence_) != version;
+void GamepadSeqLockBase::Write(const Atomic32* 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
+  // Copy in the entry.
+  for (size_t i = 0; i < size_; ++i)
+    NoBarrier_Store(&ent->data_[i], obj[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);
 }
 
-void GamepadSeqLock::WriteBegin() {
-  // Increment the sequence number to odd to indicate the beginning of a write
-  // update.
-  base::subtle::Barrier_AtomicIncrement(&sequence_, 1);
-  // -- Store fence, write membarrier
-}
-
-void GamepadSeqLock::WriteEnd() {
-  // Increment the sequence to an even number to indicate the completion of
-  // a write update.
-  // -- Store fence, write membarrier
-  base::subtle::Barrier_AtomicIncrement(&sequence_, 1);
-}
-
-} // namespace content
+}  // namespace internal
+}  // namespace content