OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "src/heap/spaces.h" | 5 #include "src/heap/spaces.h" |
6 | 6 |
7 #include "src/base/bits.h" | 7 #include "src/base/bits.h" |
8 #include "src/base/platform/platform.h" | 8 #include "src/base/platform/platform.h" |
9 #include "src/full-codegen/full-codegen.h" | 9 #include "src/full-codegen/full-codegen.h" |
10 #include "src/heap/slots-buffer.h" | 10 #include "src/heap/slots-buffer.h" |
(...skipping 2219 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2230 } else { | 2230 } else { |
2231 DCHECK(*map_location == heap->free_space_map()); | 2231 DCHECK(*map_location == heap->free_space_map()); |
2232 } | 2232 } |
2233 n = n->next(); | 2233 n = n->next(); |
2234 } | 2234 } |
2235 } | 2235 } |
2236 | 2236 |
2237 | 2237 |
2238 FreeList::FreeList(PagedSpace* owner) | 2238 FreeList::FreeList(PagedSpace* owner) |
2239 : owner_(owner), | 2239 : owner_(owner), |
2240 heap_(owner->heap()), | |
2241 wasted_bytes_(0), | 2240 wasted_bytes_(0), |
2242 small_list_(this, kSmall), | 2241 small_list_(this, kSmall), |
2243 medium_list_(this, kMedium), | 2242 medium_list_(this, kMedium), |
2244 large_list_(this, kLarge), | 2243 large_list_(this, kLarge), |
2245 huge_list_(this, kHuge) { | 2244 huge_list_(this, kHuge) { |
2246 Reset(); | 2245 Reset(); |
2247 } | 2246 } |
2248 | 2247 |
2249 | 2248 |
2250 intptr_t FreeList::Concatenate(FreeList* other) { | 2249 intptr_t FreeList::Concatenate(FreeList* other) { |
(...skipping 27 matching lines...) Expand all Loading... |
2278 medium_list_.Reset(); | 2277 medium_list_.Reset(); |
2279 large_list_.Reset(); | 2278 large_list_.Reset(); |
2280 huge_list_.Reset(); | 2279 huge_list_.Reset(); |
2281 ResetStats(); | 2280 ResetStats(); |
2282 } | 2281 } |
2283 | 2282 |
2284 | 2283 |
2285 int FreeList::Free(Address start, int size_in_bytes) { | 2284 int FreeList::Free(Address start, int size_in_bytes) { |
2286 if (size_in_bytes == 0) return 0; | 2285 if (size_in_bytes == 0) return 0; |
2287 | 2286 |
2288 heap_->CreateFillerObjectAt(start, size_in_bytes); | 2287 owner()->heap()->CreateFillerObjectAt(start, size_in_bytes); |
2289 | 2288 |
2290 Page* page = Page::FromAddress(start); | 2289 Page* page = Page::FromAddress(start); |
2291 | 2290 |
2292 // Early return to drop too-small blocks on the floor. | 2291 // Early return to drop too-small blocks on the floor. |
2293 if (size_in_bytes <= kSmallListMin) { | 2292 if (size_in_bytes <= kSmallListMin) { |
2294 page->add_non_available_small_blocks(size_in_bytes); | 2293 page->add_non_available_small_blocks(size_in_bytes); |
2295 wasted_bytes_ += size_in_bytes; | 2294 wasted_bytes_ += size_in_bytes; |
2296 return size_in_bytes; | 2295 return size_in_bytes; |
2297 } | 2296 } |
2298 | 2297 |
2299 FreeSpace* free_space = FreeSpace::cast(HeapObject::FromAddress(start)); | 2298 FreeSpace* free_space = FreeSpace::cast(HeapObject::FromAddress(start)); |
2300 // Insert other blocks at the head of a free list of the appropriate | 2299 // Insert other blocks at the head of a free list of the appropriate |
2301 // magnitude. | 2300 // magnitude. |
2302 if (size_in_bytes <= kSmallListMax) { | 2301 if (size_in_bytes <= kSmallListMax) { |
2303 small_list_.Free(free_space, size_in_bytes); | 2302 small_list_.Free(free_space, size_in_bytes); |
2304 page->add_available_in_small_free_list(size_in_bytes); | 2303 page->add_available_in_small_free_list(size_in_bytes); |
2305 } else if (size_in_bytes <= kMediumListMax) { | 2304 } else if (size_in_bytes <= kMediumListMax) { |
2306 medium_list_.Free(free_space, size_in_bytes); | 2305 medium_list_.Free(free_space, size_in_bytes); |
2307 page->add_available_in_medium_free_list(size_in_bytes); | 2306 page->add_available_in_medium_free_list(size_in_bytes); |
2308 } else if (size_in_bytes <= kLargeListMax) { | 2307 } else if (size_in_bytes <= kLargeListMax) { |
2309 large_list_.Free(free_space, size_in_bytes); | 2308 large_list_.Free(free_space, size_in_bytes); |
2310 page->add_available_in_large_free_list(size_in_bytes); | 2309 page->add_available_in_large_free_list(size_in_bytes); |
2311 } else { | 2310 } else { |
2312 huge_list_.Free(free_space, size_in_bytes); | 2311 huge_list_.Free(free_space, size_in_bytes); |
2313 page->add_available_in_huge_free_list(size_in_bytes); | 2312 page->add_available_in_huge_free_list(size_in_bytes); |
2314 } | 2313 } |
2315 | 2314 |
2316 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2315 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2317 return 0; | 2316 return 0; |
2318 } | 2317 } |
2319 | 2318 |
2320 | 2319 |
2321 FreeSpace* FreeList::FindNodeIn(FreeListCategoryType category, int* node_size) { | 2320 FreeSpace* FreeList::FindNodeIn(FreeListCategoryType category, int* node_size) { |
2322 FreeSpace* node = GetFreeListCategory(category)->PickNodeFromList(node_size); | 2321 FreeSpace* node = GetFreeListCategory(category)->PickNodeFromList(node_size); |
2323 if (node != nullptr) { | 2322 if (node != nullptr) { |
2324 Page::FromAddress(node->address()) | 2323 Page::FromAddress(node->address()) |
2325 ->add_available_in_free_list(category, -(*node_size)); | 2324 ->add_available_in_free_list(category, -(*node_size)); |
2326 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2325 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2327 } | 2326 } |
2328 return node; | 2327 return node; |
2329 } | 2328 } |
2330 | 2329 |
2331 | 2330 |
2332 FreeSpace* FreeList::FindNodeFor(int size_in_bytes, int* node_size) { | 2331 FreeSpace* FreeList::FindNodeFor(int size_in_bytes, int* node_size) { |
2333 FreeSpace* node = NULL; | 2332 FreeSpace* node = NULL; |
2334 Page* page = NULL; | 2333 Page* page = NULL; |
2335 | 2334 |
2336 if (size_in_bytes <= kSmallAllocationMax) { | 2335 if (size_in_bytes <= kSmallAllocationMax) { |
2337 node = FindNodeIn(kSmall, node_size); | 2336 node = FindNodeIn(kSmall, node_size); |
2338 if (node != NULL) { | 2337 if (node != NULL) { |
2339 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2338 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2340 return node; | 2339 return node; |
2341 } | 2340 } |
2342 } | 2341 } |
2343 | 2342 |
2344 if (size_in_bytes <= kMediumAllocationMax) { | 2343 if (size_in_bytes <= kMediumAllocationMax) { |
2345 node = FindNodeIn(kMedium, node_size); | 2344 node = FindNodeIn(kMedium, node_size); |
2346 if (node != NULL) { | 2345 if (node != NULL) { |
2347 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2346 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2348 return node; | 2347 return node; |
2349 } | 2348 } |
2350 } | 2349 } |
2351 | 2350 |
2352 if (size_in_bytes <= kLargeAllocationMax) { | 2351 if (size_in_bytes <= kLargeAllocationMax) { |
2353 node = FindNodeIn(kLarge, node_size); | 2352 node = FindNodeIn(kLarge, node_size); |
2354 if (node != NULL) { | 2353 if (node != NULL) { |
2355 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2354 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2356 return node; | 2355 return node; |
2357 } | 2356 } |
2358 } | 2357 } |
2359 | 2358 |
2360 node = huge_list_.SearchForNodeInList(size_in_bytes, node_size); | 2359 node = huge_list_.SearchForNodeInList(size_in_bytes, node_size); |
2361 | 2360 |
2362 if (node != NULL) { | 2361 if (node != NULL) { |
2363 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2362 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2364 return node; | 2363 return node; |
2365 } | 2364 } |
2366 | 2365 |
2367 if (size_in_bytes <= kSmallListMax) { | 2366 if (size_in_bytes <= kSmallListMax) { |
2368 node = small_list_.PickNodeFromList(size_in_bytes, node_size); | 2367 node = small_list_.PickNodeFromList(size_in_bytes, node_size); |
2369 if (node != NULL) { | 2368 if (node != NULL) { |
2370 DCHECK(size_in_bytes <= *node_size); | 2369 DCHECK(size_in_bytes <= *node_size); |
2371 page = Page::FromAddress(node->address()); | 2370 page = Page::FromAddress(node->address()); |
2372 page->add_available_in_small_free_list(-(*node_size)); | 2371 page->add_available_in_small_free_list(-(*node_size)); |
2373 } | 2372 } |
2374 } else if (size_in_bytes <= kMediumListMax) { | 2373 } else if (size_in_bytes <= kMediumListMax) { |
2375 node = medium_list_.PickNodeFromList(size_in_bytes, node_size); | 2374 node = medium_list_.PickNodeFromList(size_in_bytes, node_size); |
2376 if (node != NULL) { | 2375 if (node != NULL) { |
2377 DCHECK(size_in_bytes <= *node_size); | 2376 DCHECK(size_in_bytes <= *node_size); |
2378 page = Page::FromAddress(node->address()); | 2377 page = Page::FromAddress(node->address()); |
2379 page->add_available_in_medium_free_list(-(*node_size)); | 2378 page->add_available_in_medium_free_list(-(*node_size)); |
2380 } | 2379 } |
2381 } else if (size_in_bytes <= kLargeListMax) { | 2380 } else if (size_in_bytes <= kLargeListMax) { |
2382 node = large_list_.PickNodeFromList(size_in_bytes, node_size); | 2381 node = large_list_.PickNodeFromList(size_in_bytes, node_size); |
2383 if (node != NULL) { | 2382 if (node != NULL) { |
2384 DCHECK(size_in_bytes <= *node_size); | 2383 DCHECK(size_in_bytes <= *node_size); |
2385 page = Page::FromAddress(node->address()); | 2384 page = Page::FromAddress(node->address()); |
2386 page->add_available_in_large_free_list(-(*node_size)); | 2385 page->add_available_in_large_free_list(-(*node_size)); |
2387 } | 2386 } |
2388 } | 2387 } |
2389 | 2388 |
2390 DCHECK(IsVeryLong() || available() == SumFreeLists()); | 2389 DCHECK(IsVeryLong() || Available() == SumFreeLists()); |
2391 return node; | 2390 return node; |
2392 } | 2391 } |
2393 | 2392 |
2394 | 2393 |
2395 // Allocation on the old space free list. If it succeeds then a new linear | 2394 // Allocation on the old space free list. If it succeeds then a new linear |
2396 // allocation space has been set up with the top and limit of the space. If | 2395 // allocation space has been set up with the top and limit of the space. If |
2397 // the allocation fails then NULL is returned, and the caller can perform a GC | 2396 // the allocation fails then NULL is returned, and the caller can perform a GC |
2398 // or allocate a new page before retrying. | 2397 // or allocate a new page before retrying. |
2399 HeapObject* FreeList::Allocate(int size_in_bytes) { | 2398 HeapObject* FreeList::Allocate(int size_in_bytes) { |
2400 DCHECK(0 < size_in_bytes); | 2399 DCHECK(0 < size_in_bytes); |
(...skipping 103 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2504 FreeSpace* cur = top(); | 2503 FreeSpace* cur = top(); |
2505 while (cur != NULL) { | 2504 while (cur != NULL) { |
2506 DCHECK(cur->map() == cur->GetHeap()->root(Heap::kFreeSpaceMapRootIndex)); | 2505 DCHECK(cur->map() == cur->GetHeap()->root(Heap::kFreeSpaceMapRootIndex)); |
2507 sum += cur->nobarrier_size(); | 2506 sum += cur->nobarrier_size(); |
2508 cur = cur->next(); | 2507 cur = cur->next(); |
2509 } | 2508 } |
2510 return sum; | 2509 return sum; |
2511 } | 2510 } |
2512 | 2511 |
2513 | 2512 |
2514 static const int kVeryLongFreeList = 500; | |
2515 | |
2516 | |
2517 int FreeListCategory::FreeListLength() { | 2513 int FreeListCategory::FreeListLength() { |
2518 int length = 0; | 2514 int length = 0; |
2519 FreeSpace* cur = top(); | 2515 FreeSpace* cur = top(); |
2520 while (cur != NULL) { | 2516 while (cur != NULL) { |
2521 length++; | 2517 length++; |
2522 cur = cur->next(); | 2518 cur = cur->next(); |
2523 if (length == kVeryLongFreeList) return length; | 2519 if (length == kVeryLongFreeList) return length; |
2524 } | 2520 } |
2525 return length; | 2521 return length; |
2526 } | 2522 } |
2527 | 2523 |
2528 | 2524 |
| 2525 bool FreeListCategory::IsVeryLong() { |
| 2526 return FreeListLength() == kVeryLongFreeList; |
| 2527 } |
| 2528 |
| 2529 |
2529 bool FreeList::IsVeryLong() { | 2530 bool FreeList::IsVeryLong() { |
2530 if (small_list_.FreeListLength() == kVeryLongFreeList) return true; | 2531 return small_list_.IsVeryLong() || medium_list_.IsVeryLong() || |
2531 if (medium_list_.FreeListLength() == kVeryLongFreeList) return true; | 2532 large_list_.IsVeryLong() || huge_list_.IsVeryLong(); |
2532 if (large_list_.FreeListLength() == kVeryLongFreeList) return true; | |
2533 if (huge_list_.FreeListLength() == kVeryLongFreeList) return true; | |
2534 return false; | |
2535 } | 2533 } |
2536 | 2534 |
2537 | 2535 |
2538 // This can take a very long time because it is linear in the number of entries | 2536 // This can take a very long time because it is linear in the number of entries |
2539 // on the free list, so it should not be called if FreeListLength returns | 2537 // on the free list, so it should not be called if FreeListLength returns |
2540 // kVeryLongFreeList. | 2538 // kVeryLongFreeList. |
2541 intptr_t FreeList::SumFreeLists() { | 2539 intptr_t FreeList::SumFreeLists() { |
2542 intptr_t sum = small_list_.SumFreeList(); | 2540 intptr_t sum = small_list_.SumFreeList(); |
2543 sum += medium_list_.SumFreeList(); | 2541 sum += medium_list_.SumFreeList(); |
2544 sum += large_list_.SumFreeList(); | 2542 sum += large_list_.SumFreeList(); |
(...skipping 107 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2652 heap()->OldGenerationAllocationLimitReached()) { | 2650 heap()->OldGenerationAllocationLimitReached()) { |
2653 // If sweeper threads are active, wait for them at that point and steal | 2651 // If sweeper threads are active, wait for them at that point and steal |
2654 // elements form their free-lists. | 2652 // elements form their free-lists. |
2655 HeapObject* object = WaitForSweeperThreadsAndRetryAllocation(size_in_bytes); | 2653 HeapObject* object = WaitForSweeperThreadsAndRetryAllocation(size_in_bytes); |
2656 return object; | 2654 return object; |
2657 } | 2655 } |
2658 | 2656 |
2659 // Try to expand the space and allocate in the new next page. | 2657 // Try to expand the space and allocate in the new next page. |
2660 if (Expand()) { | 2658 if (Expand()) { |
2661 DCHECK((CountTotalPages() > 1) || | 2659 DCHECK((CountTotalPages() > 1) || |
2662 (size_in_bytes <= free_list_.available())); | 2660 (size_in_bytes <= free_list_.Available())); |
2663 return free_list_.Allocate(size_in_bytes); | 2661 return free_list_.Allocate(size_in_bytes); |
2664 } | 2662 } |
2665 | 2663 |
2666 // If sweeper threads are active, wait for them at that point and steal | 2664 // If sweeper threads are active, wait for them at that point and steal |
2667 // elements form their free-lists. Allocation may still fail their which | 2665 // elements form their free-lists. Allocation may still fail their which |
2668 // would indicate that there is not enough memory for the given allocation. | 2666 // would indicate that there is not enough memory for the given allocation. |
2669 return WaitForSweeperThreadsAndRetryAllocation(size_in_bytes); | 2667 return WaitForSweeperThreadsAndRetryAllocation(size_in_bytes); |
2670 } | 2668 } |
2671 | 2669 |
2672 | 2670 |
(...skipping 485 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
3158 object->ShortPrint(); | 3156 object->ShortPrint(); |
3159 PrintF("\n"); | 3157 PrintF("\n"); |
3160 } | 3158 } |
3161 printf(" --------------------------------------\n"); | 3159 printf(" --------------------------------------\n"); |
3162 printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes()); | 3160 printf(" Marked: %x, LiveCount: %x\n", mark_size, LiveBytes()); |
3163 } | 3161 } |
3164 | 3162 |
3165 #endif // DEBUG | 3163 #endif // DEBUG |
3166 } // namespace internal | 3164 } // namespace internal |
3167 } // namespace v8 | 3165 } // namespace v8 |
OLD | NEW |