2 * Copyright (C) 2013 Apple Inc. All rights reserved.
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions
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.
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.
26 #ifndef DFGAllocator_h
27 #define DFGAllocator_h
29 #include <wtf/Platform.h>
33 #include "DFGCommon.h"
34 #include <wtf/PageAllocationAligned.h>
35 #include <wtf/StdLibExtras.h>
37 namespace JSC
{ namespace DFG
{
39 // Custom pool allocator for exactly one type (type T). It has fast (O(1), only a few
40 // instructions) allocator, and a similarly fast free(). Recycling works if either of
41 // the following is true:
42 // - T has a trivial destructor. In that case you don't have to ever call free() on
43 // anything. You can just call freeAll() instead.
44 // - You call free() on all T's that you allocated, and never use freeAll().
52 void* allocate(); // Use placement new to allocate, and avoid using this method.
53 void free(T
*); // Call this method to delete; never use 'delete' directly.
55 void freeAll(); // Only call this if T has a trivial destructor.
56 void reset(); // Like freeAll(), but also returns all memory to the OS.
58 unsigned indexOf(const T
*);
60 static Allocator
* allocatorOf(const T
*);
64 void* freeListAllocate();
68 static size_t size() { return 64 * KB
; }
69 static size_t headerSize() { return std::max(sizeof(Region
), sizeof(T
)); }
70 static unsigned numberOfThingsPerRegion() { return (size() - headerSize()) / sizeof(T
); }
71 T
* data() { return bitwise_cast
<T
*>(bitwise_cast
<char*>(this) + headerSize()); }
72 bool isInThisRegion(const T
* pointer
) { return static_cast<unsigned>(pointer
- data()) < numberOfThingsPerRegion(); }
73 static Region
* regionFor(const T
* pointer
) { return bitwise_cast
<Region
*>(bitwise_cast
<uintptr_t>(pointer
) & ~(size() - 1)); }
75 PageAllocationAligned m_allocation
;
76 Allocator
* m_allocator
;
80 void freeRegionsStartingAt(Allocator::Region
*);
81 void startBumpingIn(Allocator::Region
*);
84 void** m_freeListHead
;
86 unsigned m_bumpRemaining
;
90 inline Allocator
<T
>::Allocator()
98 inline Allocator
<T
>::~Allocator()
104 ALWAYS_INLINE
void* Allocator
<T
>::allocate()
106 void* result
= bumpAllocate();
107 if (LIKELY(!!result
))
109 return freeListAllocate();
113 void Allocator
<T
>::free(T
* object
)
117 void** cell
= bitwise_cast
<void**>(object
);
118 *cell
= m_freeListHead
;
119 m_freeListHead
= cell
;
123 void Allocator
<T
>::freeAll()
126 ASSERT(!m_bumpRemaining
);
127 ASSERT(!m_freeListHead
);
131 // Since the caller is opting out of calling the destructor for any allocated thing,
132 // we have two choices, plus a continuum between: we can either just delete all regions
133 // (i.e. call reset()), or we can make all regions available for reuse. We do something
134 // that optimizes for (a) speed of freeAll(), (b) the assumption that if the user calls
135 // freeAll() then they will probably be calling allocate() in the near future. Namely,
136 // we free all but one region, and make the remaining region a bump allocation region.
138 freeRegionsStartingAt(m_regionHead
->m_next
);
140 m_regionHead
->m_next
= 0;
142 startBumpingIn(m_regionHead
);
146 void Allocator
<T
>::reset()
148 freeRegionsStartingAt(m_regionHead
);
156 unsigned Allocator
<T
>::indexOf(const T
* object
)
158 unsigned baseIndex
= 0;
159 for (Region
* region
= m_regionHead
; region
; region
= region
->m_next
) {
160 if (region
->isInThisRegion(object
))
161 return baseIndex
+ (object
- region
->data());
162 baseIndex
+= Region::numberOfThingsPerRegion();
169 Allocator
<T
>* Allocator
<T
>::allocatorOf(const T
* object
)
171 return Region::regionFor(object
)->m_allocator
;
175 ALWAYS_INLINE
void* Allocator
<T
>::bumpAllocate()
177 if (unsigned remaining
= m_bumpRemaining
) {
179 m_bumpRemaining
= remaining
;
180 return m_bumpEnd
- (remaining
+ 1);
186 void* Allocator
<T
>::freeListAllocate()
188 void** result
= m_freeListHead
;
189 if (UNLIKELY(!result
))
190 return allocateSlow();
191 m_freeListHead
= bitwise_cast
<void**>(*result
);
196 void* Allocator
<T
>::allocateSlow()
198 ASSERT(!m_freeListHead
);
199 ASSERT(!m_bumpRemaining
);
201 if (logCompilationChanges())
202 dataLog("Allocating another allocator region.\n");
204 PageAllocationAligned allocation
= PageAllocationAligned::allocate(Region::size(), Region::size(), OSAllocator::JSGCHeapPages
);
205 if (!static_cast<bool>(allocation
))
207 Region
* region
= static_cast<Region
*>(allocation
.base());
208 region
->m_allocation
= allocation
;
209 region
->m_allocator
= this;
210 startBumpingIn(region
);
211 region
->m_next
= m_regionHead
;
212 m_regionHead
= region
;
214 void* result
= bumpAllocate();
220 void Allocator
<T
>::freeRegionsStartingAt(typename Allocator
<T
>::Region
* region
)
223 Region
* nextRegion
= region
->m_next
;
224 region
->m_allocation
.deallocate();
230 void Allocator
<T
>::startBumpingIn(typename Allocator
<T
>::Region
* region
)
232 m_bumpEnd
= region
->data() + Region::numberOfThingsPerRegion();
233 m_bumpRemaining
= Region::numberOfThingsPerRegion();
236 } } // namespace JSC::DFG
238 #endif // ENABLE(DFG_JIT)
240 #endif // DFGAllocator_h