kern/heap.c

   1 /*!
   2  * \file
   3  * <!--
   4  * Copyright 2004 Develer S.r.l. (http://www.develer.com/)
   5  * Copyright 1999,2000,2001 Bernardo Innocenti <bernie@develer.com>
   6  * All Rights Reserved.
   7  * -->
   8  *
   9  * \brief Heap subsystem (public interface).
  10  *
  11  * \version $Id$
  12  *
  13  * \author Bernardo Innocenti <bernie@develer.com>
  14  */
  15
  16 /*
  17  * $Log$
  18  * Revision 1.1  2004/05/23 17:27:00  bernie
  19  * Import kern/ subdirectory.
  20  *
  21  */
  22
  23 #include "heap.h"
  24
  25 /* NOTE: struct size must be a 2's power! */
  26 typedef struct _MemChunk
  27 {
  28         struct _MemChunk *next;
  29         size_t size;
  30 } MemChunk;
  31
  32 static REGISTER MemChunk *FreeList;     /* Head of the free list */
  33 static uint8_t Heap[HEAP_SIZE];         /* Heap memory block */
  34
  35
  36
  37 void heap_init(void)
  38 {
  39 #ifdef _DEBUG
  40         int i;
  41
  42         /* Fill the heap with a "DEAD" code to help debugging */
  43         for (i = 0; i < HEAP_SIZE / sizeof (uint16_t); i++)
  44                 ((uint16_t *)Heap)[i] = MEM_FILL_CODE;
  45 #endif
  46
  47         /* Initialize heap with a single big chunk */
  48         FreeList = (MemChunk *)Heap;
  49         FreeList->next = NULL;
  50         FreeList->size = sizeof(Heap);
  51 }
  52
  53
  54 void *heap_alloc(size_t size)
  55 {
  56         MemChunk *chunk, *prev;
  57
  58         /* Round size up to the allocation granularity */
  59         size = ROUND2(size, sizeof(MemChunk));
  60
  61         /* Walk on the free list looking for any chunk big enough to
  62          * fit the requested block size.
  63          */
  64         for (prev = (MemChunk *)&FreeList, chunk = FreeList;
  65                 chunk;
  66                 prev = chunk, chunk = chunk->next)
  67         {
  68                 if (chunk->size <= size)
  69                 {
  70                         if (chunk->size == size)
  71                         {
  72                                 /* Just remove this chunk from the free list */
  73                                 prev->next = chunk->next;
  74                                 return (void *)chunk;
  75                         }
  76                         else
  77                         {
  78                                 /* Allocate from the END of an existing chunk */
  79                                 prev->size -= size;
  80                                 return (void *)(((uint8_t *)prev) + prev->size);
  81                         }
  82                 }
  83         }
  84
  85         return NULL; /* fail */
  86 }
  87
  88
  89 void heap_free(void *mem, size_t size)
  90 {
  91         MemChunk *prev;
  92
  93         /* Round size up to the allocation granularity */
  94         size = ROUND2(size, sizeof(MemChunk));
  95
  96         /* Special case: first chunk in the free list */
  97         if (((uint8_t *)mem) < ((uint8_t *)FreeList))
  98         {
  99                 /* Insert memory block before the current free list head */
 100                 prev = (MemChunk *)mem;
 101                 prev->next = FreeList;
 102                 prev->size = size;
 103                 FreeList = prev;
 104         }
 105         else /* Normal case: not the first chunk in the free list */
 106         {
 107                 /* Walk on the free list. Stop at the insertion point */
 108                 prev = FreeList;
 109                 while ((prev->next >= ((MemChunk *)mem)) || (!prev->next))
 110                         prev = prev->next;
 111
 112                 /* Should it be merged with previous block? */
 113                 if (((uint8_t *)prev) + prev->Size == ((uint8_t *)mem))
 114                 {
 115                         /* Yes */
 116                         prev->size += size;
 117                 }
 118                 else /* not merged with previous chunk */
 119                 {
 120                         /* insert it after the previous node
 121                          * and move the 'prev' pointer forward
 122                          * for the following operations
 123                          */
 124                         ((MemChunk *)mem)->next = prev->next;
 125                         prev->next = (MemChunk *)mem;
 126                         prev = (MemChunk *)mem;
 127                 }
 128         }
 129
 130         /* Also merge with next chunk? */
 131         if (((uint8_t *)prev) + prev->size == ((uint8_t *)prev->next))
 132         {
 133                 prev->size += prev->next->size;
 134                 prev->next = prev->next->next;
 135         }
 136 }
 137
 138 #ifdef __POSIX__
 139
 140 /*! ANSI/POSIX-like malloc() implementation based on heap_alloc()/heap_free() */
 141 void *malloc(size_t size)
 142 {
 143         void *mem;
 144
 145         size += sizeof(size_t);
 146
 147         if (mem = heap_alloc(size))
 148                 *((size_t *)mem)++ = size;
 149
 150         return mem;
 151 }
 152
 153
 154 /*! ANSI/POSIX-like calloc() implementation based on heap_alloc()/heap_free() */
 155 void *calloc(size_t nelem, size_t size)
 156 {
 157         void *mem, *tmp;
 158
 159         size *= nelem;
 160
 161         if (mem = malloc(size))
 162         {
 163                 tmp = mem;
 164                 while (size--)
 165                         ((uint8_t *)tmp++) = 0;
 166         }
 167
 168         return mem;
 169 }
 170
 171 /*! ANSI/POSIX-like free() implementation based on heap_alloc()/heap_free() */
 172 void free(void *mem)
 173 {
 174         ((size_t *)mem)--;
 175         heap_free(mem, *((size_t *)mem));
 176 }
 177
 178 #endif /* __POSIX__ */