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.

10 files changed, 1018 insertions, 1 deletions

diff --git a/cpukit/sapi/Makefile.am b/cpukit/sapi/Makefile.am
index 9b7ad53201..453628095b 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 0000000000..be1eec6b66
--- /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@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 5ce9966786..e7c8e2a25c 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 0000000000..798632520d
--- /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@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 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 ***