src/share/vm/gc_implementation/g1/concurrentMark.hpp

Print this page
rev 3708 : 8000244: G1: Ergonomically set MarkStackSize and use virtual space for global marking stack
Summary: Set the value of MarkStackSize to a value based on the number of parallel marking threads with a reasonable minimum. Expand the marking stack if we have to restart marking due to an overflow up to a reasonable maximum. Allocate the underlying space for the marking stack from virtual memory.
Reviewed-by: jmasa


  46 
  47   void do_object(oop obj) {
  48     ShouldNotCallThis();
  49   }
  50   bool do_object_b(oop obj);
  51 };
  52 
  53 // A generic CM bit map.  This is essentially a wrapper around the BitMap
  54 // class, with one bit per (1<<_shifter) HeapWords.
  55 
  56 class CMBitMapRO VALUE_OBJ_CLASS_SPEC {
  57  protected:
  58   HeapWord* _bmStartWord;      // base address of range covered by map
  59   size_t    _bmWordSize;       // map size (in #HeapWords covered)
  60   const int _shifter;          // map to char or bit
  61   VirtualSpace _virtual_space; // underlying the bit map
  62   BitMap    _bm;               // the bit map itself
  63 
  64  public:
  65   // constructor
  66   CMBitMapRO(ReservedSpace rs, int shifter);
  67 
  68   enum { do_yield = true };
  69 
  70   // inquiries
  71   HeapWord* startWord()   const { return _bmStartWord; }
  72   size_t    sizeInWords() const { return _bmWordSize;  }
  73   // the following is one past the last word in space
  74   HeapWord* endWord()     const { return _bmStartWord + _bmWordSize; }
  75 
  76   // read marks
  77 
  78   bool isMarked(HeapWord* addr) const {
  79     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
  80            "outside underlying space?");
  81     return _bm.at(heapWordToOffset(addr));
  82   }
  83 
  84   // iteration
  85   inline bool iterate(BitMapClosure* cl, MemRegion mr);
  86   inline bool iterate(BitMapClosure* cl);


 100   // XXX Fix these so that offsets are size_t's...
 101   HeapWord* offsetToHeapWord(size_t offset) const {
 102     return _bmStartWord + (offset << _shifter);
 103   }
 104   size_t heapWordToOffset(HeapWord* addr) const {
 105     return pointer_delta(addr, _bmStartWord) >> _shifter;
 106   }
 107   int heapWordDiffToOffsetDiff(size_t diff) const;
 108   HeapWord* nextWord(HeapWord* addr) {
 109     return offsetToHeapWord(heapWordToOffset(addr) + 1);
 110   }
 111 
 112   // debugging
 113   NOT_PRODUCT(bool covers(ReservedSpace rs) const;)
 114 };
 115 
 116 class CMBitMap : public CMBitMapRO {
 117 
 118  public:
 119   // constructor
 120   CMBitMap(ReservedSpace rs, int shifter) :
 121     CMBitMapRO(rs, shifter) {}



 122 
 123   // write marks
 124   void mark(HeapWord* addr) {
 125     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 126            "outside underlying space?");
 127     _bm.set_bit(heapWordToOffset(addr));
 128   }
 129   void clear(HeapWord* addr) {
 130     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 131            "outside underlying space?");
 132     _bm.clear_bit(heapWordToOffset(addr));
 133   }
 134   bool parMark(HeapWord* addr) {
 135     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 136            "outside underlying space?");
 137     return _bm.par_set_bit(heapWordToOffset(addr));
 138   }
 139   bool parClear(HeapWord* addr) {
 140     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 141            "outside underlying space?");
 142     return _bm.par_clear_bit(heapWordToOffset(addr));
 143   }
 144   void markRange(MemRegion mr);
 145   void clearAll();
 146   void clearRange(MemRegion mr);
 147 
 148   // Starting at the bit corresponding to "addr" (inclusive), find the next
 149   // "1" bit, if any.  This bit starts some run of consecutive "1"'s; find
 150   // the end of this run (stopping at "end_addr").  Return the MemRegion
 151   // covering from the start of the region corresponding to the first bit
 152   // of the run to the end of the region corresponding to the last bit of
 153   // the run.  If there is no "1" bit at or after "addr", return an empty
 154   // MemRegion.
 155   MemRegion getAndClearMarkedRegion(HeapWord* addr, HeapWord* end_addr);
 156 };
 157 
 158 // Represents a marking stack used by the CM collector.
 159 // Ideally this should be GrowableArray<> just like MSC's marking stack(s).
 160 class CMMarkStack VALUE_OBJ_CLASS_SPEC {

 161   ConcurrentMark* _cm;
 162   oop*   _base;        // bottom of stack
 163   jint   _index;       // one more than last occupied index
 164   jint   _capacity;    // max #elements
 165   jint   _saved_index; // value of _index saved at start of GC
 166   NOT_PRODUCT(jint _max_depth;)  // max depth plumbed during run
 167 
 168   bool   _overflow;

 169   DEBUG_ONLY(bool _drain_in_progress;)
 170   DEBUG_ONLY(bool _drain_in_progress_yields;)
 171 
 172  public:
 173   CMMarkStack(ConcurrentMark* cm);
 174   ~CMMarkStack();
 175 
 176   void allocate(size_t size);






 177 
 178   oop pop() {
 179     if (!isEmpty()) {
 180       return _base[--_index] ;
 181     }
 182     return NULL;
 183   }
 184 
 185   // If overflow happens, don't do the push, and record the overflow.
 186   // *Requires* that "ptr" is already marked.
 187   void push(oop ptr) {
 188     if (isFull()) {
 189       // Record overflow.
 190       _overflow = true;
 191       return;
 192     } else {
 193       _base[_index++] = ptr;
 194       NOT_PRODUCT(_max_depth = MAX2(_max_depth, _index));
 195     }
 196   }


 219   bool par_pop_arr(oop* ptr_arr, int max, int* n);
 220 
 221   // Drain the mark stack, applying the given closure to all fields of
 222   // objects on the stack.  (That is, continue until the stack is empty,
 223   // even if closure applications add entries to the stack.)  The "bm"
 224   // argument, if non-null, may be used to verify that only marked objects
 225   // are on the mark stack.  If "yield_after" is "true", then the
 226   // concurrent marker performing the drain offers to yield after
 227   // processing each object.  If a yield occurs, stops the drain operation
 228   // and returns false.  Otherwise, returns true.
 229   template<class OopClosureClass>
 230   bool drain(OopClosureClass* cl, CMBitMap* bm, bool yield_after = false);
 231 
 232   bool isEmpty()    { return _index == 0; }
 233   bool isFull()     { return _index == _capacity; }
 234   int maxElems()    { return _capacity; }
 235 
 236   bool overflow() { return _overflow; }
 237   void clear_overflow() { _overflow = false; }
 238 






 239   int  size() { return _index; }
 240 
 241   void setEmpty()   { _index = 0; clear_overflow(); }
 242 
 243   // Record the current index.
 244   void note_start_of_gc();
 245 
 246   // Make sure that we have not added any entries to the stack during GC.
 247   void note_end_of_gc();
 248 
 249   // iterate over the oops in the mark stack, up to the bound recorded via
 250   // the call above.
 251   void oops_do(OopClosure* f);
 252 };
 253 
 254 class ForceOverflowSettings VALUE_OBJ_CLASS_SPEC {
 255 private:
 256 #ifndef PRODUCT
 257   uintx _num_remaining;
 258   bool _force;


 327   // false otherwise.
 328   bool scan_in_progress() { return _scan_in_progress; }
 329 
 330   // Claim the next root region to scan atomically, or return NULL if
 331   // all have been claimed.
 332   HeapRegion* claim_next();
 333 
 334   // Flag that we're done with root region scanning and notify anyone
 335   // who's waiting on it. If aborted is false, assume that all regions
 336   // have been claimed.
 337   void scan_finished();
 338 
 339   // If CM threads are still scanning root regions, wait until they
 340   // are done. Return true if we had to wait, false otherwise.
 341   bool wait_until_scan_finished();
 342 };
 343 
 344 class ConcurrentMarkThread;
 345 
 346 class ConcurrentMark: public CHeapObj<mtGC> {

 347   friend class ConcurrentMarkThread;
 348   friend class CMTask;
 349   friend class CMBitMapClosure;
 350   friend class CMGlobalObjectClosure;
 351   friend class CMRemarkTask;
 352   friend class CMConcurrentMarkingTask;
 353   friend class G1ParNoteEndTask;
 354   friend class CalcLiveObjectsClosure;
 355   friend class G1CMRefProcTaskProxy;
 356   friend class G1CMRefProcTaskExecutor;
 357   friend class G1CMParKeepAliveAndDrainClosure;
 358   friend class G1CMParDrainMarkingStackClosure;
 359 
 360 protected:
 361   ConcurrentMarkThread* _cmThread;   // the thread doing the work
 362   G1CollectedHeap*      _g1h;        // the heap.
 363   uint                  _parallel_marking_threads; // the number of marking
 364                                                    // threads we're use
 365   uint                  _max_parallel_marking_threads; // max number of marking
 366                                                    // threads we'll ever use


 560   // These data structures are initialized at the start of
 561   // marking. They are written to while marking is active.
 562   // They are aggregated during remark; the aggregated values
 563   // are then used to populate the _region_bm, _card_bm, and
 564   // the total live bytes, which are then subsequently updated
 565   // during cleanup.
 566 
 567   // An array of bitmaps (one bit map per task). Each bitmap
 568   // is used to record the cards spanned by the live objects
 569   // marked by that task/worker.
 570   BitMap*  _count_card_bitmaps;
 571 
 572   // Used to record the number of marked live bytes
 573   // (for each region, by worker thread).
 574   size_t** _count_marked_bytes;
 575 
 576   // Card index of the bottom of the G1 heap. Used for biasing indices into
 577   // the card bitmaps.
 578   intptr_t _heap_bottom_card_num;
 579 



 580 public:
 581   // Manipulation of the global mark stack.
 582   // Notice that the first mark_stack_push is CAS-based, whereas the
 583   // two below are Mutex-based. This is OK since the first one is only
 584   // called during evacuation pauses and doesn't compete with the
 585   // other two (which are called by the marking tasks during
 586   // concurrent marking or remark).
 587   bool mark_stack_push(oop p) {
 588     _markStack.par_push(p);
 589     if (_markStack.overflow()) {
 590       set_has_overflown();
 591       return false;
 592     }
 593     return true;
 594   }
 595   bool mark_stack_push(oop* arr, int n) {
 596     _markStack.par_push_arr(arr, n);
 597     if (_markStack.overflow()) {
 598       set_has_overflown();
 599       return false;


 619   void clear_concurrent_marking_in_progress() {
 620     _concurrent_marking_in_progress = false;
 621   }
 622 
 623   void update_accum_task_vtime(int i, double vtime) {
 624     _accum_task_vtime[i] += vtime;
 625   }
 626 
 627   double all_task_accum_vtime() {
 628     double ret = 0.0;
 629     for (uint i = 0; i < _max_worker_id; ++i)
 630       ret += _accum_task_vtime[i];
 631     return ret;
 632   }
 633 
 634   // Attempts to steal an object from the task queues of other tasks
 635   bool try_stealing(uint worker_id, int* hash_seed, oop& obj) {
 636     return _task_queues->steal(worker_id, hash_seed, obj);
 637   }
 638 
 639   ConcurrentMark(ReservedSpace rs, uint max_regions);
 640   ~ConcurrentMark();
 641 
 642   ConcurrentMarkThread* cmThread() { return _cmThread; }
 643 
 644   CMBitMapRO* prevMarkBitMap() const { return _prevMarkBitMap; }
 645   CMBitMap*   nextMarkBitMap() const { return _nextMarkBitMap; }
 646 
 647   // Returns the number of GC threads to be used in a concurrent
 648   // phase based on the number of GC threads being used in a STW
 649   // phase.
 650   uint scale_parallel_threads(uint n_par_threads);
 651 
 652   // Calculates the number of GC threads to be used in a concurrent phase.
 653   uint calc_parallel_marking_threads();
 654 
 655   // The following three are interaction between CM and
 656   // G1CollectedHeap
 657 
 658   // This notifies CM that a root during initial-mark needs to be
 659   // grayed. It is MT-safe. word_size is the size of the object in


 890   // Similar to the above routine but we don't know the heap region that
 891   // contains the object to be marked/counted, which this routine looks up.
 892   inline bool par_mark_and_count(oop obj, uint worker_id);
 893 
 894   // Similar to the above routine but there are times when we cannot
 895   // safely calculate the size of obj due to races and we, therefore,
 896   // pass the size in as a parameter. It is the caller's reponsibility
 897   // to ensure that the size passed in for obj is valid.
 898   inline bool par_mark_and_count(oop obj, size_t word_size, uint worker_id);
 899 
 900   // Unconditionally mark the given object, and unconditinally count
 901   // the object in the counting structures for worker id 0.
 902   // Should *not* be called from parallel code.
 903   inline bool mark_and_count(oop obj, HeapRegion* hr);
 904 
 905   // Similar to the above routine but we don't know the heap region that
 906   // contains the object to be marked/counted, which this routine looks up.
 907   // Should *not* be called from parallel code.
 908   inline bool mark_and_count(oop obj);
 909 





 910 protected:
 911   // Clear all the per-task bitmaps and arrays used to store the
 912   // counting data.
 913   void clear_all_count_data();
 914 
 915   // Aggregates the counting data for each worker/task
 916   // that was constructed while marking. Also sets
 917   // the amount of marked bytes for each region and
 918   // the top at concurrent mark count.
 919   void aggregate_count_data();
 920 
 921   // Verification routine
 922   void verify_count_data();
 923 };
 924 
 925 // A class representing a marking task.
 926 class CMTask : public TerminatorTerminator {
 927 private:
 928   enum PrivateConstants {
 929     // the regular clock call is called once the scanned words reaches




  46 
  47   void do_object(oop obj) {
  48     ShouldNotCallThis();
  49   }
  50   bool do_object_b(oop obj);
  51 };
  52 
  53 // A generic CM bit map.  This is essentially a wrapper around the BitMap
  54 // class, with one bit per (1<<_shifter) HeapWords.
  55 
  56 class CMBitMapRO VALUE_OBJ_CLASS_SPEC {
  57  protected:
  58   HeapWord* _bmStartWord;      // base address of range covered by map
  59   size_t    _bmWordSize;       // map size (in #HeapWords covered)
  60   const int _shifter;          // map to char or bit
  61   VirtualSpace _virtual_space; // underlying the bit map
  62   BitMap    _bm;               // the bit map itself
  63 
  64  public:
  65   // constructor
  66   CMBitMapRO(int shifter);
  67 
  68   enum { do_yield = true };
  69 
  70   // inquiries
  71   HeapWord* startWord()   const { return _bmStartWord; }
  72   size_t    sizeInWords() const { return _bmWordSize;  }
  73   // the following is one past the last word in space
  74   HeapWord* endWord()     const { return _bmStartWord + _bmWordSize; }
  75 
  76   // read marks
  77 
  78   bool isMarked(HeapWord* addr) const {
  79     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
  80            "outside underlying space?");
  81     return _bm.at(heapWordToOffset(addr));
  82   }
  83 
  84   // iteration
  85   inline bool iterate(BitMapClosure* cl, MemRegion mr);
  86   inline bool iterate(BitMapClosure* cl);


 100   // XXX Fix these so that offsets are size_t's...
 101   HeapWord* offsetToHeapWord(size_t offset) const {
 102     return _bmStartWord + (offset << _shifter);
 103   }
 104   size_t heapWordToOffset(HeapWord* addr) const {
 105     return pointer_delta(addr, _bmStartWord) >> _shifter;
 106   }
 107   int heapWordDiffToOffsetDiff(size_t diff) const;
 108   HeapWord* nextWord(HeapWord* addr) {
 109     return offsetToHeapWord(heapWordToOffset(addr) + 1);
 110   }
 111 
 112   // debugging
 113   NOT_PRODUCT(bool covers(ReservedSpace rs) const;)
 114 };
 115 
 116 class CMBitMap : public CMBitMapRO {
 117 
 118  public:
 119   // constructor
 120   CMBitMap(int shifter) :
 121     CMBitMapRO(shifter) {}
 122 
 123   // Allocates the back store for the marking bitmap
 124   bool allocate(ReservedSpace heap_rs);
 125 
 126   // write marks
 127   void mark(HeapWord* addr) {
 128     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 129            "outside underlying space?");
 130     _bm.set_bit(heapWordToOffset(addr));
 131   }
 132   void clear(HeapWord* addr) {
 133     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 134            "outside underlying space?");
 135     _bm.clear_bit(heapWordToOffset(addr));
 136   }
 137   bool parMark(HeapWord* addr) {
 138     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 139            "outside underlying space?");
 140     return _bm.par_set_bit(heapWordToOffset(addr));
 141   }
 142   bool parClear(HeapWord* addr) {
 143     assert(_bmStartWord <= addr && addr < (_bmStartWord + _bmWordSize),
 144            "outside underlying space?");
 145     return _bm.par_clear_bit(heapWordToOffset(addr));
 146   }
 147   void markRange(MemRegion mr);
 148   void clearAll();
 149   void clearRange(MemRegion mr);
 150 
 151   // Starting at the bit corresponding to "addr" (inclusive), find the next
 152   // "1" bit, if any.  This bit starts some run of consecutive "1"'s; find
 153   // the end of this run (stopping at "end_addr").  Return the MemRegion
 154   // covering from the start of the region corresponding to the first bit
 155   // of the run to the end of the region corresponding to the last bit of
 156   // the run.  If there is no "1" bit at or after "addr", return an empty
 157   // MemRegion.
 158   MemRegion getAndClearMarkedRegion(HeapWord* addr, HeapWord* end_addr);
 159 };
 160 
 161 // Represents a marking stack used by ConcurrentMarking in the G1 collector.

 162 class CMMarkStack VALUE_OBJ_CLASS_SPEC {
 163   VirtualSpace _virtual_space;   // Underlying backing store for actual stack
 164   ConcurrentMark* _cm;
 165   oop*   _base;        // bottom of stack
 166   jint _index;       // one more than last occupied index
 167   jint _capacity;    // max #elements
 168   jint _saved_index; // value of _index saved at start of GC
 169   NOT_PRODUCT(jint _max_depth;)   // max depth plumbed during run
 170 
 171   bool  _overflow;
 172   bool  _should_expand;
 173   DEBUG_ONLY(bool _drain_in_progress;)
 174   DEBUG_ONLY(bool _drain_in_progress_yields;)
 175 
 176  public:
 177   CMMarkStack(ConcurrentMark* cm);
 178   ~CMMarkStack();
 179 
 180 #ifndef PRODUCT
 181   jint max_depth() const {
 182     return _max_depth;
 183   }
 184 #endif
 185 
 186   bool allocate(size_t capacity);
 187 
 188   oop pop() {
 189     if (!isEmpty()) {
 190       return _base[--_index] ;
 191     }
 192     return NULL;
 193   }
 194 
 195   // If overflow happens, don't do the push, and record the overflow.
 196   // *Requires* that "ptr" is already marked.
 197   void push(oop ptr) {
 198     if (isFull()) {
 199       // Record overflow.
 200       _overflow = true;
 201       return;
 202     } else {
 203       _base[_index++] = ptr;
 204       NOT_PRODUCT(_max_depth = MAX2(_max_depth, _index));
 205     }
 206   }


 229   bool par_pop_arr(oop* ptr_arr, int max, int* n);
 230 
 231   // Drain the mark stack, applying the given closure to all fields of
 232   // objects on the stack.  (That is, continue until the stack is empty,
 233   // even if closure applications add entries to the stack.)  The "bm"
 234   // argument, if non-null, may be used to verify that only marked objects
 235   // are on the mark stack.  If "yield_after" is "true", then the
 236   // concurrent marker performing the drain offers to yield after
 237   // processing each object.  If a yield occurs, stops the drain operation
 238   // and returns false.  Otherwise, returns true.
 239   template<class OopClosureClass>
 240   bool drain(OopClosureClass* cl, CMBitMap* bm, bool yield_after = false);
 241 
 242   bool isEmpty()    { return _index == 0; }
 243   bool isFull()     { return _index == _capacity; }
 244   int  maxElems()   { return _capacity; }
 245 
 246   bool overflow() { return _overflow; }
 247   void clear_overflow() { _overflow = false; }
 248 
 249   bool should_expand() const { return _should_expand; }
 250   void set_should_expand();
 251 
 252   // Expand the stack, typically in response to an overflow condition
 253   void expand();
 254 
 255   int  size() { return _index; }
 256 
 257   void setEmpty()   { _index = 0; clear_overflow(); }
 258 
 259   // Record the current index.
 260   void note_start_of_gc();
 261 
 262   // Make sure that we have not added any entries to the stack during GC.
 263   void note_end_of_gc();
 264 
 265   // iterate over the oops in the mark stack, up to the bound recorded via
 266   // the call above.
 267   void oops_do(OopClosure* f);
 268 };
 269 
 270 class ForceOverflowSettings VALUE_OBJ_CLASS_SPEC {
 271 private:
 272 #ifndef PRODUCT
 273   uintx _num_remaining;
 274   bool _force;


 343   // false otherwise.
 344   bool scan_in_progress() { return _scan_in_progress; }
 345 
 346   // Claim the next root region to scan atomically, or return NULL if
 347   // all have been claimed.
 348   HeapRegion* claim_next();
 349 
 350   // Flag that we're done with root region scanning and notify anyone
 351   // who's waiting on it. If aborted is false, assume that all regions
 352   // have been claimed.
 353   void scan_finished();
 354 
 355   // If CM threads are still scanning root regions, wait until they
 356   // are done. Return true if we had to wait, false otherwise.
 357   bool wait_until_scan_finished();
 358 };
 359 
 360 class ConcurrentMarkThread;
 361 
 362 class ConcurrentMark: public CHeapObj<mtGC> {
 363   friend class CMMarkStack;
 364   friend class ConcurrentMarkThread;
 365   friend class CMTask;
 366   friend class CMBitMapClosure;
 367   friend class CMGlobalObjectClosure;
 368   friend class CMRemarkTask;
 369   friend class CMConcurrentMarkingTask;
 370   friend class G1ParNoteEndTask;
 371   friend class CalcLiveObjectsClosure;
 372   friend class G1CMRefProcTaskProxy;
 373   friend class G1CMRefProcTaskExecutor;
 374   friend class G1CMParKeepAliveAndDrainClosure;
 375   friend class G1CMParDrainMarkingStackClosure;
 376 
 377 protected:
 378   ConcurrentMarkThread* _cmThread;   // the thread doing the work
 379   G1CollectedHeap*      _g1h;        // the heap.
 380   uint                  _parallel_marking_threads; // the number of marking
 381                                                    // threads we're use
 382   uint                  _max_parallel_marking_threads; // max number of marking
 383                                                    // threads we'll ever use


 577   // These data structures are initialized at the start of
 578   // marking. They are written to while marking is active.
 579   // They are aggregated during remark; the aggregated values
 580   // are then used to populate the _region_bm, _card_bm, and
 581   // the total live bytes, which are then subsequently updated
 582   // during cleanup.
 583 
 584   // An array of bitmaps (one bit map per task). Each bitmap
 585   // is used to record the cards spanned by the live objects
 586   // marked by that task/worker.
 587   BitMap*  _count_card_bitmaps;
 588 
 589   // Used to record the number of marked live bytes
 590   // (for each region, by worker thread).
 591   size_t** _count_marked_bytes;
 592 
 593   // Card index of the bottom of the G1 heap. Used for biasing indices into
 594   // the card bitmaps.
 595   intptr_t _heap_bottom_card_num;
 596 
 597   // Set to true when initialization is complete
 598   bool _completed_initialization;
 599 
 600 public:
 601   // Manipulation of the global mark stack.
 602   // Notice that the first mark_stack_push is CAS-based, whereas the
 603   // two below are Mutex-based. This is OK since the first one is only
 604   // called during evacuation pauses and doesn't compete with the
 605   // other two (which are called by the marking tasks during
 606   // concurrent marking or remark).
 607   bool mark_stack_push(oop p) {
 608     _markStack.par_push(p);
 609     if (_markStack.overflow()) {
 610       set_has_overflown();
 611       return false;
 612     }
 613     return true;
 614   }
 615   bool mark_stack_push(oop* arr, int n) {
 616     _markStack.par_push_arr(arr, n);
 617     if (_markStack.overflow()) {
 618       set_has_overflown();
 619       return false;


 639   void clear_concurrent_marking_in_progress() {
 640     _concurrent_marking_in_progress = false;
 641   }
 642 
 643   void update_accum_task_vtime(int i, double vtime) {
 644     _accum_task_vtime[i] += vtime;
 645   }
 646 
 647   double all_task_accum_vtime() {
 648     double ret = 0.0;
 649     for (uint i = 0; i < _max_worker_id; ++i)
 650       ret += _accum_task_vtime[i];
 651     return ret;
 652   }
 653 
 654   // Attempts to steal an object from the task queues of other tasks
 655   bool try_stealing(uint worker_id, int* hash_seed, oop& obj) {
 656     return _task_queues->steal(worker_id, hash_seed, obj);
 657   }
 658 
 659   ConcurrentMark(G1CollectedHeap* g1h, ReservedSpace heap_rs);
 660   ~ConcurrentMark();
 661 
 662   ConcurrentMarkThread* cmThread() { return _cmThread; }
 663 
 664   CMBitMapRO* prevMarkBitMap() const { return _prevMarkBitMap; }
 665   CMBitMap*   nextMarkBitMap() const { return _nextMarkBitMap; }
 666 
 667   // Returns the number of GC threads to be used in a concurrent
 668   // phase based on the number of GC threads being used in a STW
 669   // phase.
 670   uint scale_parallel_threads(uint n_par_threads);
 671 
 672   // Calculates the number of GC threads to be used in a concurrent phase.
 673   uint calc_parallel_marking_threads();
 674 
 675   // The following three are interaction between CM and
 676   // G1CollectedHeap
 677 
 678   // This notifies CM that a root during initial-mark needs to be
 679   // grayed. It is MT-safe. word_size is the size of the object in


 910   // Similar to the above routine but we don't know the heap region that
 911   // contains the object to be marked/counted, which this routine looks up.
 912   inline bool par_mark_and_count(oop obj, uint worker_id);
 913 
 914   // Similar to the above routine but there are times when we cannot
 915   // safely calculate the size of obj due to races and we, therefore,
 916   // pass the size in as a parameter. It is the caller's reponsibility
 917   // to ensure that the size passed in for obj is valid.
 918   inline bool par_mark_and_count(oop obj, size_t word_size, uint worker_id);
 919 
 920   // Unconditionally mark the given object, and unconditinally count
 921   // the object in the counting structures for worker id 0.
 922   // Should *not* be called from parallel code.
 923   inline bool mark_and_count(oop obj, HeapRegion* hr);
 924 
 925   // Similar to the above routine but we don't know the heap region that
 926   // contains the object to be marked/counted, which this routine looks up.
 927   // Should *not* be called from parallel code.
 928   inline bool mark_and_count(oop obj);
 929 
 930   // Returns true if initialization was successfully completed.
 931   bool completed_initialization() const {
 932     return _completed_initialization;
 933   }
 934 
 935 protected:
 936   // Clear all the per-task bitmaps and arrays used to store the
 937   // counting data.
 938   void clear_all_count_data();
 939 
 940   // Aggregates the counting data for each worker/task
 941   // that was constructed while marking. Also sets
 942   // the amount of marked bytes for each region and
 943   // the top at concurrent mark count.
 944   void aggregate_count_data();
 945 
 946   // Verification routine
 947   void verify_count_data();
 948 };
 949 
 950 // A class representing a marking task.
 951 class CMTask : public TerminatorTerminator {
 952 private:
 953   enum PrivateConstants {
 954     // the regular clock call is called once the scanned words reaches