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
26namespace art {
27namespace gc {
28namespace accounting {
29
30template<size_t kAlignment>
31size_t SpaceBitmap<kAlignment>::ComputeBitmapSize(uint64_t capacity) {
32  const uint64_t kBytesCoveredPerWord = kAlignment * kBitsPerWord;
33  return (RoundUp(capacity, kBytesCoveredPerWord) / kBytesCoveredPerWord) * kWordSize;
34}
35
36template<size_t kAlignment>
37SpaceBitmap<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
45template<size_t kAlignment>
46SpaceBitmap<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
55template<size_t kAlignment>
56SpaceBitmap<kAlignment>::~SpaceBitmap() {}
57
58template<size_t kAlignment>
59SpaceBitmap<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
73template<size_t kAlignment>
74void 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
84template<size_t kAlignment>
85std::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
90template<size_t kAlignment>
91void SpaceBitmap<kAlignment>::Clear() {
92  if (bitmap_begin_ != nullptr) {
93    mem_map_->MadviseDontNeedAndZero();
94  }
95}
96
97template<size_t kAlignment>
98void 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
103template<size_t kAlignment>
104void 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
124template<size_t kAlignment>
125void 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
180template<size_t kAlignment>
181void 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
205template<size_t kAlignment>
206void 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
245template<size_t kAlignment>
246void 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
268template class SpaceBitmap<kObjectAlignment>;
269template class SpaceBitmap<kPageSize>;
270
271}  // namespace accounting
272}  // namespace gc
273}  // namespace art
274