CodeBlocks should be in IsoSubspaces
[WebKit-https.git] / Source / JavaScriptCore / heap / HeapUtil.h
1 /*
2  * Copyright (C) 2016 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
28 namespace 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
43 class HeapUtil {
44 public:
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 = pointer - sizeof(IndexingHeader) - 1;
88             MarkedBlock* previousCandidate = MarkedBlock::blockFor(previousPointer);
89             if (!filter.ruleOut(bitwise_cast<Bits>(previousCandidate))
90                 && set.contains(previousCandidate)
91                 && previousCandidate->handle().cellKind() == HeapCell::Auxiliary) {
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 (candidate->handle().cellKind() == HeapCell::JSCell) {
114             if (!MarkedBlock::isAtomAligned(pointer))
115                 return;
116         
117             tryPointer(pointer);
118             return;
119         }
120     
121         // A butterfly could point into the middle of an object.
122         char* alignedPointer = static_cast<char*>(candidate->handle().cellAlign(pointer));
123         tryPointer(alignedPointer);
124     
125         // Also, a butterfly could point at the end of an object plus sizeof(IndexingHeader). In that
126         // case, this is pointing to the object to the right of the one we should be marking.
127         if (candidate->atomNumber(alignedPointer) > MarkedBlock::firstAtom()
128             && pointer <= alignedPointer + sizeof(IndexingHeader))
129             tryPointer(alignedPointer - candidate->cellSize());
130     }
131     
132     static bool isPointerGCObjectJSCell(
133         Heap& heap, TinyBloomFilter filter, const void* pointer)
134     {
135         // It could point to a large allocation.
136         const Vector<LargeAllocation*>& largeAllocations = heap.objectSpace().largeAllocations();
137         if (!largeAllocations.isEmpty()) {
138             if (largeAllocations[0]->aboveLowerBound(pointer)
139                 && largeAllocations.last()->belowUpperBound(pointer)) {
140                 LargeAllocation*const* result = approximateBinarySearch<LargeAllocation*const>(
141                     largeAllocations.begin(), largeAllocations.size(),
142                     LargeAllocation::fromCell(pointer),
143                     [] (LargeAllocation*const* ptr) -> LargeAllocation* { return *ptr; });
144                 if (result) {
145                     if (result > largeAllocations.begin()
146                         && result[-1]->cell() == pointer
147                         && result[-1]->attributes().cellKind == HeapCell::JSCell)
148                         return true;
149                     if (result[0]->cell() == pointer
150                         && result[0]->attributes().cellKind == HeapCell::JSCell)
151                         return true;
152                     if (result + 1 < largeAllocations.end()
153                         && result[1]->cell() == pointer
154                         && result[1]->attributes().cellKind == HeapCell::JSCell)
155                         return true;
156                 }
157             }
158         }
159     
160         const HashSet<MarkedBlock*>& set = heap.objectSpace().blocks().set();
161         
162         MarkedBlock* candidate = MarkedBlock::blockFor(pointer);
163         if (filter.ruleOut(bitwise_cast<Bits>(candidate))) {
164             ASSERT(!candidate || !set.contains(candidate));
165             return false;
166         }
167         
168         if (!MarkedBlock::isAtomAligned(pointer))
169             return false;
170         
171         if (!set.contains(candidate))
172             return false;
173         
174         if (candidate->handle().cellKind() != HeapCell::JSCell)
175             return false;
176         
177         if (!candidate->handle().isLiveCell(pointer))
178             return false;
179         
180         return true;
181     }
182     
183     static bool isValueGCObject(
184         Heap& heap, TinyBloomFilter filter, JSValue value)
185     {
186         if (!value.isCell())
187             return false;
188         return isPointerGCObjectJSCell(heap, filter, static_cast<void*>(value.asCell()));
189     }
190 };
191
192 } // namespace JSC
193