dos/malloc.c

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