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 #define PADDING_TO_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(x) - (x)) 145 146 #if defined(__LP64__) 147 #define SIZEOF_HEADER 16 148 #else 149 #define SIZEOF_HEADER 8 150 #endif 151 152 #define SIZEOF_SUPERMAPS (BYTES_PER_SUPERMAP * SUPERMAPS_PER_MAGAZINE) 153 #define SIZEOF_MAPS (BYTES_PER_BITMAP * BITMAPS_PER_SUPERMAP * \ 154 SUPERMAPS_PER_MAGAZINE) 155 156 // header is expected to end on supermap's required alignment 157 #define HEADER_TO_SUPERMAPS_PADDING 0 158 #define SUPERMAPS_TO_MAPS_PADDING (PADDING_TO_CONTINUATION_SIZE( \ 159 SIZEOF_SUPERMAPS + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_HEADER)) 160 #define MAPS_TO_FPMAPS_PADDING (PADDING_TO_CONTINUATION_SIZE(SIZEOF_MAPS)) 161 162 #define BYTES_LEFT_IN_FIRST_PAGE (BYTES_PER_PAGE - \ 163 (SIZEOF_HEADER + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_SUPERMAPS + \ 164 SUPERMAPS_TO_MAPS_PADDING + SIZEOF_MAPS + MAPS_TO_FPMAPS_PADDING)) 165 166 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS 167 168 #define FULL_BITMAPS_IN_FIRST_PAGE \ 169 (BYTES_LEFT_IN_FIRST_PAGE / CONSUMED_BYTES_PER_BITMAP) 170 #define REMAINDER_IN_FIRST_PAGE (BYTES_LEFT_IN_FIRST_PAGE - \ 171 (FULL_BITMAPS_IN_FIRST_PAGE * CONSUMED_BYTES_PER_BITMAP) - \ 172 (FULL_BITMAPS_IN_FIRST_PAGE ? 0 : \ 173 ROUND_UP_TO_CONTINUATION_SIZE(BYTES_PER_BITMAP))) 174 175 #define REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE \ 176 (REMAINDER_IN_FIRST_PAGE / DISPATCH_CONTINUATION_SIZE) 177 #define CONTINUATIONS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE * \ 178 CONTINUATIONS_PER_BITMAP) + REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE 179 #define BITMAPS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE + \ 180 (REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE == 0 ? 0 : 1)) 181 182 #define FPMAPS_TO_FPCONTS_PADDING (PADDING_TO_CONTINUATION_SIZE(\ 183 BYTES_PER_BITMAP * BITMAPS_IN_FIRST_PAGE)) 184 185 #else // PACK_FIRST_PAGE_WITH_CONTINUATIONS 186 187 #define MAPS_TO_CONTS_PADDING BYTES_LEFT_IN_FIRST_PAGE 188 189 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS 190 191 #define AFTER_CONTS_PADDING (BYTES_PER_MAGAZINE - (BYTES_PER_PAGE + \ 192 (DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_MAGAZINE))) 193 194 // This is the object our allocator allocates: a chunk of memory rounded up 195 // from sizeof(struct dispatch_continuation_s) to the cacheline size, so 196 // unrelated continuations don't share cachelines. It'd be nice if 197 // dispatch_continuation_s included this rounding/padding, but it doesn't. 198 typedef char padded_continuation[DISPATCH_CONTINUATION_SIZE] __aligned(8); 199 200 // A dispatch_heap_t is the base address of an array of dispatch_magazine_s, 201 // one magazine per CPU. 202 typedef struct dispatch_magazine_s * dispatch_heap_t; 203 204 struct dispatch_magazine_header_s { 205 // Link to the next heap in the chain. Only used in magazine 0's header 206 dispatch_heap_t dh_next; 207 208 // Points to the first bitmap in the page where this CPU succesfully 209 // allocated a continuation last time. Only used in the first heap. 210 bitmap_t *last_found_page; 211 }; 212 213 // A magazine is a complex data structure. It must be exactly 214 // PAGES_PER_MAGAZINE * PAGE_SIZE bytes long, and that value must be a 215 // power of 2. (See magazine_for_continuation()). 216 struct dispatch_magazine_s { 217 // See above. 218 struct dispatch_magazine_header_s header; 219 220 // Align supermaps as needed. 221 #if HEADER_TO_SUPERMAPS_PADDING > 0 222 char _pad0[HEADER_TO_SUPERMAPS_PADDING]; 223 #endif 224 225 // Second-level bitmap; each set bit means a bitmap_t in maps[][] 226 // is completely full (and can be skipped while searching). 227 bitmap_t supermaps[SUPERMAPS_PER_MAGAZINE]; 228 229 // Align maps to a cacheline. 230 #if SUPERMAPS_TO_MAPS_PADDING > 0 231 char _pad1[SUPERMAPS_TO_MAPS_PADDING]; 232 #endif 233 234 // Each bit in maps[][] is the free/used state of a member of conts[][][]. 235 bitmap_t maps[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP]; 236 237 // Align fp_maps to a cacheline. 238 #if MAPS_TO_FPMAPS_PADDING > 0 239 char _pad2[MAPS_TO_FPMAPS_PADDING]; 240 #endif 241 242 #if PACK_FIRST_PAGE_WITH_CONTINUATIONS 243 // Bitmaps for the continuations that live in the first page, which 244 // are treated specially (they have faster search code). 245 bitmap_t fp_maps[BITMAPS_IN_FIRST_PAGE]; 246 247 // Align fp_conts to cacheline. 248 #if FPMAPS_TO_FPCONTS_PADDING > 0 249 char _pad3[FPMAPS_TO_FPCONTS_PADDING]; 250 #endif 251 252 // Continuations that live in the first page. 253 padded_continuation fp_conts[CONTINUATIONS_IN_FIRST_PAGE]; 254 255 #else // PACK_FIRST_PAGE_WITH_CONTINUATIONS 256 257 #if MAPS_TO_CONTS_PADDING > 0 258 char _pad4[MAPS_TO_CONTS_PADDING]; 259 #endif 260 #endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS 261 262 // This is the big array of continuations. 263 // This must start on a page boundary. 264 padded_continuation conts[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP] 265 [CONTINUATIONS_PER_BITMAP]; 266 267 // Fill the unused space to exactly BYTES_PER_MAGAZINE 268 #if AFTER_CONTS_PADDING > 0 269 char _pad5[AFTER_CONTS_PADDING]; 270 #endif 271 }; 272 273 #if DISPATCH_DEBUG 274 #define DISPATCH_ALLOCATOR_SCRIBBLE ((uintptr_t)0xAFAFAFAFAFAFAFAF) 275 #endif 276 277 #endif // DISPATCH_ALLOCATOR 278 279 #endif // __DISPATCH_ALLOCATOR_INTERNAL__ 280