diff options
Diffstat (limited to 'cpukit/sapi/include/rtems/rbheap.h')
-rw-r--r-- | cpukit/sapi/include/rtems/rbheap.h | 187 |
1 files changed, 163 insertions, 24 deletions
diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h index be1eec6b66..5481e8954f 100644 --- a/cpukit/sapi/include/rtems/rbheap.h +++ b/cpukit/sapi/include/rtems/rbheap.h @@ -36,60 +36,191 @@ extern "C" { * * @brief Red-Black Tree Heap API. * - * In the Red-Black Tree Heap the administration data structures are not - * contained in the managed memory area. This can be used for example in a - * task stack allocator which protects the task stacks from access by other - * tasks. + * The red-black tree heap provides a memory allocator suitable to implement + * the malloc() and free() interface. It uses a first-fit allocation strategy. + * In the red-black tree heap the administration data structures are not + * contained in the managed memory area. Thus writing beyond the boundaries of + * a chunk does not damage the data to maintain the heap. This can be used for + * example in a task stack allocator which protects the task stacks from access + * by other tasks. The allocated and free memory parts of the managed area are + * called chunks. Each chunk needs a descriptor which is stored outside of the + * managed area. * * @{ */ +/** + * @brief Red-black heap chunk descriptor. + */ typedef struct { + /** + * This chain node can be used in two chains + * - the chain of spare chunk descriptors and + * - the chain of free chunks in the managed memory area. + * + * In case this chain node is not part of a chain, the chunk represents a + * used chunk in the managed memory area. + */ rtems_chain_node chain_node; + + /** + * Tree node for chunks that represent a part of the managed memory area. + * These chunks are either free or used. + */ rtems_rbtree_node tree_node; + + /** + * Begin address of the chunk. The address alignment it specified in the + * @ref rtems_rbheap_control. + */ uintptr_t begin; + + /** + * Size of the chunk in bytes. + */ uintptr_t size; -} rtems_rbheap_page; +} rtems_rbheap_chunk; typedef struct rtems_rbheap_control rtems_rbheap_control; -typedef void (*rtems_rbheap_extend_page_pool)(rtems_rbheap_control *control); +/** + * @brief Handler to extend the available chunk descriptors. + * + * This handler is called when no more chunk descriptors are available. An + * example implementation is this: + * + * @code + * void extend_descriptors_with_malloc(rtems_rbheap_control *control) + * { + * rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk)); + * + * if (chunk != NULL) { + * rtems_rbheap_add_to_spare_descriptor_chain(control, chunk); + * } + * } + * @endcode + * + * @see rtems_rbheap_extend_descriptors_never() and + * rtems_rbheap_extend_descriptors_with_malloc(). + */ +typedef void (*rtems_rbheap_extend_descriptors)(rtems_rbheap_control *control); +/** + * @brief Red-black heap control. + */ struct rtems_rbheap_control { - rtems_chain_control free_chain; - rtems_chain_control pool_chain; - rtems_rbtree_control page_tree; - uintptr_t page_alignment; - rtems_rbheap_extend_page_pool extend_page_pool; + /** + * Chain of free chunks in the managed memory area. + */ + rtems_chain_control free_chunk_chain; + + /** + * Chain of free chunk descriptors. Descriptors are consumed during + * allocation and may be produced during free if contiguous chunks can be + * coalesced. In case of descriptor starvation the @ref extend_descriptors + * handler will be called. + */ + rtems_chain_control spare_descriptor_chain; + + /** + * Tree of chunks representing the state of the managed memory area. + */ + rtems_rbtree_control chunk_tree; + + /** + * Minimum chunk begin alignment in bytes. + */ + uintptr_t alignment; + + /** + * Handler to extend the available chunk descriptors. + */ + rtems_rbheap_extend_descriptors extend_descriptors; + + /** + * User specified argument handler for private handler data. + */ void *handler_arg; }; +/** + * @brief Initializes the red-black tree heap @a control. + * + * @param[in, out] control The red-black tree heap. + * @param[in] area_begin The managed memory area begin. + * @param[in] area_size The managed memory area size. + * @param[in] alignment The minimum chunk alignment. + * @param[in] extend_descriptors The handler to extend the available chunk + * descriptors. + * @param[in] handler_arg The handler argument. + * + * @retval RTEMS_SUCCESSFUL Successful operation. + * @retval RTEMS_INVALID_NUMBER The alignment is not positive. + * @retval RTEMS_INVALID_ADDRESS The memory area is invalid. + * @retval RTEMS_NO_MEMORY Not enough chunk descriptors. + */ rtems_status_code rtems_rbheap_initialize( rtems_rbheap_control *control, void *area_begin, uintptr_t area_size, - uintptr_t page_alignment, - rtems_rbheap_extend_page_pool extend_page_pool, + uintptr_t alignment, + rtems_rbheap_extend_descriptors extend_descriptors, void *handler_arg ); +/** + * @brief Allocates a chunk of memory of at least @a size bytes from the + * red-black tree heap @a control. + * + * The chunk begin is aligned by the value specified in + * rtems_rbheap_initialize(). + * + * @param[in, out] control The red-black tree heap. + * @param[in] size The requested chunk size in bytes. + * + * @retval NULL Not enough free space in the heap. + * @retval otherwise Pointer to allocated chunk of memory. + */ void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size); +/** + * @brief Frees a chunk of memory @a ptr allocated from the red-black tree heap + * @a control. + * + * @param[in, out] control The red-black tree heap. + * @param[in] ptr The pointer to the chunk of memory. + * + * @retval RTEMS_SUCCESSFUL Successful operation. + * @retval RTEMS_INVALID_ID The chunk of memory is not a valid chunk in the + * red-black tree heap. + * @retval RTEMS_INCORRECT_STATE The chunk of memory is not in the right state. + */ rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr); -static inline rtems_chain_control *rtems_rbheap_get_pool_chain( +static inline rtems_chain_control *rtems_rbheap_get_spare_descriptor_chain( rtems_rbheap_control *control ) { - return &control->pool_chain; + return &control->spare_descriptor_chain; } -static inline void rtems_rbheap_set_extend_page_pool( +static inline void rtems_rbheap_add_to_spare_descriptor_chain( rtems_rbheap_control *control, - rtems_rbheap_extend_page_pool extend_page_pool + rtems_rbheap_chunk *chunk ) { - control->extend_page_pool = extend_page_pool; + rtems_chain_control *chain = + rtems_rbheap_get_spare_descriptor_chain(control); + + rtems_chain_prepend_unprotected(chain, &chunk->chain_node); +} + +static inline void rtems_rbheap_set_extend_descriptors( + rtems_rbheap_control *control, + rtems_rbheap_extend_descriptors extend_descriptors +) +{ + control->extend_descriptors = extend_descriptors; } static inline void *rtems_rbheap_get_handler_arg( @@ -107,20 +238,28 @@ static inline void rtems_rbheap_set_handler_arg( control->handler_arg = handler_arg; } -void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control); +/** + * @brief Chunk descriptor extend handler that does nothing. + */ +void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control); -void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control); +/** + * @brief Chunk descriptor extend handler that uses malloc(). + */ +void rtems_rbheap_extend_descriptors_with_malloc( + rtems_rbheap_control *control +); /** @} */ /* Private API */ -#define rtems_rbheap_page_of_node(node) \ - rtems_rbtree_container_of(node, rtems_rbheap_page, tree_node) +#define rtems_rbheap_chunk_of_node(node) \ + rtems_rbtree_container_of(node, rtems_rbheap_chunk, tree_node) -static inline bool rtems_rbheap_is_page_free(const rtems_rbheap_page *page) +static inline bool rtems_rbheap_is_chunk_free(const rtems_rbheap_chunk *chunk) { - return !rtems_chain_is_node_off_chain(&page->chain_node); + return !rtems_chain_is_node_off_chain(&chunk->chain_node); } #ifdef __cplusplus |