Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 1 | // Copyright (C) 2008 The Android Open Source Project |
| 2 | // |
| 3 | // Licensed under the Apache License, Version 2.0 (the "License"); |
| 4 | // you may not use this file except in compliance with the License. |
| 5 | // You may obtain a copy of the License at |
| 6 | // |
| 7 | // http://www.apache.org/licenses/LICENSE-2.0 |
| 8 | // |
| 9 | // Unless required by applicable law or agreed to in writing, software |
| 10 | // distributed under the License is distributed on an "AS IS" BASIS, |
| 11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| 12 | // See the License for the specific language governing permissions and |
| 13 | // limitations under the License. |
| 14 | |
Brian Carlstrom | 578bbdc | 2011-07-21 14:07:47 -0700 | [diff] [blame] | 15 | #include "object_bitmap.h" |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 16 | |
| 17 | #include <sys/mman.h> |
| 18 | |
Brian Carlstrom | 578bbdc | 2011-07-21 14:07:47 -0700 | [diff] [blame] | 19 | #include "logging.h" |
| 20 | #include "scoped_ptr.h" |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 21 | |
| 22 | namespace art { |
| 23 | |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 24 | HeapBitmap* HeapBitmap::Create(byte* base, size_t length) { |
| 25 | scoped_ptr<HeapBitmap> bitmap(new HeapBitmap(base, length)); |
| 26 | if (!bitmap->Init(base, length)) { |
| 27 | return NULL; |
| 28 | } else { |
| 29 | return bitmap.release(); |
| 30 | } |
| 31 | } |
| 32 | |
| 33 | // Initialize a HeapBitmap so that it points to a bitmap large enough |
| 34 | // to cover a heap at <base> of <maxSize> bytes, where objects are |
| 35 | // guaranteed to be kAlignment-aligned. |
| 36 | bool HeapBitmap::Init(const byte* base, size_t max_size) { |
| 37 | CHECK(base != NULL); |
| 38 | size_t length = HB_OFFSET_TO_INDEX(max_size) * kWordSize; |
Brian Carlstrom | 4a289ed | 2011-08-16 17:17:49 -0700 | [diff] [blame] | 39 | mem_map_.reset(MemMap::Map(length, PROT_READ | PROT_WRITE)); |
Brian Carlstrom | db4d540 | 2011-08-09 12:18:28 -0700 | [diff] [blame] | 40 | if (mem_map_ == NULL) { |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 41 | return false; |
| 42 | } |
Brian Carlstrom | db4d540 | 2011-08-09 12:18:28 -0700 | [diff] [blame] | 43 | words_ = reinterpret_cast<word*>(mem_map_->GetAddress()); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 44 | num_bytes_ = length; |
| 45 | base_ = reinterpret_cast<uintptr_t>(base); |
| 46 | max_ = base_ - 1; |
| 47 | return true; |
| 48 | } |
| 49 | |
| 50 | // Clean up any resources associated with the bitmap. |
Brian Carlstrom | db4d540 | 2011-08-09 12:18:28 -0700 | [diff] [blame] | 51 | HeapBitmap::~HeapBitmap() {} |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 52 | |
| 53 | // Fill the bitmap with zeroes. Returns the bitmap's memory to the |
| 54 | // system as a side-effect. |
| 55 | void HeapBitmap::Clear() { |
| 56 | if (words_ != NULL) { |
| 57 | // This returns the memory to the system. Successive page faults |
| 58 | // will return zeroed memory. |
| 59 | int result = madvise(words_, num_bytes_, MADV_DONTNEED); |
| 60 | if (result == -1) { |
| 61 | PLOG(WARNING) << "madvise failed"; |
| 62 | } |
| 63 | max_ = base_ - 1; |
| 64 | } |
| 65 | } |
| 66 | |
| 67 | // Return true iff <obj> is within the range of pointers that this |
| 68 | // bitmap could potentially cover, even if a bit has not been set for |
| 69 | // it. |
| 70 | bool HeapBitmap::HasAddress(const void* obj) const { |
| 71 | if (obj != NULL) { |
| 72 | const uintptr_t offset = (uintptr_t)obj - base_; |
| 73 | const size_t index = HB_OFFSET_TO_INDEX(offset); |
| 74 | return index < num_bytes_ / kWordSize; |
| 75 | } |
| 76 | return false; |
| 77 | } |
| 78 | |
| 79 | // Visits set bits in address order. The callback is not permitted to |
| 80 | // change the bitmap bits or max during the traversal. |
| 81 | void HeapBitmap::Walk(HeapBitmap::Callback* callback, void* arg) { |
| 82 | CHECK(words_ != NULL); |
| 83 | CHECK(callback != NULL); |
| 84 | uintptr_t end = HB_OFFSET_TO_INDEX(max_ - base_); |
| 85 | for (uintptr_t i = 0; i <= end; ++i) { |
| 86 | unsigned long word = words_[i]; |
| 87 | if (word != 0) { |
| 88 | unsigned long high_bit = 1 << (kBitsPerWord - 1); |
| 89 | uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + base_; |
| 90 | while (word != 0) { |
| 91 | const int shift = CLZ(word); |
Brian Carlstrom | 4873d46 | 2011-08-21 15:23:39 -0700 | [diff] [blame^] | 92 | Object* obj = (Object*) (ptr_base + shift * kAlignment); |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 93 | (*callback)(obj, arg); |
| 94 | word &= ~(high_bit >> shift); |
| 95 | } |
| 96 | } |
| 97 | } |
| 98 | } |
| 99 | |
| 100 | // Similar to Walk but the callback routine is permitted to change the |
| 101 | // bitmap bits and max during traversal. Used by the the root marking |
| 102 | // scan exclusively. |
| 103 | // |
| 104 | // The callback is invoked with a finger argument. The finger is a |
| 105 | // pointer to an address not yet visited by the traversal. If the |
| 106 | // callback sets a bit for an address at or above the finger, this |
| 107 | // address will be visited by the traversal. If the callback sets a |
| 108 | // bit for an address below the finger, this address will not be |
| 109 | // visited. |
| 110 | void HeapBitmap::ScanWalk(uintptr_t base, uintptr_t max, |
| 111 | ScanCallback* callback, void* arg) { |
| 112 | CHECK(words_ != NULL); |
| 113 | CHECK(callback != NULL); |
| 114 | CHECK(base <= max); |
| 115 | CHECK(base >= base_); |
| 116 | CHECK(max <= max_); |
| 117 | uintptr_t end = HB_OFFSET_TO_INDEX(max - base); |
| 118 | for (uintptr_t i = 0; i <= end; ++i) { |
| 119 | unsigned long word = words_[i]; |
| 120 | if (word != 0) { |
| 121 | unsigned long high_bit = 1 << (kBitsPerWord - 1); |
| 122 | uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + base_; |
| 123 | void* finger = (void*)(HB_INDEX_TO_OFFSET(i + 1) + base_); |
| 124 | while (word != 0) { |
| 125 | const int shift = CLZ(word); |
| 126 | Object* obj = (Object*)(ptr_base + shift * kAlignment); |
| 127 | (*callback)(obj, finger, arg); |
| 128 | word &= ~(high_bit >> shift); |
| 129 | } |
| 130 | end = HB_OFFSET_TO_INDEX(max_ - base_); |
| 131 | } |
| 132 | } |
| 133 | } |
| 134 | |
| 135 | // Walk through the bitmaps in increasing address order, and find the |
| 136 | // object pointers that correspond to garbage objects. Call |
| 137 | // <callback> zero or more times with lists of these object pointers. |
| 138 | // |
| 139 | // The callback is not permitted to increase the max of either bitmap. |
| 140 | void HeapBitmap::SweepWalk(const HeapBitmap& live_bitmap, |
| 141 | const HeapBitmap& mark_bitmap, |
| 142 | uintptr_t base, uintptr_t max, |
| 143 | HeapBitmap::SweepCallback* callback, void* arg) { |
| 144 | CHECK(live_bitmap.words_ != NULL); |
| 145 | CHECK(mark_bitmap.words_ != NULL); |
| 146 | CHECK(live_bitmap.base_ == mark_bitmap.base_); |
| 147 | CHECK(live_bitmap.num_bytes_ == mark_bitmap.num_bytes_); |
| 148 | CHECK(callback != NULL); |
| 149 | CHECK(base <= max); |
| 150 | CHECK(base >= live_bitmap.base_); |
| 151 | CHECK(max <= live_bitmap.max_); |
| 152 | if (live_bitmap.max_ < live_bitmap.base_) { |
| 153 | // Easy case; both are obviously empty. |
| 154 | // TODO: this should never happen |
| 155 | return; |
| 156 | } |
| 157 | void* pointer_buf[4 * kBitsPerWord]; |
| 158 | void** pb = pointer_buf; |
| 159 | size_t start = HB_OFFSET_TO_INDEX(base - live_bitmap.base_); |
| 160 | size_t end = HB_OFFSET_TO_INDEX(max - live_bitmap.base_); |
Brian Carlstrom | db4d540 | 2011-08-09 12:18:28 -0700 | [diff] [blame] | 161 | word* live = live_bitmap.words_; |
| 162 | word* mark = mark_bitmap.words_; |
Carl Shapiro | 69759ea | 2011-07-21 18:13:35 -0700 | [diff] [blame] | 163 | for (size_t i = start; i <= end; i++) { |
| 164 | unsigned long garbage = live[i] & ~mark[i]; |
| 165 | if (garbage != 0) { |
| 166 | unsigned long high_bit = 1 << (kBitsPerWord - 1); |
| 167 | uintptr_t ptr_base = HB_INDEX_TO_OFFSET(i) + live_bitmap.base_; |
| 168 | while (garbage != 0) { |
| 169 | int shift = CLZ(garbage); |
| 170 | garbage &= ~(high_bit >> shift); |
| 171 | *pb++ = (void*)(ptr_base + shift * kAlignment); |
| 172 | } |
| 173 | // Make sure that there are always enough slots available for an |
| 174 | // entire word of one bits. |
| 175 | if (pb >= &pointer_buf[ARRAYSIZE_UNSAFE(pointer_buf) - kBitsPerWord]) { |
| 176 | (*callback)(pb - pointer_buf, pointer_buf, arg); |
| 177 | pb = pointer_buf; |
| 178 | } |
| 179 | } |
| 180 | } |
| 181 | if (pb > pointer_buf) { |
| 182 | (*callback)(pb - pointer_buf, pointer_buf, arg); |
| 183 | } |
| 184 | } |
| 185 | |
| 186 | } // namespace art |