Flutter Engine
The Flutter Engine
Public Member Functions | Friends | List of all members
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)
 

Friends

class GCIncrementalCompactor
 
class PrologueTask
 

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.

76 : mutex_() {
77 Reset();
78}
dart::FreeList::Reset
void Reset()
Definition: freelist.cc:211

◆ ~FreeList()

dart::FreeList::~FreeList ( )

Definition at line 80 of file freelist.cc.

80{}

Member Function Documentation

◆ AddUnaccountedSize()

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

Definition at line 163 of file freelist.h.

163{ unaccounted_size_ += size; }
flutter::size
it will be possible to load the file into Perfetto s trace viewer disable asset Prevents usage of any non test fonts unless they were explicitly Loaded via prefetched default font Indicates whether the embedding started a prefetch of the default font manager before creating the engine run In non interactive keep the shell running after the Dart script has completed enable serial On low power devices with low core running concurrent GC tasks on threads can cause them to contend with the UI thread which could potentially lead to jank This option turns off all concurrent GC activities domain network JSON encoded network policy per domain This overrides the DisallowInsecureConnections switch Embedder can specify whether to allow or disallow insecure connections at a domain level old gen heap size
Definition: switches.h:259

◆ end()

uword dart::FreeList::end ( ) const
inline

Definition at line 160 of file freelist.h.

160{ return end_; }

◆ Free()

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

Definition at line 193 of file freelist.cc.

193 {
194 MutexLocker ml(&mutex_);
195 FreeLocked(addr, size);
196}
dart::FreeList::FreeLocked
void FreeLocked(uword addr, intptr_t size)
Definition: freelist.cc:198
dump_adb_log.addr
addr
Definition: dump_adb_log.py:17

◆ FreeLocked()

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

Definition at line 198 of file freelist.cc.

198 {
199 DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
200 // Precondition required by AsElement and EnqueueElement: the (page
201 // containing the) header of the freed block should be writable. This is
202 // the case when called for newly allocated pages because they are
203 // allocated as writable. It is the case when called during GC sweeping
204 // because the entire heap is writable.
205 intptr_t index = IndexForSize(size);
206 FreeListElement* element = FreeListElement::AsElement(addr, size);
207 EnqueueElement(element, index);
208 // Postcondition: the (page containing the) header is left writable.
209}
DEBUG_ASSERT
#define DEBUG_ASSERT(cond)
Definition: assert.h:321
dart::FreeListElement::AsElement
static FreeListElement * AsElement(uword addr, intptr_t size)
Definition: freelist.cc:16
dart::Mutex::IsOwnedByCurrentThread
bool IsOwnedByCurrentThread() const
Definition: os_thread.h:402

◆ MakeIterable()

void dart::FreeList::MakeIterable ( )
inline

Definition at line 142 of file freelist.h.

142 {
143 if (top_ < end_) {
144 FreeListElement::AsElement(top_, end_ - top_);
145 }
146 }

◆ mutex()

Mutex * dart::FreeList::mutex ( )
inline

Definition at line 91 of file freelist.h.

91{ return &mutex_; }

◆ Print()

void dart::FreeList::Print ( ) const

Definition at line 315 of file freelist.cc.

315 {
316 MutexLocker ml(&mutex_);
317 PrintSmall();
318 PrintLarge();
319}

◆ ReleaseBumpAllocation()

DART_WARN_UNUSED_RESULT intptr_t dart::FreeList::ReleaseBumpAllocation ( )
inline

Definition at line 149 of file freelist.h.

149 {
150 intptr_t remaining = end_ - top_;
151 if (remaining != 0) {
152 Free(top_, remaining);
153 top_ = 0;
154 end_ = 0;
155 }
156 return remaining;
157 }
dart::FreeList::Free
void Free(uword addr, intptr_t size)
Definition: freelist.cc:193

◆ Reset()

void dart::FreeList::Reset ( )

Definition at line 211 of file freelist.cc.

211 {
212 MutexLocker ml(&mutex_);
213 free_map_.Reset();
214 last_free_small_size_ = -1;
215 for (int i = 0; i < (kNumLists + 1); i++) {
216 free_lists_[i] = nullptr;
217 }
218}
dart::BitSet::Reset
void Reset()
Definition: bit_set.h:89
i
int i
Definition: fl_socket_accessible.cc:18

◆ set_end()

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

Definition at line 162 of file freelist.h.

162{ end_ = value; }
value
uint8_t value
Definition: fl_standard_message_codec.cc:36

◆ set_top()

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

Definition at line 161 of file freelist.h.

161{ top_ = value; }

◆ TakeUnaccountedSizeLocked()

intptr_t dart::FreeList::TakeUnaccountedSizeLocked ( )
inline

Definition at line 133 of file freelist.h.

133 {
134 ASSERT(mutex_.IsOwnedByCurrentThread());
135 intptr_t result = unaccounted_size_;
136 unaccounted_size_ = 0;
137 return result;
138 }
ASSERT
#define ASSERT(E)
Definition: entrypoints_verification_test.cc:25
result
GAsyncResult * result
Definition: fl_text_input_plugin.cc:106

◆ top()

uword dart::FreeList::top ( ) const
inline

Definition at line 159 of file freelist.h.

159{ return top_; }

◆ TryAllocate()

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

Definition at line 82 of file freelist.cc.

82 {
83 MutexLocker ml(&mutex_);
84 return TryAllocateLocked(size, is_protected);
85}
dart::FreeList::TryAllocateLocked
uword TryAllocateLocked(intptr_t size, bool is_protected)
Definition: freelist.cc:87

◆ TryAllocateBumpLocked()

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

Definition at line 122 of file freelist.h.

122 {
123 ASSERT(mutex_.IsOwnedByCurrentThread());
124 uword top = top_;
125 uword new_top = top + size;
126 if (new_top <= end_) {
127 top_ = new_top;
128 *result = top;
129 return true;
130 }
131 return false;
132 }
dart::FreeList::top
uword top() const
Definition: freelist.h:159
dart::uword
uintptr_t uword
Definition: globals.h:501

◆ TryAllocateLarge()

FreeListElement * dart::FreeList::TryAllocateLarge ( intptr_t  minimum_size)

Definition at line 356 of file freelist.cc.

356 {
357 MutexLocker ml(&mutex_);
358 return TryAllocateLargeLocked(minimum_size);
359}
dart::FreeList::TryAllocateLargeLocked
FreeListElement * TryAllocateLargeLocked(intptr_t minimum_size)
Definition: freelist.cc:361

◆ TryAllocateLargeLocked()

FreeListElement * dart::FreeList::TryAllocateLargeLocked ( intptr_t  minimum_size)

Definition at line 361 of file freelist.cc.

361 {
362 DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
363 FreeListElement* previous = nullptr;
364 FreeListElement* current = free_lists_[kNumLists];
365 // TODO(koda): Find largest.
366 // We are willing to search the freelist further for a big block.
367 intptr_t tries_left =
368 freelist_search_budget_ + (minimum_size >> kWordSizeLog2);
369 while (current != nullptr) {
370 FreeListElement* next = current->next();
371 if (current->HeapSize() >= minimum_size) {
372 if (previous == nullptr) {
373 free_lists_[kNumLists] = next;
374 } else {
375 previous->set_next(next);
376 }
377 freelist_search_budget_ =
378 Utils::Minimum(tries_left, kInitialFreeListSearchBudget);
379 return current;
380 } else if (tries_left-- < 0) {
381 freelist_search_budget_ = kInitialFreeListSearchBudget;
382 return nullptr; // Trigger allocation of new page.
383 }
384 previous = current;
385 current = next;
386 }
387 return nullptr;
388}
next
static float next(float f)
Definition: PathOpsAngleTest.cpp:32
dart::Utils::Minimum
static T Minimum(T x, T y)
Definition: utils.h:36
dart::kWordSizeLog2
constexpr intptr_t kWordSizeLog2
Definition: globals.h:507

◆ TryAllocateLocked()

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

Definition at line 87 of file freelist.cc.

87 {
88 DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
89 // Precondition: is_protected is false or else all free list elements are
90 // in non-writable pages.
91
92 // Postcondition: if allocation succeeds, the allocated block is writable.
93 int index = IndexForSize(size);
94 if ((index != kNumLists) && free_map_.Test(index)) {
95 FreeListElement* element = DequeueElement(index);
96 if (is_protected) {
97 VirtualMemory::Protect(reinterpret_cast<void*>(element), size,
98 VirtualMemory::kReadWrite);
99 }
100 return reinterpret_cast<uword>(element);
101 }
102
103 if ((index + 1) < kNumLists) {
104 intptr_t next_index = free_map_.Next(index + 1);
105 if (next_index != -1) {
106 // Dequeue an element from the list, split and enqueue the remainder in
107 // the appropriate list.
108 FreeListElement* element = DequeueElement(next_index);
109 if (is_protected) {
110 // Make the allocated block and the header of the remainder element
111 // writable. The remainder will be non-writable if necessary after
112 // the call to SplitElementAfterAndEnqueue.
113 // If the remainder size is zero, only the element itself needs to
114 // be made writable.
115 intptr_t remainder_size = element->HeapSize() - size;
116 intptr_t region_size =
117 size + FreeListElement::HeaderSizeFor(remainder_size);
118 VirtualMemory::Protect(reinterpret_cast<void*>(element), region_size,
119 VirtualMemory::kReadWrite);
120 }
121 SplitElementAfterAndEnqueue(element, size, is_protected);
122 return reinterpret_cast<uword>(element);
123 }
124 }
125
126 FreeListElement* previous = nullptr;
127 FreeListElement* current = free_lists_[kNumLists];
128 // We are willing to search the freelist further for a big block.
129 // For each successful free-list search we:
130 // * increase the search budget by #allocated-words
131 // * decrease the search budget by #free-list-entries-traversed
132 // which guarantees us to not waste more than around 1 search step per
133 // word of allocation
134 //
135 // If we run out of search budget we fall back to allocating a new page and
136 // reset the search budget.
137 intptr_t tries_left = freelist_search_budget_ + (size >> kWordSizeLog2);
138 while (current != nullptr) {
139 if (current->HeapSize() >= size) {
140 // Found an element large enough to hold the requested size. Dequeue,
141 // split and enqueue the remainder.
142 intptr_t remainder_size = current->HeapSize() - size;
143 intptr_t region_size =
144 size + FreeListElement::HeaderSizeFor(remainder_size);
145 if (is_protected) {
146 // Make the allocated block and the header of the remainder element
147 // writable. The remainder will be non-writable if necessary after
148 // the call to SplitElementAfterAndEnqueue.
149 VirtualMemory::Protect(reinterpret_cast<void*>(current), region_size,
150 VirtualMemory::kReadWrite);
151 }
152
153 if (previous == nullptr) {
154 free_lists_[kNumLists] = current->next();
155 } else {
156 // If the previous free list element's next field is protected, it
157 // needs to be unprotected before storing to it and reprotected
158 // after.
159 bool target_is_protected = false;
160 uword target_address = 0L;
161 if (is_protected) {
162 uword writable_start = reinterpret_cast<uword>(current);
163 uword writable_end = writable_start + region_size - 1;
164 target_address = previous->next_address();
165 target_is_protected =
166 !VirtualMemory::InSamePage(target_address, writable_start) &&
167 !VirtualMemory::InSamePage(target_address, writable_end);
168 }
169 if (target_is_protected) {
170 VirtualMemory::Protect(reinterpret_cast<void*>(target_address),
171 kWordSize, VirtualMemory::kReadWrite);
172 }
173 previous->set_next(current->next());
174 if (target_is_protected) {
175 VirtualMemory::Protect(reinterpret_cast<void*>(target_address),
176 kWordSize, VirtualMemory::kReadExecute);
177 }
178 }
179 SplitElementAfterAndEnqueue(current, size, is_protected);
180 freelist_search_budget_ =
181 Utils::Minimum(tries_left, kInitialFreeListSearchBudget);
182 return reinterpret_cast<uword>(current);
183 } else if (tries_left-- < 0) {
184 freelist_search_budget_ = kInitialFreeListSearchBudget;
185 return 0; // Trigger allocation of new page.
186 }
187 previous = current;
188 current = current->next();
189 }
190 return 0;
191}
dart::BitSet::Test
bool Test(intptr_t i) const
Definition: bit_set.h:31
dart::BitSet::Next
intptr_t Next(intptr_t i) const
Definition: bit_set.h:38
dart::FreeListElement::next
FreeListElement * next() const
Definition: freelist.h:26
dart::FreeListElement::HeaderSizeFor
static intptr_t HeaderSizeFor(intptr_t size)
Definition: freelist.cc:71
dart::VirtualMemory::Protect
static void Protect(void *address, intptr_t size, Protection mode)
dart::VirtualMemory::InSamePage
static bool InSamePage(uword address0, uword address1)
Definition: virtual_memory.cc:16
dart::kWordSize
constexpr intptr_t kWordSize
Definition: globals.h:509

◆ TryAllocateSmallLocked()

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

Definition at line 101 of file freelist.h.

101 {
102 DEBUG_ASSERT(mutex_.IsOwnedByCurrentThread());
103 if (size > last_free_small_size_) {
104 return 0;
105 }
106 int index = IndexForSize(size);
107 if (index != kNumLists && free_map_.Test(index)) {
108 return reinterpret_cast<uword>(DequeueElement(index));
109 }
110 if ((index + 1) < kNumLists) {
111 intptr_t next_index = free_map_.Next(index + 1);
112 if (next_index != -1) {
113 FreeListElement* element = DequeueElement(next_index);
114 SplitElementAfterAndEnqueue(element, size, false);
115 return reinterpret_cast<uword>(element);
116 }
117 }
118 return 0;
119 }

Friends And Related Function Documentation

◆ GCIncrementalCompactor

friend class GCIncrementalCompactor
friend

Definition at line 227 of file freelist.h.

◆ PrologueTask

friend class PrologueTask
friend

Definition at line 228 of file freelist.h.

The documentation for this class was generated from the following files:
Generated on Sun Jun 23 2024 21:59:06 for Flutter Engine by doxygen 1.9.4