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 <stdint.h>
20#include <assert.h>
21
22#define HB_OBJECT_ALIGNMENT 8
23#define HB_BITS_PER_WORD    (sizeof (unsigned long int) * 8)
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/* Pack the bits in backwards so they come out in address order
35 * when using CLZ.
36 */
37#define HB_OFFSET_TO_MASK(offset_) \
38    (1 << \
39        (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD)))
40
41/* Return the maximum offset (exclusive) that <hb> can represent.
42 */
43#define HB_MAX_OFFSET(hb_) \
44    HB_INDEX_TO_OFFSET((hb_)->bitsLen / sizeof(*(hb_)->bits))
45
46#define HB_INLINE_PROTO(p) \
47    static inline p __attribute__((always_inline)); \
48    static inline p
49
50
51typedef struct {
52    /* The bitmap data, which points to an mmap()ed area of zeroed
53     * anonymous memory.
54     */
55    unsigned long int *bits;
56
57    /* The size of the memory pointed to by bits, in bytes.
58     */
59    size_t bitsLen;
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} HeapBitmap;
72
73
74/*
75 * Initialize a HeapBitmap so that it points to a bitmap large
76 * enough to cover a heap at <base> of <maxSize> bytes, where
77 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned.
78 */
79bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize,
80        const char *name);
81
82/*
83 * Initialize <hb> so that it covers the same extent as <templateBitmap>.
84 */
85bool dvmHeapBitmapInitFromTemplate(HeapBitmap *hb,
86        const HeapBitmap *templateBitmap, const char *name);
87
88/*
89 * Initialize the bitmaps in <out> so that they cover the same extent as
90 * the corresponding bitmaps in <templates>.
91 */
92bool dvmHeapBitmapInitListFromTemplates(HeapBitmap out[],
93    HeapBitmap templates[], size_t numBitmaps, const char *name);
94
95/*
96 * Clean up any resources associated with the bitmap.
97 */
98void dvmHeapBitmapDelete(HeapBitmap *hb);
99
100/*
101 * Clean up any resources associated with the bitmaps.
102 */
103void dvmHeapBitmapDeleteList(HeapBitmap hbs[], size_t numBitmaps);
104
105/*
106 * Fill the bitmap with zeroes.  Returns the bitmap's memory to
107 * the system as a side-effect.
108 */
109void dvmHeapBitmapZero(HeapBitmap *hb);
110
111/*
112 * Walk through the bitmaps in increasing address order, and find the
113 * object pointers that correspond to places where the bitmaps differ.
114 * Call <callback> zero or more times with lists of these object pointers.
115 *
116 * The <finger> argument to the callback indicates the next-highest
117 * address that hasn't been visited yet; setting bits for objects whose
118 * addresses are less than <finger> are not guaranteed to be seen by
119 * the current XorWalk.  <finger> will be set to ULONG_MAX when the
120 * end of the bitmap is reached.
121 */
122bool dvmHeapBitmapXorWalk(const HeapBitmap *hb1, const HeapBitmap *hb2,
123        bool (*callback)(size_t numPtrs, void **ptrs,
124                         const void *finger, void *arg),
125        void *callbackArg);
126
127/*
128 * Similar to dvmHeapBitmapXorWalk(), but compare multiple bitmaps.
129 * Regardless of the order of the arrays, the bitmaps will be visited
130 * in address order, so that finger will increase monotonically.
131 */
132bool dvmHeapBitmapXorWalkLists(const HeapBitmap hbs1[], const HeapBitmap hbs2[],
133        size_t numBitmaps,
134        bool (*callback)(size_t numPtrs, void **ptrs,
135                         const void *finger, void *arg),
136        void *callbackArg);
137
138/*
139 * Similar to dvmHeapBitmapXorWalk(), but visit the set bits
140 * in a single bitmap.
141 */
142bool dvmHeapBitmapWalk(const HeapBitmap *hb,
143        bool (*callback)(size_t numPtrs, void **ptrs,
144                         const void *finger, void *arg),
145        void *callbackArg);
146
147/*
148 * Similar to dvmHeapBitmapXorWalkList(), but visit the set bits
149 * in a single list of bitmaps.  Regardless of the order of the array,
150 * the bitmaps will be visited in address order, so that finger will
151 * increase monotonically.
152 */
153bool dvmHeapBitmapWalkList(const HeapBitmap hbs[], size_t numBitmaps,
154        bool (*callback)(size_t numPtrs, void **ptrs,
155                         const void *finger, void *arg),
156        void *callbackArg);
157/*
158 * Return true iff <obj> is within the range of pointers that
159 * have had corresponding bits set in this bitmap.
160 */
161HB_INLINE_PROTO(
162    bool
163    dvmHeapBitmapMayContainObject(const HeapBitmap *hb,
164            const void *obj)
165)
166{
167    const uintptr_t p = (const uintptr_t)obj;
168
169    assert((p & (HB_OBJECT_ALIGNMENT - 1)) == 0);
170
171    return p >= hb->base && p <= hb->max;
172}
173
174/*
175 * Return true iff <obj> is within the range of pointers that this
176 * bitmap could potentially cover, even if a bit has not been set
177 * for it.
178 */
179HB_INLINE_PROTO(
180    bool
181    dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj)
182)
183{
184    assert(hb != NULL);
185
186    if (obj != NULL) {
187        const uintptr_t offset = (uintptr_t)obj - hb->base;
188        const size_t index = HB_OFFSET_TO_INDEX(offset);
189        return index < hb->bitsLen / sizeof(*hb->bits);
190    }
191    return false;
192}
193
194/*
195 * Internal function; do not call directly.
196 */
197HB_INLINE_PROTO(
198    unsigned long int
199    _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj,
200            bool setBit, bool returnOld)
201)
202{
203    const uintptr_t offset = (uintptr_t)obj - hb->base;
204    const size_t index = HB_OFFSET_TO_INDEX(offset);
205    const unsigned long int mask = HB_OFFSET_TO_MASK(offset);
206
207#ifndef NDEBUG
208    assert(hb->bits != NULL);
209    assert((uintptr_t)obj >= hb->base);
210    assert(index < hb->bitsLen / sizeof(*hb->bits));
211#endif
212
213    if (setBit) {
214        if ((uintptr_t)obj > hb->max) {
215            hb->max = (uintptr_t)obj;
216        }
217        if (returnOld) {
218            unsigned long int *p = hb->bits + index;
219            const unsigned long int word = *p;
220            *p |= mask;
221            return word & mask;
222        } else {
223            hb->bits[index] |= mask;
224        }
225    } else {
226        hb->bits[index] &= ~mask;
227    }
228    return false;
229}
230
231/*
232 * Sets the bit corresponding to <obj>, and returns the previous value
233 * of that bit (as zero or non-zero). Does no range checking to see if
234 * <obj> is outside of the coverage of the bitmap.
235 *
236 * NOTE: casting this value to a bool is dangerous, because higher
237 * set bits will be lost.
238 */
239HB_INLINE_PROTO(
240    unsigned long int
241    dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj)
242)
243{
244    return _heapBitmapModifyObjectBit(hb, obj, true, true);
245}
246
247/*
248 * Like dvmHeapBitmapSetAndReturnObjectBit(), but sets/returns the bit
249 * in the appropriate bitmap.  Results are undefined if <obj> is not
250 * covered by any bitmap.
251 */
252HB_INLINE_PROTO(
253    unsigned long int
254    dvmHeapBitmapSetAndReturnObjectBitInList(HeapBitmap hbs[],
255            size_t numBitmaps, const void *obj)
256)
257{
258    size_t i;
259
260    for (i = 0; i < numBitmaps; i++) {
261        if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) {
262            return dvmHeapBitmapSetAndReturnObjectBit(&hbs[i], obj);
263        }
264    }
265
266    assert(!"object not covered by any bitmap");
267    return false;
268}
269
270/*
271 * Sets the bit corresponding to <obj>, and widens the range of seen
272 * pointers if necessary.  Does no range checking.
273 */
274HB_INLINE_PROTO(
275    void
276    dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj)
277)
278{
279    (void)_heapBitmapModifyObjectBit(hb, obj, true, false);
280}
281
282/*
283 * Clears the bit corresponding to <obj>.  Does no range checking.
284 */
285HB_INLINE_PROTO(
286    void
287    dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj)
288)
289{
290    (void)_heapBitmapModifyObjectBit(hb, obj, false, false);
291}
292
293/*
294 * Returns the current value of the bit corresponding to <obj>,
295 * as zero or non-zero.  Does no range checking.
296 *
297 * NOTE: casting this value to a bool is dangerous, because higher
298 * set bits will be lost.
299 */
300HB_INLINE_PROTO(
301    unsigned long int
302    dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj)
303)
304{
305    assert(dvmHeapBitmapCoversAddress(hb, obj));
306    assert(hb->bits != NULL);
307    assert((uintptr_t)obj >= hb->base);
308
309    if ((uintptr_t)obj <= hb->max) {
310        const uintptr_t offset = (uintptr_t)obj - hb->base;
311        return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset);
312    } else {
313        return 0;
314    }
315}
316
317/*
318 * Looks through the list of bitmaps and returns the current value of the
319 * bit corresponding to <obj>, which may be covered by any of the bitmaps.
320 * Does no range checking.
321 */
322HB_INLINE_PROTO(
323    long
324    dvmHeapBitmapIsObjectBitSetInList(const HeapBitmap hbs[], size_t numBitmaps,
325            const void *obj)
326)
327{
328    size_t i;
329
330    for (i = 0; i < numBitmaps; i++) {
331        if (dvmHeapBitmapCoversAddress(&hbs[i], obj)) {
332            return dvmHeapBitmapIsObjectBitSet(&hbs[i], obj);
333        }
334    }
335    return false;
336}
337
338#undef HB_INLINE_PROTO
339
340#endif  // _DALVIK_HEAP_BITMAP
341