Simple BlinkGC heap compaction.

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

 /*
  * Copyright (C) 2013 Google Inc. All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions are
  * met:
  *
  *     * Redistributions of source code must retain the above copyright
  * notice, this list of conditions and the following disclaimer.
  *     * Redistributions in binary form must reproduce the above
@@ skipping 17 matching lines @@
  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */
 
 #include "platform/heap/HeapPage.h"
 
 #include "base/trace_event/process_memory_dump.h"
 #include "platform/MemoryCoordinator.h"
 #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"
 #include "platform/heap/SafePoint.h"
 #include "platform/heap/ThreadState.h"
 #include "platform/tracing/TraceEvent.h"
 #include "platform/tracing/web_memory_allocator_dump.h"
 #include "platform/tracing/web_process_memory_dump.h"
 #include "public/platform/Platform.h"
 #include "wtf/Assertions.h"
@@ skipping 146 matching lines @@
     ASSERT(!page->hasBeenSwept());
     page->invalidateObjectStartBitmap();
   }
   if (previousPage) {
     ASSERT(m_firstUnsweptPage);
     previousPage->m_next = m_firstPage;
     m_firstPage = m_firstUnsweptPage;
     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() {
   clearFreeLists();
   ASSERT(isConsistentForGC());
   ASSERT(!m_firstPage);
 
   // Drop marks from marked objects and rebuild free lists in preparation for
   // resuming the executions of mutators.
   BasePage* previousPage = nullptr;
@@ skipping 219 matching lines @@
       m_promptlyFreedSize(0),
       m_isLazySweeping(false) {
   clearFreeLists();
 }
 
 void NormalPageArena::clearFreeLists() {
   setAllocationPoint(nullptr, 0);
   m_freeList.clear();
 }
 
+size_t NormalPageArena::arenaSize() {
+  size_t size = 0;
+  BasePage* p = m_firstPage;

[haraken, 2016/12/05 11:27:47]

page

[sof, 2016/12/05 19:30:06]

Done.

+  while (p) {
+    size += p->size();
+    p = p->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;
+

[haraken, 2016/12/05 11:27:47]

Add DCHECK(!hasCurrentAllocationArea()).

[sof, 2016/12/05 19:30:07]

Done.

+  NormalPage* nextPage = nullptr;
+  size_t allocationPoint = 0;
+
+  while (m_firstUnsweptPage) {
+    BasePage* page = m_firstUnsweptPage;
+    if (page->isEmpty()) {
+      page->unlink(&m_firstUnsweptPage);
+      page->removeFromHeap();
+      continue;
+    }
+    if (page->isLargeObjectPage()) {
+      page->sweep();
+      page->markAsSwept();
+      continue;

[haraken, 2016/12/05 11:27:47]

Don't we need to call:

  page->unlink(&m_firstUnsweptPage);
  page->link(&m_firstPage);

?

[sof, 2016/12/05 19:30:07]

Good catch; the large object case is dead code, however. Added a DCHECK()
instead.

+    }
+    NormalPage* normalPage = static_cast<NormalPage*>(page);
+    normalPage->unlink(&m_firstUnsweptPage);
+    normalPage->markAsSwept();
+    if (!nextPage) {
+      nextPage = normalPage;
+    } else {
+      // Add |normalPage| onto the |nextPage| chain, but after it as |nextPage|
+      // is the current page being allocated from.
+      BasePage* nextP;
+      nextPage->unlink(&nextP);
+      normalPage->link(&nextP);
+      nextPage->link(&nextP);
+    }
+    allocationPoint =
+        normalPage->sweepAndCompact(nextPage, &m_firstPage, allocationPoint);

[haraken, 2016/12/05 11:27:47]

Honestly speaking, it's very hard to understand what sweepAndCompact is doing...
For example, why do we need the |nextPage|'s chain? I guess |allocationPoint| is
enough to keep track of where we're allocating. If we want to allocate from the
next page, we just need to find the next page in the |m_firstPage|'s chain
(i.e., pageFromAddress(allocationPoint)->nextPage())?

If the performance permits, we might want to consider doing the heap compaction
in two paths. In the first path, we just sweep the pages using existing code. In
the second path, we scan the chain of m_firstPage and compact the pages.

The other thing we might want to consider is if we really need to compact
objects over pages (which is making things a lot complicated). Maybe would it be
enough to compact objects inside one page and decommit unused system pages in
the page? Given that the mutator will anyway allocate new objects after the heap
compaction, we won't necessarily need to compact perfectly.

Maybe a better idea is:

1) In the first path, just sweep the objects. But while sweeping, measure how
much each page is fragmented.

2) In the second path, compact only pages that are fragmented a lot.

(In any case, my point is not that I want to make the compaction smarter but
that I want to simplify the compaction logic.)

[sof, 2016/12/05 19:30:07]

We do want to perform in-place compaction of these pages, which is what it
accomplishes. Let me try to add some comments and elucidate the code some.

[sof, 2016/12/06 10:55:59]

Done; refreshed the code + added comments.

+  }
+  // Add unused tail to the free list.
+  BasePage* nextP = nullptr;
+  if (nextPage) {
+    // If the 'next page' is used, add it to the heap's list of swept pages.
+    // Otherwise we hand it back to the OS below.
+    if (allocationPoint) {
+      nextPage->unlink(&nextP);
+      nextPage->link(&m_firstPage);
+    } else {
+      nextP = nextPage;
+      nextPage = nullptr;
+    }
+  }
+  size_t freedSize = 0;
+  if (nextPage && allocationPoint != nextPage->payloadSize()) {
+    freedSize = nextPage->payloadSize() - allocationPoint;
+#if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER) || \
+    defined(MEMORY_SANITIZER)
+    FreeList::zapFreedMemory(nextPage->payload() + allocationPoint, freedSize);
+#endif
+    nextPage->arenaForNormalPage()->addToFreeList(
+        nextPage->payload() + allocationPoint, freedSize);
+  }
+  nextPage = static_cast<NormalPage*>(nextP);
+  size_t freedPages = 0;
+  while (nextPage) {
+#if DEBUG_HEAP_COMPACTION
+    if (!freedPages)
+      LOG_HEAP_COMPACTION("Releasing:");
+    LOG_HEAP_COMPACTION(" [%p, %p]", nextPage, nextPage + nextPage->size());
+#endif
+    freedSize += nextPage->size();
+    freedPages++;
+    nextPage->unlink(&nextP);
+    nextPage->removeFromHeap();
+    nextPage = static_cast<NormalPage*>(nextP);
+  }
+  if (nextP)
+    LOG_HEAP_COMPACTION("\n");
+  heap.compaction()->finishedArenaCompaction(this, freedPages, freedSize);
+}
+
 #if ENABLE(ASSERT)
 bool NormalPageArena::isConsistentForGC() {
   // A thread heap is consistent for sweeping if none of the pages to be swept
   // contain a freelist block or the current allocation point.
   for (size_t i = 0; i < blinkPageSizeLog2; ++i) {
     for (FreeListEntry* freeListEntry = m_freeList.m_freeLists[i];
          freeListEntry; freeListEntry = freeListEntry->next()) {
       if (pagesToBeSweptContains(freeListEntry->getAddress()))
         return false;
     }
@@ skipping 21 matching lines @@
             ->createMemoryAllocatorDumpForCurrentGC(dumpName + "/buckets");
     base::trace_event::MemoryAllocatorDump* pagesDump =
         BlinkGCMemoryDumpProvider::instance()
             ->createMemoryAllocatorDumpForCurrentGC(dumpName + "/pages");
     BlinkGCMemoryDumpProvider::instance()
         ->currentProcessMemoryDump()
         ->AddOwnershipEdge(pagesDump->guid(), bucketsDump->guid());
   }
 }
 
-void NormalPageArena::allocatePage() {
+NormalPage* NormalPageArena::allocatePage() {
   getThreadState()->shouldFlushHeapDoesNotContainCache();
   PageMemory* pageMemory =
       getThreadState()->heap().getFreePagePool()->takeFreePage(arenaIndex());
 
   if (!pageMemory) {
     // Allocate a memory region for blinkPagesPerRegion pages that
     // will each have the following layout.
     //
     //    [ guard os page | ... payload ... | guard os page ]
     //    ^---{ aligned to blink page size }
@@ skipping 15 matching lines @@
         pageMemory = memory;
       } else {
         getThreadState()->heap().getFreePagePool()->addFreePage(arenaIndex(),
                                                                 memory);
       }
     }
   }
 
   NormalPage* page =
       new (pageMemory->writableStart()) NormalPage(pageMemory, this);
+  return page;

[haraken, 2016/12/05 11:27:47]

return new...

[sof, 2016/12/05 19:30:06]

Done.

+}
+
+void NormalPageArena::allocateAndAddPage() {
+  NormalPage* page = allocatePage();
   page->link(&m_firstPage);
 
   getThreadState()->heap().heapStats().increaseAllocatedSpace(page->size());
 #if ENABLE(ASSERT) || defined(LEAK_SANITIZER) || defined(ADDRESS_SANITIZER)
   // Allow the following addToFreeList() to add the newly allocated memory
   // to the free list.
   ASAN_UNPOISON_MEMORY_REGION(page->payload(), page->payloadSize());
   Address address = page->payload();
   for (size_t i = 0; i < page->payloadSize(); i++)
     address[i] = reuseAllowedZapValue;
@@ skipping 276 matching lines @@
       return result;
   }
 
   // 6. Complete sweeping.
   getThreadState()->completeSweep();
 
   // 7. Check if we should trigger a GC.
   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);
   RELEASE_ASSERT(result);
   return result;
 }
 
 Address NormalPageArena::allocateFromFreeList(size_t allocationSize,
                                               size_t gcInfoIndex) {
   // Try reusing a block from the largest bin. The underlying reasoning
@@ skipping 243 matching lines @@
 
 void NEVER_INLINE FreeList::checkFreedMemoryIsZapped(Address address,
                                                      size_t size) {
   for (size_t i = 0; i < size; i++) {
     ASSERT(address[i] == reuseAllowedZapValue ||
            address[i] == reuseForbiddenZapValue);
   }
 }
 #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)
     m_freeLists[i] = nullptr;
 }
 
 int FreeList::bucketIndexForSize(size_t size) {
   ASSERT(size > 0);
   int index = -1;
   while (size) {
@@ skipping 149 matching lines @@
 #if !ENABLE(ASSERT) && !defined(LEAK_SANITIZER) && !defined(ADDRESS_SANITIZER)
     if (MemoryCoordinator::isLowEndDevice())
       discardPages(startOfGap + sizeof(FreeListEntry), payloadEnd());
 #endif
   }
 
   if (markedObjectSize)
     pageArena->getThreadState()->increaseMarkedObjectSize(markedObjectSize);
 }
 
+size_t NormalPage::sweepAndCompact(NormalPage*& arena,
+                                   BasePage** firstPage,
+                                   size_t allocationPoint) {
+  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);
+      headerAddress += size;
+      continue;
+    }
+#if ENABLE(ASSERT)
+    DCHECK(header->checkHeader());
+#endif
+
+    if (!header->isMarked()) {
+      // This is a fast version of header->payloadSize().
+      size_t payloadSize = size - sizeof(HeapObjectHeader);
+      Address payload = header->payload();
+      // 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) || \
+    defined(MEMORY_SANITIZER)
+      FreeList::zapFreedMemory(payload, payloadSize);
+#endif
+      headerAddress += size;
+      continue;
+    }
+    DCHECK(header->isMarked());
+    header->unmark();
+    markedObjectSize += size;
+    // 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;
+      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)
+        SET_MEMORY_INACCESSIBLE(arena->payload() + allocationPoint, freeSize);
+#endif
+        arena->arenaForNormalPage()->addToFreeList(
+            arena->payload() + allocationPoint, freeSize);
+      }
+      arena = static_cast<NormalPage*>(nextP);
+      allocationPoint = 0;
+    }
+    Address movedObject = arena->payload() + allocationPoint;
+    if (LIKELY(movedObject != headerAddress)) {
+#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.
+      ASAN_UNPOISON_MEMORY_REGION(header, sizeof(HeapObjectHeader));
+      if (ThreadState::isVectorArenaIndex(
+              arena->arenaForNormalPage()->arenaIndex())) {
+        ASAN_UNPOISON_MEMORY_REGION(header->payload(),
+                                    size - sizeof(HeapObjectHeader));
+      }
+#endif
+      // Use a non-overlapping copy, if possible.
+      if (arena == this)
+        memmove(movedObject, headerAddress, size);
+      else
+        memcpy(movedObject, headerAddress, size);
+      compact->movedObject(header->payload(),

[haraken, 2016/12/05 11:27:47]

movedObject => relocate ?

[sof, 2016/12/05 19:30:07]

Alright.

+                           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)
+    memset(payload(), 0, payloadSize());
+  else
+    memset(payload() + allocationPoint, 0, payloadSize() - allocationPoint);
+  return allocationPoint;
+}
+
 void NormalPage::makeConsistentForGC() {
   size_t markedObjectSize = 0;
   for (Address headerAddress = payload(); headerAddress < payloadEnd();) {
     HeapObjectHeader* header =
         reinterpret_cast<HeapObjectHeader*>(headerAddress);
     ASSERT(header->size() < blinkPagePayloadSize());
     // Check if a free list entry first since we cannot call
     // isMarked on a free list entry.
     if (header->isFree()) {
       headerAddress += header->size();
@@ skipping 372 matching lines @@
 
   m_hasEntries = true;
   size_t index = hash(address);
   ASSERT(!(index & 1));
   Address cachePage = roundToBlinkPageStart(address);
   m_entries[index + 1] = m_entries[index];
   m_entries[index] = cachePage;
 }
 
 }  // namespace blink