1 /*
2 * Copyright (c) 2009-2021, Google LLC
3 * All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are met:
7 * * Redistributions of source code must retain the above copyright
8 * notice, this list of conditions and the following disclaimer.
9 * * Redistributions in binary form must reproduce the above copyright
10 * notice, this list of conditions and the following disclaimer in the
11 * documentation and/or other materials provided with the distribution.
12 * * Neither the name of Google LLC nor the
13 * names of its contributors may be used to endorse or promote products
14 * derived from this software without specific prior written permission.
15 *
16 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND
17 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
18 * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
19 * DISCLAIMED. IN NO EVENT SHALL Google LLC BE LIABLE FOR ANY
20 * DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
21 * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
22 * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
23 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
24 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
25 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
26 */
27
28 #include "upb/upb_internal.h"
29
30 #include <errno.h>
31 #include <stdarg.h>
32 #include <stddef.h>
33 #include <stdint.h>
34 #include <stdio.h>
35 #include <stdlib.h>
36 #include <string.h>
37
38 #include "upb/port_def.inc"
39
40 /* upb_status *****************************************************************/
41
upb_status_clear(upb_status * status)42 void upb_status_clear(upb_status *status) {
43 if (!status) return;
44 status->ok = true;
45 status->msg[0] = '\0';
46 }
47
upb_ok(const upb_status * status)48 bool upb_ok(const upb_status *status) { return status->ok; }
49
upb_status_errmsg(const upb_status * status)50 const char *upb_status_errmsg(const upb_status *status) { return status->msg; }
51
upb_status_seterrmsg(upb_status * status,const char * msg)52 void upb_status_seterrmsg(upb_status *status, const char *msg) {
53 if (!status) return;
54 status->ok = false;
55 strncpy(status->msg, msg, UPB_STATUS_MAX_MESSAGE - 1);
56 status->msg[UPB_STATUS_MAX_MESSAGE - 1] = '\0';
57 }
58
upb_status_seterrf(upb_status * status,const char * fmt,...)59 void upb_status_seterrf(upb_status *status, const char *fmt, ...) {
60 va_list args;
61 va_start(args, fmt);
62 upb_status_vseterrf(status, fmt, args);
63 va_end(args);
64 }
65
upb_status_vseterrf(upb_status * status,const char * fmt,va_list args)66 void upb_status_vseterrf(upb_status *status, const char *fmt, va_list args) {
67 if (!status) return;
68 status->ok = false;
69 vsnprintf(status->msg, sizeof(status->msg), fmt, args);
70 status->msg[UPB_STATUS_MAX_MESSAGE - 1] = '\0';
71 }
72
upb_status_vappenderrf(upb_status * status,const char * fmt,va_list args)73 void upb_status_vappenderrf(upb_status *status, const char *fmt, va_list args) {
74 size_t len;
75 if (!status) return;
76 status->ok = false;
77 len = strlen(status->msg);
78 vsnprintf(status->msg + len, sizeof(status->msg) - len, fmt, args);
79 status->msg[UPB_STATUS_MAX_MESSAGE - 1] = '\0';
80 }
81
82 /* upb_alloc ******************************************************************/
83
upb_global_allocfunc(upb_alloc * alloc,void * ptr,size_t oldsize,size_t size)84 static void *upb_global_allocfunc(upb_alloc *alloc, void *ptr, size_t oldsize,
85 size_t size) {
86 UPB_UNUSED(alloc);
87 UPB_UNUSED(oldsize);
88 if (size == 0) {
89 free(ptr);
90 return NULL;
91 } else {
92 return realloc(ptr, size);
93 }
94 }
95
upb_cleanup_pointer(uintptr_t cleanup_metadata)96 static uint32_t *upb_cleanup_pointer(uintptr_t cleanup_metadata) {
97 return (uint32_t *)(cleanup_metadata & ~0x1);
98 }
99
upb_cleanup_has_initial_block(uintptr_t cleanup_metadata)100 static bool upb_cleanup_has_initial_block(uintptr_t cleanup_metadata) {
101 return cleanup_metadata & 0x1;
102 }
103
upb_cleanup_metadata(uint32_t * cleanup,bool has_initial_block)104 static uintptr_t upb_cleanup_metadata(uint32_t *cleanup,
105 bool has_initial_block) {
106 return (uintptr_t)cleanup | has_initial_block;
107 }
108
109 upb_alloc upb_alloc_global = {&upb_global_allocfunc};
110
111 /* upb_arena ******************************************************************/
112
113 /* Be conservative and choose 16 in case anyone is using SSE. */
114
115 struct mem_block {
116 struct mem_block *next;
117 uint32_t size;
118 uint32_t cleanups;
119 /* Data follows. */
120 };
121
122 typedef struct cleanup_ent {
123 upb_cleanup_func *cleanup;
124 void *ud;
125 } cleanup_ent;
126
127 static const size_t memblock_reserve = UPB_ALIGN_UP(sizeof(mem_block), 16);
128
arena_findroot(upb_arena * a)129 static upb_arena *arena_findroot(upb_arena *a) {
130 /* Path splitting keeps time complexity down, see:
131 * https://en.wikipedia.org/wiki/Disjoint-set_data_structure */
132 while (a->parent != a) {
133 upb_arena *next = a->parent;
134 a->parent = next->parent;
135 a = next;
136 }
137 return a;
138 }
139
upb_arena_addblock(upb_arena * a,upb_arena * root,void * ptr,size_t size)140 static void upb_arena_addblock(upb_arena *a, upb_arena *root, void *ptr,
141 size_t size) {
142 mem_block *block = ptr;
143
144 /* The block is for arena |a|, but should appear in the freelist of |root|. */
145 block->next = root->freelist;
146 block->size = (uint32_t)size;
147 block->cleanups = 0;
148 root->freelist = block;
149 a->last_size = block->size;
150 if (!root->freelist_tail) root->freelist_tail = block;
151
152 a->head.ptr = UPB_PTR_AT(block, memblock_reserve, char);
153 a->head.end = UPB_PTR_AT(block, size, char);
154 a->cleanup_metadata = upb_cleanup_metadata(
155 &block->cleanups, upb_cleanup_has_initial_block(a->cleanup_metadata));
156
157 UPB_POISON_MEMORY_REGION(a->head.ptr, a->head.end - a->head.ptr);
158 }
159
upb_arena_allocblock(upb_arena * a,size_t size)160 static bool upb_arena_allocblock(upb_arena *a, size_t size) {
161 upb_arena *root = arena_findroot(a);
162 size_t block_size = UPB_MAX(size, a->last_size * 2) + memblock_reserve;
163 mem_block *block = upb_malloc(root->block_alloc, block_size);
164
165 if (!block) return false;
166 upb_arena_addblock(a, root, block, block_size);
167 return true;
168 }
169
_upb_arena_slowmalloc(upb_arena * a,size_t size)170 void *_upb_arena_slowmalloc(upb_arena *a, size_t size) {
171 if (!upb_arena_allocblock(a, size)) return NULL; /* Out of memory. */
172 UPB_ASSERT(_upb_arenahas(a) >= size);
173 return upb_arena_malloc(a, size);
174 }
175
upb_arena_doalloc(upb_alloc * alloc,void * ptr,size_t oldsize,size_t size)176 static void *upb_arena_doalloc(upb_alloc *alloc, void *ptr, size_t oldsize,
177 size_t size) {
178 upb_arena *a = (upb_arena*)alloc; /* upb_alloc is initial member. */
179 return upb_arena_realloc(a, ptr, oldsize, size);
180 }
181
182 /* Public Arena API ***********************************************************/
183
arena_initslow(void * mem,size_t n,upb_alloc * alloc)184 upb_arena *arena_initslow(void *mem, size_t n, upb_alloc *alloc) {
185 const size_t first_block_overhead = sizeof(upb_arena) + memblock_reserve;
186 upb_arena *a;
187
188 /* We need to malloc the initial block. */
189 n = first_block_overhead + 256;
190 if (!alloc || !(mem = upb_malloc(alloc, n))) {
191 return NULL;
192 }
193
194 a = UPB_PTR_AT(mem, n - sizeof(*a), upb_arena);
195 n -= sizeof(*a);
196
197 a->head.alloc.func = &upb_arena_doalloc;
198 a->block_alloc = alloc;
199 a->parent = a;
200 a->refcount = 1;
201 a->freelist = NULL;
202 a->freelist_tail = NULL;
203 a->cleanup_metadata = upb_cleanup_metadata(NULL, false);
204
205 upb_arena_addblock(a, a, mem, n);
206
207 return a;
208 }
209
upb_arena_init(void * mem,size_t n,upb_alloc * alloc)210 upb_arena *upb_arena_init(void *mem, size_t n, upb_alloc *alloc) {
211 upb_arena *a;
212
213 /* Round block size down to alignof(*a) since we will allocate the arena
214 * itself at the end. */
215 n = UPB_ALIGN_DOWN(n, UPB_ALIGN_OF(upb_arena));
216
217 if (UPB_UNLIKELY(n < sizeof(upb_arena))) {
218 return arena_initslow(mem, n, alloc);
219 }
220
221 a = UPB_PTR_AT(mem, n - sizeof(*a), upb_arena);
222
223 a->head.alloc.func = &upb_arena_doalloc;
224 a->block_alloc = alloc;
225 a->parent = a;
226 a->refcount = 1;
227 a->last_size = UPB_MAX(128, n);
228 a->head.ptr = mem;
229 a->head.end = UPB_PTR_AT(mem, n - sizeof(*a), char);
230 a->freelist = NULL;
231 a->cleanup_metadata = upb_cleanup_metadata(NULL, true);
232
233 return a;
234 }
235
arena_dofree(upb_arena * a)236 static void arena_dofree(upb_arena *a) {
237 mem_block *block = a->freelist;
238 UPB_ASSERT(a->parent == a);
239 UPB_ASSERT(a->refcount == 0);
240
241 while (block) {
242 /* Load first since we are deleting block. */
243 mem_block *next = block->next;
244
245 if (block->cleanups > 0) {
246 cleanup_ent *end = UPB_PTR_AT(block, block->size, void);
247 cleanup_ent *ptr = end - block->cleanups;
248
249 for (; ptr < end; ptr++) {
250 ptr->cleanup(ptr->ud);
251 }
252 }
253
254 upb_free(a->block_alloc, block);
255 block = next;
256 }
257 }
258
upb_arena_free(upb_arena * a)259 void upb_arena_free(upb_arena *a) {
260 a = arena_findroot(a);
261 if (--a->refcount == 0) arena_dofree(a);
262 }
263
upb_arena_addcleanup(upb_arena * a,void * ud,upb_cleanup_func * func)264 bool upb_arena_addcleanup(upb_arena *a, void *ud, upb_cleanup_func *func) {
265 cleanup_ent *ent;
266 uint32_t* cleanups = upb_cleanup_pointer(a->cleanup_metadata);
267
268 if (!cleanups || _upb_arenahas(a) < sizeof(cleanup_ent)) {
269 if (!upb_arena_allocblock(a, 128)) return false; /* Out of memory. */
270 UPB_ASSERT(_upb_arenahas(a) >= sizeof(cleanup_ent));
271 cleanups = upb_cleanup_pointer(a->cleanup_metadata);
272 }
273
274 a->head.end -= sizeof(cleanup_ent);
275 ent = (cleanup_ent*)a->head.end;
276 (*cleanups)++;
277 UPB_UNPOISON_MEMORY_REGION(ent, sizeof(cleanup_ent));
278
279 ent->cleanup = func;
280 ent->ud = ud;
281
282 return true;
283 }
284
upb_arena_fuse(upb_arena * a1,upb_arena * a2)285 bool upb_arena_fuse(upb_arena *a1, upb_arena *a2) {
286 upb_arena *r1 = arena_findroot(a1);
287 upb_arena *r2 = arena_findroot(a2);
288
289 if (r1 == r2) return true; /* Already fused. */
290
291 /* Do not fuse initial blocks since we cannot lifetime extend them. */
292 if (upb_cleanup_has_initial_block(r1->cleanup_metadata)) return false;
293 if (upb_cleanup_has_initial_block(r2->cleanup_metadata)) return false;
294
295 /* Only allow fuse with a common allocator */
296 if (r1->block_alloc != r2->block_alloc) return false;
297
298 /* We want to join the smaller tree to the larger tree.
299 * So swap first if they are backwards. */
300 if (r1->refcount < r2->refcount) {
301 upb_arena *tmp = r1;
302 r1 = r2;
303 r2 = tmp;
304 }
305
306 /* r1 takes over r2's freelist and refcount. */
307 r1->refcount += r2->refcount;
308 if (r2->freelist_tail) {
309 UPB_ASSERT(r2->freelist_tail->next == NULL);
310 r2->freelist_tail->next = r1->freelist;
311 r1->freelist = r2->freelist;
312 }
313 r2->parent = r1;
314 return true;
315 }
316