source: rtems/cpukit/score/include/rtems/score/heap.h @ 6a07436

4.104.114.84.9
Last change on this file since 6a07436 was 6a07436, checked in by Joel Sherrill <joel.sherrill@…>, on Jan 16, 2006 at 3:13:58 PM

2006-01-16 Joel Sherrill <joel@…>

Large patch to improve Doxygen output. As a side-effect, grammar and
spelling errors were corrected, spacing errors were address, and some
variable names were improved.

  • libmisc/monitor/mon-object.c, libmisc/monitor/monitor.h: Account for changing OBJECTS_NO_CLASS to OBJECTS_CLASSIC_NO_CLASS.
  • score/Doxyfile: Set output directory. Predefine some macro values. Turn on graphical output.
  • score/include/rtems/debug.h, score/include/rtems/seterr.h, score/include/rtems/system.h, score/include/rtems/score/address.h, score/include/rtems/score/apiext.h, score/include/rtems/score/apimutex.h, score/include/rtems/score/bitfield.h, score/include/rtems/score/chain.h, score/include/rtems/score/context.h, score/include/rtems/score/coremsg.h, score/include/rtems/score/coremutex.h, score/include/rtems/score/coresem.h, score/include/rtems/score/heap.h, score/include/rtems/score/interr.h, score/include/rtems/score/isr.h, score/include/rtems/score/mpci.h, score/include/rtems/score/mppkt.h, score/include/rtems/score/object.h, score/include/rtems/score/objectmp.h, score/include/rtems/score/priority.h, score/include/rtems/score/stack.h, score/include/rtems/score/states.h, score/include/rtems/score/sysstate.h, score/include/rtems/score/thread.h, score/include/rtems/score/threadmp.h, score/include/rtems/score/threadq.h, score/include/rtems/score/tod.h, score/include/rtems/score/tqdata.h, score/include/rtems/score/userext.h, score/include/rtems/score/watchdog.h, score/include/rtems/score/wkspace.h, score/inline/rtems/score/address.inl, score/inline/rtems/score/chain.inl, score/inline/rtems/score/coremutex.inl, score/inline/rtems/score/coresem.inl, score/inline/rtems/score/heap.inl, score/inline/rtems/score/object.inl, score/inline/rtems/score/stack.inl, score/inline/rtems/score/thread.inl, score/inline/rtems/score/tqdata.inl, score/macros/README, score/src/heap.c, score/src/threadmp.c, score/src/threadready.c, score/src/threadstartmultitasking.c: Improve generated Doxygen output. Fix spelling and grammar errors in comments. Correct names of some variables and propagate changes.
  • Property mode set to 100644
File size: 16.4 KB
Line 
1/**
2 *  @file  rtems/score/heap.h
3 *
4 *  This include file contains the information pertaining to the Heap
5 *  Handler.  A heap is a doubly linked list of variable size
6 *  blocks which are allocated using the first fit method.  Garbage
7 *  collection is performed each time a block is returned to the heap by
8 *  coalescing neighbor blocks.  Control information for both allocated
9 *  and unallocated blocks is contained in the heap space.  A heap control
10 *  structure contains control information for the heap.
11 *
12 *  FIXME: the alignment routines could be made faster should we require only
13 *         powers of two to be supported both for 'page_size' and for
14 *         'alignment' arguments. However, both workspace and malloc heaps are
15 *         initialized with CPU_HEAP_ALIGNMENT as 'page_size', and while all
16 *         the BSPs seem to use CPU_ALIGNMENT (that is power of two) as
17 *         CPU_HEAP_ALIGNMENT, for whatever reason CPU_HEAP_ALIGNMENT is only
18 *         required to be multiple of CPU_ALIGNMENT and explicitly not
19 *         required to be a power of two.
20 *
21 *  COPYRIGHT (c) 1989-2006.
22 *  On-Line Applications Research Corporation (OAR).
23 *
24 *  The license and distribution terms for this file may be
25 *  found in the file LICENSE in this distribution or at
26 *  http://www.rtems.com/license/LICENSE.
27 *
28 *  $Id$
29 */
30
31#ifndef _RTEMS_SCORE_HEAP_H
32#define _RTEMS_SCORE_HEAP_H
33
34/**
35 *  @defgroup ScoreHeap Heap Handler
36 *
37 *  This handler encapsulates functionality which provides the foundation
38 *  Heap services used in all of the APIs supported by RTEMS.
39 */
40/**@{*/
41
42#ifdef __cplusplus
43extern "C" {
44#endif
45
46/**
47 * This type defines unsigned integer type to store 'void*'. Analog of C99
48 * 'uintptr_t'. This should work on 16/32/64 bit architectures.
49 *
50 * FIXME: Something like this should better be defined by
51 *        'rtems/score/types.h' and used here.
52 */
53
54typedef uintptr_t _H_uptr_t;
55
56/**
57 *  Forward reference
58 *
59 *  @ref Heap_Block
60 */
61typedef struct Heap_Block_struct Heap_Block;
62
63/**
64 *  The following defines the data structure used to manage individual blocks
65 *  in a heap.  When the block is allocated, the 'next' and 'prev' fields, as
66 *  well as 'prev_size' field of the next block, are not used by the heap
67 *  manager and thus the address returned for the block starts at the address
68 *  of the 'next' field and the size of the user accessible area includes the
69 *  size of the 'prev_size' field.
70 *
71 *  @note The 'next' and 'prev' pointers are only valid when the block is free.
72 *     Caution must be taken to ensure that every block is large enough to
73 *     hold them and that they are not accessed while the block is actually
74 *     allocated (i.e., not free).
75 *
76 *  @note The 'prev_size' field is only valid when HEAP_PREV_USED bit is clear
77 *     in the 'size' field indicating that previous block is not allocated.
78 *     If the bit is set, the 'prev_size' field is part of user-accessible
79 *     space of the previous allocated block and thus shouldn't be accessed
80 *     by the heap manager code. This trick allows to further decrease
81 *     overhead in the used blocks to the size of 'size' field (4 bytes).
82 *
83 */
84
85struct Heap_Block_struct {
86  /** size of prev block (if prev block is free) */
87  uint32_t  prev_size;
88  /** size of block in bytes and status of prev block */
89  uint32_t  size;
90  /** pointer to the next free block */
91  Heap_Block *next;
92  /** pointer to the previous free block */
93  Heap_Block *prev;
94};
95
96/**
97 *  This flag used in the 'size' field of each heap block to indicate
98 *  if previous block is free or in use. As sizes are always multiples of
99 *  4, the 2 least significant bits would always be 0, and we use one of them
100 *  to store the flag.
101 */
102
103#define HEAP_PREV_USED    1     /* indicates previous block is in use */
104
105/**
106 *  The following constants reflect various requirements of the
107 *  heap data structures which impact the management of a heap.
108 */
109
110#define HEAP_MIN_BLOCK_SIZE (sizeof(Heap_Block))
111
112/**
113 *  Offset of the block header from the block pointer. Equal to the
114 *  offsetof(Heap_Block.size).
115 */
116#define HEAP_BLOCK_HEADER_OFFSET (sizeof(uint32_t))
117
118/**
119 *  Offset of user data pointer from the block pointer. Equal to the
120 *  offsetof(Heap_Block.next).
121 */
122#define HEAP_BLOCK_USER_OFFSET (sizeof(uint32_t) * 2)
123
124/**
125 *  Num bytes of overhead in used block. Equal to the sizeof(Heap_Block.size).
126 */
127#define HEAP_BLOCK_USED_OVERHEAD \
128  (HEAP_BLOCK_USER_OFFSET - HEAP_BLOCK_HEADER_OFFSET)
129
130/** Size of the permanent dummy last block. */
131#define HEAP_OVERHEAD HEAP_BLOCK_USER_OFFSET
132
133/**
134 *  Run-time heap statistics.
135 *
136 *  @note (double)searches/allocs gives mean number of searches per alloc while
137 *        max_search gives maximum number of searches ever performed on a
138 *        single call to alloc.
139 *
140 *  @note the statistics is always gathered. I believe the imposed overhead is
141 *        rather small. Feel free to make it compile-time option if you think
142 *        the overhead is too high for your application.
143 */
144
145typedef struct Heap_Statistics_tag {
146  /** instance number of this heap */
147  uint32_t instance;
148  /** the size of the memory for heap */
149  uint32_t size;
150  /** current free size */
151  uint32_t free_size;
152  /** minimum free size ever */
153  uint32_t min_free_size;
154  /** current number of free blocks */
155  uint32_t free_blocks;
156  /** maximum number of free blocks ever */
157  uint32_t max_free_blocks;
158  /** current number of used blocks */
159  uint32_t used_blocks;
160  /** maximum number of blocks searched ever */
161  uint32_t max_search;
162  /** total number of successful calls to alloc */
163  uint32_t allocs;
164  /** total number of searches ever */
165  uint32_t searches;
166  /** total number of suceessful calls to free */
167  uint32_t frees;
168  /** total number of successful resizes */
169  uint32_t resizes;
170} Heap_Statistics;
171
172/**
173 *  Control block used to manage each heap.
174 */
175typedef struct {
176  /** head and tail of circular list of free blocks */
177  Heap_Block  free_list;
178  /** allocation unit and alignment */
179  uint32_t  page_size;
180  /** minimum block size aligned on page_size */
181  uint32_t  min_block_size;
182  /** first address of memory for the heap */
183  void       *begin;
184  /** first address past end of memory for the heap */
185  void       *end;
186  /** first valid block address in the heap */
187  Heap_Block *start;
188  /** last valid block address in the heap */
189  Heap_Block *final;
190  /** run-time statistics */
191  Heap_Statistics stats;
192} Heap_Control;
193
194/**
195 *  Status codes for _Heap_Extend
196 */
197
198typedef enum {
199  HEAP_EXTEND_SUCCESSFUL,
200  HEAP_EXTEND_ERROR,
201  HEAP_EXTEND_NOT_IMPLEMENTED
202} Heap_Extend_status;
203
204/**
205 *  Status codes for _Heap_Resize_block
206 */
207
208typedef enum {
209  HEAP_RESIZE_SUCCESSFUL,
210  HEAP_RESIZE_UNSATISFIED,
211  HEAP_RESIZE_FATAL_ERROR
212} Heap_Resize_status;
213
214/**
215 *  Status codes for _Heap_Get_information
216 */
217
218typedef enum {
219  HEAP_GET_INFORMATION_SUCCESSFUL = 0,
220  HEAP_GET_INFORMATION_BLOCK_ERROR
221} Heap_Get_information_status;
222
223/**
224 *  Information block returned by the Heap routines used to
225 *  obtain heap information.  This information is returned about
226 *  either free or used blocks.
227 */
228typedef struct {
229  /** Number of blocks of this type. */
230  uint32_t number;
231  /** Largest blocks of this type. */
232  uint32_t largest;
233  /** Total size of the blocks of this type. */
234  uint32_t total;
235} Heap_Information;
236
237/**
238 *  Information block returned by _Heap_Get_information
239 */
240typedef struct {
241  /** This field is information on the used blocks in the heap. */
242  Heap_Information Free;
243  /** This field is information on the used blocks in the heap. */
244  Heap_Information Used;
245} Heap_Information_block;
246
247/**
248 *  This routine initializes @a the_heap record to manage the
249 *  contiguous heap of @a size bytes which starts at @a starting_address.
250 *  Blocks of memory are allocated from the heap in multiples of
251 *  @a page_size byte units. If @a page_size is 0 or is not multiple of
252 *  CPU_ALIGNMENT, it's aligned up to the nearest CPU_ALIGNMENT boundary.
253 *
254 *  @param[in] the_heap is the heap to operate upon
255 *  @param[in] starting_address is the starting address of the memory for
256 *         the heap
257 *  @param[in] size is the size in bytes of the memory area for the heap
258 *  @param[in] page_size is the size in bytes of the allocation unit
259 *
260 *  @return This method returns the maximum memory available.  If
261 *          unsuccessful, 0 will be returned.
262 */
263uint32_t   _Heap_Initialize(
264  Heap_Control *the_heap,
265  void         *starting_address,
266  uint32_t      size,
267  uint32_t      page_size
268);
269
270/**
271 *  This routine grows @a the_heap memory area using the size bytes which
272 *  begin at @a starting_address.
273 *
274 *  @param[in] the_heap is the heap to operate upon
275 *  @param[in] starting_address is the starting address of the memory
276 *         to add to the heap
277 *  @param[in] size is the size in bytes of the memory area to add
278 *  @param[in] amount_extended points to a user area to return the
279 *  @return a status indicating success or the reason for failure
280 *  @return *size filled in with the amount of memory added to the heap
281 */
282Heap_Extend_status _Heap_Extend(
283  Heap_Control *the_heap,
284  void         *starting_address,
285  uint32_t      size,
286  uint32_t     *amount_extended
287);
288
289/**
290 *  This function attempts to allocate a block of @a size bytes from
291 *  @a the_heap.  If insufficient memory is free in @a the_heap to allocate
292 *  a block of the requested size, then NULL is returned.
293 *
294 *  @param[in] the_heap is the heap to operate upon
295 *  @param[in] size is the amount of memory to allocate in bytes
296 *  @return NULL if unsuccessful and a pointer to the block if successful
297 */
298void *_Heap_Allocate(
299  Heap_Control *the_heap,
300  uint32_t    size
301);
302
303/**
304 *  This function attempts to allocate a memory block of @a size bytes from
305 *  @a the_heap so that the start of the user memory is aligned on the
306 *  @a alignment boundary. If @a alignment is 0, it is set to CPU_ALIGNMENT.
307 *  Any other value of @a alignment is taken "as is", i.e., even odd
308 *  alignments are possible.
309 *  Returns pointer to the start of the memory block if success, NULL if
310 *  failure.
311 *
312 *  @param[in] the_heap is the heap to operate upon
313 *  @param[in] size is the amount of memory to allocate in bytes
314 *  @param[in] alignment the required alignment
315 *  @return NULL if unsuccessful and a pointer to the block if successful
316 */
317void *_Heap_Allocate_aligned(
318  Heap_Control *the_heap,
319  uint32_t    size,
320  uint32_t    alignment
321);
322
323/**
324 *  This function sets @a *size to the size of the block of user memory
325 *  which begins at @a starting_address. The size returned in @a *size could
326 *  be greater than the size requested for allocation.
327 *  Returns TRUE if the @a starting_address is in the heap, and FALSE
328 *  otherwise.
329 *
330 *  @param[in] the_heap is the heap to operate upon
331 *  @param[in] starting_address is the starting address of the user block
332 *         to obtain the size of
333 *  @param[in] size points to a user area to return the size in
334 *  @return TRUE if successfully able to determine the size, FALSE otherwise
335 *  @return *size filled in with the size of the user area for this block
336 */
337boolean _Heap_Size_of_user_area(
338  Heap_Control        *the_heap,
339  void                *starting_address,
340  size_t              *size
341);
342
343/**
344 *  This function tries to resize in place the block that is pointed to by the
345 *  @a starting_address to the new @a size.
346 *
347 *  @param[in] the_heap is the heap to operate upon
348 *  @param[in] starting_address is the starting address of the user block
349 *         to be resized
350 *  @param[in] size is the new size
351 *  @param[in] old_mem_size points to a user area to return the size of the
352 *         user memory area of the block before resizing.
353 *  @param[in] avail_mem_size points to a user area to return the size of
354 *         the user memory area of the free block that has been enlarged or
355 *         created due to resizing, 0 if none.
356 *  @return HEAP_RESIZE_SUCCESSFUL if successfully able to resize the block,
357 *          HEAP_RESIZE_UNSATISFIED if the block can't be resized in place,
358 *          HEAP_RESIZE_FATAL_ERROR if failure
359 *  @return *old_mem_size filled in with the size of the user memory area of
360 *          the block before resizing.
361 *  @return *avail_mem_size filled in with the size of the user memory area
362 *          of the free block that has been enlarged or created due to
363 *          resizing, 0 if none.
364 */
365Heap_Resize_status _Heap_Resize_block(
366  Heap_Control *the_heap,
367  void         *starting_address,
368  uint32_t     size,
369  uint32_t     *old_mem_size,
370  uint32_t     *avail_mem_size
371);
372
373/**
374 *  This routine returns the block of memory which begins
375 *  at @a starting_address to @a the_heap.  Any coalescing which is
376 *  possible with the freeing of this routine is performed.
377 *
378 *  @param[in] the_heap is the heap to operate upon
379 *  @param[in] start_address is the starting address of the user block
380 *         to free
381 *  @return TRUE if successfully freed, FALSE otherwise
382 */
383boolean _Heap_Free(
384  Heap_Control *the_heap,
385  void         *start_address
386);
387
388/**
389 *  This routine walks the heap to verify its integrity.
390 *
391 *  @param[in] the_heap is the heap to operate upon
392 *  @param[in] source is a user specified integer which may be used to
393 *         indicate where in the application this was invoked from
394 *  @param[in] do_dump is set to TRUE if errors should be printed
395 *  @return TRUE if the test passed fine, FALSE otherwise.
396 */
397boolean _Heap_Walk(
398  Heap_Control *the_heap,
399  int           source,
400  boolean       do_dump
401);
402
403/**
404 *  This routine walks the heap and tots up the free and allocated
405 *  sizes.
406 *
407 *  @param[in] the_heap pointer to heap header
408 *  @param[in] the_info pointer to a status information area
409 *  @return *the_info is filled with status information
410 *  @return 0=success, otherwise heap is corrupt.
411 */
412Heap_Get_information_status _Heap_Get_information(
413  Heap_Control            *the_heap,
414  Heap_Information_block  *the_info
415);
416
417/**
418 *  This heap routine returns information about the free blocks
419 *  in the specified heap.
420 *
421 *  @param[in] the_heap pointer to heap header.
422 *  @param[in] info pointer to the free block information.
423 *
424 *  @return free block information filled in.
425 */
426void _Heap_Get_free_information(
427  Heap_Control        *the_heap,
428  Heap_Information    *info
429);
430
431#if !defined(__RTEMS_APPLICATION__)
432
433/**
434 *  A pointer to unsigned integer conversion.
435 */
436#define _H_p2u(_p) ((_H_uptr_t)(_p))
437
438#include <rtems/score/heap.inl>
439
440/**
441 *  Convert user requested 'size' of memory block to the block size.
442 *
443 *  @note This is an internal routine used by _Heap_Allocate() and
444 *  _Heap_Allocate_aligned().  Refer to 'heap.c' for details.
445 *
446 *  @param[in] size is the size of the block requested
447 *  @param[in] page_size is the page size of this heap instance
448 *  @param[in] min_size is minimum size block that should be allocated
449 *         from this heap instance
450 *
451 *  @return This method returns block size on success, 0 if overflow occured.
452 */
453extern uint32_t _Heap_Calc_block_size(
454  uint32_t size,
455  uint32_t page_size,
456  uint32_t min_size
457);
458
459/**
460 *  This method allocates a block of size @a alloc_size from @a the_block
461 *  belonging to @a the_heap. Split @a the_block if possible, otherwise
462 *  allocate it entirely.  When split, make the lower part used, and leave
463 *  the upper part free.
464 *
465 *  This is an internal routines used by _Heap_Allocate() and
466 *  _Heap_Allocate_aligned().  Refer to 'heap.c' for details.
467 *
468 *  @param[in] the_heap is the heap to operate upon
469 *  @param[in] the_block is the block to allocates the requested size from
470 *  @param[in] alloc_size is the requested number of bytes to take out of
471 *         the block
472 *
473 *  @return This methods returns the size of the allocated block.
474 */
475extern uint32_t _Heap_Block_allocate(
476  Heap_Control* the_heap,
477  Heap_Block*   the_block,
478  uint32_t      alloc_size
479);
480
481/*
482 * Debug support
483 */
484
485#if defined(RTEMS_DEBUG)
486#define RTEMS_HEAP_DEBUG
487#endif
488
489/**
490 *  We do asserts only for heaps with instance number greater than 0 assuming
491 *  that the heap used for malloc is initialized first and thus has instance
492 *  number 0. Asserting malloc heap may lead to troubles as printf may invoke
493 *  malloc thus probably leading to infinite recursion.
494 */
495#if defined(RTEMS_HEAP_DEBUG)
496#include <assert.h>
497
498#define _HAssert(cond_) \
499  do { \
500    if(the_heap->stats.instance && !(cond_)) \
501      __assert(__FILE__, __LINE__, #cond_);  \
502  } while(0)
503
504#else  /* !defined(RTEMS_HEAP_DEBUG) */
505
506#define _HAssert(cond_) ((void)0)
507
508#endif /* !defined(RTEMS_HEAP_DEBUG) */
509
510#endif /* !defined(__RTEMS_APPLICATION__) */
511
512#ifdef __cplusplus
513}
514#endif
515
516/**@}*/
517
518#endif
519/* end of include file */
Note: See TracBrowser for help on using the repository browser.