[rtems commit] rbheap: New files
Gedare Bloom
gedare at rtems.org
Sat Apr 14 16:20:31 UTC 2012
I have a couple concerns.
First is the naming "rbheap";. I see it is implementing a memory
manager using the rbtree and a couple chain controls. It's not really
a heap so much as a custom free page allocator.
Second is the code placement. I'm not convinced this is best to just
shim into the sapi layer. The functionality is reminiscent of the
Region Manager. What functionality is missing that this code is unable
to use existing classic or score services to achieve? I have a feeling
we could generalize the approach taken here by implementing an Arena
Manager somewhere.
Third is the use of the word "pages". Unless we are referring to
fixed-size ranges of virtual memory I think we should avoid this word
since it has a fairly common technical meaning and connotation as an
OS concept.
Fourth is the lack of documentation. This is an addition to the public
API and should be reflected somewhere in docu and the release notes.
Fifth is the lack of review before committing ;)
-Gedare
On Wed, Apr 11, 2012 at 5:23 AM, Sebastian Huber <sebh at rtems.org> wrote:
> Module: rtems
> Branch: master
> Commit: e75263083e83cac921475d0a89d8b3b398f9b902
> Changeset: http://git.rtems.org/rtems/commit/?id=e75263083e83cac921475d0a89d8b3b398f9b902
>
> Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
> Date: Tue Apr 10 11:19:39 2012 +0200
>
> rbheap: New files
>
> 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.
>
> ---
>
> cpukit/sapi/Makefile.am | 3 +-
> cpukit/sapi/include/rtems/rbheap.h | 130 +++++++
> cpukit/sapi/preinstall.am | 4 +
> cpukit/sapi/src/rbheap.c | 277 ++++++++++++++
> testsuites/libtests/Makefile.am | 1 +
> testsuites/libtests/configure.ac | 1 +
> testsuites/libtests/rbheap01/Makefile.am | 19 +
> testsuites/libtests/rbheap01/init.c | 571 +++++++++++++++++++++++++++++
> testsuites/libtests/rbheap01/rbheap01.doc | 11 +
> testsuites/libtests/rbheap01/rbheap01.scn | 2 +
> 10 files changed, 1018 insertions(+), 1 deletions(-)
>
> diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
> index 9b7ad53..4536280 100644
> --- a/cpukit/sapi/Makefile.am
> +++ b/cpukit/sapi/Makefile.am
> @@ -16,6 +16,7 @@ include_rtems_HEADERS += include/rtems/init.h
> include_rtems_HEADERS += include/rtems/io.h
> include_rtems_HEADERS += include/rtems/mptables.h
> include_rtems_HEADERS += include/rtems/cbs.h
> +include_rtems_HEADERS += include/rtems/rbheap.h
> include_rtems_HEADERS += include/rtems/rbtree.h
> include_rtems_HEADERS += include/rtems/sptables.h
>
> @@ -38,7 +39,7 @@ libsapi_a_SOURCES = src/debug.c src/extension.c src/extensioncreate.c \
> src/iounregisterdriver.c src/iowrite.c src/posixapi.c \
> src/rtemsapi.c src/extensiondata.c src/getversionstring.c \
> src/chainappendnotify.c src/chaingetnotify.c src/chaingetwait.c \
> - src/chainprependnotify.c
> + src/chainprependnotify.c src/rbheap.c
> libsapi_a_CPPFLAGS = $(AM_CPPFLAGS)
>
> include $(srcdir)/preinstall.am
> diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
> new file mode 100644
> index 0000000..be1eec6
> --- /dev/null
> +++ b/cpukit/sapi/include/rtems/rbheap.h
> @@ -0,0 +1,130 @@
> +/**
> + * @file
> + *
> + * @ingroup RBHeap
> + *
> + * @brief Red-Black Tree Heap API.
> + */
> +
> +/*
> + * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Obere Lagerstr. 30
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.com/license/LICENSE.
> + */
> +
> +#ifndef _RTEMS_RBHEAP_H
> +#define _RTEMS_RBHEAP_H
> +
> +#include <rtems.h>
> +#include <rtems/chain.h>
> +#include <rtems/rbtree.h>
> +
> +#ifdef __cplusplus
> +extern "C" {
> +#endif
> +
> +/**
> + * @defgroup RBHeap Red-Black Tree Heap
> + *
> + * @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.
> + *
> + * @{
> + */
> +
> +typedef struct {
> + rtems_chain_node chain_node;
> + rtems_rbtree_node tree_node;
> + uintptr_t begin;
> + uintptr_t size;
> +} rtems_rbheap_page;
> +
> +typedef struct rtems_rbheap_control rtems_rbheap_control;
> +
> +typedef void (*rtems_rbheap_extend_page_pool)(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;
> + void *handler_arg;
> +};
> +
> +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,
> + void *handler_arg
> +);
> +
> +void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size);
> +
> +rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr);
> +
> +static inline rtems_chain_control *rtems_rbheap_get_pool_chain(
> + rtems_rbheap_control *control
> +)
> +{
> + return &control->pool_chain;
> +}
> +
> +static inline void rtems_rbheap_set_extend_page_pool(
> + rtems_rbheap_control *control,
> + rtems_rbheap_extend_page_pool extend_page_pool
> +)
> +{
> + control->extend_page_pool = extend_page_pool;
> +}
> +
> +static inline void *rtems_rbheap_get_handler_arg(
> + const rtems_rbheap_control *control
> +)
> +{
> + return control->handler_arg;
> +}
> +
> +static inline void rtems_rbheap_set_handler_arg(
> + rtems_rbheap_control *control,
> + void *handler_arg
> +)
> +{
> + control->handler_arg = handler_arg;
> +}
> +
> +void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control);
> +
> +void rtems_rbheap_extend_page_pool_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)
> +
> +static inline bool rtems_rbheap_is_page_free(const rtems_rbheap_page *page)
> +{
> + return !rtems_chain_is_node_off_chain(&page->chain_node);
> +}
> +
> +#ifdef __cplusplus
> +}
> +#endif
> +
> +#endif /* _RTEMS_RBHEAP_H */
> diff --git a/cpukit/sapi/preinstall.am b/cpukit/sapi/preinstall.am
> index 5ce9966..e7c8e2a 100644
> --- a/cpukit/sapi/preinstall.am
> +++ b/cpukit/sapi/preinstall.am
> @@ -64,6 +64,10 @@ $(PROJECT_INCLUDE)/rtems/cbs.h: include/rtems/cbs.h $(PROJECT_INCLUDE)/rtems/$(d
> $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/cbs.h
> PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/cbs.h
>
> +$(PROJECT_INCLUDE)/rtems/rbheap.h: include/rtems/rbheap.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
> + $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbheap.h
> +PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbheap.h
> +
> $(PROJECT_INCLUDE)/rtems/rbtree.h: include/rtems/rbtree.h $(PROJECT_INCLUDE)/rtems/$(dirstamp)
> $(INSTALL_DATA) $< $(PROJECT_INCLUDE)/rtems/rbtree.h
> PREINSTALL_FILES += $(PROJECT_INCLUDE)/rtems/rbtree.h
> diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
> new file mode 100644
> index 0000000..7986325
> --- /dev/null
> +++ b/cpukit/sapi/src/rbheap.c
> @@ -0,0 +1,277 @@
> +/**
> + * @file
> + *
> + * @ingroup RBHeap
> + *
> + * @brief Red-Black Tree Heap implementation.
> + */
> +
> +/*
> + * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Obere Lagerstr. 30
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.com/license/LICENSE.
> + */
> +
> +#if HAVE_CONFIG_H
> + #include "config.h"
> +#endif
> +
> +#include <rtems/rbheap.h>
> +
> +#include <stdlib.h>
> +
> +static uintptr_t align_up(uintptr_t page_alignment, uintptr_t value)
> +{
> + uintptr_t excess = value % page_alignment;
> +
> + if (excess > 0) {
> + value += page_alignment - excess;
> + }
> +
> + return value;
> +}
> +
> +static uintptr_t align_down(uintptr_t page_alignment, uintptr_t value)
> +{
> + uintptr_t excess = value % page_alignment;
> +
> + return value - excess;
> +}
> +
> +static int page_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);
> +
> + return (int) (left->begin - right->begin);
> +}
> +
> +static rtems_rbheap_page *get_page(rtems_rbheap_control *control)
> +{
> + rtems_chain_control *pool_chain = &control->pool_chain;
> + rtems_chain_node *page = rtems_chain_get(pool_chain);
> +
> + if (page == NULL) {
> + (*control->extend_page_pool)(control);
> + page = rtems_chain_get(pool_chain);
> + }
> +
> + return (rtems_rbheap_page *) page;
> +}
> +
> +static void add_to_chain(
> + rtems_chain_control *chain,
> + rtems_rbheap_page *page
> +)
> +{
> + rtems_chain_prepend_unprotected(chain, &page->chain_node);
> +}
> +
> +static void insert_into_tree(
> + rtems_rbtree_control *tree,
> + rtems_rbheap_page *page
> +)
> +{
> + _RBTree_Insert_unprotected(tree, &page->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,
> + void *handler_arg
> +)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> +
> + if (page_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);
> +
> + 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_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;
> + control->handler_arg = handler_arg;
> + control->extend_page_pool = extend_page_pool;
> +
> + first = get_page(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);
> + } else {
> + sc = RTEMS_NO_MEMORY;
> + }
> + } else {
> + sc = RTEMS_INVALID_ADDRESS;
> + }
> + } else {
> + sc = RTEMS_INVALID_NUMBER;
> + }
> +
> + return sc;
> +}
> +
> +static rtems_rbheap_page *search_free_page(
> + 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;
> +
> + while (current != tail && big_enough == NULL) {
> + rtems_rbheap_page *free_page = (rtems_rbheap_page *) current;
> +
> + if (free_page->size >= size) {
> + big_enough = free_page;
> + }
> +
> + current = rtems_chain_next(current);
> + }
> +
> + return big_enough;
> +}
> +
> +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);
> +
> + if (size > 0 && size <= aligned_size) {
> + rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size);
> +
> + if (free_page != NULL) {
> + uintptr_t free_size = free_page->size;
> +
> + if (free_size > aligned_size) {
> + rtems_rbheap_page *new_page = get_page(control);
> +
> + if (new_page != 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;
> + }
> + } else {
> + rtems_chain_extract_unprotected(&free_page->chain_node);
> + rtems_chain_set_off_chain(&free_page->chain_node);
> + ptr = (void *) free_page->begin;
> + }
> + }
> + }
> +
> + return ptr;
> +}
> +
> +#define NULL_PAGE rtems_rbheap_page_of_node(NULL)
> +
> +static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key)
> +{
> + rtems_rbheap_page page = { .begin = key };
> +
> + return rtems_rbheap_page_of_node(
> + _RBTree_Find_unprotected(page_tree, &page.tree_node)
> + );
> +}
> +
> +static rtems_rbheap_page *get_next(
> + const rtems_rbtree_control *page_tree,
> + const rtems_rbheap_page *page,
> + RBTree_Direction dir
> +)
> +{
> + return rtems_rbheap_page_of_node(
> + _RBTree_Next_unprotected(page_tree, &page->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
> +)
> +{
> + if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) {
> + if (b->begin < a->begin) {
> + rtems_rbheap_page *t = a;
> +
> + a = b;
> + b = t;
> + }
> +
> + 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);
> + }
> +}
> +
> +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);
> + } else {
> + sc = RTEMS_INCORRECT_STATE;
> + }
> + } else {
> + sc = RTEMS_INVALID_ID;
> + }
> +
> + return sc;
> +}
> +
> +void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control)
> +{
> + /* Do nothing */
> +}
> +
> +void rtems_rbheap_extend_page_pool_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);
> +
> + add_to_chain(pool_chain, page);
> + }
> +}
> diff --git a/testsuites/libtests/Makefile.am b/testsuites/libtests/Makefile.am
> index 9521825..e964608 100644
> --- a/testsuites/libtests/Makefile.am
> +++ b/testsuites/libtests/Makefile.am
> @@ -5,6 +5,7 @@
> ACLOCAL_AMFLAGS = -I ../aclocal
>
> SUBDIRS = POSIX
> +SUBDIRS += rbheap01
> SUBDIRS += flashdisk01
>
> SUBDIRS += bspcmdline01 cpuuse devfs01 devfs02 devfs03 devfs04 \
> diff --git a/testsuites/libtests/configure.ac b/testsuites/libtests/configure.ac
> index d1ce374..f04ab0b 100644
> --- a/testsuites/libtests/configure.ac
> +++ b/testsuites/libtests/configure.ac
> @@ -43,6 +43,7 @@ AM_CONDITIONAL(NETTESTS,test "$rtems_cv_RTEMS_NETWORKING" = "yes")
>
> # Explicitly list all Makefiles here
> AC_CONFIG_FILES([Makefile
> +rbheap01/Makefile
> syscall01/Makefile
> flashdisk01/Makefile
> block01/Makefile
> diff --git a/testsuites/libtests/rbheap01/Makefile.am b/testsuites/libtests/rbheap01/Makefile.am
> new file mode 100644
> index 0000000..9bad9c0
> --- /dev/null
> +++ b/testsuites/libtests/rbheap01/Makefile.am
> @@ -0,0 +1,19 @@
> +rtems_tests_PROGRAMS = rbheap01
> +rbheap01_SOURCES = init.c
> +
> +dist_rtems_tests_DATA = rbheap01.scn rbheap01.doc
> +
> +include $(RTEMS_ROOT)/make/custom/@RTEMS_BSP at .cfg
> +include $(top_srcdir)/../automake/compile.am
> +include $(top_srcdir)/../automake/leaf.am
> +
> +AM_CPPFLAGS += -I$(top_srcdir)/../support/include
> +
> +LINK_OBJS = $(rbheap01_OBJECTS)
> +LINK_LIBS = $(rbheap01_LDLIBS)
> +
> +rbheap01$(EXEEXT): $(rbheap01_OBJECTS) $(rbheap01_DEPENDENCIES)
> + @rm -f rbheap01$(EXEEXT)
> + $(make-exe)
> +
> +include $(top_srcdir)/../automake/local.am
> diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
> new file mode 100644
> index 0000000..a66cc24
> --- /dev/null
> +++ b/testsuites/libtests/rbheap01/init.c
> @@ -0,0 +1,571 @@
> +/*
> + * Copyright (c) 2012 embedded brains GmbH. All rights reserved.
> + *
> + * embedded brains GmbH
> + * Obere Lagerstr. 30
> + * 82178 Puchheim
> + * Germany
> + * <rtems at embedded-brains.de>
> + *
> + * The license and distribution terms for this file may be
> + * found in the file LICENSE in this distribution or at
> + * http://www.rtems.com/license/LICENSE.
> + */
> +
> +#ifdef HAVE_CONFIG_H
> + #include "config.h"
> +#endif
> +
> +#include "tmacros.h"
> +
> +#include <rtems.h>
> +#include <rtems/rbheap.h>
> +
> +#define PAGE_SIZE 1024
> +
> +#define PAGE_COUNT 8
> +
> +static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1];
> +
> +static rtems_rbheap_page pages [PAGE_COUNT];
> +
> +static void extend_page_pool(rtems_rbheap_control *control)
> +{
> + rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
> +
> + rtems_rbheap_set_extend_page_pool(
> + control,
> + rtems_rbheap_extend_page_pool_never
> + );
> +
> + rtems_chain_initialize(
> + pool_chain,
> + pages,
> + PAGE_COUNT,
> + sizeof(pages [0])
> + );
> +}
> +
> +static uintptr_t idx(const rtems_rbheap_page *page)
> +{
> + uintptr_t base = (uintptr_t) area;
> + uintptr_t excess = base % PAGE_SIZE;
> +
> + if (excess > 0) {
> + base += PAGE_SIZE - excess;
> + }
> +
> + return (page->begin - base) / PAGE_SIZE;
> +}
> +
> +typedef struct {
> + const uintptr_t *index_current;
> + const uintptr_t *index_end;
> + const bool *free_current;
> + const bool *free_end;
> +} page_visitor_context;
> +
> +static bool page_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_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);
> +
> + ++context->index_current;
> + ++context->free_current;
> +
> + return false;
> +}
> +
> +static void test_init_page_alignment(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> +
> + sc = rtems_rbheap_initialize(
> + &control,
> + area,
> + sizeof(area),
> + 0,
> + extend_page_pool,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
> +}
> +
> +static void test_init_begin_greater_than_end(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> +
> + sc = rtems_rbheap_initialize(
> + &control,
> + (void *) PAGE_SIZE,
> + (uintptr_t) -PAGE_SIZE,
> + PAGE_SIZE,
> + extend_page_pool,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
> +}
> +
> +static void test_init_begin_greater_than_aligned_begin(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> +
> + sc = rtems_rbheap_initialize(
> + &control,
> + (void *) -(PAGE_SIZE / 2),
> + PAGE_SIZE,
> + PAGE_SIZE,
> + extend_page_pool,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
> +}
> +
> +static void test_init_aligned_begin_greater_than_aligned_end(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> +
> + sc = rtems_rbheap_initialize(
> + &control,
> + (void *) PAGE_SIZE,
> + PAGE_SIZE / 2,
> + PAGE_SIZE,
> + extend_page_pool,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
> +}
> +
> +static void test_init_empty_page_pool(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> +
> + sc = rtems_rbheap_initialize(
> + &control,
> + (void *) PAGE_SIZE,
> + PAGE_SIZE,
> + PAGE_SIZE,
> + rtems_rbheap_extend_page_pool_never,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_NO_MEMORY);
> +}
> +
> +static void test_page_tree(
> + const rtems_rbheap_control *control,
> + const uintptr_t *index_begin,
> + const uintptr_t *index_end,
> + const bool *free_begin,
> + const bool *free_end
> +)
> +{
> + page_visitor_context context = {
> + .index_current = index_begin,
> + .index_end = index_end,
> + .free_current = free_begin,
> + .free_end = free_end
> + };
> +
> + _RBTree_Iterate_unprotected(
> + &control->page_tree,
> + RBT_RIGHT,
> + page_visitor,
> + &context
> + );
> +}
> +
> +#define TEST_PAGE_TREE(control, indices, frees) \
> + test_page_tree( \
> + control, \
> + indices, \
> + &indices [sizeof(indices) / sizeof(indices [0])], \
> + frees, \
> + &frees [sizeof(frees) / sizeof(frees [0])] \
> + )
> +
> +static void test_init_successful(rtems_rbheap_control *control)
> +{
> + static const uintptr_t indices [] = {
> + 0
> + };
> + static const bool frees [] = {
> + true
> + };
> +
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> +
> + sc = rtems_rbheap_initialize(
> + control,
> + area,
> + sizeof(area),
> + PAGE_SIZE,
> + extend_page_pool,
> + NULL
> + );
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + TEST_PAGE_TREE(control, indices, frees);
> +}
> +
> +static void test_alloc_and_free_one(void)
> +{
> + static const uintptr_t indices_0 [] = {
> + 0,
> + PAGE_COUNT - 1
> + };
> + static const bool frees_0 [] = {
> + true,
> + false
> + };
> + static const uintptr_t indices_1 [] = {
> + 0
> + };
> + static const bool frees_1 [] = {
> + true,
> + };
> +
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> + void *ptr = NULL;
> +
> + test_init_successful(&control);
> +
> + ptr = rtems_rbheap_allocate(&control, PAGE_SIZE);
> + rtems_test_assert(ptr != NULL);
> +
> + TEST_PAGE_TREE(&control, indices_0, frees_0);
> +
> + sc = rtems_rbheap_free(&control, ptr);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + TEST_PAGE_TREE(&control, indices_1, frees_1);
> +}
> +
> +static void test_alloc_zero(void)
> +{
> + static const uintptr_t indices [] = {
> + 0
> + };
> + static const bool frees [] = {
> + true
> + };
> +
> + rtems_rbheap_control control;
> + void *ptr = NULL;
> +
> + test_init_successful(&control);
> +
> + ptr = rtems_rbheap_allocate(&control, 0);
> + rtems_test_assert(ptr == NULL);
> +
> + TEST_PAGE_TREE(&control, indices, frees);
> +}
> +
> +static void test_alloc_huge_page(void)
> +{
> + static const uintptr_t indices [] = {
> + 0
> + };
> + static const bool frees [] = {
> + true
> + };
> +
> + rtems_rbheap_control control;
> + void *ptr = NULL;
> +
> + test_init_successful(&control);
> +
> + ptr = rtems_rbheap_allocate(&control, (PAGE_COUNT + 1) * PAGE_SIZE);
> + rtems_test_assert(ptr == NULL);
> +
> + TEST_PAGE_TREE(&control, indices, frees);
> +}
> +
> +static void test_alloc_one_page(void)
> +{
> + static const uintptr_t indices_0 [] = {
> + 0
> + };
> + static const bool frees_0 [] = {
> + false
> + };
> + static const uintptr_t indices_1 [] = {
> + 0
> + };
> + static const bool frees_1 [] = {
> + true,
> + };
> +
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> + void *ptr = NULL;
> +
> + test_init_successful(&control);
> +
> + ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
> + rtems_test_assert(ptr != NULL);
> +
> + TEST_PAGE_TREE(&control, indices_0, frees_0);
> +
> + sc = rtems_rbheap_free(&control, ptr);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + TEST_PAGE_TREE(&control, indices_1, frees_1);
> +}
> +
> +static void test_alloc_many_pages(void)
> +{
> + static const uintptr_t indices_0 [] = {
> + 0,
> + 1,
> + 2,
> + 3,
> + 4,
> + 5,
> + 6,
> + 7
> + };
> + static const bool frees_0 [] = {
> + false,
> + false,
> + false,
> + false,
> + false,
> + false,
> + false,
> + false
> + };
> + static const uintptr_t indices_1 [] = {
> + 0
> + };
> + static const bool frees_1 [] = {
> + true,
> + };
> +
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> + void *ptr [PAGE_COUNT];
> + void *null = NULL;
> + int i = 0;
> +
> + test_init_successful(&control);
> +
> + for (i = 0; i < PAGE_COUNT; ++i) {
> + ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
> + rtems_test_assert(ptr [i] != NULL);
> + }
> +
> + TEST_PAGE_TREE(&control, indices_0, frees_0);
> +
> + null = rtems_rbheap_allocate(&control, PAGE_SIZE);
> + rtems_test_assert(null == NULL);
> +
> + TEST_PAGE_TREE(&control, indices_0, frees_0);
> +
> + for (i = 0; i < PAGE_COUNT; ++i) {
> + sc = rtems_rbheap_free(&control, ptr [i]);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> + }
> +
> + TEST_PAGE_TREE(&control, indices_1, frees_1);
> +}
> +
> +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, NULL);
> + rtems_test_assert(sc == RTEMS_INVALID_ID);
> +}
> +
> +static void test_free_double(void)
> +{
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> + void *ptr = NULL;
> +
> + test_init_successful(&control);
> +
> + ptr = rtems_rbheap_allocate(&control, PAGE_COUNT * PAGE_SIZE);
> + rtems_test_assert(ptr != NULL);
> +
> + sc = rtems_rbheap_free(&control, ptr);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + sc = rtems_rbheap_free(&control, ptr);
> + rtems_test_assert(sc == RTEMS_INCORRECT_STATE);
> +}
> +
> +enum {
> + LOW,
> + LEFT,
> + MIDDLE,
> + RIGHT,
> + HIGH
> +};
> +
> +static void test_free_merge_left_or_right(bool left)
> +{
> + static const uintptr_t indices_0 [] = {
> + 0,
> + 3,
> + 4,
> + 5,
> + 6,
> + 7
> + };
> + static const bool frees_0 [] = {
> + true,
> + false,
> + false,
> + false,
> + false,
> + false
> + };
> + static const uintptr_t indices_1_left [] = {
> + 0,
> + 3,
> + 4,
> + 5,
> + 6,
> + 7
> + };
> + static const bool frees_1_left [] = {
> + true,
> + false,
> + true,
> + false,
> + false,
> + false
> + };
> + static const uintptr_t indices_1_right [] = {
> + 0,
> + 3,
> + 4,
> + 5,
> + 6,
> + 7
> + };
> + static const bool frees_1_right [] = {
> + true,
> + false,
> + false,
> + false,
> + true,
> + false
> + };
> + static const uintptr_t indices_2_left [] = {
> + 0,
> + 3,
> + 4,
> + 6,
> + 7
> + };
> + static const bool frees_2_left [] = {
> + true,
> + false,
> + true,
> + false,
> + false
> + };
> + static const uintptr_t indices_2_right [] = {
> + 0,
> + 3,
> + 4,
> + 5,
> + 7
> + };
> + static const bool frees_2_right [] = {
> + true,
> + false,
> + false,
> + true,
> + false
> + };
> +
> + rtems_status_code sc = RTEMS_SUCCESSFUL;
> + rtems_rbheap_control control;
> + void *ptr [HIGH + 1];
> + int dir = left ? LEFT : RIGHT;
> + int i = 0;
> +
> + test_init_successful(&control);
> +
> + for (i = sizeof(ptr) / sizeof(ptr [0]) - 1; i >= 0; --i) {
> + ptr [i] = rtems_rbheap_allocate(&control, PAGE_SIZE);
> + rtems_test_assert(ptr [i] != NULL);
> + }
> +
> + TEST_PAGE_TREE(&control, indices_0, frees_0);
> +
> + sc = rtems_rbheap_free(&control, ptr [dir]);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + if (left) {
> + TEST_PAGE_TREE(&control, indices_1_left, frees_1_left);
> + } else {
> + TEST_PAGE_TREE(&control, indices_1_right, frees_1_right);
> + }
> +
> + sc = rtems_rbheap_free(&control, ptr [MIDDLE]);
> + rtems_test_assert(sc == RTEMS_SUCCESSFUL);
> +
> + if (left) {
> + TEST_PAGE_TREE(&control, indices_2_left, frees_2_left);
> + } else {
> + TEST_PAGE_TREE(&control, indices_2_right, frees_2_right);
> + }
> +}
> +
> +static void Init(rtems_task_argument arg)
> +{
> + puts("\n\n*** TEST RBHEAP 1 ***");
> +
> + test_init_page_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_alloc_and_free_one();
> + test_alloc_zero();
> + test_alloc_huge_page();
> + test_alloc_one_page();
> + test_alloc_many_pages();
> + test_free_invalid();
> + test_free_double();
> + test_free_merge_left_or_right(true);
> + test_free_merge_left_or_right(false);
> +
> + puts("*** END OF TEST RBHEAP 1 ***");
> +
> + rtems_test_exit(0);
> +}
> +
> +#define CONFIGURE_APPLICATION_NEEDS_CLOCK_DRIVER
> +#define CONFIGURE_APPLICATION_NEEDS_CONSOLE_DRIVER
> +
> +#define CONFIGURE_MAXIMUM_TASKS 1
> +
> +#define CONFIGURE_RTEMS_INIT_TASKS_TABLE
> +
> +#define CONFIGURE_INIT
> +
> +#include <rtems/confdefs.h>
> diff --git a/testsuites/libtests/rbheap01/rbheap01.doc b/testsuites/libtests/rbheap01/rbheap01.doc
> new file mode 100644
> index 0000000..f8dd07e
> --- /dev/null
> +++ b/testsuites/libtests/rbheap01/rbheap01.doc
> @@ -0,0 +1,11 @@
> +This file describes the directives and concepts tested by this test set.
> +
> +test set name: rbheap01
> +
> +directives:
> +
> + TBD
> +
> +concepts:
> +
> + TBD
> diff --git a/testsuites/libtests/rbheap01/rbheap01.scn b/testsuites/libtests/rbheap01/rbheap01.scn
> new file mode 100644
> index 0000000..ddbc9b3
> --- /dev/null
> +++ b/testsuites/libtests/rbheap01/rbheap01.scn
> @@ -0,0 +1,2 @@
> +*** TEST RBHEAP 1 ***
> +*** END OF TEST RBHEAP 1 ***
>
> _______________________________________________
> rtems-vc mailing list
> rtems-vc at rtems.org
> http://www.rtems.org/mailman/listinfo/rtems-vc
More information about the devel
mailing list