1
0

Allocator.c 27 KB

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