Philip Holifield / microbit-dal

from bbc microbit library

Dependencies:   BLE_API mbed-dev-bin nRF51822

Dependents:   microbit

Fork of microbit-dal by Lancaster University

inc/core/MicroBitHeapAllocator.h@1:8aa5cdb4ab67, 2016-04-07 (annotated)

Committer:
Jonathan Austin
Date:
Thu Apr 07 01:33:22 2016 +0100
Revision:
1:8aa5cdb4ab67
Synchronized with git rev 55cb9199

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 #ifndef MICROBIT_HEAP_ALLOCTOR_H
Jonathan Austin 1:8aa5cdb4ab67 52 #define MICROBIT_HEAP_ALLOCTOR_H
Jonathan Austin 1:8aa5cdb4ab67 53
Jonathan Austin 1:8aa5cdb4ab67 54 #include "mbed.h"
Jonathan Austin 1:8aa5cdb4ab67 55 #include "MicroBitConfig.h"
Jonathan Austin 1:8aa5cdb4ab67 56 #include <new>
Jonathan Austin 1:8aa5cdb4ab67 57
Jonathan Austin 1:8aa5cdb4ab67 58 // The maximum number of heap segments that can be created.
Jonathan Austin 1:8aa5cdb4ab67 59 #define MICROBIT_MAXIMUM_HEAPS 2
Jonathan Austin 1:8aa5cdb4ab67 60
Jonathan Austin 1:8aa5cdb4ab67 61 // Flag to indicate that a given block is FREE/USED
Jonathan Austin 1:8aa5cdb4ab67 62 #define MICROBIT_HEAP_BLOCK_FREE 0x80000000
Jonathan Austin 1:8aa5cdb4ab67 63
Jonathan Austin 1:8aa5cdb4ab67 64 /**
Jonathan Austin 1:8aa5cdb4ab67 65 * Create and initialise a given memory region as for heap storage.
Jonathan Austin 1:8aa5cdb4ab67 66 * After this is called, any future calls to malloc, new, free or delete may use the new heap.
Jonathan Austin 1:8aa5cdb4ab67 67 * The heap allocator will attempt to allocate memory from heaps in the order that they are created.
Jonathan Austin 1:8aa5cdb4ab67 68 * 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 69 *
Jonathan Austin 1:8aa5cdb4ab67 70 * @param start The start address of memory to use as a heap region.
Jonathan Austin 1:8aa5cdb4ab67 71 *
Jonathan Austin 1:8aa5cdb4ab67 72 * @param end The end address of memory to use as a heap region.
Jonathan Austin 1:8aa5cdb4ab67 73 *
Jonathan Austin 1:8aa5cdb4ab67 74 * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated.
Jonathan Austin 1:8aa5cdb4ab67 75 *
Jonathan Austin 1:8aa5cdb4ab67 76 * @note Only code that #includes MicroBitHeapAllocator.h will use this heap. This includes all micro:bit runtime
Jonathan Austin 1:8aa5cdb4ab67 77 * code, and user code targetting the runtime. External code can choose to include this file, or
Jonathan Austin 1:8aa5cdb4ab67 78 * simply use the standard heap.
Jonathan Austin 1:8aa5cdb4ab67 79 */
Jonathan Austin 1:8aa5cdb4ab67 80 int microbit_create_heap(uint32_t start, uint32_t end);
Jonathan Austin 1:8aa5cdb4ab67 81
Jonathan Austin 1:8aa5cdb4ab67 82 /**
Jonathan Austin 1:8aa5cdb4ab67 83 * Create and initialise a heap region within the current the heap region specified
Jonathan Austin 1:8aa5cdb4ab67 84 * by the linker script.
Jonathan Austin 1:8aa5cdb4ab67 85 *
Jonathan Austin 1:8aa5cdb4ab67 86 * If the requested amount is not available, then the amount requested will be reduced
Jonathan Austin 1:8aa5cdb4ab67 87 * automatically to fit the space available.
Jonathan Austin 1:8aa5cdb4ab67 88 *
Jonathan Austin 1:8aa5cdb4ab67 89 * @param ratio The proportion of the underlying heap to allocate.
Jonathan Austin 1:8aa5cdb4ab67 90 *
Jonathan Austin 1:8aa5cdb4ab67 91 * @return MICROBIT_OK on success, or MICROBIT_NO_RESOURCES if the heap could not be allocated.
Jonathan Austin 1:8aa5cdb4ab67 92 */
Jonathan Austin 1:8aa5cdb4ab67 93 int microbit_create_nested_heap(float ratio);
Jonathan Austin 1:8aa5cdb4ab67 94
Jonathan Austin 1:8aa5cdb4ab67 95 /**
Jonathan Austin 1:8aa5cdb4ab67 96 * Attempt to allocate a given amount of memory from any of our configured heap areas.
Jonathan Austin 1:8aa5cdb4ab67 97 *
Jonathan Austin 1:8aa5cdb4ab67 98 * @param size The amount of memory, in bytes, to allocate.
Jonathan Austin 1:8aa5cdb4ab67 99 *
Jonathan Austin 1:8aa5cdb4ab67 100 * @return A pointer to the allocated memory, or NULL if insufficient memory is available.
Jonathan Austin 1:8aa5cdb4ab67 101 */
Jonathan Austin 1:8aa5cdb4ab67 102 void *microbit_malloc(size_t size);
Jonathan Austin 1:8aa5cdb4ab67 103
Jonathan Austin 1:8aa5cdb4ab67 104
Jonathan Austin 1:8aa5cdb4ab67 105 /**
Jonathan Austin 1:8aa5cdb4ab67 106 * Release a given area of memory from the heap.
Jonathan Austin 1:8aa5cdb4ab67 107 *
Jonathan Austin 1:8aa5cdb4ab67 108 * @param mem The memory area to release.
Jonathan Austin 1:8aa5cdb4ab67 109 */
Jonathan Austin 1:8aa5cdb4ab67 110 void microbit_free(void *mem);
Jonathan Austin 1:8aa5cdb4ab67 111
Jonathan Austin 1:8aa5cdb4ab67 112 /*
Jonathan Austin 1:8aa5cdb4ab67 113 * Wrapper function to ensure we have an explicit handle on the heap allocator provided
Jonathan Austin 1:8aa5cdb4ab67 114 * by our underlying platform.
Jonathan Austin 1:8aa5cdb4ab67 115 *
Jonathan Austin 1:8aa5cdb4ab67 116 * @param size The amount of memory, in bytes, to allocate.
Jonathan Austin 1:8aa5cdb4ab67 117 *
Jonathan Austin 1:8aa5cdb4ab67 118 * @return A pointer to the memory allocated. NULL if no memory is available.
Jonathan Austin 1:8aa5cdb4ab67 119 */
Jonathan Austin 1:8aa5cdb4ab67 120 inline void *native_malloc(size_t size)
Jonathan Austin 1:8aa5cdb4ab67 121 {
Jonathan Austin 1:8aa5cdb4ab67 122 return malloc(size);
Jonathan Austin 1:8aa5cdb4ab67 123 }
Jonathan Austin 1:8aa5cdb4ab67 124
Jonathan Austin 1:8aa5cdb4ab67 125 /*
Jonathan Austin 1:8aa5cdb4ab67 126 * Wrapper function to ensure we have an explicit handle on the heap allocator provided
Jonathan Austin 1:8aa5cdb4ab67 127 * by our underlying platform.
Jonathan Austin 1:8aa5cdb4ab67 128 *
Jonathan Austin 1:8aa5cdb4ab67 129 * @param p Pointer to the memory to be freed.
Jonathan Austin 1:8aa5cdb4ab67 130 */
Jonathan Austin 1:8aa5cdb4ab67 131 inline void native_free(void *p)
Jonathan Austin 1:8aa5cdb4ab67 132 {
Jonathan Austin 1:8aa5cdb4ab67 133 free(p);
Jonathan Austin 1:8aa5cdb4ab67 134 }
Jonathan Austin 1:8aa5cdb4ab67 135
Jonathan Austin 1:8aa5cdb4ab67 136 /**
Jonathan Austin 1:8aa5cdb4ab67 137 * Overrides the 'new' operator globally, and redirects calls to the micro:bit heap allocator.
Jonathan Austin 1:8aa5cdb4ab67 138 */
Jonathan Austin 1:8aa5cdb4ab67 139 inline void* operator new(size_t size) throw(std::bad_alloc)
Jonathan Austin 1:8aa5cdb4ab67 140 {
Jonathan Austin 1:8aa5cdb4ab67 141 return microbit_malloc(size);
Jonathan Austin 1:8aa5cdb4ab67 142 }
Jonathan Austin 1:8aa5cdb4ab67 143
Jonathan Austin 1:8aa5cdb4ab67 144 /**
Jonathan Austin 1:8aa5cdb4ab67 145 * Overrides the 'new' operator globally, and redirects calls to the micro:bit theap allocator.
Jonathan Austin 1:8aa5cdb4ab67 146 */
Jonathan Austin 1:8aa5cdb4ab67 147 inline void* operator new[](size_t size) throw(std::bad_alloc)
Jonathan Austin 1:8aa5cdb4ab67 148 {
Jonathan Austin 1:8aa5cdb4ab67 149 return microbit_malloc(size);
Jonathan Austin 1:8aa5cdb4ab67 150 }
Jonathan Austin 1:8aa5cdb4ab67 151
Jonathan Austin 1:8aa5cdb4ab67 152 /**
Jonathan Austin 1:8aa5cdb4ab67 153 * Overrides the 'delete' operator globally, and redirects calls to the micro:bit theap allocator.
Jonathan Austin 1:8aa5cdb4ab67 154 */
Jonathan Austin 1:8aa5cdb4ab67 155 inline void operator delete(void *ptr) throw()
Jonathan Austin 1:8aa5cdb4ab67 156 {
Jonathan Austin 1:8aa5cdb4ab67 157 microbit_free(ptr);
Jonathan Austin 1:8aa5cdb4ab67 158 }
Jonathan Austin 1:8aa5cdb4ab67 159
Jonathan Austin 1:8aa5cdb4ab67 160
Jonathan Austin 1:8aa5cdb4ab67 161 // Macros to override overrides the 'malloc' and 'delete' functions globally, and redirects calls
Jonathan Austin 1:8aa5cdb4ab67 162 // to the micro:bit theap allocator.
Jonathan Austin 1:8aa5cdb4ab67 163
Jonathan Austin 1:8aa5cdb4ab67 164 #define malloc(X) microbit_malloc( X )
Jonathan Austin 1:8aa5cdb4ab67 165 #define free(X) microbit_free( X )
Jonathan Austin 1:8aa5cdb4ab67 166
Jonathan Austin 1:8aa5cdb4ab67 167 #endif