871b30180c65b66d1955dcb2c3aca6c33b8af407
[WebKit-https.git] / Source / JavaScriptCore / heap / MarkStack.cpp
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
32 namespace JSC {
33
34 MarkStackArray::MarkStackArray()
35     : GCSegmentedArray<const JSCell*>()
36 {
37 }
38
39 void 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
67 size_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
81 void 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
123 void 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