/* vim: set ts=4 sw=4 tw=99 et:

 *

 * Copyright (C) 2012 David Anderson

 *

 * This file is part of SourcePawn.

 *

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

 * 

 * SourcePawn 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

 * SourcePawn. If not, see http://www.gnu.org/licenses/.

 */

#ifndef _include_jitcraft_heap_h_

#define _include_jitcraft_heap_h_

#include "Utility.h"

#include "Spaces.h"

#include "Barriers.h"

#include "Objects.h"

#include "Handles.h"

namespace ke {

class Zone;

class MarkStack;

// Heap-allocated objects go here. Heaps are thread-local. The heap contains

// four spaces:

//

//    LIFO Space:  Used for objects that may be stack-allocated.

//    Old Space:   Used for objects that are expected to be long-lived, or that

//                 survive one collection.

//    Large Space: Used for objects that are so large they should never be

//                 moved between spaces.

//

// ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY.

// ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY!

//

// ---------------------------------------------------------------------------

//

// The following is a high-level overview of how garbage collection works in

// Keima. Detailed notes are present in Heap.cpp.

//

// THE TRI-COLOR INVARIANT: Via an object's mark bits, we maintain the

//   property that an object that has been fully marked may never reference a

//   dead object. Objects exist in three states during collection: unmarked

//   (white), scheduled for marking (grey), and fully marked (black).

//

//   When initiating collection, all objects are white. Objects in the root

//   set are made grey. The marking process takes grey objects and marks that

//   each child object is live: if the child is white, it becomes grey. Once

//   all children are grey or black, the parent grey object can become black,

//   as it has been fully traversed.

//

//   The result of this process is that when there are no more grey objects,

//   then we are guaranteed that all black objects are live, and all white

//   objects are dead.

//

// MAJOR COLLECTIONS are performed periodically, when either a given memory

//   threshold has been reached, or when requested by the host application.

//   They are also performed if no memory can be allocated.

//

//   Major collections are extremely slow; they require full heap traversal,

//   which can take more than a second on very large heaps. However, they

//   have the greatest chance at reclaiming all syntactically dead objects.

//

// SWEEPING is performed after major collections. The free space in between

//   live objects is added to a free list. Tenured allocations are then

//   performed in the free space, if possible.

//

class Heap

{

    Zone *zone_;

    HeapStack lifoSpace_;

    OldSpace mapSpace_;

    OldSpace oldSpace_;

    LargeObjectSpace largeSpace_;

    Map *metaMap_;

    // This is a big hunk o' memory used for marking iteratively. Eventually,

    // this will be replaced by the inactive semispace in the nursery.

    void *markStack_;

  public:

    enum Tenure {

        // Default, objects go into the nursery.

        Tenure_Default,

        // If objects are proven to not escape the stack, they can go into

        // a LIFO arena. Allocation on the LIFO arena is not guaranteed to

        // succeed; thus, objects may still be allocated in other arenas.

        Tenure_Stack,

        // Objects that should not go into the nursery (i.e. are expected

        // to be long-living) go here.

        Tenure_Old

    };

  private:

    inline Address newLargeObject(size_t bytes);

    inline Address newOldObject(size_t bytes);

    inline Address newStackObject(size_t bytes);

    inline Address newObject(size_t bytes, Tenure pretenure);

  private:

    void findGreyObjects(MarkStack &stack);

    void mark();

    void sweep();

    void reportOutOfMemory();

  public:

    Heap(Zone *zone);

    ~Heap();

    bool initialize();

    inline Object *allocate(Handle<Map> map, size_t byes, Tenure pretenure);

    Map *allocateMap(MapKind kind, size_t bytes);

    Map *metaMap() {

        return metaMap_;

    }

    inline Address lifoPosition() const {

        return lifoSpace_.position();

    }

    inline void unwindLifo(Address to) {

        lifoSpace_.unwind(to);

    }

    // Perform a full garbage collection.

    void reclaim();

};

}

#endif //_include_jitcraft_heap_h_