heap/MarkStack.cpp

   1 /*
   2  * Copyright (C) 2009, 2011 Apple Inc. All rights reserved.
   3  *
   4  * Redistribution and use in source and binary forms, with or without
   5  * modification, are permitted provided that the following conditions
   6  * are met:
   7  * 1. Redistributions of source code must retain the above copyright
   8  *    notice, this list of conditions and the following disclaimer.
   9  * 2. Redistributions in binary form must reproduce the above copyright
  10  *    notice, this list of conditions and the following disclaimer in the
  11  *    documentation and/or other materials provided with the distribution.
  12  *
  13  * THIS SOFTWARE IS PROVIDED BY APPLE INC. ``AS IS'' AND ANY
  14  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  15  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
  16  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
  17  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
  18  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
  19  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
  20  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
  21  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  22  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  23  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  24  */
  25
  26 #include "config.h"
  27 #include "MarkStack.h"
  28 #include "MarkStackInlines.h"
  29
  30 #include "ConservativeRoots.h"
  31 #include "CopiedSpace.h"
  32 #include "CopiedSpaceInlines.h"
  33 #include "Heap.h"
  34 #include "JSArray.h"
  35 #include "JSCell.h"
  36 #include "JSObject.h"
  37
  38 #include "SlotVisitorInlines.h"
  39 #include "Structure.h"
  40 #include "WriteBarrier.h"
  41 #include <wtf/Atomics.h>
  42 #include <wtf/DataLog.h>
  43 #include <wtf/MainThread.h>
  44
  45 namespace JSC {
  46
  47 COMPILE_ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize, blockSizeMatch);
  48
  49 MarkStackArray::MarkStackArray(BlockAllocator& blockAllocator)
  50     : m_blockAllocator(blockAllocator)
  51     , m_top(0)
  52     , m_numberOfSegments(0)
  53 {
  54     m_segments.push(MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>()));
  55     m_numberOfSegments++;
  56 }
  57
  58 MarkStackArray::~MarkStackArray()
  59 {
  60     ASSERT(m_numberOfSegments == 1 && m_segments.size() == 1);
  61     m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));
  62 }
  63
  64 void MarkStackArray::expand()
  65 {
  66     ASSERT(m_segments.head()->m_top == s_segmentCapacity);
  67
  68     MarkStackSegment* nextSegment = MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>());
  69     m_numberOfSegments++;
  70
  71 #if !ASSERT_DISABLED
  72     nextSegment->m_top = 0;
  73 #endif
  74
  75     m_segments.push(nextSegment);
  76     setTopForEmptySegment();
  77     validatePrevious();
  78 }
  79
  80 bool MarkStackArray::refill()
  81 {
  82     validatePrevious();
  83     if (top())
  84         return true;
  85     m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));
  86     ASSERT(m_numberOfSegments > 1);
  87     m_numberOfSegments--;
  88     setTopForFullSegment();
  89     validatePrevious();
  90     return true;
  91 }
  92
  93 void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
  94 {
  95     // Try to donate about 1 / 2 of our cells. To reduce copying costs,
  96     // we prefer donating whole segments over donating individual cells,
  97     // even if this skews away from our 1 / 2 target.
  98
  99     size_t segmentsToDonate = m_numberOfSegments / 2; // If we only have one segment (our head) we don't donate any segments.
 100
 101     if (!segmentsToDonate) {
 102         size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
 103         while (cellsToDonate--) {
 104             ASSERT(m_top);
 105             other.append(removeLast());
 106         }
 107         return;
 108     }
 109
 110     validatePrevious();
 111     other.validatePrevious();
 112
 113     // Remove our head and the head of the other list before we start moving segments around.
 114     // We'll add them back on once we're done donating.
 115     MarkStackSegment* myHead = m_segments.removeHead();
 116     MarkStackSegment* otherHead = other.m_segments.removeHead();
 117
 118     while (segmentsToDonate--) {
 119         MarkStackSegment* current = m_segments.removeHead();
 120         ASSERT(current);
 121         ASSERT(m_numberOfSegments > 1);
 122         other.m_segments.push(current);
 123         m_numberOfSegments--;
 124         other.m_numberOfSegments++;
 125     }
 126
 127     // Put the original heads back in their places.
 128     m_segments.push(myHead);
 129     other.m_segments.push(otherHead);
 130
 131     validatePrevious();
 132     other.validatePrevious();
 133 }
 134
 135 void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
 136 {
 137     // Try to steal 1 / Nth of the shared array, where N is the number of idle threads.
 138     // To reduce copying costs, we prefer stealing a whole segment over stealing
 139     // individual cells, even if this skews away from our 1 / N target.
 140
 141     validatePrevious();
 142     other.validatePrevious();
 143
 144     // If other has an entire segment, steal it and return.
 145     if (other.m_numberOfSegments > 1) {
 146         // Move the heads of the lists aside. We'll push them back on after.
 147         MarkStackSegment* otherHead = other.m_segments.removeHead();
 148         MarkStackSegment* myHead = m_segments.removeHead();
 149
 150         ASSERT(other.m_segments.head()->m_top == s_segmentCapacity);
 151
 152         m_segments.push(other.m_segments.removeHead());
 153
 154         m_numberOfSegments++;
 155         other.m_numberOfSegments--;
 156
 157         m_segments.push(myHead);
 158         other.m_segments.push(otherHead);
 159
 160         validatePrevious();
 161         other.validatePrevious();
 162         return;
 163     }
 164
 165     size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount; // Round up to steal 1 / 1.
 166     while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
 167         append(other.removeLast());
 168 }
 169
 170 } // namespace JSC