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 Subzone.h 22 Quantized Memory Allocation 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#pragma once 27#ifndef __AUTO_SUBZONE__ 28#define __AUTO_SUBZONE__ 29 30#include "Admin.h" 31#include "Definitions.h" 32#include "Bitmap.h" 33#include "FreeList.h" 34#include "WriteBarrier.h" 35#include "Region.h" 36#import "auto_tester/auto_tester.h" 37#include "auto_zone.h" 38#include "auto_trace.h" 39#include "auto_dtrace.h" 40#include <cassert> 41 42namespace Auto { 43 44 // Forward declarations 45 class Region; 46 class Thread; 47 48 49 //----- Subzone -----// 50 51 // 52 // A subzone is a region in vm memory managed by automatic garbage collection. The base address of the subheap is 53 // aligned to the subzone quantum size such that the containing subzone can be quickly determined from any refererence 54 // into the subzone. 55 // A C++ Subzone object is constructed at this aligned address. The first chunk of memory are the write-barrier cards 56 // that keep track of write-barrier-quantum ranges of objects that have been stored into. 57 // Next are the instance variables including a back pointer to the "admin" that contains the free lists. 58 // Fleshing out the rest are the "admin" data, one per quantum, indicating if its the start of a block etc. 59 // Quantum numbers are used for most operations - the object with quantum 0 starts just after the end of the admin data 60 // at the first quantum boundary opportunity. 61 // There are two quantum sizes that a Subzone can be configured to manage - small and medium. We keep a "bias" so that 62 // in a bitmap of all subzones we can quickly keep it as dense as possible. 63 // 64 65 66 class Subzone : public Preallocated { 67 68 private: 69 unsigned char _write_barrier_cards[subzone_write_barrier_max]; 70 WriteBarrier _write_barrier; 71 // write barrier for subzone - must be first 72 usword_t _quantum_log2; // ilog2 of the quantum used in this admin 73 Region *_region; // region owning this subzone (with bitmaps for these quanta) 74 Admin *_admin; // admin for this subzone (reflecting appropriate quanta size) 75 Subzone *_nextSubzone; // used by admin's _purgeable_subzones list. 76 bool _is_purgeable; // true if this subzone is in admin's _purgeable_subzones list. 77 bool _is_purged; // true if uncommit_memory() was called on the inactive range. 78 usword_t _quantum_bias; // the value added to subzone quantum numbers to get a globally 79 // unique quantum (used to index region pending/mark bits) 80 void *_allocation_address; // base address for allocations 81 usword_t _in_use; // high water mark 82 unsigned char * volatile _checking_counts; // collection checking counts, by quantum index 83 volatile int32_t _pending_count; 84 bool _is_being_scanned; 85 unsigned char _side_data[1]; // base for side data 86 87 enum { 88 /* 89 A quantum with start_bit set indicates the beginning of a block, which may be either allocated or free. 90 The block is allocated if any of the remaining bits are nonzero. If all are zero then the block is free. 91 Minimally, if a block is allocated either global_bit, or alloc_local_bit, or the garbage bit will be set. 92 The block size for an allocated block beginning at quanta q is determined by examining the side data at quanta q+1. 93 If the start bit at q+1 is set then the block size is 1 quanta. If the start bit at q+1 is not set then the remaining 94 bits hold the block size (in units of quanta.) 95 The block size for a unallocated block can be inferred from the free list it is on. 96 */ 97 98 start_bit_log2 = 7, 99 start_bit = 0x1 << start_bit_log2, // indicates beginning of block 100 101 /* 102 The layout indicates whether the block is an object and whether it is scanned. Even when a block is marked 103 as garbage the scanned bit is important because the background collector needs to scan through even local garbage 104 to find references - otherwise it might win a race and deallocate something that will be referenced in a finalize 105 run by the local collector. 106 */ 107 layout_log2 = 4, 108 layout_mask = 0x7 << layout_log2, // indicates block organization 109 110 /* 111 The global bit is consulted in order to determine the interpretation of all remaining bits. 112 When global bit == 1, the age and refcount bits are valid. 113 When global bit == 0, alloc_local_bit and garbage_bit are valid. 114 When garbage_bit == 1, refcount bit is again valid since blocks may be marked external in a finalize method. 115 When garbage_bit == 0, scan_local_bit is valid. 116 */ 117 global_bit_log2 = 0, 118 global_bit = 0x1 << global_bit_log2, // indicates thread locality of block. 0 -> thread local, 1 -> global 119 120 garbage_bit_log2 = 2, 121 garbage_bit = 0x1 << garbage_bit_log2, // iff global == 0. marks garbage, alloc_local_bit marks if local. 122 123 alloc_local_bit_log2 = 1, 124 alloc_local_bit = 0x1 << alloc_local_bit_log2, // iff global == 0. marks that a block is thread local 125 126 scan_local_bit_log2 = 3, 127 scan_local_bit = 0x1 << scan_local_bit_log2, // iff global == 0, alloc_local == 1. marks thread local to be scanned 128 129 refcount_log2 = 3, 130 refcount_bit = 0x1 << refcount_log2, // if global_bit == 1 else garbage_bit == 1. holds inline refcount 131 132 age_mask_log2 = 1, 133 age_mask = 0x3 << age_mask_log2, // iff global_bit == 1. block age bits for background collector 134 135 /* Interesting age values. */ 136 youngest_age = 3, 137 eldest_age = 0, 138 139 quanta_size_mask = 0x7f, // quanta size mask for blocks of quanta size 2+ 140 }; 141 142 // Does a side data value represent the youngest age (includes thread local)? 143 static inline bool is_youngest(unsigned char sd) { return ((sd & age_mask)>>age_mask_log2) == youngest_age; } 144 145 // Does a side data value represent the eldest age? 146 static inline bool is_eldest(unsigned char sd) { return ((sd & age_mask)>>age_mask_log2) == eldest_age; } 147 148 // 149 // subzone_side_data_max 150 // 151 // Given a constant quantum_log2 returns a constant (optimized code) defining 152 // the maximum number of quantum in the subzone. 153 // 154 static inline usword_t subzone_side_data_max(usword_t quantum_log2) { 155 // size of subzone data (non quantum) less size of side data 156 usword_t header_size = sizeof(Subzone) - sizeof(unsigned char); 157 // quantum size plus one byte for side data 158 usword_t bytes_per_quantum = (1LL << quantum_log2) + 1; 159 // round up the maximum number quantum (max out side data) 160 return (subzone_quantum - header_size + bytes_per_quantum - 1) / bytes_per_quantum; 161 } 162 163 164 // 165 // subzone_base_data_size 166 // 167 // Given a constant quantum_log2 returns a constant (optimized code) defining 168 // the size of the non quantum data rounded up to a the nearest quantum. 169 // 170 static inline usword_t subzone_base_data_size(usword_t quantum_log2) { 171 return align2(sizeof(Subzone) - sizeof(unsigned char) + subzone_side_data_max(quantum_log2), quantum_log2); 172 } 173 174 175 // 176 // subzone_allocation_size 177 // 178 // Given a constant quantum_log2 returns a constant (optimized code) defining 179 // the size of the area available for allocating quantum. 180 // 181 static inline usword_t subzone_allocation_size(usword_t quantum_log2) { 182 return subzone_quantum - subzone_base_data_size(quantum_log2); 183 } 184 185 186 // 187 // subzone_allocation_limit 188 // 189 // Given a constant quantum_log2 returns a constant (optimized code) defining 190 // the number of the quantum that can be allocated. 191 // 192 static inline usword_t subzone_allocation_limit(usword_t quantum_log2) { 193 return partition2(subzone_allocation_size(quantum_log2), quantum_log2); 194 } 195 196 197 public: 198 199 200 // 201 // Constructor 202 // 203 Subzone(Region *region, Admin *admin, usword_t quantum_log2, usword_t quantum_bias) 204 : _write_barrier(_write_barrier_cards, _write_barrier_cards, WriteBarrier::bytes_needed(subzone_quantum)), 205 _quantum_log2(quantum_log2), _region(region), _admin(admin), _nextSubzone(NULL), _is_purgeable(false), _is_purged(false), 206 _quantum_bias(quantum_bias), _allocation_address(NULL), _in_use(0), _pending_count(0), _is_being_scanned(false) 207 { 208 usword_t base_data_size = is_small() ? 209 subzone_base_data_size(allocate_quantum_small_log2) : 210 subzone_base_data_size(allocate_quantum_medium_log2); 211 _allocation_address = (void *)displace(this, base_data_size); 212 } 213 214 215 // 216 // Destructor 217 // 218 ~Subzone(); 219 220 221 // pack/unpack a subzone/quantum index pair into a single pointer sized value 222 inline uintptr_t pack(usword_t q) { 223 assert(q <= 65536); 224 assert(uintptr_t(this) == (uintptr_t(this) & ~0x1FFFF)); 225 return (uintptr_t)this | q; 226 } 227 static Subzone *unpack(uintptr_t packed, usword_t &q) { 228 q = ((usword_t)packed & 0x1FFFF); 229 return (reinterpret_cast<Subzone *>(packed & ~0x1FFFF)); 230 } 231 232 233 // 234 // Accessors 235 // 236 usword_t quantum_log2() const { return _quantum_log2; } 237 Region *region() const { return _region; } 238 Admin *admin() const { return _admin; } 239 240 Subzone *nextSubzone() const { return _nextSubzone; } 241 void setNextSubzone(Subzone *subzone) { _nextSubzone = subzone; } 242 bool is_purgeable() const { return _is_purgeable; } 243 void set_purgeable(bool purgeable) { _is_purgeable = purgeable; } 244 bool is_purged() const { return _is_purged; } 245 void set_purged(bool purged) { _is_purged = purged; } 246 247 // 248 // purgeable_range 249 // 250 // Returns the page aligned range of memory that is free at the end of the subzone. 251 // This range can be passed to madvise() to return the memory to the system. 252 // 253 Range purgeable_range() const { 254 usword_t unused = allocation_limit() - _in_use; 255 usword_t size = quantum_size(unused); 256 if (size >= page_size) { 257 void *address = quantum_address(_in_use); 258 return Range(align_up(address, page_size_log2), align_down(displace(address, size), page_size_log2)); 259 } else { 260 return Range(); 261 } 262 } 263 264 usword_t quantum_bias() const { return _quantum_bias; } 265 266 bool has_pending() const { return _pending_count != 0; } 267 int32_t add_pending_count(int32_t count) { return OSAtomicAdd32(count, &_pending_count); } 268 int32_t pending_count() const { return _pending_count; } // note that this queries a volatile value in an unsynchronized manner 269 bool is_being_scanned() const { return _is_being_scanned; } 270 void set_is_being_scanned(bool p) { _is_being_scanned = p; } 271 272 // 273 // subzone 274 // 275 // Return the subzone of an arbitrary memory address. 276 // 277 static inline Subzone *subzone(void *address) { return (Subzone *)((uintptr_t)address & ~mask(subzone_quantum_log2)); } 278 279 280 // 281 // is_small 282 // 283 // Return true if it is a small admin. 284 // 285 inline bool is_small() const { return _quantum_log2 == allocate_quantum_small_log2; } 286 287 288 // 289 // is_medium 290 // 291 // Return true if it is a medium admin. 292 // 293 inline bool is_medium() const { return _quantum_log2 == allocate_quantum_medium_log2; } 294 295 296 // 297 // allocation_address 298 // 299 // Return the first allocation address in the subzone. 300 // 301 inline void *allocation_address() const { return _allocation_address; } 302 303 304 // 305 // allocation_end 306 // 307 // Return the last allocation address in the subzone. 308 // 309 inline void *allocation_end() { return displace(this, subzone_quantum); } 310 311 312 // 313 // base_data_size 314 // 315 // Return the size of the base data space in the subzone. 316 // 317 inline usword_t base_data_size() const { 318 return is_small() ? subzone_base_data_size(allocate_quantum_small_log2): 319 subzone_base_data_size(allocate_quantum_medium_log2); 320 } 321 322 323 // 324 // base_data_quantum_count 325 // 326 // Return the number quantum of the base data space occupies. 327 // 328 inline usword_t base_data_quantum_count(usword_t quantum_log2) const { 329 return subzone_base_data_size(quantum_log2) >> quantum_log2; 330 } 331 332 333 // 334 // allocation_size 335 // 336 // Return the size of the allocation space in the subzone. 337 // 338 inline usword_t allocation_size() const { 339 return is_small() ? subzone_allocation_size(allocate_quantum_small_log2) : 340 subzone_allocation_size(allocate_quantum_medium_log2); 341 } 342 343 344 // 345 // allocation_limit 346 // 347 // Return the number quantum in the subzone. 348 // 349 inline usword_t allocation_limit() const { 350 return is_small() ? subzone_allocation_limit(allocate_quantum_small_log2) : 351 subzone_allocation_limit(allocate_quantum_medium_log2); 352 } 353 354 355 // 356 // quantum_index 357 // 358 // Returns a quantum index for a arbitrary pointer. 359 // Unless running DEBUG this could be bogus if the pointer refers to the admin (write-barrier) area of a subzone. 360 // Callers must have already done a successful is_start or be prepared to validate against quantum_limit. 361 // 362 inline usword_t quantum_index(void *address, usword_t quantum_log2) const { 363 ASSERTION(quantum_log2 == _quantum_log2); 364 usword_t result = (((uintptr_t)address & mask(subzone_quantum_log2)) >> quantum_log2) - base_data_quantum_count(quantum_log2); 365#if DEBUG 366 if (result > allocation_limit()) { printf("bad quantum index\n"); __builtin_trap(); } 367#endif 368 return result; 369 } 370 inline usword_t quantum_index(void *address) const { 371 return is_small() ? quantum_index(address, allocate_quantum_small_log2) : 372 quantum_index(address, allocate_quantum_medium_log2); 373 } 374 375 376 // 377 // quantum_index_unchecked 378 // 379 // Returns a quantum index for a arbitrary pointer. Might be bogus if the address is in the admin (writebarrier) area. 380 // 381 inline usword_t quantum_index_unchecked(void *address, usword_t quantum_log2) const { 382 ASSERTION(quantum_log2 == _quantum_log2); 383 return (((uintptr_t)address & mask(subzone_quantum_log2)) >> quantum_log2) - base_data_quantum_count(quantum_log2); 384 } 385 inline usword_t quantum_index_unchecked(void *address) const { 386 return is_small() ? quantum_index_unchecked(address, allocate_quantum_small_log2) : 387 quantum_index_unchecked(address, allocate_quantum_medium_log2); 388 } 389 390 391 // 392 // allocation_count 393 // 394 // High water count for this subzone 395 // 396 inline usword_t allocation_count() const { return _in_use; } 397 398 // 399 // add_allocation_count 400 // 401 // High water count for this subzone 402 // 403 inline void raise_allocation_count(usword_t q) { _in_use += q; } 404 405 // 406 // subtract_allocation_count 407 // 408 // High water count for this subzone 409 // 410 inline void lower_allocation_count(usword_t q) { _in_use -= q; } 411 412 // 413 // quantum_count 414 // 415 // Returns the number of quantum for a given size. 416 // 417 inline const usword_t quantum_count(const size_t size) const { 418 return partition2(size, _quantum_log2); 419 } 420 421 422 // 423 // quantum_size 424 // 425 // Returns the size in bytes of n quantum. 426 // 427 inline const usword_t quantum_size(const usword_t n) const { return n << _quantum_log2; } 428 429 430 // 431 // quantum_address 432 // 433 // Returns the address if a specified quantum. 434 // 435 inline void *quantum_address(const usword_t q) const { return displace(_allocation_address, quantum_size(q)); } 436 437 438 // 439 // quantum_range 440 // 441 // Return the range for the block at q. 442 // 443 inline void quantum_range(const usword_t q, Range &range) const { 444 range.set_range(quantum_address(q), size(q)); 445 } 446 447 // 448 // Side data accessors 449 // 450 inline bool is_free(usword_t q) const { return (_side_data[q] & ~start_bit) == 0; } 451 452 inline bool is_start(usword_t q) const { return (_side_data[q] & start_bit) != 0 && !is_free(q); } 453 inline bool block_is_start(usword_t q) const { return q < allocation_limit() && (_side_data[q] & start_bit) != 0 && !is_free(q); } 454 inline bool block_is_start(void *address, usword_t *q) const { 455 return (is_small() ? is_bit_aligned(address, allocate_quantum_small_log2) : 456 is_bit_aligned(address, allocate_quantum_medium_log2)) && 457 block_is_start(*q = quantum_index_unchecked(address)); 458 } 459 460 inline usword_t length(usword_t q) const { 461 usword_t result; 462 if (q == allocation_limit()-1 || (_side_data[q+1] & start_bit)) 463 result = 1; 464 else { 465 // ASSERTION(_side_data[q + 1] != 0); 466 result = _side_data[q+1] & quanta_size_mask; 467 } 468 return result; 469 } 470 471 inline usword_t size(usword_t q) const { return quantum_size(length(q)); } 472 473 inline bool is_new(usword_t q) const { ASSERTION(!is_thread_local(q)); return !is_eldest(_side_data[q]); } 474 475 inline bool is_newest(usword_t q) const { ASSERTION(!is_thread_local(q)); return is_youngest(_side_data[q]); } 476 477 478 inline usword_t age(usword_t q) const { ASSERTION(!is_thread_local(q)); return (_side_data[q] & age_mask) >> age_mask_log2; } 479 480 inline void set_age(usword_t q, usword_t age) { 481 ASSERTION(!is_thread_local(q)); 482 unsigned char data = _side_data[q]; 483 data &= ~age_mask; 484 data |= (age << age_mask_log2); 485 _side_data[q] = data; 486 } 487 488 inline usword_t sideData(void *address) const { return _side_data[quantum_index(address)]; } 489 490 inline void mature(usword_t q) { 491 if (!is_thread_local(q)) { 492 unsigned char data = _side_data[q]; 493 unsigned char current = (data & age_mask) >> age_mask_log2; 494 if (current > eldest_age) { 495 data &= ~age_mask; 496 data |= ((current-1) << age_mask_log2); 497 _side_data[q] = data; 498 AUTO_PROBE(auto_probe_mature(quantum_address(q), current-1)); 499 } 500 } 501 } 502 503 /* Test if the block is marked as thread local in the side data. Note that a true result does not necessarily mean it is local to the calling thread. */ 504 inline bool is_thread_local(usword_t q) const { return (_side_data[q] & (start_bit|alloc_local_bit|global_bit)) == (start_bit|alloc_local_bit); } 505 506 /* Test if the block is thread local and not garbage. Note that a true result does not necessarily mean it is local to the calling thread. */ 507 inline bool is_live_thread_local(usword_t q) const { return (_side_data[q] & (start_bit | alloc_local_bit | global_bit|garbage_bit)) == (start_bit|alloc_local_bit); } 508 509#ifdef MEASURE_TLC_STATS 510 void update_block_escaped_stats(); 511#endif 512 513 // mark a thread-local object as a global one 514 // NOTE: this must be called BEFORE the object can be retained, since it starts the object with rc=0, age=youngest. 515 inline void make_global(usword_t q) { 516 ASSERTION(is_live_thread_local(q)); 517 unsigned char data = _side_data[q]; 518 data &= ~(refcount_bit | age_mask); 519 data |= global_bit | (youngest_age << age_mask_log2); 520 _side_data[q] = data; 521 AUTO_PROBE(auto_probe_make_global(quantum_address(q), youngest_age)); 522 GARBAGE_COLLECTION_AUTO_BLOCK_LOST_THREAD_LOCALITY(quantum_address(q), size(q)); 523#ifdef MEASURE_TLC_STATS 524 update_block_escaped_stats(); 525#endif 526 } 527 528 /* 529 Mark a block as garbage. 530 For global data mark global_bit 0 and garbage_bit 1 531 For local data merely mark the garbage_bit 1 (keeping global_bit 0) 532 When marking garbage also clear the refcount bits since they may get used during finalize, even for local garbage. 533 As is, the full layout is preserved. 534 */ 535 // Theoretically we should be able to assert !is_thread_local(q) here. But due to the way the bits 536 // are encoded the assertion also triggers for a block that was previously marked garbage which was resurrected. 537 // Removing the assertion for sake of the unit tests. 538 inline void mark_global_garbage(usword_t q) { /* ASSERTION(!is_thread_local(q)); */ _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit; } 539 inline bool is_garbage(usword_t q) const { return (_side_data[q] & (start_bit|garbage_bit|global_bit)) == (start_bit|garbage_bit); } 540 inline bool is_global_garbage(usword_t q) const { return !is_thread_local(q) && is_garbage(q); } 541 542 inline void mark_local_garbage(usword_t q) { ASSERTION(is_live_thread_local(q)); _side_data[q] = (_side_data[q] & (start_bit|layout_mask)) | garbage_bit | alloc_local_bit; } 543 inline bool is_local_garbage(usword_t q) const { return (_side_data[q] & (start_bit|garbage_bit|alloc_local_bit)) == (start_bit|garbage_bit|alloc_local_bit); } 544 545 inline bool is_marked(usword_t q) const { return q < allocation_limit() && _region->marks().bit(_quantum_bias + q); } 546 547 inline usword_t layout(usword_t q) const { return (_side_data[q] & layout_mask) >> layout_log2; } 548 549 inline bool is_scanned(usword_t q) const { return !(layout(q) & AUTO_UNSCANNED); } 550 551 inline bool has_refcount(usword_t q) const { return !is_live_thread_local(q) && (_side_data[q] & refcount_bit) != 0; } 552 inline void set_has_refcount(usword_t q) { ASSERTION(!is_live_thread_local(q)); _side_data[q] |= refcount_bit; } 553 inline void clear_has_refcount(usword_t q) { ASSERTION(!is_live_thread_local(q)); _side_data[q] &= ~refcount_bit; } 554 555 inline void set_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); if (is_scanned(q)) _side_data[q] |= scan_local_bit; } 556 557 inline void clear_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); _side_data[q] &= ~scan_local_bit; } 558 559 inline bool should_scan_local_block(usword_t q) { ASSERTION(is_live_thread_local(q)); return (_side_data[q] & scan_local_bit); } 560 561 // mark (if not already marked) 562 // return already-marked 563 inline bool test_and_set_mark(usword_t q) { return _region->test_and_set_mark(_quantum_bias + q); } 564 565 // Used to mark objects ineligible for compaction. 566 inline bool test_and_set_pinned(usword_t q) { return _region->pinned().test_set_bit_atomic(_quantum_bias + q); } 567 inline void mark_pinned(usword_t q) { _region->pinned().set_bit_atomic(_quantum_bias + q); } 568 inline bool is_pinned(usword_t q) { return _region->pinned().bit(_quantum_bias + q); } 569 570 inline bool is_compactable(usword_t q) const { 571 usword_t biased_q = q + _quantum_bias; 572 return _region->marks().bit(biased_q) && !_region->pinned().bit(biased_q); 573 } 574 575 // Used to mark objects that have been forwarded during compaction. 576 inline void mark_forwarded(usword_t q) { _region->pending().set_bit(_quantum_bias + q); } 577 inline void clear_forwarded(usword_t q) { _region->pending().clear_bit(_quantum_bias + q); } 578 inline bool is_forwarded(usword_t q) { return _region->pending().bit(_quantum_bias + q); } 579 580 inline bool test_and_clear_mark(usword_t q) { return _region->test_and_clear_mark(_quantum_bias + q); } 581 582 inline void set_layout(usword_t q, usword_t layout) { 583 unsigned d = _side_data[q]; 584 d &= ~layout_mask; 585 d |= (layout << layout_log2); 586 _side_data[q] = d; 587 } 588 589 inline bool test_and_set_pending(usword_t q, bool adjust_pending_count) { 590 bool result = _region->pending().test_set_bit_atomic(_quantum_bias + q); 591 if (!result && adjust_pending_count) add_pending_count(1); 592 return result; 593 } 594 595 inline bool test_and_clear_pending(usword_t q) { return _region->pending().test_clear_bit_atomic(_quantum_bias + q); } 596 597 inline Bitmap::AtomicCursor pending_cursor() { return Bitmap::AtomicCursor(_region->pending(), _quantum_bias, allocation_limit()); } 598 599 // 600 // is_used 601 // 602 // Return true if the quantum is in a used quantum. 603 // 604 inline bool is_used(usword_t q) const { 605 // any data indicates use 606 if (!is_free(q)) return true; 607 608 // otherwise find the prior start 609 for (usword_t s = q; true; s--) { 610 if (is_start(s)) { 611 usword_t n = length(s); 612 // make sure q is in range 613 return (q - s) < n; 614 } 615 if (!s) break; 616 } 617 return false; 618 } 619 620 // 621 // next_quantum 622 // 623 // Returns the next q for block or free node. 624 // 625 inline usword_t next_quantum(usword_t q = 0) const { 626 usword_t nq; 627 if (is_start(q)) { 628 nq = q + length(q); 629 } else { 630 // FIXME: accessing the free list without holding the allocation lock is a race condition. 631 // SpinLock lock(_admin->lock()); 632 // FreeListNode *node = (FreeListNode *)quantum_address(q); 633 // q = quantum_index(node->next_block()); 634 // Instead, we simply search for the next block start. Note, this means we no longer 635 // return quanta for free blocks. 636 usword_t n = allocation_limit(); 637 nq = q + 1; 638 while (nq < n && !is_start(nq)) ++nq; 639 } 640 // Until <rdar://problem/6404163> is fixed, nq can equal q. This is mostly harmless, because the 641 // caller will keep looping over the same q value, until _side_data[q + 1] is updated. 642 ASSERTION(nq >= q); 643 return nq; 644 } 645 646 inline usword_t next_quantum(usword_t q, MemoryReader & reader) const { 647 return next_quantum(q); 648 } 649 650 // 651 // previous_quantum 652 // 653 // Returns the previous q for block or free node. 654 // 655 inline usword_t previous_quantum(usword_t q) { 656 // find a prior start before the specified q. 657 ASSERTION(q <= allocation_limit()); 658 while (q--) { 659 if (is_start(q)) 660 return q; 661 } 662 return not_found; 663 } 664 665 // 666 // block_start 667 // 668 // Return the start address for the given address. 669 // All clients must (and do) check for NULL return. 670 // 671 inline void * block_start(void *address, usword_t &startq) const { 672 usword_t q = quantum_index_unchecked(address), s = q; 673 // an arbitrary address in our admin area will return a neg (very large) number 674 if (q > allocation_limit()) return NULL; 675 do { 676 if (is_start(s)) { 677 usword_t n = length(s); 678 // make sure q is in range 679 if ((q - s) < n) { 680 startq = s; 681 return quantum_address(s); 682 } 683 return NULL; 684 } 685 } while (s--); 686 return NULL; 687 } 688 689 // 690 // allocate 691 // 692 // Initialize side data for a new block. 693 // 694 inline void allocate(usword_t q, const usword_t n, const usword_t layout, const bool refcount_is_one, const bool is_local) { 695 ASSERTION(n <= maximum_quanta && n > 0); 696 unsigned char sd; 697 sd = start_bit 698 | (layout << layout_log2) 699 | (is_local ? alloc_local_bit : (global_bit | (youngest_age << age_mask_log2))) 700 //| (is_local ? alloc_local_bit : global_bit) // hides allocation microbenchmark issues 701 | (refcount_is_one ? refcount_bit : 0); 702 703 _side_data[q] = sd; 704 if (n > 1) { 705 _side_data[q + 1] = n; 706 _side_data[q + n - 1] = n; 707 } 708 // Only touch the next block if it is zero (free) 709 // Other threads can touching that block's side data (global/local/garbage) 710 if (q+n < allocation_limit() && _side_data[q + n] == 0) 711 _side_data[q + n] |= start_bit; 712 } 713 714 // 715 // cache 716 // 717 // Initialize side data for a cached block. 718 // 719 inline void cache(usword_t q, const usword_t n) { 720 ASSERTION(n <= maximum_quanta && n > 0); 721 _side_data[q] = (start_bit | alloc_local_bit | (AUTO_MEMORY_UNSCANNED << layout_log2) | garbage_bit); 722 if (n > 1) { 723 _side_data[q + 1] = n; 724 _side_data[q + n - 1] = n; 725 } 726 // Only touch the next block if it is zero (free) 727 // Other threads can touching that block's side data (global/local/garbage) 728 if (q+n < allocation_limit() && _side_data[q + n] == 0) 729 _side_data[q + n] |= start_bit; 730 } 731 732 // 733 // deallocate 734 // 735 // Clear side data for an existing block. 736 // 737 inline void deallocate(usword_t q, usword_t len) { 738 bool prev_quanta_allocated = (q > 0 ? (_side_data[q-1] != 0) : false); 739 740 _side_data[q] = prev_quanta_allocated ? start_bit : 0; 741 if (len > 1) { 742 _side_data[q+1] = 0; 743 _side_data[q+len-1] = 0; 744 } 745 if (q+len < allocation_limit()) { 746 if (_side_data[q+len] == start_bit) 747 _side_data[q+len] = 0; 748 } 749 } 750 inline void deallocate(usword_t q) { deallocate(q, length(q)); } 751 752 753 // 754 // write_barrier 755 // 756 // Returns accessor for this subzone's write barrier. 757 // 758 inline WriteBarrier& write_barrier() { 759 return _write_barrier; 760 } 761 762 // 763 // collection_checking_count 764 // 765 // retrieve the collection checking count for a quanta 766 // 767 inline uint32_t collection_checking_count(usword_t q) const { 768 // make a copy of the volatile buffer pointer on the stack so it won't be freed while we are using it 769 unsigned char *counts = _checking_counts; 770 return counts ? counts[q] : 0; 771 } 772 773 774 // 775 // set_collection_checking_count 776 // 777 // set the collection checking count for a quanta, allocates the counts buffer if needed 778 // 779 inline void set_collection_checking_count(usword_t q, uint32_t count) { 780 // if this is the first time checking has been requested then we need to allocate a a buffer to hold the counts 781 // but don't allocate just to clear the count to zero 782 if (_checking_counts == NULL && count != 0) { 783 // Use a collectable buffer to store the check counts. This enables unsynchronized cleanup if/when checking is turned off. 784 // Note that we only get here via a collection checking request from a user thread, never from the collector internally. 785 void *tmp = auto_zone_allocate_object((auto_zone_t *)_admin->zone(), allocation_limit() * sizeof(unsigned char), AUTO_UNSCANNED, true, true); 786 if (!OSAtomicCompareAndSwapPtrBarrier(NULL, tmp, (void * volatile *)(void *)&_checking_counts)) 787 auto_zone_release((auto_zone_t *)_admin->zone(), tmp); 788 } 789 790 // make a copy of the volatile buffer pointer on the stack so it won't be freed while we are using it 791 unsigned char *counts = _checking_counts; 792 if (counts != NULL) { 793 counts[q] = count < 255 ? count : 255; 794 } 795 } 796 797 798 // 799 // reset_collection_checking 800 // 801 // frees the memory buffer used for collection checking 802 // 803 inline void reset_collection_checking() { 804 unsigned char *counts = _checking_counts; 805 if (OSAtomicCompareAndSwapPtrBarrier(counts, NULL, (void * volatile *)(void *)&_checking_counts)) 806 auto_zone_release((auto_zone_t *)_admin->zone(), counts); 807 } 808 809 810 811 // 812 // PendingCountAccumulator 813 // 814 // PendingCountAccumulator is a per-thread buffer to accumulate updates to the subzone pending count. 815 // The accumulator is used during threaded scanning to reduce the total number of atomic updates. 816 // 817 class PendingCountAccumulator { 818 Thread &_thread; 819 Subzone *_last_pended_subzone; 820 usword_t _pended_count; 821 822 public: 823 PendingCountAccumulator(Thread &thread); 824 825 ~PendingCountAccumulator(); 826 827 inline void flush_count() { 828 if (_last_pended_subzone && _pended_count) { 829 _last_pended_subzone->add_pending_count(_pended_count); 830 _pended_count = 0; 831 } 832 } 833 834 inline void pended_in_subzone(Subzone *sz) { 835 if (_last_pended_subzone != sz) { 836 if (_pended_count) { 837 flush_count(); 838 } 839 _last_pended_subzone = sz; 840 } 841 _pended_count++; 842 } 843 }; 844 845 }; 846 847 848 //----- SubzoneRangeIterator -----// 849 850 // 851 // Iterate over a range of memory 852 // 853 854 class SubzoneRangeIterator : public Range { 855 856 public: 857 858 // 859 // Constructors 860 // 861 SubzoneRangeIterator(void *address, const usword_t size) : Range(address, size) {} 862 SubzoneRangeIterator(void *address, void *end) : Range(address, end) {} 863 SubzoneRangeIterator(Range range) : Range(range) {} 864 865 866 // 867 // iteration_complete 868 // 869 // returns true if the iteration has reached the end and no more entries are available 870 // 871 inline boolean_t iteration_complete() { return !(address() < end()); } 872 873 // 874 // next 875 // 876 // Returns next subzone in the range or NULL if no more entries available. 877 // 878 inline Subzone *next() { 879 // if cursor is still in range 880 if (address() < end()) { 881 // capture cursor position 882 Subzone *subzone = (Subzone *)address(); 883 // advance for next call 884 set_address(displace(subzone, subzone_quantum)); 885 // return captured cursor position 886 return subzone; 887 } 888 889 // at end 890 return NULL; 891 } 892 893 // 894 // previous 895 // 896 // Returns previous subzone in the range or NULL if no more entries available. 897 // 898 inline Subzone *previous() { 899 if (end() > address()) { 900 Subzone *prev = (Subzone *)displace(end(), -subzone_quantum); 901 set_end(prev); 902 return prev; 903 } 904 return NULL; 905 } 906 }; 907 908}; 909 910 911#endif // __AUTO_SUBZONE__ 912 913