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