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 #ifndef V8_HEAP_SPACES_H_ | 5 #ifndef V8_HEAP_SPACES_H_ |
6 #define V8_HEAP_SPACES_H_ | 6 #define V8_HEAP_SPACES_H_ |
7 | 7 |
8 #include "src/allocation.h" | 8 #include "src/allocation.h" |
9 #include "src/atomic-utils.h" | 9 #include "src/atomic-utils.h" |
10 #include "src/base/atomicops.h" | 10 #include "src/base/atomicops.h" |
11 #include "src/base/bits.h" | 11 #include "src/base/bits.h" |
12 #include "src/base/platform/mutex.h" | 12 #include "src/base/platform/mutex.h" |
13 #include "src/flags.h" | 13 #include "src/flags.h" |
14 #include "src/hashmap.h" | 14 #include "src/hashmap.h" |
15 #include "src/list.h" | 15 #include "src/list.h" |
16 #include "src/objects.h" | 16 #include "src/objects.h" |
17 #include "src/utils.h" | 17 #include "src/utils.h" |
18 | 18 |
19 namespace v8 { | 19 namespace v8 { |
20 namespace internal { | 20 namespace internal { |
21 | 21 |
| 22 class CompactionSpaceCollection; |
22 class Isolate; | 23 class Isolate; |
23 | 24 |
24 // ----------------------------------------------------------------------------- | 25 // ----------------------------------------------------------------------------- |
25 // Heap structures: | 26 // Heap structures: |
26 // | 27 // |
27 // A JS heap consists of a young generation, an old generation, and a large | 28 // A JS heap consists of a young generation, an old generation, and a large |
28 // object space. The young generation is divided into two semispaces. A | 29 // object space. The young generation is divided into two semispaces. A |
29 // scavenger implements Cheney's copying algorithm. The old generation is | 30 // scavenger implements Cheney's copying algorithm. The old generation is |
30 // separated into a map space and an old object space. The map space contains | 31 // separated into a map space and an old object space. The map space contains |
31 // all (and only) map objects, the rest of old objects go into the old space. | 32 // all (and only) map objects, the rest of old objects go into the old space. |
(...skipping 1381 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1413 | 1414 |
1414 private: | 1415 private: |
1415 // Current allocation top. | 1416 // Current allocation top. |
1416 Address top_; | 1417 Address top_; |
1417 // Current allocation limit. | 1418 // Current allocation limit. |
1418 Address limit_; | 1419 Address limit_; |
1419 }; | 1420 }; |
1420 | 1421 |
1421 | 1422 |
1422 // An abstraction of the accounting statistics of a page-structured space. | 1423 // An abstraction of the accounting statistics of a page-structured space. |
1423 // The 'capacity' of a space is the number of object-area bytes (i.e., not | |
1424 // including page bookkeeping structures) currently in the space. The 'size' | |
1425 // of a space is the number of allocated bytes, the 'waste' in the space is | |
1426 // the number of bytes that are not allocated and not available to | |
1427 // allocation without reorganizing the space via a GC (e.g. small blocks due | |
1428 // to internal fragmentation, top of page areas in map space), and the bytes | |
1429 // 'available' is the number of unallocated bytes that are not waste. The | |
1430 // capacity is the sum of size, waste, and available. | |
1431 // | 1424 // |
1432 // The stats are only set by functions that ensure they stay balanced. These | 1425 // The stats are only set by functions that ensure they stay balanced. These |
1433 // functions increase or decrease one of the non-capacity stats in | 1426 // functions increase or decrease one of the non-capacity stats in conjunction |
1434 // conjunction with capacity, or else they always balance increases and | 1427 // with capacity, or else they always balance increases and decreases to the |
1435 // decreases to the non-capacity stats. | 1428 // non-capacity stats. |
1436 class AllocationStats BASE_EMBEDDED { | 1429 class AllocationStats BASE_EMBEDDED { |
1437 public: | 1430 public: |
1438 AllocationStats() { Clear(); } | 1431 AllocationStats() { Clear(); } |
1439 | 1432 |
1440 // Zero out all the allocation statistics (i.e., no capacity). | 1433 // Zero out all the allocation statistics (i.e., no capacity). |
1441 void Clear() { | 1434 void Clear() { |
1442 capacity_ = 0; | 1435 capacity_ = 0; |
1443 max_capacity_ = 0; | 1436 max_capacity_ = 0; |
1444 size_ = 0; | 1437 size_ = 0; |
1445 waste_ = 0; | 1438 waste_ = 0; |
| 1439 borrowed_ = 0; |
1446 } | 1440 } |
1447 | 1441 |
1448 void ClearSizeWaste() { | 1442 void ClearSizeWaste() { |
1449 size_ = capacity_; | 1443 size_ = capacity_; |
1450 waste_ = 0; | 1444 waste_ = 0; |
1451 } | 1445 } |
1452 | 1446 |
1453 // Reset the allocation statistics (i.e., available = capacity with no | 1447 // Reset the allocation statistics (i.e., available = capacity with no |
1454 // wasted or allocated bytes). | 1448 // wasted or allocated bytes). |
1455 void Reset() { | 1449 void Reset() { |
1456 size_ = 0; | 1450 size_ = 0; |
1457 waste_ = 0; | 1451 waste_ = 0; |
1458 } | 1452 } |
1459 | 1453 |
1460 // Accessors for the allocation statistics. | 1454 // Accessors for the allocation statistics. |
1461 intptr_t Capacity() { return capacity_; } | 1455 intptr_t Capacity() { return capacity_; } |
1462 intptr_t MaxCapacity() { return max_capacity_; } | 1456 intptr_t MaxCapacity() { return max_capacity_; } |
1463 intptr_t Size() { return size_; } | 1457 intptr_t Size() { return size_; } |
1464 intptr_t Waste() { return waste_; } | 1458 intptr_t Waste() { return waste_; } |
| 1459 intptr_t Borrowed() { return borrowed_; } |
1465 | 1460 |
1466 // Grow the space by adding available bytes. They are initially marked as | 1461 // Grow the space by adding available bytes. They are initially marked as |
1467 // being in use (part of the size), but will normally be immediately freed, | 1462 // being in use (part of the size), but will normally be immediately freed, |
1468 // putting them on the free list and removing them from size_. | 1463 // putting them on the free list and removing them from size_. |
1469 void ExpandSpace(int size_in_bytes) { | 1464 void ExpandSpace(int size_in_bytes) { |
1470 capacity_ += size_in_bytes; | 1465 capacity_ += size_in_bytes; |
1471 size_ += size_in_bytes; | 1466 size_ += size_in_bytes; |
1472 if (capacity_ > max_capacity_) { | 1467 if (capacity_ > max_capacity_) { |
1473 max_capacity_ = capacity_; | 1468 max_capacity_ = capacity_; |
1474 } | 1469 } |
1475 DCHECK(size_ >= 0); | 1470 DCHECK(size_ >= 0); |
1476 } | 1471 } |
1477 | 1472 |
1478 // Shrink the space by removing available bytes. Since shrinking is done | 1473 // Shrink the space by removing available bytes. Since shrinking is done |
1479 // during sweeping, bytes have been marked as being in use (part of the size) | 1474 // during sweeping, bytes have been marked as being in use (part of the size) |
1480 // and are hereby freed. | 1475 // and are hereby freed. |
1481 void ShrinkSpace(int size_in_bytes) { | 1476 void ShrinkSpace(int size_in_bytes) { |
| 1477 DCHECK_GE(size_in_bytes, 0); |
1482 capacity_ -= size_in_bytes; | 1478 capacity_ -= size_in_bytes; |
1483 size_ -= size_in_bytes; | 1479 size_ -= size_in_bytes; |
1484 DCHECK(size_ >= 0); | 1480 DCHECK_GE(size_, 0); |
| 1481 DCHECK_GE(capacity_, 0); |
1485 } | 1482 } |
1486 | 1483 |
1487 // Allocate from available bytes (available -> size). | 1484 // Allocate from available bytes (available -> size). |
1488 void AllocateBytes(intptr_t size_in_bytes) { | 1485 void AllocateBytes(intptr_t size_in_bytes) { |
| 1486 DCHECK_GE(size_in_bytes, 0); |
1489 size_ += size_in_bytes; | 1487 size_ += size_in_bytes; |
1490 DCHECK(size_ >= 0); | 1488 DCHECK_GE(size_, 0); |
| 1489 DCHECK_LE(size_, capacity_); |
1491 } | 1490 } |
1492 | 1491 |
1493 // Free allocated bytes, making them available (size -> available). | 1492 // Free allocated bytes, making them available (size -> available). |
1494 void DeallocateBytes(intptr_t size_in_bytes) { | 1493 void DeallocateBytes(intptr_t size_in_bytes) { |
1495 size_ -= size_in_bytes; | 1494 size_ -= size_in_bytes; |
1496 DCHECK(size_ >= 0); | 1495 DCHECK(size_ >= 0); |
1497 } | 1496 } |
1498 | 1497 |
1499 // Waste free bytes (available -> waste). | 1498 // Waste free bytes (available -> waste). |
1500 void WasteBytes(int size_in_bytes) { | 1499 void WasteBytes(int size_in_bytes) { |
1501 DCHECK(size_in_bytes >= 0); | 1500 DCHECK(size_in_bytes >= 0); |
1502 waste_ += size_in_bytes; | 1501 waste_ += size_in_bytes; |
1503 } | 1502 } |
1504 | 1503 |
1505 // Merge {other} into {this}. | 1504 // Merge {other} into {this}. |
1506 void Merge(const AllocationStats& other) { | 1505 void Merge(const AllocationStats& other) { |
| 1506 DCHECK_GE(other.capacity_, 0); |
| 1507 DCHECK_GE(other.size_, 0); |
| 1508 DCHECK_GE(other.waste_, 0); |
1507 capacity_ += other.capacity_; | 1509 capacity_ += other.capacity_; |
1508 size_ += other.size_; | 1510 size_ += other.size_; |
| 1511 // See description of |borrowed_| below why we need to remove it from |
| 1512 // |capacity_| as well as |size_|. |
| 1513 capacity_ -= other.borrowed_; |
| 1514 size_ -= other.borrowed_; |
1509 waste_ += other.waste_; | 1515 waste_ += other.waste_; |
1510 if (other.max_capacity_ > max_capacity_) { | 1516 if (capacity_ > max_capacity_) { |
1511 max_capacity_ = other.max_capacity_; | 1517 max_capacity_ = capacity_; |
1512 } | 1518 } |
1513 } | 1519 } |
1514 | 1520 |
1515 void DecreaseCapacity(intptr_t size_in_bytes) { | 1521 void DecreaseCapacity(intptr_t size_in_bytes) { |
| 1522 DCHECK_GE(size_in_bytes, 0); |
1516 capacity_ -= size_in_bytes; | 1523 capacity_ -= size_in_bytes; |
1517 DCHECK_GE(capacity_, 0); | 1524 DCHECK_GE(capacity_, size_); |
1518 } | 1525 } |
1519 | 1526 |
1520 void IncreaseCapacity(intptr_t size_in_bytes) { capacity_ += size_in_bytes; } | 1527 void IncreaseCapacity(intptr_t size_in_bytes) { |
| 1528 DCHECK_GE(size_in_bytes, 0); |
| 1529 capacity_ += size_in_bytes; |
| 1530 } |
| 1531 |
| 1532 void BorrowMemory(intptr_t size_in_bytes) { |
| 1533 DCHECK_GE(size_in_bytes, 0); |
| 1534 borrowed_ += size_in_bytes; |
| 1535 } |
1521 | 1536 |
1522 private: | 1537 private: |
| 1538 // |capacity_| is the number of object-area bytes (i.e., not including page |
| 1539 // bookkeeping structures) currently in the space. |
1523 intptr_t capacity_; | 1540 intptr_t capacity_; |
| 1541 |
| 1542 // |max_capacity_| is the maximum |capacity_| ever observed by a space. |
1524 intptr_t max_capacity_; | 1543 intptr_t max_capacity_; |
| 1544 |
| 1545 // |size_| is the number of allocated bytes. |
1525 intptr_t size_; | 1546 intptr_t size_; |
| 1547 |
| 1548 // |waste_| is the number of bytes that are not allocated and not available |
| 1549 // to allocation without reorganizing the space via a GC (e.g. small blocks |
| 1550 // due to internal fragmentation, top of page areas in map space |
1526 intptr_t waste_; | 1551 intptr_t waste_; |
| 1552 |
| 1553 // |borrowed_| denotes the number of bytes that are currently borrowed in this |
| 1554 // space, i.e., they have been accounted as allocated in another space, but |
| 1555 // have been moved over (e.g. through a free list) to the current space. |
| 1556 // Note that accounting them as allocated results in them being included |
| 1557 // in |size_| as well as |capacity_| of the original space. The temporary |
| 1558 // double-accounting is fixed upon merging accounting stats. |
| 1559 intptr_t borrowed_; |
1527 }; | 1560 }; |
1528 | 1561 |
1529 | 1562 |
1530 // ----------------------------------------------------------------------------- | 1563 // ----------------------------------------------------------------------------- |
1531 // Free lists for old object spaces | 1564 // Free lists for old object spaces |
1532 | 1565 |
1533 // The free list category holds a pointer to the top element and a pointer to | 1566 // The free list category holds a pointer to the top element and a pointer to |
1534 // the end element of the linked list of free memory blocks. | 1567 // the end element of the linked list of free memory blocks. |
1535 class FreeListCategory { | 1568 class FreeListCategory { |
1536 public: | 1569 public: |
(...skipping 138 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1675 bool ContainsPageFreeListItems(Page* p); | 1708 bool ContainsPageFreeListItems(Page* p); |
1676 | 1709 |
1677 FreeListCategory* small_list() { return &small_list_; } | 1710 FreeListCategory* small_list() { return &small_list_; } |
1678 FreeListCategory* medium_list() { return &medium_list_; } | 1711 FreeListCategory* medium_list() { return &medium_list_; } |
1679 FreeListCategory* large_list() { return &large_list_; } | 1712 FreeListCategory* large_list() { return &large_list_; } |
1680 FreeListCategory* huge_list() { return &huge_list_; } | 1713 FreeListCategory* huge_list() { return &huge_list_; } |
1681 | 1714 |
1682 PagedSpace* owner() { return owner_; } | 1715 PagedSpace* owner() { return owner_; } |
1683 | 1716 |
1684 private: | 1717 private: |
| 1718 enum FreeListCategoryType { kSmall, kMedium, kLarge, kHuge }; |
| 1719 |
1685 // The size range of blocks, in bytes. | 1720 // The size range of blocks, in bytes. |
1686 static const int kMinBlockSize = 3 * kPointerSize; | 1721 static const int kMinBlockSize = 3 * kPointerSize; |
1687 static const int kMaxBlockSize = Page::kMaxRegularHeapObjectSize; | 1722 static const int kMaxBlockSize = Page::kMaxRegularHeapObjectSize; |
1688 | 1723 |
1689 static const int kSmallListMin = 0x1f * kPointerSize; | 1724 static const int kSmallListMin = 0x1f * kPointerSize; |
1690 static const int kSmallListMax = 0xff * kPointerSize; | 1725 static const int kSmallListMax = 0xff * kPointerSize; |
1691 static const int kMediumListMax = 0x7ff * kPointerSize; | 1726 static const int kMediumListMax = 0x7ff * kPointerSize; |
1692 static const int kLargeListMax = 0x3fff * kPointerSize; | 1727 static const int kLargeListMax = 0x3fff * kPointerSize; |
1693 static const int kSmallAllocationMax = kSmallListMin; | 1728 static const int kSmallAllocationMax = kSmallListMin; |
1694 static const int kMediumAllocationMax = kSmallListMax; | 1729 static const int kMediumAllocationMax = kSmallListMax; |
1695 static const int kLargeAllocationMax = kMediumListMax; | 1730 static const int kLargeAllocationMax = kMediumListMax; |
1696 | 1731 |
1697 FreeSpace* FindNodeFor(int size_in_bytes, int* node_size); | 1732 FreeSpace* FindNodeFor(int size_in_bytes, int* node_size); |
| 1733 FreeSpace* FindNodeIn(FreeListCategoryType category, int* node_size); |
| 1734 |
| 1735 FreeListCategory* GetFreeListCategory(FreeListCategoryType category) { |
| 1736 switch (category) { |
| 1737 case kSmall: |
| 1738 return &small_list_; |
| 1739 case kMedium: |
| 1740 return &medium_list_; |
| 1741 case kLarge: |
| 1742 return &large_list_; |
| 1743 case kHuge: |
| 1744 return &huge_list_; |
| 1745 default: |
| 1746 UNREACHABLE(); |
| 1747 } |
| 1748 UNREACHABLE(); |
| 1749 return nullptr; |
| 1750 } |
| 1751 |
| 1752 void UpdateFragmentationStats(FreeListCategoryType category, Address address, |
| 1753 int size); |
1698 | 1754 |
1699 PagedSpace* owner_; | 1755 PagedSpace* owner_; |
1700 Heap* heap_; | 1756 Heap* heap_; |
1701 FreeListCategory small_list_; | 1757 FreeListCategory small_list_; |
1702 FreeListCategory medium_list_; | 1758 FreeListCategory medium_list_; |
1703 FreeListCategory large_list_; | 1759 FreeListCategory large_list_; |
1704 FreeListCategory huge_list_; | 1760 FreeListCategory huge_list_; |
1705 | 1761 |
| 1762 friend class PagedSpace; |
| 1763 |
1706 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList); | 1764 DISALLOW_IMPLICIT_CONSTRUCTORS(FreeList); |
1707 }; | 1765 }; |
1708 | 1766 |
1709 | 1767 |
1710 class AllocationResult { | 1768 class AllocationResult { |
1711 public: | 1769 public: |
1712 // Implicit constructor from Object*. | 1770 // Implicit constructor from Object*. |
1713 AllocationResult(Object* object) // NOLINT | 1771 AllocationResult(Object* object) // NOLINT |
1714 : object_(object) { | 1772 : object_(object) { |
1715 // AllocationResults can't return Smis, which are used to represent | 1773 // AllocationResults can't return Smis, which are used to represent |
(...skipping 262 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
1978 inline int AreaSize() { return area_size_; } | 2036 inline int AreaSize() { return area_size_; } |
1979 | 2037 |
1980 // Merges {other} into the current space. Note that this modifies {other}, | 2038 // Merges {other} into the current space. Note that this modifies {other}, |
1981 // e.g., removes its bump pointer area and resets statistics. | 2039 // e.g., removes its bump pointer area and resets statistics. |
1982 void MergeCompactionSpace(CompactionSpace* other); | 2040 void MergeCompactionSpace(CompactionSpace* other); |
1983 | 2041 |
1984 void MoveOverFreeMemory(PagedSpace* other); | 2042 void MoveOverFreeMemory(PagedSpace* other); |
1985 | 2043 |
1986 virtual bool is_local() { return false; } | 2044 virtual bool is_local() { return false; } |
1987 | 2045 |
| 2046 // Divide {this} free lists up among {other} CompactionSpaceCollections |
| 2047 // up to some certain {limit} of bytes. Note that this operation eventually |
| 2048 // needs to iterate over nodes one-by-one, making it a potentially slow |
| 2049 // operation. |
| 2050 void DivideMemory(CompactionSpaceCollection** other, int num, intptr_t limit); |
| 2051 |
1988 protected: | 2052 protected: |
| 2053 // Adds memory starting at {start} of {size_in_bytes} to the space. |
| 2054 void AddMemory(Address start, int size_in_bytes) { |
| 2055 IncreaseCapacity(size_in_bytes); |
| 2056 accounting_stats_.BorrowMemory(size_in_bytes); |
| 2057 Free(start, size_in_bytes); |
| 2058 } |
| 2059 |
| 2060 // Tries to remove some memory from {this} free lists. We try to remove |
| 2061 // as much memory as possible, i.e., we check the free lists from huge |
| 2062 // to small. |
| 2063 FreeSpace* TryRemoveMemory(); |
| 2064 |
1989 // PagedSpaces that should be included in snapshots have different, i.e., | 2065 // PagedSpaces that should be included in snapshots have different, i.e., |
1990 // smaller, initial pages. | 2066 // smaller, initial pages. |
1991 virtual bool snapshotable() { return true; } | 2067 virtual bool snapshotable() { return true; } |
1992 | 2068 |
1993 FreeList* free_list() { return &free_list_; } | 2069 FreeList* free_list() { return &free_list_; } |
1994 | 2070 |
1995 bool HasPages() { return anchor_.next_page() != &anchor_; } | 2071 bool HasPages() { return anchor_.next_page() != &anchor_; } |
1996 | 2072 |
1997 // Cleans up the space, frees all pages in this space except those belonging | 2073 // Cleans up the space, frees all pages in this space except those belonging |
1998 // to the initial chunk, uncommits addresses in the initial chunk. | 2074 // to the initial chunk, uncommits addresses in the initial chunk. |
(...skipping 735 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2734 }; | 2810 }; |
2735 | 2811 |
2736 // ----------------------------------------------------------------------------- | 2812 // ----------------------------------------------------------------------------- |
2737 // Compaction space that is used temporarily during compaction. | 2813 // Compaction space that is used temporarily during compaction. |
2738 | 2814 |
2739 class CompactionSpace : public PagedSpace { | 2815 class CompactionSpace : public PagedSpace { |
2740 public: | 2816 public: |
2741 CompactionSpace(Heap* heap, AllocationSpace id, Executability executable) | 2817 CompactionSpace(Heap* heap, AllocationSpace id, Executability executable) |
2742 : PagedSpace(heap, id, executable) {} | 2818 : PagedSpace(heap, id, executable) {} |
2743 | 2819 |
2744 // Adds external memory starting at {start} of {size_in_bytes} to the space. | |
2745 void AddExternalMemory(Address start, int size_in_bytes) { | |
2746 IncreaseCapacity(size_in_bytes); | |
2747 Free(start, size_in_bytes); | |
2748 } | |
2749 | |
2750 virtual bool is_local() { return true; } | 2820 virtual bool is_local() { return true; } |
2751 | 2821 |
2752 protected: | 2822 protected: |
2753 // The space is temporary and not included in any snapshots. | 2823 // The space is temporary and not included in any snapshots. |
2754 virtual bool snapshotable() { return false; } | 2824 virtual bool snapshotable() { return false; } |
2755 }; | 2825 }; |
2756 | 2826 |
2757 | 2827 |
2758 // A collection of |CompactionSpace|s used by a single compaction task. | 2828 // A collection of |CompactionSpace|s used by a single compaction task. |
2759 class CompactionSpaceCollection : public Malloced { | 2829 class CompactionSpaceCollection : public Malloced { |
(...skipping 215 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
2975 count = 0; | 3045 count = 0; |
2976 } | 3046 } |
2977 // Must be small, since an iteration is used for lookup. | 3047 // Must be small, since an iteration is used for lookup. |
2978 static const int kMaxComments = 64; | 3048 static const int kMaxComments = 64; |
2979 }; | 3049 }; |
2980 #endif | 3050 #endif |
2981 } | 3051 } |
2982 } // namespace v8::internal | 3052 } // namespace v8::internal |
2983 | 3053 |
2984 #endif // V8_HEAP_SPACES_H_ | 3054 #endif // V8_HEAP_SPACES_H_ |
OLD | NEW |