1 /* vim: set expandtab ts=4 sw=4: */
2 /*
3 * You may redistribute this program and/or modify it under the terms of
4 * the GNU General Public License as published by the Free Software Foundation,
5 * either version 3 of the License, or (at your option) any later version.
6 *
7 * This program is distributed in the hope that it will be useful,
8 * but WITHOUT ANY WARRANTY; without even the implied warranty of
9 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
10 * GNU General Public License for more details.
11 *
12 * You should have received a copy of the GNU General Public License
13 * along with this program. If not, see <https://www.gnu.org/licenses/>.
14 */
15
16 #include "memory/Allocator.h"
17 #include "memory/Allocator_pvt.h"
18 #include "util/Bits.h"
19 #include "util/Defined.h"
20
21 #include <stdio.h>
22
23 /** This provides the padding for each line based on the depth in the stack. */
24 struct Unroller;
25 struct Unroller
26 {
27 const char* const content;
28 const struct Unroller* const last;
29 };
writeUnroller(const struct Unroller * unroller)30 static void writeUnroller(const struct Unroller* unroller)
31 {
32 if (unroller) {
33 writeUnroller(unroller->last);
34 fprintf(stderr, "%s", unroller->content);
35 }
36 }
unroll(struct Allocator_pvt * context,int includeAllocations,struct Unroller * unroller)37 static void unroll(struct Allocator_pvt* context,
38 int includeAllocations,
39 struct Unroller* unroller)
40 {
41 writeUnroller(unroller);
42 const char* ident = (context->pub.fileName) ? context->pub.fileName : "UNKNOWN";
43
44 fprintf(stderr, "%s:%d [%lu] bytes%s\n",
45 ident,
46 context->pub.lineNum,
47 context->allocatedHere,
48 (context->pub.isFreeing) ? " (freeing)" : "");
49
50 struct Unroller childUnroller = {
51 .content = ((context->nextSibling) ? "| " : " "),
52 .last = unroller
53 };
54 if (context->firstChild) {
55 unroll(context->firstChild, includeAllocations, &childUnroller);
56 }
57 struct Allocator_Allocation_pvt* allocation = context->allocations;
58 while (allocation && includeAllocations) {
59 writeUnroller(&childUnroller);
60 fprintf(stderr, "%s:%ld [%lu] bytes at [0x%lx]\n",
61 allocation->fileName,
62 (unsigned long)allocation->lineNum,
63 (unsigned long)allocation->pub.size,
64 (unsigned long)(uintptr_t)allocation);
65 allocation = allocation->next;
66 }
67 if (context->nextSibling) {
68 unroll(context->nextSibling, includeAllocations, unroller);
69 }
70 }
71
bytesAllocated(struct Allocator_pvt * ctx)72 static inline uint64_t bytesAllocated(struct Allocator_pvt* ctx)
73 {
74 uint64_t bytes = ctx->allocatedHere;
75 for (struct Allocator_pvt* child = ctx->firstChild; child; child = child->nextSibling) {
76 bytes += bytesAllocated(child);
77 }
78 return bytes;
79 }
80
check(struct Allocator_pvt * alloc)81 static void check(struct Allocator_pvt* alloc)
82 {
83 if (!Defined(Allocator_PARANOIA)) { return; }
84 uint64_t totalAllocated = alloc->rootAlloc->maxSpace - alloc->rootAlloc->spaceAvailable;
85 uint64_t accounted = bytesAllocated(Identity_check((struct Allocator_pvt*)alloc->rootAlloc));
86 Assert_true(totalAllocated == accounted);
87 }
88
Allocator_snapshot(struct Allocator * allocator,int includeAllocations)89 void Allocator_snapshot(struct Allocator* allocator, int includeAllocations)
90 {
91 // get the root allocator.
92 struct Allocator_pvt* alloc = Identity_check((struct Allocator_pvt*)allocator);
93 struct Allocator_FirstCtx* rootAlloc = Identity_check(alloc->rootAlloc);
94 alloc = Identity_check((struct Allocator_pvt*)rootAlloc);
95
96 fprintf(stderr, "----- %scjdns memory snapshot -----\n", "");
97
98 uint64_t totalAllocated = rootAlloc->maxSpace - rootAlloc->spaceAvailable;
99 uint64_t realAllocated = bytesAllocated(alloc);
100
101 unroll(alloc, includeAllocations, NULL);
102
103 if (totalAllocated != realAllocated) {
104 fprintf(stderr, "!!!!!! INTERNAL ERROR totalAllocated = [%lu] realAllocated = [%lu] !!!!!",
105 (unsigned long)totalAllocated, (unsigned long)realAllocated);
106 }
107 fprintf(stderr, "totalBytes [%ld] remaining [%ld]\n",
108 (long)rootAlloc->maxSpace,
109 (long)rootAlloc->spaceAvailable);
110
111 fprintf(stderr, "----- %scjdns memory snapshot -----\n", "end ");
112 }
113
114 Gcc_NORETURN
failure(struct Allocator_pvt * context,const char * message,const char * fileName,int lineNum)115 static void failure(struct Allocator_pvt* context,
116 const char* message,
117 const char* fileName,
118 int lineNum)
119 {
120 Allocator_snapshot(&context->pub, 1);
121 Assert_failure("%s:%d Fatal error: [%s]", fileName, lineNum, message);
122 }
123
getRealSize(unsigned long requestedSize)124 static inline unsigned long getRealSize(unsigned long requestedSize)
125 {
126 return ((requestedSize + (sizeof(char*) - 1)) & ~(sizeof(char*) - 1)) // align
127 + sizeof(struct Allocator_Allocation_pvt)
128 #ifdef Allocator_USE_CANARIES
129 + sizeof(uintptr_t)
130 #endif
131 ;
132 }
133
134 #define END_CANARY(alloc) ((uintptr_t*) alloc)[ (alloc->pub.size / sizeof(uintptr_t)) - 1 ]
135
setCanaries(struct Allocator_Allocation_pvt * alloc,struct Allocator_pvt * context)136 static inline void setCanaries(struct Allocator_Allocation_pvt* alloc,
137 struct Allocator_pvt* context)
138 {
139 #ifdef Allocator_USE_CANARIES
140 END_CANARY(alloc) = context->canary ^ (uintptr_t)alloc->fileName;
141 #endif
142 }
143
checkCanaries(struct Allocator_Allocation_pvt * alloc,struct Allocator_pvt * context)144 static inline void checkCanaries(struct Allocator_Allocation_pvt* alloc,
145 struct Allocator_pvt* context)
146 {
147 #ifdef Allocator_USE_CANARIES
148 if (END_CANARY(alloc) == ((uintptr_t)alloc->fileName ^ context->canary)) { return; }
149 Assert_failure("%s:%d Fatal error: invalid canary\n",
150 context->pub.fileName, context->pub.lineNum);
151 #endif
152 }
153
154 Gcc_ALLOC_SIZE(2)
newAllocation(struct Allocator_pvt * context,unsigned long size,const char * fileName,int lineNum)155 static inline void* newAllocation(struct Allocator_pvt* context,
156 unsigned long size,
157 const char* fileName,
158 int lineNum)
159 {
160 check(context);
161 int64_t realSize = getRealSize(size);
162 struct Allocator_FirstCtx* rootAlloc = Identity_check(context->rootAlloc);
163 if (rootAlloc->spaceAvailable <= realSize) {
164 failure(context, "Out of memory, limit exceeded", fileName, lineNum);
165 }
166
167 rootAlloc->spaceAvailable -= realSize;
168 context->allocatedHere += realSize;
169
170 struct Allocator_Allocation_pvt* alloc =
171 rootAlloc->provider(rootAlloc->providerContext,
172 NULL,
173 realSize,
174 &context->pub);
175 if (alloc == NULL) {
176 failure(context, "Out of memory, malloc() returned NULL", fileName, lineNum);
177 }
178 alloc->next = context->allocations;
179 alloc->pub.size = realSize;
180 alloc->fileName = fileName;
181 alloc->lineNum = lineNum;
182 context->allocations = alloc;
183 setCanaries(alloc, context);
184
185 return (void*) (alloc + 1);
186 }
187
Allocator_getAllocation(struct Allocator * alloc,int allocNum)188 struct Allocator_Allocation* Allocator_getAllocation(struct Allocator* alloc, int allocNum)
189 {
190 struct Allocator_pvt* ctx = Identity_check((struct Allocator_pvt*)alloc);
191 if (allocNum < 0) {
192 return NULL;
193 }
194 struct Allocator_Allocation_pvt* allocation = ctx->allocations;
195 for (;allocation && allocNum > 0; allocNum--) {
196 allocation = allocation->next;
197 }
198 return (allocation) ? &allocation->pub : NULL;
199 }
200
Allocator_getChild(struct Allocator * alloc,int childNumber)201 struct Allocator* Allocator_getChild(struct Allocator* alloc, int childNumber)
202 {
203 struct Allocator_pvt* ctx = Identity_check((struct Allocator_pvt*)alloc);
204 if (childNumber < 0) {
205 return NULL;
206 }
207 struct Allocator_pvt* child = ctx->firstChild;
208 for (;child && childNumber > 0; childNumber--) {
209 child = child->nextSibling;
210 }
211 return (child) ? &child->pub : NULL;
212 }
213
removeJob(struct Allocator_OnFreeJob_pvt * job)214 static int removeJob(struct Allocator_OnFreeJob_pvt* job)
215 {
216 struct Allocator_pvt* context = Identity_check(job->alloc);
217 struct Allocator_OnFreeJob_pvt* j = context->onFree;
218 struct Allocator_OnFreeJob_pvt** jP = &context->onFree;
219 while (j && j != job) {
220 jP = &j->next;
221 j = j->next;
222 }
223 if (j == job) {
224 *jP = j->next;
225 return 0;
226 } else {
227 return -1;
228 failure(context, "Allocator_onFreeComplete() called multiple times", job->file, job->line);
229 }
230 }
231
releaseAllocation(struct Allocator_pvt * context,struct Allocator_Allocation_pvt * allocation,Allocator_Provider provider,Allocator_Provider_CONTEXT_TYPE * providerCtx)232 static void releaseAllocation(struct Allocator_pvt* context,
233 struct Allocator_Allocation_pvt* allocation,
234 Allocator_Provider provider,
235 Allocator_Provider_CONTEXT_TYPE* providerCtx)
236 {
237 checkCanaries(allocation, context);
238
239 // TODO(cjd): make this optional.
240 Bits_memset(&(&allocation->pub)[1],
241 0xee,
242 allocation->pub.size - sizeof(struct Allocator_Allocation));
243
244 provider(providerCtx,
245 &allocation->pub,
246 0,
247 ((char*)context != (char*)allocation) ? &context->pub : NULL);
248 }
249
releaseMemory(struct Allocator_pvt * context,Allocator_Provider provider,Allocator_Provider_CONTEXT_TYPE * providerCtx)250 static void releaseMemory(struct Allocator_pvt* context,
251 Allocator_Provider provider,
252 Allocator_Provider_CONTEXT_TYPE* providerCtx)
253 {
254 // Free all of the allocations including the one which holds the allocator.
255 #ifdef PARANOIA
256 unsigned long allocatedHere = context->allocatedHere;
257 #endif
258
259 Identity_check(context->rootAlloc)->spaceAvailable += context->allocatedHere;
260
261 struct Allocator_Allocation_pvt* loc = context->allocations;
262 while (loc != NULL) {
263 #ifdef PARANOIA
264 allocatedHere -= loc->pub.size;
265 #endif
266
267 struct Allocator_Allocation_pvt* nextLoc = loc->next;
268 releaseAllocation(context, loc, provider, providerCtx);
269 loc = nextLoc;
270 }
271 #ifdef PARANOIA
272 Assert_true(allocatedHere == 0);
273 #endif
274 }
275
276 // disconnect an allocator from it's parent.
disconnect(struct Allocator_pvt * context)277 static void disconnect(struct Allocator_pvt* context)
278 {
279 // Remove this allocator from the sibling list.
280 Assert_true(context->parent);
281
282 if (context->lastSibling) {
283 Assert_ifParanoid(context->lastSibling->nextSibling == context);
284 Assert_ifParanoid(context->parent->firstChild != context);
285 context->lastSibling->nextSibling = context->nextSibling;
286 } else {
287 // must be first in the list or a root allocator.
288 Assert_ifParanoid(context->parent->firstChild == context || context->parent == context);
289 Assert_ifParanoid(context->parent != context || !context->nextSibling);
290 context->parent->firstChild = context->nextSibling;
291 }
292 if (context->nextSibling) {
293 Assert_ifParanoid(context->nextSibling->lastSibling == context);
294 context->nextSibling->lastSibling = context->lastSibling;
295 }
296 context->lastSibling = NULL;
297 context->nextSibling = NULL;
298 context->parent = NULL;
299 }
300
301 // connect an allocator to a new parent.
connect(struct Allocator_pvt * parent,struct Allocator_pvt * child,const char * file,int line)302 static void connect(struct Allocator_pvt* parent,
303 struct Allocator_pvt* child,
304 const char* file,
305 int line)
306 {
307 Assert_ifParanoid(child->parent == NULL);
308 Assert_ifParanoid(child->lastSibling == NULL);
309 Assert_ifParanoid(child->nextSibling == NULL);
310 Assert_true(parent != child);
311 if (Defined(PARANOIA)) {
312 for (struct Allocator_pvt* c = parent->firstChild; c; c = c->nextSibling) {
313 Assert_true(child != c);
314 }
315 }
316 child->nextSibling = parent->firstChild;
317 if (parent->firstChild) {
318 parent->firstChild->lastSibling = child;
319 }
320 parent->firstChild = child;
321 child->parent = parent;
322 }
323
disconnectAllocator(struct Allocator_pvt * target,struct Allocator_List ** cpp)324 static int disconnectAllocator(struct Allocator_pvt* target, struct Allocator_List** cpp)
325 {
326 int found = 0;
327 struct Allocator_List* cp;
328 while ((cp = *cpp)) {
329 if (cp->alloc == target) {
330 *cpp = cp->next;
331 found = 1;
332 break;
333 }
334 cpp = &cp->next;
335 }
336 return found;
337 }
338
disconnectAdopted(struct Allocator_pvt * parent,struct Allocator_pvt * child)339 static void disconnectAdopted(struct Allocator_pvt* parent, struct Allocator_pvt* child)
340 {
341 Assert_true(parent->adoptions);
342 Assert_true(parent->adoptions->children);
343 Assert_true(child->adoptions);
344 Assert_true(child->adoptions->parents);
345 Assert_true(disconnectAllocator(child, &parent->adoptions->children));
346 Assert_true(disconnectAllocator(parent, &child->adoptions->parents));
347 }
348
349 // Shallow first search to prevent lots of flapping while we tear down the tree.
pivotChildrenToAdoptedParents0(struct Allocator_pvt * context,int depth,int maxDepth,const char * file,int line)350 static int pivotChildrenToAdoptedParents0(struct Allocator_pvt* context,
351 int depth,
352 int maxDepth,
353 const char* file,
354 int line)
355 {
356 int out = 0;
357 if (depth == maxDepth) {
358 if (context->pub.isFreeing) { return 0; }
359 if (context->adoptions) {
360 // Attempt to pivot around to a parent in order to save this allocator
361 if (context->adoptions->parents) {
362 Assert_true(!context->adoptions->parents->alloc->pub.isFreeing);
363 disconnect(context);
364 connect(context->adoptions->parents->alloc, context, file, line);
365 disconnectAdopted(context->adoptions->parents->alloc, context);
366 return 0;
367 }
368 // No saving it, drop it's adoptions.
369 for (struct Allocator_List* c = context->adoptions->children; c; c = c->next) {
370 Assert_true(!c->alloc->pub.isFreeing);
371 disconnectAdopted(context, c->alloc);
372 }
373 }
374 Assert_true(!context->pub.isFreeing);
375 context->pub.isFreeing = 1;
376 out++;
377 } else {
378 struct Allocator_pvt* child = context->firstChild;
379 while (child) {
380 Assert_ifParanoid(child != context);
381 struct Allocator_pvt* nextChild = child->nextSibling;
382 out += pivotChildrenToAdoptedParents0(child, depth+1, maxDepth, file, line);
383 child = nextChild;
384 }
385 }
386 return out;
387 }
388
pivotChildrenToAdoptedParents(struct Allocator_pvt * context,const char * file,int line)389 static int pivotChildrenToAdoptedParents(struct Allocator_pvt* context, const char* file, int line)
390 {
391 for (int i = 0; i < 10000; i++) {
392 if (!pivotChildrenToAdoptedParents0(context, 0, i, file, line)) {
393 // No out on i == 0 -> the allocator pivoted to another parent, cease freeing.
394 return (i != 0);
395 }
396 }
397 Assert_failure("Didn't free all allocators in 10000 deep iterations");
398 }
399
400 /**
401 * Collect all of the onFree jobs from all of the child allocators (deep) and attach them all
402 * to the root of the tree which is being freed. They are not detached from their relevant
403 * allocators because those allocators will be freed soon anyway.
404 */
marshalOnFreeJobs(struct Allocator_pvt * context,struct Allocator_pvt * rootToFree)405 static void marshalOnFreeJobs(struct Allocator_pvt* context, struct Allocator_pvt* rootToFree)
406 {
407 Assert_true(context->pub.isFreeing);
408 struct Allocator_pvt* child = context->firstChild;
409 while (child) {
410 // Theoretically the order of free jobs is not promised but this prevents libuv crashing.
411 struct Allocator_OnFreeJob_pvt** jobP = &rootToFree->onFree;
412 while (*jobP != NULL) {
413 struct Allocator_OnFreeJob_pvt* job = *jobP;
414 jobP = &job->next;
415 }
416 *jobP = child->onFree;
417 child->onFree = NULL;
418
419 while (*jobP != NULL) {
420 struct Allocator_OnFreeJob_pvt* job = *jobP;
421 job->alloc = rootToFree;
422 jobP = &job->next;
423 }
424
425 struct Allocator_pvt* nextChild = child->nextSibling;
426 marshalOnFreeJobs(child, rootToFree);
427 child = nextChild;
428 }
429 }
430
doOnFreeJobs(struct Allocator_pvt * context)431 static void doOnFreeJobs(struct Allocator_pvt* context)
432 {
433 // Do the onFree jobs.
434 struct Allocator_OnFreeJob_pvt** jobP = &context->onFree;
435 while (*jobP != NULL) {
436 struct Allocator_OnFreeJob_pvt* job = *jobP;
437 if (!job->pub.callback) {
438 // no callback, remove the job
439 Assert_true(!removeJob(job));
440 continue;
441 } else if (!job->called) {
442 if (job->pub.callback(&job->pub) != Allocator_ONFREE_ASYNC) {
443 Assert_true(!removeJob(job));
444 continue;
445 } else {
446 job->called = 1;
447 }
448 }
449 jobP = &job->next;
450 }
451 }
452
freeAllocator(struct Allocator_pvt * context)453 static void freeAllocator(struct Allocator_pvt* context)
454 {
455 Assert_true(context->pub.isFreeing);
456 int isTop = !context->parent->pub.isFreeing;
457 if (isTop) {
458 check(context);
459 disconnect(context);
460 }
461 struct Allocator_pvt* child = context->firstChild;
462 while (child) {
463 struct Allocator_pvt* nextChild = child->nextSibling;
464 freeAllocator(child);
465 child = nextChild;
466 }
467
468 // Grab out the provider and provider context in case the root allocator is freed.
469 struct Allocator_FirstCtx* rootAlloc = Identity_check(context->rootAlloc);
470 Allocator_Provider provider = rootAlloc->provider;
471 Allocator_Provider_CONTEXT_TYPE* providerCtx = rootAlloc->providerContext;
472
473 releaseMemory(context, provider, providerCtx);
474 if (isTop) {
475 check((struct Allocator_pvt*)rootAlloc);
476 }
477 }
478
Allocator_onFreeComplete(struct Allocator_OnFreeJob * onFreeJob)479 void Allocator_onFreeComplete(struct Allocator_OnFreeJob* onFreeJob)
480 {
481 struct Allocator_OnFreeJob_pvt* job = (struct Allocator_OnFreeJob_pvt*) onFreeJob;
482 struct Allocator_pvt* context = Identity_check(job->alloc);
483
484 if (removeJob(job)) {
485 failure(context, "OnFreeJob->complete() called multiple times", job->file, job->line);
486 }
487
488 if (!context->onFree) {
489 // There are no more jobs, release the memory.
490 freeAllocator(context);
491 }
492 }
493
Allocator__free(struct Allocator * alloc,const char * file,int line)494 void Allocator__free(struct Allocator* alloc, const char* file, int line)
495 {
496 struct Allocator_pvt* context = Identity_check((struct Allocator_pvt*) alloc);
497 check(context);
498
499 // It's really difficult to know that you didn't get called back inside of a freeing of a
500 // parent of a parent allocator which causes your allocator to be in isFreeing state so
501 // lets be forgiving here.
502 if (context->pub.isFreeing) { return; }
503
504 if (context->rootAlloc == (struct Allocator_FirstCtx*)context) {
505 struct Allocator_FirstCtx* rootAlloc = Identity_check((struct Allocator_FirstCtx*)context);
506 if (bytesAllocated(context) + rootAlloc->spaceAvailable != (uint64_t)rootAlloc->maxSpace) {
507 failure(context, "unaccounted for memory", file, line);
508 }
509 }
510
511 check(context);
512 if (!pivotChildrenToAdoptedParents(context, file, line)) { return; }
513 check(context);
514 marshalOnFreeJobs(context, context);
515 check(context);
516 doOnFreeJobs(context);
517 check(context);
518 if (!context->onFree) {
519 freeAllocator(context);
520 }
521 }
522
Allocator__malloc(struct Allocator * allocator,unsigned long length,const char * fileName,int lineNum)523 void* Allocator__malloc(struct Allocator* allocator,
524 unsigned long length,
525 const char* fileName,
526 int lineNum)
527 {
528 struct Allocator_pvt* ctx = Identity_check((struct Allocator_pvt*) allocator);
529 void* out = newAllocation(ctx, length, fileName, lineNum);
530 check(ctx);
531 return out;
532 }
533
Allocator__calloc(struct Allocator * alloc,unsigned long length,unsigned long count,const char * fileName,int lineNum)534 void* Allocator__calloc(struct Allocator* alloc,
535 unsigned long length,
536 unsigned long count,
537 const char* fileName,
538 int lineNum)
539 {
540 void* pointer = Allocator__malloc(alloc, length * count, fileName, lineNum);
541 Bits_memset(pointer, 0, length * count);
542 return pointer;
543 }
544
Allocator__realloc(struct Allocator * allocator,const void * original,unsigned long size,const char * fileName,int lineNum)545 void* Allocator__realloc(struct Allocator* allocator,
546 const void* original,
547 unsigned long size,
548 const char* fileName,
549 int lineNum)
550 {
551 if (original == NULL) {
552 return Allocator__malloc(allocator, size, fileName, lineNum);
553 }
554
555 struct Allocator_pvt* context = Identity_check((struct Allocator_pvt*) allocator);
556 check(context);
557 struct Allocator_Allocation_pvt** locPtr = &context->allocations;
558 struct Allocator_Allocation_pvt* origLoc =
559 ((struct Allocator_Allocation_pvt*) original) - 1;
560 for (;;) {
561 struct Allocator_Allocation_pvt* loc = *locPtr;
562 if (loc == NULL) {
563 failure(context,
564 "Reallocation of memory which was not allocated using this allocator.",
565 fileName,
566 lineNum);
567 }
568 checkCanaries(loc, context);
569 if (loc == origLoc) {
570 break;
571 }
572 locPtr = &loc->next;
573 }
574
575 struct Allocator_Allocation_pvt* nextLoc = origLoc->next;
576
577 if (size == 0) {
578 // realloc(0) means free()
579 *locPtr = nextLoc;
580 Assert_true(origLoc->pub.size <= context->allocatedHere);
581 context->rootAlloc->spaceAvailable += origLoc->pub.size;
582 context->allocatedHere -= origLoc->pub.size;
583 releaseAllocation(context,
584 origLoc,
585 context->rootAlloc->provider,
586 context->rootAlloc->providerContext);
587 check(context);
588 return NULL;
589 }
590
591 size_t realSize = getRealSize(size);
592 if (context->rootAlloc->spaceAvailable + origLoc->pub.size < realSize) {
593 failure(context, "Out of memory, limit exceeded.", fileName, lineNum);
594 }
595 context->rootAlloc->spaceAvailable += origLoc->pub.size;
596 context->rootAlloc->spaceAvailable -= realSize;
597 context->allocatedHere -= origLoc->pub.size;
598 context->allocatedHere += realSize;
599
600 struct Allocator_Allocation_pvt* alloc =
601 context->rootAlloc->provider(context->rootAlloc->providerContext,
602 &origLoc->pub,
603 realSize,
604 allocator);
605
606 if (alloc == NULL) {
607 failure(context, "Out of memory, realloc() returned NULL.", fileName, lineNum);
608 }
609 alloc->next = nextLoc;
610 alloc->pub.size = realSize;
611 *locPtr = alloc;
612
613 setCanaries(alloc, context);
614 check(context);
615
616 return (void*) (alloc + 1);
617 }
618
Allocator__clone(struct Allocator * allocator,const void * toClone,unsigned long length,const char * fileName,int lineNum)619 void* Allocator__clone(struct Allocator* allocator,
620 const void* toClone,
621 unsigned long length,
622 const char* fileName,
623 int lineNum)
624 {
625 void* pointer = Allocator__malloc(allocator, length, fileName, lineNum);
626 Bits_memcpy(pointer, toClone, length);
627 return pointer;
628 }
629
Allocator__child(struct Allocator * allocator,const char * file,int line)630 struct Allocator* Allocator__child(struct Allocator* allocator, const char* file, int line)
631 {
632 struct Allocator_pvt* parent = Identity_check((struct Allocator_pvt*) allocator);
633 check(parent);
634
635 struct Allocator_pvt stackChild = {
636 .pub = {
637 .fileName = file,
638 .lineNum = line,
639 .isFreeing = parent->pub.isFreeing
640 },
641 .rootAlloc = parent->rootAlloc
642 };
643 Identity_set(&stackChild);
644 #ifdef Allocator_USE_CANARIES
645 stackChild.nextCanary = stackChild.canary = parent->nextCanary;
646 #endif
647
648 struct Allocator_pvt* child =
649 newAllocation(&stackChild, sizeof(struct Allocator_pvt), file, line);
650 Bits_memcpy(child, &stackChild, sizeof(struct Allocator_pvt));
651
652 // Link the child into the parent's allocator list
653 connect(parent, child, file, line);
654
655 check(parent);
656 return &child->pub;
657 }
658
Allocator_cancelOnFree(struct Allocator_OnFreeJob * toRemove)659 int Allocator_cancelOnFree(struct Allocator_OnFreeJob* toRemove)
660 {
661 struct Allocator_OnFreeJob_pvt* job = (struct Allocator_OnFreeJob_pvt*) toRemove;
662 struct Allocator_pvt* context = Identity_check(job->alloc);
663 struct Allocator_OnFreeJob_pvt** jobPtr = &(context->onFree);
664 while (*jobPtr != NULL) {
665 if (*jobPtr == job) {
666 *jobPtr = (*jobPtr)->next;
667 return 0;
668 }
669 jobPtr = &(*jobPtr)->next;
670 }
671 return -1;
672 }
673
674 /** return 1 if true, otherwise zero. */
isAncestorOf(struct Allocator_pvt * maybeParent,struct Allocator_pvt * maybeChild)675 static int isAncestorOf(struct Allocator_pvt* maybeParent,
676 struct Allocator_pvt* maybeChild)
677 {
678 if (maybeParent == maybeChild) {
679 return 1;
680 }
681 if (maybeParent == NULL || maybeChild == NULL || maybeChild->parent == maybeChild) {
682 return 0;
683 }
684 if (isAncestorOf(maybeParent, maybeChild->parent)) {
685 return 1;
686 }
687 if (maybeChild->adoptions) {
688 struct Allocator_List* al = maybeChild->adoptions->parents;
689 while (al) {
690 if (isAncestorOf(maybeParent, al->alloc)) {
691 return 1;
692 }
693 }
694 }
695 return 0;
696 }
697
Allocator__disown(struct Allocator * parentAlloc,struct Allocator * allocToDisown,const char * fileName,int lineNum)698 void Allocator__disown(struct Allocator* parentAlloc,
699 struct Allocator* allocToDisown,
700 const char* fileName,
701 int lineNum)
702 {
703 struct Allocator_pvt* parent = Identity_check((struct Allocator_pvt*) parentAlloc);
704 struct Allocator_pvt* child = Identity_check((struct Allocator_pvt*) allocToDisown);
705
706 if (parent->pub.isFreeing || child->pub.isFreeing) { return; }
707
708 if (child->parent == parent) {
709 // The child's natural parent has been freed and it has pivoted to the adopted parent
710 // Do a normal Allocator_free() and it will either pivot once again to another adopter
711 // or it will drop from the tree and free.
712 Allocator__free(&child->pub, fileName, lineNum);
713 return;
714 }
715
716 if (isAncestorOf(child, parent)) {
717 // Rare but possible way that the child would never have been adopted.
718 return;
719 }
720
721 disconnectAdopted(parent, child);
722 }
723
Allocator__adopt(struct Allocator * adoptedParent,struct Allocator * childToAdopt,const char * file,int line)724 void Allocator__adopt(struct Allocator* adoptedParent,
725 struct Allocator* childToAdopt,
726 const char* file,
727 int line)
728 {
729 struct Allocator_pvt* parent = Identity_check((struct Allocator_pvt*) adoptedParent);
730 struct Allocator_pvt* child = Identity_check((struct Allocator_pvt*) childToAdopt);
731
732 if (parent->pub.isFreeing) { return; }
733 Assert_true(!child->pub.isFreeing);
734
735 if (isAncestorOf(child, parent)) {
736 // The child is a parent of the parent, this means an adoption would be meaningless
737 // because if the child is otherwise freed, it will take the parent along with it.
738 return;
739 }
740
741 if (!parent->adoptions) {
742 parent->adoptions =
743 Allocator__calloc(adoptedParent, sizeof(struct Allocator_Adoptions), 1, file, line);
744 }
745 if (!child->adoptions) {
746 child->adoptions =
747 Allocator__calloc(childToAdopt, sizeof(struct Allocator_Adoptions), 1, file, line);
748 }
749
750 struct Allocator_List* pl =
751 Allocator__calloc(childToAdopt, sizeof(struct Allocator_List), 1, file, line);
752 pl->alloc = child;
753 pl->next = parent->adoptions->children;
754 parent->adoptions->children = pl;
755
756 struct Allocator_List* cl =
757 Allocator__calloc(childToAdopt, sizeof(struct Allocator_List), 1, file, line);
758 cl->alloc = parent;
759 cl->next = child->adoptions->parents;
760 child->adoptions->parents = cl;
761 }
762
Allocator__onFree(struct Allocator * alloc,Allocator_OnFreeCallback callback,void * callbackContext,const char * file,int line)763 struct Allocator_OnFreeJob* Allocator__onFree(struct Allocator* alloc,
764 Allocator_OnFreeCallback callback,
765 void* callbackContext,
766 const char* file,
767 int line)
768 {
769 struct Allocator_pvt* context = Identity_check((struct Allocator_pvt*) alloc);
770
771 while (context->pub.isFreeing) {
772 // Assign new onFree jobs at the top level
773 if (context->parent == context || !context->parent->pub.isFreeing) {
774 break;
775 }
776 context = context->parent;
777 }
778
779 struct Allocator_OnFreeJob_pvt* newJob =
780 Allocator_clone(alloc, (&(struct Allocator_OnFreeJob_pvt) {
781 .pub = {
782 .callback = callback,
783 .userData = callbackContext
784 },
785 .alloc = context,
786 .file = file,
787 .line = line
788 }));
789 Identity_set(newJob);
790
791 struct Allocator_OnFreeJob_pvt* job = context->onFree;
792 if (job == NULL) {
793 context->onFree = newJob;
794 } else {
795 while (job->next != NULL) {
796 job = job->next;
797 }
798 job->next = newJob;
799 }
800 return &newJob->pub;
801 }
802
Allocator_new(unsigned long sizeLimit,Allocator_Provider provider,void * providerContext,const char * fileName,int lineNum)803 struct Allocator* Allocator_new(unsigned long sizeLimit,
804 Allocator_Provider provider,
805 void* providerContext,
806 const char* fileName,
807 int lineNum)
808 {
809 if (sizeLimit == 0) {
810 sizeLimit = INT64_MAX - getRealSize(sizeof(struct Allocator_FirstCtx));
811 }
812 // Add in the size of the allocator so that a very small sizeLimit is sane.
813 sizeLimit += getRealSize(sizeof(struct Allocator_FirstCtx));
814
815 struct Allocator_FirstCtx stackContext = {
816 .spaceAvailable = sizeLimit,
817 .provider = provider,
818 .providerContext = providerContext,
819 .context = {
820 .pub = {
821 .fileName = fileName,
822 .lineNum = lineNum,
823 },
824 #ifdef Allocator_USE_CANARIES
825 .canary = (uintptr_t) Constant_rand64(),
826 .nextCanary = (uintptr_t) Constant_rand64(),
827 #endif
828 }
829 };
830 stackContext.maxSpace = stackContext.spaceAvailable;
831 stackContext.context.rootAlloc = &stackContext;
832 Identity_set(&stackContext);
833 Identity_set(&stackContext.context);
834
835 struct Allocator_FirstCtx* firstContext =
836 Allocator__clone(&stackContext.context.pub,
837 &stackContext,
838 sizeof(struct Allocator_FirstCtx),
839 fileName,
840 lineNum);
841
842 struct Allocator_pvt* context = &firstContext->context;
843 context->rootAlloc = firstContext;
844 context->parent = context;
845
846 check(context);
847 return &context->pub;
848 }
849
Allocator_bytesAllocated(struct Allocator * allocator)850 unsigned long Allocator_bytesAllocated(struct Allocator* allocator)
851 {
852 struct Allocator_pvt* context = Identity_check((struct Allocator_pvt*) allocator);
853 return bytesAllocated(context);
854 }
855
Allocator_setCanary(struct Allocator * alloc,uintptr_t value)856 void Allocator_setCanary(struct Allocator* alloc, uintptr_t value)
857 {
858 #ifdef Allocator_USE_CANARIES
859 struct Allocator_pvt* context = Identity_check((struct Allocator_pvt*) alloc);
860 context->nextCanary ^= value;
861 #endif
862 }
863