1 /* 2 * Copyright (c) 2011, 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 "gc/g1/g1CollectedHeap.inline.hpp" 27 #include "gc/g1/heapRegionRemSet.hpp" 28 #include "gc/g1/heapRegionSet.inline.hpp" 29 30 uint FreeRegionList::_unrealistically_long_length = 0; 31 32 void HeapRegionSetBase::fill_in_ext_msg(hrs_ext_msg* msg, const char* message) { 33 msg->append("[%s] %s ln: %u cy: " SIZE_FORMAT, 34 name(), message, length(), total_capacity_bytes()); 35 fill_in_ext_msg_extra(msg); 36 } 37 38 #ifndef PRODUCT 39 void HeapRegionSetBase::verify_region(HeapRegion* hr) { 40 assert(hr->containing_set() == this, "Inconsistent containing set for %u", hr->hrm_index()); 41 assert(!hr->is_young(), "Adding young region %u", hr->hrm_index()); // currently we don't use these sets for young regions 42 assert(hr->is_humongous() == regions_humongous(), "Wrong humongous state for region %u and set %s", hr->hrm_index(), name()); 43 assert(hr->is_free() == regions_free(), "Wrong free state for region %u and set %s", hr->hrm_index(), name()); 44 assert(!hr->is_free() || hr->is_empty(), "Free region %u is not empty for set %s", hr->hrm_index(), name()); 45 assert(!hr->is_empty() || hr->is_free() || hr->is_archive(), 46 "Empty region %u is not free or archive for set %s", hr->hrm_index(), name()); 47 assert(hr->rem_set()->verify_ready_for_par_iteration(), "Wrong iteration state %u", hr->hrm_index()); 48 } 49 #endif 50 51 void HeapRegionSetBase::verify() { 52 // It's important that we also observe the MT safety protocol even 53 // for the verification calls. If we do verification without the 54 // appropriate locks and the set changes underneath our feet 55 // verification might fail and send us on a wild goose chase. 56 check_mt_safety(); 57 58 guarantee(( is_empty() && length() == 0 && total_capacity_bytes() == 0) || 59 (!is_empty() && length() > 0 && total_capacity_bytes() > 0) , 60 "%s", hrs_ext_msg(this, "invariant").buffer()); 61 } 62 63 void HeapRegionSetBase::verify_start() { 64 // See comment in verify() about MT safety and verification. 65 check_mt_safety(); 66 assert(!_verify_in_progress, 67 "%s", hrs_ext_msg(this, "verification should not be in progress").buffer()); 68 69 // Do the basic verification first before we do the checks over the regions. 70 HeapRegionSetBase::verify(); 71 72 _verify_in_progress = true; 73 } 74 75 void HeapRegionSetBase::verify_end() { 76 // See comment in verify() about MT safety and verification. 77 check_mt_safety(); 78 assert(_verify_in_progress, 79 "%s", hrs_ext_msg(this, "verification should be in progress").buffer()); 80 81 _verify_in_progress = false; 82 } 83 84 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) { 85 out->cr(); 86 out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this)); 87 out->print_cr(" Region Assumptions"); 88 out->print_cr(" humongous : %s", BOOL_TO_STR(regions_humongous())); 89 out->print_cr(" free : %s", BOOL_TO_STR(regions_free())); 90 out->print_cr(" Attributes"); 91 out->print_cr(" length : %14u", length()); 92 out->print_cr(" total capacity : " SIZE_FORMAT_W(14) " bytes", 93 total_capacity_bytes()); 94 } 95 96 HeapRegionSetBase::HeapRegionSetBase(const char* name, bool humongous, bool free, HRSMtSafeChecker* mt_safety_checker) 97 : _name(name), _verify_in_progress(false), 98 _is_humongous(humongous), _is_free(free), _mt_safety_checker(mt_safety_checker), 99 _count() 100 { } 101 102 void FreeRegionList::set_unrealistically_long_length(uint len) { 103 guarantee(_unrealistically_long_length == 0, "should only be set once"); 104 _unrealistically_long_length = len; 105 } 106 107 void FreeRegionList::fill_in_ext_msg_extra(hrs_ext_msg* msg) { 108 msg->append(" hd: " PTR_FORMAT " tl: " PTR_FORMAT, p2i(_head), p2i(_tail)); 109 } 110 111 void FreeRegionList::remove_all() { 112 check_mt_safety(); 113 verify_optional(); 114 115 HeapRegion* curr = _head; 116 while (curr != NULL) { 117 verify_region(curr); 118 119 HeapRegion* next = curr->next(); 120 curr->set_next(NULL); 121 curr->set_prev(NULL); 122 curr->set_containing_set(NULL); 123 curr = next; 124 } 125 clear(); 126 127 verify_optional(); 128 } 129 130 void FreeRegionList::add_ordered(FreeRegionList* from_list) { 131 check_mt_safety(); 132 from_list->check_mt_safety(); 133 134 verify_optional(); 135 from_list->verify_optional(); 136 137 if (from_list->is_empty()) { 138 return; 139 } 140 141 #ifdef ASSERT 142 FreeRegionListIterator iter(from_list); 143 while (iter.more_available()) { 144 HeapRegion* hr = iter.get_next(); 145 // In set_containing_set() we check that we either set the value 146 // from NULL to non-NULL or vice versa to catch bugs. So, we have 147 // to NULL it first before setting it to the value. 148 hr->set_containing_set(NULL); 149 hr->set_containing_set(this); 150 } 151 #endif // ASSERT 152 153 if (is_empty()) { 154 assert(length() == 0 && _tail == NULL, "%s", hrs_ext_msg(this, "invariant").buffer()); 155 _head = from_list->_head; 156 _tail = from_list->_tail; 157 } else { 158 HeapRegion* curr_to = _head; 159 HeapRegion* curr_from = from_list->_head; 160 161 while (curr_from != NULL) { 162 while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) { 163 curr_to = curr_to->next(); 164 } 165 166 if (curr_to == NULL) { 167 // The rest of the from list should be added as tail 168 _tail->set_next(curr_from); 169 curr_from->set_prev(_tail); 170 curr_from = NULL; 171 } else { 172 HeapRegion* next_from = curr_from->next(); 173 174 curr_from->set_next(curr_to); 175 curr_from->set_prev(curr_to->prev()); 176 if (curr_to->prev() == NULL) { 177 _head = curr_from; 178 } else { 179 curr_to->prev()->set_next(curr_from); 180 } 181 curr_to->set_prev(curr_from); 182 183 curr_from = next_from; 184 } 185 } 186 187 if (_tail->hrm_index() < from_list->_tail->hrm_index()) { 188 _tail = from_list->_tail; 189 } 190 } 191 192 _count.increment(from_list->length(), from_list->total_capacity_bytes()); 193 from_list->clear(); 194 195 verify_optional(); 196 from_list->verify_optional(); 197 } 198 199 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) { 200 check_mt_safety(); 201 assert(num_regions >= 1, "%s", hrs_ext_msg(this, "pre-condition").buffer()); 202 assert(!is_empty(), "%s", hrs_ext_msg(this, "pre-condition").buffer()); 203 204 verify_optional(); 205 DEBUG_ONLY(uint old_length = length();) 206 207 HeapRegion* curr = first; 208 uint count = 0; 209 while (count < num_regions) { 210 verify_region(curr); 211 HeapRegion* next = curr->next(); 212 HeapRegion* prev = curr->prev(); 213 214 assert(count < num_regions, 215 "%s", hrs_err_msg("[%s] should not come across more regions " 216 "pending for removal than num_regions: %u", 217 name(), num_regions).buffer()); 218 219 if (prev == NULL) { 220 assert(_head == curr, "%s", hrs_ext_msg(this, "invariant").buffer()); 221 _head = next; 222 } else { 223 assert(_head != curr, "%s", hrs_ext_msg(this, "invariant").buffer()); 224 prev->set_next(next); 225 } 226 if (next == NULL) { 227 assert(_tail == curr, "%s", hrs_ext_msg(this, "invariant").buffer()); 228 _tail = prev; 229 } else { 230 assert(_tail != curr, "%s", hrs_ext_msg(this, "invariant").buffer()); 231 next->set_prev(prev); 232 } 233 if (_last = curr) { 234 _last = NULL; 235 } 236 237 curr->set_next(NULL); 238 curr->set_prev(NULL); 239 remove(curr); 240 241 count++; 242 curr = next; 243 } 244 245 assert(count == num_regions, 246 "%s", hrs_err_msg("[%s] count: %u should be == num_regions: %u", 247 name(), count, num_regions).buffer()); 248 assert(length() + num_regions == old_length, 249 "%s", hrs_err_msg("[%s] new length should be consistent " 250 "new length: %u old length: %u num_regions: %u", 251 name(), length(), old_length, num_regions).buffer()); 252 253 verify_optional(); 254 } 255 256 void FreeRegionList::verify() { 257 // See comment in HeapRegionSetBase::verify() about MT safety and 258 // verification. 259 check_mt_safety(); 260 261 // This will also do the basic verification too. 262 verify_start(); 263 264 verify_list(); 265 266 verify_end(); 267 } 268 269 void FreeRegionList::clear() { 270 _count = HeapRegionSetCount(); 271 _head = NULL; 272 _tail = NULL; 273 _last = NULL; 274 } 275 276 void FreeRegionList::print_on(outputStream* out, bool print_contents) { 277 HeapRegionSetBase::print_on(out, print_contents); 278 out->print_cr(" Linking"); 279 out->print_cr(" head : " PTR_FORMAT, p2i(_head)); 280 out->print_cr(" tail : " PTR_FORMAT, p2i(_tail)); 281 282 if (print_contents) { 283 out->print_cr(" Contents"); 284 FreeRegionListIterator iter(this); 285 while (iter.more_available()) { 286 HeapRegion* hr = iter.get_next(); 287 hr->print_on(out); 288 } 289 } 290 291 out->cr(); 292 } 293 294 void FreeRegionList::verify_list() { 295 HeapRegion* curr = _head; 296 HeapRegion* prev1 = NULL; 297 HeapRegion* prev0 = NULL; 298 uint count = 0; 299 size_t capacity = 0; 300 uint last_index = 0; 301 302 guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev"); 303 while (curr != NULL) { 304 verify_region(curr); 305 306 count++; 307 guarantee(count < _unrealistically_long_length, 308 "%s", hrs_err_msg("[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u", 309 name(), count, p2i(curr), p2i(prev0), p2i(prev1), length()).buffer()); 310 311 if (curr->next() != NULL) { 312 guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up"); 313 } 314 guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted"); 315 last_index = curr->hrm_index(); 316 317 capacity += curr->capacity(); 318 319 prev1 = prev0; 320 prev0 = curr; 321 curr = curr->next(); 322 } 323 324 guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index()); 325 guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next"); 326 guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count); 327 guarantee(total_capacity_bytes() == capacity, "%s capacity mismatch. Expected " SIZE_FORMAT ", actual " SIZE_FORMAT, 328 name(), total_capacity_bytes(), capacity); 329 } 330 331 // Note on the check_mt_safety() methods below: 332 // 333 // Verification of the "master" heap region sets / lists that are 334 // maintained by G1CollectedHeap is always done during a STW pause and 335 // by the VM thread at the start / end of the pause. The standard 336 // verification methods all assert check_mt_safety(). This is 337 // important as it ensures that verification is done without 338 // concurrent updates taking place at the same time. It follows, that, 339 // for the "master" heap region sets / lists, the check_mt_safety() 340 // method should include the VM thread / STW case. 341 342 void MasterFreeRegionListMtSafeChecker::check() { 343 // Master Free List MT safety protocol: 344 // (a) If we're at a safepoint, operations on the master free list 345 // should be invoked by either the VM thread (which will serialize 346 // them) or by the GC workers while holding the 347 // FreeList_lock. 348 // (b) If we're not at a safepoint, operations on the master free 349 // list should be invoked while holding the Heap_lock. 350 351 if (SafepointSynchronize::is_at_safepoint()) { 352 guarantee(Thread::current()->is_VM_thread() || 353 FreeList_lock->owned_by_self(), "master free list MT safety protocol at a safepoint"); 354 } else { 355 guarantee(Heap_lock->owned_by_self(), "master free list MT safety protocol outside a safepoint"); 356 } 357 } 358 359 void SecondaryFreeRegionListMtSafeChecker::check() { 360 // Secondary Free List MT safety protocol: 361 // Operations on the secondary free list should always be invoked 362 // while holding the SecondaryFreeList_lock. 363 364 guarantee(SecondaryFreeList_lock->owned_by_self(), "secondary free list MT safety protocol"); 365 } 366 367 void OldRegionSetMtSafeChecker::check() { 368 // Master Old Set MT safety protocol: 369 // (a) If we're at a safepoint, operations on the master old set 370 // should be invoked: 371 // - by the VM thread (which will serialize them), or 372 // - by the GC workers while holding the FreeList_lock, if we're 373 // at a safepoint for an evacuation pause (this lock is taken 374 // anyway when an GC alloc region is retired so that a new one 375 // is allocated from the free list), or 376 // - by the GC workers while holding the OldSets_lock, if we're at a 377 // safepoint for a cleanup pause. 378 // (b) If we're not at a safepoint, operations on the master old set 379 // should be invoked while holding the Heap_lock. 380 381 if (SafepointSynchronize::is_at_safepoint()) { 382 guarantee(Thread::current()->is_VM_thread() 383 || FreeList_lock->owned_by_self() || OldSets_lock->owned_by_self(), 384 "master old set MT safety protocol at a safepoint"); 385 } else { 386 guarantee(Heap_lock->owned_by_self(), "master old set MT safety protocol outside a safepoint"); 387 } 388 } 389 390 void HumongousRegionSetMtSafeChecker::check() { 391 // Humongous Set MT safety protocol: 392 // (a) If we're at a safepoint, operations on the master humongous 393 // set should be invoked by either the VM thread (which will 394 // serialize them) or by the GC workers while holding the 395 // OldSets_lock. 396 // (b) If we're not at a safepoint, operations on the master 397 // humongous set should be invoked while holding the Heap_lock. 398 399 if (SafepointSynchronize::is_at_safepoint()) { 400 guarantee(Thread::current()->is_VM_thread() || 401 OldSets_lock->owned_by_self(), 402 "master humongous set MT safety protocol at a safepoint"); 403 } else { 404 guarantee(Heap_lock->owned_by_self(), 405 "master humongous set MT safety protocol outside a safepoint"); 406 } 407 } 408 409 void FreeRegionList_test() { 410 FreeRegionList l("test"); 411 412 const uint num_regions_in_test = 5; 413 // Create a fake heap. It does not need to be valid, as the HeapRegion constructor 414 // does not access it. 415 MemRegion heap(NULL, num_regions_in_test * HeapRegion::GrainWords); 416 // Allocate a fake BOT because the HeapRegion constructor initializes 417 // the BOT. 418 size_t bot_size = G1BlockOffsetSharedArray::compute_size(heap.word_size()); 419 HeapWord* bot_data = NEW_C_HEAP_ARRAY(HeapWord, bot_size, mtGC); 420 ReservedSpace bot_rs(G1BlockOffsetSharedArray::compute_size(heap.word_size())); 421 G1RegionToSpaceMapper* bot_storage = 422 G1RegionToSpaceMapper::create_mapper(bot_rs, 423 bot_rs.size(), 424 os::vm_page_size(), 425 HeapRegion::GrainBytes, 426 G1BlockOffsetSharedArray::N_bytes, 427 mtGC); 428 G1BlockOffsetSharedArray oa(heap, bot_storage); 429 bot_storage->commit_regions(0, num_regions_in_test); 430 431 // Set up memory regions for the heap regions. 432 MemRegion mr0(heap.start(), HeapRegion::GrainWords); 433 MemRegion mr1(mr0.end(), HeapRegion::GrainWords); 434 MemRegion mr2(mr1.end(), HeapRegion::GrainWords); 435 MemRegion mr3(mr2.end(), HeapRegion::GrainWords); 436 MemRegion mr4(mr3.end(), HeapRegion::GrainWords); 437 438 HeapRegion hr0(0, &oa, mr0); 439 HeapRegion hr1(1, &oa, mr1); 440 HeapRegion hr2(2, &oa, mr2); 441 HeapRegion hr3(3, &oa, mr3); 442 HeapRegion hr4(4, &oa, mr4); 443 l.add_ordered(&hr1); 444 l.add_ordered(&hr0); 445 l.add_ordered(&hr3); 446 l.add_ordered(&hr4); 447 l.add_ordered(&hr2); 448 assert(l.length() == num_regions_in_test, "wrong length"); 449 l.verify_list(); 450 451 bot_storage->uncommit_regions(0, num_regions_in_test); 452 delete bot_storage; 453 FREE_C_HEAP_ARRAY(HeapWord, bot_data); 454 }