1/*
2 * Copyright (C) 2016-2019 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 constexpr bool isMarking = true;
56
57 char* pointer = static_cast<char*>(passedPointer);
58
59 // It could point to a large allocation.
60 if (heap.objectSpace().preciseAllocationsForThisCollectionSize()) {
61 if (heap.objectSpace().preciseAllocationsForThisCollectionBegin()[0]->aboveLowerBound(pointer)
62 && heap.objectSpace().preciseAllocationsForThisCollectionEnd()[-1]->belowUpperBound(pointer)) {
63 PreciseAllocation** result = approximateBinarySearch<PreciseAllocation*>(
64 heap.objectSpace().preciseAllocationsForThisCollectionBegin(),
65 heap.objectSpace().preciseAllocationsForThisCollectionSize(),
66 PreciseAllocation::fromCell(pointer),
67 [] (PreciseAllocation** ptr) -> PreciseAllocation* { return *ptr; });
68 if (result) {
69 auto attemptLarge = [&] (PreciseAllocation* allocation) {
70 if (allocation->contains(pointer) && allocation->hasValidCell())
71 func(allocation->cell(), allocation->attributes().cellKind);
72 };
73
74 if (result > heap.objectSpace().preciseAllocationsForThisCollectionBegin())
75 attemptLarge(result[-1]);
76 attemptLarge(result[0]);
77 if (result + 1 < heap.objectSpace().preciseAllocationsForThisCollectionEnd())
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(Heap& heap, TinyBloomFilter filter, JSCell* pointer)
132 {
133 // It could point to a large allocation.
134 if (pointer->isPreciseAllocation()) {
135 auto* set = heap.objectSpace().preciseAllocationSet();
136 ASSERT(set);
137 if (set->isEmpty())
138 return false;
139 return set->contains(pointer);
140 }
141
142 const HashSet<MarkedBlock*>& set = heap.objectSpace().blocks().set();
143
144 MarkedBlock* candidate = MarkedBlock::blockFor(pointer);
145 if (filter.ruleOut(bitwise_cast<Bits>(candidate))) {
146 ASSERT(!candidate || !set.contains(candidate));
147 return false;
148 }
149
150 if (!MarkedBlock::isAtomAligned(pointer))
151 return false;
152
153 if (!set.contains(candidate))
154 return false;
155
156 if (candidate->handle().cellKind() != HeapCell::JSCell)
157 return false;
158
159 if (!candidate->handle().isLiveCell(pointer))
160 return false;
161
162 return true;
163 }
164
165 // This does not find the cell if the pointer is pointing at the middle of a JSCell.
166 static bool isValueGCObject(
167 Heap& heap, TinyBloomFilter filter, JSValue value)
168 {
169 ASSERT(heap.objectSpace().preciseAllocationSet());
170 if (!value.isCell())
171 return false;
172 return isPointerGCObjectJSCell(heap, filter, value.asCell());
173 }
174};
175
176} // namespace JSC
177
178