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 #include "heap.h"
  42
  43 #include <cfg/macros.h>           // IS_POW2()
  44 #include <cfg/debug.h>            // ASSERT()
  45
  46 #include <string.h>           // memset()
  47
  48 /* NOTE: struct size must be a 2's power! */
  49 typedef struct _MemChunk
  50 {
  51         struct _MemChunk *next;
  52         size_t size;
  53 } MemChunk;
  54
  55 STATIC_ASSERT(IS_POW2(sizeof(MemChunk)));
  56
  57 #define FREE_FILL_CODE     0xDEAD
  58 #define ALLOC_FILL_CODE    0xBEEF
  59
  60 void heap_init(struct Heap* h, void* memory, size_t size)
  61 {
  62 #ifdef _DEBUG
  63         memset(memory, FREE_FILL_CODE, size);
  64 #endif
  65
  66         /* Initialize heap with a single big chunk */
  67         h->FreeList = (MemChunk *)memory;
  68         h->FreeList->next = NULL;
  69         h->FreeList->size = size;
  70 }
  71
  72
  73 void *heap_allocmem(struct Heap* h, size_t size)
  74 {
  75         MemChunk *chunk, *prev;
  76
  77         /* Round size up to the allocation granularity */
  78         size = ROUND2(size, sizeof(MemChunk));
  79
  80         /* Handle allocations of 0 bytes */
  81         if (!size)
  82                 size = sizeof(MemChunk);
  83
  84         /* Walk on the free list looking for any chunk big enough to
  85          * fit the requested block size.
  86          */
  87         for (prev = (MemChunk *)&h->FreeList, chunk = h->FreeList;
  88                 chunk;
  89                 prev = chunk, chunk = chunk->next)
  90         {
  91                 if (chunk->size >= size)
  92                 {
  93                         if (chunk->size == size)
  94                         {
  95                                 /* Just remove this chunk from the free list */
  96                                 prev->next = chunk->next;
  97                                 #ifdef _DEBUG
  98                                         memset(chunk, ALLOC_FILL_CODE, size);
  99                                 #endif
 100                                 return (void *)chunk;
 101                         }
 102                         else
 103                         {
 104                                 /* Allocate from the END of an existing chunk */
 105                                 chunk->size -= size;
 106                                 #ifdef _DEBUG
 107                                         memset((uint8_t *)chunk + chunk->size, ALLOC_FILL_CODE, size);
 108                                 #endif
 109                                 return (void *)((uint8_t *)chunk + chunk->size);
 110                         }
 111                 }
 112         }
 113
 114         return NULL; /* fail */
 115 }
 116
 117
 118 void heap_freemem(struct Heap* h, void *mem, size_t size)
 119 {
 120         MemChunk *prev;
 121         ASSERT(mem);
 122
 123 #ifdef _DEBUG
 124         memset(mem, FREE_FILL_CODE, size);
 125 #endif
 126
 127         /* Round size up to the allocation granularity */
 128         size = ROUND2(size, sizeof(MemChunk));
 129
 130         /* Handle allocations of 0 bytes */
 131         if (!size)
 132                 size = sizeof(MemChunk);
 133
 134         /* Special case: first chunk in the free list */
 135         ASSERT((uint8_t*)mem != (uint8_t*)h->FreeList);
 136         if (((uint8_t *)mem) < ((uint8_t *)h->FreeList))
 137         {
 138                 /* Insert memory block before the current free list head */
 139                 prev = (MemChunk *)mem;
 140                 prev->next = h->FreeList;
 141                 prev->size = size;
 142                 h->FreeList = prev;
 143         }
 144         else /* Normal case: not the first chunk in the free list */
 145         {
 146                 /*
 147                  * Walk on the free list. Stop at the insertion point (when mem
 148                  * is between prev and prev->next)
 149                  */
 150                 prev = h->FreeList;
 151                 while (prev->next < (MemChunk *)mem && prev->next)
 152                         prev = prev->next;
 153
 154                 /* Make sure mem is not *within* prev */
 155                 ASSERT((uint8_t*)mem >= (uint8_t*)prev + prev->size);
 156
 157                 /* Should it be merged with previous block? */
 158                 if (((uint8_t *)prev) + prev->size == ((uint8_t *)mem))
 159                 {
 160                         /* Yes */
 161                         prev->size += size;
 162                 }
 163                 else /* not merged with previous chunk */
 164                 {
 165                         MemChunk *curr = (MemChunk*)mem;
 166
 167                         /* insert it after the previous node
 168                          * and move the 'prev' pointer forward
 169                          * for the following operations
 170                          */
 171                         curr->next = prev->next;
 172                         curr->size = size;
 173                         prev->next = curr;
 174
 175                         /* Adjust for the following test */
 176                         prev = curr;
 177                 }
 178         }
 179
 180         /* Also merge with next chunk? */
 181         if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
 182         {
 183                 prev->size += prev->next->size;
 184                 prev->next = prev->next->next;
 185
 186                 /* There should be only one merge opportunity, becuase we always merge on free */
 187                 ASSERT((uint8_t*)prev + prev->size != (uint8_t*)prev->next);
 188         }
 189 }
 190
 191 #if CONFIG_HEAP_MALLOC
 192
 193 void *heap_malloc(struct Heap* h, size_t size)
 194 {
 195         size_t *mem;
 196
 197         size += sizeof(size_t);
 198         if ((mem = (size_t*)heap_allocmem(h, size)))
 199                 *mem++ = size;
 200
 201         return mem;
 202 }
 203
 204 void *heap_calloc(struct Heap* h, size_t size)
 205 {
 206         void *mem;
 207
 208         if ((mem = heap_malloc(h, size)))
 209                 memset(mem, 0, size);
 210
 211         return mem;
 212 }
 213
 214 /**
 215  * Free a block of memory, determining its size automatically.
 216  *
 217  * \param h    Heap from which the block was allocated.
 218  * \param mem  Pointer to a block of memory previously allocated with
 219  *             either heap_malloc() or heap_calloc().
 220  *
 221  * \note If \a mem is a NULL pointer, no operation is performed.
 222  *
 223  * \note Freeing the same memory block twice has undefined behavior.
 224  *
 225  * \note This function works like the ANSI C free().
 226  */
 227 void heap_free(struct Heap *h, void *mem)
 228 {
 229         size_t *_mem = (size_t *)mem;
 230
 231         if (_mem)
 232         {
 233                 --_mem;
 234                 heap_freemem(h, _mem, *_mem);
 235         }
 236 }
 237
 238 #endif /* CONFIG_HEAP_MALLOC */