1/* 2 * Copyright (C) 2013 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#ifndef DFGAllocator_h 27#define DFGAllocator_h 28 29#if ENABLE(DFG_JIT) 30 31#include "DFGCommon.h" 32#include <wtf/PageAllocationAligned.h> 33#include <wtf/StdLibExtras.h> 34 35namespace JSC { namespace DFG { 36 37// Custom pool allocator for exactly one type (type T). It has fast (O(1), only a few 38// instructions) allocator, and a similarly fast free(). Recycling works if either of 39// the following is true: 40// - T has a trivial destructor. In that case you don't have to ever call free() on 41// anything. You can just call freeAll() instead. 42// - You call free() on all T's that you allocated, and never use freeAll(). 43 44template<typename T> 45class Allocator { 46public: 47 Allocator(); 48 ~Allocator(); 49 50 void* allocate(); // Use placement new to allocate, and avoid using this method. 51 void free(T*); // Call this method to delete; never use 'delete' directly. 52 53 void freeAll(); // Only call this if T has a trivial destructor. 54 void reset(); // Like freeAll(), but also returns all memory to the OS. 55 56 unsigned indexOf(const T*); 57 58 static Allocator* allocatorOf(const T*); 59 60private: 61 void* bumpAllocate(); 62 void* freeListAllocate(); 63 void* allocateSlow(); 64 65 struct Region { 66 static size_t size() { return 64 * KB; } 67 static size_t headerSize() { return std::max(sizeof(Region), sizeof(T)); } 68 static unsigned numberOfThingsPerRegion() { return (size() - headerSize()) / sizeof(T); } 69 T* data() { return bitwise_cast<T*>(bitwise_cast<char*>(this) + headerSize()); } 70 bool isInThisRegion(const T* pointer) { return static_cast<unsigned>(pointer - data()) < numberOfThingsPerRegion(); } 71 static Region* regionFor(const T* pointer) { return bitwise_cast<Region*>(bitwise_cast<uintptr_t>(pointer) & ~(size() - 1)); } 72 73 PageAllocationAligned m_allocation; 74 Allocator* m_allocator; 75 Region* m_next; 76 }; 77 78 void freeRegionsStartingAt(Region*); 79 void startBumpingIn(Region*); 80 81 Region* m_regionHead; 82 void** m_freeListHead; 83 T* m_bumpEnd; 84 unsigned m_bumpRemaining; 85}; 86 87template<typename T> 88inline Allocator<T>::Allocator() 89 : m_regionHead(0) 90 , m_freeListHead(0) 91 , m_bumpRemaining(0) 92{ 93} 94 95template<typename T> 96inline Allocator<T>::~Allocator() 97{ 98 reset(); 99} 100 101template<typename T> 102ALWAYS_INLINE void* Allocator<T>::allocate() 103{ 104 void* result = bumpAllocate(); 105 if (LIKELY(!!result)) 106 return result; 107 return freeListAllocate(); 108} 109 110template<typename T> 111void Allocator<T>::free(T* object) 112{ 113 object->~T(); 114 115 void** cell = bitwise_cast<void**>(object); 116 *cell = m_freeListHead; 117 m_freeListHead = cell; 118} 119 120template<typename T> 121void Allocator<T>::freeAll() 122{ 123 if (!m_regionHead) { 124 ASSERT(!m_bumpRemaining); 125 ASSERT(!m_freeListHead); 126 return; 127 } 128 129 // Since the caller is opting out of calling the destructor for any allocated thing, 130 // we have two choices, plus a continuum between: we can either just delete all regions 131 // (i.e. call reset()), or we can make all regions available for reuse. We do something 132 // that optimizes for (a) speed of freeAll(), (b) the assumption that if the user calls 133 // freeAll() then they will probably be calling allocate() in the near future. Namely, 134 // we free all but one region, and make the remaining region a bump allocation region. 135 136 freeRegionsStartingAt(m_regionHead->m_next); 137 138 m_regionHead->m_next = 0; 139 m_freeListHead = 0; 140 startBumpingIn(m_regionHead); 141} 142 143template<typename T> 144void Allocator<T>::reset() 145{ 146 freeRegionsStartingAt(m_regionHead); 147 148 m_regionHead = 0; 149 m_freeListHead = 0; 150 m_bumpRemaining = 0; 151} 152 153template<typename T> 154unsigned Allocator<T>::indexOf(const T* object) 155{ 156 unsigned numRegions = 0; 157 for (Region* region = m_regionHead; region; region = region->m_next) 158 numRegions++; 159 unsigned regionIndex = 0; 160 for (Region* region = m_regionHead; region; region = region->m_next) { 161 if (region->isInThisRegion(object)) 162 return (numRegions - 1 - regionIndex) * Region::numberOfThingsPerRegion() + (object - region->data()); 163 regionIndex++; 164 } 165 CRASH(); 166 return 0; 167} 168 169template<typename T> 170Allocator<T>* Allocator<T>::allocatorOf(const T* object) 171{ 172 return Region::regionFor(object)->m_allocator; 173} 174 175template<typename T> 176ALWAYS_INLINE void* Allocator<T>::bumpAllocate() 177{ 178 if (unsigned remaining = m_bumpRemaining) { 179 remaining--; 180 m_bumpRemaining = remaining; 181 return m_bumpEnd - (remaining + 1); 182 } 183 return 0; 184} 185 186template<typename T> 187void* Allocator<T>::freeListAllocate() 188{ 189 void** result = m_freeListHead; 190 if (UNLIKELY(!result)) 191 return allocateSlow(); 192 m_freeListHead = bitwise_cast<void**>(*result); 193 return result; 194} 195 196template<typename T> 197void* Allocator<T>::allocateSlow() 198{ 199 ASSERT(!m_freeListHead); 200 ASSERT(!m_bumpRemaining); 201 202 if (logCompilationChanges()) 203 dataLog("Allocating another allocator region.\n"); 204 205 PageAllocationAligned allocation = PageAllocationAligned::allocate(Region::size(), Region::size(), OSAllocator::JSGCHeapPages); 206 if (!static_cast<bool>(allocation)) 207 CRASH(); 208 Region* region = static_cast<Region*>(allocation.base()); 209 region->m_allocation = allocation; 210 region->m_allocator = this; 211 startBumpingIn(region); 212 region->m_next = m_regionHead; 213 m_regionHead = region; 214 215 void* result = bumpAllocate(); 216 ASSERT(result); 217 return result; 218} 219 220template<typename T> 221void Allocator<T>::freeRegionsStartingAt(typename Allocator<T>::Region* region) 222{ 223 while (region) { 224 Region* nextRegion = region->m_next; 225 region->m_allocation.deallocate(); 226 region = nextRegion; 227 } 228} 229 230template<typename T> 231void Allocator<T>::startBumpingIn(typename Allocator<T>::Region* region) 232{ 233 m_bumpEnd = region->data() + Region::numberOfThingsPerRegion(); 234 m_bumpRemaining = Region::numberOfThingsPerRegion(); 235} 236 237} } // namespace JSC::DFG 238 239#endif // ENABLE(DFG_JIT) 240 241#endif // DFGAllocator_h 242 243