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