1 /* 2 * Copyright (c) 2001, 2010, 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 #ifndef SHARE_VM_GC_IMPLEMENTATION_G1_CONCURRENTMARK_HPP 26 #define SHARE_VM_GC_IMPLEMENTATION_G1_CONCURRENTMARK_HPP 27 28 #include "gc_implementation/g1/heapRegion.hpp" 29 #include "utilities/taskqueue.hpp" 30 31 class G1CollectedHeap; 32 class CMTask; 33 typedef GenericTaskQueue<oop> CMTaskQueue; 34 typedef GenericTaskQueueSet<CMTaskQueue> CMTaskQueueSet; 35 36 // A generic CM bit map. This is essentially a wrapper around the BitMap 37 // class, with one bit per (1<<_shifter) HeapWords. 38 39 class CMBitMapRO VALUE_OBJ_CLASS_SPEC { 40 protected: 41 HeapWord* _bmStartWord; // base address of range covered by map 42 size_t _bmWordSize; // map size (in #HeapWords covered) 43 const int _shifter; // map to char or bit 44 VirtualSpace _virtual_space; // underlying the bit map 45 BitMap _bm; // the bit map itself 46 47 public: 48 // constructor 49 CMBitMapRO(ReservedSpace rs, int shifter); 50 51 enum { do_yield = true }; 52 53 // inquiries 54 HeapWord* startWord() const { return _bmStartWord; } 55 size_t sizeInWords() const { return _bmWordSize; } 56 // the following is one past the last word in space 57 HeapWord* endWord() const { return _bmStartWord + _bmWordSize; } 58 59 // read marks 60 61 bool isMarked(HeapWord* addr) const { 62 assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize), 63 "outside underlying space?"); 64 return _bm.at(heapWordToOffset(addr)); 65 } 66 67 // iteration 68 bool iterate(BitMapClosure* cl) { return _bm.iterate(cl); } 69 bool iterate(BitMapClosure* cl, MemRegion mr); 70 71 // Return the address corresponding to the next marked bit at or after 72 // "addr", and before "limit", if "limit" is non-NULL. If there is no 73 // such bit, returns "limit" if that is non-NULL, or else "endWord()". 74 HeapWord* getNextMarkedWordAddress(HeapWord* addr, 75 HeapWord* limit = NULL) const; 76 // Return the address corresponding to the next unmarked bit at or after 77 // "addr", and before "limit", if "limit" is non-NULL. If there is no 78 // such bit, returns "limit" if that is non-NULL, or else "endWord()". 79 HeapWord* getNextUnmarkedWordAddress(HeapWord* addr, 80 HeapWord* limit = NULL) const; 81 82 // conversion utilities 83 // XXX Fix these so that offsets are size_t's... 84 HeapWord* offsetToHeapWord(size_t offset) const { 85 return _bmStartWord + (offset << _shifter); 86 } 87 size_t heapWordToOffset(HeapWord* addr) const { 88 return pointer_delta(addr, _bmStartWord) >> _shifter; 89 } 90 int heapWordDiffToOffsetDiff(size_t diff) const; 91 HeapWord* nextWord(HeapWord* addr) { 92 return offsetToHeapWord(heapWordToOffset(addr) + 1); 93 } 94 95 void mostly_disjoint_range_union(BitMap* from_bitmap, 96 size_t from_start_index, 97 HeapWord* to_start_word, 98 size_t word_num); 99 100 // debugging 101 NOT_PRODUCT(bool covers(ReservedSpace rs) const;) 102 }; 103 104 class CMBitMap : public CMBitMapRO { 105 106 public: 107 // constructor 108 CMBitMap(ReservedSpace rs, int shifter) : 109 CMBitMapRO(rs, shifter) {} 110 111 // write marks 112 void mark(HeapWord* addr) { 113 assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize), 114 "outside underlying space?"); 115 _bm.at_put(heapWordToOffset(addr), true); 116 } 117 void clear(HeapWord* addr) { 118 assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize), 119 "outside underlying space?"); 120 _bm.at_put(heapWordToOffset(addr), false); 121 } 122 bool parMark(HeapWord* addr) { 123 assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize), 124 "outside underlying space?"); 125 return _bm.par_at_put(heapWordToOffset(addr), true); 126 } 127 bool parClear(HeapWord* addr) { 128 assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize), 129 "outside underlying space?"); 130 return _bm.par_at_put(heapWordToOffset(addr), false); 131 } 132 void markRange(MemRegion mr); 133 void clearAll(); 134 void clearRange(MemRegion mr); 135 136 // Starting at the bit corresponding to "addr" (inclusive), find the next 137 // "1" bit, if any. This bit starts some run of consecutive "1"'s; find 138 // the end of this run (stopping at "end_addr"). Return the MemRegion 139 // covering from the start of the region corresponding to the first bit 140 // of the run to the end of the region corresponding to the last bit of 141 // the run. If there is no "1" bit at or after "addr", return an empty 142 // MemRegion. 143 MemRegion getAndClearMarkedRegion(HeapWord* addr, HeapWord* end_addr); 144 }; 145 146 // Represents a marking stack used by the CM collector. 147 // Ideally this should be GrowableArray<> just like MSC's marking stack(s). 148 class CMMarkStack VALUE_OBJ_CLASS_SPEC { 149 ConcurrentMark* _cm; 150 oop* _base; // bottom of stack 151 jint _index; // one more than last occupied index 152 jint _capacity; // max #elements 153 jint _oops_do_bound; // Number of elements to include in next iteration. 154 NOT_PRODUCT(jint _max_depth;) // max depth plumbed during run 155 156 bool _overflow; 157 DEBUG_ONLY(bool _drain_in_progress;) 158 DEBUG_ONLY(bool _drain_in_progress_yields;) 159 160 public: 161 CMMarkStack(ConcurrentMark* cm); 162 ~CMMarkStack(); 163 164 void allocate(size_t size); 165 166 oop pop() { 167 if (!isEmpty()) { 168 return _base[--_index] ; 169 } 170 return NULL; 171 } 172 173 // If overflow happens, don't do the push, and record the overflow. 174 // *Requires* that "ptr" is already marked. 175 void push(oop ptr) { 176 if (isFull()) { 177 // Record overflow. 178 _overflow = true; 179 return; 180 } else { 181 _base[_index++] = ptr; 182 NOT_PRODUCT(_max_depth = MAX2(_max_depth, _index)); 183 } 184 } 185 // Non-block impl. Note: concurrency is allowed only with other 186 // "par_push" operations, not with "pop" or "drain". We would need 187 // parallel versions of them if such concurrency was desired. 188 void par_push(oop ptr); 189 190 // Pushes the first "n" elements of "ptr_arr" on the stack. 191 // Non-block impl. Note: concurrency is allowed only with other 192 // "par_adjoin_arr" or "push" operations, not with "pop" or "drain". 193 void par_adjoin_arr(oop* ptr_arr, int n); 194 195 // Pushes the first "n" elements of "ptr_arr" on the stack. 196 // Locking impl: concurrency is allowed only with 197 // "par_push_arr" and/or "par_pop_arr" operations, which use the same 198 // locking strategy. 199 void par_push_arr(oop* ptr_arr, int n); 200 201 // If returns false, the array was empty. Otherwise, removes up to "max" 202 // elements from the stack, and transfers them to "ptr_arr" in an 203 // unspecified order. The actual number transferred is given in "n" ("n 204 // == 0" is deliberately redundant with the return value.) Locking impl: 205 // concurrency is allowed only with "par_push_arr" and/or "par_pop_arr" 206 // operations, which use the same locking strategy. 207 bool par_pop_arr(oop* ptr_arr, int max, int* n); 208 209 // Drain the mark stack, applying the given closure to all fields of 210 // objects on the stack. (That is, continue until the stack is empty, 211 // even if closure applications add entries to the stack.) The "bm" 212 // argument, if non-null, may be used to verify that only marked objects 213 // are on the mark stack. If "yield_after" is "true", then the 214 // concurrent marker performing the drain offers to yield after 215 // processing each object. If a yield occurs, stops the drain operation 216 // and returns false. Otherwise, returns true. 217 template<class OopClosureClass> 218 bool drain(OopClosureClass* cl, CMBitMap* bm, bool yield_after = false); 219 220 bool isEmpty() { return _index == 0; } 221 bool isFull() { return _index == _capacity; } 222 int maxElems() { return _capacity; } 223 224 bool overflow() { return _overflow; } 225 void clear_overflow() { _overflow = false; } 226 227 int size() { return _index; } 228 229 void setEmpty() { _index = 0; clear_overflow(); } 230 231 // Record the current size; a subsequent "oops_do" will iterate only over 232 // indices valid at the time of this call. 233 void set_oops_do_bound(jint bound = -1) { 234 if (bound == -1) { 235 _oops_do_bound = _index; 236 } else { 237 _oops_do_bound = bound; 238 } 239 } 240 jint oops_do_bound() { return _oops_do_bound; } 241 // iterate over the oops in the mark stack, up to the bound recorded via 242 // the call above. 243 void oops_do(OopClosure* f); 244 }; 245 246 class CMRegionStack VALUE_OBJ_CLASS_SPEC { 247 MemRegion* _base; 248 jint _capacity; 249 jint _index; 250 jint _oops_do_bound; 251 bool _overflow; 252 public: 253 CMRegionStack(); 254 ~CMRegionStack(); 255 void allocate(size_t size); 256 257 // This is lock-free; assumes that it will only be called in parallel 258 // with other "push" operations (no pops). 259 void push_lock_free(MemRegion mr); 260 261 // Lock-free; assumes that it will only be called in parallel 262 // with other "pop" operations (no pushes). 263 MemRegion pop_lock_free(); 264 265 #if 0 266 // The routines that manipulate the region stack with a lock are 267 // not currently used. They should be retained, however, as a 268 // diagnostic aid. 269 270 // These two are the implementations that use a lock. They can be 271 // called concurrently with each other but they should not be called 272 // concurrently with the lock-free versions (push() / pop()). 273 void push_with_lock(MemRegion mr); 274 MemRegion pop_with_lock(); 275 #endif 276 277 bool isEmpty() { return _index == 0; } 278 bool isFull() { return _index == _capacity; } 279 280 bool overflow() { return _overflow; } 281 void clear_overflow() { _overflow = false; } 282 283 int size() { return _index; } 284 285 // It iterates over the entries in the region stack and it 286 // invalidates (i.e. assigns MemRegion()) the ones that point to 287 // regions in the collection set. 288 bool invalidate_entries_into_cset(); 289 290 // This gives an upper bound up to which the iteration in 291 // invalidate_entries_into_cset() will reach. This prevents 292 // newly-added entries to be unnecessarily scanned. 293 void set_oops_do_bound() { 294 _oops_do_bound = _index; 295 } 296 297 void setEmpty() { _index = 0; clear_overflow(); } 298 }; 299 300 // this will enable a variety of different statistics per GC task 301 #define _MARKING_STATS_ 0 302 // this will enable the higher verbose levels 303 #define _MARKING_VERBOSE_ 0 304 305 #if _MARKING_STATS_ 306 #define statsOnly(statement) \ 307 do { \ 308 statement ; \ 309 } while (0) 310 #else // _MARKING_STATS_ 311 #define statsOnly(statement) \ 312 do { \ 313 } while (0) 314 #endif // _MARKING_STATS_ 315 316 typedef enum { 317 no_verbose = 0, // verbose turned off 318 stats_verbose, // only prints stats at the end of marking 319 low_verbose, // low verbose, mostly per region and per major event 320 medium_verbose, // a bit more detailed than low 321 high_verbose // per object verbose 322 } CMVerboseLevel; 323 324 325 class ConcurrentMarkThread; 326 327 class ConcurrentMark: public CHeapObj { 328 friend class ConcurrentMarkThread; 329 friend class CMTask; 330 friend class CMBitMapClosure; 331 friend class CSMarkOopClosure; 332 friend class CMGlobalObjectClosure; 333 friend class CMRemarkTask; 334 friend class CMConcurrentMarkingTask; 335 friend class G1ParNoteEndTask; 336 friend class CalcLiveObjectsClosure; 337 338 protected: 339 ConcurrentMarkThread* _cmThread; // the thread doing the work 340 G1CollectedHeap* _g1h; // the heap. 341 size_t _parallel_marking_threads; // the number of marking 342 // threads we'll use 343 double _sleep_factor; // how much we have to sleep, with 344 // respect to the work we just did, to 345 // meet the marking overhead goal 346 double _marking_task_overhead; // marking target overhead for 347 // a single task 348 349 // same as the two above, but for the cleanup task 350 double _cleanup_sleep_factor; 351 double _cleanup_task_overhead; 352 353 // Stuff related to age cohort processing. 354 struct ParCleanupThreadState { 355 char _pre[64]; 356 UncleanRegionList list; 357 char _post[64]; 358 }; 359 ParCleanupThreadState** _par_cleanup_thread_state; 360 361 // CMS marking support structures 362 CMBitMap _markBitMap1; 363 CMBitMap _markBitMap2; 364 CMBitMapRO* _prevMarkBitMap; // completed mark bitmap 365 CMBitMap* _nextMarkBitMap; // under-construction mark bitmap 366 bool _at_least_one_mark_complete; 367 368 BitMap _region_bm; 369 BitMap _card_bm; 370 371 // Heap bounds 372 HeapWord* _heap_start; 373 HeapWord* _heap_end; 374 375 // For gray objects 376 CMMarkStack _markStack; // Grey objects behind global finger. 377 CMRegionStack _regionStack; // Grey regions behind global finger. 378 HeapWord* volatile _finger; // the global finger, region aligned, 379 // always points to the end of the 380 // last claimed region 381 382 // marking tasks 383 size_t _max_task_num; // maximum task number 384 size_t _active_tasks; // task num currently active 385 CMTask** _tasks; // task queue array (max_task_num len) 386 CMTaskQueueSet* _task_queues; // task queue set 387 ParallelTaskTerminator _terminator; // for termination 388 389 // Two sync barriers that are used to synchronise tasks when an 390 // overflow occurs. The algorithm is the following. All tasks enter 391 // the first one to ensure that they have all stopped manipulating 392 // the global data structures. After they exit it, they re-initialise 393 // their data structures and task 0 re-initialises the global data 394 // structures. Then, they enter the second sync barrier. This 395 // ensure, that no task starts doing work before all data 396 // structures (local and global) have been re-initialised. When they 397 // exit it, they are free to start working again. 398 WorkGangBarrierSync _first_overflow_barrier_sync; 399 WorkGangBarrierSync _second_overflow_barrier_sync; 400 401 402 // this is set by any task, when an overflow on the global data 403 // structures is detected. 404 volatile bool _has_overflown; 405 // true: marking is concurrent, false: we're in remark 406 volatile bool _concurrent; 407 // set at the end of a Full GC so that marking aborts 408 volatile bool _has_aborted; 409 410 // used when remark aborts due to an overflow to indicate that 411 // another concurrent marking phase should start 412 volatile bool _restart_for_overflow; 413 414 // This is true from the very start of concurrent marking until the 415 // point when all the tasks complete their work. It is really used 416 // to determine the points between the end of concurrent marking and 417 // time of remark. 418 volatile bool _concurrent_marking_in_progress; 419 420 // verbose level 421 CMVerboseLevel _verbose_level; 422 423 // These two fields are used to implement the optimisation that 424 // avoids pushing objects on the global/region stack if there are 425 // no collection set regions above the lowest finger. 426 427 // This is the lowest finger (among the global and local fingers), 428 // which is calculated before a new collection set is chosen. 429 HeapWord* _min_finger; 430 // If this flag is true, objects/regions that are marked below the 431 // finger should be pushed on the stack(s). If this is flag is 432 // false, it is safe not to push them on the stack(s). 433 bool _should_gray_objects; 434 435 // All of these times are in ms. 436 NumberSeq _init_times; 437 NumberSeq _remark_times; 438 NumberSeq _remark_mark_times; 439 NumberSeq _remark_weak_ref_times; 440 NumberSeq _cleanup_times; 441 double _total_counting_time; 442 double _total_rs_scrub_time; 443 444 double* _accum_task_vtime; // accumulated task vtime 445 446 WorkGang* _parallel_workers; 447 448 void weakRefsWork(bool clear_all_soft_refs); 449 450 void swapMarkBitMaps(); 451 452 // It resets the global marking data structures, as well as the 453 // task local ones; should be called during initial mark. 454 void reset(); 455 // It resets all the marking data structures. 456 void clear_marking_state(); 457 458 // It should be called to indicate which phase we're in (concurrent 459 // mark or remark) and how many threads are currently active. 460 void set_phase(size_t active_tasks, bool concurrent); 461 // We do this after we're done with marking so that the marking data 462 // structures are initialised to a sensible and predictable state. 463 void set_non_marking_state(); 464 465 // prints all gathered CM-related statistics 466 void print_stats(); 467 468 // accessor methods 469 size_t parallel_marking_threads() { return _parallel_marking_threads; } 470 double sleep_factor() { return _sleep_factor; } 471 double marking_task_overhead() { return _marking_task_overhead;} 472 double cleanup_sleep_factor() { return _cleanup_sleep_factor; } 473 double cleanup_task_overhead() { return _cleanup_task_overhead;} 474 475 HeapWord* finger() { return _finger; } 476 bool concurrent() { return _concurrent; } 477 size_t active_tasks() { return _active_tasks; } 478 ParallelTaskTerminator* terminator() { return &_terminator; } 479 480 // It claims the next available region to be scanned by a marking 481 // task. It might return NULL if the next region is empty or we have 482 // run out of regions. In the latter case, out_of_regions() 483 // determines whether we've really run out of regions or the task 484 // should call claim_region() again. This might seem a bit 485 // awkward. Originally, the code was written so that claim_region() 486 // either successfully returned with a non-empty region or there 487 // were no more regions to be claimed. The problem with this was 488 // that, in certain circumstances, it iterated over large chunks of 489 // the heap finding only empty regions and, while it was working, it 490 // was preventing the calling task to call its regular clock 491 // method. So, this way, each task will spend very little time in 492 // claim_region() and is allowed to call the regular clock method 493 // frequently. 494 HeapRegion* claim_region(int task); 495 496 // It determines whether we've run out of regions to scan. 497 bool out_of_regions() { return _finger == _heap_end; } 498 499 // Returns the task with the given id 500 CMTask* task(int id) { 501 assert(0 <= id && id < (int) _active_tasks, 502 "task id not within active bounds"); 503 return _tasks[id]; 504 } 505 506 // Returns the task queue with the given id 507 CMTaskQueue* task_queue(int id) { 508 assert(0 <= id && id < (int) _active_tasks, 509 "task queue id not within active bounds"); 510 return (CMTaskQueue*) _task_queues->queue(id); 511 } 512 513 // Returns the task queue set 514 CMTaskQueueSet* task_queues() { return _task_queues; } 515 516 // Access / manipulation of the overflow flag which is set to 517 // indicate that the global stack or region stack has overflown 518 bool has_overflown() { return _has_overflown; } 519 void set_has_overflown() { _has_overflown = true; } 520 void clear_has_overflown() { _has_overflown = false; } 521 522 bool has_aborted() { return _has_aborted; } 523 bool restart_for_overflow() { return _restart_for_overflow; } 524 525 // Methods to enter the two overflow sync barriers 526 void enter_first_sync_barrier(int task_num); 527 void enter_second_sync_barrier(int task_num); 528 529 public: 530 // Manipulation of the global mark stack. 531 // Notice that the first mark_stack_push is CAS-based, whereas the 532 // two below are Mutex-based. This is OK since the first one is only 533 // called during evacuation pauses and doesn't compete with the 534 // other two (which are called by the marking tasks during 535 // concurrent marking or remark). 536 bool mark_stack_push(oop p) { 537 _markStack.par_push(p); 538 if (_markStack.overflow()) { 539 set_has_overflown(); 540 return false; 541 } 542 return true; 543 } 544 bool mark_stack_push(oop* arr, int n) { 545 _markStack.par_push_arr(arr, n); 546 if (_markStack.overflow()) { 547 set_has_overflown(); 548 return false; 549 } 550 return true; 551 } 552 void mark_stack_pop(oop* arr, int max, int* n) { 553 _markStack.par_pop_arr(arr, max, n); 554 } 555 size_t mark_stack_size() { return _markStack.size(); } 556 size_t partial_mark_stack_size_target() { return _markStack.maxElems()/3; } 557 bool mark_stack_overflow() { return _markStack.overflow(); } 558 bool mark_stack_empty() { return _markStack.isEmpty(); } 559 560 // (Lock-free) Manipulation of the region stack 561 bool region_stack_push_lock_free(MemRegion mr) { 562 // Currently we only call the lock-free version during evacuation 563 // pauses. 564 assert(SafepointSynchronize::is_at_safepoint(), "world should be stopped"); 565 566 _regionStack.push_lock_free(mr); 567 if (_regionStack.overflow()) { 568 set_has_overflown(); 569 return false; 570 } 571 return true; 572 } 573 574 // Lock-free version of region-stack pop. Should only be 575 // called in tandem with other lock-free pops. 576 MemRegion region_stack_pop_lock_free() { 577 return _regionStack.pop_lock_free(); 578 } 579 580 #if 0 581 // The routines that manipulate the region stack with a lock are 582 // not currently used. They should be retained, however, as a 583 // diagnostic aid. 584 585 bool region_stack_push_with_lock(MemRegion mr) { 586 // Currently we only call the lock-based version during either 587 // concurrent marking or remark. 588 assert(!SafepointSynchronize::is_at_safepoint() || !concurrent(), 589 "if we are at a safepoint it should be the remark safepoint"); 590 591 _regionStack.push_with_lock(mr); 592 if (_regionStack.overflow()) { 593 set_has_overflown(); 594 return false; 595 } 596 return true; 597 } 598 599 MemRegion region_stack_pop_with_lock() { 600 // Currently we only call the lock-based version during either 601 // concurrent marking or remark. 602 assert(!SafepointSynchronize::is_at_safepoint() || !concurrent(), 603 "if we are at a safepoint it should be the remark safepoint"); 604 605 return _regionStack.pop_with_lock(); 606 } 607 #endif 608 609 int region_stack_size() { return _regionStack.size(); } 610 bool region_stack_overflow() { return _regionStack.overflow(); } 611 bool region_stack_empty() { return _regionStack.isEmpty(); } 612 613 // Iterate over any regions that were aborted while draining the 614 // region stack (any such regions are saved in the corresponding 615 // CMTask) and invalidate (i.e. assign to the empty MemRegion()) 616 // any regions that point into the collection set. 617 bool invalidate_aborted_regions_in_cset(); 618 619 // Returns true if there are any aborted memory regions. 620 bool has_aborted_regions(); 621 622 bool concurrent_marking_in_progress() { 623 return _concurrent_marking_in_progress; 624 } 625 void set_concurrent_marking_in_progress() { 626 _concurrent_marking_in_progress = true; 627 } 628 void clear_concurrent_marking_in_progress() { 629 _concurrent_marking_in_progress = false; 630 } 631 632 void update_accum_task_vtime(int i, double vtime) { 633 _accum_task_vtime[i] += vtime; 634 } 635 636 double all_task_accum_vtime() { 637 double ret = 0.0; 638 for (int i = 0; i < (int)_max_task_num; ++i) 639 ret += _accum_task_vtime[i]; 640 return ret; 641 } 642 643 // Attempts to steal an object from the task queues of other tasks 644 bool try_stealing(int task_num, int* hash_seed, oop& obj) { 645 return _task_queues->steal(task_num, hash_seed, obj); 646 } 647 648 // It grays an object by first marking it. Then, if it's behind the 649 // global finger, it also pushes it on the global stack. 650 void deal_with_reference(oop obj); 651 652 ConcurrentMark(ReservedSpace rs, int max_regions); 653 ~ConcurrentMark(); 654 ConcurrentMarkThread* cmThread() { return _cmThread; } 655 656 CMBitMapRO* prevMarkBitMap() const { return _prevMarkBitMap; } 657 CMBitMap* nextMarkBitMap() const { return _nextMarkBitMap; } 658 659 // The following three are interaction between CM and 660 // G1CollectedHeap 661 662 // This notifies CM that a root during initial-mark needs to be 663 // grayed and it's MT-safe. Currently, we just mark it. But, in the 664 // future, we can experiment with pushing it on the stack and we can 665 // do this without changing G1CollectedHeap. 666 void grayRoot(oop p); 667 // It's used during evacuation pauses to gray a region, if 668 // necessary, and it's MT-safe. It assumes that the caller has 669 // marked any objects on that region. If _should_gray_objects is 670 // true and we're still doing concurrent marking, the region is 671 // pushed on the region stack, if it is located below the global 672 // finger, otherwise we do nothing. 673 void grayRegionIfNecessary(MemRegion mr); 674 // It's used during evacuation pauses to mark and, if necessary, 675 // gray a single object and it's MT-safe. It assumes the caller did 676 // not mark the object. If _should_gray_objects is true and we're 677 // still doing concurrent marking, the objects is pushed on the 678 // global stack, if it is located below the global finger, otherwise 679 // we do nothing. 680 void markAndGrayObjectIfNecessary(oop p); 681 682 // It iterates over the heap and for each object it comes across it 683 // will dump the contents of its reference fields, as well as 684 // liveness information for the object and its referents. The dump 685 // will be written to a file with the following name: 686 // G1PrintReachableBaseFile + "." + str. use_prev_marking decides 687 // whether the prev (use_prev_marking == true) or next 688 // (use_prev_marking == false) marking information will be used to 689 // determine the liveness of each object / referent. If all is true, 690 // all objects in the heap will be dumped, otherwise only the live 691 // ones. In the dump the following symbols / abbreviations are used: 692 // M : an explicitly live object (its bitmap bit is set) 693 // > : an implicitly live object (over tams) 694 // O : an object outside the G1 heap (typically: in the perm gen) 695 // NOT : a reference field whose referent is not live 696 // AND MARKED : indicates that an object is both explicitly and 697 // implicitly live (it should be one or the other, not both) 698 void print_reachable(const char* str, 699 bool use_prev_marking, bool all) PRODUCT_RETURN; 700 701 // Clear the next marking bitmap (will be called concurrently). 702 void clearNextBitmap(); 703 704 // main CMS steps and related support 705 void checkpointRootsInitial(); 706 707 // These two do the work that needs to be done before and after the 708 // initial root checkpoint. Since this checkpoint can be done at two 709 // different points (i.e. an explicit pause or piggy-backed on a 710 // young collection), then it's nice to be able to easily share the 711 // pre/post code. It might be the case that we can put everything in 712 // the post method. TP 713 void checkpointRootsInitialPre(); 714 void checkpointRootsInitialPost(); 715 716 // Do concurrent phase of marking, to a tentative transitive closure. 717 void markFromRoots(); 718 719 // Process all unprocessed SATB buffers. It is called at the 720 // beginning of an evacuation pause. 721 void drainAllSATBBuffers(); 722 723 void checkpointRootsFinal(bool clear_all_soft_refs); 724 void checkpointRootsFinalWork(); 725 void calcDesiredRegions(); 726 void cleanup(); 727 void completeCleanup(); 728 729 // Mark in the previous bitmap. NB: this is usually read-only, so use 730 // this carefully! 731 void markPrev(oop p); 732 void clear(oop p); 733 // Clears marks for all objects in the given range, for both prev and 734 // next bitmaps. NB: the previous bitmap is usually read-only, so use 735 // this carefully! 736 void clearRangeBothMaps(MemRegion mr); 737 738 // Record the current top of the mark and region stacks; a 739 // subsequent oops_do() on the mark stack and 740 // invalidate_entries_into_cset() on the region stack will iterate 741 // only over indices valid at the time of this call. 742 void set_oops_do_bound() { 743 _markStack.set_oops_do_bound(); 744 _regionStack.set_oops_do_bound(); 745 } 746 // Iterate over the oops in the mark stack and all local queues. It 747 // also calls invalidate_entries_into_cset() on the region stack. 748 void oops_do(OopClosure* f); 749 // It is called at the end of an evacuation pause during marking so 750 // that CM is notified of where the new end of the heap is. It 751 // doesn't do anything if concurrent_marking_in_progress() is false, 752 // unless the force parameter is true. 753 void update_g1_committed(bool force = false); 754 755 void complete_marking_in_collection_set(); 756 757 // It indicates that a new collection set is being chosen. 758 void newCSet(); 759 // It registers a collection set heap region with CM. This is used 760 // to determine whether any heap regions are located above the finger. 761 void registerCSetRegion(HeapRegion* hr); 762 763 // Registers the maximum region-end associated with a set of 764 // regions with CM. Again this is used to determine whether any 765 // heap regions are located above the finger. 766 void register_collection_set_finger(HeapWord* max_finger) { 767 // max_finger is the highest heap region end of the regions currently 768 // contained in the collection set. If this value is larger than 769 // _min_finger then we need to gray objects. 770 // This routine is like registerCSetRegion but for an entire 771 // collection of regions. 772 if (max_finger > _min_finger) 773 _should_gray_objects = true; 774 } 775 776 // Returns "true" if at least one mark has been completed. 777 bool at_least_one_mark_complete() { return _at_least_one_mark_complete; } 778 779 bool isMarked(oop p) const { 780 assert(p != NULL && p->is_oop(), "expected an oop"); 781 HeapWord* addr = (HeapWord*)p; 782 assert(addr >= _nextMarkBitMap->startWord() || 783 addr < _nextMarkBitMap->endWord(), "in a region"); 784 785 return _nextMarkBitMap->isMarked(addr); 786 } 787 788 inline bool not_yet_marked(oop p) const; 789 790 // XXX Debug code 791 bool containing_card_is_marked(void* p); 792 bool containing_cards_are_marked(void* start, void* last); 793 794 bool isPrevMarked(oop p) const { 795 assert(p != NULL && p->is_oop(), "expected an oop"); 796 HeapWord* addr = (HeapWord*)p; 797 assert(addr >= _prevMarkBitMap->startWord() || 798 addr < _prevMarkBitMap->endWord(), "in a region"); 799 800 return _prevMarkBitMap->isMarked(addr); 801 } 802 803 inline bool do_yield_check(int worker_i = 0); 804 inline bool should_yield(); 805 806 // Called to abort the marking cycle after a Full GC takes palce. 807 void abort(); 808 809 // This prints the global/local fingers. It is used for debugging. 810 NOT_PRODUCT(void print_finger();) 811 812 void print_summary_info(); 813 814 void print_worker_threads_on(outputStream* st) const; 815 816 // The following indicate whether a given verbose level has been 817 // set. Notice that anything above stats is conditional to 818 // _MARKING_VERBOSE_ having been set to 1 819 bool verbose_stats() 820 { return _verbose_level >= stats_verbose; } 821 bool verbose_low() 822 { return _MARKING_VERBOSE_ && _verbose_level >= low_verbose; } 823 bool verbose_medium() 824 { return _MARKING_VERBOSE_ && _verbose_level >= medium_verbose; } 825 bool verbose_high() 826 { return _MARKING_VERBOSE_ && _verbose_level >= high_verbose; } 827 }; 828 829 // A class representing a marking task. 830 class CMTask : public TerminatorTerminator { 831 private: 832 enum PrivateConstants { 833 // the regular clock call is called once the scanned words reaches 834 // this limit 835 words_scanned_period = 12*1024, 836 // the regular clock call is called once the number of visited 837 // references reaches this limit 838 refs_reached_period = 384, 839 // initial value for the hash seed, used in the work stealing code 840 init_hash_seed = 17, 841 // how many entries will be transferred between global stack and 842 // local queues 843 global_stack_transfer_size = 16 844 }; 845 846 int _task_id; 847 G1CollectedHeap* _g1h; 848 ConcurrentMark* _cm; 849 CMBitMap* _nextMarkBitMap; 850 // the task queue of this task 851 CMTaskQueue* _task_queue; 852 private: 853 // the task queue set---needed for stealing 854 CMTaskQueueSet* _task_queues; 855 // indicates whether the task has been claimed---this is only for 856 // debugging purposes 857 bool _claimed; 858 859 // number of calls to this task 860 int _calls; 861 862 // when the virtual timer reaches this time, the marking step should 863 // exit 864 double _time_target_ms; 865 // the start time of the current marking step 866 double _start_time_ms; 867 868 // the oop closure used for iterations over oops 869 OopClosure* _oop_closure; 870 871 // the region this task is scanning, NULL if we're not scanning any 872 HeapRegion* _curr_region; 873 // the local finger of this task, NULL if we're not scanning a region 874 HeapWord* _finger; 875 // limit of the region this task is scanning, NULL if we're not scanning one 876 HeapWord* _region_limit; 877 878 // This is used only when we scan regions popped from the region 879 // stack. It records what the last object on such a region we 880 // scanned was. It is used to ensure that, if we abort region 881 // iteration, we do not rescan the first part of the region. This 882 // should be NULL when we're not scanning a region from the region 883 // stack. 884 HeapWord* _region_finger; 885 886 // If we abort while scanning a region we record the remaining 887 // unscanned portion and check this field when marking restarts. 888 // This avoids having to push on the region stack while other 889 // marking threads may still be popping regions. 890 // If we were to push the unscanned portion directly to the 891 // region stack then we would need to using locking versions 892 // of the push and pop operations. 893 MemRegion _aborted_region; 894 895 // the number of words this task has scanned 896 size_t _words_scanned; 897 // When _words_scanned reaches this limit, the regular clock is 898 // called. Notice that this might be decreased under certain 899 // circumstances (i.e. when we believe that we did an expensive 900 // operation). 901 size_t _words_scanned_limit; 902 // the initial value of _words_scanned_limit (i.e. what it was 903 // before it was decreased). 904 size_t _real_words_scanned_limit; 905 906 // the number of references this task has visited 907 size_t _refs_reached; 908 // When _refs_reached reaches this limit, the regular clock is 909 // called. Notice this this might be decreased under certain 910 // circumstances (i.e. when we believe that we did an expensive 911 // operation). 912 size_t _refs_reached_limit; 913 // the initial value of _refs_reached_limit (i.e. what it was before 914 // it was decreased). 915 size_t _real_refs_reached_limit; 916 917 // used by the work stealing stuff 918 int _hash_seed; 919 // if this is true, then the task has aborted for some reason 920 bool _has_aborted; 921 // set when the task aborts because it has met its time quota 922 bool _has_aborted_timed_out; 923 // true when we're draining SATB buffers; this avoids the task 924 // aborting due to SATB buffers being available (as we're already 925 // dealing with them) 926 bool _draining_satb_buffers; 927 928 // number sequence of past step times 929 NumberSeq _step_times_ms; 930 // elapsed time of this task 931 double _elapsed_time_ms; 932 // termination time of this task 933 double _termination_time_ms; 934 // when this task got into the termination protocol 935 double _termination_start_time_ms; 936 937 // true when the task is during a concurrent phase, false when it is 938 // in the remark phase (so, in the latter case, we do not have to 939 // check all the things that we have to check during the concurrent 940 // phase, i.e. SATB buffer availability...) 941 bool _concurrent; 942 943 TruncatedSeq _marking_step_diffs_ms; 944 945 // LOTS of statistics related with this task 946 #if _MARKING_STATS_ 947 NumberSeq _all_clock_intervals_ms; 948 double _interval_start_time_ms; 949 950 int _aborted; 951 int _aborted_overflow; 952 int _aborted_cm_aborted; 953 int _aborted_yield; 954 int _aborted_timed_out; 955 int _aborted_satb; 956 int _aborted_termination; 957 958 int _steal_attempts; 959 int _steals; 960 961 int _clock_due_to_marking; 962 int _clock_due_to_scanning; 963 964 int _local_pushes; 965 int _local_pops; 966 int _local_max_size; 967 int _objs_scanned; 968 969 int _global_pushes; 970 int _global_pops; 971 int _global_max_size; 972 973 int _global_transfers_to; 974 int _global_transfers_from; 975 976 int _region_stack_pops; 977 978 int _regions_claimed; 979 int _objs_found_on_bitmap; 980 981 int _satb_buffers_processed; 982 #endif // _MARKING_STATS_ 983 984 // it updates the local fields after this task has claimed 985 // a new region to scan 986 void setup_for_region(HeapRegion* hr); 987 // it brings up-to-date the limit of the region 988 void update_region_limit(); 989 // it resets the local fields after a task has finished scanning a 990 // region 991 void giveup_current_region(); 992 993 // called when either the words scanned or the refs visited limit 994 // has been reached 995 void reached_limit(); 996 // recalculates the words scanned and refs visited limits 997 void recalculate_limits(); 998 // decreases the words scanned and refs visited limits when we reach 999 // an expensive operation 1000 void decrease_limits(); 1001 // it checks whether the words scanned or refs visited reached their 1002 // respective limit and calls reached_limit() if they have 1003 void check_limits() { 1004 if (_words_scanned >= _words_scanned_limit || 1005 _refs_reached >= _refs_reached_limit) 1006 reached_limit(); 1007 } 1008 // this is supposed to be called regularly during a marking step as 1009 // it checks a bunch of conditions that might cause the marking step 1010 // to abort 1011 void regular_clock_call(); 1012 bool concurrent() { return _concurrent; } 1013 1014 public: 1015 // It resets the task; it should be called right at the beginning of 1016 // a marking phase. 1017 void reset(CMBitMap* _nextMarkBitMap); 1018 // it clears all the fields that correspond to a claimed region. 1019 void clear_region_fields(); 1020 1021 void set_concurrent(bool concurrent) { _concurrent = concurrent; } 1022 1023 // The main method of this class which performs a marking step 1024 // trying not to exceed the given duration. However, it might exit 1025 // prematurely, according to some conditions (i.e. SATB buffers are 1026 // available for processing). 1027 void do_marking_step(double target_ms); 1028 1029 // These two calls start and stop the timer 1030 void record_start_time() { 1031 _elapsed_time_ms = os::elapsedTime() * 1000.0; 1032 } 1033 void record_end_time() { 1034 _elapsed_time_ms = os::elapsedTime() * 1000.0 - _elapsed_time_ms; 1035 } 1036 1037 // returns the task ID 1038 int task_id() { return _task_id; } 1039 1040 // From TerminatorTerminator. It determines whether this task should 1041 // exit the termination protocol after it's entered it. 1042 virtual bool should_exit_termination(); 1043 1044 HeapWord* finger() { return _finger; } 1045 1046 bool has_aborted() { return _has_aborted; } 1047 void set_has_aborted() { _has_aborted = true; } 1048 void clear_has_aborted() { _has_aborted = false; } 1049 bool claimed() { return _claimed; } 1050 1051 // Support routines for the partially scanned region that may be 1052 // recorded as a result of aborting while draining the CMRegionStack 1053 MemRegion aborted_region() { return _aborted_region; } 1054 void set_aborted_region(MemRegion mr) 1055 { _aborted_region = mr; } 1056 1057 // Clears any recorded partially scanned region 1058 void clear_aborted_region() { set_aborted_region(MemRegion()); } 1059 1060 void set_oop_closure(OopClosure* oop_closure) { 1061 _oop_closure = oop_closure; 1062 } 1063 1064 // It grays the object by marking it and, if necessary, pushing it 1065 // on the local queue 1066 void deal_with_reference(oop obj); 1067 1068 // It scans an object and visits its children. 1069 void scan_object(oop obj) { 1070 assert(_nextMarkBitMap->isMarked((HeapWord*) obj), "invariant"); 1071 1072 if (_cm->verbose_high()) 1073 gclog_or_tty->print_cr("[%d] we're scanning object "PTR_FORMAT, 1074 _task_id, (void*) obj); 1075 1076 size_t obj_size = obj->size(); 1077 _words_scanned += obj_size; 1078 1079 obj->oop_iterate(_oop_closure); 1080 statsOnly( ++_objs_scanned ); 1081 check_limits(); 1082 } 1083 1084 // It pushes an object on the local queue. 1085 void push(oop obj); 1086 1087 // These two move entries to/from the global stack. 1088 void move_entries_to_global_stack(); 1089 void get_entries_from_global_stack(); 1090 1091 // It pops and scans objects from the local queue. If partially is 1092 // true, then it stops when the queue size is of a given limit. If 1093 // partially is false, then it stops when the queue is empty. 1094 void drain_local_queue(bool partially); 1095 // It moves entries from the global stack to the local queue and 1096 // drains the local queue. If partially is true, then it stops when 1097 // both the global stack and the local queue reach a given size. If 1098 // partially if false, it tries to empty them totally. 1099 void drain_global_stack(bool partially); 1100 // It keeps picking SATB buffers and processing them until no SATB 1101 // buffers are available. 1102 void drain_satb_buffers(); 1103 // It keeps popping regions from the region stack and processing 1104 // them until the region stack is empty. 1105 void drain_region_stack(BitMapClosure* closure); 1106 1107 // moves the local finger to a new location 1108 inline void move_finger_to(HeapWord* new_finger) { 1109 assert(new_finger >= _finger && new_finger < _region_limit, "invariant"); 1110 _finger = new_finger; 1111 } 1112 1113 // moves the region finger to a new location 1114 inline void move_region_finger_to(HeapWord* new_finger) { 1115 assert(new_finger < _cm->finger(), "invariant"); 1116 _region_finger = new_finger; 1117 } 1118 1119 CMTask(int task_num, ConcurrentMark *cm, 1120 CMTaskQueue* task_queue, CMTaskQueueSet* task_queues); 1121 1122 // it prints statistics associated with this task 1123 void print_stats(); 1124 1125 #if _MARKING_STATS_ 1126 void increase_objs_found_on_bitmap() { ++_objs_found_on_bitmap; } 1127 #endif // _MARKING_STATS_ 1128 }; 1129 1130 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_CONCURRENTMARK_HPP