1 /*
2 Copyright (c) 2012, Broadcom Europe Ltd
3 All rights reserved.
4
5 Redistribution and use in source and binary forms, with or without
6 modification, are permitted provided that the following conditions are met:
7 * Redistributions of source code must retain the above copyright
8 notice, this list of conditions and the following disclaimer.
9 * 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 * Neither the name of the copyright holder nor the
13 names of its contributors may be used to endorse or promote products
14 derived from this software without specific prior written permission.
15
16 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY
20 DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 /*=============================================================================
29 VideoCore OS Abstraction Layer - event flags implemented via a semaphore
30 =============================================================================*/
31
32 #ifndef VCOS_GENERIC_BLOCKPOOL_H
33 #define VCOS_GENERIC_BLOCKPOOL_H
34
35 /**
36 * \file
37 *
38 * This provides a generic, thread safe implementation of a VCOS block pool
39 * fixed size memory allocator.
40 */
41
42 #ifdef __cplusplus
43 extern "C" {
44 #endif
45
46 #include "interface/vcos/vcos_types.h"
47
48 /** Bits 0 to (VCOS_BLOCKPOOL_SUBPOOL_BITS - 1) are used to store the
49 * subpool id. */
50 #define VCOS_BLOCKPOOL_SUBPOOL_BITS 3
51 #define VCOS_BLOCKPOOL_MAX_SUBPOOLS (1 << VCOS_BLOCKPOOL_SUBPOOL_BITS)
52
53 /* Make zero an invalid handle at the cost of decreasing the maximum
54 * number of blocks (2^28) by 1. Alternatively, a spare bit could be
55 * used to indicated valid blocks but there are likely to be better
56 * uses for spare bits. e.g. allowing more subpools
57 */
58 #define INDEX_OFFSET 1
59
60 #define VCOS_BLOCKPOOL_HANDLE_GET_INDEX(h) \
61 (((h) >> VCOS_BLOCKPOOL_SUBPOOL_BITS) - INDEX_OFFSET)
62
63 #define VCOS_BLOCKPOOL_HANDLE_GET_SUBPOOL(h) \
64 ((h) & ((1 << VCOS_BLOCKPOOL_SUBPOOL_BITS) - 1))
65
66 #define VCOS_BLOCKPOOL_HANDLE_CREATE(i,s) \
67 ((((i) + INDEX_OFFSET) << VCOS_BLOCKPOOL_SUBPOOL_BITS) | (s))
68
69 #define VCOS_BLOCKPOOL_INVALID_HANDLE 0
70 #define VCOS_BLOCKPOOL_ALIGN_DEFAULT sizeof(unsigned long)
71 #define VCOS_BLOCKPOOL_FLAG_NONE 0
72
73 typedef struct VCOS_BLOCKPOOL_HEADER_TAG
74 {
75 /* Blocks either refer to to the pool if they are allocated
76 * or the free list if they are available.
77 */
78 union {
79 struct VCOS_BLOCKPOOL_HEADER_TAG *next;
80 struct VCOS_BLOCKPOOL_SUBPOOL_TAG* subpool;
81 } owner;
82 } VCOS_BLOCKPOOL_HEADER_T;
83
84 typedef struct VCOS_BLOCKPOOL_SUBPOOL_TAG
85 {
86 /** VCOS_BLOCKPOOL_SUBPOOL_MAGIC */
87 uint32_t magic;
88 VCOS_BLOCKPOOL_HEADER_T* free_list;
89 /* The start of the pool memory */
90 void *mem;
91 /* Address of the first block header */
92 void *start;
93 /* The end of the subpool */
94 void *end;
95 /** The number of blocks in this sub-pool */
96 VCOS_UNSIGNED num_blocks;
97 /** Current number of available blocks in this sub-pool */
98 VCOS_UNSIGNED available_blocks;
99 /** Pointers to the pool that owns this sub-pool */
100 struct VCOS_BLOCKPOOL_TAG* owner;
101 /** Define properties such as memory ownership */
102 uint32_t flags;
103 } VCOS_BLOCKPOOL_SUBPOOL_T;
104
105 typedef struct VCOS_BLOCKPOOL_TAG
106 {
107 /** VCOS_BLOCKPOOL_MAGIC */
108 uint32_t magic;
109 /** Thread safety for Alloc, Free, Delete, Stats */
110 VCOS_MUTEX_T mutex;
111 /** Alignment of block data pointers */
112 VCOS_UNSIGNED align;
113 /** Flags for future use e.g. cache options */
114 VCOS_UNSIGNED flags;
115 /** The size of the block data */
116 size_t block_data_size;
117 /** Block size inc overheads */
118 size_t block_size;
119 /** Name for debugging */
120 const char *name;
121 /* The number of subpools that may be used */
122 VCOS_UNSIGNED num_subpools;
123 /** Number of blocks in each dynamically allocated subpool */
124 VCOS_UNSIGNED num_extension_blocks;
125 /** Array of subpools. Subpool zero is is not deleted until the pool is
126 * destroed. If the index of the pool is < num_subpools and
127 * subpool[index.mem] is null then the subpool entry is valid but
128 * "not currently allocated" */
129 VCOS_BLOCKPOOL_SUBPOOL_T subpools[VCOS_BLOCKPOOL_MAX_SUBPOOLS];
130 } VCOS_BLOCKPOOL_T;
131
132 #define VCOS_BLOCKPOOL_ROUND_UP(x,s) (((x) + ((s) - 1)) & ~((s) - 1))
133 /**
134 * Calculates the size in bytes required for a block pool containing
135 * num_blocks of size block_size plus any overheads.
136 *
137 * The block pool header (VCOS_BLOCKPOOL_T) is allocated separately
138 *
139 * Overheads:
140 * block_size + header must be rounded up to meet the required alignment
141 * The start of the first block may need to be up to align bytes
142 * into the given buffer because statically allocated buffers within structures
143 * are not guaranteed to be aligned as required.
144 */
145 #define VCOS_BLOCKPOOL_SIZE(num_blocks, block_size, align) \
146 ((VCOS_BLOCKPOOL_ROUND_UP((block_size) + (align >= 4096 ? 32 : 0) + sizeof(VCOS_BLOCKPOOL_HEADER_T), \
147 (align)) * (num_blocks)) + (align))
148
149 /**
150 * Sanity check to verify whether a handle is potentially a blockpool handle
151 * when the pool pointer is not available.
152 *
153 * If the pool pointer is available use vcos_blockpool_elem_to_handle instead.
154 *
155 * @param handle the handle to verify
156 * @param max_blocks the expected maximum number of block in the pool
157 * that the handle belongs to.
158 */
159 #define VCOS_BLOCKPOOL_IS_VALID_HANDLE_FORMAT(handle, max_blocks) \
160 ((handle) != VCOS_BLOCKPOOL_INVALID_HANDLE \
161 && VCOS_BLOCKPOOL_HANDLE_GET_INDEX((handle)) < (max_blocks))
162
163 VCOSPRE_
164 VCOS_STATUS_T VCOSPOST_ vcos_generic_blockpool_init(VCOS_BLOCKPOOL_T *pool,
165 VCOS_UNSIGNED num_blocks, VCOS_UNSIGNED block_size,
166 void *start, VCOS_UNSIGNED pool_size,
167 VCOS_UNSIGNED align, VCOS_UNSIGNED flags,
168 const char *name);
169
170 VCOSPRE_
171 VCOS_STATUS_T VCOSPOST_ vcos_generic_blockpool_create_on_heap(
172 VCOS_BLOCKPOOL_T *pool, VCOS_UNSIGNED num_blocks,
173 VCOS_UNSIGNED block_size,
174 VCOS_UNSIGNED align, VCOS_UNSIGNED flags,
175 const char *name);
176
177 VCOSPRE_
178 VCOS_STATUS_T VCOSPOST_ vcos_generic_blockpool_extend(VCOS_BLOCKPOOL_T *pool,
179 VCOS_UNSIGNED num_extensions, VCOS_UNSIGNED num_blocks);
180
181 VCOSPRE_ void VCOSPOST_ *vcos_generic_blockpool_alloc(VCOS_BLOCKPOOL_T *pool);
182
183 VCOSPRE_ void VCOSPOST_ *vcos_generic_blockpool_calloc(VCOS_BLOCKPOOL_T *pool);
184
185 VCOSPRE_ void VCOSPOST_ vcos_generic_blockpool_free(void *block);
186
187 VCOSPRE_
188 VCOS_UNSIGNED VCOSPOST_ vcos_generic_blockpool_available_count(
189 VCOS_BLOCKPOOL_T *pool);
190
191 VCOSPRE_
192 VCOS_UNSIGNED VCOSPOST_ vcos_generic_blockpool_used_count(
193 VCOS_BLOCKPOOL_T *pool);
194
195 VCOSPRE_ void VCOSPOST_ vcos_generic_blockpool_delete(VCOS_BLOCKPOOL_T *pool);
196
197 VCOSPRE_ uint32_t VCOSPOST_ vcos_generic_blockpool_elem_to_handle(void *block);
198
199 VCOSPRE_ void VCOSPOST_
200 *vcos_generic_blockpool_elem_from_handle(
201 VCOS_BLOCKPOOL_T *pool, uint32_t handle);
202
203 VCOSPRE_ uint32_t VCOSPOST_
204 vcos_generic_blockpool_is_valid_elem(
205 VCOS_BLOCKPOOL_T *pool, const void *block);
206 #if defined(VCOS_INLINE_BODIES)
207
208 VCOS_INLINE_IMPL
vcos_blockpool_init(VCOS_BLOCKPOOL_T * pool,VCOS_UNSIGNED num_blocks,VCOS_UNSIGNED block_size,void * start,VCOS_UNSIGNED pool_size,VCOS_UNSIGNED align,VCOS_UNSIGNED flags,const char * name)209 VCOS_STATUS_T vcos_blockpool_init(VCOS_BLOCKPOOL_T *pool,
210 VCOS_UNSIGNED num_blocks, VCOS_UNSIGNED block_size,
211 void *start, VCOS_UNSIGNED pool_size,
212 VCOS_UNSIGNED align, VCOS_UNSIGNED flags, const char *name)
213 {
214 return vcos_generic_blockpool_init(pool, num_blocks, block_size,
215 start, pool_size, align, flags, name);
216 }
217
218 VCOS_INLINE_IMPL
vcos_blockpool_create_on_heap(VCOS_BLOCKPOOL_T * pool,VCOS_UNSIGNED num_blocks,VCOS_UNSIGNED block_size,VCOS_UNSIGNED align,VCOS_UNSIGNED flags,const char * name)219 VCOS_STATUS_T vcos_blockpool_create_on_heap(VCOS_BLOCKPOOL_T *pool,
220 VCOS_UNSIGNED num_blocks, VCOS_UNSIGNED block_size,
221 VCOS_UNSIGNED align, VCOS_UNSIGNED flags, const char *name)
222 {
223 return vcos_generic_blockpool_create_on_heap(
224 pool, num_blocks, block_size, align, flags, name);
225 }
226
227 VCOS_INLINE_IMPL
vcos_blockpool_extend(VCOS_BLOCKPOOL_T * pool,VCOS_UNSIGNED num_extensions,VCOS_UNSIGNED num_blocks)228 VCOS_STATUS_T VCOSPOST_ vcos_blockpool_extend(VCOS_BLOCKPOOL_T *pool,
229 VCOS_UNSIGNED num_extensions, VCOS_UNSIGNED num_blocks)
230 {
231 return vcos_generic_blockpool_extend(pool, num_extensions, num_blocks);
232 }
233
234 VCOS_INLINE_IMPL
vcos_blockpool_alloc(VCOS_BLOCKPOOL_T * pool)235 void *vcos_blockpool_alloc(VCOS_BLOCKPOOL_T *pool)
236 {
237 return vcos_generic_blockpool_alloc(pool);
238 }
239
240 VCOS_INLINE_IMPL
vcos_blockpool_calloc(VCOS_BLOCKPOOL_T * pool)241 void *vcos_blockpool_calloc(VCOS_BLOCKPOOL_T *pool)
242 {
243 return vcos_generic_blockpool_calloc(pool);
244 }
245
246 VCOS_INLINE_IMPL
vcos_blockpool_free(void * block)247 void vcos_blockpool_free(void *block)
248 {
249 vcos_generic_blockpool_free(block);
250 }
251
252 VCOS_INLINE_IMPL
vcos_blockpool_available_count(VCOS_BLOCKPOOL_T * pool)253 VCOS_UNSIGNED vcos_blockpool_available_count(VCOS_BLOCKPOOL_T *pool)
254 {
255 return vcos_generic_blockpool_available_count(pool);
256 }
257
258 VCOS_INLINE_IMPL
vcos_blockpool_used_count(VCOS_BLOCKPOOL_T * pool)259 VCOS_UNSIGNED vcos_blockpool_used_count(VCOS_BLOCKPOOL_T *pool)
260 {
261 return vcos_generic_blockpool_used_count(pool);
262 }
263
264 VCOS_INLINE_IMPL
vcos_blockpool_delete(VCOS_BLOCKPOOL_T * pool)265 void vcos_blockpool_delete(VCOS_BLOCKPOOL_T *pool)
266 {
267 vcos_generic_blockpool_delete(pool);
268 }
269
270 VCOS_INLINE_IMPL
vcos_blockpool_elem_to_handle(void * block)271 uint32_t vcos_blockpool_elem_to_handle(void *block)
272 {
273 return vcos_generic_blockpool_elem_to_handle(block);
274 }
275
276 VCOS_INLINE_IMPL
vcos_blockpool_elem_from_handle(VCOS_BLOCKPOOL_T * pool,uint32_t handle)277 void *vcos_blockpool_elem_from_handle(VCOS_BLOCKPOOL_T *pool, uint32_t handle)
278 {
279 return vcos_generic_blockpool_elem_from_handle(pool, handle);
280 }
281
282 VCOS_INLINE_IMPL
vcos_blockpool_is_valid_elem(VCOS_BLOCKPOOL_T * pool,const void * block)283 uint32_t vcos_blockpool_is_valid_elem(VCOS_BLOCKPOOL_T *pool, const void *block)
284 {
285 return vcos_generic_blockpool_is_valid_elem(pool, block);
286 }
287 #endif /* VCOS_INLINE_BODIES */
288
289
290 #ifdef __cplusplus
291 }
292 #endif
293 #endif /* VCOS_GENERIC_BLOCKPOOL_H */
294
295