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   {
  13     ARENA_TYPE_HEAD,
  14     0,
  15     &__malloc_head,
  16     &__malloc_head,
  17   },
  18   &__malloc_head,
  19   &__malloc_head
  20 };
  21
  22 /* This is extern so it can be overridden by the user application */
  23 const size_t __stack_size = 4096;
  24
  25 static inline size_t sp(void)
  26 {
  27   uint16_t sp;
  28   asm volatile("movw %%sp,%0" : "=rm" (sp));
  29   return sp;
  30 }
  31
  32 void __init_memory_arena(void)
  33 {
  34   extern char _end[];           /* Symbol created by the linker */
  35   struct free_arena_header *fp;
  36   size_t start, total_space;
  37
  38   start = (size_t)ARENA_ALIGN_UP(_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 }