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 #include "space_bitmap-inl.h"
18
19 #include "android-base/stringprintf.h"
20
21 #include "art_field-inl.h"
22 #include "base/mem_map.h"
23 #include "dex/dex_file-inl.h"
24 #include "mirror/class-inl.h"
25 #include "mirror/object-inl.h"
26 #include "mirror/object_array.h"
27
28 namespace art {
29 namespace gc {
30 namespace accounting {
31
32 using android::base::StringPrintf;
33
34 template<size_t kAlignment>
ComputeBitmapSize(uint64_t capacity)35 size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) {
36 // Number of space (heap) bytes covered by one bitmap word.
37 // (Word size in bytes = `sizeof(intptr_t)`, which is expected to be
38 // 4 on a 32-bit architecture and 8 on a 64-bit one.)
39 const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT;
40 // Calculate the number of words required to cover a space (heap)
41 // having a size of `capacity` bytes.
42 return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t);
43 }
44
45 template<size_t kAlignment>
ComputeHeapSize(uint64_t bitmap_bytes)46 size_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) {
47 return bitmap_bytes * kBitsPerByte * kAlignment;
48 }
49
50 template<size_t kAlignment>
CreateFromMemMap(const std::string & name,MemMap && mem_map,uint8_t * heap_begin,size_t heap_capacity)51 SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::CreateFromMemMap(
52 const std::string& name, MemMap&& mem_map, uint8_t* heap_begin, size_t heap_capacity) {
53 CHECK(mem_map.IsValid());
54 uintptr_t* bitmap_begin = reinterpret_cast<uintptr_t*>(mem_map.Begin());
55 const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
56 return { name, std::move(mem_map), bitmap_begin, bitmap_size, heap_begin, heap_capacity };
57 }
58
59 template<size_t kAlignment>
SpaceBitmap(const std::string & name,MemMap && mem_map,uintptr_t * bitmap_begin,size_t bitmap_size,const void * heap_begin,size_t heap_capacity)60 SpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name,
61 MemMap&& mem_map,
62 uintptr_t* bitmap_begin,
63 size_t bitmap_size,
64 const void* heap_begin,
65 size_t heap_capacity)
66 : mem_map_(std::move(mem_map)),
67 bitmap_begin_(reinterpret_cast<Atomic<uintptr_t>*>(bitmap_begin)),
68 bitmap_size_(bitmap_size),
69 heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
70 heap_limit_(reinterpret_cast<uintptr_t>(heap_begin) + heap_capacity),
71 name_(name) {
72 CHECK(bitmap_begin_ != nullptr);
73 CHECK_NE(bitmap_size, 0U);
74 }
75
76 template<size_t kAlignment>
~SpaceBitmap()77 SpaceBitmap<kAlignment>::~SpaceBitmap() {}
78
79 template<size_t kAlignment>
Create(const std::string & name,uint8_t * heap_begin,size_t heap_capacity)80 SpaceBitmap<kAlignment> SpaceBitmap<kAlignment>::Create(
81 const std::string& name, uint8_t* heap_begin, size_t heap_capacity) {
82 // Round up since `heap_capacity` is not necessarily a multiple of `kAlignment * kBitsPerIntPtrT`
83 // (we represent one word as an `intptr_t`).
84 const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
85 std::string error_msg;
86 MemMap mem_map = MemMap::MapAnonymous(name.c_str(),
87 bitmap_size,
88 PROT_READ | PROT_WRITE,
89 /*low_4gb=*/ false,
90 &error_msg);
91 if (UNLIKELY(!mem_map.IsValid())) {
92 LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
93 return SpaceBitmap<kAlignment>();
94 }
95 return CreateFromMemMap(name, std::move(mem_map), heap_begin, heap_capacity);
96 }
97
98 template<size_t kAlignment>
SetHeapLimit(uintptr_t new_end)99 void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) {
100 DCHECK_ALIGNED(new_end, kBitsPerIntPtrT * kAlignment);
101 size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t);
102 if (new_size < bitmap_size_) {
103 bitmap_size_ = new_size;
104 }
105 heap_limit_ = new_end;
106 // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
107 // should be marked.
108 }
109
110 template<size_t kAlignment>
Dump() const111 std::string SpaceBitmap<kAlignment>::Dump() const {
112 return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()),
113 reinterpret_cast<void*>(HeapLimit()));
114 }
115
116 template<size_t kAlignment>
Clear()117 void SpaceBitmap<kAlignment>::Clear() {
118 if (bitmap_begin_ != nullptr) {
119 mem_map_.MadviseDontNeedAndZero();
120 }
121 }
122
123 template<size_t kAlignment>
ClearRange(const mirror::Object * begin,const mirror::Object * end)124 void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirror::Object* end) {
125 uintptr_t begin_offset = reinterpret_cast<uintptr_t>(begin) - heap_begin_;
126 uintptr_t end_offset = reinterpret_cast<uintptr_t>(end) - heap_begin_;
127 // Align begin and end to bitmap word boundaries.
128 while (begin_offset < end_offset && OffsetBitIndex(begin_offset) != 0) {
129 Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + begin_offset));
130 begin_offset += kAlignment;
131 }
132 while (begin_offset < end_offset && OffsetBitIndex(end_offset) != 0) {
133 end_offset -= kAlignment;
134 Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + end_offset));
135 }
136 // Bitmap word boundaries.
137 const uintptr_t start_index = OffsetToIndex(begin_offset);
138 const uintptr_t end_index = OffsetToIndex(end_offset);
139 ZeroAndReleasePages(reinterpret_cast<uint8_t*>(&bitmap_begin_[start_index]),
140 (end_index - start_index) * sizeof(*bitmap_begin_));
141 }
142
143 template<size_t kAlignment>
CopyFrom(SpaceBitmap * source_bitmap)144 void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) {
145 DCHECK_EQ(Size(), source_bitmap->Size());
146 const size_t count = source_bitmap->Size() / sizeof(intptr_t);
147 Atomic<uintptr_t>* const src = source_bitmap->Begin();
148 Atomic<uintptr_t>* const dest = Begin();
149 for (size_t i = 0; i < count; ++i) {
150 dest[i].store(src[i].load(std::memory_order_relaxed), std::memory_order_relaxed);
151 }
152 }
153
154 template<size_t kAlignment>
SweepWalk(const SpaceBitmap<kAlignment> & live_bitmap,const SpaceBitmap<kAlignment> & mark_bitmap,uintptr_t sweep_begin,uintptr_t sweep_end,SpaceBitmap::SweepCallback * callback,void * arg)155 void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap,
156 const SpaceBitmap<kAlignment>& mark_bitmap,
157 uintptr_t sweep_begin, uintptr_t sweep_end,
158 SpaceBitmap::SweepCallback* callback, void* arg) {
159 CHECK(live_bitmap.bitmap_begin_ != nullptr);
160 CHECK(mark_bitmap.bitmap_begin_ != nullptr);
161 CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
162 CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
163 CHECK(callback != nullptr);
164 CHECK_LE(sweep_begin, sweep_end);
165 CHECK_GE(sweep_begin, live_bitmap.heap_begin_);
166
167 if (sweep_end <= sweep_begin) {
168 return;
169 }
170
171 size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT;
172 Atomic<uintptr_t>* live = live_bitmap.bitmap_begin_;
173 Atomic<uintptr_t>* mark = mark_bitmap.bitmap_begin_;
174 const size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
175 const size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
176 CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t));
177
178 if (Runtime::Current()->IsRunningOnMemoryTool()) {
179 // For memory tool, make the buffer large enough to hold all allocations. This is done since
180 // we get the size of objects (and hence read the class) inside of the freeing logic. This can
181 // cause crashes for unloaded classes since the class may get zeroed out before it is read.
182 // See b/131542326
183 for (size_t i = start; i <= end; i++) {
184 uintptr_t garbage =
185 live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
186 buffer_size += POPCOUNT(garbage);
187 }
188 }
189 std::vector<mirror::Object*> pointer_buf(buffer_size);
190 mirror::Object** cur_pointer = &pointer_buf[0];
191 mirror::Object** pointer_end = cur_pointer + (buffer_size - kBitsPerIntPtrT);
192
193 for (size_t i = start; i <= end; i++) {
194 uintptr_t garbage =
195 live[i].load(std::memory_order_relaxed) & ~mark[i].load(std::memory_order_relaxed);
196 if (UNLIKELY(garbage != 0)) {
197 uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
198 do {
199 const size_t shift = CTZ(garbage);
200 garbage ^= (static_cast<uintptr_t>(1)) << shift;
201 *cur_pointer++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
202 } while (garbage != 0);
203 // Make sure that there are always enough slots available for an
204 // entire word of one bits.
205 if (cur_pointer >= pointer_end) {
206 (*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
207 cur_pointer = &pointer_buf[0];
208 }
209 }
210 }
211 if (cur_pointer > &pointer_buf[0]) {
212 (*callback)(cur_pointer - &pointer_buf[0], &pointer_buf[0], arg);
213 }
214 }
215
216 template class SpaceBitmap<kObjectAlignment>;
217 template class SpaceBitmap<kPageSize>;
218
219 } // namespace accounting
220 } // namespace gc
221 } // namespace art
222