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