/*
 * Copyright (C) 2008 The Android Open Source Project
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *      http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
#ifndef _DALVIK_HEAP_BITMAP
#define _DALVIK_HEAP_BITMAP

#include <limits.h>
#include <stdint.h>
#include "clz.h"

#define HB_OBJECT_ALIGNMENT 8
#define HB_BITS_PER_WORD (sizeof(unsigned long) * CHAR_BIT)

/* <offset> is the difference from .base to a pointer address.
 * <index> is the index of .bits that contains the bit representing
 *         <offset>.
 */
#define HB_OFFSET_TO_INDEX(offset_) \
    ((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT / HB_BITS_PER_WORD)
#define HB_INDEX_TO_OFFSET(index_) \
    ((uintptr_t)(index_) * HB_OBJECT_ALIGNMENT * HB_BITS_PER_WORD)

#define HB_OFFSET_TO_BYTE_INDEX(offset_) \
  (HB_OFFSET_TO_INDEX(offset_) * sizeof(*((HeapBitmap *)0)->bits))

/* Pack the bits in backwards so they come out in address order
 * when using CLZ.
 */
#define HB_OFFSET_TO_MASK(offset_) \
    (1 << \
        (31-(((uintptr_t)(offset_) / HB_OBJECT_ALIGNMENT) % HB_BITS_PER_WORD)))

/* Return the maximum offset (exclusive) that <hb> can represent.
 */
#define HB_MAX_OFFSET(hb_) \
    HB_INDEX_TO_OFFSET((hb_)->bitsLen / sizeof(*(hb_)->bits))

#define HB_INLINE_PROTO(p) \
    static inline p __attribute__((always_inline)); \
    static inline p

typedef struct {
    /* The bitmap data, which points to an mmap()ed area of zeroed
     * anonymous memory.
     */
    unsigned long *bits;

    /* The size of the used memory pointed to by bits, in bytes.  This
     * value changes when the bitmap is shrunk.
     */
    size_t bitsLen;

    /* The real size of the memory pointed to by bits.  This is the
     * number of bytes we requested from the allocator and does not
     * change.
     */
    size_t allocLen;

    /* The base address, which corresponds to the first bit in
     * the bitmap.
     */
    uintptr_t base;

    /* The highest pointer value ever returned by an allocation
     * from this heap.  I.e., the highest address that may correspond
     * to a set bit.  If there are no bits set, (max < base).
     */
    uintptr_t max;
} HeapBitmap;

typedef void BitmapCallback(void *addr, void *arg);
typedef void BitmapScanCallback(void *addr, void *finger, void *arg);
typedef void BitmapSweepCallback(size_t numPtrs, void **ptrs, void *arg);

/*
 * Initialize a HeapBitmap so that it points to a bitmap large
 * enough to cover a heap at <base> of <maxSize> bytes, where
 * objects are guaranteed to be HB_OBJECT_ALIGNMENT-aligned.
 */
bool dvmHeapBitmapInit(HeapBitmap *hb, const void *base, size_t maxSize,
        const char *name);

/*
 * Clean up any resources associated with the bitmap.
 */
void dvmHeapBitmapDelete(HeapBitmap *hb);

/*
 * Fill the bitmap with zeroes.  Returns the bitmap's memory to
 * the system as a side-effect.
 */
void dvmHeapBitmapZero(HeapBitmap *hb);

/*
 * Visits set bits in address order.  The callback is not permitted to
 * change the bitmap bits or max during the traversal.
 */
HB_INLINE_PROTO(
    void
    dvmHeapBitmapWalk(const HeapBitmap *bitmap,
                      BitmapCallback *callback, void *arg)
)
{
    assert(bitmap != NULL);
    assert(bitmap->bits != NULL);
    assert(callback != NULL);
    uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
    uintptr_t i;
    for (i = 0; i <= end; ++i) {
        unsigned long word = bitmap->bits[i];
        if (UNLIKELY(word != 0)) {
            unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
            uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base;
            while (word != 0) {
                const int shift = CLZ(word);
                void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
                (*callback)(addr, arg);
                word &= ~(highBit >> shift);
            }
        }
    }
}

/*
 * Similar to dvmHeapBitmapWalk but the callback routine is permitted
 * to change the bitmap bits and max during traversal.  Used by the
 * the root marking scan exclusively.
 *
 * The callback is invoked with a finger argument.  The finger is a
 * pointer to an address not yet visited by the traversal.  If the
 * callback sets a bit for an address at or above the finger, this
 * address will be visited by the traversal.  If the callback sets a
 * bit for an address below the finger, this address will not be
 * visited.
 */
HB_INLINE_PROTO(
    void
    dvmHeapBitmapScanWalk(HeapBitmap *bitmap,
                          BitmapScanCallback *callback, void *arg)
)
{
    assert(bitmap != NULL);
    assert(bitmap->bits != NULL);
    assert(callback != NULL);
    uintptr_t end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
    uintptr_t i;
    for (i = 0; i <= end; ++i) {
        unsigned long word = bitmap->bits[i];
        if (UNLIKELY(word != 0)) {
            unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
            uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + bitmap->base;
            void *finger = (void *)(HB_INDEX_TO_OFFSET(i + 1) + bitmap->base);
            while (word != 0) {
                const int shift = CLZ(word);
                void *addr = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
                (*callback)(addr, finger, arg);
                word &= ~(highBit >> shift);
            }
            end = HB_OFFSET_TO_INDEX(bitmap->max - bitmap->base);
        }
    }
}

/*
 * Walk through the bitmaps in increasing address order, and find the
 * object pointers that correspond to garbage objects.  Call
 * <callback> zero or more times with lists of these object pointers.
 *
 * The callback is permitted to increase the bitmap's max; the walk
 * will use the updated max as a terminating condition.
 */
void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
                            BitmapSweepCallback *callback, void *callbackArg);

/*
 * Return true iff <obj> is within the range of pointers that this
 * bitmap could potentially cover, even if a bit has not been set
 * for it.
 */
HB_INLINE_PROTO(
    bool
    dvmHeapBitmapCoversAddress(const HeapBitmap *hb, const void *obj)
)
{
    assert(hb != NULL);

    if (obj != NULL) {
        const uintptr_t offset = (uintptr_t)obj - hb->base;
        const size_t index = HB_OFFSET_TO_INDEX(offset);
        return index < hb->bitsLen / sizeof(*hb->bits);
    }
    return false;
}

/*
 * Internal function; do not call directly.
 */
HB_INLINE_PROTO(
    unsigned long
    _heapBitmapModifyObjectBit(HeapBitmap *hb, const void *obj,
            bool setBit, bool returnOld)
)
{
    const uintptr_t offset = (uintptr_t)obj - hb->base;
    const size_t index = HB_OFFSET_TO_INDEX(offset);
    const unsigned long mask = HB_OFFSET_TO_MASK(offset);

    assert(hb->bits != NULL);
    assert((uintptr_t)obj >= hb->base);
    assert(index < hb->bitsLen / sizeof(*hb->bits));

    if (setBit) {
        if ((uintptr_t)obj > hb->max) {
            hb->max = (uintptr_t)obj;
        }
        if (returnOld) {
            unsigned long *p = hb->bits + index;
            const unsigned long word = *p;
            *p |= mask;
            return word & mask;
        } else {
            hb->bits[index] |= mask;
        }
    } else {
        hb->bits[index] &= ~mask;
    }
    return false;
}

/*
 * Sets the bit corresponding to <obj>, and returns the previous value
 * of that bit (as zero or non-zero). Does no range checking to see if
 * <obj> is outside of the coverage of the bitmap.
 *
 * NOTE: casting this value to a bool is dangerous, because higher
 * set bits will be lost.
 */
HB_INLINE_PROTO(
    unsigned long
    dvmHeapBitmapSetAndReturnObjectBit(HeapBitmap *hb, const void *obj)
)
{
    return _heapBitmapModifyObjectBit(hb, obj, true, true);
}

/*
 * Sets the bit corresponding to <obj>, and widens the range of seen
 * pointers if necessary.  Does no range checking.
 */
HB_INLINE_PROTO(
    void
    dvmHeapBitmapSetObjectBit(HeapBitmap *hb, const void *obj)
)
{
    (void)_heapBitmapModifyObjectBit(hb, obj, true, false);
}

/*
 * Clears the bit corresponding to <obj>.  Does no range checking.
 */
HB_INLINE_PROTO(
    void
    dvmHeapBitmapClearObjectBit(HeapBitmap *hb, const void *obj)
)
{
    (void)_heapBitmapModifyObjectBit(hb, obj, false, false);
}

/*
 * Returns the current value of the bit corresponding to <obj>,
 * as zero or non-zero.  Does no range checking.
 *
 * NOTE: casting this value to a bool is dangerous, because higher
 * set bits will be lost.
 */
HB_INLINE_PROTO(
    unsigned long
    dvmHeapBitmapIsObjectBitSet(const HeapBitmap *hb, const void *obj)
)
{
    assert(dvmHeapBitmapCoversAddress(hb, obj));
    assert(hb->bits != NULL);
    assert((uintptr_t)obj >= hb->base);

    if ((uintptr_t)obj <= hb->max) {
        const uintptr_t offset = (uintptr_t)obj - hb->base;
        return hb->bits[HB_OFFSET_TO_INDEX(offset)] & HB_OFFSET_TO_MASK(offset);
    } else {
        return 0;
    }
}

#undef HB_INLINE_PROTO

#endif  // _DALVIK_HEAP_BITMAP