Simple BlinkGC heap compaction.

third_party/WebKit/Source/platform/heap/SparseHeapBitmap.cpp

+// 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 single address bitmap and |address|
is not > bitmap->end()), and it will always hold.

It might be clearer if we DCHECK() the size() constraint instead and return
|true|; rephrased it.

+    }
+    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 there is some address set in
the range that will be lost by expanding the range to left?

If the left expansion is uncommon, would there any option to just not support it
for simplicity?

[sof, 2016/12/09 21:44:04]

It is safe because |this| is a single address bitmap (size=1), so your assumed
case won't apply here. This just helps avoid left-chained single bitmap buildup,
should the insertion pattern be such that we do end up doing these left
extensions.

+  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