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 void print_malloc_map(void);
  67
  68 static void setup(void)
  69 {
  70         int size = (unsigned int)(&_eheap - &_heap) - HDRSIZE;
  71
  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         do {
  92                 header = *((hdrtype_t *) ptr);
  93                 int size = SIZE(header);
  94
  95                 if (!HAS_MAGIC(header) || size == 0)
  96                         halt();
  97
  98                 if (header & FLAG_FREE) {
  99                         if (len <= size) {
 100                                 void *nptr = ptr + (HDRSIZE + len);
 101                                 int nsize = size - (len + 8);
 102
 103                                 /* Mark the block as used. */
 104                                 *((hdrtype_t *) ptr) = USED_BLOCK(len);
 105
 106                                 /* If there is still room in this block,
 107                                  * then mark it as such.
 108                                  */
 109
 110                                 if (nsize > 0)
 111                                         *((hdrtype_t *) nptr) =
 112                                             FREE_BLOCK(nsize - 4);
 113
 114                                 return (void *)(ptr + HDRSIZE);
 115                         }
 116                 }
 117
 118                 ptr += HDRSIZE + size;
 119
 120         } while (ptr < hend);
 121
 122         /* Nothing available. */
 123         return (void *)NULL;
 124 }
 125
 126 static void _consolidate(void)
 127 {
 128         void *ptr = hstart;
 129
 130         while (ptr < hend) {
 131                 void *nptr;
 132                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 133                 unsigned int size = 0;
 134
 135                 if (!IS_FREE(hdr)) {
 136                         ptr += HDRSIZE + SIZE(hdr);
 137                         continue;
 138                 }
 139
 140                 size = SIZE(hdr);
 141                 nptr = ptr + HDRSIZE + SIZE(hdr);
 142
 143                 while (nptr < hend) {
 144                         hdrtype_t nhdr = *((hdrtype_t *) nptr);
 145
 146                         if (!(IS_FREE(nhdr)))
 147                                 break;
 148
 149                         size += SIZE(nhdr) + HDRSIZE;
 150
 151                         *((hdrtype_t *) nptr) = 0;
 152
 153                         nptr += (HDRSIZE + SIZE(nhdr));
 154                 }
 155
 156                 *((hdrtype_t *) ptr) = FREE_BLOCK(size);
 157                 ptr = nptr;
 158         }
 159 }
 160
 161 void free(void *ptr)
 162 {
 163         hdrtype_t hdr;
 164
 165         ptr -= HDRSIZE;
 166
 167         /* Sanity check. */
 168         if (ptr < hstart || ptr >= hend)
 169                 return;
 170
 171         hdr = *((hdrtype_t *) ptr);
 172
 173         /* Not our header (we're probably poisoned). */
 174         if (!HAS_MAGIC(hdr))
 175                 return;
 176
 177         /* Double free. */
 178         if (hdr & FLAG_FREE)
 179                 return;
 180
 181         *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr));
 182         _consolidate();
 183 }
 184
 185 void *malloc(size_t size)
 186 {
 187         return alloc(size);
 188 }
 189
 190 void *calloc(size_t nmemb, size_t size)
 191 {
 192         size_t total = nmemb * size;
 193         void *ptr = alloc(total);
 194
 195         if (ptr)
 196                 memset(ptr, 0, total);
 197
 198         return ptr;
 199 }
 200
 201 void *realloc(void *ptr, size_t size)
 202 {
 203         void *ret, *pptr;
 204         unsigned int osize;
 205
 206         if (ptr == NULL)
 207                 return alloc(size);
 208
 209         pptr = ptr - HDRSIZE;
 210
 211         if (!HAS_MAGIC(*((hdrtype_t *) pptr)))
 212                 return NULL;
 213
 214         /* Get the original size of the block. */
 215         osize = SIZE(*((hdrtype_t *) pptr));
 216
 217         /*
 218          * Free the memory to update the tables - this won't touch the actual
 219          * memory, so we can still use it for the copy after we have
 220          * reallocated the new space.
 221          */
 222         free(ptr);
 223         ret = alloc(size);
 224
 225         /*
 226          * if ret == NULL, then doh - failure.
 227          * if ret == ptr then woo-hoo! no copy needed.
 228          */
 229         if (ret == NULL || ret == ptr)
 230                 return ret;
 231
 232         /* Copy the memory to the new location. */
 233         memcpy(ret, ptr, osize > size ? size : osize);
 234
 235         return ret;
 236 }
 237
 238 /* This is for debugging purposes. */
 239 #ifdef TEST
 240 void print_malloc_map(void)
 241 {
 242         void *ptr = hstart;
 243
 244         while (ptr < hend) {
 245                 hdrtype_t hdr = *((hdrtype_t *) ptr);
 246
 247                 if (!HAS_MAGIC(hdr)) {
 248                         printf("Poisoned magic - we're toast\n");
 249                         break;
 250                 }
 251
 252                 /* FIXME: Verify the size of the block. */
 253
 254                 printf("%x: %s (%x bytes)\n",
 255                        (unsigned int)(ptr - hstart),
 256                        hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr));
 257
 258                 ptr += HDRSIZE + SIZE(hdr);
 259         }
 260 }
 261 #endif