v8::internal::FreeList Class Reference

#include <spaces.h>

Collaboration diagram for v8::internal::FreeList:

Public Member Functions
	FreeList (PagedSpace *owner)
intptr_t	Concatenate (FreeList *free_list)
void	Reset ()
intptr_t	available ()
int	Free (Address start, int size_in_bytes)
MUST_USE_RESULT HeapObject *	Allocate (int size_in_bytes)
bool	IsEmpty ()
void	RepairLists (Heap *heap)
intptr_t	EvictFreeListItems (Page *p)
bool	ContainsPageFreeListItems (Page *p)
FreeListCategory *	small_list ()
FreeListCategory *	medium_list ()
FreeListCategory *	large_list ()
FreeListCategory *	huge_list ()

Static Public Member Functions
static int	GuaranteedAllocatable (int maximum_freed)

Private Member Functions
FreeListNode *	FindNodeFor (int size_in_bytes, int *node_size)
	DISALLOW_IMPLICIT_CONSTRUCTORS (FreeList)

Private Attributes
PagedSpace *	owner_
Heap *	heap_
FreeListCategory	small_list_
FreeListCategory	medium_list_
FreeListCategory	large_list_
FreeListCategory	huge_list_

Static Private Attributes
static const int	kMinBlockSize = 3 * kPointerSize
static const int	kMaxBlockSize = Page::kMaxRegularHeapObjectSize
static const int	kSmallListMin = 0x20 * kPointerSize
static const int	kSmallListMax = 0xff * kPointerSize
static const int	kMediumListMax = 0x7ff * kPointerSize
static const int	kLargeListMax = 0x3fff * kPointerSize
static const int	kSmallAllocationMax = kSmallListMin - kPointerSize
static const int	kMediumAllocationMax = kSmallListMax
static const int	kLargeAllocationMax = kMediumListMax

Detailed Description

Definition at line 1515 of file spaces.h.

Constructor & Destructor Documentation

FreeList()

v8::internal::FreeList::FreeList ( PagedSpace *  owner )

explicit

Definition at line 2154 of file spaces.cc.

                                    : owner_(owner), heap_(owner->heap()) {
  Reset();
}

References Reset().

Here is the call graph for this function:

Member Function Documentation

Allocate()

HeapObject * v8::internal::FreeList::Allocate

(

int

size_in_bytes

)

Definition at line 2326 of file spaces.cc.

                                                {
  DCHECK(0 < size_in_bytes);
  DCHECK(size_in_bytes <= kMaxBlockSize);
  DCHECK(IsAligned(size_in_bytes, kPointerSize));
  // Don't free list allocate if there is linear space available.
  DCHECK(owner_->limit() - owner_->top() < size_in_bytes);
 
  int old_linear_size = static_cast<int>(owner_->limit() - owner_->top());
  // Mark the old linear allocation area with a free space map so it can be
  // skipped when scanning the heap.  This also puts it back in the free list
  // if it is big enough.
  owner_->Free(owner_->top(), old_linear_size);
 
  owner_->heap()->incremental_marking()->OldSpaceStep(size_in_bytes -
                                                      old_linear_size);
 
  int new_node_size = 0;
  FreeListNode* new_node = FindNodeFor(size_in_bytes, &new_node_size);
  if (new_node == NULL) {
    owner_->SetTopAndLimit(NULL, NULL);
    return NULL;
  }
 
  int bytes_left = new_node_size - size_in_bytes;
  DCHECK(bytes_left >= 0);
 
#ifdef DEBUG
  for (int i = 0; i < size_in_bytes / kPointerSize; i++) {
    reinterpret_cast<Object**>(new_node->address())[i] =
        Smi::FromInt(kCodeZapValue);
  }
#endif
 
  // The old-space-step might have finished sweeping and restarted marking.
  // Verify that it did not turn the page of the new node into an evacuation
  // candidate.
  DCHECK(!MarkCompactCollector::IsOnEvacuationCandidate(new_node));
 
  const int kThreshold = IncrementalMarking::kAllocatedThreshold;
 
  // Memory in the linear allocation area is counted as allocated.  We may free
  // a little of this again immediately - see below.
  owner_->Allocate(new_node_size);
 
  if (owner_->heap()->inline_allocation_disabled()) {
    // Keep the linear allocation area empty if requested to do so, just
    // return area back to the free list instead.
    owner_->Free(new_node->address() + size_in_bytes, bytes_left);
    DCHECK(owner_->top() == NULL && owner_->limit() == NULL);
  } else if (bytes_left > kThreshold &&
             owner_->heap()->incremental_marking()->IsMarkingIncomplete() &&
             FLAG_incremental_marking_steps) {
    int linear_size = owner_->RoundSizeDownToObjectAlignment(kThreshold);
    // We don't want to give too large linear areas to the allocator while
    // incremental marking is going on, because we won't check again whether
    // we want to do another increment until the linear area is used up.
    owner_->Free(new_node->address() + size_in_bytes + linear_size,
                 new_node_size - size_in_bytes - linear_size);
    owner_->SetTopAndLimit(new_node->address() + size_in_bytes,
                           new_node->address() + size_in_bytes + linear_size);
  } else if (bytes_left > 0) {
    // Normally we give the rest of the node to the allocator as its new
    // linear allocation area.
    owner_->SetTopAndLimit(new_node->address() + size_in_bytes,
                           new_node->address() + new_node_size);
  } else {
    // TODO(gc) Try not freeing linear allocation region when bytes_left
    // are zero.
    owner_->SetTopAndLimit(NULL, NULL);
  }
 
  return new_node;
}

References v8::internal::HeapObject::address(), v8::internal::PagedSpace::Allocate(), DCHECK, FindNodeFor(), v8::internal::PagedSpace::Free(), v8::internal::Smi::FromInt(), v8::internal::Space::heap(), v8::internal::Heap::incremental_marking(), v8::internal::Heap::inline_allocation_disabled(), v8::internal::IsAligned(), v8::internal::IncrementalMarking::IsMarkingIncomplete(), v8::internal::IncrementalMarking::kAllocatedThreshold, v8::internal::kCodeZapValue, kMaxBlockSize, v8::internal::kPointerSize, v8::internal::PagedSpace::limit(), NULL, v8::internal::IncrementalMarking::OldSpaceStep(), owner_, v8::internal::Space::RoundSizeDownToObjectAlignment(), v8::internal::PagedSpace::SetTopAndLimit(), and v8::internal::PagedSpace::top().

Referenced by v8::internal::PagedSpace::AllocateRaw(), v8::internal::PagedSpace::SlowAllocateRaw(), and v8::internal::PagedSpace::WaitForSweeperThreadsAndRetryAllocation().

Here is the call graph for this function:

Here is the caller graph for this function:

available()

intptr_t v8::internal::FreeList::available ( )

inline

Definition at line 1525 of file spaces.h.

                       {
    return small_list_.available() + medium_list_.available() +
           large_list_.available() + huge_list_.available();
  }

References v8::internal::FreeListCategory::available(), huge_list_, large_list_, medium_list_, and small_list_.

Referenced by v8::internal::PagedSpace::Available(), FindNodeFor(), Free(), and v8::internal::PagedSpace::SlowAllocateRaw().

Here is the call graph for this function:

Here is the caller graph for this function:

Concatenate()

intptr_t v8::internal::FreeList::Concatenate

(

FreeList *

free_list

)

Definition at line 2159 of file spaces.cc.

                                                  {
  intptr_t free_bytes = 0;
  free_bytes += small_list_.Concatenate(free_list->small_list());
  free_bytes += medium_list_.Concatenate(free_list->medium_list());
  free_bytes += large_list_.Concatenate(free_list->large_list());
  free_bytes += huge_list_.Concatenate(free_list->huge_list());
  return free_bytes;
}

References v8::internal::FreeListCategory::Concatenate(), huge_list(), huge_list_, large_list(), large_list_, medium_list(), medium_list_, small_list(), and small_list_.

Referenced by v8::internal::MarkCompactCollector::SweepInParallel().

Here is the call graph for this function:

Here is the caller graph for this function:

ContainsPageFreeListItems()

bool v8::internal::FreeList::ContainsPageFreeListItems

(

Page *

p

)

Definition at line 2418 of file spaces.cc.

                                                {
  return huge_list_.EvictFreeListItemsInList(p) ||
         small_list_.EvictFreeListItemsInList(p) ||
         medium_list_.EvictFreeListItemsInList(p) ||
         large_list_.EvictFreeListItemsInList(p);
}

References v8::internal::FreeListCategory::EvictFreeListItemsInList(), huge_list_, large_list_, medium_list_, and small_list_.

Referenced by v8::internal::PagedSpace::FreeEmergencyMemory(), and v8::internal::PagedSpace::ReleasePage().

Here is the call graph for this function:

Here is the caller graph for this function:

DISALLOW_IMPLICIT_CONSTRUCTORS()

v8::internal::FreeList::DISALLOW_IMPLICIT_CONSTRUCTORS ( FreeList  )

private

EvictFreeListItems()

intptr_t v8::internal::FreeList::EvictFreeListItems

(

Page *

p

)

Definition at line 2401 of file spaces.cc.

                                             {
  intptr_t sum = huge_list_.EvictFreeListItemsInList(p);
  p->set_available_in_huge_free_list(0);
 
  if (sum < p->area_size()) {
    sum += small_list_.EvictFreeListItemsInList(p) +
           medium_list_.EvictFreeListItemsInList(p) +
           large_list_.EvictFreeListItemsInList(p);
    p->set_available_in_small_free_list(0);
    p->set_available_in_medium_free_list(0);
    p->set_available_in_large_free_list(0);
  }
 
  return sum;
}

References v8::internal::FreeListCategory::EvictFreeListItemsInList(), huge_list_, large_list_, medium_list_, and small_list_.

Referenced by v8::internal::PagedSpace::ReleasePage().

Here is the call graph for this function:

Here is the caller graph for this function:

FindNodeFor()

FreeListNode * v8::internal::FreeList::FindNodeFor ( int  size_in_bytes, int *  node_size  )

private

Definition at line 2211 of file spaces.cc.

                                                                     {
  FreeListNode* node = NULL;
  Page* page = NULL;
 
  if (size_in_bytes <= kSmallAllocationMax) {
    node = small_list_.PickNodeFromList(node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_small_free_list(-(*node_size));
      DCHECK(IsVeryLong() || available() == SumFreeLists());
      return node;
    }
  }
 
  if (size_in_bytes <= kMediumAllocationMax) {
    node = medium_list_.PickNodeFromList(node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_medium_free_list(-(*node_size));
      DCHECK(IsVeryLong() || available() == SumFreeLists());
      return node;
    }
  }
 
  if (size_in_bytes <= kLargeAllocationMax) {
    node = large_list_.PickNodeFromList(node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_large_free_list(-(*node_size));
      DCHECK(IsVeryLong() || available() == SumFreeLists());
      return node;
    }
  }
 
  int huge_list_available = huge_list_.available();
  FreeListNode* top_node = huge_list_.top();
  for (FreeListNode** cur = &top_node; *cur != NULL;
       cur = (*cur)->next_address()) {
    FreeListNode* cur_node = *cur;
    while (cur_node != NULL &&
           Page::FromAddress(cur_node->address())->IsEvacuationCandidate()) {
      int size = reinterpret_cast<FreeSpace*>(cur_node)->Size();
      huge_list_available -= size;
      page = Page::FromAddress(cur_node->address());
      page->add_available_in_huge_free_list(-size);
      cur_node = cur_node->next();
    }
 
    *cur = cur_node;
    if (cur_node == NULL) {
      huge_list_.set_end(NULL);
      break;
    }
 
    DCHECK((*cur)->map() == heap_->raw_unchecked_free_space_map());
    FreeSpace* cur_as_free_space = reinterpret_cast<FreeSpace*>(*cur);
    int size = cur_as_free_space->Size();
    if (size >= size_in_bytes) {
      // Large enough node found.  Unlink it from the list.
      node = *cur;
      *cur = node->next();
      *node_size = size;
      huge_list_available -= size;
      page = Page::FromAddress(node->address());
      page->add_available_in_huge_free_list(-size);
      break;
    }
  }
 
  huge_list_.set_top(top_node);
  if (huge_list_.top() == NULL) {
    huge_list_.set_end(NULL);
  }
  huge_list_.set_available(huge_list_available);
 
  if (node != NULL) {
    DCHECK(IsVeryLong() || available() == SumFreeLists());
    return node;
  }
 
  if (size_in_bytes <= kSmallListMax) {
    node = small_list_.PickNodeFromList(size_in_bytes, node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_small_free_list(-(*node_size));
    }
  } else if (size_in_bytes <= kMediumListMax) {
    node = medium_list_.PickNodeFromList(size_in_bytes, node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_medium_free_list(-(*node_size));
    }
  } else if (size_in_bytes <= kLargeListMax) {
    node = large_list_.PickNodeFromList(size_in_bytes, node_size);
    if (node != NULL) {
      DCHECK(size_in_bytes <= *node_size);
      page = Page::FromAddress(node->address());
      page->add_available_in_large_free_list(-(*node_size));
    }
  }
 
  DCHECK(IsVeryLong() || available() == SumFreeLists());
  return node;
}

References v8::internal::HeapObject::address(), available(), v8::internal::FreeListCategory::available(), DCHECK, v8::internal::MemoryChunk::FromAddress(), heap_, huge_list_, v8::internal::MemoryChunk::IsEvacuationCandidate(), kLargeAllocationMax, kLargeListMax, kMediumAllocationMax, kMediumListMax, kSmallAllocationMax, kSmallListMax, large_list_, medium_list_, v8::internal::FreeListNode::next(), NULL, v8::internal::FreeListCategory::PickNodeFromList(), v8::internal::FreeListCategory::set_available(), v8::internal::FreeListCategory::set_end(), v8::internal::FreeListCategory::set_top(), size, v8::internal::FreeSpace::Size(), small_list_, and v8::internal::FreeListCategory::top().

Referenced by Allocate().

Here is the call graph for this function:

Here is the caller graph for this function:

Free()

int v8::internal::FreeList::Free	(	Address	start,
		int	size_in_bytes
	)

Definition at line 2177 of file spaces.cc.

                                                   {
  if (size_in_bytes == 0) return 0;
 
  FreeListNode* node = FreeListNode::FromAddress(start);
  node->set_size(heap_, size_in_bytes);
  Page* page = Page::FromAddress(start);
 
  // Early return to drop too-small blocks on the floor.
  if (size_in_bytes < kSmallListMin) {
    page->add_non_available_small_blocks(size_in_bytes);
    return size_in_bytes;
  }
 
  // Insert other blocks at the head of a free list of the appropriate
  // magnitude.
  if (size_in_bytes <= kSmallListMax) {
    small_list_.Free(node, size_in_bytes);
    page->add_available_in_small_free_list(size_in_bytes);
  } else if (size_in_bytes <= kMediumListMax) {
    medium_list_.Free(node, size_in_bytes);
    page->add_available_in_medium_free_list(size_in_bytes);
  } else if (size_in_bytes <= kLargeListMax) {
    large_list_.Free(node, size_in_bytes);
    page->add_available_in_large_free_list(size_in_bytes);
  } else {
    huge_list_.Free(node, size_in_bytes);
    page->add_available_in_huge_free_list(size_in_bytes);
  }
 
  DCHECK(IsVeryLong() || available() == SumFreeLists());
  return 0;
}

References available(), DCHECK, v8::internal::FreeListCategory::Free(), v8::internal::MemoryChunk::FromAddress(), v8::internal::FreeListNode::FromAddress(), heap_, huge_list_, kLargeListMax, kMediumListMax, kSmallListMax, kSmallListMin, large_list_, medium_list_, v8::internal::FreeListNode::set_size(), and small_list_.

Referenced by v8::internal::PagedSpace::Free(), and v8::internal::Free().

Here is the call graph for this function:

Here is the caller graph for this function:

GuaranteedAllocatable()

static int v8::internal::FreeList::GuaranteedAllocatable ( int  maximum_freed )

inlinestatic

Definition at line 1540 of file spaces.h.

                                                             {
    if (maximum_freed < kSmallListMin) {
      return 0;
    } else if (maximum_freed <= kSmallListMax) {
      return kSmallAllocationMax;
    } else if (maximum_freed <= kMediumListMax) {
      return kMediumAllocationMax;
    } else if (maximum_freed <= kLargeListMax) {
      return kLargeAllocationMax;
    }
    return maximum_freed;
  }

References kLargeAllocationMax, kLargeListMax, kMediumAllocationMax, kMediumListMax, kSmallAllocationMax, kSmallListMax, and kSmallListMin.

Referenced by v8::internal::Sweep().

Here is the caller graph for this function:

huge_list()

FreeListCategory* v8::internal::FreeList::huge_list ( )

inline

Definition at line 1579 of file spaces.h.

{ return &huge_list_; }

References huge_list_.

Referenced by Concatenate().

Here is the caller graph for this function:

IsEmpty()

bool v8::internal::FreeList::IsEmpty ( )

inline

Definition at line 1559 of file spaces.h.

                 {
    return small_list_.IsEmpty() && medium_list_.IsEmpty() &&
           large_list_.IsEmpty() && huge_list_.IsEmpty();
  }

References huge_list_, v8::internal::FreeListCategory::IsEmpty(), large_list_, medium_list_, and small_list_.

Here is the call graph for this function:

large_list()

FreeListCategory* v8::internal::FreeList::large_list ( )

inline

Definition at line 1578 of file spaces.h.

{ return &large_list_; }

References large_list_.

Referenced by Concatenate().

Here is the caller graph for this function:

medium_list()

FreeListCategory* v8::internal::FreeList::medium_list ( )

inline

Definition at line 1577 of file spaces.h.

{ return &medium_list_; }

References medium_list_.

Referenced by Concatenate().

Here is the caller graph for this function:

RepairLists()

void v8::internal::FreeList::RepairLists

(

Heap *

heap

)

Definition at line 2426 of file spaces.cc.

                                     {
  small_list_.RepairFreeList(heap);
  medium_list_.RepairFreeList(heap);
  large_list_.RepairFreeList(heap);
  huge_list_.RepairFreeList(heap);
}

References huge_list_, large_list_, medium_list_, v8::internal::FreeListCategory::RepairFreeList(), and small_list_.

Referenced by v8::internal::PagedSpace::RepairFreeListsAfterBoot().

Here is the call graph for this function:

Here is the caller graph for this function:

Reset()

void v8::internal::FreeList::Reset

(

)

Definition at line 2169 of file spaces.cc.

                     {
  small_list_.Reset();
  medium_list_.Reset();
  large_list_.Reset();
  huge_list_.Reset();
}

References huge_list_, large_list_, medium_list_, v8::internal::FreeListCategory::Reset(), and small_list_.

Referenced by FreeList(), v8::internal::PagedSpace::PrepareForMarkCompact(), and v8::internal::PagedSpace::ResetFreeList().

Here is the call graph for this function:

Here is the caller graph for this function:

small_list()

FreeListCategory* v8::internal::FreeList::small_list ( )

inline

Definition at line 1576 of file spaces.h.

{ return &small_list_; }

References small_list_.

Referenced by Concatenate().

Here is the caller graph for this function:

Member Data Documentation

heap_

Heap* v8::internal::FreeList::heap_

private

Definition at line 1589 of file spaces.h.

Referenced by FindNodeFor(), and Free().

huge_list_

FreeListCategory v8::internal::FreeList::huge_list_

private

Definition at line 1601 of file spaces.h.

Referenced by available(), Concatenate(), ContainsPageFreeListItems(), EvictFreeListItems(), FindNodeFor(), Free(), huge_list(), IsEmpty(), RepairLists(), and Reset().

kLargeAllocationMax

const int v8::internal::FreeList::kLargeAllocationMax = kMediumListMax

staticprivate

Definition at line 1597 of file spaces.h.

Referenced by FindNodeFor(), and GuaranteedAllocatable().

kLargeListMax

const int v8::internal::FreeList::kLargeListMax = 0x3fff * kPointerSize

staticprivate

Definition at line 1594 of file spaces.h.

Referenced by FindNodeFor(), Free(), and GuaranteedAllocatable().

kMaxBlockSize

const int v8::internal::FreeList::kMaxBlockSize = Page::kMaxRegularHeapObjectSize

staticprivate

Definition at line 1584 of file spaces.h.

Referenced by Allocate().

kMediumAllocationMax

const int v8::internal::FreeList::kMediumAllocationMax = kSmallListMax

staticprivate

Definition at line 1596 of file spaces.h.

Referenced by FindNodeFor(), and GuaranteedAllocatable().

kMediumListMax

const int v8::internal::FreeList::kMediumListMax = 0x7ff * kPointerSize

staticprivate

Definition at line 1593 of file spaces.h.

Referenced by FindNodeFor(), Free(), and GuaranteedAllocatable().

kMinBlockSize

const int v8::internal::FreeList::kMinBlockSize = 3 * kPointerSize

staticprivate

Definition at line 1583 of file spaces.h.

kSmallAllocationMax

const int v8::internal::FreeList::kSmallAllocationMax = kSmallListMin - kPointerSize

staticprivate

Definition at line 1595 of file spaces.h.

Referenced by FindNodeFor(), and GuaranteedAllocatable().

kSmallListMax

const int v8::internal::FreeList::kSmallListMax = 0xff * kPointerSize

staticprivate

Definition at line 1592 of file spaces.h.

Referenced by FindNodeFor(), Free(), and GuaranteedAllocatable().

kSmallListMin

const int v8::internal::FreeList::kSmallListMin = 0x20 * kPointerSize

staticprivate

Definition at line 1591 of file spaces.h.

Referenced by Free(), and GuaranteedAllocatable().

large_list_

FreeListCategory v8::internal::FreeList::large_list_

private

Definition at line 1600 of file spaces.h.

Referenced by available(), Concatenate(), ContainsPageFreeListItems(), EvictFreeListItems(), FindNodeFor(), Free(), IsEmpty(), large_list(), RepairLists(), and Reset().

medium_list_

FreeListCategory v8::internal::FreeList::medium_list_

private

Definition at line 1599 of file spaces.h.

Referenced by available(), Concatenate(), ContainsPageFreeListItems(), EvictFreeListItems(), FindNodeFor(), Free(), IsEmpty(), medium_list(), RepairLists(), and Reset().

owner_

PagedSpace* v8::internal::FreeList::owner_

private

Definition at line 1588 of file spaces.h.

Referenced by Allocate().

small_list_

FreeListCategory v8::internal::FreeList::small_list_

private

Definition at line 1598 of file spaces.h.

Referenced by available(), Concatenate(), ContainsPageFreeListItems(), EvictFreeListItems(), FindNodeFor(), Free(), IsEmpty(), RepairLists(), Reset(), and small_list().

---

The documentation for this class was generated from the following files:

• /mnt/V8SourceCode/src/heap/spaces.h
• /mnt/V8SourceCode/src/heap/spaces.cc