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