1 /* Jitter: memory heap data structure.
2
3 Copyright (C) 2018, 2019 Luca Saiu
4 Written by Luca Saiu
5
6 This file is part of Jitter.
7
8 Jitter is free software: you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation, either version 3 of the License, or
11 (at your option) any later version.
12
13 Jitter is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
17
18 You should have received a copy of the GNU General Public License
19 along with Jitter. If not, see <http://www.gnu.org/licenses/>. */
20
21
22 #include <string.h> /* for memmove. */
23 #include <limits.h> /* for LONG_MAX. */
24 #include "jitter-heap.h"
25 #include <jitter/jitter-fatal.h>
26
27
28 /* Feature macros.
29 * ************************************************************************** */
30
31 /* I might want to make this settable by configure if the future, if I notice
32 that different values work better on different machines. */
33 #define JITTER_HEAP_FIT_FIRST
34 //#define JITTER_HEAP_FIT_BEST
35 #define JITTER_HEAP_HOLE_LIST_LIFO
36 //#define JITTER_HEAP_HOLE_LIST_FIFO
37
38
39
40
41 /* Feature macro validation.
42 * ************************************************************************** */
43
44 /* Check that exactly one fitting strategy has been enabled. */
45 #if defined (JITTER_HEAP_FIT_FIRST) \
46 && defined (JITTER_HEAP_FIT_BEST)
47 # error "hole fitting strategy both FIRST and BEST"
48 #elif (! defined (JITTER_HEAP_FIT_FIRST)) \
49 && (! defined (JITTER_HEAP_FIT_BEST))
50 # error "hole fitting strategy undefined"
51 #else
52 /* Do nothing: everything is fine. */
53 #endif
54
55 /* Check that exactly one hole ordering has been enabled. */
56 #if defined (JITTER_HEAP_HOLE_LIST_LIFO) \
57 && defined (JITTER_HEAP_HOLE_LIST_FIFO)
58 # error "hole list ordering both FIFO and LIFO"
59 #elif (! defined (JITTER_HEAP_HOLE_LIST_LIFO)) \
60 && (! defined (JITTER_HEAP_HOLE_LIST_FIFO))
61 # error "hole list ordering undefined"
62 #else
63 /* Do nothing: everything is fine. */
64 #endif
65
66
67
68
69 /* Heap utility.
70 * ************************************************************************** */
71
72 /* Given a pointer to a thing header, its current tag (assumed to be correct)
73 and a new tag, change the current tag with the new one. This is more fragile
74 but more efficient than a generic "set tag to" function: instead of and-ing
75 off the old tag and then or-ing on a new one, the entire change can be done
76 with just one arithmetic instruction, summing a known constant. */
77 inline static void
jitter_heap_change_tag(struct jitter_heap_thing * thing,enum jitter_heap_thing_tag old_tag,enum jitter_heap_thing_tag new_tag)78 jitter_heap_change_tag (struct jitter_heap_thing *thing,
79 enum jitter_heap_thing_tag old_tag,
80 enum jitter_heap_thing_tag new_tag)
81 {
82 thing->thing_on_the_left
83 = JITTER_HEAP_RETAG_POINTER (thing->thing_on_the_left, old_tag, new_tag);
84 }
85
86 /* Given a thing payload size as requested by the user, return it rounded up so
87 that it is usable, exactly, as a thing payload size. The result respects the
88 constraints on minimal size and alignment. */
89 inline static size_t
jitter_heap_payload_size_rounded_up(size_t payload_size_in_bytes)90 jitter_heap_payload_size_rounded_up (size_t payload_size_in_bytes)
91 {
92 /* If the requested size is smaller than the minimum payload change it to the
93 minimum, which is already correctly aligned; and we're done. */
94 if (payload_size_in_bytes < JITTER_HEAP_MINIMUM_PAYLOAD_SIZE)
95 return JITTER_HEAP_MINIMUM_PAYLOAD_SIZE;
96
97 /* Otherwise, round up to a multiple of the alignment. */
98 return (jitter_uint) JITTER_HEAP_ALIGN_RIGHT (payload_size_in_bytes);
99 }
100
101
102
103
104 /* Heap block initialization.
105 * ************************************************************************** */
106
107 /* Use an existing memory buffer of the given size starting from the given
108 pointer for a fresh heap block, and return the block header.
109 The block header, along with all the block content, will be contained within
110 the provided space but will not necessarily be at its very beginning, in
111 order to satisfy alignment constraints. */
112 static struct jitter_heap_block*
jitter_heap_initialize_block(void * allocated_space,size_t allocated_size_in_bytes,const struct jitter_heap_descriptor * d)113 jitter_heap_initialize_block (void *allocated_space,
114 size_t allocated_size_in_bytes,
115 const struct jitter_heap_descriptor *d)
116 {
117 /* The block header will be at the beginning of the allocated space, possibly
118 skipping space if the allocated space is not correctly aligned. */
119 struct jitter_heap_block *r
120 = ((struct jitter_heap_block *)
121 (jitter_uint)
122 JITTER_NEXT_MULTIPLE_OF_POWER_OF_TWO
123 ((jitter_uint) allocated_space,
124 d->block_size_and_alignment_in_bytes));
125
126 /* Compute usable block limits, on both sides. */
127 char *past_block_end_unaligned
128 = ((char *) allocated_space) + d->block_size_and_alignment_in_bytes;
129
130 /* A just-initialized block will have exactly three things: one left
131 terminator, one hole, and one right terminator. Compute their header
132 addresses, without storing anything into memory yet. The left terminator
133 is at a fixed offset from the block header beginning, so it is stored
134 as a struct field within the block. */
135 struct jitter_heap_thing *left_terminator_header = & r->left_terminator;
136 struct jitter_heap_thing *hole_header
137 = ((struct jitter_heap_thing *)
138 JITTER_HEAP_ALIGN_RIGHT(left_terminator_header + 1));
139 struct jitter_heap_thing *right_terminator_header
140 = JITTER_HEAP_ALIGN_LEFT(past_block_end_unaligned
141 - sizeof (struct jitter_heap_thing));
142 long hole_total_size
143 = ((char*) right_terminator_header) - ((char*) hole_header);
144 long hole_payload_size = hole_total_size - JITTER_HEAP_HEADER_OVERHEAD;
145
146 /* Fail if the block is too small. Block initialization should be infrequent
147 enough for this check to be enabled unconditionally. */
148 if (left_terminator_header >= hole_header
149 || hole_header >= right_terminator_header)
150 jitter_fatal ("initializing a block not large enough for initial blocks");
151 if (hole_total_size <= JITTER_HEAP_MINIMUM_THING_SIZE)
152 jitter_fatal ("initializing a block not large enough for one thing");
153 if (hole_payload_size <= JITTER_HEAP_MINIMUM_PAYLOAD_SIZE)
154 jitter_fatal ("initializing a block not large enough for one hole payload");
155
156 /* Fill the left terminator header. */
157 left_terminator_header->thing_on_the_left
158 = JITTER_HEAP_TAG_POINTER(NULL, jitter_heap_thing_tag_terminator);
159 left_terminator_header->payload_size_in_bytes
160 = JITTER_HEAP_MINIMUM_PAYLOAD_SIZE;
161
162 /* Fill the hole header. */
163 hole_header->thing_on_the_left
164 = JITTER_HEAP_TAG_POINTER(left_terminator_header,
165 jitter_heap_thing_tag_hole);
166 hole_header->payload_size_in_bytes = hole_payload_size;
167
168 /* Fill the right terminator header. */
169 right_terminator_header->thing_on_the_left
170 = JITTER_HEAP_TAG_POINTER(hole_header, jitter_heap_thing_tag_terminator);
171 right_terminator_header->payload_size_in_bytes = JITTER_HEAP_MINIMUM_PAYLOAD_SIZE;
172
173 /* Fill the block header. */
174 r->allocated_space = allocated_space;
175 r->allocated_space_size_in_bytes = allocated_size_in_bytes;
176 /* Notice that I *don't* fill the links field here. A block will be linked in
177 the block list of a heap when it's part of a heap, but this doesn't happen
178 automatically and doesn't need to happen every time. Here we make no
179 assumptions about even the existence of any heap. */
180
181 /* Make the hole linked list.
182 After we add both terminators as the first and last element, the list becomes
183 and remains "always-nonempty" in the sense of jitter-list.h , which lets me
184 use the more efficient _NONEMPTY list manipulation macros. */
185 JITTER_LIST_INITIALIZE_HEADER (& r->hole_list);
186 JITTER_LIST_LINK_FIRST (jitter_heap_thing, hole_links,
187 & (r->hole_list),
188 left_terminator_header);
189 JITTER_LIST_LINK_LAST (jitter_heap_thing, hole_links,
190 & (r->hole_list),
191 right_terminator_header);
192 JITTER_LIST_LINK_AFTER_NONEMPTY (jitter_heap_thing, hole_links,
193 & (r->hole_list),
194 left_terminator_header,
195 hole_header);
196
197 /* The block is now filled. */
198 return r;
199 }
200
201 /* There is no need for a block finalization facility: once the memory for a
202 block is released, with some external mechanism, resources for every thing
203 contained in the block are also released. */
204
205
206
207
208 /* Object allocation, deallocation and reallocation from a given block.
209 * ************************************************************************** */
210
211 /* Look for a hole in the pointed block large enough to fit an object with the
212 given payload size. Return a pointer to the hole header if one exists, or
213 NULL otherwise. */
214 static struct jitter_heap_thing*
jitter_heap_fit(struct jitter_heap_block * b,size_t size_in_bytes)215 jitter_heap_fit (struct jitter_heap_block *b,
216 size_t size_in_bytes)
217 {
218 /* In either case we have to walk the list starting from the first hole. */
219 struct jitter_heap_thing *h = b->left_terminator.hole_links.next;
220
221 /* Find the candidate according to the fitting strategy and return it. Don't
222 return within the conditional code if no candidate was found. */
223 #if defined (JITTER_HEAP_FIT_FIRST)
224 /* First-fit search: return the first hole which is large enough. */
225 while (JITTER_HEAP_GET_TAG (h) != jitter_heap_thing_tag_terminator)
226 {
227 if (h->payload_size_in_bytes >= size_in_bytes)
228 return h;
229
230 h = h->hole_links.next;
231 }
232 #elif defined (JITTER_HEAP_FIT_BEST)
233 /* Best-fit search: return the smallest hole which is large enough. */
234 struct jitter_heap_thing *best = NULL;
235 signed long wasted_bytes_best = LONG_MAX;
236 while (JITTER_HEAP_GET_TAG (h) != jitter_heap_thing_tag_terminator)
237 {
238 signed long wasted_bytes
239 = (long) h->payload_size_in_bytes - (long) size_in_bytes;
240 if (wasted_bytes == 0)
241 return h;
242 else if (wasted_bytes > 0
243 && wasted_bytes < wasted_bytes_best)
244 {
245 best = h;
246 wasted_bytes_best = wasted_bytes;
247 }
248
249 h = h->hole_links.next;
250 }
251 if (best != NULL)
252 return best;
253 #else
254 /* This should never happen. */
255 # error "unknown fitting strategy"
256 #endif
257
258 /* We've looked thru every hole in this block without finding any which was
259 large enough. */
260 return NULL;
261 }
262
263 /* Given a pointer to a block and to a hole header from the block which
264 is not currently in the hole list, link it correctly to the list.
265 Rationale: always using this function to link a hole makes it easy to
266 experiment with different hole list orderings. */
267 static void
jitter_link_hole(struct jitter_heap_block * b,struct jitter_heap_thing * hole)268 jitter_link_hole (struct jitter_heap_block *b,
269 struct jitter_heap_thing *hole)
270 {
271 #if defined (JITTER_HEAP_HOLE_LIST_LIFO)
272 /* This implements a LIFO hole list: the most recent hole becomes the first in
273 the list. */
274 JITTER_LIST_LINK_AFTER_NONEMPTY (jitter_heap_thing, hole_links,
275 & b->hole_list,
276 & b->left_terminator,
277 hole);
278 #elif defined (JITTER_HEAP_HOLE_LIST_FIFO)
279 /* This implements a FIFO hole list: the most recent hole becomes the last in
280 the list. */
281 JITTER_LIST_LINK_BEFORE_NONEMPTY (jitter_heap_thing, hole_links,
282 & b->hole_list,
283 b->hole_list.last,
284 hole);
285 #else
286 # error "No hole ordering defined"
287 #endif
288 }
289
290 void *
jitter_heap_allocate_from_block(struct jitter_heap_block * p,size_t object_payload_size_in_bytes)291 jitter_heap_allocate_from_block (struct jitter_heap_block *p,
292 size_t object_payload_size_in_bytes)
293 {
294 /* Round the size up, as required by the alignment. */
295 object_payload_size_in_bytes
296 = jitter_heap_payload_size_rounded_up (object_payload_size_in_bytes);
297
298 /* Look for a hole. If none large enough exists return NULL, and we're done. */
299 struct jitter_heap_thing *hole
300 = jitter_heap_fit (p, object_payload_size_in_bytes);
301 if (hole == NULL)
302 return NULL;
303
304 /* If we arrived here we have found a suitable hole to fill, totally or in
305 part. Check if splitting the current hole into and object and a smaller
306 hole would not violate the minimum size constraint. The cast in the if
307 condition is important here: without it JITTER_HEAP_MINIMUM_PAYLOAD_SIZE
308 would be taken as unsigned. */
309 long hole_payload_size_in_bytes = hole->payload_size_in_bytes;
310 long smaller_hole_payload_size_in_bytes = (hole_payload_size_in_bytes
311 - object_payload_size_in_bytes
312 - JITTER_HEAP_HEADER_OVERHEAD);
313 if (smaller_hole_payload_size_in_bytes
314 >= (long) JITTER_HEAP_MINIMUM_PAYLOAD_SIZE)
315 {
316 /* The old hole is large enough to split. */
317
318 /* It is more efficient to leave a hole on the left so that I don't need
319 to touch the hole list, instead only changing the payload size of the
320 current hole. The new object thing will fill the rightmost part of the
321 old hole payload. */
322 hole->payload_size_in_bytes = smaller_hole_payload_size_in_bytes;
323 struct jitter_heap_thing *object =
324 ((struct jitter_heap_thing *) (((char *) hole)
325 + JITTER_HEAP_HEADER_OVERHEAD
326 + smaller_hole_payload_size_in_bytes));
327 object->thing_on_the_left
328 = JITTER_HEAP_TAG_POINTER (hole, jitter_heap_thing_tag_object);
329 object->payload_size_in_bytes = object_payload_size_in_bytes;
330 struct jitter_heap_thing *object_on_the_right =
331 ((struct jitter_heap_thing *) (((char *) object)
332 + JITTER_HEAP_HEADER_OVERHEAD
333 + object_payload_size_in_bytes));
334 enum jitter_heap_thing_tag object_on_the_right_tag
335 = JITTER_HEAP_GET_TAG (object_on_the_right);
336 object_on_the_right->thing_on_the_left
337 = JITTER_HEAP_TAG_POINTER (object, object_on_the_right_tag);
338 return JITTER_HEAP_THING_TO_PAYLOAD (object);
339 }
340 else
341 {
342 /* The old hole is not large enough to split: I will replace it entirely
343 with the new object. */
344
345 /* The payload size remains the same since we are using it all, possibly
346 introducing internal fragmentation. The objects on the left and on the
347 right of course remain the same; only the tag needs to change, and the
348 thing, now no longer a hole, needs to be unlinked from the hole
349 list. */
350 jitter_heap_change_tag (hole, jitter_heap_thing_tag_hole,
351 jitter_heap_thing_tag_object);
352 JITTER_LIST_UNLINK_NONEMPTY(jitter_heap_thing, hole_links,
353 & (p->hole_list),
354 hole);
355 return JITTER_HEAP_THING_TO_PAYLOAD (hole);
356 }
357 }
358
359 void
jitter_heap_free_from_block(struct jitter_heap_block * b,void * payload)360 jitter_heap_free_from_block (struct jitter_heap_block *b,
361 void *payload)
362 {
363 /* This function will either make a new hole or, whenever possible, turn one
364 or two existing holes next to * thing into one bigger hole by coalescing.
365 The new or updated hole will go to the beginning of the hole list. */
366
367 /* From the payload, get a pointer to the thing we are freeing. */
368 struct jitter_heap_thing *thing = JITTER_HEAP_PAYLOAD_TO_THING (payload);
369
370 /* Get information about the thing on its left and on the right. */
371 struct jitter_heap_thing *left = JITTER_HEAP_THING_ON_THE_LEFT_OF (thing);
372 bool hole_on_the_left
373 = JITTER_HEAP_GET_TAG (left) == jitter_heap_thing_tag_hole;
374 struct jitter_heap_thing *right = JITTER_HEAP_THING_ON_THE_RIGHT_OF (thing);
375 bool hole_on_the_right =
376 JITTER_HEAP_GET_TAG (right) == jitter_heap_thing_tag_hole;
377
378 /* The new hole will need to point to the thing on its left. We will also
379 need to change the thing_on_the_left pointer in the thing on the right of
380 the hole we are making. What that thing will be depends on whether the
381 thing currently on the right ofthing is a hole (to be coalesced) or not.
382 Unlink existing holes on the left and on the right, if any: they will be
383 replaced with a new hole, in a different list position. */
384 struct jitter_heap_thing *before_new_hole;
385 struct jitter_heap_thing *new_hole;
386 struct jitter_heap_thing *after_new_hole;
387 if (hole_on_the_left)
388 {
389 new_hole = left;
390 before_new_hole = JITTER_HEAP_THING_ON_THE_LEFT_OF (left);
391 JITTER_LIST_UNLINK_NONEMPTY(jitter_heap_thing, hole_links, & (b->hole_list),
392 left);
393 }
394 else
395 {
396 new_hole = thing;
397 before_new_hole = left;
398 }
399 if (hole_on_the_right)
400 {
401 after_new_hole = JITTER_HEAP_THING_ON_THE_RIGHT_OF (right);
402 JITTER_LIST_UNLINK_NONEMPTY(jitter_heap_thing, hole_links, & (b->hole_list),
403 right);
404 }
405 else
406 after_new_hole = right;
407 enum jitter_heap_thing_tag after_new_hole_tag
408 = JITTER_HEAP_GET_TAG (after_new_hole);
409
410 /* Compute where the new hole begins and what its payload size is. Once this
411 is done I can fill in information about the new hole, and link it. */
412 size_t new_hole_payload_size
413 = ((((char *) after_new_hole) - ((char *) new_hole))
414 - JITTER_HEAP_HEADER_OVERHEAD);
415 new_hole->thing_on_the_left
416 = JITTER_HEAP_TAG_POINTER (before_new_hole, jitter_heap_thing_tag_hole);
417 new_hole->payload_size_in_bytes = new_hole_payload_size;
418
419 /* Make the object after the new hole point to the hole by its
420 thing_on_the_left field. */
421 after_new_hole->thing_on_the_left
422 = JITTER_HEAP_TAG_POINTER (new_hole, after_new_hole_tag);
423
424 /* Link the hole, currently the only non-terminator thing on the block. In
425 this case this thing will always go between the two terminators, with any
426 hole ordering implemented by jitter_link_hole . */
427 jitter_link_hole (b, new_hole);
428 }
429
430 /* The trivial version of reallocation: make a new thing, copy from the old
431 thing, free the old thing. This is called when it's difficult to do
432 better. */
433 static void *
jitter_heap_reallocate_from_block_trivial(struct jitter_heap_block * b,void * old_payload,size_t user_new_size_in_bytes)434 jitter_heap_reallocate_from_block_trivial (struct jitter_heap_block *b,
435 void *old_payload,
436 size_t user_new_size_in_bytes)
437 {
438 /* Make a new object with the new size, or return NULL immediately if there is
439 no space. */
440 void *r = jitter_heap_allocate_from_block (b, user_new_size_in_bytes);
441 if (r == NULL)
442 return NULL;
443
444 /* Look at the old object, and compute how many bytes we need to copy from it.
445 Notice that the number of bytes to copy is exactly what the user passed to
446 this function, and not the payload size rounded up by
447 jitter_heap_allocate_from_block . */
448 struct jitter_heap_thing *old_object
449 = JITTER_HEAP_PAYLOAD_TO_THING (old_payload);
450 size_t size_to_copy_in_bytes = old_object->payload_size_in_bytes;
451 if (user_new_size_in_bytes < size_to_copy_in_bytes)
452 size_to_copy_in_bytes = user_new_size_in_bytes;
453
454 /* Fill the new object payload with a copy from the old one. */
455 memmove (r, old_object->payload, size_to_copy_in_bytes);
456
457 /* Free the old object. */
458 jitter_heap_free_from_block (b, old_payload);
459 return r;
460 }
461
462 /* Given a block, and object thing on the block and a hole thing immediately on
463 its right, merge the object and the hole into a larger object.
464 Of course no sanity check is performed: the given things must have the right
465 tag and be in the right positions. */
466 static void
jitter_heap_merge_object_with_hole_on_its_right(struct jitter_heap_block * b,struct jitter_heap_thing * object,struct jitter_heap_thing * hole)467 jitter_heap_merge_object_with_hole_on_its_right
468 (struct jitter_heap_block *b,
469 struct jitter_heap_thing *object,
470 struct jitter_heap_thing *hole)
471 {
472 /* Get a pointer to the object on the right of the hole (which must exist,
473 possibly as a terminator): we will need to update its thing_on_the_right
474 pointer. */
475 struct jitter_heap_thing *after_hole
476 = JITTER_HEAP_THING_ON_THE_RIGHT_OF (hole);
477 enum jitter_heap_thing_tag after_hole_tag = JITTER_HEAP_GET_TAG (after_hole);
478
479 /* Turn the object and the hole into one object. */
480 size_t object_payload_size = object->payload_size_in_bytes;
481 size_t hole_thing_size = (JITTER_HEAP_HEADER_OVERHEAD
482 + hole->payload_size_in_bytes);
483 JITTER_LIST_UNLINK_NONEMPTY(jitter_heap_thing, hole_links,
484 & (b->hole_list), hole);
485 object->payload_size_in_bytes = object_payload_size + hole_thing_size;
486
487 /* Update the object after the removed hole, so that it can find what comes to
488 its left. */
489 after_hole->thing_on_the_left = JITTER_HEAP_TAG_POINTER (object,
490 after_hole_tag);
491 }
492
493 /* Given an existing object thing, shrink it in place by carving a hole on its
494 right if there is sufficient space; when the thing on the right of the
495 initial object is already a hole, coalesce it with the new one.
496 The new object payload size must already respect the constraints on minimum
497 size and alignment. */
498 static void
jitter_heap_shrink_object_in_block(struct jitter_heap_block * b,struct jitter_heap_thing * object,size_t new_object_payload_size_in_bytes)499 jitter_heap_shrink_object_in_block (struct jitter_heap_block *b,
500 struct jitter_heap_thing *object,
501 size_t new_object_payload_size_in_bytes)
502 {
503 /* If the thing on the right of the object thing is a hole, remove the hole
504 by having the object expand into it. Otherwise just keep the information
505 we have discovered about the thing on the right, to be used later. */
506 struct jitter_heap_thing *thing_on_the_right
507 = JITTER_HEAP_THING_ON_THE_RIGHT_OF (object);
508 enum jitter_heap_thing_tag thing_on_the_right_tag
509 = JITTER_HEAP_GET_TAG (thing_on_the_right);
510 if (thing_on_the_right_tag == jitter_heap_thing_tag_hole)
511 {
512 jitter_heap_merge_object_with_hole_on_its_right (b, object,
513 thing_on_the_right);
514 /* The thing on the right of object is now different. */
515 thing_on_the_right
516 = JITTER_HEAP_THING_ON_THE_RIGHT_OF (object);
517 thing_on_the_right_tag
518 = JITTER_HEAP_GET_TAG (thing_on_the_right);
519 }
520 /* From this point on we can assume that the object doesn't have a hole on its
521 right. */
522
523 /* Check if there is enough place for carving a new hole. If not there is
524 nothing to do: we have to live with internal fragmentation. */
525 size_t old_object_payload_size_in_bytes = object->payload_size_in_bytes;
526 size_t new_hole_thing_size_in_bytes
527 = old_object_payload_size_in_bytes - new_object_payload_size_in_bytes;
528 if (new_hole_thing_size_in_bytes < JITTER_HEAP_MINIMUM_THING_SIZE)
529 return;
530
531 /* Update the old object, which will keep existing. The only field we
532 need to change is its payload size. */
533 object->payload_size_in_bytes = new_object_payload_size_in_bytes;
534
535 /* Make a new hole on its right. */
536 char *old_payload = JITTER_HEAP_THING_TO_PAYLOAD (object);
537 struct jitter_heap_thing *new_hole
538 = ((struct jitter_heap_thing *)
539 (((char *) old_payload) + new_object_payload_size_in_bytes));
540 new_hole->payload_size_in_bytes
541 = new_hole_thing_size_in_bytes - JITTER_HEAP_HEADER_OVERHEAD;
542 new_hole->thing_on_the_left
543 = JITTER_HEAP_TAG_POINTER (object, jitter_heap_thing_tag_hole);
544 jitter_link_hole (b, new_hole);
545
546 /* The thing which was on the right of the old object is now on the right
547 of the new hole. */
548 thing_on_the_right->thing_on_the_left
549 = JITTER_HEAP_TAG_POINTER (new_hole, thing_on_the_right_tag);
550 }
551
552 void *
jitter_heap_reallocate_from_block(struct jitter_heap_block * b,void * old_payload,size_t user_new_size_in_bytes)553 jitter_heap_reallocate_from_block (struct jitter_heap_block *b,
554 void *old_payload,
555 size_t user_new_size_in_bytes)
556 {
557 /* Get information about the old thing. */
558 struct jitter_heap_thing *old_object
559 = JITTER_HEAP_PAYLOAD_TO_THING (old_payload);
560 size_t old_payload_size_in_bytes = old_object->payload_size_in_bytes;
561
562 /* Round the user-provided size up, as required by the minimum size and
563 alignment constraints. */
564 size_t new_payload_size_in_bytes
565 = jitter_heap_payload_size_rounded_up (user_new_size_in_bytes);
566
567 /* Are we shrinking or growing the thing? */
568 if (new_payload_size_in_bytes <= old_payload_size_in_bytes)
569 {
570 /* We are shrinking. This is always possible in an efficient way; in the
571 worst case we will create internal fragmentation, but anyway we don't
572 have to allocate or free new things, or copy data around. */
573
574 /* Shrink the object, making a hole if possible. */
575 jitter_heap_shrink_object_in_block (b, old_object,
576 new_payload_size_in_bytes);
577
578 /* Return the old payload: the pointer has not changed and we haven't
579 moved the data, but we have created a new hole. */
580 return old_payload;
581 }
582 else
583 {
584 /* We are growing an object. For this to be possible in an efficient way,
585 the object on the right of the old thing must be a sufficiently large
586 hole. If that is not the case we fall back to a trivial solution. */
587
588 /* Check if we have a large enough hole on the right. If not, fall back
589 to the trivial solution. */
590 struct jitter_heap_thing *thing_on_the_right
591 = JITTER_HEAP_THING_ON_THE_RIGHT_OF(old_object);
592 enum jitter_heap_thing_tag thing_on_the_right_tag
593 = JITTER_HEAP_GET_TAG (thing_on_the_right);
594 size_t thing_on_the_right_size_in_bytes
595 = (thing_on_the_right->payload_size_in_bytes
596 + JITTER_HEAP_HEADER_OVERHEAD);
597 if (thing_on_the_right_tag != jitter_heap_thing_tag_hole
598 || (old_payload_size_in_bytes + thing_on_the_right_size_in_bytes
599 < new_payload_size_in_bytes))
600 return jitter_heap_reallocate_from_block_trivial
601 (b, old_payload, user_new_size_in_bytes);
602
603 /* If we arrived here we can merge the old object with the hole on the
604 right. This current implementation, while still O(1), is slightly
605 suboptimal, as it simply fills the entire hole on the right and then
606 shrinks the new larger object when possible. */
607 jitter_heap_merge_object_with_hole_on_its_right (b, old_object,
608 thing_on_the_right);
609 jitter_heap_shrink_object_in_block (b, old_object,
610 new_payload_size_in_bytes);
611 return old_payload;
612 }
613 }
614
615
616
617
618 /* Big objects.
619 * ************************************************************************** */
620
621 void *
jitter_heap_allocate_big(struct jitter_heap * h,size_t user_payload_size_in_bytes)622 jitter_heap_allocate_big (struct jitter_heap *h,
623 size_t user_payload_size_in_bytes)
624 {
625 /* Compute the size in bytes correctly aligned, and also including the
626 pre-header and header. */
627 size_t payload_size_in_bytes
628 = jitter_heap_payload_size_rounded_up (user_payload_size_in_bytes);
629 size_t total_size_in_bytes
630 = JITTER_HEAP_BIG_TOTAL_OVERHEAD + payload_size_in_bytes;
631
632 /* Use the primitive allocation function to make it. */
633 struct jitter_heap_big *b = h->descriptor.make (total_size_in_bytes);
634 if (b == NULL)
635 jitter_fatal ("could not allocate big object");
636
637 /* Initialize the big pre-header, which means linking it to the big-object
638 list. */
639 JITTER_LIST_LINK_FIRST (jitter_heap_big, big_links, & h->big_list, b);
640
641 /* Initialize the ordinary thing header. */
642 b->thing.thing_on_the_left = JITTER_HEAP_BIG_THING_ON_THE_LEFT;
643 b->thing.payload_size_in_bytes = payload_size_in_bytes;
644
645 return JITTER_HEAP_BIG_TO_PAYLOAD (b);
646 }
647
648 void
jitter_heap_free_big(struct jitter_heap * h,void * big_payload)649 jitter_heap_free_big (struct jitter_heap *h, void *big_payload)
650 {
651 /* Obtain a pointer to the big pre-header. */
652 struct jitter_heap_big *b = JITTER_HEAP_PAYLOAD_TO_BIG (big_payload);
653
654 /* Unlink the big object from the big object list in the heap. */
655 JITTER_LIST_UNLINK (jitter_heap_big, big_links, & (h->big_list), b);
656
657 /* Immediately release storage with the primitive function. */
658 size_t payload_size_in_bytes = b->thing.payload_size_in_bytes;
659 size_t total_size_in_bytes
660 = JITTER_HEAP_BIG_TOTAL_OVERHEAD + payload_size_in_bytes;
661 h->descriptor.destroy (b, total_size_in_bytes);
662 }
663
664
665
666
667 /* Heap initialization and finalization.
668 * ************************************************************************** */
669
670 /* Initialize the pointed heap, except that the first block is set to NULL,
671 the block list is set to empty, and
672 h->descriptor.block_size_smallest_big_payload_in_bytes will be left
673 uninitialized. */
674 static void
jitter_heap_almost_initialize(struct jitter_heap * h,const struct jitter_heap_descriptor * d)675 jitter_heap_almost_initialize (struct jitter_heap *h,
676 const struct jitter_heap_descriptor *d)
677 {
678 h->descriptor = * d;
679 JITTER_LIST_INITIALIZE_HEADER (& (h->block_list));
680 JITTER_LIST_INITIALIZE_HEADER (& (h->big_list));
681 h->default_block = NULL;
682 }
683
684 /* Return a pointer to a fresh heap block allocated using the primitives from
685 the pointer descriptor. The block will be allocated within a new fresh
686 buffer large enough to contain a block of the required size and alignment, as
687 specified within the descriptor; this function serves to abstract the
688 complexity of aligned allocation and possible unmapping. Fail fatally on
689 allocation failure. */
690 static struct jitter_heap_block*
jitter_heap_make_block(const struct jitter_heap_descriptor * d)691 jitter_heap_make_block (const struct jitter_heap_descriptor *d)
692 {
693 size_t natural_alignment = d->make_natural_alignment_in_bytes;
694 size_t block_size = d->block_size_and_alignment_in_bytes;
695
696 /* If the natural alignment is already enough to guarantee the required block
697 alignment, we don't need to do anything particular: the result of the make
698 primitive will already be enough. */
699 if (natural_alignment >= block_size)
700 {
701 char *res;
702 if ((res = d->make (block_size)) == NULL)
703 jitter_fatal ("could not make block for heap");
704 return jitter_heap_initialize_block (res, block_size, d);
705 }
706
707 /* If I arrived here then the natural alignment is not enough to satisfy our
708 block alignment constraint. We have to allocate a larger buffer. */
709 size_t allocated_size = block_size * 2 - natural_alignment;
710 char *unaligned_p;
711 if ((unaligned_p = d->make (allocated_size)) == NULL)
712 jitter_fatal ("could not make (wider) block for heap");
713
714 /* If we have a suitable primitive unmap the unaligned part of the buffer, and
715 update res and allocated_size to only keep into account the part which
716 remains mapped; otherwise we are done already, and
717 jitter_heap_initialize_block will take care of skipping any initial
718 unaligned part. */
719 if (d->unmap_part_or_NULL != NULL)
720 {
721 /* In general we may have to unmap two parts of the wider buffer we
722 allocated: one on the left, and another on the right. */
723 char *p
724 = (char*)
725 (jitter_uint)
726 JITTER_NEXT_MULTIPLE_OF_POWER_OF_TWO ((jitter_uint) unaligned_p,
727 block_size);
728 size_t excess_size_left = p - unaligned_p;
729 size_t excess_size_right
730 = (unaligned_p + allocated_size) - (p + block_size);
731 if (excess_size_left > 0)
732 d->unmap_part_or_NULL (unaligned_p, excess_size_left);
733 if (excess_size_right > 0)
734 d->unmap_part_or_NULL (p + block_size, excess_size_right);
735 unaligned_p = p;
736 allocated_size = block_size;
737 }
738
739 return jitter_heap_initialize_block (unaligned_p, allocated_size, d);
740 }
741
742 /* Given a heap pointer, add a fresh block to it and return it. The pointed
743 heap must be already initialized, except that it's allowed to have a NULL
744 default block; if that is the case, the default block is filled with the
745 result of this function. In every case the new block becomes the default
746 one and the first in the list. */
747 static struct jitter_heap_block *
jitter_heap_add_fresh_block(struct jitter_heap * h)748 jitter_heap_add_fresh_block (struct jitter_heap *h)
749 {
750 /* Make a fresh block. */
751 struct jitter_heap_block *res = jitter_heap_make_block (& h->descriptor);
752
753 /* Add it to the list and set it as the default. We can't use
754 jitter_heap_set_default_block here, as b doesn't belong to the list. */
755 JITTER_LIST_LINK_FIRST (jitter_heap_block, block_links, & h->block_list, res);
756 h->default_block = res;
757
758 return res;
759 }
760
761 /* Given a pointed heap and a pointed block already belonging to the heap, make
762 the block the default one and the first on the list. */
763 static void
jitter_heap_set_default_block(struct jitter_heap * h,struct jitter_heap_block * b)764 jitter_heap_set_default_block (struct jitter_heap *h,
765 struct jitter_heap_block *b)
766 {
767 /* Unlink the block from its previous position on the list, whatever it was,
768 and make it the first item instead. */
769 JITTER_LIST_UNLINK (jitter_heap_block, block_links, & h->block_list, b);
770 JITTER_LIST_LINK_FIRST (jitter_heap_block, block_links, & h->block_list, b);
771
772 /* Set the default field. */
773 h->default_block = b;
774 }
775
776 /* Initialize the pointed heap from the pointed descriptor, ignoring the
777 block_size_smallest_big_payload_in_bytes field of the pointed descriptor,
778 which will be computed here instead. */
779 static void
jitter_heap_initialize_from_descriptor(struct jitter_heap * h,const struct jitter_heap_descriptor * d)780 jitter_heap_initialize_from_descriptor (struct jitter_heap *h,
781 const struct jitter_heap_descriptor *d)
782 {
783 /* Almost-initialize the heap: only the first block and
784 h->descriptor.block_size_smallest_big_payload_in_bytes will be missing. */
785 jitter_heap_almost_initialize (h, d);
786
787 /* Add the first block. */
788 struct jitter_heap_block *first_block = jitter_heap_add_fresh_block (h);
789
790 /* Initialize block_size_smallest_big_payload_in_bytes within the heap
791 descriptor: it's easy to do it now that we have a fresh empty block, as the
792 minimum size of an object payload not fitting in the block will be its hole
793 payload size plus one byte. */
794 const struct jitter_heap_thing *first_block_hole
795 = first_block->left_terminator.hole_links.next;
796 h->descriptor.block_size_smallest_big_payload_in_bytes
797 = first_block_hole->payload_size_in_bytes + 1;
798 }
799
800 void
jitter_heap_initialize(struct jitter_heap * h,jitter_heap_primitive_allocate_function make,jitter_heap_primitive_free_function destroy,size_t make_natural_alignment_in_bytes,jitter_heap_primitive_free_function unmap_part_or_NULL,size_t block_size_and_alignment_in_bytes)801 jitter_heap_initialize (struct jitter_heap *h,
802 jitter_heap_primitive_allocate_function make,
803 jitter_heap_primitive_free_function destroy,
804 size_t make_natural_alignment_in_bytes,
805 jitter_heap_primitive_free_function unmap_part_or_NULL,
806 size_t block_size_and_alignment_in_bytes)
807 {
808 /* Make a descriptor here, as an automatic variable. It will be copied. */
809 struct jitter_heap_descriptor d;
810 d.make = make;
811 d.destroy = destroy;
812 d.make_natural_alignment_in_bytes = make_natural_alignment_in_bytes;
813 d.unmap_part_or_NULL = unmap_part_or_NULL;
814 /* It is convenient to initialize d.block_size_smallest_big_payload_in_bytes
815 later, as the size of the initial hole plus one byte. This will be the
816 tightest possible threshold. */
817
818 /* Validate natural alignment. This operation is infrequent enough to warrant
819 a check. */
820 if (! JITTER_IS_A_POWER_OF_TWO (make_natural_alignment_in_bytes))
821 jitter_fatal ("make natural alignment not a power of two");
822
823 /* Update block_size_and_alignment_in_bytes in case it's not a power of two or
824 a multiple of the alignment size. After the value is reasonable, store it
825 in the structure. */
826 if (block_size_and_alignment_in_bytes < make_natural_alignment_in_bytes
827 || block_size_and_alignment_in_bytes % make_natural_alignment_in_bytes != 0
828 || ! JITTER_IS_A_POWER_OF_TWO (block_size_and_alignment_in_bytes))
829 {
830 size_t minimum = block_size_and_alignment_in_bytes;
831 block_size_and_alignment_in_bytes = make_natural_alignment_in_bytes;
832 while (block_size_and_alignment_in_bytes < minimum)
833 block_size_and_alignment_in_bytes *= 2;
834 }
835
836 /* Now block_size_and_alignment_in_bytes has a sensible value. Store it into
837 the struct, and use it to compute the bitmask. */
838 d.block_size_and_alignment_in_bytes = block_size_and_alignment_in_bytes;
839 d.block_bit_mask
840 = ~ (((jitter_uint) block_size_and_alignment_in_bytes) - 1);
841
842 /* Use the descriptor I have just initialized to initialize the heap. */
843 jitter_heap_initialize_from_descriptor (h, & d);
844 }
845
846 void
jitter_heap_finalize(struct jitter_heap * h)847 jitter_heap_finalize (struct jitter_heap *h)
848 {
849 jitter_heap_primitive_free_function destroy = h->descriptor.destroy;
850
851 /* Destroy every block in the list. */
852 struct jitter_heap_block *b = h->block_list.first;
853 while (b != NULL)
854 {
855 struct jitter_heap_block *next = b->block_links.next;
856 destroy (b->allocated_space, b->allocated_space_size_in_bytes);
857 b = next;
858 }
859
860 /* Do not destroy the default block: it is assumed to be in the list, so it's
861 been destroyed already at this point. */
862 }
863
864
865
866
867 /* Object allocation, deallocation and reallocation from a given heap.
868 * ************************************************************************** */
869
870 /* Given a heap pointer and an initial pointer to some object belonging to the
871 heap, return the block containing the object. */
872 static struct jitter_heap_block *
jitter_heap_get_block(struct jitter_heap * h,void * p)873 jitter_heap_get_block (struct jitter_heap *h, void *p)
874 {
875 jitter_uint mask = h->descriptor.block_bit_mask;
876 return (void *) (((jitter_uint) p) & mask);
877 }
878
879 void *
jitter_heap_allocate(struct jitter_heap * h,size_t user_payload_size_in_bytes)880 jitter_heap_allocate (struct jitter_heap *h,
881 size_t user_payload_size_in_bytes)
882 {
883 /* Check if we should make a big object. If so, do it and ignore the rest. */
884 size_t min_big_payload_size
885 = h->descriptor.block_size_smallest_big_payload_in_bytes;
886 if (__builtin_expect (user_payload_size_in_bytes >= min_big_payload_size,
887 false))
888 return jitter_heap_allocate_big (h, user_payload_size_in_bytes);
889
890 /* First try to allocate from the default block. */
891 struct jitter_heap_block *initial_block = h->default_block;
892 void *res = jitter_heap_allocate_from_block (initial_block,
893 user_payload_size_in_bytes);
894 if (__builtin_expect (res != NULL, true))
895 return res;
896
897 /* If we arrived here the default block doesn't have enough space. Try every
898 other block in the list. Here I can rely on b being the first element of
899 the list: every other block will follow it, and no other list element will
900 be equal to it. */
901 struct jitter_heap_block *b = initial_block->block_links.next;
902 while (b != NULL)
903 {
904 /* Since we failed with the default block, try again with b. */
905 res = jitter_heap_allocate_from_block (b, user_payload_size_in_bytes);
906 if (res != NULL)
907 {
908 /* Allocation from b succeeded. Make b the default block for the
909 future, in the hope that it has more space available. */
910 jitter_heap_set_default_block (h, b);
911 return res;
912 }
913 b = b->block_links.next;
914 }
915
916 /* If we arrived here allocation failed from every block in the heap. We have
917 to make a new one. If allocation failed from there as well, we fail. */
918 struct jitter_heap_block *new_block = jitter_heap_add_fresh_block (h);
919 res = jitter_heap_allocate_from_block (new_block, user_payload_size_in_bytes);
920 if (res == NULL)
921 jitter_fatal ("could not allocate from heap");
922 return res;
923 }
924
925 void
jitter_heap_shrink_in_place(struct jitter_heap * h,void * payload,size_t new_payload_size_in_bytes)926 jitter_heap_shrink_in_place (struct jitter_heap *h, void *payload,
927 size_t new_payload_size_in_bytes)
928 {
929 /* Do nothing if the object is big.
930 FIXME: given an unmapping primitive I can at least free some pages even in
931 this case. */
932 if (__builtin_expect (JITTER_HEAP_IS_PAYLOAD_BIG (payload),
933 false))
934 return;
935
936 /* If we arrived here then the object is not big, and belongs to a block. We
937 can shrink the object in place, unless carving a hole would go below the
938 minimum hole size.
939 Notice that I am *not* checking that the new size does not exceed the
940 current size. */
941 new_payload_size_in_bytes
942 = jitter_heap_payload_size_rounded_up (new_payload_size_in_bytes);
943 struct jitter_heap_block *b = jitter_heap_get_block (h, payload);
944 struct jitter_heap_thing *object = JITTER_HEAP_PAYLOAD_TO_THING (payload);
945 jitter_heap_shrink_object_in_block (b, object, new_payload_size_in_bytes);
946 }
947
948 void *
jitter_heap_reallocate(struct jitter_heap * h,void * old_payload,size_t new_payload_size_in_bytes)949 jitter_heap_reallocate (struct jitter_heap *h, void *old_payload,
950 size_t new_payload_size_in_bytes)
951 {
952 /* Surprisingly, the logic here is quite different from jitter_heap_allocate .
953 Efficient reallocation is only possible within a block; if that fails,
954 fall back to a trivial solution: allocate a fresh block, copy, free. */
955
956 /* Compute how many bytes we need to copy. If this ends up being unused, the
957 compiler should be able to trivially optimize it away. */
958 struct jitter_heap_thing *t = JITTER_HEAP_PAYLOAD_TO_THING(old_payload);
959 size_t old_payload_size_in_bytes = t->payload_size_in_bytes;
960 size_t size_to_copy_in_bytes = old_payload_size_in_bytes;
961 if (new_payload_size_in_bytes < size_to_copy_in_bytes)
962 size_to_copy_in_bytes = new_payload_size_in_bytes;
963
964 /* If the original object is big, there is nothing very clever I do at this
965 point. Anyway it is possible that even if the old object was big, its
966 reallocated copy will become non-big. */
967 if (__builtin_expect (JITTER_HEAP_IS_PAYLOAD_BIG (old_payload),
968 false))
969 {
970 /* The old object was big. Make a new object, big or small as it needs to
971 be, copy the old payload into it, and finally free the old object,
972 which was certainly big. */
973 void *res = jitter_heap_allocate (h, new_payload_size_in_bytes);
974 memcpy (res, old_payload, size_to_copy_in_bytes);
975 jitter_heap_free_big (h, old_payload);
976 return res;
977 }
978
979 /* Try the fast path. */
980 struct jitter_heap_block *b = jitter_heap_get_block (h, old_payload);
981 void *res
982 = jitter_heap_reallocate_from_block (b, old_payload,
983 new_payload_size_in_bytes);
984 if (res != NULL)
985 {
986 /* The block we used for reallocation had some space available. Use it
987 again in the future, in the hope that it has more. */
988 jitter_heap_set_default_block (h, b);
989 return res;
990 }
991
992 /* The fast path failed. */
993 res = jitter_heap_allocate (h, new_payload_size_in_bytes);
994 memcpy (res, old_payload, size_to_copy_in_bytes);
995 jitter_heap_free_from_block (b, old_payload);
996 return res;
997 }
998
999 void
jitter_heap_free(struct jitter_heap * h,void * object_payload)1000 jitter_heap_free (struct jitter_heap *h, void *object_payload)
1001 {
1002 /* If the object is big, free it as a big object and forget about the rest. */
1003 if (__builtin_expect (JITTER_HEAP_IS_PAYLOAD_BIG (object_payload),
1004 false))
1005 {
1006 jitter_heap_free_big (h, object_payload);
1007 return;
1008 }
1009
1010 /* The object is not big, so it belongs to a block. Get its block, and free
1011 it from there. */
1012 struct jitter_heap_block *b = jitter_heap_get_block (h, object_payload);
1013 jitter_heap_free_from_block (b, object_payload);
1014
1015 /* We have freed space from b. Let's use it again by default. */
1016 jitter_heap_set_default_block (h, b);
1017 }
1018