Renderer reading side of gamepad

The is the glue code that reads from the shared memory buffer on the renderer
side. The writer is a background thread the browser. The data here is returned
back up into WebKit code via the Chromium port.

The writer on the browser side was in this patch:
http://codereview.chromium.org/8568029/

And the rest of the related gamepad changes are here:
http://codereview.chromium.org/8345027/

BUG=79050


Review URL: http://codereview.chromium.org/8689011

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

4 files changed, 196 insertions, 16 deletions

diff --git a/content/common/gamepad_hardware_buffer.h b/content/common/gamepad_hardware_buffer.h
index d984522..c673d06a 100644
--- a/content/common/gamepad_hardware_buffer.h
+++ b/content/common/gamepad_hardware_buffer.h
@@ -5,10 +5,10 @@
 #ifndef CONTENT_COMMON_GAMEPAD_HARDWARE_BUFFER_H_
 #define CONTENT_COMMON_GAMEPAD_HARDWARE_BUFFER_H_
 
-#include "base/atomicops.h"
+#include "content/common/gamepad_seqlock.h"
 #include "third_party/WebKit/Source/WebKit/chromium/public/WebGamepads.h"
 
-namespace gamepad {
+namespace content {
 
 /*
 
@@ -19,25 +19,13 @@ we want low latency (so would like to avoid explicit communication via IPC
 between producer and consumer) and relatively large data size.
 
 Writer and reader operate on the same buffer assuming contention is low, and
-start_marker and end_marker are used to detect inconsistent reads.
-
-The writer atomically increments the start_marker counter before starting,
-then fills in the gamepad data, then increments end_marker to the same value
-as start_marker. The readers first reads end_marker, then the the data and
-then start_marker, and if the reader finds that the start and end markers were
-different, then it must retry as the buffer was updated while being read.
-
-There is a requirement for memory barriers between the accesses to the markers
-and the main data to ensure that both the reader and write see a consistent
-view of those values. In the current implementation, the writer uses an
-Barrier_AtomicIncrement for the counter, and the reader uses an Acquire_Load.
+contention is detected by using the associated SeqLock.
 
 */
 
 struct GamepadHardwareBuffer {
-  base::subtle::Atomic32 start_marker;
+  GamepadSeqLock sequence;
   WebKit::WebGamepads buffer;
-  base::subtle::Atomic32 end_marker;
 };
 
 }
diff --git a/content/common/gamepad_seqlock.cc b/content/common/gamepad_seqlock.cc
new file mode 100644
index 0000000..7f7e14f
--- /dev/null
+++ b/content/common/gamepad_seqlock.cc
@@ -0,0 +1,49 @@
+// 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 {
+
+GamepadSeqLock::GamepadSeqLock()
+  : sequence_(0) {
+}
+
+base::subtle::Atomic32 GamepadSeqLock::ReadBegin() {
+  base::subtle::Atomic32 version;
+  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();
+  }
+  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 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
diff --git a/content/common/gamepad_seqlock.h b/content/common/gamepad_seqlock.h
new file mode 100644
index 0000000..811aeca
--- /dev/null
+++ b/content/common/gamepad_seqlock.h
@@ -0,0 +1,45 @@
+// 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.
+
+#ifndef CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
+#define CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
+
+#include "base/atomicops.h"
+#include "base/threading/platform_thread.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:
+//   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 GamepadSeqLock {
+ public:
+  GamepadSeqLock();
+  base::subtle::Atomic32 ReadBegin();
+  bool ReadRetry(base::subtle::Atomic32 version);
+  void WriteBegin();
+  void WriteEnd();
+
+ private:
+  base::subtle::Atomic32 sequence_;
+  DISALLOW_COPY_AND_ASSIGN(GamepadSeqLock);
+};
+
+}  // namespace content
+
+#endif  // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
diff --git a/content/common/gamepad_seqlock_unittest.cc b/content/common/gamepad_seqlock_unittest.cc
new file mode 100644
index 0000000..777d804
--- /dev/null
+++ b/content/common/gamepad_seqlock_unittest.cc
@@ -0,0 +1,98 @@
+// 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"
+
+#include <stdlib.h>
+
+#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 {
+
+// Basic test to make sure that basic operation works correctly.
+
+struct TestData {
+  unsigned a, b, c;
+};
+
+class BasicSeqLockTestThread : public PlatformThread::Delegate {
+ public:
+  BasicSeqLockTestThread() {}
+
+  void Init(
+      content::GamepadSeqLock* seqlock,
+      TestData* data,
+      base::subtle::Atomic32* ready) {
+    seqlock_ = seqlock;
+    data_ = data;
+    ready_ = ready;
+  }
+  virtual void ThreadMain() {
+    while (AtomicRefCountIsZero(ready_)) {
+      PlatformThread::YieldCurrentThread();
+    }
+
+    for (unsigned i = 0; i < 10000; ++i) {
+      TestData 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);
+    }
+
+    AtomicRefCountDec(ready_);
+  }
+
+ private:
+  content::GamepadSeqLock* seqlock_;
+  TestData* data_;
+  base::AtomicRefCount* ready_;
+
+  DISALLOW_COPY_AND_ASSIGN(BasicSeqLockTestThread);
+};
+
+TEST(GamepadSeqLockTest, ManyThreads) {
+  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 = 100;
+  BasicSeqLockTestThread threads[kNumReaderThreads];
+  PlatformThreadHandle handles[kNumReaderThreads];
+
+  for (unsigned i = 0; i < kNumReaderThreads; ++i)
+    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.WriteEnd();
+
+    if (counter == 1)
+      base::AtomicRefCountIncN(&ready, kNumReaderThreads);
+
+    if (AtomicRefCountIsZero(&ready))
+      break;
+  }
+
+  for (unsigned i = 0; i < kNumReaderThreads; ++i)
+    PlatformThread::Join(handles[i]);
+}
+
+}  // namespace base