Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(369)

Side by Side Diff: content/common/gamepad_seqlock.h

Issue 8772004: Improve GamepadSeqLock impl Base URL: http://src.chromium.org/svn/trunk/src/
Patch Set: '' Created 9 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
OLDNEW
1 // Copyright (c) 2011 The Chromium Authors. All rights reserved. 1 // Copyright (c) 2011 The Chromium Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style license that can be 2 // Use of this source code is governed by a BSD-style license that can be
3 // found in the LICENSE file. 3 // found in the LICENSE file.
4 4
5 #ifndef CONTENT_COMMON_GAMEPAD_SEQLOCK_H_ 5 #ifndef CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
6 #define CONTENT_COMMON_GAMEPAD_SEQLOCK_H_ 6 #define CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
7 7
8 #include "base/atomicops.h" 8 #include "base/atomicops.h"
9 #include "base/threading/platform_thread.h"
10 #include "content/common/content_export.h" 9 #include "content/common/content_export.h"
11 10
12 namespace content { 11 namespace content {
13 12
14 // This SeqLock handles only *one* writer and multiple readers. It may be 13 // This SeqLock handles only *one* writer and multiple readers. It may be
15 // suitable for low-contention with relatively infrequent writes, and many 14 // suitable for high read frequency scenarios and is especially useful in shared
16 // readers. See: 15 // memory environment. See for the basic idea:
17 // http://en.wikipedia.org/wiki/Seqlock 16 // http://en.wikipedia.org/wiki/Seqlock
18 // http://www.concurrencykit.org/doc/ck_sequence.html 17 // However, this implementation is an improved lock-free variant.
19 // This implementation is based on ck_sequence.h from http://concurrencykit.org. 18 // The SeqLock can hold only POD fully-embed data (no pointers
20 // 19 // to satellite data), copies are done with memcpy.
21 // Currently, this is used in only one location. It may make sense to 20 template<typename T>
22 // generalize with a higher-level construct that owns both the lock and the
23 // data buffer, if it is to be used more widely.
24 //
25 // You must be very careful not to operate on potentially inconsistent read
26 // buffers. If the read must be retry'd, the data in the read buffer could
27 // contain any random garbage. e.g., contained pointers might be
28 // garbage, or indices could be out of range. Probably the only suitable thing
29 // to do during the read loop is to make a copy of the data, and operate on it
30 // only after the read was found to be consistent.
31 class CONTENT_EXPORT GamepadSeqLock { 21 class CONTENT_EXPORT GamepadSeqLock {
darin (slow to review) 2011/12/01 17:45:16 nit: since this is all implemented inline, there i
dvyukov 2011/12/01 21:27:28 Will do.
32 public: 22 public:
33 GamepadSeqLock(); 23 GamepadSeqLock();
34 base::subtle::Atomic32 ReadBegin(); 24 void ReadTo(T* obj);
35 bool ReadRetry(base::subtle::Atomic32 version); 25 void Write(T const* obj);
36 void WriteBegin();
37 void WriteEnd();
38 26
39 private: 27 private:
40 base::subtle::Atomic32 sequence_; 28 typedef base::subtle::Atomic32 Atomic32;
29 static size_t const kSize = sizeof(T) / sizeof(Atomic32) + 1;
30 static size_t const kEntries = 2;
31 struct Entry {
32 Atomic32 sequence_;
33 Atomic32 data_[kSize];
34 };
35 Atomic32 current_;
36 Entry entries_[kEntries];
41 DISALLOW_COPY_AND_ASSIGN(GamepadSeqLock); 37 DISALLOW_COPY_AND_ASSIGN(GamepadSeqLock);
42 }; 38 };
43 39
40 template<typename T>
41 GamepadSeqLock<T>::GamepadSeqLock()
42 : current_(0) {
43 memset(entries_, 0, sizeof(entries_));
44 }
45
46 template<typename T>
47 void GamepadSeqLock<T>::ReadTo(T* obj) {
48 using base::subtle::NoBarrier_Load;
49 using base::subtle::Acquire_Load;
50 using base::subtle::MemoryBarrier;
51 for (;;) {
scottmg 2011/12/01 22:36:39 Could you explain (perhaps in a comment here) why
52 Atomic32 cur = Acquire_Load(&current_);
53 Entry* ent = &entries_[cur % 2];
jbates 2011/12/01 19:31:12 I'm not sure this additional complexity is necessa
dvyukov 2011/12/01 21:27:28 Well, the current algo already has quite substanti
scottmg 2011/12/01 22:36:39 2 should be kEntries? (and below)
54 Atomic32 seq = Acquire_Load(&ent->sequence_); // membar #LoadLoad
55 // If the counter is even, then the entry is not already current -> retry.
56 if (seq % 2)
57 continue;
jbates 2011/12/01 19:31:12 Without some kind of yield or sleep, this can caus
dvyukov 2011/12/01 21:27:28 This algorithm does not require yield, it is compl
jbates 2011/12/02 21:40:14 After rereading the code 10 times or so :), I thin
58 // Copy out the entry.
59 Atomic32 tmp[kSize];
60 for (size_t i = 0; i < kSize; ++i)
scottmg 2011/12/01 22:36:39 This seems very subtle. Could you explain (again i
61 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
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
62 MemoryBarrier(); // membar #LoadLoad
63 Atomic32 seq2 = NoBarrier_Load(&ent->sequence_);
64 // If the counter is changed, then we've read inconsistend data -> retry.
scottmg 2011/12/01 22:36:39 nit: 'inconsistent'
65 if (seq2 != seq)
66 continue;
jbates 2011/12/01 19:31:12 Less likely to cause problems assuming the writer
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 t
67 // Kickback to strict-aliasing.
68 memcpy(reinterpret_cast<char*>(obj), tmp, sizeof(*obj));
69 break;
70 }
71 }
72
73 template<typename T>
74 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.
75 using base::subtle::NoBarrier_Store;
76 using base::subtle::Release_Store;
77 using base::subtle::MemoryBarrier;
78 Atomic32 tmp[kSize];
79 // Kickback to strict-aliasing.
80 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 re
81 // Get the non current entry...
82 Entry* ent = &entries_[(current_ + 1) % 2];
83 // ... and mark it as inconsistent.
84 NoBarrier_Store(&ent->sequence_, ent->sequence_ + 1);
jbates 2011/12/01 19:31:12 If the writer thread calls Write multiple times wh
dvyukov 2011/12/01 21:27:28 Yes.
85 MemoryBarrier(); // membar #StoreStore
86 // Copy in the entry.
87 for (size_t i = 0; i < kSize; ++i)
88 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
dvyukov 2011/12/01 21:27:28 It leads to undefined behavior, complicates manual
89 // Mark the entry as consistent again.
90 Release_Store(&ent->sequence_, ent->sequence_ + 1); // membar #StoreStore
91 // Switch the current entry.
92 Release_Store(&current_, current_ + 1);
93 }
94
44 } // namespace content 95 } // namespace content
45 96
46 #endif // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_ 97 #endif // CONTENT_COMMON_GAMEPAD_SEQLOCK_H_
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698