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 BlockRef.h 22 Block sieve helper classes. 23 Copyright (c) 2010-2011 Apple Inc. All rights reserved. 24 */ 25 26#include "Subzone.h" 27#include "Large.h" 28#include "Zone.h" 29#include "Admin.h" 30 31namespace Auto { 32 33 class SubzoneBlockRef { 34 Subzone * const _subzone; 35 const usword_t _q; 36 37 public: 38 SubzoneBlockRef(Subzone *subzone, usword_t q) : _subzone(subzone), _q(q) {} 39 SubzoneBlockRef(void *ptr) : _subzone(Subzone::subzone(ptr)), _q(_subzone->quantum_index_unchecked(ptr)) {} 40 41 inline Subzone * subzone() const { return _subzone; } 42 inline usword_t q() const { return _q; } 43 44 inline Zone * zone() const { return subzone()->admin()->zone(); } 45 inline usword_t size() const { return subzone()->size(q()); } 46 inline void * address() const { return subzone()->quantum_address(q()); } 47 inline bool has_refcount() const { return subzone()->has_refcount(q()); } 48 inline bool is_garbage() const { return subzone()->is_garbage(q()); } 49 inline bool is_scanned() const { return ::is_scanned(layout()); } 50 inline bool is_object() const { return ::is_object(layout()); } 51 inline auto_memory_type_t layout() const { return subzone()->layout(q()); } 52 inline bool is_thread_local() const { return subzone()->is_thread_local(q()); } 53 inline bool is_live_thread_local() const { return subzone()->is_live_thread_local(q()); } 54 inline bool is_local_garbage() const { return subzone()->is_local_garbage(q()); } 55 inline bool should_scan_local_block() const { return subzone()->should_scan_local_block(q()); } 56 inline void set_scan_local_block() const { subzone()->set_scan_local_block(q()); } 57 inline void mark_card(const void *addr) const { if (is_scanned()) subzone()->write_barrier().mark_card((void *)addr); } 58 inline bool is_new() const { return subzone()->is_new(q()); } 59 inline bool is_marked() const { return subzone()->is_marked(q()); } 60 inline void get_description(char *buf, usword_t bufsz) const { snprintf(buf, bufsz, "Subzone=%p, q=%ld", subzone(), (long)q()); } 61 inline void make_global() const { subzone()->make_global(q()); } 62 inline void set_layout(auto_memory_type_t layout) const { subzone()->set_layout(q(), layout); } 63 64 inline void enliven() const { 65 if (!subzone()->test_and_set_mark(q()) && subzone()->is_scanned(q())) 66 subzone()->test_and_set_pending(q(), true); 67 } 68 69 usword_t refcount() const; 70 usword_t inc_refcount() const; 71 usword_t dec_refcount_no_lock() const; 72 usword_t dec_refcount() const; 73 }; 74 75 class LargeBlockRef { 76 Large * const _large; 77 78 public: 79 LargeBlockRef(Large *large) : _large(large) {} 80 81 inline Large * large() const { return _large; } 82 83 inline Zone * zone() const { return _large->zone(); } 84 inline usword_t size() const { return large()->size(); } 85 inline bool has_refcount() const { return refcount() != 0; } 86 inline void * address() const { return _large->address(); } 87 inline bool is_garbage() const { return _large->is_garbage(); } 88 inline bool is_scanned() const { return _large->is_scanned(); } 89 inline bool is_object() const { return _large->is_object(); } 90 inline auto_memory_type_t layout() const { return _large->layout(); } 91 inline bool is_thread_local() const { return false; } 92 inline bool is_live_thread_local() const { return false; } 93 inline bool is_local_garbage() const { return false; } 94 inline bool should_scan_local_block() const { return false; } 95 inline void set_scan_local_block() const { } 96 inline void mark_card(const void *addr) const { if (is_scanned()) _large->write_barrier().mark_card((void *)addr); } 97 inline bool is_new() const { return _large->is_new(); } 98 inline bool is_marked() const { return _large->is_marked(); } 99 inline void get_description(char *buf, usword_t bufsz) const { snprintf(buf, bufsz, "Large=%p", _large); } 100 inline void make_global() const { } 101 inline void set_layout(auto_memory_type_t layout) const { _large->set_layout(layout); } 102 103 inline void enliven() const { 104 if (!_large->test_and_set_mark() && _large->is_scanned()) 105 _large->set_pending(); 106 } 107 108 inline usword_t refcount() const { return _large->refcount(); } 109 usword_t inc_refcount() const; 110 usword_t dec_refcount_no_lock() const; 111 usword_t dec_refcount() const; 112 }; 113 114 class sieve_base { 115 public: 116 // 117 // sieve_base_pointer 118 // 119 // This template function is used to determine whether an arbitrary pointer is a block start, and dispatches 120 // to a handler based on the type of block. The sieve must implement: 121 // void processBlock(SubzoneBlockRef ref); 122 // void processBlock(LargeBlockRef ref); 123 // void nonBlock(void *ptr); 124 // The intended use of this function is to be a fast dispatcher based on the type of block. As such it is 125 // intended to be inlined, and all the sieve functions are intended to be inlined. 126 template <class Sieve> static inline void sieve_base_pointer(Zone *zone, const void *ptr, Sieve &sieve) TEMPLATE_INLINE { 127 if (auto_expect_true(zone->address_in_arena(ptr))) { 128 if (auto_expect_true(zone->in_subzone_bitmap((void *)ptr))) { 129 Subzone *sz = Subzone::subzone((void *)ptr); 130 usword_t q; 131 if (auto_expect_true(sz->block_is_start((void *)ptr, &q))) { 132 SubzoneBlockRef block(sz, q); 133 sieve.processBlock(block); 134 } else { 135 sieve.nonBlock(ptr); 136 } 137 } else if (auto_expect_true(zone->block_is_start_large((void *)ptr))) { 138 LargeBlockRef block(Large::large((void *)ptr)); 139 sieve.processBlock(block); 140 } else { 141 sieve.nonBlock(ptr); 142 } 143 } else { 144 sieve.nonBlock(ptr); 145 } 146 } 147 148 // 149 // auto_base_pointer_sieve 150 // 151 // This template function is used to determine whether an arbitrary pointer is a pointer into a block, and dispatches 152 // to a handler based on the type of block. The sieve must implement: 153 // void processBlock(SubzoneBlockRef ref); 154 // void processBlock(LargeBlockRef ref); 155 // void nonBlock(void *ptr); 156 // The intended use of this function is to be a fast dispatcher based on the type of block. As such it is 157 // intended to be inlined, and all the sieve functions are intended to be inlined. 158 template <class Sieve> static inline void sieve_interior_pointer(Zone *zone, const void *ptr, Sieve &sieve) TEMPLATE_INLINE { 159 if (auto_expect_true(zone->address_in_arena(ptr))) { 160 if (auto_expect_true(zone->in_subzone_bitmap((void *)ptr))) { 161 Subzone *sz = Subzone::subzone((void *)ptr); 162 usword_t q; 163 if (auto_expect_true(sz->block_start((void *)ptr, q) != NULL)) { 164 SubzoneBlockRef block(sz, q); 165 sieve.processBlock(block); 166 } else { 167 sieve.nonBlock(ptr); 168 } 169 } else { 170 // BlockRef FIXME: block_start_large contains a redundant check of the coverage 171 Large *large = zone->block_start_large((void *)ptr); 172 if (auto_expect_true(large != NULL)) { 173 LargeBlockRef block(large); 174 sieve.processBlock(block); 175 } else { 176 sieve.nonBlock(ptr); 177 } 178 } 179 } else { 180 sieve.nonBlock(ptr); 181 } 182 } 183 184 inline void nonBlock(const void *ptr) { 185 } 186 }; 187 188 // Sieve classes for use with auto_pointer_sieve and auto_base_pointer_sieve 189 190 enum { 191 AUTO_BLOCK_INFO_IS_BLOCK = 0, // we always record whether it is a block or not 192 AUTO_BLOCK_INFO_LAYOUT = 1, 193 AUTO_BLOCK_INFO_SIZE = 2, 194 AUTO_BLOCK_INFO_REFCOUNT = 4, 195 AUTO_BLOCK_INFO_BASE_POINTER = 8, 196 }; 197 198 // Sieve class that records information about a block. 199 // If AUTO_BLOCK_INFO_BASE_POINTER is specified then ptr may be an interior pointer. 200 template <int requested_info> class auto_block_info_sieve : public sieve_base { 201 private: 202 auto_memory_type_t _layout; 203 usword_t _refcount; 204 size_t _size; 205 boolean_t _is_block; 206 void *_base; 207 208 public: 209 auto_block_info_sieve(Zone *zone, const void *ptr) __attribute__((always_inline)) { 210 if (requested_info & AUTO_BLOCK_INFO_BASE_POINTER) { 211 sieve_interior_pointer(zone, ptr, *this); 212 } else { 213 sieve_base_pointer(zone, ptr, *this); 214 } 215 } 216 217 template <class BlockRef> void processBlock(BlockRef ref) TEMPLATE_INLINE { 218 _is_block = true; 219 if (requested_info & AUTO_BLOCK_INFO_LAYOUT) 220 _layout = ref.layout(); 221 if (requested_info & AUTO_BLOCK_INFO_SIZE) 222 _size = ref.size(); 223 if (requested_info & AUTO_BLOCK_INFO_REFCOUNT) 224 _refcount = ref.refcount(); 225 if (requested_info & AUTO_BLOCK_INFO_BASE_POINTER) 226 _base = ref.address(); 227 } 228 229 void nonBlock(const void *ptr) __attribute__((always_inline)) { 230 _is_block = false; 231 if (requested_info & AUTO_BLOCK_INFO_LAYOUT) 232 _layout = AUTO_TYPE_UNKNOWN; 233 if (requested_info & AUTO_BLOCK_INFO_SIZE) 234 _size = 0; 235 if (requested_info & AUTO_BLOCK_INFO_REFCOUNT) 236 _refcount = 0; 237 if (requested_info & AUTO_BLOCK_INFO_BASE_POINTER) 238 _base = NULL; 239 } 240 241 inline boolean_t is_block() const { return _is_block; } 242 inline auto_memory_type_t layout() const { if (!(requested_info & AUTO_BLOCK_INFO_LAYOUT)) __builtin_trap(); return _layout; } 243 inline size_t size() const { if (!(requested_info & AUTO_BLOCK_INFO_SIZE)) __builtin_trap(); return _size; } 244 inline usword_t refcount() const { if (!(requested_info & AUTO_BLOCK_INFO_REFCOUNT)) __builtin_trap(); return _refcount; } 245 inline void * base() const { if (!(requested_info & AUTO_BLOCK_INFO_BASE_POINTER)) __builtin_trap(); return _base; } 246 }; 247 248 enum { 249 AUTO_REFCOUNT_INCREMENT, 250 AUTO_REFCOUNT_DECREMENT 251 }; 252 253 // Sieve class that deallocates a block. 254 template <int refcount_op> class auto_refcount_sieve : public sieve_base { 255 public: 256 Zone *zone; 257 usword_t refcount; 258 259 inline auto_refcount_sieve(Zone *z, const void *ptr) __attribute__((always_inline)) : zone(z), refcount(0) { 260 sieve_base_pointer(zone, ptr, *this); 261 } 262 263 template <class BlockRef> inline void processBlock(BlockRef ref) TEMPLATE_INLINE { 264 if (refcount_op == AUTO_REFCOUNT_INCREMENT) { 265 refcount = zone->block_increment_refcount(ref); 266 } else if (refcount_op == AUTO_REFCOUNT_DECREMENT) { 267 refcount = zone->block_decrement_refcount(ref); 268 } else { 269 __builtin_trap(); 270 } 271 } 272 }; 273} 274