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