1 /**
2 * Copyright (c) 2021-2024 Huawei Device Co., Ltd.
3 * Licensed under the Apache License, Version 2.0 (the "License");
4 * you may not use this file except in compliance with the License.
5 * You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software
10 * distributed under the License is distributed on an "AS IS" BASIS,
11 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 * See the License for the specific language governing permissions and
13 * limitations under the License.
14 */
15
16 #include "mem/gc/card_table.h"
17 #include <chrono>
18 #include <cstdint>
19 #include <cstdlib>
20 #include <ctime>
21 #include <random>
22
23 #include "gtest/gtest.h"
24 #include "mem/mem.h"
25 #include "runtime/mem/gc/card_table-inl.h"
26 #include "runtime/mem/mem_stats_additional_info.h"
27 #include "runtime/mem/mem_stats_default.h"
28 #include "runtime/mem/internal_allocator-inl.h"
29 #include "runtime/include/runtime_options.h"
30 #include "runtime/include/runtime.h"
31 #include "runtime/include/panda_vm.h"
32
33 namespace ark::mem::test {
34
35 class CardTableTest : public testing::Test {
36 private:
37 std::mt19937 gen_;
38 std::uniform_int_distribution<uintptr_t> addrDis_;
39 std::uniform_int_distribution<size_t> cardIndexDis_;
40
41 protected:
42 // static constexpr size_t kHeapSize = 0xffffffff;
43 static constexpr size_t K_ALLOC_COUNT = 1000;
44 // static constexpr size_t maxCardIndex = kHeapSize / ::ark::mem::CardTable::GetCardSize();
45
46 // NOLINTNEXTLINE(cert-msc51-cpp)
CardTableTest()47 CardTableTest()
48 {
49 #ifdef PANDA_NIGHTLY_TEST_ON
50 seed_ = std::time(NULL);
51 #else
52 seed_ = RANDOM_SEED;
53 #endif
54 RuntimeOptions options;
55 // NOLINTNEXTLINE(readability-magic-numbers)
56 options.SetHeapSizeLimit(64_MB);
57 options.SetShouldLoadBootPandaFiles(false);
58 options.SetShouldInitializeIntrinsics(false);
59 options.SetGcType("epsilon");
60 Runtime::Create(options);
61 thread_ = ark::MTManagedThread::GetCurrent();
62 thread_->ManagedCodeBegin();
63
64 internalAllocator_ = thread_->GetVM()->GetHeapManager()->GetInternalAllocator();
65 addrDis_ = std::uniform_int_distribution<uintptr_t>(0, GetPoolSize() - 1);
66 ASSERT(GetPoolSize() % CardTable::GetCardSize() == 0);
67 cardIndexDis_ = std::uniform_int_distribution<size_t>(0, GetPoolSize() / CardTable::GetCardSize() - 1);
68 cardTable_ = std::make_unique<CardTable>(internalAllocator_, GetMinAddress(), GetPoolSize());
69 cardTable_->Initialize();
70 }
71
~CardTableTest()72 ~CardTableTest() override
73 {
74 cardTable_.reset(nullptr);
75 thread_->ManagedCodeEnd();
76 Runtime::Destroy();
77 }
78
79 NO_COPY_SEMANTIC(CardTableTest);
80 NO_MOVE_SEMANTIC(CardTableTest);
81
SetUp()82 void SetUp() override
83 {
84 gen_.seed(seed_);
85 }
86
TearDown()87 void TearDown() override
88 {
89 const ::testing::TestInfo *const testInfo = ::testing::UnitTest::GetInstance()->current_test_info();
90 if (testInfo->result()->Failed()) {
91 std::cout << "CartTableTest seed = " << seed_ << std::endl;
92 }
93 }
94
GetMinAddress()95 uintptr_t GetMinAddress()
96 {
97 return PoolManager::GetMmapMemPool()->GetMinObjectAddress();
98 }
99
GetPoolSize()100 size_t GetPoolSize()
101 {
102 return (PoolManager::GetMmapMemPool()->GetMaxObjectAddress() -
103 PoolManager::GetMmapMemPool()->GetMinObjectAddress());
104 }
105
GetRandomAddress()106 uintptr_t GetRandomAddress()
107 {
108 return PoolManager::GetMmapMemPool()->GetMinObjectAddress() + addrDis_(gen_) % GetPoolSize();
109 }
110
GetRandomCardIndex()111 size_t GetRandomCardIndex()
112 {
113 return cardIndexDis_(gen_) % GetPoolSize();
114 }
115
116 // generate address at the begining of the card
GetRandomCardAddress()117 uintptr_t GetRandomCardAddress()
118 {
119 return PoolManager::GetMmapMemPool()->GetMinObjectAddress() + GetRandomCardIndex() * CardTable::GetCardSize();
120 }
121
GetRandomCardAddressSet()122 std::set<uintptr_t> GetRandomCardAddressSet()
123 {
124 std::set<uintptr_t> addrSet;
125 while (addrSet.size() <= K_ALLOC_COUNT) {
126 uintptr_t addr = GetRandomCardAddress();
127 if (!addrSet.insert(addr).second) {
128 continue;
129 }
130 ASSERT(cardTable_->GetCardPtr(addr)->IsClear());
131 }
132 return addrSet;
133 }
134
SetMaxHotValue(std::set<uintptr_t> & addrSet)135 void SetMaxHotValue(std::set<uintptr_t> &addrSet)
136 {
137 for (auto addr : addrSet) {
138 auto *card = cardTable_->GetCardPtr(addr);
139 auto cardValue = card->GetCard();
140 while (!CardTable::Card::IsMaxHotValue(cardValue)) {
141 card->IncrementHotValue();
142 ASSERT(!card->IsClear());
143 cardValue = card->GetCard();
144 }
145 }
146 }
147
SetHotFlag(std::set<uintptr_t> & addrSet)148 void SetHotFlag(std::set<uintptr_t> &addrSet)
149 {
150 for (auto addr : addrSet) {
151 auto *card = cardTable_->GetCardPtr(addr);
152 card->SetHot();
153 ASSERT(card->IsHot());
154 }
155 }
156
157 // NOLINTNEXTLINE(misc-non-private-member-variables-in-classes)
158 std::unique_ptr<CardTable> cardTable_;
159
160 private:
161 InternalAllocatorPtr internalAllocator_;
162 unsigned int seed_ {};
163 ark::MTManagedThread *thread_ {};
164
165 static const unsigned int RANDOM_SEED = 123456U;
166 };
167
TEST_F(CardTableTest,MarkTest)168 TEST_F(CardTableTest, MarkTest)
169 {
170 size_t markedCnt = 0;
171
172 for (size_t i = 0; i < K_ALLOC_COUNT; i++) {
173 uintptr_t addr = GetRandomAddress();
174 if (!cardTable_->IsMarked(addr)) {
175 ++markedCnt;
176 cardTable_->MarkCard(addr);
177 }
178 }
179
180 for (auto card : *cardTable_) {
181 if (card->IsMarked()) {
182 markedCnt--;
183 }
184 }
185 ASSERT_EQ(markedCnt, 0);
186 }
187
TEST_F(CardTableTest,MarkAndClearAllTest)188 TEST_F(CardTableTest, MarkAndClearAllTest)
189 {
190 // std::set<uintptr_t> addrSet;
191
192 size_t cnt = 0;
193 for (auto card : *cardTable_) {
194 card->Mark();
195 cnt++;
196 }
197 ASSERT_EQ(cnt, cardTable_->GetCardsCount());
198
199 size_t cntCleared = 0;
200 for (auto card : *cardTable_) {
201 card->Clear();
202 cntCleared++;
203 }
204 ASSERT_EQ(cntCleared, cardTable_->GetCardsCount());
205 }
206
TEST_F(CardTableTest,ClearTest)207 TEST_F(CardTableTest, ClearTest)
208 {
209 std::set<uintptr_t> addrSet;
210
211 // Mark some cards not more than once
212 while (addrSet.size() <= K_ALLOC_COUNT) {
213 uintptr_t addr = GetRandomCardAddress();
214 if (!addrSet.insert(addr).second) {
215 continue;
216 }
217 cardTable_->MarkCard(addr);
218 }
219
220 size_t clearedCnt = 0;
221 // clear all marked and count them
222 for (auto card : *cardTable_) {
223 if (card->IsMarked()) {
224 card->UnMark();
225 clearedCnt++;
226 }
227 }
228
229 ASSERT_EQ(addrSet.size(), clearedCnt);
230 // check that there are no marked
231 for (auto card : *cardTable_) {
232 ASSERT_EQ(card->IsMarked(), false);
233 }
234 }
235
TEST_F(CardTableTest,ClearAllTest)236 TEST_F(CardTableTest, ClearAllTest)
237 {
238 std::set<uintptr_t> addrSet;
239
240 // Mark some cards not more than once
241 while (addrSet.size() < K_ALLOC_COUNT) {
242 uintptr_t addr = GetRandomCardAddress();
243 if (!addrSet.insert(addr).second) {
244 continue;
245 }
246 cardTable_->MarkCard(addr);
247 }
248
249 cardTable_->ClearAll();
250 for (auto card : *cardTable_) {
251 ASSERT_EQ(card->IsMarked(), false);
252 }
253 }
254
TEST_F(CardTableTest,double_initialization)255 TEST_F(CardTableTest, double_initialization)
256 {
257 EXPECT_DEATH(cardTable_->Initialize(), ".*");
258 }
259
TEST_F(CardTableTest,corner_cases)260 TEST_F(CardTableTest, corner_cases)
261 {
262 // Mark 1st byte in the heap
263 auto cardIt = cardTable_->begin();
264 auto *firstCard = *cardIt;
265 auto *secondCard = *(++cardIt);
266 ASSERT_EQ(firstCard->IsMarked(), false);
267 cardTable_->MarkCard(GetMinAddress());
268 ASSERT_EQ(firstCard->IsMarked(), true);
269 // Mark last byte in the heap
270 uintptr_t last = GetMinAddress() + GetPoolSize() - 1;
271 ASSERT_EQ(cardTable_->IsMarked(last), false);
272 cardTable_->MarkCard(last);
273 ASSERT_EQ(cardTable_->IsMarked(last), true);
274 // Mark last byte of second card
275 uintptr_t secondLast = GetMinAddress() + 2 * cardTable_->GetCardSize() - 1;
276 ASSERT_EQ(cardTable_->IsMarked(secondLast), false);
277 cardTable_->MarkCard(secondLast);
278 ASSERT_EQ(secondCard->IsMarked(), true);
279 }
280
TEST_F(CardTableTest,VisitMarked)281 TEST_F(CardTableTest, VisitMarked)
282 {
283 size_t markedCnt = 0;
284
285 while (markedCnt < K_ALLOC_COUNT) {
286 uintptr_t addr = GetRandomAddress();
287 if (!cardTable_->IsMarked(addr)) {
288 ++markedCnt;
289 cardTable_->MarkCard(addr);
290 }
291 }
292
293 PandaVector<MemRange> memRanges;
294 cardTable_->VisitMarked([&memRanges](MemRange memRange) { memRanges.emplace_back(memRange); },
295 CardTableProcessedFlag::VISIT_MARKED);
296
297 // Got ranges one by one
298 PandaVector<MemRange> expectedRanges;
299 for (auto card : *cardTable_) {
300 if (card->IsMarked()) {
301 expectedRanges.emplace_back(cardTable_->GetMemoryRange(card));
302 }
303 }
304
305 ASSERT_EQ(expectedRanges.size(), memRanges.size());
306 for (size_t i = 0; i < expectedRanges.size(); i++) {
307 ASSERT(memRanges[i].GetStartAddress() == expectedRanges[i].GetStartAddress());
308 ASSERT(memRanges[i].GetEndAddress() == expectedRanges[i].GetEndAddress());
309 }
310 }
311
TEST_F(CardTableTest,IncrementHotValueTest)312 TEST_F(CardTableTest, IncrementHotValueTest)
313 {
314 auto addrSet = GetRandomCardAddressSet();
315 for (auto addr : addrSet) {
316 auto *card = cardTable_->GetCardPtr(addr);
317 [[maybe_unused]] auto cardValue = card->GetCard();
318 ASSERT(CardTable::Card::IsMinHotValue(cardValue));
319 }
320 SetMaxHotValue(addrSet);
321 for (auto addr : addrSet) {
322 auto *card = cardTable_->GetCardPtr(addr);
323 auto cardValue = card->GetCard();
324 [[maybe_unused]] auto cardStatus = CardTable::Card::GetStatus(cardValue);
325 ASSERT(CardTable::Card::IsMaxHotValue(cardValue));
326 ASSERT(!CardTable::Card::IsHot(cardValue));
327 ASSERT(!CardTable::Card::IsMarked(cardStatus));
328 ASSERT(!CardTable::Card::IsYoung(cardStatus));
329 ASSERT(!CardTable::Card::IsProcessed(cardStatus));
330 }
331 }
332
TEST_F(CardTableTest,SetHotFlagTest)333 TEST_F(CardTableTest, SetHotFlagTest)
334 {
335 auto addrSet = GetRandomCardAddressSet();
336 SetHotFlag(addrSet);
337 for (auto addr : addrSet) {
338 auto *card = cardTable_->GetCardPtr(addr);
339 auto cardValue = card->GetCard();
340 [[maybe_unused]] auto cardStatus = CardTable::Card::GetStatus(cardValue);
341 ASSERT(CardTable::Card::IsHot(cardValue));
342 ASSERT(CardTable::Card::IsMinHotValue(cardValue));
343 ASSERT(!CardTable::Card::IsMarked(cardStatus));
344 ASSERT(!CardTable::Card::IsYoung(cardStatus));
345 ASSERT(!CardTable::Card::IsProcessed(cardStatus));
346 }
347 }
348
TEST_F(CardTableTest,HotCardTest)349 TEST_F(CardTableTest, HotCardTest)
350 {
351 auto addrSet = GetRandomCardAddressSet();
352 // Increment hot value
353 SetMaxHotValue(addrSet);
354 // Set hot flag
355 SetHotFlag(addrSet);
356
357 // Mark card
358 for (auto addr : addrSet) {
359 auto *card = cardTable_->GetCardPtr(addr);
360 ASSERT(!card->IsMarked());
361 card->Mark();
362 auto cardValue = card->GetCard();
363 [[maybe_unused]] auto cardStatus = CardTable::Card::GetStatus(cardValue);
364 ASSERT(CardTable::Card::IsMaxHotValue(cardValue));
365 ASSERT(CardTable::Card::IsHot(cardValue));
366 ASSERT(CardTable::Card::IsMarked(cardStatus));
367 ASSERT(!CardTable::Card::IsYoung(cardStatus));
368 ASSERT(!CardTable::Card::IsProcessed(cardStatus));
369 }
370
371 // Make card clear
372 for (auto addr : addrSet) {
373 auto *card = cardTable_->GetCardPtr(addr);
374 ASSERT(card->IsMarked());
375 card->UnMark();
376 auto cardValue = card->GetCard();
377 [[maybe_unused]] auto cardStatus = CardTable::Card::GetStatus(cardValue);
378 ASSERT(CardTable::Card::IsMaxHotValue(cardValue));
379 ASSERT(CardTable::Card::IsHot(cardValue));
380 ASSERT(!CardTable::Card::IsMarked(cardStatus));
381 ASSERT(!CardTable::Card::IsYoung(cardStatus));
382 ASSERT(!CardTable::Card::IsProcessed(cardStatus));
383
384 card->ResetHot();
385 cardValue = card->GetCard();
386 cardStatus = CardTable::Card::GetStatus(cardValue);
387 ASSERT(CardTable::Card::IsMaxHotValue(cardValue));
388 ASSERT(!CardTable::Card::IsHot(cardValue));
389 ASSERT(!CardTable::Card::IsMarked(cardStatus));
390 ASSERT(!CardTable::Card::IsYoung(cardStatus));
391 ASSERT(!CardTable::Card::IsProcessed(cardStatus));
392
393 while (!CardTable::Card::IsMinHotValue(cardValue)) {
394 ASSERT(!card->IsClear());
395 card->DecrementHotValue();
396 cardValue = card->GetCard();
397 }
398 ASSERT(card->IsClear());
399 }
400 }
401
402 } // namespace ark::mem::test
403