payloads/libpayload/libc/malloc.c

   1 /*
   2  * This file is part of the libpayload project.
   3  *
   4  * Copyright (C) 2008 Advanced Micro Devices, Inc.
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  * 1. Redistributions of source code must retain the above copyright
  10  *    notice, this list of conditions and the following disclaimer.
  11  * 2. Redistributions in binary form must reproduce the above copyright
  12  *    notice, this list of conditions and the following disclaimer in the
  13  *    documentation and/or other materials provided with the distribution.
  14  * 3. The name of the author may not be used to endorse or promote products
  15  *    derived from this software without specific prior written permission.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 /*
  31  * This is a classically weak malloc() implementation. We have a relatively
  32  * small and static heap, so we take the easy route with an O(N) loop
  33  * through the tree for every malloc() and free(). Obviously, this doesn't
  34  * scale past a few hundred KB (if that).
  35  *
  36  * We're also susceptible to the usual buffer overrun poisoning, though the
  37  * risk is within acceptable ranges for this implementation (don't overrun
  38  * your buffers, kids!).
  39  */
  40
  41 #include <libpayload.h>
  42
  43 extern char _heap, _eheap;      /* Defined in the ldscript. */
  44
  45 static void *hstart = (void *)&_heap;
  46 static void *hend = (void *)&_eheap;
  47
  48 typedef unsigned int hdrtype_t;
  49
  50 #define MAGIC     (0x2a << 26)
  51 #define FLAG_FREE (1 << 25)
  52 #define FLAG_USED (1 << 24)
  53
  54 #define SIZE(_h) ((_h) & 0xFFFFFF)
  55
  56 #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & 0xFFFFFF)))
  57
  58 #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE)
  59 #define USED_BLOCK(_s) _HEADER(_s, FLAG_USED)
  60
  61 #define HDRSIZE (sizeof(hdrtype_t))
  62
  63 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
  64 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
  65
  66 static int free_aligned(void* addr);
  67 void print_malloc_map(void);
  68
  69 static void setup(void)
  70 {
  71         int size = (unsigned int)(&_eheap - &_heap) - HDRSIZE;
  72
  73         *((hdrtype_t *) hstart) = FREE_BLOCK(size);
  74 }
  75
  76 static void *alloc(int len)
  77 {
  78         hdrtype_t header;
  79         void *ptr = hstart;
  80
  81         /* Align the size. */
  82         len = (len + 3) & ~3;
  83
  84         if (!len || len > 0xffffff)
  85                 return (void *)NULL;
  86
  87         /* Make sure the region is setup correctly. */
  88         if (!HAS_MAGIC(*((hdrtype_t *) ptr)))
  89                 setup();
  90
  91         /* Find some free space. */
  92         do {
  93                 header = *((hdrtype_t *) ptr);
  94                 int size = SIZE(header);
  95
  96                 if (!HAS_MAGIC(header) || size == 0) {
  97                         printf("memory allocator panic.\n");
  98                         halt();
  99                 }
 100
 101                 if (header & FLAG_FREE) {
 102                         if (len <= size) {
 103                                 void *nptr = ptr + (HDRSIZE + len);
 104                                 int nsize = size - (HDRSIZE + len);
 105
 106                                 /* Mark the block as used. */
 107                                 *((hdrtype_t *) ptr) = USED_BLOCK(len);
 108
 109                                 /* If there is still room in this block,
 110                                  * then mark it as such.
 111                                  */
 112
 113                                 if (nsize > 0)
 114                                         *((hdrtype_t *) nptr) =
 115                                             FREE_BLOCK(nsize);
 116
 117                                 return (void *)(ptr + HDRSIZE);
 118                         }
 119                 }
 120
 121                 ptr += HDRSIZE + size;
 122
 123         } while (ptr < hend);
 124
 125         /* Nothing available. */
 126         return (void *)NULL;
 127 }
 128
 129 static void _consolidate(void)
 130 {
 131         void *ptr = hstart;
 132
 133         while (ptr < hend) {
 134                 void *nptr;
 135                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 136                 unsigned int size = 0;
 137
 138                 if (!IS_FREE(hdr)) {
 139                         ptr += HDRSIZE + SIZE(hdr);
 140                         continue;
 141                 }
 142
 143                 size = SIZE(hdr);
 144                 nptr = ptr + HDRSIZE + SIZE(hdr);
 145
 146                 while (nptr < hend) {
 147                         hdrtype_t nhdr = *((hdrtype_t *) nptr);
 148
 149                         if (!(IS_FREE(nhdr)))
 150                                 break;
 151
 152                         size += SIZE(nhdr) + HDRSIZE;
 153
 154                         *((hdrtype_t *) nptr) = 0;
 155
 156                         nptr += (HDRSIZE + SIZE(nhdr));
 157                 }
 158
 159                 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
 160                 ptr = nptr;
 161         }
 162 }
 163
 164 void free(void *ptr)
 165 {
 166         hdrtype_t hdr;
 167
 168         if (free_aligned(ptr)) return;
 169
 170         ptr -= HDRSIZE;
 171
 172         /* Sanity check. */
 173         if (ptr < hstart || ptr >= hend)
 174                 return;
 175
 176         hdr = *((hdrtype_t *) ptr);
 177
 178         /* Not our header (we're probably poisoned). */
 179         if (!HAS_MAGIC(hdr))
 180                 return;
 181
 182         /* Double free. */
 183         if (hdr & FLAG_FREE)
 184                 return;
 185
 186         *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
 187         _consolidate();
 188 }
 189
 190 void *malloc(size_t size)
 191 {
 192         return alloc(size);
 193 }
 194
 195 void *calloc(size_t nmemb, size_t size)
 196 {
 197         size_t total = nmemb * size;
 198         void *ptr = alloc(total);
 199
 200         if (ptr)
 201                 memset(ptr, 0, total);
 202
 203         return ptr;
 204 }
 205
 206 void *realloc(void *ptr, size_t size)
 207 {
 208         void *ret, *pptr;
 209         unsigned int osize;
 210
 211         if (ptr == NULL)
 212                 return alloc(size);
 213
 214         pptr = ptr - HDRSIZE;
 215
 216         if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
 217                 return NULL;
 218
 219         /* Get the original size of the block. */
 220         osize = SIZE(*((hdrtype_t *) pptr));
 221
 222         /*
 223          * Free the memory to update the tables - this won't touch the actual
 224          * memory, so we can still use it for the copy after we have
 225          * reallocated the new space.
 226          */
 227         free(ptr);
 228         ret = alloc(size);
 229
 230         /*
 231          * if ret == NULL, then doh - failure.
 232          * if ret == ptr then woo-hoo! no copy needed.
 233          */
 234         if (ret == NULL || ret == ptr)
 235                 return ret;
 236
 237         /* Copy the memory to the new location. */
 238         memcpy(ret, ptr, osize > size ? size : osize);
 239
 240         return ret;
 241 }
 242
 243 struct align_region_t
 244 {
 245         int alignment;
 246         /* start in memory, and size in bytes */
 247         void* start;
 248         int size;
 249         /* layout within a region:
 250           - num_elements bytes, 0: free, 1: used, 2: used, combines with next
 251           - padding to alignment
 252           - data section
 253           - waste space
 254
 255           start_data points to the start of the data section
 256         */
 257         void* start_data;
 258         /* number of free blocks sized "alignment" */
 259         int free;
 260         struct align_region_t *next;
 261 };
 262
 263 static struct align_region_t* align_regions = 0;
 264
 265 static struct align_region_t *allocate_region(struct align_region_t *old_first, int alignment, int num_elements)
 266 {
 267         struct align_region_t *new_region = malloc(sizeof(struct align_region_t));
 268         new_region->alignment = alignment;
 269         new_region->start = malloc((num_elements+1) * alignment + num_elements);
 270         new_region->start_data = (void*)((u32)(new_region->start + num_elements + alignment - 1) & (~(alignment-1)));
 271         new_region->size = num_elements * alignment;
 272         new_region->free = num_elements;
 273         new_region->next = old_first;
 274         memset(new_region->start, 0, num_elements);
 275         return new_region;
 276 }
 277
 278
 279 static int free_aligned(void* addr)
 280 {
 281         struct align_region_t *reg = align_regions;
 282         while (reg != 0)
 283         {
 284                 if ((addr >= reg->start_data) && (addr < reg->start_data + reg->size))
 285                 {
 286                         int i = (addr-reg->start_data)/reg->alignment;
 287                         while (((u8*)reg->start)[i]==2)
 288                         {
 289                                 ((u8*)reg->start)[i++]=0;
 290                                 reg->free++;
 291                         }
 292                         ((u8*)reg->start)[i]=0;
 293                         reg->free++;
 294                         return 1;
 295                 }
 296                 reg = reg->next;
 297         }
 298         return 0;
 299 }
 300
 301 void *memalign(size_t align, size_t size)
 302 {
 303         if (size == 0) return 0;
 304         if (align_regions == 0) {
 305                 align_regions = malloc(sizeof(struct align_region_t));
 306                 memset(align_regions, 0, sizeof(struct align_region_t));
 307         }
 308         struct align_region_t *reg = align_regions;
 309 look_further:
 310         while (reg != 0)
 311         {
 312                 if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align))
 313                 {
 314                         break;
 315                 }
 316                 reg = reg->next;
 317         }
 318         if (reg == 0)
 319         {
 320                 align_regions = allocate_region(align_regions, align, (size/align<99)?100:((size/align)+1));
 321                 reg = align_regions;
 322         }
 323         int i, count = 0, target = (size+align-1)/align;
 324         for (i = 0; i < (reg->size/align); i++)
 325         {
 326                 if (((u8*)reg->start)[i] == 0)
 327                 {
 328                         count++;
 329                         if (count == target) {
 330                                 count = i+1-count;
 331                                 for (i=0; i<target-1; i++)
 332                                 {
 333                                         ((u8*)reg->start)[count+i]=2;
 334                                 }
 335                                 ((u8*)reg->start)[count+target-1]=1;
 336                                 reg->free -= target;
 337                                 return reg->start_data+(align*count);
 338                         }
 339                 } else {
 340                         count = 0;
 341                 }
 342         }
 343         goto look_further; // end condition is once a new region is allocated - it always has enough space
 344 }
 345
 346 /* This is for debugging purposes. */
 347 #ifdef TEST
 348 void print_malloc_map(void)
 349 {
 350         void *ptr = hstart;
 351
 352         while (ptr < hend) {
 353                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 354
 355                 if (!HAS_MAGIC(hdr)) {
 356                         printf("Poisoned magic - we're toast\n");
 357                         break;
 358                 }
 359
 360                 /* FIXME: Verify the size of the block. */
 361
 362                 printf("%x: %s (%x bytes)\n",
 363                        (unsigned int)(ptr - hstart),
 364                        hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
 365
 366                 ptr += HDRSIZE + SIZE(hdr);
 367         }
 368 }
 369 #endif