Home | History | Annotate | Download | only in alloc 
      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