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 38namespace 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 45class PODArena : public RefCounted<PODArena> { 46public: 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: 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: 62 static PassRefPtr<FastMallocAllocator> create() 63 { 64 return adoptRef(new FastMallocAllocator); 65 } 66 67 virtual void* allocate(size_t size) { return fastMalloc(size); } 68 virtual void free(void* ptr) { fastFree(ptr); } 69 70 protected: 71 FastMallocAllocator() { } 72 }; 73 74 // Creates a new PODArena configured with a FastMallocAllocator. 75 static PassRefPtr<PODArena> create() 76 { 77 return adoptRef(new PODArena); 78 } 79 80 // Creates a new PODArena configured with the given 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. 87 template<class T> T* allocateObject() 88 { 89 return new (allocateBase<T>()) T(); 90 } 91 92 // Allocates an object from the arena, calling a single-argument constructor. 93 template<class T, class Argument1Type> T* allocateObject(const Argument1Type& argument1) 94 { 95 return new (allocateBase<T>()) T(argument1); 96 } 97 98 // The initial size of allocated chunks; increases as necessary to 99 // satisfy large allocations. Mainly public for unit tests. 100 enum { 101 DefaultChunkSize = 16384 102 }; 103 104protected: 105 virtual ~PODArena() { } 106 friend class WTF::RefCounted<PODArena>; 107 108 PODArena() 109 : m_allocator(FastMallocAllocator::create()) 110 , m_current(0) 111 , m_currentChunkSize(DefaultChunkSize) { } 112 113 explicit PODArena(PassRefPtr<Allocator> allocator) 114 : m_allocator(allocator) 115 , m_current(0) 116 , m_currentChunkSize(DefaultChunkSize) { } 117 118 // Returns the alignment requirement for classes and structs on the 119 // current platform. 120 template <class T> static size_t minAlignment() 121 { 122 return WTF_ALIGN_OF(T); 123 } 124 125 template<class T> void* allocateBase() 126 { 127 void* ptr = 0; 128 size_t roundedSize = roundUp(sizeof(T), minAlignment<T>()); 129 if (m_current) 130 ptr = m_current->allocate(roundedSize); 131 132 if (!ptr) { 133 if (roundedSize > m_currentChunkSize) 134 m_currentChunkSize = roundedSize; 135 m_chunks.append(adoptPtr(new Chunk(m_allocator.get(), m_currentChunkSize))); 136 m_current = m_chunks.last().get(); 137 ptr = m_current->allocate(roundedSize); 138 } 139 return ptr; 140 } 141 142 // Rounds up the given allocation size to the specified alignment. 143 size_t roundUp(size_t size, size_t alignment) 144 { 145 ASSERT(!(alignment % 2)); 146 return (size + alignment - 1) & ~(alignment - 1); 147 } 148 149 // Manages a chunk of memory and individual allocations out of it. 150 class Chunk { 151 WTF_MAKE_NONCOPYABLE(Chunk); 152 public: 153 // Allocates a block of memory of the given size from the passed 154 // Allocator. 155 Chunk(Allocator* allocator, size_t size) 156 : m_allocator(allocator) 157 , m_size(size) 158 , m_currentOffset(0) 159 { 160 m_base = static_cast<uint8_t*>(m_allocator->allocate(size)); 161 } 162 163 // Frees the memory allocated from the Allocator in the 164 // constructor. 165 virtual ~Chunk() 166 { 167 m_allocator->free(m_base); 168 } 169 170 // Returns a pointer to "size" bytes of storage, or 0 if this 171 // Chunk could not satisfy the allocation. 172 void* allocate(size_t size) 173 { 174 // Check for overflow 175 if (m_currentOffset + size < m_currentOffset) 176 return 0; 177 178 if (m_currentOffset + size > m_size) 179 return 0; 180 181 void* result = m_base + m_currentOffset; 182 m_currentOffset += size; 183 return result; 184 } 185 186 protected: 187 Allocator* m_allocator; 188 uint8_t* m_base; 189 size_t m_size; 190 size_t m_currentOffset; 191 }; 192 193 RefPtr<Allocator> m_allocator; 194 Chunk* m_current; 195 size_t m_currentChunkSize; 196 Vector<OwnPtr<Chunk> > m_chunks; 197}; 198 199} // namespace WebCore 200 201#endif // PODArena_h 202