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.

4 files changed, 413 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);
+  }
+}