dart::FreeList Class Reference

#include <freelist.h>

Public Member Functions
	FreeList ()
	~FreeList ()
uword	TryAllocate (intptr_t size, bool is_protected)
void	Free (uword addr, intptr_t size)
void	Reset ()
void	Print () const
Mutex *	mutex ()
uword	TryAllocateLocked (intptr_t size, bool is_protected)
void	FreeLocked (uword addr, intptr_t size)
FreeListElement *	TryAllocateLarge (intptr_t minimum_size)
FreeListElement *	TryAllocateLargeLocked (intptr_t minimum_size)
uword	TryAllocateSmallLocked (intptr_t size)
DART_FORCE_INLINE bool	TryAllocateBumpLocked (intptr_t size, uword *result)
intptr_t	TakeUnaccountedSizeLocked ()
void	MakeIterable ()
DART_WARN_UNUSED_RESULT intptr_t	ReleaseBumpAllocation ()
uword	top () const
uword	end () const
void	set_top (uword value)
void	set_end (uword value)
void	AddUnaccountedSize (intptr_t size)

Detailed Description

Definition at line 79 of file freelist.h.

Constructor & Destructor Documentation

FreeList()

dart::FreeList::FreeList

(

)

Definition at line 76 of file freelist.cc.

                   : mutex_() {
  Reset();
}

~FreeList()

dart::FreeList::~FreeList

(

)

Definition at line 80 of file freelist.cc.

{}

Member Function Documentation

AddUnaccountedSize()

void dart::FreeList::AddUnaccountedSize ( intptr_t  size )

inline

Definition at line 163 of file freelist.h.

{ unaccounted_size_ += size; }

end()

uword dart::FreeList::end ( ) const

inline

Definition at line 160 of file freelist.h.

{ return end_; }

Free()

void dart::FreeList::Free	(	uword	addr,
		intptr_t	size
	)

Definition at line 193 of file freelist.cc.

                                             {
  MutexLocker ml(&mutex_);
  FreeLocked(addr, size);
}

FreeLocked()

void dart::FreeList::FreeLocked	(	uword	addr,
		intptr_t	size
	)

Definition at line 198 of file freelist.cc.

                                                   {
  DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
  // Precondition required by AsElement and EnqueueElement: the (page
  // containing the) header of the freed block should be writable.  This is
  // the case when called for newly allocated pages because they are
  // allocated as writable.  It is the case when called during GC sweeping
  // because the entire heap is writable.
  intptr_t index = IndexForSize(size);
  FreeListElement* element = FreeListElement::AsElement(addr, size);
  EnqueueElement(element, index);
  // Postcondition: the (page containing the) header is left writable.
}

MakeIterable()

void dart::FreeList::MakeIterable ( )

inline

Definition at line 142 of file freelist.h.

                      {
    if (top_ < end_) {
      FreeListElement::AsElement(top_, end_ - top_);
    }
  }

mutex()

Mutex * dart::FreeList::mutex ( )

inline

Definition at line 91 of file freelist.h.

{ return &mutex_; }

Print()

void dart::FreeList::Print

(

)

const

Definition at line 315 of file freelist.cc.

                           {
  MutexLocker ml(&mutex_);
  PrintSmall();
  PrintLarge();
}

ReleaseBumpAllocation()

DART_WARN_UNUSED_RESULT intptr_t dart::FreeList::ReleaseBumpAllocation ( )

inline

Definition at line 149 of file freelist.h.

                                   {
    intptr_t remaining = end_ - top_;
    if (remaining != 0) {
      Free(top_, remaining);
      top_ = 0;
      end_ = 0;
    }
    return remaining;
  }

Reset()

void dart::FreeList::Reset

(

)

Definition at line 211 of file freelist.cc.

                     {
  MutexLocker ml(&mutex_);
  free_map_.Reset();
  last_free_small_size_ = -1;
  for (int i = 0; i < (kNumLists + 1); i++) {
    free_lists_[i] = nullptr;
  }
}

set_end()

void dart::FreeList::set_end ( uword  value )

inline

Definition at line 162 of file freelist.h.

{ end_ = value; }

set_top()

void dart::FreeList::set_top ( uword  value )

inline

Definition at line 161 of file freelist.h.

{ top_ = value; }

TakeUnaccountedSizeLocked()

intptr_t dart::FreeList::TakeUnaccountedSizeLocked ( )

inline

Definition at line 133 of file freelist.h.

                                       {
    ASSERT(mutex_.IsOwnedByCurrentThread());
    intptr_t result = unaccounted_size_;
    unaccounted_size_ = 0;
    return result;
  }

top()

uword dart::FreeList::top ( ) const

inline

Definition at line 159 of file freelist.h.

{ return top_; }

TryAllocate()

uword dart::FreeList::TryAllocate	(	intptr_t	size,
		bool	is_protected
	)

Definition at line 82 of file freelist.cc.

                                                            {
  MutexLocker ml(&mutex_);
  return TryAllocateLocked(size, is_protected);
}

TryAllocateBumpLocked()

DART_FORCE_INLINE bool dart::FreeList::TryAllocateBumpLocked ( intptr_t  size, uword *  result  )

inline

Definition at line 122 of file freelist.h.

                                                           {
    ASSERT(mutex_.IsOwnedByCurrentThread());
    uword top = top_;
    uword new_top = top + size;
    if (new_top <= end_) {
      top_ = new_top;
      *result = top;
      return true;
    }
    return false;
  }

TryAllocateLarge()

FreeListElement * dart::FreeList::TryAllocateLarge

(

intptr_t

minimum_size

)

Definition at line 356 of file freelist.cc.

                                                                 {
  MutexLocker ml(&mutex_);
  return TryAllocateLargeLocked(minimum_size);
}

TryAllocateLargeLocked()

FreeListElement * dart::FreeList::TryAllocateLargeLocked

(

intptr_t

minimum_size

)

Definition at line 361 of file freelist.cc.

                                                                       {
  DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
  FreeListElement* previous = nullptr;
  FreeListElement* current = free_lists_[kNumLists];
  // TODO(koda): Find largest.
  // We are willing to search the freelist further for a big block.
  intptr_t tries_left =
      freelist_search_budget_ + (minimum_size >> kWordSizeLog2);
  while (current != nullptr) {
    FreeListElement* next = current->next();
    if (current->HeapSize() >= minimum_size) {
      if (previous == nullptr) {
        free_lists_[kNumLists] = next;
      } else {
        previous->set_next(next);
      }
      freelist_search_budget_ =
          Utils::Minimum(tries_left, kInitialFreeListSearchBudget);
      return current;
    } else if (tries_left-- < 0) {
      freelist_search_budget_ = kInitialFreeListSearchBudget;
      return nullptr;  // Trigger allocation of new page.
    }
    previous = current;
    current = next;
  }
  return nullptr;
}

TryAllocateLocked()

uword dart::FreeList::TryAllocateLocked	(	intptr_t	size,
		bool	is_protected
	)

Definition at line 87 of file freelist.cc.

                                                                  {
  DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
  // Precondition: is_protected is false or else all free list elements are
  // in non-writable pages.
 
  // Postcondition: if allocation succeeds, the allocated block is writable.
  int index = IndexForSize(size);
  if ((index != kNumLists) && free_map_.Test(index)) {
    FreeListElement* element = DequeueElement(index);
    if (is_protected) {
      VirtualMemory::Protect(reinterpret_cast<void*>(element), size,
                             VirtualMemory::kReadWrite);
    }
    return reinterpret_cast<uword>(element);
  }
 
  if ((index + 1) < kNumLists) {
    intptr_t next_index = free_map_.Next(index + 1);
    if (next_index != -1) {
      // Dequeue an element from the list, split and enqueue the remainder in
      // the appropriate list.
      FreeListElement* element = DequeueElement(next_index);
      if (is_protected) {
        // Make the allocated block and the header of the remainder element
        // writable.  The remainder will be non-writable if necessary after
        // the call to SplitElementAfterAndEnqueue.
        // If the remainder size is zero, only the element itself needs to
        // be made writable.
        intptr_t remainder_size = element->HeapSize() - size;
        intptr_t region_size =
            size + FreeListElement::HeaderSizeFor(remainder_size);
        VirtualMemory::Protect(reinterpret_cast<void*>(element), region_size,
                               VirtualMemory::kReadWrite);
      }
      SplitElementAfterAndEnqueue(element, size, is_protected);
      return reinterpret_cast<uword>(element);
    }
  }
 
  FreeListElement* previous = nullptr;
  FreeListElement* current = free_lists_[kNumLists];
  // We are willing to search the freelist further for a big block.
  // For each successful free-list search we:
  //   * increase the search budget by #allocated-words
  //   * decrease the search budget by #free-list-entries-traversed
  //     which guarantees us to not waste more than around 1 search step per
  //     word of allocation
  //
  // If we run out of search budget we fall back to allocating a new page and
  // reset the search budget.
  intptr_t tries_left = freelist_search_budget_ + (size >> kWordSizeLog2);
  while (current != nullptr) {
    if (current->HeapSize() >= size) {
      // Found an element large enough to hold the requested size. Dequeue,
      // split and enqueue the remainder.
      intptr_t remainder_size = current->HeapSize() - size;
      intptr_t region_size =
          size + FreeListElement::HeaderSizeFor(remainder_size);
      if (is_protected) {
        // Make the allocated block and the header of the remainder element
        // writable.  The remainder will be non-writable if necessary after
        // the call to SplitElementAfterAndEnqueue.
        VirtualMemory::Protect(reinterpret_cast<void*>(current), region_size,
                               VirtualMemory::kReadWrite);
      }
 
      if (previous == nullptr) {
        free_lists_[kNumLists] = current->next();
      } else {
        // If the previous free list element's next field is protected, it
        // needs to be unprotected before storing to it and reprotected
        // after.
        bool target_is_protected = false;
        uword target_address = 0L;
        if (is_protected) {
          uword writable_start = reinterpret_cast<uword>(current);
          uword writable_end = writable_start + region_size - 1;
          target_address = previous->next_address();
          target_is_protected =
              !VirtualMemory::InSamePage(target_address, writable_start) &&
              !VirtualMemory::InSamePage(target_address, writable_end);
        }
        if (target_is_protected) {
          VirtualMemory::Protect(reinterpret_cast<void*>(target_address),
                                 kWordSize, VirtualMemory::kReadWrite);
        }
        previous->set_next(current->next());
        if (target_is_protected) {
          VirtualMemory::Protect(reinterpret_cast<void*>(target_address),
                                 kWordSize, VirtualMemory::kReadExecute);
        }
      }
      SplitElementAfterAndEnqueue(current, size, is_protected);
      freelist_search_budget_ =
          Utils::Minimum(tries_left, kInitialFreeListSearchBudget);
      return reinterpret_cast<uword>(current);
    } else if (tries_left-- < 0) {
      freelist_search_budget_ = kInitialFreeListSearchBudget;
      return 0;  // Trigger allocation of new page.
    }
    previous = current;
    current = current->next();
  }
  return 0;
}

TryAllocateSmallLocked()

uword dart::FreeList::TryAllocateSmallLocked ( intptr_t  size )

inline

Definition at line 101 of file freelist.h.

                                              {
    DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
    if (size > last_free_small_size_) {
      return 0;
    }
    int index = IndexForSize(size);
    if (index != kNumLists && free_map_.Test(index)) {
      return reinterpret_cast<uword>(DequeueElement(index));
    }
    if ((index + 1) < kNumLists) {
      intptr_t next_index = free_map_.Next(index + 1);
      if (next_index != -1) {
        FreeListElement* element = DequeueElement(next_index);
        SplitElementAfterAndEnqueue(element, size, false);
        return reinterpret_cast<uword>(element);
      }
    }
    return 0;
  }

---

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

• third_party/dart-lang/sdk/runtime/vm/heap/freelist.h
• third_party/dart-lang/sdk/runtime/vm/heap/freelist.cc