1/* 2 * Copyright (C) 2011 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 PODFreeListArena_h 27#define PODFreeListArena_h 28 29#include "PODArena.h" 30 31namespace WebCore { 32 33template <class T> 34class PODFreeListArena : public PODArena { 35public: 36 static PassRefPtr<PODFreeListArena> create() 37 { 38 return adoptRef(new PODFreeListArena); 39 } 40 41 template<class Argument1Type> T* allocateObject(const Argument1Type& argument1) 42 { 43#if defined(ADDRESS_SANITIZER) 44 return new T(argument1); 45#else 46 size_t roundedSize = roundUp(sizeof(T), minAlignment<T>()); 47 void* ptr = allocate(roundedSize); 48 if (ptr) { 49 // Use placement operator new to allocate a T at this location. 50 new(ptr) T(argument1); 51 } 52 return static_cast<T*>(ptr); 53#endif 54 } 55 56 void freeObject(T* ptr) 57 { 58#if defined(ADDRESS_SANITIZER) 59 delete ptr; 60#else 61 for (typename Vector<OwnPtr<FreeListChunk>>::const_iterator it = m_chunks.begin(), end = m_chunks.end(); it != end; ++it) { 62 FreeListChunk* chunk = static_cast<FreeListChunk*>(it->get()); 63 if (chunk->contains(ptr)) 64 chunk->free(ptr); 65 } 66#endif 67 } 68 69private: 70 // The initial size of allocated chunks; increases as necessary to 71 // satisfy large allocations. Mainly public for unit tests. 72 enum { 73 DefaultChunkSize = 16384 74 }; 75 76 PODFreeListArena() 77 : m_current(0) 78 , m_currentChunkSize(DefaultChunkSize) 79 { 80 } 81 82 void* allocate(size_t size) 83 { 84 void* ptr = 0; 85 if (m_current) { 86 // First allocate from the current chunk. 87 ptr = m_current->allocate(size); 88 if (!ptr) { 89 // Check if we can allocate from other chunks' free list. 90 for (typename Vector<OwnPtr<FreeListChunk>>::const_iterator it = m_chunks.begin(), end = m_chunks.end(); it != end; ++it) { 91 FreeListChunk* chunk = static_cast<FreeListChunk*>(it->get()); 92 if (chunk->hasFreeList()) { 93 ptr = chunk->allocate(size); 94 if (ptr) 95 break; 96 } 97 } 98 } 99 } 100 101 if (!ptr) { 102 if (size > m_currentChunkSize) 103 m_currentChunkSize = size; 104 m_chunks.append(adoptPtr(new FreeListChunk(m_currentChunkSize))); 105 m_current = m_chunks.last().get(); 106 ptr = m_current->allocate(size); 107 } 108 return ptr; 109 } 110 111 // Manages a chunk of memory and individual allocations out of it. 112 class FreeListChunk { 113 WTF_MAKE_NONCOPYABLE(FreeListChunk); 114 115 struct FreeCell { 116 FreeCell *m_next; 117 }; 118 public: 119 explicit FreeListChunk(size_t size) 120 : m_size(size) 121 , m_currentOffset(0) 122 , m_freeList(0) 123 { 124 m_base = static_cast<uint8_t*>(fastMalloc(size)); 125 } 126 127 // Frees the memory allocated from the Allocator in the 128 // constructor. 129 ~FreeListChunk() 130 { 131 fastFree(m_base); 132 } 133 134 // Returns a pointer to "size" bytes of storage, or 0 if this 135 // Chunk could not satisfy the allocation. 136 void* allocate(size_t size) 137 { 138 if (m_freeList) { 139 // Reuse a cell from the free list. 140 void *cell = m_freeList; 141 m_freeList = m_freeList->m_next; 142 return cell; 143 } 144 145 // Check for overflow 146 if (m_currentOffset + size < m_currentOffset) 147 return 0; 148 149 if (m_currentOffset + size > m_size) 150 return 0; 151 152 void* result = m_base + m_currentOffset; 153 m_currentOffset += size; 154 return result; 155 } 156 157 void free(void* ptr) 158 { 159 // Add the pointer to free list. 160 ASSERT(contains(ptr)); 161 162 FreeCell* cell = reinterpret_cast<FreeCell*>(ptr); 163 cell->m_next = m_freeList; 164 m_freeList = cell; 165 } 166 167 bool contains(void* ptr) const 168 { 169 return ptr >= m_base && ptr < m_base + m_size; 170 } 171 172 bool hasFreeList() const 173 { 174 return m_freeList; 175 } 176 177 private: 178 uint8_t* m_base; 179 size_t m_size; 180 size_t m_currentOffset; 181 182 FreeCell *m_freeList; 183 }; 184 185 FreeListChunk* m_current; 186 size_t m_currentChunkSize; 187 Vector<OwnPtr<FreeListChunk>> m_chunks; 188}; 189 190} // namespace WebCore 191 192#endif 193