1/* 2 * Copyright (c) 2011 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 Configuration.h 22 Garbage collector allocator parameters 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24*/ 25 26#pragma once 27#ifndef __AUTO_CONFIGURATION__ 28#define __AUTO_CONFIGURATION__ 29 30#include "Definitions.h" 31 32/* 33 The collector suballocates memory in multiples of 3 different quanta sizes, small, medium, and large. 34 Medium is 64*small, large is 64*medium. 35 (64 is a maximum derived from the leftover bits in a secondary 'admin' byte. It is more formally maximum_quanta) 36 The collector is presented to the rest of the system as a malloc-style "Zone" as well as with more 37 direct entry points. The zone contains two Admin data structures - one for blocks of sizes in small 38 quanta sized multiples, and one for those of medium quanta multiples. Each Admin principally maintains 39 64 freelists of blocks indexed by the quanta multiple (e.g. list[3] contains a chain of 3*quanta sized blocks). 40 The Zone also maintains a linked list of large quanta allocations that are directly allocated from the system 41 on 32-bit systems (or come from the top of the arena on 64-bit). 42 43 A "Region" is a data structure that manages a large virtual memory space of "subzone"s, each subzone 44 is dedicated to either small or medium quanta (multiples) allocation blocks. Subzones are allocated on large 45 power of two boundaries such that simple masking can quickly access administrative data stored in the first 46 few words of each. 47 The zone maintains a bitmap for all subzones in use so as to help easily deny false pointers. Also in this subzone area at 48 the beginning is space for all the write-barrier bytes and the allocation administrative data. 49 50 Regions are chained together. Apart from bitmaps used during collections, they principly serve as sources of 51 as yet unused subzones for when an Admin exhausts its freelist and its new area subzone. 52 53 Large quanta objects are freely allocated on large quanta alignment, and are tracked in their own bitmap 54 again to easily deny false pointers. There is administrative data (the "Auto::Large" instance) that 55 actually starts on that alignment - the data provided to the client is an offset from that alignment. 56 It is is thus very cheap to find the collector's admin data for an allocated block. 57 58 59 If the "Arena" logic is used, all Regions and Large quanta objects are actually suballocated from a fixed 60 sized 'Arena' that is allocated at the beginning. This is useful on 64-bit systems where the bitmaps for 61 all large or even subzones would be too huge to search if, say, the kernel handed out widely dispersed 62 large allocations. Its also useful if space is at a premium in 32-bit worlds. 63 64 */ 65 66// 67// Notes: 68// 1M subzone - 8K (2 pages) required for a 128 byte quantum write barrier 69// - 16 bytes (4 words) unused at beginning of each subzone 70// subzone_size / (write_barrier_quantum * write_barrier_quantum) 71// - 1 page is 256 x 16 byte quantum 72// or 64 bytes in allocation bit map blocked out for write barrier 73// 32 bit world - contains 1M of pages 74// - contains 4096 1M subzones 75// 512 (128 words) byte bit map required 76// - 32K (8 pages) bit map required to mark every page 77// - 8k (2 pages) bit map required to mark 64K quantum (large allocations) 78// 16 byte quantum - 64K worth per subzone 79// 64K (16 pages) required for side data 80// 1024 quantum - 1024 worth per subzone 81// 1024 bytes (1/4 page) required for side data 82// 64K large quantum - 64K worth per 32 bit world 83// - 32K (8 pages) per bit map 84// 85 86// 87// On 64-bit systems we can't keep maps of every 1M subzone or, worse, 64K Large quantum. 88// Instead, we preallocate an Arena and suballocate both Large nodes and Regions of small/medium 89// quanta from that space. The Arena can be of any reasonable power of two size on that power of two boundary. 90// 91// Note: Arenas have not been tested on 32-bit 92// Note: Only an Arena size of 4G has been tested on 64-bit 93 94#if defined(__x86_64__) 95# define UseArena 1 96#else 97# define UseArena 0 98#endif 99 100namespace Auto { 101 102 enum { 103 // pointer size 104 105#if defined(__x86_64__) 106 pointer_size_log2 = 3, 107#else 108 pointer_size_log2 = 2, 109#endif 110 111 // Maximum number of quanta per allocation (64) in the small and medium admins 112 maximum_quanta_log2 = 6u, 113 maximum_quanta = (1ul << maximum_quanta_log2), 114 115 // small allocation quantum size (16/32) 116#if defined(__x86_64__) 117 allocate_quantum_small_log2 = 5u, // 32 byte quantum (FreeBlock is 32 bytes) 118#elif defined(__i386__) || defined(__arm__) 119 allocate_quantum_small_log2 = 4u, // 16 byte quantum 120#else 121#error unknown architecture 122#endif 123 allocate_quantum_small = (1ul << allocate_quantum_small_log2), 124 125 // medium allocation quantum size (1024/2048 bytes) 126 allocate_quantum_medium_log2 = (allocate_quantum_small_log2 + maximum_quanta_log2), 127 allocate_quantum_medium = (1ul << allocate_quantum_medium_log2), 128 129 // large allocation quantum size (64K/128K bytes) aka memory quantum 130 allocate_quantum_large_log2 = (allocate_quantum_medium_log2 + maximum_quanta_log2), 131 allocate_quantum_large = (1ul << allocate_quantum_large_log2), 132 133 // arena size 134#if defined(__x86_64__) 135 arena_size_log2 = 34ul, // 16G 136#elif defined(__i386__) 137 arena_size_log2 = 32ul, // 4G 138#elif defined(__arm__) 139 arena_size_log2 = 27ul, // 128MB 140#else 141#error unknown architecture 142#endif 143 144 // maximum number of large quantum that can be allocated 145 allocate_quantum_large_max_log2 = arena_size_log2 - allocate_quantum_large_log2, 146 allocate_quantum_large_max = (1ul << allocate_quantum_large_max_log2), 147 148 // subzone quantum size (2^20 == 1M) 149 subzone_quantum_log2 = 20u, 150 subzone_quantum = (1ul << subzone_quantum_log2), 151 152 // bytes needed per subzone to represent a bitmap of smallest quantum 153 subzone_bitmap_bytes_log2 = subzone_quantum_log2 - allocate_quantum_small_log2 - 3, // 3 == byte_log2 154 subzone_bitmap_bytes = (1ul << subzone_bitmap_bytes_log2), 155 156 bitmaps_per_region = 3, // _pending, _marks, _pinned 157 158 // maximum number of subzone quantum that can be allocated 159 subzone_quantum_max_log2 = arena_size_log2 - subzone_quantum_log2, 160 subzone_quantum_max = (1ul << subzone_quantum_max_log2), 161 162 // initial subzone allocation attempt 163 initial_subzone_count = 128u, 164 165 // minimum subzone allocation (one for each quantum type) 166 initial_subzone_min_count = 2u, 167 168 // number of bytes in write barrier quantum (card == 128 bytes) 169 write_barrier_quantum_log2 = 7u, 170 write_barrier_quantum = (1ul << write_barrier_quantum_log2), 171 172 // maximum number of write barrier bytes per subzone 173 subzone_write_barrier_max = (subzone_quantum >> write_barrier_quantum_log2), 174 175 // largest quanta multiple cached 176 max_cached_small_multiple = 3, 177 178 // number of small_quantum lists cached on a per-thread basis 179 cached_lists_count = 1+max_cached_small_multiple, // we don't use 0 180 181 // number of nodes allocated per cached list 182 cached_list_node_initial_count = 10, 183 184 // maximum number of local blocks allowed (per thread) 185 local_allocations_size_limit = 2000, 186 }; 187 188}; 189 190#endif // __AUTO_CONFIGURATION__ 191