source: rtems/cpukit/include/rtems/rbheap.h @ 2afb22b

Last change on this file since 2afb22b was 2afb22b, checked in by Chris Johns <chrisj@…>, on Dec 23, 2017 at 7:18:56 AM

Remove make preinstall

A speciality of the RTEMS build system was the make preinstall step. It
copied header files from arbitrary locations into the build tree. The
header files were included via the -Bsome/build/tree/path GCC command
line option.

This has at least seven problems:

  • The make preinstall step itself needs time and disk space.
  • Errors in header files show up in the build tree copy. This makes it hard for editors to open the right file to fix the error.
  • There is no clear relationship between source and build tree header files. This makes an audit of the build process difficult.
  • The visibility of all header files in the build tree makes it difficult to enforce API barriers. For example it is discouraged to use BSP-specifics in the cpukit.
  • An introduction of a new build system is difficult.
  • Include paths specified by the -B option are system headers. This may suppress warnings.
  • The parallel build had sporadic failures on some hosts.

This patch removes the make preinstall step. All installed header
files are moved to dedicated include directories in the source tree.
Let @RTEMS_CPU@ be the target architecture, e.g. arm, powerpc, sparc,
etc. Let @RTEMS_BSP_FAMILIY@ be a BSP family base directory, e.g.
erc32, imx, qoriq, etc.

The new cpukit include directories are:

  • cpukit/include
  • cpukit/score/cpu/@RTEMS_CPU@/include
  • cpukit/libnetworking

The new BSP include directories are:

  • bsps/include
  • bsps/@RTEMS_CPU@/include
  • bsps/@RTEMS_CPU@/@RTEMS_BSP_FAMILIY@/include

There are build tree include directories for generated files.

The include directory order favours the most general header file, e.g.
it is not possible to override general header files via the include path
order.

The "bootstrap -p" option was removed. The new "bootstrap -H" option
should be used to regenerate the "headers.am" files.

Update #3254.

  • Property mode set to 100644
File size: 7.0 KB
Line 
1/**
2 * @file
3 *
4 * @brief Red-Black Tree Heap API
5 */
6
7/*
8 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
9 *
10 *  embedded brains GmbH
11 *  Obere Lagerstr. 30
12 *  82178 Puchheim
13 *  Germany
14 *  <rtems@embedded-brains.de>
15 *
16 * The license and distribution terms for this file may be
17 * found in the file LICENSE in this distribution or at
18 * http://www.rtems.org/license/LICENSE.
19 */
20
21#ifndef _RTEMS_RBHEAP_H
22#define _RTEMS_RBHEAP_H
23
24#include <rtems.h>
25#include <rtems/chain.h>
26#include <rtems/rbtree.h>
27
28#ifdef __cplusplus
29extern "C" {
30#endif
31
32/**
33 * @defgroup RBHeap Red-Black Tree Heap
34 *
35 * @ingroup ClassicRTEMS
36 *
37 * @brief Red-Black Tree Heap API.
38 *
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.
48 */
49/**@{*/
50
51/**
52 * @brief Red-black heap chunk descriptor.
53 */
54typedef struct {
55  /**
56   * This chain node can be used in two chains
57   *  - the chain of spare chunk descriptors and
58   *  - the chain of free chunks in the managed memory area.
59   *
60   * In case this chain node is not part of a chain, the chunk represents a
61   * used chunk in the managed memory area.
62   */
63  rtems_chain_node chain_node;
64
65  /**
66   * Tree node for chunks that represent a part of the managed memory area.
67   * These chunks are either free or used.
68   */
69  rtems_rbtree_node tree_node;
70
71  /**
72   * Begin address of the chunk.  The address alignment it specified in the
73   * @ref rtems_rbheap_control.
74   */
75  uintptr_t begin;
76
77  /**
78   * Size of the chunk in bytes.
79   */
80  uintptr_t size;
81} rtems_rbheap_chunk;
82
83typedef struct rtems_rbheap_control rtems_rbheap_control;
84
85/**
86 * @brief Handler to extend the available chunk descriptors.
87 *
88 * This handler is called when no more chunk descriptors are available.  An
89 * example implementation is this:
90 *
91 * @code
92 * void extend_descriptors_with_malloc(rtems_rbheap_control *control)
93 * {
94 *   rtems_rbheap_chunk *chunk = malloc(sizeof(*chunk));
95 *
96 *   if (chunk != NULL) {
97 *     rtems_rbheap_add_to_spare_descriptor_chain(control, chunk);
98 *   }
99 * }
100 * @endcode
101 *
102 * @see rtems_rbheap_extend_descriptors_never() and
103 * rtems_rbheap_extend_descriptors_with_malloc().
104 */
105typedef void (*rtems_rbheap_extend_descriptors)(rtems_rbheap_control *control);
106
107/**
108 * @brief Red-black heap control.
109 */
110struct rtems_rbheap_control {
111  /**
112   * Chain of free chunks in the managed memory area.
113   */
114  rtems_chain_control free_chunk_chain;
115
116  /**
117   * Chain of free chunk descriptors.  Descriptors are consumed during
118   * allocation and may be produced during free if contiguous chunks can be
119   * coalesced.  In case of descriptor starvation the @ref extend_descriptors
120   * handler will be called.
121   */
122  rtems_chain_control spare_descriptor_chain;
123
124  /**
125   * Tree of chunks representing the state of the managed memory area.
126   */
127  rtems_rbtree_control chunk_tree;
128
129  /**
130   * Minimum chunk begin alignment in bytes.
131   */
132  uintptr_t alignment;
133
134  /**
135   * Handler to extend the available chunk descriptors.
136   */
137  rtems_rbheap_extend_descriptors extend_descriptors;
138
139  /**
140   * User specified argument handler for private handler data.
141   */
142  void *handler_arg;
143};
144
145/**
146 * @brief Initializes the red-black tree heap @a control.
147 *
148 * @param[in, out] control The red-black tree heap.
149 * @param[in] area_begin The managed memory area begin.
150 * @param[in] area_size The managed memory area size.
151 * @param[in] alignment The minimum chunk alignment.
152 * @param[in] extend_descriptors The handler to extend the available chunk
153 * descriptors.
154 * @param[in] handler_arg The handler argument.
155 *
156 * @retval RTEMS_SUCCESSFUL Successful operation.
157 * @retval RTEMS_INVALID_ADDRESS The memory area is invalid.
158 * @retval RTEMS_NO_MEMORY Not enough chunk descriptors.
159 */
160rtems_status_code rtems_rbheap_initialize(
161  rtems_rbheap_control *control,
162  void *area_begin,
163  uintptr_t area_size,
164  uintptr_t alignment,
165  rtems_rbheap_extend_descriptors extend_descriptors,
166  void *handler_arg
167);
168
169/**
170 * @brief Allocates a chunk of memory of at least @a size bytes from the
171 * red-black tree heap @a control.
172 *
173 * The chunk begin is aligned by the value specified in
174 * rtems_rbheap_initialize().
175 *
176 * @param[in, out] control The red-black tree heap.
177 * @param[in] size The requested chunk size in bytes.
178 *
179 * @retval NULL Not enough free space in the heap.
180 * @retval otherwise Pointer to allocated chunk of memory.
181 */
182void *rtems_rbheap_allocate(rtems_rbheap_control *control, size_t size);
183
184/**
185 * @brief Frees a chunk of memory @a ptr allocated from the red-black tree heap
186 * @a control.
187 *
188 * @param[in, out] control The red-black tree heap.
189 * @param[in] ptr The pointer to the chunk of memory.
190 *
191 * @retval RTEMS_SUCCESSFUL Successful operation.
192 * @retval RTEMS_INVALID_ID The chunk of memory is not a valid chunk in the
193 * red-black tree heap.
194 * @retval RTEMS_INCORRECT_STATE The chunk of memory is not in the right state.
195 */
196rtems_status_code rtems_rbheap_free(rtems_rbheap_control *control, void *ptr);
197
198static inline rtems_chain_control *rtems_rbheap_get_spare_descriptor_chain(
199  rtems_rbheap_control *control
200)
201{
202  return &control->spare_descriptor_chain;
203}
204
205static inline void rtems_rbheap_add_to_spare_descriptor_chain(
206  rtems_rbheap_control *control,
207  rtems_rbheap_chunk *chunk
208)
209{
210  rtems_chain_control *chain =
211    rtems_rbheap_get_spare_descriptor_chain(control);
212
213  rtems_chain_initialize_node(&chunk->chain_node);
214  rtems_chain_prepend_unprotected(chain, &chunk->chain_node);
215}
216
217static inline void rtems_rbheap_set_extend_descriptors(
218  rtems_rbheap_control *control,
219  rtems_rbheap_extend_descriptors extend_descriptors
220)
221{
222  control->extend_descriptors = extend_descriptors;
223}
224
225static inline void *rtems_rbheap_get_handler_arg(
226  const rtems_rbheap_control *control
227)
228{
229  return control->handler_arg;
230}
231
232static inline void rtems_rbheap_set_handler_arg(
233  rtems_rbheap_control *control,
234  void *handler_arg
235)
236{
237  control->handler_arg = handler_arg;
238}
239
240/**
241 * @brief Chunk descriptor extend handler that does nothing.
242 */
243void rtems_rbheap_extend_descriptors_never(rtems_rbheap_control *control);
244
245/**
246 * @brief Chunk descriptor extend handler that uses malloc().
247 */
248void rtems_rbheap_extend_descriptors_with_malloc(
249  rtems_rbheap_control *control
250);
251
252/** @} */
253
254/* Private API */
255
256#define rtems_rbheap_chunk_of_node(node) \
257  RTEMS_CONTAINER_OF(node, rtems_rbheap_chunk, tree_node)
258
259static inline bool rtems_rbheap_is_chunk_free(const rtems_rbheap_chunk *chunk)
260{
261  return !rtems_chain_is_node_off_chain(&chunk->chain_node);
262}
263
264#ifdef __cplusplus
265}
266#endif
267
268#endif /* _RTEMS_RBHEAP_H */
Note: See TracBrowser for help on using the repository browser.