1 // Copyright 2015 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 <vector>
6 
7 #include "src/globals.h"
8 #include "src/heap/heap.h"
9 #include "src/heap/spaces.h"
10 #include "src/heap/spaces-inl.h"
11 #include "test/cctest/cctest.h"
12 
13 namespace v8 {
14 namespace internal {
15 
AllocateLabBackingStore(Heap * heap,intptr_t size_in_bytes)16 static Address AllocateLabBackingStore(Heap* heap, intptr_t size_in_bytes) {
17   AllocationResult result = heap->old_space()->AllocateRaw(
18       static_cast<int>(size_in_bytes), kDoubleAligned);
19   Object* obj = result.ToObjectChecked();
20   Address adr = HeapObject::cast(obj)->address();
21   return adr;
22 }
23 
24 
VerifyIterable(v8::internal::Address base,v8::internal::Address limit,std::vector<intptr_t> expected_size)25 static void VerifyIterable(v8::internal::Address base,
26                            v8::internal::Address limit,
27                            std::vector<intptr_t> expected_size) {
28   CHECK_LE(reinterpret_cast<intptr_t>(base), reinterpret_cast<intptr_t>(limit));
29   HeapObject* object = nullptr;
30   size_t counter = 0;
31   while (base < limit) {
32     object = HeapObject::FromAddress(base);
33     CHECK(object->IsFiller());
34     CHECK_LT(counter, expected_size.size());
35     CHECK_EQ(expected_size[counter], object->Size());
36     base += object->Size();
37     counter++;
38   }
39 }
40 
41 
AllocateFromLab(Heap * heap,LocalAllocationBuffer * lab,intptr_t size_in_bytes,AllocationAlignment alignment=kWordAligned)42 static bool AllocateFromLab(Heap* heap, LocalAllocationBuffer* lab,
43                             intptr_t size_in_bytes,
44                             AllocationAlignment alignment = kWordAligned) {
45   HeapObject* obj;
46   AllocationResult result =
47       lab->AllocateRawAligned(static_cast<int>(size_in_bytes), alignment);
48   if (result.To(&obj)) {
49     heap->CreateFillerObjectAt(obj->address(), static_cast<int>(size_in_bytes));
50     return true;
51   }
52   return false;
53 }
54 
55 
TEST(InvalidLab)56 TEST(InvalidLab) {
57   LocalAllocationBuffer lab = LocalAllocationBuffer::InvalidBuffer();
58   CHECK(!lab.IsValid());
59 }
60 
61 
TEST(UnusedLabImplicitClose)62 TEST(UnusedLabImplicitClose) {
63   CcTest::InitializeVM();
64   Heap* heap = CcTest::heap();
65   heap->root(Heap::kOnePointerFillerMapRootIndex);
66   const int kLabSize = 4 * KB;
67   Address base = AllocateLabBackingStore(heap, kLabSize);
68   Address limit = base + kLabSize;
69   intptr_t expected_sizes_raw[1] = {kLabSize};
70   std::vector<intptr_t> expected_sizes(expected_sizes_raw,
71                                        expected_sizes_raw + 1);
72   {
73     AllocationResult lab_backing_store(HeapObject::FromAddress(base));
74     LocalAllocationBuffer lab =
75         LocalAllocationBuffer::FromResult(heap, lab_backing_store, kLabSize);
76     CHECK(lab.IsValid());
77   }
78   VerifyIterable(base, limit, expected_sizes);
79 }
80 
81 
TEST(SimpleAllocate)82 TEST(SimpleAllocate) {
83   CcTest::InitializeVM();
84   Heap* heap = CcTest::heap();
85   const int kLabSize = 4 * KB;
86   Address base = AllocateLabBackingStore(heap, kLabSize);
87   Address limit = base + kLabSize;
88   intptr_t sizes_raw[1] = {128};
89   intptr_t expected_sizes_raw[2] = {128, kLabSize - 128};
90   std::vector<intptr_t> sizes(sizes_raw, sizes_raw + 1);
91   std::vector<intptr_t> expected_sizes(expected_sizes_raw,
92                                        expected_sizes_raw + 2);
93   {
94     AllocationResult lab_backing_store(HeapObject::FromAddress(base));
95     LocalAllocationBuffer lab =
96         LocalAllocationBuffer::FromResult(heap, lab_backing_store, kLabSize);
97     CHECK(lab.IsValid());
98     intptr_t sum = 0;
99     for (auto size : sizes) {
100       if (AllocateFromLab(heap, &lab, size)) {
101         sum += size;
102       }
103     }
104   }
105   VerifyIterable(base, limit, expected_sizes);
106 }
107 
108 
TEST(AllocateUntilLabOOM)109 TEST(AllocateUntilLabOOM) {
110   CcTest::InitializeVM();
111   Heap* heap = CcTest::heap();
112   const int kLabSize = 2 * KB;
113   Address base = AllocateLabBackingStore(heap, kLabSize);
114   Address limit = base + kLabSize;
115   // The following objects won't fit in {kLabSize}.
116   intptr_t sizes_raw[5] = {512, 512, 128, 512, 512};
117   intptr_t expected_sizes_raw[5] = {512, 512, 128, 512, 384 /* left over */};
118   std::vector<intptr_t> sizes(sizes_raw, sizes_raw + 5);
119   std::vector<intptr_t> expected_sizes(expected_sizes_raw,
120                                        expected_sizes_raw + 5);
121   intptr_t sum = 0;
122   {
123     AllocationResult lab_backing_store(HeapObject::FromAddress(base));
124     LocalAllocationBuffer lab =
125         LocalAllocationBuffer::FromResult(heap, lab_backing_store, kLabSize);
126     CHECK(lab.IsValid());
127     for (auto size : sizes) {
128       if (AllocateFromLab(heap, &lab, size)) {
129         sum += size;
130       }
131     }
132     CHECK_EQ(kLabSize - sum, 384);
133   }
134   VerifyIterable(base, limit, expected_sizes);
135 }
136 
137 
TEST(AllocateExactlyUntilLimit)138 TEST(AllocateExactlyUntilLimit) {
139   CcTest::InitializeVM();
140   Heap* heap = CcTest::heap();
141   const int kLabSize = 2 * KB;
142   Address base = AllocateLabBackingStore(heap, kLabSize);
143   Address limit = base + kLabSize;
144   intptr_t sizes_raw[4] = {512, 512, 512, 512};
145   intptr_t expected_sizes_raw[5] = {512, 512, 512, 512, 0};
146   std::vector<intptr_t> sizes(sizes_raw, sizes_raw + 4);
147   std::vector<intptr_t> expected_sizes(expected_sizes_raw,
148                                        expected_sizes_raw + 5);
149   {
150     AllocationResult lab_backing_store(HeapObject::FromAddress(base));
151     LocalAllocationBuffer lab =
152         LocalAllocationBuffer::FromResult(heap, lab_backing_store, kLabSize);
153     CHECK(lab.IsValid());
154     intptr_t sum = 0;
155     for (auto size : sizes) {
156       if (AllocateFromLab(heap, &lab, size)) {
157         sum += size;
158       } else {
159         break;
160       }
161     }
162     CHECK_EQ(kLabSize - sum, 0);
163   }
164   VerifyIterable(base, limit, expected_sizes);
165 }
166 
167 
TEST(MergeSuccessful)168 TEST(MergeSuccessful) {
169   CcTest::InitializeVM();
170   Heap* heap = CcTest::heap();
171   const int kLabSize = 2 * KB;
172   Address base1 = AllocateLabBackingStore(heap, kLabSize);
173   Address limit1 = base1 + kLabSize;
174   Address base2 = limit1;
175   Address limit2 = base2 + kLabSize;
176 
177   intptr_t sizes1_raw[4] = {512, 512, 512, 256};
178   intptr_t expected_sizes1_raw[5] = {512, 512, 512, 256, 256};
179   std::vector<intptr_t> sizes1(sizes1_raw, sizes1_raw + 4);
180   std::vector<intptr_t> expected_sizes1(expected_sizes1_raw,
181                                         expected_sizes1_raw + 5);
182 
183   intptr_t sizes2_raw[5] = {256, 512, 512, 512, 512};
184   intptr_t expected_sizes2_raw[10] = {512, 512, 512, 256, 256,
185                                       512, 512, 512, 512, 0};
186   std::vector<intptr_t> sizes2(sizes2_raw, sizes2_raw + 5);
187   std::vector<intptr_t> expected_sizes2(expected_sizes2_raw,
188                                         expected_sizes2_raw + 10);
189 
190   {
191     AllocationResult lab_backing_store1(HeapObject::FromAddress(base1));
192     LocalAllocationBuffer lab1 =
193         LocalAllocationBuffer::FromResult(heap, lab_backing_store1, kLabSize);
194     CHECK(lab1.IsValid());
195     intptr_t sum = 0;
196     for (auto size : sizes1) {
197       if (AllocateFromLab(heap, &lab1, size)) {
198         sum += size;
199       } else {
200         break;
201       }
202     }
203 
204     AllocationResult lab_backing_store2(HeapObject::FromAddress(base2));
205     LocalAllocationBuffer lab2 =
206         LocalAllocationBuffer::FromResult(heap, lab_backing_store2, kLabSize);
207     CHECK(lab2.IsValid());
208     CHECK(lab2.TryMerge(&lab1));
209     CHECK(!lab1.IsValid());
210     for (auto size : sizes2) {
211       if (AllocateFromLab(heap, &lab2, size)) {
212         sum += size;
213       } else {
214         break;
215       }
216     }
217     CHECK_EQ(2 * kLabSize - sum, 0);
218   }
219   VerifyIterable(base1, limit1, expected_sizes1);
220   VerifyIterable(base1, limit2, expected_sizes2);
221 }
222 
223 
TEST(MergeFailed)224 TEST(MergeFailed) {
225   CcTest::InitializeVM();
226   Heap* heap = CcTest::heap();
227   const int kLabSize = 2 * KB;
228   Address base1 = AllocateLabBackingStore(heap, kLabSize);
229   Address base2 = base1 + kLabSize;
230   Address base3 = base2 + kLabSize;
231 
232   {
233     AllocationResult lab_backing_store1(HeapObject::FromAddress(base1));
234     LocalAllocationBuffer lab1 =
235         LocalAllocationBuffer::FromResult(heap, lab_backing_store1, kLabSize);
236     CHECK(lab1.IsValid());
237 
238     AllocationResult lab_backing_store2(HeapObject::FromAddress(base2));
239     LocalAllocationBuffer lab2 =
240         LocalAllocationBuffer::FromResult(heap, lab_backing_store2, kLabSize);
241     CHECK(lab2.IsValid());
242 
243     AllocationResult lab_backing_store3(HeapObject::FromAddress(base3));
244     LocalAllocationBuffer lab3 =
245         LocalAllocationBuffer::FromResult(heap, lab_backing_store3, kLabSize);
246     CHECK(lab3.IsValid());
247 
248     CHECK(!lab3.TryMerge(&lab1));
249   }
250 }
251 
252 
253 #ifdef V8_HOST_ARCH_32_BIT
TEST(AllocateAligned)254 TEST(AllocateAligned) {
255   CcTest::InitializeVM();
256   Heap* heap = CcTest::heap();
257   const int kLabSize = 2 * KB;
258   Address base = AllocateLabBackingStore(heap, kLabSize);
259   Address limit = base + kLabSize;
260   std::pair<intptr_t, AllocationAlignment> sizes_raw[2] = {
261       std::make_pair(116, kWordAligned), std::make_pair(64, kDoubleAligned)};
262   std::vector<std::pair<intptr_t, AllocationAlignment>> sizes(sizes_raw,
263                                                               sizes_raw + 2);
264   intptr_t expected_sizes_raw[4] = {116, 4, 64, 1864};
265   std::vector<intptr_t> expected_sizes(expected_sizes_raw,
266                                        expected_sizes_raw + 4);
267 
268   {
269     AllocationResult lab_backing_store(HeapObject::FromAddress(base));
270     LocalAllocationBuffer lab =
271         LocalAllocationBuffer::FromResult(heap, lab_backing_store, kLabSize);
272     CHECK(lab.IsValid());
273     for (auto pair : sizes) {
274       if (!AllocateFromLab(heap, &lab, pair.first, pair.second)) {
275         break;
276       }
277     }
278   }
279   VerifyIterable(base, limit, expected_sizes);
280 }
281 #endif  // V8_HOST_ARCH_32_BIT
282 
283 }  // namespace internal
284 }  // namespace v8
285