[c6bc9d8] | 1 | /* |
---|
| 2 | * Heap Handler |
---|
| 3 | * |
---|
| 4 | * COPYRIGHT (c) 1989-1999. |
---|
| 5 | * On-Line Applications Research Corporation (OAR). |
---|
| 6 | * |
---|
| 7 | * The license and distribution terms for this file may be |
---|
| 8 | * found in the file LICENSE in this distribution or at |
---|
[1fb90ec7] | 9 | * http://www.rtems.com/license/LICENSE. |
---|
[c6bc9d8] | 10 | * |
---|
| 11 | * $Id$ |
---|
| 12 | */ |
---|
| 13 | |
---|
[a8eed23] | 14 | #if HAVE_CONFIG_H |
---|
| 15 | #include "config.h" |
---|
| 16 | #endif |
---|
[c6bc9d8] | 17 | |
---|
| 18 | #include <rtems/system.h> |
---|
| 19 | #include <rtems/score/sysstate.h> |
---|
| 20 | #include <rtems/score/heap.h> |
---|
| 21 | |
---|
| 22 | #if defined(RTEMS_HEAP_DEBUG) |
---|
| 23 | |
---|
| 24 | static void |
---|
| 25 | check_result( |
---|
| 26 | Heap_Control* the_heap, |
---|
| 27 | Heap_Block* the_block, |
---|
| 28 | _H_uptr_t user_addr, |
---|
| 29 | _H_uptr_t aligned_user_addr, |
---|
| 30 | uint32_t size) |
---|
| 31 | { |
---|
| 32 | _H_uptr_t const user_area = _H_p2u(_Heap_User_area(the_block)); |
---|
| 33 | _H_uptr_t const block_end = _H_p2u(the_block) |
---|
| 34 | + _Heap_Block_size(the_block) + HEAP_BLOCK_HEADER_OFFSET; |
---|
| 35 | _H_uptr_t const user_end = aligned_user_addr + size; |
---|
| 36 | _H_uptr_t const heap_start = _H_p2u(the_heap->start) + HEAP_OVERHEAD; |
---|
| 37 | _H_uptr_t const heap_end = _H_p2u(the_heap->final) |
---|
| 38 | + HEAP_BLOCK_HEADER_OFFSET; |
---|
| 39 | uint32_t const page_size = the_heap->page_size; |
---|
| 40 | |
---|
| 41 | _HAssert(user_addr == user_area); |
---|
| 42 | _HAssert(aligned_user_addr - user_area < page_size); |
---|
| 43 | _HAssert(aligned_user_addr >= user_area); |
---|
| 44 | _HAssert(aligned_user_addr < block_end); |
---|
| 45 | _HAssert(user_end > user_area); |
---|
| 46 | _HAssert(user_end <= block_end); |
---|
| 47 | _HAssert(aligned_user_addr >= heap_start); |
---|
| 48 | _HAssert(aligned_user_addr < heap_end); |
---|
| 49 | _HAssert(user_end > heap_start); |
---|
| 50 | _HAssert(user_end <= heap_end); |
---|
| 51 | } |
---|
| 52 | |
---|
| 53 | #else /* !defined(RTEMS_HEAP_DEBUG) */ |
---|
| 54 | |
---|
| 55 | #define check_result(a, b, c, d, e) ((void)0) |
---|
| 56 | |
---|
| 57 | #endif /* !defined(RTEMS_HEAP_DEBUG) */ |
---|
| 58 | |
---|
[493e405] | 59 | /* |
---|
| 60 | * Allocate block of size 'alloc_size' from 'the_block' belonging to |
---|
| 61 | * 'the_heap'. Split 'the_block' if possible, otherwise allocate it entirely. |
---|
| 62 | * When split, make the upper part used, and leave the lower part free. |
---|
| 63 | * Return the block allocated. |
---|
| 64 | * |
---|
| 65 | * NOTE: this is similar to _Heap_Block_allocate(), except it makes different |
---|
| 66 | * part of the split block used, and returns address of the block instead of its |
---|
| 67 | * size. We do need such variant for _Heap_Allocate_aligned() as we can't allow |
---|
| 68 | * user pointer to be too far from the beginning of the block, so that we can |
---|
| 69 | * recover start-of-block address from the user pointer without additional |
---|
| 70 | * information stored in the heap. |
---|
| 71 | */ |
---|
| 72 | static |
---|
| 73 | Heap_Block *block_allocate( |
---|
| 74 | Heap_Control *the_heap, |
---|
| 75 | Heap_Block *the_block, |
---|
| 76 | uint32_t alloc_size) |
---|
| 77 | { |
---|
| 78 | Heap_Statistics *const stats = &the_heap->stats; |
---|
| 79 | uint32_t const block_size = _Heap_Block_size(the_block); |
---|
| 80 | uint32_t const the_rest = block_size - alloc_size; |
---|
| 81 | |
---|
| 82 | _HAssert(_Heap_Is_aligned(block_size, the_heap->page_size)); |
---|
| 83 | _HAssert(_Heap_Is_aligned(alloc_size, the_heap->page_size)); |
---|
| 84 | _HAssert(alloc_size <= block_size); |
---|
| 85 | _HAssert(_Heap_Is_prev_used(the_block)); |
---|
| 86 | |
---|
| 87 | if(the_rest >= the_heap->min_block_size) { |
---|
| 88 | /* Split the block so that lower part is still free, and upper part |
---|
| 89 | becomes used. */ |
---|
| 90 | the_block->size = the_rest | HEAP_PREV_USED; |
---|
| 91 | the_block = _Heap_Block_at(the_block, the_rest); |
---|
| 92 | the_block->prev_size = the_rest; |
---|
| 93 | the_block->size = alloc_size; |
---|
| 94 | } |
---|
| 95 | else { |
---|
| 96 | /* Don't split the block as remainder is either zero or too small to be |
---|
| 97 | used as a separate free block. Change 'alloc_size' to the size of the |
---|
| 98 | block and remove the block from the list of free blocks. */ |
---|
| 99 | _Heap_Block_remove(the_block); |
---|
| 100 | alloc_size = block_size; |
---|
| 101 | stats->free_blocks -= 1; |
---|
| 102 | } |
---|
| 103 | /* Mark the block as used (in the next block). */ |
---|
| 104 | _Heap_Block_at(the_block, alloc_size)->size |= HEAP_PREV_USED; |
---|
| 105 | /* Update statistics */ |
---|
| 106 | stats->free_size -= alloc_size; |
---|
| 107 | if(stats->min_free_size > stats->free_size) |
---|
| 108 | stats->min_free_size = stats->free_size; |
---|
| 109 | stats->used_blocks += 1; |
---|
| 110 | return the_block; |
---|
| 111 | } |
---|
| 112 | |
---|
| 113 | |
---|
[c6bc9d8] | 114 | /*PAGE |
---|
| 115 | * |
---|
| 116 | * _Heap_Allocate_aligned |
---|
| 117 | * |
---|
| 118 | * This kernel routine allocates the requested size of memory |
---|
| 119 | * from the specified heap so that returned address is aligned according to |
---|
| 120 | * the 'alignment'. |
---|
| 121 | * |
---|
| 122 | * Input parameters: |
---|
| 123 | * the_heap - pointer to the heap control block. |
---|
| 124 | * size - size in bytes of the memory block to allocate. |
---|
| 125 | * alignment - required user pointer alignment in bytes |
---|
| 126 | * |
---|
| 127 | * Output parameters: |
---|
| 128 | * returns - starting address of memory block allocated. The address is |
---|
| 129 | * aligned on specified boundary. |
---|
| 130 | */ |
---|
| 131 | |
---|
| 132 | void *_Heap_Allocate_aligned( |
---|
| 133 | Heap_Control *the_heap, |
---|
[59c44c6] | 134 | size_t size, |
---|
| 135 | uint32_t alignment |
---|
[c6bc9d8] | 136 | ) |
---|
| 137 | { |
---|
| 138 | uint32_t search_count; |
---|
| 139 | Heap_Block *the_block; |
---|
| 140 | |
---|
| 141 | void *user_ptr = NULL; |
---|
| 142 | uint32_t const page_size = the_heap->page_size; |
---|
| 143 | Heap_Statistics *const stats = &the_heap->stats; |
---|
| 144 | Heap_Block *const tail = _Heap_Tail(the_heap); |
---|
| 145 | |
---|
| 146 | uint32_t const end_to_user_offs = size - HEAP_BLOCK_HEADER_OFFSET; |
---|
| 147 | |
---|
| 148 | uint32_t const the_size = |
---|
| 149 | _Heap_Calc_block_size(size, page_size, the_heap->min_block_size); |
---|
| 150 | |
---|
| 151 | if(the_size == 0) |
---|
| 152 | return NULL; |
---|
| 153 | |
---|
| 154 | if(alignment == 0) |
---|
| 155 | alignment = CPU_ALIGNMENT; |
---|
| 156 | |
---|
| 157 | /* Find large enough free block that satisfies the alignment requirements. */ |
---|
| 158 | |
---|
[493e405] | 159 | for(the_block = _Heap_First(the_heap), search_count = 0; |
---|
[c6bc9d8] | 160 | the_block != tail; |
---|
| 161 | the_block = the_block->next, ++search_count) |
---|
| 162 | { |
---|
| 163 | uint32_t const block_size = _Heap_Block_size(the_block); |
---|
| 164 | |
---|
| 165 | /* As we always coalesce free blocks, prev block must have been used. */ |
---|
| 166 | _HAssert(_Heap_Is_prev_used(the_block)); |
---|
| 167 | |
---|
| 168 | if(block_size >= the_size) { /* the_block is large enough. */ |
---|
| 169 | |
---|
| 170 | _H_uptr_t user_addr; |
---|
| 171 | _H_uptr_t aligned_user_addr; |
---|
| 172 | _H_uptr_t const user_area = _H_p2u(_Heap_User_area(the_block)); |
---|
| 173 | |
---|
| 174 | /* Calculate 'aligned_user_addr' that will become the user pointer we |
---|
| 175 | return. It should be at least 'end_to_user_offs' bytes less than the |
---|
| 176 | the 'block_end' and should be aligned on 'alignment' boundary. |
---|
| 177 | Calculations are from the 'block_end' as we are going to split free |
---|
| 178 | block so that the upper part of the block becomes used block. */ |
---|
| 179 | _H_uptr_t const block_end = _H_p2u(the_block) + block_size; |
---|
| 180 | aligned_user_addr = block_end - end_to_user_offs; |
---|
| 181 | _Heap_Align_down_uptr(&aligned_user_addr, alignment); |
---|
| 182 | |
---|
| 183 | /* 'user_addr' is the 'aligned_user_addr' further aligned down to the |
---|
| 184 | 'page_size' boundary. We need it as blocks' user areas should begin |
---|
| 185 | only at 'page_size' aligned addresses */ |
---|
| 186 | user_addr = aligned_user_addr; |
---|
| 187 | _Heap_Align_down_uptr(&user_addr, page_size); |
---|
| 188 | |
---|
[493e405] | 189 | /* Make sure 'user_addr' calculated didn't run out of 'the_block'. */ |
---|
[c6bc9d8] | 190 | if(user_addr >= user_area) { |
---|
| 191 | |
---|
| 192 | /* The block seems to be acceptable. Check if the remainder of |
---|
| 193 | 'the_block' is less than 'min_block_size' so that 'the_block' won't |
---|
| 194 | actually be split at the address we assume. */ |
---|
| 195 | if(user_addr - user_area < the_heap->min_block_size) { |
---|
| 196 | |
---|
| 197 | /* The block won't be split, so 'user_addr' will be equal to the |
---|
| 198 | 'user_area'. */ |
---|
| 199 | user_addr = user_area; |
---|
| 200 | |
---|
| 201 | /* We can't allow the distance between 'user_addr' and |
---|
| 202 | 'aligned_user_addr' to be outside of [0,page_size) range. If we do, |
---|
| 203 | we will need to store this distance somewhere to be able to |
---|
| 204 | resurrect the block address from the user pointer. (Having the |
---|
| 205 | distance within [0,page_size) range allows resurrection by |
---|
| 206 | aligning user pointer down to the nearest 'page_size' boundary.) */ |
---|
| 207 | if(aligned_user_addr - user_addr >= page_size) { |
---|
| 208 | |
---|
| 209 | /* The user pointer will be too far from 'user_addr'. See if we |
---|
| 210 | can make 'aligned_user_addr' to be close enough to the |
---|
| 211 | 'user_addr'. */ |
---|
| 212 | aligned_user_addr = user_addr; |
---|
| 213 | _Heap_Align_up_uptr(&aligned_user_addr, alignment); |
---|
| 214 | if(aligned_user_addr - user_addr >= page_size) { |
---|
| 215 | /* No, we can't use the block */ |
---|
| 216 | aligned_user_addr = 0; |
---|
| 217 | } |
---|
| 218 | } |
---|
| 219 | } |
---|
| 220 | |
---|
| 221 | if(aligned_user_addr) { |
---|
| 222 | |
---|
| 223 | /* The block is indeed acceptable: calculate the size of the block |
---|
| 224 | to be allocated and perform allocation. */ |
---|
| 225 | uint32_t const alloc_size = |
---|
| 226 | block_end - user_addr + HEAP_BLOCK_USER_OFFSET; |
---|
| 227 | |
---|
| 228 | _HAssert(_Heap_Is_aligned_ptr((void*)aligned_user_addr, alignment)); |
---|
| 229 | |
---|
[493e405] | 230 | the_block = block_allocate(the_heap, the_block, alloc_size); |
---|
[c6bc9d8] | 231 | |
---|
| 232 | stats->searches += search_count + 1; |
---|
| 233 | stats->allocs += 1; |
---|
| 234 | |
---|
| 235 | check_result(the_heap, the_block, user_addr, |
---|
| 236 | aligned_user_addr, size); |
---|
| 237 | |
---|
| 238 | user_ptr = (void*)aligned_user_addr; |
---|
| 239 | break; |
---|
| 240 | } |
---|
| 241 | } |
---|
| 242 | } |
---|
| 243 | } |
---|
| 244 | |
---|
| 245 | if(stats->max_search < search_count) |
---|
| 246 | stats->max_search = search_count; |
---|
| 247 | |
---|
| 248 | return user_ptr; |
---|
| 249 | } |
---|