klibc/klibc/malloc.c

   1 /*
   2  * malloc.c
   3  *
   4  * Very simple linked-list based malloc()/free().
   5  */
   6
   7 #include <stdlib.h>
   8 #include <sys/mman.h>
   9 #include "malloc.h"
  10
  11 struct free_arena_header __malloc_head =
  12 {
  13   {
  14     ARENA_TYPE_HEAD,
  15     0,
  16     &__malloc_head,
  17     &__malloc_head,
  18   },
  19   &__malloc_head,
  20   &__malloc_head
  21 };
  22
  23 static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
  24 {
  25   size_t fsize;
  26   struct free_arena_header *nfp, *na;
  27
  28   fsize = fp->a.size;
  29
  30   /* We need the 2* to account for the larger requirements of a free block */
  31   if ( fsize >= size+2*sizeof(struct arena_header) ) {
  32     /* Bigger block than required -- split block */
  33     nfp = (struct free_arena_header *)((char *)fp + size);
  34     na = fp->a.next;
  35
  36     nfp->a.type = ARENA_TYPE_FREE;
  37     nfp->a.size = fsize-size;
  38     fp->a.type  = ARENA_TYPE_USED;
  39     fp->a.size  = size;
  40
  41     /* Insert into all-block chain */
  42     nfp->a.prev = fp;
  43     nfp->a.next = na;
  44     na->a.prev = nfp;
  45     fp->a.next = nfp;
  46
  47     /* Replace current block on free chain */
  48     nfp->next_free = fp->next_free;
  49     nfp->prev_free = fp->prev_free;
  50     fp->next_free->prev_free = nfp;
  51     fp->prev_free->next_free = nfp;
  52   } else {
  53     /* Allocate the whole block */
  54     fp->a.type = ARENA_TYPE_USED;
  55
  56     /* Remove from free chain */
  57     fp->next_free->prev_free = fp->prev_free;
  58     fp->prev_free->next_free = fp->next_free;
  59   }
  60
  61   return (void *)(&fp->a + 1);
  62 }
  63
  64 static struct free_arena_header *
  65 __free_block(struct free_arena_header *ah)
  66 {
  67   struct free_arena_header *pah, *nah;
  68
  69   pah = ah->a.prev;
  70   nah = ah->a.next;
  71   if ( pah->a.type == ARENA_TYPE_FREE &&
  72        (char *)pah+pah->a.size == (char *)ah ) {
  73     /* Coalesce into the previous block */
  74     pah->a.size += ah->a.size;
  75     pah->a.next = nah;
  76     nah->a.prev = pah;
  77
  78 #ifdef DEBUG_MALLOC
  79     ah->a.type = ARENA_TYPE_DEAD;
  80 #endif
  81
  82     ah = pah;
  83     pah = ah->a.prev;
  84   } else {
  85     /* Need to add this block to the free chain */
  86     ah->a.type = ARENA_TYPE_FREE;
  87
  88     ah->next_free = __malloc_head.next_free;
  89     ah->prev_free = &__malloc_head;
  90     __malloc_head.next_free = ah;
  91     ah->next_free->prev_free = ah;
  92   }
  93
  94   /* In either of the previous cases, we might be able to merge
  95      with the subsequent block... */
  96   if ( nah->a.type == ARENA_TYPE_FREE &&
  97        (char *)ah+ah->a.size == (char *)nah ) {
  98     ah->a.size += nah->a.size;
  99
 100     /* Remove the old block from the chains */
 101     nah->next_free->prev_free = nah->prev_free;
 102     nah->prev_free->next_free = nah->next_free;
 103     ah->a.next = nah->a.next;
 104     nah->a.next->a.prev = ah;
 105
 106 #ifdef DEBUG_MALLOC
 107     nah->a.type = ARENA_TYPE_DEAD;
 108 #endif
 109   }
 110
 111   /* Return the block that contains the called block */
 112   return ah;
 113 }
 114
 115 void *malloc(size_t size)
 116 {
 117   struct free_arena_header *fp;
 118   struct free_arena_header *pah;
 119   size_t fsize;
 120
 121   if ( size == 0 )
 122     return NULL;
 123
 124   /* Add the obligatory arena header, and round up */
 125   size = (size+2*sizeof(struct arena_header)-1) & ARENA_SIZE_MASK;
 126
 127   for ( fp = __malloc_head.next_free ; fp->a.type != ARENA_TYPE_HEAD ;
 128         fp = fp->next_free ) {
 129     if ( fp->a.size >= size ) {
 130       /* Found fit -- allocate out of this block */
 131       return __malloc_from_block(fp, size);
 132     }
 133   }
 134
 135   /* Nothing found... need to request a block from the kernel */
 136   fsize = (size+MALLOC_CHUNK_MASK) & ~MALLOC_CHUNK_MASK;
 137
 138 #ifdef MALLOC_USING_SBRK
 139   fp = (struct free_arena_header *) sbrk(fsize);
 140 #else
 141   fp = (struct free_arena_header *)
 142     mmap(NULL, fsize, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, 0, 0);
 143 #endif
 144
 145   if ( fp == (struct free_arena_header *)MAP_FAILED ) {
 146     return NULL;                /* Failed to get a block */
 147   }
 148
 149   /* Insert the block into the management chains.  We need to set
 150      up the size and the main block list pointer, the rest of
 151      the work is logically identical to free(). */
 152   fp->a.type = ARENA_TYPE_FREE;
 153   fp->a.size = fsize;
 154
 155   /* We need to insert this into the main block list in the proper
 156      place -- this list is required to be sorted.  Since we most likely
 157      get memory assignments in ascending order, search backwards for
 158      the proper place. */
 159   for ( pah = __malloc_head.a.prev ; pah->a.type != ARENA_TYPE_HEAD ;
 160         pah = pah->a.prev ) {
 161     if ( pah < fp )
 162       break;
 163   }
 164
 165   /* Now pah points to the node that should be the predecessor of
 166      the new node */
 167   fp->a.next = pah->a.next;
 168   fp->a.prev = pah;
 169   pah->a.next  = fp;
 170   fp->a.next->a.prev = fp;
 171
 172
 173   /* Insert into the free chain and coalesce with adjacent blocks */
 174   fp = __free_block(fp);
 175
 176   /* Now we can allocate from this block */
 177   return __malloc_from_block(fp, size);
 178 }
 179
 180 void free(void *ptr)
 181 {
 182   struct free_arena_header *ah;
 183
 184   if ( !ptr )
 185     return;
 186
 187   ah = (struct free_arena_header *)
 188     ((struct arena_header *)ptr - 1);
 189
 190 #ifdef DEBUG_MALLOC
 191   assert( ah->a.type == ARENA_TYPE_USED );
 192 #endif
 193
 194   __free_block(ah);
 195
 196   /* Here we could insert code to return memory to the system. */
 197 }