Revert 143903 - Lock-free GamepadSeqLock

The change
 - provides an improved lock-free SeqLock implementation which eliminates any potential blocking of readers.
 - provides a higher-level and simpler API as was suggested by Darin.
 - ThreadSanitizer report suppressions are replaced with correct synchronization. 
 - eliminates nasty kMaximumContentionCount and associated histogram.

Review URL: https://chromiumcodereview.appspot.com/8772004

TBR=dvyukov@chromium.org
Review URL: https://chromiumcodereview.appspot.com/10656020

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@143914 0039d316-1c4b-4281-b951-d872f2087c98

4 files changed, 81 insertions, 148 deletions

diff --git a/content/common/gamepad_hardware_buffer.h b/content/common/gamepad_hardware_buffer.h
index 7f4bad9..077c782 100644
--- a/content/common/gamepad_hardware_buffer.h
+++ b/content/common/gamepad_hardware_buffer.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -24,13 +24,10 @@ contention is detected by using the associated SeqLock.
 */
 
 struct GamepadHardwareBuffer {
-  GamepadSeqLock<WebKit::WebGamepads> gamepads;
-  GamepadHardwareBuffer();
+  GamepadSeqLock sequence;
+  WebKit::WebGamepads buffer;
 };
 
-inline GamepadHardwareBuffer::GamepadHardwareBuffer() {
-}
-
 }
 
 #endif // CONTENT_COMMON_GAMEPAD_HARDWARE_BUFFER_H_
diff --git a/content/common/gamepad_seqlock.cc b/content/common/gamepad_seqlock.cc
index c399d36..7f7e14f 100644
--- a/content/common/gamepad_seqlock.cc
+++ b/content/common/gamepad_seqlock.cc
@@ -1,87 +1,49 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "content/common/gamepad_seqlock.h"
 
 namespace content {
-namespace internal {
 
-GamepadSeqLockBase::GamepadSeqLockBase(BaseEntry* entries, size_t size)
-    : size_(size)
-    , current_(0) {
-  const size_t ent_size = sizeof(BaseEntry) + sizeof(Atomic32) * (size + 1);
-  memset(entries, 0, kEntries * ent_size);
-  for (size_t i = 0; i < kEntries; ++i) {
-    entries_[i] = reinterpret_cast<BaseEntry*>
-        (reinterpret_cast<char*>(entries) + i * ent_size);
-  }
+GamepadSeqLock::GamepadSeqLock()
+  : sequence_(0) {
 }
 
-// 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;
+base::subtle::Atomic32 GamepadSeqLock::ReadBegin() {
+  base::subtle::Atomic32 version;
   for (;;) {
-    // Determine the current object.
-    Atomic32 cur = Acquire_Load(&current_);
-    BaseEntry* 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;
+    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();
   }
+  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 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 GamepadSeqLockBase::Write(const Atomic32* obj) {
-  using base::subtle::NoBarrier_Store;
-  using base::subtle::Release_Store;
-  using base::subtle::MemoryBarrier;
-  // Get the non current object...
-  BaseEntry* 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::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 internal
-}  // namespace content
+} // namespace content
diff --git a/content/common/gamepad_seqlock.h b/content/common/gamepad_seqlock.h
index 66f955d..35f51e5 100644
--- a/content/common/gamepad_seqlock.h
+++ b/content/common/gamepad_seqlock.h
@@ -1,4 +1,4 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -6,76 +6,38 @@
 #define CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
 
 #include "base/atomicops.h"
-#include "base/basictypes.h"
+#include "base/threading/platform_thread.h"
 #include "content/common/content_export.h"
 
 namespace content {
 
-namespace internal {
-
-class CONTENT_EXPORT GamepadSeqLockBase {
- protected:
-  static const size_t kEntries = 2;
-  typedef base::subtle::Atomic32 Atomic32;
-  struct BaseEntry {
-    Atomic32 sequence_;
-    // Both writer and readers work with the array concurrently,
-    // so it must be accessed with atomic operations.
-    Atomic32 data_[1];
-  };
-
-  GamepadSeqLockBase(BaseEntry* entries, size_t size);
-  void ReadTo(Atomic32* obj);
-  void Write(const Atomic32* obj);
-
- private:
-  const size_t size_;
-  Atomic32 current_;
-  BaseEntry* entries_[kEntries];
-};
-
-}  // namespace internal
-
 // This SeqLock handles only *one* writer and multiple readers. It may be
-// suitable for high read frequency scenarios and is especially useful in shared
-// memory environment. See for the basic idea:
+// suitable for low-contention with relatively infrequent writes, and many
+// readers. See:
 //   http://en.wikipedia.org/wiki/Seqlock
-// 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 internal::GamepadSeqLockBase {
+//   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 {
  public:
-  GamepadSeqLock()
-      : internal::GamepadSeqLockBase(entries_, kSize) {
-  }
-
-  // May be called concurrently with ReadTo and Write.
-  // - If ReadTo occurs in the middle of Write (on another thread),
-  //   ReadTo gets the old data (not the new data being written
-  //   by the other thread).
-  // - ReadTo never spins unless the writer thread is calling Write
-  //   multiple times before ReadTo completes.
-  void ReadTo(T* obj) {
-    // Breaks strict-aliasing rules.
-    Base::ReadTo(reinterpret_cast<Atomic32*>(obj));
-  }
+  GamepadSeqLock();
+  base::subtle::Atomic32 ReadBegin();
+  bool ReadRetry(base::subtle::Atomic32 version);
+  void WriteBegin();
+  void WriteEnd();
 
-  // Must be called by a single thread at a time.  May be called concurrently
-  // with ReadTo.
-  void Write(const T& obj) {
-    // Breaks strict-aliasing rules.
-    Base::Write(reinterpret_cast<const Atomic32*>(&obj));
-  }
-
-private:
-  typedef internal::GamepadSeqLockBase Base;
-  COMPILE_ASSERT(sizeof(T) % sizeof(Atomic32) == 0, bad_object_size);
-  static size_t const kSize = sizeof(T) / sizeof(Atomic32);
-  struct Entry : Base::BaseEntry {
-    Atomic32 data_[kSize];
-  };
-  Entry entries_[kEntries];
+ private:
+  base::subtle::Atomic32 sequence_;
   DISALLOW_COPY_AND_ASSIGN(GamepadSeqLock);
 };
 
diff --git a/content/common/gamepad_seqlock_unittest.cc b/content/common/gamepad_seqlock_unittest.cc
index cfd3b74..7e5da3f 100644
--- a/content/common/gamepad_seqlock_unittest.cc
+++ b/content/common/gamepad_seqlock_unittest.cc
@@ -1,4 +1,4 @@
-// Copyright (c) 2012 The Chromium Authors. All rights reserved.
+// Copyright (c) 2011 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
@@ -8,6 +8,7 @@
 
 #include "base/atomic_ref_count.h"
 #include "base/threading/platform_thread.h"
+#include "base/third_party/dynamic_annotations/dynamic_annotations.h"
 #include "testing/gtest/include/gtest/gtest.h"
 
 namespace base {
@@ -23,9 +24,11 @@ class BasicSeqLockTestThread : public PlatformThread::Delegate {
   BasicSeqLockTestThread() {}
 
   void Init(
-      content::GamepadSeqLock<TestData>* seqlock,
+      content::GamepadSeqLock* seqlock,
+      TestData* data,
       base::subtle::Atomic32* ready) {
     seqlock_ = seqlock;
+    data_ = data;
     ready_ = ready;
   }
   virtual void ThreadMain() {
@@ -35,7 +38,12 @@ class BasicSeqLockTestThread : public PlatformThread::Delegate {
 
     for (unsigned i = 0; i < 1000; ++i) {
       TestData copy;
-      seqlock_->ReadTo(&copy);
+      base::subtle::Atomic32 version;
+      do {
+        version = seqlock_->ReadBegin();
+        copy = *data_;
+      } while (seqlock_->ReadRetry(version));
+
       EXPECT_EQ(copy.a + 100, copy.b);
       EXPECT_EQ(copy.c, copy.b + copy.a);
     }
@@ -44,33 +52,37 @@ class BasicSeqLockTestThread : public PlatformThread::Delegate {
   }
 
  private:
-  content::GamepadSeqLock<TestData>* seqlock_;
+  content::GamepadSeqLock* seqlock_;
+  TestData* data_;
   base::AtomicRefCount* ready_;
 
   DISALLOW_COPY_AND_ASSIGN(BasicSeqLockTestThread);
 };
 
 TEST(GamepadSeqLockTest, ManyThreads) {
-  content::GamepadSeqLock<TestData> seqlock;
+  content::GamepadSeqLock seqlock;
   TestData data = { 0, 0, 0 };
   base::AtomicRefCount ready = 0;
 
+  ANNOTATE_BENIGN_RACE_SIZED(&data, sizeof(data), "Racey reads are discarded");
+
   static const unsigned kNumReaderThreads = 10;
   BasicSeqLockTestThread threads[kNumReaderThreads];
   PlatformThreadHandle handles[kNumReaderThreads];
 
   for (unsigned i = 0; i < kNumReaderThreads; ++i)
-    threads[i].Init(&seqlock, &ready);
+    threads[i].Init(&seqlock, &data, &ready);
   for (unsigned i = 0; i < kNumReaderThreads; ++i)
     ASSERT_TRUE(PlatformThread::Create(0, &threads[i], &handles[i]));
 
   // The main thread is the writer, and the spawned are readers.
   unsigned counter = 0;
   for (;;) {
+    seqlock.WriteBegin();
     data.a = counter++;
     data.b = data.a + 100;
     data.c = data.b + data.a;
-    seqlock.Write(data);
+    seqlock.WriteEnd();
 
     if (counter == 1)
       base::AtomicRefCountIncN(&ready, kNumReaderThreads);