755a0ad50033c4d9c776e8ed7810c3e43620134a
[WebKit-https.git] / Source / JavaScriptCore / 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 "Options.h"
35 #include "JSArray.h"
36 #include "JSCell.h"
37 #include "JSObject.h"
38
39 #include "SlotVisitorInlines.h"
40 #include "Structure.h"
41 #include "WriteBarrier.h"
42 #include <wtf/Atomics.h>
43 #include <wtf/DataLog.h>
44 #include <wtf/MainThread.h>
45
46 namespace JSC {
47
48 MarkStackArray::MarkStackArray(BlockAllocator& blockAllocator)
49     : m_blockAllocator(blockAllocator)
50     , m_segmentCapacity(MarkStackSegment::capacityFromSize(Options::gcMarkStackSegmentSize()))
51     , m_top(0)
52     , m_numberOfSegments(0)
53 {
54     ASSERT(MarkStackSegment::blockSize == WeakBlock::blockSize);
55     m_segments.push(MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>()));
56     m_numberOfSegments++;
57 }
58
59 MarkStackArray::~MarkStackArray()
60 {
61     ASSERT(m_numberOfSegments == 1 && m_segments.size() == 1);
62     m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));
63 }
64
65 void MarkStackArray::expand()
66 {
67     ASSERT(m_segments.head()->m_top == m_segmentCapacity);
68     
69     MarkStackSegment* nextSegment = MarkStackSegment::create(m_blockAllocator.allocate<MarkStackSegment>());
70     m_numberOfSegments++;
71     
72 #if !ASSERT_DISABLED
73     nextSegment->m_top = 0;
74 #endif
75
76     m_segments.push(nextSegment);
77     setTopForEmptySegment();
78     validatePrevious();
79 }
80
81 bool MarkStackArray::refill()
82 {
83     validatePrevious();
84     if (top())
85         return true;
86     m_blockAllocator.deallocate(MarkStackSegment::destroy(m_segments.removeHead()));
87     ASSERT(m_numberOfSegments > 1);
88     m_numberOfSegments--;
89     setTopForFullSegment();
90     validatePrevious();
91     return true;
92 }
93
94 void MarkStackArray::donateSomeCellsTo(MarkStackArray& other)
95 {
96     // Try to donate about 1 / 2 of our cells. To reduce copying costs,
97     // we prefer donating whole segments over donating individual cells,
98     // even if this skews away from our 1 / 2 target.
99
100     ASSERT(m_segmentCapacity == other.m_segmentCapacity);
101
102     size_t segmentsToDonate = m_numberOfSegments / 2; // If we only have one segment (our head) we don't donate any segments.
103
104     if (!segmentsToDonate) {
105         size_t cellsToDonate = m_top / 2; // Round down to donate 0 / 1 cells.
106         while (cellsToDonate--) {
107             ASSERT(m_top);
108             other.append(removeLast());
109         }
110         return;
111     }
112
113     validatePrevious();
114     other.validatePrevious();
115
116     // Remove our head and the head of the other list before we start moving segments around.
117     // We'll add them back on once we're done donating.
118     MarkStackSegment* myHead = m_segments.removeHead();
119     MarkStackSegment* otherHead = other.m_segments.removeHead();
120
121     while (segmentsToDonate--) {
122         MarkStackSegment* current = m_segments.removeHead();
123         ASSERT(current);
124         ASSERT(m_numberOfSegments > 1);
125         other.m_segments.push(current);
126         m_numberOfSegments--;
127         other.m_numberOfSegments++;
128     }
129
130     // Put the original heads back in their places.
131     m_segments.push(myHead);
132     other.m_segments.push(otherHead);
133
134     validatePrevious();
135     other.validatePrevious();
136 }
137
138 void MarkStackArray::stealSomeCellsFrom(MarkStackArray& other, size_t idleThreadCount)
139 {
140     // Try to steal 1 / Nth of the shared array, where N is the number of idle threads.
141     // To reduce copying costs, we prefer stealing a whole segment over stealing
142     // individual cells, even if this skews away from our 1 / N target.
143
144     ASSERT(m_segmentCapacity == other.m_segmentCapacity);
145     validatePrevious();
146     other.validatePrevious();
147         
148     // If other has an entire segment, steal it and return.
149     if (other.m_numberOfSegments > 1) {
150         // Move the heads of the lists aside. We'll push them back on after.
151         MarkStackSegment* otherHead = other.m_segments.removeHead();
152         MarkStackSegment* myHead = m_segments.removeHead();
153
154         ASSERT(other.m_segments.head()->m_top == m_segmentCapacity);
155
156         m_segments.push(other.m_segments.removeHead());
157
158         m_numberOfSegments++;
159         other.m_numberOfSegments--;
160         
161         m_segments.push(myHead);
162         other.m_segments.push(otherHead);
163     
164         validatePrevious();
165         other.validatePrevious();
166         return;
167     }
168
169     size_t numberOfCellsToSteal = (other.size() + idleThreadCount - 1) / idleThreadCount; // Round up to steal 1 / 1.
170     while (numberOfCellsToSteal-- > 0 && other.canRemoveLast())
171         append(other.removeLast());
172 }
173
174 } // namespace JSC