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 <map> | 7 #include <map> |
8 | 8 |
9 #include "vm/bit_set.h" | 9 #include "vm/bit_set.h" |
10 #include "vm/lockers.h" | 10 #include "vm/lockers.h" |
(...skipping 178 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
189 intptr_t index = IndexForSize(size); | 189 intptr_t index = IndexForSize(size); |
190 FreeListElement* element = FreeListElement::AsElement(addr, size); | 190 FreeListElement* element = FreeListElement::AsElement(addr, size); |
191 EnqueueElement(element, index); | 191 EnqueueElement(element, index); |
192 // Postcondition: the (page containing the) header is left writable. | 192 // Postcondition: the (page containing the) header is left writable. |
193 } | 193 } |
194 | 194 |
195 | 195 |
196 void FreeList::Reset() { | 196 void FreeList::Reset() { |
197 MutexLocker ml(mutex_); | 197 MutexLocker ml(mutex_); |
198 free_map_.Reset(); | 198 free_map_.Reset(); |
| 199 last_free_small_size_ = -1; |
199 for (int i = 0; i < (kNumLists + 1); i++) { | 200 for (int i = 0; i < (kNumLists + 1); i++) { |
200 free_lists_[i] = NULL; | 201 free_lists_[i] = NULL; |
201 } | 202 } |
202 } | 203 } |
203 | 204 |
204 | 205 |
205 intptr_t FreeList::IndexForSize(intptr_t size) { | 206 intptr_t FreeList::IndexForSize(intptr_t size) { |
206 ASSERT(size >= kObjectAlignment); | 207 ASSERT(size >= kObjectAlignment); |
207 ASSERT(Utils::IsAligned(size, kObjectAlignment)); | 208 ASSERT(Utils::IsAligned(size, kObjectAlignment)); |
208 | 209 |
209 intptr_t index = size / kObjectAlignment; | 210 intptr_t index = size >> kObjectAlignmentLog2; |
210 if (index >= kNumLists) { | 211 if (index >= kNumLists) { |
211 index = kNumLists; | 212 index = kNumLists; |
212 } | 213 } |
213 return index; | 214 return index; |
214 } | 215 } |
215 | 216 |
216 | 217 |
217 void FreeList::EnqueueElement(FreeListElement* element, intptr_t index) { | 218 void FreeList::EnqueueElement(FreeListElement* element, intptr_t index) { |
218 FreeListElement* next = free_lists_[index]; | 219 FreeListElement* next = free_lists_[index]; |
219 if (next == NULL && index != kNumLists) { | 220 if (next == NULL && index != kNumLists) { |
220 free_map_.Set(index, true); | 221 free_map_.Set(index, true); |
| 222 last_free_small_size_ = Utils::Maximum(last_free_small_size_, |
| 223 index << kObjectAlignmentLog2); |
221 } | 224 } |
222 element->set_next(next); | 225 element->set_next(next); |
223 free_lists_[index] = element; | 226 free_lists_[index] = element; |
224 } | 227 } |
225 | 228 |
226 | 229 |
227 FreeListElement* FreeList::DequeueElement(intptr_t index) { | 230 FreeListElement* FreeList::DequeueElement(intptr_t index) { |
228 FreeListElement* result = free_lists_[index]; | 231 FreeListElement* result = free_lists_[index]; |
229 FreeListElement* next = result->next(); | 232 FreeListElement* next = result->next(); |
230 if (next == NULL && index != kNumLists) { | 233 if (next == NULL && index != kNumLists) { |
231 free_map_.Set(index, false); | 234 free_map_.Set(index, false); |
| 235 intptr_t size = index << kObjectAlignmentLog2; |
| 236 if (size == last_free_small_size_) { |
| 237 // Note: Last() returns -1 if none are set; avoid shift of negative. |
| 238 last_free_small_size_ = free_map_.Last() * kObjectAlignment; |
| 239 // TODO(koda): Consider adding BitSet::Previous(i). |
| 240 } |
232 } | 241 } |
233 free_lists_[index] = next; | 242 free_lists_[index] = next; |
234 return result; | 243 return result; |
235 } | 244 } |
236 | 245 |
237 | 246 |
238 intptr_t FreeList::LengthLocked(int index) const { | 247 intptr_t FreeList::LengthLocked(int index) const { |
239 DEBUG_ASSERT(mutex_->Owner() == Isolate::Current()); | 248 DEBUG_ASSERT(mutex_->Owner() == Isolate::Current()); |
240 ASSERT(index >= 0); | 249 ASSERT(index >= 0); |
241 ASSERT(index < kNumLists); | 250 ASSERT(index < kNumLists); |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
337 VirtualMemory::Protect(reinterpret_cast<void*>(remainder_address), | 346 VirtualMemory::Protect(reinterpret_cast<void*>(remainder_address), |
338 remainder_size, | 347 remainder_size, |
339 VirtualMemory::kReadExecute); | 348 VirtualMemory::kReadExecute); |
340 ASSERT(status); | 349 ASSERT(status); |
341 } | 350 } |
342 } | 351 } |
343 | 352 |
344 | 353 |
345 FreeListElement* FreeList::TryAllocateLarge(intptr_t minimum_size) { | 354 FreeListElement* FreeList::TryAllocateLarge(intptr_t minimum_size) { |
346 MutexLocker ml(mutex_); | 355 MutexLocker ml(mutex_); |
| 356 return TryAllocateLargeLocked(minimum_size); |
| 357 } |
| 358 |
| 359 |
| 360 FreeListElement* FreeList::TryAllocateLargeLocked(intptr_t minimum_size) { |
| 361 DEBUG_ASSERT(mutex_->Owner() == Isolate::Current()); |
347 FreeListElement* previous = NULL; | 362 FreeListElement* previous = NULL; |
348 FreeListElement* current = free_lists_[kNumLists]; | 363 FreeListElement* current = free_lists_[kNumLists]; |
349 // TODO(koda): Find largest. | 364 // TODO(koda): Find largest. |
350 while (current != NULL) { | 365 while (current != NULL) { |
351 FreeListElement* next = current->next(); | 366 FreeListElement* next = current->next(); |
352 if (current->Size() >= minimum_size) { | 367 if (current->Size() >= minimum_size) { |
353 if (previous == NULL) { | 368 if (previous == NULL) { |
354 free_lists_[kNumLists] = next; | 369 free_lists_[kNumLists] = next; |
355 } else { | 370 } else { |
356 previous->set_next(next); | 371 previous->set_next(next); |
357 } | 372 } |
358 return current; | 373 return current; |
359 } | 374 } |
360 previous = current; | 375 previous = current; |
361 current = next; | 376 current = next; |
362 } | 377 } |
363 return NULL; | 378 return NULL; |
364 } | 379 } |
365 | 380 |
| 381 |
| 382 uword FreeList::TryAllocateSmallLocked(intptr_t size) { |
| 383 DEBUG_ASSERT(mutex_->Owner() == Isolate::Current()); |
| 384 if (size > last_free_small_size_) { |
| 385 return 0; |
| 386 } |
| 387 int index = IndexForSize(size); |
| 388 if (index != kNumLists && free_map_.Test(index)) { |
| 389 return reinterpret_cast<uword>(DequeueElement(index)); |
| 390 } |
| 391 if ((index + 1) < kNumLists) { |
| 392 intptr_t next_index = free_map_.Next(index + 1); |
| 393 if (next_index != -1) { |
| 394 FreeListElement* element = DequeueElement(next_index); |
| 395 SplitElementAfterAndEnqueue(element, size, false); |
| 396 return reinterpret_cast<uword>(element); |
| 397 } |
| 398 } |
| 399 return 0; |
| 400 } |
| 401 |
366 } // namespace dart | 402 } // namespace dart |
OLD | NEW |