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 #ifndef DALVIK_HEAP_BITMAP_H_ 17 #define DALVIK_HEAP_BITMAP_H_ 18 19 #include <limits.h> 20 #include <stdint.h> 21 22 #define HB_OBJECT_ALIGNMENT 8 23 #define HB_BITS_PER_WORD (sizeof(unsigned long) * CHAR_BIT) 24 25 /* <offset> is the difference from .base to a pointer address. 26 * <index> is the index of .bits that contains the bit representing 27 * <offset>. 28 */ 29 #define HB_OFFSET_TO_INDEX(offset_) \ 30 ((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD) 31 #define HB_INDEX_TO_OFFSET(index_) \ 32 ((uintptr_t)(index_) * HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD) 33 34 #define HB_OFFSET_TO_BYTE_INDEX(offset_) \ 35 (HB_OFFSET_TO_INDEX(offset_) * sizeof(*((HeapBitmap *)0)->bits)) 36 37 /* Pack the bits in backwards so they come out in address order 38 * when using CLZ. 39 */ 40 #define HB_OFFSET_TO_MASK(offset_) \ 41 (1 << \ 42 (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD))) 43 44 struct HeapBitmap { 45 /* The bitmap data, which points to an mmap()ed area of zeroed 46 * anonymous memory. 47 */ 48 unsigned long *bits; 49 50 /* The size of the used memory pointed to by bits, in bytes. This 51 * value changes when the bitmap is shrunk. 52 */ 53 size_t bitsLen; 54 55 /* The real size of the memory pointed to by bits. This is the 56 * number of bytes we requested from the allocator and does not 57 * change. 58 */ 59 size_t allocLen; 60 61 /* The base address, which corresponds to the first bit in 62 * the bitmap. 63 */ 64 uintptr_t base; 65 66 /* The highest pointer value ever returned by an allocation 67 * from this heap. I.e., the highest address that may correspond 68 * to a set bit. If there are no bits set, (max < base). 69 */ 70 uintptr_t max; 71 }; 72 73 /* 74 * Callback types used by the walking routines. 75 */ 76 typedef void BitmapCallback(Object *obj, void *arg); 77 typedef void BitmapScanCallback(Object *obj, void *finger, void *arg); 78 typedef void BitmapSweepCallback(size_t numPtrs, void **ptrs, void *arg); 79 80 /* 81 * Initialize a HeapBitmap so that it points to a bitmap large 82 * enough to cover a heap at <base> of <maxSize> bytes, where 83 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned. 84 */ 85 bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize, 86 const char *name); 87 88 /* 89 * Clean up any resources associated with the bitmap. 90 */ 91 void dvmHeapBitmapDelete(HeapBitmap *hb); 92 93 /* 94 * Fill the bitmap with zeroes. Returns the bitmap's memory to 95 * the system as a side-effect. 96 */ 97 void dvmHeapBitmapZero(HeapBitmap *hb); 98 99 /* 100 * Returns true if the address range of the bitmap covers the object 101 * address. 102 */ 103 bool dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj); 104 105 /* 106 * Applies the callback function to each set address in the bitmap. 107 */ 108 void dvmHeapBitmapWalk(const HeapBitmap *bitmap, 109 BitmapCallback *callback, void *callbackArg); 110 111 /* 112 * Like dvmHeapBitmapWalk but takes a callback function with a finger 113 * address. 114 */ 115 void dvmHeapBitmapScanWalk(HeapBitmap *bitmap, 116 BitmapScanCallback *callback, void *arg); 117 118 /* 119 * Walk through the bitmaps in increasing address order, and find the 120 * object pointers that correspond to garbage objects. Call 121 * <callback> zero or more times with lists of these object pointers. 122 * 123 * The callback is not permitted to increase the max of either bitmap. 124 */ 125 void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb, 126 uintptr_t base, uintptr_t max, 127 BitmapSweepCallback *callback, void *callbackArg); 128 129 #endif // DALVIK_HEAP_BITMAP_H_ 130