dvander@49: /* vim: set ts=4 sw=4 tw=99 et:
dvander@49:  *
dvander@28:  * Copyright (C) 2012 David Anderson
dvander@28:  *
dvander@122:  * This file is part of SourcePawn.
dvander@28:  *
dvander@122:  * SourcePawn is free software: you can redistribute it and/or modify it under
dvander@28:  * the terms of the GNU General Public License as published by the Free
dvander@28:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@28:  * any later version.
dvander@28:  * 
dvander@122:  * SourcePawn is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@28:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@28:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@28:  *
dvander@28:  * You should have received a copy of the GNU General Public License along with
dvander@122:  * SourcePawn. If not, see http://www.gnu.org/licenses/.
dvander@28:  */
dvander@28: #ifndef _include_jitcraft_heap_h_
dvander@28: #define _include_jitcraft_heap_h_
dvander@28: 
dvander@28: #include "Utility.h"
dvander@28: #include "Spaces.h"
dvander@28: #include "Barriers.h"
dvander@28: #include "Objects.h"
dvander@28: #include "Handles.h"
dvander@28: 
dvander@59: namespace ke {
dvander@28: 
dvander@28: class Zone;
dvander@52: class MarkStack;
dvander@28: 
dvander@49: // Heap-allocated objects go here. Heaps are thread-local. The heap contains
dvander@49: // four spaces:
dvander@49: //
dvander@49: //    LIFO Space:  Used for objects that may be stack-allocated.
dvander@49: //    Old Space:   Used for objects that are expected to be long-lived, or that
dvander@49: //                 survive one collection.
dvander@49: //    Large Space: Used for objects that are so large they should never be
dvander@49: //                 moved between spaces.
dvander@49: //
dvander@53: // ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY.
dvander@53: // ALLOCATING AN OBJECT DOES NOT ZERO ITS MEMORY!
dvander@53: //
dvander@53: // ---------------------------------------------------------------------------
dvander@53: //
dvander@52: // The following is a high-level overview of how garbage collection works in
dvander@52: // Keima. Detailed notes are present in Heap.cpp.
dvander@52: //
dvander@53: // THE TRI-COLOR INVARIANT: Via an object's mark bits, we maintain the
dvander@53: //   property that an object that has been fully marked may never reference a
dvander@53: //   dead object. Objects exist in three states during collection: unmarked
dvander@53: //   (white), scheduled for marking (grey), and fully marked (black).
dvander@52: //
dvander@53: //   When initiating collection, all objects are white. Objects in the root
dvander@53: //   set are made grey. The marking process takes grey objects and marks that
dvander@53: //   each child object is live: if the child is white, it becomes grey. Once
dvander@53: //   all children are grey or black, the parent grey object can become black,
dvander@53: //   as it has been fully traversed.
dvander@52: //
dvander@52: //   The result of this process is that when there are no more grey objects,
dvander@52: //   then we are guaranteed that all black objects are live, and all white
dvander@52: //   objects are dead.
dvander@49: //
dvander@49: // MAJOR COLLECTIONS are performed periodically, when either a given memory
dvander@49: //   threshold has been reached, or when requested by the host application.
dvander@49: //   They are also performed if no memory can be allocated.
dvander@49: //
dvander@49: //   Major collections are extremely slow; they require full heap traversal,
dvander@49: //   which can take more than a second on very large heaps. However, they
dvander@49: //   have the greatest chance at reclaiming all syntactically dead objects.
dvander@49: //
dvander@49: // SWEEPING is performed after major collections. The free space in between
dvander@49: //   live objects is added to a free list. Tenured allocations are then
dvander@49: //   performed in the free space, if possible.
dvander@49: //
dvander@28: class Heap
dvander@28: {
dvander@28:     Zone *zone_;
dvander@28:     HeapStack lifoSpace_;
dvander@28:     OldSpace mapSpace_;
dvander@28:     OldSpace oldSpace_;
dvander@49:     LargeObjectSpace largeSpace_;
dvander@28: 
dvander@28:     Map *metaMap_;
dvander@28: 
dvander@52:     // This is a big hunk o' memory used for marking iteratively. Eventually,
dvander@52:     // this will be replaced by the inactive semispace in the nursery.
dvander@52:     void *markStack_;
dvander@52: 
dvander@11:   public:
dvander@28:     enum Tenure {
dvander@28:         // Default, objects go into the nursery.
dvander@28:         Tenure_Default,
dvander@28:         
dvander@28:         // If objects are proven to not escape the stack, they can go into
dvander@28:         // a LIFO arena. Allocation on the LIFO arena is not guaranteed to
dvander@28:         // succeed; thus, objects may still be allocated in other arenas.
dvander@28:         Tenure_Stack,
dvander@28: 
dvander@28:         // Objects that should not go into the nursery (i.e. are expected
dvander@28:         // to be long-living) go here.
dvander@28:         Tenure_Old
dvander@28:     };
dvander@28: 
dvander@28:   private:
dvander@49:     inline Address newLargeObject(size_t bytes);
dvander@49:     inline Address newOldObject(size_t bytes);
dvander@28:     inline Address newStackObject(size_t bytes);
dvander@28:     inline Address newObject(size_t bytes, Tenure pretenure);
dvander@11: 
dvander@53:   private:
dvander@53:     void findGreyObjects(MarkStack &stack);
dvander@51:     void mark();
dvander@53:     void sweep();
dvander@51: 
dvander@69:     void reportOutOfMemory();
dvander@69: 
dvander@28:   public:
dvander@28:     Heap(Zone *zone);
dvander@52:     ~Heap();
dvander@28:     bool initialize();
dvander@28: 
dvander@28:     inline Object *allocate(Handle<Map> map, size_t byes, Tenure pretenure);
dvander@28:     Map *allocateMap(MapKind kind, size_t bytes);
dvander@28: 
dvander@28:     Map *metaMap() {
dvander@28:         return metaMap_;
dvander@28:     }
dvander@28:     inline Address lifoPosition() const {
dvander@28:         return lifoSpace_.position();
dvander@28:     }
dvander@28:     inline void unwindLifo(Address to) {
dvander@28:         lifoSpace_.unwind(to);
dvander@28:     }
dvander@49: 
dvander@49:     // Perform a full garbage collection.
dvander@49:     void reclaim();
dvander@28: };
dvander@28: 
dvander@28: }
dvander@28: 
dvander@28: #endif //_include_jitcraft_heap_h_