blob: 1490923a2f4a1196d02cec3fb212d49f58c1de25 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
|
// Copyright 2017 the V8 project 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 V8_HEAP_CONCURRENT_MARKING_DEQUE_
#define V8_HEAP_CONCURRENT_MARKING_DEQUE_
#include <deque>
#include "src/base/platform/mutex.h"
namespace v8 {
namespace internal {
class Heap;
class Isolate;
class HeapObject;
enum class MarkingThread { kMain, kConcurrent };
enum class TargetDeque { kShared, kBailout };
// The concurrent marking deque supports deque operations for two threads:
// main and concurrent. It is implemented using two deques: shared and bailout.
//
// The concurrent thread can use the push and pop operations with the
// MarkingThread::kConcurrent argument. All other operations are intended
// to be used by the main thread only.
//
// The interface of the concurrent marking deque for the main thread matches
// that of the sequential marking deque, so they can be easily switched
// at compile time without updating the main thread call-sites.
//
// The shared deque is shared between the main thread and the concurrent
// thread, so both threads can push to and pop from the shared deque.
// The bailout deque stores objects that cannot be processed by the concurrent
// thread. Only the concurrent thread can push to it and only the main thread
// can pop from it.
class ConcurrentMarkingDeque {
public:
// The heap parameter is needed to match the interface
// of the sequential marking deque.
explicit ConcurrentMarkingDeque(Heap* heap) {}
// Pushes the object into the specified deque assuming that the function is
// called on the specified thread. The main thread can push only to the shared
// deque. The concurrent thread can push to both deques.
bool Push(HeapObject* object, MarkingThread thread = MarkingThread::kMain,
TargetDeque target = TargetDeque::kShared) {
switch (target) {
case TargetDeque::kShared:
shared_deque_.Push(object);
break;
case TargetDeque::kBailout:
bailout_deque_.Push(object);
break;
}
return true;
}
// Pops an object from the bailout or shared deque assuming that the function
// is called on the specified thread. The main thread first tries to pop the
// bailout deque. If the deque is empty then it tries the shared deque.
// If the shared deque is also empty, then the function returns nullptr.
// The concurrent thread pops only from the shared deque.
HeapObject* Pop(MarkingThread thread = MarkingThread::kMain) {
if (thread == MarkingThread::kMain) {
HeapObject* result = bailout_deque_.Pop();
if (result != nullptr) return result;
}
return shared_deque_.Pop();
}
// All the following operations can used only by the main thread.
void Clear() {
bailout_deque_.Clear();
shared_deque_.Clear();
}
bool IsFull() { return false; }
bool IsEmpty() { return bailout_deque_.IsEmpty() && shared_deque_.IsEmpty(); }
int Size() { return bailout_deque_.Size() + shared_deque_.Size(); }
// This is used for a large array with a progress bar.
// For simpicity, unshift to the bailout deque so that the concurrent thread
// does not see such objects.
bool Unshift(HeapObject* object) {
bailout_deque_.Unshift(object);
return true;
}
// Calls the specified callback on each element of the deques and replaces
// the element with the result of the callback. If the callback returns
// nullptr then the element is removed from the deque.
// The callback must accept HeapObject* and return HeapObject*.
template <typename Callback>
void Update(Callback callback) {
bailout_deque_.Update(callback);
shared_deque_.Update(callback);
}
// These empty functions are needed to match the interface
// of the sequential marking deque.
void SetUp() {}
void TearDown() {}
void StartUsing() {}
void StopUsing() {}
void ClearOverflowed() {}
void SetOverflowed() {}
bool overflowed() const { return false; }
private:
// Simple, slow, and thread-safe deque that forwards all operations to
// a lock-protected std::deque.
class Deque {
public:
Deque() { cache_padding_[0] = 0; }
void Clear() {
base::LockGuard<base::Mutex> guard(&mutex_);
return deque_.clear();
}
bool IsEmpty() {
base::LockGuard<base::Mutex> guard(&mutex_);
return deque_.empty();
}
int Size() {
base::LockGuard<base::Mutex> guard(&mutex_);
return static_cast<int>(deque_.size());
}
void Push(HeapObject* object) {
base::LockGuard<base::Mutex> guard(&mutex_);
deque_.push_back(object);
}
HeapObject* Pop() {
base::LockGuard<base::Mutex> guard(&mutex_);
if (deque_.empty()) return nullptr;
HeapObject* result = deque_.back();
deque_.pop_back();
return result;
}
void Unshift(HeapObject* object) {
base::LockGuard<base::Mutex> guard(&mutex_);
deque_.push_front(object);
}
template <typename Callback>
void Update(Callback callback) {
base::LockGuard<base::Mutex> guard(&mutex_);
std::deque<HeapObject*> new_deque;
for (auto object : deque_) {
HeapObject* new_object = callback(object);
if (new_object) {
new_deque.push_back(new_object);
}
}
deque_.swap(new_deque);
}
private:
base::Mutex mutex_;
std::deque<HeapObject*> deque_;
// Ensure that two deques do not share the same cache line.
static int const kCachePadding = 64;
char cache_padding_[kCachePadding];
};
Deque bailout_deque_;
Deque shared_deque_;
DISALLOW_COPY_AND_ASSIGN(ConcurrentMarkingDeque);
};
} // namespace internal
} // namespace v8
#endif // V8_CONCURRENT_MARKING_DEQUE_
|
