1 /*
2 * This file is part of libplacebo.
3 *
4 * libplacebo is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU Lesser General Public
6 * License as published by the Free Software Foundation; either
7 * version 2.1 of the License, or (at your option) any later version.
8 *
9 * libplacebo is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU Lesser General Public License for more details.
13 *
14 * You should have received a copy of the GNU Lesser General Public
15 * License along with libplacebo. If not, see <http://www.gnu.org/licenses/>.
16 */
17
18 #include "common.h"
19
20 struct header {
21 #ifndef NDEBUG
22 #define MAGIC 0x20210119LU
23 uint32_t magic;
24 #endif
25 size_t size;
26 struct header *parent;
27 struct ext *ext;
28
29 // Pointer to actual data, for alignment purposes
30 intmax_t data[1];
31 };
32
33 // Lazily allocated, to save space for leaf allocations and allocations which
34 // don't need fancy requirements
35 struct ext {
36 size_t num_children;
37 size_t children_size; // total allocated size of `children`
38 struct header *children[];
39 };
40
41 #define PTR_OFFSET offsetof(struct header, data)
42 #define MAX_ALLOC (SIZE_MAX - PTR_OFFSET)
43 #define MINIMUM_CHILDREN 4
44
get_header(void * ptr)45 static inline struct header *get_header(void *ptr)
46 {
47 if (!ptr)
48 return NULL;
49
50 struct header *hdr = (struct header *) ((uintptr_t) ptr - PTR_OFFSET);
51 #ifndef NDEBUG
52 assert(hdr->magic == MAGIC);
53 #endif
54
55 return hdr;
56 }
57
oom()58 static inline void *oom()
59 {
60 fprintf(stderr, "out of memory\n");
61 abort();
62 }
63
alloc_ext(struct header * h)64 static inline struct ext *alloc_ext(struct header *h)
65 {
66 if (!h)
67 return NULL;
68
69 if (!h->ext) {
70 h->ext = malloc(sizeof(struct ext) + MINIMUM_CHILDREN * sizeof(void *));
71 if (!h->ext)
72 oom();
73 h->ext->num_children = 0;
74 h->ext->children_size = MINIMUM_CHILDREN;
75 }
76
77 return h->ext;
78 }
79
attach_child(struct header * parent,struct header * child)80 static inline void attach_child(struct header *parent, struct header *child)
81 {
82 child->parent = parent;
83 if (!parent)
84 return;
85
86
87 struct ext *ext = alloc_ext(parent);
88 if (ext->num_children == ext->children_size) {
89 size_t new_size = ext->children_size * 2;
90 ext = realloc(ext, sizeof(struct ext) + new_size * sizeof(void *));
91 if (!ext)
92 oom();
93 ext->children_size = new_size;
94 parent->ext = ext;
95 }
96
97 ext->children[ext->num_children++] = child;
98 }
99
unlink_child(struct header * parent,struct header * child)100 static inline void unlink_child(struct header *parent, struct header *child)
101 {
102 child->parent = NULL;
103 if (!parent)
104 return;
105
106 struct ext *ext = parent->ext;
107 for (size_t i = 0; i < ext->num_children; i++) {
108 if (ext->children[i] == child) {
109 memmove(&ext->children[i], &ext->children[i + 1],
110 (--ext->num_children - i) * sizeof(ext->children[0]));
111 return;
112 }
113 }
114
115 assert(!"unlinking orphaned child?");
116 }
117
pl_alloc(void * parent,size_t size)118 void *pl_alloc(void *parent, size_t size)
119 {
120 if (size >= MAX_ALLOC)
121 return oom();
122
123 struct header *h = malloc(PTR_OFFSET + size);
124 if (!h)
125 return oom();
126
127 #ifndef NDEBUG
128 h->magic = MAGIC;
129 #endif
130 h->size = size;
131 h->ext = NULL;
132
133 attach_child(get_header(parent), h);
134 return h->data;
135 }
136
pl_zalloc(void * parent,size_t size)137 void *pl_zalloc(void *parent, size_t size)
138 {
139 if (size >= MAX_ALLOC)
140 return oom();
141
142 struct header *h = calloc(1, PTR_OFFSET + size);
143 if (!h)
144 return oom();
145
146 #ifndef NDEBUG
147 h->magic = MAGIC;
148 #endif
149 h->size = size;
150
151 attach_child(get_header(parent), h);
152 return h->data;
153 }
154
pl_realloc(void * parent,void * ptr,size_t size)155 void *pl_realloc(void *parent, void *ptr, size_t size)
156 {
157 if (size >= MAX_ALLOC)
158 return oom();
159 if (!ptr)
160 return pl_alloc(parent, size);
161
162 struct header *h = get_header(ptr);
163 assert(get_header(parent) == h->parent);
164 if (h->size == size)
165 return ptr;
166
167 struct header *old_h = h;
168 h = realloc(h, PTR_OFFSET + size);
169 if (!h)
170 return oom();
171
172 h->size = size;
173
174 if (h != old_h) {
175 if (h->parent) {
176 struct ext *ext = h->parent->ext;
177 for (size_t i = 0; i < ext->num_children; i++) {
178 if (ext->children[i] == old_h) {
179 ext->children[i] = h;
180 goto done_reparenting;
181 }
182 }
183 assert(!"reallocating orphaned child?");
184 }
185 done_reparenting:
186
187 if (h->ext) {
188 for (size_t i = 0; i < h->ext->num_children; i++)
189 h->ext->children[i]->parent = h;
190 }
191 }
192
193 return h->data;
194 }
195
pl_free(void * ptr)196 void pl_free(void *ptr)
197 {
198 struct header *h = get_header(ptr);
199 if (!h)
200 return;
201
202 pl_free_children(ptr);
203 unlink_child(h->parent, h);
204
205 free(h->ext);
206 free(h);
207 }
208
pl_free_children(void * ptr)209 void pl_free_children(void *ptr)
210 {
211 struct header *h = get_header(ptr);
212 if (!h || !h->ext)
213 return;
214
215 #ifndef NDEBUG
216 // this detects recursive hierarchies
217 h->magic = 0;
218 #endif
219
220 for (size_t i = 0; i < h->ext->num_children; i++) {
221 h->ext->children[i]->parent = NULL; // prevent recursive access
222 pl_free(h->ext->children[i]->data);
223 }
224
225 #ifndef NDEBUG
226 h->magic = MAGIC;
227 #endif
228 }
229
pl_get_size(void * ptr)230 size_t pl_get_size(void *ptr)
231 {
232 struct header *h = get_header(ptr);
233 return h ? h->size : 0;
234 }
235
pl_steal(void * parent,void * ptr)236 void *pl_steal(void *parent, void *ptr)
237 {
238 struct header *h = get_header(ptr);
239 if (!h)
240 return NULL;
241
242 struct header *new_par = get_header(parent);
243 if (new_par != h->parent) {
244 unlink_child(h->parent, h);
245 attach_child(new_par, h);
246 }
247
248 return h->data;
249 }
250
pl_memdup(void * parent,const void * ptr,size_t size)251 void *pl_memdup(void *parent, const void *ptr, size_t size)
252 {
253 if (!size)
254 return NULL;
255
256 void *new = pl_alloc(parent, size);
257 if (!new)
258 return oom();
259
260 assert(ptr);
261 memcpy(new, ptr, size);
262 return new;
263 }
264
pl_str0dup0(void * parent,const char * str)265 char *pl_str0dup0(void *parent, const char *str)
266 {
267 if (!str)
268 return NULL;
269
270 return pl_memdup(parent, str, strlen(str) + 1);
271 }
272
pl_strndup0(void * parent,const char * str,size_t size)273 char *pl_strndup0(void *parent, const char *str, size_t size)
274 {
275 if (!str)
276 return NULL;
277
278 size_t str_size = strnlen(str, size);
279 char *new = pl_alloc(parent, str_size + 1);
280 if (!new)
281 return oom();
282 memcpy(new, str, str_size);
283 new[str_size] = '\0';
284 return new;
285 }
286
287 struct pl_ref {
288 pl_rc_t rc;
289 };
290
pl_ref_new(void * parent)291 struct pl_ref *pl_ref_new(void *parent)
292 {
293 struct pl_ref *ref = pl_zalloc_ptr(parent, ref);
294 if (!ref)
295 return oom();
296
297 pl_rc_init(&ref->rc);
298 return ref;
299 }
300
pl_ref_dup(struct pl_ref * ref)301 struct pl_ref *pl_ref_dup(struct pl_ref *ref)
302 {
303 if (!ref)
304 return NULL;
305
306 pl_rc_ref(&ref->rc);
307 return ref;
308 }
309
pl_ref_deref(struct pl_ref ** refp)310 void pl_ref_deref(struct pl_ref **refp)
311 {
312 struct pl_ref *ref = *refp;
313 if (!ref)
314 return;
315
316 if (pl_rc_deref(&ref->rc)) {
317 pl_free(ref);
318 *refp = NULL;
319 }
320 }
321
pl_asprintf(void * parent,const char * fmt,...)322 char *pl_asprintf(void *parent, const char *fmt, ...)
323 {
324 char *str;
325 va_list ap;
326 va_start(ap, fmt);
327 str = pl_vasprintf(parent, fmt, ap);
328 va_end(ap);
329 return str;
330 }
331
pl_vasprintf(void * parent,const char * fmt,va_list ap)332 char *pl_vasprintf(void *parent, const char *fmt, va_list ap)
333 {
334 // First, we need to determine the size that will be required for
335 // printing the entire string. Do this by making a copy of the va_list
336 // and printing it to a null buffer.
337 va_list copy;
338 va_copy(copy, ap);
339 int size = vsnprintf(NULL, 0, fmt, copy);
340 va_end(copy);
341 if (size < 0)
342 return NULL;
343
344 char *str = pl_alloc(parent, size + 1);
345 vsnprintf(str, size + 1, fmt, ap);
346 return str;
347 }
348