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