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