Line data Source code
1 : // Copyright 2017 the V8 project authors. All rights reserved.
2 : // Use of this source code is governed by a BSD-style license that can be
3 : // found in the LICENSE file.
4 :
5 : #include "src/heap/worklist.h"
6 :
7 : #include "test/unittests/test-utils.h"
8 :
9 : namespace v8 {
10 : namespace internal {
11 :
12 : class SomeObject {};
13 :
14 : using TestWorklist = Worklist<SomeObject*, 64>;
15 :
16 15443 : TEST(WorkListTest, SegmentCreate) {
17 : TestWorklist::Segment segment;
18 : EXPECT_TRUE(segment.IsEmpty());
19 2 : EXPECT_EQ(0u, segment.Size());
20 : EXPECT_FALSE(segment.IsFull());
21 1 : }
22 :
23 15443 : TEST(WorkListTest, SegmentPush) {
24 : TestWorklist::Segment segment;
25 2 : EXPECT_EQ(0u, segment.Size());
26 : EXPECT_TRUE(segment.Push(nullptr));
27 2 : EXPECT_EQ(1u, segment.Size());
28 1 : }
29 :
30 15443 : TEST(WorkListTest, SegmentPushPop) {
31 : TestWorklist::Segment segment;
32 : EXPECT_TRUE(segment.Push(nullptr));
33 2 : EXPECT_EQ(1u, segment.Size());
34 : SomeObject dummy;
35 : SomeObject* object = &dummy;
36 : EXPECT_TRUE(segment.Pop(&object));
37 2 : EXPECT_EQ(0u, segment.Size());
38 1 : EXPECT_EQ(nullptr, object);
39 1 : }
40 :
41 15443 : TEST(WorkListTest, SegmentIsEmpty) {
42 : TestWorklist::Segment segment;
43 : EXPECT_TRUE(segment.IsEmpty());
44 : EXPECT_TRUE(segment.Push(nullptr));
45 : EXPECT_FALSE(segment.IsEmpty());
46 1 : }
47 :
48 15443 : TEST(WorkListTest, SegmentIsFull) {
49 : TestWorklist::Segment segment;
50 : EXPECT_FALSE(segment.IsFull());
51 129 : for (size_t i = 0; i < TestWorklist::Segment::kCapacity; i++) {
52 64 : EXPECT_TRUE(segment.Push(nullptr));
53 : }
54 1 : EXPECT_TRUE(segment.IsFull());
55 1 : }
56 :
57 15443 : TEST(WorkListTest, SegmentClear) {
58 : TestWorklist::Segment segment;
59 : EXPECT_TRUE(segment.Push(nullptr));
60 : EXPECT_FALSE(segment.IsEmpty());
61 : segment.Clear();
62 : EXPECT_TRUE(segment.IsEmpty());
63 129 : for (size_t i = 0; i < TestWorklist::Segment::kCapacity; i++) {
64 64 : EXPECT_TRUE(segment.Push(nullptr));
65 : }
66 1 : }
67 :
68 15443 : TEST(WorkListTest, SegmentFullPushFails) {
69 : TestWorklist::Segment segment;
70 : EXPECT_FALSE(segment.IsFull());
71 129 : for (size_t i = 0; i < TestWorklist::Segment::kCapacity; i++) {
72 64 : EXPECT_TRUE(segment.Push(nullptr));
73 : }
74 1 : EXPECT_TRUE(segment.IsFull());
75 2 : EXPECT_FALSE(segment.Push(nullptr));
76 1 : }
77 :
78 15443 : TEST(WorkListTest, SegmentEmptyPopFails) {
79 : TestWorklist::Segment segment;
80 : EXPECT_TRUE(segment.IsEmpty());
81 : SomeObject* object;
82 : EXPECT_FALSE(segment.Pop(&object));
83 1 : }
84 :
85 15443 : TEST(WorkListTest, SegmentUpdateFalse) {
86 : TestWorklist::Segment segment;
87 : SomeObject* object;
88 : object = reinterpret_cast<SomeObject*>(&object);
89 : EXPECT_TRUE(segment.Push(object));
90 : segment.Update([](SomeObject* object, SomeObject** out) { return false; });
91 : EXPECT_TRUE(segment.IsEmpty());
92 1 : }
93 :
94 15443 : TEST(WorkListTest, SegmentUpdate) {
95 : TestWorklist::Segment segment;
96 : SomeObject* objectA;
97 1 : objectA = reinterpret_cast<SomeObject*>(&objectA);
98 : SomeObject* objectB;
99 1 : objectB = reinterpret_cast<SomeObject*>(&objectB);
100 : EXPECT_TRUE(segment.Push(objectA));
101 : segment.Update([objectB](SomeObject* object, SomeObject** out) {
102 1 : *out = objectB;
103 : return true;
104 : });
105 : SomeObject* object;
106 1 : EXPECT_TRUE(segment.Pop(&object));
107 1 : EXPECT_EQ(object, objectB);
108 1 : }
109 :
110 15443 : TEST(WorkListTest, CreateEmpty) {
111 1 : TestWorklist worklist;
112 : TestWorklist::View worklist_view(&worklist, 0);
113 1 : EXPECT_TRUE(worklist_view.IsLocalEmpty());
114 2 : EXPECT_TRUE(worklist.IsEmpty());
115 1 : }
116 :
117 15443 : TEST(WorkListTest, LocalPushPop) {
118 1 : TestWorklist worklist;
119 : TestWorklist::View worklist_view(&worklist, 0);
120 : SomeObject dummy;
121 1 : SomeObject* retrieved = nullptr;
122 1 : EXPECT_TRUE(worklist_view.Push(&dummy));
123 2 : EXPECT_FALSE(worklist_view.IsLocalEmpty());
124 1 : EXPECT_TRUE(worklist_view.Pop(&retrieved));
125 2 : EXPECT_EQ(&dummy, retrieved);
126 1 : }
127 :
128 15443 : TEST(WorkListTest, LocalIsBasedOnId) {
129 1 : TestWorklist worklist;
130 : // Use the same id.
131 : TestWorklist::View worklist_view1(&worklist, 0);
132 : TestWorklist::View worklist_view2(&worklist, 0);
133 : SomeObject dummy;
134 1 : SomeObject* retrieved = nullptr;
135 1 : EXPECT_TRUE(worklist_view1.Push(&dummy));
136 2 : EXPECT_FALSE(worklist_view1.IsLocalEmpty());
137 2 : EXPECT_FALSE(worklist_view2.IsLocalEmpty());
138 1 : EXPECT_TRUE(worklist_view2.Pop(&retrieved));
139 2 : EXPECT_EQ(&dummy, retrieved);
140 1 : EXPECT_TRUE(worklist_view1.IsLocalEmpty());
141 1 : EXPECT_TRUE(worklist_view2.IsLocalEmpty());
142 1 : }
143 :
144 15443 : TEST(WorkListTest, LocalPushStaysPrivate) {
145 1 : TestWorklist worklist;
146 : TestWorklist::View worklist_view1(&worklist, 0);
147 : TestWorklist::View worklist_view2(&worklist, 1);
148 : SomeObject dummy;
149 1 : SomeObject* retrieved = nullptr;
150 2 : EXPECT_TRUE(worklist.IsEmpty());
151 1 : EXPECT_TRUE(worklist_view1.Push(&dummy));
152 2 : EXPECT_FALSE(worklist.IsEmpty());
153 2 : EXPECT_FALSE(worklist_view2.Pop(&retrieved));
154 2 : EXPECT_EQ(nullptr, retrieved);
155 1 : EXPECT_TRUE(worklist_view1.Pop(&retrieved));
156 2 : EXPECT_EQ(&dummy, retrieved);
157 2 : EXPECT_TRUE(worklist.IsEmpty());
158 1 : }
159 :
160 15443 : TEST(WorkListTest, GlobalUpdateNull) {
161 1 : TestWorklist worklist;
162 : TestWorklist::View worklist_view(&worklist, 0);
163 : SomeObject* object;
164 1 : object = reinterpret_cast<SomeObject*>(&object);
165 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
166 128 : EXPECT_TRUE(worklist_view.Push(object));
167 : }
168 2 : EXPECT_TRUE(worklist_view.Push(object));
169 1 : worklist.Update([](SomeObject* object, SomeObject** out) { return false; });
170 2 : EXPECT_TRUE(worklist.IsEmpty());
171 1 : }
172 :
173 15443 : TEST(WorkListTest, GlobalUpdate) {
174 1 : TestWorklist worklist;
175 : TestWorklist::View worklist_view(&worklist, 0);
176 1 : SomeObject* objectA = nullptr;
177 1 : objectA = reinterpret_cast<SomeObject*>(&objectA);
178 1 : SomeObject* objectB = nullptr;
179 1 : objectB = reinterpret_cast<SomeObject*>(&objectB);
180 1 : SomeObject* objectC = nullptr;
181 1 : objectC = reinterpret_cast<SomeObject*>(&objectC);
182 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
183 128 : EXPECT_TRUE(worklist_view.Push(objectA));
184 : }
185 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
186 128 : EXPECT_TRUE(worklist_view.Push(objectB));
187 : }
188 2 : EXPECT_TRUE(worklist_view.Push(objectA));
189 : worklist.Update([objectA, objectC](SomeObject* object, SomeObject** out) {
190 129 : if (object != objectA) {
191 64 : *out = objectC;
192 : return true;
193 : }
194 : return false;
195 1 : });
196 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
197 : SomeObject* object;
198 64 : EXPECT_TRUE(worklist_view.Pop(&object));
199 64 : EXPECT_EQ(object, objectC);
200 : }
201 1 : }
202 :
203 15443 : TEST(WorkListTest, FlushToGlobalPushSegment) {
204 1 : TestWorklist worklist;
205 : TestWorklist::View worklist_view0(&worklist, 0);
206 : TestWorklist::View worklist_view1(&worklist, 1);
207 1 : SomeObject* object = nullptr;
208 1 : SomeObject* objectA = nullptr;
209 1 : objectA = reinterpret_cast<SomeObject*>(&objectA);
210 1 : EXPECT_TRUE(worklist_view0.Push(objectA));
211 1 : worklist.FlushToGlobal(0);
212 1 : EXPECT_TRUE(worklist_view1.Pop(&object));
213 1 : }
214 :
215 15443 : TEST(WorkListTest, FlushToGlobalPopSegment) {
216 1 : TestWorklist worklist;
217 : TestWorklist::View worklist_view0(&worklist, 0);
218 : TestWorklist::View worklist_view1(&worklist, 1);
219 1 : SomeObject* object = nullptr;
220 1 : SomeObject* objectA = nullptr;
221 1 : objectA = reinterpret_cast<SomeObject*>(&objectA);
222 1 : EXPECT_TRUE(worklist_view0.Push(objectA));
223 2 : EXPECT_TRUE(worklist_view0.Push(objectA));
224 1 : EXPECT_TRUE(worklist_view0.Pop(&object));
225 1 : worklist.FlushToGlobal(0);
226 1 : EXPECT_TRUE(worklist_view1.Pop(&object));
227 1 : }
228 :
229 15443 : TEST(WorkListTest, Clear) {
230 1 : TestWorklist worklist;
231 : TestWorklist::View worklist_view(&worklist, 0);
232 : SomeObject* object;
233 1 : object = reinterpret_cast<SomeObject*>(&object);
234 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
235 128 : EXPECT_TRUE(worklist_view.Push(object));
236 : }
237 2 : EXPECT_TRUE(worklist_view.Push(object));
238 : worklist.Clear();
239 2 : EXPECT_TRUE(worklist.IsEmpty());
240 1 : }
241 :
242 15443 : TEST(WorkListTest, SingleSegmentSteal) {
243 1 : TestWorklist worklist;
244 : TestWorklist::View worklist_view1(&worklist, 0);
245 : TestWorklist::View worklist_view2(&worklist, 1);
246 : SomeObject dummy;
247 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
248 64 : EXPECT_TRUE(worklist_view1.Push(&dummy));
249 : }
250 1 : SomeObject* retrieved = nullptr;
251 : // One more push/pop to publish the full segment.
252 1 : EXPECT_TRUE(worklist_view1.Push(nullptr));
253 1 : EXPECT_TRUE(worklist_view1.Pop(&retrieved));
254 2 : EXPECT_EQ(nullptr, retrieved);
255 : // Stealing.
256 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
257 64 : EXPECT_TRUE(worklist_view2.Pop(&retrieved));
258 128 : EXPECT_EQ(&dummy, retrieved);
259 128 : EXPECT_FALSE(worklist_view1.Pop(&retrieved));
260 : }
261 2 : EXPECT_TRUE(worklist.IsEmpty());
262 1 : }
263 :
264 15443 : TEST(WorkListTest, MultipleSegmentsStolen) {
265 1 : TestWorklist worklist;
266 : TestWorklist::View worklist_view1(&worklist, 0);
267 : TestWorklist::View worklist_view2(&worklist, 1);
268 : TestWorklist::View worklist_view3(&worklist, 2);
269 : SomeObject dummy1;
270 : SomeObject dummy2;
271 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
272 64 : EXPECT_TRUE(worklist_view1.Push(&dummy1));
273 : }
274 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
275 64 : EXPECT_TRUE(worklist_view1.Push(&dummy2));
276 : }
277 1 : SomeObject* retrieved = nullptr;
278 : SomeObject dummy3;
279 : // One more push/pop to publish the full segment.
280 1 : EXPECT_TRUE(worklist_view1.Push(&dummy3));
281 1 : EXPECT_TRUE(worklist_view1.Pop(&retrieved));
282 2 : EXPECT_EQ(&dummy3, retrieved);
283 : // Stealing.
284 1 : EXPECT_TRUE(worklist_view2.Pop(&retrieved));
285 1 : SomeObject* const expect_bag2 = retrieved;
286 1 : EXPECT_TRUE(worklist_view3.Pop(&retrieved));
287 1 : SomeObject* const expect_bag3 = retrieved;
288 1 : EXPECT_NE(expect_bag2, expect_bag3);
289 2 : EXPECT_TRUE(expect_bag2 == &dummy1 || expect_bag2 == &dummy2);
290 2 : EXPECT_TRUE(expect_bag3 == &dummy1 || expect_bag3 == &dummy2);
291 127 : for (size_t i = 1; i < TestWorklist::kSegmentCapacity; i++) {
292 63 : EXPECT_TRUE(worklist_view2.Pop(&retrieved));
293 63 : EXPECT_EQ(expect_bag2, retrieved);
294 126 : EXPECT_FALSE(worklist_view1.Pop(&retrieved));
295 : }
296 127 : for (size_t i = 1; i < TestWorklist::kSegmentCapacity; i++) {
297 63 : EXPECT_TRUE(worklist_view3.Pop(&retrieved));
298 63 : EXPECT_EQ(expect_bag3, retrieved);
299 126 : EXPECT_FALSE(worklist_view1.Pop(&retrieved));
300 : }
301 2 : EXPECT_TRUE(worklist.IsEmpty());
302 1 : }
303 :
304 15443 : TEST(WorkListTest, MergeGlobalPool) {
305 1 : TestWorklist worklist1;
306 : TestWorklist::View worklist_view1(&worklist1, 0);
307 : SomeObject dummy;
308 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
309 64 : EXPECT_TRUE(worklist_view1.Push(&dummy));
310 : }
311 1 : SomeObject* retrieved = nullptr;
312 : // One more push/pop to publish the full segment.
313 1 : EXPECT_TRUE(worklist_view1.Push(nullptr));
314 1 : EXPECT_TRUE(worklist_view1.Pop(&retrieved));
315 2 : EXPECT_EQ(nullptr, retrieved);
316 : // Merging global pool into a new Worklist.
317 1 : TestWorklist worklist2;
318 : TestWorklist::View worklist_view2(&worklist2, 0);
319 1 : worklist2.MergeGlobalPool(&worklist1);
320 2 : EXPECT_FALSE(worklist2.IsEmpty());
321 129 : for (size_t i = 0; i < TestWorklist::kSegmentCapacity; i++) {
322 64 : EXPECT_TRUE(worklist_view2.Pop(&retrieved));
323 128 : EXPECT_EQ(&dummy, retrieved);
324 128 : EXPECT_FALSE(worklist_view1.Pop(&retrieved));
325 : }
326 2 : EXPECT_TRUE(worklist1.IsEmpty());
327 2 : EXPECT_TRUE(worklist2.IsEmpty());
328 1 : }
329 :
330 : } // namespace internal
331 9264 : } // namespace v8
|
