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