Cefn Hoile
Attempting to publish a tree
Dependencies: BLE_API mbed-dev-bin nRF51822
Fork of
microbit-dal
by 
Lancaster University
source/core/MicroBitHeapAllocator.cpp@18:ce4dd8fcdf4f, 2016-06-01 (annotated)
- Committer:
- cefn
- Date:
- Wed Jun 01 17:43:26 2016 +0000
- Revision:
- 18:ce4dd8fcdf4f
- Parent:
- 1:8aa5cdb4ab67
Attempting to publish a tree
Who changed what in which revision?
| User | Revision | Line number | New contents of line |
|---|---|---|---|
| Jonathan Austin |
1:8aa5cdb4ab67 | 1 | /* |
| Jonathan Austin |
1:8aa5cdb4ab67 | 2 | The MIT License (MIT) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 3 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 4 | Copyright (c) 2016 British Broadcasting Corporation. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 5 | This software is provided by Lancaster University by arrangement with the BBC. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 6 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 7 | Permission is hereby granted, free of charge, to any person obtaining a |
| Jonathan Austin |
1:8aa5cdb4ab67 | 8 | copy of this software and associated documentation files (the "Software"), |
| Jonathan Austin |
1:8aa5cdb4ab67 | 9 | to deal in the Software without restriction, including without limitation |
| Jonathan Austin |
1:8aa5cdb4ab67 | 10 | the rights to use, copy, modify, merge, publish, distribute, sublicense, |
| Jonathan Austin |
1:8aa5cdb4ab67 | 11 | and/or sell copies of the Software, and to permit persons to whom the |
| Jonathan Austin |
1:8aa5cdb4ab67 | 12 | Software is furnished to do so, subject to the following conditions: |
| Jonathan Austin |
1:8aa5cdb4ab67 | 13 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 14 | The above copyright notice and this permission notice shall be included in |
| Jonathan Austin |
1:8aa5cdb4ab67 | 15 | all copies or substantial portions of the Software. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 16 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 17 | THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR |
| Jonathan Austin |
1:8aa5cdb4ab67 | 18 | IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, |
| Jonathan Austin |
1:8aa5cdb4ab67 | 19 | FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL |
| Jonathan Austin |
1:8aa5cdb4ab67 | 20 | THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER |
| Jonathan Austin |
1:8aa5cdb4ab67 | 21 | LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING |
| Jonathan Austin |
1:8aa5cdb4ab67 | 22 | FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER |
| Jonathan Austin |
1:8aa5cdb4ab67 | 23 | DEALINGS IN THE SOFTWARE. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 24 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 25 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 26 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 27 | * A simple 32 bit block based memory allocator. This allows one or more memory segments to |
| Jonathan Austin |
1:8aa5cdb4ab67 | 28 | * be designated as heap storage, and is designed to run in a static memory area or inside the standard C |
| Jonathan Austin |
1:8aa5cdb4ab67 | 29 | * heap for use by the micro:bit runtime. This is required for several reasons: |
| Jonathan Austin |
1:8aa5cdb4ab67 | 30 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 31 | * 1) It reduces memory fragmentation due to the high churn sometime placed on the heap |
| Jonathan Austin |
1:8aa5cdb4ab67 | 32 | * by ManagedTypes, fibers and user code. Underlying heap implentations are often have very simplistic |
| Jonathan Austin |
1:8aa5cdb4ab67 | 33 | * allocation pilicies and suffer from fragmentation in prolonged use - which can cause programs to |
| Jonathan Austin |
1:8aa5cdb4ab67 | 34 | * stop working after a period of time. The algorithm implemented here is simple, but highly tolerant to |
| Jonathan Austin |
1:8aa5cdb4ab67 | 35 | * large amounts of churn. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 36 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 37 | * 2) It allows us to reuse the 8K of SRAM set aside for SoftDevice as additional heap storage |
| Jonathan Austin |
1:8aa5cdb4ab67 | 38 | * when BLE is not in use. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 39 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 40 | * 3) It gives a simple example of how memory allocation works! :-) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 41 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 42 | * P.S. This is a very simple allocator, therefore not without its weaknesses. Why don't you consider |
| Jonathan Austin |
1:8aa5cdb4ab67 | 43 | * what these are, and consider the tradeoffs against simplicity... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 44 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 45 | * @note The need for this should be reviewed in the future, if a different memory allocator is |
| Jonathan Austin |
1:8aa5cdb4ab67 | 46 | * made availiable in the mbed platform. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 47 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 48 | * TODO: Consider caching recently freed blocks to improve allocation time. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 49 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 50 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 51 | #include "MicroBitConfig.h" |
| Jonathan Austin |
1:8aa5cdb4ab67 | 52 | #include "MicroBitHeapAllocator.h" |
| Jonathan Austin |
1:8aa5cdb4ab67 | 53 | #include "MicroBitDevice.h" |
| Jonathan Austin |
1:8aa5cdb4ab67 | 54 | #include "ErrorNo.h" |
| Jonathan Austin |
1:8aa5cdb4ab67 | 55 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 56 | struct HeapDefinition |
| Jonathan Austin |
1:8aa5cdb4ab67 | 57 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 58 | uint32_t *heap_start; // Physical address of the start of this heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 59 | uint32_t *heap_end; // Physical address of the end of this heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 60 | }; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 61 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 62 | // A list of all active heap regions, and their dimensions in memory. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 63 | HeapDefinition heap[MICROBIT_MAXIMUM_HEAPS] = { }; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 64 | uint8_t heap_count = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 65 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 66 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 67 | // Diplays a usage summary about a given heap... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 68 | void microbit_heap_print(HeapDefinition &heap) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 69 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 70 | uint32_t blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 71 | uint32_t *block; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 72 | int totalFreeBlock = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 73 | int totalUsedBlock = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 74 | int cols = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 75 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 76 | if (heap.heap_start == NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 77 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 78 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("--- HEAP NOT INITIALISED ---\n"); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 79 | return; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 80 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 81 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 82 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_start : %p\n", heap.heap_start); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 83 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_end : %p\n", heap.heap_end); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 84 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_size : %d\n", (int)heap.heap_end - (int)heap.heap_start); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 85 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 86 | // Disable IRQ temporarily to ensure no race conditions! |
| Jonathan Austin |
1:8aa5cdb4ab67 | 87 | __disable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 88 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 89 | block = heap.heap_start; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 90 | while (block < heap.heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 91 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 92 | blockSize = *block & ~MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 93 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("[%c:%d] ", *block & MICROBIT_HEAP_BLOCK_FREE ? 'F' : 'U', blockSize*4); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 94 | if (cols++ == 20) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 95 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 96 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\n"); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 97 | cols = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 98 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 99 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 100 | if (*block & MICROBIT_HEAP_BLOCK_FREE) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 101 | totalFreeBlock += blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 102 | else |
| Jonathan Austin |
1:8aa5cdb4ab67 | 103 | totalUsedBlock += blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 104 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 105 | block += blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 106 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 107 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 108 | // Enable Interrupts |
| Jonathan Austin |
1:8aa5cdb4ab67 | 109 | __enable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 110 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 111 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\n"); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 112 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 113 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("mb_total_free : %d\n", totalFreeBlock*4); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 114 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("mb_total_used : %d\n", totalUsedBlock*4); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 115 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 116 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 117 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 118 | // Diagnostics function. Displays a usage summary about all initialised heaps. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 119 | void microbit_heap_print() |
| Jonathan Austin |
1:8aa5cdb4ab67 | 120 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 121 | for (int i=0; i < heap_count; i++) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 122 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 123 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\nHEAP %d: \n", i); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 124 | microbit_heap_print(heap[i]); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 125 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 126 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 127 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 128 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 129 | void microbit_initialise_heap(HeapDefinition &heap) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 130 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 131 | // Simply mark the entire heap as free. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 132 | *heap.heap_start = ((uint32_t) heap.heap_end - (uint32_t) heap.heap_start) / MICROBIT_HEAP_BLOCK_SIZE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 133 | *heap.heap_start |= MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 134 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 135 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 136 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 137 | * Create and initialise a given memory region as for heap storage. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 138 | * After this is called, any future calls to malloc, new, free or delete may use the new heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 139 | * The heap allocator will attempt to allocate memory from heaps in the order that they are created. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 140 | * i.e. memory will be allocated from first heap created until it is full, then the second heap, and so on. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 141 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 142 | * @param start The start address of memory to use as a heap region. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 143 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 144 | * @param end The end address of memory to use as a heap region. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 145 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 146 | * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 147 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 148 | * @note Only code that #includes MicroBitHeapAllocator.h will use this heap. This includes all micro:bit runtime |
| Jonathan Austin |
1:8aa5cdb4ab67 | 149 | * code, and user code targetting the runtime. External code can choose to include this file, or |
| Jonathan Austin |
1:8aa5cdb4ab67 | 150 | * simply use the standard heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 151 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 152 | int microbit_create_heap(uint32_t start, uint32_t end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 153 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 154 | // Ensure we don't exceed the maximum number of heap segments. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 155 | if (heap_count == MICROBIT_MAXIMUM_HEAPS) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 156 | return MICROBIT_NO_RESOURCES; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 157 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 158 | // Sanity check. Ensure range is valid, large enough and word aligned. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 159 | if (end <= start || end - start < MICROBIT_HEAP_BLOCK_SIZE*2 || end % 4 != 0 || start % 4 != 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 160 | return MICROBIT_INVALID_PARAMETER; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 161 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 162 | // Disable IRQ temporarily to ensure no race conditions! |
| Jonathan Austin |
1:8aa5cdb4ab67 | 163 | __disable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 164 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 165 | // Record the dimensions of this new heap |
| Jonathan Austin |
1:8aa5cdb4ab67 | 166 | heap[heap_count].heap_start = (uint32_t *)start; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 167 | heap[heap_count].heap_end = (uint32_t *)end; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 168 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 169 | // Initialise the heap as being completely empty and available for use. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 170 | microbit_initialise_heap(heap[heap_count]); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 171 | heap_count++; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 172 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 173 | // Enable Interrupts |
| Jonathan Austin |
1:8aa5cdb4ab67 | 174 | __enable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 175 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 176 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 177 | microbit_heap_print(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 178 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 179 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 180 | return MICROBIT_OK; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 181 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 182 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 183 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 184 | * Create and initialise a heap region within the current the heap region specified |
| Jonathan Austin |
1:8aa5cdb4ab67 | 185 | * by the linker script. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 186 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 187 | * If the requested amount is not available, then the amount requested will be reduced |
| Jonathan Austin |
1:8aa5cdb4ab67 | 188 | * automatically to fit the space available. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 189 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 190 | * @param ratio The proportion of the underlying heap to allocate. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 191 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 192 | * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 193 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 194 | int microbit_create_nested_heap(float ratio) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 195 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 196 | uint32_t length; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 197 | void *p; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 198 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 199 | if (ratio <= 0.0 || ratio > 1.0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 200 | return MICROBIT_INVALID_PARAMETER; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 201 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 202 | // Snapshot something at the top of the main heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 203 | p = native_malloc(sizeof(uint32_t)); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 204 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 205 | // Estimate the size left in our heap, taking care to ensure it lands on a word boundary. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 206 | length = (uint32_t) (((float)(MICROBIT_HEAP_END - (uint32_t)p)) * ratio); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 207 | length &= 0xFFFFFFFC; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 208 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 209 | // Release our reference pointer. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 210 | native_free(p); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 211 | p = NULL; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 212 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 213 | // Allocate memory for our heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 214 | // We iteratively reduce the size of memory are allocate until it fits within available space. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 215 | while (p == NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 216 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 217 | p = native_malloc(length); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 218 | if (p == NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 219 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 220 | length -= 32; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 221 | if (length <= 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 222 | return MICROBIT_NO_RESOURCES; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 223 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 224 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 225 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 226 | uint32_t start = (uint32_t) p; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 227 | microbit_create_heap(start, start + length); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 228 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 229 | return MICROBIT_OK; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 230 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 231 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 232 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 233 | * Attempt to allocate a given amount of memory from any of our configured heap areas. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 234 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 235 | * @param size The amount of memory, in bytes, to allocate. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 236 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 237 | * @return A pointer to the allocated memory, or NULL if insufficient memory is available. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 238 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 239 | void *microbit_malloc(size_t size, HeapDefinition &heap) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 240 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 241 | uint32_t blockSize = 0; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 242 | uint32_t blocksNeeded = size % MICROBIT_HEAP_BLOCK_SIZE == 0 ? size / MICROBIT_HEAP_BLOCK_SIZE : size / MICROBIT_HEAP_BLOCK_SIZE + 1; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 243 | uint32_t *block; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 244 | uint32_t *next; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 245 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 246 | if (size <= 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 247 | return NULL; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 248 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 249 | // Account for the index block; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 250 | blocksNeeded++; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 251 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 252 | // Disable IRQ temporarily to ensure no race conditions! |
| Jonathan Austin |
1:8aa5cdb4ab67 | 253 | __disable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 254 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 255 | // We implement a first fit algorithm with cache to handle rapid churn... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 256 | // We also defragment free blocks as we search, to optimise this and future searches. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 257 | block = heap.heap_start; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 258 | while (block < heap.heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 259 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 260 | // If the block is used, then keep looking. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 261 | if(!(*block & MICROBIT_HEAP_BLOCK_FREE)) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 262 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 263 | block += *block; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 264 | continue; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 265 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 266 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 267 | blockSize = *block & ~MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 268 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 269 | // We have a free block. Let's see if the subsequent ones are too. If so, we can merge... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 270 | next = block + blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 271 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 272 | while (*next & MICROBIT_HEAP_BLOCK_FREE) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 273 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 274 | if (next >= heap.heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 275 | break; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 276 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 277 | // We can merge! |
| Jonathan Austin |
1:8aa5cdb4ab67 | 278 | blockSize += (*next & ~MICROBIT_HEAP_BLOCK_FREE); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 279 | *block = blockSize | MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 280 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 281 | next = block + blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 282 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 283 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 284 | // We have a free block. Let's see if it's big enough. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 285 | // If so, we have a winner. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 286 | if (blockSize >= blocksNeeded) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 287 | break; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 288 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 289 | // Otherwise, keep looking... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 290 | block += blockSize; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 291 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 292 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 293 | // We're full! |
| Jonathan Austin |
1:8aa5cdb4ab67 | 294 | if (block >= heap.heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 295 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 296 | __enable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 297 | return NULL; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 298 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 299 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 300 | // If we're at the end of memory or have very near match then mark the whole segment as in use. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 301 | if (blockSize <= blocksNeeded+1 || block+blocksNeeded+1 >= heap.heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 302 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 303 | // Just mark the whole block as used. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 304 | *block &= ~MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 305 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 306 | else |
| Jonathan Austin |
1:8aa5cdb4ab67 | 307 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 308 | // We need to split the block. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 309 | uint32_t *splitBlock = block + blocksNeeded; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 310 | *splitBlock = blockSize - blocksNeeded; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 311 | *splitBlock |= MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 312 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 313 | *block = blocksNeeded; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 314 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 315 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 316 | // Enable Interrupts |
| Jonathan Austin |
1:8aa5cdb4ab67 | 317 | __enable_irq(); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 318 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 319 | return block+1; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 320 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 321 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 322 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 323 | * Release a given area of memory from the heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 324 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 325 | * @param mem The memory area to release. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 326 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 327 | void *microbit_malloc(size_t size) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 328 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 329 | void *p; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 330 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 331 | // Assign the memory from the first heap created that has space. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 332 | for (int i=0; i < heap_count; i++) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 333 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 334 | p = microbit_malloc(size, heap[i]); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 335 | if (p != NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 336 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 337 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 338 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: ALLOCATED: %d [%p]\n", size, p); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 339 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 340 | return p; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 341 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 342 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 343 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 344 | // If we reach here, then either we have no memory available, or our heap spaces |
| Jonathan Austin |
1:8aa5cdb4ab67 | 345 | // haven't been initialised. Either way, we try the native allocator. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 346 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 347 | p = native_malloc(size); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 348 | if (p != NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 349 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 350 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 351 | // Keep everything trasparent if we've not been initialised yet |
| Jonathan Austin |
1:8aa5cdb4ab67 | 352 | if (heap_count > 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 353 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: NATIVE ALLOCATED: %d [%p]\n", size, p); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 354 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 355 | return p; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 356 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 357 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 358 | // We're totally out of options (and memory!). |
| Jonathan Austin |
1:8aa5cdb4ab67 | 359 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 360 | // Keep everything transparent if we've not been initialised yet |
| Jonathan Austin |
1:8aa5cdb4ab67 | 361 | if (heap_count > 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 362 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: OUT OF MEMORY [%d]\n", size); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 363 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 364 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 365 | #if CONFIG_ENABLED(MICROBIT_PANIC_HEAP_FULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 366 | microbit_panic(MICROBIT_OOM); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 367 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 368 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 369 | return NULL; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 370 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 371 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 372 | /** |
| Jonathan Austin |
1:8aa5cdb4ab67 | 373 | * Release a given area of memory from the heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 374 | * |
| Jonathan Austin |
1:8aa5cdb4ab67 | 375 | * @param mem The memory area to release. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 376 | */ |
| Jonathan Austin |
1:8aa5cdb4ab67 | 377 | void microbit_free(void *mem) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 378 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 379 | uint32_t *memory = (uint32_t *)mem; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 380 | uint32_t *cb = memory-1; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 381 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 382 | #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 383 | if (heap_count > 0) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 384 | if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_free: %p\n", mem); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 385 | #endif |
| Jonathan Austin |
1:8aa5cdb4ab67 | 386 | // Sanity check. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 387 | if (memory == NULL) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 388 | return; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 389 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 390 | // If this memory was created from a heap registered with us, free it. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 391 | for (int i=0; i < heap_count; i++) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 392 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 393 | if(memory > heap[i].heap_start && memory < heap[i].heap_end) |
| Jonathan Austin |
1:8aa5cdb4ab67 | 394 | { |
| Jonathan Austin |
1:8aa5cdb4ab67 | 395 | // The memory block given is part of this heap, so we can simply |
| Jonathan Austin |
1:8aa5cdb4ab67 | 396 | // flag that this memory area is now free, and we're done. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 397 | *cb |= MICROBIT_HEAP_BLOCK_FREE; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 398 | return; |
| Jonathan Austin |
1:8aa5cdb4ab67 | 399 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 400 | } |
| Jonathan Austin |
1:8aa5cdb4ab67 | 401 | |
| Jonathan Austin |
1:8aa5cdb4ab67 | 402 | // If we reach here, then the memory is not part of any registered heap. |
| Jonathan Austin |
1:8aa5cdb4ab67 | 403 | // Forward it to the native heap allocator, and let nature take its course... |
| Jonathan Austin |
1:8aa5cdb4ab67 | 404 | native_free(mem); |
| Jonathan Austin |
1:8aa5cdb4ab67 | 405 | } |