source: rtems/c/src/exec/score/src/heap.c @ 11290355

4.104.114.84.9
Last change on this file since 11290355 was 11290355, checked in by Joel Sherrill <joel.sherrill@…>, on Sep 29, 1995 at 5:19:16 PM

all targets compile .. tony's patches in place

  • Property mode set to 100644
File size: 14.8 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/score/sysstate.h>
18#include <rtems/score/heap.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 RTEMS_SUCCESSFUL
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  unsigned32        *p;
120 
121  /*
122   *  The overhead was taken from the original heap memory.
123   */
124
125  Heap_Block  *old_final;
126  Heap_Block  *new_final;
127
128  /*
129   *  There are five possibilities for the location of starting
130   *  address:
131   *
132   *    1. non-contiguous lower address     (NOT SUPPORTED)
133   *    2. contiguous lower address         (NOT SUPPORTED)
134   *    3. in the heap                      (ERROR)
135   *    4. contiguous higher address        (SUPPORTED)
136   *    5. non-contiguous higher address    (NOT SUPPORTED)
137   *
138   *  As noted, this code only supports (4).
139   */
140
141  if ( starting_address >= (void *) the_heap->start &&        /* case 3 */
142       starting_address <= (void *) the_heap->final
143     )
144    return HEAP_EXTEND_ERROR;
145
146  if ( starting_address < (void *) the_heap->start ) {  /* cases 1 and 2 */
147
148      return HEAP_EXTEND_NOT_IMPLEMENTED;               /* cases 1 and 2 */
149
150  } else {                                              /* cases 4 and 5 */
151
152    the_block  = (Heap_Block *) (starting_address - HEAP_OVERHEAD);
153    if ( the_block != the_heap->final )
154      return HEAP_EXTEND_NOT_IMPLEMENTED;                   /* case 5 */
155  }
156
157  /*
158   *  Currently only case 4 should make it to this point.
159   *  The basic trick is to make the extend area look like a used
160   *  block and free it.
161   */
162
163  *amount_extended = size;
164
165  old_final = the_heap->final;
166  new_final = _Addresses_Add_offset( old_final, size );
167  /* SAME AS: _Addresses_Add_offset( starting_address, size-HEAP_OVERHEAD ); */
168
169  the_heap->final = new_final;
170
171  old_final->front_flag = 
172  new_final->back_flag  = _Heap_Build_flag( size, HEAP_BLOCK_USED );
173  new_final->front_flag = HEAP_DUMMY_FLAG;
174
175  /*
176   *  Must pass in address of "user" area
177   *  So add in the offset field.
178   */
179
180  p = (unsigned32 *) &old_final->next;
181  *p = sizeof(unsigned32);
182  p++;
183  _Heap_Free( the_heap, p );
184 
185  return HEAP_EXTEND_SUCCESSFUL;
186}
187
188/*PAGE
189 *
190 *  _Heap_Allocate
191 *
192 *  This kernel routine allocates the requested size of memory
193 *  from the specified heap.
194 *
195 *  Input parameters:
196 *    the_heap  - pointer to heap header.
197 *    size      - size in bytes of the memory block to allocate.
198 *
199 *  Output parameters:
200 *    returns - starting address of memory block allocated
201 */
202
203void *_Heap_Allocate(
204  Heap_Control        *the_heap,
205  unsigned32           size
206)
207{
208  unsigned32  excess;
209  unsigned32  the_size;
210  Heap_Block *the_block;
211  Heap_Block *next_block;
212  Heap_Block *temporary_block;
213  void       *ptr;
214  unsigned32  offset;
215 
216  excess   = size % the_heap->page_size;
217  the_size = size + the_heap->page_size + HEAP_BLOCK_USED_OVERHEAD;
218 
219  if ( excess )
220    the_size += the_heap->page_size - excess;
221
222  if ( the_size < sizeof( Heap_Block ) )
223    the_size = sizeof( Heap_Block );
224
225  for ( the_block = the_heap->first;
226        ;
227        the_block = the_block->next ) {
228    if ( the_block == _Heap_Tail( the_heap ) )
229      return( NULL );
230    if ( the_block->front_flag >= the_size )
231      break;
232  }
233
234  if ( (the_block->front_flag - the_size) >
235       (the_heap->page_size + HEAP_BLOCK_USED_OVERHEAD) ) {
236    the_block->front_flag -= the_size;
237    next_block             = _Heap_Next_block( the_block );
238    next_block->back_flag  = the_block->front_flag;
239
240    temporary_block            = _Heap_Block_at( next_block, the_size );
241    temporary_block->back_flag =
242    next_block->front_flag     = _Heap_Build_flag( the_size,
243                                    HEAP_BLOCK_USED );
244    ptr = _Heap_Start_of_user_area( next_block );
245  } else {
246    next_block                = _Heap_Next_block( the_block );
247    next_block->back_flag     = _Heap_Build_flag( the_block->front_flag,
248                                   HEAP_BLOCK_USED );
249    the_block->front_flag     = next_block->back_flag;
250    the_block->next->previous = the_block->previous;
251    the_block->previous->next = the_block->next;
252    ptr = _Heap_Start_of_user_area( the_block );
253  }
254 
255  /*
256   * round ptr up to a multiple of page size
257   * Have to save the bump amount in the buffer so that free can figure it out
258   */
259 
260  offset = the_heap->page_size - (((unsigned32) ptr) & (the_heap->page_size - 1));
261  ptr += offset;
262  *(((unsigned32 *) ptr) - 1) = offset;
263
264#ifdef RTEMS_DEBUG
265  {
266      unsigned32 ptr_u32;
267      ptr_u32 = (unsigned32) ptr;
268      if (ptr_u32 & (the_heap->page_size - 1))
269          abort();
270  }
271#endif
272
273  return ptr;
274}
275
276/*PAGE
277 *
278 *  _Heap_Size_of_user_area
279 *
280 *  This kernel routine returns the size of the memory area
281 *  given heap block.
282 *
283 *  Input parameters:
284 *    the_heap         - pointer to heap header
285 *    starting_address - starting address of the memory block to free.
286 *    size             - pointer to size of area
287 *
288 *  Output parameters:
289 *    size  - size of area filled in
290 *    TRUE  - if starting_address is valid heap address
291 *    FALSE - if starting_address is invalid heap address
292 */
293
294boolean _Heap_Size_of_user_area(
295  Heap_Control        *the_heap,
296  void                *starting_address,
297  unsigned32          *size
298)
299{
300  Heap_Block        *the_block;
301  Heap_Block        *next_block;
302  unsigned32         the_size;
303
304  the_block = _Heap_User_block_at( starting_address );
305 
306  if ( !_Heap_Is_block_in( the_heap, the_block ) ||
307        _Heap_Is_block_free( the_block ) )
308    return( FALSE );
309
310  the_size   = _Heap_Block_size( the_block );
311  next_block = _Heap_Block_at( the_block, the_size );
312
313  if ( !_Heap_Is_block_in( the_heap, next_block ) ||
314       (the_block->front_flag != next_block->back_flag) )
315    return( FALSE );
316
317  *size = the_size;
318  return( TRUE );
319}
320
321/*PAGE
322 *
323 *  _Heap_Free
324 *
325 *  This kernel routine returns the memory designated by the
326 *  given heap and given starting address to the memory pool.
327 *
328 *  Input parameters:
329 *    the_heap         - pointer to heap header
330 *    starting_address - starting address of the memory block to free.
331 *
332 *  Output parameters:
333 *    TRUE  - if starting_address is valid heap address
334 *    FALSE - if starting_address is invalid heap address
335 */
336
337boolean _Heap_Free(
338  Heap_Control        *the_heap,
339  void                *starting_address
340)
341{
342  Heap_Block        *the_block;
343  Heap_Block        *next_block;
344  Heap_Block        *new_next_block;
345  Heap_Block        *previous_block;
346  Heap_Block        *temporary_block;
347  unsigned32         the_size;
348
349  the_block = _Heap_User_block_at( starting_address );
350
351  if ( !_Heap_Is_block_in( the_heap, the_block ) ||
352        _Heap_Is_block_free( the_block ) ) {
353      return( FALSE );
354  }
355
356  the_size   = _Heap_Block_size( the_block );
357  next_block = _Heap_Block_at( the_block, the_size );
358
359  if ( !_Heap_Is_block_in( the_heap, next_block ) ||
360       (the_block->front_flag != next_block->back_flag) ) {
361      return( FALSE );
362  }
363
364  if ( _Heap_Is_previous_block_free( the_block ) ) {
365    previous_block = _Heap_Previous_block( the_block );
366
367    if ( !_Heap_Is_block_in( the_heap, previous_block ) ) {
368        return( FALSE );
369    }
370
371    if ( _Heap_Is_block_free( next_block ) ) {      /* coalesce both */
372      previous_block->front_flag += next_block->front_flag + the_size;
373      temporary_block             = _Heap_Next_block( previous_block );
374      temporary_block->back_flag  = previous_block->front_flag;
375      next_block->next->previous  = next_block->previous;
376      next_block->previous->next  = next_block->next;
377    }
378    else {                     /* coalesce prev */
379      previous_block->front_flag =
380      next_block->back_flag      = previous_block->front_flag + the_size;
381    }
382  }
383  else if ( _Heap_Is_block_free( next_block ) ) { /* coalesce next */
384    the_block->front_flag     = the_size + next_block->front_flag;
385    new_next_block            = _Heap_Next_block( the_block );
386    new_next_block->back_flag = the_block->front_flag;
387    the_block->next           = next_block->next;
388    the_block->previous       = next_block->previous;
389    next_block->previous->next = the_block;
390    next_block->next->previous = the_block;
391
392    if (the_heap->first == next_block)
393        the_heap->first = the_block;
394  }
395  else {                          /* no coalesce */
396    next_block->back_flag     =
397    the_block->front_flag     = the_size;
398    the_block->previous       = _Heap_Head( the_heap );
399    the_block->next           = the_heap->first;
400    the_heap->first           = the_block;
401    the_block->next->previous = the_block;
402  }
403
404  return( TRUE );
405}
406
407/*PAGE
408 *
409 *  _Heap_Walk
410 *
411 *  This kernel routine walks the heap and verifies its correctness.
412 *
413 *  Input parameters:
414 *    the_heap  - pointer to heap header
415 *    source    - a numeric indicator of the invoker of this routine
416 *    do_dump   - when TRUE print the information
417 *
418 *  Output parameters: NONE
419 */
420
421#include <stdio.h>
422#include <unistd.h>
423
424void _Heap_Walk(
425  Heap_Control  *the_heap,
426  int            source,
427  boolean        do_dump
428)
429{
430  Heap_Block *the_block  = 0;  /* avoid warnings */
431  Heap_Block *next_block = 0;  /* avoid warnings */
432  int         notdone = 1;
433  int         error = 0;
434  int         passes = 0;
435
436  /*
437   * We don't want to allow walking the heap until we have
438   * transferred control to the user task so we watch the
439   * system state.
440   */
441
442  if ( !_System_state_Is_up( _System_state_Get() ) )
443    return;
444
445  the_block = the_heap->start;
446
447  if (do_dump == TRUE) {
448    printf("\nPASS: %d  start @ 0x%p   final 0x%p,   first 0x%p  last 0x%p\n",
449            source, the_heap->start, the_heap->final,
450                  the_heap->first, the_heap->last
451          );
452  }
453
454  /*
455   * Handle the 1st block
456   */
457
458  if (the_block->back_flag != HEAP_DUMMY_FLAG) {
459    printf("PASS: %d  Back flag of 1st block isn't HEAP_DUMMY_FLAG\n", source);
460    error = 1;
461  }
462
463  while (notdone) {
464    passes++;
465    if (error && (passes > 10))
466        abort();
467   
468    if (do_dump == TRUE) {
469      printf("PASS: %d  Block @ 0x%p   Back %d,   Front %d",
470              source, the_block,
471              the_block->back_flag, the_block->front_flag);
472      if ( _Heap_Is_block_free(the_block) ) {
473        printf( "      Prev 0x%p,   Next 0x%p\n",
474                          the_block->previous, the_block->next);
475      } else {
476        printf("\n");
477      }
478    }
479
480    /*
481     * Handle the last block
482     */
483
484    if ( the_block->front_flag != HEAP_DUMMY_FLAG ) {
485      next_block = _Heap_Next_block(the_block);
486      if ( the_block->front_flag != next_block->back_flag ) {
487        error = 1;
488        printf("PASS: %d  Front and back flags don't match\n", source);
489        printf("         Current Block:  Back - %d,  Front - %d",
490               the_block->back_flag, the_block->front_flag);
491        if (do_dump == TRUE) {
492          if (_Heap_Is_block_free(the_block)) {
493            printf("      Prev 0x%p,   Next 0x%p\n",
494                   the_block->previous, the_block->next);
495          } else {
496            printf("\n");
497          }
498        } else {
499          printf("\n");
500        }
501        printf("         Next Block:     Back - %d,  Front - %d",
502               next_block->back_flag, next_block->front_flag);
503        if (do_dump == TRUE) {
504          if (_Heap_Is_block_free(next_block)) {
505            printf("      Prev 0x%p,   Next 0x%p\n",
506                   the_block->previous, the_block->next);
507          } else {
508            printf("\n");
509          }
510        } else {
511          printf("\n");
512        }
513      }
514    }
515
516    if (the_block->front_flag == HEAP_DUMMY_FLAG)
517      notdone = 0;
518    else
519      the_block = next_block;
520  }
521
522  if (error)
523      abort();
524}
Note: See TracBrowser for help on using the repository browser.