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

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

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.cpp
diff --git a/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp
new file mode 100644
index 0000000000000000000000000000000000000000..a4db6d2eb1716767fb5ea8332e5414e66b123fcc
--- /dev/null
+++ b/third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp
@@ -0,0 +1,109 @@
+// 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.
+
+#include "platform/heap/SparseHeapBitmap.h"
+
+#include "wtf/PtrUtil.h"
+
+namespace blink {
+
+// Return the subtree/bitmap that covers the
+// [address, address + size) range. Null if there is none.
+SparseHeapBitmap* SparseHeapBitmap::hasRange(Address address, size_t size) {
+ DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));
+ SparseHeapBitmap* bitmap = this;
+ while (bitmap) {
+ // Interval starts after, |m_right| handles.
+ if (address > bitmap->end()) {
+ bitmap = bitmap->m_right.get();
+ continue;
+ }
+ // Interval starts within, |bitmap| is included in the resulting range.
+ if (address >= bitmap->base())
+ break;
+
+ Address right = address + size - 1;
+ // Interval starts before, but intersects with |bitmap|'s range.
+ if (right >= bitmap->base())
+ break;
+
+ // Interval is before entirely, for |m_left| to handle.
+ bitmap = bitmap->m_left.get();
+ }
+ return bitmap;
+}
+
+bool SparseHeapBitmap::isSet(Address address) {
+ DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));
+ SparseHeapBitmap* bitmap = this;
+ while (bitmap) {
+ if (address > bitmap->end()) {
+ bitmap = bitmap->m_right.get();
+ continue;
+ }
+ if (address >= bitmap->base()) {
+ if (bitmap->m_bitmap) {
+ return bitmap->m_bitmap->test((address - bitmap->base()) >>
+ s_pointerAlignmentInBits);
+ }
+ return bitmap->size() == 1;
haraken 2016/12/09 07:25:56 Would you help me understand when this can happen?
sof 2016/12/09 21:44:04 This case will happen if |this| represents a singl
+ }
+ bitmap = bitmap->m_left.get();
+ }
+ return false;
+}
+
+void SparseHeapBitmap::add(Address address) {
+ DCHECK(!(reinterpret_cast<uintptr_t>(address) & s_pointerAlignmentMask));
+ // |address| is beyond the maximum that this SparseHeapBitmap node can
+ // encompass.
+ if (address >= maxEnd()) {
+ if (!m_right) {
+ m_right = SparseHeapBitmap::create(address);
+ return;
+ }
+ m_right->add(address);
+ return;
+ }
+ // Same on the other side.
+ if (address < minStart()) {
+ if (!m_left) {
+ m_left = SparseHeapBitmap::create(address);
+ return;
+ }
+ m_left->add(address);
+ return;
+ }
+ if (address == base())
+ return;
+ // |address| can be encompassed by |this| by expanding its size.
+ if (address > base()) {
+ if (!m_bitmap)
+ createBitmap();
+ m_bitmap->set((address - base()) >> s_pointerAlignmentInBits);
+ return;
+ }
+ // Use |address| as the new base for this interval.
+ Address oldBase = swapBase(address);
haraken 2016/12/09 07:25:56 Why is this left expansion safe? What happens if t
sof 2016/12/09 21:44:04 It is safe because |this| is a single address bitm
+ createBitmap();
+ m_bitmap->set((oldBase - address) >> s_pointerAlignmentInBits);
+}
+
+void SparseHeapBitmap::createBitmap() {
+ DCHECK(!m_bitmap && size() == 1);
+ m_bitmap = makeUnique<std::bitset<s_bitmapChunkSize>>();
+ m_size = s_bitmapChunkRange;
+ m_bitmap->set(0);
+}
+
+size_t SparseHeapBitmap::intervalCount() const {
+ size_t count = 1;
+ if (m_left)
+ count += m_left->intervalCount();
+ if (m_right)
+ count += m_right->intervalCount();
+ return count;
+}
+
+} // namespace blink

Powered by Google App Engine
This is Rietveld 408576698