fsdfds
Dependencies: BLE_API mbed-dev-bin nRF51822
Fork of microbit-dal by
MicroBitHeapAllocator.cpp
00001 /* 00002 The MIT License (MIT) 00003 00004 Copyright (c) 2016 British Broadcasting Corporation. 00005 This software is provided by Lancaster University by arrangement with the BBC. 00006 00007 Permission is hereby granted, free of charge, to any person obtaining a 00008 copy of this software and associated documentation files (the "Software"), 00009 to deal in the Software without restriction, including without limitation 00010 the rights to use, copy, modify, merge, publish, distribute, sublicense, 00011 and/or sell copies of the Software, and to permit persons to whom the 00012 Software is furnished to do so, subject to the following conditions: 00013 00014 The above copyright notice and this permission notice shall be included in 00015 all copies or substantial portions of the Software. 00016 00017 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 00018 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 00019 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL 00020 THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 00021 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING 00022 FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER 00023 DEALINGS IN THE SOFTWARE. 00024 */ 00025 00026 /** 00027 * A simple 32 bit block based memory allocator. This allows one or more memory segments to 00028 * be designated as heap storage, and is designed to run in a static memory area or inside the standard C 00029 * heap for use by the micro:bit runtime. This is required for several reasons: 00030 * 00031 * 1) It reduces memory fragmentation due to the high churn sometime placed on the heap 00032 * by ManagedTypes, fibers and user code. Underlying heap implentations are often have very simplistic 00033 * allocation pilicies and suffer from fragmentation in prolonged use - which can cause programs to 00034 * stop working after a period of time. The algorithm implemented here is simple, but highly tolerant to 00035 * large amounts of churn. 00036 * 00037 * 2) It allows us to reuse the 8K of SRAM set aside for SoftDevice as additional heap storage 00038 * when BLE is not in use. 00039 * 00040 * 3) It gives a simple example of how memory allocation works! :-) 00041 * 00042 * P.S. This is a very simple allocator, therefore not without its weaknesses. Why don't you consider 00043 * what these are, and consider the tradeoffs against simplicity... 00044 * 00045 * @note The need for this should be reviewed in the future, if a different memory allocator is 00046 * made availiable in the mbed platform. 00047 * 00048 * TODO: Consider caching recently freed blocks to improve allocation time. 00049 */ 00050 00051 #include "MicroBitConfig.h" 00052 #include "MicroBitHeapAllocator.h" 00053 #include "MicroBitDevice.h" 00054 #include "ErrorNo.h" 00055 00056 struct HeapDefinition 00057 { 00058 uint32_t *heap_start; // Physical address of the start of this heap. 00059 uint32_t *heap_end; // Physical address of the end of this heap. 00060 }; 00061 00062 // A list of all active heap regions, and their dimensions in memory. 00063 HeapDefinition heap[MICROBIT_MAXIMUM_HEAPS] = { }; 00064 uint8_t heap_count = 0; 00065 00066 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00067 // Diplays a usage summary about a given heap... 00068 void microbit_heap_print(HeapDefinition &heap) 00069 { 00070 uint32_t blockSize; 00071 uint32_t *block; 00072 int totalFreeBlock = 0; 00073 int totalUsedBlock = 0; 00074 int cols = 0; 00075 00076 if (heap.heap_start == NULL) 00077 { 00078 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("--- HEAP NOT INITIALISED ---\n"); 00079 return; 00080 } 00081 00082 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_start : %p\n", heap.heap_start); 00083 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_end : %p\n", heap.heap_end); 00084 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("heap_size : %d\n", (int)heap.heap_end - (int)heap.heap_start); 00085 00086 // Disable IRQ temporarily to ensure no race conditions! 00087 __disable_irq(); 00088 00089 block = heap.heap_start; 00090 while (block < heap.heap_end) 00091 { 00092 blockSize = *block & ~MICROBIT_HEAP_BLOCK_FREE; 00093 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("[%c:%d] ", *block & MICROBIT_HEAP_BLOCK_FREE ? 'F' : 'U', blockSize*4); 00094 if (cols++ == 20) 00095 { 00096 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\n"); 00097 cols = 0; 00098 } 00099 00100 if (*block & MICROBIT_HEAP_BLOCK_FREE) 00101 totalFreeBlock += blockSize; 00102 else 00103 totalUsedBlock += blockSize; 00104 00105 block += blockSize; 00106 } 00107 00108 // Enable Interrupts 00109 __enable_irq(); 00110 00111 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\n"); 00112 00113 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("mb_total_free : %d\n", totalFreeBlock*4); 00114 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("mb_total_used : %d\n", totalUsedBlock*4); 00115 } 00116 00117 00118 // Diagnostics function. Displays a usage summary about all initialised heaps. 00119 void microbit_heap_print() 00120 { 00121 for (int i=0; i < heap_count; i++) 00122 { 00123 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("\nHEAP %d: \n", i); 00124 microbit_heap_print(heap[i]); 00125 } 00126 } 00127 #endif 00128 00129 void microbit_initialise_heap(HeapDefinition &heap) 00130 { 00131 // Simply mark the entire heap as free. 00132 *heap.heap_start = ((uint32_t) heap.heap_end - (uint32_t) heap.heap_start) / MICROBIT_HEAP_BLOCK_SIZE; 00133 *heap.heap_start |= MICROBIT_HEAP_BLOCK_FREE; 00134 } 00135 00136 /** 00137 * Create and initialise a given memory region as for heap storage. 00138 * After this is called, any future calls to malloc, new, free or delete may use the new heap. 00139 * The heap allocator will attempt to allocate memory from heaps in the order that they are created. 00140 * i.e. memory will be allocated from first heap created until it is full, then the second heap, and so on. 00141 * 00142 * @param start The start address of memory to use as a heap region. 00143 * 00144 * @param end The end address of memory to use as a heap region. 00145 * 00146 * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated. 00147 * 00148 * @note Only code that #includes MicroBitHeapAllocator.h will use this heap. This includes all micro:bit runtime 00149 * code, and user code targetting the runtime. External code can choose to include this file, or 00150 * simply use the standard heap. 00151 */ 00152 int microbit_create_heap(uint32_t start, uint32_t end) 00153 { 00154 // Ensure we don't exceed the maximum number of heap segments. 00155 if (heap_count == MICROBIT_MAXIMUM_HEAPS) 00156 return MICROBIT_NO_RESOURCES; 00157 00158 // Sanity check. Ensure range is valid, large enough and word aligned. 00159 if (end <= start || end - start < MICROBIT_HEAP_BLOCK_SIZE*2 || end % 4 != 0 || start % 4 != 0) 00160 return MICROBIT_INVALID_PARAMETER; 00161 00162 // Disable IRQ temporarily to ensure no race conditions! 00163 __disable_irq(); 00164 00165 // Record the dimensions of this new heap 00166 heap[heap_count].heap_start = (uint32_t *)start; 00167 heap[heap_count].heap_end = (uint32_t *)end; 00168 00169 // Initialise the heap as being completely empty and available for use. 00170 microbit_initialise_heap(heap[heap_count]); 00171 heap_count++; 00172 00173 // Enable Interrupts 00174 __enable_irq(); 00175 00176 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00177 microbit_heap_print(); 00178 #endif 00179 00180 return MICROBIT_OK; 00181 } 00182 00183 /** 00184 * Create and initialise a heap region within the current the heap region specified 00185 * by the linker script. 00186 * 00187 * If the requested amount is not available, then the amount requested will be reduced 00188 * automatically to fit the space available. 00189 * 00190 * @param ratio The proportion of the underlying heap to allocate. 00191 * 00192 * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated. 00193 */ 00194 int microbit_create_nested_heap(float ratio) 00195 { 00196 uint32_t length; 00197 void *p; 00198 00199 if (ratio <= 0.0 || ratio > 1.0) 00200 return MICROBIT_INVALID_PARAMETER; 00201 00202 // Snapshot something at the top of the main heap. 00203 p = native_malloc(sizeof(uint32_t)); 00204 00205 // Estimate the size left in our heap, taking care to ensure it lands on a word boundary. 00206 length = (uint32_t) (((float)(MICROBIT_HEAP_END - (uint32_t)p)) * ratio); 00207 length &= 0xFFFFFFFC; 00208 00209 // Release our reference pointer. 00210 native_free(p); 00211 p = NULL; 00212 00213 // Allocate memory for our heap. 00214 // We iteratively reduce the size of memory are allocate until it fits within available space. 00215 while (p == NULL) 00216 { 00217 p = native_malloc(length); 00218 if (p == NULL) 00219 { 00220 length -= 32; 00221 if (length <= 0) 00222 return MICROBIT_NO_RESOURCES; 00223 } 00224 } 00225 00226 uint32_t start = (uint32_t) p; 00227 microbit_create_heap(start, start + length); 00228 00229 return MICROBIT_OK; 00230 } 00231 00232 /** 00233 * Attempt to allocate a given amount of memory from any of our configured heap areas. 00234 * 00235 * @param size The amount of memory, in bytes, to allocate. 00236 * 00237 * @return A pointer to the allocated memory, or NULL if insufficient memory is available. 00238 */ 00239 void *microbit_malloc(size_t size, HeapDefinition &heap) 00240 { 00241 uint32_t blockSize = 0; 00242 uint32_t blocksNeeded = size % MICROBIT_HEAP_BLOCK_SIZE == 0 ? size / MICROBIT_HEAP_BLOCK_SIZE : size / MICROBIT_HEAP_BLOCK_SIZE + 1; 00243 uint32_t *block; 00244 uint32_t *next; 00245 00246 if (size <= 0) 00247 return NULL; 00248 00249 // Account for the index block; 00250 blocksNeeded++; 00251 00252 // Disable IRQ temporarily to ensure no race conditions! 00253 __disable_irq(); 00254 00255 // We implement a first fit algorithm with cache to handle rapid churn... 00256 // We also defragment free blocks as we search, to optimise this and future searches. 00257 block = heap.heap_start; 00258 while (block < heap.heap_end) 00259 { 00260 // If the block is used, then keep looking. 00261 if(!(*block & MICROBIT_HEAP_BLOCK_FREE)) 00262 { 00263 block += *block; 00264 continue; 00265 } 00266 00267 blockSize = *block & ~MICROBIT_HEAP_BLOCK_FREE; 00268 00269 // We have a free block. Let's see if the subsequent ones are too. If so, we can merge... 00270 next = block + blockSize; 00271 00272 while (*next & MICROBIT_HEAP_BLOCK_FREE) 00273 { 00274 if (next >= heap.heap_end) 00275 break; 00276 00277 // We can merge! 00278 blockSize += (*next & ~MICROBIT_HEAP_BLOCK_FREE); 00279 *block = blockSize | MICROBIT_HEAP_BLOCK_FREE; 00280 00281 next = block + blockSize; 00282 } 00283 00284 // We have a free block. Let's see if it's big enough. 00285 // If so, we have a winner. 00286 if (blockSize >= blocksNeeded) 00287 break; 00288 00289 // Otherwise, keep looking... 00290 block += blockSize; 00291 } 00292 00293 // We're full! 00294 if (block >= heap.heap_end) 00295 { 00296 __enable_irq(); 00297 return NULL; 00298 } 00299 00300 // If we're at the end of memory or have very near match then mark the whole segment as in use. 00301 if (blockSize <= blocksNeeded+1 || block+blocksNeeded+1 >= heap.heap_end) 00302 { 00303 // Just mark the whole block as used. 00304 *block &= ~MICROBIT_HEAP_BLOCK_FREE; 00305 } 00306 else 00307 { 00308 // We need to split the block. 00309 uint32_t *splitBlock = block + blocksNeeded; 00310 *splitBlock = blockSize - blocksNeeded; 00311 *splitBlock |= MICROBIT_HEAP_BLOCK_FREE; 00312 00313 *block = blocksNeeded; 00314 } 00315 00316 // Enable Interrupts 00317 __enable_irq(); 00318 00319 return block+1; 00320 } 00321 00322 /** 00323 * Release a given area of memory from the heap. 00324 * 00325 * @param mem The memory area to release. 00326 */ 00327 void *microbit_malloc(size_t size) 00328 { 00329 void *p; 00330 00331 // Assign the memory from the first heap created that has space. 00332 for (int i=0; i < heap_count; i++) 00333 { 00334 p = microbit_malloc(size, heap[i]); 00335 if (p != NULL) 00336 { 00337 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00338 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: ALLOCATED: %d [%p]\n", size, p); 00339 #endif 00340 return p; 00341 } 00342 } 00343 00344 // If we reach here, then either we have no memory available, or our heap spaces 00345 // haven't been initialised. Either way, we try the native allocator. 00346 00347 p = native_malloc(size); 00348 if (p != NULL) 00349 { 00350 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00351 // Keep everything trasparent if we've not been initialised yet 00352 if (heap_count > 0) 00353 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: NATIVE ALLOCATED: %d [%p]\n", size, p); 00354 #endif 00355 return p; 00356 } 00357 00358 // We're totally out of options (and memory!). 00359 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00360 // Keep everything transparent if we've not been initialised yet 00361 if (heap_count > 0) 00362 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_malloc: OUT OF MEMORY [%d]\n", size); 00363 #endif 00364 00365 #if CONFIG_ENABLED(MICROBIT_PANIC_HEAP_FULL) 00366 microbit_panic(MICROBIT_OOM); 00367 #endif 00368 00369 return NULL; 00370 } 00371 00372 /** 00373 * Release a given area of memory from the heap. 00374 * 00375 * @param mem The memory area to release. 00376 */ 00377 void microbit_free(void *mem) 00378 { 00379 uint32_t *memory = (uint32_t *)mem; 00380 uint32_t *cb = memory-1; 00381 00382 #if CONFIG_ENABLED(MICROBIT_DBG) && CONFIG_ENABLED(MICROBIT_HEAP_DBG) 00383 if (heap_count > 0) 00384 if(SERIAL_DEBUG) SERIAL_DEBUG->printf("microbit_free: %p\n", mem); 00385 #endif 00386 // Sanity check. 00387 if (memory == NULL) 00388 return; 00389 00390 // If this memory was created from a heap registered with us, free it. 00391 for (int i=0; i < heap_count; i++) 00392 { 00393 if(memory > heap[i].heap_start && memory < heap[i].heap_end) 00394 { 00395 // The memory block given is part of this heap, so we can simply 00396 // flag that this memory area is now free, and we're done. 00397 *cb |= MICROBIT_HEAP_BLOCK_FREE; 00398 return; 00399 } 00400 } 00401 00402 // If we reach here, then the memory is not part of any registered heap. 00403 // Forward it to the native heap allocator, and let nature take its course... 00404 native_free(mem); 00405 }
Generated on Wed Jul 13 2022 00:58:03 by 1.7.2