/*
 * Copyright (C) 2014 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 
 */

#include "config.h"
#include "HeapVerifier.h"

#include "ButterflyInlines.h"
#include "CopiedSpaceInlines.h"
#include "HeapIterationScope.h"
#include "JSCInlines.h"
#include "JSObject.h"

namespace JSC {

HeapVerifier::HeapVerifier(Heap* heap, unsigned numberOfGCCyclesToRecord)
    : m_heap(heap)
    , m_currentCycle(0)
    , m_numberOfCycles(numberOfGCCyclesToRecord)
{
    RELEASE_ASSERT(m_numberOfCycles > 0);
    m_cycles = std::make_unique<GCCycle[]>(m_numberOfCycles);
}

const char* HeapVerifier::collectionTypeName(HeapOperation type)
{
    switch (type) {
    case NoOperation:
        return "NoOperation";
    case AnyCollection:
        return "AnyCollection";
    case Allocation:
        return "Allocation";
    case EdenCollection:
        return "EdenCollection";
    case FullCollection:
        return "FullCollection";
    }
    RELEASE_ASSERT_NOT_REACHED();
    return nullptr; // Silencing a compiler warning.
}

const char* HeapVerifier::phaseName(HeapVerifier::Phase phase)
{
    switch (phase) {
    case Phase::BeforeGC:
        return "BeforeGC";
    case Phase::BeforeMarking:
        return "BeforeMarking";
    case Phase::AfterMarking:
        return "AfterMarking";
    case Phase::AfterGC:
        return "AfterGC";
    }
    RELEASE_ASSERT_NOT_REACHED();
    return nullptr; // Silencing a compiler warning.
}

static void getButterflyDetails(JSObject* obj, void*& butterflyBase, size_t& butterflyCapacityInBytes, CopiedBlock*& butterflyBlock)
{
    Structure* structure = obj->structure();
    Butterfly* butterfly = obj->butterfly();
    butterflyBase = butterfly->base(structure);
    butterflyBlock = CopiedSpace::blockFor(butterflyBase);

    size_t propertyCapacity = structure->outOfLineCapacity();
    size_t preCapacity;
    size_t indexingPayloadSizeInBytes;
    bool hasIndexingHeader = obj->hasIndexingHeader();
    if (UNLIKELY(hasIndexingHeader)) {
        preCapacity = butterfly->indexingHeader()->preCapacity(structure);
        indexingPayloadSizeInBytes = butterfly->indexingHeader()->indexingPayloadSizeInBytes(structure);
    } else {
        preCapacity = 0;
        indexingPayloadSizeInBytes = 0;
    }
    butterflyCapacityInBytes = Butterfly::totalSize(preCapacity, propertyCapacity, hasIndexingHeader, indexingPayloadSizeInBytes);
}

void HeapVerifier::initializeGCCycle()
{
    Heap* heap = m_heap;
    incrementCycle();
    currentCycle().collectionType = heap->operationInProgress();
}

struct GatherLiveObjFunctor : MarkedBlock::CountFunctor {
    GatherLiveObjFunctor(LiveObjectList& list)
        : m_list(list)
    {
        ASSERT(!list.liveObjects.size());
    }

    inline void visit(JSCell* cell)
    {
        if (!cell->isObject())
            return;        
        LiveObjectData data(asObject(cell));
        m_list.liveObjects.append(data);
    }

    IterationStatus operator()(JSCell* cell)
    {
        visit(cell);
        return IterationStatus::Continue;
    }

    LiveObjectList& m_list;
};

void HeapVerifier::gatherLiveObjects(HeapVerifier::Phase phase)
{
    Heap* heap = m_heap;
    LiveObjectList& list = *liveObjectListForGathering(phase);

    HeapIterationScope iterationScope(*heap);
    list.reset();
    GatherLiveObjFunctor functor(list);
    heap->m_objectSpace.forEachLiveCell(iterationScope, functor);
}

LiveObjectList* HeapVerifier::liveObjectListForGathering(HeapVerifier::Phase phase)
{
    switch (phase) {
    case Phase::BeforeMarking:
        return &currentCycle().before;
    case Phase::AfterMarking:
        return &currentCycle().after;
    case Phase::BeforeGC:
    case Phase::AfterGC:
        // We should not be gathering live objects during these phases.
        break;
    }
    RELEASE_ASSERT_NOT_REACHED();
    return nullptr; // Silencing a compiler warning.
}

static void trimDeadObjectsFromList(HashSet<JSObject*>& knownLiveSet, LiveObjectList& list)
{
    if (!list.hasLiveObjects)
        return;

    size_t liveObjectsFound = 0;
    for (size_t i = 0; i < list.liveObjects.size(); i++) {
        LiveObjectData& objData = list.liveObjects[i];
        if (objData.isConfirmedDead)
            continue; // Don't "resurrect" known dead objects.
        if (!knownLiveSet.contains(objData.obj)) {
            objData.isConfirmedDead = true;
            continue;
        }
        liveObjectsFound++;
    }
    list.hasLiveObjects = !!liveObjectsFound;
}

void HeapVerifier::trimDeadObjects()
{
    HashSet<JSObject*> knownLiveSet;

    LiveObjectList& after = currentCycle().after;
    for (size_t i = 0; i < after.liveObjects.size(); i++) {
        LiveObjectData& objData = after.liveObjects[i];
        knownLiveSet.add(objData.obj);
    }

    trimDeadObjectsFromList(knownLiveSet, currentCycle().before);

    for (int i = -1; i > -m_numberOfCycles; i--) {
        trimDeadObjectsFromList(knownLiveSet, cycleForIndex(i).before);
        trimDeadObjectsFromList(knownLiveSet, cycleForIndex(i).after);
    }
}

bool HeapVerifier::verifyButterflyIsInStorageSpace(Phase phase, LiveObjectList& list)
{
    auto& liveObjects = list.liveObjects;

    CopiedSpace& storageSpace = m_heap->m_storageSpace;
    bool listNamePrinted = false;
    bool success = true;
    for (size_t i = 0; i < liveObjects.size(); i++) {
        LiveObjectData& objectData = liveObjects[i];
        if (objectData.isConfirmedDead)
            continue;

        JSObject* obj = objectData.obj;
        Butterfly* butterfly = obj->butterfly();
        if (butterfly) {
            void* butterflyBase;
            size_t butterflyCapacityInBytes;
            CopiedBlock* butterflyBlock;
            getButterflyDetails(obj, butterflyBase, butterflyCapacityInBytes, butterflyBlock);

            if (!storageSpace.contains(butterflyBlock)) {
                if (!listNamePrinted) {
                    dataLogF("Verification @ phase %s FAILED in object list '%s' (size %zu)\n",
                        phaseName(phase), list.name, liveObjects.size());
                    listNamePrinted = true;
                }

                Structure* structure = obj->structure();
                const char* structureClassName = structure->classInfo()->className;
                dataLogF("    butterfly %p (base %p size %zu block %p) NOT in StorageSpace | obj %p type '%s'\n",
                    butterfly, butterflyBase, butterflyCapacityInBytes, butterflyBlock, obj, structureClassName);
                success = false;
            }
        }
    }
    return success;
}

void HeapVerifier::verify(HeapVerifier::Phase phase)
{
    bool beforeVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().before);
    bool afterVerified = verifyButterflyIsInStorageSpace(phase, currentCycle().after);
    RELEASE_ASSERT(beforeVerified && afterVerified);
}

void HeapVerifier::reportObject(LiveObjectData& objData, int cycleIndex, HeapVerifier::GCCycle& cycle, LiveObjectList& list)
{
    JSObject* obj = objData.obj;

    if (objData.isConfirmedDead) {
        dataLogF("FOUND dead obj %p in GC[%d] %s list '%s'\n",
            obj, cycleIndex, cycle.collectionTypeName(), list.name);
        return;
    }

    Structure* structure = obj->structure();
    Butterfly* butterfly = obj->butterfly();
    void* butterflyBase;
    size_t butterflyCapacityInBytes;
    CopiedBlock* butterflyBlock;
    getButterflyDetails(obj, butterflyBase, butterflyCapacityInBytes, butterflyBlock);

    dataLogF("FOUND obj %p type '%s' butterfly %p (base %p size %zu block %p) in GC[%d] %s list '%s'\n",
        obj, structure->classInfo()->className,
        butterfly, butterflyBase, butterflyCapacityInBytes, butterflyBlock,
        cycleIndex, cycle.collectionTypeName(), list.name);
}

void HeapVerifier::checkIfRecorded(JSObject* obj)
{
    bool found = false;

    for (int cycleIndex = 0; cycleIndex > -m_numberOfCycles; cycleIndex--) {
        GCCycle& cycle = cycleForIndex(cycleIndex);
        LiveObjectList& beforeList = cycle.before; 
        LiveObjectList& afterList = cycle.after; 

        LiveObjectData* objData;
        objData = beforeList.findObject(obj);
        if (objData) {
            reportObject(*objData, cycleIndex, cycle, beforeList);
            found = true;
        }
        objData = afterList.findObject(obj);
        if (objData) {
            reportObject(*objData, cycleIndex, cycle, afterList);
            found = true;
        }
    }

    if (!found)
        dataLogF("obj %p NOT FOUND\n", obj);
}

} // namespace JSC