]> git.saurik.com Git - apple/libdispatch.git/blob - src/allocator.c
libdispatch-913.30.4.tar.gz
[apple/libdispatch.git] / src / allocator.c
1 /*
2 * Copyright (c) 2012-2013 Apple Inc. All rights reserved.
3 *
4 * @APPLE_APACHE_LICENSE_HEADER_START@
5 *
6 * Licensed under the Apache License, Version 2.0 (the "License");
7 * you may not use this file except in compliance with the License.
8 * You may obtain a copy of the License at
9 *
10 * http://www.apache.org/licenses/LICENSE-2.0
11 *
12 * Unless required by applicable law or agreed to in writing, software
13 * distributed under the License is distributed on an "AS IS" BASIS,
14 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15 * See the License for the specific language governing permissions and
16 * limitations under the License.
17 *
18 * @APPLE_APACHE_LICENSE_HEADER_END@
19 */
20
21 #include "internal.h"
22 #include "allocator_internal.h"
23
24 #if DISPATCH_ALLOCATOR
25
26 #ifndef VM_MEMORY_LIBDISPATCH
27 #define VM_MEMORY_LIBDISPATCH 74
28 #endif
29
30 // _dispatch_main_heap is is the first heap in the linked list, where searches
31 // always begin.
32 //
33 // _dispatch_main_heap, and dh_next, are read normally but only written (in
34 // try_create_heap) by cmpxchg. They start life at 0, and are only written
35 // once to non-zero. They are not marked volatile. There is a small risk that
36 // some thread may see a stale 0 value and enter try_create_heap. It will
37 // waste some time in an allocate syscall, but eventually it will try to
38 // cmpxchg, expecting to overwrite 0 with an address. This will fail
39 // (because another thread already did this), the thread will deallocate the
40 // unused allocated memory, and continue with the new value.
41 //
42 // If something goes wrong here, the symptom would be a NULL dereference
43 // in alloc_continuation_from_heap or _magazine when derefing the magazine ptr.
44 static dispatch_heap_t _dispatch_main_heap;
45
46 DISPATCH_ALWAYS_INLINE
47 static void
48 set_last_found_page(bitmap_t *val)
49 {
50 dispatch_assert(_dispatch_main_heap);
51 unsigned int cpu = _dispatch_cpu_number();
52 _dispatch_main_heap[cpu].header.last_found_page = val;
53 }
54
55 DISPATCH_ALWAYS_INLINE
56 static bitmap_t *
57 last_found_page(void)
58 {
59 dispatch_assert(_dispatch_main_heap);
60 unsigned int cpu = _dispatch_cpu_number();
61 return _dispatch_main_heap[cpu].header.last_found_page;
62 }
63
64 #pragma mark -
65 #pragma mark dispatch_alloc_bitmaps
66
67 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
68 static bitmap_t *
69 supermap_address(struct dispatch_magazine_s *magazine, unsigned int supermap)
70 {
71 return &magazine->supermaps[supermap];
72 }
73
74 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
75 static bitmap_t *
76 bitmap_address(struct dispatch_magazine_s *magazine, unsigned int supermap,
77 unsigned int map)
78 {
79 return &magazine->maps[supermap][map];
80 }
81
82 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
83 static dispatch_continuation_t
84 continuation_address(struct dispatch_magazine_s *magazine,
85 unsigned int supermap, unsigned int map, unsigned int index)
86 {
87 #if DISPATCH_DEBUG
88 dispatch_assert(supermap < SUPERMAPS_PER_MAGAZINE);
89 dispatch_assert(map < BITMAPS_PER_SUPERMAP);
90 dispatch_assert(index < CONTINUATIONS_PER_BITMAP);
91 #endif
92 return (dispatch_continuation_t)&magazine->conts[supermap][map][index];
93 }
94
95 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
96 static struct dispatch_magazine_s *
97 magazine_for_continuation(dispatch_continuation_t c)
98 {
99 return (struct dispatch_magazine_s *)((uintptr_t)c & MAGAZINE_MASK);
100 }
101
102 DISPATCH_ALWAYS_INLINE_NDEBUG
103 static void
104 get_cont_and_indices_for_bitmap_and_index(bitmap_t *bitmap,
105 unsigned int index, dispatch_continuation_t *continuation_out,
106 bitmap_t **supermap_out, unsigned int *bitmap_index_out)
107 {
108 // m_for_c wants a continuation not a bitmap, but it works because it
109 // just masks off the bottom bits of the address.
110 struct dispatch_magazine_s *m = magazine_for_continuation((void *)bitmap);
111 unsigned int mindex = (unsigned int)(bitmap - m->maps[0]);
112 unsigned int bindex = mindex % BITMAPS_PER_SUPERMAP;
113 unsigned int sindex = mindex / BITMAPS_PER_SUPERMAP;
114 dispatch_assert(&m->maps[sindex][bindex] == bitmap);
115 if (fastpath(continuation_out)) {
116 *continuation_out = continuation_address(m, sindex, bindex, index);
117 }
118 if (fastpath(supermap_out)) *supermap_out = supermap_address(m, sindex);
119 if (fastpath(bitmap_index_out)) *bitmap_index_out = bindex;
120 }
121
122 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
123 static bool
124 continuation_is_in_first_page(dispatch_continuation_t c)
125 {
126 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
127 // (the base of c's magazine == the base of c's page)
128 // => c is in first page of magazine
129 return (((uintptr_t)c & MAGAZINE_MASK) ==
130 ((uintptr_t)c & ~(uintptr_t)DISPATCH_ALLOCATOR_PAGE_MASK));
131 #else
132 (void)c;
133 return false;
134 #endif
135 }
136
137 DISPATCH_ALWAYS_INLINE_NDEBUG
138 static void
139 get_maps_and_indices_for_continuation(dispatch_continuation_t c,
140 bitmap_t **supermap_out, unsigned int *bitmap_index_out,
141 bitmap_t **bitmap_out, unsigned int *index_out)
142 {
143 unsigned int cindex, sindex, index, mindex;
144 padded_continuation *p = (padded_continuation *)c;
145 struct dispatch_magazine_s *m = magazine_for_continuation(c);
146 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
147 if (fastpath(continuation_is_in_first_page(c))) {
148 cindex = (unsigned int)(p - m->fp_conts);
149 index = cindex % CONTINUATIONS_PER_BITMAP;
150 mindex = cindex / CONTINUATIONS_PER_BITMAP;
151 if (fastpath(supermap_out)) *supermap_out = NULL;
152 if (fastpath(bitmap_index_out)) *bitmap_index_out = mindex;
153 if (fastpath(bitmap_out)) *bitmap_out = &m->fp_maps[mindex];
154 if (fastpath(index_out)) *index_out = index;
155 return;
156 }
157 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
158 cindex = (unsigned int)(p - (padded_continuation *)m->conts);
159 sindex = cindex / (BITMAPS_PER_SUPERMAP * CONTINUATIONS_PER_BITMAP);
160 mindex = (cindex / CONTINUATIONS_PER_BITMAP) % BITMAPS_PER_SUPERMAP;
161 index = cindex % CONTINUATIONS_PER_BITMAP;
162 if (fastpath(supermap_out)) *supermap_out = &m->supermaps[sindex];
163 if (fastpath(bitmap_index_out)) *bitmap_index_out = mindex;
164 if (fastpath(bitmap_out)) *bitmap_out = &m->maps[sindex][mindex];
165 if (fastpath(index_out)) *index_out = index;
166 }
167
168 // Base address of page, or NULL if this page shouldn't be madvise()d
169 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
170 static void *
171 madvisable_page_base_for_continuation(dispatch_continuation_t c)
172 {
173 if (fastpath(continuation_is_in_first_page(c))) {
174 return NULL;
175 }
176 void *page_base = (void *)((uintptr_t)c &
177 ~(uintptr_t)DISPATCH_ALLOCATOR_PAGE_MASK);
178 #if DISPATCH_DEBUG
179 struct dispatch_magazine_s *m = magazine_for_continuation(c);
180 if (slowpath(page_base < (void *)&m->conts)) {
181 DISPATCH_INTERNAL_CRASH(page_base, "madvisable continuation too low");
182 }
183 if (slowpath(page_base > (void *)&m->conts[SUPERMAPS_PER_MAGAZINE-1]
184 [BITMAPS_PER_SUPERMAP-1][CONTINUATIONS_PER_BITMAP-1])) {
185 DISPATCH_INTERNAL_CRASH(page_base, "madvisable continuation too high");
186 }
187 #endif
188 return page_base;
189 }
190
191 // Bitmap that controls the first few continuations in the same page as
192 // the continuations controlled by the passed bitmap. Undefined results if the
193 // passed bitmap controls continuations in the first page.
194 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
195 static bitmap_t *
196 first_bitmap_in_same_page(bitmap_t *b)
197 {
198 #if DISPATCH_DEBUG
199 struct dispatch_magazine_s *m;
200 m = magazine_for_continuation((void*)b);
201 dispatch_assert(b >= &m->maps[0][0]);
202 dispatch_assert(b < &m->maps[SUPERMAPS_PER_MAGAZINE]
203 [BITMAPS_PER_SUPERMAP]);
204 #endif
205 const uintptr_t PAGE_BITMAP_MASK = (BITMAPS_PER_PAGE *
206 BYTES_PER_BITMAP) - 1;
207 return (bitmap_t *)((uintptr_t)b & ~PAGE_BITMAP_MASK);
208 }
209
210 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
211 static bool
212 bitmap_is_full(bitmap_t bits)
213 {
214 return (bits == BITMAP_ALL_ONES);
215 }
216
217 #define NO_BITS_WERE_UNSET (UINT_MAX)
218
219 // max_index is the 0-based position of the most significant bit that is
220 // allowed to be set.
221 DISPATCH_ALWAYS_INLINE_NDEBUG
222 static unsigned int
223 bitmap_set_first_unset_bit_upto_index(volatile bitmap_t *bitmap,
224 unsigned int max_index)
225 {
226 // No barriers needed in acquire path: the just-allocated
227 // continuation is "uninitialized", so the caller shouldn't
228 // load from it before storing, so we don't need to guard
229 // against reordering those loads.
230 dispatch_assert(sizeof(*bitmap) == sizeof(unsigned long));
231 return os_atomic_set_first_bit(bitmap, max_index);
232 }
233
234 DISPATCH_ALWAYS_INLINE
235 static unsigned int
236 bitmap_set_first_unset_bit(volatile bitmap_t *bitmap)
237 {
238 return bitmap_set_first_unset_bit_upto_index(bitmap, UINT_MAX);
239 }
240
241 #define CLEAR_EXCLUSIVELY true
242 #define CLEAR_NONEXCLUSIVELY false
243
244 // Return true if this bit was the last in the bitmap, and it is now all zeroes
245 DISPATCH_ALWAYS_INLINE_NDEBUG
246 static bool
247 bitmap_clear_bit(volatile bitmap_t *bitmap, unsigned int index,
248 bool exclusively)
249 {
250 #if DISPATCH_DEBUG
251 dispatch_assert(index < CONTINUATIONS_PER_BITMAP);
252 #endif
253 const bitmap_t mask = BITMAP_C(1) << index;
254 bitmap_t b;
255
256 if (exclusively == CLEAR_EXCLUSIVELY) {
257 if (slowpath((*bitmap & mask) == 0)) {
258 DISPATCH_CLIENT_CRASH(*bitmap,
259 "Corruption: failed to clear bit exclusively");
260 }
261 }
262
263 // and-and-fetch
264 b = os_atomic_and(bitmap, ~mask, release);
265 return b == 0;
266 }
267
268 DISPATCH_ALWAYS_INLINE_NDEBUG
269 static void
270 mark_bitmap_as_full_if_still_full(volatile bitmap_t *supermap,
271 unsigned int bitmap_index, volatile bitmap_t *bitmap)
272 {
273 #if DISPATCH_DEBUG
274 dispatch_assert(bitmap_index < BITMAPS_PER_SUPERMAP);
275 #endif
276 const bitmap_t mask = BITMAP_C(1) << bitmap_index;
277 bitmap_t s, s_new;
278
279 // No barriers because supermaps are only advisory, they
280 // don't protect access to other memory.
281 os_atomic_rmw_loop(supermap, s, s_new, relaxed, {
282 if (!bitmap_is_full(*bitmap)) {
283 os_atomic_rmw_loop_give_up(return);
284 }
285 s_new = s | mask;
286 });
287 }
288
289 #pragma mark -
290 #pragma mark dispatch_alloc_continuation_alloc
291
292 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
293 DISPATCH_ALWAYS_INLINE_NDEBUG
294 static dispatch_continuation_t
295 alloc_continuation_from_first_page(struct dispatch_magazine_s *magazine)
296 {
297 unsigned int i, index, continuation_index;
298
299 // TODO: unroll if this is hot?
300 for (i = 0; i < FULL_BITMAPS_IN_FIRST_PAGE; i++) {
301 index = bitmap_set_first_unset_bit(&magazine->fp_maps[i]);
302 if (fastpath(index != NO_BITS_WERE_UNSET)) goto found;
303 }
304 if (REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE) {
305 index = bitmap_set_first_unset_bit_upto_index(&magazine->fp_maps[i],
306 REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE - 1);
307 if (fastpath(index != NO_BITS_WERE_UNSET)) goto found;
308 }
309 return NULL;
310
311 found:
312 continuation_index = (i * CONTINUATIONS_PER_BITMAP) + index;
313 return (dispatch_continuation_t)&magazine->fp_conts[continuation_index];
314 }
315 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
316
317 DISPATCH_ALWAYS_INLINE_NDEBUG
318 static dispatch_continuation_t
319 alloc_continuation_from_magazine(struct dispatch_magazine_s *magazine)
320 {
321 unsigned int s, b, index;
322
323 for (s = 0; s < SUPERMAPS_PER_MAGAZINE; s++) {
324 volatile bitmap_t *supermap = supermap_address(magazine, s);
325 if (bitmap_is_full(*supermap)) {
326 continue;
327 }
328 for (b = 0; b < BITMAPS_PER_SUPERMAP; b++) {
329 volatile bitmap_t *bitmap = bitmap_address(magazine, s, b);
330 index = bitmap_set_first_unset_bit(bitmap);
331 if (index != NO_BITS_WERE_UNSET) {
332 set_last_found_page(
333 first_bitmap_in_same_page((bitmap_t *)bitmap));
334 mark_bitmap_as_full_if_still_full(supermap, b, bitmap);
335 return continuation_address(magazine, s, b, index);
336 }
337 }
338 }
339 return NULL;
340 }
341
342 DISPATCH_NOINLINE
343 static void
344 _dispatch_alloc_try_create_heap(dispatch_heap_t *heap_ptr)
345 {
346 #if HAVE_MACH
347 kern_return_t kr;
348 mach_vm_size_t vm_size = MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE;
349 mach_vm_offset_t vm_mask = ~MAGAZINE_MASK;
350 mach_vm_address_t vm_addr = vm_page_size;
351 while (slowpath(kr = mach_vm_map(mach_task_self(), &vm_addr, vm_size,
352 vm_mask, VM_FLAGS_ANYWHERE | VM_MAKE_TAG(VM_MEMORY_LIBDISPATCH),
353 MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_ALL,
354 VM_INHERIT_DEFAULT))) {
355 if (kr != KERN_NO_SPACE) {
356 DISPATCH_CLIENT_CRASH(kr, "Could not allocate heap");
357 }
358 _dispatch_temporary_resource_shortage();
359 vm_addr = vm_page_size;
360 }
361 uintptr_t aligned_region = (uintptr_t)vm_addr;
362 #else // HAVE_MACH
363 const size_t region_sz = (1 + MAGAZINES_PER_HEAP) * BYTES_PER_MAGAZINE;
364 void *region_p;
365 while (!dispatch_assume((region_p = mmap(NULL, region_sz,
366 PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE,
367 VM_MAKE_TAG(VM_MEMORY_LIBDISPATCH), 0)) != MAP_FAILED)) {
368 _dispatch_temporary_resource_shortage();
369 }
370 uintptr_t region = (uintptr_t)region_p;
371 uintptr_t region_end = region + region_sz;
372 uintptr_t aligned_region, aligned_region_end;
373 uintptr_t bottom_slop_len, top_slop_len;
374 // Realign if needed; find the slop at top/bottom to unmap
375 if ((region & ~(MAGAZINE_MASK)) == 0) {
376 bottom_slop_len = 0;
377 aligned_region = region;
378 aligned_region_end = region_end - BYTES_PER_MAGAZINE;
379 top_slop_len = BYTES_PER_MAGAZINE;
380 } else {
381 aligned_region = (region & MAGAZINE_MASK) + BYTES_PER_MAGAZINE;
382 aligned_region_end = aligned_region +
383 (MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE);
384 bottom_slop_len = aligned_region - region;
385 top_slop_len = BYTES_PER_MAGAZINE - bottom_slop_len;
386 }
387 #if DISPATCH_DEBUG
388 // Double-check our math.
389 dispatch_assert(aligned_region % DISPATCH_ALLOCATOR_PAGE_SIZE == 0);
390 dispatch_assert(aligned_region % vm_kernel_page_size == 0);
391 dispatch_assert(aligned_region_end % DISPATCH_ALLOCATOR_PAGE_SIZE == 0);
392 dispatch_assert(aligned_region_end % vm_kernel_page_size == 0);
393 dispatch_assert(aligned_region_end > aligned_region);
394 dispatch_assert(top_slop_len % DISPATCH_ALLOCATOR_PAGE_SIZE == 0);
395 dispatch_assert(bottom_slop_len % DISPATCH_ALLOCATOR_PAGE_SIZE == 0);
396 dispatch_assert(aligned_region_end + top_slop_len == region_end);
397 dispatch_assert(region + bottom_slop_len == aligned_region);
398 dispatch_assert(region_sz == bottom_slop_len + top_slop_len +
399 MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE);
400 if (bottom_slop_len) {
401 (void)dispatch_assume_zero(mprotect((void *)region, bottom_slop_len,
402 PROT_NONE));
403 }
404 if (top_slop_len) {
405 (void)dispatch_assume_zero(mprotect((void *)aligned_region_end,
406 top_slop_len, PROT_NONE));
407 }
408 #else
409 if (bottom_slop_len) {
410 (void)dispatch_assume_zero(munmap((void *)region, bottom_slop_len));
411 }
412 if (top_slop_len) {
413 (void)dispatch_assume_zero(munmap((void *)aligned_region_end,
414 top_slop_len));
415 }
416 #endif // DISPATCH_DEBUG
417 #endif // HAVE_MACH
418
419 if (!os_atomic_cmpxchg(heap_ptr, NULL, (void *)aligned_region,
420 relaxed)) {
421 // If we lost the race to link in the new region, unmap the whole thing.
422 #if DISPATCH_DEBUG
423 (void)dispatch_assume_zero(mprotect((void *)aligned_region,
424 MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE, PROT_NONE));
425 #else
426 (void)dispatch_assume_zero(munmap((void *)aligned_region,
427 MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE));
428 #endif
429 }
430 }
431
432 DISPATCH_NOINLINE
433 static dispatch_continuation_t
434 _dispatch_alloc_continuation_from_heap(dispatch_heap_t heap)
435 {
436 dispatch_continuation_t cont;
437
438 unsigned int cpu_number = _dispatch_cpu_number();
439 #ifdef DISPATCH_DEBUG
440 dispatch_assert(cpu_number < NUM_CPU);
441 #endif
442
443 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
444 // First try the continuations in the first page for this CPU
445 cont = alloc_continuation_from_first_page(&(heap[cpu_number]));
446 if (fastpath(cont)) {
447 return cont;
448 }
449 #endif
450 // Next, try the rest of the magazine for this CPU
451 cont = alloc_continuation_from_magazine(&(heap[cpu_number]));
452 return cont;
453 }
454
455 DISPATCH_NOINLINE
456 static dispatch_continuation_t
457 _dispatch_alloc_continuation_from_heap_slow(void)
458 {
459 dispatch_heap_t *heap = &_dispatch_main_heap;
460 dispatch_continuation_t cont;
461
462 for (;;) {
463 if (!fastpath(*heap)) {
464 _dispatch_alloc_try_create_heap(heap);
465 }
466 cont = _dispatch_alloc_continuation_from_heap(*heap);
467 if (fastpath(cont)) {
468 return cont;
469 }
470 // If we have tuned our parameters right, 99.999% of apps should
471 // never reach this point! The ones that do have gone off the rails...
472 //
473 // Magazine is full? Onto the next heap!
474 // We tried 'stealing' from other CPUs' magazines. The net effect
475 // was worse performance from more wasted search time and more
476 // cache contention.
477
478 // rdar://11378331
479 // Future optimization: start at the page we last used, start
480 // in the *zone* we last used. But this would only improve deeply
481 // pathological cases like dispatch_starfish
482 heap = &(*heap)->header.dh_next;
483 }
484 }
485
486 DISPATCH_ALLOC_NOINLINE
487 static dispatch_continuation_t
488 _dispatch_alloc_continuation_alloc(void)
489 {
490 dispatch_continuation_t cont;
491
492 if (fastpath(_dispatch_main_heap)) {
493 // Start looking in the same page where we found a continuation
494 // last time.
495 bitmap_t *last = last_found_page();
496 if (fastpath(last)) {
497 unsigned int i;
498 for (i = 0; i < BITMAPS_PER_PAGE; i++) {
499 bitmap_t *cur = last + i;
500 unsigned int index = bitmap_set_first_unset_bit(cur);
501 if (fastpath(index != NO_BITS_WERE_UNSET)) {
502 bitmap_t *supermap;
503 unsigned int bindex;
504 get_cont_and_indices_for_bitmap_and_index(cur,
505 index, &cont, &supermap, &bindex);
506 mark_bitmap_as_full_if_still_full(supermap, bindex,
507 cur);
508 return cont;
509 }
510 }
511 }
512
513 cont = _dispatch_alloc_continuation_from_heap(_dispatch_main_heap);
514 if (fastpath(cont)) {
515 return cont;
516 }
517 }
518 return _dispatch_alloc_continuation_from_heap_slow();
519 }
520
521 #pragma mark -
522 #pragma mark dispatch_alloc_continuation_free
523
524 DISPATCH_NOINLINE
525 static void
526 _dispatch_alloc_maybe_madvise_page(dispatch_continuation_t c)
527 {
528 void *page = madvisable_page_base_for_continuation(c);
529 if (!page) {
530 // page can't be madvised; maybe it contains non-continuations
531 return;
532 }
533 // Are all the continuations in this page unallocated?
534 volatile bitmap_t *page_bitmaps;
535 get_maps_and_indices_for_continuation((dispatch_continuation_t)page, NULL,
536 NULL, (bitmap_t **)&page_bitmaps, NULL);
537 unsigned int i;
538 for (i = 0; i < BITMAPS_PER_PAGE; i++) {
539 if (page_bitmaps[i] != 0) {
540 return;
541 }
542 }
543 // They are all unallocated, so we could madvise the page. Try to
544 // take ownership of them all.
545 int last_locked = 0;
546 do {
547 if (!os_atomic_cmpxchg(&page_bitmaps[last_locked], BITMAP_C(0),
548 BITMAP_ALL_ONES, relaxed)) {
549 // We didn't get one; since there is a cont allocated in
550 // the page, we can't madvise. Give up and unlock all.
551 goto unlock;
552 }
553 } while (++last_locked < (signed)BITMAPS_PER_PAGE);
554 #if DISPATCH_DEBUG
555 //fprintf(stderr, "%s: madvised page %p for cont %p (next = %p), "
556 // "[%u+1]=%u bitmaps at %p\n", __func__, page, c, c->do_next,
557 // last_locked-1, BITMAPS_PER_PAGE, &page_bitmaps[0]);
558 // Scribble to expose use-after-free bugs
559 // madvise (syscall) flushes these stores
560 memset(page, DISPATCH_ALLOCATOR_SCRIBBLE, DISPATCH_ALLOCATOR_PAGE_SIZE);
561 #endif
562 (void)dispatch_assume_zero(madvise(page, DISPATCH_ALLOCATOR_PAGE_SIZE,
563 MADV_FREE));
564
565 unlock:
566 while (last_locked > 1) {
567 page_bitmaps[--last_locked] = BITMAP_C(0);
568 }
569 if (last_locked) {
570 os_atomic_store(&page_bitmaps[0], BITMAP_C(0), relaxed);
571 }
572 return;
573 }
574
575 DISPATCH_ALLOC_NOINLINE
576 static void
577 _dispatch_alloc_continuation_free(dispatch_continuation_t c)
578 {
579 bitmap_t *b, *s;
580 unsigned int b_idx, idx;
581
582 get_maps_and_indices_for_continuation(c, &s, &b_idx, &b, &idx);
583 bool bitmap_now_empty = bitmap_clear_bit(b, idx, CLEAR_EXCLUSIVELY);
584 if (slowpath(s)) {
585 (void)bitmap_clear_bit(s, b_idx, CLEAR_NONEXCLUSIVELY);
586 }
587 // We only try to madvise(2) pages outside of the first page.
588 // (Allocations in the first page do not have a supermap entry.)
589 if (slowpath(bitmap_now_empty) && slowpath(s)) {
590 return _dispatch_alloc_maybe_madvise_page(c);
591 }
592 }
593
594 #pragma mark -
595 #pragma mark dispatch_alloc_init
596
597 #if DISPATCH_DEBUG
598 static void
599 _dispatch_alloc_init(void)
600 {
601 // Double-check our math. These are all compile time checks and don't
602 // generate code.
603
604 dispatch_assert(sizeof(bitmap_t) == BYTES_PER_BITMAP);
605 dispatch_assert(sizeof(bitmap_t) == BYTES_PER_SUPERMAP);
606 dispatch_assert(sizeof(struct dispatch_magazine_header_s) ==
607 SIZEOF_HEADER);
608
609 dispatch_assert(sizeof(struct dispatch_continuation_s) <=
610 DISPATCH_CONTINUATION_SIZE);
611
612 // Magazines should be the right size, so they pack neatly into an array of
613 // heaps.
614 dispatch_assert(sizeof(struct dispatch_magazine_s) == BYTES_PER_MAGAZINE);
615
616 // The header and maps sizes should match what we computed.
617 dispatch_assert(SIZEOF_HEADER ==
618 sizeof(((struct dispatch_magazine_s *)0x0)->header));
619 dispatch_assert(SIZEOF_MAPS ==
620 sizeof(((struct dispatch_magazine_s *)0x0)->maps));
621
622 // The main array of continuations should start at the second page,
623 // self-aligned.
624 dispatch_assert(offsetof(struct dispatch_magazine_s, conts) %
625 (CONTINUATIONS_PER_BITMAP * DISPATCH_CONTINUATION_SIZE) == 0);
626 dispatch_assert(offsetof(struct dispatch_magazine_s, conts) ==
627 DISPATCH_ALLOCATOR_PAGE_SIZE);
628
629 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
630 // The continuations in the first page should actually fit within the first
631 // page.
632 dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) <
633 DISPATCH_ALLOCATOR_PAGE_SIZE);
634 dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) %
635 DISPATCH_CONTINUATION_SIZE == 0);
636 dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) +
637 sizeof(((struct dispatch_magazine_s *)0x0)->fp_conts) ==
638 DISPATCH_ALLOCATOR_PAGE_SIZE);
639 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
640 // Make sure our alignment will be correct: that is, that we are correctly
641 // aligning to both.
642 dispatch_assert(ROUND_UP_TO_BITMAP_ALIGNMENT(ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(1)) ==
643 ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(1));
644 dispatch_assert(ROUND_UP_TO_CONTINUATION_SIZE(ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(1)) ==
645 ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(1));
646 }
647 #elif (DISPATCH_ALLOCATOR && DISPATCH_CONTINUATION_MALLOC) \
648 || (DISPATCH_CONTINUATION_MALLOC && DISPATCH_USE_MALLOCZONE)
649 static inline void _dispatch_alloc_init(void) {}
650 #endif
651
652 #endif // DISPATCH_ALLOCATOR
653
654 #pragma mark -
655 #pragma mark dispatch_malloc
656
657 #if DISPATCH_CONTINUATION_MALLOC
658
659 #if DISPATCH_USE_MALLOCZONE
660 static malloc_zone_t *_dispatch_ccache_zone;
661
662 #define calloc(n, s) malloc_zone_calloc(_dispatch_ccache_zone, (n), (s))
663 #define free(c) malloc_zone_free(_dispatch_ccache_zone, (c))
664
665 static void
666 _dispatch_malloc_init(void)
667 {
668 _dispatch_ccache_zone = malloc_create_zone(0, 0);
669 dispatch_assert(_dispatch_ccache_zone);
670 malloc_set_zone_name(_dispatch_ccache_zone, "DispatchContinuations");
671 }
672 #else
673 #define _dispatch_malloc_init() ((void)0)
674 #endif // DISPATCH_USE_MALLOCZONE
675
676 static dispatch_continuation_t
677 _dispatch_malloc_continuation_alloc(void)
678 {
679 dispatch_continuation_t dc;
680 while (!(dc = fastpath(calloc(1,
681 ROUND_UP_TO_CACHELINE_SIZE(sizeof(*dc)))))) {
682 _dispatch_temporary_resource_shortage();
683 }
684 return dc;
685 }
686
687 static inline void
688 _dispatch_malloc_continuation_free(dispatch_continuation_t c)
689 {
690 free(c);
691 }
692 #endif // DISPATCH_CONTINUATION_MALLOC
693
694 #pragma mark -
695 #pragma mark dispatch_continuation_alloc
696
697 #if DISPATCH_ALLOCATOR
698 #if DISPATCH_CONTINUATION_MALLOC
699 #if DISPATCH_USE_NANOZONE
700 extern boolean_t malloc_engaged_nano(void);
701 #else
702 #define malloc_engaged_nano() false
703 #endif // DISPATCH_USE_NANOZONE
704 static int _dispatch_use_dispatch_alloc;
705 #else
706 #define _dispatch_use_dispatch_alloc 1
707 #endif // DISPATCH_CONTINUATION_MALLOC
708 #endif // DISPATCH_ALLOCATOR
709
710 #if (DISPATCH_ALLOCATOR && (DISPATCH_CONTINUATION_MALLOC || DISPATCH_DEBUG)) \
711 || (DISPATCH_CONTINUATION_MALLOC && DISPATCH_USE_MALLOCZONE)
712 static void
713 _dispatch_continuation_alloc_init(void *ctxt DISPATCH_UNUSED)
714 {
715 #if DISPATCH_ALLOCATOR
716 #if DISPATCH_CONTINUATION_MALLOC
717 bool use_dispatch_alloc = !malloc_engaged_nano();
718 char *e = getenv("LIBDISPATCH_CONTINUATION_ALLOCATOR");
719 if (e) {
720 use_dispatch_alloc = atoi(e);
721 }
722 _dispatch_use_dispatch_alloc = use_dispatch_alloc;
723 #endif // DISPATCH_CONTINUATION_MALLOC
724 if (_dispatch_use_dispatch_alloc)
725 return _dispatch_alloc_init();
726 #endif // DISPATCH_ALLOCATOR
727 #if DISPATCH_CONTINUATION_MALLOC
728 return _dispatch_malloc_init();
729 #endif // DISPATCH_ALLOCATOR
730 }
731
732 static void
733 _dispatch_continuation_alloc_once()
734 {
735 static dispatch_once_t pred;
736 dispatch_once_f(&pred, NULL, _dispatch_continuation_alloc_init);
737 }
738 #else
739 static inline void _dispatch_continuation_alloc_once(void) {}
740 #endif // DISPATCH_ALLOCATOR ... || DISPATCH_CONTINUATION_MALLOC ...
741
742 dispatch_continuation_t
743 _dispatch_continuation_alloc_from_heap(void)
744 {
745 _dispatch_continuation_alloc_once();
746 #if DISPATCH_ALLOCATOR
747 if (_dispatch_use_dispatch_alloc)
748 return _dispatch_alloc_continuation_alloc();
749 #endif
750 #if DISPATCH_CONTINUATION_MALLOC
751 return _dispatch_malloc_continuation_alloc();
752 #endif
753 }
754
755 void
756 _dispatch_continuation_free_to_heap(dispatch_continuation_t c)
757 {
758 #if DISPATCH_ALLOCATOR
759 if (_dispatch_use_dispatch_alloc)
760 return _dispatch_alloc_continuation_free(c);
761 #endif
762 #if DISPATCH_CONTINUATION_MALLOC
763 return _dispatch_malloc_continuation_free(c);
764 #endif
765 }