1 /**
2  * A generic pool allocator.
3  *
4  * This is an efficient (constant-time allocation and freeing) allocator for objects of a fixed size
5  * and alignment (typically, fixed type), based on a fixed-size object pool.
6  *
7  * The main API works with void* buffers and a couple of helper macros are used for a type-safe
8  * (well, as far as C can go with type safety) "templatization" of the pool for a specific object
9  * type.
10  *
11  * Typical usage:
12  *
13  * typedef struct {
14  *   ...
15  * } foo_t;
16  *
17  * // "Specialize" the pool for type foo_t.
18  * #define FOO_POOL_STORAGE_SIZE(object_count) TYPED_POOL_STORAGE_SIZE(foo_t, object_count)
19  * #define FOO_POOL_STORAGE_ALIGN() TYPED_POOL_STORAGE_ALIGN(foo_t)
20  * #define DEFINE_FOO_POOL_STORAGE(name, count) DEFINE_TYPED_POOL_STORAGE(foo_t, name, count)
21  * #define FOO_POOL_INIT(pool, count, storage) TYPED_POOL_INIT(foo_t, pool, count, storage)
22  * #define FOO_POOL_ALLOC(pool) TYPED_POOL_ALLOC(foo_t, pool)
23  * #define FOO_POOL_FREE(pool, object) TYPED_POOL_FREE(foo_t, pool, object)
24  *
25  * // Allocate storage for a pool of 100 objects.
26  * DEFINE_FOO_POOL_STORAGE(foo_pool_storage, 100);
27  *
28  * // Alternatively, allocate storage some other way, using the FOO_POOL_STORAGE_SIZE() and
29  * // FOO_POOL_STORAGE_ALIGN() to determine the required size and alignment of the storage buffer.
30  *
31  * // Instantiate the pool.
32  * pool_t pool;
33  * FOO_POOL_INIT(&pool, 100, &foo_pool_storage);
34  *
35  * // Allocate a foo_t from the pool.
36  * foo_t * newfoo =  FOO_POOL_ALLOC(&pool);
37  *
38  * if (!newfoo) {
39  *   // Handle allocation failure.
40  * } else {
41  *   // Use newfoo.
42  *   ...
43  *   // Free it.
44  *   FOO_POOL_FREE(&pool, newfoo);
45  * }
46  */
47 #pragma once
48 
49 #include <lk/compiler.h>
50 #include <stddef.h>
51 #include <stdint.h>
52 
53 __BEGIN_CDECLS
54 
55 /**
56  * Pool type.
57  */
58 typedef struct {
59     // Private:
60     void *next_free;
61 } pool_t;
62 
63 /**
64  * Helper macro, not for public usage.
65  */
66 #define _MAX(a,b) \
67     ((a) > (b) ? (a) : (b))
68 
69 /**
70  * Helper macro, not for public usage.
71  */
72 #define _PAD(size, align) \
73     (((size) + (align) - 1) / (align) * (align))
74 
75 /**
76  * Calculates the required alignment for the pool storage given the size and alignment of the object
77  * type.
78  */
79 #define POOL_STORAGE_ALIGN(object_size, object_align) \
80     (_MAX(__alignof(void *), object_align))
81 
82 /**
83  * Helper macro, not for public usage.
84  */
85 #define POOL_PADDED_OBJECT_SIZE(object_size, object_align) \
86     _PAD(_MAX(sizeof(void *), object_size), POOL_STORAGE_ALIGN(object_size, object_align))
87 
88 /**
89  * Calculates the size of the pool storage given the size and alignment of the object type and the
90  * total number of objects in the pool.
91  */
92 #define POOL_STORAGE_SIZE(object_size, object_align, object_count) \
93     ((object_count) * POOL_PADDED_OBJECT_SIZE(object_size, object_align))
94 
95 /**
96  * Convenience macro for static allocation of pool storage.
97  */
98 #define DEFINE_POOL_STORAGE(name, object_size, object_align, object_count) \
99     uint8_t name[POOL_STORAGE_SIZE(object_size, object_align, object_count)] \
100     __attribute__((aligned(POOL_STORAGE_ALIGN(object_size, object_align))))
101 
102 /**
103  * Initialize the pool object.
104  * Provided storage must be aligned to POOL_STORAGE_ALIGN(object_size, object_align) and of size of
105  * at least POOL_STORAGE_SIZE(object_size, object_align, object_count).
106  * The DEFINE_POOL_STORAGE(...) makes this process simple for cases when the storage is to be
107  * statically allocated.
108  */
109 void pool_init(pool_t *pool,
110                size_t object_size,
111                size_t object_align,
112                size_t object_count,
113                void *storage);
114 
115 /**
116  * Allocate an object from the pool.
117  * Returns NULL if all pool objects are currently allocated.
118  * Otherwise, the return value is guarantee to be aligned at object_align and be at least of size
119  * object_size.
120  */
121 void *pool_alloc(pool_t *pool);
122 
123 /**
124  * Free an object previously allocated with pool_alloc.
125  */
126 void pool_free(pool_t *pool, void *object);
127 
128 /**
129  * This set of macros help in "specializing" the pool API to a specific object type.
130  * See example at the header of this file.
131  */
132 
133 #define TYPED_POOL_STORAGE_SIZE(type, object_count) \
134     POOL_STORAGE_SIZE(sizeof(type), __alignof(type), object_count)
135 
136 #define TYPED_POOL_STORAGE_ALIGN(type) \
137     POOL_STORAGE_ALIGN(sizeof(type), __alignof(type))
138 
139 #define DEFINE_TYPED_POOL_STORAGE(type, name, count) \
140     DEFINE_POOL_STORAGE(name, sizeof(type), __alignof(type), count)
141 
142 #define TYPED_POOL_INIT(type, pool, count, storage) \
143     pool_init(pool, sizeof(type), __alignof(type), count, storage)
144 
145 #define TYPED_POOL_ALLOC(type, pool) \
146     ((type*) pool_alloc(pool))
147 
148 #define TYPED_POOL_FREE(type, pool, object) \
149     pool_free(pool, object)
150 
151 __END_CDECLS
152