Mon, 26 Jan 2009 12:47:21 -0800
6786503: Overflow list performance can be improved
Summary: Avoid overflow list walk in CMS & ParNew when it is unnecessary. Fix a couple of correctness issues, including a C-heap leak, in ParNew at the intersection of promotion failure, work queue overflow and object array chunking. Add stress testing option and related assertion checking.
Reviewed-by: jmasa
duke@435 | 1 | /* |
xdono@631 | 2 | * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved. |
duke@435 | 3 | * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
duke@435 | 4 | * |
duke@435 | 5 | * This code is free software; you can redistribute it and/or modify it |
duke@435 | 6 | * under the terms of the GNU General Public License version 2 only, as |
duke@435 | 7 | * published by the Free Software Foundation. |
duke@435 | 8 | * |
duke@435 | 9 | * This code is distributed in the hope that it will be useful, but WITHOUT |
duke@435 | 10 | * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or |
duke@435 | 11 | * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License |
duke@435 | 12 | * version 2 for more details (a copy is included in the LICENSE file that |
duke@435 | 13 | * accompanied this code). |
duke@435 | 14 | * |
duke@435 | 15 | * You should have received a copy of the GNU General Public License version |
duke@435 | 16 | * 2 along with this work; if not, write to the Free Software Foundation, |
duke@435 | 17 | * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. |
duke@435 | 18 | * |
duke@435 | 19 | * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, |
duke@435 | 20 | * CA 95054 USA or visit www.sun.com if you need additional information or |
duke@435 | 21 | * have any questions. |
duke@435 | 22 | * |
duke@435 | 23 | */ |
duke@435 | 24 | |
duke@435 | 25 | # include "incls/_precompiled.incl" |
duke@435 | 26 | # include "incls/_cardTableRS.cpp.incl" |
duke@435 | 27 | |
duke@435 | 28 | CardTableRS::CardTableRS(MemRegion whole_heap, |
duke@435 | 29 | int max_covered_regions) : |
ysr@777 | 30 | GenRemSet(), |
ysr@777 | 31 | _cur_youngergen_card_val(youngergenP1_card), |
ysr@777 | 32 | _regions_to_iterate(max_covered_regions - 1) |
duke@435 | 33 | { |
ysr@777 | 34 | #ifndef SERIALGC |
ysr@777 | 35 | if (UseG1GC) { |
ysr@777 | 36 | if (G1RSBarrierUseQueue) { |
ysr@777 | 37 | _ct_bs = new G1SATBCardTableLoggingModRefBS(whole_heap, |
ysr@777 | 38 | max_covered_regions); |
ysr@777 | 39 | } else { |
ysr@777 | 40 | _ct_bs = new G1SATBCardTableModRefBS(whole_heap, max_covered_regions); |
ysr@777 | 41 | } |
ysr@777 | 42 | } else { |
ysr@777 | 43 | _ct_bs = new CardTableModRefBSForCTRS(whole_heap, max_covered_regions); |
ysr@777 | 44 | } |
ysr@777 | 45 | #else |
ysr@777 | 46 | _ct_bs = new CardTableModRefBSForCTRS(whole_heap, max_covered_regions); |
ysr@777 | 47 | #endif |
ysr@777 | 48 | set_bs(_ct_bs); |
duke@435 | 49 | _last_cur_val_in_gen = new jbyte[GenCollectedHeap::max_gens + 1]; |
duke@435 | 50 | if (_last_cur_val_in_gen == NULL) { |
duke@435 | 51 | vm_exit_during_initialization("Could not last_cur_val_in_gen array."); |
duke@435 | 52 | } |
duke@435 | 53 | for (int i = 0; i < GenCollectedHeap::max_gens + 1; i++) { |
duke@435 | 54 | _last_cur_val_in_gen[i] = clean_card_val(); |
duke@435 | 55 | } |
ysr@777 | 56 | _ct_bs->set_CTRS(this); |
duke@435 | 57 | } |
duke@435 | 58 | |
duke@435 | 59 | void CardTableRS::resize_covered_region(MemRegion new_region) { |
ysr@777 | 60 | _ct_bs->resize_covered_region(new_region); |
duke@435 | 61 | } |
duke@435 | 62 | |
duke@435 | 63 | jbyte CardTableRS::find_unused_youngergenP_card_value() { |
duke@435 | 64 | for (jbyte v = youngergenP1_card; |
duke@435 | 65 | v < cur_youngergen_and_prev_nonclean_card; |
duke@435 | 66 | v++) { |
duke@435 | 67 | bool seen = false; |
ysr@777 | 68 | for (int g = 0; g < _regions_to_iterate; g++) { |
duke@435 | 69 | if (_last_cur_val_in_gen[g] == v) { |
duke@435 | 70 | seen = true; |
duke@435 | 71 | break; |
duke@435 | 72 | } |
duke@435 | 73 | } |
duke@435 | 74 | if (!seen) return v; |
duke@435 | 75 | } |
duke@435 | 76 | ShouldNotReachHere(); |
duke@435 | 77 | return 0; |
duke@435 | 78 | } |
duke@435 | 79 | |
duke@435 | 80 | void CardTableRS::prepare_for_younger_refs_iterate(bool parallel) { |
duke@435 | 81 | // Parallel or sequential, we must always set the prev to equal the |
duke@435 | 82 | // last one written. |
duke@435 | 83 | if (parallel) { |
duke@435 | 84 | // Find a parallel value to be used next. |
duke@435 | 85 | jbyte next_val = find_unused_youngergenP_card_value(); |
duke@435 | 86 | set_cur_youngergen_card_val(next_val); |
duke@435 | 87 | |
duke@435 | 88 | } else { |
duke@435 | 89 | // In an sequential traversal we will always write youngergen, so that |
duke@435 | 90 | // the inline barrier is correct. |
duke@435 | 91 | set_cur_youngergen_card_val(youngergen_card); |
duke@435 | 92 | } |
duke@435 | 93 | } |
duke@435 | 94 | |
duke@435 | 95 | void CardTableRS::younger_refs_iterate(Generation* g, |
duke@435 | 96 | OopsInGenClosure* blk) { |
duke@435 | 97 | _last_cur_val_in_gen[g->level()+1] = cur_youngergen_card_val(); |
duke@435 | 98 | g->younger_refs_iterate(blk); |
duke@435 | 99 | } |
duke@435 | 100 | |
duke@435 | 101 | class ClearNoncleanCardWrapper: public MemRegionClosure { |
duke@435 | 102 | MemRegionClosure* _dirty_card_closure; |
duke@435 | 103 | CardTableRS* _ct; |
duke@435 | 104 | bool _is_par; |
duke@435 | 105 | private: |
duke@435 | 106 | // Clears the given card, return true if the corresponding card should be |
duke@435 | 107 | // processed. |
duke@435 | 108 | bool clear_card(jbyte* entry) { |
duke@435 | 109 | if (_is_par) { |
duke@435 | 110 | while (true) { |
duke@435 | 111 | // In the parallel case, we may have to do this several times. |
duke@435 | 112 | jbyte entry_val = *entry; |
duke@435 | 113 | assert(entry_val != CardTableRS::clean_card_val(), |
duke@435 | 114 | "We shouldn't be looking at clean cards, and this should " |
duke@435 | 115 | "be the only place they get cleaned."); |
duke@435 | 116 | if (CardTableRS::card_is_dirty_wrt_gen_iter(entry_val) |
duke@435 | 117 | || _ct->is_prev_youngergen_card_val(entry_val)) { |
duke@435 | 118 | jbyte res = |
duke@435 | 119 | Atomic::cmpxchg(CardTableRS::clean_card_val(), entry, entry_val); |
duke@435 | 120 | if (res == entry_val) { |
duke@435 | 121 | break; |
duke@435 | 122 | } else { |
duke@435 | 123 | assert(res == CardTableRS::cur_youngergen_and_prev_nonclean_card, |
duke@435 | 124 | "The CAS above should only fail if another thread did " |
duke@435 | 125 | "a GC write barrier."); |
duke@435 | 126 | } |
duke@435 | 127 | } else if (entry_val == |
duke@435 | 128 | CardTableRS::cur_youngergen_and_prev_nonclean_card) { |
duke@435 | 129 | // Parallelism shouldn't matter in this case. Only the thread |
duke@435 | 130 | // assigned to scan the card should change this value. |
duke@435 | 131 | *entry = _ct->cur_youngergen_card_val(); |
duke@435 | 132 | break; |
duke@435 | 133 | } else { |
duke@435 | 134 | assert(entry_val == _ct->cur_youngergen_card_val(), |
duke@435 | 135 | "Should be the only possibility."); |
duke@435 | 136 | // In this case, the card was clean before, and become |
duke@435 | 137 | // cur_youngergen only because of processing of a promoted object. |
duke@435 | 138 | // We don't have to look at the card. |
duke@435 | 139 | return false; |
duke@435 | 140 | } |
duke@435 | 141 | } |
duke@435 | 142 | return true; |
duke@435 | 143 | } else { |
duke@435 | 144 | jbyte entry_val = *entry; |
duke@435 | 145 | assert(entry_val != CardTableRS::clean_card_val(), |
duke@435 | 146 | "We shouldn't be looking at clean cards, and this should " |
duke@435 | 147 | "be the only place they get cleaned."); |
duke@435 | 148 | assert(entry_val != CardTableRS::cur_youngergen_and_prev_nonclean_card, |
duke@435 | 149 | "This should be possible in the sequential case."); |
duke@435 | 150 | *entry = CardTableRS::clean_card_val(); |
duke@435 | 151 | return true; |
duke@435 | 152 | } |
duke@435 | 153 | } |
duke@435 | 154 | |
duke@435 | 155 | public: |
duke@435 | 156 | ClearNoncleanCardWrapper(MemRegionClosure* dirty_card_closure, |
duke@435 | 157 | CardTableRS* ct) : |
duke@435 | 158 | _dirty_card_closure(dirty_card_closure), _ct(ct) { |
duke@435 | 159 | _is_par = (SharedHeap::heap()->n_par_threads() > 0); |
duke@435 | 160 | } |
duke@435 | 161 | void do_MemRegion(MemRegion mr) { |
duke@435 | 162 | // We start at the high end of "mr", walking backwards |
duke@435 | 163 | // while accumulating a contiguous dirty range of cards in |
duke@435 | 164 | // [start_of_non_clean, end_of_non_clean) which we then |
duke@435 | 165 | // process en masse. |
duke@435 | 166 | HeapWord* end_of_non_clean = mr.end(); |
duke@435 | 167 | HeapWord* start_of_non_clean = end_of_non_clean; |
duke@435 | 168 | jbyte* entry = _ct->byte_for(mr.last()); |
duke@435 | 169 | const jbyte* first_entry = _ct->byte_for(mr.start()); |
duke@435 | 170 | while (entry >= first_entry) { |
duke@435 | 171 | HeapWord* cur = _ct->addr_for(entry); |
duke@435 | 172 | if (!clear_card(entry)) { |
duke@435 | 173 | // We hit a clean card; process any non-empty |
duke@435 | 174 | // dirty range accumulated so far. |
duke@435 | 175 | if (start_of_non_clean < end_of_non_clean) { |
duke@435 | 176 | MemRegion mr2(start_of_non_clean, end_of_non_clean); |
duke@435 | 177 | _dirty_card_closure->do_MemRegion(mr2); |
duke@435 | 178 | } |
duke@435 | 179 | // Reset the dirty window while continuing to |
duke@435 | 180 | // look for the next dirty window to process. |
duke@435 | 181 | end_of_non_clean = cur; |
duke@435 | 182 | start_of_non_clean = end_of_non_clean; |
duke@435 | 183 | } |
duke@435 | 184 | // Open the left end of the window one card to the left. |
duke@435 | 185 | start_of_non_clean = cur; |
duke@435 | 186 | // Note that "entry" leads "start_of_non_clean" in |
duke@435 | 187 | // its leftward excursion after this point |
duke@435 | 188 | // in the loop and, when we hit the left end of "mr", |
duke@435 | 189 | // will point off of the left end of the card-table |
duke@435 | 190 | // for "mr". |
duke@435 | 191 | entry--; |
duke@435 | 192 | } |
duke@435 | 193 | // If the first card of "mr" was dirty, we will have |
duke@435 | 194 | // been left with a dirty window, co-initial with "mr", |
duke@435 | 195 | // which we now process. |
duke@435 | 196 | if (start_of_non_clean < end_of_non_clean) { |
duke@435 | 197 | MemRegion mr2(start_of_non_clean, end_of_non_clean); |
duke@435 | 198 | _dirty_card_closure->do_MemRegion(mr2); |
duke@435 | 199 | } |
duke@435 | 200 | } |
duke@435 | 201 | }; |
duke@435 | 202 | // clean (by dirty->clean before) ==> cur_younger_gen |
duke@435 | 203 | // dirty ==> cur_youngergen_and_prev_nonclean_card |
duke@435 | 204 | // precleaned ==> cur_youngergen_and_prev_nonclean_card |
duke@435 | 205 | // prev-younger-gen ==> cur_youngergen_and_prev_nonclean_card |
duke@435 | 206 | // cur-younger-gen ==> cur_younger_gen |
duke@435 | 207 | // cur_youngergen_and_prev_nonclean_card ==> no change. |
coleenp@548 | 208 | void CardTableRS::write_ref_field_gc_par(void* field, oop new_val) { |
duke@435 | 209 | jbyte* entry = ct_bs()->byte_for(field); |
duke@435 | 210 | do { |
duke@435 | 211 | jbyte entry_val = *entry; |
duke@435 | 212 | // We put this first because it's probably the most common case. |
duke@435 | 213 | if (entry_val == clean_card_val()) { |
duke@435 | 214 | // No threat of contention with cleaning threads. |
duke@435 | 215 | *entry = cur_youngergen_card_val(); |
duke@435 | 216 | return; |
duke@435 | 217 | } else if (card_is_dirty_wrt_gen_iter(entry_val) |
duke@435 | 218 | || is_prev_youngergen_card_val(entry_val)) { |
duke@435 | 219 | // Mark it as both cur and prev youngergen; card cleaning thread will |
duke@435 | 220 | // eventually remove the previous stuff. |
duke@435 | 221 | jbyte new_val = cur_youngergen_and_prev_nonclean_card; |
duke@435 | 222 | jbyte res = Atomic::cmpxchg(new_val, entry, entry_val); |
duke@435 | 223 | // Did the CAS succeed? |
duke@435 | 224 | if (res == entry_val) return; |
duke@435 | 225 | // Otherwise, retry, to see the new value. |
duke@435 | 226 | continue; |
duke@435 | 227 | } else { |
duke@435 | 228 | assert(entry_val == cur_youngergen_and_prev_nonclean_card |
duke@435 | 229 | || entry_val == cur_youngergen_card_val(), |
duke@435 | 230 | "should be only possibilities."); |
duke@435 | 231 | return; |
duke@435 | 232 | } |
duke@435 | 233 | } while (true); |
duke@435 | 234 | } |
duke@435 | 235 | |
duke@435 | 236 | void CardTableRS::younger_refs_in_space_iterate(Space* sp, |
duke@435 | 237 | OopsInGenClosure* cl) { |
ysr@777 | 238 | DirtyCardToOopClosure* dcto_cl = sp->new_dcto_cl(cl, _ct_bs->precision(), |
duke@435 | 239 | cl->gen_boundary()); |
duke@435 | 240 | ClearNoncleanCardWrapper clear_cl(dcto_cl, this); |
duke@435 | 241 | |
ysr@777 | 242 | _ct_bs->non_clean_card_iterate(sp, sp->used_region_at_save_marks(), |
duke@435 | 243 | dcto_cl, &clear_cl, false); |
duke@435 | 244 | } |
duke@435 | 245 | |
duke@435 | 246 | void CardTableRS::clear_into_younger(Generation* gen, bool clear_perm) { |
duke@435 | 247 | GenCollectedHeap* gch = GenCollectedHeap::heap(); |
duke@435 | 248 | // Generations younger than gen have been evacuated. We can clear |
duke@435 | 249 | // card table entries for gen (we know that it has no pointers |
duke@435 | 250 | // to younger gens) and for those below. The card tables for |
duke@435 | 251 | // the youngest gen need never be cleared, and those for perm gen |
duke@435 | 252 | // will be cleared based on the parameter clear_perm. |
duke@435 | 253 | // There's a bit of subtlety in the clear() and invalidate() |
duke@435 | 254 | // methods that we exploit here and in invalidate_or_clear() |
duke@435 | 255 | // below to avoid missing cards at the fringes. If clear() or |
duke@435 | 256 | // invalidate() are changed in the future, this code should |
duke@435 | 257 | // be revisited. 20040107.ysr |
duke@435 | 258 | Generation* g = gen; |
duke@435 | 259 | for(Generation* prev_gen = gch->prev_gen(g); |
duke@435 | 260 | prev_gen != NULL; |
duke@435 | 261 | g = prev_gen, prev_gen = gch->prev_gen(g)) { |
duke@435 | 262 | MemRegion to_be_cleared_mr = g->prev_used_region(); |
duke@435 | 263 | clear(to_be_cleared_mr); |
duke@435 | 264 | } |
duke@435 | 265 | // Clear perm gen cards if asked to do so. |
duke@435 | 266 | if (clear_perm) { |
duke@435 | 267 | MemRegion to_be_cleared_mr = gch->perm_gen()->prev_used_region(); |
duke@435 | 268 | clear(to_be_cleared_mr); |
duke@435 | 269 | } |
duke@435 | 270 | } |
duke@435 | 271 | |
duke@435 | 272 | void CardTableRS::invalidate_or_clear(Generation* gen, bool younger, |
duke@435 | 273 | bool perm) { |
duke@435 | 274 | GenCollectedHeap* gch = GenCollectedHeap::heap(); |
duke@435 | 275 | // For each generation gen (and younger and/or perm) |
duke@435 | 276 | // invalidate the cards for the currently occupied part |
duke@435 | 277 | // of that generation and clear the cards for the |
duke@435 | 278 | // unoccupied part of the generation (if any, making use |
duke@435 | 279 | // of that generation's prev_used_region to determine that |
duke@435 | 280 | // region). No need to do anything for the youngest |
duke@435 | 281 | // generation. Also see note#20040107.ysr above. |
duke@435 | 282 | Generation* g = gen; |
duke@435 | 283 | for(Generation* prev_gen = gch->prev_gen(g); prev_gen != NULL; |
duke@435 | 284 | g = prev_gen, prev_gen = gch->prev_gen(g)) { |
duke@435 | 285 | MemRegion used_mr = g->used_region(); |
duke@435 | 286 | MemRegion to_be_cleared_mr = g->prev_used_region().minus(used_mr); |
duke@435 | 287 | if (!to_be_cleared_mr.is_empty()) { |
duke@435 | 288 | clear(to_be_cleared_mr); |
duke@435 | 289 | } |
duke@435 | 290 | invalidate(used_mr); |
duke@435 | 291 | if (!younger) break; |
duke@435 | 292 | } |
duke@435 | 293 | // Clear perm gen cards if asked to do so. |
duke@435 | 294 | if (perm) { |
duke@435 | 295 | g = gch->perm_gen(); |
duke@435 | 296 | MemRegion used_mr = g->used_region(); |
duke@435 | 297 | MemRegion to_be_cleared_mr = g->prev_used_region().minus(used_mr); |
duke@435 | 298 | if (!to_be_cleared_mr.is_empty()) { |
duke@435 | 299 | clear(to_be_cleared_mr); |
duke@435 | 300 | } |
duke@435 | 301 | invalidate(used_mr); |
duke@435 | 302 | } |
duke@435 | 303 | } |
duke@435 | 304 | |
duke@435 | 305 | |
duke@435 | 306 | class VerifyCleanCardClosure: public OopClosure { |
coleenp@548 | 307 | private: |
coleenp@548 | 308 | HeapWord* _boundary; |
coleenp@548 | 309 | HeapWord* _begin; |
coleenp@548 | 310 | HeapWord* _end; |
coleenp@548 | 311 | protected: |
coleenp@548 | 312 | template <class T> void do_oop_work(T* p) { |
duke@435 | 313 | HeapWord* jp = (HeapWord*)p; |
coleenp@548 | 314 | if (jp >= _begin && jp < _end) { |
coleenp@548 | 315 | oop obj = oopDesc::load_decode_heap_oop(p); |
coleenp@548 | 316 | guarantee(obj == NULL || |
coleenp@548 | 317 | (HeapWord*)p < _boundary || |
coleenp@548 | 318 | (HeapWord*)obj >= _boundary, |
duke@435 | 319 | "pointer on clean card crosses boundary"); |
duke@435 | 320 | } |
duke@435 | 321 | } |
coleenp@548 | 322 | public: |
coleenp@548 | 323 | VerifyCleanCardClosure(HeapWord* b, HeapWord* begin, HeapWord* end) : |
coleenp@548 | 324 | _boundary(b), _begin(begin), _end(end) {} |
coleenp@548 | 325 | virtual void do_oop(oop* p) { VerifyCleanCardClosure::do_oop_work(p); } |
coleenp@548 | 326 | virtual void do_oop(narrowOop* p) { VerifyCleanCardClosure::do_oop_work(p); } |
duke@435 | 327 | }; |
duke@435 | 328 | |
duke@435 | 329 | class VerifyCTSpaceClosure: public SpaceClosure { |
coleenp@548 | 330 | private: |
duke@435 | 331 | CardTableRS* _ct; |
duke@435 | 332 | HeapWord* _boundary; |
duke@435 | 333 | public: |
duke@435 | 334 | VerifyCTSpaceClosure(CardTableRS* ct, HeapWord* boundary) : |
duke@435 | 335 | _ct(ct), _boundary(boundary) {} |
coleenp@548 | 336 | virtual void do_space(Space* s) { _ct->verify_space(s, _boundary); } |
duke@435 | 337 | }; |
duke@435 | 338 | |
duke@435 | 339 | class VerifyCTGenClosure: public GenCollectedHeap::GenClosure { |
duke@435 | 340 | CardTableRS* _ct; |
duke@435 | 341 | public: |
duke@435 | 342 | VerifyCTGenClosure(CardTableRS* ct) : _ct(ct) {} |
duke@435 | 343 | void do_generation(Generation* gen) { |
duke@435 | 344 | // Skip the youngest generation. |
duke@435 | 345 | if (gen->level() == 0) return; |
duke@435 | 346 | // Normally, we're interested in pointers to younger generations. |
duke@435 | 347 | VerifyCTSpaceClosure blk(_ct, gen->reserved().start()); |
duke@435 | 348 | gen->space_iterate(&blk, true); |
duke@435 | 349 | } |
duke@435 | 350 | }; |
duke@435 | 351 | |
duke@435 | 352 | void CardTableRS::verify_space(Space* s, HeapWord* gen_boundary) { |
duke@435 | 353 | // We don't need to do young-gen spaces. |
duke@435 | 354 | if (s->end() <= gen_boundary) return; |
duke@435 | 355 | MemRegion used = s->used_region(); |
duke@435 | 356 | |
duke@435 | 357 | jbyte* cur_entry = byte_for(used.start()); |
duke@435 | 358 | jbyte* limit = byte_after(used.last()); |
duke@435 | 359 | while (cur_entry < limit) { |
duke@435 | 360 | if (*cur_entry == CardTableModRefBS::clean_card) { |
duke@435 | 361 | jbyte* first_dirty = cur_entry+1; |
duke@435 | 362 | while (first_dirty < limit && |
duke@435 | 363 | *first_dirty == CardTableModRefBS::clean_card) { |
duke@435 | 364 | first_dirty++; |
duke@435 | 365 | } |
duke@435 | 366 | // If the first object is a regular object, and it has a |
duke@435 | 367 | // young-to-old field, that would mark the previous card. |
duke@435 | 368 | HeapWord* boundary = addr_for(cur_entry); |
duke@435 | 369 | HeapWord* end = (first_dirty >= limit) ? used.end() : addr_for(first_dirty); |
duke@435 | 370 | HeapWord* boundary_block = s->block_start(boundary); |
duke@435 | 371 | HeapWord* begin = boundary; // Until proven otherwise. |
duke@435 | 372 | HeapWord* start_block = boundary_block; // Until proven otherwise. |
duke@435 | 373 | if (boundary_block < boundary) { |
duke@435 | 374 | if (s->block_is_obj(boundary_block) && s->obj_is_alive(boundary_block)) { |
duke@435 | 375 | oop boundary_obj = oop(boundary_block); |
duke@435 | 376 | if (!boundary_obj->is_objArray() && |
duke@435 | 377 | !boundary_obj->is_typeArray()) { |
duke@435 | 378 | guarantee(cur_entry > byte_for(used.start()), |
duke@435 | 379 | "else boundary would be boundary_block"); |
duke@435 | 380 | if (*byte_for(boundary_block) != CardTableModRefBS::clean_card) { |
duke@435 | 381 | begin = boundary_block + s->block_size(boundary_block); |
duke@435 | 382 | start_block = begin; |
duke@435 | 383 | } |
duke@435 | 384 | } |
duke@435 | 385 | } |
duke@435 | 386 | } |
duke@435 | 387 | // Now traverse objects until end. |
duke@435 | 388 | HeapWord* cur = start_block; |
duke@435 | 389 | VerifyCleanCardClosure verify_blk(gen_boundary, begin, end); |
duke@435 | 390 | while (cur < end) { |
duke@435 | 391 | if (s->block_is_obj(cur) && s->obj_is_alive(cur)) { |
duke@435 | 392 | oop(cur)->oop_iterate(&verify_blk); |
duke@435 | 393 | } |
duke@435 | 394 | cur += s->block_size(cur); |
duke@435 | 395 | } |
duke@435 | 396 | cur_entry = first_dirty; |
duke@435 | 397 | } else { |
duke@435 | 398 | // We'd normally expect that cur_youngergen_and_prev_nonclean_card |
duke@435 | 399 | // is a transient value, that cannot be in the card table |
duke@435 | 400 | // except during GC, and thus assert that: |
duke@435 | 401 | // guarantee(*cur_entry != cur_youngergen_and_prev_nonclean_card, |
duke@435 | 402 | // "Illegal CT value"); |
duke@435 | 403 | // That however, need not hold, as will become clear in the |
duke@435 | 404 | // following... |
duke@435 | 405 | |
duke@435 | 406 | // We'd normally expect that if we are in the parallel case, |
duke@435 | 407 | // we can't have left a prev value (which would be different |
duke@435 | 408 | // from the current value) in the card table, and so we'd like to |
duke@435 | 409 | // assert that: |
duke@435 | 410 | // guarantee(cur_youngergen_card_val() == youngergen_card |
duke@435 | 411 | // || !is_prev_youngergen_card_val(*cur_entry), |
duke@435 | 412 | // "Illegal CT value"); |
duke@435 | 413 | // That, however, may not hold occasionally, because of |
duke@435 | 414 | // CMS or MSC in the old gen. To wit, consider the |
duke@435 | 415 | // following two simple illustrative scenarios: |
duke@435 | 416 | // (a) CMS: Consider the case where a large object L |
duke@435 | 417 | // spanning several cards is allocated in the old |
duke@435 | 418 | // gen, and has a young gen reference stored in it, dirtying |
duke@435 | 419 | // some interior cards. A young collection scans the card, |
duke@435 | 420 | // finds a young ref and installs a youngergenP_n value. |
duke@435 | 421 | // L then goes dead. Now a CMS collection starts, |
duke@435 | 422 | // finds L dead and sweeps it up. Assume that L is |
duke@435 | 423 | // abutting _unallocated_blk, so _unallocated_blk is |
duke@435 | 424 | // adjusted down to (below) L. Assume further that |
duke@435 | 425 | // no young collection intervenes during this CMS cycle. |
duke@435 | 426 | // The next young gen cycle will not get to look at this |
duke@435 | 427 | // youngergenP_n card since it lies in the unoccupied |
duke@435 | 428 | // part of the space. |
duke@435 | 429 | // Some young collections later the blocks on this |
duke@435 | 430 | // card can be re-allocated either due to direct allocation |
duke@435 | 431 | // or due to absorbing promotions. At this time, the |
duke@435 | 432 | // before-gc verification will fail the above assert. |
duke@435 | 433 | // (b) MSC: In this case, an object L with a young reference |
duke@435 | 434 | // is on a card that (therefore) holds a youngergen_n value. |
duke@435 | 435 | // Suppose also that L lies towards the end of the used |
duke@435 | 436 | // the used space before GC. An MSC collection |
duke@435 | 437 | // occurs that compacts to such an extent that this |
duke@435 | 438 | // card is no longer in the occupied part of the space. |
duke@435 | 439 | // Since current code in MSC does not always clear cards |
duke@435 | 440 | // in the unused part of old gen, this stale youngergen_n |
duke@435 | 441 | // value is left behind and can later be covered by |
duke@435 | 442 | // an object when promotion or direct allocation |
duke@435 | 443 | // re-allocates that part of the heap. |
duke@435 | 444 | // |
duke@435 | 445 | // Fortunately, the presence of such stale card values is |
duke@435 | 446 | // "only" a minor annoyance in that subsequent young collections |
duke@435 | 447 | // might needlessly scan such cards, but would still never corrupt |
duke@435 | 448 | // the heap as a result. However, it's likely not to be a significant |
duke@435 | 449 | // performance inhibitor in practice. For instance, |
duke@435 | 450 | // some recent measurements with unoccupied cards eagerly cleared |
duke@435 | 451 | // out to maintain this invariant, showed next to no |
duke@435 | 452 | // change in young collection times; of course one can construct |
duke@435 | 453 | // degenerate examples where the cost can be significant.) |
duke@435 | 454 | // Note, in particular, that if the "stale" card is modified |
duke@435 | 455 | // after re-allocation, it would be dirty, not "stale". Thus, |
duke@435 | 456 | // we can never have a younger ref in such a card and it is |
duke@435 | 457 | // safe not to scan that card in any collection. [As we see |
duke@435 | 458 | // below, we do some unnecessary scanning |
duke@435 | 459 | // in some cases in the current parallel scanning algorithm.] |
duke@435 | 460 | // |
duke@435 | 461 | // The main point below is that the parallel card scanning code |
duke@435 | 462 | // deals correctly with these stale card values. There are two main |
duke@435 | 463 | // cases to consider where we have a stale "younger gen" value and a |
duke@435 | 464 | // "derivative" case to consider, where we have a stale |
duke@435 | 465 | // "cur_younger_gen_and_prev_non_clean" value, as will become |
duke@435 | 466 | // apparent in the case analysis below. |
duke@435 | 467 | // o Case 1. If the stale value corresponds to a younger_gen_n |
duke@435 | 468 | // value other than the cur_younger_gen value then the code |
duke@435 | 469 | // treats this as being tantamount to a prev_younger_gen |
duke@435 | 470 | // card. This means that the card may be unnecessarily scanned. |
duke@435 | 471 | // There are two sub-cases to consider: |
duke@435 | 472 | // o Case 1a. Let us say that the card is in the occupied part |
duke@435 | 473 | // of the generation at the time the collection begins. In |
duke@435 | 474 | // that case the card will be either cleared when it is scanned |
duke@435 | 475 | // for young pointers, or will be set to cur_younger_gen as a |
duke@435 | 476 | // result of promotion. (We have elided the normal case where |
duke@435 | 477 | // the scanning thread and the promoting thread interleave |
duke@435 | 478 | // possibly resulting in a transient |
duke@435 | 479 | // cur_younger_gen_and_prev_non_clean value before settling |
duke@435 | 480 | // to cur_younger_gen. [End Case 1a.] |
duke@435 | 481 | // o Case 1b. Consider now the case when the card is in the unoccupied |
duke@435 | 482 | // part of the space which becomes occupied because of promotions |
duke@435 | 483 | // into it during the current young GC. In this case the card |
duke@435 | 484 | // will never be scanned for young references. The current |
duke@435 | 485 | // code will set the card value to either |
duke@435 | 486 | // cur_younger_gen_and_prev_non_clean or leave |
duke@435 | 487 | // it with its stale value -- because the promotions didn't |
duke@435 | 488 | // result in any younger refs on that card. Of these two |
duke@435 | 489 | // cases, the latter will be covered in Case 1a during |
duke@435 | 490 | // a subsequent scan. To deal with the former case, we need |
duke@435 | 491 | // to further consider how we deal with a stale value of |
duke@435 | 492 | // cur_younger_gen_and_prev_non_clean in our case analysis |
duke@435 | 493 | // below. This we do in Case 3 below. [End Case 1b] |
duke@435 | 494 | // [End Case 1] |
duke@435 | 495 | // o Case 2. If the stale value corresponds to cur_younger_gen being |
duke@435 | 496 | // a value not necessarily written by a current promotion, the |
duke@435 | 497 | // card will not be scanned by the younger refs scanning code. |
duke@435 | 498 | // (This is OK since as we argued above such cards cannot contain |
duke@435 | 499 | // any younger refs.) The result is that this value will be |
duke@435 | 500 | // treated as a prev_younger_gen value in a subsequent collection, |
duke@435 | 501 | // which is addressed in Case 1 above. [End Case 2] |
duke@435 | 502 | // o Case 3. We here consider the "derivative" case from Case 1b. above |
duke@435 | 503 | // because of which we may find a stale |
duke@435 | 504 | // cur_younger_gen_and_prev_non_clean card value in the table. |
duke@435 | 505 | // Once again, as in Case 1, we consider two subcases, depending |
duke@435 | 506 | // on whether the card lies in the occupied or unoccupied part |
duke@435 | 507 | // of the space at the start of the young collection. |
duke@435 | 508 | // o Case 3a. Let us say the card is in the occupied part of |
duke@435 | 509 | // the old gen at the start of the young collection. In that |
duke@435 | 510 | // case, the card will be scanned by the younger refs scanning |
duke@435 | 511 | // code which will set it to cur_younger_gen. In a subsequent |
duke@435 | 512 | // scan, the card will be considered again and get its final |
duke@435 | 513 | // correct value. [End Case 3a] |
duke@435 | 514 | // o Case 3b. Now consider the case where the card is in the |
duke@435 | 515 | // unoccupied part of the old gen, and is occupied as a result |
duke@435 | 516 | // of promotions during thus young gc. In that case, |
duke@435 | 517 | // the card will not be scanned for younger refs. The presence |
duke@435 | 518 | // of newly promoted objects on the card will then result in |
duke@435 | 519 | // its keeping the value cur_younger_gen_and_prev_non_clean |
duke@435 | 520 | // value, which we have dealt with in Case 3 here. [End Case 3b] |
duke@435 | 521 | // [End Case 3] |
duke@435 | 522 | // |
duke@435 | 523 | // (Please refer to the code in the helper class |
duke@435 | 524 | // ClearNonCleanCardWrapper and in CardTableModRefBS for details.) |
duke@435 | 525 | // |
duke@435 | 526 | // The informal arguments above can be tightened into a formal |
duke@435 | 527 | // correctness proof and it behooves us to write up such a proof, |
duke@435 | 528 | // or to use model checking to prove that there are no lingering |
duke@435 | 529 | // concerns. |
duke@435 | 530 | // |
duke@435 | 531 | // Clearly because of Case 3b one cannot bound the time for |
duke@435 | 532 | // which a card will retain what we have called a "stale" value. |
duke@435 | 533 | // However, one can obtain a Loose upper bound on the redundant |
duke@435 | 534 | // work as a result of such stale values. Note first that any |
duke@435 | 535 | // time a stale card lies in the occupied part of the space at |
duke@435 | 536 | // the start of the collection, it is scanned by younger refs |
duke@435 | 537 | // code and we can define a rank function on card values that |
duke@435 | 538 | // declines when this is so. Note also that when a card does not |
duke@435 | 539 | // lie in the occupied part of the space at the beginning of a |
duke@435 | 540 | // young collection, its rank can either decline or stay unchanged. |
duke@435 | 541 | // In this case, no extra work is done in terms of redundant |
duke@435 | 542 | // younger refs scanning of that card. |
duke@435 | 543 | // Then, the case analysis above reveals that, in the worst case, |
duke@435 | 544 | // any such stale card will be scanned unnecessarily at most twice. |
duke@435 | 545 | // |
duke@435 | 546 | // It is nonethelss advisable to try and get rid of some of this |
duke@435 | 547 | // redundant work in a subsequent (low priority) re-design of |
duke@435 | 548 | // the card-scanning code, if only to simplify the underlying |
duke@435 | 549 | // state machine analysis/proof. ysr 1/28/2002. XXX |
duke@435 | 550 | cur_entry++; |
duke@435 | 551 | } |
duke@435 | 552 | } |
duke@435 | 553 | } |
duke@435 | 554 | |
duke@435 | 555 | void CardTableRS::verify() { |
duke@435 | 556 | // At present, we only know how to verify the card table RS for |
duke@435 | 557 | // generational heaps. |
duke@435 | 558 | VerifyCTGenClosure blk(this); |
duke@435 | 559 | CollectedHeap* ch = Universe::heap(); |
duke@435 | 560 | // We will do the perm-gen portion of the card table, too. |
duke@435 | 561 | Generation* pg = SharedHeap::heap()->perm_gen(); |
duke@435 | 562 | HeapWord* pg_boundary = pg->reserved().start(); |
duke@435 | 563 | |
duke@435 | 564 | if (ch->kind() == CollectedHeap::GenCollectedHeap) { |
duke@435 | 565 | GenCollectedHeap::heap()->generation_iterate(&blk, false); |
ysr@777 | 566 | _ct_bs->verify(); |
duke@435 | 567 | |
duke@435 | 568 | // If the old gen collections also collect perm, then we are only |
duke@435 | 569 | // interested in perm-to-young pointers, not perm-to-old pointers. |
duke@435 | 570 | GenCollectedHeap* gch = GenCollectedHeap::heap(); |
duke@435 | 571 | CollectorPolicy* cp = gch->collector_policy(); |
duke@435 | 572 | if (cp->is_mark_sweep_policy() || cp->is_concurrent_mark_sweep_policy()) { |
duke@435 | 573 | pg_boundary = gch->get_gen(1)->reserved().start(); |
duke@435 | 574 | } |
duke@435 | 575 | } |
duke@435 | 576 | VerifyCTSpaceClosure perm_space_blk(this, pg_boundary); |
duke@435 | 577 | SharedHeap::heap()->perm_gen()->space_iterate(&perm_space_blk, true); |
duke@435 | 578 | } |
duke@435 | 579 | |
duke@435 | 580 | |
jmasa@441 | 581 | void CardTableRS::verify_aligned_region_empty(MemRegion mr) { |
duke@435 | 582 | if (!mr.is_empty()) { |
duke@435 | 583 | jbyte* cur_entry = byte_for(mr.start()); |
duke@435 | 584 | jbyte* limit = byte_after(mr.last()); |
jmasa@441 | 585 | // The region mr may not start on a card boundary so |
jmasa@441 | 586 | // the first card may reflect a write to the space |
jmasa@441 | 587 | // just prior to mr. |
jmasa@441 | 588 | if (!is_aligned(mr.start())) { |
jmasa@441 | 589 | cur_entry++; |
jmasa@441 | 590 | } |
duke@435 | 591 | for (;cur_entry < limit; cur_entry++) { |
duke@435 | 592 | guarantee(*cur_entry == CardTableModRefBS::clean_card, |
duke@435 | 593 | "Unexpected dirty card found"); |
duke@435 | 594 | } |
duke@435 | 595 | } |
duke@435 | 596 | } |