Line data Source code
1 : // Copyright 2016 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/zone/zone-chunk-list.h"
6 :
7 : #include "src/zone/accounting-allocator.h"
8 : #include "src/zone/zone.h"
9 : #include "testing/gtest/include/gtest/gtest.h"
10 :
11 : namespace v8 {
12 : namespace internal {
13 :
14 : const size_t kItemCount = size_t(1) << 10;
15 :
16 15443 : TEST(ZoneChunkList, ForwardIterationTest) {
17 2 : AccountingAllocator allocator;
18 2 : Zone zone(&allocator, ZONE_NAME);
19 :
20 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
21 :
22 2049 : for (size_t i = 0; i < kItemCount; ++i) {
23 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
24 : }
25 :
26 1 : size_t count = 0;
27 :
28 2049 : for (uintptr_t item : zone_chunk_list) {
29 2048 : EXPECT_EQ(static_cast<size_t>(item), count);
30 1024 : count++;
31 : }
32 :
33 1 : EXPECT_EQ(count, kItemCount);
34 1 : }
35 :
36 15443 : TEST(ZoneChunkList, ReverseIterationTest) {
37 2 : AccountingAllocator allocator;
38 2 : Zone zone(&allocator, ZONE_NAME);
39 :
40 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
41 :
42 2049 : for (size_t i = 0; i < kItemCount; ++i) {
43 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
44 : }
45 :
46 1 : size_t count = 0;
47 :
48 1025 : for (auto it = zone_chunk_list.rbegin(); it != zone_chunk_list.rend(); ++it) {
49 3072 : EXPECT_EQ(static_cast<size_t>(*it), kItemCount - count - 1);
50 1024 : count++;
51 : }
52 :
53 1 : EXPECT_EQ(count, kItemCount);
54 1 : }
55 :
56 15443 : TEST(ZoneChunkList, PushFrontTest) {
57 2 : AccountingAllocator allocator;
58 2 : Zone zone(&allocator, ZONE_NAME);
59 :
60 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
61 :
62 2049 : for (size_t i = 0; i < kItemCount; ++i) {
63 1024 : zone_chunk_list.push_front(static_cast<uintptr_t>(i));
64 : }
65 :
66 1 : size_t count = 0;
67 :
68 2049 : for (uintptr_t item : zone_chunk_list) {
69 2048 : EXPECT_EQ(static_cast<size_t>(item), kItemCount - count - 1);
70 1024 : count++;
71 : }
72 :
73 1 : EXPECT_EQ(count, kItemCount);
74 1 : }
75 :
76 15443 : TEST(ZoneChunkList, RewindTest) {
77 2 : AccountingAllocator allocator;
78 2 : Zone zone(&allocator, ZONE_NAME);
79 :
80 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
81 :
82 2049 : for (size_t i = 0; i < kItemCount; ++i) {
83 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
84 : }
85 :
86 : zone_chunk_list.Rewind(42);
87 :
88 1 : size_t count = 0;
89 :
90 85 : for (uintptr_t item : zone_chunk_list) {
91 84 : EXPECT_EQ(static_cast<size_t>(item), count);
92 42 : count++;
93 : }
94 :
95 2 : EXPECT_EQ(count, 42u);
96 2 : EXPECT_EQ(count, zone_chunk_list.size());
97 :
98 : zone_chunk_list.Rewind(0);
99 :
100 1 : count = 0;
101 :
102 1 : for (uintptr_t item : zone_chunk_list) {
103 : USE(item);
104 0 : count++;
105 : }
106 :
107 2 : EXPECT_EQ(count, 0u);
108 2 : EXPECT_EQ(count, zone_chunk_list.size());
109 :
110 : zone_chunk_list.Rewind(100);
111 :
112 1 : count = 0;
113 :
114 1 : for (uintptr_t item : zone_chunk_list) {
115 0 : EXPECT_EQ(static_cast<size_t>(item), count);
116 0 : count++;
117 : }
118 :
119 2 : EXPECT_EQ(count, 0u);
120 2 : EXPECT_EQ(count, zone_chunk_list.size());
121 1 : }
122 :
123 15443 : TEST(ZoneChunkList, FindTest) {
124 2 : AccountingAllocator allocator;
125 2 : Zone zone(&allocator, ZONE_NAME);
126 :
127 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
128 :
129 2049 : for (size_t i = 0; i < kItemCount; ++i) {
130 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
131 : }
132 :
133 : const size_t index = kItemCount / 2 + 42;
134 :
135 2 : EXPECT_EQ(*zone_chunk_list.Find(index), static_cast<uintptr_t>(index));
136 :
137 1 : *zone_chunk_list.Find(index) = 42;
138 :
139 2 : EXPECT_EQ(*zone_chunk_list.Find(index), 42u);
140 1 : }
141 :
142 15443 : TEST(ZoneChunkList, CopyToTest) {
143 2 : AccountingAllocator allocator;
144 2 : Zone zone(&allocator, ZONE_NAME);
145 :
146 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
147 :
148 2049 : for (size_t i = 0; i < kItemCount; ++i) {
149 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
150 : }
151 :
152 : uintptr_t* array = zone.NewArray<uintptr_t>(kItemCount);
153 :
154 1 : zone_chunk_list.CopyTo(array);
155 :
156 2049 : for (size_t i = 0; i < kItemCount; ++i) {
157 2048 : EXPECT_EQ(array[i], static_cast<uintptr_t>(i));
158 : }
159 1 : }
160 :
161 15443 : TEST(ZoneChunkList, SmallCopyToTest) {
162 2 : AccountingAllocator allocator;
163 2 : Zone zone(&allocator, ZONE_NAME);
164 :
165 : ZoneChunkList<uint8_t> zone_chunk_list(&zone);
166 :
167 2049 : for (size_t i = 0; i < kItemCount; ++i) {
168 1024 : zone_chunk_list.push_back(static_cast<uint8_t>(i & 0xFF));
169 : }
170 :
171 : uint8_t* array = zone.NewArray<uint8_t>(kItemCount);
172 :
173 1 : zone_chunk_list.CopyTo(array);
174 :
175 2049 : for (size_t i = 0; i < kItemCount; ++i) {
176 2048 : EXPECT_EQ(array[i], static_cast<uint8_t>(i & 0xFF));
177 : }
178 1 : }
179 :
180 : struct Fubar {
181 : size_t a_;
182 : size_t b_;
183 : };
184 :
185 15443 : TEST(ZoneChunkList, BigCopyToTest) {
186 2 : AccountingAllocator allocator;
187 2 : Zone zone(&allocator, ZONE_NAME);
188 :
189 : ZoneChunkList<Fubar> zone_chunk_list(&zone);
190 :
191 2049 : for (size_t i = 0; i < kItemCount; ++i) {
192 1024 : zone_chunk_list.push_back({i, i + 5});
193 : }
194 :
195 : Fubar* array = zone.NewArray<Fubar>(kItemCount);
196 :
197 1 : zone_chunk_list.CopyTo(array);
198 :
199 1025 : for (size_t i = 0; i < kItemCount; ++i) {
200 2048 : EXPECT_EQ(array[i].a_, i);
201 2048 : EXPECT_EQ(array[i].b_, i + 5);
202 : }
203 1 : }
204 :
205 1 : void TestForwardIterationOfConstList(
206 : const ZoneChunkList<uintptr_t>& zone_chunk_list) {
207 1 : size_t count = 0;
208 :
209 2049 : for (uintptr_t item : zone_chunk_list) {
210 2048 : EXPECT_EQ(static_cast<size_t>(item), count);
211 1024 : count++;
212 : }
213 :
214 1 : EXPECT_EQ(count, kItemCount);
215 1 : }
216 :
217 15443 : TEST(ZoneChunkList, ConstForwardIterationTest) {
218 2 : AccountingAllocator allocator;
219 2 : Zone zone(&allocator, ZONE_NAME);
220 :
221 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
222 :
223 2049 : for (size_t i = 0; i < kItemCount; ++i) {
224 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
225 : }
226 :
227 1 : TestForwardIterationOfConstList(zone_chunk_list);
228 1 : }
229 :
230 15443 : TEST(ZoneChunkList, RewindAndIterate) {
231 : // Regression test for https://bugs.chromium.org/p/v8/issues/detail?id=7478
232 2 : AccountingAllocator allocator;
233 2 : Zone zone(&allocator, ZONE_NAME);
234 :
235 : ZoneChunkList<int> zone_chunk_list(&zone);
236 :
237 : // Fill the list enough so that it will contain 2 chunks.
238 : int chunk_size = static_cast<int>(ZoneChunkList<int>::StartMode::kSmall);
239 10 : for (int i = 0; i < chunk_size + 1; ++i) {
240 9 : zone_chunk_list.push_back(i);
241 : }
242 :
243 : // Rewind and fill the first chunk again.
244 : zone_chunk_list.Rewind();
245 9 : for (int i = 0; i < chunk_size; ++i) {
246 8 : zone_chunk_list.push_back(i);
247 : }
248 :
249 : std::vector<int> expected;
250 9 : for (int i = 0; i < chunk_size; ++i) {
251 8 : expected.push_back(i);
252 : }
253 : std::vector<int> got;
254 :
255 : // Iterate. This used to not yield the expected result, since the end iterator
256 : // was in a weird state, and the running iterator didn't reach it after the
257 : // first chunk.
258 : auto it = zone_chunk_list.begin();
259 17 : while (it != zone_chunk_list.end()) {
260 8 : int value = *it;
261 8 : got.push_back(value);
262 : ++it;
263 : }
264 1 : CHECK_EQ(expected.size(), got.size());
265 17 : for (size_t i = 0; i < expected.size(); ++i) {
266 16 : CHECK_EQ(expected[i], got[i]);
267 : }
268 1 : }
269 :
270 15443 : TEST(ZoneChunkList, PushBackPopBackSize) {
271 : // Regression test for https://bugs.chromium.org/p/v8/issues/detail?id=7489
272 2 : AccountingAllocator allocator;
273 2 : Zone zone(&allocator, ZONE_NAME);
274 :
275 : ZoneChunkList<int> zone_chunk_list(&zone);
276 : CHECK_EQ(size_t(0), zone_chunk_list.size());
277 1 : zone_chunk_list.push_back(1);
278 1 : CHECK_EQ(size_t(1), zone_chunk_list.size());
279 : zone_chunk_list.pop_back();
280 1 : CHECK_EQ(size_t(0), zone_chunk_list.size());
281 1 : }
282 :
283 15443 : TEST(ZoneChunkList, AdvanceZeroTest) {
284 2 : AccountingAllocator allocator;
285 2 : Zone zone(&allocator, ZONE_NAME);
286 :
287 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
288 :
289 2049 : for (size_t i = 0; i < kItemCount; ++i) {
290 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
291 : }
292 :
293 : auto iterator_advance = zone_chunk_list.begin();
294 :
295 : iterator_advance.Advance(0);
296 :
297 1 : CHECK_EQ(iterator_advance, zone_chunk_list.begin());
298 1 : }
299 :
300 15443 : TEST(ZoneChunkList, AdvancePartwayTest) {
301 2 : AccountingAllocator allocator;
302 2 : Zone zone(&allocator, ZONE_NAME);
303 :
304 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
305 :
306 2049 : for (size_t i = 0; i < kItemCount; ++i) {
307 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
308 : }
309 :
310 : auto iterator_advance = zone_chunk_list.begin();
311 : auto iterator_one_by_one = zone_chunk_list.begin();
312 :
313 : iterator_advance.Advance(kItemCount / 2);
314 1025 : for (size_t i = 0; i < kItemCount / 2; ++i) {
315 : ++iterator_one_by_one;
316 : }
317 :
318 1 : CHECK_EQ(iterator_advance, iterator_one_by_one);
319 1 : }
320 :
321 15443 : TEST(ZoneChunkList, AdvanceEndTest) {
322 2 : AccountingAllocator allocator;
323 2 : Zone zone(&allocator, ZONE_NAME);
324 :
325 : ZoneChunkList<uintptr_t> zone_chunk_list(&zone);
326 :
327 2049 : for (size_t i = 0; i < kItemCount; ++i) {
328 1024 : zone_chunk_list.push_back(static_cast<uintptr_t>(i));
329 : }
330 :
331 : auto iterator_advance = zone_chunk_list.begin();
332 :
333 : iterator_advance.Advance(kItemCount);
334 :
335 1 : CHECK_EQ(iterator_advance, zone_chunk_list.end());
336 1 : }
337 :
338 15443 : TEST(ZoneChunkList, FindOverChunkBoundary) {
339 2 : AccountingAllocator allocator;
340 2 : Zone zone(&allocator, ZONE_NAME);
341 :
342 : ZoneChunkList<int> zone_chunk_list(&zone);
343 :
344 : // Make sure we get two chunks.
345 : int chunk_size = static_cast<int>(ZoneChunkList<int>::StartMode::kSmall);
346 10 : for (int i = 0; i < chunk_size + 1; ++i) {
347 9 : zone_chunk_list.push_back(i);
348 : }
349 :
350 19 : for (int i = 0; i < chunk_size + 1; ++i) {
351 18 : CHECK_EQ(i, *zone_chunk_list.Find(i));
352 : }
353 1 : }
354 :
355 : } // namespace internal
356 9264 : } // namespace v8
|
