source: rtems/cpukit/score/include/rtems/score/heap.h @ 4508a5a

4.115
Last change on this file since 4508a5a was 4508a5a, checked in by Sebastian Huber <sebastian.huber@…>, on Jul 24, 2013 at 1:24:51 PM

score: Move _Heap_Area_overhead() definition.

This function is used in bootcard.h.

  • Property mode set to 100644
File size: 12.6 KB
Line 
1/**
2 * @file
3 *
4 * @ingroup ScoreHeap
5 *
6 * @brief Heap Handler API
7 */
8
9/*
10 *  COPYRIGHT (c) 1989-2006.
11 *  On-Line Applications Research Corporation (OAR).
12 *
13 *  The license and distribution terms for this file may be
14 *  found in the file LICENSE in this distribution or at
15 *  http://www.rtems.com/license/LICENSE.
16 */
17
18#ifndef _RTEMS_SCORE_HEAP_H
19#define _RTEMS_SCORE_HEAP_H
20
21#include <rtems/score/cpu.h>
22
23#ifdef __cplusplus
24extern "C" {
25#endif
26
27#ifdef RTEMS_DEBUG
28  #define HEAP_PROTECTION
29#endif
30
31/**
32 * @defgroup ScoreHeap Heap Handler
33 *
34 * @ingroup Score
35 *
36 * @brief The Heap Handler provides a heap.
37 *
38 * A heap is a doubly linked list of variable size blocks which are allocated
39 * using the first fit method.  Garbage collection is performed each time a
40 * block is returned to the heap by coalescing neighbor blocks.  Control
41 * information for both allocated and free blocks is contained in the heap
42 * area.  A heap control structure contains control information for the heap.
43 *
44 * The alignment routines could be made faster should we require only powers of
45 * two to be supported for page size, alignment and boundary arguments.  The
46 * minimum alignment requirement for pages is currently CPU_ALIGNMENT and this
47 * value is only required to be multiple of two and explicitly not required to
48 * be a power of two.
49 *
50 * There are two kinds of blocks.  One sort describes a free block from which
51 * we can allocate memory.  The other blocks are used and provide an allocated
52 * memory area.  The free blocks are accessible via a list of free blocks.
53 *
54 * Blocks or areas cover a continuous set of memory addresses. They have a
55 * begin and end address.  The end address is not part of the set.  The size of
56 * a block or area equals the distance between the begin and end address in
57 * units of bytes.
58 *
59 * Free blocks look like:
60 * <table>
61 *   <tr>
62 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
63 *       previous block is free, <br> otherwise it may contain data used by
64 *       the previous block</td>
65 *   </tr>
66 *   <tr>
67 *     <td>block size and a flag which indicates if the previous block is free
68 *       or used, <br> this field contains always valid data regardless of the
69 *       block usage</td>
70 *   </tr>
71 *   <tr><td>pointer to next block (this field is page size aligned)</td></tr>
72 *   <tr><td>pointer to previous block</td></tr>
73 *   <tr><td colspan=2>free space</td></tr>
74 * </table>
75 *
76 * Used blocks look like:
77 * <table>
78 *   <tr>
79 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
80 *       previous block is free,<br>otherwise it may contain data used by
81 *       the previous block</td>
82 *   </tr>
83 *   <tr>
84 *     <td>block size and a flag which indicates if the previous block is free
85 *       or used, <br> this field contains always valid data regardless of the
86 *       block usage</td>
87 *   </tr>
88 *   <tr><td>begin of allocated area (this field is page size aligned)</td></tr>
89 *   <tr><td>allocated space</td></tr>
90 *   <tr><td colspan=2>allocated space</td></tr>
91 * </table>
92 *
93 * The heap area after initialization contains two blocks and looks like:
94 * <table>
95 *   <tr><th>Label</th><th colspan=2>Content</th></tr>
96 *   <tr><td>heap->area_begin</td><td colspan=2>heap area begin address</td></tr>
97 *   <tr>
98 *     <td>first_block->prev_size</td>
99 *     <td colspan=2>
100 *       subordinate heap area end address (this will be used to maintain a
101 *       linked list of scattered heap areas)
102 *     </td>
103 *   </tr>
104 *   <tr>
105 *     <td>first_block->size</td>
106 *     <td colspan=2>size available for allocation
107 *       | @c HEAP_PREV_BLOCK_USED</td>
108 *   </tr>
109 *   <tr>
110 *     <td>first_block->next</td><td>_Heap_Free_list_tail(heap)</td>
111 *     <td rowspan=3>memory area available for allocation</td>
112 *   </tr>
113 *   <tr><td>first_block->prev</td><td>_Heap_Free_list_head(heap)</td></tr>
114 *   <tr><td>...</td></tr>
115 *   <tr>
116 *     <td>last_block->prev_size</td><td colspan=2>size of first block</td>
117 *   </tr>
118 *   <tr>
119 *     <td>last_block->size</td>
120 *     <td colspan=2>first block begin address - last block begin address</td>
121 *   </tr>
122 *   <tr><td>heap->area_end</td><td colspan=2>heap area end address</td></tr>
123 * </table>
124 * The next block of the last block is the first block.  Since the first
125 * block indicates that the previous block is used, this ensures that the
126 * last block appears as used for the _Heap_Is_used() and _Heap_Is_free()
127 * functions.
128 */
129/**@{**/
130
131typedef struct Heap_Control Heap_Control;
132
133typedef struct Heap_Block Heap_Block;
134
135#ifndef HEAP_PROTECTION
136  #define HEAP_PROTECTION_HEADER_SIZE 0
137#else
138  #include <rtems/score/thread.h>
139
140  #define HEAP_PROTECTOR_COUNT 2
141
142  #define HEAP_BEGIN_PROTECTOR_0 ((uintptr_t) 0xfd75a98f)
143  #define HEAP_BEGIN_PROTECTOR_1 ((uintptr_t) 0xbfa1f177)
144  #define HEAP_END_PROTECTOR_0 ((uintptr_t) 0xd6b8855e)
145  #define HEAP_END_PROTECTOR_1 ((uintptr_t) 0x13a44a5b)
146
147  #define HEAP_FREE_PATTERN ((uintptr_t) 0xe7093cdf)
148
149  #define HEAP_PROTECTION_OBOLUS ((Heap_Block *) 1)
150
151  typedef void (*_Heap_Protection_handler)(
152     Heap_Control *heap,
153     Heap_Block *block
154  );
155
156  typedef struct {
157    _Heap_Protection_handler block_initialize;
158    _Heap_Protection_handler block_check;
159    _Heap_Protection_handler block_error;
160    void *handler_data;
161    Heap_Block *first_delayed_free_block;
162    Heap_Block *last_delayed_free_block;
163    uintptr_t delayed_free_block_count;
164  } Heap_Protection;
165
166  typedef struct {
167    uintptr_t protector [HEAP_PROTECTOR_COUNT];
168    Heap_Block *next_delayed_free_block;
169    Thread_Control *task;
170    void *tag;
171  } Heap_Protection_block_begin;
172
173  typedef struct {
174    uintptr_t protector [HEAP_PROTECTOR_COUNT];
175  } Heap_Protection_block_end;
176
177  #define HEAP_PROTECTION_HEADER_SIZE \
178    (sizeof(Heap_Protection_block_begin) + sizeof(Heap_Protection_block_end))
179#endif
180
181/**
182 * @brief The block header consists of the two size fields
183 * (@ref Heap_Block.prev_size and @ref Heap_Block.size_and_flag).
184 */
185#define HEAP_BLOCK_HEADER_SIZE \
186  (2 * sizeof(uintptr_t) + HEAP_PROTECTION_HEADER_SIZE)
187
188/**
189 * @brief Description for free or used blocks.
190 */
191struct Heap_Block {
192  /**
193   * @brief Size of the previous block or part of the allocated area of the
194   * previous block.
195   *
196   * This field is only valid if the previous block is free.  This case is
197   * indicated by a cleared @c HEAP_PREV_BLOCK_USED flag in the
198   * @a size_and_flag field of the current block.
199   *
200   * In a used block only the @a size_and_flag field needs to be valid.  The
201   * @a prev_size field of the current block is maintained by the previous
202   * block.  The current block can use the @a prev_size field in the next block
203   * for allocation.
204   */
205  uintptr_t prev_size;
206
207  #ifdef HEAP_PROTECTION
208    Heap_Protection_block_begin Protection_begin;
209  #endif
210
211  /**
212   * @brief Contains the size of the current block and a flag which indicates
213   * if the previous block is free or used.
214   *
215   * If the flag @c HEAP_PREV_BLOCK_USED is set, then the previous block is
216   * used, otherwise the previous block is free.  A used previous block may
217   * claim the @a prev_size field for allocation.  This trick allows to
218   * decrease the overhead in the used blocks by the size of the @a prev_size
219   * field.  As sizes are required to be multiples of two, the least
220   * significant bits would be always zero. We use this bit to store the flag.
221   *
222   * This field is always valid.
223   */
224  uintptr_t size_and_flag;
225
226  #ifdef HEAP_PROTECTION
227    Heap_Protection_block_end Protection_end;
228  #endif
229
230  /**
231   * @brief Pointer to the next free block or part of the allocated area.
232   *
233   * This field is page size aligned and begins of the allocated area in case
234   * the block is used.
235   *
236   * This field is only valid if the block is free and thus part of the free
237   * block list.
238   */
239  Heap_Block *next;
240
241  /**
242   * @brief Pointer to the previous free block or part of the allocated area.
243   *
244   * This field is only valid if the block is free and thus part of the free
245   * block list.
246   */
247  Heap_Block *prev;
248};
249
250/**
251 * @brief Run-time heap statistics.
252 *
253 * The value @a searches / @a allocs gives the mean number of searches per
254 * allocation, while @a max_search gives maximum number of searches ever
255 * performed on a single allocation call.
256 */
257typedef struct {
258  /**
259   * @brief Instance number of this heap.
260   */
261  uint32_t instance;
262
263  /**
264   * @brief Size of the allocatable area in bytes.
265   *
266   * This value is an integral multiple of the page size.
267   */
268  uintptr_t size;
269
270  /**
271   * @brief Current free size in bytes.
272   *
273   * This value is an integral multiple of the page size.
274   */
275  uintptr_t free_size;
276
277  /**
278   * @brief Minimum free size ever in bytes.
279   *
280   * This value is an integral multiple of the page size.
281   */
282  uintptr_t min_free_size;
283
284  /**
285   * @brief Current number of free blocks.
286   */
287  uint32_t free_blocks;
288
289  /**
290   * @brief Maximum number of free blocks ever.
291   */
292  uint32_t max_free_blocks;
293
294  /**
295   * @brief Current number of used blocks.
296   */
297  uint32_t used_blocks;
298
299  /**
300   * @brief Maximum number of blocks searched ever.
301   */
302  uint32_t max_search;
303
304  /**
305   * @brief Total number of successful allocations.
306   */
307  uint32_t allocs;
308
309  /**
310   * @brief Total number of searches ever.
311   */
312  uint32_t searches;
313
314  /**
315   * @brief Total number of suceessful calls to free.
316   */
317  uint32_t frees;
318
319  /**
320   * @brief Total number of successful resizes.
321   */
322  uint32_t resizes;
323} Heap_Statistics;
324
325/**
326 * @brief Control block used to manage a heap.
327 */
328struct Heap_Control {
329  Heap_Block free_list;
330  uintptr_t page_size;
331  uintptr_t min_block_size;
332  uintptr_t area_begin;
333  uintptr_t area_end;
334  Heap_Block *first_block;
335  Heap_Block *last_block;
336  Heap_Statistics stats;
337  #ifdef HEAP_PROTECTION
338    Heap_Protection Protection;
339  #endif
340};
341
342/**
343 * @brief Information about blocks.
344 */
345typedef struct {
346  /**
347   * @brief Number of blocks of this type.
348   */
349  uint32_t number;
350
351  /**
352   * @brief Largest block of this type.
353   */
354  uint32_t largest;
355
356  /**
357   * @brief Total size of the blocks of this type.
358   */
359  uint32_t total;
360} Heap_Information;
361
362/**
363 * @brief Information block returned by _Heap_Get_information().
364 */
365typedef struct {
366  Heap_Information Free;
367  Heap_Information Used;
368} Heap_Information_block;
369
370/**
371 * @brief Heap area structure for table based heap initialization and
372 * extension.
373 *
374 * @see Heap_Initialization_or_extend_handler.
375 */
376typedef struct {
377  void *begin;
378  uintptr_t size;
379} Heap_Area;
380
381/**
382 * @brief Heap initialization and extend handler type.
383 *
384 * This helps to do a table based heap initialization and extension.  Create a
385 * table of Heap_Area elements and iterate through it.  Set the handler to
386 * _Heap_Initialize() in the first iteration and then to _Heap_Extend().
387 *
388 * @see Heap_Area, _Heap_Initialize(), _Heap_Extend(), or _Heap_No_extend().
389 */
390typedef uintptr_t (*Heap_Initialization_or_extend_handler)(
391  Heap_Control *heap,
392  void *area_begin,
393  uintptr_t area_size,
394  uintptr_t page_size_or_unused
395);
396
397/**
398 * @brief Extends the memory available for the heap @a heap using the memory
399 * area starting at @a area_begin of size @a area_size bytes.
400 *
401 * There are no alignment requirements.  The memory area must be big enough to
402 * contain some maintainance blocks.  It must not overlap parts of the current
403 * heap areas.  Disconnected subordinate heap areas will lead to used blocks
404 * which cover the gaps.  Extending with an inappropriate memory area will
405 * corrupt the heap.
406 *
407 * The unused fourth parameter is provided to have the same signature as
408 * _Heap_Initialize().
409 *
410 * Returns the extended space available for allocation, or zero in case of failure.
411 *
412 * @see Heap_Initialization_or_extend_handler.
413 */
414uintptr_t _Heap_Extend(
415  Heap_Control *heap,
416  void *area_begin,
417  uintptr_t area_size,
418  uintptr_t unused
419);
420
421/**
422 * @brief This function returns always zero.
423 *
424 * This function only returns zero and does nothing else.
425 *
426 * Returns always zero.
427 *
428 * @see Heap_Initialization_or_extend_handler.
429 */
430uintptr_t _Heap_No_extend(
431  Heap_Control *unused_0,
432  void *unused_1,
433  uintptr_t unused_2,
434  uintptr_t unused_3
435);
436
437RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_up(
438  uintptr_t value,
439  uintptr_t alignment
440)
441{
442  uintptr_t remainder = value % alignment;
443
444  if ( remainder != 0 ) {
445    return value - remainder + alignment;
446  } else {
447    return value;
448  }
449}
450
451/**
452 * @brief Returns the worst case overhead to manage a memory area.
453 */
454RTEMS_INLINE_ROUTINE uintptr_t _Heap_Area_overhead(
455  uintptr_t page_size
456)
457{
458  if ( page_size != 0 ) {
459    page_size = _Heap_Align_up( page_size, CPU_ALIGNMENT );
460  } else {
461    page_size = CPU_ALIGNMENT;
462  }
463
464  return 2 * (page_size - 1) + HEAP_BLOCK_HEADER_SIZE;
465}
466
467/** @} */
468
469#ifdef __cplusplus
470}
471#endif
472
473#endif
474/* end of include file */
Note: See TracBrowser for help on using the repository browser.