HeapBitmap.h revision 375fb116bcb817b37509ab579dbd55cdbb765cbf 
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
44struct 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 */
76typedef void BitmapCallback(Object *obj, void *arg);
77typedef void BitmapScanCallback(Object *obj, void *finger, void *arg);
78typedef 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 */
85bool 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 */
91void 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 */
97void dvmHeapBitmapZero(HeapBitmap *hb);
98
99/*
100 * Returns true if the address range of the bitmap covers the object
101 * address.
102 */
103bool dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj);
104
105/*
106 * Applies the callback function to each set address in the bitmap.
107 */
108void 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 */
115void dvmHeapBitmapScanWalk(HeapBitmap *bitmap,
116                           uintptr_t base, uintptr_t max,
117                           BitmapScanCallback *callback, void *arg);
118
119/*
120 * Walk through the bitmaps in increasing address order, and find the
121 * object pointers that correspond to garbage objects.  Call
122 * <callback> zero or more times with lists of these object pointers.
123 *
124 * The callback is not permitted to increase the max of either bitmap.
125 */
126void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
127                            uintptr_t base, uintptr_t max,
128                            BitmapSweepCallback *callback, void *callbackArg);
129
130#endif  // DALVIK_HEAP_BITMAP_H_
131