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,92 @@
 #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.
+// 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 CONTENT_EXPORT GamepadSeqLock {

[darin (slow to review), 2011/12/01 17:45:16]

nit: since this is all implemented inline, there is nothing to export.  remove
CONTENT_EXPORT.

[dvyukov, 2011/12/01 21:27:28]

Will do.

  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;
+  static size_t const kSize = sizeof(T) / sizeof(Atomic32) + 1;
+  static size_t const kEntries = 2;
+  struct Entry {
+    Atomic32 sequence_;
+    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_));
+}
+
+template<typename T>
+void GamepadSeqLock<T>::ReadTo(T* obj) {
+  using base::subtle::NoBarrier_Load;
+  using base::subtle::Acquire_Load;
+  using base::subtle::MemoryBarrier;
+  for (;;) {

[scottmg, 2011/12/01 22:36:39]

Could you explain (perhaps in a comment here) why this loop is lock-free &
cannot cause live-lock?

+    Atomic32 cur = Acquire_Load(&current_);
+    Entry* ent = &entries_[cur % 2];

[jbates, 2011/12/01 19:31:12]

I'm not sure this additional complexity is necessary now that we have a
templated class with T. Why not just internalize the loop from Scott's original
seqlock code and keep the ANNOTATE_BENIGN_RACE_SIZED here? Then there's no
chance of the end user getting an inconsistent copy of obj because this loop
doesn't return until it gets a good version. This would also keep the lock free
code much simpler (which is helpful to avoid unpredictable and rare bugs).

[dvyukov, 2011/12/01 21:27:28]

Well, the current algo already has quite substantial complexity, so I do not see
significant difference... and in the end nobody proved that it is correct. This
algo just has better properties.
Annotations must not be used in application code.

[scottmg, 2011/12/01 22:36:39]

2 should be kEntries? (and below)

+    Atomic32 seq = Acquire_Load(&ent->sequence_);  // membar #LoadLoad
+    // If the counter is even, then the entry is not already current -> retry.
+    if (seq % 2)
+      continue;

[jbates, 2011/12/01 19:31:12]

Without some kind of yield or sleep, this can cause livelock via starvation on
certain OSes. Even a yield is not enough for some OSes when thread priorities
vary.

[dvyukov, 2011/12/01 21:27:28]

This algorithm does not require yield, it is completely lock-free for readers,
as opposed to the current algo which contains a spin-mutex.

[jbates, 2011/12/02 21:40:14]

After rereading the code 10 times or so :), I think I understand that this can't
spin unless the writer thread is spamming Writes. If that's the case, it would
be helpful to explain in the comments.

+    // Copy out the entry.
+    Atomic32 tmp[kSize];
+    for (size_t i = 0; i < kSize; ++i)

[scottmg, 2011/12/01 22:36:39]

This seems very subtle. Could you explain (again in a comment perhaps) why it is
required that the data are stored as an array of Atomic32s? Is it alright for
the buffer to contain qwords? bytes? unaligned data?

+      tmp[i] = NoBarrier_Load(&ent->data_[i]);

[jbates, 2011/12/01 19:31:12]

Why not store a volatile T in ent, and change this loop to:
*obj = ent->data;

NoBarrier_Load is just a volatile load on all of our platforms.
MemoryBarriers already guarantee ordering.

[dvyukov, 2011/12/01 21:27:28]

Because it leads to undefined behavior.

[jbates, 2011/12/02 21:40:14]

I'd be interested in learning how you came to that conclusion. Based on the
implementation of NoBarrier_Load/Store, the behavior is identical (just volatile
loads and stores). I agree the T::operator= could be bad though because we don't
want user code executing here, so allow me to suggest a memcpy instead.

+    MemoryBarrier();  // membar #LoadLoad
+    Atomic32 seq2 = NoBarrier_Load(&ent->sequence_);
+    // If the counter is changed, then we've read inconsistend data -> retry.

[scottmg, 2011/12/01 22:36:39]

nit: 'inconsistent'

+    if (seq2 != seq)
+      continue;

[jbates, 2011/12/01 19:31:12]

Less likely to cause problems assuming the writer is not updating frequently,
but still safer to yield here as well.

[dvyukov, 2011/12/01 21:27:28]

yield is not required here.

[jbates, 2011/12/02 21:40:14]

Is that because it can only happen once per call to Write? Again, would be
helpful to see that in the comments.

+    // Kickback to strict-aliasing.
+    memcpy(reinterpret_cast<char*>(obj), tmp, sizeof(*obj));
+    break;
+  }
+}
+
+template<typename T>
+void GamepadSeqLock<T>::Write(T const* obj) {

[jbates, 2011/12/01 19:31:12]

nit: consider changing this to const T&?

[dvyukov, 2011/12/01 21:27:28]

Will do.

+  using base::subtle::NoBarrier_Store;
+  using base::subtle::Release_Store;
+  using base::subtle::MemoryBarrier;
+  Atomic32 tmp[kSize];
+  // Kickback to strict-aliasing.
+  memcpy(tmp, reinterpret_cast<char const*>(obj), sizeof(*obj));

[jbates, 2011/12/01 19:31:12]

Why the extra memcpy?

[dvyukov, 2011/12/01 21:27:28]

I don't know how to implement w/o it.

[jbates, 2011/12/02 21:40:14]

It appears this is to prevent the compiler from reordering the NoBarrier_Stores
(line 88) with the user's stores to obj (before calling Write) (based on strict
aliasing rules, which btw we don't compile with but that's another issue). The
MemoryBarrier() below (line 85) should be enough to order those, no? I thought
GCC does not reorder around assembly ops such as that.

+  // Get the non current entry...
+  Entry* ent = &entries_[(current_ + 1) % 2];
+  // ... and mark it as inconsistent.
+  NoBarrier_Store(&ent->sequence_, ent->sequence_ + 1);

[jbates, 2011/12/01 19:31:12]

If the writer thread calls Write multiple times while the reader thread is
reading, is there still a race on ent->data_? It should be rare enough that it
doesn't matter with the gamepad use case.

[dvyukov, 2011/12/01 21:27:28]

Yes.

+  MemoryBarrier();  // membar #StoreStore
+  // Copy in the entry.
+  for (size_t i = 0; i < kSize; ++i)
+    NoBarrier_Store(&ent->data_[i], tmp[i]);

[jbates, 2011/12/01 19:31:12]

Why not store a volatile T in ent, and change this loop to:
ent->obj_ = obj;

NoBarrier_Store is also just a volatile store on all of our platforms, and the
MemoryBarriers already guarantee ordering.

[dvyukov, 2011/12/01 21:27:28]

It leads to undefined behavior, complicates manual verification, leads to poorly
documented code, confuses tools and does not allow them to do proper
verification.

+  // Mark the entry as consistent again.
+  Release_Store(&ent->sequence_, ent->sequence_ + 1);  // membar #StoreStore
+  // Switch the current entry.
+  Release_Store(&current_, current_ + 1);
+}
+
 }  // namespace content
 
 #endif  // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_