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