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.cc_max_logical 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#if TARGET_OS_EMBEDDED 88#define PAGES_PER_MAGAZINE 64 89#else 90#define PAGES_PER_MAGAZINE 512 91#endif 92 93// Use the largest type your platform is comfortable doing atomic ops with. 94#if defined(__x86_64__) // TODO: rdar://11477843 95typedef unsigned long bitmap_t; 96#define BYTES_PER_BITMAP 8 97#else 98typedef uint32_t bitmap_t; 99#define BYTES_PER_BITMAP 4 100#endif 101 102#define BITMAP_C(v) ((bitmap_t)(v)) 103#define BITMAP_ALL_ONES (~BITMAP_C(0)) 104 105// Stop configuring. 106 107#define CONTINUATIONS_PER_BITMAP (BYTES_PER_BITMAP * 8) 108#define BITMAPS_PER_SUPERMAP (BYTES_PER_SUPERMAP * 8) 109 110#define BYTES_PER_MAGAZINE (PAGES_PER_MAGAZINE * PAGE_SIZE) 111#define CONSUMED_BYTES_PER_BITMAP (BYTES_PER_BITMAP + \ 112 (DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_BITMAP)) 113 114#define BYTES_PER_SUPERMAP BYTES_PER_BITMAP 115#define CONSUMED_BYTES_PER_SUPERMAP (BYTES_PER_SUPERMAP + \ 116 (BITMAPS_PER_SUPERMAP * CONSUMED_BYTES_PER_BITMAP)) 117 118#define BYTES_PER_HEAP (BYTES_PER_MAGAZINE * MAGAZINES_PER_HEAP) 119 120#define BYTES_PER_PAGE PAGE_SIZE 121#define CONTINUATIONS_PER_PAGE (BYTES_PER_PAGE / DISPATCH_CONTINUATION_SIZE) 122#define BITMAPS_PER_PAGE (CONTINUATIONS_PER_PAGE / CONTINUATIONS_PER_BITMAP) 123 124// Assumption: metadata will be only in the first page. 125#define SUPERMAPS_PER_MAGAZINE ((BYTES_PER_MAGAZINE - BYTES_PER_PAGE) / \ 126 CONSUMED_BYTES_PER_SUPERMAP) 127#define BITMAPS_PER_MAGAZINE (SUPERMAPS_PER_MAGAZINE * BITMAPS_PER_SUPERMAP) 128#define CONTINUATIONS_PER_MAGAZINE \ 129 (BITMAPS_PER_MAGAZINE * CONTINUATIONS_PER_BITMAP) 130 131#define HEAP_MASK (~(uintptr_t)(BYTES_PER_HEAP - 1)) 132#define MAGAZINE_MASK (~(uintptr_t)(BYTES_PER_MAGAZINE - 1)) 133 134#define PADDING_TO_CONTINUATION_SIZE(x) (ROUND_UP_TO_CONTINUATION_SIZE(x) - (x)) 135 136#if defined(__LP64__) 137#define SIZEOF_HEADER 16 138#else 139#define SIZEOF_HEADER 8 140#endif 141 142#define SIZEOF_SUPERMAPS (BYTES_PER_SUPERMAP * SUPERMAPS_PER_MAGAZINE) 143#define SIZEOF_MAPS (BYTES_PER_BITMAP * BITMAPS_PER_SUPERMAP * \ 144 SUPERMAPS_PER_MAGAZINE) 145 146// header is expected to end on supermap's required alignment 147#define HEADER_TO_SUPERMAPS_PADDING 0 148#define SUPERMAPS_TO_MAPS_PADDING (PADDING_TO_CONTINUATION_SIZE( \ 149 SIZEOF_SUPERMAPS + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_HEADER)) 150#define MAPS_TO_FPMAPS_PADDING (PADDING_TO_CONTINUATION_SIZE(SIZEOF_MAPS)) 151 152#define BYTES_LEFT_IN_FIRST_PAGE (BYTES_PER_PAGE - \ 153 (SIZEOF_HEADER + HEADER_TO_SUPERMAPS_PADDING + SIZEOF_SUPERMAPS + \ 154 SUPERMAPS_TO_MAPS_PADDING + SIZEOF_MAPS + MAPS_TO_FPMAPS_PADDING)) 155 156#if PACK_FIRST_PAGE_WITH_CONTINUATIONS 157 158#define FULL_BITMAPS_IN_FIRST_PAGE \ 159 (BYTES_LEFT_IN_FIRST_PAGE / CONSUMED_BYTES_PER_BITMAP) 160#define REMAINDER_IN_FIRST_PAGE (BYTES_LEFT_IN_FIRST_PAGE - \ 161 (FULL_BITMAPS_IN_FIRST_PAGE * CONSUMED_BYTES_PER_BITMAP) - \ 162 (FULL_BITMAPS_IN_FIRST_PAGE ? 0 : ROUND_UP_TO_CONTINUATION_SIZE(BYTES_PER_BITMAP))) 163 164#define REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE \ 165 (REMAINDER_IN_FIRST_PAGE / DISPATCH_CONTINUATION_SIZE) 166#define CONTINUATIONS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE * \ 167 CONTINUATIONS_PER_BITMAP) + REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE 168#define BITMAPS_IN_FIRST_PAGE (FULL_BITMAPS_IN_FIRST_PAGE + \ 169 (REMAINDERED_CONTINUATIONS_IN_FIRST_PAGE == 0 ? 0 : 1)) 170 171#define FPMAPS_TO_FPCONTS_PADDING (PADDING_TO_CONTINUATION_SIZE(\ 172 BYTES_PER_BITMAP * BITMAPS_IN_FIRST_PAGE)) 173 174#else // PACK_FIRST_PAGE_WITH_CONTINUATIONS 175 176#define MAPS_TO_CONTS_PADDING BYTES_LEFT_IN_FIRST_PAGE 177 178#endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS 179 180#define AFTER_CONTS_PADDING (BYTES_PER_MAGAZINE - (BYTES_PER_PAGE + \ 181 (DISPATCH_CONTINUATION_SIZE * CONTINUATIONS_PER_MAGAZINE))) 182 183// This is the object our allocator allocates: a chunk of memory rounded up 184// from sizeof(struct dispatch_continuation_s) to the cacheline size, so 185// unrelated continuations don't share cachelines. It'd be nice if 186// dispatch_continuation_s included this rounding/padding, but it doesn't. 187typedef char padded_continuation[DISPATCH_CONTINUATION_SIZE]; 188 189// A dispatch_heap_t is the base address of an array of dispatch_magazine_s, 190// one magazine per CPU. 191typedef struct dispatch_magazine_s * dispatch_heap_t; 192 193struct dispatch_magazine_header_s { 194 // Link to the next heap in the chain. Only used in magazine 0's header 195 dispatch_heap_t dh_next; 196 197 // Points to the first bitmap in the page where this CPU succesfully 198 // allocated a continuation last time. Only used in the first heap. 199 bitmap_t *last_found_page; 200}; 201 202// A magazine is a complex data structure. It must be exactly 203// PAGES_PER_MAGAZINE * PAGE_SIZE bytes long, and that value must be a 204// power of 2. (See magazine_for_continuation()). 205struct dispatch_magazine_s { 206 // See above. 207 struct dispatch_magazine_header_s header; 208 209 // Align supermaps as needed. 210#if HEADER_TO_SUPERMAPS_PADDING > 0 211 char _pad0[HEADER_TO_SUPERMAPS_PADDING]; 212#endif 213 214 // Second-level bitmap; each set bit means a bitmap_t in maps[][] 215 // is completely full (and can be skipped while searching). 216 bitmap_t supermaps[SUPERMAPS_PER_MAGAZINE]; 217 218 // Align maps to a cacheline. 219#if SUPERMAPS_TO_MAPS_PADDING > 0 220 char _pad1[SUPERMAPS_TO_MAPS_PADDING]; 221#endif 222 223 // Each bit in maps[][] is the free/used state of a member of conts[][][]. 224 bitmap_t maps[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP]; 225 226 // Align fp_maps to a cacheline. 227#if MAPS_TO_FPMAPS_PADDING > 0 228 char _pad2[MAPS_TO_FPMAPS_PADDING]; 229#endif 230 231#if PACK_FIRST_PAGE_WITH_CONTINUATIONS 232 // Bitmaps for the continuations that live in the first page, which 233 // are treated specially (they have faster search code). 234 bitmap_t fp_maps[BITMAPS_IN_FIRST_PAGE]; 235 236 // Align fp_conts to cacheline. 237#if FPMAPS_TO_FPCONTS_PADDING > 0 238 char _pad3[FPMAPS_TO_FPCONTS_PADDING]; 239#endif 240 241 // Continuations that live in the first page. 242 padded_continuation fp_conts[CONTINUATIONS_IN_FIRST_PAGE]; 243 244#else // PACK_FIRST_PAGE_WITH_CONTINUATIONS 245 246#if MAPS_TO_CONTS_PADDING > 0 247 char _pad4[MAPS_TO_CONTS_PADDING]; 248#endif 249#endif // PACK_FIRST_PAGE_WITH_CONTINUATIONS 250 251 // This is the big array of continuations. 252 // This must start on a page boundary. 253 padded_continuation conts[SUPERMAPS_PER_MAGAZINE][BITMAPS_PER_SUPERMAP] 254 [CONTINUATIONS_PER_BITMAP]; 255 256 // Fill the unused space to exactly BYTES_PER_MAGAZINE 257#if AFTER_CONTS_PADDING > 0 258 char _pad5[AFTER_CONTS_PADDING]; 259#endif 260}; 261 262#if DISPATCH_DEBUG 263#define DISPATCH_ALLOCATOR_SCRIBBLE ((uintptr_t)0xAFAFAFAFAFAFAFAF) 264#endif 265 266#endif // DISPATCH_ALLOCATOR 267 268#endif // __DISPATCH_ALLOCATOR_INTERNAL__ 269