1/*
2 * Copyright (C) 2009-2017 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
29#include "GCSegmentedArrayInlines.h"
30#include "JSCInlines.h"
31
32namespace JSC {
33
34MarkStackArray::MarkStackArray()
35 : GCSegmentedArray<const JSCell*>()
36{
37}
38
39void MarkStackArray::transferTo(MarkStackArray& other)
40{
41 RELEASE_ASSERT(this != &other);
42
43 // Remove our head and the head of the other list.
44 GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
45 GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
46 m_numberOfSegments--;
47 other.m_numberOfSegments--;
48
49 other.m_segments.append(m_segments);
50
51 other.m_numberOfSegments += m_numberOfSegments;
52 m_numberOfSegments = 0;
53
54 // Put the original heads back in their places.
55 m_segments.push(myHead);
56 other.m_segments.push(otherHead);
57 m_numberOfSegments++;
58 other.m_numberOfSegments++;
59
60 while (!isEmpty()) {
61 refill();
62 while (canRemoveLast())
63 other.append(removeLast());
64 }
65}
66
67size_t MarkStackArray::transferTo(MarkStackArray& other, size_t limit)
68{
69 size_t count = 0;
70 while (count < limit && !isEmpty()) {
71 refill();
72 while (count < limit && canRemoveLast()) {
73 other.append(removeLast());
74 count++;
75 }
76 }
77 RELEASE_ASSERT(count <= limit);
78 return count;
79}
80
81void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
82{
83 // Try to donate about 1 / 2 of our cells. To reduce copying costs,
84 // we prefer donating whole segments over donating individual cells,
85 // even if this skews away from our 1 / 2 target.
86
87 size_t segmentsToDonate = m_numberOfSegments / 2; // If we only have one segment (our head) we don't donate any segments.
88
89 if (!segmentsToDonate) {
90 size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
91 while (cellsToDonate--) {
92 ASSERT(m_top);
93 other.append(removeLast());
94 }
95 return;
96 }
97
98 validatePrevious();
99 other.validatePrevious();
100
101 // Remove our head and the head of the other list before we start moving segments around.
102 // We'll add them back on once we're done donating.
103 GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
104 GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
105
106 while (segmentsToDonate--) {
107 GCArraySegment<const JSCell*>* current = m_segments.removeHead();
108 ASSERT(current);
109 ASSERT(m_numberOfSegments > 1);
110 other.m_segments.push(current);
111 m_numberOfSegments--;
112 other.m_numberOfSegments++;
113 }
114
115 // Put the original heads back in their places.
116 m_segments.push(myHead);
117 other.m_segments.push(otherHead);
118
119 validatePrevious();
120 other.validatePrevious();
121}
122
123void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
124{
125 // Try to steal 1 / Nth of the shared array, where N is the number of idle threads.
126 // To reduce copying costs, we prefer stealing a whole segment over stealing
127 // individual cells, even if this skews away from our 1 / N target.
128
129 validatePrevious();
130 other.validatePrevious();
131
132 // If other has an entire segment, steal it and return.
133 if (other.m_numberOfSegments > 1) {
134 // Move the heads of the lists aside. We'll push them back on after.
135 GCArraySegment<const JSCell*>* otherHead = other.m_segments.removeHead();
136 GCArraySegment<const JSCell*>* myHead = m_segments.removeHead();
137
138 ASSERT(other.m_segments.head()->m_top == s_segmentCapacity);
139
140 m_segments.push(other.m_segments.removeHead());
141
142 m_numberOfSegments++;
143 other.m_numberOfSegments--;
144
145 m_segments.push(myHead);
146 other.m_segments.push(otherHead);
147
148 validatePrevious();
149 other.validatePrevious();
150 return;
151 }
152
153 // Steal ceil(other.size() / idleThreadCount) things.
154 size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount;
155 while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
156 append(other.removeLast());
157}
158
159} // namespace JSC
160