OLD | NEW |
1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file | 1 // Copyright (c) 2011, the Dart project authors. Please see the AUTHORS file |
2 // for details. All rights reserved. Use of this source code is governed by a | 2 // for details. All rights reserved. Use of this source code is governed by a |
3 // BSD-style license that can be found in the LICENSE file. | 3 // BSD-style license that can be found in the LICENSE file. |
4 | 4 |
5 #include "vm/freelist.h" | 5 #include "vm/freelist.h" |
6 | 6 |
7 #include "vm/bit_set.h" | 7 #include "vm/bit_set.h" |
8 #include "vm/hash_map.h" | 8 #include "vm/hash_map.h" |
9 #include "vm/lockers.h" | 9 #include "vm/lockers.h" |
10 #include "vm/object.h" | 10 #include "vm/object.h" |
(...skipping 33 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
44 ASSERT(OFFSET_OF(FreeListElement, tags_) == Object::tags_offset()); | 44 ASSERT(OFFSET_OF(FreeListElement, tags_) == Object::tags_offset()); |
45 } | 45 } |
46 | 46 |
47 | 47 |
48 intptr_t FreeListElement::HeaderSizeFor(intptr_t size) { | 48 intptr_t FreeListElement::HeaderSizeFor(intptr_t size) { |
49 if (size == 0) return 0; | 49 if (size == 0) return 0; |
50 return ((size > RawObject::SizeTag::kMaxSizeTag) ? 3 : 2) * kWordSize; | 50 return ((size > RawObject::SizeTag::kMaxSizeTag) ? 3 : 2) * kWordSize; |
51 } | 51 } |
52 | 52 |
53 | 53 |
54 FreeList::FreeList() : mutex_(new Mutex()) { | 54 FreeList::FreeList() |
| 55 : mutex_(new Mutex()), |
| 56 freelist_search_budget_(kInitialFreeListSearchBudget) { |
55 Reset(); | 57 Reset(); |
56 } | 58 } |
57 | 59 |
58 | 60 |
59 FreeList::~FreeList() { | 61 FreeList::~FreeList() { |
60 delete mutex_; | 62 delete mutex_; |
61 } | 63 } |
62 | 64 |
63 | 65 |
64 uword FreeList::TryAllocate(intptr_t size, bool is_protected) { | 66 uword FreeList::TryAllocate(intptr_t size, bool is_protected) { |
(...skipping 39 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
104 region_size, VirtualMemory::kReadWrite); | 106 region_size, VirtualMemory::kReadWrite); |
105 ASSERT(status); | 107 ASSERT(status); |
106 } | 108 } |
107 SplitElementAfterAndEnqueue(element, size, is_protected); | 109 SplitElementAfterAndEnqueue(element, size, is_protected); |
108 return reinterpret_cast<uword>(element); | 110 return reinterpret_cast<uword>(element); |
109 } | 111 } |
110 } | 112 } |
111 | 113 |
112 FreeListElement* previous = NULL; | 114 FreeListElement* previous = NULL; |
113 FreeListElement* current = free_lists_[kNumLists]; | 115 FreeListElement* current = free_lists_[kNumLists]; |
| 116 // We are willing to search the freelist further for a big block. |
| 117 // For each successful free-list search we: |
| 118 // * increase the search budget by #allocated-words |
| 119 // * decrease the search budget by #free-list-entries-traversed |
| 120 // which guarantees us to not waste more than around 1 search step per |
| 121 // word of allocation |
| 122 // |
| 123 // If we run out of search budget we fall back to allocating a new page and |
| 124 // reset the search budget. |
| 125 intptr_t tries_left = freelist_search_budget_ + (size >> kWordSizeLog2); |
114 while (current != NULL) { | 126 while (current != NULL) { |
115 if (current->Size() >= size) { | 127 if (current->Size() >= size) { |
116 // Found an element large enough to hold the requested size. Dequeue, | 128 // Found an element large enough to hold the requested size. Dequeue, |
117 // split and enqueue the remainder. | 129 // split and enqueue the remainder. |
118 intptr_t remainder_size = current->Size() - size; | 130 intptr_t remainder_size = current->Size() - size; |
119 intptr_t region_size = | 131 intptr_t region_size = |
120 size + FreeListElement::HeaderSizeFor(remainder_size); | 132 size + FreeListElement::HeaderSizeFor(remainder_size); |
121 if (is_protected) { | 133 if (is_protected) { |
122 // Make the allocated block and the header of the remainder element | 134 // Make the allocated block and the header of the remainder element |
123 // writable. The remainder will be non-writable if necessary after | 135 // writable. The remainder will be non-writable if necessary after |
(...skipping 28 matching lines...) Expand all Loading... |
152 } | 164 } |
153 previous->set_next(current->next()); | 165 previous->set_next(current->next()); |
154 if (target_is_protected) { | 166 if (target_is_protected) { |
155 bool status = | 167 bool status = |
156 VirtualMemory::Protect(reinterpret_cast<void*>(target_address), | 168 VirtualMemory::Protect(reinterpret_cast<void*>(target_address), |
157 kWordSize, VirtualMemory::kReadExecute); | 169 kWordSize, VirtualMemory::kReadExecute); |
158 ASSERT(status); | 170 ASSERT(status); |
159 } | 171 } |
160 } | 172 } |
161 SplitElementAfterAndEnqueue(current, size, is_protected); | 173 SplitElementAfterAndEnqueue(current, size, is_protected); |
| 174 freelist_search_budget_ = |
| 175 Utils::Minimum(tries_left, kInitialFreeListSearchBudget); |
162 return reinterpret_cast<uword>(current); | 176 return reinterpret_cast<uword>(current); |
| 177 } else if (tries_left-- < 0) { |
| 178 freelist_search_budget_ = kInitialFreeListSearchBudget; |
| 179 return 0; // Trigger allocation of new page. |
163 } | 180 } |
164 previous = current; | 181 previous = current; |
165 current = current->next(); | 182 current = current->next(); |
166 } | 183 } |
167 return 0; | 184 return 0; |
168 } | 185 } |
169 | 186 |
170 | 187 |
171 void FreeList::Free(uword addr, intptr_t size) { | 188 void FreeList::Free(uword addr, intptr_t size) { |
172 MutexLocker ml(mutex_); | 189 MutexLocker ml(mutex_); |
(...skipping 202 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
375 MutexLocker ml(mutex_); | 392 MutexLocker ml(mutex_); |
376 return TryAllocateLargeLocked(minimum_size); | 393 return TryAllocateLargeLocked(minimum_size); |
377 } | 394 } |
378 | 395 |
379 | 396 |
380 FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) { | 397 FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) { |
381 DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread()); | 398 DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread()); |
382 FreeListElement* previous = NULL; | 399 FreeListElement* previous = NULL; |
383 FreeListElement* current = free_lists_[kNumLists]; | 400 FreeListElement* current = free_lists_[kNumLists]; |
384 // TODO(koda): Find largest. | 401 // TODO(koda): Find largest. |
| 402 // We are willing to search the freelist further for a big block. |
| 403 intptr_t tries_left = |
| 404 freelist_search_budget_ + (minimum_size >> kWordSizeLog2); |
385 while (current != NULL) { | 405 while (current != NULL) { |
386 FreeListElement* next = current->next(); | 406 FreeListElement* next = current->next(); |
387 if (current->Size() >= minimum_size) { | 407 if (current->Size() >= minimum_size) { |
388 if (previous == NULL) { | 408 if (previous == NULL) { |
389 free_lists_[kNumLists] = next; | 409 free_lists_[kNumLists] = next; |
390 } else { | 410 } else { |
391 previous->set_next(next); | 411 previous->set_next(next); |
392 } | 412 } |
| 413 freelist_search_budget_ = |
| 414 Utils::Minimum(tries_left, kInitialFreeListSearchBudget); |
393 return current; | 415 return current; |
| 416 } else if (tries_left-- < 0) { |
| 417 freelist_search_budget_ = kInitialFreeListSearchBudget; |
| 418 return 0; // Trigger allocation of new page. |
394 } | 419 } |
395 previous = current; | 420 previous = current; |
396 current = next; | 421 current = next; |
397 } | 422 } |
398 return NULL; | 423 return NULL; |
399 } | 424 } |
400 | 425 |
401 | 426 |
402 uword FreeList::TryAllocateSmallLocked(intptr_t size) { | 427 uword FreeList::TryAllocateSmallLocked(intptr_t size) { |
403 DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread()); | 428 DEBUG_ASSERT(mutex_->IsOwnedByCurrentThread()); |
404 if (size > last_free_small_size_) { | 429 if (size > last_free_small_size_) { |
405 return 0; | 430 return 0; |
406 } | 431 } |
407 int index = IndexForSize(size); | 432 int index = IndexForSize(size); |
408 if (index != kNumLists && free_map_.Test(index)) { | 433 if (index != kNumLists && free_map_.Test(index)) { |
409 return reinterpret_cast<uword>(DequeueElement(index)); | 434 return reinterpret_cast<uword>(DequeueElement(index)); |
410 } | 435 } |
411 if ((index + 1) < kNumLists) { | 436 if ((index + 1) < kNumLists) { |
412 intptr_t next_index = free_map_.Next(index + 1); | 437 intptr_t next_index = free_map_.Next(index + 1); |
413 if (next_index != -1) { | 438 if (next_index != -1) { |
414 FreeListElement* element = DequeueElement(next_index); | 439 FreeListElement* element = DequeueElement(next_index); |
415 SplitElementAfterAndEnqueue(element, size, false); | 440 SplitElementAfterAndEnqueue(element, size, false); |
416 return reinterpret_cast<uword>(element); | 441 return reinterpret_cast<uword>(element); |
417 } | 442 } |
418 } | 443 } |
419 return 0; | 444 return 0; |
420 } | 445 } |
421 | 446 |
422 } // namespace dart | 447 } // namespace dart |
OLD | NEW |