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 45namespace JSC { 46 47COMPILE_ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize, blockSizeMatch); 48 49MarkStackArray::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 58MarkStackArray::~MarkStackArray() 59{ 60 ASSERT(m_numberOfSegments == 1 && m_segments.size() == 1); 61 m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead())); 62} 63 64void 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 80bool 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 93void 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 135void 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 171