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 #include "content/common/gamepad_seqlock.h" | 5 #include "content/common/gamepad_seqlock.h" |
6 | 6 |
7 namespace content { | 7 namespace content { |
8 namespace internal { | |
8 | 9 |
9 GamepadSeqLock::GamepadSeqLock() | 10 GamepadSeqLockBase::GamepadSeqLockBase(Entry* entries, size_t size) |
10 : sequence_(0) { | 11 : size_(size) |
12 , current_(0) { | |
13 const size_t entSize = sizeof(Entry) + sizeof(Atomic32) * size; | |
14 memset(entries, 0, kEntries * entSize); | |
15 for (size_t i = 0; i < kEntries; ++i) | |
16 entries_[i] = (Entry*)((char*)entries + i * entSize); | |
jbates
2012/02/17 23:29:52
guidelines prohibit c-style casts I think.
dvyukov
2012/02/21 15:18:04
Done.
| |
11 } | 17 } |
12 | 18 |
13 base::subtle::Atomic32 GamepadSeqLock::ReadBegin() { | 19 // The algorithm works as follows. |
14 base::subtle::Atomic32 version; | 20 // The SeqLock contains 2 user objects - a current and a non-current. |
21 // The object roles can be swapped by incrementing the current_ variable. | |
22 // Initially both objects are consistent, that is, their sequence_%2 == 0. | |
23 // A writer proceeds as follows. First, it marks the non-current object | |
24 // as inconsistent by incrementing it's sequence_ (the sequence_ becomes odd). | |
25 // Then it mutates the object. Then marks it as consistent by incrementing | |
26 // it's sequence_ once again (the sequence_ is even now). And finally swaps | |
27 // the object roles, that is, the object becomes current. | |
28 // Such disipline establishes an important property - the current object | |
29 // is always consistent and contains the most recent data. | |
30 // Readers proceed as follows. First, determine what is the current object, | |
31 // remember it's seqence, check that the sequence is even | |
32 // (the object is consistent), copy out the object, verify that | |
33 // the sequence is not changed. If any of the checks fail, a reader works | |
34 // with a non-current object (current object is always consistent), so it | |
35 // just retries from the beginning. Thus readers are completely lock-free, | |
36 // that is, a reader retries iff a writer has accomplished a write operation | |
37 // during reading (only constant sequence of writes can stall readers, | |
38 // a stalled writer can't block readers). | |
39 | |
40 void GamepadSeqLockBase::ReadTo(Atomic32* obj) { | |
41 using base::subtle::NoBarrier_Load; | |
42 using base::subtle::Acquire_Load; | |
43 using base::subtle::MemoryBarrier; | |
15 for (;;) { | 44 for (;;) { |
16 version = base::subtle::NoBarrier_Load(&sequence_); | 45 // Determine the current object. |
17 | 46 Atomic32 cur = Acquire_Load(¤t_); |
18 // If the counter is even, then the associated data might be in a | 47 Entry* ent = entries_[cur % kEntries]; |
19 // consistent state, so we can try to read. | 48 Atomic32 seq = Acquire_Load(&ent->sequence_); // membar #LoadLoad |
20 if ((version & 1) == 0) | 49 // If the counter is even, then the object is not already current, |
21 break; | 50 // no need to yield, just retry (the current object is consistent). |
22 | 51 if (seq % 2) |
23 // Otherwise, the writer is in the middle of an update. Retry the read. | 52 continue; |
24 base::PlatformThread::YieldCurrentThread(); | 53 // Copy out the entry. |
54 for (size_t i = 0; i < size_; ++i) | |
55 obj[i] = NoBarrier_Load(&ent->data_[i]); | |
56 MemoryBarrier(); // membar #LoadLoad | |
57 Atomic32 seq2 = NoBarrier_Load(&ent->sequence_); | |
58 // If the counter is changed, then we've read inconsistent data, | |
59 // no need to yield, just retry (the current object is consistent). | |
60 if (seq2 != seq) | |
61 continue; | |
62 break; | |
25 } | 63 } |
26 return version; | |
27 } | 64 } |
28 | 65 |
29 bool GamepadSeqLock::ReadRetry(base::subtle::Atomic32 version) { | 66 void GamepadSeqLockBase::Write(const Atomic32* obj) { |
30 // If the sequence number was updated then a read should be re-attempted. | 67 using base::subtle::NoBarrier_Store; |
31 // -- Load fence, read membarrier | 68 using base::subtle::Release_Store; |
32 return base::subtle::Release_Load(&sequence_) != version; | 69 using base::subtle::MemoryBarrier; |
70 // Get the non current object... | |
71 Entry* ent = entries_[(current_ + 1) % kEntries]; | |
72 // ... and mark it as inconsistent. | |
73 NoBarrier_Store(&ent->sequence_, ent->sequence_ + 1); | |
74 MemoryBarrier(); // membar #StoreStore | |
75 // Copy in the entry. | |
76 for (size_t i = 0; i < size_; ++i) | |
77 NoBarrier_Store(&ent->data_[i], obj[i]); | |
78 // Mark the object as consistent again. | |
79 Release_Store(&ent->sequence_, ent->sequence_ + 1); // membar #StoreStore | |
80 // Switch the current object. | |
81 Release_Store(¤t_, current_ + 1); | |
33 } | 82 } |
34 | 83 |
35 void GamepadSeqLock::WriteBegin() { | 84 } // namespace internal |
36 // Increment the sequence number to odd to indicate the beginning of a write | 85 } // namespace content |
37 // update. | |
38 base::subtle::Barrier_AtomicIncrement(&sequence_, 1); | |
39 // -- Store fence, write membarrier | |
40 } | |
41 | |
42 void GamepadSeqLock::WriteEnd() { | |
43 // Increment the sequence to an even number to indicate the completion of | |
44 // a write update. | |
45 // -- Store fence, write membarrier | |
46 base::subtle::Barrier_AtomicIncrement(&sequence_, 1); | |
47 } | |
48 | |
49 } // namespace content | |
OLD | NEW |