Wendy Warne / microbit-dal

updates

Dependencies:   BLE_API mbed-dev-bin nRF51822

Fork of microbit-dal-eddystone by Martin Woolley

source/core/MicroBitHeapAllocator.cpp@61:b597fb218f84, 2016-07-13 (annotated)

Committer:
LancasterUniversity
Date:
Wed Jul 13 12:18:40 2016 +0100
Revision:
61:b597fb218f84
Parent:
1:8aa5cdb4ab67 
Synchronized with git rev 64042e4a

Author: James Devine

microbit-dal: BUGFIX cast in MicroBitSerial from int to char



There was an unnecessary cast in MicroBitSerial.read that meant error

codes would never be returned to the user application, this has now

been removed.

Who changed what in which revision?

UserRevisionLine numberNew 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 }