core/mem/malloc.c

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