1 /*
2 * Copyright (C) 2008 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #ifndef ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
18 #define ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
19
20 #include "space_bitmap.h"
21
22 #include <memory>
23
24 #include "atomic.h"
25 #include "base/bit_utils.h"
26 #include "base/logging.h"
27
28 namespace art {
29 namespace gc {
30 namespace accounting {
31
32 template<size_t kAlignment>
AtomicTestAndSet(const mirror::Object * obj)33 inline bool SpaceBitmap<kAlignment>::AtomicTestAndSet(const mirror::Object* obj) {
34 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
35 DCHECK_GE(addr, heap_begin_);
36 const uintptr_t offset = addr - heap_begin_;
37 const size_t index = OffsetToIndex(offset);
38 const uintptr_t mask = OffsetToMask(offset);
39 Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
40 DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
41 uintptr_t old_word;
42 do {
43 old_word = atomic_entry->LoadRelaxed();
44 // Fast path: The bit is already set.
45 if ((old_word & mask) != 0) {
46 DCHECK(Test(obj));
47 return true;
48 }
49 } while (!atomic_entry->CompareExchangeWeakRelaxed(old_word, old_word | mask));
50 DCHECK(Test(obj));
51 return false;
52 }
53
54 template<size_t kAlignment>
Test(const mirror::Object * obj)55 inline bool SpaceBitmap<kAlignment>::Test(const mirror::Object* obj) const {
56 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
57 DCHECK(HasAddress(obj)) << obj;
58 DCHECK(bitmap_begin_ != nullptr);
59 DCHECK_GE(addr, heap_begin_);
60 const uintptr_t offset = addr - heap_begin_;
61 return (bitmap_begin_[OffsetToIndex(offset)].LoadRelaxed() & OffsetToMask(offset)) != 0;
62 }
63
64 template<size_t kAlignment> template<typename Visitor>
VisitMarkedRange(uintptr_t visit_begin,uintptr_t visit_end,Visitor && visitor)65 inline void SpaceBitmap<kAlignment>::VisitMarkedRange(uintptr_t visit_begin,
66 uintptr_t visit_end,
67 Visitor&& visitor) const {
68 DCHECK_LE(visit_begin, visit_end);
69 #if 0
70 for (uintptr_t i = visit_begin; i < visit_end; i += kAlignment) {
71 mirror::Object* obj = reinterpret_cast<mirror::Object*>(i);
72 if (Test(obj)) {
73 visitor(obj);
74 }
75 }
76 #else
77 DCHECK_LE(heap_begin_, visit_begin);
78 DCHECK_LE(visit_end, HeapLimit());
79
80 const uintptr_t offset_start = visit_begin - heap_begin_;
81 const uintptr_t offset_end = visit_end - heap_begin_;
82
83 const uintptr_t index_start = OffsetToIndex(offset_start);
84 const uintptr_t index_end = OffsetToIndex(offset_end);
85
86 const size_t bit_start = (offset_start / kAlignment) % kBitsPerIntPtrT;
87 const size_t bit_end = (offset_end / kAlignment) % kBitsPerIntPtrT;
88
89 // Index(begin) ... Index(end)
90 // [xxxxx???][........][????yyyy]
91 // ^ ^
92 // | #---- Bit of visit_end
93 // #---- Bit of visit_begin
94 //
95
96 // Left edge.
97 uintptr_t left_edge = bitmap_begin_[index_start];
98 // Mark of lower bits that are not in range.
99 left_edge &= ~((static_cast<uintptr_t>(1) << bit_start) - 1);
100
101 // Right edge. Either unique, or left_edge.
102 uintptr_t right_edge;
103
104 if (index_start < index_end) {
105 // Left edge != right edge.
106
107 // Traverse left edge.
108 if (left_edge != 0) {
109 const uintptr_t ptr_base = IndexToOffset(index_start) + heap_begin_;
110 do {
111 const size_t shift = CTZ(left_edge);
112 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
113 visitor(obj);
114 left_edge ^= (static_cast<uintptr_t>(1)) << shift;
115 } while (left_edge != 0);
116 }
117
118 // Traverse the middle, full part.
119 for (size_t i = index_start + 1; i < index_end; ++i) {
120 uintptr_t w = bitmap_begin_[i].LoadRelaxed();
121 if (w != 0) {
122 const uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
123 do {
124 const size_t shift = CTZ(w);
125 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
126 visitor(obj);
127 w ^= (static_cast<uintptr_t>(1)) << shift;
128 } while (w != 0);
129 }
130 }
131
132 // Right edge is unique.
133 // But maybe we don't have anything to do: visit_end starts in a new word...
134 if (bit_end == 0) {
135 // Do not read memory, as it could be after the end of the bitmap.
136 right_edge = 0;
137 } else {
138 right_edge = bitmap_begin_[index_end];
139 }
140 } else {
141 // Right edge = left edge.
142 right_edge = left_edge;
143 }
144
145 // Right edge handling.
146 right_edge &= ((static_cast<uintptr_t>(1) << bit_end) - 1);
147 if (right_edge != 0) {
148 const uintptr_t ptr_base = IndexToOffset(index_end) + heap_begin_;
149 do {
150 const size_t shift = CTZ(right_edge);
151 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
152 visitor(obj);
153 right_edge ^= (static_cast<uintptr_t>(1)) << shift;
154 } while (right_edge != 0);
155 }
156 #endif
157 }
158
159 template<size_t kAlignment> template<typename Visitor>
Walk(Visitor && visitor)160 void SpaceBitmap<kAlignment>::Walk(Visitor&& visitor) {
161 CHECK(bitmap_begin_ != nullptr);
162
163 uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1);
164 Atomic<uintptr_t>* bitmap_begin = bitmap_begin_;
165 for (uintptr_t i = 0; i <= end; ++i) {
166 uintptr_t w = bitmap_begin[i].LoadRelaxed();
167 if (w != 0) {
168 uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
169 do {
170 const size_t shift = CTZ(w);
171 mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
172 visitor(obj);
173 w ^= (static_cast<uintptr_t>(1)) << shift;
174 } while (w != 0);
175 }
176 }
177 }
178
179 template<size_t kAlignment> template<bool kSetBit>
Modify(const mirror::Object * obj)180 inline bool SpaceBitmap<kAlignment>::Modify(const mirror::Object* obj) {
181 uintptr_t addr = reinterpret_cast<uintptr_t>(obj);
182 DCHECK_GE(addr, heap_begin_);
183 DCHECK(HasAddress(obj)) << obj;
184 const uintptr_t offset = addr - heap_begin_;
185 const size_t index = OffsetToIndex(offset);
186 const uintptr_t mask = OffsetToMask(offset);
187 DCHECK_LT(index, bitmap_size_ / sizeof(intptr_t)) << " bitmap_size_ = " << bitmap_size_;
188 Atomic<uintptr_t>* atomic_entry = &bitmap_begin_[index];
189 uintptr_t old_word = atomic_entry->LoadRelaxed();
190 if (kSetBit) {
191 // Check the bit before setting the word incase we are trying to mark a read only bitmap
192 // like an image space bitmap. This bitmap is mapped as read only and will fault if we
193 // attempt to change any words. Since all of the objects are marked, this will never
194 // occur if we check before setting the bit. This also prevents dirty pages that would
195 // occur if the bitmap was read write and we did not check the bit.
196 if ((old_word & mask) == 0) {
197 atomic_entry->StoreRelaxed(old_word | mask);
198 }
199 } else {
200 atomic_entry->StoreRelaxed(old_word & ~mask);
201 }
202 DCHECK_EQ(Test(obj), kSetBit);
203 return (old_word & mask) != 0;
204 }
205
206 template<size_t kAlignment>
207 inline std::ostream& operator << (std::ostream& stream, const SpaceBitmap<kAlignment>& bitmap) {
208 return stream
209 << bitmap.GetName() << "["
210 << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
211 << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
212 << "]";
213 }
214
215 } // namespace accounting
216 } // namespace gc
217 } // namespace art
218
219 #endif // ART_RUNTIME_GC_ACCOUNTING_SPACE_BITMAP_INL_H_
220