Simple BlinkGC heap compaction.

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

Index: third_party/WebKit/Source/platform/heap/HeapPage.cpp
diff --git a/third_party/WebKit/Source/platform/heap/HeapPage.cpp b/third_party/WebKit/Source/platform/heap/HeapPage.cpp
index 89a65566dbe00d96cb98946653cab24b50164ada..f7fd7cadbc3bdc7a2d3ad3ac60c5ded3acd17079 100644
--- a/third_party/WebKit/Source/platform/heap/HeapPage.cpp
+++ b/third_party/WebKit/Source/platform/heap/HeapPage.cpp
@@ -35,6 +35,7 @@
 #include "platform/ScriptForbiddenScope.h"
 #include "platform/heap/BlinkGCMemoryDumpProvider.h"
 #include "platform/heap/CallbackStack.h"
+#include "platform/heap/HeapCompact.h"
 #include "platform/heap/MarkingVisitor.h"
 #include "platform/heap/PageMemory.h"
 #include "platform/heap/PagePool.h"
@@ -201,6 +202,17 @@ void BaseArena::makeConsistentForGC() {
     m_firstUnsweptPage = nullptr;
   }
   ASSERT(!m_firstUnsweptPage);
+
+  HeapCompact* heapCompactor = getThreadState()->heap().compaction();
+  if (!heapCompactor->isCompactingArena(arenaIndex()))
+    return;
+
+  BasePage* nextPage = m_firstPage;
+  while (nextPage) {
+    if (!nextPage->isLargeObjectPage())
+      heapCompactor->addCompactablePage(nextPage);
+    nextPage = nextPage->next();
+  }
 }
 
 void BaseArena::makeConsistentForMutator() {
@@ -440,6 +452,132 @@ void NormalPageArena::clearFreeLists() {
   m_freeList.clear();
 }
 
+size_t NormalPageArena::arenaSize() {
+  size_t size = 0;
+  BasePage* page = m_firstPage;
+  while (page) {
+    size += page->size();
+    page = page->next();
+  }
+  LOG_HEAP_FREELIST_VERBOSE("Heap size: %zu (%d)\n", size, arenaIndex());
+  return size;
+}
+
+size_t NormalPageArena::freeListSize() {
+  size_t freeSize = m_freeList.freeListSize();
+  LOG_HEAP_FREELIST_VERBOSE("Free size: %zu (%d)\n", freeSize, arenaIndex());
+  return freeSize;
+}
+
+void NormalPageArena::sweepAndCompact() {
+  ThreadHeap& heap = getThreadState()->heap();
+  if (!heap.compaction()->isCompactingArena(arenaIndex()))
+    return;
+
+  DCHECK(!hasCurrentAllocationArea());
+
+  // Compaction is performed in-place, sliding objects down over unused
+  // holes for a smaller heap page footprint and improved locality.
+  // A "compaction pointer" is consequently kept, pointing to the next
+  // available address to move objects down to. It will belong to one
+  // of the already sweep-compacted pages for this arena, but as compaction
+  // proceeds, it will not belong to the same page as the one being
+  // currently compacted.
+  //
+  // The compaction pointer is represented by the
+  // |(availablePages, allocationPoint)| pair, with |allocationPoint|
+  // being the offset into |*availablePages|, making up the next
+  // available location. As the compaction of a arena page may cause the
+  // compaction pointer to exhaust the current page it is compacting into,
+  // page compaction can update both the current page of the compaction
+  // pointer, as well as the allocation point.
+  //
+  // By construction, the page compaction can be performed without having
+  // to allocate any new pages. So to arrange for the page compaction's
+  // supply of freed, available pages, we chain them together after each
+  // has been "compacted from". The page compaction will then reuse those
+  // as needed, and once finished, the chained pages after |*availablePages|,
+  // can be released back to the OS.

[haraken, 2016/12/06 13:30:39]

This comment looks awesome!

+  NormalPage* availablePages = nullptr;
+  size_t allocationPoint = 0;
+
+  while (m_firstUnsweptPage) {
+    BasePage* page = m_firstUnsweptPage;
+    if (page->isEmpty()) {
+      page->unlink(&m_firstUnsweptPage);
+      page->removeFromHeap();
+      continue;
+    }
+    // Large objects do not belong to this arena.
+    DCHECK(!page->isLargeObjectPage());
+    NormalPage* normalPage = static_cast<NormalPage*>(page);
+    normalPage->unlink(&m_firstUnsweptPage);
+    normalPage->markAsSwept();
+    if (!availablePages) {
+      availablePages = normalPage;
+    } else {
+      // Add |normalPage| onto the available pages chain, after the
+      // current head as it is the one currently being compacted
+      // into.

[haraken, 2016/12/06 13:30:39]

Hmm. What's an issue of just doing normalPage->link(&availablePages)? IIUC, the
only point is that when we exhaust the allocation point on the current available
page, we need to pick up *any* available page. Even if we do
normalPage->link(&availablePages), we can pick up a new available page from
availablePages.

If that is the case, we won't need the chain of availablePages; we can just call
normalPage->link(&m_firstPage) at line 514 and pick up m_firstPage when we need
a new available page.

When we finish the compaction, we just need to scan the chain of m_firstPage and
remove pages where page->isEmpty() returns true.

What do you think?

[sof, 2016/12/06 21:39:35]

Thanks for your input, but it seems very complex to add additional
scanning/flitering as m_firstPage may at this stage already have allocations
(from prefinalizers and whatnot).

I'm keeping this scheme, it's clear and follows the normal style of chaining
pages.

[haraken, 2016/12/07 08:55:11]

Okay. But even if we want to use the availablePage's chain, why can't we call
normalPage->link(&availablePages)? i.e., why we need the complexity of
|secondPage|?

[sof, 2016/12/07 10:45:08]

As the comment above explains, we're allocating from the head of
|availablePages|, so we have to inject it past that.

[haraken, 2016/12/07 12:44:33]

Ah, ok, now I understand the logic.

In addition to the below comment, I want to simplify the chaining logic a bit
more. I think the complexity comes from the fact that you're using
availablePages for two meanings: the head of the available page's chain and the
page which you're allocating from.

- availablePages is the head of the available page's chain
- allocatingPage points to the page which you're allocating from.

Then you won't need the secondPage magic.

[sof, 2016/12/07 13:01:59]

Stating the obvious perhaps, but notice that the head (i.e., |allocatingPage|)
will clearly have to be updated & advanced to the next while compacting a page &
we're out of space on the current one. Which is why the pages are chained like
here, rather than kept as two separately updatable pointers.

(I don't find that a magic/inscrutable representation, but I might well be
partial.)

[haraken, 2016/12/07 15:45:53]

You're right, but if we keep |availablePages| and |allocatingPage|:

- When we want to add a new available page, we just need to call
page->link(&availablePages).
- When we exhausted the current |allocatingPage|, we just need to call
allocatingPage=availablePages; allocatingPage->unlink(&availablePages);

which looks more straightforward and consistent with what we're doing for
m_firstPage & m_firstUnsweptPage to me personally.

[sof, 2016/12/07 22:37:25]

given the state threading that needs to happen, it makes for something a bit too
verbose, which is why I preferred this. I've spelt it out and split up the state
now though.

+      BasePage* secondPage;
+      availablePages->unlink(&secondPage);
+      normalPage->link(&secondPage);
+      // Note: |secondPage| is now aliased to |normalPage|, but we
+      // have to preserve |normalPage| for the call below.
+      availablePages->link(&secondPage);
+    }
+    allocationPoint = normalPage->sweepAndCompact(
+        availablePages, allocationPoint, &m_firstPage);
+  }
+
+  // Release unused tail of |availablePages| back to the OS.
+
+  BasePage* freePages = nullptr;
+  if (availablePages) {
+    // If the first available page has been allocated into, add it to the
+    // heap's list of swept pages. Otherwise we hand it back to the OS below.
+    if (allocationPoint) {
+      availablePages->unlink(&freePages);
+      availablePages->link(&m_firstPage);
+    } else {
+      freePages = availablePages;
+      availablePages = nullptr;
+    }
+  }
+
+  size_t freedSize = 0;
+  size_t freedPageCount = 0;
+  if (availablePages && allocationPoint != availablePages->payloadSize()) {

[haraken, 2016/12/06 13:30:39]

If we rewrite this branch as follows:

if (allocationPoint) {
  DCHECK(availablePages);
  if (allocationPoint != availablePages->payloadSize()) {
    ...;
  }
  BasePage* nextPage;
  availablePages->unlink(&nextPage);
  availablePages = static_cast<NormalPage*>(nextPage);
}

can we remove line 533 - 546 and line 561?

[sof, 2016/12/06 21:39:35]

Thanks for the suggestion, but what's here already is perfectly clear, so
keeping it.

[haraken, 2016/12/07 08:55:11]

It took me a while to understand why line 533 - 546 is needed. It seems worth to
me removing the block.

+    // Put the remainder of the page onto the free list.
+    freedSize = availablePages->payloadSize() - allocationPoint;
+    Address payload = availablePages->payload();
+#if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER) || \
+    defined(MEMORY_SANITIZER)

[haraken, 2016/12/06 13:30:39]

Should we use SET_MEMORY_INACCESSIBLE?

[sof, 2016/12/06 21:39:35]

Done.

+    FreeList::zapFreedMemory(payload + allocationPoint, freedSize);
+#endif
+    availablePages->arenaForNormalPage()->addToFreeList(
+        payload + allocationPoint, freedSize);
+  }
+  availablePages = static_cast<NormalPage*>(freePages);
+  while (availablePages) {
+    size_t pageSize = availablePages->size();
+#if DEBUG_HEAP_COMPACTION
+    if (!freedPageCount)
+      LOG_HEAP_COMPACTION("Releasing:");
+    LOG_HEAP_COMPACTION(" [%p, %p]", availablePages, availablePages + pageSize);
+#endif
+    freedSize += pageSize;
+    freedPageCount++;
+    BasePage* nextPage;
+    availablePages->unlink(&nextPage);
+    availablePages->removeFromHeap();
+    availablePages = static_cast<NormalPage*>(nextPage);
+  }
+  if (freePages)
+    LOG_HEAP_COMPACTION("\n");
+  heap.compaction()->finishedArenaCompaction(this, freedPageCount, freedSize);
+}
+
 #if ENABLE(ASSERT)
 bool NormalPageArena::isConsistentForGC() {
   // A thread heap is consistent for sweeping if none of the pages to be swept
@@ -481,7 +619,7 @@ void NormalPageArena::takeFreelistSnapshot(const String& dumpName) {
   }
 }
 
-void NormalPageArena::allocatePage() {
+NormalPage* NormalPageArena::allocatePage() {
   getThreadState()->shouldFlushHeapDoesNotContainCache();
   PageMemory* pageMemory =
       getThreadState()->heap().getFreePagePool()->takeFreePage(arenaIndex());
@@ -514,9 +652,11 @@ void NormalPageArena::allocatePage() {
       }
     }
   }
+  return new (pageMemory->writableStart()) NormalPage(pageMemory, this);
+}
 
-  NormalPage* page =
-      new (pageMemory->writableStart()) NormalPage(pageMemory, this);
+void NormalPageArena::allocateAndAddPage() {
+  NormalPage* page = allocatePage();
   page->link(&m_firstPage);
 
   getThreadState()->heap().heapStats().increaseAllocatedSpace(page->size());
@@ -813,7 +953,7 @@ Address NormalPageArena::outOfLineAllocate(size_t allocationSize,
   getThreadState()->scheduleGCIfNeeded();
 
   // 8. Add a new page to this heap.
-  allocatePage();
+  allocateAndAddPage();
 
   // 9. Try to allocate from a free list. This allocation must succeed.
   result = allocateFromFreeList(allocationSize, gcInfoIndex);
@@ -1077,6 +1217,37 @@ void NEVER_INLINE FreeList::checkFreedMemoryIsZapped(Address address,
 }
 #endif
 
+size_t FreeList::freeListSize() const {
+  size_t freeSize = 0;
+  for (unsigned i = 0; i < blinkPageSizeLog2; ++i) {
+    FreeListEntry* entry = m_freeLists[i];
+    while (entry) {
+      freeSize += entry->size();
+      entry = entry->next();
+    }
+  }
+#if DEBUG_HEAP_FREELIST
+  if (freeSize) {
+    LOG_HEAP_FREELIST_VERBOSE("FreeList(%p): %zu\n", this, freeSize);
+    for (unsigned i = 0; i < blinkPageSizeLog2; ++i) {
+      FreeListEntry* entry = m_freeLists[i];
+      size_t bucket = 0;
+      size_t count = 0;
+      while (entry) {
+        bucket += entry->size();
+        count++;
+        entry = entry->next();
+      }
+      if (bucket) {
+        LOG_HEAP_FREELIST_VERBOSE("[%d, %d]: %zu (%zu)\n", 0x1 << i,
+                                  0x1 << (i + 1), bucket, count);
+      }
+    }
+  }
+#endif
+  return freeSize;
+}
+
 void FreeList::clear() {
   m_biggestFreeListIndex = 0;
   for (size_t i = 0; i < blinkPageSizeLog2; ++i)
@@ -1246,6 +1417,110 @@ void NormalPage::sweep() {
     pageArena->getThreadState()->increaseMarkedObjectSize(markedObjectSize);
 }
 
+size_t NormalPage::sweepAndCompact(NormalPage*& arena,

[haraken, 2016/12/06 13:30:39]

arena => avalilablePages

[sof, 2016/12/06 21:39:35]

Renamed.

+                                   size_t allocationPoint,
+                                   BasePage** firstPage) {
+  size_t markedObjectSize = 0;
+  NormalPageArena* pageArena = arenaForNormalPage();
+  HeapCompact* compact = pageArena->getThreadState()->heap().compaction();
+  for (Address headerAddress = payload(); headerAddress < payloadEnd();) {
+    HeapObjectHeader* header =
+        reinterpret_cast<HeapObjectHeader*>(headerAddress);
+    size_t size = header->size();
+    DCHECK(size > 0 && size < blinkPagePayloadSize());
+
+    if (header->isPromptlyFreed())
+      pageArena->decreasePromptlyFreedSize(size);
+    if (header->isFree()) {
+      // Unpoison the freelist entry so that we
+      // can compact into it as wanted.
+      ASAN_UNPOISON_MEMORY_REGION(headerAddress, size);

[haraken, 2016/12/06 13:30:39]

SET_MEMORY_INACCESSIBLE + CHECK_MEMORY_INACCESSIBLE

Maybe you want to copy things from NormalPage::sweep() on ToT.

[sof, 2016/12/06 21:39:35]

No, please see the comment above why that isn't appropriate.

+      headerAddress += size;
+      continue;
+    }
+#if ENABLE(ASSERT)

[haraken, 2016/12/06 13:30:39]

Remove?

In any case, mimic ToT.

[sof, 2016/12/06 21:39:34]

It currently is (but the other uses tend to still use ASSERT())

+    DCHECK(header->checkHeader());
+#endif
+
+    // This is a fast version of header->payloadSize().
+    size_t payloadSize = size - sizeof(HeapObjectHeader);
+    Address payload = header->payload();
+    if (!header->isMarked()) {
+      // For ASan, unpoison the object before calling the finalizer. The
+      // finalized object will be zero-filled and poison'ed afterwards.
+      // Given all other unmarked objects are poisoned, ASan will detect
+      // an error if the finalizer touches any other on-heap object that
+      // die at the same GC cycle.
+      ASAN_UNPOISON_MEMORY_REGION(headerAddress, size);
+      header->finalize(payload, payloadSize);
+
+// As compaction is under way, leave the freed memory accessible
+// while compacting the rest of the page. We just zap the payload
+// to catch out other finalizers trying to access it.
+#if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER) || \

[haraken, 2016/12/06 13:30:39]

SET_MEMORY_INACCESSIBLE

[sof, 2016/12/06 21:39:35]

Not appropriate at this stage, see comment above (which 'git cl format' insists
on mis-indenting.)

+    defined(MEMORY_SANITIZER)
+      FreeList::zapFreedMemory(payload, payloadSize);
+#endif
+      headerAddress += size;
+      continue;
+    }
+    DCHECK(header->isMarked());

[haraken, 2016/12/06 13:30:39]

Remove. This is checked in unmark().

[sof, 2016/12/06 21:39:35]

Done.

+    header->unmark();
+    markedObjectSize += size;

[haraken, 2016/12/06 13:30:39]

I'd move this to line 1509.

[sof, 2016/12/06 21:39:35]

Moved.

+    // Allocate and copy over the live object.
+    if (arena->payload() + allocationPoint + size > arena->payloadEnd()) {
+      // Can't fit on current allocation page.
+      // TODO(sof): be more clever & compact later objects into |arena|'s unused
+      // slop.
+      BasePage* nextP;

[haraken, 2016/12/06 13:30:39]

nextP => nextAvailablePage

[sof, 2016/12/06 21:39:35]

alright..

+      arena->unlink(&nextP);
+      arena->link(firstPage);
+      size_t freeSize = arena->payloadSize() - allocationPoint;
+      if (freeSize) {
+#if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER) || \
+    defined(MEMORY_SANITIZER)

[haraken, 2016/12/06 13:30:39]

This #if wouldn't be needed -- it's covered by SET_MEMORY_INACCESSIBLE.

[sof, 2016/12/06 21:39:34]

Done.

+        SET_MEMORY_INACCESSIBLE(arena->payload() + allocationPoint, freeSize);
+#endif
+        arena->arenaForNormalPage()->addToFreeList(

[haraken, 2016/12/06 13:30:39]

'arena->arenaForNormalPage()->' would not be needed.

[sof, 2016/12/06 21:39:35]

It's preferable not to subtly build in the assumption that the pages here belong
to the same arena.

+            arena->payload() + allocationPoint, freeSize);
+      }
+      arena = static_cast<NormalPage*>(nextP);
+      allocationPoint = 0;
+    }
+    Address movedObject = arena->payload() + allocationPoint;
+    if (LIKELY(movedObject != headerAddress)) {

[haraken, 2016/12/06 13:30:39]

Just to confirm: movedObject == headerAddress can happen only at the very
beginning of the compaction phase (before hitting the first fragmented object),
right?

[sof, 2016/12/06 21:39:35]

Yes, pretty much -- it could conceivably also happen on pages later than the
first one, if the first allocation on those wouldn't fit the current |arena|. If
the first page evolves to contain old & stable allocations, that is a
possibility.

+#if defined(ADDRESS_SANITIZER)
+      // Unpoison the header + if it is a vector backing
+      // store object, let go of the container annotations.
+      // Do that by unpoisoning the payload entirely.

[haraken, 2016/12/06 13:30:39]

Would you help me understand why you need the unpoisoning?

If it's really needed, we need to poison it again after moving the object.

[sof, 2016/12/06 21:39:35]

The above comment explains this already.

+      ASAN_UNPOISON_MEMORY_REGION(header, sizeof(HeapObjectHeader));
+      if (ThreadState::isVectorArenaIndex(
+              arena->arenaForNormalPage()->arenaIndex())) {

[haraken, 2016/12/06 13:30:39]

At least, you can move the arenaIndex check outside the sweeping loop.

[sof, 2016/12/06 21:39:35]

Done; a bug to consult |arena| here, btw.

+        ASAN_UNPOISON_MEMORY_REGION(payload, payloadSize);
+      }
+#endif
+      // Use a non-overlapping copy, if possible.
+      if (arena == this)
+        memmove(movedObject, headerAddress, size);
+      else
+        memcpy(movedObject, headerAddress, size);
+      compact->relocate(payload, movedObject + sizeof(HeapObjectHeader));
+    }
+    headerAddress += size;
+    allocationPoint += size;
+    DCHECK(allocationPoint <= arena->payloadSize());
+  }
+  if (markedObjectSize)
+    pageArena->getThreadState()->increaseMarkedObjectSize(markedObjectSize);
+
+  // Clear the page; it'll either be used for compacted objects or freed.
+  if (arena != this)

[haraken, 2016/12/06 13:30:39]

Shouldn't this be equal to 'if (allocationPoint == 0)'? If that is the case,
this branch won't be needed.

[sof, 2016/12/06 21:39:35]

If the compacted page overlaps with where the compaction pointer currently
resides, we only clear the remainder. If it doesn't, we clear it all.

The logic here is correct and the natural one, afaict.

+    memset(payload(), 0, payloadSize());
+  else
+    memset(payload() + allocationPoint, 0, payloadSize() - allocationPoint);

[haraken, 2016/12/06 13:30:39]

Just in case, I'd prefer zapping the memory. And check that we're moving object
to the zapped memory at line 1506.

[sof, 2016/12/06 21:39:35]

Now zapped/memset(), as appropriate.

+  return allocationPoint;
+}
+
 void NormalPage::makeConsistentForGC() {
   size_t markedObjectSize = 0;
   for (Address headerAddress = payload(); headerAddress < payloadEnd();) {