Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 1 | /* |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 2 | * |
| 3 | * Copyright (C) 2008 Advanced Micro Devices, Inc. |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 4 | * Copyright (C) 2008-2010 coresystems GmbH |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 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 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 30 | /* |
Uwe Hermann | 661e380 | 2008-03-21 18:37:23 +0000 | [diff] [blame] | 31 | * This is a classically weak malloc() implementation. We have a relatively |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 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 | * |
Uwe Hermann | 661e380 | 2008-03-21 18:37:23 +0000 | [diff] [blame] | 36 | * We're also susceptible to the usual buffer overrun poisoning, though the |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 37 | * risk is within acceptable ranges for this implementation (don't overrun |
| 38 | * your buffers, kids!). |
| 39 | */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 40 | |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 41 | #define IN_MALLOC_C |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 42 | #include <libpayload.h> |
Furquan Shaikh | 79a591f | 2014-05-13 13:47:32 -0700 | [diff] [blame] | 43 | #include <stdint.h> |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 44 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 45 | struct memory_type { |
| 46 | void *start; |
| 47 | void *end; |
| 48 | struct align_region_t* align_regions; |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 49 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 50 | int magic_initialized; |
| 51 | size_t minimal_free; |
| 52 | const char *name; |
| 53 | #endif |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 54 | }; |
| 55 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 56 | extern char _heap, _eheap; /* Defined in the ldscript. */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 57 | |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 58 | static struct memory_type default_type = |
| 59 | { (void *)&_heap, (void *)&_eheap, NULL |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 60 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 61 | , 0, 0, "HEAP" |
| 62 | #endif |
| 63 | }; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 64 | static struct memory_type *const heap = &default_type; |
| 65 | static struct memory_type *dma = &default_type; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 66 | |
Nico Huber | 25dd247 | 2013-06-14 15:34:59 +0200 | [diff] [blame] | 67 | typedef u64 hdrtype_t; |
Nico Huber | 2d4b4ca | 2013-06-14 15:26:49 +0200 | [diff] [blame] | 68 | #define HDRSIZE (sizeof(hdrtype_t)) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 69 | |
Nico Huber | 2d4b4ca | 2013-06-14 15:26:49 +0200 | [diff] [blame] | 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) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 74 | |
Nico Huber | 3665ace | 2012-10-08 15:03:35 +0200 | [diff] [blame] | 75 | #define SIZE(_h) ((_h) & MAX_SIZE) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 76 | |
Nico Huber | 3665ace | 2012-10-08 15:03:35 +0200 | [diff] [blame] | 77 | #define _HEADER(_s, _f) ((hdrtype_t) (MAGIC | (_f) | ((_s) & MAX_SIZE))) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 78 | |
| 79 | #define FREE_BLOCK(_s) _HEADER(_s, FLAG_FREE) |
Nico Huber | 3665ace | 2012-10-08 15:03:35 +0200 | [diff] [blame] | 80 | #define USED_BLOCK(_s) _HEADER(_s, 0) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 81 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 82 | #define IS_FREE(_h) (((_h) & (MAGIC | FLAG_FREE)) == (MAGIC | FLAG_FREE)) |
| 83 | #define HAS_MAGIC(_h) (((_h) & MAGIC) == MAGIC) |
| 84 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 85 | static int free_aligned(void* addr, struct memory_type *type); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 86 | void print_malloc_map(void); |
| 87 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 88 | void init_dma_memory(void *start, u32 size) |
| 89 | { |
Julius Werner | 509c37e | 2013-08-28 12:29:28 -0700 | [diff] [blame] | 90 | if (dma_initialized()) { |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 91 | printf("ERROR: %s called twice!\n", __func__); |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 92 | return; |
| 93 | } |
| 94 | |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 95 | /* |
Martin Roth | e81ce04 | 2017-06-03 20:00:36 -0600 | [diff] [blame] | 96 | * DMA memory might not be zeroed by coreboot on stage loading, so make |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 97 | * sure we clear the magic cookie from last boot. |
| 98 | */ |
| 99 | *(hdrtype_t *)start = 0; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 100 | |
| 101 | dma = malloc(sizeof(*dma)); |
| 102 | dma->start = start; |
| 103 | dma->end = start + size; |
| 104 | dma->align_regions = NULL; |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 105 | |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 106 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 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 |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 113 | } |
| 114 | |
Arthur Heymans | ae57f1d | 2023-08-25 13:07:25 +0200 | [diff] [blame] | 115 | int dma_initialized(void) |
Julius Werner | 509c37e | 2013-08-28 12:29:28 -0700 | [diff] [blame] | 116 | { |
| 117 | return dma != heap; |
| 118 | } |
| 119 | |
| 120 | /* For boards that don't initialize DMA we assume all locations are coherent */ |
Yu-Ping Wu | 30d8e72 | 2022-08-23 16:40:03 +0800 | [diff] [blame] | 121 | int dma_coherent(const void *ptr) |
Julius Werner | 509c37e | 2013-08-28 12:29:28 -0700 | [diff] [blame] | 122 | { |
| 123 | return !dma_initialized() || (dma->start <= ptr && dma->end > ptr); |
| 124 | } |
| 125 | |
Yi Chou | 582c2a7 | 2023-10-16 11:34:52 +0800 | [diff] [blame^] | 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 | |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 138 | /* Find free block of size >= len */ |
| 139 | static hdrtype_t volatile *find_free_block(int len, struct memory_type *type) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 140 | { |
| 141 | hdrtype_t header; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 142 | hdrtype_t volatile *ptr = (hdrtype_t volatile *)type->start; |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 143 | |
| 144 | /* Align the size. */ |
Patrick Georgi | 04a5b48 | 2015-01-21 17:37:34 +0100 | [diff] [blame] | 145 | len = ALIGN_UP(len, HDRSIZE); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 146 | |
Nico Huber | 3665ace | 2012-10-08 15:03:35 +0200 | [diff] [blame] | 147 | if (!len || len > MAX_SIZE) |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 148 | return (void *)NULL; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 149 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 150 | /* Make sure the region is setup correctly. */ |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 151 | if (!HAS_MAGIC(*ptr)) { |
| 152 | size_t size = (type->end - type->start) - HDRSIZE; |
| 153 | *ptr = FREE_BLOCK(size); |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 154 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 155 | type->magic_initialized = 1; |
| 156 | type->minimal_free = size; |
| 157 | #endif |
| 158 | } |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 159 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 160 | /* Find some free space. */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 161 | do { |
Marc Jones | 987e883 | 2012-03-01 16:12:11 -0700 | [diff] [blame] | 162 | header = *ptr; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 163 | int size = SIZE(header); |
| 164 | |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 165 | if (!HAS_MAGIC(header) || size == 0) { |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 166 | printf("memory allocator panic. (%s%s)\n", |
| 167 | !HAS_MAGIC(header) ? " no magic " : "", |
| 168 | size == 0 ? " size=0 " : ""); |
Jordan Crouse | 24a0404 | 2008-04-25 23:08:47 +0000 | [diff] [blame] | 169 | halt(); |
Stefan Reinauer | ee67319 | 2008-08-14 14:40:10 +0000 | [diff] [blame] | 170 | } |
Jordan Crouse | 24a0404 | 2008-04-25 23:08:47 +0000 | [diff] [blame] | 171 | |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 172 | if ((header & FLAG_FREE) && len <= size) |
| 173 | return ptr; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 174 | |
Furquan Shaikh | 79a591f | 2014-05-13 13:47:32 -0700 | [diff] [blame] | 175 | ptr = (hdrtype_t volatile *)((uintptr_t)ptr + HDRSIZE + size); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 176 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 177 | } while (ptr < (hdrtype_t *) type->end); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 178 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 179 | /* Nothing available. */ |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 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); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 219 | } |
| 220 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 221 | static void _consolidate(struct memory_type *type) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 222 | { |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 223 | void *ptr = type->start; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 224 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 225 | while (ptr < type->end) { |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 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 | } |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 234 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 235 | size = SIZE(hdr); |
| 236 | nptr = ptr + HDRSIZE + SIZE(hdr); |
| 237 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 238 | while (nptr < type->end) { |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 239 | hdrtype_t nhdr = *((hdrtype_t *) nptr); |
| 240 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 241 | if (!(IS_FREE(nhdr))) |
| 242 | break; |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 243 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 244 | size += SIZE(nhdr) + HDRSIZE; |
| 245 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 246 | *((hdrtype_t *) nptr) = 0; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 247 | |
| 248 | nptr += (HDRSIZE + SIZE(nhdr)); |
| 249 | } |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 250 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 251 | *((hdrtype_t *) ptr) = FREE_BLOCK(size); |
| 252 | ptr = nptr; |
| 253 | } |
| 254 | } |
| 255 | |
| 256 | void free(void *ptr) |
| 257 | { |
| 258 | hdrtype_t hdr; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 259 | struct memory_type *type = heap; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 260 | |
Hsuan Ting Chen | 8742e2a | 2020-09-17 15:51:34 +0800 | [diff] [blame] | 261 | /* No action occurs on NULL. */ |
| 262 | if (ptr == NULL) |
| 263 | return; |
| 264 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 265 | /* Sanity check. */ |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 266 | if (ptr < type->start || ptr >= type->end) { |
| 267 | type = dma; |
| 268 | if (ptr < type->start || ptr >= type->end) |
| 269 | return; |
| 270 | } |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 271 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 272 | if (free_aligned(ptr, type)) return; |
| 273 | |
| 274 | ptr -= HDRSIZE; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 275 | hdr = *((hdrtype_t *) ptr); |
| 276 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 277 | /* Not our header (we're probably poisoned). */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 278 | if (!HAS_MAGIC(hdr)) |
| 279 | return; |
| 280 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 281 | /* Double free. */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 282 | if (hdr & FLAG_FREE) |
| 283 | return; |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 284 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 285 | *((hdrtype_t *) ptr) = FREE_BLOCK(SIZE(hdr)); |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 286 | _consolidate(type); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 287 | } |
| 288 | |
| 289 | void *malloc(size_t size) |
| 290 | { |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 291 | return alloc(size, heap); |
| 292 | } |
| 293 | |
| 294 | void *dma_malloc(size_t size) |
| 295 | { |
| 296 | return alloc(size, dma); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 297 | } |
| 298 | |
| 299 | void *calloc(size_t nmemb, size_t size) |
| 300 | { |
Jordan Crouse | 24a0404 | 2008-04-25 23:08:47 +0000 | [diff] [blame] | 301 | size_t total = nmemb * size; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 302 | void *ptr = alloc(total, heap); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 303 | |
| 304 | if (ptr) |
| 305 | memset(ptr, 0, total); |
| 306 | |
| 307 | return ptr; |
| 308 | } |
| 309 | |
| 310 | void *realloc(void *ptr, size_t size) |
| 311 | { |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 312 | void *ret, *pptr; |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 313 | hdrtype_t volatile *block; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 314 | unsigned int osize; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 315 | struct memory_type *type = heap; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 316 | |
| 317 | if (ptr == NULL) |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 318 | return alloc(size, type); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 319 | |
| 320 | pptr = ptr - HDRSIZE; |
| 321 | |
| 322 | if (!HAS_MAGIC(*((hdrtype_t *) pptr))) |
| 323 | return NULL; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 324 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 325 | if (ptr < type->start || ptr >= type->end) |
| 326 | type = dma; |
| 327 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 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); |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 337 | |
| 338 | block = find_free_block(size, type); |
| 339 | if (block == NULL) |
| 340 | return NULL; |
| 341 | |
| 342 | ret = (void *)((uintptr_t)block + HDRSIZE); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 343 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 344 | /* |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 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(). |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 348 | */ |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 349 | if (ret != ptr) |
| 350 | memmove(ret, ptr, osize > size ? size : osize); |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 351 | |
Yu-Ping Wu | aec3b1f | 2020-09-11 14:39:03 +0800 | [diff] [blame] | 352 | /* Mark the block as used. */ |
| 353 | use_block(block, size); |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 354 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 355 | return ret; |
| 356 | } |
| 357 | |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 358 | struct align_region_t |
| 359 | { |
Elyes HAOUAS | 824b4b8 | 2020-02-15 09:27:11 +0100 | [diff] [blame] | 360 | /* If alignment is 0 then the region represents a large region which |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 361 | * has no metadata for tracking subelements. */ |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 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 | |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 380 | static inline int region_is_large(const struct align_region_t *r) |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 381 | { |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 382 | return r->alignment == 0; |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 383 | } |
| 384 | |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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 | |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 398 | #if CONFIG(LP_DEBUG_MALLOC) |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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 | |
Jonathan Neuschäfer | a4fbc38 | 2016-04-05 21:36:34 +0200 | [diff] [blame] | 408 | memset(r, 0, sizeof(*r)); |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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 | } |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 462 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 463 | static int free_aligned(void* addr, struct memory_type *type) |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 464 | { |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 465 | struct align_region_t **prev_link = &type->align_regions; |
| 466 | |
| 467 | while (*prev_link != NULL) |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 468 | { |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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); |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 476 | return 1; |
| 477 | } |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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; |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 490 | } |
| 491 | return 0; |
| 492 | } |
| 493 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 494 | 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] | 495 | { |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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 | |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 500 | if (size == 0) return 0; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 501 | if (type->align_regions == 0) { |
| 502 | type->align_regions = malloc(sizeof(struct align_region_t)); |
| 503 | if (type->align_regions == NULL) |
Stefan Reinauer | 5fe6e23 | 2009-07-31 11:39:55 +0000 | [diff] [blame] | 504 | return NULL; |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 505 | memset(type->align_regions, 0, sizeof(struct align_region_t)); |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 506 | } |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 507 | struct align_region_t *reg = type->align_regions; |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 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 | |
Stefan Reinauer | 14e2277 | 2010-04-27 06:56:47 +0000 | [diff] [blame] | 516 | look_further: |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 517 | while (reg != 0) |
| 518 | { |
| 519 | if ((reg->alignment == align) && (reg->free >= (size + align - 1)/align)) |
| 520 | { |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 521 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | f5b76fe | 2016-05-19 13:15:16 -0700 | [diff] [blame] | 522 | printf(" found memalign region. %u free, %zu required\n", reg->free, (size + align - 1)/align); |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 523 | #endif |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 524 | break; |
| 525 | } |
| 526 | reg = reg->next; |
| 527 | } |
| 528 | if (reg == 0) |
| 529 | { |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 530 | #if CONFIG(LP_DEBUG_MALLOC) |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 531 | printf(" need to allocate a new memalign region\n"); |
| 532 | #endif |
| 533 | /* get align regions */ |
Aaron Durbin | 8bbd04e | 2015-01-22 08:59:03 -0600 | [diff] [blame] | 534 | reg = allocate_region(align, large_request/align, size, type); |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 535 | #if CONFIG(LP_DEBUG_MALLOC) |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 536 | printf(" ... returned %p\n", reg); |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 537 | #endif |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 538 | } |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 539 | if (reg == 0) { |
| 540 | /* Nothing available. */ |
| 541 | return (void *)NULL; |
| 542 | } |
| 543 | |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 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 | } |
Nico Huber | 7a32e88 | 2012-11-22 17:37:32 +0100 | [diff] [blame] | 564 | /* The free space in this region is fragmented, |
| 565 | so we will move on and try the next one: */ |
| 566 | reg = reg->next; |
Stefan Reinauer | 1ff26a7 | 2009-04-29 19:11:18 +0000 | [diff] [blame] | 567 | 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] | 568 | } |
| 569 | |
Julius Werner | b8fad3d | 2013-08-27 15:48:32 -0700 | [diff] [blame] | 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 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 580 | /* This is for debugging purposes. */ |
Julius Werner | eab2a29 | 2019-03-05 16:55:15 -0800 | [diff] [blame] | 581 | #if CONFIG(LP_DEBUG_MALLOC) |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 582 | void print_malloc_map(void) |
| 583 | { |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 584 | struct memory_type *type = heap; |
| 585 | void *ptr; |
| 586 | int free_memory; |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 587 | |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 588 | again: |
| 589 | ptr = type->start; |
| 590 | free_memory = 0; |
| 591 | |
| 592 | while (ptr < type->end) { |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 593 | hdrtype_t hdr = *((hdrtype_t *) ptr); |
| 594 | |
| 595 | if (!HAS_MAGIC(hdr)) { |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 596 | if (type->magic_initialized) |
| 597 | printf("%s: Poisoned magic - we're toast\n", type->name); |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 598 | else |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 599 | printf("%s: No magic yet - going to initialize\n", type->name); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 600 | break; |
| 601 | } |
| 602 | |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 603 | /* FIXME: Verify the size of the block. */ |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 604 | |
Julius Werner | f5b76fe | 2016-05-19 13:15:16 -0700 | [diff] [blame] | 605 | printf("%s %x: %s (%llx bytes)\n", type->name, |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 606 | (unsigned int)(ptr - type->start), |
Uwe Hermann | 6a441bf | 2008-03-20 19:54:59 +0000 | [diff] [blame] | 607 | hdr & FLAG_FREE ? "FREE" : "USED", SIZE(hdr)); |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 608 | |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 609 | if (hdr & FLAG_FREE) |
| 610 | free_memory += SIZE(hdr); |
| 611 | |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 612 | ptr += HDRSIZE + SIZE(hdr); |
| 613 | } |
Stefan Reinauer | e5d30b7 | 2010-03-25 22:15:19 +0000 | [diff] [blame] | 614 | |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 615 | if (free_memory && (type->minimal_free > free_memory)) |
| 616 | type->minimal_free = free_memory; |
Julius Werner | f5b76fe | 2016-05-19 13:15:16 -0700 | [diff] [blame] | 617 | printf("%s: Maximum memory consumption: %zu bytes\n", type->name, |
Julius Werner | 9665d38 | 2013-09-13 18:21:46 -0700 | [diff] [blame] | 618 | (type->end - type->start) - HDRSIZE - type->minimal_free); |
| 619 | |
| 620 | if (type != dma) { |
| 621 | type = dma; |
| 622 | goto again; |
| 623 | } |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 624 | } |
Jordan Crouse | f6145c3 | 2008-03-19 23:56:58 +0000 | [diff] [blame] | 625 | #endif |