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
27namespace art {
28namespace gc {
29namespace accounting {
30
31template<size_t kAlignment>
32size_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
37template<size_t kAlignment>
38size_t SpaceBitmap<kAlignment>::ComputeHeapSize(uint64_t bitmap_bytes) {
39  return bitmap_bytes * kBitsPerByte * kAlignment;
40}
41
42template<size_t kAlignment>
43SpaceBitmap<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
51template<size_t kAlignment>
52SpaceBitmap<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
61template<size_t kAlignment>
62SpaceBitmap<kAlignment>::~SpaceBitmap() {}
63
64template<size_t kAlignment>
65SpaceBitmap<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
80template<size_t kAlignment>
81void 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
91template<size_t kAlignment>
92std::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
97template<size_t kAlignment>
98void SpaceBitmap<kAlignment>::Clear() {
99  if (bitmap_begin_ != nullptr) {
100    mem_map_->MadviseDontNeedAndZero();
101  }
102}
103
104template<size_t kAlignment>
105void 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
110template<size_t kAlignment>
111void 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
131template<size_t kAlignment>
132void 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
187template<size_t kAlignment>
188void 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
210template<size_t kAlignment>
211void 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
248template<size_t kAlignment>
249void 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
271template class SpaceBitmap<kObjectAlignment>;
272template class SpaceBitmap<kPageSize>;
273
274}  // namespace accounting
275}  // namespace gc
276}  // namespace art
277