rbheap: API changes and documentation

3 files changed, 309 insertions, 156 deletions

diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
index be1eec6b66..5481e8954f 100644
--- a/cpukit/sapi/include/rtems/rbheap.h
+++ b/cpukit/sapi/include/rtems/rbheap.h
@@ -36,60 +36,191 @@ extern "C" {
  *
  * @brief Red-Black Tree Heap API.
  *
- * In the Red-Black Tree Heap the administration data structures are not
- * contained in the managed memory area.  This can be used for example in a
- * task stack allocator which protects the task stacks from access by other
- * tasks.
+ * The red-black tree heap provides a memory allocator suitable to implement
+ * the malloc() and free() interface.  It uses a first-fit allocation strategy.
+ * In the red-black tree heap the administration data structures are not
+ * contained in the managed memory area.  Thus writing beyond the boundaries of
+ * a chunk does not damage the data to maintain the heap.  This can be used for
+ * example in a task stack allocator which protects the task stacks from access
+ * by other tasks.  The allocated and free memory parts of the managed area are
+ * called chunks.  Each chunk needs a descriptor which is stored outside of the
+ * managed area.
  *
  * @{
  */
 
+/**
+ * @brief Red-black heap chunk descriptor.
+ */
 typedef struct {
+  /**
+   * This chain node can be used in two chains
+   *  - the chain of spare chunk descriptors and
+   *  - the chain of free chunks in the managed memory area.
+   *
+   * In case this chain node is not part of a chain, the chunk represents a
+   * used chunk in the managed memory area.
+   */
   rtems_chain_node chain_node;
+
+  /**
+   * Tree node for chunks that represent a part of the managed memory area.
+   * These chunks are either free or used.
+   */
   rtems_rbtree_node tree_node;
+
+  /**
+   * Begin address of the chunk.  The address alignment it specified in the
+   * @ref rtems_rbheap_control.
+   */
   uintptr_t begin;
+
+  /**
+   * Size of the chunk in bytes.
+   */
   uintptr_t size;
-} rtems_rbheap_page;
+} rtems_rbheap_chunk;
 
 typedef struct rtems_rbheap_control rtems_rbheap_control;
 
-typedef void (*rtems_rbheap_extend_page_pool)(rtems_rbheap_control *control);
+/**
+ * @brief Handler to extend the available chunk descriptors.
+ *
+ * This handler is called when no more chunk descriptors are available.  An
+ * example implementation is this:
+ *
+ * @code
+ * void extend_descriptors_with_malloc(rtems_rbheap_control *control)
+ * {
+ *   rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
+ *
+ *   if (chunk != NULL) {
+ *     rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
+ *   }
+ * }
+ * @endcode
+ *
+ * @see rtems_rbheap_extend_descriptors_never() and
+ * rtems_rbheap_extend_descriptors_with_malloc().
+ */
+typedef void (*rtems_rbheap_extend_descriptors)(rtems_rbheap_control *control);
 
+/**
+ * @brief Red-black heap control.
+ */
 struct rtems_rbheap_control {
-  rtems_chain_control free_chain;
-  rtems_chain_control pool_chain;
-  rtems_rbtree_control page_tree;
-  uintptr_t page_alignment;
-  rtems_rbheap_extend_page_pool extend_page_pool;
+  /**
+   * Chain of free chunks in the managed memory area.
+   */
+  rtems_chain_control free_chunk_chain;
+
+  /**
+   * Chain of free chunk descriptors.  Descriptors are consumed during
+   * allocation and may be produced during free if contiguous chunks can be
+   * coalesced.  In case of descriptor starvation the @ref extend_descriptors
+   * handler will be called.
+   */
+  rtems_chain_control spare_descriptor_chain;
+
+  /**
+   * Tree of chunks representing the state of the managed memory area.
+   */
+  rtems_rbtree_control chunk_tree;
+
+  /**
+   * Minimum chunk begin alignment in bytes.
+   */
+  uintptr_t alignment;
+
+  /**
+   * Handler to extend the available chunk descriptors.
+   */
+  rtems_rbheap_extend_descriptors extend_descriptors;
+
+  /**
+   * User specified argument handler for private handler data.
+   */
   void *handler_arg;
 };
 
+/**
+ * @brief Initializes the red-black tree heap @a control.
+ *
+ * @param[in, out] control The red-black tree heap.
+ * @param[in] area_begin The managed memory area begin.
+ * @param[in] area_size The managed memory area size.
+ * @param[in] alignment The minimum chunk alignment.
+ * @param[in] extend_descriptors The handler to extend the available chunk
+ * descriptors.
+ * @param[in] handler_arg The handler argument.
+ *
+ * @retval RTEMS_SUCCESSFUL Successful operation.
+ * @retval RTEMS_INVALID_NUMBER The alignment is not positive.
+ * @retval RTEMS_INVALID_ADDRESS The memory area is invalid.
+ * @retval RTEMS_NO_MEMORY Not enough chunk descriptors.
+ */
 rtems_status_code rtems_rbheap_initialize(
   rtems_rbheap_control *control,
   void *area_begin,
   uintptr_t area_size,
-  uintptr_t page_alignment,
-  rtems_rbheap_extend_page_pool extend_page_pool,
+  uintptr_t alignment,
+  rtems_rbheap_extend_descriptors extend_descriptors,
   void *handler_arg
 );
 
+/**
+ * @brief Allocates a chunk of memory of at least @a size bytes from the
+ * red-black tree heap @a control.
+ *
+ * The chunk begin is aligned by the value specified in
+ * rtems_rbheap_initialize().
+ *
+ * @param[in, out] control The red-black tree heap.
+ * @param[in] size The requested chunk size in bytes.
+ *
+ * @retval NULL Not enough free space in the heap.
+ * @retval otherwise Pointer to allocated chunk of memory.
+ */
 void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size);
 
+/**
+ * @brief Frees a chunk of memory @a ptr allocated from the red-black tree heap
+ * @a control.
+ *
+ * @param[in, out] control The red-black tree heap.
+ * @param[in] ptr The pointer to the chunk of memory.
+ *
+ * @retval RTEMS_SUCCESSFUL Successful operation.
+ * @retval RTEMS_INVALID_ID The chunk of memory is not a valid chunk in the
+ * red-black tree heap.
+ * @retval RTEMS_INCORRECT_STATE The chunk of memory is not in the right state.
+ */
 rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr);
 
-static inline rtems_chain_control *rtems_rbheap_get_pool_chain(
+static inline rtems_chain_control *rtems_rbheap_get_spare_descriptor_chain(
   rtems_rbheap_control *control
 )
 {
-  return &control->pool_chain;
+  return &control->spare_descriptor_chain;
 }
 
-static inline void rtems_rbheap_set_extend_page_pool(
+static inline void rtems_rbheap_add_to_spare_descriptor_chain(
   rtems_rbheap_control *control,
-  rtems_rbheap_extend_page_pool extend_page_pool
+  rtems_rbheap_chunk *chunk
 )
 {
-  control->extend_page_pool = extend_page_pool;
+  rtems_chain_control *chain =
+    rtems_rbheap_get_spare_descriptor_chain(control);
+
+  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
+}
+
+static inline void rtems_rbheap_set_extend_descriptors(
+  rtems_rbheap_control *control,
+  rtems_rbheap_extend_descriptors extend_descriptors
+)
+{
+  control->extend_descriptors = extend_descriptors;
 }
 
 static inline void *rtems_rbheap_get_handler_arg(
@@ -107,20 +238,28 @@ static inline void rtems_rbheap_set_handler_arg(
   control->handler_arg = handler_arg;
 }
 
-void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control);
+/**
+ * @brief Chunk descriptor extend handler that does nothing.
+ */
+void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control);
 
-void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control);
+/**
+ * @brief Chunk descriptor extend handler that uses malloc().
+ */
+void rtems_rbheap_extend_descriptors_with_malloc(
+  rtems_rbheap_control *control
+);
 
 /** @} */
 
 /* Private API */
 
-#define rtems_rbheap_page_of_node(node) \
-  rtems_rbtree_container_of(node, rtems_rbheap_page, tree_node)
+#define rtems_rbheap_chunk_of_node(node) \
+  rtems_rbtree_container_of(node, rtems_rbheap_chunk, tree_node)
 
-static inline bool rtems_rbheap_is_page_free(const rtems_rbheap_page *page)
+static inline bool rtems_rbheap_is_chunk_free(const rtems_rbheap_chunk *chunk)
 {
-  return !rtems_chain_is_node_off_chain(&page->chain_node);
+  return !rtems_chain_is_node_off_chain(&chunk->chain_node);
 }
 
 #ifdef __cplusplus
diff --git a/cpukit/sapi/src/rbheap.c b/cpukit/sapi/src/rbheap.c
index 798632520d..7facf4f9af 100644
--- a/cpukit/sapi/src/rbheap.c
+++ b/cpukit/sapi/src/rbheap.c
@@ -28,96 +28,96 @@
 
 #include <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 *chain = &control->spare_descriptor_chain;
+  rtems_chain_node *chunk = rtems_chain_get_unprotected(chain);
 
-  if (page == NULL) {
-    (*control->extend_page_pool)(control);
-    page = rtems_chain_get(pool_chain);
+  if (chunk == NULL) {
+    (*control->extend_descriptors)(control);
+    chunk = rtems_chain_get_unprotected(chain);
   }
 
-  return (rtems_rbheap_page *) page;
+  return (rtems_rbheap_chunk *) chunk;
 }
 
 static void add_to_chain(
   rtems_chain_control *chain,
-  rtems_rbheap_page *page
+  rtems_rbheap_chunk *chunk
 )
 {
-  rtems_chain_prepend_unprotected(chain, &page->chain_node);
+  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
 }
 
 static void insert_into_tree(
   rtems_rbtree_control *tree,
-  rtems_rbheap_page *page
+  rtems_rbheap_chunk *chunk
 )
 {
-  _RBTree_Insert_unprotected(tree, &page->tree_node);
+  _RBTree_Insert_unprotected(tree, &chunk->tree_node);
 }
 
 rtems_status_code rtems_rbheap_initialize(
   rtems_rbheap_control *control,
   void *area_begin,
   uintptr_t area_size,
-  uintptr_t page_alignment,
-  rtems_rbheap_extend_page_pool extend_page_pool,
+  uintptr_t alignment,
+  rtems_rbheap_extend_descriptors extend_descriptors,
   void *handler_arg
 )
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
 
-  if (page_alignment > 0) {
+  if (alignment > 0) {
     uintptr_t begin = (uintptr_t) area_begin;
     uintptr_t end = begin + area_size;
-    uintptr_t aligned_begin = align_up(page_alignment, begin);
-    uintptr_t aligned_end = align_down(page_alignment, end);
+    uintptr_t aligned_begin = align_up(alignment, begin);
+    uintptr_t aligned_end = align_down(alignment, end);
 
     if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
-      rtems_chain_control *free_chain = &control->free_chain;
-      rtems_rbtree_control *page_tree = &control->page_tree;
-      rtems_rbheap_page *first = NULL;
+      rtems_chain_control *free_chain = &control->free_chunk_chain;
+      rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+      rtems_rbheap_chunk *first = NULL;
 
       rtems_chain_initialize_empty(free_chain);
-      rtems_chain_initialize_empty(&control->pool_chain);
-      rtems_rbtree_initialize_empty(page_tree, page_compare, true);
-      control->page_alignment = page_alignment;
+      rtems_chain_initialize_empty(&control->spare_descriptor_chain);
+      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
+      control->alignment = alignment;
       control->handler_arg = handler_arg;
-      control->extend_page_pool = extend_page_pool;
+      control->extend_descriptors = extend_descriptors;
 
-      first = get_page(control);
+      first = get_chunk(control);
       if (first != NULL) {
         first->begin = aligned_begin;
         first->size = aligned_end - aligned_begin;
         add_to_chain(free_chain, first);
-        insert_into_tree(page_tree, first);
+        insert_into_tree(chunk_tree, first);
       } else {
         sc = RTEMS_NO_MEMORY;
       }
@@ -131,20 +131,20 @@ rtems_status_code rtems_rbheap_initialize(
   return sc;
 }
 
-static rtems_rbheap_page *search_free_page(
+static rtems_rbheap_chunk *search_free_chunk(
   rtems_chain_control *free_chain,
   size_t size
 )
 {
   rtems_chain_node *current = rtems_chain_first(free_chain);
   const rtems_chain_node *tail = rtems_chain_tail(free_chain);
-  rtems_rbheap_page *big_enough = NULL;
+  rtems_rbheap_chunk *big_enough = NULL;
 
   while (current != tail && big_enough == NULL) {
-    rtems_rbheap_page *free_page = (rtems_rbheap_page *) current;
+    rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current;
 
-    if (free_page->size >= size) {
-      big_enough = free_page;
+    if (free_chunk->size >= size) {
+      big_enough = free_chunk;
     }
 
     current = rtems_chain_next(current);
@@ -156,34 +156,34 @@ static rtems_rbheap_page *search_free_page(
 void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size)
 {
   void *ptr = NULL;
-  rtems_chain_control *free_chain = &control->free_chain;
-  rtems_rbtree_control *page_tree = &control->page_tree;
-  uintptr_t page_alignment = control->page_alignment;
-  uintptr_t aligned_size = align_up(page_alignment, size);
+  rtems_chain_control *free_chain = &control->free_chunk_chain;
+  rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+  uintptr_t alignment = control->alignment;
+  uintptr_t aligned_size = align_up(alignment, size);
 
   if (size > 0 && size <= aligned_size) {
-    rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size);
+    rtems_rbheap_chunk *free_chunk = search_free_chunk(free_chain, aligned_size);
 
-    if (free_page != NULL) {
-      uintptr_t free_size = free_page->size;
+    if (free_chunk != NULL) {
+      uintptr_t free_size = free_chunk->size;
 
       if (free_size > aligned_size) {
-        rtems_rbheap_page *new_page = get_page(control);
+        rtems_rbheap_chunk *new_chunk = get_chunk(control);
 
-        if (new_page != NULL) {
+        if (new_chunk != NULL) {
           uintptr_t new_free_size = free_size - aligned_size;
 
-          free_page->size = new_free_size;
-          new_page->begin = free_page->begin + new_free_size;
-          new_page->size = aligned_size;
-          rtems_chain_set_off_chain(&new_page->chain_node);
-          insert_into_tree(page_tree, new_page);
-          ptr = (void *) new_page->begin;
+          free_chunk->size = new_free_size;
+          new_chunk->begin = free_chunk->begin + new_free_size;
+          new_chunk->size = aligned_size;
+          rtems_chain_set_off_chain(&new_chunk->chain_node);
+          insert_into_tree(chunk_tree, new_chunk);
+          ptr = (void *) new_chunk->begin;
         }
       } else {
-        rtems_chain_extract_unprotected(&free_page->chain_node);
-        rtems_chain_set_off_chain(&free_page->chain_node);
-        ptr = (void *) free_page->begin;
+        rtems_chain_extract_unprotected(&free_chunk->chain_node);
+        rtems_chain_set_off_chain(&free_chunk->chain_node);
+        ptr = (void *) free_chunk->begin;
       }
     }
   }
@@ -191,38 +191,38 @@ void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size)
   return ptr;
 }
 
-#define NULL_PAGE rtems_rbheap_page_of_node(NULL)
+#define NULL_PAGE rtems_rbheap_chunk_of_node(NULL)
 
-static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key)
+static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
 {
-  rtems_rbheap_page page = { .begin = key };
+  rtems_rbheap_chunk chunk = { .begin = key };
 
-  return rtems_rbheap_page_of_node(
-    _RBTree_Find_unprotected(page_tree, &page.tree_node)
+  return rtems_rbheap_chunk_of_node(
+    _RBTree_Find_unprotected(chunk_tree, &chunk.tree_node)
   );
 }
 
-static rtems_rbheap_page *get_next(
-  const rtems_rbtree_control *page_tree,
-  const rtems_rbheap_page *page,
+static rtems_rbheap_chunk *get_next(
+  const rtems_rbtree_control *chunk_tree,
+  const rtems_rbheap_chunk *chunk,
   RBTree_Direction dir
 )
 {
-  return rtems_rbheap_page_of_node(
-    _RBTree_Next_unprotected(page_tree, &page->tree_node, dir)
+  return rtems_rbheap_chunk_of_node(
+    _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir)
   );
 }
 
 static void check_and_merge(
   rtems_chain_control *free_chain,
-  rtems_rbtree_control *page_tree,
-  rtems_rbheap_page *a,
-  rtems_rbheap_page *b
+  rtems_rbtree_control *chunk_tree,
+  rtems_rbheap_chunk *a,
+  rtems_rbheap_chunk *b
 )
 {
-  if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) {
+  if (b != NULL_PAGE && rtems_rbheap_is_chunk_free(b)) {
     if (b->begin < a->begin) {
-      rtems_rbheap_page *t = a;
+      rtems_rbheap_chunk *t = a;
 
       a = b;
       b = t;
@@ -231,47 +231,48 @@ static void check_and_merge(
     a->size += b->size;
     rtems_chain_extract_unprotected(&b->chain_node);
     add_to_chain(free_chain, b);
-    _RBTree_Extract_unprotected(page_tree, &b->tree_node);
+    _RBTree_Extract_unprotected(chunk_tree, &b->tree_node);
   }
 }
 
 rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr)
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
-  rtems_chain_control *free_chain = &control->free_chain;
-  rtems_rbtree_control *page_tree = &control->page_tree;
-  rtems_rbheap_page *page = find(page_tree, (uintptr_t) ptr);
-
-  if (page != NULL_PAGE) {
-    if (!rtems_rbheap_is_page_free(page)) {
-      rtems_rbheap_page *pred = get_next(page_tree, page, RBT_LEFT);
-      rtems_rbheap_page *succ = get_next(page_tree, page, RBT_RIGHT);
-
-      check_and_merge(free_chain, page_tree, page, succ);
-      add_to_chain(free_chain, page);
-      check_and_merge(free_chain, page_tree, page, pred);
+
+  if (ptr != NULL) {
+    rtems_chain_control *free_chain = &control->free_chunk_chain;
+    rtems_rbtree_control *chunk_tree = &control->chunk_tree;
+    rtems_rbheap_chunk *chunk = find(chunk_tree, (uintptr_t) ptr);
+
+    if (chunk != NULL_PAGE) {
+      if (!rtems_rbheap_is_chunk_free(chunk)) {
+        rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
+        rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
+
+        check_and_merge(free_chain, chunk_tree, chunk, succ);
+        add_to_chain(free_chain, chunk);
+        check_and_merge(free_chain, chunk_tree, chunk, pred);
+      } else {
+        sc = RTEMS_INCORRECT_STATE;
+      }
     } else {
-      sc = RTEMS_INCORRECT_STATE;
+      sc = RTEMS_INVALID_ID;
     }
-  } else {
-    sc = RTEMS_INVALID_ID;
   }
 
   return sc;
 }
 
-void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control)
+void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control)
 {
   /* Do nothing */
 }
 
-void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control)
+void rtems_rbheap_extend_descriptors_with_malloc(rtems_rbheap_control *control)
 {
-  rtems_rbheap_page *page = malloc(sizeof(*page));
-
-  if (page != NULL) {
-    rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
+  rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
 
-    add_to_chain(pool_chain, page);
+  if (chunk != NULL) {
+    rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
   }
 }
diff --git a/testsuites/libtests/rbheap01/init.c b/testsuites/libtests/rbheap01/init.c
index a66cc24273..ce180d8541 100644
--- a/testsuites/libtests/rbheap01/init.c
+++ b/testsuites/libtests/rbheap01/init.c
@@ -27,26 +27,27 @@
 
 static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1];
 
-static rtems_rbheap_page pages [PAGE_COUNT];
+static rtems_rbheap_chunk chunks [PAGE_COUNT];
 
-static void extend_page_pool(rtems_rbheap_control *control)
+static void extend_descriptors(rtems_rbheap_control *control)
 {
-  rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
+  rtems_chain_control *chain =
+    rtems_rbheap_get_spare_descriptor_chain(control);
 
-  rtems_rbheap_set_extend_page_pool(
+  rtems_rbheap_set_extend_descriptors(
     control,
-    rtems_rbheap_extend_page_pool_never
+    rtems_rbheap_extend_descriptors_never
   );
 
   rtems_chain_initialize(
-    pool_chain,
-    pages,
+    chain,
+    chunks,
     PAGE_COUNT,
-    sizeof(pages [0])
+    sizeof(chunks [0])
   );
 }
 
-static uintptr_t idx(const rtems_rbheap_page *page)
+static uintptr_t idx(const rtems_rbheap_chunk *chunk)
 {
   uintptr_t base = (uintptr_t) area;
   uintptr_t excess = base % PAGE_SIZE;
@@ -55,7 +56,7 @@ static uintptr_t idx(const rtems_rbheap_page *page)
     base += PAGE_SIZE - excess;
   }
 
-  return (page->begin - base) / PAGE_SIZE;
+  return (chunk->begin - base) / PAGE_SIZE;
 }
 
 typedef struct {
@@ -63,22 +64,22 @@ typedef struct {
   const uintptr_t *index_end;
   const bool *free_current;
   const bool *free_end;
-} page_visitor_context;
+} chunk_visitor_context;
 
-static bool page_visitor(
+static bool chunk_visitor(
   const RBTree_Node *node,
   RBTree_Direction dir,
   void *visitor_arg
 )
 {
-  rtems_rbheap_page *page = rtems_rbheap_page_of_node(node);
-  page_visitor_context *context = visitor_arg;
+  rtems_rbheap_chunk *chunk = rtems_rbheap_chunk_of_node(node);
+  chunk_visitor_context *context = visitor_arg;
 
   rtems_test_assert(context->index_current != context->index_end);
   rtems_test_assert(context->free_current != context->free_end);
 
-  rtems_test_assert(idx(page) == *context->index_current);
-  rtems_test_assert(rtems_rbheap_is_page_free(page) == *context->free_current);
+  rtems_test_assert(idx(chunk) == *context->index_current);
+  rtems_test_assert(rtems_rbheap_is_chunk_free(chunk) == *context->free_current);
 
   ++context->index_current;
   ++context->free_current;
@@ -86,7 +87,7 @@ static bool page_visitor(
   return false;
 }
 
-static void test_init_page_alignment(void)
+static void test_init_chunk_alignment(void)
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
   rtems_rbheap_control control;
@@ -96,7 +97,7 @@ static void test_init_page_alignment(void)
     area,
     sizeof(area),
     0,
-    extend_page_pool,
+    extend_descriptors,
     NULL
   );
   rtems_test_assert(sc == RTEMS_INVALID_NUMBER);
@@ -112,7 +113,7 @@ static void test_init_begin_greater_than_end(void)
     (void *) PAGE_SIZE,
     (uintptr_t) -PAGE_SIZE,
     PAGE_SIZE,
-    extend_page_pool,
+    extend_descriptors,
     NULL
   );
   rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
@@ -128,7 +129,7 @@ static void test_init_begin_greater_than_aligned_begin(void)
     (void *) -(PAGE_SIZE / 2),
     PAGE_SIZE,
     PAGE_SIZE,
-    extend_page_pool,
+    extend_descriptors,
     NULL
   );
   rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
@@ -144,13 +145,13 @@ static void test_init_aligned_begin_greater_than_aligned_end(void)
     (void *) PAGE_SIZE,
     PAGE_SIZE / 2,
     PAGE_SIZE,
-    extend_page_pool,
+    extend_descriptors,
     NULL
   );
   rtems_test_assert(sc == RTEMS_INVALID_ADDRESS);
 }
 
-static void test_init_empty_page_pool(void)
+static void test_init_empty_descriptors(void)
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
   rtems_rbheap_control control;
@@ -160,13 +161,13 @@ static void test_init_empty_page_pool(void)
     (void *) PAGE_SIZE,
     PAGE_SIZE,
     PAGE_SIZE,
-    rtems_rbheap_extend_page_pool_never,
+    rtems_rbheap_extend_descriptors_never,
     NULL
   );
   rtems_test_assert(sc == RTEMS_NO_MEMORY);
 }
 
-static void test_page_tree(
+static void test_chunk_tree(
   const rtems_rbheap_control *control,
   const uintptr_t *index_begin,
   const uintptr_t *index_end,
@@ -174,7 +175,7 @@ static void test_page_tree(
   const bool *free_end
 )
 {
-  page_visitor_context context = {
+  chunk_visitor_context context = {
     .index_current = index_begin,
     .index_end = index_end,
     .free_current = free_begin,
@@ -182,15 +183,15 @@ static void test_page_tree(
   };
 
   _RBTree_Iterate_unprotected(
-    &control->page_tree,
+    &control->chunk_tree,
     RBT_RIGHT,
-    page_visitor,
+    chunk_visitor,
     &context
   );
 }
 
 #define TEST_PAGE_TREE(control, indices, frees) \
-  test_page_tree( \
+  test_chunk_tree( \
     control, \
     indices, \
     &indices [sizeof(indices) / sizeof(indices [0])], \
@@ -214,7 +215,7 @@ static void test_init_successful(rtems_rbheap_control *control)
     area,
     sizeof(area),
     PAGE_SIZE,
-    extend_page_pool,
+    extend_descriptors,
     NULL
   );
   rtems_test_assert(sc == RTEMS_SUCCESSFUL);
@@ -276,7 +277,7 @@ static void test_alloc_zero(void)
   TEST_PAGE_TREE(&control, indices, frees);
 }
 
-static void test_alloc_huge_page(void)
+static void test_alloc_huge_chunk(void)
 {
   static const uintptr_t indices [] = {
     0
@@ -296,7 +297,7 @@ static void test_alloc_huge_page(void)
   TEST_PAGE_TREE(&control, indices, frees);
 }
 
-static void test_alloc_one_page(void)
+static void test_alloc_one_chunk(void)
 {
   static const uintptr_t indices_0 [] = {
     0
@@ -328,7 +329,7 @@ static void test_alloc_one_page(void)
   TEST_PAGE_TREE(&control, indices_1, frees_1);
 }
 
-static void test_alloc_many_pages(void)
+static void test_alloc_many_chunks(void)
 {
   static const uintptr_t indices_0 [] = {
     0,
@@ -385,7 +386,7 @@ static void test_alloc_many_pages(void)
   TEST_PAGE_TREE(&control, indices_1, frees_1);
 }
 
-static void test_free_invalid(void)
+static void test_free_null(void)
 {
   rtems_status_code sc = RTEMS_SUCCESSFUL;
   rtems_rbheap_control control;
@@ -393,6 +394,17 @@ static void test_free_invalid(void)
   test_init_successful(&control);
 
   sc = rtems_rbheap_free(&control, NULL);
+  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
+}
+
+static void test_free_invalid(void)
+{
+  rtems_status_code sc = RTEMS_SUCCESSFUL;
+  rtems_rbheap_control control;
+
+  test_init_successful(&control);
+
+  sc = rtems_rbheap_free(&control, (void *) 1);
   rtems_test_assert(sc == RTEMS_INVALID_ID);
 }
 
@@ -539,16 +551,17 @@ static void Init(rtems_task_argument arg)
 {
   puts("\n\n*** TEST RBHEAP 1 ***");
 
-  test_init_page_alignment();
+  test_init_chunk_alignment();
   test_init_begin_greater_than_end();
   test_init_begin_greater_than_aligned_begin();
   test_init_aligned_begin_greater_than_aligned_end();
-  test_init_empty_page_pool();
+  test_init_empty_descriptors();
   test_alloc_and_free_one();
   test_alloc_zero();
-  test_alloc_huge_page();
-  test_alloc_one_page();
-  test_alloc_many_pages();
+  test_alloc_huge_chunk();
+  test_alloc_one_chunk();
+  test_alloc_many_chunks();
+  test_free_null();
   test_free_invalid();
   test_free_double();
   test_free_merge_left_or_right(true);