payloads/libpayload/libc/malloc.c

   1 /*
   2  *
   3  * Copyright (C) 2008 Advanced Micro Devices, Inc.
   4  * Copyright (C) 2008-2010 coresystems GmbH
   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 #define IN_MALLOC_C
  42 #include <libpayload.h>
  43 #include <stdint.h>
  44
  45 struct memory_type {
  46         void *start;
  47         void *end;
  48         struct align_region_t* align_regions;
  49 #if CONFIG(LP_DEBUG_MALLOC)
  50         int magic_initialized;
  51         size_t minimal_free;
  52         const char *name;
  53 #endif
  54 };
  55
  56 extern char _heap, _eheap;      /* Defined in the ldscript. */
  57
  58 static struct memory_type default_type =
  59         { (void *)&_heap, (void *)&_eheap, NULL
  60 #if CONFIG(LP_DEBUG_MALLOC)
  61         , 0, 0, "HEAP"
  62 #endif
  63         };
  64 static struct memory_type *const heap = &default_type;
  65 static struct memory_type *dma = &default_type;
  66
  67 typedef u64 hdrtype_t;
  68 #define HDRSIZE (sizeof(hdrtype_t))
  69
  70 #define SIZE_BITS ((HDRSIZE << 3) - 7)
  71 #define MAGIC     (((hdrtype_t)0x2a) << (SIZE_BITS + 1))
  72 #define FLAG_FREE (((hdrtype_t)0x01) << (SIZE_BITS + 0))
  73 #define MAX_SIZE  ((((hdrtype_t)0x01) << SIZE_BITS) - 1)
  74
  75 #define SIZE(_h) ((_h) & MAX_SIZE)
  76
  77 #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & MAX_SIZE)))
  78
  79 #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE)
  80 #define USED_BLOCK(_s) _HEADER(_s, 0)
  81
  82 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
  83 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
  84
  85 static int free_aligned(void* addr, struct memory_type *type);
  86 void print_malloc_map(void);
  87
  88 void init_dma_memory(void *start, u32 size)
  89 {
  90         if (dma_initialized()) {
  91                 printf("ERROR: %s called twice!\n", __func__);
  92                 return;
  93         }
  94
  95         /*
  96          * DMA memory might not be zeroed by coreboot on stage loading, so make
  97          * sure we clear the magic cookie from last boot.
  98          */
  99         *(hdrtype_t *)start = 0;
 100
 101         dma = malloc(sizeof(*dma));
 102         dma->start = start;
 103         dma->end = start + size;
 104         dma->align_regions = NULL;
 105
 106 #if CONFIG(LP_DEBUG_MALLOC)
 107         dma->minimal_free = 0;
 108         dma->magic_initialized = 0;
 109         dma->name = "DMA";
 110
 111         printf("Initialized cache-coherent DMA memory at [%p:%p]\n", start, start + size);
 112 #endif
 113 }
 114
 115 int dma_initialized(void)
 116 {
 117         return dma != heap;
 118 }
 119
 120 /* For boards that don't initialize DMA we assume all locations are coherent */
 121 int dma_coherent(const void *ptr)
 122 {
 123         return !dma_initialized() || (dma->start <= ptr && dma->end > ptr);
 124 }
 125
 126 /* Get the range of memory that can be allocated by the dma allocator. */
 127 void dma_allocator_range(void **start_out, size_t *size_out)
 128 {
 129         if (dma_initialized()) {
 130                 *start_out = dma->start;
 131                 *size_out = dma->end - dma->start;
 132         } else {
 133                 *start_out = NULL;
 134                 *size_out = 0;
 135         }
 136 }
 137
 138 /* Find free block of size >= len */
 139 static hdrtype_t volatile *find_free_block(int len, struct memory_type *type)
 140 {
 141         hdrtype_t header;
 142         hdrtype_t volatile *ptr = (hdrtype_t volatile *)type->start;
 143
 144         /* Align the size. */
 145         len = ALIGN_UP(len, HDRSIZE);
 146
 147         if (!len || len > MAX_SIZE)
 148                 return (void *)NULL;
 149
 150         /* Make sure the region is setup correctly. */
 151         if (!HAS_MAGIC(*ptr)) {
 152                 size_t size = (type->end - type->start) - HDRSIZE;
 153                 *ptr = FREE_BLOCK(size);
 154 #if CONFIG(LP_DEBUG_MALLOC)
 155                 type->magic_initialized = 1;
 156                 type->minimal_free = size;
 157 #endif
 158         }
 159
 160         /* Find some free space. */
 161         do {
 162                 header = *ptr;
 163                 int size = SIZE(header);
 164
 165                 if (!HAS_MAGIC(header) || size == 0) {
 166                         printf("memory allocator panic. (%s%s)\n",
 167                                !HAS_MAGIC(header) ? " no magic " : "",
 168                                    size == 0 ? " size=0 " : "");
 169                         halt();
 170                 }
 171
 172                 if ((header & FLAG_FREE) && len <= size)
 173                         return ptr;
 174
 175                 ptr = (hdrtype_t volatile *)((uintptr_t)ptr + HDRSIZE + size);
 176
 177         } while (ptr < (hdrtype_t *) type->end);
 178
 179         /* Nothing available. */
 180         return NULL;
 181 }
 182
 183 /* Mark the block with length 'len' as used */
 184 static void use_block(hdrtype_t volatile *ptr, int len)
 185 {
 186         /* Align the size. */
 187         len = ALIGN_UP(len, HDRSIZE);
 188
 189         hdrtype_t volatile *nptr = (hdrtype_t volatile *)
 190                 ((uintptr_t)ptr + HDRSIZE + len);
 191         int size = SIZE(*ptr);
 192         int nsize = size - (HDRSIZE + len);
 193
 194         /*
 195          * If there is still room in this block, then mark it as such otherwise
 196          * account the whole space for that block.
 197          */
 198         if (nsize > 0) {
 199                 /* Mark the block as used. */
 200                 *ptr = USED_BLOCK(len);
 201
 202                 /* Create a new free block. */
 203                 *nptr = FREE_BLOCK(nsize);
 204         } else {
 205                 /* Mark the block as used. */
 206                 *ptr = USED_BLOCK(size);
 207         }
 208 }
 209
 210 static void *alloc(int len, struct memory_type *type)
 211 {
 212         hdrtype_t volatile *ptr = find_free_block(len, type);
 213
 214         if (ptr == NULL)
 215                 return NULL;
 216
 217         use_block(ptr, len);
 218         return (void *)((uintptr_t)ptr + HDRSIZE);
 219 }
 220
 221 static void _consolidate(struct memory_type *type)
 222 {
 223         void *ptr = type->start;
 224
 225         while (ptr < type->end) {
 226                 void *nptr;
 227                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 228                 unsigned int size = 0;
 229
 230                 if (!IS_FREE(hdr)) {
 231                         ptr += HDRSIZE + SIZE(hdr);
 232                         continue;
 233                 }
 234
 235                 size = SIZE(hdr);
 236                 nptr = ptr + HDRSIZE + SIZE(hdr);
 237
 238                 while (nptr < type->end) {
 239                         hdrtype_t nhdr = *((hdrtype_t *) nptr);
 240
 241                         if (!(IS_FREE(nhdr)))
 242                                 break;
 243
 244                         size += SIZE(nhdr) + HDRSIZE;
 245
 246                         *((hdrtype_t *) nptr) = 0;
 247
 248                         nptr += (HDRSIZE + SIZE(nhdr));
 249                 }
 250
 251                 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
 252                 ptr = nptr;
 253         }
 254 }
 255
 256 void free(void *ptr)
 257 {
 258         hdrtype_t hdr;
 259         struct memory_type *type = heap;
 260
 261         /* No action occurs on NULL. */
 262         if (ptr == NULL)
 263                 return;
 264
 265         /* Sanity check. */
 266         if (ptr < type->start || ptr >= type->end) {
 267                 type = dma;
 268                 if (ptr < type->start || ptr >= type->end)
 269                         return;
 270         }
 271
 272         if (free_aligned(ptr, type)) return;
 273
 274         ptr -= HDRSIZE;
 275         hdr = *((hdrtype_t *) ptr);
 276
 277         /* Not our header (we're probably poisoned). */
 278         if (!HAS_MAGIC(hdr))
 279                 return;
 280
 281         /* Double free. */
 282         if (hdr & FLAG_FREE)
 283                 return;
 284
 285         *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
 286         _consolidate(type);
 287 }
 288
 289 void *malloc(size_t size)
 290 {
 291         return alloc(size, heap);
 292 }
 293
 294 void *dma_malloc(size_t size)
 295 {
 296         return alloc(size, dma);
 297 }
 298
 299 void *calloc(size_t nmemb, size_t size)
 300 {
 301         size_t total = nmemb * size;
 302         void *ptr = alloc(total, heap);
 303
 304         if (ptr)
 305                 memset(ptr, 0, total);
 306
 307         return ptr;
 308 }
 309
 310 void *realloc(void *ptr, size_t size)
 311 {
 312         void *ret, *pptr;
 313         hdrtype_t volatile *block;
 314         unsigned int osize;
 315         struct memory_type *type = heap;
 316
 317         if (ptr == NULL)
 318                 return alloc(size, type);
 319
 320         pptr = ptr - HDRSIZE;
 321
 322         if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
 323                 return NULL;
 324
 325         if (ptr < type->start || ptr >= type->end)
 326                 type = dma;
 327
 328         /* Get the original size of the block. */
 329         osize = SIZE(*((hdrtype_t *) pptr));
 330
 331         /*
 332          * Free the memory to update the tables - this won't touch the actual
 333          * memory, so we can still use it for the copy after we have
 334          * reallocated the new space.
 335          */
 336         free(ptr);
 337
 338         block = find_free_block(size, type);
 339         if (block == NULL)
 340                 return NULL;
 341
 342         ret = (void *)((uintptr_t)block + HDRSIZE);
 343
 344         /*
 345          * If ret == ptr, then no copy is needed. Otherwise, move the memory to
 346          * the new location, which might be before the old one and overlap since
 347          * the free() above includes a _consolidate().
 348          */
 349         if (ret != ptr)
 350                 memmove(ret, ptr, osize > size ? size : osize);
 351
 352         /* Mark the block as used. */
 353         use_block(block, size);
 354
 355         return ret;
 356 }
 357
 358 struct align_region_t
 359 {
 360         /* If alignment is 0 then the region represents a large region which
 361          * has no metadata for tracking subelements. */
 362         int alignment;
 363         /* start in memory, and size in bytes */
 364         void* start;
 365         int size;
 366         /* layout within a region:
 367           - num_elements bytes, 0: free, 1: used, 2: used, combines with next
 368           - padding to alignment
 369           - data section
 370           - waste space
 371
 372           start_data points to the start of the data section
 373         */
 374         void* start_data;
 375         /* number of free blocks sized "alignment" */
 376         int free;
 377         struct align_region_t *next;
 378 };
 379
 380 static inline int region_is_large(const struct align_region_t *r)
 381 {
 382         return r->alignment == 0;
 383 }
 384
 385 static inline int addr_in_region(const struct align_region_t *r, void *addr)
 386 {
 387         return ((addr >= r->start_data) && (addr < r->start_data + r->size));
 388 }
 389
 390 /* num_elements == 0 indicates a large aligned region instead of a smaller
 391  * region comprised of alignment-sized chunks. */
 392 static struct align_region_t *allocate_region(int alignment, int num_elements,
 393                                         size_t size, struct memory_type *type)
 394 {
 395         struct align_region_t *r;
 396         size_t extra_space;
 397
 398 #if CONFIG(LP_DEBUG_MALLOC)
 399         printf("%s(old align_regions=%p, alignment=%u, num_elements=%u, size=%zu)\n",
 400                 __func__, type->align_regions, alignment, num_elements, size);
 401 #endif
 402
 403         r = malloc(sizeof(*r));
 404
 405         if (r == NULL)
 406                 return NULL;
 407
 408         memset(r, 0, sizeof(*r));
 409
 410         if (num_elements != 0) {
 411                 r->alignment = alignment;
 412                 r->size = num_elements * alignment;
 413                 r->free = num_elements;
 414                 /* Allocate enough memory for alignment requirements and
 415                  * metadata for each chunk. */
 416                 extra_space = num_elements;
 417         } else {
 418                 /* Large aligned allocation. Set alignment = 0. */
 419                 r->alignment = 0;
 420                 r->size = size;
 421                 extra_space = 0;
 422         }
 423
 424         r->start = alloc(r->size + alignment + extra_space, type);
 425
 426         if (r->start == NULL) {
 427                 free(r);
 428                 return NULL;
 429         }
 430
 431         r->start_data = (void *)ALIGN_UP((uintptr_t)r->start + extra_space,
 432                                         alignment);
 433
 434         /* Clear any (if requested) metadata. */
 435         memset(r->start, 0, extra_space);
 436
 437         /* Link the region with the rest. */
 438         r->next = type->align_regions;
 439         type->align_regions = r;
 440
 441         return r;
 442 }
 443
 444 static void try_free_region(struct align_region_t **prev_link)
 445 {
 446         struct align_region_t *r = *prev_link;
 447
 448         /* All large regions are immediately free-able. Non-large regions
 449          * need to be checked for the fully freed state. */
 450         if (!region_is_large(r)) {
 451                 if (r->free != r->size / r->alignment)
 452                         return;
 453         }
 454
 455         /* Unlink region from link list. */
 456         *prev_link = r->next;
 457
 458         /* Free the data and metadata. */
 459         free(r->start);
 460         free(r);
 461 }
 462
 463 static int free_aligned(void* addr, struct memory_type *type)
 464 {
 465         struct align_region_t **prev_link = &type->align_regions;
 466
 467         while (*prev_link != NULL)
 468         {
 469                 if (!addr_in_region(*prev_link, addr)) {
 470                         prev_link = &((*prev_link)->next);
 471                         continue;
 472                 }
 473
 474                 if (region_is_large(*prev_link)) {
 475                         try_free_region(prev_link);
 476                         return 1;
 477                 }
 478
 479                 int i = (addr-(*prev_link)->start_data)/(*prev_link)->alignment;
 480                 u8 *meta = (*prev_link)->start;
 481                 while (meta[i] == 2)
 482                 {
 483                         meta[i++] = 0;
 484                         (*prev_link)->free++;
 485                 }
 486                 meta[i] = 0;
 487                 (*prev_link)->free++;
 488                 try_free_region(prev_link);
 489                 return 1;
 490         }
 491         return 0;
 492 }
 493
 494 static void *alloc_aligned(size_t align, size_t size, struct memory_type *type)
 495 {
 496         /* Define a large request to be 1024 bytes for either alignment or
 497          * size of allocation. */
 498         const size_t large_request = 1024;
 499
 500         if (size == 0) return 0;
 501         if (type->align_regions == 0) {
 502                 type->align_regions = malloc(sizeof(struct align_region_t));
 503                 if (type->align_regions == NULL)
 504                         return NULL;
 505                 memset(type->align_regions, 0, sizeof(struct align_region_t));
 506         }
 507         struct align_region_t *reg = type->align_regions;
 508
 509         if (size >= large_request || align >= large_request) {
 510                 reg = allocate_region(align, 0, size, type);
 511                 if (reg == NULL)
 512                         return NULL;
 513                 return reg->start_data;
 514         }
 515
 516 look_further:
 517         while (reg != 0)
 518         {
 519                 if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align))
 520                 {
 521 #if CONFIG(LP_DEBUG_MALLOC)
 522                         printf("  found memalign region. %u free, %zu required\n", reg->free, (size + align - 1)/align);
 523 #endif
 524                         break;
 525                 }
 526                 reg = reg->next;
 527         }
 528         if (reg == 0)
 529         {
 530 #if CONFIG(LP_DEBUG_MALLOC)
 531                 printf("  need to allocate a new memalign region\n");
 532 #endif
 533                 /* get align regions */
 534                 reg = allocate_region(align, large_request/align, size, type);
 535 #if CONFIG(LP_DEBUG_MALLOC)
 536                 printf("  ... returned %p\n", reg);
 537 #endif
 538         }
 539         if (reg == 0) {
 540                 /* Nothing available. */
 541                 return (void *)NULL;
 542         }
 543
 544         int i, count = 0, target = (size+align-1)/align;
 545         for (i = 0; i < (reg->size/align); i++)
 546         {
 547                 if (((u8*)reg->start)[i] == 0)
 548                 {
 549                         count++;
 550                         if (count == target) {
 551                                 count = i+1-count;
 552                                 for (i=0; i<target-1; i++)
 553                                 {
 554                                         ((u8*)reg->start)[count+i]=2;
 555                                 }
 556                                 ((u8*)reg->start)[count+target-1]=1;
 557                                 reg->free -= target;
 558                                 return reg->start_data+(align*count);
 559                         }
 560                 } else {
 561                         count = 0;
 562                 }
 563         }
 564         /* The free space in this region is fragmented,
 565            so we will move on and try the next one: */
 566         reg = reg->next;
 567         goto look_further; // end condition is once a new region is allocated - it always has enough space
 568 }
 569
 570 void *memalign(size_t align, size_t size)
 571 {
 572         return alloc_aligned(align, size, heap);
 573 }
 574
 575 void *dma_memalign(size_t align, size_t size)
 576 {
 577         return alloc_aligned(align, size, dma);
 578 }
 579
 580 /* This is for debugging purposes. */
 581 #if CONFIG(LP_DEBUG_MALLOC)
 582 void print_malloc_map(void)
 583 {
 584         struct memory_type *type = heap;
 585         void *ptr;
 586         int free_memory;
 587
 588 again:
 589         ptr = type->start;
 590         free_memory = 0;
 591
 592         while (ptr < type->end) {
 593                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 594
 595                 if (!HAS_MAGIC(hdr)) {
 596                         if (type->magic_initialized)
 597                                 printf("%s: Poisoned magic - we're toast\n", type->name);
 598                         else
 599                                 printf("%s: No magic yet - going to initialize\n", type->name);
 600                         break;
 601                 }
 602
 603                 /* FIXME: Verify the size of the block. */
 604
 605                 printf("%s %x: %s (%llx bytes)\n", type->name,
 606                        (unsigned int)(ptr - type->start),
 607                        hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
 608
 609                 if (hdr & FLAG_FREE)
 610                         free_memory += SIZE(hdr);
 611
 612                 ptr += HDRSIZE + SIZE(hdr);
 613         }
 614
 615         if (free_memory && (type->minimal_free > free_memory))
 616                 type->minimal_free = free_memory;
 617         printf("%s: Maximum memory consumption: %zu bytes\n", type->name,
 618                 (type->end - type->start) - HDRSIZE - type->minimal_free);
 619
 620         if (type != dma) {
 621                 type = dma;
 622                 goto again;
 623         }
 624 }
 625 #endif