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
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
#include "smallobj.h"
#include <assert.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>
// When defined, this symbol causes freed objects to be overwritten so that
// it's easier to detect access-after-free bugs.
#define OVERWRITE_MEM
// Forward-declare the chunk_t struct type.
typedef struct chunk_t chunk_t;
/*!
* This struct is used by the small-object allocator to represent a pool of
* objects that are all some small fixed size. The pool scales up and down
* based on the number of objects that are in use; this is done by allocating
* multiple "chunks" (chunks are allocated using malloc()), each which can hold
* some number of objects of the specified size. Chunks are maintained in a
* singly linked list. When a chunk is no longer in use, it is removed from the
* list of chunks, and the chunk's memory is released from the pool using
* free().
*/
struct smallobj_pool_t {
// The size of objects in this small-object pool.
int objsize;
// The total number of objects allocated per chunk.
int objects_per_chunk;
// The list of chunks in the small-object pool.
chunk_t *chunk_list;
};
/*!
* This struct represents one chunk of objects in a small-object pool. The
* pool's "objects_per_chunk" value specifies how many objects fit in each
* chunk. The last member "mem" is an array of size
* pool->objsize * pool->objects_per_chunk bytes.
*/
struct chunk_t {
// The pool that the chunk is from.
smallobj_pool_t *pool;
// Index of the next available object in the chunk.
int next_available;
// How many small objects in this chunk have been released.
int num_freed;
// A pointer to the next chunk in the pool, or NULL if this is the last
// chunk in the pool.
chunk_t *next_chunk;
// The start of the memory area for this chunk.
char mem[];
};
// === GENERAL POOL MANAGEMENT FUNCTIONS =======================================
/*!
* Given a pool, returns how much memory each chunk in the pool provides for
* allocations. In other words, this is the size of the "mem" member at the
* end of chunks in a given pool.
*/
size_t chunk_mem_size(smallobj_pool_t *pool) {
return pool->objects_per_chunk * pool->objsize;
}
/*!
* Initialize a small-object pool of objects of the specified size. The
* initial pool will have no chunks allocated in it.
*
* If malloc() cannot allocate the small-object pool (unlikely) then this
* function will report an error and then abort().
*/
smallobj_pool_t * make_so_pool(size_t objsize, int objects_per_chunk) {
assert(objsize >= sizeof(intptr_t));
// Allocate an empty pool.
smallobj_pool_t *pool = malloc(sizeof(smallobj_pool_t));
if (pool == NULL) {
fprintf(stderr, "ERROR: Couldn't allocate small-object pool");
abort();
}
pool->objsize = objsize;
pool->objects_per_chunk = objects_per_chunk;
pool->chunk_list = NULL;
return pool;
}
/*!
* Release a small-object pool. Any pointers to objects in this pool are
* no longer valid after release.
*/
void release_so_pool(smallobj_pool_t *pool) {
assert(pool != NULL);
// Iterate through all chunks and free() each one.
chunk_t *chunk = pool->chunk_list;
while (chunk != NULL) {
chunk_t *next = chunk->next_chunk;
free(chunk);
chunk = next;
}
// Free the pool itself.
free(pool);
}
/*!
* Reports the total size of the small-object pool in bytes, including the size
* of the pool structure, and the sizes of all chunks allocated for the pool.
* This value will never be zero, since the pool data structure always occupies
* some number of bytes.
*/
size_t total_pool_size(smallobj_pool_t *pool) {
assert(pool != NULL);
size_t size = sizeof(smallobj_pool_t);
chunk_t *chunk = pool->chunk_list;
while (chunk != NULL) {
size += sizeof(chunk_t) + chunk_mem_size(pool);
chunk = chunk->next_chunk;
}
return size;
}
// === ALLOCATION FUNCTIONS ====================================================
/*!
* This helper function initializes a new chunk for use in a small-object pool.
* The function calls malloc() to allocate the chunk's memory, and then it
* performs any necessary initialization on the chunk's contents to prepare for
* small-object allocations.
*/
chunk_t *init_new_chunk(smallobj_pool_t *pool) {
size_t chunk_size = sizeof(chunk_t) + chunk_mem_size(pool);
chunk_t *chunk = malloc(chunk_size);
if (chunk == NULL) {
fprintf(stderr, "ERROR: Couldn't allocate chunk for pool %p", pool);
abort();
}
chunk->pool = pool;
chunk->next_available = 0;
chunk->num_freed = 0;
chunk->next_chunk = NULL;
return chunk;
}
/*!
* This helper function searches through the small-object pool for a chunk that
* has room for another allocation. If all chunks are full, a new chunk will
* be initialized and added to the pool.
*/
chunk_t * get_nonfull_chunk(smallobj_pool_t *pool) {
chunk_t *chunk = pool->chunk_list;
chunk_t *prev = NULL;
// Try to find a chunk that has available space.
while (chunk != NULL) {
if (chunk->next_available < pool->objects_per_chunk)
break;
prev = chunk;
chunk = chunk->next_chunk;
}
// If all chunks are full, we need to allocate a new chunk.
if (chunk == NULL) {
chunk = init_new_chunk(pool);
if (prev != NULL)
prev->next_chunk = chunk;
else
pool->chunk_list = chunk;
}
return chunk;
}
/*!
* Given a non-full chunk from a pool, this helper function returns a newly
* allocated object from the chunk. The helper also performs any bookkeeping
* necessary to record that the object has been allocated.
*/
void * alloc_object_from_chunk(chunk_t *chunk) {
assert(chunk != NULL);
// Make sure the chunk isn't already full.
assert(chunk->next_available < chunk->pool->objects_per_chunk);
// Allocate a new object from the chunk.
void *obj = chunk->mem + chunk->next_available * chunk->pool->objsize;
chunk->next_available++;
return obj;
}
/*!
* Allocate a small object from the specified pool. The pool itself knows what
* size objects it produces, so this function does not take a size argument.
*
* This function always returns a non-NULL value, which is not very realistic,
* but certainly keeps life simple. If a chunk-allocation failure occurs, the
* function will print an error and then abort().
*/
void * so_alloc(smallobj_pool_t *pool) {
assert(pool != NULL);
// Find or allocate a chunk that has available space.
chunk_t *chunk = get_nonfull_chunk(pool);
// The chunk should be able to hold a new allocation.
assert(chunk != NULL);
assert(chunk->next_available < pool->objects_per_chunk);
// Allocate a new object from the chunk.
return alloc_object_from_chunk(chunk);
}
// === DEALLOCATION FUNCTIONS ==================================================
/*!
* Returns true if the specified pointer falls within the specified chunk,
* false otherwise.
*/
bool is_object_in_chunk(void *obj, chunk_t *chunk) {
return obj >= (void *) chunk->mem &&
obj < (void *) (chunk->mem + chunk_mem_size(chunk->pool));
}
/*! Records that the specified object in the chunk has been freed. */
void free_object_in_chunk(void *obj, chunk_t *chunk) {
assert(obj != NULL);
assert(chunk != NULL);
assert(is_object_in_chunk(obj, chunk));
// Record that the object has been freed.
chunk->num_freed++;
}
/*!
* Returns true if the chunk no longer holds any allocated objects; false
* otherwise.
*/
bool is_chunk_empty(chunk_t *chunk) {
return chunk->num_freed == chunk->pool->objects_per_chunk;
}
/*!
* Release a small object back to the specified pool.
*
* It is an error to pass in a pointer to an object that is not from this pool.
* this kind of error is usually detectable and will result in an error message
* being printed and the program aborted.
*
* It is also an error to free the same object twice in a row. This kind of
* error is not detectable and may cause all manner of chaos to ensue.
*/
void so_free(smallobj_pool_t *pool, void *obj) {
#ifdef OVERWRITE_MEM
// Overwrite the object that was just released, so that access-after-free
// bugs are more obvious.
memset(obj, 0xEE, pool->objsize);
#endif
// Find the chunk that corresponds to the memory being freed. Also keep
// track of the "previous chunk" so that we can remove completely empty
// chunks.
chunk_t *chunk = pool->chunk_list;
chunk_t *prev = NULL;
while (chunk != NULL) {
if (is_object_in_chunk(obj, chunk))
break; // Found the chunk containing the allocation.
prev = chunk;
chunk = chunk->next_chunk;
}
if (chunk == NULL) {
fprintf(stderr, "ERROR: Pointer %p isn't from pool %p", obj, pool);
abort();
}
free_object_in_chunk(obj, chunk);
if (is_chunk_empty(chunk)) {
// This chunk has been completely freed. Remove it from the list.
if (prev == NULL)
pool->chunk_list = chunk->next_chunk;
else
prev->next_chunk = chunk->next_chunk;
#ifdef OVERWRITE_MEM
// Overwrite the chunk so that access-after-free bugs are more obvious.
memset(chunk, 0xEF, sizeof(chunk_t) + chunk_mem_size(pool));
#endif
free(chunk);
}
}