dos/malloc.c

   1 /*
   2  * malloc.c
   3  *
   4  * Very simple linked-list based malloc()/free().
   5  */
   6
   7 #include <stdlib.h>
   8 #include <string.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 extern void *__mem_end;         /* In argv.c */
  24
  25 void __init_memory_arena(void)
  26 {
  27   extern char __heap_end[];
  28   struct free_arena_header *fp;
  29
  30   fp = (struct free_arena_header *)__mem_end;
  31   fp->a.type = ARENA_TYPE_FREE;
  32   fp->a.size = __heap_end - (char *)__mem_end;
  33
  34   /* Insert into chains */
  35   fp->a.next = fp->a.prev = &__malloc_head;
  36   fp->next_free = fp->prev_free = &__malloc_head;
  37   __malloc_head.a.next = __malloc_head.a.prev = fp;
  38   __malloc_head.next_free = __malloc_head.prev_free = fp;
  39 }
  40
  41 static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
  42 {
  43   size_t fsize;
  44   struct free_arena_header *nfp, *na;
  45
  46   fsize = fp->a.size;
  47
  48   /* We need the 2* to account for the larger requirements of a free block */
  49   if ( fsize >= size+2*sizeof(struct arena_header) ) {
  50     /* Bigger block than required -- split block */
  51     nfp = (struct free_arena_header *)((char *)fp + size);
  52     na = fp->a.next;
  53
  54     nfp->a.type = ARENA_TYPE_FREE;
  55     nfp->a.size = fsize-size;
  56     fp->a.type  = ARENA_TYPE_USED;
  57     fp->a.size  = size;
  58
  59     /* Insert into all-block chain */
  60     nfp->a.prev = fp;
  61     nfp->a.next = na;
  62     na->a.prev = nfp;
  63     fp->a.next = nfp;
  64
  65     /* Replace current block on free chain */
  66     nfp->next_free = fp->next_free;
  67     nfp->prev_free = fp->prev_free;
  68     fp->next_free->prev_free = nfp;
  69     fp->prev_free->next_free = nfp;
  70   } else {
  71     /* Allocate the whole block */
  72     fp->a.type = ARENA_TYPE_USED;
  73
  74     /* Remove from free chain */
  75     fp->next_free->prev_free = fp->prev_free;
  76     fp->prev_free->next_free = fp->next_free;
  77   }
  78
  79   return (void *)(&fp->a + 1);
  80 }
  81
  82 void *malloc(size_t size)
  83 {
  84   struct free_arena_header *fp;
  85
  86   if ( size == 0 )
  87     return NULL;
  88
  89   /* Add the obligatory arena header, and round up */
  90   size = (size+2*sizeof(struct arena_header)-1) & ~ARENA_SIZE_MASK;
  91
  92   for ( fp = __malloc_head.next_free ; fp->a.type != ARENA_TYPE_HEAD ;
  93         fp = fp->next_free ) {
  94     if ( fp->a.size >= size ) {
  95       /* Found fit -- allocate out of this block */
  96       return __malloc_from_block(fp, size);
  97     }
  98   }
  99
 100   /* Nothing found... need to request a block from the kernel */
 101   return NULL;                  /* No kernel to get stuff from */
 102 }
 103
 104 void *calloc(size_t nmemb, size_t size)
 105 {
 106   void *p;
 107   size *= nmemb;
 108   p = malloc(size);
 109   if (p)
 110     memset(p, 0, size);
 111   return p;
 112 }