4 * This file is part of BeRTOS.
6 * Bertos is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
20 * As a special exception, you may use this file as part of a free software
21 * library without restriction. Specifically, if other files instantiate
22 * templates or use macros or inline functions from this file, or you compile
23 * this file and link it with other files to produce an executable, this
24 * file does not by itself cause the resulting executable to be covered by
25 * the GNU General Public License. This exception does not however
26 * invalidate any other reasons why the executable file might be covered by
27 * the GNU General Public License.
29 * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
30 * Copyright 1999,2000,2001 Bernardo Innocenti <bernie@develer.com>
34 * \brief Heap subsystem (public interface).
38 * \author Bernardo Innocenti <bernie@develer.com>
43 *#* Revision 1.9 2006/07/19 12:56:27 bernie
44 *#* Convert to new Doxygen style.
46 *#* Revision 1.8 2005/11/04 16:20:02 bernie
47 *#* Fix reference to README.devlib in header.
49 *#* Revision 1.7 2005/04/11 19:10:28 bernie
50 *#* Include top-level headers from cfg/ subdir.
52 *#* Revision 1.6 2004/10/26 09:02:13 bernie
53 *#* heap_free(): Handle NULL pointers like free(), write documentation.
55 *#* Revision 1.5 2004/10/03 20:43:22 bernie
56 *#* Import changes from sc/firmware.
58 *#* Revision 1.1 2004/07/31 16:33:58 rasky
59 *#* Spostato lo heap da kern/ a mware/
61 *#* Revision 1.2 2004/06/03 11:27:09 bernie
62 *#* Add dual-license information.
64 *#* Revision 1.1 2004/05/23 17:27:00 bernie
65 *#* Import kern/ subdirectory.
70 #include <string.h> // memset()
71 #include <cfg/macros.h> // IS_POW2()
72 #include <cfg/debug.h> // ASSERT()
74 /* NOTE: struct size must be a 2's power! */
75 typedef struct _MemChunk
77 struct _MemChunk *next;
81 STATIC_ASSERT(IS_POW2(sizeof(MemChunk)));
83 #define FREE_FILL_CODE 0xDEAD
84 #define ALLOC_FILL_CODE 0xBEEF
86 void heap_init(struct Heap* h, void* memory, size_t size)
89 memset(memory, FREE_FILL_CODE, size);
92 /* Initialize heap with a single big chunk */
93 h->FreeList = (MemChunk *)memory;
94 h->FreeList->next = NULL;
95 h->FreeList->size = size;
99 void *heap_allocmem(struct Heap* h, size_t size)
101 MemChunk *chunk, *prev;
103 /* Round size up to the allocation granularity */
104 size = ROUND2(size, sizeof(MemChunk));
106 /* Handle allocations of 0 bytes */
108 size = sizeof(MemChunk);
110 /* Walk on the free list looking for any chunk big enough to
111 * fit the requested block size.
113 for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList;
115 prev = chunk, chunk = chunk->next)
117 if (chunk->size >= size)
119 if (chunk->size == size)
121 /* Just remove this chunk from the free list */
122 prev->next = chunk->next;
124 memset(chunk, ALLOC_FILL_CODE, size);
126 return (void *)chunk;
130 /* Allocate from the END of an existing chunk */
133 memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size);
135 return (void *)((uint8_t *)chunk + chunk->size);
140 return NULL; /* fail */
144 void heap_freemem(struct Heap* h, void *mem, size_t size)
151 memset(mem, FREE_FILL_CODE, size);
154 /* Round size up to the allocation granularity */
155 size = ROUND2(size, sizeof(MemChunk));
157 /* Handle allocations of 0 bytes */
159 size = sizeof(MemChunk);
161 /* Special case: first chunk in the free list */
162 ASSERT((uint8_t*)mem != (uint8_t*)h->FreeList);
163 if (((uint8_t *)mem) < ((uint8_t *)h->FreeList))
165 /* Insert memory block before the current free list head */
166 prev = (MemChunk *)mem;
167 prev->next = h->FreeList;
171 else /* Normal case: not the first chunk in the free list */
174 * Walk on the free list. Stop at the insertion point (when mem
175 * is between prev and prev->next)
178 while (prev->next < (MemChunk *)mem && prev->next)
181 /* Make sure mem is not *within* prev */
182 ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size);
184 /* Should it be merged with previous block? */
185 if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem))
190 else /* not merged with previous chunk */
192 MemChunk *curr = (MemChunk*)mem;
194 /* insert it after the previous node
195 * and move the 'prev' pointer forward
196 * for the following operations
198 curr->next = prev->next;
202 /* Adjust for the following test */
207 /* Also merge with next chunk? */
208 if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
210 prev->size += prev->next->size;
211 prev->next = prev->next->next;
213 /* There should be only one merge opportunity, becuase we always merge on free */
214 ASSERT((uint8_t*)prev + prev->size != (uint8_t*)prev->next);
218 #if CONFIG_HEAP_MALLOC
220 void *heap_malloc(struct Heap* h, size_t size)
224 size += sizeof(size_t);
225 if ((mem = (size_t*)heap_allocmem(h, size)))
231 void *heap_calloc(struct Heap* h, size_t size)
235 if ((mem = heap_malloc(h, size)))
236 memset(mem, 0, size);
242 * Free a block of memory, determining its size automatically.
244 * \param h Heap from which the block was allocated.
245 * \param mem Pointer to a block of memory previously allocated with
246 * either heap_malloc() or heap_calloc().
248 * \note If \a mem is a NULL pointer, no operation is performed.
250 * \note Freeing the same memory block twice has undefined behavior.
252 * \note This function works like the ANSI C free().
254 void heap_free(struct Heap *h, void *mem)
256 size_t *_mem = (size_t *)mem;
261 heap_freemem(h, _mem, *_mem);
265 #endif /* CONFIG_HEAP_MALLOC */