source: rtems/cpukit/score/include/rtems/score/heap.h @ e89faf3e

4.104.115
Last change on this file since e89faf3e was e89faf3e, checked in by Joel Sherrill <joel.sherrill@…>, on 09/25/09 at 17:49:32

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

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