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 overwite 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)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 & ~(uintptr_t)PAGE_MASK);
 177 #if DISPATCH_DEBUG
 178         struct dispatch_magazine_s *m = magazine_for_continuation(c);
 179         if (slowpath(page_base < (void *)&m->conts)) {
 180                 DISPATCH_CRASH("madvisable continuation too low");
 181         }
 182         if (slowpath(page_base > (void *)&m->conts[SUPERMAPS_PER_MAGAZINE-1]
 183                         [BITMAPS_PER_SUPERMAP-1][CONTINUATIONS_PER_BITMAP-1])) {
 184                 DISPATCH_CRASH("madvisable continuation too high");
 185         }
 186 #endif
 187         return page_base;
 188 }
 189
 190 // Bitmap that controls the first few continuations in the same page as
 191 // the continuations controlled by the passed bitmap. Undefined results if the
 192 // passed bitmap controls continuations in the first page.
 193 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
 194 static bitmap_t *
 195 first_bitmap_in_same_page(bitmap_t *b)
 196 {
 197 #if DISPATCH_DEBUG
 198         struct dispatch_magazine_s *m;
 199         m = magazine_for_continuation((void*)b);
 200         dispatch_assert(b >= &m->maps[0][0]);
 201         dispatch_assert(b <  &m->maps[SUPERMAPS_PER_MAGAZINE]
 202                         [BITMAPS_PER_SUPERMAP]);
 203 #endif
 204         const uintptr_t PAGE_BITMAP_MASK = (BITMAPS_PER_PAGE *
 205                         BYTES_PER_BITMAP) - 1;
 206         return (bitmap_t *)((uintptr_t)b & ~PAGE_BITMAP_MASK);
 207 }
 208
 209 DISPATCH_ALWAYS_INLINE_NDEBUG DISPATCH_CONST
 210 static bool
 211 bitmap_is_full(bitmap_t bits)
 212 {
 213         return (bits == BITMAP_ALL_ONES);
 214 }
 215
 216 #define NO_BITS_WERE_UNSET (UINT_MAX)
 217
 218 // max_index is the 0-based position of the most significant bit that is
 219 // allowed to be set.
 220 DISPATCH_ALWAYS_INLINE_NDEBUG
 221 static unsigned int
 222 bitmap_set_first_unset_bit_upto_index(volatile bitmap_t *bitmap,
 223                 unsigned int max_index)
 224 {
 225         // No barriers needed in acquire path: the just-allocated
 226         // continuation is "uninitialized", so the caller shouldn't
 227         // load from it before storing, so we don't need to guard
 228         // against reordering those loads.
 229 #if defined(__x86_64__) // TODO rdar://problem/11477843
 230         dispatch_assert(sizeof(*bitmap) == sizeof(uint64_t));
 231         return dispatch_atomic_set_first_bit((volatile uint64_t *)bitmap,max_index);
 232 #else
 233         dispatch_assert(sizeof(*bitmap) == sizeof(uint32_t));
 234         return dispatch_atomic_set_first_bit((volatile uint32_t *)bitmap,max_index);
 235 #endif
 236 }
 237
 238 DISPATCH_ALWAYS_INLINE
 239 static unsigned int
 240 bitmap_set_first_unset_bit(volatile bitmap_t *bitmap)
 241 {
 242         return bitmap_set_first_unset_bit_upto_index(bitmap, UINT_MAX);
 243 }
 244
 245 #define CLEAR_EXCLUSIVELY true
 246 #define CLEAR_NONEXCLUSIVELY false
 247
 248 // Return true if this bit was the last in the bitmap, and it is now all zeroes
 249 DISPATCH_ALWAYS_INLINE_NDEBUG
 250 static bool
 251 bitmap_clear_bit(volatile bitmap_t *bitmap, unsigned int index,
 252                 bool exclusively)
 253 {
 254 #if DISPATCH_DEBUG
 255         dispatch_assert(index < CONTINUATIONS_PER_BITMAP);
 256 #endif
 257         const bitmap_t mask = BITMAP_C(1) << index;
 258         bitmap_t b;
 259
 260         b = *bitmap;
 261         if (exclusively == CLEAR_EXCLUSIVELY) {
 262                 if (slowpath((b & mask) == 0)) {
 263                         DISPATCH_CRASH("Corruption: failed to clear bit exclusively");
 264                 }
 265         }
 266
 267         // and-and-fetch
 268         b = dispatch_atomic_and(bitmap, ~mask, release);
 269         return b == 0;
 270 }
 271
 272 DISPATCH_ALWAYS_INLINE_NDEBUG
 273 static void
 274 mark_bitmap_as_full_if_still_full(volatile bitmap_t *supermap,
 275                 unsigned int bitmap_index, volatile bitmap_t *bitmap)
 276 {
 277 #if DISPATCH_DEBUG
 278         dispatch_assert(bitmap_index < BITMAPS_PER_SUPERMAP);
 279 #endif
 280         const bitmap_t mask = BITMAP_C(1) << bitmap_index;
 281         bitmap_t s, s_new, s_masked;
 282
 283         if (!bitmap_is_full(*bitmap)) {
 284                 return;
 285         }
 286         s_new = *supermap;
 287         for (;;) {
 288                 // No barriers because supermaps are only advisory, they
 289                 // don't protect access to other memory.
 290                 s = s_new;
 291                 s_masked = s | mask;
 292                 if (dispatch_atomic_cmpxchgvw(supermap, s, s_masked, &s_new, relaxed) ||
 293                                 !bitmap_is_full(*bitmap)) {
 294                         return;
 295                 }
 296         }
 297 }
 298
 299 #pragma mark -
 300 #pragma mark dispatch_alloc_continuation_alloc
 301
 302 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
 303 DISPATCH_ALWAYS_INLINE_NDEBUG
 304 static dispatch_continuation_t
 305 alloc_continuation_from_first_page(struct dispatch_magazine_s *magazine)
 306 {
 307         unsigned int i, index, continuation_index;
 308
 309         // TODO: unroll if this is hot?
 310         for (i = 0; i < FULL_BITMAPS_IN_FIRST_PAGE; i++) {
 311                 index = bitmap_set_first_unset_bit(&magazine->fp_maps[i]);
 312                 if (fastpath(index != NO_BITS_WERE_UNSET)) goto found;
 313         }
 314         if (REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE) {
 315                 index = bitmap_set_first_unset_bit_upto_index(&magazine->fp_maps[i],
 316                                 REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE - 1);
 317                 if (fastpath(index != NO_BITS_WERE_UNSET)) goto found;
 318         }
 319         return NULL;
 320
 321 found:
 322         continuation_index = (i * CONTINUATIONS_PER_BITMAP) + index;
 323         return (dispatch_continuation_t)&magazine->fp_conts[continuation_index];
 324 }
 325 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 326
 327 DISPATCH_ALWAYS_INLINE_NDEBUG
 328 static dispatch_continuation_t
 329 alloc_continuation_from_magazine(struct dispatch_magazine_s *magazine)
 330 {
 331         unsigned int s, b, index;
 332
 333         for (s = 0; s < SUPERMAPS_PER_MAGAZINE; s++) {
 334                 volatile bitmap_t *supermap = supermap_address(magazine, s);
 335                 if (bitmap_is_full(*supermap)) {
 336                         continue;
 337                 }
 338                 for (b = 0; b < BITMAPS_PER_SUPERMAP; b++) {
 339                         volatile bitmap_t *bitmap = bitmap_address(magazine, s, b);
 340                         index = bitmap_set_first_unset_bit(bitmap);
 341                         if (index != NO_BITS_WERE_UNSET) {
 342                                 set_last_found_page(
 343                                                 first_bitmap_in_same_page((bitmap_t *)bitmap));
 344                                 mark_bitmap_as_full_if_still_full(supermap, b, bitmap);
 345                                 return continuation_address(magazine, s, b, index);
 346                         }
 347                 }
 348         }
 349         return NULL;
 350 }
 351
 352 DISPATCH_NOINLINE
 353 static void
 354 _dispatch_alloc_try_create_heap(dispatch_heap_t *heap_ptr)
 355 {
 356 #if HAVE_MACH
 357         kern_return_t kr;
 358         mach_vm_size_t vm_size = MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE;
 359         mach_vm_offset_t vm_mask = ~MAGAZINE_MASK;
 360         mach_vm_address_t vm_addr = vm_page_size;
 361         while (slowpath(kr = mach_vm_map(mach_task_self(), &vm_addr, vm_size,
 362                         vm_mask, VM_FLAGS_ANYWHERE | VM_MAKE_TAG(VM_MEMORY_LIBDISPATCH),
 363                         MEMORY_OBJECT_NULL, 0, FALSE, VM_PROT_DEFAULT, VM_PROT_ALL,
 364                         VM_INHERIT_DEFAULT))) {
 365                 if (kr != KERN_NO_SPACE) {
 366                         (void)dispatch_assume_zero(kr);
 367                         DISPATCH_CLIENT_CRASH("Could not allocate heap");
 368                 }
 369                 _dispatch_temporary_resource_shortage();
 370                 vm_addr = vm_page_size;
 371         }
 372         uintptr_t aligned_region = (uintptr_t)vm_addr;
 373 #else // HAVE_MACH
 374         const size_t region_sz = (1 + MAGAZINES_PER_HEAP) * BYTES_PER_MAGAZINE;
 375         void *region_p;
 376         while (!dispatch_assume((region_p = mmap(NULL, region_sz,
 377                         PROT_READ|PROT_WRITE, MAP_ANON | MAP_PRIVATE,
 378                         VM_MAKE_TAG(VM_MEMORY_LIBDISPATCH), 0)) != MAP_FAILED)) {
 379                 _dispatch_temporary_resource_shortage();
 380         }
 381         uintptr_t region = (uintptr_t)region_p;
 382         uintptr_t region_end = region + region_sz;
 383         uintptr_t aligned_region, aligned_region_end;
 384         uintptr_t bottom_slop_len, top_slop_len;
 385         // Realign if needed; find the slop at top/bottom to unmap
 386         if ((region & ~(MAGAZINE_MASK)) == 0) {
 387                 bottom_slop_len = 0;
 388                 aligned_region = region;
 389                 aligned_region_end = region_end - BYTES_PER_MAGAZINE;
 390                 top_slop_len = BYTES_PER_MAGAZINE;
 391         } else {
 392                 aligned_region = (region & MAGAZINE_MASK) + BYTES_PER_MAGAZINE;
 393                 aligned_region_end = aligned_region +
 394                                 (MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE);
 395                 bottom_slop_len = aligned_region - region;
 396                 top_slop_len = BYTES_PER_MAGAZINE - bottom_slop_len;
 397         }
 398 #if DISPATCH_DEBUG
 399         // Double-check our math.
 400         dispatch_assert(aligned_region % PAGE_SIZE == 0);
 401         dispatch_assert(aligned_region_end % PAGE_SIZE == 0);
 402         dispatch_assert(aligned_region_end > aligned_region);
 403         dispatch_assert(top_slop_len % PAGE_SIZE == 0);
 404         dispatch_assert(bottom_slop_len % PAGE_SIZE == 0);
 405         dispatch_assert(aligned_region_end + top_slop_len == region_end);
 406         dispatch_assert(region + bottom_slop_len == aligned_region);
 407         dispatch_assert(region_sz == bottom_slop_len + top_slop_len +
 408                         MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE);
 409         if (bottom_slop_len) {
 410                 (void)dispatch_assume_zero(mprotect((void *)region, bottom_slop_len,
 411                                 PROT_NONE));
 412         }
 413         if (top_slop_len) {
 414                 (void)dispatch_assume_zero(mprotect((void *)aligned_region_end,
 415                                 top_slop_len, PROT_NONE));
 416         }
 417 #else
 418         if (bottom_slop_len) {
 419                 (void)dispatch_assume_zero(munmap((void *)region, bottom_slop_len));
 420         }
 421         if (top_slop_len) {
 422                 (void)dispatch_assume_zero(munmap((void *)aligned_region_end,
 423                                 top_slop_len));
 424         }
 425 #endif // DISPATCH_DEBUG
 426 #endif // HAVE_MACH
 427
 428         if (!dispatch_atomic_cmpxchg(heap_ptr, NULL, (void *)aligned_region,
 429                         relaxed)) {
 430                 // If we lost the race to link in the new region, unmap the whole thing.
 431 #if DISPATCH_DEBUG
 432                 (void)dispatch_assume_zero(mprotect((void *)aligned_region,
 433                                 MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE, PROT_NONE));
 434 #else
 435                 (void)dispatch_assume_zero(munmap((void *)aligned_region,
 436                                 MAGAZINES_PER_HEAP * BYTES_PER_MAGAZINE));
 437 #endif
 438         }
 439 }
 440
 441 DISPATCH_NOINLINE
 442 static dispatch_continuation_t
 443 _dispatch_alloc_continuation_from_heap(dispatch_heap_t heap)
 444 {
 445         dispatch_continuation_t cont;
 446
 447         unsigned int cpu_number = _dispatch_cpu_number();
 448 #ifdef DISPATCH_DEBUG
 449         dispatch_assert(cpu_number < NUM_CPU);
 450 #endif
 451
 452 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
 453         // First try the continuations in the first page for this CPU
 454         cont = alloc_continuation_from_first_page(&(heap[cpu_number]));
 455         if (fastpath(cont)) {
 456                 return cont;
 457         }
 458 #endif
 459         // Next, try the rest of the magazine for this CPU
 460         cont = alloc_continuation_from_magazine(&(heap[cpu_number]));
 461         return cont;
 462 }
 463
 464 DISPATCH_NOINLINE
 465 static dispatch_continuation_t
 466 _dispatch_alloc_continuation_from_heap_slow(void)
 467 {
 468         dispatch_heap_t *heap = &_dispatch_main_heap;
 469         dispatch_continuation_t cont;
 470
 471         for (;;) {
 472                 if (!fastpath(*heap)) {
 473                         _dispatch_alloc_try_create_heap(heap);
 474                 }
 475                 cont = _dispatch_alloc_continuation_from_heap(*heap);
 476                 if (fastpath(cont)) {
 477                         return cont;
 478                 }
 479                 // If we have tuned our parameters right, 99.999% of apps should
 480                 // never reach this point! The ones that do have gone off the rails...
 481                 //
 482                 // Magazine is full? Onto the next heap!
 483                 // We tried 'stealing' from other CPUs' magazines. The net effect
 484                 // was worse performance from more wasted search time and more
 485                 // cache contention.
 486
 487                 // rdar://11378331
 488                 // Future optimization: start at the page we last used, start
 489                 // in the *zone* we last used. But this would only improve deeply
 490                 // pathological cases like dispatch_starfish
 491                 heap = &(*heap)->header.dh_next;
 492         }
 493 }
 494
 495 DISPATCH_ALLOC_NOINLINE
 496 static dispatch_continuation_t
 497 _dispatch_alloc_continuation_alloc(void)
 498 {
 499         dispatch_continuation_t cont;
 500
 501         if (fastpath(_dispatch_main_heap)) {
 502                 // Start looking in the same page where we found a continuation
 503                 // last time.
 504                 bitmap_t *last = last_found_page();
 505                 if (fastpath(last)) {
 506                         unsigned int i;
 507                         for (i = 0; i < BITMAPS_PER_PAGE; i++) {
 508                                 bitmap_t *cur = last + i;
 509                                 unsigned int index = bitmap_set_first_unset_bit(cur);
 510                                 if (fastpath(index != NO_BITS_WERE_UNSET)) {
 511                                         bitmap_t *supermap;
 512                                         unsigned int bindex;
 513                                         get_cont_and_indices_for_bitmap_and_index(cur,
 514                                                         index, &cont, &supermap, &bindex);
 515                                         mark_bitmap_as_full_if_still_full(supermap, bindex,
 516                                                         cur);
 517                                         return cont;
 518                                 }
 519                         }
 520                 }
 521
 522                 cont = _dispatch_alloc_continuation_from_heap(_dispatch_main_heap);
 523                 if (fastpath(cont)) {
 524                         return cont;
 525                 }
 526         }
 527         return _dispatch_alloc_continuation_from_heap_slow();
 528 }
 529
 530 #pragma mark -
 531 #pragma mark dispatch_alloc_continuation_free
 532
 533 DISPATCH_NOINLINE
 534 static void
 535 _dispatch_alloc_maybe_madvise_page(dispatch_continuation_t c)
 536 {
 537         void *page = madvisable_page_base_for_continuation(c);
 538         if (!page) {
 539                 // page can't be madvised; maybe it contains non-continuations
 540                 return;
 541         }
 542         // Are all the continuations in this page unallocated?
 543         volatile bitmap_t *page_bitmaps;
 544         get_maps_and_indices_for_continuation((dispatch_continuation_t)page, NULL,
 545                         NULL, (bitmap_t **)&page_bitmaps, NULL);
 546         unsigned int i;
 547         for (i = 0; i < BITMAPS_PER_PAGE; i++) {
 548                 if (page_bitmaps[i] != 0) {
 549                         return;
 550                 }
 551         }
 552         // They are all unallocated, so we could madvise the page. Try to
 553         // take ownership of them all.
 554         int last_locked = 0;
 555         do {
 556                 if (!dispatch_atomic_cmpxchg(&page_bitmaps[last_locked], BITMAP_C(0),
 557                                 BITMAP_ALL_ONES, relaxed)) {
 558                         // We didn't get one; since there is a cont allocated in
 559                         // the page, we can't madvise. Give up and unlock all.
 560                         goto unlock;
 561                 }
 562         } while (++last_locked < (signed)BITMAPS_PER_PAGE);
 563 #if DISPATCH_DEBUG
 564         //fprintf(stderr, "%s: madvised page %p for cont %p (next = %p), "
 565         //              "[%u+1]=%u bitmaps at %p\n", __func__, page, c, c->do_next,
 566         //              last_locked-1, BITMAPS_PER_PAGE, &page_bitmaps[0]);
 567         // Scribble to expose use-after-free bugs
 568         // madvise (syscall) flushes these stores
 569         memset(page, DISPATCH_ALLOCATOR_SCRIBBLE, PAGE_SIZE);
 570 #endif
 571         (void)dispatch_assume_zero(madvise(page, PAGE_SIZE, MADV_FREE));
 572
 573 unlock:
 574         while (last_locked > 1) {
 575                 page_bitmaps[--last_locked] = BITMAP_C(0);
 576         }
 577         if (last_locked) {
 578                 dispatch_atomic_store(&page_bitmaps[0], BITMAP_C(0), relaxed);
 579         }
 580         return;
 581 }
 582
 583 DISPATCH_ALLOC_NOINLINE
 584 static void
 585 _dispatch_alloc_continuation_free(dispatch_continuation_t c)
 586 {
 587         bitmap_t *b, *s;
 588         unsigned int b_idx, idx;
 589
 590         get_maps_and_indices_for_continuation(c, &s, &b_idx, &b, &idx);
 591         bool bitmap_now_empty = bitmap_clear_bit(b, idx, CLEAR_EXCLUSIVELY);
 592         if (slowpath(s)) {
 593                 (void)bitmap_clear_bit(s, b_idx, CLEAR_NONEXCLUSIVELY);
 594         }
 595         // We only try to madvise(2) pages outside of the first page.
 596         // (Allocations in the first page do not have a supermap entry.)
 597         if (slowpath(bitmap_now_empty) && slowpath(s)) {
 598                 return _dispatch_alloc_maybe_madvise_page(c);
 599         }
 600 }
 601
 602 #pragma mark -
 603 #pragma mark dispatch_alloc_init
 604
 605 #if DISPATCH_DEBUG
 606 static void
 607 _dispatch_alloc_init(void)
 608 {
 609         // Double-check our math. These are all compile time checks and don't
 610         // generate code.
 611
 612         dispatch_assert(sizeof(bitmap_t) == BYTES_PER_BITMAP);
 613         dispatch_assert(sizeof(bitmap_t) == BYTES_PER_SUPERMAP);
 614         dispatch_assert(sizeof(struct dispatch_magazine_header_s) ==
 615                         SIZEOF_HEADER);
 616
 617         dispatch_assert(sizeof(struct dispatch_continuation_s) <=
 618                         DISPATCH_CONTINUATION_SIZE);
 619
 620         // Magazines should be the right size, so they pack neatly into an array of
 621         // heaps.
 622         dispatch_assert(sizeof(struct dispatch_magazine_s) == BYTES_PER_MAGAZINE);
 623
 624         // The header and maps sizes should match what we computed.
 625         dispatch_assert(SIZEOF_HEADER ==
 626                         sizeof(((struct dispatch_magazine_s *)0x0)->header));
 627         dispatch_assert(SIZEOF_MAPS ==
 628                         sizeof(((struct dispatch_magazine_s *)0x0)->maps));
 629
 630         // The main array of continuations should start at the second page,
 631         // self-aligned.
 632         dispatch_assert(offsetof(struct dispatch_magazine_s, conts) %
 633                         (CONTINUATIONS_PER_BITMAP * DISPATCH_CONTINUATION_SIZE) == 0);
 634         dispatch_assert(offsetof(struct dispatch_magazine_s, conts) == PAGE_SIZE);
 635
 636 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
 637         // The continuations in the first page should actually fit within the first
 638         // page.
 639         dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) < PAGE_SIZE);
 640         dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) %
 641                         DISPATCH_CONTINUATION_SIZE == 0);
 642         dispatch_assert(offsetof(struct dispatch_magazine_s, fp_conts) +
 643                         sizeof(((struct dispatch_magazine_s *)0x0)->fp_conts) == PAGE_SIZE);
 644 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 645 }
 646 #else
 647 static inline void _dispatch_alloc_init(void) {}
 648 #endif
 649
 650 #endif // DISPATCH_ALLOCATOR
 651
 652 #pragma mark -
 653 #pragma mark dispatch_malloc
 654
 655 #if DISPATCH_CONTINUATION_MALLOC
 656
 657 #if DISPATCH_USE_MALLOCZONE
 658 static malloc_zone_t *_dispatch_ccache_zone;
 659
 660 #define calloc(n, s) malloc_zone_calloc(_dispatch_ccache_zone, (n), (s))
 661 #define free(c) malloc_zone_free(_dispatch_ccache_zone, (c))
 662
 663 static void
 664 _dispatch_malloc_init(void)
 665 {
 666         _dispatch_ccache_zone = malloc_create_zone(0, 0);
 667         dispatch_assert(_dispatch_ccache_zone);
 668         malloc_set_zone_name(_dispatch_ccache_zone, "DispatchContinuations");
 669 }
 670 #else
 671 static inline void _dispatch_malloc_init(void) {}
 672 #endif // DISPATCH_USE_MALLOCZONE
 673
 674 static dispatch_continuation_t
 675 _dispatch_malloc_continuation_alloc(void)
 676 {
 677         dispatch_continuation_t dc;
 678         while (!(dc = fastpath(calloc(1,
 679                         ROUND_UP_TO_CACHELINE_SIZE(sizeof(*dc)))))) {
 680                 _dispatch_temporary_resource_shortage();
 681         }
 682         return dc;
 683 }
 684
 685 static inline void
 686 _dispatch_malloc_continuation_free(dispatch_continuation_t c)
 687 {
 688         free(c);
 689 }
 690 #endif // DISPATCH_CONTINUATION_MALLOC
 691
 692 #pragma mark -
 693 #pragma mark dispatch_continuation_alloc
 694
 695 #if DISPATCH_ALLOCATOR
 696 #if DISPATCH_CONTINUATION_MALLOC
 697 #if DISPATCH_USE_NANOZONE
 698 extern boolean_t malloc_engaged_nano(void);
 699 #else
 700 #define malloc_engaged_nano() false
 701 #endif // DISPATCH_USE_NANOZONE
 702 static int _dispatch_use_dispatch_alloc;
 703 #else
 704 #define _dispatch_use_dispatch_alloc 1
 705 #endif // DISPATCH_CONTINUATION_MALLOC
 706 #endif // DISPATCH_ALLOCATOR
 707
 708 #if (DISPATCH_ALLOCATOR && (DISPATCH_CONTINUATION_MALLOC || DISPATCH_DEBUG)) \
 709                 || (DISPATCH_CONTINUATION_MALLOC && DISPATCH_USE_MALLOCZONE)
 710 static void
 711 _dispatch_continuation_alloc_init(void *ctxt DISPATCH_UNUSED)
 712 {
 713 #if DISPATCH_ALLOCATOR
 714 #if DISPATCH_CONTINUATION_MALLOC
 715         bool use_dispatch_alloc = !malloc_engaged_nano();
 716         char *e = getenv("LIBDISPATCH_CONTINUATION_ALLOCATOR");
 717         if (e) {
 718                 use_dispatch_alloc = atoi(e);
 719         }
 720         _dispatch_use_dispatch_alloc = use_dispatch_alloc;
 721 #endif // DISPATCH_CONTINUATION_MALLOC
 722         if (_dispatch_use_dispatch_alloc)
 723                 return _dispatch_alloc_init();
 724 #endif // DISPATCH_ALLOCATOR
 725 #if DISPATCH_CONTINUATION_MALLOC
 726         return _dispatch_malloc_init();
 727 #endif // DISPATCH_ALLOCATOR
 728 }
 729
 730 static void
 731 _dispatch_continuation_alloc_once()
 732 {
 733         static dispatch_once_t pred;
 734         dispatch_once_f(&pred, NULL, _dispatch_continuation_alloc_init);
 735 }
 736 #else
 737 static inline void _dispatch_continuation_alloc_once(void) {}
 738 #endif // DISPATCH_ALLOCATOR ... || DISPATCH_CONTINUATION_MALLOC ...
 739
 740 dispatch_continuation_t
 741 _dispatch_continuation_alloc_from_heap(void)
 742 {
 743         _dispatch_continuation_alloc_once();
 744 #if DISPATCH_ALLOCATOR
 745         if (_dispatch_use_dispatch_alloc)
 746                 return _dispatch_alloc_continuation_alloc();
 747 #endif
 748 #if DISPATCH_CONTINUATION_MALLOC
 749         return _dispatch_malloc_continuation_alloc();
 750 #endif
 751 }
 752
 753 void
 754 _dispatch_continuation_free_to_heap(dispatch_continuation_t c)
 755 {
 756 #if DISPATCH_ALLOCATOR
 757         if (_dispatch_use_dispatch_alloc)
 758                 return _dispatch_alloc_continuation_free(c);
 759 #endif
 760 #if DISPATCH_CONTINUATION_MALLOC
 761         return _dispatch_malloc_continuation_free(c);
 762 #endif
 763 }
 764