1/*
2 * Copyright (C) 2016-2018 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. AND ITS CONTRIBUTORS ``AS IS''
14 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
15 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
17 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
19 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
20 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
21 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
22 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
23 * THE POSSIBILITY OF SUCH DAMAGE.
24 */
25
26#pragma once
27
28namespace JSC {
29
30// Are you tired of waiting for all of WebKit to build because you changed the implementation of a
31// function in HeapInlines.h? Does it bother you that you're waiting on rebuilding the JS DOM
32// bindings even though your change is in a function called from only 2 .cpp files? Then HeapUtil.h
33// is for you! Everything in this class should be a static method that takes a Heap& if needed.
34// This is a friend of Heap, so you can access all of Heap's privates.
35//
36// This ends up being an issue because Heap exposes a lot of methods that ought to be inline for
37// performance or that must be inline because they are templates. This class ought to contain
38// methods that are used for the implementation of the collector, or for unusual clients that need
39// to reach deep into the collector for some reason. Don't put things in here that would cause you
40// to have to include it from more than a handful of places, since that would defeat the purpose.
41// This class isn't here to look pretty. It's to let us hack the GC more easily!
42
43class HeapUtil {
44public:
45 // This function must be run after stopAllocation() is called and
46 // before liveness data is cleared to be accurate.
47 template<typename Func>
48 static void findGCObjectPointersForMarking(
49 Heap& heap, HeapVersion markingVersion, HeapVersion newlyAllocatedVersion, TinyBloomFilter filter,
50 void* passedPointer, const Func& func)
51 {
52 const HashSet<MarkedBlock*>& set = heap.objectSpace().blocks().set();
53
54 ASSERT(heap.objectSpace().isMarking());
55 static const bool isMarking = true;
56
57 char* pointer = static_cast<char*>(passedPointer);
58
59 // It could point to a large allocation.
60 if (heap.objectSpace().largeAllocationsForThisCollectionSize()) {
61 if (heap.objectSpace().largeAllocationsForThisCollectionBegin()[0]->aboveLowerBound(pointer)
62 && heap.objectSpace().largeAllocationsForThisCollectionEnd()[-1]->belowUpperBound(pointer)) {
63 LargeAllocation** result = approximateBinarySearch<LargeAllocation*>(
64 heap.objectSpace().largeAllocationsForThisCollectionBegin(),
65 heap.objectSpace().largeAllocationsForThisCollectionSize(),
66 LargeAllocation::fromCell(pointer),
67 [] (LargeAllocation** ptr) -> LargeAllocation* { return *ptr; });
68 if (result) {
69 auto attemptLarge = [&] (LargeAllocation* allocation) {
70 if (allocation->contains(pointer))
71 func(allocation->cell(), allocation->attributes().cellKind);
72 };
73
74 if (result > heap.objectSpace().largeAllocationsForThisCollectionBegin())
75 attemptLarge(result[-1]);
76 attemptLarge(result[0]);
77 if (result + 1 < heap.objectSpace().largeAllocationsForThisCollectionEnd())
78 attemptLarge(result[1]);
79 }
80 }
81 }
82
83 MarkedBlock* candidate = MarkedBlock::blockFor(pointer);
84 // It's possible for a butterfly pointer to point past the end of a butterfly. Check this now.
85 if (pointer <= bitwise_cast<char*>(candidate) + sizeof(IndexingHeader)) {
86 // We may be interested in the last cell of the previous MarkedBlock.
87 char* previousPointer = bitwise_cast<char*>(bitwise_cast<uintptr_t>(pointer) - sizeof(IndexingHeader) - 1);
88 MarkedBlock* previousCandidate = MarkedBlock::blockFor(previousPointer);
89 if (!filter.ruleOut(bitwise_cast<Bits>(previousCandidate))
90 && set.contains(previousCandidate)
91 && hasInteriorPointers(previousCandidate->handle().cellKind())) {
92 previousPointer = static_cast<char*>(previousCandidate->handle().cellAlign(previousPointer));
93 if (previousCandidate->handle().isLiveCell(markingVersion, newlyAllocatedVersion, isMarking, previousPointer))
94 func(previousPointer, previousCandidate->handle().cellKind());
95 }
96 }
97
98 if (filter.ruleOut(bitwise_cast<Bits>(candidate))) {
99 ASSERT(!candidate || !set.contains(candidate));
100 return;
101 }
102
103 if (!set.contains(candidate))
104 return;
105
106 HeapCell::Kind cellKind = candidate->handle().cellKind();
107
108 auto tryPointer = [&] (void* pointer) {
109 if (candidate->handle().isLiveCell(markingVersion, newlyAllocatedVersion, isMarking, pointer))
110 func(pointer, cellKind);
111 };
112
113 if (isJSCellKind(cellKind)) {
114 if (MarkedBlock::isAtomAligned(pointer))
115 tryPointer(pointer);
116 if (!hasInteriorPointers(cellKind))
117 return;
118 }
119
120 // A butterfly could point into the middle of an object.
121 char* alignedPointer = static_cast<char*>(candidate->handle().cellAlign(pointer));
122 tryPointer(alignedPointer);
123
124 // Also, a butterfly could point at the end of an object plus sizeof(IndexingHeader). In that
125 // case, this is pointing to the object to the right of the one we should be marking.
126 if (candidate->atomNumber(alignedPointer) > 0
127 && pointer <= alignedPointer + sizeof(IndexingHeader))
128 tryPointer(alignedPointer - candidate->cellSize());
129 }
130
131 static bool isPointerGCObjectJSCell(
132 Heap& heap, TinyBloomFilter filter, const void* pointer)
133 {
134 // It could point to a large allocation.
135 const Vector<LargeAllocation*>& largeAllocations = heap.objectSpace().largeAllocations();
136 if (!largeAllocations.isEmpty()) {
137 if (largeAllocations[0]->aboveLowerBound(pointer)
138 && largeAllocations.last()->belowUpperBound(pointer)) {
139 LargeAllocation*const* result = approximateBinarySearch<LargeAllocation*const>(
140 largeAllocations.begin(), largeAllocations.size(),
141 LargeAllocation::fromCell(pointer),
142 [] (LargeAllocation*const* ptr) -> LargeAllocation* { return *ptr; });
143 if (result) {
144 if (result > largeAllocations.begin()
145 && result[-1]->cell() == pointer
146 && isJSCellKind(result[-1]->attributes().cellKind))
147 return true;
148 if (result[0]->cell() == pointer
149 && isJSCellKind(result[0]->attributes().cellKind))
150 return true;
151 if (result + 1 < largeAllocations.end()
152 && result[1]->cell() == pointer
153 && isJSCellKind(result[1]->attributes().cellKind))
154 return true;
155 }
156 }
157 }
158
159 const HashSet<MarkedBlock*>& set = heap.objectSpace().blocks().set();
160
161 MarkedBlock* candidate = MarkedBlock::blockFor(pointer);
162 if (filter.ruleOut(bitwise_cast<Bits>(candidate))) {
163 ASSERT(!candidate || !set.contains(candidate));
164 return false;
165 }
166
167 if (!MarkedBlock::isAtomAligned(pointer))
168 return false;
169
170 if (!set.contains(candidate))
171 return false;
172
173 if (candidate->handle().cellKind() != HeapCell::JSCell)
174 return false;
175
176 if (!candidate->handle().isLiveCell(pointer))
177 return false;
178
179 return true;
180 }
181
182 static bool isValueGCObject(
183 Heap& heap, TinyBloomFilter filter, JSValue value)
184 {
185 if (!value.isCell())
186 return false;
187 return isPointerGCObjectJSCell(heap, filter, static_cast<void*>(value.asCell()));
188 }
189};
190
191} // namespace JSC
192
193