source: rtems/cpukit/score/include/rtems/score/heap.h @ 518c2aeb

4.104.115
Last change on this file since 518c2aeb was 518c2aeb, checked in by Joel Sherrill <joel.sherrill@…>, on 09/09/09 at 14:58:37

2009-09-09 Sebastian Huber <Sebastian.Huber@…>

  • score/include/rtems/score/heap.h, score/inline/rtems/score/heap.inl, score/src/heapallocate.c, score/src/heap.c, score/src/heapextend.c, score/src/heapresizeblock.c, score/src/heapwalk.c: Documenation. Simplified block resize. Improved heap walk. Changed heap layout to avoid a special case for _Heap_Is_used() and _Heap_Is_free().
  • libmisc/stackchk/check.c: Update for heap API changes.
  • Property mode set to 100644
File size: 15.0 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#ifdef __cplusplus
24extern "C" {
25#endif
26
27/**
28 * @defgroup ScoreHeap Heap Handler
29 *
30 * @ingroup Score
31 *
32 * @brief The Heap Handler provides a heap.
33 *
34 * A heap is a doubly linked list of variable size blocks which are allocated
35 * using the first fit method.  Garbage collection is performed each time a
36 * block is returned to the heap by coalescing neighbor blocks.  Control
37 * information for both allocated and free blocks is contained in the heap
38 * area.  A heap control structure contains control information for the heap.
39 *
40 * The alignment routines could be made faster should we require only powers of
41 * two to be supported both for page size, alignment and boundary arguments.
42 * However, both workspace and malloc heaps are initialized with
43 * CPU_HEAP_ALIGNMENT as page size, and while all the BSPs seem to use
44 * CPU_ALIGNMENT (that is power of two) as CPU_HEAP_ALIGNMENT, for whatever
45 * reason CPU_HEAP_ALIGNMENT is only required to be multiple of CPU_ALIGNMENT
46 * and explicitly not required to be a power of two.
47 *
48 * There are two kinds of blocks.  One sort describes a free block from which
49 * we can allocate memory.  The other blocks are used and provide an allocated
50 * memory area.  The free blocks are accessible via a list of free blocks.
51 *
52 * Blocks or areas cover a continuous set of memory addresses. They have a
53 * begin and end address.  The end address is not part of the set.  The size of
54 * a block or area equals the distance between the begin and end address in
55 * units of bytes.
56 *
57 * Free blocks look like:
58 * <table>
59 *   <tr>
60 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
61 *       previous block is free, <br> otherwise it may contain data used by
62 *       the previous block</td>
63 *   </tr>
64 *   <tr>
65 *     <td>block size and a flag which indicates if the previous block is free
66 *       or used, <br> this field contains always valid data regardless of the
67 *       block usage</td>
68 *   </tr>
69 *   <tr><td>pointer to next block (this field is page size aligned)</td></tr>
70 *   <tr><td>pointer to previous block</td></tr>
71 *   <tr><td colspan=2>free space</td></tr>
72 * </table>
73 *
74 * Used blocks look like:
75 * <table>
76 *   <tr>
77 *     <td rowspan=4>@ref Heap_Block</td><td>previous block size in case the
78 *       previous block is free,<br>otherwise it may contain data used by
79 *       the previous block</td>
80 *   </tr>
81 *   <tr>
82 *     <td>block size and a flag which indicates if the previous block is free
83 *       or used, <br> this field contains always valid data regardless of the
84 *       block usage</td>
85 *   </tr>
86 *   <tr><td>begin of allocated area (this field is page size aligned)</td></tr>
87 *   <tr><td>allocated space</td></tr>
88 *   <tr><td colspan=2>allocated space</td></tr>
89 * </table>
90 *
91 * The heap area after initialization contains two blocks and looks like:
92 * <table>
93 *   <tr><th>Label</th><th colspan=2>Content</th></tr>
94 *   <tr><td>heap->area_begin</td><td colspan=2>heap area begin address</td></tr>
95 *   <tr>
96 *     <td>first_block->prev_size</td>
97 *     <td colspan=2>page size (the value is arbitrary)</td>
98 *   </tr>
99 *   <tr>
100 *     <td>first_block->size</td>
101 *     <td colspan=2>size available for allocation
102 *       | @c HEAP_PREV_BLOCK_USED</td>
103 *   </tr>
104 *   <tr>
105 *     <td>first_block->next</td><td>_Heap_Free_list_tail(heap)</td>
106 *     <td rowspan=3>memory area available for allocation</td>
107 *   </tr>
108 *   <tr><td>first_block->prev</td><td>_Heap_Free_list_head(heap)</td></tr>
109 *   <tr><td>...</td></tr>
110 *   <tr>
111 *     <td>last_block->prev_size</td><td colspan=2>size of first block</td>
112 *   </tr>
113 *   <tr>
114 *     <td>last_block->size</td>
115 *     <td colspan=2>first block begin address - last block begin address</td>
116 *   </tr>
117 *   <tr><td>heap->area_end</td><td colspan=2>heap area end address</td></tr>
118 * </table>
119 * The next block of the last block is the first block.  Since the first
120 * block indicates that the previous block is used, this ensures that the
121 * last block appears as used for the _Heap_Is_used() and _Heap_Is_free()
122 * functions.
123 *
124 * @{
125 */
126
127/**
128 * @brief See also @ref Heap_Block.size_and_flag.
129 */
130#define HEAP_PREV_BLOCK_USED ((uintptr_t) 1)
131
132/**
133 * @brief Offset from the block begin up to the block size field
134 * (@ref Heap_Block.size_and_flag).
135 */
136#define HEAP_BLOCK_SIZE_OFFSET sizeof(uintptr_t)
137
138/**
139 * @brief The block header consists of the two size fields
140 * (@ref Heap_Block.prev_size and @ref Heap_Block.size_and_flag).
141 */
142#define HEAP_BLOCK_HEADER_SIZE (sizeof(uintptr_t) * 2)
143
144/**
145 * @brief Description for free or used blocks.
146 */
147typedef struct Heap_Block {
148  /**
149   * @brief Size of the previous block or part of the allocated area of the
150   * previous block.
151   *
152   * This field is only valid if the previous block is free.  This case is
153   * indicated by a cleared @c HEAP_PREV_BLOCK_USED flag in the
154   * @a size_and_flag field of the current block.
155   *
156   * In a used block only the @a size_and_flag field needs to be valid.  The
157   * @a prev_size field of the current block is maintained by the previous
158   * block.  The current block can use the @a prev_size field in the next block
159   * for allocation.
160   */
161  uintptr_t prev_size;
162
163  /**
164   * @brief Contains the size of the current block and a flag which indicates
165   * if the previous block is free or used.
166   *
167   * If the flag @c HEAP_PREV_BLOCK_USED is set, then the previous block is
168   * used, otherwise the previous block is free.  A used previous block may
169   * claim the @a prev_size field for allocation.  This trick allows to
170   * decrease the overhead in the used blocks by the size of the
171   * @a prev_size field.  As sizes are always multiples of four, the two least
172   * significant bits are always zero. We use one of them to store the flag.
173   *
174   * This field is always valid.
175   */
176  uintptr_t size_and_flag;
177
178  /**
179   * @brief Pointer to the next free block or part of the allocated area.
180   *
181   * This field is page size aligned and begins of the allocated area in case
182   * the block is used.
183   *
184   * This field is only valid if the block is free and thus part of the free
185   * block list.
186   */
187  struct Heap_Block *next;
188
189  /**
190   * @brief Pointer to the previous free block or part of the allocated area.
191   *
192   * This field is only valid if the block is free and thus part of the free
193   * block list.
194   */
195  struct Heap_Block *prev;
196} Heap_Block;
197
198/**
199 * @brief Run-time heap statistics.
200 *
201 * The value @a searches / @a allocs gives the mean number of searches per
202 * allocation, while @a max_search gives maximum number of searches ever
203 * performed on a single allocation call.
204 */
205typedef struct {
206  /**
207   * @brief Instance number of this heap.
208   */
209  uint32_t instance;
210
211  /**
212   * @brief Size of the allocatable area in bytes.
213   *
214   * This value is an integral multiple of the page size.
215   */
216  uintptr_t size;
217
218  /**
219   * @brief Current free size in bytes.
220   *
221   * This value is an integral multiple of the page size.
222   */
223  uintptr_t free_size;
224
225  /**
226   * @brief Minimum free size ever in bytes.
227   *
228   * This value is an integral multiple of the page size.
229   */
230  uintptr_t min_free_size;
231
232  /**
233   * @brief Current number of free blocks.
234   */
235  uint32_t free_blocks;
236
237  /**
238   * @brief Maximum number of free blocks ever.
239   */
240  uint32_t max_free_blocks;
241
242  /**
243   * @brief Current number of used blocks.
244   */
245  uint32_t used_blocks;
246
247  /**
248   * @brief Maximum number of blocks searched ever.
249   */
250  uint32_t max_search;
251
252  /**
253   * @brief Total number of successful allocations.
254   */
255  uint32_t allocs;
256
257  /**
258   * @brief Total number of searches ever.
259   */
260  uint32_t searches;
261
262  /**
263   * @brief Total number of suceessful calls to free.
264   */
265  uint32_t frees;
266
267  /**
268   * @brief Total number of successful resizes.
269   */
270  uint32_t resizes;
271} Heap_Statistics;
272
273/**
274 * @brief Control block used to manage a heap.
275 */
276typedef struct {
277  Heap_Block free_list;
278  uintptr_t page_size;
279  uintptr_t min_block_size;
280  uintptr_t area_begin;
281  uintptr_t area_end;
282  Heap_Block *first_block;
283  Heap_Block *last_block;
284  Heap_Statistics stats;
285} Heap_Control;
286
287/**
288 * @brief Information about blocks.
289 */
290typedef struct {
291  /**
292   * @brief Number of blocks of this type.
293   */
294  uint32_t number;
295
296  /**
297   * @brief Largest block of this type.
298   */
299  uint32_t largest;
300
301  /**
302   * @brief Total size of the blocks of this type.
303   */
304  uint32_t total;
305} Heap_Information;
306
307/**
308 * @brief Information block returned by _Heap_Get_information().
309 */
310typedef struct {
311  Heap_Information Free;
312  Heap_Information Used;
313} Heap_Information_block;
314
315/**
316 * @brief See _Heap_Extend().
317 */
318typedef enum {
319  HEAP_EXTEND_SUCCESSFUL,
320  HEAP_EXTEND_ERROR,
321  HEAP_EXTEND_NOT_IMPLEMENTED
322} Heap_Extend_status;
323
324/**
325 * @brief See _Heap_Resize_block().
326 */
327typedef enum {
328  HEAP_RESIZE_SUCCESSFUL,
329  HEAP_RESIZE_UNSATISFIED,
330  HEAP_RESIZE_FATAL_ERROR
331} Heap_Resize_status;
332
333/**
334 * @brief Initializes the heap control block @a heap to manage the area
335 * starting at @a area_begin of size @a area_size bytes.
336 *
337 * Blocks of memory are allocated from the heap in multiples of @a page_size
338 * byte units.  If the @a page_size is equal to zero or is not multiple of
339 * @c CPU_ALIGNMENT, it is aligned up to the nearest @c CPU_ALIGNMENT boundary.
340 *
341 * Returns the maximum memory available, or zero in case of failure.
342 */
343uintptr_t _Heap_Initialize(
344  Heap_Control *heap,
345  void *area_begin,
346  uintptr_t area_size,
347  uintptr_t page_size
348);
349
350/**
351 * @brief Extends the memory area of the heap @a heap using the memory area
352 * starting at @a area_begin of size @a area_size bytes.
353 *
354 * The extended space available for allocation will be returned in
355 * @a amount_extended.
356 *
357 * The memory area must start at the end of the currently used memory area.
358 */
359Heap_Extend_status _Heap_Extend(
360  Heap_Control *heap,
361  void *area_begin,
362  uintptr_t area_size,
363  uintptr_t *amount_extended
364);
365
366/**
367 * @brief Allocates a memory area of size @a size bytes from the heap @a heap.
368 *
369 * If the alignment parameter @a alignment is not equal to zero, the allocated
370 * memory area will begin at an address aligned by this value.
371 *
372 * If the boundary parameter @a boundary is not equal to zero, the allocated
373 * memory area will fulfill a boundary constraint.  The boudnary value
374 * specifies the set of addresses which are aligned by the boundary value.  The
375 * interior of the allocated memory area will not contain an element of this
376 * set.  The begin or end address of the area may be a member of the set.
377 *
378 * A size value of zero will return a unique address which may be freed with
379 * _Heap_Free().
380 *
381 * Returns a pointer to the begin of the allocated memory area, or @c NULL if
382 * no memory is available or the parameters are inconsistent.
383 */
384void *_Heap_Allocate_aligned_with_boundary(
385  Heap_Control *heap,
386  uintptr_t size,
387  uintptr_t alignment,
388  uintptr_t boundary
389);
390
391/**
392 * @brief See _Heap_Allocate_aligned_with_boundary() with boundary equals zero.
393 */
394RTEMS_INLINE_ROUTINE void *_Heap_Allocate_aligned(
395  Heap_Control *heap,
396  uintptr_t size,
397  uintptr_t alignment
398)
399{
400  return _Heap_Allocate_aligned_with_boundary( heap, size, alignment, 0 );
401}
402
403/**
404 * @brief See _Heap_Allocate_aligned_with_boundary() with alignment and
405 * boundary equals zero.
406 */
407RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size )
408{
409  return _Heap_Allocate_aligned_with_boundary( heap, size, 0, 0 );
410}
411
412/**
413 * @brief Frees the allocated memory area starting at @a addr in the heap
414 * @a heap.
415 *
416 * Inappropriate values for @a addr may corrupt the heap.
417 *
418 * Returns @c true in case of success, and @c false otherwise.
419 */
420bool _Heap_Free( Heap_Control *heap, void *addr );
421
422/**
423 * @brief Walks the heap @a heap to verify its integrity.
424 *
425 * If @a dump is @c true, then diagnostic messages will be printed to standard
426 * output.  In this case @a source is used to mark the output lines.
427 *
428 * Returns @c true if no errors occured, and @c false if the heap is corrupt.
429 */
430bool _Heap_Walk(
431  Heap_Control *heap,
432  int source,
433  bool dump
434);
435
436/**
437 * @brief Returns information about used and free blocks for the heap @a heap
438 * in @a info.
439 */
440void _Heap_Get_information(
441  Heap_Control *heap,
442  Heap_Information_block *info
443);
444
445/**
446 * @brief Returns information about free blocks for the heap @a heap in
447 * @a info.
448 */
449void _Heap_Get_free_information(
450  Heap_Control *heap,
451  Heap_Information *info
452);
453
454/**
455 * @brief Returns the size of the allocatable memory area starting at @a addr
456 * in @a size.
457 *
458 * The size value may be greater than the initially requested size in
459 * _Heap_Allocate_aligned_with_boundary().
460 *
461 * Inappropriate values for @a addr will not corrupt the heap, but may yield
462 * invalid size values.
463 *
464 * Returns @a true if successful, and @c false otherwise.
465 */
466bool _Heap_Size_of_alloc_area(
467  Heap_Control *heap,
468  void *addr,
469  uintptr_t *size
470);
471
472/**
473 * @brief Resizes the block of the allocated memory area starting at @a addr.
474 *
475 * The new memory area will have a size of at least @a size bytes.  A resize
476 * may be impossible and depends on the current heap usage.
477 *
478 * The size available for allocation in the current block before the resize
479 * will be returned in @a old_size.  The size available for allocation in
480 * the resized block will be returned in @a new_size.  If the resize was not
481 * successful, then a value of zero will be returned in @a new_size.
482 *
483 * Inappropriate values for @a addr may corrupt the heap.
484 */
485Heap_Resize_status _Heap_Resize_block(
486  Heap_Control *heap,
487  void *addr,
488  uintptr_t size,
489  uintptr_t *old_size,
490  uintptr_t *new_size
491);
492
493#if !defined(__RTEMS_APPLICATION__)
494
495#include <rtems/score/heap.inl>
496
497/**
498 * @brief Allocates the memory area starting at @a alloc_begin of size
499 * @a alloc_size bytes in the block @a block.
500 *
501 * The block may be split up into multiple blocks.  The previous and next block
502 * may be used or free.  Free block parts which form a vaild new block will be
503 * inserted into the free list or merged with an adjacent free block.  If the
504 * block is used, they will be inserted after the free list head.  If the block
505 * is free, they will be inserted after the previous block in the free list.
506 *
507 * Inappropriate values for @a alloc_begin or @a alloc_size may corrupt the
508 * heap.
509 *
510 * Returns the block containing the allocated memory area.
511 */
512Heap_Block *_Heap_Block_allocate(
513  Heap_Control *heap,
514  Heap_Block *block,
515  uintptr_t alloc_begin,
516  uintptr_t alloc_size
517);
518
519/** @} */
520
521#ifdef RTEMS_DEBUG
522  #define RTEMS_HEAP_DEBUG
523  #define RTEMS_MALLOC_BOUNDARY_HELPERS
524#endif
525
526#ifdef RTEMS_HEAP_DEBUG
527  #include <assert.h>
528  #define _HAssert( cond ) \
529    do { \
530      if ( !(cond) ) { \
531        __assert( __FILE__, __LINE__, #cond ); \
532      } \
533    } while (0)
534#else
535  #define _HAssert( cond ) ((void) 0)
536#endif
537
538#endif /* !defined(__RTEMS_APPLICATION__) */
539
540#ifdef __cplusplus
541}
542#endif
543
544#endif
545/* end of include file */
Note: See TracBrowser for help on using the repository browser.