1 /* Simple and straight-forward malloc implementation (front end).
2
3 Copyright (C) 2020-2021 Free Software Foundation, Inc.
4
5 This file is free software: you can redistribute it and/or modify
6 it under the terms of the GNU Lesser General Public License as
7 published by the Free Software Foundation; either version 2.1 of the
8 License, or (at your option) any later version.
9
10 This file is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
13 GNU Lesser General Public License for more details.
14
15 You should have received a copy of the GNU Lesser General Public License
16 along with this program. If not, see <https://www.gnu.org/licenses/>. */
17
18 /* Written by Bruno Haible <bruno@clisp.org>, 2020. */
19
20 /* This file implements an allocator of memory blocks of given size (a
21 "malloc front end"), based on an allocator of memory pages (a "malloc
22 back end").
23
24 The need for such an allocator arises because a memory block is often
25 50 bytes large or less, whereas an allocator of memory pages provides
26 entire pages (4096 bytes or more).
27
28 This implementation attempts to be
29 - simple and straight-forward,
30 - respecting locality of reference,
31 - usable for small allocations,
32 - nevertheless of reasonable speed.
33
34 Simple and straight-forward - means that it contains only a small amount
35 of code (compared to e.g. tcmalloc).
36
37 Respecting locality of reference - means that searching for a free block
38 will not follow lists of pointers that touch unrelated cache lines in
39 the same page or even unrelated memory pages, because that would cause
40 cache misses or even swapping in of unrelated memory pages.
41
42 Usable for small allocations - means that it can be used for data types
43 with few instances. It does not, unlike some other malloc implementations,
44 allocate 256 KB of memory up-front. Nor does it allocate memory pages
45 per thread.
46
47 Reasonable speed is nevertheless guaranteed by
48 - choosing algorithms that lead to little fragmentation,
49 - small caches where they make sense.
50 */
51
52 /* The user of this file needs to define the following macros before including
53 this file:
54
55 PAGESIZE A variable-like macro of type intptr_t or uintptr_t
56 that evaluates to the memory page size (>= 4096).
57
58 PAGESIZE_MAX A constant that specifies an upper bound for PAGESIZE.
59
60 ALLOC_PAGES A function-like macro with the signature
61 uintptr_t ALLOC_PAGES (size_t size)
62 where the argument size is > 0 and a multiple of the
63 PAGESIZE. It returns a multiple of PAGESIZE, or 0
64 upon failure.
65
66 FREE_PAGES A function-like macro with the signature
67 void FREE_PAGES (uintptr_t pages, size_t size)
68 where pages is a non-zero value returned by
69 ALLOC_PAGES (size).
70
71 ALIGNMENT A constant that specifies the desired alignment of all
72 the returned memory blocks. Possible values are the
73 powers of 2, from sizeof (void *) to 32.
74
75 PAGE_RESERVED_HEADER_SIZE A constant, either 0 or a multiple of
76 sizeof (void *), that denotes the size of a reserved
77 header - not to be used by the application - at the
78 beginning of a page sequence returned by ALLOC_PAGES.
79 */
80
81 /* =================== Declarations of exported functions =================== */
82
83 #include <stdint.h>
84
85 /* Allocates a block of memory, aligned to ALIGNMENT bytes.
86 Returns 0 upon failure. */
87 static uintptr_t allocate_block (size_t size);
88
89 /* Frees a block of memory, returned by allocate_block. */
90 static void free_block (uintptr_t block);
91
92 /* ============================= Implementation ============================= */
93
94 /* Outline of the implementation decisions (ID):
95
96 * ID: This implementation considers three types of blocks:
97 - small blocks - these are allocated in "small block" pages.
98 - medium blocks - these are allocated in "medium block" pages.
99 - large blocks - these are allocated individually, with a page or
100 sequence of pages uniquely for this block.
101 * Rationale:
102 - Most memory allocations are small (e.g. <= 32 bytes); this is a lesson
103 learned from xc/programs/Xserver/os/xalloc.c (1997) [Pascal Haible].
104 - Fragmentation is one of the biggest problems, and keeping large
105 blocks and small blocks separate from medium blocks is one way to
106 control it.
107
108 * ID: If an allocation succeeds in one page, the next allocation (of the
109 same type of block) will try to use the same page.
110 * Rationale: Locality of reference.
111
112 * ID: Pages of small or medium blocks have their management data structures
113 concentrated at the beginning of the page. No chained lists that force
114 to walk through the page.
115 * Rationale: Locality of reference.
116
117 * ID: Across pages, the management of the free space is done through data
118 structures outside the pages. No chained lists across pages.
119 * Rationale: Locality of reference.
120
121 */
122
123 #include <stdlib.h>
124 #include <string.h> /* ffsll */
125 #include <strings.h> /* ffs */
126 #include "flexmember.h"
127 #include "glthread/lock.h"
128 #include "thread-optim.h"
129 #include "gl_oset.h"
130 #include "gl_rbtree_oset.h"
131
132 /* Help the branch prediction. */
133 #if __GNUC__ >= 3
134 # define likely(cond) __builtin_expect ((cond), 1)
135 # define unlikely(cond) __builtin_expect ((cond), 0)
136 #else
137 # define likely(cond) (cond)
138 # define unlikely(cond) (cond)
139 #endif
140
141 enum { small_page_type = 1, medium_page_type = 2, large_page_type = 3 };
142
143 /* Header of a page of small or medium blocks or of a large block.
144 Lies at an address that is a multiple of PAGESIZE. */
145 struct any_page_header
146 {
147 #if PAGE_RESERVED_HEADER_SIZE > 0
148 void * reserved[PAGE_RESERVED_HEADER_SIZE / sizeof (void *)];
149 #endif
150 /* small_page_type or medium_page_type or large_page_type */
151 unsigned char page_type;
152 };
153
154 /* ========================= Small and medium blocks ======================== */
155
156 /* An integer type, capable of holding the values 0 .. PAGESIZE. */
157 #if PAGESIZE_MAX >= 0x10000
158 typedef unsigned int pg_offset_t;
159 #else
160 typedef unsigned short pg_offset_t;
161 #endif
162
163 /* Tree element that corresponds to a page.
164 These tree elements are allocated via malloc(). */
165 struct page_tree_element
166 {
167 uintptr_t page;
168 pg_offset_t free_space;
169 };
170
171 /* Header of a page of small or medium blocks.
172 Lies at an address that is a multiple of PAGESIZE. */
173 struct dissected_page_header
174 {
175 struct any_page_header common;
176 /* Amount of free space in this page. Always a multiple of ALIGNMENT. */
177 pg_offset_t free_space;
178 /* The tree element. */
179 struct page_tree_element *tree_element;
180 };
181
182 /* Data structure for managing a pool of pages. */
183 struct page_pool
184 {
185 /* Methods. */
186 void (*init_page_pool) (struct page_pool *pool);
187 void (*init_page) (uintptr_t page);
188 uintptr_t (*allocate_block_in_page) (size_t size, uintptr_t page);
189 void (*free_block_in_page) (uintptr_t block, uintptr_t page);
190
191 /* Maximum free space in a page of this pool. */
192 size_t page_capacity;
193
194 /* Page that provided the last successful allocation from this pool,
195 or 0. */
196 uintptr_t last_page;
197
198 /* Ordered set of managed pages, sorted according to free_space, in ascending
199 order. */
200 gl_oset_t /* <struct page_tree_element *> */ managed_pages;
201
202 /* A queue of pages which have a modified free_space but which have not been
203 updated in the managed_pages tree so far. */
204 #define UPDATE_QUEUE_SIZE 10
205 unsigned int update_queue_count; /* <= UPDATE_QUEUE_SIZE */
206 uintptr_t update_queue[UPDATE_QUEUE_SIZE];
207
208 /* A page that could be freed.
209 We don't free it immediately, so that on allocation/deallocation
210 pattern like
211 2x allocate, 2x free, 2x allocate, 2x free, 2x allocate, 2x free, ...
212 will not allocate and free a page so frequently. */
213 uintptr_t freeable_page;
214 };
215
216 /* Comparison function for managed_pages. */
217 static int
compare_pages_by_free_space(const void * elt1,const void * elt2)218 compare_pages_by_free_space (const void *elt1, const void *elt2)
219 {
220 struct page_tree_element *element1 = (struct page_tree_element *) elt1;
221 struct page_tree_element *element2 = (struct page_tree_element *) elt2;
222 int cmp = _GL_CMP (element1->free_space, element2->free_space);
223 if (unlikely (cmp == 0))
224 cmp = _GL_CMP (element1->page, element2->page);
225 return cmp;
226 }
227
228 /* Tests whether the free space in a tree element is greater or equal than the
229 given threshold. */
230 static bool
page_free_space_is_at_least(const void * elt,const void * threshold)231 page_free_space_is_at_least (const void *elt, const void *threshold)
232 {
233 struct page_tree_element *element = (struct page_tree_element *) elt;
234
235 return element->free_space >= (uintptr_t) threshold;
236 }
237
238 /* Updates the free space of a 'struct page_tree_element *'.
239 Only to be called through gl_oset_update! */
240 static void
set_free_space(const void * elt,void * action_data)241 set_free_space (const void *elt, void *action_data)
242 {
243 struct page_tree_element *element = (struct page_tree_element *) elt;
244
245 element->free_space = (pg_offset_t) (uintptr_t) action_data;
246 }
247
248 /* Executes the pending updates in the managed_pages tree. */
249 static void
flush_all_updates(struct page_pool * pool)250 flush_all_updates (struct page_pool *pool)
251 {
252 size_t count = pool->update_queue_count;
253 while (likely (count > 0))
254 {
255 --count;
256 uintptr_t page = pool->update_queue[count];
257 struct dissected_page_header *pageptr =
258 (struct dissected_page_header *) page;
259 struct page_tree_element *tree_element = pageptr->tree_element;
260 if (gl_oset_update (pool->managed_pages, tree_element,
261 set_free_space,
262 (void *) (uintptr_t) pageptr->free_space)
263 < 0)
264 /* A collision was found. This contradicts the definition of
265 compare_pages_by_free_space. */
266 abort ();
267 }
268 pool->update_queue_count = 0;
269 }
270
271 /* Adds a page to the update queue.
272 This function has to be called when the free_space of the page has
273 changed. */
274 static inline void
add_update(uintptr_t page,struct page_pool * pool)275 add_update (uintptr_t page, struct page_pool *pool)
276 {
277 size_t count = pool->update_queue_count;
278 size_t i;
279 for (i = 0; i < count; i++)
280 if (pool->update_queue[i] == page)
281 /* It's already in the queue. */
282 return;
283
284 /* Ensure there is room for adding one more page to the update queue. */
285 if (unlikely (count == UPDATE_QUEUE_SIZE))
286 flush_all_updates (pool);
287
288 /* Add it to the update queue. */
289 pool->update_queue[pool->update_queue_count++] = page;
290 }
291
292 /* Drops a page from the update queue. */
293 static inline void
drop_update(uintptr_t page,struct page_pool * pool)294 drop_update (uintptr_t page, struct page_pool *pool)
295 {
296 size_t count = pool->update_queue_count;
297 size_t i;
298 for (i = 0; i < count; i++)
299 if (pool->update_queue[i] == page)
300 {
301 /* It's in the queue. Remove it. */
302 for (i = i + 1; i < count; i++)
303 pool->update_queue[i - 1] = pool->update_queue[i];
304 pool->update_queue_count--;
305 return;
306 }
307 }
308
309 /* ============================== Small blocks ============================== */
310
311 #include "ssfmalloc-bitmap.h"
312
313 /* Maximum size of a small block.
314 Must be a power of 2. */
315 #define SMALL_BLOCK_MAX_SIZE (ALIGNMENT < 8 ? 32 * ALIGNMENT : 256)
316
317 /* Number of rows of ALIGNMENT bytes available in an empty page. */
318 static unsigned int small_block_page_num_bits;
319 /* Offset in the page where the memory blocks start.
320 A multiple of ALIGNMENT. */
321 static unsigned int small_block_page_blocks_start;
322 /* Number of uint32_t words in each of the two bitmaps. */
323 static unsigned int small_block_page_num_bitmap_words;
324
325 /* Header of a page of small blocks.
326 Lies at an address that is a multiple of PAGESIZE. */
327 struct small_page_header
328 {
329 struct dissected_page_header common;
330 /* Two bitmaps, each with small_block_page_num_bitmap_words. In each a bit
331 represents ALIGNMENT bytes.
332 - available_bitmap: bit set means available, bit clear means allocated.
333 - blockend_bitmap: bit set means the an allocated block ends here. */
334 uint32_t bitmap_words[FLEXIBLE_ARRAY_MEMBER];
335 };
336
337 static inline uint32_t *
small_block_page_available_bitmap(struct small_page_header * pageptr)338 small_block_page_available_bitmap (struct small_page_header *pageptr)
339 {
340 return &pageptr->bitmap_words[0];
341 }
342
343 static inline uint32_t *
small_block_page_blockend_bitmap(struct small_page_header * pageptr)344 small_block_page_blockend_bitmap (struct small_page_header *pageptr)
345 {
346 return &pageptr->bitmap_words[small_block_page_num_bitmap_words];
347 }
348
349 static void
init_small_block_page_pool(struct page_pool * pool)350 init_small_block_page_pool (struct page_pool *pool)
351 {
352 /* How many usable rows of ALIGNMENT bytes can we have?
353 Each takes ALIGNMENT bytes + 1/8 byte in each bitmap, so approximately
354 (ALIGNMENT + 1/4) bytes. */
355 unsigned int num_bits = (unsigned int) (4 * PAGESIZE) / (4 * ALIGNMENT + 1);
356 unsigned int num_bitmap_words;
357 unsigned int blocks_start;
358 /* Iterate until it converges. */
359 for (;;)
360 {
361 num_bitmap_words = (num_bits + 32 - 1) / 32;
362 blocks_start =
363 (FLEXSIZEOF (struct small_page_header, bitmap_words,
364 2 * num_bitmap_words * sizeof (uint32_t))
365 + ALIGNMENT - 1) & -ALIGNMENT;
366 unsigned int num_bits_r = (unsigned int) (PAGESIZE - blocks_start) / ALIGNMENT;
367 if (num_bits_r >= num_bits)
368 break;
369 num_bits = num_bits_r;
370 }
371
372 small_block_page_num_bits = num_bits;
373 small_block_page_num_bitmap_words = num_bitmap_words;
374 small_block_page_blocks_start = blocks_start;
375
376 pool->page_capacity = small_block_page_num_bits * ALIGNMENT;
377 }
378
379 static void
init_small_block_page(uintptr_t page)380 init_small_block_page (uintptr_t page)
381 {
382 struct small_page_header *pageptr = (struct small_page_header *) page;
383 pageptr->common.common.page_type = small_page_type;
384
385 /* Initialize available_bitmap. */
386 uint32_t *available_bitmap = small_block_page_available_bitmap (pageptr);
387 init_bitmap_all_bits_set (small_block_page_num_bitmap_words,
388 available_bitmap);
389 if ((small_block_page_num_bits % 32) != 0)
390 available_bitmap[small_block_page_num_bitmap_words - 1] =
391 (1U << (small_block_page_num_bits % 32)) - 1;
392
393 /* Initialize blockend_bitmap. */
394 init_bitmap_all_bits_clear (small_block_page_num_bitmap_words,
395 small_block_page_blockend_bitmap (pageptr));
396
397 pageptr->common.free_space = small_block_page_num_bits * ALIGNMENT;
398 }
399
400 /* Allocates a block of memory of size <= SMALL_BLOCK_MAX_SIZE,
401 aligned to ALIGNMENT bytes, from the given page.
402 Returns 0 upon failure. */
403 static uintptr_t
allocate_small_block_in_page(size_t size,uintptr_t page)404 allocate_small_block_in_page (size_t size, uintptr_t page)
405 {
406 struct small_page_header *pageptr = (struct small_page_header *) page;
407
408 /* glibc compatible. */
409 if (size == 0)
410 size = 1;
411
412 /* Number of consecutive bits to look for in the bitmap. */
413 size_t c = (size + ALIGNMENT - 1) / ALIGNMENT;
414
415 /* SMALL_BLOCK_MAX_SIZE has been chosen so that c <= 32. */
416 if (!(c > 0 && c <= 32))
417 abort ();
418
419 uint32_t *available_bitmap = small_block_page_available_bitmap (pageptr);
420 size_t k = find_first_packet_set (small_block_page_num_bitmap_words,
421 available_bitmap,
422 c);
423 if (unlikely (k == (size_t)(-1)))
424 /* Failed to find c consecutive available rows of ALIGNMENT bytes each. */
425 return 0;
426
427 uint32_t *blockend_bitmap = small_block_page_blockend_bitmap (pageptr);
428 size_t j = k / 32;
429 size_t i = k % 32;
430 if (i + c <= 32)
431 {
432 available_bitmap[j] &= ~(((2U << (c - 1)) - 1) << i);
433 blockend_bitmap[j] |= (1U << (i + c - 1));
434 }
435 else
436 {
437 available_bitmap[j] &= ~(-1U << i);
438 available_bitmap[j + 1] &= ~((1U << (i + c - 32)) - 1);
439 blockend_bitmap[j + 1] |= (1U << (i + c - 1 - 32));
440 }
441
442 pageptr->common.free_space -= c * ALIGNMENT;
443
444 return page + small_block_page_blocks_start + k * ALIGNMENT;
445 }
446
447 static void
free_small_block_in_page(uintptr_t block,uintptr_t page)448 free_small_block_in_page (uintptr_t block, uintptr_t page)
449 {
450 struct small_page_header *pageptr = (struct small_page_header *) page;
451
452 if (!(block >= page + small_block_page_blocks_start
453 && (block % ALIGNMENT) == 0))
454 /* Invalid argument. */
455 abort ();
456
457 uint32_t *available_bitmap = small_block_page_available_bitmap (pageptr);
458 uint32_t *blockend_bitmap = small_block_page_blockend_bitmap (pageptr);
459
460 /* The bit that corresponds to where the block starts. */
461 size_t k = (block - page - small_block_page_blocks_start) / ALIGNMENT;
462 /* The bit that corresponds to where the block ends. */
463 size_t ke = find_first_bit_set (small_block_page_num_bitmap_words,
464 blockend_bitmap,
465 k);
466 if (/* ke == (size_t)(-1) || */ ke >= k + 32)
467 /* Invalid argument or invalid state. */
468 abort ();
469
470 /* Number of consecutive bits to manipulate in the bitmap. */
471 size_t c = ke - k + 1;
472
473 size_t j = k / 32;
474 size_t i = k % 32;
475 if (i + c <= 32)
476 {
477 available_bitmap[j] |= (((2U << (c - 1)) - 1) << i);
478 blockend_bitmap[j] &= ~(1U << (i + c - 1));
479 }
480 else
481 {
482 available_bitmap[j] |= (-1U << i);
483 available_bitmap[j + 1] |= ((1U << (i + c - 32)) - 1);
484 blockend_bitmap[j + 1] &= ~(1U << (i + c - 1 - 32));
485 }
486
487 pageptr->common.free_space += c * ALIGNMENT;
488 }
489
490 /* Management of pages of small blocks. */
491 struct page_pool small_block_pages =
492 {
493 init_small_block_page_pool,
494 init_small_block_page,
495 allocate_small_block_in_page,
496 free_small_block_in_page
497 };
498
499 /* ============================== Medium blocks ============================= */
500
501 /* A range of memory in a page.
502 It covers the address range [page+start, page+end).
503 start <= end. */
504 struct memory_range
505 {
506 pg_offset_t start;
507 pg_offset_t end;
508 };
509
510 /* Header of a page of medium blocks.
511 Lies at an address that is a multiple of PAGESIZE. */
512 struct medium_page_header
513 {
514 struct dissected_page_header common;
515 /* If n blocks are allocated, there are n+1 gaps before, between, and
516 after them. Keep them in an array, sorted in ascending order. */
517 unsigned int num_gaps; /* > 0 */
518 struct memory_range gaps[FLEXIBLE_ARRAY_MEMBER /* PAGESIZE / SMALL_BLOCK_MAX_SIZE + 1 */];
519 };
520
521 #define MEDIUM_BLOCKS_PAGE_MAX_GAPS \
522 (PAGESIZE / SMALL_BLOCK_MAX_SIZE + 1)
523 #define MEDIUM_BLOCKS_PAGE_FIRST_GAP_START \
524 ((FLEXSIZEOF (struct medium_page_header, gaps, \
525 MEDIUM_BLOCKS_PAGE_MAX_GAPS * sizeof (struct memory_range)) \
526 + ALIGNMENT - 1) & -ALIGNMENT)
527 #define MEDIUM_BLOCKS_PAGE_LAST_GAP_END \
528 PAGESIZE
529 #define MEDIUM_BLOCKS_PAGE_CAPACITY \
530 (MEDIUM_BLOCKS_PAGE_LAST_GAP_END - MEDIUM_BLOCKS_PAGE_FIRST_GAP_START)
531
532 static void
init_medium_block_page_pool(struct page_pool * pool)533 init_medium_block_page_pool (struct page_pool *pool)
534 {
535 pool->page_capacity = MEDIUM_BLOCKS_PAGE_CAPACITY;
536 }
537
538 static void
init_medium_block_page(uintptr_t page)539 init_medium_block_page (uintptr_t page)
540 {
541 struct medium_page_header *pageptr = (struct medium_page_header *) page;
542 pageptr->common.common.page_type = medium_page_type;
543 pageptr->num_gaps = 1;
544 pageptr->gaps[0].start = MEDIUM_BLOCKS_PAGE_FIRST_GAP_START;
545 pageptr->gaps[0].end = MEDIUM_BLOCKS_PAGE_LAST_GAP_END;
546 pageptr->common.free_space = MEDIUM_BLOCKS_PAGE_CAPACITY;
547 }
548
549 /* Allocates a block of memory of size > SMALL_BLOCK_MAX_SIZE,
550 aligned to ALIGNMENT bytes, from the given page.
551 Returns 0 upon failure. */
552 static uintptr_t
allocate_medium_block_in_page(size_t size,uintptr_t page)553 allocate_medium_block_in_page (size_t size, uintptr_t page)
554 {
555 struct medium_page_header *pageptr = (struct medium_page_header *) page;
556
557 /* Walk through the gaps and remember the smallest gap of at least
558 the given size. */
559 size_t best_i = (size_t)(-1);
560 size_t best_length = (size_t)(-1);
561 size_t num_gaps = pageptr->num_gaps;
562 size_t i;
563 for (i = 0; i < num_gaps; i++)
564 {
565 size_t length = pageptr->gaps[i].end - pageptr->gaps[i].start;
566 if (length >= size)
567 {
568 /* Found a gap of sufficient size. */
569 if (length < best_length)
570 {
571 best_i = i;
572 best_length = length;
573 }
574 }
575 }
576 if (unlikely (best_i == (size_t)(-1)))
577 /* Failed to find a gap of sufficient size. */
578 return 0;
579
580 size_t aligned_size = (size + ALIGNMENT - 1) & -ALIGNMENT;
581
582 if (pageptr->common.free_space < aligned_size)
583 /* Invalid state: Less free space than expected. */
584 abort ();
585
586 /* Split the gap, leaving an empty gap and a remaining gap. */
587 for (i = num_gaps - 1; ; i--)
588 {
589 pageptr->gaps[i + 1] = pageptr->gaps[i];
590 if (i == best_i)
591 break;
592 }
593 size_t result = pageptr->gaps[best_i].start;
594 pageptr->gaps[best_i].end = result;
595 pageptr->gaps[best_i + 1].start = result + aligned_size;
596 pageptr->num_gaps = num_gaps + 1;
597 if (pageptr->num_gaps > PAGESIZE / SMALL_BLOCK_MAX_SIZE + 1)
598 /* Invalid state: More gaps than expected. */
599 abort ();
600
601 pageptr->common.free_space -= aligned_size;
602
603 return page + result;
604 }
605
606 static void
free_medium_block_in_page(uintptr_t block,uintptr_t page)607 free_medium_block_in_page (uintptr_t block, uintptr_t page)
608 {
609 struct medium_page_header *pageptr = (struct medium_page_header *) page;
610 size_t offset = block - page;
611
612 /* Search for the gap that ends where this block begins.
613 We can ignore the last gap here, since it ends where the page ends. */
614 struct memory_range *gaps = pageptr->gaps;
615 size_t lo = 0;
616 size_t hi = pageptr->num_gaps - 1;
617 size_t index;
618 while (lo < hi)
619 {
620 /* Invariant:
621 for i < lo, gaps[i].end < offset,
622 for i >= hi, gaps[i].end > offset. */
623 size_t mid = (hi + lo) >> 1; /* >= lo, < hi */
624 if (offset > gaps[mid].end)
625 lo = mid + 1;
626 else if (offset < gaps[mid].end)
627 hi = mid;
628 else
629 {
630 /* Found it: offset == gaps[mid].end. */
631 index = mid;
632 goto found;
633 }
634 }
635 /* Invalid argument: block is not the start of a currently allocated
636 block. */
637 abort ();
638
639 found:
640 /* Here 0 <= index < pageptr->num_gaps - 1.
641 Combine the gaps index and index+1. */
642 pageptr->common.free_space += gaps[index + 1].start - gaps[index].end;
643 if (pageptr->common.free_space < gaps[index + 1].start - gaps[index].end)
644 /* Wrap around. */
645 abort ();
646
647 gaps[index].end = gaps[index + 1].end;
648
649 size_t num_gaps = pageptr->num_gaps - 1;
650 size_t i;
651 for (i = index + 1; i < num_gaps; i++)
652 gaps[i] = gaps[i + 1];
653 pageptr->num_gaps = num_gaps;
654 }
655
656 /* Management of pages of medium blocks. */
657 struct page_pool medium_block_pages =
658 {
659 init_medium_block_page_pool,
660 init_medium_block_page,
661 allocate_medium_block_in_page,
662 free_medium_block_in_page
663 };
664
665 /* ==================== Pages of small and medium blocks ==================== */
666
667 /* Allocates a block of memory from the given pool, aligned to ALIGNMENT bytes.
668 Returns 0 upon failure. */
669 static inline uintptr_t
allocate_block_from_pool(size_t size,struct page_pool * pool)670 allocate_block_from_pool (size_t size, struct page_pool *pool)
671 {
672 uintptr_t page;
673
674 /* Try in the last used page first. */
675 page = pool->last_page;
676 if (likely (page != 0))
677 {
678 uintptr_t block = pool->allocate_block_in_page (size, page);
679 if (likely (block != 0))
680 {
681 add_update (page, pool);
682 return block;
683 }
684 }
685
686 /* Ensure that the pool and its managed_pages is initialized. */
687 if (unlikely (pool->managed_pages == NULL))
688 {
689 pool->managed_pages =
690 gl_oset_nx_create_empty (GL_RBTREE_OSET, compare_pages_by_free_space, NULL);
691 if (unlikely (pool->managed_pages == NULL))
692 /* Could not allocate the managed_pages. */
693 return 0;
694 pool->init_page_pool (pool);
695 }
696
697 /* Ensure that managed_pages is up-to-date. */
698 flush_all_updates (pool);
699
700 /* Try in the other managed_pages. */
701 {
702 gl_oset_iterator_t iter =
703 gl_oset_iterator_atleast (pool->managed_pages,
704 page_free_space_is_at_least,
705 (void *) (uintptr_t) size);
706 const void *elt;
707 while (gl_oset_iterator_next (&iter, &elt))
708 {
709 struct page_tree_element *element = (struct page_tree_element *) elt;
710 page = element->page;
711 /* No need to try the last used page again. */
712 if (likely (page != pool->last_page))
713 {
714 uintptr_t block = pool->allocate_block_in_page (size, page);
715 if (likely (block != 0))
716 {
717 gl_oset_iterator_free (&iter);
718 add_update (page, pool);
719 pool->last_page = page;
720 return block;
721 }
722 }
723 }
724 gl_oset_iterator_free (&iter);
725 }
726
727 /* If we have a freeable page ready for reuse, use it. */
728 if (pool->freeable_page != 0)
729 {
730 page = pool->freeable_page;
731 pool->init_page (page);
732 struct page_tree_element *element =
733 (struct page_tree_element *) malloc (sizeof (struct page_tree_element));
734 if (unlikely (element == NULL))
735 {
736 /* Could not allocate the tree element. */
737 pool->last_page = 0;
738 return 0;
739 }
740 element->page = page;
741 element->free_space = ((struct dissected_page_header *) page)->free_space;
742 if (unlikely (gl_oset_nx_add (pool->managed_pages, element) < 0))
743 {
744 /* Could not allocate the tree node. */
745 free (element);
746 pool->last_page = 0;
747 return 0;
748 }
749 ((struct dissected_page_header *) page)->tree_element = element;
750 pool->freeable_page = 0;
751
752 uintptr_t block = pool->allocate_block_in_page (size, page);
753 if (block == 0)
754 /* If the size is too large for an empty page, this function should not
755 have been invoked. */
756 abort ();
757 add_update (page, pool);
758 pool->last_page = page;
759 return block;
760 }
761
762 /* Allocate a fresh page. */
763 page = ALLOC_PAGES (PAGESIZE);
764 if (unlikely (page == 0))
765 {
766 /* Failed. */
767 pool->last_page = 0;
768 return 0;
769 }
770 if ((page & (PAGESIZE - 1)) != 0)
771 /* ALLOC_PAGES's result is not aligned as expected. */
772 abort ();
773
774 pool->init_page (page);
775 struct page_tree_element *element =
776 (struct page_tree_element *) malloc (sizeof (struct page_tree_element));
777 if (unlikely (element == NULL))
778 {
779 /* Could not allocate the tree element. */
780 FREE_PAGES (page, PAGESIZE);
781 pool->last_page = 0;
782 return 0;
783 }
784 element->page = page;
785 element->free_space = ((struct dissected_page_header *) page)->free_space;
786 if (unlikely (gl_oset_nx_add (pool->managed_pages, element) < 0))
787 {
788 /* Could not allocate the tree node. */
789 free (element);
790 FREE_PAGES (page, PAGESIZE);
791 pool->last_page = 0;
792 return 0;
793 }
794 ((struct dissected_page_header *) page)->tree_element = element;
795
796 uintptr_t block = pool->allocate_block_in_page (size, page);
797 if (block == 0)
798 /* If the size is too large for an empty page, this function should not
799 have been invoked. */
800 abort ();
801 add_update (page, pool);
802 pool->last_page = page;
803 return block;
804 }
805
806 static void
free_block_from_pool(uintptr_t block,uintptr_t page,struct page_pool * pool)807 free_block_from_pool (uintptr_t block, uintptr_t page, struct page_pool *pool)
808 {
809 if (pool->page_capacity == 0)
810 /* Invalid argument: The block is not valid, since the pool has not yet
811 been initialized. */
812 abort ();
813
814 pool->free_block_in_page (block, page);
815
816 struct dissected_page_header *pageptr = (struct dissected_page_header *) page;
817 if (likely (pageptr->free_space != pool->page_capacity))
818 {
819 /* The page is not entirely free. */
820 add_update (page, pool);
821 }
822 else
823 {
824 /* The page is now entirely free. */
825 /* Remove its tree element and free it. */
826 struct page_tree_element *element = pageptr->tree_element;
827 if (!gl_oset_remove (pool->managed_pages, element))
828 /* Invalid state: The element is not in the managed_pages. */
829 abort ();
830 free (element);
831
832 if (pool->last_page == page)
833 pool->last_page = 0;
834
835 drop_update (page, pool);
836
837 /* If we would now have two freeable pages, free the old one. */
838 if (pool->freeable_page != 0)
839 FREE_PAGES (pool->freeable_page, PAGESIZE);
840
841 /* Don't free the page now, but later. */
842 pool->freeable_page = page;
843 }
844 }
845
846 /* Lock that protects the management of small and medium blocks from
847 simultaneous access from multiple threads. */
848 gl_lock_define_initialized(static, ssfmalloc_lock)
849
850 /* ============================== Large blocks ============================== */
851
852 /* Header of a page sequence for a large block.
853 Lies at an address that is a multiple of PAGESIZE. */
854 struct large_block_header
855 {
856 #if PAGE_RESERVED_HEADER_SIZE > 0
857 void * reserved[PAGE_RESERVED_HEADER_SIZE / sizeof (void *)];
858 #endif
859 unsigned char page_type; /* large_page_type */
860 };
861
862 /* Information about a large block.
863 Ends at an address that is a multiple of ALIGNMENT. */
864 struct large_block_caption
865 {
866 size_t pages_size; /* A multiple of PAGESIZE. */
867 };
868
869 /* Size of large block page header, gap, and caption. */
870 #define LARGE_BLOCK_OFFSET \
871 ((sizeof (struct large_block_header) + sizeof (struct large_block_caption) \
872 + ALIGNMENT - 1) & -ALIGNMENT)
873
874 /* =========================== Exported functions =========================== */
875
876 /* Allocates a block of memory, aligned to ALIGNMENT bytes.
877 Returns 0 upon failure. */
878 static uintptr_t
allocate_block(size_t size)879 allocate_block (size_t size)
880 {
881 uintptr_t block;
882
883 if (unlikely (size > MEDIUM_BLOCKS_PAGE_CAPACITY))
884 {
885 /* Allocate a large block. */
886 size_t pages_size = (size + LARGE_BLOCK_OFFSET + PAGESIZE - 1) & -PAGESIZE;
887 uintptr_t pages = ALLOC_PAGES (pages_size);
888 if (unlikely (pages == 0))
889 /* Failed. */
890 return 0;
891 if ((pages & (PAGESIZE - 1)) != 0)
892 /* ALLOC_PAGES's result is not aligned as expected. */
893 abort ();
894 ((struct any_page_header *) pages)->page_type = large_page_type;
895 block = pages + LARGE_BLOCK_OFFSET;
896 ((struct large_block_caption *) block)[-1].pages_size = pages_size;
897 }
898 else
899 {
900 bool mt = gl_multithreaded ();
901 if (mt) gl_lock_lock (ssfmalloc_lock);
902 struct page_pool *pool =
903 (size <= SMALL_BLOCK_MAX_SIZE ? &small_block_pages : &medium_block_pages);
904 block = allocate_block_from_pool (size, pool);
905 if (mt) gl_lock_unlock (ssfmalloc_lock);
906 }
907 return block;
908 }
909
910 /* Frees a block of memory, returned by allocate_block. */
911 static void
free_block(uintptr_t block)912 free_block (uintptr_t block)
913 {
914 if (block == 0 || (block % ALIGNMENT) != 0)
915 /* Invalid argument. */
916 abort ();
917 uintptr_t pages = block & -PAGESIZE;
918 unsigned char type = ((struct any_page_header *) pages)->page_type;
919 if (unlikely (type == large_page_type))
920 {
921 if (block != pages + LARGE_BLOCK_OFFSET)
922 /* Invalid argument. */
923 abort ();
924 size_t pages_size = ((struct large_block_caption *) block)[-1].pages_size;
925 if ((pages_size & (PAGESIZE - 1)) != 0)
926 /* Invalid memory state: pages_size not as expected. */
927 abort ();
928 FREE_PAGES (pages, pages_size);
929 }
930 else
931 {
932 bool mt = gl_multithreaded ();
933 if (mt) gl_lock_lock (ssfmalloc_lock);
934 struct page_pool *pool;
935 if (type == small_page_type)
936 pool = &small_block_pages;
937 else if (type == medium_page_type)
938 pool = &medium_block_pages;
939 else
940 /* Invalid memory state: type not as expected. */
941 abort ();
942 free_block_from_pool (block, pages, pool);
943 if (mt) gl_lock_unlock (ssfmalloc_lock);
944 }
945 }
946