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