| 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 |