RTEMS  5.0.0
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 
35 #define HEAP_PREV_BLOCK_USED ((uintptr_t) 1)
36 
41 #define HEAP_ALLOC_BONUS sizeof(uintptr_t)
42 
46 typedef enum {
47  HEAP_RESIZE_SUCCESSFUL,
48  HEAP_RESIZE_UNSATISFIED,
49  HEAP_RESIZE_FATAL_ERROR
51 
67  uintptr_t heap_area_begin,
68  uintptr_t heap_area_size,
69  uintptr_t page_size,
70  uintptr_t min_block_size,
71  Heap_Block **first_block_ptr,
72  Heap_Block **last_block_ptr
73 );
74 
87 uintptr_t _Heap_Initialize(
88  Heap_Control *heap,
89  void *area_begin,
90  uintptr_t area_size,
91  uintptr_t page_size
92 );
93 
113  Heap_Control *heap,
114  uintptr_t size,
115  uintptr_t alignment,
116  uintptr_t boundary
117 );
118 
123  Heap_Control *heap,
124  uintptr_t size,
125  uintptr_t alignment
126 )
127 {
128  return _Heap_Allocate_aligned_with_boundary( heap, size, alignment, 0 );
129 }
130 
135 RTEMS_INLINE_ROUTINE void *_Heap_Allocate( Heap_Control *heap, uintptr_t size )
136 {
137  return _Heap_Allocate_aligned_with_boundary( heap, size, 0, 0 );
138 }
139 
148 bool _Heap_Free( Heap_Control *heap, void *addr );
149 
158 bool _Heap_Walk(
159  Heap_Control *heap,
160  int source,
161  bool dump
162 );
163 
172 typedef bool (*Heap_Block_visitor)(
173  const Heap_Block *block,
174  uintptr_t block_size,
175  bool block_is_used,
176  void *visitor_arg
177 );
178 
185 void _Heap_Iterate(
186  Heap_Control *heap,
187  Heap_Block_visitor visitor,
188  void *visitor_arg
189 );
190 
201  Heap_Control *heap,
202  const uintptr_t *block_sizes,
203  size_t block_count
204 );
205 
216  Heap_Control *heap,
217  uintptr_t *allocatable_size
218 );
219 
225 void _Heap_Greedy_free(
226  Heap_Control *heap,
227  Heap_Block *blocks
228 );
229 
235  Heap_Control *heap,
237 );
238 
244  Heap_Control *heap,
245  Heap_Information *info
246 );
247 
261  Heap_Control *heap,
262  void *addr,
263  uintptr_t *size
264 );
265 
279 Heap_Resize_status _Heap_Resize_block(
280  Heap_Control *heap,
281  void *addr,
282  uintptr_t size,
283  uintptr_t *old_size,
284  uintptr_t *new_size
285 );
286 
303  Heap_Control *heap,
304  Heap_Block *block,
305  uintptr_t alloc_begin,
306  uintptr_t alloc_size
307 );
308 
309 #ifndef HEAP_PROTECTION
310  #define _Heap_Protection_block_initialize( heap, block ) ((void) 0)
311  #define _Heap_Protection_block_check( heap, block ) ((void) 0)
312  #define _Heap_Protection_block_error( heap, block ) ((void) 0)
313  #define _Heap_Protection_free_all_delayed_blocks( heap ) ((void) 0)
314 #else
315  static inline void _Heap_Protection_block_initialize(
316  Heap_Control *heap,
317  Heap_Block *block
318  )
319  {
320  (*heap->Protection.block_initialize)( heap, block );
321  }
322 
323  static inline void _Heap_Protection_block_check(
324  Heap_Control *heap,
325  Heap_Block *block
326  )
327  {
328  (*heap->Protection.block_check)( heap, block );
329  }
330 
331  static inline void _Heap_Protection_block_error(
332  Heap_Control *heap,
333  Heap_Block *block
334  )
335  {
336  (*heap->Protection.block_error)( heap, block );
337  }
338 
339  static inline void _Heap_Protection_free_all_delayed_blocks( Heap_Control *heap )
340  {
341  uintptr_t large = 0
342  - (uintptr_t) HEAP_BLOCK_HEADER_SIZE
343  - (uintptr_t) HEAP_ALLOC_BONUS
344  - (uintptr_t) 1;
345  void *p = _Heap_Allocate( heap, large );
346  _Heap_Free( heap, p );
347  }
348 #endif
349 
361  Heap_Control *heap,
362  uintptr_t fraction
363 )
364 {
365 #ifdef HEAP_PROTECTION
366  heap->Protection.delayed_free_fraction = fraction;
367 #else
368  (void) heap;
369  (void) fraction;
370 #endif
371 }
372 
373 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_head( Heap_Control *heap )
374 {
375  return &heap->free_list;
376 }
377 
378 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_tail( Heap_Control *heap )
379 {
380  return &heap->free_list;
381 }
382 
383 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_first( Heap_Control *heap )
384 {
385  return _Heap_Free_list_head(heap)->next;
386 }
387 
388 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Free_list_last( Heap_Control *heap )
389 {
390  return _Heap_Free_list_tail(heap)->prev;
391 }
392 
393 RTEMS_INLINE_ROUTINE void _Heap_Free_list_remove( Heap_Block *block )
394 {
395  Heap_Block *next = block->next;
396  Heap_Block *prev = block->prev;
397 
398  prev->next = next;
399  next->prev = prev;
400 }
401 
402 RTEMS_INLINE_ROUTINE void _Heap_Free_list_replace(
403  Heap_Block *old_block,
404  Heap_Block *new_block
405 )
406 {
407  Heap_Block *next = old_block->next;
408  Heap_Block *prev = old_block->prev;
409 
410  new_block->next = next;
411  new_block->prev = prev;
412 
413  next->prev = new_block;
414  prev->next = new_block;
415 }
416 
417 RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_after(
418  Heap_Block *block_before,
419  Heap_Block *new_block
420 )
421 {
422  Heap_Block *next = block_before->next;
423 
424  new_block->next = next;
425  new_block->prev = block_before;
426  block_before->next = new_block;
427  next->prev = new_block;
428 }
429 
430 RTEMS_INLINE_ROUTINE void _Heap_Free_list_insert_before(
431  Heap_Block *block_next,
432  Heap_Block *new_block
433 )
434 {
435  Heap_Block *prev = block_next->prev;
436 
437  new_block->next = block_next;
438  new_block->prev = prev;
439  prev->next = new_block;
440  block_next->prev = new_block;
441 }
442 
443 RTEMS_INLINE_ROUTINE bool _Heap_Is_aligned(
444  uintptr_t value,
445  uintptr_t alignment
446 )
447 {
448  return (value % alignment) == 0;
449 }
450 
451 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Align_down(
452  uintptr_t value,
453  uintptr_t alignment
454 )
455 {
456  return value - (value % alignment);
457 }
458 
463  const Heap_Block *block,
464  uintptr_t offset
465 )
466 {
467  return (Heap_Block *) ((uintptr_t) block + offset);
468 }
469 
470 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Prev_block(
471  const Heap_Block *block
472 )
473 {
474  return (Heap_Block *) ((uintptr_t) block - block->prev_size);
475 }
476 
477 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Alloc_area_of_block(
478  const Heap_Block *block
479 )
480 {
481  return (uintptr_t) block + HEAP_BLOCK_HEADER_SIZE;
482 }
483 
484 RTEMS_INLINE_ROUTINE Heap_Block *_Heap_Block_of_alloc_area(
485  uintptr_t alloc_begin,
486  uintptr_t page_size
487 )
488 {
489  return (Heap_Block *) (_Heap_Align_down( alloc_begin, page_size )
491 }
492 
493 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Block_size( const Heap_Block *block )
494 {
495  return block->size_and_flag & ~HEAP_PREV_BLOCK_USED;
496 }
497 
498 RTEMS_INLINE_ROUTINE void _Heap_Block_set_size(
499  Heap_Block *block,
500  uintptr_t size
501 )
502 {
503  uintptr_t flag = block->size_and_flag & HEAP_PREV_BLOCK_USED;
504 
505  block->size_and_flag = size | flag;
506 }
507 
508 RTEMS_INLINE_ROUTINE bool _Heap_Is_prev_used( const Heap_Block *block )
509 {
510  return block->size_and_flag & HEAP_PREV_BLOCK_USED;
511 }
512 
513 RTEMS_INLINE_ROUTINE bool _Heap_Is_used(
514  const Heap_Block *block
515 )
516 {
517  const Heap_Block *const next_block =
518  _Heap_Block_at( block, _Heap_Block_size( block ) );
519 
520  return _Heap_Is_prev_used( next_block );
521 }
522 
523 RTEMS_INLINE_ROUTINE bool _Heap_Is_free(
524  const Heap_Block *block
525 )
526 {
527  return !_Heap_Is_used( block );
528 }
529 
530 RTEMS_INLINE_ROUTINE bool _Heap_Is_block_in_heap(
531  const Heap_Control *heap,
532  const Heap_Block *block
533 )
534 {
535  return (uintptr_t) block >= (uintptr_t) heap->first_block
536  && (uintptr_t) block <= (uintptr_t) heap->last_block;
537 }
538 
551 {
552  _Heap_Block_set_size(
553  heap->last_block,
554  (uintptr_t) heap->first_block - (uintptr_t) heap->last_block
555  );
556 }
557 
564 {
565  return heap->stats.size;
566 }
567 
568 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Max( uintptr_t a, uintptr_t b )
569 {
570  return a > b ? a : b;
571 }
572 
573 RTEMS_INLINE_ROUTINE uintptr_t _Heap_Min( uintptr_t a, uintptr_t b )
574 {
575  return a < b ? a : b;
576 }
577 
578 #ifdef RTEMS_DEBUG
579  #define RTEMS_HEAP_DEBUG
580 #endif
581 
582 #ifdef RTEMS_HEAP_DEBUG
583  #include <assert.h>
584  #define _HAssert( cond ) \
585  do { \
586  if ( !(cond) ) { \
587  __assert( __FILE__, __LINE__, #cond ); \
588  } \
589  } while (0)
590 #else
591  #define _HAssert( cond ) ((void) 0)
592 #endif
593 
596 #ifdef __cplusplus
597 }
598 #endif
599 
600 #endif
601 /* end of include file */
bool _Heap_Walk(Heap_Control *heap, int source, bool dump)
Walks the heap heap to verify its integrity.
Definition: heapwalk.c:312
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:226
void _Heap_Iterate(Heap_Control *heap, Heap_Block_visitor visitor, void *visitor_arg)
Iterates over all blocks of the heap.
Definition: heapiterate.c:29
Heap_Block * _Heap_Greedy_allocate_all_except_largest(Heap_Control *heap, uintptr_t *allocatable_size)
Greedy allocate all blocks except the largest free block.
Definition: heapgreedy.c:78
void * _Heap_Allocate_aligned_with_boundary(Heap_Control *heap, uintptr_t size, uintptr_t alignment, uintptr_t boundary)
Allocates a memory area of size size bytes from the heap heap.
Definition: heapallocate.c:188
#define RTEMS_INLINE_ROUTINE
Definition: basedefs.h:65
RTEMS_INLINE_ROUTINE void _Heap_Set_last_block_size(Heap_Control *heap)
Sets the size of the last block for heap heap.
Definition: heapimpl.h:550
uintptr_t _Heap_Initialize(Heap_Control *heap, void *area_begin, uintptr_t area_size, uintptr_t page_size)
Initializes the heap control block heap to manage the area starting at area_begin of size area_size b...
Definition: heap.c:201
void _Heap_Get_information(Heap_Control *heap, Heap_Information_block *info)
Returns information about used and free blocks for the heap heap in info.
Definition: heapgetinfo.c:45
Information block returned by _Heap_Get_information().
Definition: heapinfo.h:145
unsigned p
Definition: tte.h:90
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 starting at addr.
Definition: heapresizeblock.c:86
void _Heap_Greedy_free(Heap_Control *heap, Heap_Block *blocks)
Frees blocks of a greedy allocation.
Definition: heapgreedy.c:96
Heap Handler API.
Description for free or used blocks.
Definition: heap.h:193
RTEMS_INLINE_ROUTINE void * _Heap_Allocate(Heap_Control *heap, uintptr_t size)
See _Heap_Allocate_aligned_with_boundary() with alignment and boundary equals zero.
Definition: heapimpl.h:135
RTEMS_INLINE_ROUTINE void * _Heap_Allocate_aligned(Heap_Control *heap, uintptr_t size, uintptr_t alignment)
See _Heap_Allocate_aligned_with_boundary() with boundary equals zero.
Definition: heapimpl.h:122
Heap_Resize_status
See _Heap_Resize_block().
Definition: heapimpl.h:46
#define HEAP_PREV_BLOCK_USED
See also Heap_Block::size_and_flag.
Definition: heapimpl.h:35
#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:187
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 with begin heap_area_begin and size heap_area_size...
Definition: heap.c:164
void _Heap_Get_free_information(Heap_Control *heap, Heap_Information *info)
Returns information about free blocks for the heap heap in info.
Definition: heapgetfreeinfo.c:24
RTEMS_INLINE_ROUTINE uintptr_t _Heap_Get_size(const Heap_Control *heap)
Returns the size of the allocatable area in bytes.
Definition: heapimpl.h:563
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:429
Control block used to manage a heap.
Definition: heap.h:255
#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:41
Information about blocks.
Definition: heapinfo.h:125
uintptr_t size
Size of the allocatable area in bytes.
Definition: heapinfo.h:60
Heap_Block * next
Pointer to the next free block or part of the allocated area.
Definition: heap.h:241
Heap_Block * _Heap_Greedy_allocate(Heap_Control *heap, const uintptr_t *block_sizes, size_t block_count)
Greedy allocate that empties the heap.
Definition: heapgreedy.c:29
uintptr_t prev_size
Size of the previous block or part of the allocated area of the previous block.
Definition: heap.h:207
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:172
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:462
unsigned size
Definition: tte.h:74
Heap_Block * prev
Pointer to the previous free block or part of the allocated area.
Definition: heap.h:249
bool _Heap_Free(Heap_Control *heap, void *addr)
Frees the allocated memory area starting at addr in the heap heap.
Definition: heapfree.c:99
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:360
bool _Heap_Size_of_alloc_area(Heap_Control *heap, void *addr, uintptr_t *size)
Returns the size of the allocatable memory area starting at addr in size.
Definition: heapsizeofuserarea.c:24