dvander@49: /* vim: set ts=4 sw=4 tw=99 et:
dvander@49:  *
dvander@49:  * Copyright (C) 2012 David Anderson
dvander@49:  *
dvander@49:  * This file is part of JITCraft.
dvander@49:  *
dvander@49:  * JITCraft is free software: you can redistribute it and/or modify it under
dvander@49:  * the terms of the GNU General Public License as published by the Free
dvander@49:  * Software Foundation, either version 3 of the License, or (at your option)
dvander@49:  * any later version.
dvander@49:  * 
dvander@49:  * Foobar is distributed in the hope that it will be useful, but WITHOUT ANY
dvander@49:  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
dvander@49:  * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
dvander@49:  *
dvander@49:  * You should have received a copy of the GNU General Public License along with
dvander@49:  * JITCraft. If not, see http://www.gnu.org/licenses/.
dvander@49:  */
danderson@91: #include <string.h>
dvander@53: #include "Zone.h"
dvander@49: #include "Spaces.h"
dvander@49: #include "Platform.h"
dvander@49: #include "Spaces-inl.h"
danderson@92: #include "Heap-inl.h"
dvander@49: 
dvander@59: using namespace ke;
dvander@49: 
dvander@49: HeapStack::HeapStack()
dvander@51:   : chunk_(NULL),
dvander@51:     cursor_(NULL)
dvander@49: {
dvander@49: }
dvander@49: 
dvander@49: HeapStack::~HeapStack()
dvander@49: {
dvander@51:     if (chunk_)
dvander@51:         HeapChunk::Destroy(chunk_);
dvander@49: }
dvander@49: 
dvander@49: bool
dvander@49: HeapStack::initialize()
dvander@49: {
dvander@51:     chunk_ = HeapChunk::New(NULL, kStackSize);
dvander@51:     cursor_ = chunk_->first();
dvander@49:     return true;
dvander@49: }
dvander@49: 
dvander@11: HeapChunk *
dvander@11: HeapChunk::New(HeapChunk *prev, size_t size)
dvander@11: {
dvander@11:     OS::AlignableMapping map = 
dvander@11:         OS::MapAlignedMemory(size, HeapChunk::kAlignment, OS::Map_Commit);
dvander@11: 
dvander@11:     if (!map.base())
dvander@11:         return NULL;
dvander@11: 
dvander@11:     HeapChunk *chunk = reinterpret_cast<HeapChunk *>(map.aligned());
dvander@11:     chunk->base_ = map.base();
dvander@11:     chunk->end_ = map.base() + map.size();
dvander@11:     if (prev)
dvander@11:         prev->next_ = chunk;
dvander@11: 
dvander@11:     return chunk;
dvander@11: }
dvander@11: 
dvander@11: void
dvander@11: HeapChunk::Destroy(HeapChunk *chunk)
dvander@11: {
dvander@11:     OS::UnmapAlignedMemory(chunk->base(), chunk->size());
dvander@11: }
dvander@11: 
dvander@53: void
dvander@53: HeapChunk::resetMarkBits()
dvander@53: {
dvander@53:     memset(markBits(), 0, kMarkBytes);
dvander@53: }
dvander@53: 
dvander@53: FreeList::FreeList()
dvander@53:   : small_objects_(NULL),
dvander@53:     medium_objects_(NULL),
dvander@53:     large_objects_(NULL),
dvander@53:     huge_objects_(NULL)
dvander@53: {
dvander@53: }
dvander@53: 
dvander@53: void
dvander@53: FreeList::add(FreedObject *obj)
dvander@53: {
dvander@53:     if (obj->size() < kMinObjectSize) 
dvander@53:         return;
dvander@53: 
dvander@53:     FreedObject **list;
dvander@53:     if (obj->size() < kMaxSmallObject)
dvander@53:         list = &small_objects_;
dvander@53:     else if (obj->size() < kMaxMediumObject)
dvander@53:         list = &medium_objects_;
dvander@53:     else if (obj->size() < kMaxLargeObject)
dvander@53:         list = &large_objects_;
dvander@53:     else
dvander@53:         list = &huge_objects_;
dvander@53: 
dvander@53:     if (*list)
dvander@53:         (*list)->setNext(obj);
dvander@53:     *list = obj;
dvander@53: }
dvander@53: 
dvander@53: FreedObject *
dvander@53: FreeList::pick(size_t size)
dvander@53: {
dvander@53:     if (size < kMinObjectSize && small_objects_) {
dvander@53:         FreedObject *obj = small_objects_;
dvander@53:         small_objects_ = small_objects_->next();
dvander@53:         return obj;
dvander@53:     }
dvander@53:     if (size < kMaxSmallObject && medium_objects_) {
dvander@53:         FreedObject *obj = medium_objects_;
dvander@53:         medium_objects_ = medium_objects_->next();
dvander@53:         return obj;
dvander@53:     }
dvander@53:     if (size < kMaxMediumObject && large_objects_) {
dvander@53:         FreedObject *obj = large_objects_;
dvander@53:         large_objects_ = large_objects_->next();
dvander@53:         return obj;
dvander@53:     }
dvander@53:     if (huge_objects_) {
dvander@53:         FreedObject *obj = huge_objects_;
dvander@53:         huge_objects_ = huge_objects_->next();
dvander@53:         return obj;
dvander@53:     }
dvander@53:     return NULL;
dvander@53: }
dvander@53: 
dvander@53: void
dvander@53: FreeList::reset()
dvander@53: {
dvander@53:     small_objects_ = NULL;
dvander@53:     medium_objects_ = NULL;
dvander@53:     large_objects_ = NULL;
dvander@53:     huge_objects_ = NULL;
dvander@53: }
dvander@53: 
dvander@53: OldSpace::OldSpace(Zone *zone)
dvander@53:   : zone_(zone),
dvander@53:     first_(NULL),
dvander@11:     last_(NULL)
dvander@11: {
dvander@11: }
dvander@11: 
dvander@11: bool
dvander@11: OldSpace::initialize()
dvander@11: {
dvander@11:     first_ = HeapChunk::New(first_, HeapChunk::kDefaultSize);
dvander@11:     last_ = first_;
dvander@51:     cursor_ = first_->first();
dvander@11: 
dvander@11:     return !!first_;
dvander@11: }
dvander@11: 
dvander@53: OldSpace::~OldSpace()
dvander@53: {
dvander@53:     while (first_) {
dvander@53:         HeapChunk *temp = first_->next();
dvander@53:         HeapChunk::Destroy(first_);
dvander@53:         first_ = temp;
dvander@53:     }
dvander@53: }
dvander@53: 
dvander@11: Address
dvander@11: OldSpace::allocateSlow(size_t nbytes)
dvander@11: {
dvander@53:     if (FreedObject *obj = freelist_.pick(nbytes)) {
dvander@53:         Address address = reinterpret_cast<Address>(obj);
dvander@53:         size_t actual = obj->size();
dvander@53:         assert(actual >= nbytes);
dvander@53:         if (actual != nbytes)
dvander@53:             markRegionFree(address + nbytes, actual - nbytes);
dvander@53: 
dvander@53:         return address;
dvander@53:     }
dvander@53: 
dvander@53:     // Free unused stuff at the end of the current chunk.
dvander@53:     if (cursor_ != last_->end())
dvander@53:         markRegionFree(cursor_, last_->end() - cursor_);
dvander@53: 
dvander@53:     HeapChunk *chunk;
dvander@53:     if (last_->next()) {
dvander@53:         // The next chunk is guaranteed to be empty.
dvander@53:         chunk = last_->next();
dvander@53:     } else {
dvander@53:         chunk = HeapChunk::New(last_, HeapChunk::kDefaultSize);
dvander@53:         if (!chunk)
dvander@53:             return NULL;
dvander@53:     }
dvander@11: 
dvander@51:     last_ = chunk;
dvander@51:     cursor_ = chunk->first();
dvander@51: 
dvander@51:     assert(cursor_ + nbytes <= chunk->end());
dvander@51: 
dvander@51:     Address address = cursor_;
dvander@51:     cursor_ += nbytes;
dvander@51:     return address;
dvander@11: }
dvander@11: 
dvander@53: void
dvander@53: OldSpace::markRegionFree(Address start, size_t length)
dvander@53: {
dvander@53:     FreedObject *obj = reinterpret_cast<FreedObject *>(start);
dvander@53:     new (obj) FreedObject(zone_->getMap(MapKind_FreeRegion), length);
dvander@53: 
dvander@53:     if (length < sizeof(FreedObject)) {
dvander@53:         // Can't encode a list in this object, but it's marked free, so we're done.
dvander@53:         return;
dvander@53:     }
dvander@53: 
dvander@53:     freelist_.add(obj);
dvander@53: }
dvander@53: 
dvander@53: void
dvander@53: OldSpace::freeUnusedPages()
dvander@11: {
dvander@53:     HeapChunk **prev = &first_;
dvander@53:     HeapChunk *empty = NULL;
dvander@53:     while (*prev) {
dvander@53:         HeapChunk *chunk = *prev;
dvander@53:         if (chunk->isEmpty()) {
dvander@53:             *prev = chunk->next();
dvander@53:             if (empty) {
dvander@53:                 // Remove this chunk.
dvander@53:                 HeapChunk::Destroy(chunk);
dvander@53:                 continue;
dvander@53:             }
dvander@53:             empty = chunk;                
dvander@53:         }
dvander@53:         prev = chunk->nextp();
dvander@11:     }
dvander@53: 
dvander@53:     if (empty) {
dvander@53:         *empty->nextp() = NULL;
dvander@53:         *last_->nextp() = empty;
dvander@53:     }
dvander@53: }
dvander@53: 
dvander@53: void
dvander@53: OldSpace::resetFreeList()
dvander@53: {
dvander@53:     freelist_.reset();
dvander@11: }
dvander@49: 
dvander@50: LargeObjectSpace::LargeObjectSpace()
dvander@50:   : first_(NULL),
dvander@50:     last_(NULL)
dvander@50: {
dvander@50: }
dvander@50: 
dvander@50: LargeObjectSpace::~LargeObjectSpace()
dvander@50: {
dvander@50:     while (first_) {
dvander@50:         HeapChunk *temp = first_->next();
dvander@50:         HeapChunk::Destroy(first_);
dvander@50:         first_ = temp;
dvander@50:     }
dvander@50: }
dvander@50: 
dvander@50: bool
dvander@50: LargeObjectSpace::initialize()
dvander@50: {
dvander@50:     return true;
dvander@50: }
dvander@49: 
dvander@49: Address
dvander@49: LargeObjectSpace::allocate(size_t nbytes)
dvander@49: {
dvander@49:     assert(IsAligned(nbytes, kObjectAlignment));
dvander@49: 
dvander@50:     // Always allocate a new chunk for large objects.
dvander@50:     HeapChunk *chunk = HeapChunk::New(last_, nbytes);
dvander@50:     if (!chunk)
dvander@50:         return NULL;
dvander@49: 
dvander@50:     if (!first_)
dvander@50:         first_ = chunk;
dvander@50:     last_ = chunk;
dvander@49: 
dvander@51:     return chunk->first();
dvander@49: }
dvander@49: 
dvander@53: void
dvander@53: LargeObjectSpace::sweep()
dvander@53: {
dvander@53:     if (!first_)
dvander@53:         return;
dvander@53: 
dvander@53:     HeapChunk **pprev = &first_;
dvander@53:     do {
dvander@53:         HeapChunk *chunk = *pprev;
dvander@53:         Object *obj = reinterpret_cast<Object *>(chunk->first());
dvander@53:         MarkBit bit = HeapChunk::GetMarkBit(obj);
dvander@53:         if (HeapChunk::IsWhite(bit)) {
dvander@53:             *pprev = chunk->next();
dvander@53:             HeapChunk::Destroy(chunk);
dvander@53:         } else {
dvander@53:             assert(HeapChunk::IsBlack(bit));
dvander@53:             HeapChunk::Clear(bit);
dvander@53:             pprev = chunk->nextp();
dvander@53:             last_ = chunk;
dvander@53:         }
dvander@53:     } while (*pprev);
dvander@53: }