source: rtems/c/src/exec/score/include/rtems/score/heap.h @ 91a3554d

4.104.114.84.95
Last change on this file since 91a3554d was 91a3554d, checked in by Joel Sherrill <joel.sherrill@…>, on 09/19/95 at 21:43:12

Modifications from Tony Bennett accepted to return aligned block.

  • Property mode set to 100644
File size: 9.1 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/*PAGE
282 *
283 *  _Heap_User_Block_at
284 *
285 */
286
287STATIC INLINE Heap_Block *_Heap_User_Block_at(
288  void       *base
289);
290
291/*
292 *  _Heap_Is_previous_block_free
293 *
294 *  DESCRIPTION:
295 *
296 *  This function returns TRUE if the previous block of the_block
297 *  is free, and FALSE otherwise.
298 */
299
300STATIC INLINE boolean _Heap_Is_previous_block_free (
301  Heap_Block *the_block
302);
303
304/*
305 *  _Heap_Is_block_free
306 *
307 *  DESCRIPTION:
308 *
309 *  This function returns TRUE if the block is free, and FALSE otherwise.
310 */
311
312STATIC INLINE boolean _Heap_Is_block_free (
313  Heap_Block *the_block
314);
315
316/*
317 *  _Heap_Is_block_used
318 *
319 *  DESCRIPTION:
320 *
321 *  This function returns TRUE if the block is currently allocated,
322 *  and FALSE otherwise.
323 */
324
325STATIC INLINE boolean _Heap_Is_block_used (
326  Heap_Block *the_block
327);
328
329/*
330 *  _Heap_Block_size
331 *
332 *  DESCRIPTION:
333 *
334 *  This function returns the size of the_block in bytes.
335 */
336
337STATIC INLINE unsigned32 _Heap_Block_size (
338  Heap_Block *the_block
339);
340
341/*
342 *  _Heap_Start_of_user_area
343 *
344 *  DESCRIPTION:
345 *
346 *  This function returns the starting address of the portion of the block
347 *  which the user may access.
348 */
349
350STATIC INLINE void *_Heap_Start_of_user_area (
351  Heap_Block *the_block
352);
353
354/*
355 *  _Heap_Is_block_in
356 *
357 *  DESCRIPTION:
358 *
359 *  This function returns TRUE if the_block is within the memory area
360 *  managed by the_heap, and FALSE otherwise.
361 */
362
363STATIC INLINE boolean _Heap_Is_block_in (
364  Heap_Control *the_heap,
365  Heap_Block   *the_block
366);
367
368
369/*
370 *  _Heap_Is_page_size_valid
371 *
372 *  DESCRIPTION:
373 *
374 *  This function validates a specified heap page size.  If the page size
375 *  is 0 or if lies outside a page size alignment boundary it is invalid
376 *  and FALSE is returned.  Otherwise, the page size is valid and TRUE is
377 *  returned.
378 */
379
380STATIC INLINE boolean _Heap_Is_page_size_valid(
381  unsigned32 page_size
382);
383
384/*
385 *  _Heap_Build_flag
386 *
387 *  DESCRIPTION:
388 *
389 *  This function returns the block flag composed of size and in_use_flag.
390 *  The flag returned is suitable for use as a back or front flag in a
391 *  heap block.
392 */
393
394STATIC INLINE unsigned32 _Heap_Build_flag (
395  unsigned32 size,
396  unsigned32 in_use_flag
397);
398
399#include <rtems/core/heap.inl>
400
401#ifdef __cplusplus
402}
403#endif
404
405#endif
406/* end of include file */
Note: See TracBrowser for help on using the repository browser.