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 <string.h>
   9 #include <com32.h>
  10 #include <syslinux/memscan.h>
  11 #include "init.h"
  12 #include "malloc.h"
  13
  14 struct free_arena_header __malloc_head = {
  15     {
  16      ARENA_TYPE_HEAD,
  17      0,
  18      &__malloc_head,
  19      &__malloc_head,
  20      },
  21     &__malloc_head,
  22     &__malloc_head
  23 };
  24
  25 /* This is extern so it can be overridden by the user application */
  26 extern size_t __stack_size;
  27 extern void *__mem_end;         /* Produced after argv parsing */
  28
  29 static inline size_t sp(void)
  30 {
  31     size_t sp;
  32     asm volatile ("movl %%esp,%0":"=rm" (sp));
  33     return sp;
  34 }
  35
  36 #define E820_MEM_MAX 0xfff00000 /* 4 GB - 1 MB */
  37
  38 static int consider_memory_area(void *dummy, addr_t start,
  39                                 addr_t len, bool valid)
  40 {
  41     struct free_arena_header *fp;
  42     addr_t end;
  43
  44     (void)dummy;
  45
  46     if (valid && start < E820_MEM_MAX) {
  47         if (len > E820_MEM_MAX - start)
  48             len = E820_MEM_MAX - start;
  49
  50         end = start + len;
  51
  52         if (end > __com32.cs_memsize) {
  53             if (start <= __com32.cs_memsize) {
  54                 start = __com32.cs_memsize;
  55                 len = end - start;
  56             }
  57
  58             if (len >= 2 * sizeof(struct arena_header)) {
  59                 fp = (struct free_arena_header *)start;
  60                 fp->a.size = len;
  61                 __inject_free_block(fp);
  62             }
  63         }
  64     }
  65
  66     return 0;
  67 }
  68
  69 static void __constructor init_memory_arena(void)
  70 {
  71     struct free_arena_header *fp;
  72     size_t start, total_space;
  73
  74     start = (size_t) ARENA_ALIGN_UP(__mem_end);
  75     total_space = sp() - start;
  76
  77     if (__stack_size == 0 || __stack_size > total_space >> 1)
  78         __stack_size = total_space >> 1;        /* Half for the stack, half for the heap... */
  79
  80     if (total_space < __stack_size + 4 * sizeof(struct arena_header))
  81         __stack_size = total_space - 4 * sizeof(struct arena_header);
  82
  83     fp = (struct free_arena_header *)start;
  84     fp->a.size = total_space - __stack_size;
  85
  86     __inject_free_block(fp);
  87
  88     /* Scan the memory map to look for other suitable regions */
  89     if (!__com32.cs_memsize)
  90         return;                 /* Old Syslinux core, can't do this... */
  91
  92     syslinux_scan_memory(consider_memory_area, NULL);
  93 }
  94
  95 static void *__malloc_from_block(struct free_arena_header *fp, size_t size)
  96 {
  97     size_t fsize;
  98     struct free_arena_header *nfp, *na;
  99
 100     fsize = fp->a.size;
 101
 102     /* We need the 2* to account for the larger requirements of a free block */
 103     if (fsize >= size + 2 * sizeof(struct arena_header)) {
 104         /* Bigger block than required -- split block */
 105         nfp = (struct free_arena_header *)((char *)fp + size);
 106         na = fp->a.next;
 107
 108         nfp->a.type = ARENA_TYPE_FREE;
 109         nfp->a.size = fsize - size;
 110         fp->a.type = ARENA_TYPE_USED;
 111         fp->a.size = size;
 112
 113         /* Insert into all-block chain */
 114         nfp->a.prev = fp;
 115         nfp->a.next = na;
 116         na->a.prev = nfp;
 117         fp->a.next = nfp;
 118
 119         /* Replace current block on free chain */
 120         nfp->next_free = fp->next_free;
 121         nfp->prev_free = fp->prev_free;
 122         fp->next_free->prev_free = nfp;
 123         fp->prev_free->next_free = nfp;
 124     } else {
 125         /* Allocate the whole block */
 126         fp->a.type = ARENA_TYPE_USED;
 127
 128         /* Remove from free chain */
 129         fp->next_free->prev_free = fp->prev_free;
 130         fp->prev_free->next_free = fp->next_free;
 131     }
 132
 133     return (void *)(&fp->a + 1);
 134 }
 135
 136 void *malloc(size_t size)
 137 {
 138     struct free_arena_header *fp;
 139
 140     if (size == 0)
 141         return NULL;
 142
 143     /* Add the obligatory arena header, and round up */
 144     size = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;
 145
 146     for (fp = __malloc_head.next_free; fp->a.type != ARENA_TYPE_HEAD;
 147          fp = fp->next_free) {
 148         if (fp->a.size >= size) {
 149             /* Found fit -- allocate out of this block */
 150             return __malloc_from_block(fp, size);
 151         }
 152     }
 153
 154     /* Nothing found... need to request a block from the kernel */
 155     return NULL;                /* No kernel to get stuff from */
 156 }