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