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 "Dalvik.h" 18 #include "HeapBitmap.h" 19 #include <sys/mman.h> /* for PROT_* */ 20 21 /* 22 * Initialize a HeapBitmap so that it points to a bitmap large 23 * enough to cover a heap at <base> of <maxSize> bytes, where 24 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 25 */ 26 bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 27 const char *name) 28 { 29 void *bits; 30 size_t bitsLen; 31 32 assert(hb != NULL); 33 assert(name != NULL); 34 bitsLen = HB_OFFSET_TO_INDEX(maxSize) * sizeof(*hb->bits); 35 bits = dvmAllocRegion(bitsLen, PROT_READ | PROT_WRITE, name); 36 if (bits == NULL) { 37 ALOGE("Could not mmap %zd-byte ashmem region '%s'", bitsLen, name); 38 return false; 39 } 40 hb->bits = (unsigned long *)bits; 41 hb->bitsLen = hb->allocLen = bitsLen; 42 hb->base = (uintptr_t)base; 43 hb->max = hb->base - 1; 44 return true; 45 } 46 47 /* 48 * Clean up any resources associated with the bitmap. 49 */ 50 void dvmHeapBitmapDelete(HeapBitmap *hb) 51 { 52 assert(hb != NULL); 53 54 if (hb->bits != NULL) { 55 munmap((char *)hb->bits, hb->allocLen); 56 } 57 memset(hb, 0, sizeof(*hb)); 58 } 59 60 /* 61 * Fill the bitmap with zeroes. Returns the bitmap's memory to 62 * the system as a side-effect. 63 */ 64 void dvmHeapBitmapZero(HeapBitmap *hb) 65 { 66 assert(hb != NULL); 67 68 if (hb->bits != NULL) { 69 /* This returns the memory to the system. 70 * Successive page faults will return zeroed memory. 71 */ 72 madvise(hb->bits, hb->bitsLen, MADV_DONTNEED); 73 hb->max = hb->base - 1; 74 } 75 } 76 77 /* 78 * Return true iff <obj> is within the range of pointers that this 79 * bitmap could potentially cover, even if a bit has not been set 80 * for it. 81 */ 82 bool dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj) 83 { 84 assert(hb != NULL); 85 if (obj != NULL) { 86 const uintptr_t offset = (uintptr_t)obj - hb->base; 87 const size_t index = HB_OFFSET_TO_INDEX(offset); 88 return index < hb->bitsLen / sizeof(*hb->bits); 89 } 90 return false; 91 } 92 93 /* 94 * Visits set bits in address order. The callback is not permitted to 95 * change the bitmap bits or max during the traversal. 96 */ 97 void dvmHeapBitmapWalk(const HeapBitmap *bitmap, BitmapCallback *callback, 98 void *arg) 99 { 100 assert(bitmap != NULL); 101 assert(bitmap->bits != NULL); 102 assert(callback != NULL); 103 uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 104 for (uintptr_t i = 0; i <= end; ++i) { 105 unsigned long word = bitmap->bits[i]; 106 if (UNLIKELY(word != 0)) { 107 unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); 108 uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base; 109 while (word != 0) { 110 const int shift = CLZ(word); 111 Object* obj = (Object *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); 112 (*callback)(obj, arg); 113 word &= ~(highBit >> shift); 114 } 115 } 116 } 117 } 118 119 /* 120 * Similar to dvmHeapBitmapWalk but the callback routine is permitted 121 * to change the bitmap bits and max during traversal. Used by the 122 * the root marking scan exclusively. 123 * 124 * The callback is invoked with a finger argument. The finger is a 125 * pointer to an address not yet visited by the traversal. If the 126 * callback sets a bit for an address at or above the finger, this 127 * address will be visited by the traversal. If the callback sets a 128 * bit for an address below the finger, this address will not be 129 * visited. 130 */ 131 void dvmHeapBitmapScanWalk(HeapBitmap *bitmap, 132 BitmapScanCallback *callback, void *arg) 133 { 134 assert(bitmap != NULL); 135 assert(bitmap->bits != NULL); 136 assert(callback != NULL); 137 uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 138 uintptr_t i; 139 for (i = 0; i <= end; ++i) { 140 unsigned long word = bitmap->bits[i]; 141 if (UNLIKELY(word != 0)) { 142 unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); 143 uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base; 144 void *finger = (void *)(HB_INDEX_TO_OFFSET(i + 1) + bitmap->base); 145 while (word != 0) { 146 const int shift = CLZ(word); 147 Object *obj = (Object *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); 148 (*callback)(obj, finger, arg); 149 word &= ~(highBit >> shift); 150 } 151 end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base); 152 } 153 } 154 } 155 156 /* 157 * Walk through the bitmaps in increasing address order, and find the 158 * object pointers that correspond to garbage objects. Call 159 * <callback> zero or more times with lists of these object pointers. 160 * 161 * The callback is not permitted to increase the max of either bitmap. 162 */ 163 void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb, 164 uintptr_t base, uintptr_t max, 165 BitmapSweepCallback *callback, void *callbackArg) 166 { 167 assert(liveHb != NULL); 168 assert(liveHb->bits != NULL); 169 assert(markHb != NULL); 170 assert(markHb->bits != NULL); 171 assert(liveHb->base == markHb->base); 172 assert(liveHb->bitsLen == markHb->bitsLen); 173 assert(callback != NULL); 174 assert(base <= max); 175 assert(base >= liveHb->base); 176 assert(max <= liveHb->max); 177 if (liveHb->max < liveHb->base) { 178 /* Easy case; both are obviously empty. 179 */ 180 return; 181 } 182 void *pointerBuf[4 * HB_BITS_PER_WORD]; 183 void **pb = pointerBuf; 184 size_t start = HB_OFFSET_TO_INDEX(base - liveHb->base); 185 size_t end = HB_OFFSET_TO_INDEX(max - liveHb->base); 186 unsigned long *live = liveHb->bits; 187 unsigned long *mark = markHb->bits; 188 for (size_t i = start; i <= end; i++) { 189 unsigned long garbage = live[i] & ~mark[i]; 190 if (UNLIKELY(garbage != 0)) { 191 unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1); 192 uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + liveHb->base; 193 while (garbage != 0) { 194 int shift = CLZ(garbage); 195 garbage &= ~(highBit >> shift); 196 *pb++ = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT); 197 } 198 /* Make sure that there are always enough slots available */ 199 /* for an entire word of 1s. */ 200 if (pb >= &pointerBuf[NELEM(pointerBuf) - HB_BITS_PER_WORD]) { 201 (*callback)(pb - pointerBuf, pointerBuf, callbackArg); 202 pb = pointerBuf; 203 } 204 } 205 } 206 if (pb > pointerBuf) { 207 (*callback)(pb - pointerBuf, pointerBuf, callbackArg); 208 } 209 } 210
