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 "wtf/PtrUtil.h" |
| 10 #include <bitset> |
| 11 #include <memory> |
| 12 |
| 13 namespace blink { |
| 14 |
| 15 // A sparse bitmap of heap addresses where the (very few) addresses that are |
| 16 // set are likely to be in small clusters. The abstraction is tailored to |
| 17 // support heap compaction, assuming the following: |
| 18 // |
| 19 // - Addresses will be bitmap-marked from lower to higher addresses. |
| 20 // - Bitmap lookups are performed for each object that is compacted |
| 21 // and moved to some new location, supplying the (base, size) |
| 22 // pair of the object's heap allocation. |
| 23 // - If the sparse bitmap has any marked addresses in that range, it |
| 24 // returns a sub-bitmap that can be quickly iterated over to check which |
| 25 // addresses within the range are actually set. |
| 26 // - The bitmap is needed to support something that is very rarely done |
| 27 // by the current Blink codebase, which is to have nested collection |
| 28 // part objects. Consequently, it is safe to assume sparseness. |
| 29 // |
| 30 // Support the above by having a sparse bitmap organized as a binary |
| 31 // tree with nodes covering fixed size ranges via a simple bitmap/set. |
| 32 // That is, each SparseHeapBitmap node will contain a bitmap/set for |
| 33 // some fixed size range, along with pointers to SparseHeapBitmaps |
| 34 // for addresses on each side its range. |
| 35 // |
| 36 // This bitmap tree isn't kept balanced across the Address additions |
| 37 // made. |
| 38 class PLATFORM_EXPORT SparseHeapBitmap { |
| 39 public: |
| 40 static std::unique_ptr<SparseHeapBitmap> create(Address base) { |
| 41 return wrapUnique(new SparseHeapBitmap(base)); |
| 42 } |
| 43 |
| 44 ~SparseHeapBitmap() {} |
| 45 |
| 46 // Return the sparse bitmap subtree that covers the [address, address + size) |
| 47 // range, if any. |
| 48 // |
| 49 // The returned SparseHeapBitmap can be used to quickly lookup what |
| 50 // addresses in that range are set or not; see |isSet()|. |
| 51 SparseHeapBitmap* hasRange(Address, size_t); |
| 52 |
| 53 // True iff |address| is set for this SparseHeapBitmap tree. |
| 54 bool isSet(Address); |
| 55 |
| 56 // Mark |address| as present/set. |
| 57 void add(Address); |
| 58 |
| 59 // Represent ranges in 0x100 chunks; a SparseHeapBitmap either contains a |
| 60 // single Address or a bitmap recording the mapping for |
| 61 // [base, base + s_maxRange). |
| 62 static const size_t s_maxRange = 0x100; |
| 63 |
| 64 // Return the number of nodes; needed debugging info only. |
| 65 size_t intervalCount() const; |
| 66 |
| 67 private: |
| 68 SparseHeapBitmap(Address base) : m_base(base), m_size(1) {} |
| 69 |
| 70 Address base() const { return m_base; } |
| 71 size_t size() const { return m_size; } |
| 72 Address end() const { return m_base + (m_size - 1); } |
| 73 |
| 74 Address maxEnd() const { return m_base + s_maxRange; } |
| 75 |
| 76 Address minStart() const { |
| 77 // If this bitmap node represents the sparse [m_base, s_maxRange) range, |
| 78 // do not allow it to be "left extended" as that would entail having |
| 79 // to shift down the contents of the std::bitset somehow. |
| 80 // |
| 81 // This shouldn't be a real problem as any clusters of set addresses |
| 82 // will be marked while iterating from lower to higher addresses, hence |
| 83 // "left extension" are unlikely to be common. |
| 84 if (m_bitmap) |
| 85 return m_base; |
| 86 return (m_base > reinterpret_cast<Address>(s_maxRange)) |
| 87 ? (m_base - s_maxRange + 1) |
| 88 : nullptr; |
| 89 } |
| 90 |
| 91 Address swapBase(Address address) { |
| 92 Address oldBase = m_base; |
| 93 m_base = address; |
| 94 return oldBase; |
| 95 } |
| 96 |
| 97 void createBitmap(); |
| 98 |
| 99 Address m_base; |
| 100 // Either 1 or |s_maxRange|. |
| 101 size_t m_size; |
| 102 |
| 103 // If non-null, contains a bitmap for addresses within [m_base, m_size) |
| 104 std::unique_ptr<std::bitset<s_maxRange>> m_bitmap; |
| 105 |
| 106 std::unique_ptr<SparseHeapBitmap> m_left; |
| 107 std::unique_ptr<SparseHeapBitmap> m_right; |
| 108 }; |
| 109 |
| 110 } // namespace blink |
| 111 |
| 112 #endif // SparseHeapBitmap_h |
OLD | NEW |