1 /*
   2  * Copyright (c) 2001, 2016, 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/g1/concurrentG1Refine.hpp"
  27 #include "gc/g1/g1CollectedHeap.inline.hpp"
  28 #include "gc/g1/heapRegion.hpp"
  29 #include "gc/g1/heapRegionManager.inline.hpp"
  30 #include "gc/g1/heapRegionSet.inline.hpp"
  31 #include "memory/allocation.hpp"
  32 
  33 void HeapRegionManager::initialize(G1RegionToSpaceMapper* heap_storage,
  34                                G1RegionToSpaceMapper* prev_bitmap,
  35                                G1RegionToSpaceMapper* next_bitmap,
  36                                G1RegionToSpaceMapper* bot,
  37                                G1RegionToSpaceMapper* cardtable,
  38                                G1RegionToSpaceMapper* card_counts) {
  39   _allocated_heapregions_length = 0;
  40 
  41   _heap_mapper = heap_storage;
  42 
  43   _prev_bitmap_mapper = prev_bitmap;
  44   _next_bitmap_mapper = next_bitmap;
  45 
  46   _bot_mapper = bot;
  47   _cardtable_mapper = cardtable;
  48 
  49   _card_counts_mapper = card_counts;
  50 
  51   MemRegion reserved = heap_storage->reserved();
  52   _regions.initialize(reserved.start(), reserved.end(), HeapRegion::GrainBytes);
  53 
  54   _available_map.initialize(_regions.length());
  55 }
  56 
  57 bool HeapRegionManager::is_available(uint region) const {
  58   return _available_map.at(region);
  59 }
  60 
  61 #ifdef ASSERT
  62 bool HeapRegionManager::is_free(HeapRegion* hr) const {
  63   return _free_list.contains(hr);
  64 }
  65 #endif
  66 
  67 HeapRegion* HeapRegionManager::new_heap_region(uint hrm_index) {
  68   G1CollectedHeap* g1h = G1CollectedHeap::heap();
  69   HeapWord* bottom = g1h->bottom_addr_for_region(hrm_index);
  70   MemRegion mr(bottom, bottom + HeapRegion::GrainWords);
  71   assert(reserved().contains(mr), "invariant");
  72   return g1h->new_heap_region(hrm_index, mr);
  73 }
  74 
  75 void HeapRegionManager::commit_regions(uint index, size_t num_regions) {
  76   guarantee(num_regions > 0, "Must commit more than zero regions");
  77   guarantee(_num_committed + num_regions <= max_length(), "Cannot commit more than the maximum amount of regions");
  78 
  79   _num_committed += (uint)num_regions;
  80 
  81   _heap_mapper->commit_regions(index, num_regions);
  82 
  83   // Also commit auxiliary data
  84   _prev_bitmap_mapper->commit_regions(index, num_regions);
  85   _next_bitmap_mapper->commit_regions(index, num_regions);
  86 
  87   _bot_mapper->commit_regions(index, num_regions);
  88   _cardtable_mapper->commit_regions(index, num_regions);
  89 
  90   _card_counts_mapper->commit_regions(index, num_regions);
  91 }
  92 
  93 void HeapRegionManager::uncommit_regions(uint start, size_t num_regions) {
  94   guarantee(num_regions >= 1, "Need to specify at least one region to uncommit, tried to uncommit zero regions at %u", start);
  95   guarantee(_num_committed >= num_regions, "pre-condition");
  96 
  97   // Print before uncommitting.
  98   if (G1CollectedHeap::heap()->hr_printer()->is_active()) {
  99     for (uint i = start; i < start + num_regions; i++) {
 100       HeapRegion* hr = at(i);
 101       G1CollectedHeap::heap()->hr_printer()->uncommit(hr);
 102     }
 103   }
 104 
 105   _num_committed -= (uint)num_regions;
 106 
 107   _available_map.par_clear_range(start, start + num_regions, BitMap::unknown_range);
 108   _heap_mapper->uncommit_regions(start, num_regions);
 109 
 110   // Also uncommit auxiliary data
 111   _prev_bitmap_mapper->uncommit_regions(start, num_regions);
 112   _next_bitmap_mapper->uncommit_regions(start, num_regions);
 113 
 114   _bot_mapper->uncommit_regions(start, num_regions);
 115   _cardtable_mapper->uncommit_regions(start, num_regions);
 116 
 117   _card_counts_mapper->uncommit_regions(start, num_regions);
 118 }
 119 
 120 void HeapRegionManager::make_regions_available(uint start, uint num_regions) {
 121   guarantee(num_regions > 0, "No point in calling this for zero regions");
 122   commit_regions(start, num_regions);
 123   for (uint i = start; i < start + num_regions; i++) {
 124     if (_regions.get_by_index(i) == NULL) {
 125       HeapRegion* new_hr = new_heap_region(i);
 126       _regions.set_by_index(i, new_hr);
 127       _allocated_heapregions_length = MAX2(_allocated_heapregions_length, i + 1);
 128     }
 129   }
 130 
 131   _available_map.par_set_range(start, start + num_regions, BitMap::unknown_range);
 132 
 133   for (uint i = start; i < start + num_regions; i++) {
 134     assert(is_available(i), "Just made region %u available but is apparently not.", i);
 135     HeapRegion* hr = at(i);
 136     if (G1CollectedHeap::heap()->hr_printer()->is_active()) {
 137       G1CollectedHeap::heap()->hr_printer()->commit(hr);
 138     }
 139     HeapWord* bottom = G1CollectedHeap::heap()->bottom_addr_for_region(i);
 140     MemRegion mr(bottom, bottom + HeapRegion::GrainWords);
 141 
 142     hr->initialize(mr);
 143     insert_into_free_list(at(i));
 144   }
 145 }
 146 
 147 MemoryUsage HeapRegionManager::get_auxiliary_data_memory_usage() const {
 148   size_t used_sz =
 149     _prev_bitmap_mapper->committed_size() +
 150     _next_bitmap_mapper->committed_size() +
 151     _bot_mapper->committed_size() +
 152     _cardtable_mapper->committed_size() +
 153     _card_counts_mapper->committed_size();
 154 
 155   size_t committed_sz =
 156     _prev_bitmap_mapper->reserved_size() +
 157     _next_bitmap_mapper->reserved_size() +
 158     _bot_mapper->reserved_size() +
 159     _cardtable_mapper->reserved_size() +
 160     _card_counts_mapper->reserved_size();
 161 
 162   return MemoryUsage(0, used_sz, committed_sz, committed_sz);
 163 }
 164 
 165 uint HeapRegionManager::expand_by(uint num_regions) {
 166   return expand_at(0, num_regions);
 167 }
 168 
 169 uint HeapRegionManager::expand_at(uint start, uint num_regions) {
 170   if (num_regions == 0) {
 171     return 0;
 172   }
 173 
 174   uint cur = start;
 175   uint idx_last_found = 0;
 176   uint num_last_found = 0;
 177 
 178   uint expanded = 0;
 179 
 180   while (expanded < num_regions &&
 181          (num_last_found = find_unavailable_from_idx(cur, &idx_last_found)) > 0) {
 182     uint to_expand = MIN2(num_regions - expanded, num_last_found);
 183     make_regions_available(idx_last_found, to_expand);
 184     expanded += to_expand;
 185     cur = idx_last_found + num_last_found + 1;
 186   }
 187 
 188   verify_optional();
 189   return expanded;
 190 }
 191 
 192 uint HeapRegionManager::find_contiguous(size_t num, bool empty_only) {
 193   uint found = 0;
 194   size_t length_found = 0;
 195   uint cur = 0;
 196 
 197   while (length_found < num && cur < max_length()) {
 198     HeapRegion* hr = _regions.get_by_index(cur);
 199     if ((!empty_only && !is_available(cur)) || (is_available(cur) && hr != NULL && hr->is_empty())) {
 200       // This region is a potential candidate for allocation into.
 201       length_found++;
 202     } else {
 203       // This region is not a candidate. The next region is the next possible one.
 204       found = cur + 1;
 205       length_found = 0;
 206     }
 207     cur++;
 208   }
 209 
 210   if (length_found == num) {
 211     for (uint i = found; i < (found + num); i++) {
 212       HeapRegion* hr = _regions.get_by_index(i);
 213       // sanity check
 214       guarantee((!empty_only && !is_available(i)) || (is_available(i) && hr != NULL && hr->is_empty()),
 215                 "Found region sequence starting at " UINT32_FORMAT ", length " SIZE_FORMAT
 216                 " that is not empty at " UINT32_FORMAT ". Hr is " PTR_FORMAT, found, num, i, p2i(hr));
 217     }
 218     return found;
 219   } else {
 220     return G1_NO_HRM_INDEX;
 221   }
 222 }
 223 
 224 HeapRegion* HeapRegionManager::next_region_in_heap(const HeapRegion* r) const {
 225   guarantee(r != NULL, "Start region must be a valid region");
 226   guarantee(is_available(r->hrm_index()), "Trying to iterate starting from region %u which is not in the heap", r->hrm_index());
 227   for (uint i = r->hrm_index() + 1; i < _allocated_heapregions_length; i++) {
 228     HeapRegion* hr = _regions.get_by_index(i);
 229     if (is_available(i)) {
 230       return hr;
 231     }
 232   }
 233   return NULL;
 234 }
 235 
 236 void HeapRegionManager::iterate(HeapRegionClosure* blk) const {
 237   uint len = max_length();
 238 
 239   for (uint i = 0; i < len; i++) {
 240     if (!is_available(i)) {
 241       continue;
 242     }
 243     guarantee(at(i) != NULL, "Tried to access region %u that has a NULL HeapRegion*", i);
 244     bool res = blk->doHeapRegion(at(i));
 245     if (res) {
 246       blk->incomplete();
 247       return;
 248     }
 249   }
 250 }
 251 
 252 uint HeapRegionManager::find_unavailable_from_idx(uint start_idx, uint* res_idx) const {
 253   guarantee(res_idx != NULL, "checking");
 254   guarantee(start_idx <= (max_length() + 1), "checking");
 255 
 256   uint num_regions = 0;
 257 
 258   uint cur = start_idx;
 259   while (cur < max_length() && is_available(cur)) {
 260     cur++;
 261   }
 262   if (cur == max_length()) {
 263     return num_regions;
 264   }
 265   *res_idx = cur;
 266   while (cur < max_length() && !is_available(cur)) {
 267     cur++;
 268   }
 269   num_regions = cur - *res_idx;
 270 #ifdef ASSERT
 271   for (uint i = *res_idx; i < (*res_idx + num_regions); i++) {
 272     assert(!is_available(i), "just checking");
 273   }
 274   assert(cur == max_length() || num_regions == 0 || is_available(cur),
 275          "The region at the current position %u must be available or at the end of the heap.", cur);
 276 #endif
 277   return num_regions;
 278 }
 279 
 280 uint HeapRegionManager::find_highest_free(bool* expanded) {
 281   // Loop downwards from the highest region index, looking for an
 282   // entry which is either free or not yet committed.  If not yet
 283   // committed, expand_at that index.
 284   uint curr = max_length() - 1;
 285   while (true) {
 286     HeapRegion *hr = _regions.get_by_index(curr);
 287     if (hr == NULL) {
 288       uint res = expand_at(curr, 1);
 289       if (res == 1) {
 290         *expanded = true;
 291         return curr;
 292       }
 293     } else {
 294       if (hr->is_free()) {
 295         *expanded = false;
 296         return curr;
 297       }
 298     }
 299     if (curr == 0) {
 300       return G1_NO_HRM_INDEX;
 301     }
 302     curr--;
 303   }
 304 }
 305 
 306 bool HeapRegionManager::allocate_containing_regions(MemRegion range, size_t* commit_count) {
 307   size_t commits = 0;
 308   uint start_index = (uint)_regions.get_index_by_address(range.start());
 309   uint last_index = (uint)_regions.get_index_by_address(range.last());
 310 
 311   // Ensure that each G1 region in the range is free, returning false if not.
 312   // Commit those that are not yet available, and keep count.
 313   for (uint curr_index = start_index; curr_index <= last_index; curr_index++) {
 314     if (!is_available(curr_index)) {
 315       commits++;
 316       expand_at(curr_index, 1);
 317     }
 318     HeapRegion* curr_region  = _regions.get_by_index(curr_index);
 319     if (!curr_region->is_free()) {
 320       return false;
 321     }
 322   }
 323 
 324   allocate_free_regions_starting_at(start_index, (last_index - start_index) + 1);
 325   *commit_count = commits;
 326   return true;
 327 }
 328 
 329 void HeapRegionManager::par_iterate(HeapRegionClosure* blk, uint worker_id, HeapRegionClaimer* hrclaimer, bool concurrent) const {
 330   const uint start_index = hrclaimer->start_region_for_worker(worker_id);
 331 
 332   // Every worker will actually look at all regions, skipping over regions that
 333   // are currently not committed.
 334   // This also (potentially) iterates over regions newly allocated during GC. This
 335   // is no problem except for some extra work.
 336   const uint n_regions = hrclaimer->n_regions();
 337   for (uint count = 0; count < n_regions; count++) {
 338     const uint index = (start_index + count) % n_regions;
 339     assert(index < n_regions, "sanity");
 340     // Skip over unavailable regions
 341     if (!is_available(index)) {
 342       continue;
 343     }
 344     HeapRegion* r = _regions.get_by_index(index);
 345     // We'll ignore regions already claimed.
 346     // However, if the iteration is specified as concurrent, the values for
 347     // is_starts_humongous and is_continues_humongous can not be trusted,
 348     // and we should just blindly iterate over regions regardless of their
 349     // humongous status.
 350     if (hrclaimer->is_region_claimed(index)) {
 351       continue;
 352     }
 353     // OK, try to claim it
 354     if (!hrclaimer->claim_region(index)) {
 355       continue;
 356     }
 357     bool res = blk->doHeapRegion(r);
 358     if (res) {
 359       return;
 360     }
 361   }
 362 }
 363 
 364 uint HeapRegionManager::shrink_by(uint num_regions_to_remove) {
 365   assert(length() > 0, "the region sequence should not be empty");
 366   assert(length() <= _allocated_heapregions_length, "invariant");
 367   assert(_allocated_heapregions_length > 0, "we should have at least one region committed");
 368   assert(num_regions_to_remove < length(), "We should never remove all regions");
 369 
 370   if (num_regions_to_remove == 0) {
 371     return 0;
 372   }
 373 
 374   uint removed = 0;
 375   uint cur = _allocated_heapregions_length - 1;
 376   uint idx_last_found = 0;
 377   uint num_last_found = 0;
 378 
 379   while ((removed < num_regions_to_remove) &&
 380       (num_last_found = find_empty_from_idx_reverse(cur, &idx_last_found)) > 0) {
 381     uint to_remove = MIN2(num_regions_to_remove - removed, num_last_found);
 382 
 383     shrink_at(idx_last_found + num_last_found - to_remove, to_remove);
 384 
 385     cur = idx_last_found;
 386     removed += to_remove;
 387   }
 388 
 389   verify_optional();
 390 
 391   return removed;
 392 }
 393 
 394 void HeapRegionManager::shrink_at(uint index, size_t num_regions) {
 395 #ifdef ASSERT
 396   for (uint i = index; i < (index + num_regions); i++) {
 397     assert(is_available(i), "Expected available region at index %u", i);
 398     assert(at(i)->is_empty(), "Expected empty region at index %u", i);
 399     assert(at(i)->is_free(), "Expected free region at index %u", i);
 400   }
 401 #endif
 402   uncommit_regions(index, num_regions);
 403 }
 404 
 405 uint HeapRegionManager::find_empty_from_idx_reverse(uint start_idx, uint* res_idx) const {
 406   guarantee(start_idx < _allocated_heapregions_length, "checking");
 407   guarantee(res_idx != NULL, "checking");
 408 
 409   uint num_regions_found = 0;
 410 
 411   jlong cur = start_idx;
 412   while (cur != -1 && !(is_available(cur) && at(cur)->is_empty())) {
 413     cur--;
 414   }
 415   if (cur == -1) {
 416     return num_regions_found;
 417   }
 418   jlong old_cur = cur;
 419   // cur indexes the first empty region
 420   while (cur != -1 && is_available(cur) && at(cur)->is_empty()) {
 421     cur--;
 422   }
 423   *res_idx = cur + 1;
 424   num_regions_found = old_cur - cur;
 425 
 426 #ifdef ASSERT
 427   for (uint i = *res_idx; i < (*res_idx + num_regions_found); i++) {
 428     assert(at(i)->is_empty(), "just checking");
 429   }
 430 #endif
 431   return num_regions_found;
 432 }
 433 
 434 void HeapRegionManager::verify() {
 435   guarantee(length() <= _allocated_heapregions_length,
 436             "invariant: _length: %u _allocated_length: %u",
 437             length(), _allocated_heapregions_length);
 438   guarantee(_allocated_heapregions_length <= max_length(),
 439             "invariant: _allocated_length: %u _max_length: %u",
 440             _allocated_heapregions_length, max_length());
 441 
 442   bool prev_committed = true;
 443   uint num_committed = 0;
 444   HeapWord* prev_end = heap_bottom();
 445   for (uint i = 0; i < _allocated_heapregions_length; i++) {
 446     if (!is_available(i)) {
 447       prev_committed = false;
 448       continue;
 449     }
 450     num_committed++;
 451     HeapRegion* hr = _regions.get_by_index(i);
 452     guarantee(hr != NULL, "invariant: i: %u", i);
 453     guarantee(!prev_committed || hr->bottom() == prev_end,
 454               "invariant i: %u " HR_FORMAT " prev_end: " PTR_FORMAT,
 455               i, HR_FORMAT_PARAMS(hr), p2i(prev_end));
 456     guarantee(hr->hrm_index() == i,
 457               "invariant: i: %u hrm_index(): %u", i, hr->hrm_index());
 458     // Asserts will fire if i is >= _length
 459     HeapWord* addr = hr->bottom();
 460     guarantee(addr_to_region(addr) == hr, "sanity");
 461     // We cannot check whether the region is part of a particular set: at the time
 462     // this method may be called, we have only completed allocation of the regions,
 463     // but not put into a region set.
 464     prev_committed = true;
 465     prev_end = hr->end();
 466   }
 467   for (uint i = _allocated_heapregions_length; i < max_length(); i++) {
 468     guarantee(_regions.get_by_index(i) == NULL, "invariant i: %u", i);
 469   }
 470 
 471   guarantee(num_committed == _num_committed, "Found %u committed regions, but should be %u", num_committed, _num_committed);
 472   _free_list.verify();
 473 }
 474 
 475 #ifndef PRODUCT
 476 void HeapRegionManager::verify_optional() {
 477   verify();
 478 }
 479 #endif // PRODUCT
 480 
 481 HeapRegionClaimer::HeapRegionClaimer(uint n_workers) :
 482     _n_workers(n_workers), _n_regions(G1CollectedHeap::heap()->_hrm._allocated_heapregions_length), _claims(NULL) {
 483   assert(n_workers > 0, "Need at least one worker.");
 484   uint* new_claims = NEW_C_HEAP_ARRAY(uint, _n_regions, mtGC);
 485   memset(new_claims, Unclaimed, sizeof(*_claims) * _n_regions);
 486   _claims = new_claims;
 487 }
 488 
 489 HeapRegionClaimer::~HeapRegionClaimer() {
 490   if (_claims != NULL) {
 491     FREE_C_HEAP_ARRAY(uint, _claims);
 492   }
 493 }
 494 
 495 uint HeapRegionClaimer::start_region_for_worker(uint worker_id) const {
 496   assert(worker_id < _n_workers, "Invalid worker_id.");
 497   return _n_regions * worker_id / _n_workers;
 498 }
 499 
 500 bool HeapRegionClaimer::is_region_claimed(uint region_index) const {
 501   assert(region_index < _n_regions, "Invalid index.");
 502   return _claims[region_index] == Claimed;
 503 }
 504 
 505 bool HeapRegionClaimer::claim_region(uint region_index) {
 506   assert(region_index < _n_regions, "Invalid index.");
 507   uint old_val = Atomic::cmpxchg(Claimed, &_claims[region_index], Unclaimed);
 508   return old_val == Unclaimed;
 509 }