source: rtems/cpukit/score/src/heap.c @ 3652ad35

4.104.114.84.95
Last change on this file since 3652ad35 was 3a4ae6c, checked in by Joel Sherrill <joel.sherrill@…>, on 09/11/95 at 19:35:39

The word "RTEMS" almost completely removed from the core.

Configuration Table Template file added and all tests
modified to use this. All gvar.h and conftbl.h files
removed from test directories.

Configuration parameter maximum_devices added.

Core semaphore and mutex handlers added and RTEMS API Semaphore
Manager updated to reflect this.

Initialization sequence changed to invoke API specific initialization
routines. Initialization tasks table now owned by RTEMS Tasks Manager.

Added user extension for post-switch.

Utilized user extensions to implement API specific functionality
like signal dispatching.

Added extensions to the System Initialization Thread so that an
API can register a function to be invoked while the system
is being initialized. These are largely equivalent to the
pre-driver and post-driver hooks.

Added the Modules file oar-go32_p5, modified oar-go32, and modified
the file make/custom/go32.cfg to look at an environment varable which
determines what CPU model is being used.

All BSPs updated to reflect named devices and clock driver's IOCTL
used by the Shared Memory Driver. Also merged clock isr into
main file and removed ckisr.c where possible.

Updated spsize to reflect new and moved variables.

Makefiles for the executive source and include files updated to show
break down of files into Core, RTEMS API, and Neither.

Header and inline files installed into subdirectory based on whether
logically in the Core or a part of the RTEMS API.

  • Property mode set to 100644
File size: 14.0 KB
Line 
1/*
2 *  Heap Handler
3 *
4 *  COPYRIGHT (c) 1989, 1990, 1991, 1992, 1993, 1994.
5 *  On-Line Applications Research Corporation (OAR).
6 *  All rights assigned to U.S. Government, 1994.
7 *
8 *  This material may be reproduced by or for the U.S. Government pursuant
9 *  to the copyright license under the clause at DFARS 252.227-7013.  This
10 *  notice must appear in all copies of this file and its derivatives.
11 *
12 *  $Id$
13 */
14
15
16#include <rtems/system.h>
17#include <rtems/core/heap.h>
18#include <rtems/sysstate.h>
19
20/*PAGE
21 *
22 *  _Heap_Initialize
23 *
24 *  This kernel routine initializes a heap.
25 *
26 *  Input parameters:
27 *    the_heap         - pointer to heap header
28 *    starting_address - starting address of heap
29 *    size             - size of heap
30 *    page_size        - allocatable unit of memory
31 *
32 *  Output parameters:
33 *    returns - maximum memory available if successfully initialized
34 *    0       - otherwise
35 *
36 *    This is what a heap looks like in memory immediately
37 *    after initialization:
38 *
39 *            +--------------------------------+
40 *     0      |  size = 0      | status = used |  a.k.a.  dummy back flag
41 *            +--------------------------------+
42 *     4      |  size = size-8 | status = free |  a.k.a.  front flag
43 *            +--------------------------------+
44 *     8      |  next     = PERM HEAP_TAIL     |
45 *            +--------------------------------+
46 *    12      |  previous = PERM HEAP_HEAD     |
47 *            +--------------------------------+
48 *            |                                |
49 *            |      memory available          |
50 *            |       for allocation           |
51 *            |                                |
52 *            +--------------------------------+
53 *  size - 8  |  size = size-8 | status = free |  a.k.a.  back flag
54 *            +--------------------------------+
55 *  size - 4  |  size = 0      | status = used |  a.k.a.  dummy front flag
56 *            +--------------------------------+
57 */
58
59unsigned32 _Heap_Initialize(
60  Heap_Control        *the_heap,
61  void                *starting_address,
62  unsigned32           size,
63  unsigned32           page_size
64)
65{
66  Heap_Block        *the_block;
67  unsigned32         the_size;
68
69  if ( !_Heap_Is_page_size_valid( page_size ) ||
70       (size < HEAP_MINIMUM_SIZE) )
71    return 0;
72
73  the_heap->page_size = page_size;
74  the_size = size - HEAP_OVERHEAD;
75
76  the_block             = (Heap_Block *) starting_address;
77  the_block->back_flag  = HEAP_DUMMY_FLAG;
78  the_block->front_flag = the_size;
79  the_block->next       = _Heap_Tail( the_heap );
80  the_block->previous   = _Heap_Head( the_heap );
81
82  the_heap->start          = the_block;
83  the_heap->first          = the_block;
84  the_heap->permanent_null = NULL;
85  the_heap->last           = the_block;
86
87  the_block             = _Heap_Next_block( the_block );
88  the_block->back_flag  = the_size;
89  the_block->front_flag = HEAP_DUMMY_FLAG;
90  the_heap->final       = the_block;
91
92  return ( the_size - HEAP_BLOCK_USED_OVERHEAD );
93}
94
95/*PAGE
96 *
97 *  _Heap_Extend
98 *
99 *  This routine grows the_heap memory area using the size bytes which
100 *  begin at starting_address.
101 *
102 *  Input parameters:
103 *    the_heap          - pointer to heap header.
104 *    starting_address  - pointer to the memory area.
105 *    size              - size in bytes of the memory block to allocate.
106 *
107 *  Output parameters:
108 *    *amount_extended  - amount of memory added to the_heap
109 */
110
111Heap_Extend_status _Heap_Extend(
112  Heap_Control        *the_heap,
113  void                *starting_address,
114  unsigned32           size,
115  unsigned32          *amount_extended
116)
117{
118  Heap_Block        *the_block;
119 
120  /*
121   *  The overhead was taken from the original heap memory.
122   */
123
124  Heap_Block  *old_final;
125  Heap_Block  *new_final;
126
127  /*
128   *  There are five possibilities for the location of starting
129   *  address:
130   *
131   *    1. non-contiguous lower address     (NOT SUPPORTED)
132   *    2. contiguous lower address         (NOT SUPPORTED)
133   *    3. in the heap                      (ERROR)
134   *    4. contiguous higher address        (SUPPORTED)
135   *    5. non-contiguous higher address    (NOT SUPPORTED)
136   *
137   *  As noted, this code only supports (4).
138   */
139
140  if ( starting_address >= (void *) the_heap->start &&        /* case 3 */
141       starting_address <= (void *) the_heap->final
142     )
143    return HEAP_EXTEND_ERROR;
144
145  if ( starting_address < (void *) the_heap->start ) {  /* cases 1 and 2 */
146
147      return HEAP_EXTEND_NOT_IMPLEMENTED;               /* cases 1 and 2 */
148
149  } else {                                              /* cases 4 and 5 */
150
151    the_block  = (Heap_Block *) (starting_address - HEAP_OVERHEAD);
152    if ( the_block != the_heap->final )
153      return HEAP_EXTEND_NOT_IMPLEMENTED;                   /* case 5 */
154  }
155
156  /*
157   *  Currently only case 4 should make it to this point.
158   *  The basic trick is to make the extend area look like a used
159   *  block and free it.
160   */
161
162  *amount_extended = size;
163
164  old_final = the_heap->final;
165  new_final = _Addresses_Add_offset( old_final, size );
166  /* SAME AS: _Addresses_Add_offset( starting_address, size-HEAP_OVERHEAD ); */
167
168  the_heap->final = new_final;
169
170  old_final->front_flag =
171  new_final->back_flag  = _Heap_Build_flag( size, HEAP_BLOCK_USED );
172  new_final->front_flag = HEAP_DUMMY_FLAG;
173
174  /*
175   *  Must pass in address of "user" area
176   */
177
178  _Heap_Free( the_heap, &old_final->next );
179
180  return HEAP_EXTEND_SUCCESSFUL;
181}
182
183/*PAGE
184 *
185 *  _Heap_Allocate
186 *
187 *  This kernel routine allocates the requested size of memory
188 *  from the specified heap.
189 *
190 *  Input parameters:
191 *    the_heap  - pointer to heap header.
192 *    size      - size in bytes of the memory block to allocate.
193 *
194 *  Output parameters:
195 *    returns - starting address of memory block allocated
196 */
197
198void *_Heap_Allocate(
199  Heap_Control        *the_heap,
200  unsigned32           size
201)
202{
203  unsigned32  excess;
204  unsigned32  the_size;
205  Heap_Block *the_block;
206  Heap_Block *next_block;
207  Heap_Block *temporary_block;
208
209  excess   = size % the_heap->page_size;
210  the_size = size + HEAP_BLOCK_USED_OVERHEAD;
211
212  if ( excess )
213    the_size += the_heap->page_size - excess;
214
215  if ( the_size < sizeof( Heap_Block ) )
216    the_size = sizeof( Heap_Block );
217
218  for ( the_block = the_heap->first;
219        ;
220        the_block = the_block->next ) {
221    if ( the_block == _Heap_Tail( the_heap ) )
222      return( NULL );
223    if ( the_block->front_flag >= the_size )
224      break;
225  }
226
227  if ( (the_block->front_flag - the_size) >
228       (the_heap->page_size + HEAP_BLOCK_USED_OVERHEAD) ) {
229    the_block->front_flag -= the_size;
230    next_block             = _Heap_Next_block( the_block );
231    next_block->back_flag  = the_block->front_flag;
232
233    temporary_block            = _Heap_Block_at( next_block, the_size );
234    temporary_block->back_flag =
235    next_block->front_flag     = _Heap_Build_flag( the_size,
236                                    HEAP_BLOCK_USED );
237    return( _Heap_Start_of_user_area( next_block ) );
238  } else {
239    next_block                = _Heap_Next_block( the_block );
240    next_block->back_flag     = _Heap_Build_flag( the_block->front_flag,
241                                   HEAP_BLOCK_USED );
242    the_block->front_flag     = next_block->back_flag;
243    the_block->next->previous = the_block->previous;
244    the_block->previous->next = the_block->next;
245    return( _Heap_Start_of_user_area( the_block ) );
246  }
247}
248
249/*PAGE
250 *
251 *  _Heap_Size_of_user_area
252 *
253 *  This kernel routine returns the size of the memory area
254 *  given heap block.
255 *
256 *  Input parameters:
257 *    the_heap         - pointer to heap header
258 *    starting_address - starting address of the memory block to free.
259 *    size             - pointer to size of area
260 *
261 *  Output parameters:
262 *    size  - size of area filled in
263 *    TRUE  - if starting_address is valid heap address
264 *    FALSE - if starting_address is invalid heap address
265 */
266
267boolean _Heap_Size_of_user_area(
268  Heap_Control        *the_heap,
269  void                *starting_address,
270  unsigned32          *size
271)
272{
273  Heap_Block        *the_block;
274  Heap_Block        *next_block;
275  unsigned32         the_size;
276
277  the_block = _Heap_Block_at( starting_address, - (sizeof( void * ) * 2) );
278
279  if ( !_Heap_Is_block_in( the_heap, the_block ) ||
280        _Heap_Is_block_free( the_block ) )
281    return( FALSE );
282
283  the_size   = _Heap_Block_size( the_block );
284  next_block = _Heap_Block_at( the_block, the_size );
285
286  if ( !_Heap_Is_block_in( the_heap, next_block ) ||
287       (the_block->front_flag != next_block->back_flag) )
288    return( FALSE );
289
290  *size = the_size;
291  return( TRUE );
292}
293
294/*PAGE
295 *
296 *  _Heap_Free
297 *
298 *  This kernel routine returns the memory designated by the
299 *  given heap and given starting address to the memory pool.
300 *
301 *  Input parameters:
302 *    the_heap         - pointer to heap header
303 *    starting_address - starting address of the memory block to free.
304 *
305 *  Output parameters:
306 *    TRUE  - if starting_address is valid heap address
307 *    FALSE - if starting_address is invalid heap address
308 */
309
310boolean _Heap_Free(
311  Heap_Control        *the_heap,
312  void                *starting_address
313)
314{
315  Heap_Block        *the_block;
316  Heap_Block        *next_block;
317  Heap_Block        *new_next_block;
318  Heap_Block        *previous_block;
319  Heap_Block        *temporary_block;
320  unsigned32         the_size;
321
322  the_block = _Heap_Block_at( starting_address, - (sizeof( void * ) * 2) );
323
324  if ( !_Heap_Is_block_in( the_heap, the_block ) ||
325        _Heap_Is_block_free( the_block ) ) {
326      return( FALSE );
327  }
328
329  the_size   = _Heap_Block_size( the_block );
330  next_block = _Heap_Block_at( the_block, the_size );
331
332  if ( !_Heap_Is_block_in( the_heap, next_block ) ||
333       (the_block->front_flag != next_block->back_flag) ) {
334      return( FALSE );
335  }
336
337  if ( _Heap_Is_previous_block_free( the_block ) ) {
338    previous_block = _Heap_Previous_block( the_block );
339
340    if ( !_Heap_Is_block_in( the_heap, previous_block ) ) {
341        return( FALSE );
342    }
343
344    if ( _Heap_Is_block_free( next_block ) ) {      /* coalesce both */
345      previous_block->front_flag += next_block->front_flag + the_size;
346      temporary_block             = _Heap_Next_block( previous_block );
347      temporary_block->back_flag  = previous_block->front_flag;
348      next_block->next->previous  = next_block->previous;
349      next_block->previous->next  = next_block->next;
350    }
351    else {                     /* coalesce prev */
352      previous_block->front_flag =
353      next_block->back_flag      = previous_block->front_flag + the_size;
354    }
355  }
356  else if ( _Heap_Is_block_free( next_block ) ) { /* coalesce next */
357    the_block->front_flag     = the_size + next_block->front_flag;
358    new_next_block            = _Heap_Next_block( the_block );
359    new_next_block->back_flag = the_block->front_flag;
360    the_block->next           = next_block->next;
361    the_block->previous       = next_block->previous;
362    next_block->previous->next = the_block;
363    next_block->next->previous = the_block;
364
365    if (the_heap->first == next_block)
366        the_heap->first = the_block;
367  }
368  else {                          /* no coalesce */
369    next_block->back_flag     =
370    the_block->front_flag     = the_size;
371    the_block->previous       = _Heap_Head( the_heap );
372    the_block->next           = the_heap->first;
373    the_heap->first           = the_block;
374    the_block->next->previous = the_block;
375  }
376
377  return( TRUE );
378}
379
380/*PAGE
381 *
382 *  _Heap_Walk
383 *
384 *  This kernel routine walks the heap and verifies its correctness.
385 *
386 *  Input parameters:
387 *    the_heap  - pointer to heap header
388 *    source    - a numeric indicator of the invoker of this routine
389 *    do_dump   - when TRUE print the information
390 *
391 *  Output parameters: NONE
392 */
393
394#include <stdio.h>
395#include <unistd.h>
396
397void _Heap_Walk(
398  Heap_Control  *the_heap,
399  int            source,
400  boolean        do_dump
401)
402{
403  Heap_Block *the_block  = 0;  /* avoid warnings */
404  Heap_Block *next_block = 0;  /* avoid warnings */
405  int         notdone = 1;
406
407  /*
408   * We don't want to allow walking the heap until we have
409   * transferred control to the user task so we watch the
410   * system state.
411   */
412
413  if ( !_System_state_Is_up( _System_state_Get() ) )
414    return;
415
416  the_block = the_heap->start;
417
418  if (do_dump == TRUE) {
419    printf("\nPASS: %d  start @ 0x%p   final 0x%p,   first 0x%p  last 0x%p\n",
420            source, the_heap->start, the_heap->final,
421                  the_heap->first, the_heap->last
422          );
423  }
424
425  /*
426   * Handle the 1st block
427   */
428
429  if (the_block->back_flag != HEAP_DUMMY_FLAG) {
430    printf("PASS: %d  Back flag of 1st block isn't HEAP_DUMMY_FLAG\n", source);
431  }
432
433  while (notdone) {
434    if (do_dump == TRUE) {
435      printf("PASS: %d  Block @ 0x%p   Back %d,   Front %d",
436              source, the_block,
437              the_block->back_flag, the_block->front_flag);
438      if ( _Heap_Is_block_free(the_block) ) {
439        printf( "      Prev 0x%p,   Next 0x%p\n",
440                          the_block->previous, the_block->next);
441      } else {
442        printf("\n");
443      }
444    }
445
446    /*
447     * Handle the last block
448     */
449
450    if ( the_block->front_flag != HEAP_DUMMY_FLAG ) {
451      next_block = _Heap_Next_block(the_block);
452      if ( the_block->front_flag != next_block->back_flag ) {
453        printf("PASS: %d  Front and back flags don't match\n", source);
454        printf("         Current Block:  Back - %d,  Front - %d",
455               the_block->back_flag, the_block->front_flag);
456        if (do_dump == TRUE) {
457          if (_Heap_Is_block_free(the_block)) {
458            printf("      Prev 0x%p,   Next 0x%p\n",
459                   the_block->previous, the_block->next);
460          } else {
461            printf("\n");
462          }
463        } else {
464          printf("\n");
465        }
466        printf("         Next Block:     Back - %d,  Front - %d",
467               next_block->back_flag, next_block->front_flag);
468        if (do_dump == TRUE) {
469          if (_Heap_Is_block_free(next_block)) {
470            printf("      Prev 0x%p,   Next 0x%p\n",
471                   the_block->previous, the_block->next);
472          } else {
473            printf("\n");
474          }
475        } else {
476          printf("\n");
477        }
478      }
479    }
480
481    if (the_block->front_flag == HEAP_DUMMY_FLAG)
482      notdone = 0;
483    else
484      the_block = next_block;
485  }
486}
Note: See TracBrowser for help on using the repository browser.