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 #ifndef RUNTIME_MEM_GC_CARD_TABLE_INL_H
17 #define RUNTIME_MEM_GC_CARD_TABLE_INL_H
18
19 #include "runtime/mem/gc/card_table.h"
20 #include "runtime/include/mem/panda_containers.h"
21
22 #include <atomic>
23
24 namespace ark::mem {
25
GetCard()26 inline uint8_t CardTable::Card::GetCard() const
27 {
28 // Atomic with relaxed order reason: data race with value_ with no synchronization or ordering constraints imposed
29 // on other reads or writes
30 return value_.load(std::memory_order_relaxed);
31 }
32
SetCard(uint8_t newVal)33 inline void CardTable::Card::SetCard(uint8_t newVal)
34 {
35 // Atomic with relaxed order reason: data race with value_ with no synchronization or ordering constraints imposed
36 // on other reads or writes
37 value_.store(newVal, std::memory_order_relaxed);
38 }
39
GetStatus()40 inline CardTable::Card::Status CardTable::Card::GetStatus() const
41 {
42 // Atomic with relaxed order reason: data race with value_ with no synchronization or ordering constraints imposed
43 // on other reads or writes
44 return value_.load(std::memory_order_relaxed) & STATUS_MASK;
45 }
46
FillRanges(PandaVector<MemRange> * ranges,const Card * startCard,const Card * endCard)47 inline void CardTable::FillRanges(PandaVector<MemRange> *ranges, const Card *startCard, const Card *endCard)
48 {
49 constexpr size_t MIN_RANGE = 32;
50 constexpr size_t MAX_CARDS_COUNT = 1000; // How many cards we can process at once
51 static std::array<char, MAX_CARDS_COUNT> zeroArray {};
52
53 if (static_cast<size_t>(endCard - startCard) < MIN_RANGE) {
54 for (auto cardPtr = startCard; cardPtr <= endCard; cardPtr++) {
55 if (cardPtr->IsMarked()) {
56 ranges->emplace_back(minAddress_ + (cardPtr - cards_) * CARD_SIZE,
57 minAddress_ + (cardPtr - cards_ + 1) * CARD_SIZE - 1);
58 }
59 }
60 } else {
61 size_t diff = endCard - startCard + 1;
62 size_t splitSize = std::min(diff / 2, MAX_CARDS_COUNT); // divide 2 to get smaller split_size
63 if (memcmp(startCard, &zeroArray, splitSize) != 0) {
64 FillRanges(ranges, startCard, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize - 1));
65 }
66 // NOLINTNEXTLINE(bugprone-branch-clone)
67 if (diff - splitSize > MAX_CARDS_COUNT) {
68 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), endCard);
69 } else if (memcmp(ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), &zeroArray, diff - splitSize) != 0) {
70 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), endCard);
71 }
72 }
73 }
74
75 // Make sure we can treat size_t as lockfree atomic
76 static_assert(std::atomic_size_t::is_always_lock_free);
77 static_assert(sizeof(std::atomic_size_t) == sizeof(size_t));
78
79 template <typename CardVisitor>
VisitMarked(CardVisitor cardVisitor,uint32_t processedFlag)80 void CardTable::VisitMarked(CardVisitor cardVisitor, uint32_t processedFlag)
81 {
82 bool visitMarked = processedFlag & CardTableProcessedFlag::VISIT_MARKED;
83 bool visitProcessed = processedFlag & CardTableProcessedFlag::VISIT_PROCESSED;
84 bool setProcessed = processedFlag & CardTableProcessedFlag::SET_PROCESSED;
85 auto *card = cards_;
86 auto *cardEnd = cards_ + (cardsCount_ / CHUNK_CARD_NUM) * CHUNK_CARD_NUM;
87 while (card < cardEnd) {
88 // NB! In general wide load/short store on overlapping memory of different address are allowed to be reordered
89 // This optimization currently is allowed since additional VisitMarked is called after concurrent mark with
90 // global Mutator lock held, so all previous managed thread's writes should be visible by GC thread
91 // Atomic with relaxed order reason: data race with card with no synchronization or ordering constraints imposed
92 // on other reads or writes
93 if (LIKELY((reinterpret_cast<std::atomic_size_t *>(card))->load(std::memory_order_relaxed) == 0)) {
94 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
95 card += CHUNK_CARD_NUM;
96 continue;
97 }
98 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
99 auto *chunkEnd = card + CHUNK_CARD_NUM;
100 while (card < chunkEnd) {
101 auto cardStatus = card->GetStatus();
102 if (!(visitMarked && Card::IsMarked(cardStatus)) && !(visitProcessed && Card::IsProcessed(cardStatus))) {
103 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
104 ++card;
105 continue;
106 }
107
108 if (setProcessed) {
109 card->SetProcessed();
110 }
111 cardVisitor(GetMemoryRange(card));
112 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
113 ++card;
114 }
115 }
116 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
117 for (; card < cards_ + cardsCount_; ++card) {
118 auto cardStatus = card->GetStatus();
119 if ((visitMarked && Card::IsMarked(cardStatus)) || (visitProcessed && Card::IsProcessed(cardStatus))) {
120 if (setProcessed) {
121 card->SetProcessed();
122 }
123 cardVisitor(GetMemoryRange(card));
124 }
125 }
126 }
127
128 template <typename CardVisitor>
VisitMarkedCompact(CardVisitor cardVisitor)129 void CardTable::VisitMarkedCompact(CardVisitor cardVisitor)
130 {
131 constexpr size_t MAX_CARDS_COUNT = 1000;
132 size_t curPos = 0;
133 size_t endPos = 0;
134 PandaVector<MemRange> memRanges;
135
136 ASSERT(cardsCount_ > 0);
137 auto maxPoolAddress = PoolManager::GetMmapMemPool()->GetMaxObjectAddress();
138 while (curPos < cardsCount_) {
139 endPos = std::min(curPos + MAX_CARDS_COUNT - 1, cardsCount_ - 1);
140 FillRanges(&memRanges, &cards_[curPos], &cards_[endPos]);
141 curPos = endPos + 1;
142 if (GetCardStartAddress(&cards_[curPos]) > maxPoolAddress) {
143 break;
144 }
145 }
146 for (const auto &memRange : memRanges) {
147 cardVisitor(memRange);
148 }
149 }
150
151 #ifndef NDEBUG
IsClear()152 inline bool CardTable::IsClear()
153 {
154 bool clear = true;
155 VisitMarked(
156 [&clear](const MemRange &range) {
157 LOG(ERROR, GC) << "Card [" << ToVoidPtr(range.GetStartAddress()) << " - "
158 << ToVoidPtr(range.GetEndAddress()) << "] is not clear";
159 clear = false;
160 },
161 CardTableProcessedFlag::VISIT_MARKED | CardTableProcessedFlag::VISIT_PROCESSED);
162 return clear;
163 }
164 #endif
165 } // namespace ark::mem
166
167 #endif // RUNTIME_MEM_GC_CARD_TABLE_INL_H
168