1 /* Copyright (C) 2011 Wildfire Games.
2 *
3 * Permission is hereby granted, free of charge, to any person obtaining
4 * a copy of this software and associated documentation files (the
5 * "Software"), to deal in the Software without restriction, including
6 * without limitation the rights to use, copy, modify, merge, publish,
7 * distribute, sublicense, and/or sell copies of the Software, and to
8 * permit persons to whom the Software is furnished to do so, subject to
9 * the following conditions:
10 *
11 * The above copyright notice and this permission notice shall be included
12 * in all copies or substantial portions of the Software.
13 *
14 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
15 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
16 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
17 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
18 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
19 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
20 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
21 */
22
23 /*
24 * pool allocator
25 */
26
27 #include "precompiled.h"
28 #include "lib/allocators/pool.h"
29
30 #include "lib/alignment.h"
31 #include "lib/allocators/freelist.h"
32 #include "lib/allocators/allocator_adapters.h"
33
34 #include "lib/timer.h"
35
36 namespace Allocators {
37
38 template<class Storage>
39 struct BasicPoolTest
40 {
operator ()Allocators::BasicPoolTest41 void operator()() const
42 {
43 Pool<double, Storage> p(100);
44 const size_t initialSpace = p.RemainingObjects();
45 double* p1 = p.Allocate();
46 ENSURE(p1 != 0);
47 ENSURE(p.Contains(uintptr_t(p1)));
48 ENSURE(p.RemainingObjects() == initialSpace-1);
49 ENSURE(p.Contains(uintptr_t(p1)+1));
50 ENSURE(p.Contains(uintptr_t(p1)+sizeof(double)-1));
51 ENSURE(!p.Contains(uintptr_t(p1)-1));
52 ENSURE(!p.Contains(uintptr_t(p1)+sizeof(double)));
53 if(p.RemainingObjects() == 0)
54 ENSURE(p.Allocate() == 0); // full
55 else
56 ENSURE(p.Allocate() != 0); // can still expand
57 p.DeallocateAll();
58 ENSURE(!p.Contains(uintptr_t(p1)));
59
60 p1 = p.Allocate();
61 ENSURE(p1 != 0);
62 ENSURE(p.Contains(uintptr_t(p1)));
63 ENSURE(p.RemainingObjects() == initialSpace-1);
64 double* p2 = p.Allocate();
65 ENSURE(p2 != 0);
66 ENSURE(p.Contains(uintptr_t(p2)));
67 ENSURE(p.RemainingObjects() == initialSpace-2);
68 ENSURE(p2 == (double*)(uintptr_t(p1)+sizeof(double)));
69 if(p.RemainingObjects() == 0)
70 ENSURE(p.Allocate() == 0); // full
71 else
72 ENSURE(p.Allocate() != 0); // can still expand
73 }
74 };
75
TestPool()76 void TestPool()
77 {
78 ForEachStorage<BasicPoolTest>();
79 }
80
81 } // namespace Allocators
82
83
84 TIMER_ADD_CLIENT(tc_pool_alloc);
85
pool_create(Pool * p,size_t max_size,size_t el_size)86 Status pool_create(Pool* p, size_t max_size, size_t el_size)
87 {
88 if(el_size == POOL_VARIABLE_ALLOCS)
89 p->el_size = 0;
90 else
91 p->el_size = Align<allocationAlignment>(el_size);
92 p->freelist = mem_freelist_Sentinel();
93 RETURN_STATUS_IF_ERR(da_alloc(&p->da, max_size));
94 return INFO::OK;
95 }
96
97
pool_destroy(Pool * p)98 Status pool_destroy(Pool* p)
99 {
100 // don't be picky and complain if the freelist isn't empty;
101 // we don't care since it's all part of the da anyway.
102 // however, zero it to prevent further allocs from succeeding.
103 p->freelist = mem_freelist_Sentinel();
104 return da_free(&p->da);
105 }
106
107
pool_contains(const Pool * p,void * el)108 bool pool_contains(const Pool* p, void* el)
109 {
110 // outside of our range
111 if(!(p->da.base <= el && el < p->da.base+p->da.pos))
112 return false;
113 // sanity check: it should be aligned (if pool has fixed-size elements)
114 if(p->el_size)
115 ENSURE((uintptr_t)((u8*)el - p->da.base) % p->el_size == 0);
116 return true;
117 }
118
119
pool_alloc(Pool * p,size_t size)120 void* pool_alloc(Pool* p, size_t size)
121 {
122 TIMER_ACCRUE(tc_pool_alloc);
123 // if pool allows variable sizes, go with the size parameter,
124 // otherwise the pool el_size setting.
125 const size_t el_size = p->el_size? p->el_size : Align<allocationAlignment>(size);
126 ASSERT(el_size != 0);
127
128 // note: freelist is always empty in pools with variable-sized elements
129 // because they disallow pool_free.
130 void* el = mem_freelist_Detach(p->freelist);
131 if(!el) // freelist empty, need to allocate a new entry
132 {
133 // expand, if necessary
134 if(da_reserve(&p->da, el_size) < 0)
135 return 0;
136
137 el = p->da.base + p->da.pos;
138 p->da.pos += el_size;
139 }
140
141 ASSERT(pool_contains(p, el)); // paranoia
142 return el;
143 }
144
145
pool_free(Pool * p,void * el)146 void pool_free(Pool* p, void* el)
147 {
148 // only allowed to free items if we were initialized with
149 // fixed el_size. (this avoids having to pass el_size here and
150 // check if requested_size matches that when allocating)
151 if(p->el_size == 0)
152 {
153 DEBUG_WARN_ERR(ERR::LOGIC); // cannot free variable-size items
154 return;
155 }
156
157 if(pool_contains(p, el))
158 mem_freelist_AddToFront(p->freelist, el);
159 else
160 DEBUG_WARN_ERR(ERR::LOGIC); // invalid pointer (not in pool)
161 }
162
163
pool_free_all(Pool * p)164 void pool_free_all(Pool* p)
165 {
166 p->freelist = mem_freelist_Sentinel();
167
168 // must be reset before da_set_size or CHECK_DA will complain.
169 p->da.pos = 0;
170
171 da_set_size(&p->da, 0);
172 }
173
pool_committed(Pool * p)174 size_t pool_committed(Pool* p)
175 {
176 return p->da.cur_size;
177 }
178