summaryrefslogtreecommitdiffstats
path: root/cpukit/include/rtems/rbheap.h
blob: b1f7b562c8b2684fa1a091e5e9078803c80dec78 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
/* SPDX-License-Identifier: BSD-2-Clause */

/**
 * @file
 *
 * @ingroup RTEMSAPIRBHeap
 *
 * @brief This header file provides the Red-Black Tree Heap API.
 */

/*
 * Copyright (c) 2012 embedded brains GmbH.  All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 */

#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 RTEMSAPIRBHeap Red-Black Tree Heap
 *
 * @ingroup RTEMSAPI
 *
 * @brief The red-black tree heap provides a memory allocator using a red-black
 *   tree to maintain blocks of memory.
 *
 * 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_chunk;

typedef struct rtems_rbheap_control rtems_rbheap_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 {
  /**
   * 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_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 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_spare_descriptor_chain(
  rtems_rbheap_control *control
)
{
  return &control->spare_descriptor_chain;
}

static inline void rtems_rbheap_add_to_spare_descriptor_chain(
  rtems_rbheap_control *control,
  rtems_rbheap_chunk *chunk
)
{
  rtems_chain_control *chain =
    rtems_rbheap_get_spare_descriptor_chain(control);

  rtems_chain_initialize_node(&chunk->chain_node);
  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(
  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;
}

/**
 * @brief Chunk descriptor extend handler that does nothing.
 */
void rtems_rbheap_extend_descriptors_never(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_chunk_of_node(node) \
  RTEMS_CONTAINER_OF(node, rtems_rbheap_chunk, tree_node)

static inline bool rtems_rbheap_is_chunk_free(const rtems_rbheap_chunk *chunk)
{
  return !rtems_chain_is_node_off_chain(&chunk->chain_node);
}

#ifdef __cplusplus
}
#endif

#endif /* _RTEMS_RBHEAP_H */