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 WriteBarrier.cpp 22 Write Barrier for Generational GC 23 Copyright (c) 2004-2011 Apple Inc. All rights reserved. 24 */ 25 26#include "Configuration.h" 27#include "Definitions.h" 28#include "Range.h" 29#include "WriteBarrier.h" 30#include "Zone.h" 31 32 33namespace Auto { 34 35 //----- WriteBarrier -----// 36 37 38 // 39 // scan_marked_ranges 40 // 41 // Scan ranges in block that are marked in the write barrier. 42 // 43 void WriteBarrier::scan_marked_ranges(void *address, const usword_t size, write_barrier_scanner_t scanner) { 44 // determine the end address 45 void *end = displace(address, size); 46 // determine the last used address 47 void *last = displace(address, size - 1); 48 // get the write barrier index for the begining of the block 49 usword_t i = card_index(address); 50 // get the write barrier index for the end of the block 51 const usword_t j = card_index(last); 52 53 Range sub_range; 54 while (true) { 55 // skip over unmarked ranges 56 for ( ; i <= j && !is_card_marked(i); i++) {} 57 58 // if no marks then we are done 59 if (i > j) break; 60 61 // scan the marks 62 usword_t k = i; 63 for ( ; i <= j && is_card_marked(i); i++) {} 64 65 // set up the begin and end of the marked range 66 void *range_begin = card_address(k); 67 void *range_end = card_address(i); 68 69 // truncate the range to reflect address range 70 if (range_begin < address) range_begin = address; 71 if (range_end > end) range_end = end; 72 73 // scan range 74 sub_range.set_range(range_begin, range_end); 75 scanner(sub_range, this); 76 } 77 } 78 79#ifndef __BLOCKS__ 80 class write_barrier_scanner_helper : public WriteBarrier::write_barrier_scanner { 81 void (*_scanner) (Range&, WriteBarrier*, void*); 82 void *_arg; 83 public: 84 write_barrier_scanner_helper(void (*scanner) (const Range&, WriteBarrier*, void*), void *arg) : _scanner(scanner), _arg(arg) {} 85 virtual void operator() (const Range &range, WriteBarrier *wb) { _scanner(range, wb, _arg); } 86 }; 87#endif 88 89 void WriteBarrier::scan_marked_ranges(void *address, const usword_t size, void (*scanner) (const Range&, WriteBarrier*, void*), void *arg) { 90#ifdef __BLOCKS__ 91 scan_marked_ranges(address, size, ^(const Range &range, WriteBarrier *wb) { scanner(range, wb, arg); }); 92#else 93 write_barrier_scanner_helper helper(scanner, arg); 94 scan_marked_ranges(address, size, helper); 95#endif 96 } 97 98 bool WriteBarrier::range_has_marked_cards(void *address, const usword_t size) { 99 void *last = displace(address, size - 1); 100 // get the write barrier index for the begining of the block 101 usword_t i = card_index(address); 102 // get the write barrier index for the end of the block 103 const usword_t j = card_index(last); 104 while (i <= j) if (is_card_marked(i++)) return true; 105 return false; 106 } 107 108 inline bool compare_and_swap(unsigned char *card, unsigned char old_value, unsigned char new_value) { 109#if defined(__arm__) 110 // <rdar://problem/7001590> FIXME: use LDREX/STREX. 111 if (*card == old_value) { 112 *card = new_value; 113 return true; 114 } 115 return false; 116#else 117 return __sync_bool_compare_and_swap(card, old_value, new_value); 118#endif 119 } 120 121 // this should only called from Zone::mark_write_barriers_untouched(). 122 usword_t WriteBarrier::mark_cards_untouched() { 123 usword_t count = 0; 124 for (unsigned char *card = (unsigned char*)address() + _protect, *limit = (unsigned char *)end(); card != limit; ++card) { 125 if (*card != card_unmarked) { 126 if (compare_and_swap(card, (unsigned char)card_marked, (unsigned char)card_marked_untouched)) 127 ++count; 128 } 129 } 130 return count; 131 } 132 133 // this should only called from Zone::clear_untouched_write_barriers(). 134 usword_t WriteBarrier::clear_untouched_cards() { 135 usword_t count = 0; 136 for (unsigned char *card = (unsigned char*)address() + _protect, *limit = (unsigned char *)end(); card != limit; ++card) { 137 if (*card == card_marked_untouched) { 138 if (compare_and_swap(card, (unsigned char)card_marked_untouched, (unsigned char)card_unmarked)) 139 ++count; 140 } 141 } 142 return count; 143 } 144}; 145