OLD | NEW |
---|---|
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(¤t_); | |
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(¤t_, 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_ |
OLD | NEW |