1 /**
2 * \file
3 *
4 * \brief Memory bag allocator
5 *
6 * Copyright (C) 2012-2015 Atmel Corporation. All rights reserved.
7 *
8 * \asf_license_start
9 *
10 * \page License
11 *
12 * Redistribution and use in source and binary forms, with or without
13 * modification, are permitted provided that the following conditions are met:
14 *
15 * 1. Redistributions of source code must retain the above copyright notice,
16 * this list of conditions and the following disclaimer.
17 *
18 * 2. Redistributions in binary form must reproduce the above copyright notice,
19 * this list of conditions and the following disclaimer in the documentation
20 * and/or other materials provided with the distribution.
21 *
22 * 3. The name of Atmel may not be used to endorse or promote products derived
23 * from this software without specific prior written permission.
24 *
25 * 4. This software may only be redistributed and used in connection with an
26 * Atmel microcontroller product.
27 *
28 * THIS SOFTWARE IS PROVIDED BY ATMEL "AS IS" AND ANY EXPRESS OR IMPLIED
29 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF
30 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NON-INFRINGEMENT ARE
31 * EXPRESSLY AND SPECIFICALLY DISCLAIMED. IN NO EVENT SHALL ATMEL BE LIABLE FOR
32 * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
33 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
34 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
35 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
36 * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN
37 * ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
38 * POSSIBILITY OF SUCH DAMAGE.
39 *
40 * \asf_license_stop
41 *
42 */
43 /*
44 * Support and FAQ: visit <a href="http://www.atmel.com/design-support/">Atmel Support</a>
45 */
46
47 #include <compiler.h>
48 #include <membag.h>
49 #include "conf_membag.h"
50
51 /** \internal
52 *
53 * Retrieves the number of elements in a statically declared array.
54 */
55 #define ARRAY_LEN(a) (sizeof(a) / sizeof((a)[0]))
56
57 /**
58 * Static address space which is split up into usable chunks by membag.
59 * For configuration details, see \ref membag_list.
60 */
61 static uint8_t membag_pool[CONF_MEMBAG_POOL_SIZE];
62
63 /**
64 * Internal structure used by membag to keep track of memory,
65 * with maximum 32 blocks per membag.
66 */
67 struct membag {
68 /*! Number of bytes per block in this bag. */
69 size_t block_size;
70 /*! Total number of blocks. */
71 size_t num_blocks;
72 /*! Pointer to start of this bag. */
73 uintptr_t start;
74 /*! Pointer to end of this bag. */
75 uintptr_t end;
76 /*! 32-bit integer used to keep track of allocations. */
77 uint32_t allocated;
78 /*! Counter for number of free blocks. */
79 uint8_t blocks_free;
80 };
81
82 /**
83 * Array of available membags, provided by the user in the applications
84 * conf_membag.h header file. Example:
85 *
86 * \code
87 #define CONF_MEMBAG_ARRAY \
88 MEMBAG(32, 4), \
89 MEMBAG(16, 2),
90
91 #define CONF_MEMBAG_POOL_SIZE \
92 MEMBAG_SIZE(32, 4) + \
93 MEMBAG_SIZE(16, 2)
94 \endcode
95 *
96 */
97 static struct membag membag_list[] = {
98 CONF_MEMBAG_ARRAY
99 };
100
101 /**
102 * \brief Initialize the membag system.
103 *
104 * This function sets up the membags, allocates memory from the memory pool, and
105 * initializes them. Any existing allocations are destroyed and all memory pools
106 * reset to their initial states.
107 */
membag_init(void)108 void membag_init(void)
109 {
110 uint8_t i;
111 uintptr_t poolptr;
112
113 poolptr = (uintptr_t)membag_pool;
114
115 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
116 Assert(membag_list[i].block_size > 0);
117 Assert(membag_list[i].num_blocks > 0);
118 Assert(membag_list[i].num_blocks <= 32);
119
120 membag_list[i].start = poolptr;
121 poolptr += (membag_list[i].block_size *
122 membag_list[i].num_blocks);
123 membag_list[i].end = poolptr;
124 membag_list[i].blocks_free = membag_list[i].num_blocks;
125
126 /* Mark all blocks as free. */
127 membag_list[i].allocated = 0;
128 }
129 }
130
131 /**
132 * \brief Determine the total remaining free memory from all membags.
133 *
134 * \return Sum of all free memory, in bytes.
135 */
membag_get_total_free(void)136 size_t membag_get_total_free(void)
137 {
138 uint8_t i;
139 size_t total_free = 0;
140
141 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
142 total_free += membag_list[i].blocks_free *
143 membag_list[i].block_size;
144 }
145
146 return total_free;
147 }
148
149 /**
150 * \brief Determine the total memory from all membags.
151 *
152 * \return Sum of all blocks in all bags, in bytes.
153 */
membag_get_total(void)154 size_t membag_get_total(void)
155 {
156 uint8_t i;
157 size_t total = 0;
158
159 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
160 total += membag_list[i].num_blocks * membag_list[i].block_size;
161 }
162
163 return total;
164 }
165
166 /**
167 * \brief Determine the smallest available block size.
168 *
169 * Calculates the smallest block which can be allocated by the Membag allocator
170 * if requested. Allocations larger than this amount are not guaranteed to
171 * complete successfully.
172 *
173 * \return Size of the smallest available block, in bytes.
174 */
membag_get_smallest_free_block_size(void)175 size_t membag_get_smallest_free_block_size(void)
176 {
177 uint8_t i;
178 struct membag *smallest_bag = NULL;
179
180 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
181 if (membag_list[i].blocks_free == 0) {
182 continue;
183 }
184
185 if (!smallest_bag ||
186 (smallest_bag->block_size > membag_list[i].block_size)) {
187 smallest_bag = &membag_list[i];
188 }
189 }
190
191 if (smallest_bag) {
192 return smallest_bag->block_size;
193 }
194
195 return 0;
196 }
197
198 /**
199 * \brief Determine the largest available block size.
200 *
201 * Calculates the largest block which can be allocated by the Membag allocator
202 * if requested. Allocations larger than this amount are guaranteed to fail.
203 *
204 * \return Size of the largest available block, in bytes.
205 */
membag_get_largest_free_block_size(void)206 size_t membag_get_largest_free_block_size(void)
207 {
208 uint8_t i;
209 struct membag *largest_bag = NULL;
210
211 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
212 if (membag_list[i].blocks_free == 0) {
213 continue;
214 }
215
216 if (!largest_bag ||
217 (largest_bag->block_size < membag_list[i].block_size)) {
218 largest_bag = &membag_list[i];
219 }
220 }
221
222 if (largest_bag) {
223 return largest_bag->block_size;
224 }
225
226 return 0;
227 }
228
229 /**
230 * \brief Allocate a memory block via a block from the Membag pool
231 *
232 * Allocates memory to the user from one of the available Membag pools. Each
233 * Membag pool is examined in sequence, and the first free block of sufficient
234 * size (if any) is chosen for the allocation. Allocated blocks persist until
235 * either the Membag module is re-initialized, or an allocation block is freed
236 * via \ref membag_free().
237 *
238 * \note The execution cycle time for this function is not deterministic; each
239 * allocation request may take a variable amount of cycles to complete.
240 *
241 * \param size Size of memory block requested, in bytes
242 *
243 * \return Pointer to the start of an allocated block if one was found in the
244 * Membag pool, NULL if no suitable block was found.
245 */
membag_alloc(const size_t size)246 void *membag_alloc(const size_t size)
247 {
248 uint8_t i;
249 struct membag *smallest_bag = NULL;
250 uintptr_t p;
251
252 /* Find the smallest available block size big enough for the requested
253 * memory chunk size. */
254 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
255 if (membag_list[i].blocks_free == 0) {
256 continue;
257 }
258
259 if (membag_list[i].block_size >= size) {
260 if (!smallest_bag ||
261 (smallest_bag->block_size > membag_list[i].block_size)) {
262 smallest_bag = &membag_list[i];
263 }
264 }
265 }
266
267 /* We return the first available block in the bag that has one, and if
268 * there is none, we return NULL.
269 */
270 if (smallest_bag) {
271 /* We know that there is a free block within the membag's
272 * memory, and we simply return the first one available.
273 */
274 p = smallest_bag->start;
275
276 for (i = 0; i < smallest_bag->num_blocks; i++) {
277 /* Check the allocation byte to see whether the block is
278 * in use. */
279 if (!(smallest_bag->allocated & ((uint32_t)1 << i))) {
280 /* It is free, set it to used. */
281 smallest_bag->allocated |= ((uint32_t)1 << i);
282 smallest_bag->blocks_free--;
283
284 return (void *)(p);
285 }
286
287 p += smallest_bag->block_size;
288 }
289 }
290
291 /* There is no available memory. Return NULL. */
292 return NULL;
293 }
294
295 /**
296 * \brief Free a previously allocated memory block from the Membag pool
297 *
298 * This function frees memory which has been allocated previously via a
299 * successful call to \ref membag_alloc(). Once deallocated, the given pointer
300 * is no longer valid and should not be used in the user application unless
301 * re-allocated.
302 *
303 * \note The execution cycle time for this function is not deterministic; each
304 * allocation request may take a variable amount of cycles to complete.
305 *
306 * \param ptr Pointer to an allocated memory block to free
307 */
membag_free(const void * ptr)308 void membag_free(const void *ptr)
309 {
310 uint8_t i;
311 uintptr_t p = (uintptr_t)ptr;
312 uint8_t block_index;
313
314 for (i = 0; i < ARRAY_LEN(membag_list); i++) {
315 if (p >= membag_list[i].start && p < membag_list[i].end) {
316 block_index = (p - membag_list[i].start) / membag_list[i].block_size;
317
318 /* Mark the memory as free. */
319 membag_list[i].allocated &= ~((uint32_t)1 << block_index);
320 membag_list[i].blocks_free++;
321
322 return;
323 }
324 }
325 }
326