src/allocator_internal.h

   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 /*
  22  * IMPORTANT: This header file describes INTERNAL interfaces to libdispatch
  23  * which are subject to change in future releases of Mac OS X. Any applications
  24  * relying on these interfaces WILL break.
  25  */
  26
  27 #ifndef __DISPATCH_ALLOCATOR_INTERNAL__
  28 #define __DISPATCH_ALLOCATOR_INTERNAL__
  29
  30 #ifndef DISPATCH_ALLOCATOR
  31 #if TARGET_OS_MAC && (defined(__LP64__) || TARGET_OS_EMBEDDED)
  32 #define DISPATCH_ALLOCATOR 1
  33 #endif
  34 #endif
  35
  36 #if TARGET_IPHONE_SIMULATOR && IPHONE_SIMULATOR_HOST_MIN_VERSION_REQUIRED < 1090
  37 #undef DISPATCH_USE_NANOZONE
  38 #define DISPATCH_USE_NANOZONE 0
  39 #endif
  40 #ifndef DISPATCH_USE_NANOZONE
  41 #if TARGET_OS_MAC && defined(__LP64__) && \
  42                 (__MAC_OS_X_VERSION_MIN_REQUIRED >= 1090 || \
  43                 __IPHONE_OS_VERSION_MIN_REQUIRED >= 70000)
  44 #define DISPATCH_USE_NANOZONE 1
  45 #endif
  46 #endif
  47
  48 #ifndef DISPATCH_USE_MALLOCZONE
  49 #if (TARGET_OS_MAC && !DISPATCH_USE_NANOZONE) || \
  50                 (!TARGET_OS_MAC && HAVE_MALLOC_CREATE_ZONE)
  51 #define DISPATCH_USE_MALLOCZONE 1
  52 #endif
  53 #endif
  54
  55 #ifndef DISPATCH_CONTINUATION_MALLOC
  56 #if DISPATCH_USE_NANOZONE || !DISPATCH_ALLOCATOR
  57 #define DISPATCH_CONTINUATION_MALLOC 1
  58 #endif
  59 #endif
  60
  61 #if !DISPATCH_ALLOCATOR && !DISPATCH_CONTINUATION_MALLOC
  62 #error Invalid allocator configuration
  63 #endif
  64
  65 #if DISPATCH_ALLOCATOR && DISPATCH_CONTINUATION_MALLOC
  66 #define DISPATCH_ALLOC_NOINLINE DISPATCH_NOINLINE
  67 #else
  68 #define DISPATCH_ALLOC_NOINLINE
  69 #endif
  70
  71 #pragma mark -
  72 #pragma mark DISPATCH_ALLOCATOR
  73
  74 #if DISPATCH_ALLOCATOR
  75
  76 // Configuration here!
  77 #define NUM_CPU dispatch_hw_config(logical_cpus)
  78 #define MAGAZINES_PER_HEAP (NUM_CPU)
  79
  80 // Do you care about compaction or performance?
  81 #if TARGET_OS_EMBEDDED
  82 #define PACK_FIRST_PAGE_WITH_CONTINUATIONS 1
  83 #else
  84 #define PACK_FIRST_PAGE_WITH_CONTINUATIONS 0
  85 #endif
  86
  87 #ifndef PAGE_MAX_SIZE
  88 #define PAGE_MAX_SIZE PAGE_SIZE
  89 #endif
  90 #ifndef PAGE_MAX_MASK
  91 #define PAGE_MAX_MASK PAGE_MASK
  92 #endif
  93 #define DISPATCH_ALLOCATOR_PAGE_SIZE PAGE_MAX_SIZE
  94 #define DISPATCH_ALLOCATOR_PAGE_MASK PAGE_MAX_MASK
  95
  96
  97 #if TARGET_OS_EMBEDDED
  98 #define PAGES_PER_MAGAZINE 64
  99 #else
 100 #define PAGES_PER_MAGAZINE 512
 101 #endif
 102
 103 // Use the largest type your platform is comfortable doing atomic ops with.
 104 // TODO: rdar://11477843
 105 typedef unsigned long bitmap_t;
 106 #if defined(__LP64__)
 107 #define BYTES_PER_BITMAP 8
 108 #else
 109 #define BYTES_PER_BITMAP 4
 110 #endif
 111
 112 #define BITMAP_C(v) ((bitmap_t)(v))
 113 #define BITMAP_ALL_ONES (~BITMAP_C(0))
 114
 115 // Stop configuring.
 116
 117 #define CONTINUATIONS_PER_BITMAP (BYTES_PER_BITMAP * 8)
 118 #define BITMAPS_PER_SUPERMAP (BYTES_PER_SUPERMAP * 8)
 119
 120 #define BYTES_PER_MAGAZINE (PAGES_PER_MAGAZINE * DISPATCH_ALLOCATOR_PAGE_SIZE)
 121 #define CONSUMED_BYTES_PER_BITMAP (BYTES_PER_BITMAP + \
 122                 (DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_BITMAP))
 123
 124 #define BYTES_PER_SUPERMAP BYTES_PER_BITMAP
 125 #define CONSUMED_BYTES_PER_SUPERMAP (BYTES_PER_SUPERMAP + \
 126                 (BITMAPS_PER_SUPERMAP * CONSUMED_BYTES_PER_BITMAP))
 127
 128 #define BYTES_PER_HEAP (BYTES_PER_MAGAZINE * MAGAZINES_PER_HEAP)
 129
 130 #define BYTES_PER_PAGE DISPATCH_ALLOCATOR_PAGE_SIZE
 131 #define CONTINUATIONS_PER_PAGE (BYTES_PER_PAGE / DISPATCH_CONTINUATION_SIZE)
 132 #define BITMAPS_PER_PAGE (CONTINUATIONS_PER_PAGE / CONTINUATIONS_PER_BITMAP)
 133
 134 // Assumption: metadata will be only in the first page.
 135 #define SUPERMAPS_PER_MAGAZINE ((BYTES_PER_MAGAZINE - BYTES_PER_PAGE) / \
 136                 CONSUMED_BYTES_PER_SUPERMAP)
 137 #define BITMAPS_PER_MAGAZINE (SUPERMAPS_PER_MAGAZINE * BITMAPS_PER_SUPERMAP)
 138 #define CONTINUATIONS_PER_MAGAZINE \
 139                 (BITMAPS_PER_MAGAZINE * CONTINUATIONS_PER_BITMAP)
 140
 141 #define HEAP_MASK (~(uintptr_t)(BYTES_PER_HEAP - 1))
 142 #define MAGAZINE_MASK (~(uintptr_t)(BYTES_PER_MAGAZINE - 1))
 143
 144 // this will round up such that first_bitmap_in_same_page() can mask the address
 145 // of a bitmap_t in the maps to obtain the first bitmap for that same page
 146 #define ROUND_UP_TO_BITMAP_ALIGNMENT(x) \
 147                 (((x) + ((BITMAPS_PER_PAGE * BYTES_PER_BITMAP) - 1u)) & \
 148                 ~((BITMAPS_PER_PAGE * BYTES_PER_BITMAP) - 1u))
 149 // Since these are both powers of two, we end up with not only the max alignment,
 150 // but happily the least common multiple, which will be the greater of the two.
 151 #define ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(ROUND_UP_TO_BITMAP_ALIGNMENT(x)))
 152 #define PADDING_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) (ROUND_UP_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE(x) - (x))
 153
 154 #define PADDING_TO_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(x) - (x))
 155
 156 #if defined(__LP64__)
 157 #define SIZEOF_HEADER 16
 158 #else
 159 #define SIZEOF_HEADER 8
 160 #endif
 161
 162 #define SIZEOF_SUPERMAPS (BYTES_PER_SUPERMAP * SUPERMAPS_PER_MAGAZINE)
 163 #define SIZEOF_MAPS (BYTES_PER_BITMAP * BITMAPS_PER_SUPERMAP * \
 164                 SUPERMAPS_PER_MAGAZINE)
 165
 166 // header is expected to end on supermap's required alignment
 167 #define HEADER_TO_SUPERMAPS_PADDING 0
 168 // we want to align the maps to a continuation size, but we must also have proper padding
 169 // so that we can perform first_bitmap_in_same_page()
 170 #define SUPERMAPS_TO_MAPS_PADDING (PADDING_TO_BITMAP_ALIGNMENT_AND_CONTINUATION_SIZE( \
 171                 SIZEOF_SUPERMAPS + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_HEADER))
 172
 173 #define MAPS_TO_FPMAPS_PADDING (PADDING_TO_CONTINUATION_SIZE(SIZEOF_MAPS))
 174
 175 #define BYTES_LEFT_IN_FIRST_PAGE (BYTES_PER_PAGE - \
 176                 (SIZEOF_HEADER + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_SUPERMAPS + \
 177                 SUPERMAPS_TO_MAPS_PADDING + SIZEOF_MAPS + MAPS_TO_FPMAPS_PADDING))
 178
 179 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
 180
 181 #define FULL_BITMAPS_IN_FIRST_PAGE \
 182                 (BYTES_LEFT_IN_FIRST_PAGE / CONSUMED_BYTES_PER_BITMAP)
 183 #define REMAINDER_IN_FIRST_PAGE (BYTES_LEFT_IN_FIRST_PAGE - \
 184                 (FULL_BITMAPS_IN_FIRST_PAGE * CONSUMED_BYTES_PER_BITMAP) - \
 185                 (FULL_BITMAPS_IN_FIRST_PAGE ? 0 : \
 186                 ROUND_UP_TO_CONTINUATION_SIZE(BYTES_PER_BITMAP)))
 187
 188 #define REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE \
 189                 (REMAINDER_IN_FIRST_PAGE / DISPATCH_CONTINUATION_SIZE)
 190 #define CONTINUATIONS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE * \
 191                 CONTINUATIONS_PER_BITMAP) + REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE
 192 #define BITMAPS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE + \
 193                 (REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE == 0 ? 0 : 1))
 194
 195 #define FPMAPS_TO_FPCONTS_PADDING (PADDING_TO_CONTINUATION_SIZE(\
 196                 BYTES_PER_BITMAP * BITMAPS_IN_FIRST_PAGE))
 197
 198 #else // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 199
 200 #define MAPS_TO_CONTS_PADDING BYTES_LEFT_IN_FIRST_PAGE
 201
 202 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 203
 204 #define AFTER_CONTS_PADDING (BYTES_PER_MAGAZINE - (BYTES_PER_PAGE + \
 205                 (DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_MAGAZINE)))
 206
 207 // This is the object our allocator allocates: a chunk of memory rounded up
 208 // from sizeof(struct dispatch_continuation_s) to the cacheline size, so
 209 // unrelated continuations don't share cachelines. It'd be nice if
 210 // dispatch_continuation_s included this rounding/padding, but it doesn't.
 211 typedef char padded_continuation[DISPATCH_CONTINUATION_SIZE];
 212
 213 // A dispatch_heap_t is the base address of an array of dispatch_magazine_s,
 214 // one magazine per CPU.
 215 typedef struct dispatch_magazine_s * dispatch_heap_t;
 216
 217 struct dispatch_magazine_header_s {
 218         // Link to the next heap in the chain. Only used in magazine 0's header
 219         dispatch_heap_t dh_next;
 220
 221         // Points to the first bitmap in the page where this CPU succesfully
 222         // allocated a continuation last time. Only used in the first heap.
 223         bitmap_t *last_found_page;
 224 };
 225
 226 // A magazine is a complex data structure. It must be exactly
 227 // PAGES_PER_MAGAZINE * PAGE_SIZE bytes long, and that value must be a
 228 // power of 2. (See magazine_for_continuation()).
 229 struct dispatch_magazine_s {
 230         // See above.
 231         struct dispatch_magazine_header_s header;
 232
 233         // Align supermaps as needed.
 234 #if HEADER_TO_SUPERMAPS_PADDING > 0
 235         char _pad0[HEADER_TO_SUPERMAPS_PADDING];
 236 #endif
 237
 238         // Second-level bitmap; each set bit means a bitmap_t in maps[][]
 239         // is completely full (and can be skipped while searching).
 240         bitmap_t supermaps[SUPERMAPS_PER_MAGAZINE];
 241
 242         // Align maps to a cacheline.
 243 #if SUPERMAPS_TO_MAPS_PADDING > 0
 244         char _pad1[SUPERMAPS_TO_MAPS_PADDING];
 245 #endif
 246
 247         // Each bit in maps[][] is the free/used state of a member of conts[][][].
 248         bitmap_t maps[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP];
 249
 250         // Align fp_maps to a cacheline.
 251 #if MAPS_TO_FPMAPS_PADDING > 0
 252         char _pad2[MAPS_TO_FPMAPS_PADDING];
 253 #endif
 254
 255 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS
 256         // Bitmaps for the continuations that live in the first page, which
 257         // are treated specially (they have faster search code).
 258         bitmap_t fp_maps[BITMAPS_IN_FIRST_PAGE];
 259
 260         // Align fp_conts to cacheline.
 261 #if FPMAPS_TO_FPCONTS_PADDING > 0
 262         char _pad3[FPMAPS_TO_FPCONTS_PADDING];
 263 #endif
 264
 265         // Continuations that live in the first page.
 266         padded_continuation fp_conts[CONTINUATIONS_IN_FIRST_PAGE];
 267
 268 #else // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 269
 270 #if MAPS_TO_CONTS_PADDING > 0
 271         char _pad4[MAPS_TO_CONTS_PADDING];
 272 #endif
 273 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS
 274
 275         // This is the big array of continuations.
 276         // This must start on a page boundary.
 277         padded_continuation conts[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP]
 278                         [CONTINUATIONS_PER_BITMAP];
 279
 280         // Fill the unused space to exactly BYTES_PER_MAGAZINE
 281 #if AFTER_CONTS_PADDING > 0
 282         char _pad5[AFTER_CONTS_PADDING];
 283 #endif
 284 };
 285
 286 #if DISPATCH_DEBUG
 287 #define DISPATCH_ALLOCATOR_SCRIBBLE ((uintptr_t)0xAFAFAFAFAFAFAFAF)
 288 #endif
 289
 290 #endif // DISPATCH_ALLOCATOR
 291
 292 #endif // __DISPATCH_ALLOCATOR_INTERNAL__