1 | /* |
2 | * Copyright (C) 2010 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 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 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 BumpPointerAllocator_h |
27 | #define BumpPointerAllocator_h |
28 | |
29 | #include <algorithm> |
30 | #include <wtf/PageAllocation.h> |
31 | #include <wtf/PageBlock.h> |
32 | |
33 | namespace WTF { |
34 | |
35 | #define MINIMUM_BUMP_POOL_SIZE 0x1000 |
36 | |
37 | class BumpPointerPool { |
38 | public: |
39 | // ensureCapacity will check whether the current pool has capacity to |
40 | // allocate 'size' bytes of memory If it does not, it will attempt to |
41 | // allocate a new pool (which will be added to this one in a chain). |
42 | // |
43 | // If allocation fails (out of memory) this method will return null. |
44 | // If the return value is non-null, then callers should update any |
45 | // references they have to this current (possibly full) BumpPointerPool |
46 | // to instead point to the newly returned BumpPointerPool. |
47 | BumpPointerPool* ensureCapacity(size_t size) |
48 | { |
49 | void* allocationEnd = static_cast<char*>(m_current) + size; |
50 | ASSERT(allocationEnd > m_current); // check for overflow |
51 | if (allocationEnd <= static_cast<void*>(this)) |
52 | return this; |
53 | return ensureCapacityCrossPool(previousPool: this, size); |
54 | } |
55 | |
56 | // alloc should only be called after calling ensureCapacity; as such |
57 | // alloc will never fail. |
58 | void* alloc(size_t size) |
59 | { |
60 | void* current = m_current; |
61 | void* allocationEnd = static_cast<char*>(current) + size; |
62 | ASSERT(allocationEnd > current); // check for overflow |
63 | ASSERT(allocationEnd <= static_cast<void*>(this)); |
64 | m_current = allocationEnd; |
65 | return current; |
66 | } |
67 | |
68 | // The dealloc method releases memory allocated using alloc. Memory |
69 | // must be released in a LIFO fashion, e.g. if the client calls alloc |
70 | // four times, returning pointer A, B, C, D, then the only valid order |
71 | // in which these may be deallocaed is D, C, B, A. |
72 | // |
73 | // The client may optionally skip some deallocations. In the example |
74 | // above, it would be valid to only explicitly dealloc C, A (D being |
75 | // dealloced along with C, B along with A). |
76 | // |
77 | // If pointer was not allocated from this pool (or pools) then dealloc |
78 | // will CRASH(). Callers should update any references they have to |
79 | // this current BumpPointerPool to instead point to the returned |
80 | // BumpPointerPool. |
81 | BumpPointerPool* dealloc(void* position) |
82 | { |
83 | if ((position >= m_start) && (position <= static_cast<void*>(this))) { |
84 | ASSERT(position <= m_current); |
85 | m_current = position; |
86 | return this; |
87 | } |
88 | return deallocCrossPool(pool: this, position); |
89 | } |
90 | |
91 | private: |
92 | // Placement operator new, returns the last 'size' bytes of allocation for use as this. |
93 | void* operator new(size_t size, const PageAllocation& allocation) |
94 | { |
95 | ASSERT(size < allocation.size()); |
96 | return reinterpret_cast<char*>(reinterpret_cast<intptr_t>(allocation.base()) + allocation.size()) - size; |
97 | } |
98 | |
99 | BumpPointerPool(const PageAllocation& allocation) |
100 | : m_current(allocation.base()) |
101 | , m_start(allocation.base()) |
102 | , m_next(0) |
103 | , m_previous(0) |
104 | , m_allocation(allocation) |
105 | { |
106 | } |
107 | |
108 | static BumpPointerPool* create(size_t minimumCapacity = 0) |
109 | { |
110 | // Add size of BumpPointerPool object, check for overflow. |
111 | minimumCapacity += sizeof(BumpPointerPool); |
112 | if (minimumCapacity < sizeof(BumpPointerPool)) |
113 | return 0; |
114 | |
115 | size_t poolSize = std::max(a: static_cast<size_t>(MINIMUM_BUMP_POOL_SIZE), b: WTF::pageSize()); |
116 | while (poolSize < minimumCapacity) { |
117 | poolSize <<= 1; |
118 | // The following if check relies on MINIMUM_BUMP_POOL_SIZE being a power of 2! |
119 | ASSERT(!(MINIMUM_BUMP_POOL_SIZE & (MINIMUM_BUMP_POOL_SIZE - 1))); |
120 | if (!poolSize) |
121 | return 0; |
122 | } |
123 | |
124 | PageAllocation allocation = PageAllocation::allocate(size: poolSize); |
125 | if (!!allocation) |
126 | return new (allocation) BumpPointerPool(allocation); |
127 | return 0; |
128 | } |
129 | |
130 | void shrink() |
131 | { |
132 | ASSERT(!m_previous); |
133 | m_current = m_start; |
134 | while (m_next) { |
135 | BumpPointerPool* nextNext = m_next->m_next; |
136 | m_next->destroy(); |
137 | m_next = nextNext; |
138 | } |
139 | } |
140 | |
141 | void destroy() |
142 | { |
143 | m_allocation.deallocate(); |
144 | } |
145 | |
146 | static BumpPointerPool* ensureCapacityCrossPool(BumpPointerPool* previousPool, size_t size) |
147 | { |
148 | // The pool passed should not have capacity, so we'll start with the next one. |
149 | ASSERT(previousPool); |
150 | ASSERT((static_cast<char*>(previousPool->m_current) + size) > previousPool->m_current); // check for overflow |
151 | ASSERT((static_cast<char*>(previousPool->m_current) + size) > static_cast<void*>(previousPool)); |
152 | BumpPointerPool* pool = previousPool->m_next; |
153 | |
154 | while (true) { |
155 | if (!pool) { |
156 | // We've run to the end; allocate a new pool. |
157 | pool = BumpPointerPool::create(minimumCapacity: size); |
158 | previousPool->m_next = pool; |
159 | pool->m_previous = previousPool; |
160 | return pool; |
161 | } |
162 | |
163 | // |
164 | void* current = pool->m_current; |
165 | void* allocationEnd = static_cast<char*>(current) + size; |
166 | ASSERT(allocationEnd > current); // check for overflow |
167 | if (allocationEnd <= static_cast<void*>(pool)) |
168 | return pool; |
169 | } |
170 | } |
171 | |
172 | static BumpPointerPool* deallocCrossPool(BumpPointerPool* pool, void* position) |
173 | { |
174 | // Should only be called if position is not in the current pool. |
175 | ASSERT((position < pool->m_start) || (position > static_cast<void*>(pool))); |
176 | |
177 | while (true) { |
178 | // Unwind the current pool to the start, move back in the chain to the previous pool. |
179 | pool->m_current = pool->m_start; |
180 | pool = pool->m_previous; |
181 | |
182 | // position was nowhere in the chain! |
183 | if (!pool) |
184 | CRASH(); |
185 | |
186 | if ((position >= pool->m_start) && (position <= static_cast<void*>(pool))) { |
187 | ASSERT(position <= pool->m_current); |
188 | pool->m_current = position; |
189 | return pool; |
190 | } |
191 | } |
192 | } |
193 | |
194 | void* m_current; |
195 | void* m_start; |
196 | BumpPointerPool* m_next; |
197 | BumpPointerPool* m_previous; |
198 | PageAllocation m_allocation; |
199 | |
200 | friend class BumpPointerAllocator; |
201 | }; |
202 | |
203 | // A BumpPointerAllocator manages a set of BumpPointerPool objects, which |
204 | // can be used for LIFO (stack like) allocation. |
205 | // |
206 | // To begin allocating using this class call startAllocator(). The result |
207 | // of this method will be null if the initial pool allocation fails, or a |
208 | // pointer to a BumpPointerPool object that can be used to perform |
209 | // allocations. Whilst running no memory will be released until |
210 | // stopAllocator() is called. At this point all allocations made through |
211 | // this allocator will be reaped, and underlying memory may be freed. |
212 | // |
213 | // (In practice we will still hold on to the initial pool to allow allocation |
214 | // to be quickly restared, but aditional pools will be freed). |
215 | // |
216 | // This allocator is non-renetrant, it is encumbant on the clients to ensure |
217 | // startAllocator() is not called again until stopAllocator() has been called. |
218 | class BumpPointerAllocator { |
219 | public: |
220 | BumpPointerAllocator() |
221 | : m_head(0) |
222 | { |
223 | } |
224 | |
225 | ~BumpPointerAllocator() |
226 | { |
227 | if (m_head) |
228 | m_head->destroy(); |
229 | } |
230 | |
231 | BumpPointerPool* startAllocator() |
232 | { |
233 | if (!m_head) |
234 | m_head = BumpPointerPool::create(); |
235 | return m_head; |
236 | } |
237 | |
238 | void stopAllocator() |
239 | { |
240 | if (m_head) |
241 | m_head->shrink(); |
242 | } |
243 | |
244 | private: |
245 | BumpPointerPool* m_head; |
246 | }; |
247 | |
248 | } |
249 | |
250 | using WTF::BumpPointerAllocator; |
251 | |
252 | #endif // BumpPointerAllocator_h |
253 | |