Allocator.h 17 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328329330331332333334335336337338339340341342343344345346347348349350351352353354355356357358359360361362363364365366367368369370371372373374375376377378379
  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. #ifndef Allocator_H
  16. #define Allocator_H
  17. #include "util/Identity.h"
  18. #include "util/Gcc.h"
  19. #include "util/Linker.h"
  20. Linker_require("memory/Allocator.c")
  21. /**
  22. * A handle which is provided in response to calls to Allocator_onFree().
  23. * This handle is sutable for use with Allocator_notOnFree() to cancel a job.
  24. */
  25. struct Allocator_OnFreeJob;
  26. typedef int (* Allocator_OnFreeCallback)(struct Allocator_OnFreeJob* job);
  27. struct Allocator_OnFreeJob
  28. {
  29. /** Set by caller. */
  30. Allocator_OnFreeCallback callback;
  31. void* userData;
  32. };
  33. /**
  34. * If an onFree job needs to complete asynchronously, it should return this,
  35. * then when it is complete it must call job->complete(job) on the OnFreeJob
  36. * which was passed to it.
  37. */
  38. #define Allocator_ONFREE_ASYNC 10000
  39. /**
  40. * Allocator for structured memory management.
  41. * The objective of the allocator structure is to make manual memory management easier, specifically
  42. * to make making a mistake difficult.
  43. *
  44. * Every function which allocates memory, either to return a structure or to do processing which
  45. * cannot be done on the stack takes an allocator as a parameter.
  46. *
  47. * In traditional C, each call to malloc() must be traced to a corresponding free() call, a
  48. * laborious process which can be partially automated but inevitably leaves some memory leak
  49. * investigative work to the developer. Allocator attempts to move the memory freeing operations
  50. * close to the memory allocations thus making bugs easy to spot without searching over large
  51. * amounts of code.
  52. *
  53. * With Allocator, you might do the following:
  54. *
  55. * struct Allocator* child = Allocator_child(myAlloc); <-- myAlloc is the one provided to you
  56. * potentiallyLeakyFunction(child);
  57. * Allocator_free(child);
  58. *
  59. * Given this simple pattern, as long as potentiallyLeakyFunction() did not bypass the allocator
  60. * system using malloc() directly, we can prove that it is not the source of a memory leak.
  61. * As the real code is far more complex than this contrived example, there are a few rules which
  62. * have proven useful in preventing both memory leaks and dangling pointers.
  63. *
  64. * #1 Do not create new root allocators, create child allocators instead.
  65. * When you call MallocAllocator_new() or equivalent, you are creating a parentless allocator and
  66. * you must take responsibility for it's freeing when you are finished with it. In cjdns there is
  67. * only one call to a main allocator and all other allocators are spawned from it using
  68. * Allocator_child().
  69. * Exception: In certain code which interfaces with libuv, an alternate root allocator is necessary
  70. * because libuv teardown process is asynchronous and memory used by libuv must not be freed
  71. * until this is complete.
  72. *
  73. * #2 Free your allocators and not anyone else's.
  74. * With precious few exceptions, an allocator is always freed in the same .c file where it was
  75. * created. It is obviously rude to destroy something of someone else's just as it is rude to leave
  76. * things lying around expecting someone else to clean up after you. Sometimes you want to "take
  77. * ownership" of some memory which somebody else allocated and they are passing to you. Rather
  78. * than slowly allocate your own memory and copy the data over, you can use Allocator_adopt() to
  79. * hold that memory in existance until you and the creator both are finished with it.
  80. *
  81. * #3 Assume that any allocator may be freed at any time.
  82. * A typical example is the ping message. When a ping is sent, a structure is allocated to hold
  83. * information about the ping so that when the response comes back it will be recognized. That
  84. * structure is inserted into a table of outstanding pings. If that allocator were freed while the
  85. * ping was outstanding, the response would come back and the table lookup would access freed
  86. * memory. To prevent this, every place where temporary memory is placed into a more permanent
  87. * structure (the table), Allocator_onFree() is used to hook the freeing of that memory and add a
  88. * function to remove the entry from the table.
  89. * Cjdns is notably lacking in "deregister" or "cancel" type functions as the accepted method of
  90. * deregistering a peer or cancelling an operation is by freeing the associated allocator, both
  91. * simplifying the code and avoiding bug prone "cold" codepaths.
  92. *
  93. * The function pointers in the allocator structure are best called through the associated macros.
  94. */
  95. struct Allocator
  96. {
  97. /** The name of the file where this allocator was created. */
  98. const char* fileName;
  99. /** The number of the line where this allocator was created. */
  100. int lineNum;
  101. /** Non-zero if allocator is currently freeing. */
  102. int isFreeing;
  103. };
  104. struct Allocator_Allocation
  105. {
  106. const char* fileName;
  107. int lineNum;
  108. unsigned long size;
  109. };
  110. /**
  111. * Get a child of a given allocator.
  112. *
  113. * @param alloc the parent
  114. * @param childNumber
  115. * @return a child allocator or NULL if childNumber is out of range.
  116. */
  117. struct Allocator* Allocator_getChild(struct Allocator* alloc, int childNumber);
  118. /**
  119. * Get one of the allocations held by this allocator.
  120. *
  121. * @param alloc the allocator.
  122. * @param allocNum the number of the allocation.
  123. * @return an allocation or NULL if allocNum is out of range.
  124. */
  125. struct Allocator_Allocation* Allocator_getAllocation(struct Allocator* alloc, int allocNum);
  126. /**
  127. * Allocate some memory from this memory allocator.
  128. * The allocation will be aligned on the size of a pointer, if you need further alignment then
  129. * you must handle it manually.
  130. *
  131. * @param alloc the memory allocator.
  132. * @param size the number of bytes to allocate.
  133. * @return a pointer to the newly allocated memory.
  134. * @see malloc()
  135. */
  136. Gcc_ALLOC_SIZE(2)
  137. void* Allocator__malloc(struct Allocator* allocator,
  138. unsigned long length,
  139. const char* fileName,
  140. int lineNum);
  141. #define Allocator_malloc(a, b) Allocator__malloc((a),(b),Gcc_SHORT_FILE,Gcc_LINE)
  142. /**
  143. * Allocate some memory from this memory allocator.
  144. * The allocation will be aligned on the size of a pointer, if you need further alignment then
  145. * you must handle it manually.
  146. * Memory location will be filled with 0 bytes.
  147. *
  148. * @param alloc the memory allocator.
  149. * @param size the number of bytes per element.
  150. * @param count the number of elements in the allocation.
  151. * @return a pointer to the newly allocated memory.
  152. * @see calloc()
  153. */
  154. Gcc_ALLOC_SIZE(2,3)
  155. void* Allocator__calloc(struct Allocator* alloc,
  156. unsigned long length,
  157. unsigned long count,
  158. const char* fileName,
  159. int lineNum);
  160. #define Allocator_calloc(a, b, c) Allocator__calloc((a),(b),(c),Gcc_SHORT_FILE,Gcc_LINE)
  161. /**
  162. * Re-allocate memory so that an allocation can be expanded.
  163. * The allocation will be aligned on the size of a pointer, if you need further alignment then
  164. * you must handle it manually.
  165. * Caution: Use of this function is not advisable with memory which is shared with other parts
  166. * of the system.
  167. *
  168. * @param alloc the allocator to allocate with, must be the same allocator which allocated orig.
  169. * @param orig a pointer to the original memory allocation which is to be reallocated.
  170. * if NULL, this function will behave exactly as Allocator_malloc().
  171. * @param size how much memory to allocate. If 0, this function will free the specific memory
  172. * without freeing the entire allocator.
  173. * @return a pointer to the newly allocated memory.
  174. */
  175. Gcc_ALLOC_SIZE(3)
  176. void* Allocator__realloc(struct Allocator* allocator,
  177. const void* original,
  178. unsigned long size,
  179. const char* fileName,
  180. int lineNum);
  181. #define Allocator_realloc(a, b, c) Allocator__realloc((a),(b),(c),Gcc_SHORT_FILE,Gcc_LINE)
  182. /**
  183. * Allocate some memory and copy something into that memory space.
  184. * The allocation will be aligned on the size of a pointer, if you need further alignment then
  185. * you must handle it manually.
  186. * Caution: if content is an expression, it will be evaluated twice.
  187. *
  188. * @param alloc the memory allocator.
  189. * @param content a pointer to something which will be cloned into the newly allocated memory.
  190. * the size of the new allocation will be sizeof(*content).
  191. * @return a pointer to the newly allocated memory.
  192. */
  193. Gcc_ALLOC_SIZE(3)
  194. void* Allocator__clone(struct Allocator* allocator,
  195. const void* toClone,
  196. unsigned long length,
  197. const char* fileName,
  198. int lineNum);
  199. #define Allocator_clone(a, b) Allocator__clone((a),(b),sizeof(*(b)),Gcc_SHORT_FILE,Gcc_LINE)
  200. /**
  201. * Spawn a new child of this allocator.
  202. * When this allocator is freed all of its children which have no surviving parent will also be
  203. * freed.
  204. *
  205. * @param alloc the memory allocator.
  206. * @return a child allocator.
  207. */
  208. struct Allocator* Allocator__child(struct Allocator* alloc, const char* fileName, int lineNum);
  209. #define Allocator_child(a) Allocator__child((a),Gcc_SHORT_FILE,Gcc_LINE)
  210. /**
  211. * Sever the link between an allocator and it's original parent.
  212. * If it has been adopted using Allocator_adopt() then the freeing of the allocator will be deferred
  213. * until the allocator returned by Allocator_adopt() has also been freed.
  214. * Any allocator which has no surviving parent allocator will be implicitly freed.
  215. * NOTE: This does not do what it seems to do, it does not necessarily *free* the allocator, it
  216. * only promises to cut the link to the allocator's normal parent, if the allocator has been
  217. * adopter then the adopted parent becomes the normal parent and then the allocator is not
  218. * freed even though you asked to free it!
  219. *
  220. * @param alloc the allocator to disconnect from it's parent.
  221. */
  222. void Allocator__free(struct Allocator* alloc, const char* file, int line);
  223. #define Allocator_free(a) Allocator__free((a),Gcc_SHORT_FILE,Gcc_LINE)
  224. /**
  225. * Add a function to be called when the allocator is freed.
  226. * There is no guarantee of which order the onFree jobs will be executed.
  227. *
  228. * @param alloc the memory allocator.
  229. * @param callback the function to call.
  230. * @return an Allocator_OnFreeJob which can be cancelled with Allocator_cancelOnFree().
  231. */
  232. struct Allocator_OnFreeJob* Allocator__onFree(struct Allocator* alloc,
  233. Allocator_OnFreeCallback callback,
  234. void* context,
  235. const char* file,
  236. int line);
  237. #define Allocator_onFree(a, b, c) Allocator__onFree((a), (b), (c), Gcc_SHORT_FILE, Gcc_LINE)
  238. /**
  239. * Remove a function which was registered with Allocator_onFree().
  240. *
  241. * @param job the return value from calling Allocator_onFree().
  242. * @return 0 if the job was found and removed, -1 otherwise.
  243. */
  244. int Allocator_cancelOnFree(struct Allocator_OnFreeJob* toRemove);
  245. /**
  246. * Tell the allocator that an asynchronous onFree() job has completed.
  247. *
  248. * @param job the return value from calling Allocator_onFree().
  249. */
  250. void Allocator_onFreeComplete(struct Allocator_OnFreeJob* onFreeJob);
  251. /**
  252. * Adopt an allocator.
  253. * This creates a child of parentAlloc which is an adopted parent of toAdopt.
  254. * When Allocator_free() is called on toAdopt or one of it's parents, it will not be freed until
  255. * Allocator_free() has also been called on the allocator newly returned by this function.
  256. * This function may be used multiple times.
  257. *
  258. * Caution: Do not free an allocator which you did not create, even after adopting it.
  259. *
  260. * Allocator_adopt(myAlloc, somebodyElsesAllocator);
  261. * asynchronousStuff();
  262. * .... some time later...
  263. * Allocator_free(somebodyElsesAllocator); <-- WRONG: you freed an allocator that is not yours.
  264. *
  265. *
  266. * struct Allocator* adoptedParent = Allocator_child(myAlloc);
  267. * Allocator_adopt(adoptedParent, somebodyElsesAllocator);
  268. * asynchronousStuff();
  269. * .... some time later...
  270. * Allocator_free(adoptedParent); <-- RIGHT
  271. *
  272. *
  273. * @param parentAlloc the allocator to create a child of.
  274. * @param toAdopt the allocator which should be adopted by the returned child allocator.
  275. */
  276. void Allocator__adopt(struct Allocator* parentAlloc,
  277. struct Allocator* alloc,
  278. const char* fileName,
  279. int lineNum);
  280. #define Allocator_adopt(a, b) Allocator__adopt((a),(b),Gcc_SHORT_FILE,Gcc_LINE)
  281. /**
  282. * Disown an allocator.
  283. *
  284. * Sever the link between an adopted parent allocator and the child which it has adopted.
  285. * If this causes the child allocator to disconnect from the tree entirely, it will be
  286. * freed.
  287. *
  288. * @param parentAlloc the parent which has adopted the child allocator.
  289. * @param childToDisown the child allocator which has been adopted.
  290. */
  291. void Allocator__disown(struct Allocator* parentAlloc,
  292. struct Allocator* allocToDisown,
  293. const char* fileName,
  294. int lineNum);
  295. #define Allocator_disown(a, b) Allocator__disown((a),(b),Gcc_SHORT_FILE,Gcc_LINE)
  296. /**
  297. * Set the heap protection canary for the next child allocator.
  298. * If heap protection canaries are enabled, they will be added at the beginning and end
  299. * of each memory allocation and checked during free and other operations. If one is corrupted
  300. * the program will be aborted to protect against security attacks and other faults.
  301. * By default the canaries are statically set but this allows the value to be changed so that
  302. * the value of the canaries is unpredictable in order to foil targetted attacks.
  303. */
  304. void Allocator_setCanary(struct Allocator* alloc, unsigned long value);
  305. /**
  306. * Get the number of bytes allocated by this allocator and all of it's children.
  307. */
  308. unsigned long Allocator_bytesAllocated(struct Allocator* allocator);
  309. /**
  310. * Dump a memory snapshot to stderr.
  311. *
  312. * @param alloc any allocator in the tree, the whole tree will be dumped.
  313. * @param includeAllocations if non-zero then the individual memory allocations will be printed.
  314. */
  315. void Allocator_snapshot(struct Allocator* alloc, int includeAllocations);
  316. /**
  317. * The underlying memory provider function which backs the allocator.
  318. * This function is roughly equivilant to realloc() API in that it is used for allocation,
  319. * reallocation and freeing but it also contains a context field which allows the provider
  320. * to store it's state in a non-global way and a group pointer.
  321. *
  322. * The group pointer is used to add memory to an allocation group. If the group pointer is set to
  323. * NULL, the provider is requested to begin a new group, if the group pointer is not null, it will
  324. * be set to an allocation which had previously been returned by the provider, in this case the
  325. * provider should internally group this allocation with the other as they will likely be freed
  326. * at the same time.
  327. *
  328. * @param ctx the context which was passed to Allocator_new() along with the provider.
  329. * @param original if this is NULL then the allocator is to provide a new allocation, otherwise it
  330. * should resize or free an existing allocation.
  331. * @param size if this is 0 then the allocator should free original and return NULL, if it is not
  332. * zero then original should be resized or created.
  333. * @param group if this is not NULL then the provider is being informed that the current allocation
  334. * and the allocation in group are likely to have the same life span and should be
  335. * colocated if it is logical to do so.
  336. */
  337. #ifndef Allocator_Provider_CONTEXT_TYPE
  338. #define Allocator_Provider_CONTEXT_TYPE void
  339. #endif
  340. Gcc_ALLOC_SIZE(3)
  341. typedef void* (* Allocator_Provider)(Allocator_Provider_CONTEXT_TYPE* ctx,
  342. struct Allocator_Allocation* original,
  343. unsigned long size,
  344. struct Allocator* group);
  345. struct Allocator* Allocator_new(unsigned long sizeLimit,
  346. Allocator_Provider provider,
  347. Allocator_Provider_CONTEXT_TYPE* providerContext,
  348. const char* fileName,
  349. int lineNum);
  350. #endif