[PATCH] rbheap: API changes and documentation
Gedare Bloom
gedare at rtems.org
Mon Apr 16 15:30:48 UTC 2012
On Mon, Apr 16, 2012 at 4:39 AM, <sebastian.huber at embedded-brains.de> wrote:
> From: Sebastian Huber <sebastian.huber at embedded-brains.de>
>
> ---
> cpukit/sapi/include/rtems/rbheap.h | 129 ++++++++++++++++++++-----
> cpukit/sapi/src/rbheap.c | 181 ++++++++++++++++++-----------------
> testsuites/libtests/rbheap01/init.c | 88 ++++++++++-------
> 3 files changed, 247 insertions(+), 151 deletions(-)
>
> diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
> index be1eec6..47620d0 100644
> --- a/cpukit/sapi/include/rtems/rbheap.h
> +++ b/cpukit/sapi/include/rtems/rbheap.h
> @@ -36,10 +36,14 @@ 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. 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.
> *
> * @{
> */
> @@ -49,47 +53,118 @@ typedef struct {
> rtems_rbtree_node tree_node;
> uintptr_t begin;
> 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_free_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);
>
> 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;
> + rtems_chain_control free_descriptor_chain;
> + rtems_rbtree_control chunk_tree;
> + uintptr_t alignment;
> + rtems_rbheap_extend_descriptors extend_descriptors;
> void *handler_arg;
> };
>
Please differentiate free_chain from free_descriptor_chain. I think
this is really about free (available) chunks versus free chunk
descriptors? A little bit of code documentation for the structure
fields might help here. Thanks for adding the doxygen to the rest of
the function prototypes it helps a lot.
> +/**
> + * @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_free_descriptor_chain(
> rtems_rbheap_control *control
> )
> {
> - return &control->pool_chain;
> + return &control->free_descriptor_chain;
> }
>
> -static inline void rtems_rbheap_set_extend_page_pool(
> +static inline void rtems_rbheap_add_to_free_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_free_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 +182,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 7986325..c527c52 100644
> --- a/cpukit/sapi/src/rbheap.c
> +++ b/cpukit/sapi/src/rbheap.c
> @@ -28,96 +28,96 @@
>
> #include <stdlib.h>
>
> -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 *free_descriptor_chain = &control->free_descriptor_chain;
> + rtems_chain_node *chunk = rtems_chain_get_unprotected(free_descriptor_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(free_descriptor_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_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->free_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);
> @@ -157,33 +157,33 @@ 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_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);
> + if (ptr != NULL) {
> + rtems_chain_control *free_chain = &control->free_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, page_tree, page, succ);
> - add_to_chain(free_chain, page);
> - check_and_merge(free_chain, page_tree, page, pred);
> + 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_free_descriptor_chain(control, chunk);
> }
> }
> diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
> index a66cc24..171cfd2 100644
> --- a/testsuites/libtests/rbheap01/init.c
> +++ b/testsuites/libtests/rbheap01/init.c
> @@ -27,26 +27,26 @@
>
> 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_free_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 +55,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 +63,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 +86,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 +96,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 +112,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 +128,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 +144,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 +160,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 +174,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 +182,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 +214,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 +276,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 +296,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 +328,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 +385,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 +393,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 +550,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);
> --
> 1.6.4.2
>
> _______________________________________________
> rtems-devel mailing list
> rtems-devel at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-devel
More information about the devel
mailing list