source: rtems/cpukit/score/src/heap.c @ 8f0529f

4.104.114.84.95
Last change on this file since 8f0529f was 60b791ad, checked in by Joel Sherrill <joel.sherrill@…>, on 02/17/98 at 23:46:28

updated copyright to 1998

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