1 /* 2 * Copyright (c) 2011, 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/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 #ifndef PRODUCT 33 void HeapRegionSetBase::verify_region(HeapRegion* hr) { 34 assert(hr->containing_set() == this, "Inconsistent containing set for %u", hr->hrm_index()); 35 assert(!hr->is_young(), "Adding young region %u", hr->hrm_index()); // currently we don't use these sets for young regions 36 assert(_checker == NULL || _checker->is_correct_type(hr), "Wrong type of region %u (%s) and set %s", 37 hr->hrm_index(), hr->get_type_str(), name()); 38 assert(!hr->is_free() || hr->is_empty(), "Free region %u is not empty for set %s", hr->hrm_index(), name()); 39 assert(!hr->is_empty() || hr->is_free() || hr->is_archive(), 40 "Empty region %u is not free or archive for set %s", hr->hrm_index(), name()); 41 } 42 #endif 43 44 void HeapRegionSetBase::verify() { 45 // It's important that we also observe the MT safety protocol even 46 // for the verification calls. If we do verification without the 47 // appropriate locks and the set changes underneath our feet 48 // verification might fail and send us on a wild goose chase. 49 check_mt_safety(); 50 51 guarantee_heap_region_set(( is_empty() && length() == 0) || 52 (!is_empty() && length() > 0), 53 "invariant"); 54 } 55 56 void HeapRegionSetBase::verify_start() { 57 // See comment in verify() about MT safety and verification. 58 check_mt_safety(); 59 assert_heap_region_set(!_verify_in_progress, "verification should not be in progress"); 60 61 // Do the basic verification first before we do the checks over the regions. 62 HeapRegionSetBase::verify(); 63 64 _verify_in_progress = true; 65 } 66 67 void HeapRegionSetBase::verify_end() { 68 // See comment in verify() about MT safety and verification. 69 check_mt_safety(); 70 assert_heap_region_set(_verify_in_progress, "verification should be in progress"); 71 72 _verify_in_progress = false; 73 } 74 75 void HeapRegionSetBase::print_on(outputStream* out, bool print_contents) { 76 out->cr(); 77 out->print_cr("Set: %s (" PTR_FORMAT ")", name(), p2i(this)); 78 out->print_cr(" Region Type : %s", _checker->get_description()); 79 out->print_cr(" Length : %14u", length()); 80 } 81 82 HeapRegionSetBase::HeapRegionSetBase(const char* name, HeapRegionSetChecker* checker) 83 : _checker(checker), _length(0), _name(name), _verify_in_progress(false) 84 { 85 } 86 87 void FreeRegionList::set_unrealistically_long_length(uint len) { 88 guarantee(_unrealistically_long_length == 0, "should only be set once"); 89 _unrealistically_long_length = len; 90 } 91 92 void FreeRegionList::remove_all() { 93 check_mt_safety(); 94 verify_optional(); 95 96 HeapRegion* curr = _head; 97 while (curr != NULL) { 98 verify_region(curr); 99 100 HeapRegion* next = curr->next(); 101 curr->set_next(NULL); 102 curr->set_prev(NULL); 103 curr->set_containing_set(NULL); 104 curr = next; 105 } 106 clear(); 107 108 verify_optional(); 109 } 110 111 void FreeRegionList::add_ordered(FreeRegionList* from_list) { 112 check_mt_safety(); 113 from_list->check_mt_safety(); 114 115 verify_optional(); 116 from_list->verify_optional(); 117 118 if (from_list->is_empty()) { 119 return; 120 } 121 122 #ifdef ASSERT 123 FreeRegionListIterator iter(from_list); 124 while (iter.more_available()) { 125 HeapRegion* hr = iter.get_next(); 126 // In set_containing_set() we check that we either set the value 127 // from NULL to non-NULL or vice versa to catch bugs. So, we have 128 // to NULL it first before setting it to the value. 129 hr->set_containing_set(NULL); 130 hr->set_containing_set(this); 131 } 132 #endif // ASSERT 133 134 if (is_empty()) { 135 assert_free_region_list(length() == 0 && _tail == NULL, "invariant"); 136 _head = from_list->_head; 137 _tail = from_list->_tail; 138 } else { 139 HeapRegion* curr_to = _head; 140 HeapRegion* curr_from = from_list->_head; 141 142 while (curr_from != NULL) { 143 while (curr_to != NULL && curr_to->hrm_index() < curr_from->hrm_index()) { 144 curr_to = curr_to->next(); 145 } 146 147 if (curr_to == NULL) { 148 // The rest of the from list should be added as tail 149 _tail->set_next(curr_from); 150 curr_from->set_prev(_tail); 151 curr_from = NULL; 152 } else { 153 HeapRegion* next_from = curr_from->next(); 154 155 curr_from->set_next(curr_to); 156 curr_from->set_prev(curr_to->prev()); 157 if (curr_to->prev() == NULL) { 158 _head = curr_from; 159 } else { 160 curr_to->prev()->set_next(curr_from); 161 } 162 curr_to->set_prev(curr_from); 163 164 curr_from = next_from; 165 } 166 } 167 168 if (_tail->hrm_index() < from_list->_tail->hrm_index()) { 169 _tail = from_list->_tail; 170 } 171 } 172 173 _length += from_list->length(); 174 from_list->clear(); 175 176 verify_optional(); 177 from_list->verify_optional(); 178 } 179 180 void FreeRegionList::remove_starting_at(HeapRegion* first, uint num_regions) { 181 check_mt_safety(); 182 assert_free_region_list(num_regions >= 1, "pre-condition"); 183 assert_free_region_list(!is_empty(), "pre-condition"); 184 185 verify_optional(); 186 DEBUG_ONLY(uint old_length = length();) 187 188 HeapRegion* curr = first; 189 uint count = 0; 190 while (count < num_regions) { 191 verify_region(curr); 192 HeapRegion* next = curr->next(); 193 HeapRegion* prev = curr->prev(); 194 195 assert(count < num_regions, 196 "[%s] should not come across more regions " 197 "pending for removal than num_regions: %u", 198 name(), num_regions); 199 200 if (prev == NULL) { 201 assert_free_region_list(_head == curr, "invariant"); 202 _head = next; 203 } else { 204 assert_free_region_list(_head != curr, "invariant"); 205 prev->set_next(next); 206 } 207 if (next == NULL) { 208 assert_free_region_list(_tail == curr, "invariant"); 209 _tail = prev; 210 } else { 211 assert_free_region_list(_tail != curr, "invariant"); 212 next->set_prev(prev); 213 } 214 if (_last == curr) { 215 _last = NULL; 216 } 217 218 curr->set_next(NULL); 219 curr->set_prev(NULL); 220 remove(curr); 221 222 count++; 223 curr = next; 224 } 225 226 assert(count == num_regions, 227 "[%s] count: %u should be == num_regions: %u", 228 name(), count, num_regions); 229 assert(length() + num_regions == old_length, 230 "[%s] new length should be consistent " 231 "new length: %u old length: %u num_regions: %u", 232 name(), length(), old_length, num_regions); 233 234 verify_optional(); 235 } 236 237 uint FreeRegionList::num_of_regions_in_range(uint start, uint end) const { 238 HeapRegion* cur = _head; 239 uint num = 0; 240 bool started = false; 241 while (cur != NULL && cur->hrm_index() <= end) { 242 if (!started && cur->hrm_index() >= start) { 243 started = true; 244 } 245 if(started) { 246 num++; 247 } 248 cur = cur->next(); 249 } 250 return num; 251 } 252 253 void FreeRegionList::verify() { 254 // See comment in HeapRegionSetBase::verify() about MT safety and 255 // verification. 256 check_mt_safety(); 257 258 // This will also do the basic verification too. 259 verify_start(); 260 261 verify_list(); 262 263 verify_end(); 264 } 265 266 void FreeRegionList::clear() { 267 _length = 0; 268 _head = NULL; 269 _tail = NULL; 270 _last = NULL; 271 } 272 273 void FreeRegionList::verify_list() { 274 HeapRegion* curr = _head; 275 HeapRegion* prev1 = NULL; 276 HeapRegion* prev0 = NULL; 277 uint count = 0; 278 size_t capacity = 0; 279 uint last_index = 0; 280 281 guarantee(_head == NULL || _head->prev() == NULL, "_head should not have a prev"); 282 while (curr != NULL) { 283 verify_region(curr); 284 285 count++; 286 guarantee(count < _unrealistically_long_length, 287 "[%s] the calculated length: %u seems very long, is there maybe a cycle? curr: " PTR_FORMAT " prev0: " PTR_FORMAT " " "prev1: " PTR_FORMAT " length: %u", 288 name(), count, p2i(curr), p2i(prev0), p2i(prev1), length()); 289 290 if (curr->next() != NULL) { 291 guarantee(curr->next()->prev() == curr, "Next or prev pointers messed up"); 292 } 293 guarantee(curr->hrm_index() == 0 || curr->hrm_index() > last_index, "List should be sorted"); 294 last_index = curr->hrm_index(); 295 296 capacity += curr->capacity(); 297 298 prev1 = prev0; 299 prev0 = curr; 300 curr = curr->next(); 301 } 302 303 guarantee(_tail == prev0, "Expected %s to end with %u but it ended with %u.", name(), _tail->hrm_index(), prev0->hrm_index()); 304 guarantee(_tail == NULL || _tail->next() == NULL, "_tail should not have a next"); 305 guarantee(length() == count, "%s count mismatch. Expected %u, actual %u.", name(), length(), count); 306 }