OLD | NEW |
(Empty) | |
| 1 // Copyright 2016 Opera Software AS. All rights reserved. |
| 2 // Use of this source code is governed by a BSD-style license that can be |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #ifndef SparseHeapBitmap_h |
| 6 #define SparseHeapBitmap_h |
| 7 |
| 8 #include "platform/heap/BlinkGC.h" |
| 9 #include "platform/heap/HeapPage.h" |
| 10 #include "wtf/Alignment.h" |
| 11 #include "wtf/PtrUtil.h" |
| 12 #include <bitset> |
| 13 #include <memory> |
| 14 |
| 15 namespace blink { |
| 16 |
| 17 // A sparse bitmap of heap addresses where the (very few) addresses that are |
| 18 // set are likely to be in small clusters. The abstraction is tailored to |
| 19 // support heap compaction, assuming the following: |
| 20 // |
| 21 // - Addresses will be bitmap-marked from lower to higher addresses. |
| 22 // - Bitmap lookups are performed for each object that is compacted |
| 23 // and moved to some new location, supplying the (base, size) |
| 24 // pair of the object's heap allocation. |
| 25 // - If the sparse bitmap has any marked addresses in that range, it |
| 26 // returns a sub-bitmap that can be quickly iterated over to check which |
| 27 // addresses within the range are actually set. |
| 28 // - The bitmap is needed to support something that is very rarely done |
| 29 // by the current Blink codebase, which is to have nested collection |
| 30 // part objects. Consequently, it is safe to assume sparseness. |
| 31 // |
| 32 // Support the above by having a sparse bitmap organized as a binary |
| 33 // tree with nodes covering fixed size ranges via a simple bitmap/set. |
| 34 // That is, each SparseHeapBitmap node will contain a bitmap/set for |
| 35 // some fixed size range, along with pointers to SparseHeapBitmaps |
| 36 // for addresses on each side its range. |
| 37 // |
| 38 // This bitmap tree isn't kept balanced across the Address additions |
| 39 // made. |
| 40 // |
| 41 class PLATFORM_EXPORT SparseHeapBitmap { |
| 42 public: |
| 43 static std::unique_ptr<SparseHeapBitmap> create(Address base) { |
| 44 return WTF::wrapUnique(new SparseHeapBitmap(base)); |
| 45 } |
| 46 |
| 47 ~SparseHeapBitmap() {} |
| 48 |
| 49 // Return the sparse bitmap subtree that at least covers the |
| 50 // [address, address + size) range, or nullptr if none. |
| 51 // |
| 52 // The returned SparseHeapBitmap can be used to quickly lookup what |
| 53 // addresses in that range are set or not; see |isSet()|. Its |
| 54 // |isSet()| behavior outside that range is not defined. |
| 55 SparseHeapBitmap* hasRange(Address, size_t); |
| 56 |
| 57 // True iff |address| is set for this SparseHeapBitmap tree. |
| 58 bool isSet(Address); |
| 59 |
| 60 // Mark |address| as present/set. |
| 61 void add(Address); |
| 62 |
| 63 // The assumed minimum alignment of the pointers being added. Cannot |
| 64 // exceed |log2(allocationGranularity)|; having it be equal to |
| 65 // the platform pointer alignment is what's wanted. |
| 66 static const int s_pointerAlignmentInBits = WTF_ALIGN_OF(void*) == 8 ? 3 : 2; |
| 67 static const size_t s_pointerAlignmentMask = |
| 68 (0x1u << s_pointerAlignmentInBits) - 1; |
| 69 |
| 70 // Represent ranges in 0x100 bitset chunks; bit I is set iff Address |
| 71 // |m_base + I * (0x1 << s_pointerAlignmentInBits)| has been added to the |
| 72 // |SparseHeapBitmap|. |
| 73 static const size_t s_bitmapChunkSize = 0x100; |
| 74 |
| 75 // A SparseHeapBitmap either contains a single Address or a bitmap |
| 76 // recording the mapping for [m_base, m_base + s_bitmapChunkRange) |
| 77 static const size_t s_bitmapChunkRange = s_bitmapChunkSize |
| 78 << s_pointerAlignmentInBits; |
| 79 |
| 80 // Return the number of nodes; for debug stats. |
| 81 size_t intervalCount() const; |
| 82 |
| 83 private: |
| 84 explicit SparseHeapBitmap(Address base) : m_base(base), m_size(1) { |
| 85 DCHECK(!(reinterpret_cast<uintptr_t>(m_base) & s_pointerAlignmentMask)); |
| 86 static_assert(s_pointerAlignmentMask <= allocationMask, |
| 87 "address shift exceeds heap pointer alignment"); |
| 88 // For now, only recognize 8 and 4. |
| 89 static_assert(WTF_ALIGN_OF(void*) == 8 || WTF_ALIGN_OF(void*) == 4, |
| 90 "unsupported pointer alignment"); |
| 91 } |
| 92 |
| 93 Address base() const { return m_base; } |
| 94 size_t size() const { return m_size; } |
| 95 Address end() const { return base() + (m_size - 1); } |
| 96 |
| 97 Address maxEnd() const { return base() + s_bitmapChunkRange; } |
| 98 |
| 99 Address minStart() const { |
| 100 // If this bitmap node represents the sparse [m_base, s_bitmapChunkRange) |
| 101 // range, do not allow it to be "left extended" as that would entail |
| 102 // having to shift down the contents of the std::bitset somehow. |
| 103 // |
| 104 // This shouldn't be a real problem as any clusters of set addresses |
| 105 // will be marked while iterating from lower to higher addresses, hence |
| 106 // "left extension" are unlikely to be common. |
| 107 if (m_bitmap) |
| 108 return base(); |
| 109 return (m_base > reinterpret_cast<Address>(s_bitmapChunkRange)) |
| 110 ? (base() - s_bitmapChunkRange + 1) |
| 111 : nullptr; |
| 112 } |
| 113 |
| 114 Address swapBase(Address address) { |
| 115 DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask)); |
| 116 Address oldBase = m_base; |
| 117 m_base = address; |
| 118 return oldBase; |
| 119 } |
| 120 |
| 121 void createBitmap(); |
| 122 |
| 123 Address m_base; |
| 124 // Either 1 or |s_bitmapChunkRange|. |
| 125 size_t m_size; |
| 126 |
| 127 // If non-null, contains a bitmap for addresses within [m_base, m_size) |
| 128 std::unique_ptr<std::bitset<s_bitmapChunkSize>> m_bitmap; |
| 129 |
| 130 std::unique_ptr<SparseHeapBitmap> m_left; |
| 131 std::unique_ptr<SparseHeapBitmap> m_right; |
| 132 }; |
| 133 |
| 134 } // namespace blink |
| 135 |
| 136 #endif // SparseHeapBitmap_h |
OLD | NEW |