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