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