Index: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
diff --git a/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
new file mode 100644 |
index 0000000000000000000000000000000000000000..bdc267296e1ce0bcaa66cc1b8dd6a43a941c8fb5 |
--- /dev/null |
+++ b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h |
@@ -0,0 +1,136 @@ |
+// Copyright 2016 The Chromium Authors. All rights reserved. |
+// Use of this source code is governed by a BSD-style license that can be |
+// found in the LICENSE file. |
+ |
+#ifndef SparseHeapBitmap_h |
+#define SparseHeapBitmap_h |
+ |
+#include "platform/heap/BlinkGC.h" |
+#include "platform/heap/HeapPage.h" |
+#include "wtf/Alignment.h" |
+#include "wtf/PtrUtil.h" |
+#include <bitset> |
+#include <memory> |
+ |
+namespace blink { |
+ |
+// A sparse bitmap of heap addresses where the (very few) addresses that are |
+// set are likely to be in small clusters. The abstraction is tailored to |
+// support heap compaction, assuming the following: |
+// |
+// - Addresses will be bitmap-marked from lower to higher addresses. |
+// - Bitmap lookups are performed for each object that is compacted |
+// and moved to some new location, supplying the (base, size) |
+// pair of the object's heap allocation. |
+// - If the sparse bitmap has any marked addresses in that range, it |
+// returns a sub-bitmap that can be quickly iterated over to check which |
+// addresses within the range are actually set. |
+// - The bitmap is needed to support something that is very rarely done |
+// by the current Blink codebase, which is to have nested collection |
+// part objects. Consequently, it is safe to assume sparseness. |
+// |
+// Support the above by having a sparse bitmap organized as a binary |
+// tree with nodes covering fixed size ranges via a simple bitmap/set. |
+// That is, each SparseHeapBitmap node will contain a bitmap/set for |
+// some fixed size range, along with pointers to SparseHeapBitmaps |
+// for addresses on each side its range. |
+// |
+// This bitmap tree isn't kept balanced across the Address additions |
+// made. |
+// |
+class PLATFORM_EXPORT SparseHeapBitmap { |
+ public: |
+ static std::unique_ptr<SparseHeapBitmap> create(Address base) { |
+ return WTF::wrapUnique(new SparseHeapBitmap(base)); |
+ } |
+ |
+ ~SparseHeapBitmap() {} |
+ |
+ // Return the sparse bitmap subtree that at least covers the |
+ // [address, address + size) range, or nullptr if none. |
+ // |
+ // The returned SparseHeapBitmap can be used to quickly lookup what |
+ // addresses in that range are set or not; see |isSet()|. Its |
+ // |isSet()| behavior outside that range is not defined. |
+ SparseHeapBitmap* hasRange(Address, size_t); |
+ |
+ // True iff |address| is set for this SparseHeapBitmap tree. |
+ bool isSet(Address); |
+ |
+ // Mark |address| as present/set. |
+ void add(Address); |
+ |
+ // The assumed minimum alignment of the pointers being added. Cannot |
+ // exceed |log2(allocationGranularity)|; having it be equal to |
+ // the platform pointer alignment is what's wanted. |
+ static const int s_pointerAlignmentInBits = WTF_ALIGN_OF(void*) == 8 ? 3 : 2; |
+ static const size_t s_pointerAlignmentMask = |
+ (0x1u << s_pointerAlignmentInBits) - 1; |
+ |
+ // Represent ranges in 0x100 bitset chunks; bit I is set iff Address |
+ // |m_base + I * (0x1 << s_pointerAlignmentInBits)| has been added to the |
+ // |SparseHeapBitmap|. |
+ static const size_t s_bitmapChunkSize = 0x100; |
+ |
+ // A SparseHeapBitmap either contains a single Address or a bitmap |
+ // recording the mapping for [m_base, m_base + s_bitmapChunkRange) |
+ static const size_t s_bitmapChunkRange = s_bitmapChunkSize |
+ << s_pointerAlignmentInBits; |
+ |
+ // Return the number of nodes; for debug stats. |
+ size_t intervalCount() const; |
+ |
+ private: |
+ explicit SparseHeapBitmap(Address base) : m_base(base), m_size(1) { |
+ DCHECK(!(reinterpret_cast<uintptr_t>(m_base) & s_pointerAlignmentMask)); |
+ static_assert(s_pointerAlignmentMask <= allocationMask, |
+ "address shift exceeds heap pointer alignment"); |
+ // For now, only recognize 8 and 4. |
+ static_assert(WTF_ALIGN_OF(void*) == 8 || WTF_ALIGN_OF(void*) == 4, |
+ "unsupported pointer alignment"); |
+ } |
+ |
+ Address base() const { return m_base; } |
+ size_t size() const { return m_size; } |
+ Address end() const { return base() + (m_size - 1); } |
+ |
+ Address maxEnd() const { return base() + s_bitmapChunkRange; } |
+ |
+ Address minStart() const { |
+ // If this bitmap node represents the sparse [m_base, s_bitmapChunkRange) |
+ // range, do not allow it to be "left extended" as that would entail |
+ // having to shift down the contents of the std::bitset somehow. |
+ // |
+ // This shouldn't be a real problem as any clusters of set addresses |
+ // will be marked while iterating from lower to higher addresses, hence |
+ // "left extension" are unlikely to be common. |
+ if (m_bitmap) |
+ return base(); |
+ return (m_base > reinterpret_cast<Address>(s_bitmapChunkRange)) |
+ ? (base() - s_bitmapChunkRange + 1) |
+ : nullptr; |
+ } |
+ |
+ Address swapBase(Address address) { |
+ DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask)); |
+ Address oldBase = m_base; |
+ m_base = address; |
+ return oldBase; |
+ } |
+ |
+ void createBitmap(); |
+ |
+ Address m_base; |
+ // Either 1 or |s_bitmapChunkRange|. |
+ size_t m_size; |
+ |
+ // If non-null, contains a bitmap for addresses within [m_base, m_size) |
+ std::unique_ptr<std::bitset<s_bitmapChunkSize>> m_bitmap; |
+ |
+ std::unique_ptr<SparseHeapBitmap> m_left; |
+ std::unique_ptr<SparseHeapBitmap> m_right; |
+}; |
+ |
+} // namespace blink |
+ |
+#endif // SparseHeapBitmap_h |