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 }