diff options
author | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2012-04-10 11:19:39 +0200 |
---|---|---|
committer | Sebastian Huber <sebastian.huber@embedded-brains.de> | 2012-04-11 11:24:19 +0200 |
commit | e75263083e83cac921475d0a89d8b3b398f9b902 (patch) | |
tree | ee606a61f71499421724066779ccb22a7855046e /testsuites/libtests | |
parent | rbtree: New function _RBTree_Iterate_unprotected() (diff) | |
download | rtems-e75263083e83cac921475d0a89d8b3b398f9b902.tar.bz2 |
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.
Diffstat (limited to 'testsuites/libtests')
-rw-r--r-- | testsuites/libtests/Makefile.am | 1 | ||||
-rw-r--r-- | testsuites/libtests/configure.ac | 1 | ||||
-rw-r--r-- | testsuites/libtests/rbheap01/Makefile.am | 19 | ||||
-rw-r--r-- | testsuites/libtests/rbheap01/init.c | 571 | ||||
-rw-r--r-- | testsuites/libtests/rbheap01/rbheap01.doc | 11 | ||||
-rw-r--r-- | testsuites/libtests/rbheap01/rbheap01.scn | 2 |
6 files changed, 605 insertions, 0 deletions
diff --git a/testsuites/libtests/Makefile.am b/testsuites/libtests/Makefile.am index 9521825441..e964608089 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 d1ce3745df..f04ab0b789 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 0000000000..9bad9c0759 --- /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@.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 0000000000..a66cc24273 --- /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@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 0000000000..f8dd07efd0 --- /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 0000000000..ddbc9b3af7 --- /dev/null +++ b/testsuites/libtests/rbheap01/rbheap01.scn @@ -0,0 +1,2 @@ +*** TEST RBHEAP 1 *** +*** END OF TEST RBHEAP 1 *** |