Changeset 122677 in webkit for trunk/Source/JavaScriptCore/heap/CopiedSpace.cpp

Timestamp:

Jul 14, 2012, 9:02:16 PM (13 years ago)

Author:

[email protected]

Message:

Rationalize and optimize storage allocation
​https://bugs.webkit.org/show_bug.cgi?id=91303

Reviewed by Oliver Hunt.

This implements a backwards bump allocator for copied space storage
allocation, shown in pseudo-code below:

pointer bump(size) {

pointer tmp = allocator->remaining;
tmp -= size;
if (tmp < 0)

fail;

allocator->remaining = tmp;
return allocator->payloadEnd - tmp - size;

}

The advantage of this allocator is that it:

• Only requires one comparison in the common case where size is known to not be huge, and this comparison can be done by checking the sign bit of the subtraction.

• Can be implemented even when only one register is available. This register is reused for both temporary storage during allocation and for the result.

• Preserves the behavior that memory in a block is filled in from lowest address to highest address, which allows for a cheap reallocation fast path.

• Is resilient against the block used for allocation being the last one in virtual memory, thereby otherwise leading to the risk of overflow in the bump pointer, despite only doing one branch.

In order to implement this allocator using the smallest possible chunk
of code, I refactored the copied space code so that all of the allocation
logic is in CopiedAllocator, and all of the state is in either
CopiedBlock or CopiedAllocator. This should make changing the allocation
fast path easier in the future.

In order to do this, I needed to add some new assembler support,
particularly for various forms of add(address, register) and negPtr().

This is performance neutral. The purpose of this change is to facilitate
further inlining of storage allocation without having to reserve
additional registers or emit too much code.

• assembler/MacroAssembler.h:

(JSC::MacroAssembler::addPtr):
(MacroAssembler):
(JSC::MacroAssembler::negPtr):

• assembler/MacroAssemblerARMv7.h:

(MacroAssemblerARMv7):
(JSC::MacroAssemblerARMv7::add32):

• assembler/MacroAssemblerX86.h:

(JSC::MacroAssemblerX86::add32):
(MacroAssemblerX86):

• assembler/MacroAssemblerX86_64.h:

(MacroAssemblerX86_64):
(JSC::MacroAssemblerX86_64::addPtr):
(JSC::MacroAssemblerX86_64::negPtr):

• assembler/X86Assembler.h:

(X86Assembler):
(JSC::X86Assembler::addl_mr):
(JSC::X86Assembler::addq_mr):
(JSC::X86Assembler::negq_r):

• heap/CopiedAllocator.h:

(CopiedAllocator):
(JSC::CopiedAllocator::isValid):
(JSC::CopiedAllocator::CopiedAllocator):
(JSC::CopiedAllocator::tryAllocate):
(JSC):
(JSC::CopiedAllocator::tryReallocate):
(JSC::CopiedAllocator::forceAllocate):
(JSC::CopiedAllocator::resetCurrentBlock):
(JSC::CopiedAllocator::setCurrentBlock):
(JSC::CopiedAllocator::currentCapacity):

• heap/CopiedBlock.h:

(CopiedBlock):
(JSC::CopiedBlock::create):
(JSC::CopiedBlock::zeroFillWilderness):
(JSC::CopiedBlock::CopiedBlock):
(JSC::CopiedBlock::payloadEnd):
(JSC):
(JSC::CopiedBlock::payloadCapacity):
(JSC::CopiedBlock::data):
(JSC::CopiedBlock::dataEnd):
(JSC::CopiedBlock::dataSize):
(JSC::CopiedBlock::wilderness):
(JSC::CopiedBlock::wildernessEnd):
(JSC::CopiedBlock::wildernessSize):
(JSC::CopiedBlock::size):

• heap/CopiedSpace.cpp:

(JSC::CopiedSpace::tryAllocateSlowCase):
(JSC::CopiedSpace::tryAllocateOversize):
(JSC::CopiedSpace::tryReallocate):
(JSC::CopiedSpace::doneFillingBlock):
(JSC::CopiedSpace::doneCopying):

• heap/CopiedSpace.h:

(CopiedSpace):

• heap/CopiedSpaceInlineMethods.h:

(JSC::CopiedSpace::startedCopying):
(JSC::CopiedSpace::allocateBlockForCopyingPhase):
(JSC::CopiedSpace::allocateBlock):
(JSC::CopiedSpace::tryAllocate):
(JSC):

• heap/MarkStack.cpp:

(JSC::SlotVisitor::startCopying):
(JSC::SlotVisitor::allocateNewSpace):
(JSC::SlotVisitor::doneCopying):

• heap/SlotVisitor.h:

(JSC::SlotVisitor::SlotVisitor):

• jit/JIT.h:
• jit/JITInlineMethods.h:

(JSC::JIT::emitAllocateBasicStorage):
(JSC::JIT::emitAllocateJSArray):

File:

• trunk/Source/JavaScriptCore/heap/CopiedSpace.cpp (modified) (5 diffs)

trunk/Source/JavaScriptCore/heap/CopiedSpace.cpp

@@ -72 +72 @@
     allocateBlock();
 
-    *outPtr = m_allocator.allocate(bytes);
-    ASSERT(*outPtr);
+    *outPtr = m_allocator.forceAllocate(bytes);
     return true;
 }
@@ -94 +93 @@
     m_blockSet.add(block);
     
-    *outPtr = allocateFromBlock(block, bytes);
+    CopiedAllocator allocator;
+    allocator.setCurrentBlock(block);
+    *outPtr = allocator.forceAllocate(bytes);
+    allocator.resetCurrentBlock();
 
     m_heap->didAllocate(blockSize);
@@ -108 +110 @@
     void* oldPtr = *ptr;
     ASSERT(!m_heap->globalData()->isInitializingObject());
-
+    
     if (isOversize(oldSize) || isOversize(newSize))
         return tryReallocateOversize(ptr, oldSize, newSize);
-
-    if (m_allocator.wasLastAllocation(oldPtr, oldSize)) {
-        size_t delta = newSize - oldSize;
-        if (m_allocator.fitsInCurrentBlock(delta)) {
-            (void)m_allocator.allocate(delta);
-            return true;
-        }
-    }
+    
+    if (m_allocator.tryReallocate(oldPtr, oldSize, newSize))
+        return true;
 
     void* result = 0;
@@ -158 +155 @@
 void CopiedSpace::doneFillingBlock(CopiedBlock* block)
 {
-    ASSERT(block);
-    ASSERT(block->m_offset < reinterpret_cast<char*>(block) + HeapBlock::s_blockSize);
     ASSERT(m_inCopyingPhase);
-
-    if (block->m_offset == block->payload()) {
+    
+    if (!block)
+        return;
+
+    if (!block->dataSize()) {
         recycleBlock(block);
         return;
     }
 
-    block->zeroFillToEnd();
+    block->zeroFillWilderness();
 
     {
@@ -227 +225 @@
         allocateBlock();
     else
-        m_allocator.resetCurrentBlock(static_cast<CopiedBlock*>(m_toSpace->head()));
+        m_allocator.setCurrentBlock(static_cast<CopiedBlock*>(m_toSpace->head()));
 }