1 /**
2 * Copyright (c) 2021-2022 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 panda::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
FillRanges(PandaVector<MemRange> * ranges,const Card * startCard,const Card * endCard)40 inline void CardTable::FillRanges(PandaVector<MemRange> *ranges, const Card *startCard, const Card *endCard)
41 {
42 constexpr size_t MIN_RANGE = 32;
43 constexpr size_t MAX_CARDS_COUNT = 1000; // How many cards we can process at once
44 static std::array<char, MAX_CARDS_COUNT> zeroArray {};
45
46 if (static_cast<size_t>(endCard - startCard) < MIN_RANGE) {
47 for (auto cardPtr = startCard; cardPtr <= endCard; cardPtr++) {
48 if (cardPtr->IsMarked()) {
49 ranges->emplace_back(minAddress_ + (cardPtr - cards_) * CARD_SIZE,
50 minAddress_ + (cardPtr - cards_ + 1) * CARD_SIZE - 1);
51 }
52 }
53 } else {
54 size_t diff = endCard - startCard + 1;
55 size_t splitSize = std::min(diff / 2, MAX_CARDS_COUNT); // divide 2 to get smaller split_size
56 if (memcmp(startCard, &zeroArray, splitSize) != 0) {
57 FillRanges(ranges, startCard, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize - 1));
58 }
59 // NOLINTNEXTLINE(bugprone-branch-clone)
60 if (diff - splitSize > MAX_CARDS_COUNT) {
61 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), endCard);
62 } else if (memcmp(ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), &zeroArray, diff - splitSize) != 0) {
63 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(startCard) + splitSize), endCard);
64 }
65 }
66 }
67
68 // Make sure we can treat size_t as lockfree atomic
69 static_assert(std::atomic_size_t::is_always_lock_free);
70 static_assert(sizeof(std::atomic_size_t) == sizeof(size_t));
71
72 template <typename CardVisitor>
VisitMarked(CardVisitor cardVisitor,uint32_t processedFlag)73 void CardTable::VisitMarked(CardVisitor cardVisitor, uint32_t processedFlag)
74 {
75 bool visitMarked = processedFlag & CardTableProcessedFlag::VISIT_MARKED;
76 bool visitProcessed = processedFlag & CardTableProcessedFlag::VISIT_PROCESSED;
77 bool setProcessed = processedFlag & CardTableProcessedFlag::SET_PROCESSED;
78 static_assert(sizeof(std::atomic_size_t) % sizeof(Card) == 0);
79 constexpr size_t CHUNK_CARD_NUM = sizeof(std::atomic_size_t) / sizeof(Card);
80 auto *card = cards_;
81 auto *cardEnd = cards_ + (cardsCount_ / CHUNK_CARD_NUM) * CHUNK_CARD_NUM;
82 while (card < cardEnd) {
83 // NB! In general wide load/short store on overlapping memory of different address are allowed to be reordered
84 // This optimization currently is allowed since additional VisitMarked is called after concurrent mark with
85 // global Mutator lock held, so all previous managed thread's writes should be visible by GC thread
86 // Atomic with relaxed order reason: data race with card with no synchronization or ordering constraints imposed
87 // on other reads or writes
88 if (LIKELY((reinterpret_cast<std::atomic_size_t *>(card))->load(std::memory_order_relaxed) == 0)) {
89 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
90 card += CHUNK_CARD_NUM;
91 continue;
92 }
93 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
94 auto *chunkEnd = card + CHUNK_CARD_NUM;
95 while (card < chunkEnd) {
96 if (!(visitMarked && card->IsMarked()) && !(visitProcessed && card->IsProcessed())) {
97 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
98 ++card;
99 continue;
100 }
101
102 if (setProcessed) {
103 card->SetProcessed();
104 }
105 cardVisitor(GetMemoryRange(card));
106 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
107 ++card;
108 }
109 }
110 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
111 for (; card < cards_ + cardsCount_; ++card) {
112 if ((visitMarked && card->IsMarked()) || (visitProcessed && card->IsProcessed())) {
113 if (setProcessed) {
114 card->SetProcessed();
115 }
116 cardVisitor(GetMemoryRange(card));
117 }
118 }
119 }
120
121 template <typename CardVisitor>
VisitMarkedCompact(CardVisitor cardVisitor)122 void CardTable::VisitMarkedCompact(CardVisitor cardVisitor)
123 {
124 constexpr size_t MAX_CARDS_COUNT = 1000;
125 size_t curPos = 0;
126 size_t endPos = 0;
127 PandaVector<MemRange> memRanges;
128
129 ASSERT(cardsCount_ > 0);
130 auto maxPoolAddress = PoolManager::GetMmapMemPool()->GetMaxObjectAddress();
131 while (curPos < cardsCount_) {
132 endPos = std::min(curPos + MAX_CARDS_COUNT - 1, cardsCount_ - 1);
133 FillRanges(&memRanges, &cards_[curPos], &cards_[endPos]);
134 curPos = endPos + 1;
135 if (GetCardStartAddress(&cards_[curPos]) > maxPoolAddress) {
136 break;
137 }
138 }
139 for (const auto &memRange : memRanges) {
140 cardVisitor(memRange);
141 }
142 }
143
144 } // namespace panda::mem
145
146 #endif // RUNTIME_MEM_GC_CARD_TABLE_INL_H
147