1 /*
   2  * Copyright (c) 1997, 2015, 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_SERIAL_MARKSWEEP_HPP
  26 #define SHARE_VM_GC_SERIAL_MARKSWEEP_HPP
  27 
  28 #include "gc/cms/compactibleFreeListSpace.hpp"
  29 #include "gc/shared/collectedHeap.hpp"
  30 #include "gc/shared/genCollectedHeap.hpp"
  31 #include "gc/shared/genOopClosures.hpp"
  32 #include "gc/shared/space.hpp"
  33 #include "gc/shared/strongRootsScope.hpp"
  34 #include "gc/shared/taskqueue.inline.hpp"
  35 #include "memory/iterator.hpp"
  36 #include "oops/markOop.hpp"
  37 #include "oops/oop.hpp"
  38 #include "runtime/prefetch.inline.hpp"
  39 #include "runtime/timer.hpp"
  40 #include "utilities/growableArray.hpp"
  41 #include "utilities/stack.hpp"
  42 
  43 class ReferenceProcessor;
  44 class DataLayout;
  45 class SerialOldTracer;
  46 class STWGCTimer;
  47 
  48 // MarkSweep takes care of global mark-compact garbage collection for a
  49 // GenCollectedHeap using a four-phase pointer forwarding algorithm.  All
  50 // generations are assumed to support marking; those that can also support
  51 // compaction.
  52 //
  53 // Class unloading will only occur when a full gc is invoked.
  54 
  55 // declared at end
  56 class PreservedMark;
  57 class PMSMarkBitMap;
  58 class PMSRegion;
  59 class PMSRegionArray;
  60 class PMSRegionArraySet;
  61 typedef OverflowTaskQueue<PMSRegion*, mtGC>                  PMSRegionTaskQueue;
  62 typedef GenericTaskQueueSet<PMSRegionTaskQueue, mtGC>        PMSRegionTaskQueueSet;
  63 
  64 class MarkSweep : AllStatic {
  65   //
  66   // Inline closure decls
  67   //
  68   class FollowRootClosure: public OopsInGenClosure {
  69    public:
  70     virtual void do_oop(oop* p);
  71     virtual void do_oop(narrowOop* p);
  72   };
  73 
  74   class MarkAndPushClosure: public ExtendedOopClosure {
  75    public:
  76     template <typename T> void do_oop_nv(T* p);
  77     virtual void do_oop(oop* p);
  78     virtual void do_oop(narrowOop* p);
  79   };
  80 
  81   class FollowStackClosure: public VoidClosure {
  82    public:
  83     virtual void do_void();
  84   };
  85 
  86   class AdjustPointerClosure: public OopsInGenClosure {
  87    public:
  88     template <typename T> void do_oop_nv(T* p);
  89     virtual void do_oop(oop* p);
  90     virtual void do_oop(narrowOop* p);
  91 
  92     // This closure provides its own oop verification code.
  93     debug_only(virtual bool should_verify_oops() { return false; })
  94   };
  95 
  96   // Used for java/lang/ref handling
  97   class IsAliveClosure: public BoolObjectClosure {
  98    public:
  99     virtual bool do_object_b(oop p);
 100   };
 101 
 102   class KeepAliveClosure: public OopClosure {
 103    protected:
 104     template <class T> void do_oop_work(T* p);
 105    public:
 106     virtual void do_oop(oop* p);
 107     virtual void do_oop(narrowOop* p);
 108   };
 109 
 110   //
 111   // Friend decls
 112   //
 113   friend class AdjustPointerClosure;
 114   friend class KeepAliveClosure;
 115   friend class VM_MarkSweep;
 116   friend class PMSRefProcTask;
 117   friend void marksweep_init();
 118 
 119  public:
 120   static void initialize_parallel_mark_sweep();
 121   //
 122   // Vars
 123   //
 124  protected:
 125   // Total invocations of a MarkSweep collection
 126   static uint _total_invocations;
 127 
 128   // Traversal stacks used during phase1
 129   static Stack<oop, mtGC>                      _marking_stack;
 130   static Stack<ObjArrayTask, mtGC>             _objarray_stack;
 131 
 132   // Space for storing/restoring mark word
 133   static Stack<markOop, mtGC>                  _preserved_mark_stack;
 134   static Stack<oop, mtGC>                      _preserved_oop_stack;
 135   static size_t                          _preserved_count;
 136   static size_t                          _preserved_count_max;
 137   static PreservedMark*                  _preserved_marks;
 138 
 139   // For parallel mark sweep (PMS)
 140   static PMSMarkBitMap*                  _pms_mark_bit_map;
 141   static PMSRegionArraySet*              _pms_region_array_set;
 142   static volatile intptr_t               _pms_mark_counter;
 143   static PMSRegionTaskQueueSet*          _pms_region_task_queues;
 144 
 145   // Reference processing (used in ...follow_contents)
 146   static ReferenceProcessor*             _ref_processor;
 147 
 148   static STWGCTimer*                     _gc_timer;
 149   static SerialOldTracer*                _gc_tracer;
 150 
 151   // Non public closures
 152   static KeepAliveClosure keep_alive;
 153 
 154  public:
 155   // Public closures
 156   static IsAliveClosure       is_alive;
 157   static FollowRootClosure    follow_root_closure;
 158   static MarkAndPushClosure   mark_and_push_closure;
 159   static FollowStackClosure   follow_stack_closure;
 160   static CLDToOopClosure      follow_cld_closure;
 161   static AdjustPointerClosure adjust_pointer_closure;
 162   static CLDToOopClosure      adjust_cld_closure;
 163 
 164   // Accessors
 165   static uint total_invocations() { return _total_invocations; }
 166 
 167   // Reference Processing
 168   static ReferenceProcessor* const ref_processor() { return _ref_processor; }
 169 
 170   // Archive Object handling
 171   static inline bool is_archive_object(oop object);
 172 
 173   static STWGCTimer* gc_timer() { return _gc_timer; }
 174   static SerialOldTracer* gc_tracer() { return _gc_tracer; }
 175 
 176   static PMSMarkBitMap*         pms_mark_bit_map()       { return _pms_mark_bit_map; }
 177   static PMSRegionArraySet*     pms_region_array_set()   { return _pms_region_array_set; }
 178   static PMSRegionTaskQueueSet* pms_region_task_queues() { return _pms_region_task_queues; }
 179 
 180 
 181   // Call backs for marking
 182   static void mark_object(oop obj);
 183   static bool par_mark_object(oop obj);
 184   static bool is_object_marked(oop obj);
 185   // Mark pointer and follow contents.  Empty marking stack afterwards.
 186   template <class T> static inline void follow_root(T* p);
 187 
 188   // Check mark and maybe push on marking stack
 189   template <class T> static void mark_and_push(T* p);
 190 
 191   static inline void push_objarray(oop obj, size_t index);
 192 
 193   static void follow_stack();   // Empty marking stack.
 194 
 195   static void follow_object(oop obj);
 196 
 197   static void follow_array(objArrayOop array, int index);
 198 
 199   static void follow_klass(Klass* klass);
 200 
 201   static void follow_class_loader(ClassLoaderData* cld);
 202 
 203   static int adjust_pointers(oop obj);
 204 
 205   static void preserve_mark(oop p, markOop mark);
 206                                 // Save the mark word so it can be restored later
 207   static void adjust_marks();   // Adjust the pointers in the preserved marks table
 208   static void restore_marks();  // Restore the marks that we saved in preserve_mark
 209 
 210   static void adjust_marks_helper(Stack<markOop, mtGC>* preserved_mark_stack,
 211                                   Stack<oop, mtGC>*     preserved_oop_stack,
 212                                   size_t          preserved_count,
 213                                   PreservedMark*  preserved_marks);
 214   static void restore_marks_helper(Stack<markOop, mtGC>* preserved_mark_stack,
 215                                    Stack<oop, mtGC>*     preserved_oop_stack,
 216                                    size_t          preserved_count,
 217                                    PreservedMark*  preserved_marks,
 218                                    bool            should_release);
 219 
 220   template <class T> static inline void adjust_pointer(T* p);
 221 };
 222 
 223 class PreservedMark VALUE_OBJ_CLASS_SPEC {
 224 private:
 225   oop _obj;
 226   markOop _mark;
 227 
 228 public:
 229   void init(oop obj, markOop mark) {
 230     _obj = obj;
 231     _mark = mark;
 232   }
 233 
 234   void adjust_pointer();
 235   void restore();
 236 };
 237 
 238 //
 239 // CMSParallelFullGC support code
 240 //
 241 typedef OverflowTaskQueue<oop, mtGC>                         ObjTaskQueue;
 242 typedef GenericTaskQueueSet<ObjTaskQueue, mtGC>              ObjTaskQueueSet;
 243 typedef OverflowTaskQueue<ObjArrayTask, mtGC>                ObjArrayTaskQueue;
 244 typedef GenericTaskQueueSet<ObjArrayTaskQueue, mtGC>         ObjArrayTaskQueueSet;
 245 
 246 // A region for PMS. A unit of parallelism. It's a fixed-size (1 MB by
 247 // default) region (except for the last part of a space) of the space
 248 // of the heap.
 249 class PMSRegion {
 250  public:
 251   class RegionDest : public CHeapObj<mtGC> {
 252     // CHeapObj because it's accessed by different threads (workers)
 253     // and does not have a scoped lifetime. Deallocated by
 254     // PMSRegion::cleanup().
 255    public:
 256     RegionDest() :
 257         _from_mr(MemRegion()), _to_space(NULL),
 258         _to_space_off(0), _to_space_size(0) {}
 259     RegionDest(MemRegion from_mr, CompactibleSpace* to_space,
 260                size_t to_space_off, size_t to_space_size) :
 261         _from_mr(from_mr), _to_space(to_space),
 262         _to_space_off(to_space_off), _to_space_size(to_space_size) {}
 263     MemRegion         _from_mr;              // the address range of the subregion
 264     CompactibleSpace* _to_space;             // the to-space
 265     size_t            _to_space_off;         // the word offset in the to-space
 266     size_t            _to_space_size;        // the word size in the to_space
 267     void log(outputStream* os) {
 268       os->print_cr("RegionDest(from:" PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT "),"
 269                    "to:" PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT "))",
 270                    p2i(_from_mr.start()), p2i(_from_mr.end()), _from_mr.byte_size(),
 271                    p2i(_to_space->bottom() + _to_space_off),
 272                    p2i(_to_space->bottom() + _to_space_off + _to_space_size),
 273                    _to_space_size * HeapWordSize);
 274     }
 275   };
 276   enum EvacState { NOT_EVAC, BEING_EVAC, HAS_BEEN_EVAC };
 277   // Evacuation state for parallel compaction
 278   jbyte _evac_state;
 279   // Used for synchronization in the parallel compact phase
 280   Monitor* _monitor;
 281 
 282  private:
 283   intptr_t  _index;
 284   MemRegion _mr;
 285   CompactibleSpace* _space;
 286 
 287   // The total word size of all the live objects in this region. This
 288   // includes all the live objects whose starting addresses are in the
 289   // region (but objects' tails can be outside of this region).
 290   intptr_t  _live_size;      // for YG where block_size == obj->size()
 291   intptr_t  _cfls_live_size; // for CFLS (OG and PG) where
 292                              // block_size = adjustObjectSize(obj->size())
 293 
 294   HeapWord* _beginning_of_live; // The beginning of the first live object in a region
 295   HeapWord* _end_of_live;       // The end (exclusive) end of the last live object in a region.
 296   HeapWord* _first_moved;       // The first live object that moves (for compaction) in a region.
 297 
 298   // Where the live objects in this region are evacuated.
 299   GrowableArray<RegionDest*>* _destinations;
 300 
 301   // The (other) regions that must be evacuated before this region can
 302   // be evacuated. In parallel compaction, a region cannot be
 303   // evacuated until the destination region is evacuated so that no
 304   // objects are overwritten before they are copied.
 305   GrowableArray<PMSRegion*>* _dependencies;
 306 
 307  public:
 308   PMSRegion() : _index(-1), _mr(MemRegion(NULL, (size_t)0)), _evac_state(HAS_BEEN_EVAC),
 309                 _monitor(NULL), _destinations(NULL), _dependencies(NULL) {}
 310   PMSRegion(intptr_t index, HeapWord* start, size_t size, CompactibleSpace* space) :
 311       _index(index), _mr(MemRegion(start, size)), _space(space),
 312       _live_size(0), _cfls_live_size(0), _destinations(new GrowableArray<RegionDest*>()),
 313       _dependencies(new GrowableArray<PMSRegion*>()),
 314       _beginning_of_live(start + size), _end_of_live(start), _first_moved(start + size),
 315       _evac_state(HAS_BEEN_EVAC) {
 316     _monitor = new Monitor(Mutex::barrier,               // rank
 317                            "MarkSweep Region monitor",   // name
 318                            Mutex::_allow_vm_block_flag); // allow_vm_block
 319   }
 320   // Because this object is resource-allocated, a destructor won't be
 321   // called. Use this function to reclaim resources.
 322   void cleanup() {
 323     if (_monitor != NULL) {
 324       delete _monitor;
 325     }
 326     if (_destinations != NULL) {
 327       size_t len = _destinations->length();
 328       for (size_t i = 0; i < len; i++) {
 329         delete _destinations->at(i);
 330       }
 331     }
 332   }
 333   intptr_t  index() { return _index; }
 334   HeapWord* start() { return _mr.start(); }
 335   HeapWord* end()   { return _mr.end(); }
 336   size_t    size()  { return _mr.word_size(); }
 337   CompactibleSpace* space() { return _space; }
 338   size_t    live_size() { return (size_t)_live_size; }
 339   size_t    cfls_live_size() { return (size_t)_cfls_live_size; }
 340   inline void      add_to_live_size(size_t word_size) {
 341     Atomic::add_ptr((intptr_t)word_size, &_live_size);
 342   }
 343   inline void      add_to_cfls_live_size(size_t word_size) {
 344     Atomic::add_ptr((intptr_t)word_size, &_cfls_live_size);
 345   }
 346   GrowableArray<RegionDest*>* destinations() { return _destinations; }
 347   void      add_destination(MemRegion from_mr, CompactibleSpace* to_space,
 348                             size_t to_space_off, size_t to_space_size) {
 349     RegionDest* d = new RegionDest(from_mr, to_space,
 350                                    to_space_off, to_space_size);
 351     _destinations->append(d);
 352   }
 353   RegionDest* find_destination(HeapWord* addr) {
 354     assert(_mr.start() <= addr && addr < _mr.end(), "Must be in the region");
 355     size_t len = _destinations->length();
 356     for (size_t i = 0; i < len; i++) {
 357       RegionDest* d = _destinations->at(i);
 358       if (d->_from_mr.contains(addr)) {
 359         return d;
 360       }
 361     }
 362     ShouldNotReachHere();
 363     return NULL;
 364   }
 365 
 366   void log_destinations(outputStream* os) {
 367     gclog_or_tty->print("Forwarding region " PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT "): ",
 368                         p2i(_mr.start()), p2i(_mr.end()), _mr.byte_size());
 369     for (int i = 0; i < _destinations->length(); i++) {
 370       RegionDest* d = _destinations->at(i);
 371       MemRegion dest_mr = MemRegion(d->_to_space->bottom() + d->_to_space_off,
 372                                     d->_to_space_size);
 373       gclog_or_tty->print("%d: " PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT ") -> "
 374                           PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT ") ",
 375                           i, p2i(d->_from_mr.start()), p2i(d->_from_mr.end()), d->_from_mr.byte_size(),
 376                           p2i(dest_mr.start()), p2i(dest_mr.end()), dest_mr.byte_size());
 377     }
 378     gclog_or_tty->cr();
 379   }
 380 
 381   GrowableArray<PMSRegion*>* dependencies() { return _dependencies; }
 382 
 383   void      record_stats(HeapWord* beginning_of_live,
 384                          HeapWord* end_of_live,
 385                          HeapWord* first_moved) {
 386     _beginning_of_live = beginning_of_live;
 387     _end_of_live = end_of_live;
 388     _first_moved = first_moved;
 389   }
 390   HeapWord* beginning_of_live() { return _beginning_of_live; }
 391   HeapWord* end_of_live() { return _end_of_live; }
 392   HeapWord* first_moved() { return _first_moved; }
 393   MemRegion live_range() {
 394     if (_beginning_of_live < _end_of_live) {
 395       return MemRegion(_beginning_of_live, _end_of_live);
 396     }
 397     return MemRegion();
 398   }
 399 };
 400 
 401 // An array of PMSRegions. There is one per space. The relevant spaces
 402 // under CMS are eden, two survivor spaces (they are the three
 403 // ContiguousSpace's in the young gen), the old gen (the entire
 404 // generation is one CompactibleFreeListSpace). Note that the
 405 // last PMSRegion of a space can be smaller than the standard fixed
 406 // size (1 MB by default) (as in a remainder.)
 407 class PMSRegionArray {
 408  private:
 409   CompactibleSpace* _space;
 410   MemRegion         _mr;
 411   PMSRegion*        _regions;
 412   size_t            _region_word_size;
 413   size_t            _n_regions;
 414 
 415   void reset_regions(MemRegion mr, size_t region_byte_size) {
 416     _mr = mr;
 417     _region_word_size = region_byte_size/HeapWordSize;
 418     assert(region_byte_size % HeapWordSize == 0, "Not word aligned?");
 419     size_t mr_size = mr.word_size();
 420     _n_regions = mr_size / _region_word_size;
 421     if (mr_size % _region_word_size != 0) {
 422       // The last region is of an odd size
 423       _n_regions++;
 424     }
 425     _regions = NEW_RESOURCE_ARRAY(PMSRegion, _n_regions);
 426     size_t index = 0;
 427     HeapWord* p = mr.start();
 428     for (; p < mr.end(); p += _region_word_size) {
 429       HeapWord* r_start = p;
 430       HeapWord* r_end = p + _region_word_size;
 431       if (mr.end() < r_end) {
 432         // The last region is of an odd size
 433         r_end = mr.end();
 434         assert(pointer_delta(r_end, r_start) < _region_word_size,
 435                "the remainder should be smaller than the standard region size");
 436       }
 437       _regions[index] = PMSRegion(index, r_start, r_end - r_start, _space);
 438       index++;
 439     }
 440     assert(index == _n_regions, "sanity check");
 441   }
 442 
 443  public:
 444   PMSRegionArray() : _space(NULL) {}
 445   PMSRegionArray(CompactibleSpace* space, size_t region_byte_size) : _space(space) {
 446     reset_regions(MemRegion(space->bottom(), space->end()), region_byte_size);
 447   }
 448   // Because this object is resource-allocated, a destructor won't be
 449   // called. Use this function to reclaim resources.
 450   void cleanup() {
 451     for (size_t i = 0; i < _n_regions; i++) {
 452       _regions[i].cleanup();
 453     }
 454   }
 455   inline bool contains(HeapWord* addr) {
 456     return _mr.start() <= addr && addr < _mr.end();
 457   }
 458   CompactibleSpace* space() { return _space; }
 459   // The first region
 460   PMSRegion* begin() { return &_regions[0]; }
 461   // The last region
 462   PMSRegion* end()   { return &_regions[_n_regions - 1]; }
 463   size_t region_word_size() { return _region_word_size; }
 464   size_t region_byte_size() { return _region_word_size * HeapWordSize; }
 465   size_t n_regions() { return _n_regions; }
 466   inline PMSRegion* region_for_index(size_t i) {
 467     // Use '<' below so we don't allow the sentinel end region here
 468     assert(i < _n_regions, "Out of bounds");
 469     return &_regions[i];
 470   }
 471   inline PMSRegion* region_for_addr(HeapWord* addr) {
 472     return region_for_index(addr_to_index(addr));
 473   }
 474   // Returns the index of the region that contains addr
 475   inline size_t addr_to_index(HeapWord* addr) {
 476     assert(_mr.start() <= addr && addr < _mr.end(), "Out of bounds");
 477     size_t index = pointer_delta(addr, _mr.start()) / _region_word_size;
 478     assert(index < _n_regions, "Index out of bounds");
 479     return index;
 480   }
 481   void record_space_live_range_for_compaction() {
 482     HeapWord* beginning_of_live = _space->end();
 483     HeapWord* end_of_live = _space->bottom();
 484     HeapWord* first_moved = _space->end();
 485     PMSRegion* first_r = begin();
 486     PMSRegion* last_r = end();
 487     for (PMSRegion* r = first_r; r <= last_r; r++) {
 488       if (r->beginning_of_live() < r->end()) {
 489         beginning_of_live = r->beginning_of_live();
 490         break;
 491       }
 492     }
 493     for (PMSRegion* r = last_r; r >= first_r; r--) {
 494       if (r->start() < r->end_of_live()) {
 495         end_of_live = r->end_of_live();
 496         break;
 497       }
 498     }
 499     for (PMSRegion* r = first_r; r <= last_r; r++) {
 500       if (r->first_moved() < r->end()) {
 501         first_moved = r->first_moved();
 502         break;
 503       }
 504     }
 505     if (LogCMSParallelFullGC) {
 506       gclog_or_tty->print_cr("beginning_of_live=" PTR_FORMAT,
 507                              p2i(beginning_of_live));
 508       gclog_or_tty->print_cr("end_of_live=" PTR_FORMAT,
 509                              p2i(end_of_live));
 510       gclog_or_tty->print_cr("first_moved=" PTR_FORMAT,
 511                              p2i(first_moved));
 512     }
 513     assert(beginning_of_live <= first_moved, "sanity check");
 514     _space->set_live_range_for_compaction(beginning_of_live,
 515                                           end_of_live,
 516                                           first_moved);
 517   }
 518   void compute_compact_dependencies();
 519   void mark_dense_prefix_as_evacuated() {
 520     if (_space->end_of_live() <= _space->first_moved()) {
 521       // No objects moved. Nothing to compact.
 522       return;
 523     }
 524     // Mark the 'dense prefix' regions, which have no objects that
 525     // will move in this compaction, evacuated. Note that the last
 526     // such region may be a destination of an object from a
 527     // region. If we don't mark them evacuated here, the compaction
 528     // routine (phase 4) may hang because no one will mark the last
 529     // such region evacuated.
 530     PMSRegion* first_r = region_for_addr(_space->first_moved());
 531     for (PMSRegion* r = begin(); r < first_r; r++) {
 532       r->_evac_state = PMSRegion::HAS_BEEN_EVAC;
 533     }
 534   }
 535 };
 536 
 537 // A set of PMSRegionArray's. There is one for the entire heap.
 538 class PMSRegionArraySet : public ResourceObj {
 539  private:
 540   class GetSpacesClosure : public SpaceClosure {
 541    private:
 542     GrowableArray<Space*>* _spaces;
 543    public:
 544     GetSpacesClosure() {
 545       _spaces = new GrowableArray<Space*>();
 546     }
 547     void do_space(Space* s) {
 548       _spaces->append(s);
 549     }
 550     GrowableArray<Space*>* spaces() { return _spaces; }
 551   };
 552   class SizeLiveObjectClosure : public BitMapClosure {
 553    private:
 554     PMSMarkBitMap* _mark_bit_map;
 555     Space*      _space;
 556     size_t      _live_size;
 557     size_t      _cfls_live_size;
 558    public:
 559     SizeLiveObjectClosure(PMSMarkBitMap* mark_bit_map, Space* space)
 560         : _mark_bit_map(mark_bit_map), _space(space),
 561           _live_size(0), _cfls_live_size(0) {
 562     }
 563     bool do_bit(size_t offset);
 564     size_t live_size() { return _live_size; }
 565     size_t cfls_live_size() { return _cfls_live_size; }
 566   };
 567 
 568   enum space_index {
 569     EDEN_SPACE = 0,
 570     S0_SPACE   = 1,
 571     S1_SPACE   = 2,
 572     CMS_SPACE  = 3,
 573     N_SPACES   = 4  // The number of spaces
 574   };
 575 
 576   // Spaces and their bottom addresses
 577   PMSRegionArray          _arrays[N_SPACES];
 578   CompactibleSpace*       _spaces[N_SPACES];
 579   HeapWord*               _space_bottoms[N_SPACES];
 580 
 581  public:
 582   PMSRegionArraySet() {
 583     GetSpacesClosure cl;
 584     GenCollectedHeap* gch = GenCollectedHeap::heap();
 585 #ifdef ASSERT
 586     MemRegion reserved = gch->reserved_region();
 587     MemRegion yg_reserved = gch->young_gen()->reserved();
 588     MemRegion og_reserved = gch->old_gen()->reserved();
 589     if (LogCMSParallelFullGC) {
 590       gclog_or_tty->print_cr("reserved: " PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT ")",
 591                              p2i(reserved.start()), p2i(reserved.end()), reserved.byte_size());
 592       gclog_or_tty->print_cr("yg_reserved: " PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT ")",
 593                              p2i(yg_reserved.start()), p2i(yg_reserved.end()), yg_reserved.byte_size());
 594       gclog_or_tty->print_cr("og_reserved: " PTR_FORMAT "-" PTR_FORMAT "(" SIZE_FORMAT ")",
 595                              p2i(og_reserved.start()), p2i(og_reserved.end()), og_reserved.byte_size());
 596     }
 597     assert(reserved.contains(yg_reserved), "Huh?");
 598     assert(reserved.contains(og_reserved), "Huh?");
 599     assert(reserved.start() == yg_reserved.start(), "Huh?");
 600     assert(yg_reserved.end() == og_reserved.start(), "Huh?");
 601     assert(og_reserved.end() == reserved.end(), "Huh?");
 602 #endif
 603     gch->young_gen()->space_iterate(&cl, true);
 604     gch->old_gen()->space_iterate(&cl, true);
 605     GrowableArray<Space*>* spaces = cl.spaces();
 606     // Five spaces (eden, s0, s1, OG, and PG.)
 607     assert(spaces->length() == N_SPACES, "wrong number of spaces");
 608     for (size_t i = 0; i < N_SPACES; i++) {
 609       Space* s = spaces->at(i);
 610       CompactibleSpace* cs = s->toCompactibleSpace();
 611       assert(cs != NULL, "Must be a CompactibleSpace");
 612       _spaces[i] = cs;
 613     }
 614     // The spaces come in the ascending address order of 0:eden, 1:s0,
 615     // 2:s1, 3:og. Note s0 and s1 can be in a reverse order. Fix it if so.
 616     if (_spaces[2]->bottom() < _spaces[1]->bottom()) {
 617       CompactibleSpace* tmp = _spaces[2];
 618       _spaces[2] = _spaces[1];
 619       _spaces[1] = tmp;
 620     }
 621 #ifdef ASSERT
 622     for (size_t i = 0; i < N_SPACES - 1; i++) {
 623       assert(_spaces[i]->bottom() < _spaces[i + 1]->bottom(),
 624              "The spaces must be in the ascending address order");
 625     }
 626 #endif
 627     for (size_t i = 0; i < N_SPACES; i++) {
 628       _arrays[i] = PMSRegionArray(_spaces[i], CMSParallelFullGCHeapRegionSize);
 629       _space_bottoms[i] = _spaces[i]->bottom();
 630     }
 631   }
 632 
 633   // Because this object is resource-allocated, a destructor won't be
 634   // called. Use this function to reclaim resources.
 635   void cleanup() {
 636     for (size_t i = 0; i < N_SPACES; i++) {
 637       _arrays[i].cleanup();
 638     }
 639   }
 640 
 641   CompactibleSpace* cms_space() { return _spaces[CMS_SPACE]; }
 642 
 643   inline PMSRegionArray* region_array_for(HeapWord* addr) {
 644     for (size_t i = 0; i < N_SPACES; i++) {
 645       PMSRegionArray* ra = &_arrays[i];
 646       if (ra->contains(addr)) {
 647         return ra;
 648       }
 649     }
 650     return NULL;
 651   }
 652 
 653   // A faster region array lookup. This is important for minimizing
 654   // marking overhead (MarkSweep::par_mark_object()).
 655   inline PMSRegionArray* fast_region_array_for(HeapWord* addr) {
 656     PMSRegionArray* res;
 657     if (_space_bottoms[CMS_SPACE] <= addr) {
 658       res = &_arrays[CMS_SPACE];
 659     } else {
 660       if (_space_bottoms[S0_SPACE] <= addr) {
 661         if (_space_bottoms[S1_SPACE] <= addr) {
 662           res = &_arrays[S1_SPACE];
 663         } else {
 664           res = &_arrays[S0_SPACE];
 665         }
 666       } else {
 667         res = &_arrays[EDEN_SPACE];
 668       }
 669     }
 670     assert(res->contains(addr), "The result region array must contain the address");
 671     return res;
 672   }
 673 
 674   PMSRegionArray* region_array_for(Space* space) {
 675     for (size_t i = 0; i < N_SPACES; i++) {
 676       PMSRegionArray* ra = &_arrays[i];
 677       if (ra->space() == space) {
 678         return ra;
 679       }
 680     }
 681     return NULL;
 682   }
 683 
 684   void verify_live_size();
 685 };
 686 
 687 // This is an AbstractGangTask used in Phase 1 (marking) of the
 688 // parallel mark sweep.
 689 class PMSMarkTask : public AbstractGangTask {
 690   WorkGang*              _workers;
 691   ObjTaskQueueSet*       _task_queues;
 692   ObjArrayTaskQueueSet*  _objarray_task_queues;
 693   ParallelTaskTerminator _terminator;
 694   ParallelTaskTerminator _objarray_terminator;
 695   StrongRootsScope*      _strong_roots_scope;
 696  public:
 697   PMSMarkTask(StrongRootsScope *srs, WorkGang* workers,
 698               ObjTaskQueueSet* task_queues,
 699               ObjArrayTaskQueueSet* objarray_task_queues) :
 700       AbstractGangTask("genMarkSweep parallel mark"),
 701       _strong_roots_scope(srs), _workers(workers),
 702       _task_queues(task_queues), _objarray_task_queues(objarray_task_queues),
 703       _terminator(ParallelTaskTerminator(srs->n_threads(), task_queues)),
 704       _objarray_terminator(ParallelTaskTerminator(srs->n_threads(), objarray_task_queues)) {}
 705   void work(uint worker_id);
 706   void do_steal_work(uint worker_id);
 707 };
 708 
 709 // This is an AbstractGangTask used in Phase 3 (adjust pointers) of
 710 // the parallel mark sweep.
 711 class PMSParAdjustTask : public AbstractGangTask {
 712  private:
 713   WorkGang*              _workers;
 714   int                    _n_workers;
 715   PMSRegionTaskQueueSet*    _task_queues;
 716   ParallelTaskTerminator _terminator;
 717   BitMapClosure*         _cl;
 718  public:
 719   PMSParAdjustTask(int n_workers, WorkGang* workers,
 720                    PMSRegionTaskQueueSet* task_queues,
 721                    BitMapClosure* cl) :
 722       AbstractGangTask("genMarkSweep parallel adjust"),
 723       _n_workers(n_workers), _workers(workers),
 724       _task_queues(task_queues), _cl(cl),
 725       _terminator(ParallelTaskTerminator(n_workers, task_queues)) {
 726     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");
 727   }
 728   void work(uint worker_id);
 729   void do_steal_work(uint worker_id);
 730 };
 731 
 732 // This is an AbstractGangTask used in Phase 3 (adjust pointers) of
 733 // the parallel mark sweep where it adjuts the pointers in the GC
 734 // roots.
 735 class PMSAdjustRootsTask : public AbstractGangTask {
 736   WorkGang*              _workers;
 737   StrongRootsScope*      _strong_roots_scope;
 738  public:
 739   PMSAdjustRootsTask(StrongRootsScope *srs, WorkGang* workers) :
 740       AbstractGangTask("genMarkSweep parallel adjust roots"),
 741       _strong_roots_scope(srs), _workers(workers) {}
 742   void work(uint worker_id);
 743 };
 744 
 745 // This is an AbstractGangTask used in Phase 3 (adjust pointers) of
 746 // the parallel mark sweep where it adjusts the pointers in the
 747 // 'preserved marks' (the mark header word for each object is
 748 // saved/restored before/after the parallel mark sweep.)
 749 class PMSParAdjustPreservedMarksTask : public AbstractGangTask {
 750   WorkGang*              _workers;
 751  public:
 752   PMSParAdjustPreservedMarksTask(WorkGang* workers) :
 753       AbstractGangTask("MarkSweep parallel adjust preserved marks"),
 754       _workers(workers) {
 755     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");
 756   }
 757   void work(uint worker_id);
 758 };
 759 
 760 // This is an AbstractGangTask used in Phase 4 (compaction/evacuation)
 761 // of the parallel mark sweep.
 762 class PMSParEvacTask : public AbstractGangTask {
 763  private:
 764   WorkGang*              _workers;
 765   int                    _n_workers;
 766   CompactibleSpace*      _space;
 767   BitMapClosure*         _cl;
 768  public:
 769   PMSParEvacTask(int n_workers, WorkGang* workers,
 770                  CompactibleSpace* space, BitMapClosure* cl) :
 771       AbstractGangTask("genMarkSweep parallel evac"),
 772       _n_workers(n_workers), _workers(workers), _space(space), _cl(cl) {
 773     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");
 774   }
 775   void work(uint worker_id);
 776 };
 777 
 778 // The mark bit map used for the parallel mark sweep.
 779 class PMSMarkBitMap : public CHeapObj<mtGC> {
 780  private:
 781   int       _shifter; // We allocate one bit per 2^_shifter in the bit map
 782   HeapWord* _start;   // The beginning address of the region covered by this mark bit map
 783   size_t    _size;    // The word size of the covered region == The number of bits
 784   BitMap    _bits;    // The underlying BitMap
 785  public:
 786   PMSMarkBitMap();
 787   PMSMarkBitMap(MemRegion underlying_memory);
 788 
 789   inline size_t addr_to_bit(HeapWord* addr) const {
 790     assert(addr >= _start, "addr too small");
 791     // Note: the addr == _start + _size case is valid for the
 792     // (exclusive) right index for the iterate() call.
 793     assert(addr <= _start + _size, "addr too large");
 794     assert((intptr_t)addr % MinObjAlignmentInBytes == 0,
 795           "Non-object-aligned address is suspicious");
 796     return pointer_delta(addr, _start) >> _shifter;
 797   }
 798 
 799   inline HeapWord* bit_to_addr(size_t bit) const {
 800     assert(bit < _bits.size(), "bit out of range");
 801     return _start + (bit << _shifter);
 802   }
 803 
 804   inline bool mark(oop obj) {
 805     size_t bit = addr_to_bit((HeapWord*)obj);
 806     return _bits.par_set_bit(bit);
 807   }
 808 
 809   inline bool is_marked(oop obj) const {
 810     size_t bit = addr_to_bit((HeapWord*)obj);
 811     return _bits.at(bit);
 812   }
 813 
 814   inline bool iterate(BitMapClosure* cl) { return _bits.iterate(cl); }
 815   inline bool iterate(BitMapClosure* cl, size_t left, size_t right) { return _bits.iterate(cl, left, right); }
 816   inline size_t count_one_bits() const { return _bits.count_one_bits(); }
 817   inline void clear() { return _bits.clear(); }
 818   inline bool isAllClear() const { return _bits.is_empty(); }
 819 };
 820 
 821 // The BitMapClosure used in Phase 3 (adjust pointers) of the parallel
 822 // mark sweep.
 823 class PMSAdjustClosure : public BitMapClosure {
 824  private:
 825   PMSMarkBitMap* _mark_bit_map;
 826  public:
 827   PMSAdjustClosure(PMSMarkBitMap* mark_bit_map) :
 828       _mark_bit_map(mark_bit_map) {
 829     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");
 830   }
 831   bool do_bit(size_t offset) {
 832     HeapWord* addr = _mark_bit_map->bit_to_addr(offset);
 833     oop obj = oop(addr);
 834     assert(_mark_bit_map->is_marked(obj), "sanity check");
 835     const intx interval = PrefetchScanIntervalInBytes;
 836     Prefetch::write(addr, interval);
 837     MarkSweep::adjust_pointers(obj);
 838     return true;
 839   }
 840 };
 841 
 842 // This BitMapClosure is used in Phase 2 (forwarding) of the parallel
 843 // mark sweep for finding a split point of a PMSRegion. A region may
 844 // need to be split into multiple subparts in terms of what space they
 845 // are evacuated into (copied to) when one destination space is
 846 // completely filled.
 847 class PMSFindRegionSplitPointClosure : public BitMapClosure {
 848  private:
 849   PMSMarkBitMap*    _mark_bit_map;
 850   HeapWord*         _compact_top;
 851   CompactibleSpace* _dst_space;
 852   HeapWord*         _dst_space_end;
 853   size_t            _dst_space_minimum_free_block_size;
 854   bool              _is_dst_cfls;
 855   HeapWord*         _split_point;
 856   size_t            _live_size_up_to_split_point;
 857   size_t            _cfls_live_size_up_to_split_point;
 858  public:
 859   PMSFindRegionSplitPointClosure(PMSMarkBitMap* mark_bit_map,
 860                                  HeapWord* compact_top,
 861                                  CompactibleSpace* dst_space)
 862       : _mark_bit_map(mark_bit_map), _dst_space(dst_space),
 863         _dst_space_end(dst_space->end()),
 864         _dst_space_minimum_free_block_size(
 865             dst_space->minimum_free_block_size()),
 866         _is_dst_cfls(dst_space->isCompactibleFreeListSpace()),
 867         _compact_top(compact_top), _split_point(NULL),
 868         _live_size_up_to_split_point(0),
 869         _cfls_live_size_up_to_split_point(0) {
 870   }
 871   bool do_bit(size_t offset) {
 872     HeapWord* addr = _mark_bit_map->bit_to_addr(offset);
 873     oop obj = oop(addr);
 874     size_t size = obj->size();
 875     size_t cfls_size = CompactibleFreeListSpace::adjustObjectSize(obj->size());
 876     size_t dst_size = _is_dst_cfls ? cfls_size : size;
 877     HeapWord* dst_space_end = _dst_space_end;
 878     if (_compact_top + dst_size > dst_space_end) {
 879       _split_point = addr;
 880       return false; /* exit out of iteration */
 881     }
 882     if (_is_dst_cfls &&
 883         _compact_top + dst_size +
 884           _dst_space_minimum_free_block_size > dst_space_end &&
 885         _compact_top + dst_size != _dst_space_end) {
 886       /* CFLS cannot leave a residual fragment smaller than */
 887       /* MinChunkSize.  So split right there. */
 888       _split_point = addr;
 889       return false;
 890     }
 891     _compact_top += dst_size;
 892     _live_size_up_to_split_point += size;
 893     _cfls_live_size_up_to_split_point += cfls_size;
 894     return true; /* continue iteration */
 895   }
 896   HeapWord* split_point() { return _split_point; }
 897   HeapWord* compact_top() { return _compact_top; }
 898   size_t live_size_up_to_split_point() {
 899     return _live_size_up_to_split_point;
 900   }
 901   size_t cfls_live_size_up_to_split_point() {
 902     return _cfls_live_size_up_to_split_point;
 903   }
 904 };
 905 
 906 #define pms_cfls_obj_size(q) CompactibleFreeListSpace::adjustObjectSize(oop(q)->size())
 907 
 908 // This macro defines specialized support code for parallel mark
 909 // sweep. It's defined as a macro to de-virtualize (specialize) the
 910 // object size routine (obj_size) for ContiguousSpace (space.cpp) and
 911 // CompactibleFreeListSpace (compactibleFreeListSpace.cpp),
 912 // respectively, like SCAN_AND_xxx in space.hpp.
 913 //
 914 // This macro contains three classes and two functions related to 'class_name'.
 915 //
 916 // The three classes are:
 917 //    PMSPerRegionForwardClosure_##class_name        (used in the forward phase)
 918 //    PMSForwardTask_##class_name                    (used in the forward phase)
 919 //    PMSCompactClosure_##class_name                 (used in the compact phase)
 920 //
 921 // The two functions are:
 922 //    class_name::pms_prepare_for_compaction_work()  (used in the forward phase)
 923 //    class_name::pms_compact_work()                 (used in the compact phase)
 924 //
 925 // where 'class_name' is either ContiguousSpace or CompactibleFreeListSpace.
 926 //
 927 #define DECLARE_PMS_SPECIALIZED_CODE(class_name, obj_size)                      \
 928 /* This is the BitMapClosure used for Phase 2 (forwarding) of PMS.     */       \
 929 /* This is used to forward (objects in) a region (PMSRegion) at a time */       \
 930 /* for parallelism.                                                    */       \
 931 class PMSPerRegionForwardClosure_##class_name : public BitMapClosure {          \
 932  private:                                                                       \
 933   PMSMarkBitMap*         _mark_bit_map;                                         \
 934   PMSRegion*             _region;                                               \
 935   PMSRegion::RegionDest* _dest;                                                 \
 936   CompactibleSpace*      _dest_space;                                           \
 937   bool                   _is_dest_cfls;                                         \
 938   HeapWord*              _compact_top;                                          \
 939   HeapWord*          _beginning_of_live; /* the first live object */            \
 940   HeapWord*          _end_of_live;       /* right after the last live object */ \
 941   HeapWord*          _first_moved;       /* the first moved (live) object */    \
 942                                          /* where the compaction phase */       \
 943                                          /* starts from */                      \
 944   bool               _beginning_of_live_set;                                    \
 945   bool               _first_moved_set;                                          \
 946   void update_dest(HeapWord* addr) {                                            \
 947     _dest = _region->find_destination(addr);                                    \
 948     assert(_dest->_from_mr.contains(addr), "sanity check");                     \
 949     _dest_space = _dest->_to_space;                                             \
 950     _is_dest_cfls = _dest_space->isCompactibleFreeListSpace();                  \
 951     _compact_top = _dest_space->bottom() + _dest->_to_space_off;                \
 952   }                                                                             \
 953  public:                                                                        \
 954   PMSPerRegionForwardClosure_##class_name(PMSMarkBitMap* mark_bit_map,          \
 955                                           PMSRegion* region) :                  \
 956       _mark_bit_map(mark_bit_map), _region(region),                             \
 957       _beginning_of_live(region->end()), _end_of_live(region->start()),         \
 958       _first_moved(region->end()), _beginning_of_live_set(false),               \
 959       _first_moved_set(false) {                                                 \
 960     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");                \
 961     update_dest(region->start());                                               \
 962   }                                                                             \
 963   HeapWord* compact_top()       { return _compact_top; }                        \
 964   HeapWord* beginning_of_live() { return _beginning_of_live; }                  \
 965   HeapWord* end_of_live()       { return _end_of_live; }                        \
 966   HeapWord* first_moved()       { return _first_moved; }                        \
 967   bool do_bit(size_t offset) {                                                  \
 968     HeapWord* addr = _mark_bit_map->bit_to_addr(offset);                        \
 969     assert(_region->start() <= addr && addr < _region->end(), "out of region"); \
 970     if (_dest->_from_mr.end() <= addr) {                                        \
 971       update_dest(addr);                                                        \
 972     }                                                                           \
 973     assert(_dest->_from_mr.contains(addr), "out of bounds");                    \
 974     if (!_beginning_of_live_set) {                                              \
 975       _beginning_of_live_set = true;                                            \
 976       _beginning_of_live = addr;                                                \
 977       /* Tighten the from_mr to the live portion only */                        \
 978       _dest->_from_mr = MemRegion(addr, _dest->_from_mr.end());                 \
 979     }                                                                           \
 980     oop obj = oop(addr);                                                        \
 981     assert(_mark_bit_map->is_marked(obj), "sanity check");                      \
 982     assert((intptr_t)addr % MinObjAlignmentInBytes == 0, "obj alignemnt check");\
 983     const intx interval = PrefetchScanIntervalInBytes;                          \
 984     Prefetch::write(addr, interval);                                            \
 985     size_t ssize = obj_size(addr);                                              \
 986     size_t dsize = _is_dest_cfls ? pms_cfls_obj_size(obj) : obj->size();        \
 987     if (addr != _compact_top) {                                                 \
 988       obj->forward_to(oop(_compact_top));                                       \
 989       assert(MarkSweep::is_object_marked(obj),                                  \
 990              "encoding the pointer should preserve the mark");                  \
 991     } else {                                                                    \
 992       obj->init_mark();                                                         \
 993       assert(obj->forwardee() == NULL, "should be forwarded to NULL");          \
 994     }                                                                           \
 995     /* Update the BOT. Make sure this is MT-safe */                             \
 996     _dest_space->cross_threshold(_compact_top, _compact_top + dsize);           \
 997     _compact_top += dsize;                                                      \
 998     _end_of_live = addr + ssize;                                                \
 999     /* Tighten the from_mr only to the live portion. Especially, */             \
1000     /* for the last object whose end sticks out of the end of the region */     \
1001     /* we need to update the end of from_mr. */                                 \
1002     if (_region->end() < _end_of_live) {                                        \
1003       _dest->_from_mr = MemRegion(_dest->_from_mr.start(), _end_of_live);       \
1004     }                                                                           \
1005     assert(_end_of_live <= _region->space()->end(), "Out of space bound");      \
1006     if (!_first_moved_set && obj->forwardee() != NULL) {                        \
1007       /* Non-moving object's forwarding pointer is set to NULL */               \
1008       _first_moved_set = true;                                                  \
1009       _first_moved = addr;                                                      \
1010     }                                                                           \
1011     return true;                                                                \
1012   }                                                                             \
1013   void record() {                                                               \
1014     _region->record_stats(_beginning_of_live, _end_of_live, _first_moved);      \
1015   }                                                                             \
1016 };                                                                              \
1017 /* This is an AbstractGangTask used for Phase 2 (forwarding) of PMS.   */       \
1018 /* This is used to forward (objects in) a region (PMSRegion) at a time */       \
1019 /* for parallelism.                                                    */       \
1020 class PMSForwardTask_##class_name : public AbstractGangTask {                   \
1021  private:                                                                       \
1022   typedef OverflowTaskQueue<PMSRegion*, mtGC>           PMSRegionTaskQueue;     \
1023   typedef GenericTaskQueueSet<PMSRegionTaskQueue, mtGC> PMSRegionTaskQueueSet;  \
1024   WorkGang*              _workers;                                              \
1025   int                    _n_workers;                                            \
1026   PMSRegionTaskQueueSet* _task_queues;                                          \
1027   ParallelTaskTerminator _terminator;                                           \
1028   PMSMarkBitMap*         _mark_bit_map;                                         \
1029  public:                                                                        \
1030   PMSForwardTask_##class_name(int n_workers, WorkGang* workers,                 \
1031                               PMSRegionTaskQueueSet* task_queues) :             \
1032       AbstractGangTask("genMarkSweep parallel forward"),                        \
1033       _n_workers(n_workers), _workers(workers),                                 \
1034       _task_queues(task_queues),                                                \
1035       _terminator(ParallelTaskTerminator(n_workers, task_queues)),              \
1036       _mark_bit_map(MarkSweep::pms_mark_bit_map()) {                            \
1037     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");                \
1038   }                                                                             \
1039   void work(uint worker_id) {                                                   \
1040     elapsedTimer timer;                                                         \
1041     ResourceMark rm;                                                            \
1042     HandleMark   hm;                                                            \
1043     if (LogCMSParallelFullGC) {                                                 \
1044       timer.start();                                                            \
1045       gclog_or_tty->print_cr("Parallel forward worker %d started...",           \
1046                              worker_id);                                        \
1047     }                                                                           \
1048     PMSRegionTaskQueue* task_queue = _task_queues->queue(worker_id);            \
1049     GenCollectedHeap* gch = GenCollectedHeap::heap();                           \
1050     elapsedTimer timer1;                                                        \
1051     if (LogCMSParallelFullGC) {                                                 \
1052       timer1.start();                                                           \
1053     }                                                                           \
1054     PMSRegion* r;                                                               \
1055     do {                                                                        \
1056       while (task_queue->pop_overflow(r)) {                                     \
1057         PMSPerRegionForwardClosure_##class_name cl(_mark_bit_map, r);           \
1058         _mark_bit_map->iterate(&cl,                                             \
1059                                _mark_bit_map->addr_to_bit(r->start()),          \
1060                                _mark_bit_map->addr_to_bit(r->end()));           \
1061         cl.record();                                                            \
1062       }                                                                         \
1063       while (task_queue->pop_local(r)) {                                        \
1064         PMSPerRegionForwardClosure_##class_name cl(_mark_bit_map, r);           \
1065         _mark_bit_map->iterate(&cl,                                             \
1066                                _mark_bit_map->addr_to_bit(r->start()),          \
1067                                _mark_bit_map->addr_to_bit(r->end()));           \
1068         cl.record();                                                            \
1069       }                                                                         \
1070     } while (!task_queue->is_empty());                                          \
1071     if (LogCMSParallelFullGC) {                                                 \
1072       timer1.stop();                                                            \
1073       gclog_or_tty->print_cr("Parallel forward worker %d finished scanning "    \
1074                              "(%3.5f sec)",                                     \
1075                              worker_id, timer1.seconds());                      \
1076     }                                                                           \
1077     do_steal_work(worker_id);                                                   \
1078     if (LogCMSParallelFullGC) {                                                 \
1079       timer.stop();                                                             \
1080       gclog_or_tty->print_cr("Parallel forward worker %d finished (%3.5f sec)", \
1081                              worker_id, timer.seconds());                       \
1082     }                                                                           \
1083   }                                                                             \
1084                                                                                 \
1085   void do_steal_work(uint worker_id) {                                          \
1086     elapsedTimer timer;                                                         \
1087     if (LogCMSParallelFullGC) {                                                 \
1088       timer.start();                                                            \
1089     }                                                                           \
1090     int seed = 17;                                                              \
1091     int num_steals = 0;                                                         \
1092     PMSRegionTaskQueue* task_queue = _task_queues->queue(worker_id);            \
1093     assert(task_queue == _task_queues->queue(worker_id), "Sanity check");       \
1094     PMSRegion* r;                                                               \
1095     do {                                                                        \
1096       assert(task_queue->is_empty(),                                            \
1097              "Task queue should be empty before work stealing");                \
1098       while (_task_queues->steal(worker_id, &seed, r)) {                        \
1099         num_steals++;                                                           \
1100         PMSPerRegionForwardClosure_##class_name cl(_mark_bit_map, r);           \
1101         _mark_bit_map->iterate(&cl,                                             \
1102                                _mark_bit_map->addr_to_bit(r->start()),          \
1103                                _mark_bit_map->addr_to_bit(r->end()));           \
1104         cl.record();                                                            \
1105       }                                                                         \
1106     } while (!_terminator.offer_termination());                                 \
1107     assert(task_queue->is_empty(), "Check my task queue is empty again");       \
1108     if (LogCMSParallelFullGC) {                                                 \
1109       timer.stop();                                                             \
1110       gclog_or_tty->print_cr(                                                   \
1111         "Parallel forward worker %d finished work-stealing "                    \
1112         "(%d steals, %3.5f sec)",                                               \
1113         worker_id, num_steals, timer.seconds());                                \
1114     }                                                                           \
1115   }                                                                             \
1116 };                                                                              \
1117                                                                                 \
1118 /* This is the BitMapClosure used for Phase 4 (compaction/evacuation) of PMS.*/ \
1119 /* This is used to copy objects.                                             */ \
1120 class PMSCompactClosure_##class_name : public BitMapClosure {                   \
1121  private:                                                                       \
1122   PMSMarkBitMap* _mark_bit_map;                                                 \
1123  public:                                                                        \
1124   PMSCompactClosure_##class_name(PMSMarkBitMap* mark_bit_map) :                 \
1125       _mark_bit_map(mark_bit_map) {                                             \
1126     assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");                \
1127   }                                                                             \
1128   bool do_bit(size_t offset) {                                                  \
1129     HeapWord* addr = _mark_bit_map->bit_to_addr(offset);                        \
1130     oop obj = oop(addr);                                                        \
1131     assert(_mark_bit_map->is_marked(obj), "sanity check");                      \
1132     const intx scan_interval = PrefetchScanIntervalInBytes;                     \
1133     const intx copy_interval = PrefetchCopyIntervalInBytes;                     \
1134     Prefetch::read(addr, scan_interval);                                        \
1135     size_t size = obj_size(addr);                                               \
1136     HeapWord* compaction_top = (HeapWord*)obj->forwardee();                     \
1137     assert(compaction_top != NULL, "Non-moving object should not be seen here");\
1138     Prefetch::write(compaction_top, copy_interval);                             \
1139     assert(addr != compaction_top, "everything in this pass should be moving"); \
1140     Copy::aligned_conjoint_words(addr, compaction_top, size);                   \
1141     oop(compaction_top)->init_mark();                                           \
1142     assert(oop(compaction_top)->klass() != NULL, "should have a class");        \
1143     return true;                                                                \
1144   }                                                                             \
1145 };                                                                              \
1146                                                                                 \
1147 /* Parallel version of prepare_for_compaction() used for Phase 2 (forwarding)*/ \
1148 /* of PMS.                                                                   */ \
1149 void class_name::pms_prepare_for_compaction_work(CompactPoint* cp) {            \
1150   assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");                  \
1151   HeapWord* compact_top;                                                        \
1152   set_compaction_top(bottom());                                                 \
1153                                                                                 \
1154   if (cp->space == NULL) {                                                      \
1155     assert(cp->gen != NULL, "need a generation");                               \
1156     assert(cp->threshold == NULL, "just checking");                             \
1157     assert(cp->gen->first_compaction_space() == this, "just checking");         \
1158     cp->space = cp->gen->first_compaction_space();                              \
1159     compact_top = cp->space->bottom();                                          \
1160     cp->space->set_compaction_top(compact_top);                                 \
1161     cp->threshold = cp->space->initialize_threshold();                          \
1162   } else {                                                                      \
1163     compact_top = cp->space->compaction_top();                                  \
1164   }                                                                             \
1165                                                                                 \
1166   PMSMarkBitMap* mark_bit_map = MarkSweep::pms_mark_bit_map();                  \
1167   GenCollectedHeap* gch = GenCollectedHeap::heap();                             \
1168   PMSRegionTaskQueueSet* task_queues = MarkSweep::pms_region_task_queues();     \
1169   WorkGang* workers = gch->workers();                                           \
1170   int n_workers = workers->total_workers();                                     \
1171   PMSRegionArraySet* region_array_set = MarkSweep::pms_region_array_set();      \
1172   PMSRegionArray* regions = region_array_set->region_array_for(this);           \
1173   assert(regions != NULL, "Must be non-null");                                  \
1174                                                                                 \
1175   PMSRegion* first_r = regions->begin();                                        \
1176   PMSRegion* last_r = regions->end(); /* Inclusive */                           \
1177   int i = 0;                                                                    \
1178                                                                                 \
1179   for (PMSRegion* r = first_r; r <= last_r; r++) {                              \
1180     size_t live_size = r->live_size();                                          \
1181     size_t cfls_live_size = r->cfls_live_size();                                \
1182     if (live_size == 0) {                                                       \
1183       r->_evac_state = PMSRegion::HAS_BEEN_EVAC;                                \
1184       assert(cfls_live_size == 0, "cfls_live_size must be zero, too");          \
1185       continue;                                                                 \
1186     }                                                                           \
1187     r->_evac_state = PMSRegion::NOT_EVAC;                                       \
1188     bool is_cfls = cp->space->isCompactibleFreeListSpace();                     \
1189     size_t size = is_cfls ? cfls_live_size : live_size;                         \
1190     size_t compaction_max_size = pointer_delta(cp->space->end(), compact_top);  \
1191     HeapWord* split_point = r->start();                                         \
1192     /* If the current compaction space is not large enough or the */            \
1193     /* remaining fragment is smaller than MinChunkSize (which is not */         \
1194     /* allowed for the CMS space), we need to use the next */                   \
1195     /* compaction space and split the region. */                                \
1196     while (size > compaction_max_size ||                                        \
1197            (size + cp->space->minimum_free_block_size() > compaction_max_size &&\
1198             size != compaction_max_size)) {                                     \
1199       /* First split the region */                                              \
1200       HeapWord* prev_compact_top = compact_top;                                 \
1201       HeapWord* prev_split_point = split_point;                                 \
1202       PMSFindRegionSplitPointClosure cl(mark_bit_map, compact_top, cp->space);  \
1203       mark_bit_map->iterate(&cl,                                                \
1204                             mark_bit_map->addr_to_bit(split_point),             \
1205                             mark_bit_map->addr_to_bit(r->end()));               \
1206       split_point = cl.split_point();                                           \
1207       assert(split_point != NULL, "Region must be split");                      \
1208       compact_top = cl.compact_top();                                           \
1209       size_t live_size_up_to_split_point = cl.live_size_up_to_split_point();    \
1210       size_t cfls_live_size_up_to_split_point =                                 \
1211         cl.cfls_live_size_up_to_split_point();                                  \
1212       if (prev_split_point != split_point) {                                    \
1213         /* This is for the first split piece of the region */                   \
1214         r->add_destination(MemRegion(prev_split_point, split_point),            \
1215                            cp->space, prev_compact_top - cp->space->bottom(),   \
1216                            is_cfls ? cfls_live_size_up_to_split_point :         \
1217                                      live_size_up_to_split_point);              \
1218       } else {                                                                  \
1219         assert(compact_top == prev_compact_top,                                 \
1220                "the space didn't accommodate even one object");                 \
1221       }                                                                         \
1222       /* switch to next compaction space */                                     \
1223       cp->space->set_compaction_top(compact_top);                               \
1224       cp->space = cp->space->next_compaction_space();                           \
1225       if (cp->space == NULL) {                                                  \
1226         assert(gch->is_old_gen(cp->gen), "compaction must succeed");            \
1227         cp->gen = gch->young_gen();                                             \
1228         cp->space = cp->gen->first_compaction_space();                          \
1229         assert(cp->space != NULL,                                               \
1230                "generation must have a first compaction space");                \
1231       }                                                                         \
1232       is_cfls = cp->space->isCompactibleFreeListSpace();                        \
1233       compact_top = cp->space->bottom();                                        \
1234       cp->space->set_compaction_top(compact_top);                               \
1235       cp->threshold = cp->space->initialize_threshold();                        \
1236       compaction_max_size = pointer_delta(cp->space->end(), compact_top);       \
1237       live_size -= live_size_up_to_split_point;                                 \
1238       cfls_live_size -= cfls_live_size_up_to_split_point;                       \
1239       size = is_cfls ? cfls_live_size : live_size;                              \
1240     }                                                                           \
1241     assert(size <= compaction_max_size,                                         \
1242            "The whole region (if no split) "                                    \
1243            "or the last split piece must fit the current compact space");       \
1244     /* This is for the whole region (if no split) or the last split piece   */  \
1245     /* of the region. Note the from_mr will be 'tightened' later in         */  \
1246     /* PMSPerRegionForwardClosure_### so that it will be the                */  \
1247     /* smallest memory range that contains only the live portion of the     */  \
1248     /* region. Note that the last object's tail can stick out of the region.*/  \
1249     r->add_destination(MemRegion(split_point, r->end()),                        \
1250                        cp->space, compact_top - cp->space->bottom(), size);     \
1251     compact_top += size;                                                        \
1252     assert(compact_top <= cp->space->end(), "Must fit");                        \
1253     assert((intptr_t)compact_top % MinObjAlignmentInBytes == 0,                 \
1254            "obj alignemnt check");                                              \
1255     task_queues->queue(i)->push(r);                                             \
1256     i = (i + 1) % n_workers;                                                    \
1257     if (LogCMSParallelFullGC) {                                                 \
1258       r->log_destinations(gclog_or_tty);                                        \
1259     }                                                                           \
1260   }                                                                             \
1261   /* save the compaction_top of the compaction space. */                        \
1262   cp->space->set_compaction_top(compact_top);                                   \
1263   PMSForwardTask_##class_name tsk(n_workers, workers, task_queues);             \
1264   GCTraceTime tm1("par-forward",                                                \
1265                   (PrintGC && Verbose) || LogCMSParallelFullGC,                 \
1266                   true, NULL, GCId::peek());                                    \
1267   if (n_workers > 1) {                                                          \
1268     workers->run_task(&tsk);                                                    \
1269   } else {                                                                      \
1270     tsk.work(0);                                                                \
1271   }                                                                             \
1272   /* Save the global info from the regions. Note _first_dead is unused. */      \
1273   assert(regions->space() == this, "sanity check");                             \
1274   /* TODO: get rid of the parameter below */                                    \
1275   regions->record_space_live_range_for_compaction();                            \
1276   regions->compute_compact_dependencies();                                      \
1277   regions->mark_dense_prefix_as_evacuated();                                    \
1278 }                                                                               \
1279                                                                                 \
1280 /* Parallel version of compact() used for Phase 4 (compaction/evacuation) */    \
1281 /* of PMS.                                                                */    \
1282 void class_name::pms_compact_work() {                                           \
1283   assert(CMSParallelFullGC, "Used only if CMSParallelFullGC");                  \
1284   if (_first_moved < _end_of_live) { /* Unless there is no moving live object*/ \
1285     PMSMarkBitMap* mark_bit_map = MarkSweep::pms_mark_bit_map();                \
1286     PMSCompactClosure_##class_name compact_cl(mark_bit_map);                    \
1287     GenCollectedHeap* gch = GenCollectedHeap::heap();                           \
1288     WorkGang* workers = gch->workers();                                         \
1289     int n_workers = workers->total_workers();                                   \
1290     PMSParEvacTask tsk(n_workers, workers, this, &compact_cl);                  \
1291     GCTraceTime tm1("par-compact",                                              \
1292                     (PrintGC && Verbose) || LogCMSParallelFullGC,               \
1293                     true, NULL, GCId::peek());                                  \
1294     if (n_workers > 1) {                                                        \
1295       workers->run_task(&tsk);                                                  \
1296     } else {                                                                    \
1297       tsk.work(0);                                                              \
1298     }                                                                           \
1299   }                                                                             \
1300   /* Let's remember if we were empty before we did the compaction. */           \
1301   bool was_empty = used_region().is_empty();                                    \
1302   /* Reset space after compaction is complete */                                \
1303   reset_after_compaction();                                                     \
1304   /* We do this clear, below, since it has overloaded meanings for some */      \
1305   /* space subtypes.  For example, OffsetTableContigSpace's that were   */      \
1306   /* compacted into will have had their offset table thresholds updated */      \
1307   /* continuously, but those that weren't need to have their thresholds */      \
1308   /* re-initialized.  Also mangles unused area for debugging.           */      \
1309   if (used_region().is_empty()) {                                               \
1310     if (!was_empty) clear(SpaceDecorator::Mangle);                              \
1311   } else {                                                                      \
1312     if (ZapUnusedHeapArea) mangle_unused_area();                                \
1313   }                                                                             \
1314 }
1315 
1316 class PMSRefProcTaskExecutor : public AbstractRefProcTaskExecutor {
1317  private:
1318   ObjTaskQueueSet*      _task_queues;
1319   ObjArrayTaskQueueSet* _objarray_task_queues;
1320  public:
1321   PMSRefProcTaskExecutor(ObjTaskQueueSet* task_queues,
1322                          ObjArrayTaskQueueSet* objarray_task_queues)
1323       : _task_queues(task_queues), _objarray_task_queues(objarray_task_queues) {}
1324 
1325   // Executes a task using worker threads.
1326   virtual void execute(ProcessTask& task);
1327   virtual void execute(EnqueueTask& task);
1328 };
1329 
1330 #endif // SHARE_VM_GC_SERIAL_MARKSWEEP_HPP