blob: d7381d760b772918a8feeb189c90c1f95e3f1567 [file] [log] [blame]
// Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file
// for details. All rights reserved. Use of this source code is governed by a
// BSD-style license that can be found in the LICENSE file.
#include "vm/globals.h"
#include "vm/heap/freelist.h"
#include "vm/heap/spaces.h"
#include "vm/lockers.h"
#include "vm/ring_buffer.h"
#include "vm/thread.h"
#include "vm/virtual_memory.h"
namespace dart {
DECLARE_FLAG(bool, log_code_drop);
DECLARE_FLAG(bool, always_drop_code);
DECLARE_FLAG(bool, write_protect_code);
// Forward declarations.
class Heap;
class JSONObject;
class ObjectPointerVisitor;
class ObjectSet;
class ForwardingPage;
class GCMarker;
// TODO(iposva): Determine heap sizes and tune the page size accordingly.
static const intptr_t kPageSize = 256 * KB;
static const intptr_t kPageSizeInWords = kPageSize / kWordSize;
static const intptr_t kPageMask = ~(kPageSize - 1);
// A page containing old generation objects.
class HeapPage {
enum PageType { kData = 0, kExecutable, kNumPageTypes };
HeapPage* next() const { return next_; }
void set_next(HeapPage* next) { next_ = next; }
bool Contains(uword addr) const { return memory_->Contains(addr); }
intptr_t AliasOffset() const { return memory_->AliasOffset(); }
uword object_start() const { return memory_->start() + ObjectStartOffset(); }
uword object_end() const { return object_end_; }
uword used_in_bytes() const { return used_in_bytes_; }
void set_used_in_bytes(uword value) {
ASSERT(Utils::IsAligned(value, kObjectAlignment));
used_in_bytes_ = value;
ForwardingPage* forwarding_page() const { return forwarding_page_; }
ForwardingPage* AllocateForwardingPage();
void FreeForwardingPage();
PageType type() const { return type_; }
bool is_image_page() const { return !memory_->vm_owns_region(); }
void VisitObjects(ObjectVisitor* visitor) const;
void VisitObjectPointers(ObjectPointerVisitor* visitor) const;
RawObject* FindObject(FindObjectVisitor* visitor) const;
void WriteProtect(bool read_only);
static intptr_t ObjectStartOffset() {
return Utils::RoundUp(sizeof(HeapPage), OS::kMaxPreferredCodeAlignment);
// Warning: This does not work for objects on image pages because image pages
// are not aligned. However, it works for objects on large pages, because
// only one object is allocated per large page.
static HeapPage* Of(RawObject* obj) {
return reinterpret_cast<HeapPage*>(reinterpret_cast<uword>(obj) &
// Warning: This does not work for addresses on image pages or on large pages.
static HeapPage* Of(uword addr) {
return reinterpret_cast<HeapPage*>(addr & kPageMask);
// Warning: This does not work for objects on image pages.
static RawObject* ToExecutable(RawObject* obj) {
HeapPage* page = Of(obj);
VirtualMemory* memory = page->memory_;
const intptr_t alias_offset = memory->AliasOffset();
if (alias_offset == 0) {
return obj; // Not aliased.
uword addr = RawObject::ToAddr(obj);
if (memory->Contains(addr)) {
return RawObject::FromAddr(addr + alias_offset);
// obj is executable.
return obj;
// Warning: This does not work for objects on image pages.
static RawObject* ToWritable(RawObject* obj) {
HeapPage* page = Of(obj);
VirtualMemory* memory = page->memory_;
const intptr_t alias_offset = memory->AliasOffset();
if (alias_offset == 0) {
return obj; // Not aliased.
uword addr = RawObject::ToAddr(obj);
if (memory->ContainsAlias(addr)) {
return RawObject::FromAddr(addr - alias_offset);
// obj is writable.
return obj;
// 1 card = 128 slots.
static const intptr_t kSlotsPerCardLog2 = 7;
static const intptr_t kBytesPerCardLog2 = kWordSizeLog2 + kSlotsPerCardLog2;
intptr_t card_table_size() const {
return memory_->size() >> kBytesPerCardLog2;
static intptr_t card_table_offset() {
return OFFSET_OF(HeapPage, card_table_);
void RememberCard(RawObject* const* slot) {
if (card_table_ == NULL) {
card_table_ = reinterpret_cast<uint8_t*>(
calloc(card_table_size(), sizeof(uint8_t)));
intptr_t offset =
reinterpret_cast<uword>(slot) - reinterpret_cast<uword>(this);
intptr_t index = offset >> kBytesPerCardLog2;
ASSERT((index >= 0) && (index < card_table_size()));
card_table_[index] = 1;
void VisitRememberedCards(ObjectPointerVisitor* visitor);
void set_object_end(uword value) {
ASSERT((value & kObjectAlignmentMask) == kOldObjectAlignmentOffset);
object_end_ = value;
// Returns NULL on OOM.
static HeapPage* Allocate(intptr_t size_in_words,
PageType type,
const char* name);
// Deallocate the virtual memory backing this page. The page pointer to this
// page becomes immediately inaccessible.
void Deallocate();
VirtualMemory* memory_;
HeapPage* next_;
uword object_end_;
uword used_in_bytes_;
ForwardingPage* forwarding_page_;
uint8_t* card_table_; // Remembered set, not marking.
PageType type_;
friend class PageSpace;
friend class GCCompactor;
// The history holds the timing information of the last garbage collection
// runs.
class PageSpaceGarbageCollectionHistory {
PageSpaceGarbageCollectionHistory() {}
~PageSpaceGarbageCollectionHistory() {}
void AddGarbageCollectionTime(int64_t start, int64_t end);
int GarbageCollectionTimeFraction();
bool IsEmpty() const { return history_.Size() == 0; }
struct Entry {
int64_t start;
int64_t end;
static const intptr_t kHistoryLength = 4;
RingBuffer<Entry, kHistoryLength> history_;
// PageSpaceController controls the heap size.
class PageSpaceController {
// The heap is passed in for recording stats only. The controller does not
// invoke GC by itself.
PageSpaceController(Heap* heap,
int heap_growth_ratio,
int heap_growth_max,
int garbage_collection_time_ratio);
// Returns whether growing to 'after' should trigger a GC.
// This method can be called before allocation (e.g., pretenuring) or after
// (e.g., promotion), as it does not change the state of the controller.
bool NeedsGarbageCollection(SpaceUsage after) const;
bool AlmostNeedsGarbageCollection(SpaceUsage after) const;
// Returns whether an idle GC is worthwhile.
bool NeedsIdleGarbageCollection(SpaceUsage current) const;
// Should be called after each collection to update the controller state.
void EvaluateGarbageCollection(SpaceUsage before,
SpaceUsage after,
int64_t start,
int64_t end);
void EvaluateAfterLoading(SpaceUsage after);
int64_t last_code_collection_in_us() { return last_code_collection_in_us_; }
void set_last_code_collection_in_us(int64_t t) {
last_code_collection_in_us_ = t;
void set_last_usage(SpaceUsage current) { last_usage_ = current; }
void Enable() { is_enabled_ = true; }
void Disable() { is_enabled_ = false; }
bool is_enabled() { return is_enabled_; }
Heap* heap_;
bool is_enabled_;
// Usage after last evaluated GC or last enabled.
SpaceUsage last_usage_;
// If the garbage collector was not able to free more than heap_growth_ratio_
// memory, then the heap is grown. Otherwise garbage collection is performed.
const int heap_growth_ratio_;
// The desired percent of heap in-use after a garbage collection.
// Equivalent to \frac{100-heap_growth_ratio_}{100}.
const double desired_utilization_;
// Max number of pages we grow.
const int heap_growth_max_;
// If the relative GC time goes above garbage_collection_time_ratio_ %,
// we grow the heap more aggressively.
const int garbage_collection_time_ratio_;
// The time in microseconds of the last time we tried to collect unused
// code.
int64_t last_code_collection_in_us_;
// Perform a synchronous GC when capacity exceeds this amount.
intptr_t gc_threshold_in_words_;
// Perform a synchronous GC when external allocations exceed this amount.
intptr_t gc_external_threshold_in_words_;
// Start considering idle GC when capacity exceeds this amount.
intptr_t idle_gc_threshold_in_words_;
PageSpaceGarbageCollectionHistory history_;
class PageSpace {
enum GrowthPolicy { kControlGrowth, kForceGrowth };
enum Phase { kDone, kMarking, kAwaitingFinalization, kSweeping };
PageSpace(Heap* heap, intptr_t max_capacity_in_words);
uword TryAllocate(intptr_t size,
HeapPage::PageType type = HeapPage::kData,
GrowthPolicy growth_policy = kControlGrowth) {
bool is_protected =
(type == HeapPage::kExecutable) && FLAG_write_protect_code;
bool is_locked = false;
return TryAllocateInternal(size, type, growth_policy, is_protected,
bool NeedsGarbageCollection() const {
return page_space_controller_.NeedsGarbageCollection(usage_);
bool AlmostNeedsGarbageCollection() const {
return page_space_controller_.AlmostNeedsGarbageCollection(usage_);
void EvaluateAfterLoading() {
int64_t UsedInWords() const { return usage_.used_in_words; }
int64_t CapacityInWords() const {
MutexLocker ml(pages_lock_);
return usage_.capacity_in_words;
void IncreaseCapacityInWords(intptr_t increase_in_words) {
MutexLocker ml(pages_lock_);
void IncreaseCapacityInWordsLocked(intptr_t increase_in_words) {
usage_.capacity_in_words += increase_in_words;
void UpdateMaxCapacityLocked();
void UpdateMaxUsed();
int64_t ExternalInWords() const { return usage_.external_in_words; }
SpaceUsage GetCurrentUsage() const {
MutexLocker ml(pages_lock_);
return usage_;
bool Contains(uword addr) const;
bool Contains(uword addr, HeapPage::PageType type) const;
bool DataContains(uword addr) const;
bool IsValidAddress(uword addr) const { return Contains(addr); }
void VisitObjects(ObjectVisitor* visitor) const;
void VisitObjectsNoImagePages(ObjectVisitor* visitor) const;
void VisitObjectsImagePages(ObjectVisitor* visitor) const;
void VisitObjectPointers(ObjectPointerVisitor* visitor) const;
void VisitRememberedCards(ObjectPointerVisitor* visitor) const;
RawObject* FindObject(FindObjectVisitor* visitor,
HeapPage::PageType type) const;
// Checks if enough time has elapsed since the last attempt to collect
// code.
bool ShouldCollectCode();
// Collect the garbage in the page space using mark-sweep or mark-compact.
void CollectGarbage(bool compact, bool finalize);
void AddRegionsToObjectSet(ObjectSet* set) const;
void InitGrowthControl() {
void SetGrowthControlState(bool state) {
if (state) {
} else {
bool GrowthControlState() { return page_space_controller_.is_enabled(); }
// Note: Code pages are made executable/non-executable when 'read_only' is
// true/false, respectively.
void WriteProtect(bool read_only);
void WriteProtectCode(bool read_only);
bool ShouldPerformIdleMarkSweep(int64_t deadline);
bool ShouldPerformIdleMarkCompact(int64_t deadline);
void AddGCTime(int64_t micros) { gc_time_micros_ += micros; }
int64_t gc_time_micros() const { return gc_time_micros_; }
void IncrementCollections() { collections_++; }
intptr_t collections() const { return collections_; }
#ifndef PRODUCT
void PrintToJSONObject(JSONObject* object) const;
void PrintHeapMapToJSONStream(Isolate* isolate, JSONStream* stream) const;
#endif // PRODUCT
void AllocateBlack(intptr_t size) {
size >> kWordSizeLog2);
void AllocateExternal(intptr_t cid, intptr_t size);
void PromoteExternal(intptr_t cid, intptr_t size);
void FreeExternal(intptr_t size);
// Bulk data allocation.
void AcquireDataLock();
void ReleaseDataLock();
#if defined(DEBUG)
bool CurrentThreadOwnsDataLock();
uword TryAllocateDataLocked(intptr_t size, GrowthPolicy growth_policy) {
bool is_protected = false;
bool is_locked = true;
return TryAllocateInternal(size, HeapPage::kData, growth_policy,
is_protected, is_locked);
Monitor* tasks_lock() const { return tasks_lock_; }
intptr_t tasks() const { return tasks_; }
void set_tasks(intptr_t val) {
ASSERT(val >= 0);
tasks_ = val;
intptr_t concurrent_marker_tasks() const { return concurrent_marker_tasks_; }
void set_concurrent_marker_tasks(intptr_t val) {
ASSERT(val >= 0);
concurrent_marker_tasks_ = val;
Phase phase() const { return phase_; }
void set_phase(Phase val) { phase_ = val; }
// Attempt to allocate from bump block rather than normal freelist.
uword TryAllocateDataBumpLocked(intptr_t size);
// Prefer small freelist blocks, then chip away at the bump block.
uword TryAllocatePromoLocked(intptr_t size);
void SetupImagePage(void* pointer, uword size, bool is_executable);
// Return any bump allocation block to the freelist.
void AbandonBumpAllocation();
// Have threads release marking stack blocks, etc.
void AbandonMarkingForShutdown();
bool enable_concurrent_mark() const { return enable_concurrent_mark_; }
void set_enable_concurrent_mark(bool enable_concurrent_mark) {
enable_concurrent_mark_ = enable_concurrent_mark;
// Ids for time and data records in Heap::GCStats.
enum {
// Time
kConcurrentSweep = 0,
kSafePoint = 1,
kMarkObjects = 2,
kResetFreeLists = 3,
kSweepPages = 4,
kSweepLargePages = 5,
// Data
kGarbageRatio = 0,
kGCTimeFraction = 1,
kPageGrowth = 2,
kAllowedGrowth = 3
static const intptr_t kAllocatablePageSize = 64 * KB;
uword TryAllocateInternal(intptr_t size,
HeapPage::PageType type,
GrowthPolicy growth_policy,
bool is_protected,
bool is_locked);
uword TryAllocateInFreshPage(intptr_t size,
HeapPage::PageType type,
GrowthPolicy growth_policy,
bool is_locked);
// Makes bump block walkable; do not call concurrently with mutator.
void MakeIterable() const;
HeapPage* AllocatePage(HeapPage::PageType type, bool link = true);
void FreePage(HeapPage* page, HeapPage* previous_page);
HeapPage* AllocateLargePage(intptr_t size, HeapPage::PageType type);
void TruncateLargePage(HeapPage* page, intptr_t new_object_size_in_bytes);
void FreeLargePage(HeapPage* page, HeapPage* previous_page);
void FreePages(HeapPage* pages);
void CollectGarbageAtSafepoint(bool compact,
bool finalize,
int64_t pre_wait_for_sweepers,
int64_t pre_safe_point);
void BlockingSweep();
void ConcurrentSweep(Isolate* isolate);
void Compact(Thread* thread);
static intptr_t LargePageSizeInWordsFor(intptr_t size);
bool CanIncreaseCapacityInWordsLocked(intptr_t increase_in_words) {
if (max_capacity_in_words_ == 0) {
// Unlimited.
return true;
intptr_t free_capacity_in_words =
(max_capacity_in_words_ - usage_.capacity_in_words);
return ((free_capacity_in_words > 0) &&
(increase_in_words <= free_capacity_in_words));
FreeList freelist_[HeapPage::kNumPageTypes];
Heap* heap_;
// Use ExclusivePageIterator for safe access to these.
Mutex* pages_lock_;
HeapPage* pages_;
HeapPage* pages_tail_;
HeapPage* exec_pages_;
HeapPage* exec_pages_tail_;
HeapPage* large_pages_;
HeapPage* image_pages_;
// A block of memory in a data page, managed by bump allocation. The remainder
// is kept formatted as a FreeListElement, but is not in any freelist.
uword bump_top_;
uword bump_end_;
// Various sizes being tracked for this generation.
intptr_t max_capacity_in_words_;
// NOTE: The capacity component of usage_ is updated by the concurrent
// sweeper. Use (Increase)CapacityInWords(Locked) for thread-safe access.
SpaceUsage usage_;
intptr_t allocated_black_in_words_;
// Keep track of running MarkSweep tasks.
Monitor* tasks_lock_;
intptr_t tasks_;
intptr_t concurrent_marker_tasks_;
Phase phase_;
#if defined(DEBUG)
Thread* iterating_thread_;
PageSpaceController page_space_controller_;
GCMarker* marker_;
int64_t gc_time_micros_;
intptr_t collections_;
intptr_t mark_words_per_micro_;
bool enable_concurrent_mark_;
friend class ExclusivePageIterator;
friend class ExclusiveCodePageIterator;
friend class ExclusiveLargePageIterator;
friend class HeapIterationScope;
friend class PageSpaceController;
friend class ConcurrentSweeperTask;
friend class GCCompactor;
friend class CompactorTask;
} // namespace dart