1 /* 2 * Copyright (C) 2010 Google 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 * 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 14 * THIS SOFTWARE IS PROVIDED BY APPLE AND ITS CONTRIBUTORS "AS IS" AND ANY 15 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 16 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 17 * DISCLAIMED. IN NO EVENT SHALL APPLE OR ITS CONTRIBUTORS BE LIABLE FOR ANY 18 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES 19 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; 20 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 21 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF 23 * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26 #ifndef PODArena_h 27 #define PODArena_h 28 29 #include <stdint.h> 30 #include <wtf/Assertions.h> 31 #include <wtf/FastMalloc.h> 32 #include <wtf/Noncopyable.h> 33 #include <wtf/OwnPtr.h> 34 #include <wtf/PassOwnPtr.h> 35 #include <wtf/RefCounted.h> 36 #include <wtf/Vector.h> 37 38 namespace WebCore { 39 40 // An arena which allocates only Plain Old Data (POD), or classes and 41 // structs bottoming out in Plain Old Data. NOTE: the constructors of 42 // the objects allocated in this arena are called, but _not_ their 43 // destructors. 44 45 class PODArena : public RefCounted<PODArena> { 46 public: 47 // The arena is configured with an allocator, which is responsible 48 // for allocating and freeing chunks of memory at a time. 49 class Allocator : public RefCounted<Allocator> { 50 public: 51 virtual void* allocate(size_t size) = 0; 52 virtual void free(void* ptr) = 0; 53 protected: ~Allocator()54 virtual ~Allocator() { } 55 friend class WTF::RefCounted<Allocator>; 56 }; 57 58 // The Arena's default allocator, which uses fastMalloc and 59 // fastFree to allocate chunks of storage. 60 class FastMallocAllocator : public Allocator { 61 public: create()62 static PassRefPtr<FastMallocAllocator> create() 63 { 64 return adoptRef(new FastMallocAllocator); 65 } 66 allocate(size_t size)67 virtual void* allocate(size_t size) { return fastMalloc(size); } free(void * ptr)68 virtual void free(void* ptr) { fastFree(ptr); } 69 70 protected: FastMallocAllocator()71 FastMallocAllocator() { } 72 }; 73 74 // Creates a new PODArena configured with a FastMallocAllocator. create()75 static PassRefPtr<PODArena> create() 76 { 77 return adoptRef(new PODArena); 78 } 79 80 // Creates a new PODArena configured with the given Allocator. create(PassRefPtr<Allocator> allocator)81 static PassRefPtr<PODArena> create(PassRefPtr<Allocator> allocator) 82 { 83 return adoptRef(new PODArena(allocator)); 84 } 85 86 // Allocates an object from the arena. allocateObject()87 template<class T> T* allocateObject() 88 { 89 void* ptr = allocateBase<T>(); 90 if (ptr) { 91 // Use placement operator new to allocate a T at this location. 92 new(ptr) T(); 93 } 94 return static_cast<T*>(ptr); 95 } 96 97 // Allocates an object from the arena, calling a single-argument constructor. allocateObject(const Argument1Type & argument1)98 template<class T, class Argument1Type> T* allocateObject(const Argument1Type& argument1) 99 { 100 void* ptr = allocateBase<T>(); 101 if (ptr) { 102 // Use placement operator new to allocate a T at this location. 103 new(ptr) T(argument1); 104 } 105 return static_cast<T*>(ptr); 106 } 107 108 // The initial size of allocated chunks; increases as necessary to 109 // satisfy large allocations. Mainly public for unit tests. 110 enum { 111 DefaultChunkSize = 16384 112 }; 113 114 protected: ~PODArena()115 ~PODArena() { } 116 friend class WTF::RefCounted<PODArena>; 117 118 private: PODArena()119 PODArena() 120 : m_allocator(FastMallocAllocator::create()) 121 , m_current(0) 122 , m_currentChunkSize(DefaultChunkSize) { } 123 PODArena(PassRefPtr<Allocator> allocator)124 explicit PODArena(PassRefPtr<Allocator> allocator) 125 : m_allocator(allocator) 126 , m_current(0) 127 , m_currentChunkSize(DefaultChunkSize) { } 128 129 // Returns the alignment requirement for classes and structs on the 130 // current platform. minAlignment()131 template <class T> static size_t minAlignment() 132 { 133 return WTF_ALIGN_OF(T); 134 } 135 allocateBase()136 template<class T> void* allocateBase() 137 { 138 void* ptr = 0; 139 size_t roundedSize = roundUp(sizeof(T), minAlignment<T>()); 140 if (m_current) 141 ptr = m_current->allocate(roundedSize); 142 143 if (!ptr) { 144 if (roundedSize > m_currentChunkSize) 145 m_currentChunkSize = roundedSize; 146 m_chunks.append(adoptPtr(new Chunk(m_allocator.get(), m_currentChunkSize))); 147 m_current = m_chunks.last().get(); 148 ptr = m_current->allocate(roundedSize); 149 } 150 return ptr; 151 } 152 153 // Rounds up the given allocation size to the specified alignment. roundUp(size_t size,size_t alignment)154 size_t roundUp(size_t size, size_t alignment) 155 { 156 ASSERT(!(alignment % 2)); 157 return (size + alignment - 1) & ~(alignment - 1); 158 } 159 160 // Manages a chunk of memory and individual allocations out of it. 161 class Chunk { 162 WTF_MAKE_NONCOPYABLE(Chunk); 163 public: 164 // Allocates a block of memory of the given size from the passed 165 // Allocator. Chunk(Allocator * allocator,size_t size)166 Chunk(Allocator* allocator, size_t size) 167 : m_allocator(allocator) 168 , m_size(size) 169 , m_currentOffset(0) 170 { 171 m_base = static_cast<uint8_t*>(m_allocator->allocate(size)); 172 } 173 174 // Frees the memory allocated from the Allocator in the 175 // constructor. ~Chunk()176 ~Chunk() 177 { 178 m_allocator->free(m_base); 179 } 180 181 // Returns a pointer to "size" bytes of storage, or 0 if this 182 // Chunk could not satisfy the allocation. allocate(size_t size)183 void* allocate(size_t size) 184 { 185 // Check for overflow 186 if (m_currentOffset + size < m_currentOffset) 187 return 0; 188 189 if (m_currentOffset + size > m_size) 190 return 0; 191 192 void* result = m_base + m_currentOffset; 193 m_currentOffset += size; 194 return result; 195 } 196 197 private: 198 Allocator* m_allocator; 199 uint8_t* m_base; 200 size_t m_size; 201 size_t m_currentOffset; 202 }; 203 204 RefPtr<Allocator> m_allocator; 205 Chunk* m_current; 206 size_t m_currentChunkSize; 207 Vector<OwnPtr<Chunk> > m_chunks; 208 }; 209 210 } // namespace WebCore 211 212 #endif // PODArena_h 213