From 5c51ba1333d96e2ada2c374ba22b551d179e6685 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Mon, 16 Apr 2012 10:38:31 +0200 Subject: rbheap: API changes and documentation --- cpukit/sapi/include/rtems/rbheap.h | 187 ++++++++++++++++++++++++++++++----- cpukit/sapi/src/rbheap.c | 189 ++++++++++++++++++------------------ testsuites/libtests/rbheap01/init.c | 89 +++++++++-------- 3 files changed, 309 insertions(+), 156 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 diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c index 798632520d..7facf4f9af 100644 --- a/cpukit/sapi/src/rbheap.c +++ b/cpukit/sapi/src/rbheap.c @@ -28,96 +28,96 @@ #include -static uintptr_t align_up(uintptr_t page_alignment, uintptr_t value) +static uintptr_t align_up(uintptr_t alignment, uintptr_t value) { - uintptr_t excess = value % page_alignment; + uintptr_t excess = value % alignment; if (excess > 0) { - value += page_alignment - excess; + value += alignment - excess; } return value; } -static uintptr_t align_down(uintptr_t page_alignment, uintptr_t value) +static uintptr_t align_down(uintptr_t alignment, uintptr_t value) { - uintptr_t excess = value % page_alignment; + uintptr_t excess = value % alignment; return value - excess; } -static int page_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b) +static int chunk_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b) { - const rtems_rbheap_page *left = rtems_rbheap_page_of_node(a); - const rtems_rbheap_page *right = rtems_rbheap_page_of_node(b); + const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a); + const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b); return (int) (left->begin - right->begin); } -static rtems_rbheap_page *get_page(rtems_rbheap_control *control) +static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control) { - rtems_chain_control *pool_chain = &control->pool_chain; - rtems_chain_node *page = rtems_chain_get(pool_chain); + rtems_chain_control *chain = &control->spare_descriptor_chain; + rtems_chain_node *chunk = rtems_chain_get_unprotected(chain); - if (page == NULL) { - (*control->extend_page_pool)(control); - page = rtems_chain_get(pool_chain); + if (chunk == NULL) { + (*control->extend_descriptors)(control); + chunk = rtems_chain_get_unprotected(chain); } - return (rtems_rbheap_page *) page; + return (rtems_rbheap_chunk *) chunk; } static void add_to_chain( rtems_chain_control *chain, - rtems_rbheap_page *page + rtems_rbheap_chunk *chunk ) { - rtems_chain_prepend_unprotected(chain, &page->chain_node); + rtems_chain_prepend_unprotected(chain, &chunk->chain_node); } static void insert_into_tree( rtems_rbtree_control *tree, - rtems_rbheap_page *page + rtems_rbheap_chunk *chunk ) { - _RBTree_Insert_unprotected(tree, &page->tree_node); + _RBTree_Insert_unprotected(tree, &chunk->tree_node); } 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 ) { rtems_status_code sc = RTEMS_SUCCESSFUL; - if (page_alignment > 0) { + if (alignment > 0) { uintptr_t begin = (uintptr_t) area_begin; uintptr_t end = begin + area_size; - uintptr_t aligned_begin = align_up(page_alignment, begin); - uintptr_t aligned_end = align_down(page_alignment, end); + uintptr_t aligned_begin = align_up(alignment, begin); + uintptr_t aligned_end = align_down(alignment, end); if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) { - rtems_chain_control *free_chain = &control->free_chain; - rtems_rbtree_control *page_tree = &control->page_tree; - rtems_rbheap_page *first = NULL; + rtems_chain_control *free_chain = &control->free_chunk_chain; + rtems_rbtree_control *chunk_tree = &control->chunk_tree; + rtems_rbheap_chunk *first = NULL; rtems_chain_initialize_empty(free_chain); - rtems_chain_initialize_empty(&control->pool_chain); - rtems_rbtree_initialize_empty(page_tree, page_compare, true); - control->page_alignment = page_alignment; + rtems_chain_initialize_empty(&control->spare_descriptor_chain); + rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true); + control->alignment = alignment; control->handler_arg = handler_arg; - control->extend_page_pool = extend_page_pool; + control->extend_descriptors = extend_descriptors; - first = get_page(control); + first = get_chunk(control); if (first != NULL) { first->begin = aligned_begin; first->size = aligned_end - aligned_begin; add_to_chain(free_chain, first); - insert_into_tree(page_tree, first); + insert_into_tree(chunk_tree, first); } else { sc = RTEMS_NO_MEMORY; } @@ -131,20 +131,20 @@ rtems_status_code rtems_rbheap_initialize( return sc; } -static rtems_rbheap_page *search_free_page( +static rtems_rbheap_chunk *search_free_chunk( rtems_chain_control *free_chain, size_t size ) { rtems_chain_node *current = rtems_chain_first(free_chain); const rtems_chain_node *tail = rtems_chain_tail(free_chain); - rtems_rbheap_page *big_enough = NULL; + rtems_rbheap_chunk *big_enough = NULL; while (current != tail && big_enough == NULL) { - rtems_rbheap_page *free_page = (rtems_rbheap_page *) current; + rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current; - if (free_page->size >= size) { - big_enough = free_page; + if (free_chunk->size >= size) { + big_enough = free_chunk; } current = rtems_chain_next(current); @@ -156,34 +156,34 @@ static rtems_rbheap_page *search_free_page( void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size) { void *ptr = NULL; - rtems_chain_control *free_chain = &control->free_chain; - rtems_rbtree_control *page_tree = &control->page_tree; - uintptr_t page_alignment = control->page_alignment; - uintptr_t aligned_size = align_up(page_alignment, size); + rtems_chain_control *free_chain = &control->free_chunk_chain; + rtems_rbtree_control *chunk_tree = &control->chunk_tree; + uintptr_t alignment = control->alignment; + uintptr_t aligned_size = align_up(alignment, size); if (size > 0 && size <= aligned_size) { - rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size); + rtems_rbheap_chunk *free_chunk = search_free_chunk(free_chain, aligned_size); - if (free_page != NULL) { - uintptr_t free_size = free_page->size; + if (free_chunk != NULL) { + uintptr_t free_size = free_chunk->size; if (free_size > aligned_size) { - rtems_rbheap_page *new_page = get_page(control); + rtems_rbheap_chunk *new_chunk = get_chunk(control); - if (new_page != NULL) { + if (new_chunk != NULL) { uintptr_t new_free_size = free_size - aligned_size; - free_page->size = new_free_size; - new_page->begin = free_page->begin + new_free_size; - new_page->size = aligned_size; - rtems_chain_set_off_chain(&new_page->chain_node); - insert_into_tree(page_tree, new_page); - ptr = (void *) new_page->begin; + free_chunk->size = new_free_size; + new_chunk->begin = free_chunk->begin + new_free_size; + new_chunk->size = aligned_size; + rtems_chain_set_off_chain(&new_chunk->chain_node); + insert_into_tree(chunk_tree, new_chunk); + ptr = (void *) new_chunk->begin; } } else { - rtems_chain_extract_unprotected(&free_page->chain_node); - rtems_chain_set_off_chain(&free_page->chain_node); - ptr = (void *) free_page->begin; + rtems_chain_extract_unprotected(&free_chunk->chain_node); + rtems_chain_set_off_chain(&free_chunk->chain_node); + ptr = (void *) free_chunk->begin; } } } @@ -191,38 +191,38 @@ void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size) return ptr; } -#define NULL_PAGE rtems_rbheap_page_of_node(NULL) +#define NULL_PAGE rtems_rbheap_chunk_of_node(NULL) -static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key) +static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key) { - rtems_rbheap_page page = { .begin = key }; + rtems_rbheap_chunk chunk = { .begin = key }; - return rtems_rbheap_page_of_node( - _RBTree_Find_unprotected(page_tree, &page.tree_node) + return rtems_rbheap_chunk_of_node( + _RBTree_Find_unprotected(chunk_tree, &chunk.tree_node) ); } -static rtems_rbheap_page *get_next( - const rtems_rbtree_control *page_tree, - const rtems_rbheap_page *page, +static rtems_rbheap_chunk *get_next( + const rtems_rbtree_control *chunk_tree, + const rtems_rbheap_chunk *chunk, RBTree_Direction dir ) { - return rtems_rbheap_page_of_node( - _RBTree_Next_unprotected(page_tree, &page->tree_node, dir) + return rtems_rbheap_chunk_of_node( + _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir) ); } static void check_and_merge( rtems_chain_control *free_chain, - rtems_rbtree_control *page_tree, - rtems_rbheap_page *a, - rtems_rbheap_page *b + rtems_rbtree_control *chunk_tree, + rtems_rbheap_chunk *a, + rtems_rbheap_chunk *b ) { - if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) { + if (b != NULL_PAGE && rtems_rbheap_is_chunk_free(b)) { if (b->begin < a->begin) { - rtems_rbheap_page *t = a; + rtems_rbheap_chunk *t = a; a = b; b = t; @@ -231,47 +231,48 @@ static void check_and_merge( a->size += b->size; rtems_chain_extract_unprotected(&b->chain_node); add_to_chain(free_chain, b); - _RBTree_Extract_unprotected(page_tree, &b->tree_node); + _RBTree_Extract_unprotected(chunk_tree, &b->tree_node); } } rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr) { rtems_status_code sc = RTEMS_SUCCESSFUL; - rtems_chain_control *free_chain = &control->free_chain; - rtems_rbtree_control *page_tree = &control->page_tree; - rtems_rbheap_page *page = find(page_tree, (uintptr_t) ptr); - - if (page != NULL_PAGE) { - if (!rtems_rbheap_is_page_free(page)) { - rtems_rbheap_page *pred = get_next(page_tree, page, RBT_LEFT); - rtems_rbheap_page *succ = get_next(page_tree, page, RBT_RIGHT); - - check_and_merge(free_chain, page_tree, page, succ); - add_to_chain(free_chain, page); - check_and_merge(free_chain, page_tree, page, pred); + + if (ptr != NULL) { + rtems_chain_control *free_chain = &control->free_chunk_chain; + rtems_rbtree_control *chunk_tree = &control->chunk_tree; + rtems_rbheap_chunk *chunk = find(chunk_tree, (uintptr_t) ptr); + + if (chunk != NULL_PAGE) { + if (!rtems_rbheap_is_chunk_free(chunk)) { + rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT); + rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT); + + check_and_merge(free_chain, chunk_tree, chunk, succ); + add_to_chain(free_chain, chunk); + check_and_merge(free_chain, chunk_tree, chunk, pred); + } else { + sc = RTEMS_INCORRECT_STATE; + } } else { - sc = RTEMS_INCORRECT_STATE; + sc = RTEMS_INVALID_ID; } - } else { - sc = RTEMS_INVALID_ID; } return sc; } -void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control) +void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control) { /* Do nothing */ } -void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control) +void rtems_rbheap_extend_descriptors_with_malloc(rtems_rbheap_control *control) { - rtems_rbheap_page *page = malloc(sizeof(*page)); - - if (page != NULL) { - rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control); + rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk)); - add_to_chain(pool_chain, page); + if (chunk != NULL) { + rtems_rbheap_add_to_spare_descriptor_chain(control, chunk); } } diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c index a66cc24273..ce180d8541 100644 --- a/testsuites/libtests/rbheap01/init.c +++ b/testsuites/libtests/rbheap01/init.c @@ -27,26 +27,27 @@ static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1]; -static rtems_rbheap_page pages [PAGE_COUNT]; +static rtems_rbheap_chunk chunks [PAGE_COUNT]; -static void extend_page_pool(rtems_rbheap_control *control) +static void extend_descriptors(rtems_rbheap_control *control) { - rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control); + rtems_chain_control *chain = + rtems_rbheap_get_spare_descriptor_chain(control); - rtems_rbheap_set_extend_page_pool( + rtems_rbheap_set_extend_descriptors( control, - rtems_rbheap_extend_page_pool_never + rtems_rbheap_extend_descriptors_never ); rtems_chain_initialize( - pool_chain, - pages, + chain, + chunks, PAGE_COUNT, - sizeof(pages [0]) + sizeof(chunks [0]) ); } -static uintptr_t idx(const rtems_rbheap_page *page) +static uintptr_t idx(const rtems_rbheap_chunk *chunk) { uintptr_t base = (uintptr_t) area; uintptr_t excess = base % PAGE_SIZE; @@ -55,7 +56,7 @@ static uintptr_t idx(const rtems_rbheap_page *page) base += PAGE_SIZE - excess; } - return (page->begin - base) / PAGE_SIZE; + return (chunk->begin - base) / PAGE_SIZE; } typedef struct { @@ -63,22 +64,22 @@ typedef struct { const uintptr_t *index_end; const bool *free_current; const bool *free_end; -} page_visitor_context; +} chunk_visitor_context; -static bool page_visitor( +static bool chunk_visitor( const RBTree_Node *node, RBTree_Direction dir, void *visitor_arg ) { - rtems_rbheap_page *page = rtems_rbheap_page_of_node(node); - page_visitor_context *context = visitor_arg; + rtems_rbheap_chunk *chunk = rtems_rbheap_chunk_of_node(node); + chunk_visitor_context *context = visitor_arg; rtems_test_assert(context->index_current != context->index_end); rtems_test_assert(context->free_current != context->free_end); - rtems_test_assert(idx(page) == *context->index_current); - rtems_test_assert(rtems_rbheap_is_page_free(page) == *context->free_current); + rtems_test_assert(idx(chunk) == *context->index_current); + rtems_test_assert(rtems_rbheap_is_chunk_free(chunk) == *context->free_current); ++context->index_current; ++context->free_current; @@ -86,7 +87,7 @@ static bool page_visitor( return false; } -static void test_init_page_alignment(void) +static void test_init_chunk_alignment(void) { rtems_status_code sc = RTEMS_SUCCESSFUL; rtems_rbheap_control control; @@ -96,7 +97,7 @@ static void test_init_page_alignment(void) area, sizeof(area), 0, - extend_page_pool, + extend_descriptors, NULL ); rtems_test_assert(sc == RTEMS_INVALID_NUMBER); @@ -112,7 +113,7 @@ static void test_init_begin_greater_than_end(void) (void *) PAGE_SIZE, (uintptr_t) -PAGE_SIZE, PAGE_SIZE, - extend_page_pool, + extend_descriptors, NULL ); rtems_test_assert(sc == RTEMS_INVALID_ADDRESS); @@ -128,7 +129,7 @@ static void test_init_begin_greater_than_aligned_begin(void) (void *) -(PAGE_SIZE / 2), PAGE_SIZE, PAGE_SIZE, - extend_page_pool, + extend_descriptors, NULL ); rtems_test_assert(sc == RTEMS_INVALID_ADDRESS); @@ -144,13 +145,13 @@ static void test_init_aligned_begin_greater_than_aligned_end(void) (void *) PAGE_SIZE, PAGE_SIZE / 2, PAGE_SIZE, - extend_page_pool, + extend_descriptors, NULL ); rtems_test_assert(sc == RTEMS_INVALID_ADDRESS); } -static void test_init_empty_page_pool(void) +static void test_init_empty_descriptors(void) { rtems_status_code sc = RTEMS_SUCCESSFUL; rtems_rbheap_control control; @@ -160,13 +161,13 @@ static void test_init_empty_page_pool(void) (void *) PAGE_SIZE, PAGE_SIZE, PAGE_SIZE, - rtems_rbheap_extend_page_pool_never, + rtems_rbheap_extend_descriptors_never, NULL ); rtems_test_assert(sc == RTEMS_NO_MEMORY); } -static void test_page_tree( +static void test_chunk_tree( const rtems_rbheap_control *control, const uintptr_t *index_begin, const uintptr_t *index_end, @@ -174,7 +175,7 @@ static void test_page_tree( const bool *free_end ) { - page_visitor_context context = { + chunk_visitor_context context = { .index_current = index_begin, .index_end = index_end, .free_current = free_begin, @@ -182,15 +183,15 @@ static void test_page_tree( }; _RBTree_Iterate_unprotected( - &control->page_tree, + &control->chunk_tree, RBT_RIGHT, - page_visitor, + chunk_visitor, &context ); } #define TEST_PAGE_TREE(control, indices, frees) \ - test_page_tree( \ + test_chunk_tree( \ control, \ indices, \ &indices [sizeof(indices) / sizeof(indices [0])], \ @@ -214,7 +215,7 @@ static void test_init_successful(rtems_rbheap_control *control) area, sizeof(area), PAGE_SIZE, - extend_page_pool, + extend_descriptors, NULL ); rtems_test_assert(sc == RTEMS_SUCCESSFUL); @@ -276,7 +277,7 @@ static void test_alloc_zero(void) TEST_PAGE_TREE(&control, indices, frees); } -static void test_alloc_huge_page(void) +static void test_alloc_huge_chunk(void) { static const uintptr_t indices [] = { 0 @@ -296,7 +297,7 @@ static void test_alloc_huge_page(void) TEST_PAGE_TREE(&control, indices, frees); } -static void test_alloc_one_page(void) +static void test_alloc_one_chunk(void) { static const uintptr_t indices_0 [] = { 0 @@ -328,7 +329,7 @@ static void test_alloc_one_page(void) TEST_PAGE_TREE(&control, indices_1, frees_1); } -static void test_alloc_many_pages(void) +static void test_alloc_many_chunks(void) { static const uintptr_t indices_0 [] = { 0, @@ -385,7 +386,7 @@ static void test_alloc_many_pages(void) TEST_PAGE_TREE(&control, indices_1, frees_1); } -static void test_free_invalid(void) +static void test_free_null(void) { rtems_status_code sc = RTEMS_SUCCESSFUL; rtems_rbheap_control control; @@ -393,6 +394,17 @@ static void test_free_invalid(void) test_init_successful(&control); sc = rtems_rbheap_free(&control, NULL); + rtems_test_assert(sc == RTEMS_SUCCESSFUL); +} + +static void test_free_invalid(void) +{ + rtems_status_code sc = RTEMS_SUCCESSFUL; + rtems_rbheap_control control; + + test_init_successful(&control); + + sc = rtems_rbheap_free(&control, (void *) 1); rtems_test_assert(sc == RTEMS_INVALID_ID); } @@ -539,16 +551,17 @@ static void Init(rtems_task_argument arg) { puts("\n\n*** TEST RBHEAP 1 ***"); - test_init_page_alignment(); + test_init_chunk_alignment(); test_init_begin_greater_than_end(); test_init_begin_greater_than_aligned_begin(); test_init_aligned_begin_greater_than_aligned_end(); - test_init_empty_page_pool(); + test_init_empty_descriptors(); test_alloc_and_free_one(); test_alloc_zero(); - test_alloc_huge_page(); - test_alloc_one_page(); - test_alloc_many_pages(); + test_alloc_huge_chunk(); + test_alloc_one_chunk(); + test_alloc_many_chunks(); + test_free_null(); test_free_invalid(); test_free_double(); test_free_merge_left_or_right(true); -- cgit v1.2.3