OLD | NEW |
1 // Copyright 2011 the V8 project authors. All rights reserved. | 1 // Copyright 2011 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 1363 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1374 return reinterpret_cast<FreeListNode*>(maybe); | 1374 return reinterpret_cast<FreeListNode*>(maybe); |
1375 } | 1375 } |
1376 | 1376 |
1377 private: | 1377 private: |
1378 static const int kNextOffset = POINTER_SIZE_ALIGN(FreeSpace::kHeaderSize); | 1378 static const int kNextOffset = POINTER_SIZE_ALIGN(FreeSpace::kHeaderSize); |
1379 | 1379 |
1380 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode); | 1380 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeListNode); |
1381 }; | 1381 }; |
1382 | 1382 |
1383 | 1383 |
| 1384 // The free list category holds a pointer to the top element and a pointer to |
| 1385 // the end element of the linked list of free memory blocks. |
| 1386 class FreeListCategory { |
| 1387 public: |
| 1388 FreeListCategory() : top_(NULL), end_(NULL), available_(0) {} |
| 1389 |
| 1390 void Reset(); |
| 1391 |
| 1392 void Free(FreeListNode* node, int size_in_bytes); |
| 1393 |
| 1394 FreeListNode* PickNodeFromList(int *node_size); |
| 1395 |
| 1396 intptr_t CountFreeListItemsInList(Page* p); |
| 1397 |
| 1398 intptr_t EvictFreeListItemsInList(Page* p); |
| 1399 |
| 1400 void RepairFreeList(Heap* heap); |
| 1401 |
| 1402 FreeListNode** GetTopAddress() { return &top_; } |
| 1403 FreeListNode* top() const { return top_; } |
| 1404 void set_top(FreeListNode* top) { top_ = top; } |
| 1405 |
| 1406 FreeListNode** GetEndAddress() { return &end_; } |
| 1407 FreeListNode* end() const { return end_; } |
| 1408 void set_end(FreeListNode* end) { end_ = end; } |
| 1409 |
| 1410 int* GetAvailableAddress() { return &available_; } |
| 1411 int available() const { return available_; } |
| 1412 void set_available(int available) { available_ = available; } |
| 1413 |
| 1414 #ifdef DEBUG |
| 1415 intptr_t SumFreeList(); |
| 1416 int FreeListLength(); |
| 1417 #endif |
| 1418 |
| 1419 private: |
| 1420 FreeListNode* top_; |
| 1421 FreeListNode* end_; |
| 1422 |
| 1423 // Total available bytes in all blocks of this free list category. |
| 1424 int available_; |
| 1425 }; |
| 1426 |
| 1427 |
1384 // The free list for the old space. The free list is organized in such a way | 1428 // The free list for the old space. The free list is organized in such a way |
1385 // as to encourage objects allocated around the same time to be near each | 1429 // as to encourage objects allocated around the same time to be near each |
1386 // other. The normal way to allocate is intended to be by bumping a 'top' | 1430 // other. The normal way to allocate is intended to be by bumping a 'top' |
1387 // pointer until it hits a 'limit' pointer. When the limit is hit we need to | 1431 // pointer until it hits a 'limit' pointer. When the limit is hit we need to |
1388 // find a new space to allocate from. This is done with the free list, which | 1432 // find a new space to allocate from. This is done with the free list, which |
1389 // is divided up into rough categories to cut down on waste. Having finer | 1433 // is divided up into rough categories to cut down on waste. Having finer |
1390 // categories would scatter allocation more. | 1434 // categories would scatter allocation more. |
1391 | 1435 |
1392 // The old space free list is organized in categories. | 1436 // The old space free list is organized in categories. |
1393 // 1-31 words: Such small free areas are discarded for efficiency reasons. | 1437 // 1-31 words: Such small free areas are discarded for efficiency reasons. |
(...skipping 11 matching lines...) Expand all Loading... |
1405 // At least 16384 words. This list is for objects of 2048 words or larger. | 1449 // At least 16384 words. This list is for objects of 2048 words or larger. |
1406 // Empty pages are added to this list. These spaces are called huge. | 1450 // Empty pages are added to this list. These spaces are called huge. |
1407 class FreeList BASE_EMBEDDED { | 1451 class FreeList BASE_EMBEDDED { |
1408 public: | 1452 public: |
1409 explicit FreeList(PagedSpace* owner); | 1453 explicit FreeList(PagedSpace* owner); |
1410 | 1454 |
1411 // Clear the free list. | 1455 // Clear the free list. |
1412 void Reset(); | 1456 void Reset(); |
1413 | 1457 |
1414 // Return the number of bytes available on the free list. | 1458 // Return the number of bytes available on the free list. |
1415 intptr_t available() { return available_; } | 1459 intptr_t available() { |
| 1460 return small_list_.available() + medium_list_.available() + |
| 1461 large_list_.available() + huge_list_.available(); |
| 1462 } |
1416 | 1463 |
1417 // Place a node on the free list. The block of size 'size_in_bytes' | 1464 // Place a node on the free list. The block of size 'size_in_bytes' |
1418 // starting at 'start' is placed on the free list. The return value is the | 1465 // starting at 'start' is placed on the free list. The return value is the |
1419 // number of bytes that have been lost due to internal fragmentation by | 1466 // number of bytes that have been lost due to internal fragmentation by |
1420 // freeing the block. Bookkeeping information will be written to the block, | 1467 // freeing the block. Bookkeeping information will be written to the block, |
1421 // i.e., its contents will be destroyed. The start address should be word | 1468 // i.e., its contents will be destroyed. The start address should be word |
1422 // aligned, and the size should be a non-zero multiple of the word size. | 1469 // aligned, and the size should be a non-zero multiple of the word size. |
1423 int Free(Address start, int size_in_bytes); | 1470 int Free(Address start, int size_in_bytes); |
1424 | 1471 |
1425 // Allocate a block of size 'size_in_bytes' from the free list. The block | 1472 // Allocate a block of size 'size_in_bytes' from the free list. The block |
1426 // is unitialized. A failure is returned if no block is available. The | 1473 // is unitialized. A failure is returned if no block is available. The |
1427 // number of bytes lost to fragmentation is returned in the output parameter | 1474 // number of bytes lost to fragmentation is returned in the output parameter |
1428 // 'wasted_bytes'. The size should be a non-zero multiple of the word size. | 1475 // 'wasted_bytes'. The size should be a non-zero multiple of the word size. |
1429 MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes); | 1476 MUST_USE_RESULT HeapObject* Allocate(int size_in_bytes); |
1430 | 1477 |
1431 #ifdef DEBUG | 1478 #ifdef DEBUG |
1432 void Zap(); | 1479 void Zap(); |
1433 static intptr_t SumFreeList(FreeListNode* node); | |
1434 static int FreeListLength(FreeListNode* cur); | |
1435 intptr_t SumFreeLists(); | 1480 intptr_t SumFreeLists(); |
1436 bool IsVeryLong(); | 1481 bool IsVeryLong(); |
1437 #endif | 1482 #endif |
1438 | 1483 |
1439 // Used after booting the VM. | 1484 // Used after booting the VM. |
1440 void RepairLists(Heap* heap); | 1485 void RepairLists(Heap* heap); |
1441 | 1486 |
1442 struct SizeStats { | 1487 struct SizeStats { |
1443 intptr_t Total() { | 1488 intptr_t Total() { |
1444 return small_size_ + medium_size_ + large_size_ + huge_size_; | 1489 return small_size_ + medium_size_ + large_size_ + huge_size_; |
1445 } | 1490 } |
1446 | 1491 |
1447 intptr_t small_size_; | 1492 intptr_t small_size_; |
1448 intptr_t medium_size_; | 1493 intptr_t medium_size_; |
1449 intptr_t large_size_; | 1494 intptr_t large_size_; |
1450 intptr_t huge_size_; | 1495 intptr_t huge_size_; |
1451 }; | 1496 }; |
1452 | 1497 |
1453 void CountFreeListItems(Page* p, SizeStats* sizes); | 1498 void CountFreeListItems(Page* p, SizeStats* sizes); |
1454 | 1499 |
1455 intptr_t EvictFreeListItems(Page* p); | 1500 intptr_t EvictFreeListItems(Page* p); |
1456 | 1501 |
1457 private: | 1502 private: |
1458 // The size range of blocks, in bytes. | 1503 // The size range of blocks, in bytes. |
1459 static const int kMinBlockSize = 3 * kPointerSize; | 1504 static const int kMinBlockSize = 3 * kPointerSize; |
1460 static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize; | 1505 static const int kMaxBlockSize = Page::kMaxNonCodeHeapObjectSize; |
1461 | 1506 |
1462 FreeListNode* PickNodeFromList(FreeListNode** list, int* node_size); | |
1463 | |
1464 FreeListNode* FindNodeFor(int size_in_bytes, int* node_size); | 1507 FreeListNode* FindNodeFor(int size_in_bytes, int* node_size); |
1465 | 1508 |
1466 PagedSpace* owner_; | 1509 PagedSpace* owner_; |
1467 Heap* heap_; | 1510 Heap* heap_; |
1468 | 1511 |
1469 // Total available bytes in all blocks on this free list. | |
1470 int available_; | |
1471 | |
1472 static const int kSmallListMin = 0x20 * kPointerSize; | 1512 static const int kSmallListMin = 0x20 * kPointerSize; |
1473 static const int kSmallListMax = 0xff * kPointerSize; | 1513 static const int kSmallListMax = 0xff * kPointerSize; |
1474 static const int kMediumListMax = 0x7ff * kPointerSize; | 1514 static const int kMediumListMax = 0x7ff * kPointerSize; |
1475 static const int kLargeListMax = 0x3fff * kPointerSize; | 1515 static const int kLargeListMax = 0x3fff * kPointerSize; |
1476 static const int kSmallAllocationMax = kSmallListMin - kPointerSize; | 1516 static const int kSmallAllocationMax = kSmallListMin - kPointerSize; |
1477 static const int kMediumAllocationMax = kSmallListMax; | 1517 static const int kMediumAllocationMax = kSmallListMax; |
1478 static const int kLargeAllocationMax = kMediumListMax; | 1518 static const int kLargeAllocationMax = kMediumListMax; |
1479 FreeListNode* small_list_; | 1519 FreeListCategory small_list_; |
1480 FreeListNode* medium_list_; | 1520 FreeListCategory medium_list_; |
1481 FreeListNode* large_list_; | 1521 FreeListCategory large_list_; |
1482 FreeListNode* huge_list_; | 1522 FreeListCategory huge_list_; |
1483 | 1523 |
1484 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList); | 1524 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList); |
1485 }; | 1525 }; |
1486 | 1526 |
1487 | 1527 |
1488 class PagedSpace : public Space { | 1528 class PagedSpace : public Space { |
1489 public: | 1529 public: |
1490 // Creates a space with a maximum capacity, and an id. | 1530 // Creates a space with a maximum capacity, and an id. |
1491 PagedSpace(Heap* heap, | 1531 PagedSpace(Heap* heap, |
1492 intptr_t max_capacity, | 1532 intptr_t max_capacity, |
(...skipping 1230 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2723 } | 2763 } |
2724 // Must be small, since an iteration is used for lookup. | 2764 // Must be small, since an iteration is used for lookup. |
2725 static const int kMaxComments = 64; | 2765 static const int kMaxComments = 64; |
2726 }; | 2766 }; |
2727 #endif | 2767 #endif |
2728 | 2768 |
2729 | 2769 |
2730 } } // namespace v8::internal | 2770 } } // namespace v8::internal |
2731 | 2771 |
2732 #endif // V8_SPACES_H_ | 2772 #endif // V8_SPACES_H_ |
OLD | NEW |