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
|
/*
* Copyright (c) 2020 Cisco and/or its affiliates.
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at:
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
/**
* \file array.h
* \brief Fixed-size pool allocator.
*
* This memory pool allocates a single block of memory that is used to efficiently
* allocate/deallocate fixed-size blocks for high churn data structures.
*
* Internally this data structure leverages a vector for managing elements (and
* it thus resizeable if needed), as well as a list of free indices (in the
* form of another vector) and a bitmap marking free indices also (for fast
* iteration).
*
* The internal API manipulates a pointer to the vector that that is can be
* seamlessly resized, and a more convenient user interface is provided through
* macros.
*
* The vector of free indices is managed as a stack where elements indices are
* retrieved from and put back to the end of the vector. In the bitmap,
* available elements are set to 1, and unset to 0 when in use.
*
* The pool is not currently resized down when releasing elements.
*
* It is freely inspired (and simplified) from the VPP infra infrastructure
* library.
*/
#ifndef UTIL_POOL_H
#define UTIL_POOL_H
#include <stdint.h>
#include "bitmap.h"
#include "vector.h"
/* Pool header */
typedef struct {
size_t elt_size;
size_t max_size;
uint_fast32_t * free_bitmap; /* bitmap of free indices */
off_t * free_indices; /* vector of free indices */
} pool_hdr_t;
#define POOL_HDRLEN SIZEOF_ALIGNED(pool_hdr_t)
/* This header actually prepends the actual content of the pool. */
#define pool_hdr(pool) ((pool_hdr_t *)((uint8_t*)(pool) - POOL_HDRLEN))
/******************************************************************************/
/* Helpers */
/** Local variable naming macro. */
#define _pool_var(v) _pool_##v
/**
* @brief Allocate and initialize a pool data structure (helper).
*
* @param[in,out] pool_ptr Pointer to the pool data structure.
* @param[in] elt_size Size of elements in vector.
* @param[in] max_size Maximum size.
*
* NOTE: that an empty pool might be equal to NULL.
*/
void _pool_init(void ** pool_ptr, size_t elt_size, size_t max_size);
/**
* @brief Free a pool data structure (helper).
*
* @param[in] pool_ptr Pointer to the pool data structure.
*/
void _pool_free(void ** pool_ptr);
/**
* @brief Resize a pool data structure (helper).
*
* @param pool_ptr Pointer to the pool data structure.
*
* This function should only be called internally, as the resize is implicitly
* done (if allowed by the maximum size) when the user tries to get a new slot.
*/
void _pool_resize(void ** pool_ptr, size_t elt_size);
/**
* @brief Get a free element from the pool data structure (helper).
*
* @param[in] pool Pointer to the pool data structure to use.
* @param[in,out] elt Pointer to an empty element that will be used to return
* the allocated one from the pool.
*
* NOTES:
* - The memory chunk is cleared upon attribution
*/
void _pool_get(void ** pool, void ** elt, size_t elt_size);
/**
* @brief Put an element back into the pool data structure (helper).
*
* @param[in] pool_ptr Pointer to the pool data structure to use.
* @param[in] elt Pointer to the pool element to put back.
*/
void _pool_put(void ** pool, void ** elt, size_t elt_size);
/******************************************************************************/
/* Public API */
/**
* @brief Allocate and initialize a pool data structure.
*
* @param[in,out] pool Pointer to the pool data structure.
* @param[in] elt_size Size of elements in pool.
* @param[in] max_size Maximum size.
*
* NOTE: that an empty pool might be equal to NULL.
*/
#define pool_init(pool, max_size) \
_pool_init((void**)&pool, sizeof(pool[0]), max_size);
/**
* @brief Free a pool data structure.
*
* @param[in] pool The pool data structure to free.
*/
#define pool_free(pool) _pool_free((void**)&pool);
/**
* @brief Get a free element from the pool data structure.
*
* @param[in] pool The pool data structure to use.
* @param[in,out] elt An empty element that will be used to return the
* allocated one from the pool.
*
* NOTES:
* - The memory chunk is cleared upon attribution
*/
#define pool_get(pool, elt) _pool_get((void**)&pool, (void**)&elt, sizeof(elt))
/**
* @brief Put an element back into the pool data structure.
*
* @param[in] pool The pool data structure to use.
* @param[in] elt The pool element to put back.
*/
#define pool_put(pool, elt) _pool_put((void**)&pool, (void**)&elt, sizeof(elt))
/**
* @brief Validate a pool element by index.
*
* @param[in] pool The pool data structure to use.
* @param[in] id The index of the element to validate.
*
* @return bool A flag indicating whether the index is valid or not.
*/
#define pool_validate_id(pool, id) \
bitmap_is_unset((pool_hdr(pool))->free_bitmap, (id))
/**
* @brief Returns the current length of the pool.
*
* @param[in] pool The pool data structure for which to return the length.
*
* @return size_t The current length of the pool.
*
* NOTE:
* - The pool length corresponds to the number of allocated elements, not the
* size of the pool.
*/
#define pool_len(pool) \
(pool_hdr(pool)->max_size - vector_len((pool_hdr(pool)->free_indices)))
/**
* @brief Enumerate elements from a pool.
*
* @param[in] pool The pool data structure to enumerate.
* @param[in, out] i An integer that will be used for enumeration.
* @param[in, out] eltp A pointer to the element type that will be used for
* enumeration.
* @param[in] BODY Block to execute during enumeration.
*
* Enumeration will iteratively execute BODY with (i, eltp) corresponding
* respectively to the index and element found in the pool.
*
* NOTE: i stars at 0.
*/
#define pool_enumerate(pool, i, eltp, BODY) \
do { \
pool_hdr_t * _pool_var(ph) = pool_hdr(pool); \
uint_fast32_t * _pool_var(fb) = _pool_var(ph)->free_bitmap; \
for((i) = 0; (i) < _pool_var(ph)->max_size; (i)++) { \
if (bitmap_is_unset(_pool_var(fb), (i))) \
continue; \
eltp = (pool) + (i); \
do { BODY; } while (0); \
} \
} while(0)
/**
* @brief Iterate over elements in a pool.
*
* @param[in] pool The pool data structure to iterate over.
* @param[in,out] eltp A pointer to the element type that will be used for
* iteration.
* @param[in] BODY Block to execute during iteration.
*
* Iteration will execute BODY with eltp corresponding successively to all
* elements found in the pool. It is implemented using the more generic
* enumeration function.
*/
#define pool_foreach(pool, eltp, BODY) \
do { \
unsigned _pool_var(i); \
pool_enumerate((pool), _pool_var(i), (eltp), BODY); \
} while(0)
#endif /* UTIL_POOL_H */
|
