baker.cpp

/*
 *    BakerMemoryManager.cpp
 *
 *    Implementation of BakerMemoryManager class
 *
 *    LLST (LLVM Smalltalk or Low Level Smalltalk) version 0.2
 *
 *    LLST is
 *        Copyright (C) 2012-2013 by Dmitry Kashitsyn   <[email protected]>
 *        Copyright (C) 2012-2013 by Roman Proskuryakov <[email protected]>
 *
 *    LLST is based on the LittleSmalltalk which is
 *        Copyright (C) 1987-2005 by Timothy A. Budd
 *        Copyright (C) 2007 by Charles R. Childers
 *        Copyright (C) 2005-2007 by Danny Reinhold
 *
 *    Original license of LittleSmalltalk may be found in the LICENSE file.
 *
 *
 *    This file is part of LLST.
 *    LLST is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    LLST is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with LLST.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <memory.h>
#include <cstring>
#include <cstdlib>
#include <sys/time.h>

BakerMemoryManager::BakerMemoryManager() :
    m_collectionsCount(0), m_allocationsCount(0), m_totalCollectionDelay(0),
    m_heapSize(0), m_maxHeapSize(0), m_heapOne(0), m_heapTwo(0),
    m_activeHeapOne(true), m_inactiveHeapBase(0), m_inactiveHeapPointer(0),
    m_activeHeapBase(0), m_activeHeapPointer(0), m_staticHeapSize(0),
    m_staticHeapBase(0), m_staticHeapPointer(0), m_externalPointersHead(0)
{
    // TODO set everything in m_memoryInfo to 0
    gettimeofday(&(m_memoryInfo.timeBegin), NULL);
    m_logFile.open("gc.log", std::fstream::out);
    // Nothing to be done here
}

BakerMemoryManager::~BakerMemoryManager()
{
    // TODO Reset the external pointers to catch the null pointers if something goes wrong
    m_logFile.close();
    std::free(m_staticHeapBase);
    std::free(m_heapOne);
    std::free(m_heapTwo);
}

//void BakerMemoryManager::writeLogEnd(TMemoryManagerEvent *event){
//
//}

void BakerMemoryManager::writeLogLine(TMemoryManagerEvent *event){
    m_logFile << event->time.tv_sec << "." << event->time.tv_usec/1000
              << ": [" << event->eventName << ": ";
    if(event->heapInfo != NULL){
        TMemoryManagerHeapInfo *eh = event->heapInfo;
        m_logFile << eh->usedHeapSizeBeforeCollect << "K->"
                  << eh->usedHeapSizeAfterCollect << "K("
                  << eh->totalHeapSize << "K)";
        for(std::list<TMemoryManagerHeapEvent*>::iterator i = eh->heapEvents.begin(); i != eh->heapEvents.end(); i++){
            m_logFile << "[" << (*i)->eventName << ": "
                      << (*i)->usedHeapSizeBeforeCollect << "K->"
                      << (*i)->usedHeapSizeAfterCollect << "K("
                      << (*i)->totalHeapSize << "K)";
            if((*i)->timeDiff.tv_sec != 0 || (*i)->timeDiff.tv_usec != 0){
                m_logFile << ", " << (*i)->timeDiff.tv_sec << "." << (*i)->timeDiff.tv_usec/1000 << " secs";
            }
            m_logFile << "] ";
        }
    }
    if(event->timeDiff.tv_sec != 0 || event->timeDiff.tv_usec != 0){
        m_logFile << ", " << event->timeDiff.tv_sec << "." << event->timeDiff.tv_usec << " secs";
    }
    m_logFile << "]\n";
}

bool BakerMemoryManager::initializeStaticHeap(std::size_t heapSize)
{
    heapSize = correctPadding(heapSize);

    uint8_t* heap = static_cast<uint8_t*>( std::malloc(heapSize) );
    if (!heap)
        return false;

    std::memset(heap, 0, heapSize);

    m_staticHeapBase = heap;
    m_staticHeapPointer = heap + heapSize;
    m_staticHeapSize = heapSize;

    return true;
}

bool BakerMemoryManager::initializeHeap(std::size_t heapSize, std::size_t maxHeapSize /* = 0 */)
{
    // To initialize properly we need a heap with an even size
    heapSize = correctPadding(heapSize);

    uint32_t mediane = heapSize / 2;
    m_heapSize = heapSize;
    m_maxHeapSize = maxHeapSize;

    m_heapOne = static_cast<uint8_t*>( std::malloc(mediane) );
    m_heapTwo = static_cast<uint8_t*>( std::malloc(mediane) );
    // TODO check for allocation errors

    std::memset(m_heapOne, 0, mediane);
    std::memset(m_heapTwo, 0, mediane);

    m_activeHeapOne = true;

    m_activeHeapBase = m_heapOne;
    m_activeHeapPointer = m_heapOne + mediane;

    m_inactiveHeapBase =  m_heapTwo;
    m_inactiveHeapPointer = m_heapTwo + mediane;

    return true;
}

void BakerMemoryManager::growHeap(uint32_t requestedSize)
{
    // Stage1. Growing inactive heap
    uint32_t newHeapSize = correctPadding(requestedSize + m_heapSize + m_heapSize / 2);

    std::printf("MM: Growing heap to %d\n", newHeapSize);

    uint32_t newMediane = newHeapSize / 2;
    uint8_t** activeHeapBase   = m_activeHeapOne ? &m_heapOne : &m_heapTwo;
    uint8_t** inactiveHeapBase = m_activeHeapOne ? &m_heapTwo : &m_heapOne;

    // Reallocating space and zeroing it
    {
        void* newInactiveHeap = std::realloc(*inactiveHeapBase, newMediane);
        if (!newInactiveHeap)
        {
            std::printf("MM: Cannot reallocate %d bytes for inactive heap\n", newMediane);
            std::abort();
        } else {
            *inactiveHeapBase = static_cast<uint8_t*>(newInactiveHeap);
            std::memset(*inactiveHeapBase, 0, newMediane);
        }
    }
    // Stage 2. Collecting garbage so that
    // active objects will be moved to a new home
    collectGarbage();

    // Now pointers are swapped and previously active heap is now inactive
    // We need to reallocate it too
    {
        void* newActiveHeap = std::realloc(*activeHeapBase, newMediane);
        if (!newActiveHeap)
        {
            std::printf("MM: Cannot reallocate %d bytes for active heap\n", newMediane);
            std::abort();
        } else {
            *activeHeapBase = static_cast<uint8_t*>(newActiveHeap);
            std::memset(*activeHeapBase, 0, newMediane);
        }
    }
    collectGarbage();

    m_heapSize = newHeapSize;
}

void* BakerMemoryManager::allocate(std::size_t requestedSize, bool* gcOccured /*= 0*/ )
{
    if (gcOccured)
        *gcOccured = false;

    std::size_t attempts = 2;
    while (attempts-- > 0) {
        if (m_activeHeapPointer - requestedSize < m_activeHeapBase) {
            collectGarbage();

            // If even after collection there is too less space
            // we may try to expand the heap
            const uintptr_t distance = m_activeHeapPointer - m_activeHeapBase;
            if ((m_heapSize < m_maxHeapSize) && (distance < m_heapSize / 6))
               growHeap(requestedSize);

            if (gcOccured)
                *gcOccured = true;
            continue;
        }

        m_activeHeapPointer -= requestedSize;
        void* result = m_activeHeapPointer;

        if (gcOccured && !*gcOccured)
            m_allocationsCount++;
        return result;
    }

    // TODO Grow the heap if object still not fits

    std::fprintf(stderr, "Could not allocate %u bytes in heap\n", requestedSize);
    return 0;
}

void* BakerMemoryManager::staticAllocate(std::size_t requestedSize)
{
    uint8_t* newPointer = m_staticHeapPointer - requestedSize;
    if (newPointer < m_staticHeapBase)
    {
        std::fprintf(stderr, "Could not allocate %u bytes in static heaps\n", requestedSize);
        return 0; // TODO Report memory allocation error
    }
    m_staticHeapPointer = newPointer;
    return newPointer;
}

BakerMemoryManager::TMovableObject* BakerMemoryManager::moveObject(TMovableObject* object)
{
    TMovableObject* currentObject  = object;
    TMovableObject* previousObject = 0;
    TMovableObject* objectCopy     = 0;
    TMovableObject* replacement    = 0;

    while (true) {

        // Stage 1. Walking down the tree. Keep stacking objects to be moved
        // until we find one that we can handle
        while (true) {
            // Checking whether this is inline integer
            if (isSmallInteger( reinterpret_cast<TObject*>(currentObject) )) {
                // Inline integers are stored directly in the
                // pointer space. All we need to do is just copy
                // contents of the poiner to a new place

                replacement   = currentObject;
                currentObject = previousObject;
                break;
            }

            bool inOldSpace = (reinterpret_cast<uint8_t*>(currentObject) >= m_inactiveHeapPointer) &&
                              (reinterpret_cast<uint8_t*>(currentObject) < (m_inactiveHeapBase + m_heapSize / 2));

            // Checking if object is not in the old space
            if (!inOldSpace)
            {
                // Object does not belong to a heap.
                // Either it is located in static space
                // or this is a broken pointer
                replacement   = currentObject;
                currentObject = previousObject;
                break;
            }

            // Checking if object is already moved
            if (currentObject->size.isRelocated()) {
                if (currentObject->size.isBinary()) {
                    replacement = currentObject->data[0];
                } else {
                    uint32_t index = currentObject->size.getSize();
                    replacement = currentObject->data[index];
                }
                currentObject = previousObject;
                break;
            }

            // Checking whether we're dealing with the binary object
            if (currentObject->size.isBinary()) {
                // Current object is binary.
                // Moving object to a new space, copying it's data
                // and finally walking up to the object's class

                // Size of binary data
                uint32_t dataSize = currentObject->size.getSize();

                // Allocating copy in new space

                // We need to allocate space evenly, so calculating the
                // actual size of the block being reserved for the moving object
                m_activeHeapPointer -= sizeof(TByteObject) + correctPadding(dataSize);
                objectCopy = new (m_activeHeapPointer) TMovableObject(dataSize, true);

                // Copying byte data. data[0] is the class pointer,
                // actual binary data starts from the data[1]
                uint8_t* source      = reinterpret_cast<uint8_t*>( & currentObject->data[1] );
                uint8_t* destination = reinterpret_cast<uint8_t*>( & objectCopy->data[1] );
                std::memcpy(destination, source, dataSize);

                // Marking original copy of object as relocated so it would not be processed again
                currentObject->size.setRelocated();

                // During GC process temporarily using data[0] as indirection pointer
                // This will be corrected on the next stage of current GC operation
                objectCopy->data[0] = previousObject;
                previousObject = currentObject;
                currentObject  = currentObject->data[0];
                previousObject->data[0] = objectCopy;

                // On the next iteration we'll be processing the data[0] of the current object
                // which is actually class pointer in TObject.
                // NOTE It is expected that class of binary object would be non binary
            } else {
                // Current object is not binary, i.e. this is an ordinary object
                // with fields that are either SmallIntegers or pointers to other objects

                uint32_t fieldsCount = currentObject->size.getSize();

                m_activeHeapPointer -= sizeof(TObject) + fieldsCount * sizeof (TObject*);
                objectCopy = new (m_activeHeapPointer) TMovableObject(fieldsCount, false);

                currentObject->size.setRelocated();

                // Initializing indices. Actual field copying
                // will be done later in the next subloop
                const uint32_t lastObjectIndex = fieldsCount;
                objectCopy->data[lastObjectIndex] = previousObject;
                previousObject = currentObject;
                currentObject  = currentObject->data[lastObjectIndex];
                previousObject->data[lastObjectIndex] = objectCopy;
            }
        }

        // Stage 2.  Fix up pointers,
        // Move back up tree as long as possible
        // old_address points to an object in the old space,
        // which in turns points to an object in the new space,
        // which holds a pointer that is now to be replaced.
        // the value in replacement is the new value

        while (true) {
            // We're got out entirely
            if (currentObject == 0)
                return replacement;

            // Either binary object or the last value (field from the ordinary one?)
            if ( currentObject->size.isBinary() || (currentObject->size.getSize() == 0) ) {
                // Fixing up class pointer
                objectCopy = currentObject->data[0];

                previousObject = objectCopy->data[0];
                objectCopy->data[0] = replacement;
                currentObject->data[0] = objectCopy;

                replacement = objectCopy;
                currentObject = previousObject;
            } else {
                // last field from TObject
                uint32_t lastFieldIndex = currentObject->size.getSize();

                objectCopy = currentObject->data[lastFieldIndex];
                previousObject = objectCopy->data[lastFieldIndex];
                objectCopy->data[lastFieldIndex] = replacement;

                // Recovering zero fields
                lastFieldIndex--;
                while((lastFieldIndex > 0) && (currentObject->data[lastFieldIndex] == 0))
                {
                    objectCopy->data[lastFieldIndex] = 0;
                    lastFieldIndex--;
                }

                // Storing the last visited index to the size
                // If it gets zero then all fields were moved
                currentObject->size.setSize(lastFieldIndex);
                currentObject->size.setRelocated();

                objectCopy->data[lastFieldIndex] = previousObject;
                previousObject = currentObject;
                currentObject = currentObject->data[lastFieldIndex];
                previousObject->data[lastFieldIndex] = objectCopy;
                break;
            }
        }
    }
}


void BakerMemoryManager::collectGarbage()
{
    //get statistic before collect
    m_collectionsCount++;
    TMemoryManagerEvent* event = new TMemoryManagerEvent();
    event->eventName = "GC";
    gettimeofday(&(event->time), NULL);
    long tempTimeDiff = (event->time.tv_sec - m_memoryInfo.timeBegin.tv_sec)*1000000
                      + event->time.tv_usec - m_memoryInfo.timeBegin.tv_usec;
    event->time.tv_sec = tempTimeDiff / 1000000;
    event->time.tv_usec = tempTimeDiff - event->time.tv_sec * 1000000;
    event->heapInfo = new TMemoryManagerHeapInfo;
    event->heapInfo->usedHeapSizeBeforeCollect =  (m_heapSize - (m_activeHeapPointer - m_activeHeapBase))/1024;
    event->heapInfo->totalHeapSize = m_heapSize/1024;
    // First of all swapping the spaces
    if (m_activeHeapOne)
    {
        m_activeHeapBase = m_heapTwo;
        m_inactiveHeapBase = m_heapOne;
    } else {
        m_activeHeapBase = m_heapOne;
        m_inactiveHeapBase = m_heapTwo;
    }

    m_activeHeapOne = not m_activeHeapOne;

    m_inactiveHeapPointer = m_activeHeapPointer;
    m_activeHeapPointer = m_activeHeapBase + m_heapSize / 2;

    // Then, performing the collection. Seeking from the root
    // objects down the hierarchy to find active objects.
    // Then moving them to the new active heap.

    // Storing timestamp on start
    timeval tv1;
    gettimeofday(&tv1, NULL);

    // Moving the live objects in the new heap
    moveObjects();

    // Storing timestamp of the end
    timeval tv2;
    gettimeofday(&tv2, NULL);

    std::memset(m_inactiveHeapBase, 0, m_heapSize / 2);

    // Calculating total microseconds spent in the garbage collection procedure
    m_totalCollectionDelay += (tv2.tv_sec - tv1.tv_sec) * 1000000 + (tv2.tv_usec - tv1.tv_usec);
    event->heapInfo->usedHeapSizeAfterCollect =  (m_heapSize - (m_activeHeapPointer - m_activeHeapBase))/1024;
    event->timeDiff.tv_sec = m_totalCollectionDelay/1000000;
    event->timeDiff.tv_usec = m_totalCollectionDelay - event->timeDiff.tv_sec*1000000;
    m_memoryInfo.events.push_front(event);
    writeLogLine(event);
}

void BakerMemoryManager::moveObjects()
{
    // Here we need to check the rootStack, staticRoots and the VM execution context
    TStaticRootsIterator iRoot = m_staticRoots.begin();
    for (; iRoot != m_staticRoots.end(); ++iRoot) {
        **iRoot = moveObject(**iRoot);
    }

    // Updating external references. Typically these are pointers stored in the hptr<>
    object_ptr* currentPointer = m_externalPointersHead;
    while (currentPointer != 0) {
        currentPointer->data = reinterpret_cast<TObject*>( moveObject( reinterpret_cast<TMovableObject*>(currentPointer->data) ) );
        currentPointer = currentPointer->next;
    }
}

bool BakerMemoryManager::isInStaticHeap(void* location)
{
    return (location >= m_staticHeapPointer) && (location < m_staticHeapBase + m_staticHeapSize);
}

bool BakerMemoryManager::checkRoot(TObject* value, TObject** objectSlot)
{
    // Here we need to perform some actions depending on whether the object slot and
    // the value resides. Generally, all pointers from the static heap to the dynamic one
    // should be tracked by the GC because it may be the only valid link to the object.
    // Object may be collected otherwise.

    bool slotIsStatic  = isInStaticHeap(objectSlot);

    // Only static slots are subject of our interest
    if (slotIsStatic) {
        TObject* oldValue  = *objectSlot;

        bool valueIsStatic = isInStaticHeap(value);
        bool oldValueIsStatic = isInStaticHeap(oldValue);

        if (!valueIsStatic) {
            // Adding dynamic value to a static slot. If slot previously contained
            // the dynamic value then it means that slot was already registered before.
            // In that case we do not need to register it again.

            if (oldValueIsStatic) {
                addStaticRoot(objectSlot);
                return true; // Root list was altered
            }
        } else {
            // Adding static value to a static slot. Typically it means assigning something
            // like nilObject. We need to check what pointer was in the slot before (oldValue).
            // If it was dynamic, we need to remove the slot from the root list, so GC will not
            // try to collect a static value from the static heap (it's just a waste of time).

            if (!oldValueIsStatic) {
                removeStaticRoot(objectSlot);
                return true; // Root list was altered
            }
        }
    }

    // Root list was not altered
    return false;
}

void BakerMemoryManager::addStaticRoot(TObject** pointer)
{
    m_staticRoots.push_front( reinterpret_cast<TMovableObject**>(pointer) );
}

void BakerMemoryManager::removeStaticRoot(TObject** pointer)
{
    TStaticRootsIterator iRoot = m_staticRoots.begin();
    for (; iRoot != m_staticRoots.end(); ++iRoot) {
        if (*iRoot == reinterpret_cast<TMovableObject**>(pointer)) {
            m_staticRoots.erase(iRoot);
            return;
        }
    }
}

void BakerMemoryManager::registerExternalHeapPointer(object_ptr& pointer) {
    pointer.next = m_externalPointersHead;
    m_externalPointersHead = &pointer;
}

void BakerMemoryManager::releaseExternalHeapPointer(object_ptr& pointer) {
    if (m_externalPointersHead == &pointer) {
        m_externalPointersHead = pointer.next;
        return;
    }

    // If it is not the last element of the list
    //  we replace the given pointer with the next one
    if (pointer.next) {
        object_ptr* next_object = pointer.next;
        pointer.data = next_object->data;
        pointer.next = next_object->next;
    } else {
        // This is the last element, we have to find the previous
        // element in the list and unlink the given pointer
        object_ptr* previousPointer = m_externalPointersHead;
        while (previousPointer->next != &pointer)
            previousPointer = previousPointer->next;

        previousPointer->next = 0;
        return;
    }
}

TMemoryManagerInfo BakerMemoryManager::getStat()
{
    //FIXME collect statistic
    m_memoryInfo.leftToRightCollections = 0;
    m_memoryInfo.rightToLeftCollections = 0;
    m_memoryInfo.rightCollectionDelay   = 0;
    m_memoryInfo.allocationsCount       = m_allocationsCount;
    m_memoryInfo.collectionsCount       = m_collectionsCount;
    m_memoryInfo.totalCollectionDelay   = m_totalCollectionDelay;
    return m_memoryInfo;
}

memory.h

/*
 *    memory.h
 *
 *    LLST memory management routines and interfaces
 *
 *    LLST (LLVM Smalltalk or Low Level Smalltalk) version 0.2
 *
 *    LLST is
 *        Copyright (C) 2012-2013 by Dmitry Kashitsyn   <[email protected]>
 *        Copyright (C) 2012-2013 by Roman Proskuryakov <[email protected]>
 *
 *    LLST is based on the LittleSmalltalk which is
 *        Copyright (C) 1987-2005 by Timothy A. Budd
 *        Copyright (C) 2007 by Charles R. Childers
 *        Copyright (C) 2005-2007 by Danny Reinhold
 *
 *    Original license of LittleSmalltalk may be found in the LICENSE file.
 *
 *
 *    This file is part of LLST.
 *    LLST is free software: you can redistribute it and/or modify
 *    it under the terms of the GNU General Public License as published by
 *    the Free Software Foundation, either version 3 of the License, or
 *    (at your option) any later version.
 *
 *    LLST is distributed in the hope that it will be useful,
 *    but WITHOUT ANY WARRANTY; without even the implied warranty of
 *    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *    GNU General Public License for more details.
 *
 *    You should have received a copy of the GNU General Public License
 *    along with LLST.  If not, see <http://www.gnu.org/licenses/>.
 */

#ifndef LLST_MEMORY_H_INCLUDED
#define LLST_MEMORY_H_INCLUDED

#include <cstddef>
#include <stdint.h>
#include <types.h>
#include <vector>
#include <list>
#include <fstream>

struct TMemoryManagerHeapEvent{
    const char* eventName;
    //timeval time; //unusual value
    timeval timeDiff;
    uint32_t usedHeapSizeBeforeCollect;
    uint32_t usedHeapSizeAfterCollect;
    uint32_t totalHeapSize;
};

struct TMemoryManagerHeapInfo{
    uint32_t usedHeapSizeBeforeCollect;
    uint32_t usedHeapSizeAfterCollect;
    uint32_t totalHeapSize;
    std::list<TMemoryManagerHeapEvent*> heapEvents;
};

//represent three kinds of events in garbage collection log:
//just event, event which takes some time, event which interacting with a heap
struct TMemoryManagerEvent{
    const char* eventName;
    timeval time;
    timeval timeDiff; //maybe null
    TMemoryManagerHeapInfo* heapInfo; //maybe null
};


// Memory manager statics is held
// in the following structure
struct TMemoryManagerInfo {
    uint32_t collectionsCount;
    uint32_t allocationsCount;
    uint64_t totalCollectionDelay;

    uint32_t leftToRightCollections;
    uint32_t rightToLeftCollections;
    uint64_t rightCollectionDelay;
    timeval timeBegin;
    std::list<TMemoryManagerEvent*> events;
};

struct object_ptr {
    TObject* data;
    object_ptr* next;
    object_ptr() : data(0), next(0) {}
    explicit object_ptr(TObject* data)  : data(data), next(0) {}
    object_ptr& operator=(const object_ptr& value) { this->data = value.data; return *this; }
private:
    object_ptr(const object_ptr& value);
};

// Generic interface to a memory manager.
// Custom implementations such as BakerMemoryManager
// implement this interface.
class IMemoryManager {
public:
    virtual bool initializeHeap(std::size_t heapSize, std::size_t maxSize = 0) = 0;
    virtual bool initializeStaticHeap(std::size_t staticHeapSize) = 0;

    virtual void* allocate(std::size_t size, bool* collectionOccured = 0) = 0;
    virtual void* staticAllocate(std::size_t size) = 0;
    virtual void  collectGarbage() = 0;

    virtual bool  checkRoot(TObject* value, TObject** objectSlot) = 0;
    virtual void  addStaticRoot(TObject** pointer) = 0;
    virtual void  removeStaticRoot(TObject** pointer) = 0;
    virtual bool  isInStaticHeap(void* location) = 0;

    // External pointer handling
    virtual void  registerExternalHeapPointer(object_ptr& pointer) = 0;
    virtual void  releaseExternalHeapPointer(object_ptr& pointer) = 0;

    virtual uint32_t allocsBeyondCollection() = 0;
    virtual TMemoryManagerInfo getStat() = 0;

    virtual ~IMemoryManager() {};
};

// When pointer to a heap object is stored outside of the heap,
// specific actions need to be taken in order to prevent pointer
// invalidation due to GC procedure. External pointers need to be
// registered in GC so it will use this pointers as roots for the
// object traversing. GC will update the pointer data with the
// actual object location. hptr<> helps to organize external pointers
// by automatically calling registerExternalPointer() in constructor
// and releaseExternalPointer() in desctructor.
//
// External pointers are widely used in the VM execution code.
// VM provide helper functions newPointer() and newObject() which
// deal with hptr<> in a user friendly way. Use of these functions
// is highly recommended.

template <typename O> class hptr_base {
public:
    typedef O Object;

protected:
    object_ptr target;  // TODO static heap optimization && volatility
    IMemoryManager* mm; // TODO assign on copy operators
    bool isRegistered;  // TODO Pack flag into address
public:
    hptr_base(Object* object, IMemoryManager* mm, bool registerPointer = true)
    : target(object), mm(mm), isRegistered(registerPointer)
    {
        if (mm && registerPointer) mm->registerExternalHeapPointer(target);
            //mm->registerExternalPointer((TObject**) &target);
    }

    hptr_base(const hptr_base<Object>& pointer) : target(pointer.target.data), mm(pointer.mm), isRegistered(true)
    {
        if (mm) mm->registerExternalHeapPointer(target);
    }

    ~hptr_base() { if (mm && isRegistered) mm->releaseExternalHeapPointer(target); }

    //hptr_base<Object>& operator = (hptr_base<Object>& pointer) { target = pointer.target; return *this; }
    //hptr_base<Object>& operator = (Object* object) { target = object; return *this; }

    Object* rawptr() const { return static_cast<Object*>(target.data); }
    Object* operator -> () const { return static_cast<Object*>(target.data); }
    //Object& (operator*)() const { return *target; }
    operator Object*() const { return static_cast<Object*>(target.data); }

    template<typename C> C* cast() const { return static_cast<C*>(target.data); }
};

template <typename O> class hptr : public hptr_base<O> {
public:
    typedef O Object;
public:
    hptr(Object* object, IMemoryManager* mm, bool registerPointer = true) : hptr_base<Object>(object, mm, registerPointer) {}
    hptr(const hptr<Object>& pointer) : hptr_base<Object>(pointer) { }
    hptr<Object>& operator = (Object* object) { hptr_base<Object>::target.data = object; return *this; }

//     template<typename I>
//     Object& operator [] (I index) const { return hptr_base<Object>::target->operator[](index); }
};

// Hptr specialization for TArray<> class.
// Provides typed [] operator that allows
// convinient indexed access to the array contents
template <typename T> class hptr< TArray<T> > : public hptr_base< TArray<T> > {
public:
    typedef TArray<T> Object;
public:
    hptr(Object* object, IMemoryManager* mm, bool registerPointer = true) : hptr_base<Object>(object, mm, registerPointer) {}
    hptr(const hptr<Object>& pointer) : hptr_base<Object>(pointer) { }
    hptr<Object>& operator = (Object* object) { hptr_base<Object>::target.data = object; return *this; }

    template<typename I> T*& operator [] (I index) const { return hptr_base<Object>::target.data->operator[](index); }
};

// Hptr specialization for TByteObject.
// Provides typed [] operator that allows
// convinient indexed access to the bytearray contents
template <> class hptr<TByteObject> : public hptr_base<TByteObject> {
public:
    typedef TByteObject Object;
public:
    hptr(Object* object, IMemoryManager* mm, bool registerPointer = true) : hptr_base<Object>(object, mm, registerPointer) {}
    hptr(const hptr<Object>& pointer) : hptr_base<Object>(pointer) { }

    uint8_t& operator [] (uint32_t index) const { return static_cast<Object*>(target.data)->operator[](index); }
};

// Simple memory manager implementing classic baker two space algorithm.
// Each time two separate heaps are allocated but only one is active.
//
// When we need to allocate more memory but no space left on the current heap
// then garbage collection procedure takes place. It simply moves objects from
// the active heap to the inactive one and fixes the original pointers so they
// start directing to a new place. Collection is started from the root objects
// on the root stack and then on static allocated heap traversing reference tree in depth.
// When collection is done heaps are interchanged so the new one became active.
// All objects that were not moved during the collection are said to be disposed,
// so thier space may be reused by newly allocated ones.
//
class BakerMemoryManager : public IMemoryManager
{
protected:
    uint32_t  m_collectionsCount;
    uint32_t  m_allocationsCount;
    uint64_t  m_totalCollectionDelay;

    std::size_t m_heapSize;
    std::size_t m_maxHeapSize;

    uint8_t*  m_heapOne;
    uint8_t*  m_heapTwo;
    bool      m_activeHeapOne;

    uint8_t*  m_inactiveHeapBase;
    uint8_t*  m_inactiveHeapPointer;
    uint8_t*  m_activeHeapBase;
    uint8_t*  m_activeHeapPointer;

    std::size_t m_staticHeapSize;
    uint8_t*  m_staticHeapBase;
    uint8_t*  m_staticHeapPointer;

    //FIXME delete from memory meneger. initize somewhere else 
    std::fstream       m_logFile;
    TMemoryManagerInfo m_memoryInfo;
    void writeLogLine(TMemoryManagerEvent *event);

    struct TRootPointers {
        uint32_t size;
        uint32_t top;
        TObject* data[0];
    };

    // During GC we need to treat all objects in a very simple manner,
    // just as pointer holders. Class field is also a pointer so we
    // treat it just as one more object field.
    struct TMovableObject {
        TSize size;
        TMovableObject* data[0];

        TMovableObject(uint32_t dataSize, bool isBinary = false) : size(dataSize, isBinary) { }
    };

    /*virtual*/ TMovableObject* moveObject(TMovableObject* object);
    virtual void moveObjects();
    virtual void growHeap(uint32_t requestedSize);

    // These variables contain an array of pointers to objects from the
    // static heap to the dynamic one. Ihey are used during the GC
    // as a root for pointer iteration.

    // FIXME Temporary solution before GC will prove it's working
    //       Think about better memory organization
    typedef std::list<TMovableObject**> TStaticRoots;
    typedef std::list<TMovableObject**>::iterator TStaticRootsIterator;
    TStaticRoots m_staticRoots;

    // External pointers are typically managed by hptr<> template.
    // When pointer to a heap object is stored outside of the heap,
    // specific actions need to be taken in order to prevent pointer
    // invalidation. GC uses this information to correct external
    // pointers so they will point to correct location even after
    // garbage collection.
    object_ptr* m_externalPointersHead;
public:
    BakerMemoryManager();
    virtual ~BakerMemoryManager();

    virtual bool  initializeHeap(std::size_t heapSize, std::size_t maxHeapSize = 0);
    virtual bool  initializeStaticHeap(std::size_t staticHeapSize);
    virtual void* allocate(std::size_t requestedSize, bool* gcOccured = 0);
    virtual void* staticAllocate(std::size_t requestedSize);
    virtual void  collectGarbage();

    virtual bool  checkRoot(TObject* value, TObject** objectSlot);
    virtual void  addStaticRoot(TObject** pointer);
    virtual void  removeStaticRoot(TObject** pointer);
    virtual bool  isInStaticHeap(void* location);

    // External pointer handling
    virtual void  registerExternalHeapPointer(object_ptr& pointer);
    virtual void  releaseExternalHeapPointer(object_ptr& pointer);

    // Returns amount of allocations that were done after last GC
    // May be used as a flag that GC had just took place
    virtual uint32_t allocsBeyondCollection() { return m_allocationsCount; }

    virtual TMemoryManagerInfo getStat();
};

class GenerationalMemoryManager : public BakerMemoryManager
{
protected:
    uint32_t m_leftToRightCollections;
    uint32_t m_rightToLeftCollections;
    uint32_t m_rightCollectionDelay;

    void collectLeftToRight(bool fullCollect = false);
    void collectRightToLeft();
    bool checkThreshold();
    void moveYoungObjects();

    bool isInYoungHeap(void* location);
    void addCrossgenReference(TObject** pointer);
    void removeCrossgenReference(TObject** pointer);

    typedef std::list<TMovableObject**> TPointerList;
    typedef std::list<TMovableObject**>::iterator TPointerIterator;
    TPointerList m_crossGenerationalReferences;
public:
    GenerationalMemoryManager() : BakerMemoryManager(),
        m_leftToRightCollections(0), m_rightToLeftCollections(0), m_rightCollectionDelay(0) { }
    virtual ~GenerationalMemoryManager();

    virtual bool checkRoot(TObject* value, TObject** objectSlot);
    virtual void collectGarbage();
    virtual TMemoryManagerInfo getStat();
};

class NonCollectMemoryManager : public IMemoryManager
{
protected:
    size_t    m_heapSize;
    uint8_t*  m_heapBase;
    uint8_t*  m_heapPointer;

    std::vector<void*> m_usedHeaps;

    size_t    m_staticHeapSize;
    uint8_t*  m_staticHeapBase;
    uint8_t*  m_staticHeapPointer;

    void growHeap();
public:
    NonCollectMemoryManager();
    virtual ~NonCollectMemoryManager();

    virtual bool  initializeHeap(size_t heapSize, size_t maxHeapSize = 0);
    virtual bool  initializeStaticHeap(size_t staticHeapSize);
    virtual void* allocate(size_t requestedSize, bool* gcOccured = 0);
    virtual void* staticAllocate(size_t requestedSize);
    virtual bool  isInStaticHeap(void* location);

    virtual void  collectGarbage() {}
    virtual void  addStaticRoot(TObject** pointer) {}
    virtual void  removeStaticRoot(TObject** pointer) {}
    virtual void  registerExternalPointer(TObject** pointer) {}
    virtual void  releaseExternalPointer(TObject** pointer) {}
    virtual void  registerExternalHeapPointer(object_ptr& pointer) {}
    virtual void  releaseExternalHeapPointer(object_ptr& pointer) {}
    virtual bool  checkRoot(TObject* value, TObject** objectSlot) { return false; }
    virtual uint32_t allocsBeyondCollection() { return 0; }
    virtual TMemoryManagerInfo getStat() { return TMemoryManagerInfo(); }
};

class LLVMMemoryManager : public BakerMemoryManager {
protected:
    virtual void moveObjects();

public:
    struct TFrameMap {
        int32_t numRoots;
        int32_t numMeta;
        const void* meta[0];
    };

    struct TStackEntry {
        TStackEntry* next;
        const TFrameMap* map;
        void* roots[0];
    };

    struct TMetaInfo {
        bool isStackObject : 1;
    };

    LLVMMemoryManager();
    virtual ~LLVMMemoryManager();
};

extern "C" { extern LLVMMemoryManager::TStackEntry* llvm_gc_root_chain; }

class Image
{
private:
    std::vector<TObject*> m_indirects;
    std::ifstream m_inputStream;

    enum TImageRecordType {
        invalidObject = 0,
        ordinaryObject,
        inlineInteger,  // inline 32 bit integer in network byte order
        byteObject,     //
        previousObject, // link to previously loaded object
        nilObject       // uninitialized (nil) field
    };

    uint32_t readWord();
    TObject* readObject();
    template<typename ResultType>
    ResultType* readObject() { return static_cast<ResultType*>(readObject()); }

    IMemoryManager* m_memoryManager;
public:
    Image(IMemoryManager* manager)
        : m_memoryManager(manager)
    { }

    bool     loadImage(const std::string& fileName);
    void     storeImage(const char* fileName);

    template<typename N> TObject* getGlobal(const N* name) const;
    template<typename T, typename N> T* getGlobal(const N* name) const { return static_cast<T*>(getGlobal(name)); }

    class ImageWriter;
    // GLobal VM objects
};

struct TGlobals {
    TObject* nilObject;
    TObject* trueObject;
    TObject* falseObject;
    TClass*  smallIntClass;
    TClass*  arrayClass;
    TClass*  blockClass;
    TClass*  contextClass;
    TClass*  stringClass;
    TDictionary* globalsObject;
    TMethod* initialMethod;
    TObject* binaryMessages[3];
    TClass*  integerClass;
    TSymbol* badMethodSymbol;
};

extern TGlobals globals;

class Image::ImageWriter
{
private:
    std::vector<TObject*> m_writtenObjects; //used to link objects together with type 'previousObject'
    TGlobals              m_globals;

    TImageRecordType getObjectType(TObject* object) const;
    int              getPreviousObjectIndex(TObject* object) const;
    void             writeWord(std::ofstream& os, uint32_t word);
    void             writeObject(std::ofstream& os, TObject* object);
public:
    ImageWriter();
    ImageWriter& setGlobals(const TGlobals& globals);
    void writeTo(const char* fileName);
};

#endif