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

4.104.114.84.95
Last change on this file since ac7d5ef0 was ac7d5ef0, checked in by Joel Sherrill <joel.sherrill@…>, on May 11, 1995 at 5:39:37 PM

Initial revision

  • Property mode set to 100644
File size: 9.0 KB
Line 
1/*  heap.h
2 *
3 *  This include file contains the information pertaining to the Heap
4 *  Handler.  A heap is a doubly linked list of variable size
5 *  blocks which are allocated using the first fit method.  Garbage
6 *  collection is performed each time a block is returned to the heap by
7 *  coalescing neighbor blocks.  Control information for both allocated
8 *  and unallocated blocks is contained in the heap space.  A heap header
9 *  contains control information for the heap.
10 *
11 *  COPYRIGHT (c) 1989, 1990, 1991, 1992, 1993, 1994.
12 *  On-Line Applications Research Corporation (OAR).
13 *  All rights assigned to U.S. Government, 1994.
14 *
15 *  This material may be reproduced by or for the U.S. Government pursuant
16 *  to the copyright license under the clause at DFARS 252.227-7013.  This
17 *  notice must appear in all copies of this file and its derivatives.
18 *
19 *  $Id$
20 */
21
22#ifndef __RTEMS_HEAP_h
23#define __RTEMS_HEAP_h
24
25#ifdef __cplusplus
26extern "C" {
27#endif
28
29/*
30 *  Status codes for heap_extend
31 */
32
33typedef enum {
34  HEAP_EXTEND_SUCCESSFUL,
35  HEAP_EXTEND_ERROR,
36  HEAP_EXTEND_NOT_IMPLEMENTED
37}  Heap_Extend_status;
38
39/*
40 *  Constants used in the size/used field of each heap block to
41 *  indicate when a block is free or in use.
42 */
43
44#define HEAP_BLOCK_USED    1           /* indicates block is in use */
45#define HEAP_BLOCK_FREE    0           /* indicates block is free */
46
47/*
48 *  The size/used field value for the dummy front and back flags.
49 */
50
51#define HEAP_DUMMY_FLAG    (0 + HEAP_BLOCK_USED)
52
53/*
54 *  The following constants reflect various requirements of the
55 *  heap data structures which impact the management of a heap.
56 *
57 * NOTE:   Because free block overhead is greater than used block
58 *         overhead AND a portion of the allocated space is from
59 *         the extra free block overhead, the absolute lower bound
60 *         of the minimum fragment size is equal to the size of
61 *         the free block overhead.
62 */
63
64#define HEAP_OVERHEAD \
65  (sizeof( unsigned32 ) * 2)         /* size dummy first and last blocks */
66#define HEAP_BLOCK_USED_OVERHEAD \
67  (sizeof( void * ) * 2)             /* num bytes overhead in used block */
68#define HEAP_MINIMUM_SIZE \
69  (HEAP_OVERHEAD + sizeof (Heap_Block))
70                                     /* min number of bytes the user may */
71                                     /*   specify for the heap size      */
72
73/*
74 *  The following defines the data structure used to manage
75 *  individual blocks in a heap.   When the block is allocated, the
76 *  next and previous fields are not used by the Heap Handler
77 *  and thus the address returned for the block starts at
78 *  the address of the next field.
79 *
80 *  NOTE:  The next and previous pointers are only valid when the
81 *         block is free.  Caution must be exercised to insure that
82 *         allocated blocks are large enough to contain them and
83 *         that they are not accidentally overwritten when the
84 *         block is actually allocated.
85 */
86
87typedef struct Heap_Block_struct Heap_Block;
88
89struct Heap_Block_struct {
90  unsigned32  back_flag;   /* size and status of prev block */
91  unsigned32  front_flag;  /* size and status of block */
92  Heap_Block *next;        /* pointer to next block */
93  Heap_Block *previous;    /* pointer to previous block */
94};
95
96/*
97 *  The following defines the control block used to manage each heap.
98 *
99 *  NOTE:
100 *
101 *  This structure is layed out such that it can be used a a dummy
102 *  first and last block on the free block chain.  The extra padding
103 *  insures the dummy last block is the correct size.
104 *
105 *  The first Heap_Block starts at first while the second starts at
106 *  final.  This is effectively the same trick as is used in the Chain
107 *  Handler.
108 */
109
110typedef struct {
111  Heap_Block *start;       /* first valid block address in heap */
112  Heap_Block *final;       /* last valid block address in heap */
113
114  Heap_Block *first;       /* pointer to first block in heap */
115  Heap_Block *permanent_null;  /* always NULL pointer */
116  Heap_Block *last;        /* pointer to last block in heap */
117  unsigned32  page_size;   /* allocation unit */
118  unsigned32  reserved;
119}   Heap_Control;
120
121/*
122 *  _Heap_Initialize
123 *
124 *  DESCRIPTION:
125 *
126 *  This routine initializes the_heap record to manage the
127 *  contiguous heap of size bytes which starts at starting_address.
128 *  Blocks of memory are allocated from the heap in multiples of
129 *  page_size byte units.
130 */
131
132unsigned32 _Heap_Initialize(
133  Heap_Control *the_heap,
134  void         *starting_address,
135  unsigned32    size,
136  unsigned32    page_size
137);
138
139/*
140 *  _Heap_Extend
141 *
142 *  DESCRIPTION:
143 *
144 *  This routine grows the_heap memory area using the size bytes which
145 *  begin at starting_address.
146 */
147
148Heap_Extend_status _Heap_Extend(
149  Heap_Control *the_heap,
150  void         *starting_address,
151  unsigned32    size,
152  unsigned32   *amount_extended
153);
154
155/*
156 *  _Heap_Allocate
157 *
158 *  DESCRIPTION:
159 *
160 *  DESCRIPTION:
161 *
162 *  This function attempts to allocate a block of size bytes from
163 *  the_heap.  If insufficient memory is free in the_heap to allocate
164 *  a  block of the requested size, then NULL is returned.
165 */
166
167void *_Heap_Allocate(
168  Heap_Control *the_heap,
169  unsigned32    size
170);
171
172/*
173 *  _Heap_Size_of_user_area
174 *
175 *  DESCRIPTION:
176 *
177 *  This kernel routine sets size to the size of the given heap block.
178 *  It returns TRUE if the starting_address is in the heap, and FALSE
179 *  otherwise.
180 */
181
182boolean _Heap_Size_of_user_area(
183  Heap_Control        *the_heap,
184  void                *starting_address,
185  unsigned32          *size
186);
187
188/*
189 *  _Heap_Free
190 *
191 *  DESCRIPTION:
192 *
193 *  This routine returns the block of memory which begins
194 *  at starting_address to the_heap.  Any coalescing which is
195 *  possible with the freeing of this routine is performed.
196 */
197
198boolean _Heap_Free(
199  Heap_Control *the_heap,
200  void         *start_address
201);
202
203/*
204 *  _Heap_Walk
205 *
206 *  DESCRIPTION:
207 *
208 *  This routine walks the heap to verify its integrity.
209 */
210
211void _Heap_Walk(
212  Heap_Control *the_heap,
213  int           source,
214  boolean       do_dump
215);
216
217/*
218 *  _Heap_Head
219 *
220 *  DESCRIPTION:
221 *
222 *  This function returns the head of the specified heap.
223 */
224
225STATIC INLINE Heap_Block *_Heap_Head (
226  Heap_Control *the_heap
227);
228
229/*
230 *  _Heap_Tail
231 *
232 *  DESCRIPTION:
233 *
234 *  This function returns the tail of the specified heap.
235 */
236
237STATIC INLINE Heap_Block *_Heap_Tail (
238  Heap_Control *the_heap
239);
240
241/*
242 *  _Heap_Previous_block
243 *
244 *  DESCRIPTION:
245 *
246 *  This function returns the address of the block which physically
247 *  precedes the_block in memory.
248 */
249
250STATIC INLINE Heap_Block *_Heap_Previous_block (
251  Heap_Block *the_block
252);
253
254/*
255 *  _Heap_Next_block
256 *
257 *  DESCRIPTION:
258 *
259 *  This function returns the address of the block which physically
260 *  follows the_block in memory.
261 */
262
263STATIC INLINE Heap_Block *_Heap_Next_block (
264  Heap_Block *the_block
265);
266
267/*
268 *  _Heap_Block_at
269 *
270 *  DESCRIPTION:
271 *
272 *  This function calculates and returns a block's location (address)
273 *  in the heap based upad a base address and an offset.
274 */
275
276STATIC INLINE Heap_Block *_Heap_Block_at(
277  void       *base,
278  unsigned32  offset
279);
280
281/*
282 *  _Heap_Is_previous_block_free
283 *
284 *  DESCRIPTION:
285 *
286 *  This function returns TRUE if the previous block of the_block
287 *  is free, and FALSE otherwise.
288 */
289
290STATIC INLINE boolean _Heap_Is_previous_block_free (
291  Heap_Block *the_block
292);
293
294/*
295 *  _Heap_Is_block_free
296 *
297 *  DESCRIPTION:
298 *
299 *  This function returns TRUE if the block is free, and FALSE otherwise.
300 */
301
302STATIC INLINE boolean _Heap_Is_block_free (
303  Heap_Block *the_block
304);
305
306/*
307 *  _Heap_Is_block_used
308 *
309 *  DESCRIPTION:
310 *
311 *  This function returns TRUE if the block is currently allocated,
312 *  and FALSE otherwise.
313 */
314
315STATIC INLINE boolean _Heap_Is_block_used (
316  Heap_Block *the_block
317);
318
319/*
320 *  _Heap_Block_size
321 *
322 *  DESCRIPTION:
323 *
324 *  This function returns the size of the_block in bytes.
325 */
326
327STATIC INLINE unsigned32 _Heap_Block_size (
328  Heap_Block *the_block
329);
330
331/*
332 *  _Heap_Start_of_user_area
333 *
334 *  DESCRIPTION:
335 *
336 *  This function returns the starting address of the portion of the block
337 *  which the user may access.
338 */
339
340STATIC INLINE void *_Heap_Start_of_user_area (
341  Heap_Block *the_block
342);
343
344/*
345 *  _Heap_Is_block_in
346 *
347 *  DESCRIPTION:
348 *
349 *  This function returns TRUE if the_block is within the memory area
350 *  managed by the_heap, and FALSE otherwise.
351 */
352
353STATIC INLINE boolean _Heap_Is_block_in (
354  Heap_Control *the_heap,
355  Heap_Block   *the_block
356);
357
358
359/*
360 *  _Heap_Is_page_size_valid
361 *
362 *  DESCRIPTION:
363 *
364 *  This function validates a specified heap page size.  If the page size
365 *  is 0 or if lies outside a page size alignment boundary it is invalid
366 *  and FALSE is returned.  Otherwise, the page size is valid and TRUE is
367 *  returned.
368 */
369
370STATIC INLINE boolean _Heap_Is_page_size_valid(
371  unsigned32 page_size
372);
373
374/*
375 *  _Heap_Build_flag
376 *
377 *  DESCRIPTION:
378 *
379 *  This function returns the block flag composed of size and in_use_flag.
380 *  The flag returned is suitable for use as a back or front flag in a
381 *  heap block.
382 */
383
384STATIC INLINE unsigned32 _Heap_Build_flag (
385  unsigned32 size,
386  unsigned32 in_use_flag
387);
388
389#include <rtems/heap.inl>
390
391#ifdef __cplusplus
392}
393#endif
394
395#endif
396/* end of include file */
Note: See TracBrowser for help on using the repository browser.