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

Unified Diff: third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h

Issue 2531973002: Simple BlinkGC heap compaction. (Closed)
Patch Set: add pointer alignment handling to SparseHeapBitmap 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 side-by-side diff with in-line comments
Download patch
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..2c86ea258e35e2e4e33be31f0008f82d01f959d3
--- /dev/null
+++ b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.h
@@ -0,0 +1,132 @@
+// Copyright 2016 Opera Software AS. 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/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 {
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
+ public:
+ static std::unique_ptr<SparseHeapBitmap> create(Address base) {
+ return 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)|.. but having it be equal is a fine
+ // choice.
+ static const int s_pointerAlignmentInBits = 3;
+ 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:
+ 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.
+ DCHECK(!(reinterpret_cast<uintptr_t>(m_base) & s_pointerAlignmentMask));
+ static_assert(s_pointerAlignmentMask <= allocationMask,
+ "address shift exceeds heap 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

Powered by Google App Engine
This is Rietveld 408576698