bertos/mware/heap.c

   1 /**
   2  * \file
   3  * <!--
   4  * This file is part of BeRTOS.
   5  *
   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.
  10  *
  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.
  15  *
  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
  19  *
  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.
  28  *
  29  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
  30  * Copyright 1999,2000,2001 Bernardo Innocenti <bernie@develer.com>
  31  *
  32  * -->
  33  *
  34  * \brief Heap subsystem (public interface).
  35  *
  36  * \version $Id$
  37  *
  38  * \author Bernardo Innocenti <bernie@develer.com>
  39  */
  40
  41 /*#*
  42  *#* $Log$
  43  *#* Revision 1.9  2006/07/19 12:56:27  bernie
  44  *#* Convert to new Doxygen style.
  45  *#*
  46  *#* Revision 1.8  2005/11/04 16:20:02  bernie
  47  *#* Fix reference to README.devlib in header.
  48  *#*
  49  *#* Revision 1.7  2005/04/11 19:10:28  bernie
  50  *#* Include top-level headers from cfg/ subdir.
  51  *#*
  52  *#* Revision 1.6  2004/10/26 09:02:13  bernie
  53  *#* heap_free(): Handle NULL pointers like free(), write documentation.
  54  *#*
  55  *#* Revision 1.5  2004/10/03 20:43:22  bernie
  56  *#* Import changes from sc/firmware.
  57  *#*
  58  *#* Revision 1.1  2004/07/31 16:33:58  rasky
  59  *#* Spostato lo heap da kern/ a mware/
  60  *#*
  61  *#* Revision 1.2  2004/06/03 11:27:09  bernie
  62  *#* Add dual-license information.
  63  *#*
  64  *#* Revision 1.1  2004/05/23 17:27:00  bernie
  65  *#* Import kern/ subdirectory.
  66  *#*
  67  *#*/
  68
  69 #include "heap.h"
  70 #include <string.h>           // memset()
  71 #include <cfg/macros.h>           // IS_POW2()
  72 #include <cfg/debug.h>            // ASSERT()
  73
  74 /* NOTE: struct size must be a 2's power! */
  75 typedef struct _MemChunk
  76 {
  77         struct _MemChunk *next;
  78         size_t size;
  79 } MemChunk;
  80
  81 STATIC_ASSERT(IS_POW2(sizeof(MemChunk)));
  82
  83 #define FREE_FILL_CODE     0xDEAD
  84 #define ALLOC_FILL_CODE    0xBEEF
  85
  86 void heap_init(struct Heap* h, void* memory, size_t size)
  87 {
  88 #ifdef _DEBUG
  89         memset(memory, FREE_FILL_CODE, size);
  90 #endif
  91
  92         /* Initialize heap with a single big chunk */
  93         h->FreeList = (MemChunk *)memory;
  94         h->FreeList->next = NULL;
  95         h->FreeList->size = size;
  96 }
  97
  98
  99 void *heap_allocmem(struct Heap* h, size_t size)
 100 {
 101         MemChunk *chunk, *prev;
 102
 103         /* Round size up to the allocation granularity */
 104         size = ROUND2(size, sizeof(MemChunk));
 105
 106         /* Handle allocations of 0 bytes */
 107         if (!size)
 108                 size = sizeof(MemChunk);
 109
 110         /* Walk on the free list looking for any chunk big enough to
 111          * fit the requested block size.
 112          */
 113         for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList;
 114                 chunk;
 115                 prev = chunk, chunk = chunk->next)
 116         {
 117                 if (chunk->size >= size)
 118                 {
 119                         if (chunk->size == size)
 120                         {
 121                                 /* Just remove this chunk from the free list */
 122                                 prev->next = chunk->next;
 123                                 #ifdef _DEBUG
 124                                         memset(chunk, ALLOC_FILL_CODE, size);
 125                                 #endif
 126                                 return (void *)chunk;
 127                         }
 128                         else
 129                         {
 130                                 /* Allocate from the END of an existing chunk */
 131                                 chunk->size -= size;
 132                                 #ifdef _DEBUG
 133                                         memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size);
 134                                 #endif
 135                                 return (void *)((uint8_t *)chunk + chunk->size);
 136                         }
 137                 }
 138         }
 139
 140         return NULL; /* fail */
 141 }
 142
 143
 144 void heap_freemem(struct Heap* h, void *mem, size_t size)
 145 {
 146         MemChunk *prev;
 147
 148         ASSERT(mem);
 149
 150 #ifdef _DEBUG
 151         memset(mem, FREE_FILL_CODE, size);
 152 #endif
 153
 154         /* Round size up to the allocation granularity */
 155         size = ROUND2(size, sizeof(MemChunk));
 156
 157         /* Handle allocations of 0 bytes */
 158         if (!size)
 159                 size = sizeof(MemChunk);
 160
 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))
 164         {
 165                 /* Insert memory block before the current free list head */
 166                 prev = (MemChunk *)mem;
 167                 prev->next = h->FreeList;
 168                 prev->size = size;
 169                 h->FreeList = prev;
 170         }
 171         else /* Normal case: not the first chunk in the free list */
 172         {
 173                 /*
 174                  * Walk on the free list. Stop at the insertion point (when mem
 175                  * is between prev and prev->next)
 176                  */
 177                 prev = h->FreeList;
 178                 while (prev->next < (MemChunk *)mem && prev->next)
 179                         prev = prev->next;
 180
 181                 /* Make sure mem is not *within* prev */
 182                 ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size);
 183
 184                 /* Should it be merged with previous block? */
 185                 if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem))
 186                 {
 187                         /* Yes */
 188                         prev->size += size;
 189                 }
 190                 else /* not merged with previous chunk */
 191                 {
 192                         MemChunk *curr = (MemChunk*)mem;
 193
 194                         /* insert it after the previous node
 195                          * and move the 'prev' pointer forward
 196                          * for the following operations
 197                          */
 198                         curr->next = prev->next;
 199                         curr->size = size;
 200                         prev->next = curr;
 201
 202                         /* Adjust for the following test */
 203                         prev = curr;
 204                 }
 205         }
 206
 207         /* Also merge with next chunk? */
 208         if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
 209         {
 210                 prev->size += prev->next->size;
 211                 prev->next = prev->next->next;
 212
 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);
 215         }
 216 }
 217
 218 #if CONFIG_HEAP_MALLOC
 219
 220 void *heap_malloc(struct Heap* h, size_t size)
 221 {
 222         size_t *mem;
 223
 224         size += sizeof(size_t);
 225         if ((mem = (size_t*)heap_allocmem(h, size)))
 226                 *mem++ = size;
 227
 228         return mem;
 229 }
 230
 231 void *heap_calloc(struct Heap* h, size_t size)
 232 {
 233         void *mem;
 234
 235         if ((mem = heap_malloc(h, size)))
 236                 memset(mem, 0, size);
 237
 238         return mem;
 239 }
 240
 241 /**
 242  * Free a block of memory, determining its size automatically.
 243  *
 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().
 247  *
 248  * \note If \a mem is a NULL pointer, no operation is performed.
 249  *
 250  * \note Freeing the same memory block twice has undefined behavior.
 251  *
 252  * \note This function works like the ANSI C free().
 253  */
 254 void heap_free(struct Heap *h, void *mem)
 255 {
 256         size_t *_mem = (size_t *)mem;
 257
 258         if (_mem)
 259         {
 260                 --_mem;
 261                 heap_freemem(h, _mem, *_mem);
 262         }
 263 }
 264
 265 #endif /* CONFIG_HEAP_MALLOC */