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 "dex/dex_file-inl.h"
23 #include "mem_map.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 != nullptr);
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(name, 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_(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 std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size,
87 PROT_READ | PROT_WRITE, false, false,
88 &error_msg));
89 if (UNLIKELY(mem_map.get() == nullptr)) {
90 LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
91 return nullptr;
92 }
93 return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity);
94 }
95
96 template<size_t kAlignment>
SetHeapLimit(uintptr_t new_end)97 void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) {
98 DCHECK_ALIGNED(new_end, kBitsPerIntPtrT * kAlignment);
99 size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t);
100 if (new_size < bitmap_size_) {
101 bitmap_size_ = new_size;
102 }
103 heap_limit_ = new_end;
104 // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
105 // should be marked.
106 }
107
108 template<size_t kAlignment>
Dump() const109 std::string SpaceBitmap<kAlignment>::Dump() const {
110 return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()),
111 reinterpret_cast<void*>(HeapLimit()));
112 }
113
114 template<size_t kAlignment>
Clear()115 void SpaceBitmap<kAlignment>::Clear() {
116 if (bitmap_begin_ != nullptr) {
117 mem_map_->MadviseDontNeedAndZero();
118 }
119 }
120
121 template<size_t kAlignment>
ClearRange(const mirror::Object * begin,const mirror::Object * end)122 void SpaceBitmap<kAlignment>::ClearRange(const mirror::Object* begin, const mirror::Object* end) {
123 uintptr_t begin_offset = reinterpret_cast<uintptr_t>(begin) - heap_begin_;
124 uintptr_t end_offset = reinterpret_cast<uintptr_t>(end) - heap_begin_;
125 // Align begin and end to bitmap word boundaries.
126 while (begin_offset < end_offset && OffsetBitIndex(begin_offset) != 0) {
127 Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + begin_offset));
128 begin_offset += kAlignment;
129 }
130 while (begin_offset < end_offset && OffsetBitIndex(end_offset) != 0) {
131 end_offset -= kAlignment;
132 Clear(reinterpret_cast<mirror::Object*>(heap_begin_ + end_offset));
133 }
134 // Bitmap word boundaries.
135 const uintptr_t start_index = OffsetToIndex(begin_offset);
136 const uintptr_t end_index = OffsetToIndex(end_offset);
137 ZeroAndReleasePages(reinterpret_cast<uint8_t*>(&bitmap_begin_[start_index]),
138 (end_index - start_index) * sizeof(*bitmap_begin_));
139 }
140
141 template<size_t kAlignment>
CopyFrom(SpaceBitmap * source_bitmap)142 void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) {
143 DCHECK_EQ(Size(), source_bitmap->Size());
144 const size_t count = source_bitmap->Size() / sizeof(intptr_t);
145 Atomic<uintptr_t>* const src = source_bitmap->Begin();
146 Atomic<uintptr_t>* const dest = Begin();
147 for (size_t i = 0; i < count; ++i) {
148 dest[i].StoreRelaxed(src[i].LoadRelaxed());
149 }
150 }
151
152 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)153 void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap,
154 const SpaceBitmap<kAlignment>& mark_bitmap,
155 uintptr_t sweep_begin, uintptr_t sweep_end,
156 SpaceBitmap::SweepCallback* callback, void* arg) {
157 CHECK(live_bitmap.bitmap_begin_ != nullptr);
158 CHECK(mark_bitmap.bitmap_begin_ != nullptr);
159 CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
160 CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
161 CHECK(callback != nullptr);
162 CHECK_LE(sweep_begin, sweep_end);
163 CHECK_GE(sweep_begin, live_bitmap.heap_begin_);
164
165 if (sweep_end <= sweep_begin) {
166 return;
167 }
168
169 // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**?
170 constexpr size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT;
171 #ifdef __LP64__
172 // Heap-allocate for smaller stack frame.
173 std::unique_ptr<mirror::Object*[]> pointer_buf_ptr(new mirror::Object*[buffer_size]);
174 mirror::Object** pointer_buf = pointer_buf_ptr.get();
175 #else
176 // Stack-allocate buffer as it's small enough.
177 mirror::Object* pointer_buf[buffer_size];
178 #endif
179 mirror::Object** pb = &pointer_buf[0];
180
181 size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
182 size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
183 CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t));
184 Atomic<uintptr_t>* live = live_bitmap.bitmap_begin_;
185 Atomic<uintptr_t>* mark = mark_bitmap.bitmap_begin_;
186 for (size_t i = start; i <= end; i++) {
187 uintptr_t garbage = live[i].LoadRelaxed() & ~mark[i].LoadRelaxed();
188 if (UNLIKELY(garbage != 0)) {
189 uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
190 do {
191 const size_t shift = CTZ(garbage);
192 garbage ^= (static_cast<uintptr_t>(1)) << shift;
193 *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
194 } while (garbage != 0);
195 // Make sure that there are always enough slots available for an
196 // entire word of one bits.
197 if (pb >= &pointer_buf[buffer_size - kBitsPerIntPtrT]) {
198 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
199 pb = &pointer_buf[0];
200 }
201 }
202 }
203 if (pb > &pointer_buf[0]) {
204 (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
205 }
206 }
207
208 template class SpaceBitmap<kObjectAlignment>;
209 template class SpaceBitmap<kPageSize>;
210
211 } // namespace accounting
212 } // namespace gc
213 } // namespace art
214