RTEMS
heapimpl.h
Go to the documentation of this file.
1 
9 /*
10  * COPYRIGHT (c) 1989-2008.
11  * On-Line Applications Research Corporation (OAR).
12  *
13  * The license and distribution terms for this file may be
14  * found in the file LICENSE in this distribution or at
15  * http://www.rtems.org/license/LICENSE.
16  */
17 
18 #ifndef _RTEMS_SCORE_HEAPIMPL_H
19 #define _RTEMS_SCORE_HEAPIMPL_H
20 
21 #include <rtems/score/heap.h>
22 
23 #ifdef __cplusplus
24 extern "C" {
25 #endif
26 
36 #define HEAP_PREV_BLOCK_USED ((uintptr_t) 1)
37 
42 #define HEAP_ALLOC_BONUS sizeof(uintptr_t)
43 
47 typedef enum {
48  HEAP_RESIZE_SUCCESSFUL,
49  HEAP_RESIZE_UNSATISFIED,
50  HEAP_RESIZE_FATAL_ERROR
52 
69  uintptr_t heap_area_begin,
70  uintptr_t heap_area_size,
71  uintptr_t page_size,
72  uintptr_t min_block_size,
73  Heap_Block **first_block_ptr,
74  Heap_Block **last_block_ptr
75 );
76 
94 uintptr_t _Heap_Initialize(
95  Heap_Control *heap,
96  void *area_begin,
97  uintptr_t area_size,
98  uintptr_t page_size
99 );
100 
120  Heap_Control *heap,
121  uintptr_t size,
122  uintptr_t alignment,
123  uintptr_t boundary
124 );
125 
140  Heap_Control *heap,
141  uintptr_t size,
142  uintptr_t alignment
143 )
144 {
145  return _Heap_Allocate_aligned_with_boundary( heap, size, alignment, 0 );
146 }
147 
160 RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size )
161 {
162  return _Heap_Allocate_aligned_with_boundary( heap, size, 0, 0 );
163 }
164 
176 bool _Heap_Free( Heap_Control *heap, void *addr );
177 
190 bool _Heap_Walk(
191  Heap_Control *heap,
192  int source,
193  bool dump
194 );
195 
204 typedef bool (*Heap_Block_visitor)(
205  const Heap_Block *block,
206  uintptr_t block_size,
207  bool block_is_used,
208  void *visitor_arg
209 );
210 
219 void _Heap_Iterate(
220  Heap_Control *heap,
221  Heap_Block_visitor visitor,
222  void *visitor_arg
223 );
224 
242  Heap_Control *heap,
243  const uintptr_t *block_sizes,
244  size_t block_count
245 );
246 
262  Heap_Control *heap,
263  uintptr_t *allocatable_size
264 );
265 
272 void _Heap_Greedy_free(
273  Heap_Control *heap,
274  Heap_Block *blocks
275 );
276 
284  Heap_Control *heap,
286 );
287 
296  Heap_Control *heap,
297  Heap_Information *info
298 );
299 
317  Heap_Control *heap,
318  void *addr,
319  uintptr_t *size
320 );
321 
344  Heap_Control *heap,
345  void *addr,
346  uintptr_t size,
347  uintptr_t *old_size,
348  uintptr_t *new_size
349 );
350 
373  Heap_Control *heap,
374  Heap_Block *block,
375  uintptr_t alloc_begin,
376  uintptr_t alloc_size
377 );
378 
379 #ifndef HEAP_PROTECTION
380  #define _Heap_Protection_block_initialize( heap, block ) ((void) 0)
381  #define _Heap_Protection_block_check( heap, block ) ((void) 0)
382  #define _Heap_Protection_block_error( heap, block, reason ) ((void) 0)
383  #define _Heap_Protection_free_all_delayed_blocks( heap ) ((void) 0)
384 #else
385  static inline void _Heap_Protection_block_initialize(
386  Heap_Control *heap,
387  Heap_Block *block
388  )
389  {
390  (*heap->Protection.block_initialize)( heap, block );
391  }
392 
393  static inline void _Heap_Protection_block_check(
394  Heap_Control *heap,
395  Heap_Block *block
396  )
397  {
398  (*heap->Protection.block_check)( heap, block );
399  }
400 
401  static inline void _Heap_Protection_block_error(
402  Heap_Control *heap,
403  Heap_Block *block,
404  Heap_Error_reason reason
405  )
406  {
407  (*heap->Protection.block_error)( heap, block, reason );
408  }
409 
410  static inline void _Heap_Protection_free_all_delayed_blocks( Heap_Control *heap )
411  {
412  uintptr_t large = 0
413  - (uintptr_t) HEAP_BLOCK_HEADER_SIZE
414  - (uintptr_t) HEAP_ALLOC_BONUS
415  - (uintptr_t) 1;
416  void *p = _Heap_Allocate( heap, large );
417  _Heap_Free( heap, p );
418  }
419 #endif
420 
432  Heap_Control *heap,
433  uintptr_t fraction
434 )
435 {
436 #ifdef HEAP_PROTECTION
437  heap->Protection.delayed_free_fraction = fraction;
438 #else
439  (void) heap;
440  (void) fraction;
441 #endif
442 }
443 
452 {
453  return &heap->free_list;
454 }
455 
464 {
465  return &heap->free_list;
466 }
467 
476 {
477  return _Heap_Free_list_head(heap)->next;
478 }
479 
488 {
489  return _Heap_Free_list_tail(heap)->prev;
490 }
491 
498 {
499  Heap_Block *next = block->next;
500  Heap_Block *prev = block->prev;
501 
502  prev->next = next;
503  next->prev = prev;
504 }
505 
513  Heap_Block *old_block,
514  Heap_Block *new_block
515 )
516 {
517  Heap_Block *next = old_block->next;
518  Heap_Block *prev = old_block->prev;
519 
520  new_block->next = next;
521  new_block->prev = prev;
522 
523  next->prev = new_block;
524  prev->next = new_block;
525 }
526 
534  Heap_Block *block_before,
535  Heap_Block *new_block
536 )
537 {
538  Heap_Block *next = block_before->next;
539 
540  new_block->next = next;
541  new_block->prev = block_before;
542  block_before->next = new_block;
543  next->prev = new_block;
544 }
545 
553  Heap_Block *block_next,
554  Heap_Block *new_block
555 )
556 {
557  Heap_Block *prev = block_next->prev;
558 
559  new_block->next = block_next;
560  new_block->prev = prev;
561  prev->next = new_block;
562  block_next->prev = new_block;
563 }
564 
575  uintptr_t value,
576  uintptr_t alignment
577 )
578 {
579  return (value % alignment) == 0;
580 }
581 
591  uintptr_t value,
592  uintptr_t alignment
593 )
594 {
595  return value - (value % alignment);
596 }
597 
607  const Heap_Block *block,
608  uintptr_t offset
609 )
610 {
611  return (Heap_Block *) ((uintptr_t) block + offset);
612 }
613 
622  const Heap_Block *block
623 )
624 {
625  return (Heap_Block *) ((uintptr_t) block - block->prev_size);
626 }
627 
636  const Heap_Block *block
637 )
638 {
639  return (uintptr_t) block + HEAP_BLOCK_HEADER_SIZE;
640 }
641 
651  uintptr_t alloc_begin,
652  uintptr_t page_size
653 )
654 {
655  return (Heap_Block *) (_Heap_Align_down( alloc_begin, page_size )
657 }
658 
667 {
668  return block->size_and_flag & ~HEAP_PREV_BLOCK_USED;
669 }
670 
678  Heap_Block *block,
679  uintptr_t size
680 )
681 {
682  uintptr_t flag = block->size_and_flag & HEAP_PREV_BLOCK_USED;
683 
684  block->size_and_flag = size | flag;
685 }
686 
697 {
698  return block->size_and_flag & HEAP_PREV_BLOCK_USED;
699 }
700 
710  const Heap_Block *block
711 )
712 {
713  const Heap_Block *const next_block =
714  _Heap_Block_at( block, _Heap_Block_size( block ) );
715 
716  return _Heap_Is_prev_used( next_block );
717 }
718 
728  const Heap_Block *block
729 )
730 {
731  return !_Heap_Is_used( block );
732 }
733 
744  const Heap_Control *heap,
745  const Heap_Block *block
746 )
747 {
748  return (uintptr_t) block >= (uintptr_t) heap->first_block
749  && (uintptr_t) block <= (uintptr_t) heap->last_block;
750 }
751 
766 {
768  heap->last_block,
769  (uintptr_t) heap->first_block - (uintptr_t) heap->last_block
770  );
771 }
772 
783 {
784  return heap->stats.size;
785 }
786 
796 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Max( uintptr_t a, uintptr_t b )
797 {
798  return a > b ? a : b;
799 }
800 
810 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Min( uintptr_t a, uintptr_t b )
811 {
812  return a < b ? a : b;
813 }
814 
815 #ifdef RTEMS_DEBUG
816  #define RTEMS_HEAP_DEBUG
817 #endif
818 
819 #ifdef RTEMS_HEAP_DEBUG
820  #include <assert.h>
821  #define _HAssert( cond ) \
822  do { \
823  if ( !(cond) ) { \
824  __assert( __FILE__, __LINE__, #cond ); \
825  } \
826  } while (0)
827 #else
828  #define _HAssert( cond ) ((void) 0)
829 #endif
830 
833 #ifdef __cplusplus
834 }
835 #endif
836 
837 #endif
838 /* end of include file */
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Alloc_area_of_block(const Heap_Block *block)
Returns the first address in the block without the heap header.
Definition: heapimpl.h:635
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Free_list_first(Heap_Control *heap)
Returns the first block of the free list of the heap.
Definition: heapimpl.h:475
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Max(uintptr_t a, uintptr_t b)
Returns the bigger one of the two arguments.
Definition: heapimpl.h:796
uintptr_t size_and_flag
Contains the size of the current block and a flag which indicates if the previous block is free or us...
Definition: heap.h:289
Heap_Block * _Heap_Greedy_allocate_all_except_largest(Heap_Control *heap, uintptr_t *allocatable_size)
Greedily allocates all blocks except the largest free block.
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Prev_block(const Heap_Block *block)
Returns the address of the previous block.
Definition: heapimpl.h:621
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Block_at(const Heap_Block *block, uintptr_t offset)
Returns the block which is offset away from block.
Definition: heapimpl.h:606
Heap_Resize_status
See _Heap_Resize_block().
Definition: heapimpl.h:47
bool _Heap_Free(Heap_Control *heap, void *addr)
Frees the allocated memory area.
RTEMS_INLINE_ROUTINE void * _Heap_Allocate_aligned(Heap_Control *heap, uintptr_t size, uintptr_t alignment)
Allocates an aligned memory area.
Definition: heapimpl.h:139
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Block_of_alloc_area(uintptr_t alloc_begin, uintptr_t page_size)
Returns the starting address of the block corresponding to the allocatable area.
Definition: heapimpl.h:650
RTEMS_INLINE_ROUTINE bool _Heap_Is_free(const Heap_Block *block)
Returns if the heap block is free.
Definition: heapimpl.h:727
void _Heap_Iterate(Heap_Control *heap, Heap_Block_visitor visitor, void *visitor_arg)
Iterates over all blocks of the heap.
RTEMS_INLINE_ROUTINE void * _Heap_Allocate(Heap_Control *heap, uintptr_t size)
Allocates a memory area.
Definition: heapimpl.h:160
RTEMS_INLINE_ROUTINE void _Heap_Free_list_remove(Heap_Block *block)
Removes the block from the free list.
Definition: heapimpl.h:497
RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in_heap(const Heap_Control *heap, const Heap_Block *block)
Returns if the block is part of the heap.
Definition: heapimpl.h:743
Information block returned by _Heap_Get_information().
Definition: heapinfo.h:145
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Free_list_tail(Heap_Control *heap)
Returns the tail of the free list of the heap.
Definition: heapimpl.h:463
RTEMS_INLINE_ROUTINE void _Heap_Block_set_size(Heap_Block *block, uintptr_t size)
Sets the block size.
Definition: heapimpl.h:677
Heap_Block * _Heap_Greedy_allocate(Heap_Control *heap, const uintptr_t *block_sizes, size_t block_count)
Greedily allocates and empties the heap.
void _Heap_Get_information(Heap_Control *heap, Heap_Information_block *info)
Returns information about used and free blocks for the heap.
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Get_size(const Heap_Control *heap)
Returns the size of the allocatable area in bytes.
Definition: heapimpl.h:782
RTEMS_INLINE_ROUTINE void _Heap_Protection_set_delayed_free_fraction(Heap_Control *heap, uintptr_t fraction)
Sets the fraction of delayed free blocks that is actually freed during memory shortage.
Definition: heapimpl.h:431
Information for the Assert Handler.
Heap Handler API.
Description for free or used blocks.
Definition: heap.h:256
RTEMS_INLINE_ROUTINE bool _Heap_Is_prev_used(const Heap_Block *block)
Returns if the previous heap block is used.
Definition: heapimpl.h:696
void _Heap_Greedy_free(Heap_Control *heap, Heap_Block *blocks)
Frees blocks of a greedy allocation.
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Free_list_head(Heap_Control *heap)
Returns the head of the free list of the heap.
Definition: heapimpl.h:451
RTEMS_INLINE_ROUTINE Heap_Block * _Heap_Free_list_last(Heap_Control *heap)
Returns the last block of the free list of the heap.
Definition: heapimpl.h:487
RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned(uintptr_t value, uintptr_t alignment)
Checks if the value is aligned to the given alignment.
Definition: heapimpl.h:574
Control block used to manage a heap.
Definition: heap.h:318
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_down(uintptr_t value, uintptr_t alignment)
Returns the aligned value, truncating.
Definition: heapimpl.h:590
uintptr_t _Heap_Initialize(Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size)
Initializes the heap control block.
Definition: heap.c:207
RTEMS_INLINE_ROUTINE void _Heap_Free_list_replace(Heap_Block *old_block, Heap_Block *new_block)
Replaces one block in the free list by another.
Definition: heapimpl.h:512
Information about blocks.
Definition: heapinfo.h:125
uintptr_t size
Size of the allocatable area in bytes.
Definition: heapinfo.h:60
Heap_Error_reason
The heap error reason.
Definition: heap.h:142
Heap_Block * next
Pointer to the next free block or part of the allocated area.
Definition: heap.h:304
#define HEAP_ALLOC_BONUS
Size of the part at the block begin which may be used for allocation in charge of the previous block...
Definition: heapimpl.h:42
uintptr_t prev_size
Size of the previous block or part of the allocated area of the previous block.
Definition: heap.h:270
Heap_Resize_status _Heap_Resize_block(Heap_Control *heap, void *addr, uintptr_t size, uintptr_t *old_size, uintptr_t *new_size)
Resizes the block of the allocated memory area.
RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_before(Heap_Block *block_next, Heap_Block *new_block)
Inserts a block before an existing block in the free list.
Definition: heapimpl.h:552
Heap_Block * _Heap_Block_allocate(Heap_Control *heap, Heap_Block *block, uintptr_t alloc_begin, uintptr_t alloc_size)
Allocates the memory area. starting at alloc_begin of size alloc_size bytes in the block block...
Definition: heap.c:431
RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_after(Heap_Block *block_before, Heap_Block *new_block)
Inserts a block after an existing block in the free list.
Definition: heapimpl.h:533
bool(* Heap_Block_visitor)(const Heap_Block *block, uintptr_t block_size, bool block_is_used, void *visitor_arg)
Heap block visitor.
Definition: heapimpl.h:204
#define RTEMS_INLINE_ROUTINE
Gives a hint to the compiler in a function declaration to inline this function.
Definition: basedefs.h:683
void _Heap_Get_free_information(Heap_Control *heap, Heap_Information *info)
Returns information about free blocks for the heap.
Heap_Block * prev
Pointer to the previous free block or part of the allocated area.
Definition: heap.h:312
#define HEAP_PREV_BLOCK_USED
See also Heap_Block::size_and_flag.
Definition: heapimpl.h:36
bool _Heap_Size_of_alloc_area(Heap_Control *heap, void *addr, uintptr_t *size)
Returns the size of the allocatable memory area.
#define HEAP_BLOCK_HEADER_SIZE
The block header consists of the two size fields (Heap_Block::prev_size and Heap_Block::size_and_flag...
Definition: heap.h:250
void * _Heap_Allocate_aligned_with_boundary(Heap_Control *heap, uintptr_t size, uintptr_t alignment, uintptr_t boundary)
Allocates an aligned memory area with boundary constraint.
Definition: heapallocate.c:192
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Min(uintptr_t a, uintptr_t b)
Returns the smaller one of the two arguments.
Definition: heapimpl.h:810
RTEMS_INLINE_ROUTINE void _Heap_Set_last_block_size(Heap_Control *heap)
Sets the size of the last block for the heap.
Definition: heapimpl.h:765
RTEMS_INLINE_ROUTINE bool _Heap_Is_used(const Heap_Block *block)
Returns if the heap block is used.
Definition: heapimpl.h:709
bool _Heap_Get_first_and_last_block(uintptr_t heap_area_begin, uintptr_t heap_area_size, uintptr_t page_size, uintptr_t min_block_size, Heap_Block **first_block_ptr, Heap_Block **last_block_ptr)
Gets the first and last block for the heap area.
Definition: heap.c:170
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Block_size(const Heap_Block *block)
Returns the block size.
Definition: heapimpl.h:666
bool _Heap_Walk(Heap_Control *heap, int source, bool dump)
Verifies the integrity of the heap.