Allocator.h 13 KB

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