From e75263083e83cac921475d0a89d8b3b398f9b902 Mon Sep 17 00:00:00 2001 From: Sebastian Huber Date: Tue, 10 Apr 2012 11:19:39 +0200 Subject: 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 +++++++++++++++++++++++++++++++++++++ 4 files changed, 413 insertions(+), 1 deletion(-) create mode 100644 cpukit/sapi/include/rtems/rbheap.h create mode 100644 cpukit/sapi/src/rbheap.c (limited to 'cpukit') 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 + * + * + * 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 +#include +#include + +#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 + * + * + * 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 + +#include + +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); + } +} -- cgit v1.2.3