Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(403)

Side by Side Diff: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h

Issue 2531973002: Simple BlinkGC heap compaction. (Closed)
Patch Set: synchronize on compaction finish Created 4 years ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
(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
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698