source: rtems/cpukit/score/include/rtems/score/heap.h @ 962e894f

4.104.114.84.95
Last change on this file since 962e894f was 962e894f, checked in by Joel Sherrill <joel.sherrill@…>, on 01/20/05 at 18:22:29

2005-01-20 Sergei Organov <osv@…>

PR 536/rtems
Heap manager re-implementation to consume less memory and still satisfy
alignment requirements.


  • score/src/heap.c, score/src/heapallocate.c, score/src/heapextend.c, score/src/heapfree.c, score/src/heapgetinfo.c, score/src/heapgetfreeinfo.c, core/src/heapsizeofuserarea.c, score/src/heapwalk.c, core/macros/rtems/score/heap.inl, score/inline/rtems/score/heap.inl, score/include/rtems/score/heap.h: Reimplemented.
  • score/src/heapallocatealigned.c: new file
  • score/Makefile.am: HEAP_C_FILES: add score/src/heapallocatealigned.c
  • Property mode set to 100644
File size: 13.6 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-2004.
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_HEAP_h
32#define __RTEMS_HEAP_h
33
34/**
35 *  @defgroup ScoreHeap Heap Handler
36 *
37 *  This group contains 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 unsigned long int _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} Heap_Statistics;
169
170/**
171 *  Control block used to manage each heap.
172 */
173typedef struct {
174  /** head and tail of circular list of free blocks */
175  Heap_Block  free_list;
176  /** allocation unit and alignment */
177  uint32_t  page_size;
178  /** minimum block size aligned on page_size */
179  uint32_t  min_block_size;
180  /** first address of memory for the heap */
181  void       *begin;
182  /** first address past end of memory for the heap */
183  void       *end;
184  /** first valid block address in the heap */
185  Heap_Block *start;
186  /** last valid block address in the heap */
187  Heap_Block *final;
188  /** run-time statistics */
189  Heap_Statistics stats;
190} Heap_Control;
191
192/**
193 *  Status codes for heap_extend
194 */
195
196typedef enum {
197  HEAP_EXTEND_SUCCESSFUL,
198  HEAP_EXTEND_ERROR,
199  HEAP_EXTEND_NOT_IMPLEMENTED
200} Heap_Extend_status;
201
202/**
203 *  Status codes for _Heap_Get_information
204 */
205
206typedef enum {
207  HEAP_GET_INFORMATION_SUCCESSFUL = 0,
208  HEAP_GET_INFORMATION_BLOCK_ERROR
209} Heap_Get_information_status;
210
211/**
212 *  Information block returned by the Heap routines used to
213 *  obtain heap information.  This information is returned about
214 *  either free or used blocks.
215 */
216typedef struct {
217  /** Number of blocks of this type. */
218  uint32_t number;
219  /** Largest blocks of this type. */
220  uint32_t largest;
221  /** Total size of the blocks of this type. */
222  uint32_t total;
223} Heap_Information;
224
225/**
226 *  Information block returned by _Heap_Get_information
227 */
228typedef struct {
229  /** This field is information on the used blocks in the heap. */
230  Heap_Information Free;
231  /** This field is information on the used blocks in the heap. */
232  Heap_Information Used;
233} Heap_Information_block;
234
235/**
236 *  This routine initializes @a the_heap record to manage the
237 *  contiguous heap of @a size bytes which starts at @a starting_address.
238 *  Blocks of memory are allocated from the heap in multiples of
239 *  @a page_size byte units. If @a page_size is 0 or is not multiple of
240 *  CPU_ALIGNMENT, it's aligned up to the nearest CPU_ALIGNMENT boundary.
241 *
242 *  @param the_heap (in) is the heap to operate upon
243 *  @param starting_address (in) is the starting address of the memory for
244 *         the heap
245 *  @param size (in) is the size in bytes of the memory area for the heap
246 *  @param page_size (in) is the size in bytes of the allocation unit
247 *  @return XXX
248 */
249uint32_t   _Heap_Initialize(
250  Heap_Control *the_heap,
251  void         *starting_address,
252  uint32_t      size,
253  uint32_t      page_size
254);
255
256/**
257 *  This routine grows @a the_heap memory area using the size bytes which
258 *  begin at @a starting_address.
259 *
260 *  @param the_heap (in) is the heap to operate upon
261 *  @param starting_address (in) is the starting address of the memory
262 *         to add to the heap
263 *  @param size (in) is the size in bytes of the memory area to add
264 *  @param amount_extended (in) points to a user area to return the
265 *  @return a status indicating success or the reason for failure
266 *  @return *size filled in with the amount of memory added to the heap
267 */
268Heap_Extend_status _Heap_Extend(
269  Heap_Control *the_heap,
270  void         *starting_address,
271  uint32_t      size,
272  uint32_t     *amount_extended
273);
274
275/**
276 *  This function attempts to allocate a block of @a size bytes from
277 *  @a the_heap.  If insufficient memory is free in @a the_heap to allocate
278 *  a block of the requested size, then NULL is returned.
279 *
280 *  @param the_heap (in) is the heap to operate upon
281 *  @param size (in) is the amount of memory to allocate in bytes
282 *  @return NULL if unsuccessful and a pointer to the block if successful
283 */
284void *_Heap_Allocate(
285  Heap_Control *the_heap,
286  uint32_t    size
287);
288
289/**
290 *  This function attempts to allocate a memory block of @a size bytes from
291 *  @a the_heap so that the start of the user memory is aligned on the
292 *  @a alignment boundary. If @a alignment is 0, it is set to CPU_ALIGNMENT.
293 *  Any other value of @a alignment is taken "as is", i.e., even odd
294 *  alignments are possible.
295 *  Returns pointer to the start of the memory block if success, NULL if
296 *  failure.
297 *
298 *  @param the_heap (in) is the heap to operate upon
299 *  @param size (in) is the amount of memory to allocate in bytes
300 *  @param alignment (in) the required alignment
301 *  @return NULL if unsuccessful and a pointer to the block if successful
302 */
303void *_Heap_Allocate_aligned(
304  Heap_Control *the_heap,
305  uint32_t    size,
306  uint32_t    alignment
307);
308
309/**
310 *  This function sets @a *size to the size of the block of user memory
311 *  which begins at @a starting_address. The size returned in @a *size could
312 *  be greater than the size requested for allocation.
313 *  Returns TRUE if the @a starting_address is in the heap, and FALSE
314 *  otherwise.
315 *
316 *  @param the_heap (in) is the heap to operate upon
317 *  @param starting_address (in) is the starting address of the user block
318 *         to obtain the size of
319 *  @param size (in) points to a user area to return the size in
320 *  @return TRUE if successfully able to determine the size, FALSE otherwise
321 *  @return *size filled in with the size of the user area for this block
322 */
323boolean _Heap_Size_of_user_area(
324  Heap_Control        *the_heap,
325  void                *starting_address,
326  size_t              *size
327);
328
329/**
330 *  This routine returns the block of memory which begins
331 *  at @a starting_address to @a the_heap.  Any coalescing which is
332 *  possible with the freeing of this routine is performed.
333 *
334 *  @param the_heap (in) is the heap to operate upon
335 *  @param starting_address (in) is the starting address of the user block
336 *         to free
337 *  @return TRUE if successfully freed, FALSE otherwise
338 */
339boolean _Heap_Free(
340  Heap_Control *the_heap,
341  void         *start_address
342);
343
344/**
345 *  This routine walks the heap to verify its integrity.
346 *
347 *  @param the_heap (in) is the heap to operate upon
348 *  @param source (in) XXX
349 *  @param do_dump (in) is set to TRUE if errors should be printed
350 *  @return TRUE if the test passed fine, FALSE otherwise.
351 */
352
353boolean _Heap_Walk(
354  Heap_Control *the_heap,
355  int           source,
356  boolean       do_dump
357);
358
359/**
360 *  This routine walks the heap and tots up the free and allocated
361 *  sizes.
362 *
363 *  @param the_heap (in) pointer to heap header
364 *  @param the_info (in) pointer to a status information area
365 *  @return *the_info is filled with status information
366 *  @return 0=success, otherwise heap is corrupt.
367 */
368Heap_Get_information_status _Heap_Get_information(
369  Heap_Control            *the_heap,
370  Heap_Information_block  *the_info
371);
372
373/**
374 *  This heap routine returns information about the free blocks
375 *  in the specified heap.
376 *
377 *  @param the_heap (in) pointer to heap header.
378 *  @param info (in) pointer to the free block information.
379 *
380 *  @return free block information filled in.
381 */
382
383void _Heap_Get_free_information(
384  Heap_Control        *the_heap,
385  Heap_Information    *info
386);
387
388#if !defined(__RTEMS_APPLICATION__)
389
390/*
391 *  A pointer to unsigned integer conversion.
392 */
393#define _H_p2u(_p) ((_H_uptr_t)(_p))
394
395#include <rtems/score/heap.inl>
396
397/*
398 *  Internal routines shared by _Heap_Allocate() and _Heap_Allocate_aligned().
399 *  Refer to 'heap.c' for details.
400 */
401
402extern uint32_t _Heap_Calc_block_size(
403  uint32_t size,
404  uint32_t page_size,
405  uint32_t min_size);
406
407extern Heap_Block* _Heap_Block_allocate(
408  Heap_Control* the_heap,
409  Heap_Block* the_block,
410  uint32_t alloc_size);
411
412/*
413 * Debug support
414 */
415
416#if defined(RTEMS_DEBUG)
417#define RTEMS_HEAP_DEBUG
418#endif
419
420#if defined(RTEMS_HEAP_DEBUG)
421
422#include <assert.h>
423
424/*
425 *  We do asserts only for heaps with instance number greater than 0 assuming
426 *  that the heap used for malloc is initialized first and thus has instance
427 *  number 0. Asserting malloc heap may lead to troubles as printf may invoke
428 *  malloc thus probably leading to infinite recursion.
429 */
430
431#define _HAssert(cond_) \
432  do { \
433    if(the_heap->stats.instance && !(cond_)) \
434      __assert(__FILE__, __LINE__, #cond_);  \
435  } while(0)
436
437#else  /* !defined(RTEMS_HEAP_DEBUG) */
438
439#define _HAssert(cond_) ((void)0)
440
441#endif /* !defined(RTEMS_HEAP_DEBUG) */
442
443#endif /* !defined(__RTEMS_APPLICATION__) */
444
445#ifdef __cplusplus
446}
447#endif
448
449/**@}*/
450
451#endif
452/* end of include file */
Note: See TracBrowser for help on using the repository browser.