1 /*
   2  * Copyright (c) 2010, 2018, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #include "precompiled.hpp"
  26 #include "gc/cms/compactibleFreeListSpace.hpp"
  27 #include "gc/cms/promotionInfo.hpp"
  28 #include "gc/shared/genOopClosures.hpp"
  29 #include "oops/compressedOops.inline.hpp"
  30 #include "oops/markWord.inline.hpp"
  31 #include "oops/oop.hpp"
  32 
  33 /////////////////////////////////////////////////////////////////////////
  34 //// PromotionInfo
  35 /////////////////////////////////////////////////////////////////////////
  36 
  37 
  38 PromotedObject* PromotedObject::next() const {
  39   assert(!((FreeChunk*)this)->is_free(), "Error");
  40   PromotedObject* res;
  41   if (UseCompressedOops) {
  42     // The next pointer is a compressed oop stored in the top 32 bits
  43     res = (PromotedObject*)CompressedOops::decode(_data._narrow_next);
  44   } else {
  45     res = (PromotedObject*)(_next & next_mask);
  46   }
  47   assert(oopDesc::is_oop_or_null(oop(res), true /* ignore mark word */), "Expected an oop or NULL at " PTR_FORMAT, p2i(oop(res)));
  48   return res;
  49 }
  50 
  51 inline void PromotedObject::setNext(PromotedObject* x) {
  52   assert(((intptr_t)x & ~next_mask) == 0, "Conflict in bit usage, "
  53          "or insufficient alignment of objects");
  54   if (UseCompressedOops) {
  55     assert(_data._narrow_next == 0, "Overwrite?");
  56     _data._narrow_next = CompressedOops::encode(oop(x));
  57   } else {
  58     _next |= (intptr_t)x;
  59   }
  60   assert(!((FreeChunk*)this)->is_free(), "Error");
  61 }
  62 
  63 // Return the next displaced header, incrementing the pointer and
  64 // recycling spool area as necessary.
  65 markWord PromotionInfo::nextDisplacedHeader() {
  66   assert(_spoolHead != NULL, "promotionInfo inconsistency");
  67   assert(_spoolHead != _spoolTail || _firstIndex < _nextIndex,
  68          "Empty spool space: no displaced header can be fetched");
  69   assert(_spoolHead->bufferSize > _firstIndex, "Off by one error at head?");
  70   markWord hdr = _spoolHead->displacedHdr[_firstIndex];
  71   // Spool forward
  72   if (++_firstIndex == _spoolHead->bufferSize) { // last location in this block
  73     // forward to next block, recycling this block into spare spool buffer
  74     SpoolBlock* tmp = _spoolHead->nextSpoolBlock;
  75     assert(_spoolHead != _spoolTail, "Spooling storage mix-up");
  76     _spoolHead->nextSpoolBlock = _spareSpool;
  77     _spareSpool = _spoolHead;
  78     _spoolHead = tmp;
  79     _firstIndex = 1;
  80     NOT_PRODUCT(
  81       if (_spoolHead == NULL) {  // all buffers fully consumed
  82         assert(_spoolTail == NULL && _nextIndex == 1,
  83                "spool buffers processing inconsistency");
  84       }
  85     )
  86   }
  87   return hdr;
  88 }
  89 
  90 void PromotionInfo::track(PromotedObject* trackOop) {
  91   track(trackOop, oop(trackOop)->klass());
  92 }
  93 
  94 void PromotionInfo::track(PromotedObject* trackOop, Klass* klassOfOop) {
  95   // make a copy of header as it may need to be spooled
  96   markWord mark = oop(trackOop)->mark_raw();
  97   trackOop->clear_next();
  98   if (mark.must_be_preserved_for_cms_scavenge(klassOfOop)) {
  99     // save non-prototypical header, and mark oop
 100     saveDisplacedHeader(mark);
 101     trackOop->setDisplacedMark();
 102   } else {
 103     // we'd like to assert something like the following:
 104     // assert(mark == markWord::prototype(), "consistency check");
 105     // ... but the above won't work because the age bits have not (yet) been
 106     // cleared. The remainder of the check would be identical to the
 107     // condition checked in must_be_preserved() above, so we don't really
 108     // have anything useful to check here!
 109   }
 110   if (_promoTail != NULL) {
 111     assert(_promoHead != NULL, "List consistency");
 112     _promoTail->setNext(trackOop);
 113     _promoTail = trackOop;
 114   } else {
 115     assert(_promoHead == NULL, "List consistency");
 116     _promoHead = _promoTail = trackOop;
 117   }
 118   // Mask as newly promoted, so we can skip over such objects
 119   // when scanning dirty cards
 120   assert(!trackOop->hasPromotedMark(), "Should not have been marked");
 121   trackOop->setPromotedMark();
 122 }
 123 
 124 // Save the given displaced header, incrementing the pointer and
 125 // obtaining more spool area as necessary.
 126 void PromotionInfo::saveDisplacedHeader(markWord hdr) {
 127   assert(_spoolHead != NULL && _spoolTail != NULL,
 128          "promotionInfo inconsistency");
 129   assert(_spoolTail->bufferSize > _nextIndex, "Off by one error at tail?");
 130   _spoolTail->displacedHdr[_nextIndex] = hdr;
 131   // Spool forward
 132   if (++_nextIndex == _spoolTail->bufferSize) { // last location in this block
 133     // get a new spooling block
 134     assert(_spoolTail->nextSpoolBlock == NULL, "tail should terminate spool list");
 135     _splice_point = _spoolTail;                   // save for splicing
 136     _spoolTail->nextSpoolBlock = getSpoolBlock(); // might fail
 137     _spoolTail = _spoolTail->nextSpoolBlock;      // might become NULL ...
 138     // ... but will attempt filling before next promotion attempt
 139     _nextIndex = 1;
 140   }
 141 }
 142 
 143 // Ensure that spooling space exists. Return false if spooling space
 144 // could not be obtained.
 145 bool PromotionInfo::ensure_spooling_space_work() {
 146   assert(!has_spooling_space(), "Only call when there is no spooling space");
 147   // Try and obtain more spooling space
 148   SpoolBlock* newSpool = getSpoolBlock();
 149   assert(newSpool == NULL ||
 150          (newSpool->bufferSize != 0 && newSpool->nextSpoolBlock == NULL),
 151         "getSpoolBlock() sanity check");
 152   if (newSpool == NULL) {
 153     return false;
 154   }
 155   _nextIndex = 1;
 156   if (_spoolTail == NULL) {
 157     _spoolTail = newSpool;
 158     if (_spoolHead == NULL) {
 159       _spoolHead = newSpool;
 160       _firstIndex = 1;
 161     } else {
 162       assert(_splice_point != NULL && _splice_point->nextSpoolBlock == NULL,
 163              "Splice point invariant");
 164       // Extra check that _splice_point is connected to list
 165       #ifdef ASSERT
 166       {
 167         SpoolBlock* blk = _spoolHead;
 168         for (; blk->nextSpoolBlock != NULL;
 169              blk = blk->nextSpoolBlock);
 170         assert(blk != NULL && blk == _splice_point,
 171                "Splice point incorrect");
 172       }
 173       #endif // ASSERT
 174       _splice_point->nextSpoolBlock = newSpool;
 175     }
 176   } else {
 177     assert(_spoolHead != NULL, "spool list consistency");
 178     _spoolTail->nextSpoolBlock = newSpool;
 179     _spoolTail = newSpool;
 180   }
 181   return true;
 182 }
 183 
 184 // Get a free spool buffer from the free pool, getting a new block
 185 // from the heap if necessary.
 186 SpoolBlock* PromotionInfo::getSpoolBlock() {
 187   SpoolBlock* res;
 188   if ((res = _spareSpool) != NULL) {
 189     _spareSpool = _spareSpool->nextSpoolBlock;
 190     res->nextSpoolBlock = NULL;
 191   } else {  // spare spool exhausted, get some from heap
 192     res = (SpoolBlock*)(space()->allocateScratch(refillSize()));
 193     if (res != NULL) {
 194       res->init();
 195     }
 196   }
 197   assert(res == NULL || res->nextSpoolBlock == NULL, "postcondition");
 198   return res;
 199 }
 200 
 201 void PromotionInfo::startTrackingPromotions() {
 202   assert(noPromotions(), "sanity");
 203   assert(_spoolHead == _spoolTail && _firstIndex == _nextIndex,
 204          "spooling inconsistency?");
 205   _firstIndex = _nextIndex = 1;
 206   _tracking = true;
 207 }
 208 
 209 void PromotionInfo::stopTrackingPromotions() {
 210   assert(noPromotions(), "we should have torn down the lists by now");
 211   assert(_spoolHead == _spoolTail && _firstIndex == _nextIndex,
 212          "spooling inconsistency?");
 213   _firstIndex = _nextIndex = 1;
 214   _tracking = false;
 215 }
 216 
 217 // When _spoolTail is not NULL, then the slot <_spoolTail, _nextIndex>
 218 // points to the next slot available for filling.
 219 // The set of slots holding displaced headers are then all those in the
 220 // right-open interval denoted by:
 221 //
 222 //    [ <_spoolHead, _firstIndex>, <_spoolTail, _nextIndex> )
 223 //
 224 // When _spoolTail is NULL, then the set of slots with displaced headers
 225 // is all those starting at the slot <_spoolHead, _firstIndex> and
 226 // going up to the last slot of last block in the linked list.
 227 // In this latter case, _splice_point points to the tail block of
 228 // this linked list of blocks holding displaced headers.
 229 void PromotionInfo::verify() const {
 230   // Verify the following:
 231   // 1. the number of displaced headers matches the number of promoted
 232   //    objects that have displaced headers
 233   // 2. each promoted object lies in this space
 234   debug_only(
 235     PromotedObject* junk = NULL;
 236     assert(junk->next_addr() == (void*)(oop(junk)->mark_addr_raw()),
 237            "Offset of PromotedObject::_next is expected to align with "
 238            "  the OopDesc::_mark within OopDesc");
 239   )
 240   // FIXME: guarantee????
 241   guarantee(_spoolHead == NULL || _spoolTail != NULL ||
 242             _splice_point != NULL, "list consistency");
 243   guarantee(_promoHead == NULL || _promoTail != NULL, "list consistency");
 244   // count the number of objects with displaced headers
 245   size_t numObjsWithDisplacedHdrs = 0;
 246   for (PromotedObject* curObj = _promoHead; curObj != NULL; curObj = curObj->next()) {
 247     guarantee(space()->is_in_reserved((HeapWord*)curObj), "Containment");
 248     // the last promoted object may fail the mark() != NULL test of is_oop().
 249     guarantee(curObj->next() == NULL || oopDesc::is_oop(oop(curObj)), "must be an oop");
 250     if (curObj->hasDisplacedMark()) {
 251       numObjsWithDisplacedHdrs++;
 252     }
 253   }
 254   // Count the number of displaced headers
 255   size_t numDisplacedHdrs = 0;
 256   for (SpoolBlock* curSpool = _spoolHead;
 257        curSpool != _spoolTail && curSpool != NULL;
 258        curSpool = curSpool->nextSpoolBlock) {
 259     // the first entry is just a self-pointer; indices 1 through
 260     // bufferSize - 1 are occupied (thus, bufferSize - 1 slots).
 261     guarantee((void*)curSpool->displacedHdr == (void*)&curSpool->displacedHdr,
 262               "first entry of displacedHdr should be self-referential");
 263     numDisplacedHdrs += curSpool->bufferSize - 1;
 264   }
 265   guarantee((_spoolHead == _spoolTail) == (numDisplacedHdrs == 0),
 266             "internal consistency");
 267   guarantee(_spoolTail != NULL || _nextIndex == 1,
 268             "Inconsistency between _spoolTail and _nextIndex");
 269   // We overcounted (_firstIndex-1) worth of slots in block
 270   // _spoolHead and we undercounted (_nextIndex-1) worth of
 271   // slots in block _spoolTail. We make an appropriate
 272   // adjustment by subtracting the first and adding the
 273   // second:  - (_firstIndex - 1) + (_nextIndex - 1)
 274   numDisplacedHdrs += (_nextIndex - _firstIndex);
 275   guarantee(numDisplacedHdrs == numObjsWithDisplacedHdrs, "Displaced hdr count");
 276 }
 277 
 278 void PromotionInfo::print_on(outputStream* st) const {
 279   SpoolBlock* curSpool = NULL;
 280   size_t i = 0;
 281   st->print_cr(" start & end indices: [" SIZE_FORMAT ", " SIZE_FORMAT ")",
 282                _firstIndex, _nextIndex);
 283   for (curSpool = _spoolHead; curSpool != _spoolTail && curSpool != NULL;
 284        curSpool = curSpool->nextSpoolBlock) {
 285     curSpool->print_on(st);
 286     st->print_cr(" active ");
 287     i++;
 288   }
 289   for (curSpool = _spoolTail; curSpool != NULL;
 290        curSpool = curSpool->nextSpoolBlock) {
 291     curSpool->print_on(st);
 292     st->print_cr(" inactive ");
 293     i++;
 294   }
 295   for (curSpool = _spareSpool; curSpool != NULL;
 296        curSpool = curSpool->nextSpoolBlock) {
 297     curSpool->print_on(st);
 298     st->print_cr(" free ");
 299     i++;
 300   }
 301   st->print_cr("  " SIZE_FORMAT " header spooling blocks", i);
 302 }
 303 
 304 void SpoolBlock::print_on(outputStream* st) const {
 305   st->print("[" PTR_FORMAT "," PTR_FORMAT "), " SIZE_FORMAT " HeapWords -> " PTR_FORMAT,
 306             p2i(this), p2i((HeapWord*)displacedHdr + bufferSize),
 307             bufferSize, p2i(nextSpoolBlock));
 308 }