1 /*
2 * Copyright (c) 2021 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 PANDA_RUNTIME_MEM_GC_CARD_TABLE_INL_H_
17 #define PANDA_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
FillRanges(PandaVector<MemRange> * ranges,const Card * start_card,const Card * end_card)26 inline void CardTable::FillRanges(PandaVector<MemRange> *ranges, const Card *start_card, const Card *end_card)
27 {
28 constexpr size_t MIN_RANGE = 32;
29 constexpr size_t MAX_CARDS_COUNT = 1000; // How many cards we can process at once
30 static std::array<char, MAX_CARDS_COUNT> zero_array {};
31
32 if (static_cast<size_t>(end_card - start_card) < MIN_RANGE) {
33 for (auto card_ptr = start_card; card_ptr <= end_card; card_ptr++) {
34 if (card_ptr->IsMarked()) {
35 ranges->emplace_back(min_address_ + (card_ptr - cards_) * CARD_SIZE,
36 min_address_ + (card_ptr - cards_ + 1) * CARD_SIZE - 1);
37 }
38 }
39 } else {
40 size_t diff = end_card - start_card + 1;
41 size_t split_size = std::min(diff / 2, MAX_CARDS_COUNT); // divide 2 to get smaller split_size
42 if (memcmp(start_card, &zero_array, split_size) != 0) {
43 FillRanges(ranges, start_card, ToNativePtr<Card>(ToUintPtr(start_card) + split_size - 1));
44 }
45 // NOLINTNEXTLINE(bugprone-branch-clone)
46 if (diff - split_size > MAX_CARDS_COUNT) {
47 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(start_card) + split_size), end_card);
48 } else if (memcmp(ToNativePtr<Card>(ToUintPtr(start_card) + split_size), &zero_array, diff - split_size) != 0) {
49 FillRanges(ranges, ToNativePtr<Card>(ToUintPtr(start_card) + split_size), end_card);
50 }
51 }
52 }
53
54 // Make sure we can treat size_t as lockfree atomic
55 static_assert(std::atomic_size_t::is_always_lock_free);
56 static_assert(sizeof(std::atomic_size_t) == sizeof(size_t));
57
58 template <typename CardVisitor>
VisitMarked(CardVisitor card_visitor,uint32_t processed_flag)59 void CardTable::VisitMarked(CardVisitor card_visitor, uint32_t processed_flag)
60 {
61 bool visit_marked = processed_flag & CardTableProcessedFlag::VISIT_MARKED;
62 bool visit_processed = processed_flag & CardTableProcessedFlag::VISIT_PROCESSED;
63 bool set_processed = processed_flag & CardTableProcessedFlag::SET_PROCESSED;
64 static_assert(sizeof(std::atomic_size_t) % sizeof(Card) == 0);
65 constexpr size_t chunk_card_num = sizeof(std::atomic_size_t) / sizeof(Card);
66 auto *card = cards_;
67 auto *card_end = cards_ + (cards_count_ / chunk_card_num) * chunk_card_num;
68 while (card < card_end) {
69 // NB! In general wide load/short store on overlapping memory of different address are allowed to be reordered
70 // This optimization currently is allowed since additional VisitMarked is called after concurrent mark with
71 // global Mutator lock held, so all previous java thread's writes should be visible by GC thread
72 if (LIKELY((reinterpret_cast<std::atomic_size_t *>(card))->load(std::memory_order_relaxed) == 0)) {
73 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
74 card += chunk_card_num;
75 continue;
76 }
77 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
78 auto *chunk_end = card + chunk_card_num;
79 while (card < chunk_end) {
80 if (!(visit_marked && card->IsMarked()) && !(visit_processed && card->IsProcessed())) {
81 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
82 ++card;
83 continue;
84 }
85
86 if (set_processed) {
87 card->SetProcessed();
88 }
89 card_visitor(GetMemoryRange(card));
90 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
91 ++card;
92 }
93 }
94 // NOLINTNEXTLINE(cppcoreguidelines-pro-bounds-pointer-arithmetic)
95 for (; card < cards_ + cards_count_; ++card) {
96 if ((visit_marked && card->IsMarked()) || (visit_processed && card->IsProcessed())) {
97 if (set_processed) {
98 card->SetProcessed();
99 }
100 card_visitor(GetMemoryRange(card));
101 }
102 }
103 }
104
105 template <typename CardVisitor>
VisitMarkedCompact(CardVisitor card_visitor)106 void CardTable::VisitMarkedCompact(CardVisitor card_visitor)
107 {
108 constexpr size_t MAX_CARDS_COUNT = 1000;
109 size_t cur_pos = 0;
110 size_t end_pos = 0;
111 PandaVector<MemRange> mem_ranges;
112
113 ASSERT(cards_count_ > 0);
114 auto max_pool_address = PoolManager::GetMmapMemPool()->GetMaxObjectAddress();
115 while (cur_pos < cards_count_) {
116 end_pos = std::min(cur_pos + MAX_CARDS_COUNT - 1, cards_count_ - 1);
117 FillRanges(&mem_ranges, &cards_[cur_pos], &cards_[end_pos]);
118 cur_pos = end_pos + 1;
119 if (GetCardStartAddress(&cards_[cur_pos]) > max_pool_address) {
120 break;
121 }
122 }
123 for (const auto &mem_range : mem_ranges) {
124 card_visitor(mem_range);
125 }
126 }
127
128 } // namespace panda::mem
129
130 #endif // PANDA_RUNTIME_MEM_GC_CARD_TABLE_INL_H_
131