1 /*
   2  * Copyright (c) 2001, 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 #include "precompiled.hpp"
  26 #include "classfile/systemDictionary.hpp"
  27 #include "gc/parallel/objectStartArray.hpp"
  28 #include "gc/parallel/parallelScavengeHeap.hpp"
  29 #include "gc/parallel/parMarkBitMap.inline.hpp"
  30 #include "gc/parallel/psMarkSweep.hpp"
  31 #include "gc/parallel/psMarkSweepDecorator.hpp"
  32 #include "gc/parallel/psParallelCompact.inline.hpp"
  33 #include "gc/serial/markSweep.inline.hpp"
  34 #include "gc/shared/spaceDecorator.hpp"
  35 #include "oops/oop.inline.hpp"
  36 #include "runtime/prefetch.inline.hpp"
  37 
  38 PSMarkSweepDecorator* PSMarkSweepDecorator::_destination_decorator = NULL;
  39 
  40 
  41 void PSMarkSweepDecorator::set_destination_decorator_tenured() {
  42   ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
  43   _destination_decorator = heap->old_gen()->object_mark_sweep();
  44 }
  45 
  46 void PSMarkSweepDecorator::advance_destination_decorator() {
  47   ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
  48 
  49   assert(_destination_decorator != NULL, "Sanity");
  50 
  51   PSMarkSweepDecorator* first = heap->old_gen()->object_mark_sweep();
  52   PSMarkSweepDecorator* second = heap->young_gen()->eden_mark_sweep();
  53   PSMarkSweepDecorator* third = heap->young_gen()->from_mark_sweep();
  54   PSMarkSweepDecorator* fourth = heap->young_gen()->to_mark_sweep();
  55 
  56   if ( _destination_decorator == first ) {
  57     _destination_decorator = second;
  58   } else if ( _destination_decorator == second ) {
  59     _destination_decorator = third;
  60   } else if ( _destination_decorator == third ) {
  61     _destination_decorator = fourth;
  62   } else {
  63     fatal("PSMarkSweep attempting to advance past last compaction area");
  64   }
  65 }
  66 
  67 PSMarkSweepDecorator* PSMarkSweepDecorator::destination_decorator() {
  68   assert(_destination_decorator != NULL, "Sanity");
  69 
  70   return _destination_decorator;
  71 }
  72 
  73 // FIX ME FIX ME FIX ME FIX ME!!!!!!!!!
  74 // The object forwarding code is duplicated. Factor this out!!!!!
  75 //
  76 // This method "precompacts" objects inside its space to dest. It places forwarding
  77 // pointers into markOops for use by adjust_pointers. If "dest" should overflow, we
  78 // finish by compacting into our own space.
  79 
  80 void PSMarkSweepDecorator::precompact() {
  81   // Reset our own compact top.
  82   set_compaction_top(space()->bottom());
  83 
  84   /* We allow some amount of garbage towards the bottom of the space, so
  85    * we don't start compacting before there is a significant gain to be made.
  86    * Occasionally, we want to ensure a full compaction, which is determined
  87    * by the MarkSweepAlwaysCompactCount parameter. This is a significant
  88    * performance improvement!
  89    */
  90   bool skip_dead = ((PSMarkSweep::total_invocations() % MarkSweepAlwaysCompactCount) != 0);
  91 
  92   size_t allowed_deadspace = 0;
  93   if (skip_dead) {
  94     const size_t ratio = allowed_dead_ratio();
  95     allowed_deadspace = space()->capacity_in_words() * ratio / 100;
  96   }
  97 
  98   // Fetch the current destination decorator
  99   PSMarkSweepDecorator* dest = destination_decorator();
 100   ObjectStartArray* start_array = dest->start_array();
 101 
 102   HeapWord* compact_top = dest->compaction_top();
 103   HeapWord* compact_end = dest->space()->end();
 104 
 105   HeapWord* q = space()->bottom();
 106   HeapWord* t = space()->top();
 107 
 108   HeapWord*  end_of_live= q;    /* One byte beyond the last byte of the last
 109                                    live object. */
 110   HeapWord*  first_dead = space()->end(); /* The first dead object. */
 111 
 112   const intx interval = PrefetchScanIntervalInBytes;
 113 
 114   while (q < t) {
 115     assert(oop(q)->mark()->is_marked() || oop(q)->mark()->is_unlocked() ||
 116            oop(q)->mark()->has_bias_pattern(),
 117            "these are the only valid states during a mark sweep");
 118     if (oop(q)->is_gc_marked()) {
 119       /* prefetch beyond q */
 120       Prefetch::write(q, interval);
 121       size_t size = oop(q)->size();
 122 
 123       size_t compaction_max_size = pointer_delta(compact_end, compact_top);
 124 
 125       // This should only happen if a space in the young gen overflows the
 126       // old gen. If that should happen, we null out the start_array, because
 127       // the young spaces are not covered by one.
 128       while(size > compaction_max_size) {
 129         // First record the last compact_top
 130         dest->set_compaction_top(compact_top);
 131 
 132         // Advance to the next compaction decorator
 133         advance_destination_decorator();
 134         dest = destination_decorator();
 135 
 136         // Update compaction info
 137         start_array = dest->start_array();
 138         compact_top = dest->compaction_top();
 139         compact_end = dest->space()->end();
 140         assert(compact_top == dest->space()->bottom(), "Advanced to space already in use");
 141         assert(compact_end > compact_top, "Must always be space remaining");
 142         compaction_max_size =
 143           pointer_delta(compact_end, compact_top);
 144       }
 145 
 146       // store the forwarding pointer into the mark word
 147       if (q != compact_top) {
 148         oop(q)->forward_to(oop(compact_top));
 149         assert(oop(q)->is_gc_marked(), "encoding the pointer should preserve the mark");
 150       } else {
 151         // if the object isn't moving we can just set the mark to the default
 152         // mark and handle it specially later on.
 153         oop(q)->init_mark();
 154         assert(oop(q)->forwardee() == NULL, "should be forwarded to NULL");
 155       }
 156 
 157       // Update object start array
 158       if (start_array) {
 159         start_array->allocate_block(compact_top);
 160       }
 161 
 162       compact_top += size;
 163       assert(compact_top <= dest->space()->end(),
 164         "Exceeding space in destination");
 165 
 166       q += size;
 167       end_of_live = q;
 168     } else {
 169       /* run over all the contiguous dead objects */
 170       HeapWord* end = q;
 171       do {
 172         /* prefetch beyond end */
 173         Prefetch::write(end, interval);
 174         end += oop(end)->size();
 175       } while (end < t && (!oop(end)->is_gc_marked()));
 176 
 177       /* see if we might want to pretend this object is alive so that
 178        * we don't have to compact quite as often.
 179        */
 180       if (allowed_deadspace > 0 && q == compact_top) {
 181         size_t sz = pointer_delta(end, q);
 182         if (insert_deadspace(allowed_deadspace, q, sz)) {
 183           size_t compaction_max_size = pointer_delta(compact_end, compact_top);
 184 
 185           // This should only happen if a space in the young gen overflows the
 186           // old gen. If that should happen, we null out the start_array, because
 187           // the young spaces are not covered by one.
 188           while (sz > compaction_max_size) {
 189             // First record the last compact_top
 190             dest->set_compaction_top(compact_top);
 191 
 192             // Advance to the next compaction decorator
 193             advance_destination_decorator();
 194             dest = destination_decorator();
 195 
 196             // Update compaction info
 197             start_array = dest->start_array();
 198             compact_top = dest->compaction_top();
 199             compact_end = dest->space()->end();
 200             assert(compact_top == dest->space()->bottom(), "Advanced to space already in use");
 201             assert(compact_end > compact_top, "Must always be space remaining");
 202             compaction_max_size =
 203               pointer_delta(compact_end, compact_top);
 204           }
 205 
 206           // store the forwarding pointer into the mark word
 207           if (q != compact_top) {
 208             oop(q)->forward_to(oop(compact_top));
 209             assert(oop(q)->is_gc_marked(), "encoding the pointer should preserve the mark");
 210           } else {
 211             // if the object isn't moving we can just set the mark to the default
 212             // mark and handle it specially later on.
 213             oop(q)->init_mark();
 214             assert(oop(q)->forwardee() == NULL, "should be forwarded to NULL");
 215           }
 216 
 217           // Update object start array
 218           if (start_array) {
 219             start_array->allocate_block(compact_top);
 220           }
 221 
 222           compact_top += sz;
 223           assert(compact_top <= dest->space()->end(),
 224             "Exceeding space in destination");
 225 
 226           q = end;
 227           end_of_live = end;
 228           continue;
 229         }
 230       }
 231 
 232       // q is a pointer to a dead object. Use this dead memory to store a pointer to the next live object.
 233       (*(HeapWord**)q) = end;
 234 
 235       /* see if this is the first dead region. */
 236       if (q < first_dead) {
 237         first_dead = q;
 238       }
 239 
 240       /* move on to the next object */
 241       q = end;
 242     }
 243   }
 244 
 245   assert(q == t, "just checking");
 246   _end_of_live = end_of_live;
 247   if (end_of_live < first_dead) {
 248     first_dead = end_of_live;
 249   }
 250   _first_dead = first_dead;
 251 
 252   // Update compaction top
 253   dest->set_compaction_top(compact_top);
 254 }
 255 
 256 bool PSMarkSweepDecorator::insert_deadspace(size_t& allowed_deadspace_words,
 257                                             HeapWord* q, size_t deadlength) {
 258   if (allowed_deadspace_words >= deadlength) {
 259     allowed_deadspace_words -= deadlength;
 260     CollectedHeap::fill_with_object(q, deadlength);
 261     oop(q)->set_mark(oop(q)->mark()->set_marked());
 262     assert((int) deadlength == oop(q)->size(), "bad filler object size");
 263     // Recall that we required "q == compaction_top".
 264     return true;
 265   } else {
 266     allowed_deadspace_words = 0;
 267     return false;
 268   }
 269 }
 270 
 271 void PSMarkSweepDecorator::adjust_pointers() {
 272   // adjust all the interior pointers to point at the new locations of objects
 273   // Used by MarkSweep::mark_sweep_phase3()
 274 
 275   HeapWord* q = space()->bottom();
 276   HeapWord* t = _end_of_live;  // Established by "prepare_for_compaction".
 277 
 278   assert(_first_dead <= _end_of_live, "Stands to reason, no?");
 279 
 280   if (q < t && _first_dead > q &&
 281       !oop(q)->is_gc_marked()) {
 282     // we have a chunk of the space which hasn't moved and we've
 283     // reinitialized the mark word during the previous pass, so we can't
 284     // use is_gc_marked for the traversal.
 285     HeapWord* end = _first_dead;
 286 
 287     while (q < end) {
 288       // point all the oops to the new location
 289       size_t size = MarkSweep::adjust_pointers(oop(q));
 290       q += size;
 291     }
 292 
 293     if (_first_dead == t) {
 294       q = t;
 295     } else {
 296       // The first dead object should contain a pointer to the first live object
 297       q = *(HeapWord**)_first_dead;
 298     }
 299   }
 300   const intx interval = PrefetchScanIntervalInBytes;
 301 
 302   debug_only(HeapWord* prev_q = NULL);
 303   while (q < t) {
 304     // prefetch beyond q
 305     Prefetch::write(q, interval);
 306     if (oop(q)->is_gc_marked()) {
 307       // q is alive
 308       // point all the oops to the new location
 309       size_t size = MarkSweep::adjust_pointers(oop(q));
 310       debug_only(prev_q = q);
 311       q += size;
 312     } else {
 313       debug_only(prev_q = q);
 314       // The first dead object is no longer an object. At that memory address,
 315       // there is a pointer to the first live object that the previous phase found.
 316       q = *(HeapWord**)q;
 317       assert(q > prev_q, "we should be moving forward through memory, q: " PTR_FORMAT ", prev_q: " PTR_FORMAT, p2i(q), p2i(prev_q));
 318     }
 319   }
 320 
 321   assert(q == t, "just checking");
 322 }
 323 
 324 void PSMarkSweepDecorator::compact(bool mangle_free_space ) {
 325   // Copy all live objects to their new location
 326   // Used by MarkSweep::mark_sweep_phase4()
 327 
 328   HeapWord*       q = space()->bottom();
 329   HeapWord* const t = _end_of_live;
 330   debug_only(HeapWord* prev_q = NULL);
 331 
 332   if (q < t && _first_dead > q &&
 333       !oop(q)->is_gc_marked()) {
 334 #ifdef ASSERT
 335     // we have a chunk of the space which hasn't moved and we've reinitialized the
 336     // mark word during the previous pass, so we can't use is_gc_marked for the
 337     // traversal.
 338     HeapWord* const end = _first_dead;
 339 
 340     while (q < end) {
 341       size_t size = oop(q)->size();
 342       assert(!oop(q)->is_gc_marked(), "should be unmarked (special dense prefix handling)");
 343       debug_only(prev_q = q);
 344       q += size;
 345     }
 346 #endif
 347 
 348     if (_first_dead == t) {
 349       q = t;
 350     } else {
 351       // $$$ Funky
 352       q = (HeapWord*) oop(_first_dead)->mark()->decode_pointer();
 353     }
 354   }
 355 
 356   const intx scan_interval = PrefetchScanIntervalInBytes;
 357   const intx copy_interval = PrefetchCopyIntervalInBytes;
 358 
 359   while (q < t) {
 360     if (!oop(q)->is_gc_marked()) {
 361       // mark is pointer to next marked oop
 362       debug_only(prev_q = q);
 363       q = (HeapWord*) oop(q)->mark()->decode_pointer();
 364       assert(q > prev_q, "we should be moving forward through memory");
 365     } else {
 366       // prefetch beyond q
 367       Prefetch::read(q, scan_interval);
 368 
 369       // size and destination
 370       size_t size = oop(q)->size();
 371       HeapWord* compaction_top = (HeapWord*)oop(q)->forwardee();
 372 
 373       // prefetch beyond compaction_top
 374       Prefetch::write(compaction_top, copy_interval);
 375 
 376       // copy object and reinit its mark
 377       assert(q != compaction_top, "everything in this pass should be moving");
 378       Copy::aligned_conjoint_words(q, compaction_top, size);
 379       oop(compaction_top)->init_mark();
 380       assert(oop(compaction_top)->klass() != NULL, "should have a class");
 381 
 382       debug_only(prev_q = q);
 383       q += size;
 384     }
 385   }
 386 
 387   assert(compaction_top() >= space()->bottom() && compaction_top() <= space()->end(),
 388          "should point inside space");
 389   space()->set_top(compaction_top());
 390 
 391   if (mangle_free_space) {
 392     space()->mangle_unused_area();
 393   }
 394 }