1 /*
2 * Copyright (c) 2001, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "gc/shared/cardTableRS.hpp"
27 #include "gc/shared/genCollectedHeap.hpp"
28 #include "gc/shared/generation.hpp"
29 #include "gc/shared/space.inline.hpp"
30 #include "memory/allocation.inline.hpp"
31 #include "oops/oop.inline.hpp"
32 #include "runtime/atomic.hpp"
33 #include "runtime/java.hpp"
34 #include "runtime/os.hpp"
35 #include "utilities/macros.hpp"
36
37 class HasAccumulatedModifiedOopsClosure : public KlassClosure {
38 bool _found;
39 public:
40 HasAccumulatedModifiedOopsClosure() : _found(false) {}
41 void do_klass(Klass* klass) {
42 if (_found) {
43 return;
44 }
45
46 if (klass->has_accumulated_modified_oops()) {
47 _found = true;
48 }
49 }
50 bool found() {
51 return _found;
52 }
53 };
54
55 bool KlassRemSet::mod_union_is_clear() {
56 HasAccumulatedModifiedOopsClosure closure;
57 ClassLoaderDataGraph::classes_do(&closure);
58
59 return !closure.found();
60 }
61
62
63 class ClearKlassModUnionClosure : public KlassClosure {
64 public:
65 void do_klass(Klass* klass) {
66 if (klass->has_accumulated_modified_oops()) {
67 klass->clear_accumulated_modified_oops();
68 }
69 }
70 };
71
72 void KlassRemSet::clear_mod_union() {
73 ClearKlassModUnionClosure closure;
74 ClassLoaderDataGraph::classes_do(&closure);
75 }
76
77 jbyte CardTableRS::find_unused_youngergenP_card_value() {
78 for (jbyte v = youngergenP1_card;
79 v < cur_youngergen_and_prev_nonclean_card;
80 v++) {
81 bool seen = false;
82 for (int g = 0; g < _regions_to_iterate; g++) {
83 if (_last_cur_val_in_gen[g] == v) {
84 seen = true;
85 break;
86 }
87 }
88 if (!seen) {
89 return v;
90 }
91 }
92 ShouldNotReachHere();
93 return 0;
94 }
95
96 void CardTableRS::prepare_for_younger_refs_iterate(bool parallel) {
97 // Parallel or sequential, we must always set the prev to equal the
98 // last one written.
99 if (parallel) {
100 // Find a parallel value to be used next.
101 jbyte next_val = find_unused_youngergenP_card_value();
102 set_cur_youngergen_card_val(next_val);
103
104 } else {
105 // In an sequential traversal we will always write youngergen, so that
106 // the inline barrier is correct.
107 set_cur_youngergen_card_val(youngergen_card);
108 }
109 }
110
111 void CardTableRS::younger_refs_iterate(Generation* g,
112 OopsInGenClosure* blk,
113 uint n_threads) {
114 // The indexing in this array is slightly odd. We want to access
115 // the old generation record here, which is at index 2.
116 _last_cur_val_in_gen[2] = cur_youngergen_card_val();
117 g->younger_refs_iterate(blk, n_threads);
118 }
119
120 inline bool ClearNoncleanCardWrapper::clear_card(jbyte* entry) {
121 if (_is_par) {
122 return clear_card_parallel(entry);
123 } else {
124 return clear_card_serial(entry);
125 }
126 }
127
128 inline bool ClearNoncleanCardWrapper::clear_card_parallel(jbyte* entry) {
129 while (true) {
130 // In the parallel case, we may have to do this several times.
131 jbyte entry_val = *entry;
132 assert(entry_val != CardTableRS::clean_card_val(),
133 "We shouldn't be looking at clean cards, and this should "
134 "be the only place they get cleaned.");
135 if (CardTableRS::card_is_dirty_wrt_gen_iter(entry_val)
136 || _ct->is_prev_youngergen_card_val(entry_val)) {
137 jbyte res =
138 Atomic::cmpxchg(CardTableRS::clean_card_val(), entry, entry_val);
139 if (res == entry_val) {
140 break;
141 } else {
142 assert(res == CardTableRS::cur_youngergen_and_prev_nonclean_card,
143 "The CAS above should only fail if another thread did "
144 "a GC write barrier.");
145 }
146 } else if (entry_val ==
147 CardTableRS::cur_youngergen_and_prev_nonclean_card) {
148 // Parallelism shouldn't matter in this case. Only the thread
149 // assigned to scan the card should change this value.
150 *entry = _ct->cur_youngergen_card_val();
151 break;
152 } else {
153 assert(entry_val == _ct->cur_youngergen_card_val(),
154 "Should be the only possibility.");
155 // In this case, the card was clean before, and become
156 // cur_youngergen only because of processing of a promoted object.
157 // We don't have to look at the card.
158 return false;
159 }
160 }
161 return true;
162 }
163
164
165 inline bool ClearNoncleanCardWrapper::clear_card_serial(jbyte* entry) {
166 jbyte entry_val = *entry;
167 assert(entry_val != CardTableRS::clean_card_val(),
168 "We shouldn't be looking at clean cards, and this should "
169 "be the only place they get cleaned.");
170 assert(entry_val != CardTableRS::cur_youngergen_and_prev_nonclean_card,
171 "This should be possible in the sequential case.");
172 *entry = CardTableRS::clean_card_val();
173 return true;
174 }
175
176 ClearNoncleanCardWrapper::ClearNoncleanCardWrapper(
177 DirtyCardToOopClosure* dirty_card_closure, CardTableRS* ct, bool is_par) :
178 _dirty_card_closure(dirty_card_closure), _ct(ct), _is_par(is_par) {
179 }
180
181 bool ClearNoncleanCardWrapper::is_word_aligned(jbyte* entry) {
182 return (((intptr_t)entry) & (BytesPerWord-1)) == 0;
183 }
184
185 // The regions are visited in *decreasing* address order.
186 // This order aids with imprecise card marking, where a dirty
187 // card may cause scanning, and summarization marking, of objects
188 // that extend onto subsequent cards.
189 void ClearNoncleanCardWrapper::do_MemRegion(MemRegion mr) {
190 assert(mr.word_size() > 0, "Error");
191 assert(_ct->is_aligned(mr.start()), "mr.start() should be card aligned");
192 // mr.end() may not necessarily be card aligned.
193 jbyte* cur_entry = _ct->byte_for(mr.last());
194 const jbyte* limit = _ct->byte_for(mr.start());
195 HeapWord* end_of_non_clean = mr.end();
196 HeapWord* start_of_non_clean = end_of_non_clean;
197 while (cur_entry >= limit) {
198 HeapWord* cur_hw = _ct->addr_for(cur_entry);
199 if ((*cur_entry != CardTableRS::clean_card_val()) && clear_card(cur_entry)) {
200 // Continue the dirty range by opening the
201 // dirty window one card to the left.
202 start_of_non_clean = cur_hw;
203 } else {
204 // We hit a "clean" card; process any non-empty
205 // "dirty" range accumulated so far.
206 if (start_of_non_clean < end_of_non_clean) {
207 const MemRegion mrd(start_of_non_clean, end_of_non_clean);
208 _dirty_card_closure->do_MemRegion(mrd);
209 }
210
211 // fast forward through potential continuous whole-word range of clean cards beginning at a word-boundary
212 if (is_word_aligned(cur_entry)) {
213 jbyte* cur_row = cur_entry - BytesPerWord;
214 while (cur_row >= limit && *((intptr_t*)cur_row) == CardTableRS::clean_card_row_val()) {
215 cur_row -= BytesPerWord;
216 }
217 cur_entry = cur_row + BytesPerWord;
218 cur_hw = _ct->addr_for(cur_entry);
219 }
220
221 // Reset the dirty window, while continuing to look
222 // for the next dirty card that will start a
223 // new dirty window.
224 end_of_non_clean = cur_hw;
225 start_of_non_clean = cur_hw;
226 }
227 // Note that "cur_entry" leads "start_of_non_clean" in
228 // its leftward excursion after this point
229 // in the loop and, when we hit the left end of "mr",
230 // will point off of the left end of the card-table
231 // for "mr".
232 cur_entry--;
233 }
234 // If the first card of "mr" was dirty, we will have
235 // been left with a dirty window, co-initial with "mr",
236 // which we now process.
237 if (start_of_non_clean < end_of_non_clean) {
238 const MemRegion mrd(start_of_non_clean, end_of_non_clean);
239 _dirty_card_closure->do_MemRegion(mrd);
240 }
241 }
242
243 // clean (by dirty->clean before) ==> cur_younger_gen
244 // dirty ==> cur_youngergen_and_prev_nonclean_card
245 // precleaned ==> cur_youngergen_and_prev_nonclean_card
246 // prev-younger-gen ==> cur_youngergen_and_prev_nonclean_card
247 // cur-younger-gen ==> cur_younger_gen
248 // cur_youngergen_and_prev_nonclean_card ==> no change.
249 void CardTableRS::write_ref_field_gc_par(void* field, oop new_val) {
250 volatile jbyte* entry = byte_for(field);
251 do {
252 jbyte entry_val = *entry;
253 // We put this first because it's probably the most common case.
254 if (entry_val == clean_card_val()) {
255 // No threat of contention with cleaning threads.
256 *entry = cur_youngergen_card_val();
257 return;
258 } else if (card_is_dirty_wrt_gen_iter(entry_val)
259 || is_prev_youngergen_card_val(entry_val)) {
260 // Mark it as both cur and prev youngergen; card cleaning thread will
261 // eventually remove the previous stuff.
262 jbyte new_val = cur_youngergen_and_prev_nonclean_card;
263 jbyte res = Atomic::cmpxchg(new_val, entry, entry_val);
264 // Did the CAS succeed?
265 if (res == entry_val) return;
266 // Otherwise, retry, to see the new value.
267 continue;
268 } else {
269 assert(entry_val == cur_youngergen_and_prev_nonclean_card
270 || entry_val == cur_youngergen_card_val(),
271 "should be only possibilities.");
272 return;
273 }
274 } while (true);
275 }
276
277 void CardTableRS::younger_refs_in_space_iterate(Space* sp,
278 OopsInGenClosure* cl,
279 uint n_threads) {
280 const MemRegion urasm = sp->used_region_at_save_marks();
281 #ifdef ASSERT
282 // Convert the assertion check to a warning if we are running
283 // CMS+ParNew until related bug is fixed.
284 MemRegion ur = sp->used_region();
285 assert(ur.contains(urasm) || (UseConcMarkSweepGC),
286 "Did you forget to call save_marks()? "
287 "[" PTR_FORMAT ", " PTR_FORMAT ") is not contained in "
288 "[" PTR_FORMAT ", " PTR_FORMAT ")",
289 p2i(urasm.start()), p2i(urasm.end()), p2i(ur.start()), p2i(ur.end()));
290 // In the case of CMS+ParNew, issue a warning
291 if (!ur.contains(urasm)) {
292 assert(UseConcMarkSweepGC, "Tautology: see assert above");
293 log_warning(gc)("CMS+ParNew: Did you forget to call save_marks()? "
294 "[" PTR_FORMAT ", " PTR_FORMAT ") is not contained in "
295 "[" PTR_FORMAT ", " PTR_FORMAT ")",
296 p2i(urasm.start()), p2i(urasm.end()), p2i(ur.start()), p2i(ur.end()));
297 MemRegion ur2 = sp->used_region();
298 MemRegion urasm2 = sp->used_region_at_save_marks();
299 if (!ur.equals(ur2)) {
300 log_warning(gc)("CMS+ParNew: Flickering used_region()!!");
301 }
302 if (!urasm.equals(urasm2)) {
303 log_warning(gc)("CMS+ParNew: Flickering used_region_at_save_marks()!!");
304 }
305 ShouldNotReachHere();
306 }
307 #endif
308 non_clean_card_iterate_possibly_parallel(sp, urasm, cl, this, n_threads);
309 }
310
311 void CardTableRS::clear_into_younger(Generation* old_gen) {
312 assert(GenCollectedHeap::heap()->is_old_gen(old_gen),
313 "Should only be called for the old generation");
314 // The card tables for the youngest gen need never be cleared.
315 // There's a bit of subtlety in the clear() and invalidate()
316 // methods that we exploit here and in invalidate_or_clear()
317 // below to avoid missing cards at the fringes. If clear() or
318 // invalidate() are changed in the future, this code should
319 // be revisited. 20040107.ysr
320 clear(old_gen->prev_used_region());
321 }
322
323 void CardTableRS::invalidate_or_clear(Generation* old_gen) {
324 assert(GenCollectedHeap::heap()->is_old_gen(old_gen),
325 "Should only be called for the old generation");
326 // Invalidate the cards for the currently occupied part of
327 // the old generation and clear the cards for the
328 // unoccupied part of the generation (if any, making use
329 // of that generation's prev_used_region to determine that
330 // region). No need to do anything for the youngest
331 // generation. Also see note#20040107.ysr above.
332 MemRegion used_mr = old_gen->used_region();
333 MemRegion to_be_cleared_mr = old_gen->prev_used_region().minus(used_mr);
334 if (!to_be_cleared_mr.is_empty()) {
335 clear(to_be_cleared_mr);
336 }
337 invalidate(used_mr);
338 }
339
340
341 class VerifyCleanCardClosure: public OopClosure {
342 private:
343 HeapWord* _boundary;
344 HeapWord* _begin;
345 HeapWord* _end;
346 protected:
347 template <class T> void do_oop_work(T* p) {
348 HeapWord* jp = (HeapWord*)p;
349 assert(jp >= _begin && jp < _end,
350 "Error: jp " PTR_FORMAT " should be within "
351 "[_begin, _end) = [" PTR_FORMAT "," PTR_FORMAT ")",
352 p2i(jp), p2i(_begin), p2i(_end));
353 oop obj = oopDesc::load_decode_heap_oop(p);
354 guarantee(obj == NULL || (HeapWord*)obj >= _boundary,
355 "pointer " PTR_FORMAT " at " PTR_FORMAT " on "
356 "clean card crosses boundary" PTR_FORMAT,
357 p2i(obj), p2i(jp), p2i(_boundary));
358 }
359
360 public:
361 VerifyCleanCardClosure(HeapWord* b, HeapWord* begin, HeapWord* end) :
362 _boundary(b), _begin(begin), _end(end) {
363 assert(b <= begin,
364 "Error: boundary " PTR_FORMAT " should be at or below begin " PTR_FORMAT,
365 p2i(b), p2i(begin));
366 assert(begin <= end,
367 "Error: begin " PTR_FORMAT " should be strictly below end " PTR_FORMAT,
368 p2i(begin), p2i(end));
369 }
370
371 virtual void do_oop(oop* p) { VerifyCleanCardClosure::do_oop_work(p); }
372 virtual void do_oop(narrowOop* p) { VerifyCleanCardClosure::do_oop_work(p); }
373 };
374
375 class VerifyCTSpaceClosure: public SpaceClosure {
376 private:
377 CardTableRS* _ct;
378 HeapWord* _boundary;
379 public:
380 VerifyCTSpaceClosure(CardTableRS* ct, HeapWord* boundary) :
381 _ct(ct), _boundary(boundary) {}
382 virtual void do_space(Space* s) { _ct->verify_space(s, _boundary); }
383 };
384
385 class VerifyCTGenClosure: public GenCollectedHeap::GenClosure {
386 CardTableRS* _ct;
387 public:
388 VerifyCTGenClosure(CardTableRS* ct) : _ct(ct) {}
389 void do_generation(Generation* gen) {
390 // Skip the youngest generation.
391 if (GenCollectedHeap::heap()->is_young_gen(gen)) {
392 return;
393 }
394 // Normally, we're interested in pointers to younger generations.
395 VerifyCTSpaceClosure blk(_ct, gen->reserved().start());
396 gen->space_iterate(&blk, true);
397 }
398 };
399
400 void CardTableRS::verify_space(Space* s, HeapWord* gen_boundary) {
401 // We don't need to do young-gen spaces.
402 if (s->end() <= gen_boundary) return;
403 MemRegion used = s->used_region();
404
405 jbyte* cur_entry = byte_for(used.start());
406 jbyte* limit = byte_after(used.last());
407 while (cur_entry < limit) {
408 if (*cur_entry == clean_card_val()) {
409 jbyte* first_dirty = cur_entry+1;
410 while (first_dirty < limit &&
411 *first_dirty == clean_card_val()) {
412 first_dirty++;
413 }
414 // If the first object is a regular object, and it has a
415 // young-to-old field, that would mark the previous card.
416 HeapWord* boundary = addr_for(cur_entry);
417 HeapWord* end = (first_dirty >= limit) ? used.end() : addr_for(first_dirty);
418 HeapWord* boundary_block = s->block_start(boundary);
419 HeapWord* begin = boundary; // Until proven otherwise.
420 HeapWord* start_block = boundary_block; // Until proven otherwise.
421 if (boundary_block < boundary) {
422 if (s->block_is_obj(boundary_block) && s->obj_is_alive(boundary_block)) {
423 oop boundary_obj = oop(boundary_block);
424 if (!boundary_obj->is_objArray() &&
425 !boundary_obj->is_typeArray()) {
426 guarantee(cur_entry > byte_for(used.start()),
427 "else boundary would be boundary_block");
428 if (*byte_for(boundary_block) != clean_card_val()) {
429 begin = boundary_block + s->block_size(boundary_block);
430 start_block = begin;
431 }
432 }
433 }
434 }
435 // Now traverse objects until end.
436 if (begin < end) {
437 MemRegion mr(begin, end);
438 VerifyCleanCardClosure verify_blk(gen_boundary, begin, end);
439 for (HeapWord* cur = start_block; cur < end; cur += s->block_size(cur)) {
440 if (s->block_is_obj(cur) && s->obj_is_alive(cur)) {
441 oop(cur)->oop_iterate_no_header(&verify_blk, mr);
442 }
443 }
444 }
445 cur_entry = first_dirty;
446 } else {
447 // We'd normally expect that cur_youngergen_and_prev_nonclean_card
448 // is a transient value, that cannot be in the card table
449 // except during GC, and thus assert that:
450 // guarantee(*cur_entry != cur_youngergen_and_prev_nonclean_card,
451 // "Illegal CT value");
452 // That however, need not hold, as will become clear in the
453 // following...
454
455 // We'd normally expect that if we are in the parallel case,
456 // we can't have left a prev value (which would be different
457 // from the current value) in the card table, and so we'd like to
458 // assert that:
459 // guarantee(cur_youngergen_card_val() == youngergen_card
460 // || !is_prev_youngergen_card_val(*cur_entry),
461 // "Illegal CT value");
462 // That, however, may not hold occasionally, because of
463 // CMS or MSC in the old gen. To wit, consider the
464 // following two simple illustrative scenarios:
465 // (a) CMS: Consider the case where a large object L
466 // spanning several cards is allocated in the old
467 // gen, and has a young gen reference stored in it, dirtying
468 // some interior cards. A young collection scans the card,
469 // finds a young ref and installs a youngergenP_n value.
470 // L then goes dead. Now a CMS collection starts,
471 // finds L dead and sweeps it up. Assume that L is
472 // abutting _unallocated_blk, so _unallocated_blk is
473 // adjusted down to (below) L. Assume further that
474 // no young collection intervenes during this CMS cycle.
475 // The next young gen cycle will not get to look at this
476 // youngergenP_n card since it lies in the unoccupied
477 // part of the space.
478 // Some young collections later the blocks on this
479 // card can be re-allocated either due to direct allocation
480 // or due to absorbing promotions. At this time, the
481 // before-gc verification will fail the above assert.
482 // (b) MSC: In this case, an object L with a young reference
483 // is on a card that (therefore) holds a youngergen_n value.
484 // Suppose also that L lies towards the end of the used
485 // the used space before GC. An MSC collection
486 // occurs that compacts to such an extent that this
487 // card is no longer in the occupied part of the space.
488 // Since current code in MSC does not always clear cards
489 // in the unused part of old gen, this stale youngergen_n
490 // value is left behind and can later be covered by
491 // an object when promotion or direct allocation
492 // re-allocates that part of the heap.
493 //
494 // Fortunately, the presence of such stale card values is
495 // "only" a minor annoyance in that subsequent young collections
496 // might needlessly scan such cards, but would still never corrupt
497 // the heap as a result. However, it's likely not to be a significant
498 // performance inhibitor in practice. For instance,
499 // some recent measurements with unoccupied cards eagerly cleared
500 // out to maintain this invariant, showed next to no
501 // change in young collection times; of course one can construct
502 // degenerate examples where the cost can be significant.)
503 // Note, in particular, that if the "stale" card is modified
504 // after re-allocation, it would be dirty, not "stale". Thus,
505 // we can never have a younger ref in such a card and it is
506 // safe not to scan that card in any collection. [As we see
507 // below, we do some unnecessary scanning
508 // in some cases in the current parallel scanning algorithm.]
509 //
510 // The main point below is that the parallel card scanning code
511 // deals correctly with these stale card values. There are two main
512 // cases to consider where we have a stale "young gen" value and a
513 // "derivative" case to consider, where we have a stale
514 // "cur_younger_gen_and_prev_non_clean" value, as will become
515 // apparent in the case analysis below.
516 // o Case 1. If the stale value corresponds to a younger_gen_n
517 // value other than the cur_younger_gen value then the code
518 // treats this as being tantamount to a prev_younger_gen
519 // card. This means that the card may be unnecessarily scanned.
520 // There are two sub-cases to consider:
521 // o Case 1a. Let us say that the card is in the occupied part
522 // of the generation at the time the collection begins. In
523 // that case the card will be either cleared when it is scanned
524 // for young pointers, or will be set to cur_younger_gen as a
525 // result of promotion. (We have elided the normal case where
526 // the scanning thread and the promoting thread interleave
527 // possibly resulting in a transient
528 // cur_younger_gen_and_prev_non_clean value before settling
529 // to cur_younger_gen. [End Case 1a.]
530 // o Case 1b. Consider now the case when the card is in the unoccupied
531 // part of the space which becomes occupied because of promotions
532 // into it during the current young GC. In this case the card
533 // will never be scanned for young references. The current
534 // code will set the card value to either
535 // cur_younger_gen_and_prev_non_clean or leave
536 // it with its stale value -- because the promotions didn't
537 // result in any younger refs on that card. Of these two
538 // cases, the latter will be covered in Case 1a during
539 // a subsequent scan. To deal with the former case, we need
540 // to further consider how we deal with a stale value of
541 // cur_younger_gen_and_prev_non_clean in our case analysis
542 // below. This we do in Case 3 below. [End Case 1b]
543 // [End Case 1]
544 // o Case 2. If the stale value corresponds to cur_younger_gen being
545 // a value not necessarily written by a current promotion, the
546 // card will not be scanned by the younger refs scanning code.
547 // (This is OK since as we argued above such cards cannot contain
548 // any younger refs.) The result is that this value will be
549 // treated as a prev_younger_gen value in a subsequent collection,
550 // which is addressed in Case 1 above. [End Case 2]
551 // o Case 3. We here consider the "derivative" case from Case 1b. above
552 // because of which we may find a stale
553 // cur_younger_gen_and_prev_non_clean card value in the table.
554 // Once again, as in Case 1, we consider two subcases, depending
555 // on whether the card lies in the occupied or unoccupied part
556 // of the space at the start of the young collection.
557 // o Case 3a. Let us say the card is in the occupied part of
558 // the old gen at the start of the young collection. In that
559 // case, the card will be scanned by the younger refs scanning
560 // code which will set it to cur_younger_gen. In a subsequent
561 // scan, the card will be considered again and get its final
562 // correct value. [End Case 3a]
563 // o Case 3b. Now consider the case where the card is in the
564 // unoccupied part of the old gen, and is occupied as a result
565 // of promotions during thus young gc. In that case,
566 // the card will not be scanned for younger refs. The presence
567 // of newly promoted objects on the card will then result in
568 // its keeping the value cur_younger_gen_and_prev_non_clean
569 // value, which we have dealt with in Case 3 here. [End Case 3b]
570 // [End Case 3]
571 //
572 // (Please refer to the code in the helper class
573 // ClearNonCleanCardWrapper and in CardTableModRefBS for details.)
574 //
575 // The informal arguments above can be tightened into a formal
576 // correctness proof and it behooves us to write up such a proof,
577 // or to use model checking to prove that there are no lingering
578 // concerns.
579 //
580 // Clearly because of Case 3b one cannot bound the time for
581 // which a card will retain what we have called a "stale" value.
582 // However, one can obtain a Loose upper bound on the redundant
583 // work as a result of such stale values. Note first that any
584 // time a stale card lies in the occupied part of the space at
585 // the start of the collection, it is scanned by younger refs
586 // code and we can define a rank function on card values that
587 // declines when this is so. Note also that when a card does not
588 // lie in the occupied part of the space at the beginning of a
589 // young collection, its rank can either decline or stay unchanged.
590 // In this case, no extra work is done in terms of redundant
591 // younger refs scanning of that card.
592 // Then, the case analysis above reveals that, in the worst case,
593 // any such stale card will be scanned unnecessarily at most twice.
594 //
595 // It is nonetheless advisable to try and get rid of some of this
596 // redundant work in a subsequent (low priority) re-design of
597 // the card-scanning code, if only to simplify the underlying
598 // state machine analysis/proof. ysr 1/28/2002. XXX
599 cur_entry++;
600 }
601 }
602 }
603
604 void CardTableRS::verify() {
605 // At present, we only know how to verify the card table RS for
606 // generational heaps.
607 VerifyCTGenClosure blk(this);
608 GenCollectedHeap::heap()->generation_iterate(&blk, false);
609 CardTable::verify();
610 }
611
612 CardTableRS::CardTableRS(MemRegion whole_heap) :
613 CardTable(whole_heap, /* scanned concurrently */ UseConcMarkSweepGC),
614 _cur_youngergen_card_val(youngergenP1_card),
615 // LNC functionality
616 _lowest_non_clean(NULL),
617 _lowest_non_clean_chunk_size(NULL),
618 _lowest_non_clean_base_chunk_index(NULL),
619 _last_LNC_resizing_collection(NULL)
620 {
621 // max_gens is really GenCollectedHeap::heap()->gen_policy()->number_of_generations()
622 // (which is always 2, young & old), but GenCollectedHeap has not been initialized yet.
623 uint max_gens = 2;
624 _last_cur_val_in_gen = NEW_C_HEAP_ARRAY3(jbyte, max_gens + 1,
625 mtGC, CURRENT_PC, AllocFailStrategy::RETURN_NULL);
626 if (_last_cur_val_in_gen == NULL) {
627 vm_exit_during_initialization("Could not create last_cur_val_in_gen array.");
628 }
629 for (uint i = 0; i < max_gens + 1; i++) {
630 _last_cur_val_in_gen[i] = clean_card_val();
631 }
632 }
633
634 CardTableRS::~CardTableRS() {
635 if (_last_cur_val_in_gen) {
636 FREE_C_HEAP_ARRAY(jbyte, _last_cur_val_in_gen);
637 }
638 if (_lowest_non_clean) {
639 FREE_C_HEAP_ARRAY(CardArr, _lowest_non_clean);
640 _lowest_non_clean = NULL;
641 }
642 if (_lowest_non_clean_chunk_size) {
643 FREE_C_HEAP_ARRAY(size_t, _lowest_non_clean_chunk_size);
644 _lowest_non_clean_chunk_size = NULL;
645 }
646 if (_lowest_non_clean_base_chunk_index) {
647 FREE_C_HEAP_ARRAY(uintptr_t, _lowest_non_clean_base_chunk_index);
648 _lowest_non_clean_base_chunk_index = NULL;
649 }
650 if (_last_LNC_resizing_collection) {
651 FREE_C_HEAP_ARRAY(int, _last_LNC_resizing_collection);
652 _last_LNC_resizing_collection = NULL;
653 }
654 }
655
656 void CardTableRS::initialize() {
657 CardTable::initialize();
658 _lowest_non_clean =
659 NEW_C_HEAP_ARRAY(CardArr, _max_covered_regions, mtGC);
660 _lowest_non_clean_chunk_size =
661 NEW_C_HEAP_ARRAY(size_t, _max_covered_regions, mtGC);
662 _lowest_non_clean_base_chunk_index =
663 NEW_C_HEAP_ARRAY(uintptr_t, _max_covered_regions, mtGC);
664 _last_LNC_resizing_collection =
665 NEW_C_HEAP_ARRAY(int, _max_covered_regions, mtGC);
666 if (_lowest_non_clean == NULL
667 || _lowest_non_clean_chunk_size == NULL
668 || _lowest_non_clean_base_chunk_index == NULL
669 || _last_LNC_resizing_collection == NULL)
670 vm_exit_during_initialization("couldn't allocate an LNC array.");
671 for (int i = 0; i < _max_covered_regions; i++) {
672 _lowest_non_clean[i] = NULL;
673 _lowest_non_clean_chunk_size[i] = 0;
674 _last_LNC_resizing_collection[i] = -1;
675 }
676 }
677
678 bool CardTableRS::card_will_be_scanned(jbyte cv) {
679 return card_is_dirty_wrt_gen_iter(cv) || is_prev_nonclean_card_val(cv);
680 }
681
682 bool CardTableRS::card_may_have_been_dirty(jbyte cv) {
683 return
684 cv != clean_card &&
685 (card_is_dirty_wrt_gen_iter(cv) ||
686 CardTableRS::youngergen_may_have_been_dirty(cv));
687 }
688
689 void CardTableRS::non_clean_card_iterate_possibly_parallel(
690 Space* sp,
691 MemRegion mr,
692 OopsInGenClosure* cl,
693 CardTableRS* ct,
694 uint n_threads)
695 {
696 if (!mr.is_empty()) {
697 if (n_threads > 0) {
698 #if INCLUDE_ALL_GCS
699 non_clean_card_iterate_parallel_work(sp, mr, cl, ct, n_threads);
700 #else // INCLUDE_ALL_GCS
701 fatal("Parallel gc not supported here.");
702 #endif // INCLUDE_ALL_GCS
703 } else {
704 // clear_cl finds contiguous dirty ranges of cards to process and clear.
705
706 // This is the single-threaded version used by DefNew.
707 const bool parallel = false;
708
709 DirtyCardToOopClosure* dcto_cl = sp->new_dcto_cl(cl, precision(), cl->gen_boundary(), parallel);
710 ClearNoncleanCardWrapper clear_cl(dcto_cl, ct, parallel);
711
712 clear_cl.do_MemRegion(mr);
713 }
714 }
715 }
716
717 bool CardTableRS::is_in_young(void* addr) const {
718 return GenCollectedHeap::heap()->is_in_young((oop)addr);
719 }