source: rtems/cpukit/score/include/rtems/score/heap.h @ 74ac113

4.115
Last change on this file since 74ac113 was 74ac113, checked in by Joel Sherrill <joel.sherrill@…>, on 08/21/11 at 19:51:41

2011-08-21 Joel Sherrill <joel.sherrilL@…>

PR 1873/cpukit

  • score/include/rtems/score/heap.h: When using heap protection, we should account for adding an aligned protection footer.
  • Property mode set to 100644
File size: 18.2 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 *  $Id$
18 */
19
20#ifndef _RTEMS_SCORE_HEAP_H
21#define _RTEMS_SCORE_HEAP_H
22
23#include <rtems/system.h>
24#include <rtems/score/thread.h>
25
26#ifdef __cplusplus
27extern "C" {
28#endif
29
30#ifdef RTEMS_DEBUG
31  #define HEAP_PROTECTION
32#endif
33
34/**
35 * @defgroup ScoreHeap Heap Handler
36 *
37 * @ingroup Score
38 *
39 * @brief The Heap Handler provides a heap.
40 *
41 * A heap is a doubly linked list of variable size blocks which are allocated
42 * using the first fit method.  Garbage collection is performed each time a
43 * block is returned to the heap by coalescing neighbor blocks.  Control
44 * information for both allocated and free blocks is contained in the heap
45 * area.  A heap control structure contains control information for the heap.
46 *
47 * The alignment routines could be made faster should we require only powers of
48 * two to be supported for page size, alignment and boundary arguments.  The
49 * minimum alignment requirement for pages is currently CPU_ALIGNMENT and this
50 * value is only required to be multiple of two and explicitly not required to
51 * be a power of two.
52 *
53 * There are two kinds of blocks.  One sort describes a free block from which
54 * we can allocate memory.  The other blocks are used and provide an allocated
55 * memory area.  The free blocks are accessible via a list of free blocks.
56 *
57 * Blocks or areas cover a continuous set of memory addresses. They have a
58 * begin and end address.  The end address is not part of the set.  The size of
59 * a block or area equals the distance between the begin and end address in
60 * units of bytes.
61 *
62 * Free blocks look like:
63 * <table>
64 *   <tr>
65 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
66 *       previous block is free, <br> otherwise it may contain data used by
67 *       the previous block</td>
68 *   </tr>
69 *   <tr>
70 *     <td>block size and a flag which indicates if the previous block is free
71 *       or used, <br> this field contains always valid data regardless of the
72 *       block usage</td>
73 *   </tr>
74 *   <tr><td>pointer to next block (this field is page size aligned)</td></tr>
75 *   <tr><td>pointer to previous block</td></tr>
76 *   <tr><td colspan=2>free space</td></tr>
77 * </table>
78 *
79 * Used blocks look like:
80 * <table>
81 *   <tr>
82 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
83 *       previous block is free,<br>otherwise it may contain data used by
84 *       the previous block</td>
85 *   </tr>
86 *   <tr>
87 *     <td>block size and a flag which indicates if the previous block is free
88 *       or used, <br> this field contains always valid data regardless of the
89 *       block usage</td>
90 *   </tr>
91 *   <tr><td>begin of allocated area (this field is page size aligned)</td></tr>
92 *   <tr><td>allocated space</td></tr>
93 *   <tr><td colspan=2>allocated space</td></tr>
94 * </table>
95 *
96 * The heap area after initialization contains two blocks and looks like:
97 * <table>
98 *   <tr><th>Label</th><th colspan=2>Content</th></tr>
99 *   <tr><td>heap->area_begin</td><td colspan=2>heap area begin address</td></tr>
100 *   <tr>
101 *     <td>first_block->prev_size</td>
102 *     <td colspan=2>
103 *       subordinate heap area end address (this will be used to maintain a
104 *       linked list of scattered heap areas)
105 *     </td>
106 *   </tr>
107 *   <tr>
108 *     <td>first_block->size</td>
109 *     <td colspan=2>size available for allocation
110 *       | @c HEAP_PREV_BLOCK_USED</td>
111 *   </tr>
112 *   <tr>
113 *     <td>first_block->next</td><td>_Heap_Free_list_tail(heap)</td>
114 *     <td rowspan=3>memory area available for allocation</td>
115 *   </tr>
116 *   <tr><td>first_block->prev</td><td>_Heap_Free_list_head(heap)</td></tr>
117 *   <tr><td>...</td></tr>
118 *   <tr>
119 *     <td>last_block->prev_size</td><td colspan=2>size of first block</td>
120 *   </tr>
121 *   <tr>
122 *     <td>last_block->size</td>
123 *     <td colspan=2>first block begin address - last block begin address</td>
124 *   </tr>
125 *   <tr><td>heap->area_end</td><td colspan=2>heap area end address</td></tr>
126 * </table>
127 * The next block of the last block is the first block.  Since the first
128 * block indicates that the previous block is used, this ensures that the
129 * last block appears as used for the _Heap_Is_used() and _Heap_Is_free()
130 * functions.
131 *
132 * @{
133 */
134
135typedef struct Heap_Control Heap_Control;
136
137typedef struct Heap_Block Heap_Block;
138
139#ifndef HEAP_PROTECTION
140  #define HEAP_PROTECTION_HEADER_SIZE 0
141#else
142  #define HEAP_PROTECTOR_COUNT 2
143
144  #define HEAP_BEGIN_PROTECTOR_0 ((uintptr_t) 0xfd75a98f)
145  #define HEAP_BEGIN_PROTECTOR_1 ((uintptr_t) 0xbfa1f177)
146  #define HEAP_END_PROTECTOR_0 ((uintptr_t) 0xd6b8855e)
147  #define HEAP_END_PROTECTOR_1 ((uintptr_t) 0x13a44a5b)
148
149  #define HEAP_FREE_PATTERN ((uintptr_t) 0xe7093cdf)
150
151  #define HEAP_PROTECTION_OBOLUS ((Heap_Block *) 1)
152
153  typedef void (*_Heap_Protection_handler)(
154     Heap_Control *heap,
155     Heap_Block *block
156  );
157
158  typedef struct {
159    _Heap_Protection_handler block_initialize;
160    _Heap_Protection_handler block_check;
161    _Heap_Protection_handler block_error;
162    void *handler_data;
163    Heap_Block *first_delayed_free_block;
164    Heap_Block *last_delayed_free_block;
165    uintptr_t delayed_free_block_count;
166  } Heap_Protection;
167
168  typedef struct {
169    uintptr_t protector [HEAP_PROTECTOR_COUNT];
170    Heap_Block *next_delayed_free_block;
171    Thread_Control *task;
172    void *tag;
173  } Heap_Protection_block_begin;
174
175  typedef struct {
176    uintptr_t protector [HEAP_PROTECTOR_COUNT];
177  } Heap_Protection_block_end;
178
179  #define HEAP_PROTECTION_HEADER_SIZE \
180    (sizeof(Heap_Protection_block_begin) + \
181     CPU_ALIGNMENT + \
182     sizeof(Heap_Protection_block_end))
183#endif
184
185/**
186 * @brief See also @ref Heap_Block.size_and_flag.
187 */
188#define HEAP_PREV_BLOCK_USED ((uintptr_t) 1)
189
190/**
191 * @brief Size of the part at the block begin which may be used for allocation
192 * in charge of the previous block.
193 */
194#define HEAP_ALLOC_BONUS sizeof(uintptr_t)
195
196/**
197 * @brief The block header consists of the two size fields
198 * (@ref Heap_Block.prev_size and @ref Heap_Block.size_and_flag).
199 */
200#define HEAP_BLOCK_HEADER_SIZE \
201  (2 * sizeof(uintptr_t) + HEAP_PROTECTION_HEADER_SIZE)
202
203/**
204 * @brief Description for free or used blocks.
205 */
206struct Heap_Block {
207  /**
208   * @brief Size of the previous block or part of the allocated area of the
209   * previous block.
210   *
211   * This field is only valid if the previous block is free.  This case is
212   * indicated by a cleared @c HEAP_PREV_BLOCK_USED flag in the
213   * @a size_and_flag field of the current block.
214   *
215   * In a used block only the @a size_and_flag field needs to be valid.  The
216   * @a prev_size field of the current block is maintained by the previous
217   * block.  The current block can use the @a prev_size field in the next block
218   * for allocation.
219   */
220  uintptr_t prev_size;
221
222  #ifdef HEAP_PROTECTION
223    Heap_Protection_block_begin Protection_begin;
224  #endif
225
226  /**
227   * @brief Contains the size of the current block and a flag which indicates
228   * if the previous block is free or used.
229   *
230   * If the flag @c HEAP_PREV_BLOCK_USED is set, then the previous block is
231   * used, otherwise the previous block is free.  A used previous block may
232   * claim the @a prev_size field for allocation.  This trick allows to
233   * decrease the overhead in the used blocks by the size of the @a prev_size
234   * field.  As sizes are required to be multiples of two, the least
235   * significant bits would be always zero. We use this bit to store the flag.
236   *
237   * This field is always valid.
238   */
239  uintptr_t size_and_flag;
240
241  #ifdef HEAP_PROTECTION
242    Heap_Protection_block_end Protection_end;
243  #endif
244
245  /**
246   * @brief Pointer to the next free block or part of the allocated area.
247   *
248   * This field is page size aligned and begins of the allocated area in case
249   * the block is used.
250   *
251   * This field is only valid if the block is free and thus part of the free
252   * block list.
253   */
254  Heap_Block *next;
255
256  /**
257   * @brief Pointer to the previous free block or part of the allocated area.
258   *
259   * This field is only valid if the block is free and thus part of the free
260   * block list.
261   */
262  Heap_Block *prev;
263};
264
265/**
266 * @brief Run-time heap statistics.
267 *
268 * The value @a searches / @a allocs gives the mean number of searches per
269 * allocation, while @a max_search gives maximum number of searches ever
270 * performed on a single allocation call.
271 */
272typedef struct {
273  /**
274   * @brief Instance number of this heap.
275   */
276  uint32_t instance;
277
278  /**
279   * @brief Size of the allocatable area in bytes.
280   *
281   * This value is an integral multiple of the page size.
282   */
283  uintptr_t size;
284
285  /**
286   * @brief Current free size in bytes.
287   *
288   * This value is an integral multiple of the page size.
289   */
290  uintptr_t free_size;
291
292  /**
293   * @brief Minimum free size ever in bytes.
294   *
295   * This value is an integral multiple of the page size.
296   */
297  uintptr_t min_free_size;
298
299  /**
300   * @brief Current number of free blocks.
301   */
302  uint32_t free_blocks;
303
304  /**
305   * @brief Maximum number of free blocks ever.
306   */
307  uint32_t max_free_blocks;
308
309  /**
310   * @brief Current number of used blocks.
311   */
312  uint32_t used_blocks;
313
314  /**
315   * @brief Maximum number of blocks searched ever.
316   */
317  uint32_t max_search;
318
319  /**
320   * @brief Total number of successful allocations.
321   */
322  uint32_t allocs;
323
324  /**
325   * @brief Total number of searches ever.
326   */
327  uint32_t searches;
328
329  /**
330   * @brief Total number of suceessful calls to free.
331   */
332  uint32_t frees;
333
334  /**
335   * @brief Total number of successful resizes.
336   */
337  uint32_t resizes;
338} Heap_Statistics;
339
340/**
341 * @brief Control block used to manage a heap.
342 */
343struct Heap_Control {
344  Heap_Block free_list;
345  uintptr_t page_size;
346  uintptr_t min_block_size;
347  uintptr_t area_begin;
348  uintptr_t area_end;
349  Heap_Block *first_block;
350  Heap_Block *last_block;
351  Heap_Statistics stats;
352  #ifdef HEAP_PROTECTION
353    Heap_Protection Protection;
354  #endif
355};
356
357/**
358 * @brief Information about blocks.
359 */
360typedef struct {
361  /**
362   * @brief Number of blocks of this type.
363   */
364  uint32_t number;
365
366  /**
367   * @brief Largest block of this type.
368   */
369  uint32_t largest;
370
371  /**
372   * @brief Total size of the blocks of this type.
373   */
374  uint32_t total;
375} Heap_Information;
376
377/**
378 * @brief Information block returned by _Heap_Get_information().
379 */
380typedef struct {
381  Heap_Information Free;
382  Heap_Information Used;
383} Heap_Information_block;
384
385/**
386 * @brief See _Heap_Resize_block().
387 */
388typedef enum {
389  HEAP_RESIZE_SUCCESSFUL,
390  HEAP_RESIZE_UNSATISFIED,
391  HEAP_RESIZE_FATAL_ERROR
392} Heap_Resize_status;
393
394/**
395 * @brief Gets the first and last block for the heap area with begin
396 * @a heap_area_begin and size @a heap_area_size.
397 *
398 * A page size of @a page_size and minimal block size of @a min_block_size will
399 * be used for calculation.
400 *
401 * Nothing will be written to this area.
402 *
403 * In case of success the pointers to the first and last block will be returned
404 * via @a first_block_ptr and @a last_block_ptr.
405 *
406 * Returns @c true if the area is big enough, and @c false otherwise.
407 */
408bool _Heap_Get_first_and_last_block(
409  uintptr_t heap_area_begin,
410  uintptr_t heap_area_size,
411  uintptr_t page_size,
412  uintptr_t min_block_size,
413  Heap_Block **first_block_ptr,
414  Heap_Block **last_block_ptr
415);
416
417/**
418 * @brief Initializes the heap control block @a heap to manage the area
419 * starting at @a area_begin of size @a area_size bytes.
420 *
421 * Blocks of memory are allocated from the heap in multiples of @a page_size
422 * byte units.  If the @a page_size is equal to zero or is not multiple of
423 * @c CPU_ALIGNMENT, it is aligned up to the nearest @c CPU_ALIGNMENT boundary.
424 *
425 * Returns the maximum memory available, or zero in case of failure.
426 */
427uintptr_t _Heap_Initialize(
428  Heap_Control *heap,
429  void *area_begin,
430  uintptr_t area_size,
431  uintptr_t page_size
432);
433
434/**
435 * @brief Extends the memory available for the heap @a heap using the memory
436 * area starting at @a area_begin of size @a area_size bytes.
437 *
438 * The extended space available for allocation will be returned in
439 * @a amount_extended.  This pointer may be @c NULL.
440 *
441 * There are no alignment requirements.  The memory area must be big enough to
442 * contain some maintainance blocks.  It must not overlap parts of the current
443 * heap areas.  Disconnected subordinate heap areas will lead to used blocks
444 * which cover the gaps.  Extending with an inappropriate memory area will
445 * corrupt the heap.
446 *
447 * Returns @c true in case of success, and @c false otherwise.
448 */
449bool _Heap_Extend(
450  Heap_Control *heap,
451  void *area_begin,
452  uintptr_t area_size,
453  uintptr_t *amount_extended
454);
455
456/**
457 * @brief Allocates a memory area of size @a size bytes from the heap @a heap.
458 *
459 * If the alignment parameter @a alignment is not equal to zero, the allocated
460 * memory area will begin at an address aligned by this value.
461 *
462 * If the boundary parameter @a boundary is not equal to zero, the allocated
463 * memory area will fulfill a boundary constraint.  The boundary value
464 * specifies the set of addresses which are aligned by the boundary value.  The
465 * interior of the allocated memory area will not contain an element of this
466 * set.  The begin or end address of the area may be a member of the set.
467 *
468 * A size value of zero will return a unique address which may be freed with
469 * _Heap_Free().
470 *
471 * Returns a pointer to the begin of the allocated memory area, or @c NULL if
472 * no memory is available or the parameters are inconsistent.
473 */
474void *_Heap_Allocate_aligned_with_boundary(
475  Heap_Control *heap,
476  uintptr_t size,
477  uintptr_t alignment,
478  uintptr_t boundary
479);
480
481/**
482 * @brief See _Heap_Allocate_aligned_with_boundary() with boundary equals zero.
483 */
484RTEMS_INLINE_ROUTINE void *_Heap_Allocate_aligned(
485  Heap_Control *heap,
486  uintptr_t size,
487  uintptr_t alignment
488)
489{
490  return _Heap_Allocate_aligned_with_boundary( heap, size, alignment, 0 );
491}
492
493/**
494 * @brief See _Heap_Allocate_aligned_with_boundary() with alignment and
495 * boundary equals zero.
496 */
497RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size )
498{
499  return _Heap_Allocate_aligned_with_boundary( heap, size, 0, 0 );
500}
501
502/**
503 * @brief Frees the allocated memory area starting at @a addr in the heap
504 * @a heap.
505 *
506 * Inappropriate values for @a addr may corrupt the heap.
507 *
508 * Returns @c true in case of success, and @c false otherwise.
509 */
510bool _Heap_Free( Heap_Control *heap, void *addr );
511
512/**
513 * @brief Walks the heap @a heap to verify its integrity.
514 *
515 * If @a dump is @c true, then diagnostic messages will be printed to standard
516 * output.  In this case @a source is used to mark the output lines.
517 *
518 * Returns @c true if no errors occured, and @c false if the heap is corrupt.
519 */
520bool _Heap_Walk(
521  Heap_Control *heap,
522  int source,
523  bool dump
524);
525
526/**
527 * @brief Returns information about used and free blocks for the heap @a heap
528 * in @a info.
529 */
530void _Heap_Get_information(
531  Heap_Control *heap,
532  Heap_Information_block *info
533);
534
535/**
536 * @brief Returns information about free blocks for the heap @a heap in
537 * @a info.
538 */
539void _Heap_Get_free_information(
540  Heap_Control *heap,
541  Heap_Information *info
542);
543
544/**
545 * @brief Returns the size of the allocatable memory area starting at @a addr
546 * in @a size.
547 *
548 * The size value may be greater than the initially requested size in
549 * _Heap_Allocate_aligned_with_boundary().
550 *
551 * Inappropriate values for @a addr will not corrupt the heap, but may yield
552 * invalid size values.
553 *
554 * Returns @a true if successful, and @c false otherwise.
555 */
556bool _Heap_Size_of_alloc_area(
557  Heap_Control *heap,
558  void *addr,
559  uintptr_t *size
560);
561
562/**
563 * @brief Resizes the block of the allocated memory area starting at @a addr.
564 *
565 * The new memory area will have a size of at least @a size bytes.  A resize
566 * may be impossible and depends on the current heap usage.
567 *
568 * The size available for allocation in the current block before the resize
569 * will be returned in @a old_size.  The size available for allocation in
570 * the resized block will be returned in @a new_size.  If the resize was not
571 * successful, then a value of zero will be returned in @a new_size.
572 *
573 * Inappropriate values for @a addr may corrupt the heap.
574 */
575Heap_Resize_status _Heap_Resize_block(
576  Heap_Control *heap,
577  void *addr,
578  uintptr_t size,
579  uintptr_t *old_size,
580  uintptr_t *new_size
581);
582
583#if !defined(__RTEMS_APPLICATION__)
584
585#include <rtems/score/heap.inl>
586
587/**
588 * @brief Allocates the memory area starting at @a alloc_begin of size
589 * @a alloc_size bytes in the block @a block.
590 *
591 * The block may be split up into multiple blocks.  The previous and next block
592 * may be used or free.  Free block parts which form a vaild new block will be
593 * inserted into the free list or merged with an adjacent free block.  If the
594 * block is used, they will be inserted after the free list head.  If the block
595 * is free, they will be inserted after the previous block in the free list.
596 *
597 * Inappropriate values for @a alloc_begin or @a alloc_size may corrupt the
598 * heap.
599 *
600 * Returns the block containing the allocated memory area.
601 */
602Heap_Block *_Heap_Block_allocate(
603  Heap_Control *heap,
604  Heap_Block *block,
605  uintptr_t alloc_begin,
606  uintptr_t alloc_size
607);
608
609#ifndef HEAP_PROTECTION
610  #define _Heap_Protection_block_initialize( heap, block ) ((void) 0)
611  #define _Heap_Protection_block_check( heap, block ) ((void) 0)
612  #define _Heap_Protection_block_error( heap, block ) ((void) 0)
613#else
614  static inline void _Heap_Protection_block_initialize(
615    Heap_Control *heap,
616    Heap_Block *block
617  )
618  {
619    (*heap->Protection.block_initialize)( heap, block );
620  }
621
622  static inline void _Heap_Protection_block_check(
623    Heap_Control *heap,
624    Heap_Block *block
625  )
626  {
627    (*heap->Protection.block_check)( heap, block );
628  }
629
630  static inline void _Heap_Protection_block_error(
631    Heap_Control *heap,
632    Heap_Block *block
633  )
634  {
635    (*heap->Protection.block_error)( heap, block );
636  }
637#endif
638
639/** @} */
640
641#ifdef RTEMS_DEBUG
642  #define RTEMS_HEAP_DEBUG
643#endif
644
645#ifdef RTEMS_HEAP_DEBUG
646  #include <assert.h>
647  #define _HAssert( cond ) \
648    do { \
649      if ( !(cond) ) { \
650        __assert( __FILE__, __LINE__, #cond ); \
651      } \
652    } while (0)
653#else
654  #define _HAssert( cond ) ((void) 0)
655#endif
656
657#endif /* !defined(__RTEMS_APPLICATION__) */
658
659#ifdef __cplusplus
660}
661#endif
662
663#endif
664/* end of include file */
Note: See TracBrowser for help on using the repository browser.