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 }