1 /* 2 * Copyright (c) 2011, 2019, 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/g1NUMA.hpp" 28 #include "gc/g1/heapRegionRemSet.hpp" 29 #include "gc/g1/heapRegionSet.inline.hpp" 30 31 uint FreeRegionList::_unrealistically_long_length = 0; 32 33 #ifndef PRODUCT 34 void HeapRegionSetBase::verify_region(HeapRegion* hr) { 35 assert(hr->containing_set() == this, "Inconsistent containing set for %u", hr->hrm_index()); 36 assert(!hr->is_young(), "Adding young region %u", hr->hrm_index()); // currently we don't use these sets for young regions 37 assert(_checker == NULL || _checker->is_correct_type(hr), "Wrong type of region %u (%s) and set %s", 38 hr->hrm_index(), hr->get_type_str(), name()); 39 assert(!hr->is_free() || hr->is_empty(), "Free region %u is not empty for set %s", hr->hrm_index(), name()); 40 assert(!hr->is_empty() || hr->is_free() || hr->is_archive(), 41 "Empty region %u is not free or archive for set %s", hr->hrm_index(), name()); 42 } 43 #endif 44 45 void HeapRegionSetBase::verify() { 46 // It's important that we also observe the MT safety protocol even 47 // for the verification calls. If we do verification without the 48 // appropriate locks and the set changes underneath our feet 49 // verification might fail and send us on a wild goose chase. 50 check_mt_safety(); 51 52 guarantee_heap_region_set(( is_empty() && length() == 0) || 53 (!is_empty() && length() > 0), 54 "invariant"); 55 } 56 57 void HeapRegionSetBase::verify_start() { 58 // See comment in verify() about MT safety and verification. 59 check_mt_safety(); 60 assert_heap_region_set(!_verify_in_progress, "verification should not be in progress"); 61 62 // Do the basic verification first before we do the checks over the regions. 63 HeapRegionSetBase::verify(); 64 65 _verify_in_progress = true; 66 } 67 68 void HeapRegionSetBase::verify_end() { 69 // See comment in verify() about MT safety and verification. 70 check_mt_safety(); 71 assert_heap_region_set(_verify_in_progress, "verification should be in progress"); 72 73 _verify_in_progress = false; 74 } 75 76 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) { 77 out->cr(); 78 out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this)); 79 out->print_cr(" Region Type : %s", _checker->get_description()); 80 out->print_cr(" Length : %14u", length()); 81 } 82 83 HeapRegionSetBase::HeapRegionSetBase(const char* name, HeapRegionSetChecker* checker) 84 : _checker(checker), _length(0), _name(name), _verify_in_progress(false) 85 { 86 } 87 88 void FreeRegionList::set_unrealistically_long_length(uint len) { 89 guarantee(_unrealistically_long_length == 0, "should only be set once"); 90 _unrealistically_long_length = len; 91 } 92 93 void FreeRegionList::abandon() { 94 check_mt_safety(); 95 clear(); 96 verify_optional(); 97 } 98 99 void FreeRegionList::remove_all() { 100 check_mt_safety(); 101 verify_optional(); 102 103 HeapRegion* curr = _head; 104 while (curr != NULL) { 105 verify_region(curr); 106 107 HeapRegion* next = curr->next(); 108 curr->set_next(NULL); 109 curr->set_prev(NULL); 110 curr->set_containing_set(NULL); 111 112 decrease_length(curr->node_index()); 113 114 curr = next; 115 } 116 clear(); 117 118 verify_optional(); 119 } 120 121 void FreeRegionList::add_list_common_start(FreeRegionList* from_list) { 122 check_mt_safety(); 123 from_list->check_mt_safety(); 124 verify_optional(); 125 from_list->verify_optional(); 126 127 if (from_list->is_empty()) { 128 return; 129 } 130 131 if (_node_info != NULL && from_list->_node_info != NULL) { 132 _node_info->add(from_list->_node_info); 133 } 134 135 #ifdef ASSERT 136 FreeRegionListIterator iter(from_list); 137 while (iter.more_available()) { 138 HeapRegion* hr = iter.get_next(); 139 // In set_containing_set() we check that we either set the value 140 // from NULL to non-NULL or vice versa to catch bugs. So, we have 141 // to NULL it first before setting it to the value. 142 hr->set_containing_set(NULL); 143 hr->set_containing_set(this); 144 } 145 #endif // ASSERT 146 } 147 148 void FreeRegionList::add_list_common_end(FreeRegionList* from_list) { 149 _length += from_list->length(); 150 from_list->clear(); 151 152 verify_optional(); 153 from_list->verify_optional(); 154 } 155 156 void FreeRegionList::append_ordered(FreeRegionList* from_list) { 157 add_list_common_start(from_list); 158 159 if (from_list->is_empty()) { 160 return; 161 } 162 163 if (is_empty()) { 164 // Make from_list the current list. 165 assert_free_region_list(length() == 0 && _tail == NULL, "invariant"); 166 _head = from_list->_head; 167 _tail = from_list->_tail; 168 } else { 169 // Add the from_list to the end of the current list. 170 assert(_tail->hrm_index() < from_list->_head->hrm_index(), "Should be sorted %u < %u", 171 _tail->hrm_index(), from_list->_head->hrm_index()); 172 173 _tail->set_next(from_list->_head); 174 from_list->_head->set_prev(_tail); 175 _tail = from_list->_tail; 176 } 177 178 add_list_common_end(from_list); 179 } 180 181 void FreeRegionList::add_ordered(FreeRegionList* from_list) { 182 add_list_common_start(from_list); 183 184 if (from_list->is_empty()) { 185 return; 186 } 187 188 if (is_empty()) { 189 assert_free_region_list(length() == 0 && _tail == NULL, "invariant"); 190 _head = from_list->_head; 191 _tail = from_list->_tail; 192 } else { 193 HeapRegion* curr_to = _head; 194 HeapRegion* curr_from = from_list->_head; 195 196 while (curr_from != NULL) { 197 while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) { 198 curr_to = curr_to->next(); 199 } 200 201 if (curr_to == NULL) { 202 // The rest of the from list should be added as tail 203 _tail->set_next(curr_from); 204 curr_from->set_prev(_tail); 205 curr_from = NULL; 206 } else { 207 HeapRegion* next_from = curr_from->next(); 208 209 curr_from->set_next(curr_to); 210 curr_from->set_prev(curr_to->prev()); 211 if (curr_to->prev() == NULL) { 212 _head = curr_from; 213 } else { 214 curr_to->prev()->set_next(curr_from); 215 } 216 curr_to->set_prev(curr_from); 217 218 curr_from = next_from; 219 } 220 } 221 222 if (_tail->hrm_index() < from_list->_tail->hrm_index()) { 223 _tail = from_list->_tail; 224 } 225 } 226 227 add_list_common_end(from_list); 228 } 229 230 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) { 231 check_mt_safety(); 232 assert_free_region_list(num_regions >= 1, "pre-condition"); 233 assert_free_region_list(!is_empty(), "pre-condition"); 234 235 verify_optional(); 236 DEBUG_ONLY(uint old_length = length();) 237 238 HeapRegion* curr = first; 239 uint count = 0; 240 while (count < num_regions) { 241 verify_region(curr); 242 HeapRegion* next = curr->next(); 243 HeapRegion* prev = curr->prev(); 244 245 assert(count < num_regions, 246 "[%s] should not come across more regions " 247 "pending for removal than num_regions: %u", 248 name(), num_regions); 249 250 if (prev == NULL) { 251 assert_free_region_list(_head == curr, "invariant"); 252 _head = next; 253 } else { 254 assert_free_region_list(_head != curr, "invariant"); 255 prev->set_next(next); 256 } 257 if (next == NULL) { 258 assert_free_region_list(_tail == curr, "invariant"); 259 _tail = prev; 260 } else { 261 assert_free_region_list(_tail != curr, "invariant"); 262 next->set_prev(prev); 263 } 264 if (_last == curr) { 265 _last = NULL; 266 } 267 268 curr->set_next(NULL); 269 curr->set_prev(NULL); 270 remove(curr); 271 272 count++; 273 274 decrease_length(curr->node_index()); 275 276 curr = next; 277 } 278 279 assert(count == num_regions, 280 "[%s] count: %u should be == num_regions: %u", 281 name(), count, num_regions); 282 assert(length() + num_regions == old_length, 283 "[%s] new length should be consistent " 284 "new length: %u old length: %u num_regions: %u", 285 name(), length(), old_length, num_regions); 286 287 verify_optional(); 288 } 289 290 uint FreeRegionList::num_of_regions_in_range(uint start, uint end) const { 291 HeapRegion* cur = _head; 292 uint num = 0; 293 while (cur != NULL) { 294 uint index = cur->hrm_index(); 295 if (index > end) { 296 break; 297 } else if (index >= start) { 298 num++; 299 } 300 cur = cur->next(); 301 } 302 return num; 303 } 304 305 void FreeRegionList::verify() { 306 // See comment in HeapRegionSetBase::verify() about MT safety and 307 // verification. 308 check_mt_safety(); 309 310 // This will also do the basic verification too. 311 verify_start(); 312 313 verify_list(); 314 315 verify_end(); 316 } 317 318 void FreeRegionList::clear() { 319 _length = 0; 320 _head = NULL; 321 _tail = NULL; 322 _last = NULL; 323 324 if (_node_info!= NULL) { 325 _node_info->clear(); 326 } 327 } 328 329 void FreeRegionList::verify_list() { 330 HeapRegion* curr = _head; 331 HeapRegion* prev1 = NULL; 332 HeapRegion* prev0 = NULL; 333 uint count = 0; 334 size_t capacity = 0; 335 uint last_index = 0; 336 337 guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev"); 338 while (curr != NULL) { 339 verify_region(curr); 340 341 count++; 342 guarantee(count < _unrealistically_long_length, 343 "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u", 344 name(), count, p2i(curr), p2i(prev0), p2i(prev1), length()); 345 346 if (curr->next() != NULL) { 347 guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up"); 348 } 349 guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted"); 350 last_index = curr->hrm_index(); 351 352 capacity += curr->capacity(); 353 354 prev1 = prev0; 355 prev0 = curr; 356 curr = curr->next(); 357 } 358 359 guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index()); 360 guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next"); 361 guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count); 362 } 363 364 365 FreeRegionList::FreeRegionList(const char* name, HeapRegionSetChecker* checker): 366 HeapRegionSetBase(name, checker), 367 _node_info(G1NUMA::numa()->is_enabled() ? new NodeInfo() : NULL) { 368 369 clear(); 370 } 371 372 FreeRegionList::~FreeRegionList() { 373 if (_node_info != NULL) { 374 delete _node_info; 375 } 376 } 377 378 FreeRegionList::NodeInfo::NodeInfo() : _numa(G1NUMA::numa()), _length_of_node(NULL), 379 _num_nodes(_numa->num_active_nodes()) { 380 assert(UseNUMA, "Invariant"); 381 382 _length_of_node = NEW_C_HEAP_ARRAY(uint, _num_nodes, mtGC); 383 } 384 385 FreeRegionList::NodeInfo::~NodeInfo() { 386 FREE_C_HEAP_ARRAY(uint, _length_of_node); 387 } 388 389 void FreeRegionList::NodeInfo::clear() { 390 for (uint i = 0; i < _num_nodes; ++i) { 391 _length_of_node[i] = 0; 392 } 393 } 394 395 void FreeRegionList::NodeInfo::add(NodeInfo* info) { 396 for (uint i = 0; i < _num_nodes; ++i) { 397 _length_of_node[i] += info->_length_of_node[i]; 398 } 399 } 400