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