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 blink {
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 FINAL : 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) OVERRIDE { return fastMalloc(size); }
68        virtual void free(void* ptr) OVERRIDE { 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    friend class WTF::RefCounted<PODArena>;
106
107    PODArena()
108        : m_allocator(FastMallocAllocator::create())
109        , m_current(0)
110        , m_currentChunkSize(DefaultChunkSize) { }
111
112    explicit PODArena(PassRefPtr<Allocator> allocator)
113        : m_allocator(allocator)
114        , m_current(0)
115        , m_currentChunkSize(DefaultChunkSize) { }
116
117    // Returns the alignment requirement for classes and structs on the
118    // current platform.
119    template <class T> static size_t minAlignment()
120    {
121        return WTF_ALIGN_OF(T);
122    }
123
124    template<class T> void* allocateBase()
125    {
126        void* ptr = 0;
127        size_t roundedSize = roundUp(sizeof(T), minAlignment<T>());
128        if (m_current)
129            ptr = m_current->allocate(roundedSize);
130
131        if (!ptr) {
132            if (roundedSize > m_currentChunkSize)
133                m_currentChunkSize = roundedSize;
134            m_chunks.append(adoptPtr(new Chunk(m_allocator.get(), m_currentChunkSize)));
135            m_current = m_chunks.last().get();
136            ptr = m_current->allocate(roundedSize);
137        }
138        return ptr;
139    }
140
141    // Rounds up the given allocation size to the specified alignment.
142    size_t roundUp(size_t size, size_t alignment)
143    {
144        ASSERT(!(alignment % 2));
145        return (size + alignment - 1) & ~(alignment - 1);
146    }
147
148    // Manages a chunk of memory and individual allocations out of it.
149    class Chunk FINAL {
150        WTF_MAKE_NONCOPYABLE(Chunk);
151    public:
152        // Allocates a block of memory of the given size from the passed
153        // Allocator.
154        Chunk(Allocator* allocator, size_t size)
155            : m_allocator(allocator)
156            , m_size(size)
157            , m_currentOffset(0)
158        {
159            m_base = static_cast<uint8_t*>(m_allocator->allocate(size));
160        }
161
162        // Frees the memory allocated from the Allocator in the
163        // constructor.
164        ~Chunk()
165        {
166            m_allocator->free(m_base);
167        }
168
169        // Returns a pointer to "size" bytes of storage, or 0 if this
170        // Chunk could not satisfy the allocation.
171        void* allocate(size_t size)
172        {
173            // Check for overflow
174            if (m_currentOffset + size < m_currentOffset)
175                return 0;
176
177            if (m_currentOffset + size > m_size)
178                return 0;
179
180            void* result = m_base + m_currentOffset;
181            m_currentOffset += size;
182            return result;
183        }
184
185    protected:
186        Allocator* m_allocator;
187        uint8_t* m_base;
188        size_t m_size;
189        size_t m_currentOffset;
190    };
191
192    RefPtr<Allocator> m_allocator;
193    Chunk* m_current;
194    size_t m_currentChunkSize;
195    Vector<OwnPtr<Chunk> > m_chunks;
196};
197
198} // namespace blink
199
200#endif // PODArena_h
201