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 ZoneCollectors.cpp 22 Zone Scanning Algorithms 23 Copyright (c) 2009-2001 Apple Inc. All rights reserved. 24 */ 25 26#include "ReferenceIterator.h" 27#include "Zone.h" 28 29namespace Auto { 30 31 // BitmapPendingStack uses the pending bitmap as its store. 32 template <typename ReferenceIterator> class BitmapPendingStack { 33 public: 34 ReferenceIterator *_scanner; 35 CollectionTimer *_collection_timer; 36 pthread_mutex_t _scan_mutex; 37 pthread_cond_t _scan_cond; 38 Region *_scan_region; 39 SubzoneRangeIterator _subzone_iterator; 40 Large *_scan_large; 41 usword_t _scanning_threads; 42 bool _pendedLargeBlock; 43 bool _pendedSubzoneBlock; 44 45 BitmapPendingStack() : _scanner(NULL), _collection_timer(NULL), _subzone_iterator(NULL), _scanning_threads(0), _pendedLargeBlock(false), _pendedSubzoneBlock(false) 46 { 47 pthread_mutex_init(&_scan_mutex, NULL); 48 pthread_cond_init(&_scan_cond, NULL); 49 } 50 51 const PendingStackHint hints() { return PendingStackIsFixedSize | PendingStackChecksPendingBitmap | PendingStackSupportsThreadedScan; } 52 53 void set_timer(CollectionTimer *timer) { _collection_timer = timer; } 54 55 void push(Subzone *subzone, usword_t q) { 56 if (!subzone->test_and_set_pending(q, false)) { 57 _pendedSubzoneBlock = true; 58 Subzone::PendingCountAccumulator *accumulator = (Subzone::PendingCountAccumulator *)subzone->region()->zone()->registered_thread().pending_count_accumulator(); 59 if (accumulator) 60 accumulator->pended_in_subzone(subzone); 61 else 62 subzone->add_pending_count(1); 63 } 64 } 65 66 void push(Large *large) { 67 _pendedLargeBlock = true; 68 large->set_pending(); 69 } 70 71 static bool mark(Subzone *subzone, usword_t q) { return subzone->test_and_set_mark(q); } 72 static bool mark(Large *large) { return large->test_and_set_mark(); } 73 bool is_marked(Subzone *subzone, usword_t q) { return subzone->is_marked(q); } 74 bool is_marked(Large *large) { return large->is_marked(); } 75 76 void visit(Zone *zone, Large *large) { 77 Subzone::PendingCountAccumulator info(zone->registered_thread()); 78 CollectionTimer::ScanTimer timer; 79 if (_collection_timer) timer.start(); 80 if (large->is_pending()) { 81 worker_print("scanning large %p\n", large); 82 large->clear_pending(); 83 _scanner->scan(large); 84 zone->statistics().add_blocks_scanned(1); 85 zone->statistics().add_bytes_scanned(large->size()); 86 } 87 if (_collection_timer) { 88 timer.stop(); 89 _collection_timer->scan_timer().add_time(timer); 90 } 91 } 92 93 void visit(Zone *zone, Subzone *sz) { 94 usword_t blocks_scanned = 0; 95 usword_t bytes_scanned = 0; 96 Subzone::PendingCountAccumulator info(zone->registered_thread()); 97 CollectionTimer::ScanTimer timer; 98 if (_collection_timer) timer.start(); 99 worker_print("scanning subzone %p\n", sz); 100 int32_t scanned_count; 101 do { 102 Bitmap::AtomicCursor cursor = sz->pending_cursor(); 103 scanned_count = 0; 104 usword_t q = cursor.next_set_bit(); 105 while (q != (usword_t)-1) { 106 if (!sz->is_free(q)) { 107 _scanner->scan(sz, q); 108 blocks_scanned++; 109 bytes_scanned += sz->size(q); 110 } 111 scanned_count++; 112 q = cursor.next_set_bit(); 113 } 114 info.flush_count(); 115 } while (sz->add_pending_count(-scanned_count) != 0); 116 if (_collection_timer) { 117 timer.stop(); 118 _collection_timer->scan_timer().add_time(timer); 119 } 120 zone->statistics().add_blocks_scanned(blocks_scanned); 121 zone->statistics().add_bytes_scanned(bytes_scanned); 122 } 123 124 const inline bool visit_larges_concurrently() const { return true; } 125 126 void scan(ReferenceIterator &scanner) { 127 _scanner = &scanner; 128 do { 129 _pendedSubzoneBlock = false; 130 _pendedLargeBlock = false; 131 visitAllocatedBlocks_concurrent(_scanner->zone(), *this); 132 } while (_pendedSubzoneBlock || _pendedLargeBlock); 133 } 134 135 template <typename U> struct rebind { typedef BitmapPendingStack<U> other; }; 136 }; 137 138 class PartialCollectionVisitor { 139 protected: 140 struct Configuration; 141 typedef ReferenceIterator<Configuration> PartialReferenceIterator; 142 143 struct Configuration { 144 typedef PartialCollectionVisitor ReferenceVisitor; 145 typedef BitmapPendingStack<PartialReferenceIterator> PendingStack; 146 typedef GenerationalScanningStrategy<PartialReferenceIterator> ScanningStrategy; 147 }; 148 149 public: 150 void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {} 151 void visit(const ReferenceInfo &info, void **slot, Large *large) {} 152 153 void scan(Zone *zone, void *stack_bottom, CollectionTimer &timer) { 154 Configuration::PendingStack stack; 155 const bool should_enliven = true; 156 PartialReferenceIterator scanner(zone, *this, stack, stack_bottom, should_enliven, zone->repair_write_barrier()); 157 if (timer.scan_timer_enabled()) 158 stack.set_timer(&timer); 159 scanner.scan(); 160 } 161 }; 162 163 class FullCollectionVisitor { 164 protected: 165 struct Configuration; 166 typedef ReferenceIterator<Configuration> FullReferenceIterator; 167 struct Configuration { 168 typedef FullCollectionVisitor ReferenceVisitor; 169 typedef BitmapPendingStack<FullReferenceIterator> PendingStack; 170 typedef FullScanningStrategy<FullReferenceIterator> ScanningStrategy; 171 }; 172 public: 173 void visit(const ReferenceInfo &info, void **slot, Subzone *subzone, usword_t q) {} 174 void visit(const ReferenceInfo &info, void **slot, Large *large) {} 175 176 void scan(Zone *zone, void *stack_bottom, CollectionTimer &timer) { 177 Configuration::PendingStack stack; 178 const bool should_enliven = true, dont_repair = false; 179 FullReferenceIterator scanner(zone, *this, stack, stack_bottom, should_enliven, dont_repair); 180 if (timer.scan_timer_enabled()) 181 stack.set_timer(&timer); 182 scanner.scan(); 183 } 184 185 const boolean_t keep_statistics() const { return true; } 186 }; 187 188 // 189 // collect_partial 190 // 191 // Performs a partial (generational) collection. 192 // 193 void Zone::collect_partial(void *current_stack_bottom, CollectionTimer &timer) { 194 PartialCollectionVisitor visitor; 195 visitor.scan(this, current_stack_bottom, timer); 196 } 197 198 // 199 // collect_full 200 // 201 void Zone::collect_full(void *current_stack_bottom, CollectionTimer &timer) { 202 FullCollectionVisitor visitor; 203 visitor.scan(this, current_stack_bottom, timer); 204 } 205 206} // namespace Auto 207