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 "art_field-inl.h"
20 #include "base/stringprintf.h"
21 #include "dex_file-inl.h"
22 #include "mem_map.h"
23 #include "mirror/object-inl.h"
24 #include "mirror/class-inl.h"
25 #include "mirror/object_array.h"
26 
27 namespace art {
28 namespace gc {
29 namespace accounting {
30 
31 template<size_t kAlignment>
ComputeBitmapSize(uint64_t capacity)32 size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) {
33   const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerIntPtrT;
34   return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * sizeof(intptr_t);
35 }
36 
37 template<size_t kAlignment>
ComputeHeapSize(uint64_t bitmap_bytes)38 size_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) {
39   return bitmap_bytes * kBitsPerByte * kAlignment;
40 }
41 
42 template<size_t kAlignment>
CreateFromMemMap(const std::string & name,MemMap * mem_map,uint8_t * heap_begin,size_t heap_capacity)43 SpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::CreateFromMemMap(
44     const std::string& name, MemMap* mem_map, uint8_t* heap_begin, size_t heap_capacity) {
45   CHECK(mem_map != nullptr);
46   uintptr_t* bitmap_begin = reinterpret_cast<uintptr_t*>(mem_map->Begin());
47   const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
48   return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin);
49 }
50 
51 template<size_t kAlignment>
SpaceBitmap(const std::string & name,MemMap * mem_map,uintptr_t * bitmap_begin,size_t bitmap_size,const void * heap_begin)52 SpaceBitmap<kAlignment>::SpaceBitmap(const std::string& name, MemMap* mem_map, uintptr_t* bitmap_begin,
53                                      size_t bitmap_size, const void* heap_begin)
54     : mem_map_(mem_map), bitmap_begin_(bitmap_begin), bitmap_size_(bitmap_size),
55       heap_begin_(reinterpret_cast<uintptr_t>(heap_begin)),
56       name_(name) {
57   CHECK(bitmap_begin_ != nullptr);
58   CHECK_NE(bitmap_size, 0U);
59 }
60 
61 template<size_t kAlignment>
~SpaceBitmap()62 SpaceBitmap<kAlignment>::~SpaceBitmap() {}
63 
64 template<size_t kAlignment>
Create(const std::string & name,uint8_t * heap_begin,size_t heap_capacity)65 SpaceBitmap<kAlignment>* SpaceBitmap<kAlignment>::Create(
66     const std::string& name, uint8_t* heap_begin, size_t heap_capacity) {
67   // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord.
68   const size_t bitmap_size = ComputeBitmapSize(heap_capacity);
69   std::string error_msg;
70   std::unique_ptr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), nullptr, bitmap_size,
71                                                        PROT_READ | PROT_WRITE, false, false,
72                                                        &error_msg));
73   if (UNLIKELY(mem_map.get() == nullptr)) {
74     LOG(ERROR) << "Failed to allocate bitmap " << name << ": " << error_msg;
75     return nullptr;
76   }
77   return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity);
78 }
79 
80 template<size_t kAlignment>
SetHeapLimit(uintptr_t new_end)81 void SpaceBitmap<kAlignment>::SetHeapLimit(uintptr_t new_end) {
82   DCHECK(IsAligned<kBitsPerIntPtrT * kAlignment>(new_end));
83   size_t new_size = OffsetToIndex(new_end - heap_begin_) * sizeof(intptr_t);
84   if (new_size < bitmap_size_) {
85     bitmap_size_ = new_size;
86   }
87   // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
88   // should be marked.
89 }
90 
91 template<size_t kAlignment>
Dump() const92 std::string SpaceBitmap<kAlignment>::Dump() const {
93   return StringPrintf("%s: %p-%p", name_.c_str(), reinterpret_cast<void*>(HeapBegin()),
94                       reinterpret_cast<void*>(HeapLimit()));
95 }
96 
97 template<size_t kAlignment>
Clear()98 void SpaceBitmap<kAlignment>::Clear() {
99   if (bitmap_begin_ != nullptr) {
100     mem_map_->MadviseDontNeedAndZero();
101   }
102 }
103 
104 template<size_t kAlignment>
CopyFrom(SpaceBitmap * source_bitmap)105 void SpaceBitmap<kAlignment>::CopyFrom(SpaceBitmap* source_bitmap) {
106   DCHECK_EQ(Size(), source_bitmap->Size());
107   std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / sizeof(intptr_t), Begin());
108 }
109 
110 template<size_t kAlignment>
Walk(ObjectCallback * callback,void * arg)111 void SpaceBitmap<kAlignment>::Walk(ObjectCallback* callback, void* arg) {
112   CHECK(bitmap_begin_ != nullptr);
113   CHECK(callback != nullptr);
114 
115   uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1);
116   uintptr_t* bitmap_begin = bitmap_begin_;
117   for (uintptr_t i = 0; i <= end; ++i) {
118     uintptr_t w = bitmap_begin[i];
119     if (w != 0) {
120       uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
121       do {
122         const size_t shift = CTZ(w);
123         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
124         (*callback)(obj, arg);
125         w ^= (static_cast<uintptr_t>(1)) << shift;
126       } while (w != 0);
127     }
128   }
129 }
130 
131 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)132 void SpaceBitmap<kAlignment>::SweepWalk(const SpaceBitmap<kAlignment>& live_bitmap,
133                                         const SpaceBitmap<kAlignment>& mark_bitmap,
134                                         uintptr_t sweep_begin, uintptr_t sweep_end,
135                                         SpaceBitmap::SweepCallback* callback, void* arg) {
136   CHECK(live_bitmap.bitmap_begin_ != nullptr);
137   CHECK(mark_bitmap.bitmap_begin_ != nullptr);
138   CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
139   CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
140   CHECK(callback != nullptr);
141   CHECK_LE(sweep_begin, sweep_end);
142   CHECK_GE(sweep_begin, live_bitmap.heap_begin_);
143 
144   if (sweep_end <= sweep_begin) {
145     return;
146   }
147 
148   // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**?
149   constexpr size_t buffer_size = sizeof(intptr_t) * kBitsPerIntPtrT;
150 #ifdef __LP64__
151   // Heap-allocate for smaller stack frame.
152   std::unique_ptr<mirror::Object*[]> pointer_buf_ptr(new mirror::Object*[buffer_size]);
153   mirror::Object** pointer_buf = pointer_buf_ptr.get();
154 #else
155   // Stack-allocate buffer as it's small enough.
156   mirror::Object* pointer_buf[buffer_size];
157 #endif
158   mirror::Object** pb = &pointer_buf[0];
159 
160   size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
161   size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
162   CHECK_LT(end, live_bitmap.Size() / sizeof(intptr_t));
163   uintptr_t* live = live_bitmap.bitmap_begin_;
164   uintptr_t* mark = mark_bitmap.bitmap_begin_;
165   for (size_t i = start; i <= end; i++) {
166     uintptr_t garbage = live[i] & ~mark[i];
167     if (UNLIKELY(garbage != 0)) {
168       uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
169       do {
170         const size_t shift = CTZ(garbage);
171         garbage ^= (static_cast<uintptr_t>(1)) << shift;
172         *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
173       } while (garbage != 0);
174       // Make sure that there are always enough slots available for an
175       // entire word of one bits.
176       if (pb >= &pointer_buf[buffer_size - kBitsPerIntPtrT]) {
177         (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
178         pb = &pointer_buf[0];
179       }
180     }
181   }
182   if (pb > &pointer_buf[0]) {
183     (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
184   }
185 }
186 
187 template<size_t kAlignment>
WalkInstanceFields(SpaceBitmap<kAlignment> * visited,ObjectCallback * callback,mirror::Object * obj,mirror::Class * klass,void * arg)188 void SpaceBitmap<kAlignment>::WalkInstanceFields(SpaceBitmap<kAlignment>* visited,
189                                                  ObjectCallback* callback, mirror::Object* obj,
190                                                  mirror::Class* klass, void* arg)
191     SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
192   // Visit fields of parent classes first.
193   mirror::Class* super = klass->GetSuperClass();
194   if (super != nullptr) {
195     WalkInstanceFields(visited, callback, obj, super, arg);
196   }
197   // Walk instance fields
198   auto* fields = klass->GetIFields();
199   for (size_t i = 0, count = klass->NumInstanceFields(); i < count; ++i) {
200     ArtField* field = &fields[i];
201     if (!field->IsPrimitiveType()) {
202       mirror::Object* value = field->GetObj(obj);
203       if (value != nullptr) {
204         WalkFieldsInOrder(visited, callback, value, arg);
205       }
206     }
207   }
208 }
209 
210 template<size_t kAlignment>
WalkFieldsInOrder(SpaceBitmap<kAlignment> * visited,ObjectCallback * callback,mirror::Object * obj,void * arg)211 void SpaceBitmap<kAlignment>::WalkFieldsInOrder(SpaceBitmap<kAlignment>* visited,
212                                                 ObjectCallback* callback, mirror::Object* obj,
213                                                 void* arg) {
214   if (visited->Test(obj)) {
215     return;
216   }
217   // visit the object itself
218   (*callback)(obj, arg);
219   visited->Set(obj);
220   // Walk instance fields of all objects
221   mirror::Class* klass = obj->GetClass();
222   WalkInstanceFields(visited, callback, obj, klass, arg);
223   // Walk static fields of a Class
224   if (obj->IsClass()) {
225     auto* sfields = klass->GetSFields();
226     for (size_t i = 0, count = klass->NumStaticFields(); i < count; ++i) {
227       ArtField* field = &sfields[i];
228       if (!field->IsPrimitiveType()) {
229         mirror::Object* value = field->GetObj(nullptr);
230         if (value != nullptr) {
231           WalkFieldsInOrder(visited, callback, value, arg);
232         }
233       }
234     }
235   } else if (obj->IsObjectArray()) {
236     // Walk elements of an object array
237     mirror::ObjectArray<mirror::Object>* obj_array = obj->AsObjectArray<mirror::Object>();
238     int32_t length = obj_array->GetLength();
239     for (int32_t i = 0; i < length; i++) {
240       mirror::Object* value = obj_array->Get(i);
241       if (value != nullptr) {
242         WalkFieldsInOrder(visited, callback, value, arg);
243       }
244     }
245   }
246 }
247 
248 template<size_t kAlignment>
InOrderWalk(ObjectCallback * callback,void * arg)249 void SpaceBitmap<kAlignment>::InOrderWalk(ObjectCallback* callback, void* arg) {
250   std::unique_ptr<SpaceBitmap<kAlignment>> visited(
251       Create("bitmap for in-order walk", reinterpret_cast<uint8_t*>(heap_begin_),
252              IndexToOffset(bitmap_size_ / sizeof(intptr_t))));
253   CHECK(bitmap_begin_ != nullptr);
254   CHECK(callback != nullptr);
255   uintptr_t end = Size() / sizeof(intptr_t);
256   for (uintptr_t i = 0; i < end; ++i) {
257     // Need uint for unsigned shift.
258     uintptr_t w = bitmap_begin_[i];
259     if (UNLIKELY(w != 0)) {
260       uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
261       while (w != 0) {
262         const size_t shift = CTZ(w);
263         mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
264         WalkFieldsInOrder(visited.get(), callback, obj, arg);
265         w ^= (static_cast<uintptr_t>(1)) << shift;
266       }
267     }
268   }
269 }
270 
271 template class SpaceBitmap<kObjectAlignment>;
272 template class SpaceBitmap<kPageSize>;
273 
274 }  // namespace accounting
275 }  // namespace gc
276 }  // namespace art
277