[rtems commit] rbheap: API changes and documentation
Sebastian Huber
sebh at rtems.org
Wed Apr 18 10:15:30 UTC 2012
Module: rtems
Branch: master
Commit: 5c51ba1333d96e2ada2c374ba22b551d179e6685
Changeset: http://git.rtems.org/rtems/commit/?id=5c51ba1333d96e2ada2c374ba22b551d179e6685
Author: Sebastian Huber <sebastian.huber at embedded-brains.de>
Date: Mon Apr 16 10:38:31 2012 +0200
rbheap: API changes and documentation
---
cpukit/sapi/include/rtems/rbheap.h | 187 ++++++++++++++++++++++++++++++-----
cpukit/sapi/src/rbheap.c | 189 ++++++++++++++++++-----------------
testsuites/libtests/rbheap01/init.c | 89 ++++++++++-------
3 files changed, 309 insertions(+), 156 deletions(-)
diff --git a/cpukit/sapi/include/rtems/rbheap.h b/cpukit/sapi/include/rtems/rbheap.h
index be1eec6..5481e89 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 7986325..7facf4f 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 a66cc24..ce180d8 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);
More information about the vc
mailing list