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 "base/logging.h"
18#include "dex_file-inl.h"
19#include "heap_bitmap.h"
20#include "mirror/art_field-inl.h"
21#include "mirror/class-inl.h"
22#include "mirror/object-inl.h"
23#include "mirror/object_array-inl.h"
24#include "object_utils.h"
25#include "space_bitmap-inl.h"
26#include "UniquePtr.h"
27#include "utils.h"
28
29namespace art {
30namespace gc {
31namespace accounting {
32
33std::string SpaceBitmap::GetName() const {
34  return name_;
35}
36
37void SpaceBitmap::SetName(const std::string& name) {
38  name_ = name;
39}
40
41std::string SpaceBitmap::Dump() const {
42  return StringPrintf("%s: %p-%p", name_.c_str(),
43                      reinterpret_cast<void*>(HeapBegin()),
44                      reinterpret_cast<void*>(HeapLimit()));
45}
46
47void SpaceSetMap::Walk(SpaceBitmap::Callback* callback, void* arg) {
48  for (const mirror::Object* obj : contained_) {
49    callback(const_cast<mirror::Object*>(obj), arg);
50  }
51}
52
53SpaceBitmap* SpaceBitmap::CreateFromMemMap(const std::string& name, MemMap* mem_map,
54                                           byte* heap_begin, size_t heap_capacity) {
55  CHECK(mem_map != nullptr);
56  word* bitmap_begin = reinterpret_cast<word*>(mem_map->Begin());
57  size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize;
58  return new SpaceBitmap(name, mem_map, bitmap_begin, bitmap_size, heap_begin);
59}
60
61SpaceBitmap* SpaceBitmap::Create(const std::string& name, byte* heap_begin, size_t heap_capacity) {
62  CHECK(heap_begin != NULL);
63  // Round up since heap_capacity is not necessarily a multiple of kAlignment * kBitsPerWord.
64  size_t bitmap_size = OffsetToIndex(RoundUp(heap_capacity, kAlignment * kBitsPerWord)) * kWordSize;
65  UniquePtr<MemMap> mem_map(MemMap::MapAnonymous(name.c_str(), NULL, bitmap_size, PROT_READ | PROT_WRITE));
66  if (mem_map.get() == NULL) {
67    LOG(ERROR) << "Failed to allocate bitmap " << name;
68    return NULL;
69  }
70  return CreateFromMemMap(name, mem_map.release(), heap_begin, heap_capacity);
71}
72
73// Clean up any resources associated with the bitmap.
74SpaceBitmap::~SpaceBitmap() {}
75
76void SpaceBitmap::SetHeapLimit(uintptr_t new_end) {
77  DCHECK(IsAligned<kBitsPerWord * kAlignment>(new_end));
78  size_t new_size = OffsetToIndex(new_end - heap_begin_) * kWordSize;
79  if (new_size < bitmap_size_) {
80    bitmap_size_ = new_size;
81  }
82  // Not sure if doing this trim is necessary, since nothing past the end of the heap capacity
83  // should be marked.
84}
85
86void SpaceBitmap::Clear() {
87  if (bitmap_begin_ != NULL) {
88    // This returns the memory to the system.  Successive page faults will return zeroed memory.
89    int result = madvise(bitmap_begin_, bitmap_size_, MADV_DONTNEED);
90    if (result == -1) {
91      PLOG(FATAL) << "madvise failed";
92    }
93  }
94}
95
96void SpaceBitmap::CopyFrom(SpaceBitmap* source_bitmap) {
97  DCHECK_EQ(Size(), source_bitmap->Size());
98  std::copy(source_bitmap->Begin(), source_bitmap->Begin() + source_bitmap->Size() / kWordSize, Begin());
99}
100
101// Visits set bits in address order.  The callback is not permitted to
102// change the bitmap bits or max during the traversal.
103void SpaceBitmap::Walk(SpaceBitmap::Callback* callback, void* arg) {
104  CHECK(bitmap_begin_ != NULL);
105  CHECK(callback != NULL);
106
107  uintptr_t end = OffsetToIndex(HeapLimit() - heap_begin_ - 1);
108  word* bitmap_begin = bitmap_begin_;
109  for (uintptr_t i = 0; i <= end; ++i) {
110    word w = bitmap_begin[i];
111    if (w != 0) {
112      uintptr_t ptr_base = IndexToOffset(i) + heap_begin_;
113      do {
114        const size_t shift = CLZ(w);
115        mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
116        (*callback)(obj, arg);
117        w ^= static_cast<size_t>(kWordHighBitMask) >> shift;
118      } while (w != 0);
119    }
120  }
121}
122
123// Walk through the bitmaps in increasing address order, and find the
124// object pointers that correspond to garbage objects.  Call
125// <callback> zero or more times with lists of these object pointers.
126//
127// The callback is not permitted to increase the max of either bitmap.
128void SpaceBitmap::SweepWalk(const SpaceBitmap& live_bitmap,
129                           const SpaceBitmap& mark_bitmap,
130                           uintptr_t sweep_begin, uintptr_t sweep_end,
131                           SpaceBitmap::SweepCallback* callback, void* arg) {
132  CHECK(live_bitmap.bitmap_begin_ != NULL);
133  CHECK(mark_bitmap.bitmap_begin_ != NULL);
134  CHECK_EQ(live_bitmap.heap_begin_, mark_bitmap.heap_begin_);
135  CHECK_EQ(live_bitmap.bitmap_size_, mark_bitmap.bitmap_size_);
136  CHECK(callback != NULL);
137  CHECK_LE(sweep_begin, sweep_end);
138  CHECK_GE(sweep_begin, live_bitmap.heap_begin_);
139
140  if (sweep_end <= sweep_begin) {
141    return;
142  }
143
144  // TODO: rewrite the callbacks to accept a std::vector<mirror::Object*> rather than a mirror::Object**?
145  const size_t buffer_size = kWordSize * kBitsPerWord;
146  mirror::Object* pointer_buf[buffer_size];
147  mirror::Object** pb = &pointer_buf[0];
148  size_t start = OffsetToIndex(sweep_begin - live_bitmap.heap_begin_);
149  size_t end = OffsetToIndex(sweep_end - live_bitmap.heap_begin_ - 1);
150  CHECK_LT(end, live_bitmap.Size() / kWordSize);
151  word* live = live_bitmap.bitmap_begin_;
152  word* mark = mark_bitmap.bitmap_begin_;
153  for (size_t i = start; i <= end; i++) {
154    word garbage = live[i] & ~mark[i];
155    if (UNLIKELY(garbage != 0)) {
156      uintptr_t ptr_base = IndexToOffset(i) + live_bitmap.heap_begin_;
157      do {
158        const size_t shift = CLZ(garbage);
159        garbage ^= static_cast<size_t>(kWordHighBitMask) >> shift;
160        *pb++ = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
161      } while (garbage != 0);
162      // Make sure that there are always enough slots available for an
163      // entire word of one bits.
164      if (pb >= &pointer_buf[buffer_size - kBitsPerWord]) {
165        (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
166        pb = &pointer_buf[0];
167      }
168    }
169  }
170  if (pb > &pointer_buf[0]) {
171    (*callback)(pb - &pointer_buf[0], &pointer_buf[0], arg);
172  }
173}
174
175static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj,
176                              void* arg);
177
178// Walk instance fields of the given Class. Separate function to allow recursion on the super
179// class.
180static void WalkInstanceFields(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj,
181                               mirror::Class* klass, void* arg)
182    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
183  // Visit fields of parent classes first.
184  mirror::Class* super = klass->GetSuperClass();
185  if (super != NULL) {
186    WalkInstanceFields(visited, callback, obj, super, arg);
187  }
188  // Walk instance fields
189  mirror::ObjectArray<mirror::ArtField>* fields = klass->GetIFields();
190  if (fields != NULL) {
191    for (int32_t i = 0; i < fields->GetLength(); i++) {
192      mirror::ArtField* field = fields->Get(i);
193      FieldHelper fh(field);
194      if (!fh.IsPrimitiveType()) {
195        mirror::Object* value = field->GetObj(obj);
196        if (value != NULL) {
197          WalkFieldsInOrder(visited, callback, value,  arg);
198        }
199      }
200    }
201  }
202}
203
204// For an unvisited object, visit it then all its children found via fields.
205static void WalkFieldsInOrder(SpaceBitmap* visited, SpaceBitmap::Callback* callback, mirror::Object* obj,
206                              void* arg)
207    SHARED_LOCKS_REQUIRED(Locks::mutator_lock_) {
208  if (visited->Test(obj)) {
209    return;
210  }
211  // visit the object itself
212  (*callback)(obj, arg);
213  visited->Set(obj);
214  // Walk instance fields of all objects
215  mirror::Class* klass = obj->GetClass();
216  WalkInstanceFields(visited, callback, obj, klass, arg);
217  // Walk static fields of a Class
218  if (obj->IsClass()) {
219    mirror::ObjectArray<mirror::ArtField>* fields = klass->GetSFields();
220    if (fields != NULL) {
221      for (int32_t i = 0; i < fields->GetLength(); i++) {
222        mirror::ArtField* field = fields->Get(i);
223        FieldHelper fh(field);
224        if (!fh.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// Visits set bits with an in order traversal.  The callback is not permitted to change the bitmap
246// bits or max during the traversal.
247void SpaceBitmap::InOrderWalk(SpaceBitmap::Callback* callback, void* arg) {
248  UniquePtr<SpaceBitmap> visited(Create("bitmap for in-order walk",
249                                       reinterpret_cast<byte*>(heap_begin_),
250                                       IndexToOffset(bitmap_size_ / kWordSize)));
251  CHECK(bitmap_begin_ != NULL);
252  CHECK(callback != NULL);
253  uintptr_t end = Size() / kWordSize;
254  for (uintptr_t i = 0; i < end; ++i) {
255    word 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 = CLZ(w);
260        mirror::Object* obj = reinterpret_cast<mirror::Object*>(ptr_base + shift * kAlignment);
261        WalkFieldsInOrder(visited.get(), callback, obj, arg);
262        w ^= static_cast<size_t>(kWordHighBitMask) >> shift;
263      }
264    }
265  }
266}
267
268std::string SpaceSetMap::GetName() const {
269  return name_;
270}
271
272void SpaceSetMap::SetName(const std::string& name) {
273  name_ = name;
274}
275
276void SpaceSetMap::CopyFrom(const SpaceSetMap& space_set) {
277  contained_ = space_set.contained_;
278}
279
280std::ostream& operator << (std::ostream& stream, const SpaceBitmap& bitmap) {
281  return stream
282    << bitmap.GetName() << "["
283    << "begin=" << reinterpret_cast<const void*>(bitmap.HeapBegin())
284    << ",end=" << reinterpret_cast<const void*>(bitmap.HeapLimit())
285    << "]";
286}
287
288}  // namespace accounting
289}  // namespace gc
290}  // namespace art
291