com32/lib/malloc.c

   1 /*
   2  * malloc.c
   3  *
   4  * Very simple linked-list based malloc()/free().
   5  */
   6
   7 #include <stdlib.h>
   8 #include "init.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 /* This is extern so it can be overridden by the user application */
  24 extern size_t __stack_size;
  25 extern void *__mem_end;         /* Produced after argv parsing */
  26
  27 static inline size_t sp(void)
  28 {
  29   size_t sp;
  30   asm volatile("movl %%esp,%0" : "=rm" (sp));
  31   return sp;
  32 }
  33
  34 static void __constructor init_memory_arena(void)
  35 {
  36   struct free_arena_header *fp;
  37   size_t start, total_space;
  38
  39   start = (size_t)ARENA_ALIGN_UP(__mem_end);
  40   total_space = sp() - start;
  41
  42   if ( __stack_size == 0 || __stack_size > total_space >> 1 )
  43     __stack_size = total_space >> 1; /* Half for the stack, half for the heap... */
  44
  45   if ( total_space < __stack_size + 4*sizeof(struct arena_header) )
  46     __stack_size = total_space - 4*sizeof(struct arena_header);
  47
  48   fp = (struct free_arena_header *)start;
  49   fp->a.type = ARENA_TYPE_FREE;
  50   fp->a.size = total_space - __stack_size;
  51
  52   /* Insert into chains */
  53   fp->a.next = fp->a.prev = &__malloc_head;
  54   fp->next_free = fp->prev_free = &__malloc_head;
  55   __malloc_head.a.next = __malloc_head.a.prev = fp;
  56   __malloc_head.next_free = __malloc_head.prev_free = fp;
  57 }
  58
  59 static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
  60 {
  61   size_t fsize;
  62   struct free_arena_header *nfp, *na;
  63
  64   fsize = fp->a.size;
  65
  66   /* We need the 2* to account for the larger requirements of a free block */
  67   if ( fsize >= size+2*sizeof(struct arena_header) ) {
  68     /* Bigger block than required -- split block */
  69     nfp = (struct free_arena_header *)((char *)fp + size);
  70     na = fp->a.next;
  71
  72     nfp->a.type = ARENA_TYPE_FREE;
  73     nfp->a.size = fsize-size;
  74     fp->a.type  = ARENA_TYPE_USED;
  75     fp->a.size  = size;
  76
  77     /* Insert into all-block chain */
  78     nfp->a.prev = fp;
  79     nfp->a.next = na;
  80     na->a.prev = nfp;
  81     fp->a.next = nfp;
  82
  83     /* Replace current block on free chain */
  84     nfp->next_free = fp->next_free;
  85     nfp->prev_free = fp->prev_free;
  86     fp->next_free->prev_free = nfp;
  87     fp->prev_free->next_free = nfp;
  88   } else {
  89     /* Allocate the whole block */
  90     fp->a.type = ARENA_TYPE_USED;
  91
  92     /* Remove from free chain */
  93     fp->next_free->prev_free = fp->prev_free;
  94     fp->prev_free->next_free = fp->next_free;
  95   }
  96
  97   return (void *)(&fp->a + 1);
  98 }
  99
 100 void *malloc(size_t size)
 101 {
 102   struct free_arena_header *fp;
 103
 104   if ( size == 0 )
 105     return NULL;
 106
 107   /* Add the obligatory arena header, and round up */
 108   size = (size+2*sizeof(struct arena_header)-1) & ARENA_SIZE_MASK;
 109
 110   for ( fp = __malloc_head.next_free ; fp->a.type != ARENA_TYPE_HEAD ;
 111         fp = fp->next_free ) {
 112     if ( fp->a.size >= size ) {
 113       /* Found fit -- allocate out of this block */
 114       return __malloc_from_block(fp, size);
 115     }
 116   }
 117
 118   /* Nothing found... need to request a block from the kernel */
 119   return NULL;                  /* No kernel to get stuff from */
 120 }