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 /* This is a classically weak malloc() implmentation.
  31    We have a relatively small and static heap, so we take
  32    the easy route with an O(N) loop through the tree for
  33    every malloc() and free().  Obviously, this doesn't scale
  34    past a few hundred K (if that).
  35
  36    We're also susecptable to the usual buffer overun poisoning,
  37    though the risk is within acceptable ranges for this
  38    implementation (don't overrun your buffers, kids!)
  39 */
  40
  41 #include <libpayload.h>
  42
  43 /* Defined in the ldscript */
  44 extern char _heap, _eheap;
  45
  46 static void *hstart = (void *) &_heap;
  47 static void *hend = (void *) &_eheap;
  48
  49 typedef unsigned int hdrtype_t;
  50
  51 #define MAGIC     (0x2a << 26)
  52 #define FLAG_FREE (1 << 25)
  53 #define FLAG_USED (1 << 24)
  54
  55 #define SIZE(_h) ((_h) & 0xFFFFFF)
  56
  57 #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & 0xFFFFFF)))
  58
  59 #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE)
  60 #define USED_BLOCK(_s) _HEADER(_s, FLAG_USED)
  61
  62 #define HDRSIZE (sizeof(hdrtype_t))
  63
  64 #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE))
  65 #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC)
  66
  67 void print_malloc_map(void);
  68
  69 static void setup(void)
  70 {
  71         int size = (unsigned int) (_heap - _eheap) - HDRSIZE;
  72         *((hdrtype_t *) hstart) = FREE_BLOCK(size);
  73 }
  74
  75 static void *alloc(int len)
  76 {
  77         hdrtype_t header;
  78         void *ptr = hstart;
  79
  80         /* align the size */
  81         len = (len + 3) & ~3;
  82
  83         if (!len || len > 0xFFFFFF)
  84                 return (void *) NULL;
  85
  86         /* Make sure the region is setup correctly */
  87         if (!HAS_MAGIC(*((hdrtype_t *) ptr)))
  88                 setup();
  89
  90         /* Find some free space */
  91
  92         do {
  93                 header = *((hdrtype_t *) ptr);
  94                 int size = SIZE(header);
  95
  96                 if (header & FLAG_FREE) {
  97
  98                         if (len <= size) {
  99                                 void *nptr = ptr + HDRSIZE + len;
 100                                 int nsize = size - (len + 8);
 101
 102                                 /* Mark the block as used */
 103                                 *((hdrtype_t *) ptr) = USED_BLOCK(len);
 104
 105                                 /* If there is still room in this block,
 106                                  * then mark it as such */
 107
 108                                 if (nsize > 0)
 109                                         *((hdrtype_t *) nptr) =
 110                                                 FREE_BLOCK(nsize - 4);
 111
 112                                 return (void *) (ptr + HDRSIZE);
 113                         }
 114                 }
 115
 116                 ptr += HDRSIZE + size;
 117
 118         } while(ptr < hend);
 119
 120         /* Nothing available */
 121         return (void *) NULL;
 122 }
 123
 124 static void _consolidate(void)
 125 {
 126         void *ptr = hstart;
 127
 128         while(ptr < hend) {
 129                 void *nptr;
 130                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 131                 unsigned int size = 0;
 132
 133                 if (!IS_FREE(hdr)) {
 134                         ptr += HDRSIZE + SIZE(hdr);
 135                         continue;
 136                 }
 137
 138                 size = SIZE(hdr);
 139                 nptr = ptr + HDRSIZE + SIZE(hdr);
 140
 141                 while (nptr < hend) {
 142                         hdrtype_t nhdr =  *((hdrtype_t *) nptr);
 143
 144                         if (!(IS_FREE(nhdr)))
 145                                 break;
 146
 147                         size += SIZE(nhdr) + HDRSIZE;
 148
 149                         *((hdrtype_t *) nptr) = 0;
 150
 151                         nptr += (HDRSIZE + SIZE(nhdr));
 152                 }
 153
 154                 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
 155                 ptr = nptr;
 156         }
 157 }
 158
 159 void free(void *ptr)
 160 {
 161         hdrtype_t hdr;
 162
 163         ptr -= HDRSIZE;
 164
 165         /* Sanity check */
 166         if (ptr < hstart || ptr >= hend)
 167                 return;
 168
 169         hdr = *((hdrtype_t *) ptr);
 170
 171         /* Not our header (we're probably poisoned) */
 172         if (!HAS_MAGIC(hdr))
 173                 return;
 174
 175         /* Double free */
 176         if (hdr & FLAG_FREE)
 177                 return;
 178
 179         *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
 180         _consolidate();
 181 }
 182
 183 void *malloc(size_t size)
 184 {
 185         return alloc(size);
 186 }
 187
 188 void *calloc(size_t nmemb, size_t size)
 189 {
 190         unsigned int total = (nmemb * size);
 191         void *ptr = alloc(size);
 192
 193         if (ptr)
 194                 memset(ptr, 0, total);
 195
 196         return ptr;
 197 }
 198
 199 void *realloc(void *ptr, size_t size)
 200 {
 201         void *ret;
 202         void *pptr;
 203         unsigned int osize;
 204
 205         if (ptr == NULL)
 206                 return alloc(size);
 207
 208         pptr = ptr - HDRSIZE;
 209
 210         if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
 211                 return NULL;
 212
 213         /* Get the original size of the block */
 214         osize = SIZE(*((hdrtype_t *) pptr));
 215
 216         /* Free the memory to update the tables - this
 217            won't touch the actual memory, so we can still
 218            use it for the copy after we have reallocated
 219            the new space
 220         */
 221
 222         free(ptr);
 223         ret = alloc(size);
 224
 225         /* if ret == NULL, then doh - failure.
 226            if ret == ptr then woo-hoo!  no copy needed */
 227
 228         if (ret == NULL || ret == ptr)
 229                 return ret;
 230
 231         /* Copy the memory to the new location */
 232         memcpy(ret, ptr, osize > size ? size : osize);
 233         return ret;
 234 }
 235
 236 /* This is for debugging purposes */
 237 #ifdef TEST
 238
 239 void print_malloc_map(void)
 240 {
 241         void *ptr = hstart;
 242
 243         while(ptr < hend) {
 244                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 245
 246                 if (!HAS_MAGIC(hdr)) {
 247                         printf("Poisoned magic - we're toast\n");
 248                         break;
 249                 }
 250
 251                 /* FIXME:  Verify the size of the block */
 252
 253                 printf("%x: %s (%x bytes)\n",
 254                        (unsigned int) (ptr - hstart),
 255                        hdr & FLAG_FREE ? "FREE" : "USED",
 256                        SIZE(hdr));
 257
 258                 ptr += HDRSIZE + SIZE(hdr);
 259         }
 260 }
 261
 262 #endif