HeapBitmap.cpp revision c1a4ab9c313d8a3d12007f2dbef7b5a6fa4ac2ef 
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 */
26bool 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 */
50void 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 */
64void 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 */
82bool 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 */
97void 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 */
131void 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 */
163void 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