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
17#define _DALVIK_HEAP_BITMAP
18
19#include <limits.h>
20#include <stdint.h>
21#include "clz.h"
22
23#define HB_OBJECT_ALIGNMENT 8
24#define HB_BITS_PER_WORD (sizeof(unsigned long) * CHAR_BIT)
25
26/* <offset> is the difference from .base to a pointer address.
27 * <index> is the index of .bits that contains the bit representing
28 *         <offset>.
29 */
30#define HB_OFFSET_TO_INDEX(offset_) \
31    ((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD)
32#define HB_INDEX_TO_OFFSET(index_) \
33    ((uintptr_t)(index_) * HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD)
34
35#define HB_OFFSET_TO_BYTE_INDEX(offset_) \
36  (HB_OFFSET_TO_INDEX(offset_) * sizeof(*((HeapBitmap *)0)->bits))
37
38/* Pack the bits in backwards so they come out in address order
39 * when using CLZ.
40 */
41#define HB_OFFSET_TO_MASK(offset_) \
42    (1 << \
43        (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD)))
44
45/* Return the maximum offset (exclusive) that <hb> can represent.
46 */
47#define HB_MAX_OFFSET(hb_) \
48    HB_INDEX_TO_OFFSET((hb_)->bitsLen / sizeof(*(hb_)->bits))
49
50#define HB_INLINE_PROTO(p) \
51    static inline p __attribute__((always_inline)); \
52    static inline p
53
54typedef struct {
55    /* The bitmap data, which points to an mmap()ed area of zeroed
56     * anonymous memory.
57     */
58    unsigned long *bits;
59
60    /* The size of the used memory pointed to by bits, in bytes.  This
61     * value changes when the bitmap is shrunk.
62     */
63    size_t bitsLen;
64
65    /* The real size of the memory pointed to by bits.  This is the
66     * number of bytes we requested from the allocator and does not
67     * change.
68     */
69    size_t allocLen;
70
71    /* The base address, which corresponds to the first bit in
72     * the bitmap.
73     */
74    uintptr_t base;
75
76    /* The highest pointer value ever returned by an allocation
77     * from this heap.  I.e., the highest address that may correspond
78     * to a set bit.  If there are no bits set, (max < base).
79     */
80    uintptr_t max;
81} HeapBitmap;
82
83typedef void BitmapCallback(void *addr, void *arg);
84typedef void BitmapScanCallback(void *addr, void *finger, void *arg);
85typedef void BitmapSweepCallback(size_t numPtrs, void **ptrs, void *arg);
86
87/*
88 * Initialize a HeapBitmap so that it points to a bitmap large
89 * enough to cover a heap at <base> of <maxSize> bytes, where
90 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned.
91 */
92bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize,
93        const char *name);
94
95/*
96 * Clean up any resources associated with the bitmap.
97 */
98void dvmHeapBitmapDelete(HeapBitmap *hb);
99
100/*
101 * Fill the bitmap with zeroes.  Returns the bitmap's memory to
102 * the system as a side-effect.
103 */
104void dvmHeapBitmapZero(HeapBitmap *hb);
105
106/*
107 * Visits set bits in address order.  The callback is not permitted to
108 * change the bitmap bits or max during the traversal.
109 */
110HB_INLINE_PROTO(
111    void
112    dvmHeapBitmapWalk(const HeapBitmap *bitmap,
113                      BitmapCallback *callback, void *arg)
114)
115{
116    assert(bitmap != NULL);
117    assert(bitmap->bits != NULL);
118    assert(callback != NULL);
119    uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
120    uintptr_t i;
121    for (i = 0; i <= end; ++i) {
122        unsigned long word = bitmap->bits[i];
123        if (UNLIKELY(word != 0)) {
124            unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
125            uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base;
126            while (word != 0) {
127                const int shift = CLZ(word);
128                void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
129                (*callback)(addr, arg);
130                word &= ~(highBit >> shift);
131            }
132        }
133    }
134}
135
136/*
137 * Similar to dvmHeapBitmapWalk but the callback routine is permitted
138 * to change the bitmap bits and max during traversal.  Used by the
139 * the root marking scan exclusively.
140 *
141 * The callback is invoked with a finger argument.  The finger is a
142 * pointer to an address not yet visited by the traversal.  If the
143 * callback sets a bit for an address at or above the finger, this
144 * address will be visited by the traversal.  If the callback sets a
145 * bit for an address below the finger, this address will not be
146 * visited.
147 */
148HB_INLINE_PROTO(
149    void
150    dvmHeapBitmapScanWalk(HeapBitmap *bitmap,
151                          BitmapScanCallback *callback, void *arg)
152)
153{
154    assert(bitmap != NULL);
155    assert(bitmap->bits != NULL);
156    assert(callback != NULL);
157    uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
158    uintptr_t i;
159    for (i = 0; i <= end; ++i) {
160        unsigned long word = bitmap->bits[i];
161        if (UNLIKELY(word != 0)) {
162            unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
163            uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base;
164            void *finger = (void *)(HB_INDEX_TO_OFFSET(i + 1) + bitmap->base);
165            while (word != 0) {
166                const int shift = CLZ(word);
167                void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
168                (*callback)(addr, finger, arg);
169                word &= ~(highBit >> shift);
170            }
171            end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
172        }
173    }
174}
175
176/*
177 * Walk through the bitmaps in increasing address order, and find the
178 * object pointers that correspond to garbage objects.  Call
179 * <callback> zero or more times with lists of these object pointers.
180 *
181 * The callback is permitted to increase the bitmap's max; the walk
182 * will use the updated max as a terminating condition.
183 */
184void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
185                            BitmapSweepCallback *callback, void *callbackArg);
186
187/*
188 * Return true iff <obj> is within the range of pointers that this
189 * bitmap could potentially cover, even if a bit has not been set
190 * for it.
191 */
192HB_INLINE_PROTO(
193    bool
194    dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj)
195)
196{
197    assert(hb != NULL);
198
199    if (obj != NULL) {
200        const uintptr_t offset = (uintptr_t)obj - hb->base;
201        const size_t index = HB_OFFSET_TO_INDEX(offset);
202        return index < hb->bitsLen / sizeof(*hb->bits);
203    }
204    return false;
205}
206
207/*
208 * Internal function; do not call directly.
209 */
210HB_INLINE_PROTO(
211    unsigned long
212    _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj,
213            bool setBit, bool returnOld)
214)
215{
216    const uintptr_t offset = (uintptr_t)obj - hb->base;
217    const size_t index = HB_OFFSET_TO_INDEX(offset);
218    const unsigned long mask = HB_OFFSET_TO_MASK(offset);
219
220    assert(hb->bits != NULL);
221    assert((uintptr_t)obj >= hb->base);
222    assert(index < hb->bitsLen / sizeof(*hb->bits));
223
224    if (setBit) {
225        if ((uintptr_t)obj > hb->max) {
226            hb->max = (uintptr_t)obj;
227        }
228        if (returnOld) {
229            unsigned long *p = hb->bits + index;
230            const unsigned long word = *p;
231            *p |= mask;
232            return word & mask;
233        } else {
234            hb->bits[index] |= mask;
235        }
236    } else {
237        hb->bits[index] &= ~mask;
238    }
239    return false;
240}
241
242/*
243 * Sets the bit corresponding to <obj>, and returns the previous value
244 * of that bit (as zero or non-zero). Does no range checking to see if
245 * <obj> is outside of the coverage of the bitmap.
246 *
247 * NOTE: casting this value to a bool is dangerous, because higher
248 * set bits will be lost.
249 */
250HB_INLINE_PROTO(
251    unsigned long
252    dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj)
253)
254{
255    return _heapBitmapModifyObjectBit(hb, obj, true, true);
256}
257
258/*
259 * Sets the bit corresponding to <obj>, and widens the range of seen
260 * pointers if necessary.  Does no range checking.
261 */
262HB_INLINE_PROTO(
263    void
264    dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj)
265)
266{
267    (void)_heapBitmapModifyObjectBit(hb, obj, true, false);
268}
269
270/*
271 * Clears the bit corresponding to <obj>.  Does no range checking.
272 */
273HB_INLINE_PROTO(
274    void
275    dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj)
276)
277{
278    (void)_heapBitmapModifyObjectBit(hb, obj, false, false);
279}
280
281/*
282 * Returns the current value of the bit corresponding to <obj>,
283 * as zero or non-zero.  Does no range checking.
284 *
285 * NOTE: casting this value to a bool is dangerous, because higher
286 * set bits will be lost.
287 */
288HB_INLINE_PROTO(
289    unsigned long
290    dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj)
291)
292{
293    assert(dvmHeapBitmapCoversAddress(hb, obj));
294    assert(hb->bits != NULL);
295    assert((uintptr_t)obj >= hb->base);
296
297    if ((uintptr_t)obj <= hb->max) {
298        const uintptr_t offset = (uintptr_t)obj - hb->base;
299        return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset);
300    } else {
301        return 0;
302    }
303}
304
305#undef HB_INLINE_PROTO
306
307#endif  // _DALVIK_HEAP_BITMAP
308