1 /* Jitter: memory heap data structure header. 2 3 Copyright (C) 2018, 2019 Luca Saiu 4 Updated in 2020 by Luca Saiu 5 Written by Luca Saiu 6 7 This file is part of Jitter. 8 9 Jitter is free software: you can redistribute it and/or modify 10 it under the terms of the GNU General Public License as published by 11 the Free Software Foundation, either version 3 of the License, or 12 (at your option) any later version. 13 14 Jitter is distributed in the hope that it will be useful, 15 but WITHOUT ANY WARRANTY; without even the implied warranty of 16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 17 GNU General Public License for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */ 21 22 23 #ifndef JITTER_HEAP_H_ 24 #define JITTER_HEAP_H_ 25 26 #include <jitter/jitter-config.h> /* For feature macros. */ 27 28 #if defined (JITTER_HAVE_ALIGNAS) 29 # include <stdalign.h> /* For alignas. */ 30 #endif // defined (JITTER_HAVE_ALIGNAS) 31 #include <stddef.h> /* For offsetof. */ 32 33 #include <jitter/jitter.h> 34 #include <jitter/jitter-bitwise.h> 35 #include <jitter/jitter-list.h> 36 37 38 39 40 /* This is a memory handling facility. 41 * ************************************************************************** */ 42 43 /* This is a heap in the sense of a data structure for implementing dynamic 44 memory allocation and freeing of buffers from larger blocks. A heap in 45 this sense is sometimes called a "memory pool". 46 47 This has nothing to do with the tree data structure imposing ordering 48 constraints, also called "heap". */ 49 50 // FIXME: a few words about policies (first-fit in a LIFO-ordered non-segregated 51 // free list [hole list here], immediate coalescing), single blocks and heaps. 52 // Wilson's survey citing his own work [p. 68, left column seems to strongly 53 // favor FIFO over LIFO. Wilson's arguments seem very reasonable; I am only 54 // worried about stronger cache effects on current machines, 25 years after 55 // his publication. 56 // I can experiment quite easily with FIFO, or conditionalize.] 57 58 59 60 61 /* Heap blocks and things. 62 * ************************************************************************** */ 63 64 /* A "block" is a memory interval containing a header, plus space for the 65 objects to be allocated. Every object in a block lives within its memory 66 space, without relying on external memory allocation facilities. The same 67 block memory also contains every bookkeeping data structure, again without 68 relying on external memory. */ 69 70 /* An alignment where it is safe for both header structures and payloads to 71 begin. 72 This *must* be a power of two. */ 73 #define JITTER_HEAP_ALIGNMENT \ 74 8 // Eight bytes should be enough for every architecture. 75 76 /* Each heap block contains a header and then a sequence of "things", each 77 aligned to JITTER_HEAP_ALIGNMENT bytes and all living within the block 78 memory. 79 Each thing can be: 80 - a terminator (a special marker at the beginning and end of each block); 81 - a hole (currently unused memory); 82 - an object (currently used memory). 83 Holes within a single block are linked together in a doubly-linked list, 84 always preceded by the left terminator and followed by the right 85 terminator. 86 Currently, the last freed block is the first in the list (after the 87 left terminator). 88 Every thing, independently from its tag, contains a payload_size field 89 allowing to navigate things within a block left-to-right, ad a 90 thing_on_the_left (tagged) pointer, allowing to navigate right-to-left. */ 91 92 /* A thing header and the beginning of its payload. Every thing pointer is 93 aliged to JITTER_HEAP_ALIGNMENT bytes. Since every thing header stores a 94 pointer to the previous thing (in address order) within the same block and 95 its payload size, it is always possible to navigate from one thing to its 96 neighbors in both directions; this is useful for hole coalescing. 97 This struct is used for things allocated on blocks, and for big objects as 98 well. */ 99 struct jitter_heap_thing 100 { 101 /* The first field should have pointer type, so that we can guarantee that if 102 the structure is aligned correctly, then no 64-bit pointer will be accessed 103 unaligned. The following fields should get correctly aligned for free. */ 104 105 /* A tagged pointer, whose two least significant bits hold a value of type 106 enum jitter_heap_thing_tag. The tag encodes the type of the current thing, 107 and not of the thing on the left. 108 The pointer itself is aligned to at least JITTER_HEAP_ALIGNMENT bytes, and 109 its untagged value can be extracted by masking off the two least 110 significant bits or by subtracting a known tag; no shifting is required. 111 After untagging this pointer points to the header for the thing immediately 112 to the left of the current thing, or is NULL for a left terminator. 113 This is NULL, apart from the tag, for big objects. */ 114 struct jitter_heap_thing *thing_on_the_left; 115 116 /* The payload size, including the anonymous union below and possibly 117 extending further; the byte at (payload + payload_size_in_bytes) is right 118 past the allocated size of this thing and marks the beginning of the next 119 thing on the same block, if any. */ 120 size_t payload_size_in_bytes; 121 122 /* Which of the following field is used depends on the thing tag. */ 123 alignas (JITTER_HEAP_ALIGNMENT) 124 union 125 { 126 /* Doubly-linked-list pointers to the previous and next hole in the block. 127 This is only used for holes. */ 128 struct jitter_list_links hole_links; 129 130 /* The beginning of the payload, which can actually extend further than the 131 size declared here. */ 132 char payload [sizeof (struct jitter_list_links)]; 133 134 /* /\* This unused field should force the anonymous union to be aligned in a */ 135 /* conservative way, so that we can store any reasonable datum as an object */ 136 /* payload. *\/ */ 137 /* double unused; */ 138 }; 139 }; 140 141 /* The number of bytes occupied by the initial header in a block, plus padding. 142 In other words, this is the offset from the header beginning to the payload 143 beginning in each object. */ 144 #define JITTER_HEAP_HEADER_OVERHEAD \ 145 (offsetof (struct jitter_heap_thing, payload)) \ 146 147 /* The size for the smallest possible thing. The "size of a thing" always 148 includes the header as well, and not only the payload. */ 149 #define JITTER_HEAP_MINIMUM_THING_SIZE \ 150 (sizeof (struct jitter_heap_thing)) 151 152 /* The minimum payload (or links) size for a thing in bytes, independently from 153 its tag. */ 154 #define JITTER_HEAP_MINIMUM_PAYLOAD_SIZE \ 155 (sizeof (struct jitter_heap_thing) \ 156 - JITTER_HEAP_HEADER_OVERHEAD) 157 158 /* Given an expression evaluating to a pointer, expand to an expression 159 evaluting to the same pointer or the next possible smaller value respecting 160 JITTER_HEAP_ALIGNMENT. */ 161 #define JITTER_HEAP_ALIGN_LEFT(p) \ 162 ((void *) \ 163 JITTER_PREVIOUS_MULTIPLE_OF_POWER_OF_TWO((jitter_uint) (p), \ 164 JITTER_HEAP_ALIGNMENT)) 165 166 /* Like JITTER_HEAP_ALIGN_LEFT, but evaluate to the same pointer or the next 167 possible *larger* value. */ 168 #define JITTER_HEAP_ALIGN_RIGHT(p) \ 169 ((void *) \ 170 JITTER_NEXT_MULTIPLE_OF_POWER_OF_TWO((jitter_uint) (p), \ 171 JITTER_HEAP_ALIGNMENT)) 172 173 /* Every used configuration of the tag associated to the pointer field in object 174 headers. The tag is JITTER_HEAP_THING_TAG_BIT_NO bits wide. */ 175 enum jitter_heap_thing_tag 176 { 177 /* The header is for a hole. */ 178 jitter_heap_thing_tag_hole = 0, 179 180 /* The header is for an object. */ 181 jitter_heap_thing_tag_object = 1, 182 183 /* The header is for a block terminator, without distinction between left and 184 right. */ 185 jitter_heap_thing_tag_terminator = 2, 186 187 /* The header for a big object. Big objects don't live in blocks, but are 188 allocated each in its own buffer, controlled by heaps. See below. */ 189 jitter_heap_thing_tag_big = 3 190 }; 191 192 /* How many bits are reserved for a tag within a tagged pointer. Right now, 193 with objects aligned to 8 bytes on every architectures, I could already 194 afford 3 tag bits for free, even if 2 suffice. By simply enforcing a wider 195 alignment I could make even more tag bits available. */ 196 #define JITTER_HEAP_THING_TAG_BIT_NO \ 197 2 198 199 /* A bitmask having 1 bits where the tag is in a pointer, 0 elsewhere. */ 200 #define JITTER_HEAP_THING_TAG_BIT_MASK \ 201 ((jitter_uint) ((1 << JITTER_HEAP_THING_TAG_BIT_NO) - 1)) 202 203 /* A bitmask having 0 bits where the tag is in a pointer, 1 elsewhere. */ 204 #define JITTER_HEAP_THING_NON_TAG_BIT_MASK \ 205 (~ JITTER_HEAP_THING_TAG_BIT_MASK) 206 207 /* Given an expression evaluating to an untagged pointer, expand to an 208 expression evaluating to the same pointer with the given tag. The expansion 209 may evaluate p multiple times. */ 210 #define JITTER_HEAP_TAG_POINTER(p, tag) \ 211 ((struct jitter_heap_thing *) \ 212 (((jitter_uint) (p)) | ((jitter_uint) (tag)))) 213 214 /* Given an expression evaluating to a tagged pointer and an expression 215 evaluating to its tag, assumed to be the same, expand to an expression 216 evaluating to the same untagged pointer. The expansion may evaluate the 217 macro arguments multiple times. 218 This is the preferred way of untagging a pointer: often the untagging can be 219 done at zero costs, as GCC can generate a load instruction with a constant 220 offset to account for the quantity to subtract. */ 221 #define JITTER_HEAP_UNTAG_POINTER_KNOWN_TAG(p, tag) \ 222 ((struct jitter_heap_thing *) \ 223 (((jitter_uint) (p)) - ((jitter_uint) (tag)))) 224 225 /* Given an expression evaluating to a tagged pointer, an expression 226 evaluating to its current tag assumed to be the the given one, and a third 227 expression evaluating to a new tag, expand to an expression evaluating to 228 the same pointer tagged with the new tag instead of the current one. 229 The expansion may evaluate the macro arguments multiple times. */ 230 #define JITTER_HEAP_RETAG_POINTER(p, old_tag, new_tag) \ 231 ((struct jitter_heap_thing *) \ 232 (((jitter_uint) (p)) \ 233 - ((jitter_uint) (old_tag)) \ 234 + ((jitter_uint) (new_tag)))) 235 236 /* Given an expression evaluating to a tagged pointer expand to an expression 237 evaluating to the same untagged pointer. The expansion may evaluate the 238 macro arguments multiple times. 239 This is usually less efficient than JITTER_HEAP_UNTAG_POINTER_KNOWN_TAG. */ 240 #define JITTER_HEAP_UNTAG_POINTER(p) \ 241 ((struct jitter_heap_thing *) \ 242 (((jitter_uint) (p)) & JITTER_HEAP_THING_NON_TAG_BIT_MASK)) 243 244 /* Given an expression evaluating to a tagged pointer expand to an expression 245 evaluating to its tag. The expansion may evaluate the macro argument 246 multiple times. */ 247 #define JITTER_HEAP_POINTER_TAG(p) \ 248 ((enum jitter_heap_thing_tag) \ 249 (((jitter_uint) (p)) & JITTER_HEAP_THING_TAG_BIT_MASK)) 250 251 /* Expand to an expression evaluating to the tag of the thing pointed to by the 252 result of the given expression, which should evaluate to an object of type 253 struct jitter_heap_thing * . */ 254 #define JITTER_HEAP_GET_TAG(thing) \ 255 (JITTER_HEAP_POINTER_TAG ((thing)->thing_on_the_left)) 256 257 /* Expand to an expression evaluating to the payload of the result of the given 258 expression, which should evaluate to an object of type 259 struct jitter_heap_thing * . 260 The argument may be evaluated multiple times. */ 261 #define JITTER_HEAP_THING_TO_PAYLOAD(thing) \ 262 ((thing)->payload) 263 264 /* Expand to an expression evaluating to a the pointer of the thing whose 265 initial payload pointer is the result of the given expression. 266 The argument may be evaluated multiple times. */ 267 #define JITTER_HEAP_PAYLOAD_TO_THING(p) \ 268 ((struct jitter_heap_thing *) \ 269 (((char *) (p)) - JITTER_HEAP_HEADER_OVERHEAD)) 270 271 /* Expand to an expression evaluating to a pointer to the thing on the left of 272 the thing pointed by the result of the given expression, which should 273 evaluate to an object of type struct jitter_heap_thing * . 274 The argument may be evaluated multiple times. */ 275 #define JITTER_HEAP_THING_ON_THE_LEFT_OF(thing) \ 276 (JITTER_HEAP_UNTAG_POINTER((thing)->thing_on_the_left)) 277 278 /* Expand to an expression evaluating to a pointer to the thing on the right of 279 the thing pointed by the result of the given expression, which should 280 evaluate to an object of type struct jitter_heap_thing * . 281 The argument may be evaluated multiple times. */ 282 #define JITTER_HEAP_THING_ON_THE_RIGHT_OF(thing) \ 283 ((struct jitter_heap_thing *) \ 284 (((char *) JITTER_HEAP_THING_TO_PAYLOAD (thing)) \ 285 + (thing)->payload_size_in_bytes)) 286 287 /* A "block" is a data structure written at or near the beginning of some 288 allocated memory, followed by things living in the same memory space. */ 289 struct jitter_heap_block 290 { 291 /* The first field should have pointer type; see the comment above. */ 292 293 /* A pointer to the allocated memory for the block, which is not necessarily 294 the same as a pointer to this structure, as there may be alignment 295 constraints. The memory to be freed when the block is released is the one 296 referred by this pointer. */ 297 void *allocated_space; 298 299 /* A doubly linked list containing: 300 - the left terminator; 301 - all the holes in this block, in an unspecified order; 302 - the right terminator. 303 304 The left and right terminators never change after block initialization, and 305 therefore the list is "always-nonempty" in the sense of jitter-list.h . 306 This assumption makes list update operations much more efficient. */ 307 struct jitter_list_header hole_list; 308 309 /* How many bytes were allocated, including any bytes wasted by misalignment. */ 310 size_t allocated_space_size_in_bytes; 311 312 /* Links to the previous and next block within a heap. */ 313 struct jitter_list_links block_links; 314 315 /* Having the left terminator directly accessible as a field is convenient to 316 walk thru the hole list, without dereferencing hole_list->first and then skipping 317 the first element every time. 318 The right terminator cannot be stored in the same way, as its offset from 319 the beginning of the block header depends on the block size. */ 320 alignas (JITTER_HEAP_ALIGNMENT) 321 struct jitter_heap_thing left_terminator; 322 323 /* There must be no other field after the left terminator: other things get 324 allocated in the memory buffer holding this data structure right after the 325 left terminator. */ 326 }; 327 328 329 330 331 /* Object allocation, deallocation and reallocation from a given block. 332 * ************************************************************************** */ 333 334 /* The functions in this section work on object payload pointers, as seen by the 335 user; internal object (and hole) headers are invisible. */ 336 337 /* Given a heap block, return a pointer to a freshly allocated object within the 338 block having the given payload size (or higher, to satisfy alignment 339 constraints). Return NULL if there is no single hole large enough to satisy 340 the request. 341 The returned pointer is aligned to JITTER_HEAP_ALIGNMENT bytes. */ 342 void * 343 jitter_heap_allocate_from_block (struct jitter_heap_block *b, 344 size_t size_in_bytes) 345 __attribute__ ((nonnull (1), malloc, 346 alloc_size (2), 347 assume_aligned (JITTER_HEAP_ALIGNMENT))); 348 349 /* Given a heap block and a pointer to an existing object within it, return a 350 pointer to a new object of the given new size having the same content of the 351 pointed existing object up to the given new size, and free the existing 352 object. Return NULL if there is no single hole large enough to satisy the 353 request. 354 The returned pointer may be the same as old_payload or the new object may 355 otherwise reuse the same space occupied by the old one, but in the general 356 case it is invalid to keep using old_payload after this call returns a 357 non-NULL value. 358 The returned pointer is aligned to JITTER_HEAP_ALIGNMENT bytes. */ 359 void * 360 jitter_heap_reallocate_from_block (struct jitter_heap_block *b, 361 void *old_payload, 362 size_t new_size_in_bytes) 363 __attribute__ ((nonnull (1, 2), 364 alloc_size (3), 365 assume_aligned (JITTER_HEAP_ALIGNMENT), 366 warn_unused_result)); 367 368 /* Given a heap block and an initial pointer to the payload of an object 369 allocated on the block, free the object, compacting any holes around it. */ 370 void 371 jitter_heap_free_from_block (struct jitter_heap_block *p, 372 void *object_on_p) 373 __attribute__ ((nonnull (1, 2))); 374 375 376 377 378 /* Big objects. 379 * ************************************************************************** */ 380 381 /* Big objects do not live on heap blocks: they are allocated individually, on 382 demand, with the primitives supplies by the user in a heap header and 383 released immediately as soon as the user frees. This, when the primitive 384 relies on mmap, will let the memory be immediately returned to the operating 385 system. */ 386 387 /* Every big object has a header just like heap things living in blocks, for 388 format compatibility. In order to be able to distinguish big and non-big 389 objects at run time big objects have a distinct tag (see the definition of 390 enum jitter_heap_thing_tag above). 391 392 Every big object in a heap belongs to a doubly linked list, distinct from the 393 list of objects in a block and from the list of blocks. Since I don't want 394 to add two fields in the header of *every* object, wasting space on non-big 395 objects as well, big objects have a "big pre-header", which is allocated in 396 memory just before the ordinary object header, at a fixed negative offset. */ 397 398 /* The pre-header for big objects, also containing the object header, structured 399 like the header of non-big objects, which in its turn includes the beginning 400 of the object payload. 401 The pre-header is aligned to JITTER_HEAP_ALIGNMENT bytes, and so are its 402 internal header and the payload within the header. */ 403 struct jitter_heap_big 404 { 405 /* Doubly-linked list pointers to the previous and next big objects in 406 the same heap. */ 407 struct jitter_list_links big_links; 408 409 /* The ordinary thing header, containing a jitter_heap_thing_tag_big tag 410 and NULL as the thing_on_the_left pointer. */ 411 alignas (JITTER_HEAP_ALIGNMENT) 412 struct jitter_heap_thing thing; 413 414 /* There must be nothing else after the header: the header actually includes 415 the beginning of the payload, which must not be interrupted by other fields 416 before the rest of the payload. */ 417 }; 418 419 /* The thing_on_the_left field value for every big object, which is to say a 420 NULL pointer tagged with the jitter_heap_thing_tag_big tag. */ 421 #define JITTER_HEAP_BIG_THING_ON_THE_LEFT \ 422 ((struct jitter_heap_thing *) \ 423 (((jitter_uint) NULL) \ 424 | (jitter_uint) jitter_heap_thing_tag_big)) 425 426 /* Given an expression evaluating to an initial pointer to an object payload, 427 expand to an expression evaluating to non-false iff the object is big. 428 Implementation note: this is faster than using JITTER_HEAP_GET_TAG: I can 429 avoid the masking operation by relying on the fact that the thing_on_the_left 430 pointer is always (tagged) NULL for big objects. */ 431 #define JITTER_HEAP_IS_PAYLOAD_BIG(payload) \ 432 ((JITTER_HEAP_PAYLOAD_TO_THING(payload)->thing_on_the_left) \ 433 == JITTER_HEAP_BIG_THING_ON_THE_LEFT) 434 435 /* The overhead of a big pre-header in bytes, or in other words the offset from 436 the beginning of the big pre-haeder to the beginning of the thing header. 437 The big pre-header overhead doesn't include the thing header size. */ 438 #define JITTER_HEAP_BIG_PRE_HEADER_OVERHEAD \ 439 (offsetof (struct jitter_heap_big, thing)) 440 441 /* The total overhead of big pre-header plus thing header for a big object, or 442 in other words the offset from the beginning of the big pre-haeder to the 443 beginning of the payload within the thing within the big pre-header. */ 444 #define JITTER_HEAP_BIG_TOTAL_OVERHEAD \ 445 (JITTER_HEAP_BIG_PRE_HEADER_OVERHEAD \ 446 + JITTER_HEAP_HEADER_OVERHEAD) 447 448 /* Given an expression evaluating to an initial pointer to an big object 449 payload, expand to an expression evaluating to a pointer to the object 450 big pre-header. */ 451 #define JITTER_HEAP_PAYLOAD_TO_BIG(payload) \ 452 ((struct jitter_heap_big *) \ 453 (((char *) (payload)) - JITTER_HEAP_BIG_TOTAL_OVERHEAD)) 454 455 /* Given an expression evaluating to an initial pointer to an big object 456 payload, expand to an expression evaluating to a pointer to the object 457 big pre-header. */ 458 #define JITTER_HEAP_BIG_TO_PAYLOAD(bigp) \ 459 ((void *) (((char *) (bigp)) + JITTER_HEAP_BIG_TOTAL_OVERHEAD)) 460 461 /* A forward-declaration. */ 462 struct jitter_heap; 463 464 /* Allocate a fresh big object of the given user payload size from the pointed 465 heap. Return an initial pointer to its payload. 466 This function is slightly more efficient than general heap allocation, and 467 can be used when the user is sure that the required object will be big. */ 468 void * 469 jitter_heap_allocate_big (struct jitter_heap *h, 470 size_t user_payload_size_in_bytes) 471 __attribute__ ((nonnull (1), returns_nonnull)); 472 473 /* Given a heap pointer and an initial pointer to the payload of a big object 474 belonging to it, free the big object. This doesn't check that the payload 475 actually belongs to a suitable object, but should be slightly faster than 476 the general freeing function. */ 477 void 478 jitter_heap_free_big (struct jitter_heap *h, void *big_payload) 479 __attribute__ ((nonnull (1))); 480 481 /* Reallocation is not supported for big objects. For the time being I will 482 assume that it's a non-critical operation in this case. */ 483 484 485 486 487 /* Heaps. 488 * ************************************************************************** */ 489 490 /* A "heap" as intended here is a data structure holding an arbitrary number of 491 blocks, each block holding objects, along with information about how to make 492 and destroy blocks. 493 Every block in the heap will have the same length, and will be aligned to 494 this length. This makes it possible, given any object address within the 495 block, to find the block with a quick bitwise masking operation. 496 497 A heap is a convenient abstraction to allocate, deallocate and reallocate 498 objects from blocks which are automatically made and destroyed as needed; if 499 an allocated object is too big to fit in a blog, heap allocation and 500 reallocation functions will automatically make a big object instead. 501 502 Of course operations within an existing block are assumed to be more 503 efficient than operations altering the number of blocks, which usually 504 require syscalls. Heap operations will attempt to reuse existing blocks as 505 far as possible. */ 506 507 /* Here come some types for functions to be supplied by the user, defining a 508 block "kind". */ 509 510 /* A function allocating fresh memory for a block, taking a size in bytes and 511 returning a fresh block of at least the required size, or NULL on allocation 512 failure. */ 513 typedef void * (* jitter_heap_primitive_allocate_function) 514 (size_t size_in_bytes); 515 516 /* A function destroying an existing block, taking the block as returned by the 517 appropriate jitter_heap_primitive_allocate_function function and the 518 allocated size as it was passed at making time. */ 519 typedef void (* jitter_heap_primitive_free_function) 520 (void *allocated_memory, size_t size_in_bytes); 521 522 /* A descriptor for heap objects, specifying its allocation primitives. The 523 same descriptor might be used for multiple heaps, but it's relatively 524 inconvenient for the user to specify it; therefore structures of this type 525 are automatically filled by jitter_heap_initialize , and are effectively 526 invisible to the user. */ 527 struct jitter_heap_descriptor 528 { 529 /* A function allocating a fresh block or big object. */ 530 jitter_heap_primitive_allocate_function make; 531 532 /* A function destroying an entire existing block or big object. */ 533 jitter_heap_primitive_free_function destroy; 534 535 /* The "natural" alignment in bytes which is always and automatically 536 guaranteed by the make allocation primitive, pointed by the field above. */ 537 size_t make_natural_alignment_in_bytes; 538 539 /* A function deallocating only a *part* for a block allocated by the make 540 primitive pointed above. This can be NULL if no suitable primitive for 541 unmapping part of a buffer exists; otherwise the API will be just like an 542 munmap with no result. */ 543 jitter_heap_primitive_free_function unmap_part_or_NULL; 544 545 /* The desired block size in bytes. This constraint is, in general, respected 546 by allocating larger blocks using the make primitive pointed above, and if 547 possible unmapping a part of the buffer. */ 548 size_t block_size_and_alignment_in_bytes; 549 550 /* The block bit mask, having 1 bits for the bits identifying a block and 551 0 bits for the bits which are part of an offset within the block. */ 552 jitter_uint block_bit_mask; 553 554 /* The size in bytes of the smallest payload large enough to belong to a big 555 object. */ 556 size_t block_size_smallest_big_payload_in_bytes; 557 }; 558 559 /* A data structure encoding a heap. The user will initialize a structure 560 of this type and use it for allocating and freeing. */ 561 struct jitter_heap 562 { 563 /* A descriptor for this heap. This small struct is copied rather than 564 pointed, to avoid an indirection on time-critical heap operations on 565 objects. */ 566 struct jitter_heap_descriptor descriptor; 567 568 /* The list of all the blocks in this current heap. This is never empty, but 569 the list cannot be considered "always-nonempty" as per jitter-list.h , 570 since this doesn't use terminator elements and the first and last elements 571 of the list can change. */ 572 // FIXME: possibly make this always-nonempty, by adding two dummy (unaligned) 573 // blocks as elements within this struct. In this case the terminators don't 574 // need to be in a specific order by address, differently from thing 575 // terminators within a block. Is this critical enough? Maybe not. 576 struct jitter_list_header block_list; 577 578 /* The list of all the big objects in this heap. */ 579 // FIXME: possibly make this always-nonempty as well. 580 struct jitter_list_header big_list; 581 582 /* A pointer to the current block, from which we are allocating by default. 583 This is never NULL, and is always equal to the first element of the list; 584 however we save indirections by keeping a pointer here as an 585 optimization. */ 586 struct jitter_heap_block *default_block; 587 }; 588 589 /* Initialize the pointed heap to use the pointed descriptor elements. A 590 suitable descriptor, stored in the heap, is initialized automatically and 591 completed by computing values for the remaining fields from the given 592 values. 593 The given value for block_size_and_alignment_in_bytes here is a lower bound: 594 the actual block size will be increased as needed in order for it to be 595 a power of two, and a multiple of make_natural_alignment_in_bytes . */ 596 void 597 jitter_heap_initialize (struct jitter_heap *h, 598 jitter_heap_primitive_allocate_function make, 599 jitter_heap_primitive_free_function destroy, 600 size_t make_natural_alignment_in_bytes, 601 jitter_heap_primitive_free_function unmap_part_or_NULL, 602 size_t block_size_and_alignment_in_bytes) 603 __attribute__ ((nonnull (1, 2, 3))); 604 605 /* Finalize the pointed heap, destroying every block it contains. */ 606 void 607 jitter_heap_finalize (struct jitter_heap *h) 608 __attribute__ ((nonnull (1))); 609 610 611 612 613 /* Object allocation, deallocation and reallocation from a given heap. 614 * ************************************************************************** */ 615 616 /* These function are similar to their _from_block counterparts, but take a heap 617 pointer instead of a block pointer. 618 619 These are the main user functions for working with allocation, reallocation 620 and freeing of objects. The returned payloads may be big objects: the user 621 sees no difference. 622 623 Allocation and reallocation never return NULL: failure is fatal. */ 624 625 /* Given a heap, return a pointer to a freshly allocated object within the 626 heap having at least the given payload size (or higher, to satisfy alignment 627 constraints). Fail fatally if allocation is not possible. 628 The returned pointer is aligned to JITTER_HEAP_ALIGNMENT bytes. */ 629 void * 630 jitter_heap_allocate (struct jitter_heap *h, size_t size_in_bytes) 631 __attribute__ ((nonnull (1), malloc, returns_nonnull, 632 alloc_size (2), 633 assume_aligned (JITTER_HEAP_ALIGNMENT))); 634 635 /* Given a heap pointer and a pointer to an existing object within it, return a 636 pointer to a new object of the given new size having the same content of the 637 pointed existing object up to the given new size, and free the existing 638 object. Fail fatally if there is not enough space and creating a new block 639 fails. The returned pointer may be the same as old_payload or the new object 640 may otherwise reuse the same space occupied by the old one, but in the 641 general case it is invalid to keep using old_payload after this call returns. 642 The returned pointer is aligned to JITTER_HEAP_ALIGNMENT bytes. */ 643 void * 644 jitter_heap_reallocate (struct jitter_heap *h, void *old_payload, 645 size_t new_size_in_bytes) 646 __attribute__ ((nonnull (1, 2), returns_nonnull, alloc_size (3), 647 assume_aligned (JITTER_HEAP_ALIGNMENT), warn_unused_result)); 648 649 /* Given a heap pointer and a pointer to an existing object within it, free 650 space after the object by shrinking it to the given new size in bytes, which 651 must not be less than the current object allocated size, rounded up as 652 required by the implementation. If freeing up space is not possible do 653 nothing, without failing. */ 654 void 655 jitter_heap_shrink_in_place (struct jitter_heap *h, void *payload, 656 size_t new_size_in_bytes) 657 __attribute__ ((nonnull (1, 2))); 658 659 /* Given a heap and an initial pointer to the payload of an object from the 660 heap, free the object. */ 661 void 662 jitter_heap_free (struct jitter_heap *h, void *object_payload) 663 __attribute__ ((nonnull (1, 2))); 664 665 #endif // #ifndef JITTER_HEAP_H_ 666