/*
 * 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.
 */

#include "Dalvik.h"
#include "HeapBitmap.h"
#include <sys/mman.h>   /* for PROT_* */

/*
 * 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)
{
    void *bits;
    size_t bitsLen;

    assert(hb != NULL);
    assert(name != NULL);
    bitsLen = HB_OFFSET_TO_INDEX(maxSize) * sizeof(*hb->bits);
    bits = dvmAllocRegion(bitsLen, PROT_READ | PROT_WRITE, name);
    if (bits == NULL) {
        ALOGE("Could not mmap %zd-byte ashmem region '%s'", bitsLen, name);
        return false;
    }
    hb->bits = (unsigned long *)bits;
    hb->bitsLen = hb->allocLen = bitsLen;
    hb->base = (uintptr_t)base;
    hb->max = hb->base - 1;
    return true;
}

/*
 * Clean up any resources associated with the bitmap.
 */
void dvmHeapBitmapDelete(HeapBitmap *hb)
{
    assert(hb != NULL);

    if (hb->bits != NULL) {
        munmap((char *)hb->bits, hb->allocLen);
    }
    memset(hb, 0, sizeof(*hb));
}

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

    if (hb->bits != NULL) {
        /* This returns the memory to the system.
         * Successive page faults will return zeroed memory.
         */
        madvise(hb->bits, hb->bitsLen, MADV_DONTNEED);
        hb->max = hb->base - 1;
    }
}

/*
 * 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.
 */
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;
}

/*
 * Visits set bits in address order.  The callback is not permitted to
 * change the bitmap bits or max during the traversal.
 */
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);
    for (uintptr_t 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);
                Object* obj = (Object *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
                (*callback)(obj, 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.
 */
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);
                Object *obj = (Object *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
                (*callback)(obj, 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 not permitted to increase the max of either bitmap.
 */
void dvmHeapBitmapSweepWalk(const HeapBitmap *liveHb, const HeapBitmap *markHb,
                            uintptr_t base, uintptr_t max,
                            BitmapSweepCallback *callback, void *callbackArg)
{
    assert(liveHb != NULL);
    assert(liveHb->bits != NULL);
    assert(markHb != NULL);
    assert(markHb->bits != NULL);
    assert(liveHb->base == markHb->base);
    assert(liveHb->bitsLen == markHb->bitsLen);
    assert(callback != NULL);
    assert(base <= max);
    assert(base >= liveHb->base);
    assert(max <= liveHb->max);
    if (liveHb->max < liveHb->base) {
        /* Easy case; both are obviously empty.
         */
        return;
    }
    void *pointerBuf[4 * HB_BITS_PER_WORD];
    void **pb = pointerBuf;
    size_t start = HB_OFFSET_TO_INDEX(base - liveHb->base);
    size_t end = HB_OFFSET_TO_INDEX(max - liveHb->base);
    unsigned long *live = liveHb->bits;
    unsigned long *mark = markHb->bits;
    for (size_t i = start; i <= end; i++) {
        unsigned long garbage = live[i] & ~mark[i];
        if (UNLIKELY(garbage != 0)) {
            unsigned long highBit = 1 << (HB_BITS_PER_WORD - 1);
            uintptr_t ptrBase = HB_INDEX_TO_OFFSET(i) + liveHb->base;
            while (garbage != 0) {
                int shift = CLZ(garbage);
                garbage &= ~(highBit >> shift);
                *pb++ = (void *)(ptrBase + shift * HB_OBJECT_ALIGNMENT);
            }
            /* Make sure that there are always enough slots available */
            /* for an entire word of 1s. */
            if (pb >= &pointerBuf[NELEM(pointerBuf) - HB_BITS_PER_WORD]) {
                (*callback)(pb - pointerBuf, pointerBuf, callbackArg);
                pb = pointerBuf;
            }
        }
    }
    if (pb > pointerBuf) {
        (*callback)(pb - pointerBuf, pointerBuf, callbackArg);
    }
}