Changeset 5c51ba1 in rtems


Ignore:
Timestamp:
Apr 16, 2012, 8:38:31 AM (8 years ago)
Author:
Sebastian Huber <sebastian.huber@…>
Branches:
4.11, master
Children:
6845f80, e1417b3
Parents:
7a01a888
git-author:
Sebastian Huber <sebastian.huber@…> (04/16/12 08:38:31)
git-committer:
Sebastian Huber <sebastian.huber@…> (04/18/12 10:18:11)
Message:

rbheap: API changes and documentation

Files:
3 edited

Legend:

Unmodified
Added
Removed
  • cpukit/sapi/include/rtems/rbheap.h

    r7a01a888 r5c51ba1  
    3737 * @brief Red-Black Tree Heap API.
    3838 *
    39  * In the Red-Black Tree Heap the administration data structures are not
    40  * contained in the managed memory area.  This can be used for example in a
    41  * task stack allocator which protects the task stacks from access by other
    42  * tasks.
     39 * The red-black tree heap provides a memory allocator suitable to implement
     40 * the malloc() and free() interface.  It uses a first-fit allocation strategy.
     41 * In the red-black tree heap the administration data structures are not
     42 * contained in the managed memory area.  Thus writing beyond the boundaries of
     43 * a chunk does not damage the data to maintain the heap.  This can be used for
     44 * example in a task stack allocator which protects the task stacks from access
     45 * by other tasks.  The allocated and free memory parts of the managed area are
     46 * called chunks.  Each chunk needs a descriptor which is stored outside of the
     47 * managed area.
    4348 *
    4449 * @{
    4550 */
    4651
     52/**
     53 * @brief Red-black heap chunk descriptor.
     54 */
    4755typedef struct {
     56  /**
     57   * This chain node can be used in two chains
     58   *  - the chain of spare chunk descriptors and
     59   *  - the chain of free chunks in the managed memory area.
     60   *
     61   * In case this chain node is not part of a chain, the chunk represents a
     62   * used chunk in the managed memory area.
     63   */
    4864  rtems_chain_node chain_node;
     65
     66  /**
     67   * Tree node for chunks that represent a part of the managed memory area.
     68   * These chunks are either free or used.
     69   */
    4970  rtems_rbtree_node tree_node;
     71
     72  /**
     73   * Begin address of the chunk.  The address alignment it specified in the
     74   * @ref rtems_rbheap_control.
     75   */
    5076  uintptr_t begin;
     77
     78  /**
     79   * Size of the chunk in bytes.
     80   */
    5181  uintptr_t size;
    52 } rtems_rbheap_page;
     82} rtems_rbheap_chunk;
    5383
    5484typedef struct rtems_rbheap_control rtems_rbheap_control;
    5585
    56 typedef void (*rtems_rbheap_extend_page_pool)(rtems_rbheap_control *control);
    57 
     86/**
     87 * @brief Handler to extend the available chunk descriptors.
     88 *
     89 * This handler is called when no more chunk descriptors are available.  An
     90 * example implementation is this:
     91 *
     92 * @code
     93 * void extend_descriptors_with_malloc(rtems_rbheap_control *control)
     94 * {
     95 *   rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
     96 *
     97 *   if (chunk != NULL) {
     98 *     rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
     99 *   }
     100 * }
     101 * @endcode
     102 *
     103 * @see rtems_rbheap_extend_descriptors_never() and
     104 * rtems_rbheap_extend_descriptors_with_malloc().
     105 */
     106typedef void (*rtems_rbheap_extend_descriptors)(rtems_rbheap_control *control);
     107
     108/**
     109 * @brief Red-black heap control.
     110 */
    58111struct rtems_rbheap_control {
    59   rtems_chain_control free_chain;
    60   rtems_chain_control pool_chain;
    61   rtems_rbtree_control page_tree;
    62   uintptr_t page_alignment;
    63   rtems_rbheap_extend_page_pool extend_page_pool;
     112  /**
     113   * Chain of free chunks in the managed memory area.
     114   */
     115  rtems_chain_control free_chunk_chain;
     116
     117  /**
     118   * Chain of free chunk descriptors.  Descriptors are consumed during
     119   * allocation and may be produced during free if contiguous chunks can be
     120   * coalesced.  In case of descriptor starvation the @ref extend_descriptors
     121   * handler will be called.
     122   */
     123  rtems_chain_control spare_descriptor_chain;
     124
     125  /**
     126   * Tree of chunks representing the state of the managed memory area.
     127   */
     128  rtems_rbtree_control chunk_tree;
     129
     130  /**
     131   * Minimum chunk begin alignment in bytes.
     132   */
     133  uintptr_t alignment;
     134
     135  /**
     136   * Handler to extend the available chunk descriptors.
     137   */
     138  rtems_rbheap_extend_descriptors extend_descriptors;
     139
     140  /**
     141   * User specified argument handler for private handler data.
     142   */
    64143  void *handler_arg;
    65144};
    66145
     146/**
     147 * @brief Initializes the red-black tree heap @a control.
     148 *
     149 * @param[in, out] control The red-black tree heap.
     150 * @param[in] area_begin The managed memory area begin.
     151 * @param[in] area_size The managed memory area size.
     152 * @param[in] alignment The minimum chunk alignment.
     153 * @param[in] extend_descriptors The handler to extend the available chunk
     154 * descriptors.
     155 * @param[in] handler_arg The handler argument.
     156 *
     157 * @retval RTEMS_SUCCESSFUL Successful operation.
     158 * @retval RTEMS_INVALID_NUMBER The alignment is not positive.
     159 * @retval RTEMS_INVALID_ADDRESS The memory area is invalid.
     160 * @retval RTEMS_NO_MEMORY Not enough chunk descriptors.
     161 */
    67162rtems_status_code rtems_rbheap_initialize(
    68163  rtems_rbheap_control *control,
    69164  void *area_begin,
    70165  uintptr_t area_size,
    71   uintptr_t page_alignment,
    72   rtems_rbheap_extend_page_pool extend_page_pool,
     166  uintptr_t alignment,
     167  rtems_rbheap_extend_descriptors extend_descriptors,
    73168  void *handler_arg
    74169);
    75170
     171/**
     172 * @brief Allocates a chunk of memory of at least @a size bytes from the
     173 * red-black tree heap @a control.
     174 *
     175 * The chunk begin is aligned by the value specified in
     176 * rtems_rbheap_initialize().
     177 *
     178 * @param[in, out] control The red-black tree heap.
     179 * @param[in] size The requested chunk size in bytes.
     180 *
     181 * @retval NULL Not enough free space in the heap.
     182 * @retval otherwise Pointer to allocated chunk of memory.
     183 */
    76184void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size);
    77185
     186/**
     187 * @brief Frees a chunk of memory @a ptr allocated from the red-black tree heap
     188 * @a control.
     189 *
     190 * @param[in, out] control The red-black tree heap.
     191 * @param[in] ptr The pointer to the chunk of memory.
     192 *
     193 * @retval RTEMS_SUCCESSFUL Successful operation.
     194 * @retval RTEMS_INVALID_ID The chunk of memory is not a valid chunk in the
     195 * red-black tree heap.
     196 * @retval RTEMS_INCORRECT_STATE The chunk of memory is not in the right state.
     197 */
    78198rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr);
    79199
    80 static inline rtems_chain_control *rtems_rbheap_get_pool_chain(
     200static inline rtems_chain_control *rtems_rbheap_get_spare_descriptor_chain(
    81201  rtems_rbheap_control *control
    82202)
    83203{
    84   return &control->pool_chain;
    85 }
    86 
    87 static inline void rtems_rbheap_set_extend_page_pool(
    88   rtems_rbheap_control *control,
    89   rtems_rbheap_extend_page_pool extend_page_pool
    90 )
    91 {
    92   control->extend_page_pool = extend_page_pool;
     204  return &control->spare_descriptor_chain;
     205}
     206
     207static inline void rtems_rbheap_add_to_spare_descriptor_chain(
     208  rtems_rbheap_control *control,
     209  rtems_rbheap_chunk *chunk
     210)
     211{
     212  rtems_chain_control *chain =
     213    rtems_rbheap_get_spare_descriptor_chain(control);
     214
     215  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
     216}
     217
     218static inline void rtems_rbheap_set_extend_descriptors(
     219  rtems_rbheap_control *control,
     220  rtems_rbheap_extend_descriptors extend_descriptors
     221)
     222{
     223  control->extend_descriptors = extend_descriptors;
    93224}
    94225
     
    108239}
    109240
    110 void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control);
    111 
    112 void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control);
     241/**
     242 * @brief Chunk descriptor extend handler that does nothing.
     243 */
     244void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control);
     245
     246/**
     247 * @brief Chunk descriptor extend handler that uses malloc().
     248 */
     249void rtems_rbheap_extend_descriptors_with_malloc(
     250  rtems_rbheap_control *control
     251);
    113252
    114253/** @} */
     
    116255/* Private API */
    117256
    118 #define rtems_rbheap_page_of_node(node) \
    119   rtems_rbtree_container_of(node, rtems_rbheap_page, tree_node)
    120 
    121 static inline bool rtems_rbheap_is_page_free(const rtems_rbheap_page *page)
    122 {
    123   return !rtems_chain_is_node_off_chain(&page->chain_node);
     257#define rtems_rbheap_chunk_of_node(node) \
     258  rtems_rbtree_container_of(node, rtems_rbheap_chunk, tree_node)
     259
     260static inline bool rtems_rbheap_is_chunk_free(const rtems_rbheap_chunk *chunk)
     261{
     262  return !rtems_chain_is_node_off_chain(&chunk->chain_node);
    124263}
    125264
  • cpukit/sapi/src/rbheap.c

    r7a01a888 r5c51ba1  
    2929#include <stdlib.h>
    3030
    31 static uintptr_t align_up(uintptr_t page_alignment, uintptr_t value)
    32 {
    33   uintptr_t excess = value % page_alignment;
     31static uintptr_t align_up(uintptr_t alignment, uintptr_t value)
     32{
     33  uintptr_t excess = value % alignment;
    3434
    3535  if (excess > 0) {
    36     value += page_alignment - excess;
     36    value += alignment - excess;
    3737  }
    3838
     
    4040}
    4141
    42 static uintptr_t align_down(uintptr_t page_alignment, uintptr_t value)
    43 {
    44   uintptr_t excess = value % page_alignment;
     42static uintptr_t align_down(uintptr_t alignment, uintptr_t value)
     43{
     44  uintptr_t excess = value % alignment;
    4545
    4646  return value - excess;
    4747}
    4848
    49 static int page_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
    50 {
    51   const rtems_rbheap_page *left = rtems_rbheap_page_of_node(a);
    52   const rtems_rbheap_page *right = rtems_rbheap_page_of_node(b);
     49static int chunk_compare(const rtems_rbtree_node *a, const rtems_rbtree_node *b)
     50{
     51  const rtems_rbheap_chunk *left = rtems_rbheap_chunk_of_node(a);
     52  const rtems_rbheap_chunk *right = rtems_rbheap_chunk_of_node(b);
    5353
    5454  return (int) (left->begin - right->begin);
    5555}
    5656
    57 static rtems_rbheap_page *get_page(rtems_rbheap_control *control)
    58 {
    59   rtems_chain_control *pool_chain = &control->pool_chain;
    60   rtems_chain_node *page = rtems_chain_get(pool_chain);
    61 
    62   if (page == NULL) {
    63     (*control->extend_page_pool)(control);
    64     page = rtems_chain_get(pool_chain);
    65   }
    66 
    67   return (rtems_rbheap_page *) page;
     57static rtems_rbheap_chunk *get_chunk(rtems_rbheap_control *control)
     58{
     59  rtems_chain_control *chain = &control->spare_descriptor_chain;
     60  rtems_chain_node *chunk = rtems_chain_get_unprotected(chain);
     61
     62  if (chunk == NULL) {
     63    (*control->extend_descriptors)(control);
     64    chunk = rtems_chain_get_unprotected(chain);
     65  }
     66
     67  return (rtems_rbheap_chunk *) chunk;
    6868}
    6969
    7070static void add_to_chain(
    7171  rtems_chain_control *chain,
    72   rtems_rbheap_page *page
    73 )
    74 {
    75   rtems_chain_prepend_unprotected(chain, &page->chain_node);
     72  rtems_rbheap_chunk *chunk
     73)
     74{
     75  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
    7676}
    7777
    7878static void insert_into_tree(
    7979  rtems_rbtree_control *tree,
    80   rtems_rbheap_page *page
    81 )
    82 {
    83   _RBTree_Insert_unprotected(tree, &page->tree_node);
     80  rtems_rbheap_chunk *chunk
     81)
     82{
     83  _RBTree_Insert_unprotected(tree, &chunk->tree_node);
    8484}
    8585
     
    8888  void *area_begin,
    8989  uintptr_t area_size,
    90   uintptr_t page_alignment,
    91   rtems_rbheap_extend_page_pool extend_page_pool,
     90  uintptr_t alignment,
     91  rtems_rbheap_extend_descriptors extend_descriptors,
    9292  void *handler_arg
    9393)
     
    9595  rtems_status_code sc = RTEMS_SUCCESSFUL;
    9696
    97   if (page_alignment > 0) {
     97  if (alignment > 0) {
    9898    uintptr_t begin = (uintptr_t) area_begin;
    9999    uintptr_t end = begin + area_size;
    100     uintptr_t aligned_begin = align_up(page_alignment, begin);
    101     uintptr_t aligned_end = align_down(page_alignment, end);
     100    uintptr_t aligned_begin = align_up(alignment, begin);
     101    uintptr_t aligned_end = align_down(alignment, end);
    102102
    103103    if (begin < end && begin <= aligned_begin && aligned_begin < aligned_end) {
    104       rtems_chain_control *free_chain = &control->free_chain;
    105       rtems_rbtree_control *page_tree = &control->page_tree;
    106       rtems_rbheap_page *first = NULL;
     104      rtems_chain_control *free_chain = &control->free_chunk_chain;
     105      rtems_rbtree_control *chunk_tree = &control->chunk_tree;
     106      rtems_rbheap_chunk *first = NULL;
    107107
    108108      rtems_chain_initialize_empty(free_chain);
    109       rtems_chain_initialize_empty(&control->pool_chain);
    110       rtems_rbtree_initialize_empty(page_tree, page_compare, true);
    111       control->page_alignment = page_alignment;
     109      rtems_chain_initialize_empty(&control->spare_descriptor_chain);
     110      rtems_rbtree_initialize_empty(chunk_tree, chunk_compare, true);
     111      control->alignment = alignment;
    112112      control->handler_arg = handler_arg;
    113       control->extend_page_pool = extend_page_pool;
    114 
    115       first = get_page(control);
     113      control->extend_descriptors = extend_descriptors;
     114
     115      first = get_chunk(control);
    116116      if (first != NULL) {
    117117        first->begin = aligned_begin;
    118118        first->size = aligned_end - aligned_begin;
    119119        add_to_chain(free_chain, first);
    120         insert_into_tree(page_tree, first);
     120        insert_into_tree(chunk_tree, first);
    121121      } else {
    122122        sc = RTEMS_NO_MEMORY;
     
    132132}
    133133
    134 static rtems_rbheap_page *search_free_page(
     134static rtems_rbheap_chunk *search_free_chunk(
    135135  rtems_chain_control *free_chain,
    136136  size_t size
     
    139139  rtems_chain_node *current = rtems_chain_first(free_chain);
    140140  const rtems_chain_node *tail = rtems_chain_tail(free_chain);
    141   rtems_rbheap_page *big_enough = NULL;
     141  rtems_rbheap_chunk *big_enough = NULL;
    142142
    143143  while (current != tail && big_enough == NULL) {
    144     rtems_rbheap_page *free_page = (rtems_rbheap_page *) current;
    145 
    146     if (free_page->size >= size) {
    147       big_enough = free_page;
     144    rtems_rbheap_chunk *free_chunk = (rtems_rbheap_chunk *) current;
     145
     146    if (free_chunk->size >= size) {
     147      big_enough = free_chunk;
    148148    }
    149149
     
    157157{
    158158  void *ptr = NULL;
    159   rtems_chain_control *free_chain = &control->free_chain;
    160   rtems_rbtree_control *page_tree = &control->page_tree;
    161   uintptr_t page_alignment = control->page_alignment;
    162   uintptr_t aligned_size = align_up(page_alignment, size);
     159  rtems_chain_control *free_chain = &control->free_chunk_chain;
     160  rtems_rbtree_control *chunk_tree = &control->chunk_tree;
     161  uintptr_t alignment = control->alignment;
     162  uintptr_t aligned_size = align_up(alignment, size);
    163163
    164164  if (size > 0 && size <= aligned_size) {
    165     rtems_rbheap_page *free_page = search_free_page(free_chain, aligned_size);
    166 
    167     if (free_page != NULL) {
    168       uintptr_t free_size = free_page->size;
     165    rtems_rbheap_chunk *free_chunk = search_free_chunk(free_chain, aligned_size);
     166
     167    if (free_chunk != NULL) {
     168      uintptr_t free_size = free_chunk->size;
    169169
    170170      if (free_size > aligned_size) {
    171         rtems_rbheap_page *new_page = get_page(control);
    172 
    173         if (new_page != NULL) {
     171        rtems_rbheap_chunk *new_chunk = get_chunk(control);
     172
     173        if (new_chunk != NULL) {
    174174          uintptr_t new_free_size = free_size - aligned_size;
    175175
    176           free_page->size = new_free_size;
    177           new_page->begin = free_page->begin + new_free_size;
    178           new_page->size = aligned_size;
    179           rtems_chain_set_off_chain(&new_page->chain_node);
    180           insert_into_tree(page_tree, new_page);
    181           ptr = (void *) new_page->begin;
     176          free_chunk->size = new_free_size;
     177          new_chunk->begin = free_chunk->begin + new_free_size;
     178          new_chunk->size = aligned_size;
     179          rtems_chain_set_off_chain(&new_chunk->chain_node);
     180          insert_into_tree(chunk_tree, new_chunk);
     181          ptr = (void *) new_chunk->begin;
    182182        }
    183183      } else {
    184         rtems_chain_extract_unprotected(&free_page->chain_node);
    185         rtems_chain_set_off_chain(&free_page->chain_node);
    186         ptr = (void *) free_page->begin;
     184        rtems_chain_extract_unprotected(&free_chunk->chain_node);
     185        rtems_chain_set_off_chain(&free_chunk->chain_node);
     186        ptr = (void *) free_chunk->begin;
    187187      }
    188188    }
     
    192192}
    193193
    194 #define NULL_PAGE rtems_rbheap_page_of_node(NULL)
    195 
    196 static rtems_rbheap_page *find(rtems_rbtree_control *page_tree, uintptr_t key)
    197 {
    198   rtems_rbheap_page page = { .begin = key };
    199 
    200   return rtems_rbheap_page_of_node(
    201     _RBTree_Find_unprotected(page_tree, &page.tree_node)
     194#define NULL_PAGE rtems_rbheap_chunk_of_node(NULL)
     195
     196static rtems_rbheap_chunk *find(rtems_rbtree_control *chunk_tree, uintptr_t key)
     197{
     198  rtems_rbheap_chunk chunk = { .begin = key };
     199
     200  return rtems_rbheap_chunk_of_node(
     201    _RBTree_Find_unprotected(chunk_tree, &chunk.tree_node)
    202202  );
    203203}
    204204
    205 static rtems_rbheap_page *get_next(
    206   const rtems_rbtree_control *page_tree,
    207   const rtems_rbheap_page *page,
     205static rtems_rbheap_chunk *get_next(
     206  const rtems_rbtree_control *chunk_tree,
     207  const rtems_rbheap_chunk *chunk,
    208208  RBTree_Direction dir
    209209)
    210210{
    211   return rtems_rbheap_page_of_node(
    212     _RBTree_Next_unprotected(page_tree, &page->tree_node, dir)
     211  return rtems_rbheap_chunk_of_node(
     212    _RBTree_Next_unprotected(chunk_tree, &chunk->tree_node, dir)
    213213  );
    214214}
     
    216216static void check_and_merge(
    217217  rtems_chain_control *free_chain,
    218   rtems_rbtree_control *page_tree,
    219   rtems_rbheap_page *a,
    220   rtems_rbheap_page *b
    221 )
    222 {
    223   if (b != NULL_PAGE && rtems_rbheap_is_page_free(b)) {
     218  rtems_rbtree_control *chunk_tree,
     219  rtems_rbheap_chunk *a,
     220  rtems_rbheap_chunk *b
     221)
     222{
     223  if (b != NULL_PAGE && rtems_rbheap_is_chunk_free(b)) {
    224224    if (b->begin < a->begin) {
    225       rtems_rbheap_page *t = a;
     225      rtems_rbheap_chunk *t = a;
    226226
    227227      a = b;
     
    232232    rtems_chain_extract_unprotected(&b->chain_node);
    233233    add_to_chain(free_chain, b);
    234     _RBTree_Extract_unprotected(page_tree, &b->tree_node);
     234    _RBTree_Extract_unprotected(chunk_tree, &b->tree_node);
    235235  }
    236236}
     
    239239{
    240240  rtems_status_code sc = RTEMS_SUCCESSFUL;
    241   rtems_chain_control *free_chain = &control->free_chain;
    242   rtems_rbtree_control *page_tree = &control->page_tree;
    243   rtems_rbheap_page *page = find(page_tree, (uintptr_t) ptr);
    244 
    245   if (page != NULL_PAGE) {
    246     if (!rtems_rbheap_is_page_free(page)) {
    247       rtems_rbheap_page *pred = get_next(page_tree, page, RBT_LEFT);
    248       rtems_rbheap_page *succ = get_next(page_tree, page, RBT_RIGHT);
    249 
    250       check_and_merge(free_chain, page_tree, page, succ);
    251       add_to_chain(free_chain, page);
    252       check_and_merge(free_chain, page_tree, page, pred);
     241
     242  if (ptr != NULL) {
     243    rtems_chain_control *free_chain = &control->free_chunk_chain;
     244    rtems_rbtree_control *chunk_tree = &control->chunk_tree;
     245    rtems_rbheap_chunk *chunk = find(chunk_tree, (uintptr_t) ptr);
     246
     247    if (chunk != NULL_PAGE) {
     248      if (!rtems_rbheap_is_chunk_free(chunk)) {
     249        rtems_rbheap_chunk *pred = get_next(chunk_tree, chunk, RBT_LEFT);
     250        rtems_rbheap_chunk *succ = get_next(chunk_tree, chunk, RBT_RIGHT);
     251
     252        check_and_merge(free_chain, chunk_tree, chunk, succ);
     253        add_to_chain(free_chain, chunk);
     254        check_and_merge(free_chain, chunk_tree, chunk, pred);
     255      } else {
     256        sc = RTEMS_INCORRECT_STATE;
     257      }
    253258    } else {
    254       sc = RTEMS_INCORRECT_STATE;
    255     }
    256   } else {
    257     sc = RTEMS_INVALID_ID;
     259      sc = RTEMS_INVALID_ID;
     260    }
    258261  }
    259262
     
    261264}
    262265
    263 void rtems_rbheap_extend_page_pool_never(rtems_rbheap_control *control)
     266void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control)
    264267{
    265268  /* Do nothing */
    266269}
    267270
    268 void rtems_rbheap_extend_page_pool_with_malloc(rtems_rbheap_control *control)
    269 {
    270   rtems_rbheap_page *page = malloc(sizeof(*page));
    271 
    272   if (page != NULL) {
    273     rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
    274 
    275     add_to_chain(pool_chain, page);
    276   }
    277 }
     271void rtems_rbheap_extend_descriptors_with_malloc(rtems_rbheap_control *control)
     272{
     273  rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
     274
     275  if (chunk != NULL) {
     276    rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
     277  }
     278}
  • testsuites/libtests/rbheap01/init.c

    r7a01a888 r5c51ba1  
    2828static char area [PAGE_SIZE * PAGE_COUNT + PAGE_SIZE - 1];
    2929
    30 static rtems_rbheap_page pages [PAGE_COUNT];
    31 
    32 static void extend_page_pool(rtems_rbheap_control *control)
    33 {
    34   rtems_chain_control *pool_chain = rtems_rbheap_get_pool_chain(control);
    35 
    36   rtems_rbheap_set_extend_page_pool(
     30static rtems_rbheap_chunk chunks [PAGE_COUNT];
     31
     32static void extend_descriptors(rtems_rbheap_control *control)
     33{
     34  rtems_chain_control *chain =
     35    rtems_rbheap_get_spare_descriptor_chain(control);
     36
     37  rtems_rbheap_set_extend_descriptors(
    3738    control,
    38     rtems_rbheap_extend_page_pool_never
     39    rtems_rbheap_extend_descriptors_never
    3940  );
    4041
    4142  rtems_chain_initialize(
    42     pool_chain,
    43     pages,
     43    chain,
     44    chunks,
    4445    PAGE_COUNT,
    45     sizeof(pages [0])
    46   );
    47 }
    48 
    49 static uintptr_t idx(const rtems_rbheap_page *page)
     46    sizeof(chunks [0])
     47  );
     48}
     49
     50static uintptr_t idx(const rtems_rbheap_chunk *chunk)
    5051{
    5152  uintptr_t base = (uintptr_t) area;
     
    5657  }
    5758
    58   return (page->begin - base) / PAGE_SIZE;
     59  return (chunk->begin - base) / PAGE_SIZE;
    5960}
    6061
     
    6465  const bool *free_current;
    6566  const bool *free_end;
    66 } page_visitor_context;
    67 
    68 static bool page_visitor(
     67} chunk_visitor_context;
     68
     69static bool chunk_visitor(
    6970  const RBTree_Node *node,
    7071  RBTree_Direction dir,
     
    7273)
    7374{
    74   rtems_rbheap_page *page = rtems_rbheap_page_of_node(node);
    75   page_visitor_context *context = visitor_arg;
     75  rtems_rbheap_chunk *chunk = rtems_rbheap_chunk_of_node(node);
     76  chunk_visitor_context *context = visitor_arg;
    7677
    7778  rtems_test_assert(context->index_current != context->index_end);
    7879  rtems_test_assert(context->free_current != context->free_end);
    7980
    80   rtems_test_assert(idx(page) == *context->index_current);
    81   rtems_test_assert(rtems_rbheap_is_page_free(page) == *context->free_current);
     81  rtems_test_assert(idx(chunk) == *context->index_current);
     82  rtems_test_assert(rtems_rbheap_is_chunk_free(chunk) == *context->free_current);
    8283
    8384  ++context->index_current;
     
    8788}
    8889
    89 static void test_init_page_alignment(void)
     90static void test_init_chunk_alignment(void)
    9091{
    9192  rtems_status_code sc = RTEMS_SUCCESSFUL;
     
    9798    sizeof(area),
    9899    0,
    99     extend_page_pool,
     100    extend_descriptors,
    100101    NULL
    101102  );
     
    113114    (uintptr_t) -PAGE_SIZE,
    114115    PAGE_SIZE,
    115     extend_page_pool,
     116    extend_descriptors,
    116117    NULL
    117118  );
     
    129130    PAGE_SIZE,
    130131    PAGE_SIZE,
    131     extend_page_pool,
     132    extend_descriptors,
    132133    NULL
    133134  );
     
    145146    PAGE_SIZE / 2,
    146147    PAGE_SIZE,
    147     extend_page_pool,
     148    extend_descriptors,
    148149    NULL
    149150  );
     
    151152}
    152153
    153 static void test_init_empty_page_pool(void)
     154static void test_init_empty_descriptors(void)
    154155{
    155156  rtems_status_code sc = RTEMS_SUCCESSFUL;
     
    161162    PAGE_SIZE,
    162163    PAGE_SIZE,
    163     rtems_rbheap_extend_page_pool_never,
     164    rtems_rbheap_extend_descriptors_never,
    164165    NULL
    165166  );
     
    167168}
    168169
    169 static void test_page_tree(
     170static void test_chunk_tree(
    170171  const rtems_rbheap_control *control,
    171172  const uintptr_t *index_begin,
     
    175176)
    176177{
    177   page_visitor_context context = {
     178  chunk_visitor_context context = {
    178179    .index_current = index_begin,
    179180    .index_end = index_end,
     
    183184
    184185  _RBTree_Iterate_unprotected(
    185     &control->page_tree,
     186    &control->chunk_tree,
    186187    RBT_RIGHT,
    187     page_visitor,
     188    chunk_visitor,
    188189    &context
    189190  );
     
    191192
    192193#define TEST_PAGE_TREE(control, indices, frees) \
    193   test_page_tree( \
     194  test_chunk_tree( \
    194195    control, \
    195196    indices, \
     
    215216    sizeof(area),
    216217    PAGE_SIZE,
    217     extend_page_pool,
     218    extend_descriptors,
    218219    NULL
    219220  );
     
    277278}
    278279
    279 static void test_alloc_huge_page(void)
     280static void test_alloc_huge_chunk(void)
    280281{
    281282  static const uintptr_t indices [] = {
     
    297298}
    298299
    299 static void test_alloc_one_page(void)
     300static void test_alloc_one_chunk(void)
    300301{
    301302  static const uintptr_t indices_0 [] = {
     
    329330}
    330331
    331 static void test_alloc_many_pages(void)
     332static void test_alloc_many_chunks(void)
    332333{
    333334  static const uintptr_t indices_0 [] = {
     
    386387}
    387388
     389static void test_free_null(void)
     390{
     391  rtems_status_code sc = RTEMS_SUCCESSFUL;
     392  rtems_rbheap_control control;
     393
     394  test_init_successful(&control);
     395
     396  sc = rtems_rbheap_free(&control, NULL);
     397  rtems_test_assert(sc == RTEMS_SUCCESSFUL);
     398}
     399
    388400static void test_free_invalid(void)
    389401{
     
    393405  test_init_successful(&control);
    394406
    395   sc = rtems_rbheap_free(&control, NULL);
     407  sc = rtems_rbheap_free(&control, (void *) 1);
    396408  rtems_test_assert(sc == RTEMS_INVALID_ID);
    397409}
     
    540552  puts("\n\n*** TEST RBHEAP 1 ***");
    541553
    542   test_init_page_alignment();
     554  test_init_chunk_alignment();
    543555  test_init_begin_greater_than_end();
    544556  test_init_begin_greater_than_aligned_begin();
    545557  test_init_aligned_begin_greater_than_aligned_end();
    546   test_init_empty_page_pool();
     558  test_init_empty_descriptors();
    547559  test_alloc_and_free_one();
    548560  test_alloc_zero();
    549   test_alloc_huge_page();
    550   test_alloc_one_page();
    551   test_alloc_many_pages();
     561  test_alloc_huge_chunk();
     562  test_alloc_one_chunk();
     563  test_alloc_many_chunks();
     564  test_free_null();
    552565  test_free_invalid();
    553566  test_free_double();
Note: See TracChangeset for help on using the changeset viewer.