core/mem/malloc.c

   1 /*
   2  * malloc.c
   3  *
   4  * Very simple linked-list based malloc()/free().
   5  */
   6
   7 #include <syslinux/firmware.h>
   8 #include <stdio.h>
   9 #include <stdlib.h>
  10 #include <errno.h>
  11 #include <string.h>
  12 #include <dprintf.h>
  13 #include <minmax.h>
  14
  15 #include "malloc.h"
  16 #include "thread.h"
  17
  18 DECLARE_INIT_SEMAPHORE(__malloc_semaphore, 1);
  19
  20 static void *__malloc_from_block(struct free_arena_header *fp,
  21                                  size_t size, malloc_tag_t tag)
  22 {
  23     size_t fsize;
  24     struct free_arena_header *nfp, *na;
  25     unsigned int heap = ARENA_HEAP_GET(fp->a.attrs);
  26
  27     fsize = ARENA_SIZE_GET(fp->a.attrs);
  28
  29     /* We need the 2* to account for the larger requirements of a free block */
  30     if ( fsize >= size+2*sizeof(struct arena_header) ) {
  31         /* Bigger block than required -- split block */
  32         nfp = (struct free_arena_header *)((char *)fp + size);
  33         na = fp->a.next;
  34
  35         ARENA_TYPE_SET(nfp->a.attrs, ARENA_TYPE_FREE);
  36         ARENA_HEAP_SET(nfp->a.attrs, heap);
  37         ARENA_SIZE_SET(nfp->a.attrs, fsize-size);
  38         nfp->a.tag = MALLOC_FREE;
  39 #ifdef DEBUG_MALLOC
  40         nfp->a.magic = ARENA_MAGIC;
  41 #endif
  42         ARENA_TYPE_SET(fp->a.attrs, ARENA_TYPE_USED);
  43         ARENA_SIZE_SET(fp->a.attrs, size);
  44         fp->a.tag = tag;
  45
  46         /* Insert into all-block chain */
  47         nfp->a.prev = fp;
  48         nfp->a.next = na;
  49         na->a.prev = nfp;
  50         fp->a.next = nfp;
  51
  52         /* Replace current block on free chain */
  53         nfp->next_free = fp->next_free;
  54         nfp->prev_free = fp->prev_free;
  55         fp->next_free->prev_free = nfp;
  56         fp->prev_free->next_free = nfp;
  57     } else {
  58         /* Allocate the whole block */
  59         ARENA_TYPE_SET(fp->a.attrs, ARENA_TYPE_USED);
  60         fp->a.tag = tag;
  61
  62         /* Remove from free chain */
  63         fp->next_free->prev_free = fp->prev_free;
  64         fp->prev_free->next_free = fp->next_free;
  65     }
  66
  67     return (void *)(&fp->a + 1);
  68 }
  69
  70 void *bios_malloc(size_t size, enum heap heap, malloc_tag_t tag)
  71 {
  72     struct free_arena_header *fp;
  73     struct free_arena_header *head = &__core_malloc_head[heap];
  74     void *p = NULL;
  75
  76     if (size) {
  77         /* Add the obligatory arena header, and round up */
  78         size = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;
  79
  80         for ( fp = head->next_free ; fp != head ; fp = fp->next_free ) {
  81             if ( ARENA_SIZE_GET(fp->a.attrs) >= size ) {
  82                 /* Found fit -- allocate out of this block */
  83                 p = __malloc_from_block(fp, size, tag);
  84                 break;
  85             }
  86         }
  87     }
  88
  89     return p;
  90 }
  91
  92 static void *_malloc(size_t size, enum heap heap, malloc_tag_t tag)
  93 {
  94     void *p;
  95
  96     dprintf("_malloc(%zu, %u, %u) @ %p = ",
  97         size, heap, tag, __builtin_return_address(0));
  98
  99     sem_down(&__malloc_semaphore, 0);
 100     p = firmware->mem->malloc(size, heap, tag);
 101     sem_up(&__malloc_semaphore);
 102
 103     dprintf("%p\n", p);
 104     return p;
 105 }
 106
 107 __export void *malloc(size_t size)
 108 {
 109     return _malloc(size, HEAP_MAIN, MALLOC_CORE);
 110 }
 111
 112 __export void *lmalloc(size_t size)
 113 {
 114     void *p;
 115
 116     p = _malloc(size, HEAP_LOWMEM, MALLOC_CORE);
 117     if (!p)
 118         errno = ENOMEM;
 119     return p;
 120 }
 121
 122 void *pmapi_lmalloc(size_t size)
 123 {
 124     return _malloc(size, HEAP_LOWMEM, MALLOC_MODULE);
 125 }
 126
 127 void *bios_realloc(void *ptr, size_t size)
 128 {
 129     struct free_arena_header *ah, *nah;
 130     struct free_arena_header *head;
 131
 132     void *newptr;
 133     size_t newsize, oldsize, xsize;
 134
 135     if (!ptr)
 136         return malloc(size);
 137
 138     if (size == 0) {
 139         free(ptr);
 140         return NULL;
 141     }
 142
 143     ah = (struct free_arena_header *)
 144         ((struct arena_header *)ptr - 1);
 145
 146         head = &__core_malloc_head[ARENA_HEAP_GET(ah->a.attrs)];
 147
 148 #ifdef DEBUG_MALLOC
 149     if (ah->a.magic != ARENA_MAGIC)
 150         dprintf("failed realloc() magic check: %p\n", ptr);
 151 #endif
 152
 153     /* Actual size of the old block */
 154     //oldsize = ah->a.size;
 155     oldsize = ARENA_SIZE_GET(ah->a.attrs);
 156
 157     /* Add the obligatory arena header, and round up */
 158     newsize = (size + 2 * sizeof(struct arena_header) - 1) & ARENA_SIZE_MASK;
 159
 160     if (oldsize >= newsize && newsize >= (oldsize >> 2) &&
 161         oldsize - newsize < 4096) {
 162         /* This allocation is close enough already. */
 163         return ptr;
 164     } else {
 165         xsize = oldsize;
 166
 167         nah = ah->a.next;
 168         if ((char *)nah == (char *)ah + ARENA_SIZE_GET(ah->a.attrs) &&
 169                 ARENA_TYPE_GET(nah->a.attrs) == ARENA_TYPE_FREE &&
 170                 ARENA_SIZE_GET(nah->a.attrs) + oldsize >= newsize) {
 171             //nah->a.type == ARENA_TYPE_FREE &&
 172             //oldsize + nah->a.size >= newsize) {
 173             /* Merge in subsequent free block */
 174             ah->a.next = nah->a.next;
 175             ah->a.next->a.prev = ah;
 176             nah->next_free->prev_free = nah->prev_free;
 177             nah->prev_free->next_free = nah->next_free;
 178             ARENA_SIZE_SET(ah->a.attrs, ARENA_SIZE_GET(ah->a.attrs) +
 179                            ARENA_SIZE_GET(nah->a.attrs));
 180             xsize = ARENA_SIZE_GET(ah->a.attrs);
 181         }
 182
 183         if (xsize >= newsize) {
 184             /* We can reallocate in place */
 185             if (xsize >= newsize + 2 * sizeof(struct arena_header)) {
 186                 /* Residual free block at end */
 187                 nah = (struct free_arena_header *)((char *)ah + newsize);
 188                 ARENA_TYPE_SET(nah->a.attrs, ARENA_TYPE_FREE);
 189                 ARENA_SIZE_SET(nah->a.attrs, xsize - newsize);
 190                 ARENA_SIZE_SET(ah->a.attrs, newsize);
 191                 ARENA_HEAP_SET(nah->a.attrs, ARENA_HEAP_GET(ah->a.attrs));
 192
 193 #ifdef DEBUG_MALLOC
 194                 nah->a.magic = ARENA_MAGIC;
 195 #endif
 196
 197                 //nah->a.type = ARENA_TYPE_FREE;
 198                 //nah->a.size = xsize - newsize;
 199                 //ah->a.size = newsize;
 200
 201                 /* Insert into block list */
 202                 nah->a.next = ah->a.next;
 203                 ah->a.next = nah;
 204                 nah->a.next->a.prev = nah;
 205                 nah->a.prev = ah;
 206
 207                 /* Insert into free list */
 208                 if (newsize > oldsize) {
 209                     /* Hack: this free block is in the path of a memory object
 210                        which has already been grown at least once.  As such, put
 211                        it at the *end* of the freelist instead of the beginning;
 212                        trying to save it for future realloc()s of the same block. */
 213                     nah->prev_free = head->prev_free;
 214                     nah->next_free = head;
 215                     head->prev_free = nah;
 216                     nah->prev_free->next_free = nah;
 217                 } else {
 218                     nah->next_free = head->next_free;
 219                     nah->prev_free = head;
 220                     head->next_free = nah;
 221                     nah->next_free->prev_free = nah;
 222                 }
 223             }
 224             /* otherwise, use up the whole block */
 225             return ptr;
 226         } else {
 227             /* Last resort: need to allocate a new block and copy */
 228             oldsize -= sizeof(struct arena_header);
 229             newptr = malloc(size);
 230             if (newptr) {
 231                 memcpy(newptr, ptr, min(size, oldsize));
 232                 free(ptr);
 233             }
 234             return newptr;
 235         }
 236     }
 237 }
 238
 239 __export void *realloc(void *ptr, size_t size)
 240 {
 241     return firmware->mem->realloc(ptr, size);
 242 }
 243
 244 __export void *zalloc(size_t size)
 245 {
 246     void *ptr;
 247
 248     ptr = malloc(size);
 249     if (ptr)
 250         memset(ptr, 0, size);
 251
 252     return ptr;
 253 }