1 /*
2 * Copyright (c) 2005, 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 "classfile/stringTable.hpp"
27 #include "classfile/systemDictionary.hpp"
28 #include "code/codeCache.hpp"
29 #include "gc/parallel/gcTaskManager.hpp"
30 #include "gc/parallel/parallelScavengeHeap.inline.hpp"
31 #include "gc/parallel/pcTasks.hpp"
32 #include "gc/parallel/psAdaptiveSizePolicy.hpp"
33 #include "gc/parallel/psCompactionManager.inline.hpp"
34 #include "gc/parallel/psMarkSweep.hpp"
35 #include "gc/parallel/psMarkSweepDecorator.hpp"
36 #include "gc/parallel/psOldGen.hpp"
37 #include "gc/parallel/psParallelCompact.inline.hpp"
38 #include "gc/parallel/psPromotionManager.inline.hpp"
39 #include "gc/parallel/psScavenge.hpp"
40 #include "gc/parallel/psYoungGen.hpp"
41 #include "gc/shared/gcCause.hpp"
42 #include "gc/shared/gcHeapSummary.hpp"
43 #include "gc/shared/gcId.hpp"
44 #include "gc/shared/gcLocker.inline.hpp"
45 #include "gc/shared/gcTimer.hpp"
46 #include "gc/shared/gcTrace.hpp"
47 #include "gc/shared/gcTraceTime.hpp"
48 #include "gc/shared/isGCActiveMark.hpp"
49 #include "gc/shared/referencePolicy.hpp"
50 #include "gc/shared/referenceProcessor.hpp"
51 #include "gc/shared/spaceDecorator.hpp"
52 #include "logging/log.hpp"
53 #include "oops/instanceKlass.inline.hpp"
54 #include "oops/instanceMirrorKlass.inline.hpp"
55 #include "oops/methodData.hpp"
56 #include "oops/objArrayKlass.inline.hpp"
57 #include "oops/oop.inline.hpp"
58 #include "runtime/atomic.inline.hpp"
59 #include "runtime/fprofiler.hpp"
60 #include "runtime/safepoint.hpp"
61 #include "runtime/vmThread.hpp"
62 #include "services/management.hpp"
63 #include "services/memTracker.hpp"
64 #include "services/memoryService.hpp"
65 #include "utilities/events.hpp"
66 #include "utilities/stack.inline.hpp"
67
68 #include <math.h>
69
70 // All sizes are in HeapWords.
71 const size_t ParallelCompactData::Log2RegionSize = 16; // 64K words
72 const size_t ParallelCompactData::RegionSize = (size_t)1 << Log2RegionSize;
73 const size_t ParallelCompactData::RegionSizeBytes =
74 RegionSize << LogHeapWordSize;
75 const size_t ParallelCompactData::RegionSizeOffsetMask = RegionSize - 1;
76 const size_t ParallelCompactData::RegionAddrOffsetMask = RegionSizeBytes - 1;
77 const size_t ParallelCompactData::RegionAddrMask = ~RegionAddrOffsetMask;
78
79 const size_t ParallelCompactData::Log2BlockSize = 7; // 128 words
80 const size_t ParallelCompactData::BlockSize = (size_t)1 << Log2BlockSize;
81 const size_t ParallelCompactData::BlockSizeBytes =
82 BlockSize << LogHeapWordSize;
83 const size_t ParallelCompactData::BlockSizeOffsetMask = BlockSize - 1;
84 const size_t ParallelCompactData::BlockAddrOffsetMask = BlockSizeBytes - 1;
85 const size_t ParallelCompactData::BlockAddrMask = ~BlockAddrOffsetMask;
86
87 const size_t ParallelCompactData::BlocksPerRegion = RegionSize / BlockSize;
88 const size_t ParallelCompactData::Log2BlocksPerRegion =
89 Log2RegionSize - Log2BlockSize;
90
91 const ParallelCompactData::RegionData::region_sz_t
92 ParallelCompactData::RegionData::dc_shift = 27;
93
94 const ParallelCompactData::RegionData::region_sz_t
95 ParallelCompactData::RegionData::dc_mask = ~0U << dc_shift;
96
97 const ParallelCompactData::RegionData::region_sz_t
98 ParallelCompactData::RegionData::dc_one = 0x1U << dc_shift;
99
100 const ParallelCompactData::RegionData::region_sz_t
101 ParallelCompactData::RegionData::los_mask = ~dc_mask;
102
103 const ParallelCompactData::RegionData::region_sz_t
104 ParallelCompactData::RegionData::dc_claimed = 0x8U << dc_shift;
105
106 const ParallelCompactData::RegionData::region_sz_t
107 ParallelCompactData::RegionData::dc_completed = 0xcU << dc_shift;
108
109 SpaceInfo PSParallelCompact::_space_info[PSParallelCompact::last_space_id];
110
111 ReferenceProcessor* PSParallelCompact::_ref_processor = NULL;
112
113 double PSParallelCompact::_dwl_mean;
114 double PSParallelCompact::_dwl_std_dev;
115 double PSParallelCompact::_dwl_first_term;
116 double PSParallelCompact::_dwl_adjustment;
117 #ifdef ASSERT
118 bool PSParallelCompact::_dwl_initialized = false;
119 #endif // #ifdef ASSERT
120
121 void SplitInfo::record(size_t src_region_idx, size_t partial_obj_size,
122 HeapWord* destination)
123 {
124 assert(src_region_idx != 0, "invalid src_region_idx");
125 assert(partial_obj_size != 0, "invalid partial_obj_size argument");
126 assert(destination != NULL, "invalid destination argument");
127
128 _src_region_idx = src_region_idx;
129 _partial_obj_size = partial_obj_size;
130 _destination = destination;
131
132 // These fields may not be updated below, so make sure they're clear.
133 assert(_dest_region_addr == NULL, "should have been cleared");
134 assert(_first_src_addr == NULL, "should have been cleared");
135
136 // Determine the number of destination regions for the partial object.
137 HeapWord* const last_word = destination + partial_obj_size - 1;
138 const ParallelCompactData& sd = PSParallelCompact::summary_data();
139 HeapWord* const beg_region_addr = sd.region_align_down(destination);
140 HeapWord* const end_region_addr = sd.region_align_down(last_word);
141
142 if (beg_region_addr == end_region_addr) {
143 // One destination region.
144 _destination_count = 1;
145 if (end_region_addr == destination) {
146 // The destination falls on a region boundary, thus the first word of the
147 // partial object will be the first word copied to the destination region.
148 _dest_region_addr = end_region_addr;
149 _first_src_addr = sd.region_to_addr(src_region_idx);
150 }
151 } else {
152 // Two destination regions. When copied, the partial object will cross a
153 // destination region boundary, so a word somewhere within the partial
154 // object will be the first word copied to the second destination region.
155 _destination_count = 2;
156 _dest_region_addr = end_region_addr;
157 const size_t ofs = pointer_delta(end_region_addr, destination);
158 assert(ofs < _partial_obj_size, "sanity");
159 _first_src_addr = sd.region_to_addr(src_region_idx) + ofs;
160 }
161 }
162
163 void SplitInfo::clear()
164 {
165 _src_region_idx = 0;
166 _partial_obj_size = 0;
167 _destination = NULL;
168 _destination_count = 0;
169 _dest_region_addr = NULL;
170 _first_src_addr = NULL;
171 assert(!is_valid(), "sanity");
172 }
173
174 #ifdef ASSERT
175 void SplitInfo::verify_clear()
176 {
177 assert(_src_region_idx == 0, "not clear");
178 assert(_partial_obj_size == 0, "not clear");
179 assert(_destination == NULL, "not clear");
180 assert(_destination_count == 0, "not clear");
181 assert(_dest_region_addr == NULL, "not clear");
182 assert(_first_src_addr == NULL, "not clear");
183 }
184 #endif // #ifdef ASSERT
185
186
187 void PSParallelCompact::print_on_error(outputStream* st) {
188 _mark_bitmap.print_on_error(st);
189 }
190
191 #ifndef PRODUCT
192 const char* PSParallelCompact::space_names[] = {
193 "old ", "eden", "from", "to "
194 };
195
196 void PSParallelCompact::print_region_ranges() {
197 LogHandle(gc, compaction, phases) log;
198 if (!log.is_develop()) {
199 return;
200 }
201 ResourceMark rm;
202 Universe::print_on(log.develop_stream());
203 log.develop("space bottom top end new_top");
204 log.develop("------ ---------- ---------- ---------- ----------");
205
206 for (unsigned int id = 0; id < last_space_id; ++id) {
207 const MutableSpace* space = _space_info[id].space();
208 log.develop("%u %s "
209 SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) " "
210 SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10) " ",
211 id, space_names[id],
212 summary_data().addr_to_region_idx(space->bottom()),
213 summary_data().addr_to_region_idx(space->top()),
214 summary_data().addr_to_region_idx(space->end()),
215 summary_data().addr_to_region_idx(_space_info[id].new_top()));
216 }
217 }
218
219 void
220 print_generic_summary_region(size_t i, const ParallelCompactData::RegionData* c)
221 {
222 #define REGION_IDX_FORMAT SIZE_FORMAT_W(7)
223 #define REGION_DATA_FORMAT SIZE_FORMAT_W(5)
224
225 ParallelCompactData& sd = PSParallelCompact::summary_data();
226 size_t dci = c->destination() ? sd.addr_to_region_idx(c->destination()) : 0;
227 log_develop(gc, compaction, phases)(
228 REGION_IDX_FORMAT " " PTR_FORMAT " "
229 REGION_IDX_FORMAT " " PTR_FORMAT " "
230 REGION_DATA_FORMAT " " REGION_DATA_FORMAT " "
231 REGION_DATA_FORMAT " " REGION_IDX_FORMAT " %d",
232 i, p2i(c->data_location()), dci, p2i(c->destination()),
233 c->partial_obj_size(), c->live_obj_size(),
234 c->data_size(), c->source_region(), c->destination_count());
235
236 #undef REGION_IDX_FORMAT
237 #undef REGION_DATA_FORMAT
238 }
239
240 void
241 print_generic_summary_data(ParallelCompactData& summary_data,
242 HeapWord* const beg_addr,
243 HeapWord* const end_addr)
244 {
245 size_t total_words = 0;
246 size_t i = summary_data.addr_to_region_idx(beg_addr);
247 const size_t last = summary_data.addr_to_region_idx(end_addr);
248 HeapWord* pdest = 0;
249
250 while (i <= last) {
251 ParallelCompactData::RegionData* c = summary_data.region(i);
252 if (c->data_size() != 0 || c->destination() != pdest) {
253 print_generic_summary_region(i, c);
254 total_words += c->data_size();
255 pdest = c->destination();
256 }
257 ++i;
258 }
259
260 log_develop(gc, compaction, phases)("summary_data_bytes=" SIZE_FORMAT, total_words * HeapWordSize);
261 }
262
263 void
264 print_generic_summary_data(ParallelCompactData& summary_data,
265 SpaceInfo* space_info)
266 {
267 if (!log_is_enabled(Develop, gc, compaction, phases)) {
268 return;
269 }
270
271 for (unsigned int id = 0; id < PSParallelCompact::last_space_id; ++id) {
272 const MutableSpace* space = space_info[id].space();
273 print_generic_summary_data(summary_data, space->bottom(),
274 MAX2(space->top(), space_info[id].new_top()));
275 }
276 }
277
278 void
279 print_initial_summary_data(ParallelCompactData& summary_data,
280 const MutableSpace* space) {
281 if (space->top() == space->bottom()) {
282 return;
283 }
284
285 const size_t region_size = ParallelCompactData::RegionSize;
286 typedef ParallelCompactData::RegionData RegionData;
287 HeapWord* const top_aligned_up = summary_data.region_align_up(space->top());
288 const size_t end_region = summary_data.addr_to_region_idx(top_aligned_up);
289 const RegionData* c = summary_data.region(end_region - 1);
290 HeapWord* end_addr = c->destination() + c->data_size();
291 const size_t live_in_space = pointer_delta(end_addr, space->bottom());
292
293 // Print (and count) the full regions at the beginning of the space.
294 size_t full_region_count = 0;
295 size_t i = summary_data.addr_to_region_idx(space->bottom());
296 while (i < end_region && summary_data.region(i)->data_size() == region_size) {
297 ParallelCompactData::RegionData* c = summary_data.region(i);
298 log_develop(gc, compaction, phases)(
299 SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d",
300 i, p2i(c->destination()),
301 c->partial_obj_size(), c->live_obj_size(),
302 c->data_size(), c->source_region(), c->destination_count());
303 ++full_region_count;
304 ++i;
305 }
306
307 size_t live_to_right = live_in_space - full_region_count * region_size;
308
309 double max_reclaimed_ratio = 0.0;
310 size_t max_reclaimed_ratio_region = 0;
311 size_t max_dead_to_right = 0;
312 size_t max_live_to_right = 0;
313
314 // Print the 'reclaimed ratio' for regions while there is something live in
315 // the region or to the right of it. The remaining regions are empty (and
316 // uninteresting), and computing the ratio will result in division by 0.
317 while (i < end_region && live_to_right > 0) {
318 c = summary_data.region(i);
319 HeapWord* const region_addr = summary_data.region_to_addr(i);
320 const size_t used_to_right = pointer_delta(space->top(), region_addr);
321 const size_t dead_to_right = used_to_right - live_to_right;
322 const double reclaimed_ratio = double(dead_to_right) / live_to_right;
323
324 if (reclaimed_ratio > max_reclaimed_ratio) {
325 max_reclaimed_ratio = reclaimed_ratio;
326 max_reclaimed_ratio_region = i;
327 max_dead_to_right = dead_to_right;
328 max_live_to_right = live_to_right;
329 }
330
331 ParallelCompactData::RegionData* c = summary_data.region(i);
332 log_develop(gc, compaction, phases)(
333 SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d"
334 "%12.10f " SIZE_FORMAT_W(10) " " SIZE_FORMAT_W(10),
335 i, p2i(c->destination()),
336 c->partial_obj_size(), c->live_obj_size(),
337 c->data_size(), c->source_region(), c->destination_count(),
338 reclaimed_ratio, dead_to_right, live_to_right);
339
340
341 live_to_right -= c->data_size();
342 ++i;
343 }
344
345 // Any remaining regions are empty. Print one more if there is one.
346 if (i < end_region) {
347 ParallelCompactData::RegionData* c = summary_data.region(i);
348 log_develop(gc, compaction, phases)(
349 SIZE_FORMAT_W(5) " " PTR_FORMAT " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " " SIZE_FORMAT_W(5) " %d",
350 i, p2i(c->destination()),
351 c->partial_obj_size(), c->live_obj_size(),
352 c->data_size(), c->source_region(), c->destination_count());
353 }
354
355 log_develop(gc, compaction, phases)("max: " SIZE_FORMAT_W(4) " d2r=" SIZE_FORMAT_W(10) " l2r=" SIZE_FORMAT_W(10) " max_ratio=%14.12f",
356 max_reclaimed_ratio_region, max_dead_to_right, max_live_to_right, max_reclaimed_ratio);
357 }
358
359 void
360 print_initial_summary_data(ParallelCompactData& summary_data,
361 SpaceInfo* space_info) {
362 if (!log_is_enabled(Develop, gc, compaction, phases)) {
363 return;
364 }
365
366 unsigned int id = PSParallelCompact::old_space_id;
367 const MutableSpace* space;
368 do {
369 space = space_info[id].space();
370 print_initial_summary_data(summary_data, space);
371 } while (++id < PSParallelCompact::eden_space_id);
372
373 do {
374 space = space_info[id].space();
375 print_generic_summary_data(summary_data, space->bottom(), space->top());
376 } while (++id < PSParallelCompact::last_space_id);
377 }
378 #endif // #ifndef PRODUCT
379
380 #ifdef ASSERT
381 size_t add_obj_count;
382 size_t add_obj_size;
383 size_t mark_bitmap_count;
384 size_t mark_bitmap_size;
385 #endif // #ifdef ASSERT
386
387 ParallelCompactData::ParallelCompactData()
388 {
389 _region_start = 0;
390
391 _region_vspace = 0;
392 _reserved_byte_size = 0;
393 _region_data = 0;
394 _region_count = 0;
395
396 _block_vspace = 0;
397 _block_data = 0;
398 _block_count = 0;
399 }
400
401 bool ParallelCompactData::initialize(MemRegion covered_region)
402 {
403 _region_start = covered_region.start();
404 const size_t region_size = covered_region.word_size();
405 DEBUG_ONLY(_region_end = _region_start + region_size;)
406
407 assert(region_align_down(_region_start) == _region_start,
408 "region start not aligned");
409 assert((region_size & RegionSizeOffsetMask) == 0,
410 "region size not a multiple of RegionSize");
411
412 bool result = initialize_region_data(region_size) && initialize_block_data();
413 return result;
414 }
415
416 PSVirtualSpace*
417 ParallelCompactData::create_vspace(size_t count, size_t element_size)
418 {
419 const size_t raw_bytes = count * element_size;
420 const size_t page_sz = os::page_size_for_region_aligned(raw_bytes, 10);
421 const size_t granularity = os::vm_allocation_granularity();
422 _reserved_byte_size = align_size_up(raw_bytes, MAX2(page_sz, granularity));
423
424 const size_t rs_align = page_sz == (size_t) os::vm_page_size() ? 0 :
425 MAX2(page_sz, granularity);
426 ReservedSpace rs(_reserved_byte_size, rs_align, rs_align > 0);
427 os::trace_page_sizes("par compact", raw_bytes, raw_bytes, page_sz, rs.base(),
428 rs.size());
429
430 MemTracker::record_virtual_memory_type((address)rs.base(), mtGC);
431
432 PSVirtualSpace* vspace = new PSVirtualSpace(rs, page_sz);
433 if (vspace != 0) {
434 if (vspace->expand_by(_reserved_byte_size)) {
435 return vspace;
436 }
437 delete vspace;
438 // Release memory reserved in the space.
439 rs.release();
440 }
441
442 return 0;
443 }
444
445 bool ParallelCompactData::initialize_region_data(size_t region_size)
446 {
447 const size_t count = (region_size + RegionSizeOffsetMask) >> Log2RegionSize;
448 _region_vspace = create_vspace(count, sizeof(RegionData));
449 if (_region_vspace != 0) {
450 _region_data = (RegionData*)_region_vspace->reserved_low_addr();
451 _region_count = count;
452 return true;
453 }
454 return false;
455 }
456
457 bool ParallelCompactData::initialize_block_data()
458 {
459 assert(_region_count != 0, "region data must be initialized first");
460 const size_t count = _region_count << Log2BlocksPerRegion;
461 _block_vspace = create_vspace(count, sizeof(BlockData));
462 if (_block_vspace != 0) {
463 _block_data = (BlockData*)_block_vspace->reserved_low_addr();
464 _block_count = count;
465 return true;
466 }
467 return false;
468 }
469
470 void ParallelCompactData::clear()
471 {
472 memset(_region_data, 0, _region_vspace->committed_size());
473 memset(_block_data, 0, _block_vspace->committed_size());
474 }
475
476 void ParallelCompactData::clear_range(size_t beg_region, size_t end_region) {
477 assert(beg_region <= _region_count, "beg_region out of range");
478 assert(end_region <= _region_count, "end_region out of range");
479 assert(RegionSize % BlockSize == 0, "RegionSize not a multiple of BlockSize");
480
481 const size_t region_cnt = end_region - beg_region;
482 memset(_region_data + beg_region, 0, region_cnt * sizeof(RegionData));
483
484 const size_t beg_block = beg_region * BlocksPerRegion;
485 const size_t block_cnt = region_cnt * BlocksPerRegion;
486 memset(_block_data + beg_block, 0, block_cnt * sizeof(BlockData));
487 }
488
489 HeapWord* ParallelCompactData::partial_obj_end(size_t region_idx) const
490 {
491 const RegionData* cur_cp = region(region_idx);
492 const RegionData* const end_cp = region(region_count() - 1);
493
494 HeapWord* result = region_to_addr(region_idx);
495 if (cur_cp < end_cp) {
496 do {
497 result += cur_cp->partial_obj_size();
498 } while (cur_cp->partial_obj_size() == RegionSize && ++cur_cp < end_cp);
499 }
500 return result;
501 }
502
503 void ParallelCompactData::add_obj(HeapWord* addr, size_t len)
504 {
505 const size_t obj_ofs = pointer_delta(addr, _region_start);
506 const size_t beg_region = obj_ofs >> Log2RegionSize;
507 const size_t end_region = (obj_ofs + len - 1) >> Log2RegionSize;
508
509 DEBUG_ONLY(Atomic::inc_ptr(&add_obj_count);)
510 DEBUG_ONLY(Atomic::add_ptr(len, &add_obj_size);)
511
512 if (beg_region == end_region) {
513 // All in one region.
514 _region_data[beg_region].add_live_obj(len);
515 return;
516 }
517
518 // First region.
519 const size_t beg_ofs = region_offset(addr);
520 _region_data[beg_region].add_live_obj(RegionSize - beg_ofs);
521
522 Klass* klass = ((oop)addr)->klass();
523 // Middle regions--completely spanned by this object.
524 for (size_t region = beg_region + 1; region < end_region; ++region) {
525 _region_data[region].set_partial_obj_size(RegionSize);
526 _region_data[region].set_partial_obj_addr(addr);
527 }
528
529 // Last region.
530 const size_t end_ofs = region_offset(addr + len - 1);
531 _region_data[end_region].set_partial_obj_size(end_ofs + 1);
532 _region_data[end_region].set_partial_obj_addr(addr);
533 }
534
535 void
536 ParallelCompactData::summarize_dense_prefix(HeapWord* beg, HeapWord* end)
537 {
538 assert(region_offset(beg) == 0, "not RegionSize aligned");
539 assert(region_offset(end) == 0, "not RegionSize aligned");
540
541 size_t cur_region = addr_to_region_idx(beg);
542 const size_t end_region = addr_to_region_idx(end);
543 HeapWord* addr = beg;
544 while (cur_region < end_region) {
545 _region_data[cur_region].set_destination(addr);
546 _region_data[cur_region].set_destination_count(0);
547 _region_data[cur_region].set_source_region(cur_region);
548 _region_data[cur_region].set_data_location(addr);
549
550 // Update live_obj_size so the region appears completely full.
551 size_t live_size = RegionSize - _region_data[cur_region].partial_obj_size();
552 _region_data[cur_region].set_live_obj_size(live_size);
553
554 ++cur_region;
555 addr += RegionSize;
556 }
557 }
558
559 // Find the point at which a space can be split and, if necessary, record the
560 // split point.
561 //
562 // If the current src region (which overflowed the destination space) doesn't
563 // have a partial object, the split point is at the beginning of the current src
564 // region (an "easy" split, no extra bookkeeping required).
565 //
566 // If the current src region has a partial object, the split point is in the
567 // region where that partial object starts (call it the split_region). If
568 // split_region has a partial object, then the split point is just after that
569 // partial object (a "hard" split where we have to record the split data and
570 // zero the partial_obj_size field). With a "hard" split, we know that the
571 // partial_obj ends within split_region because the partial object that caused
572 // the overflow starts in split_region. If split_region doesn't have a partial
573 // obj, then the split is at the beginning of split_region (another "easy"
574 // split).
575 HeapWord*
576 ParallelCompactData::summarize_split_space(size_t src_region,
577 SplitInfo& split_info,
578 HeapWord* destination,
579 HeapWord* target_end,
580 HeapWord** target_next)
581 {
582 assert(destination <= target_end, "sanity");
583 assert(destination + _region_data[src_region].data_size() > target_end,
584 "region should not fit into target space");
585 assert(is_region_aligned(target_end), "sanity");
586
587 size_t split_region = src_region;
588 HeapWord* split_destination = destination;
589 size_t partial_obj_size = _region_data[src_region].partial_obj_size();
590
591 if (destination + partial_obj_size > target_end) {
592 // The split point is just after the partial object (if any) in the
593 // src_region that contains the start of the object that overflowed the
594 // destination space.
595 //
596 // Find the start of the "overflow" object and set split_region to the
597 // region containing it.
598 HeapWord* const overflow_obj = _region_data[src_region].partial_obj_addr();
599 split_region = addr_to_region_idx(overflow_obj);
600
601 // Clear the source_region field of all destination regions whose first word
602 // came from data after the split point (a non-null source_region field
603 // implies a region must be filled).
604 //
605 // An alternative to the simple loop below: clear during post_compact(),
606 // which uses memcpy instead of individual stores, and is easy to
607 // parallelize. (The downside is that it clears the entire RegionData
608 // object as opposed to just one field.)
609 //
610 // post_compact() would have to clear the summary data up to the highest
611 // address that was written during the summary phase, which would be
612 //
613 // max(top, max(new_top, clear_top))
614 //
615 // where clear_top is a new field in SpaceInfo. Would have to set clear_top
616 // to target_end.
617 const RegionData* const sr = region(split_region);
618 const size_t beg_idx =
619 addr_to_region_idx(region_align_up(sr->destination() +
620 sr->partial_obj_size()));
621 const size_t end_idx = addr_to_region_idx(target_end);
622
623 log_develop(gc, compaction, phases)("split: clearing source_region field in [" SIZE_FORMAT ", " SIZE_FORMAT ")", beg_idx, end_idx);
624 for (size_t idx = beg_idx; idx < end_idx; ++idx) {
625 _region_data[idx].set_source_region(0);
626 }
627
628 // Set split_destination and partial_obj_size to reflect the split region.
629 split_destination = sr->destination();
630 partial_obj_size = sr->partial_obj_size();
631 }
632
633 // The split is recorded only if a partial object extends onto the region.
634 if (partial_obj_size != 0) {
635 _region_data[split_region].set_partial_obj_size(0);
636 split_info.record(split_region, partial_obj_size, split_destination);
637 }
638
639 // Setup the continuation addresses.
640 *target_next = split_destination + partial_obj_size;
641 HeapWord* const source_next = region_to_addr(split_region) + partial_obj_size;
642
643 if (log_is_enabled(Develop, gc, compaction, phases)) {
644 const char * split_type = partial_obj_size == 0 ? "easy" : "hard";
645 log_develop(gc, compaction, phases)("%s split: src=" PTR_FORMAT " src_c=" SIZE_FORMAT " pos=" SIZE_FORMAT,
646 split_type, p2i(source_next), split_region, partial_obj_size);
647 log_develop(gc, compaction, phases)("%s split: dst=" PTR_FORMAT " dst_c=" SIZE_FORMAT " tn=" PTR_FORMAT,
648 split_type, p2i(split_destination),
649 addr_to_region_idx(split_destination),
650 p2i(*target_next));
651
652 if (partial_obj_size != 0) {
653 HeapWord* const po_beg = split_info.destination();
654 HeapWord* const po_end = po_beg + split_info.partial_obj_size();
655 log_develop(gc, compaction, phases)("%s split: po_beg=" PTR_FORMAT " " SIZE_FORMAT " po_end=" PTR_FORMAT " " SIZE_FORMAT,
656 split_type,
657 p2i(po_beg), addr_to_region_idx(po_beg),
658 p2i(po_end), addr_to_region_idx(po_end));
659 }
660 }
661
662 return source_next;
663 }
664
665 bool ParallelCompactData::summarize(SplitInfo& split_info,
666 HeapWord* source_beg, HeapWord* source_end,
667 HeapWord** source_next,
668 HeapWord* target_beg, HeapWord* target_end,
669 HeapWord** target_next)
670 {
671 HeapWord* const source_next_val = source_next == NULL ? NULL : *source_next;
672 log_develop(gc, compaction, phases)(
673 "sb=" PTR_FORMAT " se=" PTR_FORMAT " sn=" PTR_FORMAT
674 "tb=" PTR_FORMAT " te=" PTR_FORMAT " tn=" PTR_FORMAT,
675 p2i(source_beg), p2i(source_end), p2i(source_next_val),
676 p2i(target_beg), p2i(target_end), p2i(*target_next));
677
678 size_t cur_region = addr_to_region_idx(source_beg);
679 const size_t end_region = addr_to_region_idx(region_align_up(source_end));
680
681 HeapWord *dest_addr = target_beg;
682 while (cur_region < end_region) {
683 // The destination must be set even if the region has no data.
684 _region_data[cur_region].set_destination(dest_addr);
685
686 size_t words = _region_data[cur_region].data_size();
687 if (words > 0) {
688 // If cur_region does not fit entirely into the target space, find a point
689 // at which the source space can be 'split' so that part is copied to the
690 // target space and the rest is copied elsewhere.
691 if (dest_addr + words > target_end) {
692 assert(source_next != NULL, "source_next is NULL when splitting");
693 *source_next = summarize_split_space(cur_region, split_info, dest_addr,
694 target_end, target_next);
695 return false;
696 }
697
698 // Compute the destination_count for cur_region, and if necessary, update
699 // source_region for a destination region. The source_region field is
700 // updated if cur_region is the first (left-most) region to be copied to a
701 // destination region.
702 //
703 // The destination_count calculation is a bit subtle. A region that has
704 // data that compacts into itself does not count itself as a destination.
705 // This maintains the invariant that a zero count means the region is
706 // available and can be claimed and then filled.
707 uint destination_count = 0;
708 if (split_info.is_split(cur_region)) {
709 // The current region has been split: the partial object will be copied
710 // to one destination space and the remaining data will be copied to
711 // another destination space. Adjust the initial destination_count and,
712 // if necessary, set the source_region field if the partial object will
713 // cross a destination region boundary.
714 destination_count = split_info.destination_count();
715 if (destination_count == 2) {
716 size_t dest_idx = addr_to_region_idx(split_info.dest_region_addr());
717 _region_data[dest_idx].set_source_region(cur_region);
718 }
719 }
720
721 HeapWord* const last_addr = dest_addr + words - 1;
722 const size_t dest_region_1 = addr_to_region_idx(dest_addr);
723 const size_t dest_region_2 = addr_to_region_idx(last_addr);
724
725 // Initially assume that the destination regions will be the same and
726 // adjust the value below if necessary. Under this assumption, if
727 // cur_region == dest_region_2, then cur_region will be compacted
728 // completely into itself.
729 destination_count += cur_region == dest_region_2 ? 0 : 1;
730 if (dest_region_1 != dest_region_2) {
731 // Destination regions differ; adjust destination_count.
732 destination_count += 1;
733 // Data from cur_region will be copied to the start of dest_region_2.
734 _region_data[dest_region_2].set_source_region(cur_region);
735 } else if (region_offset(dest_addr) == 0) {
736 // Data from cur_region will be copied to the start of the destination
737 // region.
738 _region_data[dest_region_1].set_source_region(cur_region);
739 }
740
741 _region_data[cur_region].set_destination_count(destination_count);
742 _region_data[cur_region].set_data_location(region_to_addr(cur_region));
743 dest_addr += words;
744 }
745
746 ++cur_region;
747 }
748
749 *target_next = dest_addr;
750 return true;
751 }
752
753 HeapWord* ParallelCompactData::calc_new_pointer(HeapWord* addr) {
754 assert(addr != NULL, "Should detect NULL oop earlier");
755 assert(ParallelScavengeHeap::heap()->is_in(addr), "not in heap");
756 assert(PSParallelCompact::mark_bitmap()->is_marked(addr), "not marked");
757
758 // Region covering the object.
759 RegionData* const region_ptr = addr_to_region_ptr(addr);
760 HeapWord* result = region_ptr->destination();
761
762 // If the entire Region is live, the new location is region->destination + the
763 // offset of the object within in the Region.
764
765 // Run some performance tests to determine if this special case pays off. It
766 // is worth it for pointers into the dense prefix. If the optimization to
767 // avoid pointer updates in regions that only point to the dense prefix is
768 // ever implemented, this should be revisited.
769 if (region_ptr->data_size() == RegionSize) {
770 result += region_offset(addr);
771 return result;
772 }
773
774 // Otherwise, the new location is region->destination + block offset + the
775 // number of live words in the Block that are (a) to the left of addr and (b)
776 // due to objects that start in the Block.
777
778 // Fill in the block table if necessary. This is unsynchronized, so multiple
779 // threads may fill the block table for a region (harmless, since it is
780 // idempotent).
781 if (!region_ptr->blocks_filled()) {
782 PSParallelCompact::fill_blocks(addr_to_region_idx(addr));
783 region_ptr->set_blocks_filled();
784 }
785
786 HeapWord* const search_start = block_align_down(addr);
787 const size_t block_offset = addr_to_block_ptr(addr)->offset();
788
789 const ParMarkBitMap* bitmap = PSParallelCompact::mark_bitmap();
790 const size_t live = bitmap->live_words_in_range(search_start, oop(addr));
791 result += block_offset + live;
792 DEBUG_ONLY(PSParallelCompact::check_new_location(addr, result));
793 return result;
794 }
795
796 #ifdef ASSERT
797 void ParallelCompactData::verify_clear(const PSVirtualSpace* vspace)
798 {
799 const size_t* const beg = (const size_t*)vspace->committed_low_addr();
800 const size_t* const end = (const size_t*)vspace->committed_high_addr();
801 for (const size_t* p = beg; p < end; ++p) {
802 assert(*p == 0, "not zero");
803 }
804 }
805
806 void ParallelCompactData::verify_clear()
807 {
808 verify_clear(_region_vspace);
809 verify_clear(_block_vspace);
810 }
811 #endif // #ifdef ASSERT
812
813 STWGCTimer PSParallelCompact::_gc_timer;
814 ParallelOldTracer PSParallelCompact::_gc_tracer;
815 elapsedTimer PSParallelCompact::_accumulated_time;
816 unsigned int PSParallelCompact::_total_invocations = 0;
817 unsigned int PSParallelCompact::_maximum_compaction_gc_num = 0;
818 jlong PSParallelCompact::_time_of_last_gc = 0;
819 CollectorCounters* PSParallelCompact::_counters = NULL;
820 ParMarkBitMap PSParallelCompact::_mark_bitmap;
821 ParallelCompactData PSParallelCompact::_summary_data;
822
823 PSParallelCompact::IsAliveClosure PSParallelCompact::_is_alive_closure;
824
825 bool PSParallelCompact::IsAliveClosure::do_object_b(oop p) { return mark_bitmap()->is_marked(p); }
826
827 PSParallelCompact::AdjustPointerClosure PSParallelCompact::_adjust_pointer_closure;
828 PSParallelCompact::AdjustKlassClosure PSParallelCompact::_adjust_klass_closure;
829
830 void PSParallelCompact::AdjustKlassClosure::do_klass(Klass* klass) {
831 klass->oops_do(&PSParallelCompact::_adjust_pointer_closure);
832 }
833
834 void PSParallelCompact::post_initialize() {
835 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
836 MemRegion mr = heap->reserved_region();
837 _ref_processor =
838 new ReferenceProcessor(mr, // span
839 ParallelRefProcEnabled && (ParallelGCThreads > 1), // mt processing
840 ParallelGCThreads, // mt processing degree
841 true, // mt discovery
842 ParallelGCThreads, // mt discovery degree
843 true, // atomic_discovery
844 &_is_alive_closure); // non-header is alive closure
845 _counters = new CollectorCounters("PSParallelCompact", 1);
846
847 // Initialize static fields in ParCompactionManager.
848 ParCompactionManager::initialize(mark_bitmap());
849 }
850
851 bool PSParallelCompact::initialize() {
852 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
853 MemRegion mr = heap->reserved_region();
854
855 // Was the old gen get allocated successfully?
856 if (!heap->old_gen()->is_allocated()) {
857 return false;
858 }
859
860 initialize_space_info();
861 initialize_dead_wood_limiter();
862
863 if (!_mark_bitmap.initialize(mr)) {
864 vm_shutdown_during_initialization(
865 err_msg("Unable to allocate " SIZE_FORMAT "KB bitmaps for parallel "
866 "garbage collection for the requested " SIZE_FORMAT "KB heap.",
867 _mark_bitmap.reserved_byte_size()/K, mr.byte_size()/K));
868 return false;
869 }
870
871 if (!_summary_data.initialize(mr)) {
872 vm_shutdown_during_initialization(
873 err_msg("Unable to allocate " SIZE_FORMAT "KB card tables for parallel "
874 "garbage collection for the requested " SIZE_FORMAT "KB heap.",
875 _summary_data.reserved_byte_size()/K, mr.byte_size()/K));
876 return false;
877 }
878
879 return true;
880 }
881
882 void PSParallelCompact::initialize_space_info()
883 {
884 memset(&_space_info, 0, sizeof(_space_info));
885
886 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
887 PSYoungGen* young_gen = heap->young_gen();
888
889 _space_info[old_space_id].set_space(heap->old_gen()->object_space());
890 _space_info[eden_space_id].set_space(young_gen->eden_space());
891 _space_info[from_space_id].set_space(young_gen->from_space());
892 _space_info[to_space_id].set_space(young_gen->to_space());
893
894 _space_info[old_space_id].set_start_array(heap->old_gen()->start_array());
895 }
896
897 void PSParallelCompact::initialize_dead_wood_limiter()
898 {
899 const size_t max = 100;
900 _dwl_mean = double(MIN2(ParallelOldDeadWoodLimiterMean, max)) / 100.0;
901 _dwl_std_dev = double(MIN2(ParallelOldDeadWoodLimiterStdDev, max)) / 100.0;
902 _dwl_first_term = 1.0 / (sqrt(2.0 * M_PI) * _dwl_std_dev);
903 DEBUG_ONLY(_dwl_initialized = true;)
904 _dwl_adjustment = normal_distribution(1.0);
905 }
906
907 void
908 PSParallelCompact::clear_data_covering_space(SpaceId id)
909 {
910 // At this point, top is the value before GC, new_top() is the value that will
911 // be set at the end of GC. The marking bitmap is cleared to top; nothing
912 // should be marked above top. The summary data is cleared to the larger of
913 // top & new_top.
914 MutableSpace* const space = _space_info[id].space();
915 HeapWord* const bot = space->bottom();
916 HeapWord* const top = space->top();
917 HeapWord* const max_top = MAX2(top, _space_info[id].new_top());
918
919 const idx_t beg_bit = _mark_bitmap.addr_to_bit(bot);
920 const idx_t end_bit = BitMap::word_align_up(_mark_bitmap.addr_to_bit(top));
921 _mark_bitmap.clear_range(beg_bit, end_bit);
922
923 const size_t beg_region = _summary_data.addr_to_region_idx(bot);
924 const size_t end_region =
925 _summary_data.addr_to_region_idx(_summary_data.region_align_up(max_top));
926 _summary_data.clear_range(beg_region, end_region);
927
928 // Clear the data used to 'split' regions.
929 SplitInfo& split_info = _space_info[id].split_info();
930 if (split_info.is_valid()) {
931 split_info.clear();
932 }
933 DEBUG_ONLY(split_info.verify_clear();)
934 }
935
936 void PSParallelCompact::pre_compact()
937 {
938 // Update the from & to space pointers in space_info, since they are swapped
939 // at each young gen gc. Do the update unconditionally (even though a
940 // promotion failure does not swap spaces) because an unknown number of young
941 // collections will have swapped the spaces an unknown number of times.
942 GCTraceTime(Trace, gc, phases) tm("pre compact", &_gc_timer);
943 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
944 _space_info[from_space_id].set_space(heap->young_gen()->from_space());
945 _space_info[to_space_id].set_space(heap->young_gen()->to_space());
946
947 DEBUG_ONLY(add_obj_count = add_obj_size = 0;)
948 DEBUG_ONLY(mark_bitmap_count = mark_bitmap_size = 0;)
949
950 // Increment the invocation count
951 heap->increment_total_collections(true);
952
953 // We need to track unique mark sweep invocations as well.
954 _total_invocations++;
955
956 heap->print_heap_before_gc();
957 heap->trace_heap_before_gc(&_gc_tracer);
958
959 // Fill in TLABs
960 heap->accumulate_statistics_all_tlabs();
961 heap->ensure_parsability(true); // retire TLABs
962
963 if (VerifyBeforeGC && heap->total_collections() >= VerifyGCStartAt) {
964 HandleMark hm; // Discard invalid handles created during verification
965 Universe::verify("Before GC");
966 }
967
968 // Verify object start arrays
969 if (VerifyObjectStartArray &&
970 VerifyBeforeGC) {
971 heap->old_gen()->verify_object_start_array();
972 }
973
974 DEBUG_ONLY(mark_bitmap()->verify_clear();)
975 DEBUG_ONLY(summary_data().verify_clear();)
976
977 // Have worker threads release resources the next time they run a task.
978 gc_task_manager()->release_all_resources();
979 }
980
981 void PSParallelCompact::post_compact()
982 {
983 GCTraceTime(Trace, gc, phases) tm("post compact", &_gc_timer);
984
985 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
986 // Clear the marking bitmap, summary data and split info.
987 clear_data_covering_space(SpaceId(id));
988 // Update top(). Must be done after clearing the bitmap and summary data.
989 _space_info[id].publish_new_top();
990 }
991
992 MutableSpace* const eden_space = _space_info[eden_space_id].space();
993 MutableSpace* const from_space = _space_info[from_space_id].space();
994 MutableSpace* const to_space = _space_info[to_space_id].space();
995
996 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
997 bool eden_empty = eden_space->is_empty();
998 if (!eden_empty) {
999 eden_empty = absorb_live_data_from_eden(heap->size_policy(),
1000 heap->young_gen(), heap->old_gen());
1001 }
1002
1003 // Update heap occupancy information which is used as input to the soft ref
1004 // clearing policy at the next gc.
1005 Universe::update_heap_info_at_gc();
1006
1007 bool young_gen_empty = eden_empty && from_space->is_empty() &&
1008 to_space->is_empty();
1009
1010 ModRefBarrierSet* modBS = barrier_set_cast<ModRefBarrierSet>(heap->barrier_set());
1011 MemRegion old_mr = heap->old_gen()->reserved();
1012 if (young_gen_empty) {
1013 modBS->clear(MemRegion(old_mr.start(), old_mr.end()));
1014 } else {
1015 modBS->invalidate(MemRegion(old_mr.start(), old_mr.end()));
1016 }
1017
1018 // Delete metaspaces for unloaded class loaders and clean up loader_data graph
1019 ClassLoaderDataGraph::purge();
1020 MetaspaceAux::verify_metrics();
1021
1022 CodeCache::gc_epilogue();
1023 JvmtiExport::gc_epilogue();
1024
1025 #if defined(COMPILER2) || INCLUDE_JVMCI
1026 DerivedPointerTable::update_pointers();
1027 #endif
1028
1029 ref_processor()->enqueue_discovered_references(NULL);
1030
1031 if (ZapUnusedHeapArea) {
1032 heap->gen_mangle_unused_area();
1033 }
1034
1035 // Update time of last GC
1036 reset_millis_since_last_gc();
1037 }
1038
1039 HeapWord*
1040 PSParallelCompact::compute_dense_prefix_via_density(const SpaceId id,
1041 bool maximum_compaction)
1042 {
1043 const size_t region_size = ParallelCompactData::RegionSize;
1044 const ParallelCompactData& sd = summary_data();
1045
1046 const MutableSpace* const space = _space_info[id].space();
1047 HeapWord* const top_aligned_up = sd.region_align_up(space->top());
1048 const RegionData* const beg_cp = sd.addr_to_region_ptr(space->bottom());
1049 const RegionData* const end_cp = sd.addr_to_region_ptr(top_aligned_up);
1050
1051 // Skip full regions at the beginning of the space--they are necessarily part
1052 // of the dense prefix.
1053 size_t full_count = 0;
1054 const RegionData* cp;
1055 for (cp = beg_cp; cp < end_cp && cp->data_size() == region_size; ++cp) {
1056 ++full_count;
1057 }
1058
1059 assert(total_invocations() >= _maximum_compaction_gc_num, "sanity");
1060 const size_t gcs_since_max = total_invocations() - _maximum_compaction_gc_num;
1061 const bool interval_ended = gcs_since_max > HeapMaximumCompactionInterval;
1062 if (maximum_compaction || cp == end_cp || interval_ended) {
1063 _maximum_compaction_gc_num = total_invocations();
1064 return sd.region_to_addr(cp);
1065 }
1066
1067 HeapWord* const new_top = _space_info[id].new_top();
1068 const size_t space_live = pointer_delta(new_top, space->bottom());
1069 const size_t space_used = space->used_in_words();
1070 const size_t space_capacity = space->capacity_in_words();
1071
1072 const double cur_density = double(space_live) / space_capacity;
1073 const double deadwood_density =
1074 (1.0 - cur_density) * (1.0 - cur_density) * cur_density * cur_density;
1075 const size_t deadwood_goal = size_t(space_capacity * deadwood_density);
1076
1077 if (TraceParallelOldGCDensePrefix) {
1078 tty->print_cr("cur_dens=%5.3f dw_dens=%5.3f dw_goal=" SIZE_FORMAT,
1079 cur_density, deadwood_density, deadwood_goal);
1080 tty->print_cr("space_live=" SIZE_FORMAT " " "space_used=" SIZE_FORMAT " "
1081 "space_cap=" SIZE_FORMAT,
1082 space_live, space_used,
1083 space_capacity);
1084 }
1085
1086 // XXX - Use binary search?
1087 HeapWord* dense_prefix = sd.region_to_addr(cp);
1088 const RegionData* full_cp = cp;
1089 const RegionData* const top_cp = sd.addr_to_region_ptr(space->top() - 1);
1090 while (cp < end_cp) {
1091 HeapWord* region_destination = cp->destination();
1092 const size_t cur_deadwood = pointer_delta(dense_prefix, region_destination);
1093 if (TraceParallelOldGCDensePrefix && Verbose) {
1094 tty->print_cr("c#=" SIZE_FORMAT_W(4) " dst=" PTR_FORMAT " "
1095 "dp=" PTR_FORMAT " " "cdw=" SIZE_FORMAT_W(8),
1096 sd.region(cp), p2i(region_destination),
1097 p2i(dense_prefix), cur_deadwood);
1098 }
1099
1100 if (cur_deadwood >= deadwood_goal) {
1101 // Found the region that has the correct amount of deadwood to the left.
1102 // This typically occurs after crossing a fairly sparse set of regions, so
1103 // iterate backwards over those sparse regions, looking for the region
1104 // that has the lowest density of live objects 'to the right.'
1105 size_t space_to_left = sd.region(cp) * region_size;
1106 size_t live_to_left = space_to_left - cur_deadwood;
1107 size_t space_to_right = space_capacity - space_to_left;
1108 size_t live_to_right = space_live - live_to_left;
1109 double density_to_right = double(live_to_right) / space_to_right;
1110 while (cp > full_cp) {
1111 --cp;
1112 const size_t prev_region_live_to_right = live_to_right -
1113 cp->data_size();
1114 const size_t prev_region_space_to_right = space_to_right + region_size;
1115 double prev_region_density_to_right =
1116 double(prev_region_live_to_right) / prev_region_space_to_right;
1117 if (density_to_right <= prev_region_density_to_right) {
1118 return dense_prefix;
1119 }
1120 if (TraceParallelOldGCDensePrefix && Verbose) {
1121 tty->print_cr("backing up from c=" SIZE_FORMAT_W(4) " d2r=%10.8f "
1122 "pc_d2r=%10.8f", sd.region(cp), density_to_right,
1123 prev_region_density_to_right);
1124 }
1125 dense_prefix -= region_size;
1126 live_to_right = prev_region_live_to_right;
1127 space_to_right = prev_region_space_to_right;
1128 density_to_right = prev_region_density_to_right;
1129 }
1130 return dense_prefix;
1131 }
1132
1133 dense_prefix += region_size;
1134 ++cp;
1135 }
1136
1137 return dense_prefix;
1138 }
1139
1140 #ifndef PRODUCT
1141 void PSParallelCompact::print_dense_prefix_stats(const char* const algorithm,
1142 const SpaceId id,
1143 const bool maximum_compaction,
1144 HeapWord* const addr)
1145 {
1146 const size_t region_idx = summary_data().addr_to_region_idx(addr);
1147 RegionData* const cp = summary_data().region(region_idx);
1148 const MutableSpace* const space = _space_info[id].space();
1149 HeapWord* const new_top = _space_info[id].new_top();
1150
1151 const size_t space_live = pointer_delta(new_top, space->bottom());
1152 const size_t dead_to_left = pointer_delta(addr, cp->destination());
1153 const size_t space_cap = space->capacity_in_words();
1154 const double dead_to_left_pct = double(dead_to_left) / space_cap;
1155 const size_t live_to_right = new_top - cp->destination();
1156 const size_t dead_to_right = space->top() - addr - live_to_right;
1157
1158 tty->print_cr("%s=" PTR_FORMAT " dpc=" SIZE_FORMAT_W(5) " "
1159 "spl=" SIZE_FORMAT " "
1160 "d2l=" SIZE_FORMAT " d2l%%=%6.4f "
1161 "d2r=" SIZE_FORMAT " l2r=" SIZE_FORMAT
1162 " ratio=%10.8f",
1163 algorithm, p2i(addr), region_idx,
1164 space_live,
1165 dead_to_left, dead_to_left_pct,
1166 dead_to_right, live_to_right,
1167 double(dead_to_right) / live_to_right);
1168 }
1169 #endif // #ifndef PRODUCT
1170
1171 // Return a fraction indicating how much of the generation can be treated as
1172 // "dead wood" (i.e., not reclaimed). The function uses a normal distribution
1173 // based on the density of live objects in the generation to determine a limit,
1174 // which is then adjusted so the return value is min_percent when the density is
1175 // 1.
1176 //
1177 // The following table shows some return values for a different values of the
1178 // standard deviation (ParallelOldDeadWoodLimiterStdDev); the mean is 0.5 and
1179 // min_percent is 1.
1180 //
1181 // fraction allowed as dead wood
1182 // -----------------------------------------------------------------
1183 // density std_dev=70 std_dev=75 std_dev=80 std_dev=85 std_dev=90 std_dev=95
1184 // ------- ---------- ---------- ---------- ---------- ---------- ----------
1185 // 0.00000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000
1186 // 0.05000 0.03193096 0.02836880 0.02550828 0.02319280 0.02130337 0.01974941
1187 // 0.10000 0.05247504 0.04547452 0.03988045 0.03537016 0.03170171 0.02869272
1188 // 0.15000 0.07135702 0.06111390 0.05296419 0.04641639 0.04110601 0.03676066
1189 // 0.20000 0.08831616 0.07509618 0.06461766 0.05622444 0.04943437 0.04388975
1190 // 0.25000 0.10311208 0.08724696 0.07471205 0.06469760 0.05661313 0.05002313
1191 // 0.30000 0.11553050 0.09741183 0.08313394 0.07175114 0.06257797 0.05511132
1192 // 0.35000 0.12538832 0.10545958 0.08978741 0.07731366 0.06727491 0.05911289
1193 // 0.40000 0.13253818 0.11128511 0.09459590 0.08132834 0.07066107 0.06199500
1194 // 0.45000 0.13687208 0.11481163 0.09750361 0.08375387 0.07270534 0.06373386
1195 // 0.50000 0.13832410 0.11599237 0.09847664 0.08456518 0.07338887 0.06431510
1196 // 0.55000 0.13687208 0.11481163 0.09750361 0.08375387 0.07270534 0.06373386
1197 // 0.60000 0.13253818 0.11128511 0.09459590 0.08132834 0.07066107 0.06199500
1198 // 0.65000 0.12538832 0.10545958 0.08978741 0.07731366 0.06727491 0.05911289
1199 // 0.70000 0.11553050 0.09741183 0.08313394 0.07175114 0.06257797 0.05511132
1200 // 0.75000 0.10311208 0.08724696 0.07471205 0.06469760 0.05661313 0.05002313
1201 // 0.80000 0.08831616 0.07509618 0.06461766 0.05622444 0.04943437 0.04388975
1202 // 0.85000 0.07135702 0.06111390 0.05296419 0.04641639 0.04110601 0.03676066
1203 // 0.90000 0.05247504 0.04547452 0.03988045 0.03537016 0.03170171 0.02869272
1204 // 0.95000 0.03193096 0.02836880 0.02550828 0.02319280 0.02130337 0.01974941
1205 // 1.00000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000 0.01000000
1206
1207 double PSParallelCompact::dead_wood_limiter(double density, size_t min_percent)
1208 {
1209 assert(_dwl_initialized, "uninitialized");
1210
1211 // The raw limit is the value of the normal distribution at x = density.
1212 const double raw_limit = normal_distribution(density);
1213
1214 // Adjust the raw limit so it becomes the minimum when the density is 1.
1215 //
1216 // First subtract the adjustment value (which is simply the precomputed value
1217 // normal_distribution(1.0)); this yields a value of 0 when the density is 1.
1218 // Then add the minimum value, so the minimum is returned when the density is
1219 // 1. Finally, prevent negative values, which occur when the mean is not 0.5.
1220 const double min = double(min_percent) / 100.0;
1221 const double limit = raw_limit - _dwl_adjustment + min;
1222 return MAX2(limit, 0.0);
1223 }
1224
1225 ParallelCompactData::RegionData*
1226 PSParallelCompact::first_dead_space_region(const RegionData* beg,
1227 const RegionData* end)
1228 {
1229 const size_t region_size = ParallelCompactData::RegionSize;
1230 ParallelCompactData& sd = summary_data();
1231 size_t left = sd.region(beg);
1232 size_t right = end > beg ? sd.region(end) - 1 : left;
1233
1234 // Binary search.
1235 while (left < right) {
1236 // Equivalent to (left + right) / 2, but does not overflow.
1237 const size_t middle = left + (right - left) / 2;
1238 RegionData* const middle_ptr = sd.region(middle);
1239 HeapWord* const dest = middle_ptr->destination();
1240 HeapWord* const addr = sd.region_to_addr(middle);
1241 assert(dest != NULL, "sanity");
1242 assert(dest <= addr, "must move left");
1243
1244 if (middle > left && dest < addr) {
1245 right = middle - 1;
1246 } else if (middle < right && middle_ptr->data_size() == region_size) {
1247 left = middle + 1;
1248 } else {
1249 return middle_ptr;
1250 }
1251 }
1252 return sd.region(left);
1253 }
1254
1255 ParallelCompactData::RegionData*
1256 PSParallelCompact::dead_wood_limit_region(const RegionData* beg,
1257 const RegionData* end,
1258 size_t dead_words)
1259 {
1260 ParallelCompactData& sd = summary_data();
1261 size_t left = sd.region(beg);
1262 size_t right = end > beg ? sd.region(end) - 1 : left;
1263
1264 // Binary search.
1265 while (left < right) {
1266 // Equivalent to (left + right) / 2, but does not overflow.
1267 const size_t middle = left + (right - left) / 2;
1268 RegionData* const middle_ptr = sd.region(middle);
1269 HeapWord* const dest = middle_ptr->destination();
1270 HeapWord* const addr = sd.region_to_addr(middle);
1271 assert(dest != NULL, "sanity");
1272 assert(dest <= addr, "must move left");
1273
1274 const size_t dead_to_left = pointer_delta(addr, dest);
1275 if (middle > left && dead_to_left > dead_words) {
1276 right = middle - 1;
1277 } else if (middle < right && dead_to_left < dead_words) {
1278 left = middle + 1;
1279 } else {
1280 return middle_ptr;
1281 }
1282 }
1283 return sd.region(left);
1284 }
1285
1286 // The result is valid during the summary phase, after the initial summarization
1287 // of each space into itself, and before final summarization.
1288 inline double
1289 PSParallelCompact::reclaimed_ratio(const RegionData* const cp,
1290 HeapWord* const bottom,
1291 HeapWord* const top,
1292 HeapWord* const new_top)
1293 {
1294 ParallelCompactData& sd = summary_data();
1295
1296 assert(cp != NULL, "sanity");
1297 assert(bottom != NULL, "sanity");
1298 assert(top != NULL, "sanity");
1299 assert(new_top != NULL, "sanity");
1300 assert(top >= new_top, "summary data problem?");
1301 assert(new_top > bottom, "space is empty; should not be here");
1302 assert(new_top >= cp->destination(), "sanity");
1303 assert(top >= sd.region_to_addr(cp), "sanity");
1304
1305 HeapWord* const destination = cp->destination();
1306 const size_t dense_prefix_live = pointer_delta(destination, bottom);
1307 const size_t compacted_region_live = pointer_delta(new_top, destination);
1308 const size_t compacted_region_used = pointer_delta(top,
1309 sd.region_to_addr(cp));
1310 const size_t reclaimable = compacted_region_used - compacted_region_live;
1311
1312 const double divisor = dense_prefix_live + 1.25 * compacted_region_live;
1313 return double(reclaimable) / divisor;
1314 }
1315
1316 // Return the address of the end of the dense prefix, a.k.a. the start of the
1317 // compacted region. The address is always on a region boundary.
1318 //
1319 // Completely full regions at the left are skipped, since no compaction can
1320 // occur in those regions. Then the maximum amount of dead wood to allow is
1321 // computed, based on the density (amount live / capacity) of the generation;
1322 // the region with approximately that amount of dead space to the left is
1323 // identified as the limit region. Regions between the last completely full
1324 // region and the limit region are scanned and the one that has the best
1325 // (maximum) reclaimed_ratio() is selected.
1326 HeapWord*
1327 PSParallelCompact::compute_dense_prefix(const SpaceId id,
1328 bool maximum_compaction)
1329 {
1330 const size_t region_size = ParallelCompactData::RegionSize;
1331 const ParallelCompactData& sd = summary_data();
1332
1333 const MutableSpace* const space = _space_info[id].space();
1334 HeapWord* const top = space->top();
1335 HeapWord* const top_aligned_up = sd.region_align_up(top);
1336 HeapWord* const new_top = _space_info[id].new_top();
1337 HeapWord* const new_top_aligned_up = sd.region_align_up(new_top);
1338 HeapWord* const bottom = space->bottom();
1339 const RegionData* const beg_cp = sd.addr_to_region_ptr(bottom);
1340 const RegionData* const top_cp = sd.addr_to_region_ptr(top_aligned_up);
1341 const RegionData* const new_top_cp =
1342 sd.addr_to_region_ptr(new_top_aligned_up);
1343
1344 // Skip full regions at the beginning of the space--they are necessarily part
1345 // of the dense prefix.
1346 const RegionData* const full_cp = first_dead_space_region(beg_cp, new_top_cp);
1347 assert(full_cp->destination() == sd.region_to_addr(full_cp) ||
1348 space->is_empty(), "no dead space allowed to the left");
1349 assert(full_cp->data_size() < region_size || full_cp == new_top_cp - 1,
1350 "region must have dead space");
1351
1352 // The gc number is saved whenever a maximum compaction is done, and used to
1353 // determine when the maximum compaction interval has expired. This avoids
1354 // successive max compactions for different reasons.
1355 assert(total_invocations() >= _maximum_compaction_gc_num, "sanity");
1356 const size_t gcs_since_max = total_invocations() - _maximum_compaction_gc_num;
1357 const bool interval_ended = gcs_since_max > HeapMaximumCompactionInterval ||
1358 total_invocations() == HeapFirstMaximumCompactionCount;
1359 if (maximum_compaction || full_cp == top_cp || interval_ended) {
1360 _maximum_compaction_gc_num = total_invocations();
1361 return sd.region_to_addr(full_cp);
1362 }
1363
1364 const size_t space_live = pointer_delta(new_top, bottom);
1365 const size_t space_used = space->used_in_words();
1366 const size_t space_capacity = space->capacity_in_words();
1367
1368 const double density = double(space_live) / double(space_capacity);
1369 const size_t min_percent_free = MarkSweepDeadRatio;
1370 const double limiter = dead_wood_limiter(density, min_percent_free);
1371 const size_t dead_wood_max = space_used - space_live;
1372 const size_t dead_wood_limit = MIN2(size_t(space_capacity * limiter),
1373 dead_wood_max);
1374
1375 if (TraceParallelOldGCDensePrefix) {
1376 tty->print_cr("space_live=" SIZE_FORMAT " " "space_used=" SIZE_FORMAT " "
1377 "space_cap=" SIZE_FORMAT,
1378 space_live, space_used,
1379 space_capacity);
1380 tty->print_cr("dead_wood_limiter(%6.4f, " SIZE_FORMAT ")=%6.4f "
1381 "dead_wood_max=" SIZE_FORMAT " dead_wood_limit=" SIZE_FORMAT,
1382 density, min_percent_free, limiter,
1383 dead_wood_max, dead_wood_limit);
1384 }
1385
1386 // Locate the region with the desired amount of dead space to the left.
1387 const RegionData* const limit_cp =
1388 dead_wood_limit_region(full_cp, top_cp, dead_wood_limit);
1389
1390 // Scan from the first region with dead space to the limit region and find the
1391 // one with the best (largest) reclaimed ratio.
1392 double best_ratio = 0.0;
1393 const RegionData* best_cp = full_cp;
1394 for (const RegionData* cp = full_cp; cp < limit_cp; ++cp) {
1395 double tmp_ratio = reclaimed_ratio(cp, bottom, top, new_top);
1396 if (tmp_ratio > best_ratio) {
1397 best_cp = cp;
1398 best_ratio = tmp_ratio;
1399 }
1400 }
1401
1402 return sd.region_to_addr(best_cp);
1403 }
1404
1405 void PSParallelCompact::summarize_spaces_quick()
1406 {
1407 for (unsigned int i = 0; i < last_space_id; ++i) {
1408 const MutableSpace* space = _space_info[i].space();
1409 HeapWord** nta = _space_info[i].new_top_addr();
1410 bool result = _summary_data.summarize(_space_info[i].split_info(),
1411 space->bottom(), space->top(), NULL,
1412 space->bottom(), space->end(), nta);
1413 assert(result, "space must fit into itself");
1414 _space_info[i].set_dense_prefix(space->bottom());
1415 }
1416 }
1417
1418 void PSParallelCompact::fill_dense_prefix_end(SpaceId id)
1419 {
1420 HeapWord* const dense_prefix_end = dense_prefix(id);
1421 const RegionData* region = _summary_data.addr_to_region_ptr(dense_prefix_end);
1422 const idx_t dense_prefix_bit = _mark_bitmap.addr_to_bit(dense_prefix_end);
1423 if (dead_space_crosses_boundary(region, dense_prefix_bit)) {
1424 // Only enough dead space is filled so that any remaining dead space to the
1425 // left is larger than the minimum filler object. (The remainder is filled
1426 // during the copy/update phase.)
1427 //
1428 // The size of the dead space to the right of the boundary is not a
1429 // concern, since compaction will be able to use whatever space is
1430 // available.
1431 //
1432 // Here '||' is the boundary, 'x' represents a don't care bit and a box
1433 // surrounds the space to be filled with an object.
1434 //
1435 // In the 32-bit VM, each bit represents two 32-bit words:
1436 // +---+
1437 // a) beg_bits: ... x x x | 0 | || 0 x x ...
1438 // end_bits: ... x x x | 0 | || 0 x x ...
1439 // +---+
1440 //
1441 // In the 64-bit VM, each bit represents one 64-bit word:
1442 // +------------+
1443 // b) beg_bits: ... x x x | 0 || 0 | x x ...
1444 // end_bits: ... x x 1 | 0 || 0 | x x ...
1445 // +------------+
1446 // +-------+
1447 // c) beg_bits: ... x x | 0 0 | || 0 x x ...
1448 // end_bits: ... x 1 | 0 0 | || 0 x x ...
1449 // +-------+
1450 // +-----------+
1451 // d) beg_bits: ... x | 0 0 0 | || 0 x x ...
1452 // end_bits: ... 1 | 0 0 0 | || 0 x x ...
1453 // +-----------+
1454 // +-------+
1455 // e) beg_bits: ... 0 0 | 0 0 | || 0 x x ...
1456 // end_bits: ... 0 0 | 0 0 | || 0 x x ...
1457 // +-------+
1458
1459 // Initially assume case a, c or e will apply.
1460 size_t obj_len = CollectedHeap::min_fill_size();
1461 HeapWord* obj_beg = dense_prefix_end - obj_len;
1462
1463 #ifdef _LP64
1464 if (MinObjAlignment > 1) { // object alignment > heap word size
1465 // Cases a, c or e.
1466 } else if (_mark_bitmap.is_obj_end(dense_prefix_bit - 2)) {
1467 // Case b above.
1468 obj_beg = dense_prefix_end - 1;
1469 } else if (!_mark_bitmap.is_obj_end(dense_prefix_bit - 3) &&
1470 _mark_bitmap.is_obj_end(dense_prefix_bit - 4)) {
1471 // Case d above.
1472 obj_beg = dense_prefix_end - 3;
1473 obj_len = 3;
1474 }
1475 #endif // #ifdef _LP64
1476
1477 CollectedHeap::fill_with_object(obj_beg, obj_len);
1478 _mark_bitmap.mark_obj(obj_beg, obj_len);
1479 _summary_data.add_obj(obj_beg, obj_len);
1480 assert(start_array(id) != NULL, "sanity");
1481 start_array(id)->allocate_block(obj_beg);
1482 }
1483 }
1484
1485 void
1486 PSParallelCompact::clear_source_region(HeapWord* beg_addr, HeapWord* end_addr)
1487 {
1488 RegionData* const beg_ptr = _summary_data.addr_to_region_ptr(beg_addr);
1489 HeapWord* const end_aligned_up = _summary_data.region_align_up(end_addr);
1490 RegionData* const end_ptr = _summary_data.addr_to_region_ptr(end_aligned_up);
1491 for (RegionData* cur = beg_ptr; cur < end_ptr; ++cur) {
1492 cur->set_source_region(0);
1493 }
1494 }
1495
1496 void
1497 PSParallelCompact::summarize_space(SpaceId id, bool maximum_compaction)
1498 {
1499 assert(id < last_space_id, "id out of range");
1500 assert(_space_info[id].dense_prefix() == _space_info[id].space()->bottom(),
1501 "should have been reset in summarize_spaces_quick()");
1502
1503 const MutableSpace* space = _space_info[id].space();
1504 if (_space_info[id].new_top() != space->bottom()) {
1505 HeapWord* dense_prefix_end = compute_dense_prefix(id, maximum_compaction);
1506 _space_info[id].set_dense_prefix(dense_prefix_end);
1507
1508 #ifndef PRODUCT
1509 if (TraceParallelOldGCDensePrefix) {
1510 print_dense_prefix_stats("ratio", id, maximum_compaction,
1511 dense_prefix_end);
1512 HeapWord* addr = compute_dense_prefix_via_density(id, maximum_compaction);
1513 print_dense_prefix_stats("density", id, maximum_compaction, addr);
1514 }
1515 #endif // #ifndef PRODUCT
1516
1517 // Recompute the summary data, taking into account the dense prefix. If
1518 // every last byte will be reclaimed, then the existing summary data which
1519 // compacts everything can be left in place.
1520 if (!maximum_compaction && dense_prefix_end != space->bottom()) {
1521 // If dead space crosses the dense prefix boundary, it is (at least
1522 // partially) filled with a dummy object, marked live and added to the
1523 // summary data. This simplifies the copy/update phase and must be done
1524 // before the final locations of objects are determined, to prevent
1525 // leaving a fragment of dead space that is too small to fill.
1526 fill_dense_prefix_end(id);
1527
1528 // Compute the destination of each Region, and thus each object.
1529 _summary_data.summarize_dense_prefix(space->bottom(), dense_prefix_end);
1530 _summary_data.summarize(_space_info[id].split_info(),
1531 dense_prefix_end, space->top(), NULL,
1532 dense_prefix_end, space->end(),
1533 _space_info[id].new_top_addr());
1534 }
1535 }
1536
1537 if (log_is_enabled(Develop, gc, compaction, phases)) {
1538 const size_t region_size = ParallelCompactData::RegionSize;
1539 HeapWord* const dense_prefix_end = _space_info[id].dense_prefix();
1540 const size_t dp_region = _summary_data.addr_to_region_idx(dense_prefix_end);
1541 const size_t dp_words = pointer_delta(dense_prefix_end, space->bottom());
1542 HeapWord* const new_top = _space_info[id].new_top();
1543 const HeapWord* nt_aligned_up = _summary_data.region_align_up(new_top);
1544 const size_t cr_words = pointer_delta(nt_aligned_up, dense_prefix_end);
1545 log_develop(gc, compaction, phases)(
1546 "id=%d cap=" SIZE_FORMAT " dp=" PTR_FORMAT " "
1547 "dp_region=" SIZE_FORMAT " " "dp_count=" SIZE_FORMAT " "
1548 "cr_count=" SIZE_FORMAT " " "nt=" PTR_FORMAT,
1549 id, space->capacity_in_words(), p2i(dense_prefix_end),
1550 dp_region, dp_words / region_size,
1551 cr_words / region_size, p2i(new_top));
1552 }
1553 }
1554
1555 #ifndef PRODUCT
1556 void PSParallelCompact::summary_phase_msg(SpaceId dst_space_id,
1557 HeapWord* dst_beg, HeapWord* dst_end,
1558 SpaceId src_space_id,
1559 HeapWord* src_beg, HeapWord* src_end)
1560 {
1561 log_develop(gc, compaction, phases)(
1562 "Summarizing %d [%s] into %d [%s]: "
1563 "src=" PTR_FORMAT "-" PTR_FORMAT " "
1564 SIZE_FORMAT "-" SIZE_FORMAT " "
1565 "dst=" PTR_FORMAT "-" PTR_FORMAT " "
1566 SIZE_FORMAT "-" SIZE_FORMAT,
1567 src_space_id, space_names[src_space_id],
1568 dst_space_id, space_names[dst_space_id],
1569 p2i(src_beg), p2i(src_end),
1570 _summary_data.addr_to_region_idx(src_beg),
1571 _summary_data.addr_to_region_idx(src_end),
1572 p2i(dst_beg), p2i(dst_end),
1573 _summary_data.addr_to_region_idx(dst_beg),
1574 _summary_data.addr_to_region_idx(dst_end));
1575 }
1576 #endif // #ifndef PRODUCT
1577
1578 void PSParallelCompact::summary_phase(ParCompactionManager* cm,
1579 bool maximum_compaction)
1580 {
1581 GCTraceTime(Trace, gc, phases) tm("summary phase", &_gc_timer);
1582
1583 #ifdef ASSERT
1584 if (TraceParallelOldGCMarkingPhase) {
1585 tty->print_cr("add_obj_count=" SIZE_FORMAT " "
1586 "add_obj_bytes=" SIZE_FORMAT,
1587 add_obj_count, add_obj_size * HeapWordSize);
1588 tty->print_cr("mark_bitmap_count=" SIZE_FORMAT " "
1589 "mark_bitmap_bytes=" SIZE_FORMAT,
1590 mark_bitmap_count, mark_bitmap_size * HeapWordSize);
1591 }
1592 #endif // #ifdef ASSERT
1593
1594 // Quick summarization of each space into itself, to see how much is live.
1595 summarize_spaces_quick();
1596
1597 log_develop(gc, compaction, phases)("Summary_phase: after summarizing each space to self");
1598 NOT_PRODUCT(print_region_ranges());
1599 NOT_PRODUCT(print_initial_summary_data(_summary_data, _space_info));
1600
1601 // The amount of live data that will end up in old space (assuming it fits).
1602 size_t old_space_total_live = 0;
1603 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
1604 old_space_total_live += pointer_delta(_space_info[id].new_top(),
1605 _space_info[id].space()->bottom());
1606 }
1607
1608 MutableSpace* const old_space = _space_info[old_space_id].space();
1609 const size_t old_capacity = old_space->capacity_in_words();
1610 if (old_space_total_live > old_capacity) {
1611 // XXX - should also try to expand
1612 maximum_compaction = true;
1613 }
1614
1615 // Old generations.
1616 summarize_space(old_space_id, maximum_compaction);
1617
1618 // Summarize the remaining spaces in the young gen. The initial target space
1619 // is the old gen. If a space does not fit entirely into the target, then the
1620 // remainder is compacted into the space itself and that space becomes the new
1621 // target.
1622 SpaceId dst_space_id = old_space_id;
1623 HeapWord* dst_space_end = old_space->end();
1624 HeapWord** new_top_addr = _space_info[dst_space_id].new_top_addr();
1625 for (unsigned int id = eden_space_id; id < last_space_id; ++id) {
1626 const MutableSpace* space = _space_info[id].space();
1627 const size_t live = pointer_delta(_space_info[id].new_top(),
1628 space->bottom());
1629 const size_t available = pointer_delta(dst_space_end, *new_top_addr);
1630
1631 NOT_PRODUCT(summary_phase_msg(dst_space_id, *new_top_addr, dst_space_end,
1632 SpaceId(id), space->bottom(), space->top());)
1633 if (live > 0 && live <= available) {
1634 // All the live data will fit.
1635 bool done = _summary_data.summarize(_space_info[id].split_info(),
1636 space->bottom(), space->top(),
1637 NULL,
1638 *new_top_addr, dst_space_end,
1639 new_top_addr);
1640 assert(done, "space must fit into old gen");
1641
1642 // Reset the new_top value for the space.
1643 _space_info[id].set_new_top(space->bottom());
1644 } else if (live > 0) {
1645 // Attempt to fit part of the source space into the target space.
1646 HeapWord* next_src_addr = NULL;
1647 bool done = _summary_data.summarize(_space_info[id].split_info(),
1648 space->bottom(), space->top(),
1649 &next_src_addr,
1650 *new_top_addr, dst_space_end,
1651 new_top_addr);
1652 assert(!done, "space should not fit into old gen");
1653 assert(next_src_addr != NULL, "sanity");
1654
1655 // The source space becomes the new target, so the remainder is compacted
1656 // within the space itself.
1657 dst_space_id = SpaceId(id);
1658 dst_space_end = space->end();
1659 new_top_addr = _space_info[id].new_top_addr();
1660 NOT_PRODUCT(summary_phase_msg(dst_space_id,
1661 space->bottom(), dst_space_end,
1662 SpaceId(id), next_src_addr, space->top());)
1663 done = _summary_data.summarize(_space_info[id].split_info(),
1664 next_src_addr, space->top(),
1665 NULL,
1666 space->bottom(), dst_space_end,
1667 new_top_addr);
1668 assert(done, "space must fit when compacted into itself");
1669 assert(*new_top_addr <= space->top(), "usage should not grow");
1670 }
1671 }
1672
1673 log_develop(gc, compaction, phases)("Summary_phase: after final summarization");
1674 NOT_PRODUCT(print_region_ranges());
1675 NOT_PRODUCT(print_initial_summary_data(_summary_data, _space_info));
1676 }
1677
1678 // This method should contain all heap-specific policy for invoking a full
1679 // collection. invoke_no_policy() will only attempt to compact the heap; it
1680 // will do nothing further. If we need to bail out for policy reasons, scavenge
1681 // before full gc, or any other specialized behavior, it needs to be added here.
1682 //
1683 // Note that this method should only be called from the vm_thread while at a
1684 // safepoint.
1685 //
1686 // Note that the all_soft_refs_clear flag in the collector policy
1687 // may be true because this method can be called without intervening
1688 // activity. For example when the heap space is tight and full measure
1689 // are being taken to free space.
1690 void PSParallelCompact::invoke(bool maximum_heap_compaction) {
1691 assert(SafepointSynchronize::is_at_safepoint(), "should be at safepoint");
1692 assert(Thread::current() == (Thread*)VMThread::vm_thread(),
1693 "should be in vm thread");
1694
1695 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
1696 GCCause::Cause gc_cause = heap->gc_cause();
1697 assert(!heap->is_gc_active(), "not reentrant");
1698
1699 PSAdaptiveSizePolicy* policy = heap->size_policy();
1700 IsGCActiveMark mark;
1701
1702 if (ScavengeBeforeFullGC) {
1703 PSScavenge::invoke_no_policy();
1704 }
1705
1706 const bool clear_all_soft_refs =
1707 heap->collector_policy()->should_clear_all_soft_refs();
1708
1709 PSParallelCompact::invoke_no_policy(clear_all_soft_refs ||
1710 maximum_heap_compaction);
1711 }
1712
1713 // This method contains no policy. You should probably
1714 // be calling invoke() instead.
1715 bool PSParallelCompact::invoke_no_policy(bool maximum_heap_compaction) {
1716 assert(SafepointSynchronize::is_at_safepoint(), "must be at a safepoint");
1717 assert(ref_processor() != NULL, "Sanity");
1718
1719 if (GC_locker::check_active_before_gc()) {
1720 return false;
1721 }
1722
1723 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
1724
1725 GCIdMark gc_id_mark;
1726 _gc_timer.register_gc_start();
1727 _gc_tracer.report_gc_start(heap->gc_cause(), _gc_timer.gc_start());
1728
1729 TimeStamp marking_start;
1730 TimeStamp compaction_start;
1731 TimeStamp collection_exit;
1732
1733 GCCause::Cause gc_cause = heap->gc_cause();
1734 PSYoungGen* young_gen = heap->young_gen();
1735 PSOldGen* old_gen = heap->old_gen();
1736 PSAdaptiveSizePolicy* size_policy = heap->size_policy();
1737
1738 // The scope of casr should end after code that can change
1739 // CollectorPolicy::_should_clear_all_soft_refs.
1740 ClearedAllSoftRefs casr(maximum_heap_compaction,
1741 heap->collector_policy());
1742
1743 if (ZapUnusedHeapArea) {
1744 // Save information needed to minimize mangling
1745 heap->record_gen_tops_before_GC();
1746 }
1747
1748 heap->pre_full_gc_dump(&_gc_timer);
1749
1750 // Make sure data structures are sane, make the heap parsable, and do other
1751 // miscellaneous bookkeeping.
1752 pre_compact();
1753
1754 PreGCValues pre_gc_values(heap);
1755
1756 // Get the compaction manager reserved for the VM thread.
1757 ParCompactionManager* const vmthread_cm =
1758 ParCompactionManager::manager_array(gc_task_manager()->workers());
1759
1760 {
1761 ResourceMark rm;
1762 HandleMark hm;
1763
1764 // Set the number of GC threads to be used in this collection
1765 gc_task_manager()->set_active_gang();
1766 gc_task_manager()->task_idle_workers();
1767
1768 GCTraceCPUTime tcpu;
1769 GCTraceTime(Info, gc) tm("Full GC", NULL, gc_cause, true);
1770 TraceCollectorStats tcs(counters());
1771 TraceMemoryManagerStats tms(true /* Full GC */,gc_cause);
1772
1773 if (TraceOldGenTime) accumulated_time()->start();
1774
1775 // Let the size policy know we're starting
1776 size_policy->major_collection_begin();
1777
1778 CodeCache::gc_prologue();
1779
1780 #if defined(COMPILER2) || INCLUDE_JVMCI
1781 DerivedPointerTable::clear();
1782 #endif
1783
1784 ref_processor()->enable_discovery();
1785 ref_processor()->setup_policy(maximum_heap_compaction);
1786
1787 bool marked_for_unloading = false;
1788
1789 marking_start.update();
1790 marking_phase(vmthread_cm, maximum_heap_compaction, &_gc_tracer);
1791
1792 bool max_on_system_gc = UseMaximumCompactionOnSystemGC
1793 && GCCause::is_user_requested_gc(gc_cause);
1794 summary_phase(vmthread_cm, maximum_heap_compaction || max_on_system_gc);
1795
1796 #if defined(COMPILER2) || INCLUDE_JVMCI
1797 assert(DerivedPointerTable::is_active(), "Sanity");
1798 DerivedPointerTable::set_active(false);
1799 #endif
1800
1801 // adjust_roots() updates Universe::_intArrayKlassObj which is
1802 // needed by the compaction for filling holes in the dense prefix.
1803 adjust_roots();
1804
1805 compaction_start.update();
1806 compact();
1807
1808 // Reset the mark bitmap, summary data, and do other bookkeeping. Must be
1809 // done before resizing.
1810 post_compact();
1811
1812 // Let the size policy know we're done
1813 size_policy->major_collection_end(old_gen->used_in_bytes(), gc_cause);
1814
1815 if (UseAdaptiveSizePolicy) {
1816 log_debug(gc, ergo)("AdaptiveSizeStart: collection: %d ", heap->total_collections());
1817 log_trace(gc, ergo)("old_gen_capacity: " SIZE_FORMAT " young_gen_capacity: " SIZE_FORMAT,
1818 old_gen->capacity_in_bytes(), young_gen->capacity_in_bytes());
1819
1820 // Don't check if the size_policy is ready here. Let
1821 // the size_policy check that internally.
1822 if (UseAdaptiveGenerationSizePolicyAtMajorCollection &&
1823 AdaptiveSizePolicy::should_update_promo_stats(gc_cause)) {
1824 // Swap the survivor spaces if from_space is empty. The
1825 // resize_young_gen() called below is normally used after
1826 // a successful young GC and swapping of survivor spaces;
1827 // otherwise, it will fail to resize the young gen with
1828 // the current implementation.
1829 if (young_gen->from_space()->is_empty()) {
1830 young_gen->from_space()->clear(SpaceDecorator::Mangle);
1831 young_gen->swap_spaces();
1832 }
1833
1834 // Calculate optimal free space amounts
1835 assert(young_gen->max_size() >
1836 young_gen->from_space()->capacity_in_bytes() +
1837 young_gen->to_space()->capacity_in_bytes(),
1838 "Sizes of space in young gen are out-of-bounds");
1839
1840 size_t young_live = young_gen->used_in_bytes();
1841 size_t eden_live = young_gen->eden_space()->used_in_bytes();
1842 size_t old_live = old_gen->used_in_bytes();
1843 size_t cur_eden = young_gen->eden_space()->capacity_in_bytes();
1844 size_t max_old_gen_size = old_gen->max_gen_size();
1845 size_t max_eden_size = young_gen->max_size() -
1846 young_gen->from_space()->capacity_in_bytes() -
1847 young_gen->to_space()->capacity_in_bytes();
1848
1849 // Used for diagnostics
1850 size_policy->clear_generation_free_space_flags();
1851
1852 size_policy->compute_generations_free_space(young_live,
1853 eden_live,
1854 old_live,
1855 cur_eden,
1856 max_old_gen_size,
1857 max_eden_size,
1858 true /* full gc*/);
1859
1860 size_policy->check_gc_overhead_limit(young_live,
1861 eden_live,
1862 max_old_gen_size,
1863 max_eden_size,
1864 true /* full gc*/,
1865 gc_cause,
1866 heap->collector_policy());
1867
1868 size_policy->decay_supplemental_growth(true /* full gc*/);
1869
1870 heap->resize_old_gen(
1871 size_policy->calculated_old_free_size_in_bytes());
1872
1873 heap->resize_young_gen(size_policy->calculated_eden_size_in_bytes(),
1874 size_policy->calculated_survivor_size_in_bytes());
1875 }
1876
1877 log_debug(gc, ergo)("AdaptiveSizeStop: collection: %d ", heap->total_collections());
1878 }
1879
1880 if (UsePerfData) {
1881 PSGCAdaptivePolicyCounters* const counters = heap->gc_policy_counters();
1882 counters->update_counters();
1883 counters->update_old_capacity(old_gen->capacity_in_bytes());
1884 counters->update_young_capacity(young_gen->capacity_in_bytes());
1885 }
1886
1887 heap->resize_all_tlabs();
1888
1889 // Resize the metaspace capacity after a collection
1890 MetaspaceGC::compute_new_size();
1891
1892 if (TraceOldGenTime) {
1893 accumulated_time()->stop();
1894 }
1895
1896 young_gen->print_used_change(pre_gc_values.young_gen_used());
1897 old_gen->print_used_change(pre_gc_values.old_gen_used());
1898 MetaspaceAux::print_metaspace_change(pre_gc_values.metadata_used());
1899
1900 // Track memory usage and detect low memory
1901 MemoryService::track_memory_usage();
1902 heap->update_counters();
1903 gc_task_manager()->release_idle_workers();
1904 }
1905
1906 #ifdef ASSERT
1907 for (size_t i = 0; i < ParallelGCThreads + 1; ++i) {
1908 ParCompactionManager* const cm =
1909 ParCompactionManager::manager_array(int(i));
1910 assert(cm->marking_stack()->is_empty(), "should be empty");
1911 assert(ParCompactionManager::region_list(int(i))->is_empty(), "should be empty");
1912 }
1913 #endif // ASSERT
1914
1915 if (VerifyAfterGC && heap->total_collections() >= VerifyGCStartAt) {
1916 HandleMark hm; // Discard invalid handles created during verification
1917 Universe::verify("After GC");
1918 }
1919
1920 // Re-verify object start arrays
1921 if (VerifyObjectStartArray &&
1922 VerifyAfterGC) {
1923 old_gen->verify_object_start_array();
1924 }
1925
1926 if (ZapUnusedHeapArea) {
1927 old_gen->object_space()->check_mangled_unused_area_complete();
1928 }
1929
1930 NOT_PRODUCT(ref_processor()->verify_no_references_recorded());
1931
1932 collection_exit.update();
1933
1934 heap->print_heap_after_gc();
1935 heap->trace_heap_after_gc(&_gc_tracer);
1936
1937 log_debug(gc, task, time)("VM-Thread " JLONG_FORMAT " " JLONG_FORMAT " " JLONG_FORMAT,
1938 marking_start.ticks(), compaction_start.ticks(),
1939 collection_exit.ticks());
1940 gc_task_manager()->print_task_time_stamps();
1941
1942 heap->post_full_gc_dump(&_gc_timer);
1943
1944 #ifdef TRACESPINNING
1945 ParallelTaskTerminator::print_termination_counts();
1946 #endif
1947
1948 AdaptiveSizePolicyOutput::print(size_policy, heap->total_collections());
1949
1950 _gc_timer.register_gc_end();
1951
1952 _gc_tracer.report_dense_prefix(dense_prefix(old_space_id));
1953 _gc_tracer.report_gc_end(_gc_timer.gc_end(), _gc_timer.time_partitions());
1954
1955 return true;
1956 }
1957
1958 bool PSParallelCompact::absorb_live_data_from_eden(PSAdaptiveSizePolicy* size_policy,
1959 PSYoungGen* young_gen,
1960 PSOldGen* old_gen) {
1961 MutableSpace* const eden_space = young_gen->eden_space();
1962 assert(!eden_space->is_empty(), "eden must be non-empty");
1963 assert(young_gen->virtual_space()->alignment() ==
1964 old_gen->virtual_space()->alignment(), "alignments do not match");
1965
1966 if (!(UseAdaptiveSizePolicy && UseAdaptiveGCBoundary)) {
1967 return false;
1968 }
1969
1970 // Both generations must be completely committed.
1971 if (young_gen->virtual_space()->uncommitted_size() != 0) {
1972 return false;
1973 }
1974 if (old_gen->virtual_space()->uncommitted_size() != 0) {
1975 return false;
1976 }
1977
1978 // Figure out how much to take from eden. Include the average amount promoted
1979 // in the total; otherwise the next young gen GC will simply bail out to a
1980 // full GC.
1981 const size_t alignment = old_gen->virtual_space()->alignment();
1982 const size_t eden_used = eden_space->used_in_bytes();
1983 const size_t promoted = (size_t)size_policy->avg_promoted()->padded_average();
1984 const size_t absorb_size = align_size_up(eden_used + promoted, alignment);
1985 const size_t eden_capacity = eden_space->capacity_in_bytes();
1986
1987 if (absorb_size >= eden_capacity) {
1988 return false; // Must leave some space in eden.
1989 }
1990
1991 const size_t new_young_size = young_gen->capacity_in_bytes() - absorb_size;
1992 if (new_young_size < young_gen->min_gen_size()) {
1993 return false; // Respect young gen minimum size.
1994 }
1995
1996 log_trace(heap, ergo)(" absorbing " SIZE_FORMAT "K: "
1997 "eden " SIZE_FORMAT "K->" SIZE_FORMAT "K "
1998 "from " SIZE_FORMAT "K, to " SIZE_FORMAT "K "
1999 "young_gen " SIZE_FORMAT "K->" SIZE_FORMAT "K ",
2000 absorb_size / K,
2001 eden_capacity / K, (eden_capacity - absorb_size) / K,
2002 young_gen->from_space()->used_in_bytes() / K,
2003 young_gen->to_space()->used_in_bytes() / K,
2004 young_gen->capacity_in_bytes() / K, new_young_size / K);
2005
2006 // Fill the unused part of the old gen.
2007 MutableSpace* const old_space = old_gen->object_space();
2008 HeapWord* const unused_start = old_space->top();
2009 size_t const unused_words = pointer_delta(old_space->end(), unused_start);
2010
2011 if (unused_words > 0) {
2012 if (unused_words < CollectedHeap::min_fill_size()) {
2013 return false; // If the old gen cannot be filled, must give up.
2014 }
2015 CollectedHeap::fill_with_objects(unused_start, unused_words);
2016 }
2017
2018 // Take the live data from eden and set both top and end in the old gen to
2019 // eden top. (Need to set end because reset_after_change() mangles the region
2020 // from end to virtual_space->high() in debug builds).
2021 HeapWord* const new_top = eden_space->top();
2022 old_gen->virtual_space()->expand_into(young_gen->virtual_space(),
2023 absorb_size);
2024 young_gen->reset_after_change();
2025 old_space->set_top(new_top);
2026 old_space->set_end(new_top);
2027 old_gen->reset_after_change();
2028
2029 // Update the object start array for the filler object and the data from eden.
2030 ObjectStartArray* const start_array = old_gen->start_array();
2031 for (HeapWord* p = unused_start; p < new_top; p += oop(p)->size()) {
2032 start_array->allocate_block(p);
2033 }
2034
2035 // Could update the promoted average here, but it is not typically updated at
2036 // full GCs and the value to use is unclear. Something like
2037 //
2038 // cur_promoted_avg + absorb_size / number_of_scavenges_since_last_full_gc.
2039
2040 size_policy->set_bytes_absorbed_from_eden(absorb_size);
2041 return true;
2042 }
2043
2044 GCTaskManager* const PSParallelCompact::gc_task_manager() {
2045 assert(ParallelScavengeHeap::gc_task_manager() != NULL,
2046 "shouldn't return NULL");
2047 return ParallelScavengeHeap::gc_task_manager();
2048 }
2049
2050 void PSParallelCompact::marking_phase(ParCompactionManager* cm,
2051 bool maximum_heap_compaction,
2052 ParallelOldTracer *gc_tracer) {
2053 // Recursively traverse all live objects and mark them
2054 GCTraceTime(Trace, gc, phases) tm("marking phase", &_gc_timer);
2055
2056 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
2057 uint parallel_gc_threads = heap->gc_task_manager()->workers();
2058 uint active_gc_threads = heap->gc_task_manager()->active_workers();
2059 TaskQueueSetSuper* qset = ParCompactionManager::region_array();
2060 ParallelTaskTerminator terminator(active_gc_threads, qset);
2061
2062 ParCompactionManager::MarkAndPushClosure mark_and_push_closure(cm);
2063 ParCompactionManager::FollowStackClosure follow_stack_closure(cm);
2064
2065 // Need new claim bits before marking starts.
2066 ClassLoaderDataGraph::clear_claimed_marks();
2067
2068 {
2069 GCTraceTime(Trace, gc, phases) tm("par mark", &_gc_timer);
2070
2071 ParallelScavengeHeap::ParStrongRootsScope psrs;
2072
2073 GCTaskQueue* q = GCTaskQueue::create();
2074
2075 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::universe));
2076 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::jni_handles));
2077 // We scan the thread roots in parallel
2078 Threads::create_thread_roots_marking_tasks(q);
2079 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::object_synchronizer));
2080 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::flat_profiler));
2081 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::management));
2082 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::system_dictionary));
2083 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::class_loader_data));
2084 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::jvmti));
2085 q->enqueue(new MarkFromRootsTask(MarkFromRootsTask::code_cache));
2086
2087 if (active_gc_threads > 1) {
2088 for (uint j = 0; j < active_gc_threads; j++) {
2089 q->enqueue(new StealMarkingTask(&terminator));
2090 }
2091 }
2092
2093 gc_task_manager()->execute_and_wait(q);
2094 }
2095
2096 // Process reference objects found during marking
2097 {
2098 GCTraceTime(Trace, gc, phases) tm("reference processing", &_gc_timer);
2099
2100 ReferenceProcessorStats stats;
2101 if (ref_processor()->processing_is_mt()) {
2102 RefProcTaskExecutor task_executor;
2103 stats = ref_processor()->process_discovered_references(
2104 is_alive_closure(), &mark_and_push_closure, &follow_stack_closure,
2105 &task_executor, &_gc_timer);
2106 } else {
2107 stats = ref_processor()->process_discovered_references(
2108 is_alive_closure(), &mark_and_push_closure, &follow_stack_closure, NULL,
2109 &_gc_timer);
2110 }
2111
2112 gc_tracer->report_gc_reference_stats(stats);
2113 }
2114
2115 GCTraceTime(Trace, gc) tm_m("class unloading", &_gc_timer);
2116
2117 // This is the point where the entire marking should have completed.
2118 assert(cm->marking_stacks_empty(), "Marking should have completed");
2119
2120 // Follow system dictionary roots and unload classes.
2121 bool purged_class = SystemDictionary::do_unloading(is_alive_closure());
2122
2123 // Unload nmethods.
2124 CodeCache::do_unloading(is_alive_closure(), purged_class);
2125
2126 // Prune dead klasses from subklass/sibling/implementor lists.
2127 Klass::clean_weak_klass_links(is_alive_closure());
2128
2129 // Delete entries for dead interned strings.
2130 StringTable::unlink(is_alive_closure());
2131
2132 // Clean up unreferenced symbols in symbol table.
2133 SymbolTable::unlink();
2134 _gc_tracer.report_object_count_after_gc(is_alive_closure());
2135 }
2136
2137 // This should be moved to the shared markSweep code!
2138 class PSAlwaysTrueClosure: public BoolObjectClosure {
2139 public:
2140 bool do_object_b(oop p) { return true; }
2141 };
2142 static PSAlwaysTrueClosure always_true;
2143
2144 void PSParallelCompact::adjust_roots() {
2145 // Adjust the pointers to reflect the new locations
2146 GCTraceTime(Trace, gc, phases) tm("adjust roots", &_gc_timer);
2147
2148 // Need new claim bits when tracing through and adjusting pointers.
2149 ClassLoaderDataGraph::clear_claimed_marks();
2150
2151 // General strong roots.
2152 Universe::oops_do(adjust_pointer_closure());
2153 JNIHandles::oops_do(adjust_pointer_closure()); // Global (strong) JNI handles
2154 CLDToOopClosure adjust_from_cld(adjust_pointer_closure());
2155 Threads::oops_do(adjust_pointer_closure(), &adjust_from_cld, NULL);
2156 ObjectSynchronizer::oops_do(adjust_pointer_closure());
2157 FlatProfiler::oops_do(adjust_pointer_closure());
2158 Management::oops_do(adjust_pointer_closure());
2159 JvmtiExport::oops_do(adjust_pointer_closure());
2160 SystemDictionary::oops_do(adjust_pointer_closure());
2161 ClassLoaderDataGraph::oops_do(adjust_pointer_closure(), adjust_klass_closure(), true);
2162
2163 // Now adjust pointers in remaining weak roots. (All of which should
2164 // have been cleared if they pointed to non-surviving objects.)
2165 // Global (weak) JNI handles
2166 JNIHandles::weak_oops_do(&always_true, adjust_pointer_closure());
2167
2168 CodeBlobToOopClosure adjust_from_blobs(adjust_pointer_closure(), CodeBlobToOopClosure::FixRelocations);
2169 CodeCache::blobs_do(&adjust_from_blobs);
2170 StringTable::oops_do(adjust_pointer_closure());
2171 ref_processor()->weak_oops_do(adjust_pointer_closure());
2172 // Roots were visited so references into the young gen in roots
2173 // may have been scanned. Process them also.
2174 // Should the reference processor have a span that excludes
2175 // young gen objects?
2176 PSScavenge::reference_processor()->weak_oops_do(adjust_pointer_closure());
2177 }
2178
2179 // Helper class to print 8 region numbers per line and then print the total at the end.
2180 class FillableRegionLogger : public StackObj {
2181 private:
2182 LogHandle(gc, compaction) log;
2183 static const int LineLength = 8;
2184 size_t _regions[LineLength];
2185 int _next_index;
2186 bool _enabled;
2187 size_t _total_regions;
2188 public:
2189 FillableRegionLogger() : _next_index(0), _total_regions(0), _enabled(log.is_develop()) { }
2190 ~FillableRegionLogger() {
2191 log.develop(SIZE_FORMAT " initially fillable regions", _total_regions);
2192 }
2193
2194 void print_line() {
2195 if (!_enabled || _next_index == 0) {
2196 return;
2197 }
2198 FormatBuffer<> line("Fillable: ");
2199 for (int i = 0; i < _next_index; i++) {
2200 line.append(" " SIZE_FORMAT_W(7), _regions[i]);
2201 }
2202 log.develop("%s", line.buffer());
2203 _next_index = 0;
2204 }
2205
2206 void handle(size_t region) {
2207 if (!_enabled) {
2208 return;
2209 }
2210 _regions[_next_index++] = region;
2211 if (_next_index == LineLength) {
2212 print_line();
2213 }
2214 _total_regions++;
2215 }
2216 };
2217
2218 void PSParallelCompact::enqueue_region_draining_tasks(GCTaskQueue* q,
2219 uint parallel_gc_threads)
2220 {
2221 GCTraceTime(Trace, gc, phases) tm("drain task setup", &_gc_timer);
2222
2223 // Find the threads that are active
2224 unsigned int which = 0;
2225
2226 const uint task_count = MAX2(parallel_gc_threads, 1U);
2227 for (uint j = 0; j < task_count; j++) {
2228 q->enqueue(new DrainStacksCompactionTask(j));
2229 ParCompactionManager::verify_region_list_empty(j);
2230 // Set the region stacks variables to "no" region stack values
2231 // so that they will be recognized and needing a region stack
2232 // in the stealing tasks if they do not get one by executing
2233 // a draining stack.
2234 ParCompactionManager* cm = ParCompactionManager::manager_array(j);
2235 cm->set_region_stack(NULL);
2236 cm->set_region_stack_index((uint)max_uintx);
2237 }
2238 ParCompactionManager::reset_recycled_stack_index();
2239
2240 // Find all regions that are available (can be filled immediately) and
2241 // distribute them to the thread stacks. The iteration is done in reverse
2242 // order (high to low) so the regions will be removed in ascending order.
2243
2244 const ParallelCompactData& sd = PSParallelCompact::summary_data();
2245
2246 // A region index which corresponds to the tasks created above.
2247 // "which" must be 0 <= which < task_count
2248
2249 which = 0;
2250 // id + 1 is used to test termination so unsigned can
2251 // be used with an old_space_id == 0.
2252 FillableRegionLogger region_logger;
2253 for (unsigned int id = to_space_id; id + 1 > old_space_id; --id) {
2254 SpaceInfo* const space_info = _space_info + id;
2255 MutableSpace* const space = space_info->space();
2256 HeapWord* const new_top = space_info->new_top();
2257
2258 const size_t beg_region = sd.addr_to_region_idx(space_info->dense_prefix());
2259 const size_t end_region =
2260 sd.addr_to_region_idx(sd.region_align_up(new_top));
2261
2262 for (size_t cur = end_region - 1; cur + 1 > beg_region; --cur) {
2263 if (sd.region(cur)->claim_unsafe()) {
2264 ParCompactionManager::region_list_push(which, cur);
2265 region_logger.handle(cur);
2266 // Assign regions to tasks in round-robin fashion.
2267 if (++which == task_count) {
2268 assert(which <= parallel_gc_threads,
2269 "Inconsistent number of workers");
2270 which = 0;
2271 }
2272 }
2273 }
2274 region_logger.print_line();
2275 }
2276 }
2277
2278 #define PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING 4
2279
2280 void PSParallelCompact::enqueue_dense_prefix_tasks(GCTaskQueue* q,
2281 uint parallel_gc_threads) {
2282 GCTraceTime(Trace, gc, phases) tm("dense prefix task setup", &_gc_timer);
2283
2284 ParallelCompactData& sd = PSParallelCompact::summary_data();
2285
2286 // Iterate over all the spaces adding tasks for updating
2287 // regions in the dense prefix. Assume that 1 gc thread
2288 // will work on opening the gaps and the remaining gc threads
2289 // will work on the dense prefix.
2290 unsigned int space_id;
2291 for (space_id = old_space_id; space_id < last_space_id; ++ space_id) {
2292 HeapWord* const dense_prefix_end = _space_info[space_id].dense_prefix();
2293 const MutableSpace* const space = _space_info[space_id].space();
2294
2295 if (dense_prefix_end == space->bottom()) {
2296 // There is no dense prefix for this space.
2297 continue;
2298 }
2299
2300 // The dense prefix is before this region.
2301 size_t region_index_end_dense_prefix =
2302 sd.addr_to_region_idx(dense_prefix_end);
2303 RegionData* const dense_prefix_cp =
2304 sd.region(region_index_end_dense_prefix);
2305 assert(dense_prefix_end == space->end() ||
2306 dense_prefix_cp->available() ||
2307 dense_prefix_cp->claimed(),
2308 "The region after the dense prefix should always be ready to fill");
2309
2310 size_t region_index_start = sd.addr_to_region_idx(space->bottom());
2311
2312 // Is there dense prefix work?
2313 size_t total_dense_prefix_regions =
2314 region_index_end_dense_prefix - region_index_start;
2315 // How many regions of the dense prefix should be given to
2316 // each thread?
2317 if (total_dense_prefix_regions > 0) {
2318 uint tasks_for_dense_prefix = 1;
2319 if (total_dense_prefix_regions <=
2320 (parallel_gc_threads * PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING)) {
2321 // Don't over partition. This assumes that
2322 // PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING is a small integer value
2323 // so there are not many regions to process.
2324 tasks_for_dense_prefix = parallel_gc_threads;
2325 } else {
2326 // Over partition
2327 tasks_for_dense_prefix = parallel_gc_threads *
2328 PAR_OLD_DENSE_PREFIX_OVER_PARTITIONING;
2329 }
2330 size_t regions_per_thread = total_dense_prefix_regions /
2331 tasks_for_dense_prefix;
2332 // Give each thread at least 1 region.
2333 if (regions_per_thread == 0) {
2334 regions_per_thread = 1;
2335 }
2336
2337 for (uint k = 0; k < tasks_for_dense_prefix; k++) {
2338 if (region_index_start >= region_index_end_dense_prefix) {
2339 break;
2340 }
2341 // region_index_end is not processed
2342 size_t region_index_end = MIN2(region_index_start + regions_per_thread,
2343 region_index_end_dense_prefix);
2344 q->enqueue(new UpdateDensePrefixTask(SpaceId(space_id),
2345 region_index_start,
2346 region_index_end));
2347 region_index_start = region_index_end;
2348 }
2349 }
2350 // This gets any part of the dense prefix that did not
2351 // fit evenly.
2352 if (region_index_start < region_index_end_dense_prefix) {
2353 q->enqueue(new UpdateDensePrefixTask(SpaceId(space_id),
2354 region_index_start,
2355 region_index_end_dense_prefix));
2356 }
2357 }
2358 }
2359
2360 void PSParallelCompact::enqueue_region_stealing_tasks(
2361 GCTaskQueue* q,
2362 ParallelTaskTerminator* terminator_ptr,
2363 uint parallel_gc_threads) {
2364 GCTraceTime(Trace, gc, phases) tm("steal task setup", &_gc_timer);
2365
2366 // Once a thread has drained it's stack, it should try to steal regions from
2367 // other threads.
2368 if (parallel_gc_threads > 1) {
2369 for (uint j = 0; j < parallel_gc_threads; j++) {
2370 q->enqueue(new StealRegionCompactionTask(terminator_ptr));
2371 }
2372 }
2373 }
2374
2375 #ifdef ASSERT
2376 // Write a histogram of the number of times the block table was filled for a
2377 // region.
2378 void PSParallelCompact::write_block_fill_histogram()
2379 {
2380 LogHandle(gc, compaction) log;
2381 if (!log.is_develop()) return;
2382
2383 ResourceMark rm;
2384 outputStream* out = log.develop_stream();
2385
2386 typedef ParallelCompactData::RegionData rd_t;
2387 ParallelCompactData& sd = summary_data();
2388
2389 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2390 MutableSpace* const spc = _space_info[id].space();
2391 if (spc->bottom() != spc->top()) {
2392 const rd_t* const beg = sd.addr_to_region_ptr(spc->bottom());
2393 HeapWord* const top_aligned_up = sd.region_align_up(spc->top());
2394 const rd_t* const end = sd.addr_to_region_ptr(top_aligned_up);
2395
2396 size_t histo[5] = { 0, 0, 0, 0, 0 };
2397 const size_t histo_len = sizeof(histo) / sizeof(size_t);
2398 const size_t region_cnt = pointer_delta(end, beg, sizeof(rd_t));
2399
2400 for (const rd_t* cur = beg; cur < end; ++cur) {
2401 ++histo[MIN2(cur->blocks_filled_count(), histo_len - 1)];
2402 }
2403 out->print("Block fill histogram: %u %-4s" SIZE_FORMAT_W(5), id, space_names[id], region_cnt);
2404 for (size_t i = 0; i < histo_len; ++i) {
2405 out->print(" " SIZE_FORMAT_W(5) " %5.1f%%",
2406 histo[i], 100.0 * histo[i] / region_cnt);
2407 }
2408 out->cr();
2409 }
2410 }
2411 }
2412 #endif // #ifdef ASSERT
2413
2414 void PSParallelCompact::compact() {
2415 GCTraceTime(Trace, gc, phases) tm("compaction phase", &_gc_timer);
2416
2417 ParallelScavengeHeap* heap = ParallelScavengeHeap::heap();
2418 PSOldGen* old_gen = heap->old_gen();
2419 old_gen->start_array()->reset();
2420 uint parallel_gc_threads = heap->gc_task_manager()->workers();
2421 uint active_gc_threads = heap->gc_task_manager()->active_workers();
2422 TaskQueueSetSuper* qset = ParCompactionManager::region_array();
2423 ParallelTaskTerminator terminator(active_gc_threads, qset);
2424
2425 GCTaskQueue* q = GCTaskQueue::create();
2426 enqueue_region_draining_tasks(q, active_gc_threads);
2427 enqueue_dense_prefix_tasks(q, active_gc_threads);
2428 enqueue_region_stealing_tasks(q, &terminator, active_gc_threads);
2429
2430 {
2431 GCTraceTime(Trace, gc, phases) tm("par compact", &_gc_timer);
2432
2433 gc_task_manager()->execute_and_wait(q);
2434
2435 #ifdef ASSERT
2436 // Verify that all regions have been processed before the deferred updates.
2437 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2438 verify_complete(SpaceId(id));
2439 }
2440 #endif
2441 }
2442
2443 {
2444 // Update the deferred objects, if any. Any compaction manager can be used.
2445 GCTraceTime(Trace, gc, phases) tm("deferred updates", &_gc_timer);
2446 ParCompactionManager* cm = ParCompactionManager::manager_array(0);
2447 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2448 update_deferred_objects(cm, SpaceId(id));
2449 }
2450 }
2451
2452 DEBUG_ONLY(write_block_fill_histogram());
2453 }
2454
2455 #ifdef ASSERT
2456 void PSParallelCompact::verify_complete(SpaceId space_id) {
2457 // All Regions between space bottom() to new_top() should be marked as filled
2458 // and all Regions between new_top() and top() should be available (i.e.,
2459 // should have been emptied).
2460 ParallelCompactData& sd = summary_data();
2461 SpaceInfo si = _space_info[space_id];
2462 HeapWord* new_top_addr = sd.region_align_up(si.new_top());
2463 HeapWord* old_top_addr = sd.region_align_up(si.space()->top());
2464 const size_t beg_region = sd.addr_to_region_idx(si.space()->bottom());
2465 const size_t new_top_region = sd.addr_to_region_idx(new_top_addr);
2466 const size_t old_top_region = sd.addr_to_region_idx(old_top_addr);
2467
2468 bool issued_a_warning = false;
2469
2470 size_t cur_region;
2471 for (cur_region = beg_region; cur_region < new_top_region; ++cur_region) {
2472 const RegionData* const c = sd.region(cur_region);
2473 if (!c->completed()) {
2474 warning("region " SIZE_FORMAT " not filled: "
2475 "destination_count=%u",
2476 cur_region, c->destination_count());
2477 issued_a_warning = true;
2478 }
2479 }
2480
2481 for (cur_region = new_top_region; cur_region < old_top_region; ++cur_region) {
2482 const RegionData* const c = sd.region(cur_region);
2483 if (!c->available()) {
2484 warning("region " SIZE_FORMAT " not empty: "
2485 "destination_count=%u",
2486 cur_region, c->destination_count());
2487 issued_a_warning = true;
2488 }
2489 }
2490
2491 if (issued_a_warning) {
2492 print_region_ranges();
2493 }
2494 }
2495 #endif // #ifdef ASSERT
2496
2497 inline void UpdateOnlyClosure::do_addr(HeapWord* addr) {
2498 _start_array->allocate_block(addr);
2499 compaction_manager()->update_contents(oop(addr));
2500 }
2501
2502 // Update interior oops in the ranges of regions [beg_region, end_region).
2503 void
2504 PSParallelCompact::update_and_deadwood_in_dense_prefix(ParCompactionManager* cm,
2505 SpaceId space_id,
2506 size_t beg_region,
2507 size_t end_region) {
2508 ParallelCompactData& sd = summary_data();
2509 ParMarkBitMap* const mbm = mark_bitmap();
2510
2511 HeapWord* beg_addr = sd.region_to_addr(beg_region);
2512 HeapWord* const end_addr = sd.region_to_addr(end_region);
2513 assert(beg_region <= end_region, "bad region range");
2514 assert(end_addr <= dense_prefix(space_id), "not in the dense prefix");
2515
2516 #ifdef ASSERT
2517 // Claim the regions to avoid triggering an assert when they are marked as
2518 // filled.
2519 for (size_t claim_region = beg_region; claim_region < end_region; ++claim_region) {
2520 assert(sd.region(claim_region)->claim_unsafe(), "claim() failed");
2521 }
2522 #endif // #ifdef ASSERT
2523
2524 if (beg_addr != space(space_id)->bottom()) {
2525 // Find the first live object or block of dead space that *starts* in this
2526 // range of regions. If a partial object crosses onto the region, skip it;
2527 // it will be marked for 'deferred update' when the object head is
2528 // processed. If dead space crosses onto the region, it is also skipped; it
2529 // will be filled when the prior region is processed. If neither of those
2530 // apply, the first word in the region is the start of a live object or dead
2531 // space.
2532 assert(beg_addr > space(space_id)->bottom(), "sanity");
2533 const RegionData* const cp = sd.region(beg_region);
2534 if (cp->partial_obj_size() != 0) {
2535 beg_addr = sd.partial_obj_end(beg_region);
2536 } else if (dead_space_crosses_boundary(cp, mbm->addr_to_bit(beg_addr))) {
2537 beg_addr = mbm->find_obj_beg(beg_addr, end_addr);
2538 }
2539 }
2540
2541 if (beg_addr < end_addr) {
2542 // A live object or block of dead space starts in this range of Regions.
2543 HeapWord* const dense_prefix_end = dense_prefix(space_id);
2544
2545 // Create closures and iterate.
2546 UpdateOnlyClosure update_closure(mbm, cm, space_id);
2547 FillClosure fill_closure(cm, space_id);
2548 ParMarkBitMap::IterationStatus status;
2549 status = mbm->iterate(&update_closure, &fill_closure, beg_addr, end_addr,
2550 dense_prefix_end);
2551 if (status == ParMarkBitMap::incomplete) {
2552 update_closure.do_addr(update_closure.source());
2553 }
2554 }
2555
2556 // Mark the regions as filled.
2557 RegionData* const beg_cp = sd.region(beg_region);
2558 RegionData* const end_cp = sd.region(end_region);
2559 for (RegionData* cp = beg_cp; cp < end_cp; ++cp) {
2560 cp->set_completed();
2561 }
2562 }
2563
2564 // Return the SpaceId for the space containing addr. If addr is not in the
2565 // heap, last_space_id is returned. In debug mode it expects the address to be
2566 // in the heap and asserts such.
2567 PSParallelCompact::SpaceId PSParallelCompact::space_id(HeapWord* addr) {
2568 assert(ParallelScavengeHeap::heap()->is_in_reserved(addr), "addr not in the heap");
2569
2570 for (unsigned int id = old_space_id; id < last_space_id; ++id) {
2571 if (_space_info[id].space()->contains(addr)) {
2572 return SpaceId(id);
2573 }
2574 }
2575
2576 assert(false, "no space contains the addr");
2577 return last_space_id;
2578 }
2579
2580 void PSParallelCompact::update_deferred_objects(ParCompactionManager* cm,
2581 SpaceId id) {
2582 assert(id < last_space_id, "bad space id");
2583
2584 ParallelCompactData& sd = summary_data();
2585 const SpaceInfo* const space_info = _space_info + id;
2586 ObjectStartArray* const start_array = space_info->start_array();
2587
2588 const MutableSpace* const space = space_info->space();
2589 assert(space_info->dense_prefix() >= space->bottom(), "dense_prefix not set");
2590 HeapWord* const beg_addr = space_info->dense_prefix();
2591 HeapWord* const end_addr = sd.region_align_up(space_info->new_top());
2592
2593 const RegionData* const beg_region = sd.addr_to_region_ptr(beg_addr);
2594 const RegionData* const end_region = sd.addr_to_region_ptr(end_addr);
2595 const RegionData* cur_region;
2596 for (cur_region = beg_region; cur_region < end_region; ++cur_region) {
2597 HeapWord* const addr = cur_region->deferred_obj_addr();
2598 if (addr != NULL) {
2599 if (start_array != NULL) {
2600 start_array->allocate_block(addr);
2601 }
2602 cm->update_contents(oop(addr));
2603 assert(oop(addr)->is_oop_or_null(), "Expected an oop or NULL at " PTR_FORMAT, p2i(oop(addr)));
2604 }
2605 }
2606 }
2607
2608 // Skip over count live words starting from beg, and return the address of the
2609 // next live word. Unless marked, the word corresponding to beg is assumed to
2610 // be dead. Callers must either ensure beg does not correspond to the middle of
2611 // an object, or account for those live words in some other way. Callers must
2612 // also ensure that there are enough live words in the range [beg, end) to skip.
2613 HeapWord*
2614 PSParallelCompact::skip_live_words(HeapWord* beg, HeapWord* end, size_t count)
2615 {
2616 assert(count > 0, "sanity");
2617
2618 ParMarkBitMap* m = mark_bitmap();
2619 idx_t bits_to_skip = m->words_to_bits(count);
2620 idx_t cur_beg = m->addr_to_bit(beg);
2621 const idx_t search_end = BitMap::word_align_up(m->addr_to_bit(end));
2622
2623 do {
2624 cur_beg = m->find_obj_beg(cur_beg, search_end);
2625 idx_t cur_end = m->find_obj_end(cur_beg, search_end);
2626 const size_t obj_bits = cur_end - cur_beg + 1;
2627 if (obj_bits > bits_to_skip) {
2628 return m->bit_to_addr(cur_beg + bits_to_skip);
2629 }
2630 bits_to_skip -= obj_bits;
2631 cur_beg = cur_end + 1;
2632 } while (bits_to_skip > 0);
2633
2634 // Skipping the desired number of words landed just past the end of an object.
2635 // Find the start of the next object.
2636 cur_beg = m->find_obj_beg(cur_beg, search_end);
2637 assert(cur_beg < m->addr_to_bit(end), "not enough live words to skip");
2638 return m->bit_to_addr(cur_beg);
2639 }
2640
2641 HeapWord* PSParallelCompact::first_src_addr(HeapWord* const dest_addr,
2642 SpaceId src_space_id,
2643 size_t src_region_idx)
2644 {
2645 assert(summary_data().is_region_aligned(dest_addr), "not aligned");
2646
2647 const SplitInfo& split_info = _space_info[src_space_id].split_info();
2648 if (split_info.dest_region_addr() == dest_addr) {
2649 // The partial object ending at the split point contains the first word to
2650 // be copied to dest_addr.
2651 return split_info.first_src_addr();
2652 }
2653
2654 const ParallelCompactData& sd = summary_data();
2655 ParMarkBitMap* const bitmap = mark_bitmap();
2656 const size_t RegionSize = ParallelCompactData::RegionSize;
2657
2658 assert(sd.is_region_aligned(dest_addr), "not aligned");
2659 const RegionData* const src_region_ptr = sd.region(src_region_idx);
2660 const size_t partial_obj_size = src_region_ptr->partial_obj_size();
2661 HeapWord* const src_region_destination = src_region_ptr->destination();
2662
2663 assert(dest_addr >= src_region_destination, "wrong src region");
2664 assert(src_region_ptr->data_size() > 0, "src region cannot be empty");
2665
2666 HeapWord* const src_region_beg = sd.region_to_addr(src_region_idx);
2667 HeapWord* const src_region_end = src_region_beg + RegionSize;
2668
2669 HeapWord* addr = src_region_beg;
2670 if (dest_addr == src_region_destination) {
2671 // Return the first live word in the source region.
2672 if (partial_obj_size == 0) {
2673 addr = bitmap->find_obj_beg(addr, src_region_end);
2674 assert(addr < src_region_end, "no objects start in src region");
2675 }
2676 return addr;
2677 }
2678
2679 // Must skip some live data.
2680 size_t words_to_skip = dest_addr - src_region_destination;
2681 assert(src_region_ptr->data_size() > words_to_skip, "wrong src region");
2682
2683 if (partial_obj_size >= words_to_skip) {
2684 // All the live words to skip are part of the partial object.
2685 addr += words_to_skip;
2686 if (partial_obj_size == words_to_skip) {
2687 // Find the first live word past the partial object.
2688 addr = bitmap->find_obj_beg(addr, src_region_end);
2689 assert(addr < src_region_end, "wrong src region");
2690 }
2691 return addr;
2692 }
2693
2694 // Skip over the partial object (if any).
2695 if (partial_obj_size != 0) {
2696 words_to_skip -= partial_obj_size;
2697 addr += partial_obj_size;
2698 }
2699
2700 // Skip over live words due to objects that start in the region.
2701 addr = skip_live_words(addr, src_region_end, words_to_skip);
2702 assert(addr < src_region_end, "wrong src region");
2703 return addr;
2704 }
2705
2706 void PSParallelCompact::decrement_destination_counts(ParCompactionManager* cm,
2707 SpaceId src_space_id,
2708 size_t beg_region,
2709 HeapWord* end_addr)
2710 {
2711 ParallelCompactData& sd = summary_data();
2712
2713 #ifdef ASSERT
2714 MutableSpace* const src_space = _space_info[src_space_id].space();
2715 HeapWord* const beg_addr = sd.region_to_addr(beg_region);
2716 assert(src_space->contains(beg_addr) || beg_addr == src_space->end(),
2717 "src_space_id does not match beg_addr");
2718 assert(src_space->contains(end_addr) || end_addr == src_space->end(),
2719 "src_space_id does not match end_addr");
2720 #endif // #ifdef ASSERT
2721
2722 RegionData* const beg = sd.region(beg_region);
2723 RegionData* const end = sd.addr_to_region_ptr(sd.region_align_up(end_addr));
2724
2725 // Regions up to new_top() are enqueued if they become available.
2726 HeapWord* const new_top = _space_info[src_space_id].new_top();
2727 RegionData* const enqueue_end =
2728 sd.addr_to_region_ptr(sd.region_align_up(new_top));
2729
2730 for (RegionData* cur = beg; cur < end; ++cur) {
2731 assert(cur->data_size() > 0, "region must have live data");
2732 cur->decrement_destination_count();
2733 if (cur < enqueue_end && cur->available() && cur->claim()) {
2734 cm->push_region(sd.region(cur));
2735 }
2736 }
2737 }
2738
2739 size_t PSParallelCompact::next_src_region(MoveAndUpdateClosure& closure,
2740 SpaceId& src_space_id,
2741 HeapWord*& src_space_top,
2742 HeapWord* end_addr)
2743 {
2744 typedef ParallelCompactData::RegionData RegionData;
2745
2746 ParallelCompactData& sd = PSParallelCompact::summary_data();
2747 const size_t region_size = ParallelCompactData::RegionSize;
2748
2749 size_t src_region_idx = 0;
2750
2751 // Skip empty regions (if any) up to the top of the space.
2752 HeapWord* const src_aligned_up = sd.region_align_up(end_addr);
2753 RegionData* src_region_ptr = sd.addr_to_region_ptr(src_aligned_up);
2754 HeapWord* const top_aligned_up = sd.region_align_up(src_space_top);
2755 const RegionData* const top_region_ptr =
2756 sd.addr_to_region_ptr(top_aligned_up);
2757 while (src_region_ptr < top_region_ptr && src_region_ptr->data_size() == 0) {
2758 ++src_region_ptr;
2759 }
2760
2761 if (src_region_ptr < top_region_ptr) {
2762 // The next source region is in the current space. Update src_region_idx
2763 // and the source address to match src_region_ptr.
2764 src_region_idx = sd.region(src_region_ptr);
2765 HeapWord* const src_region_addr = sd.region_to_addr(src_region_idx);
2766 if (src_region_addr > closure.source()) {
2767 closure.set_source(src_region_addr);
2768 }
2769 return src_region_idx;
2770 }
2771
2772 // Switch to a new source space and find the first non-empty region.
2773 unsigned int space_id = src_space_id + 1;
2774 assert(space_id < last_space_id, "not enough spaces");
2775
2776 HeapWord* const destination = closure.destination();
2777
2778 do {
2779 MutableSpace* space = _space_info[space_id].space();
2780 HeapWord* const bottom = space->bottom();
2781 const RegionData* const bottom_cp = sd.addr_to_region_ptr(bottom);
2782
2783 // Iterate over the spaces that do not compact into themselves.
2784 if (bottom_cp->destination() != bottom) {
2785 HeapWord* const top_aligned_up = sd.region_align_up(space->top());
2786 const RegionData* const top_cp = sd.addr_to_region_ptr(top_aligned_up);
2787
2788 for (const RegionData* src_cp = bottom_cp; src_cp < top_cp; ++src_cp) {
2789 if (src_cp->live_obj_size() > 0) {
2790 // Found it.
2791 assert(src_cp->destination() == destination,
2792 "first live obj in the space must match the destination");
2793 assert(src_cp->partial_obj_size() == 0,
2794 "a space cannot begin with a partial obj");
2795
2796 src_space_id = SpaceId(space_id);
2797 src_space_top = space->top();
2798 const size_t src_region_idx = sd.region(src_cp);
2799 closure.set_source(sd.region_to_addr(src_region_idx));
2800 return src_region_idx;
2801 } else {
2802 assert(src_cp->data_size() == 0, "sanity");
2803 }
2804 }
2805 }
2806 } while (++space_id < last_space_id);
2807
2808 assert(false, "no source region was found");
2809 return 0;
2810 }
2811
2812 void PSParallelCompact::fill_region(ParCompactionManager* cm, size_t region_idx)
2813 {
2814 typedef ParMarkBitMap::IterationStatus IterationStatus;
2815 const size_t RegionSize = ParallelCompactData::RegionSize;
2816 ParMarkBitMap* const bitmap = mark_bitmap();
2817 ParallelCompactData& sd = summary_data();
2818 RegionData* const region_ptr = sd.region(region_idx);
2819
2820 // Get the items needed to construct the closure.
2821 HeapWord* dest_addr = sd.region_to_addr(region_idx);
2822 SpaceId dest_space_id = space_id(dest_addr);
2823 ObjectStartArray* start_array = _space_info[dest_space_id].start_array();
2824 HeapWord* new_top = _space_info[dest_space_id].new_top();
2825 assert(dest_addr < new_top, "sanity");
2826 const size_t words = MIN2(pointer_delta(new_top, dest_addr), RegionSize);
2827
2828 // Get the source region and related info.
2829 size_t src_region_idx = region_ptr->source_region();
2830 SpaceId src_space_id = space_id(sd.region_to_addr(src_region_idx));
2831 HeapWord* src_space_top = _space_info[src_space_id].space()->top();
2832
2833 MoveAndUpdateClosure closure(bitmap, cm, start_array, dest_addr, words);
2834 closure.set_source(first_src_addr(dest_addr, src_space_id, src_region_idx));
2835
2836 // Adjust src_region_idx to prepare for decrementing destination counts (the
2837 // destination count is not decremented when a region is copied to itself).
2838 if (src_region_idx == region_idx) {
2839 src_region_idx += 1;
2840 }
2841
2842 if (bitmap->is_unmarked(closure.source())) {
2843 // The first source word is in the middle of an object; copy the remainder
2844 // of the object or as much as will fit. The fact that pointer updates were
2845 // deferred will be noted when the object header is processed.
2846 HeapWord* const old_src_addr = closure.source();
2847 closure.copy_partial_obj();
2848 if (closure.is_full()) {
2849 decrement_destination_counts(cm, src_space_id, src_region_idx,
2850 closure.source());
2851 region_ptr->set_deferred_obj_addr(NULL);
2852 region_ptr->set_completed();
2853 return;
2854 }
2855
2856 HeapWord* const end_addr = sd.region_align_down(closure.source());
2857 if (sd.region_align_down(old_src_addr) != end_addr) {
2858 // The partial object was copied from more than one source region.
2859 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
2860
2861 // Move to the next source region, possibly switching spaces as well. All
2862 // args except end_addr may be modified.
2863 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
2864 end_addr);
2865 }
2866 }
2867
2868 do {
2869 HeapWord* const cur_addr = closure.source();
2870 HeapWord* const end_addr = MIN2(sd.region_align_up(cur_addr + 1),
2871 src_space_top);
2872 IterationStatus status = bitmap->iterate(&closure, cur_addr, end_addr);
2873
2874 if (status == ParMarkBitMap::incomplete) {
2875 // The last obj that starts in the source region does not end in the
2876 // region.
2877 assert(closure.source() < end_addr, "sanity");
2878 HeapWord* const obj_beg = closure.source();
2879 HeapWord* const range_end = MIN2(obj_beg + closure.words_remaining(),
2880 src_space_top);
2881 HeapWord* const obj_end = bitmap->find_obj_end(obj_beg, range_end);
2882 if (obj_end < range_end) {
2883 // The end was found; the entire object will fit.
2884 status = closure.do_addr(obj_beg, bitmap->obj_size(obj_beg, obj_end));
2885 assert(status != ParMarkBitMap::would_overflow, "sanity");
2886 } else {
2887 // The end was not found; the object will not fit.
2888 assert(range_end < src_space_top, "obj cannot cross space boundary");
2889 status = ParMarkBitMap::would_overflow;
2890 }
2891 }
2892
2893 if (status == ParMarkBitMap::would_overflow) {
2894 // The last object did not fit. Note that interior oop updates were
2895 // deferred, then copy enough of the object to fill the region.
2896 region_ptr->set_deferred_obj_addr(closure.destination());
2897 status = closure.copy_until_full(); // copies from closure.source()
2898
2899 decrement_destination_counts(cm, src_space_id, src_region_idx,
2900 closure.source());
2901 region_ptr->set_completed();
2902 return;
2903 }
2904
2905 if (status == ParMarkBitMap::full) {
2906 decrement_destination_counts(cm, src_space_id, src_region_idx,
2907 closure.source());
2908 region_ptr->set_deferred_obj_addr(NULL);
2909 region_ptr->set_completed();
2910 return;
2911 }
2912
2913 decrement_destination_counts(cm, src_space_id, src_region_idx, end_addr);
2914
2915 // Move to the next source region, possibly switching spaces as well. All
2916 // args except end_addr may be modified.
2917 src_region_idx = next_src_region(closure, src_space_id, src_space_top,
2918 end_addr);
2919 } while (true);
2920 }
2921
2922 void PSParallelCompact::fill_blocks(size_t region_idx)
2923 {
2924 // Fill in the block table elements for the specified region. Each block
2925 // table element holds the number of live words in the region that are to the
2926 // left of the first object that starts in the block. Thus only blocks in
2927 // which an object starts need to be filled.
2928 //
2929 // The algorithm scans the section of the bitmap that corresponds to the
2930 // region, keeping a running total of the live words. When an object start is
2931 // found, if it's the first to start in the block that contains it, the
2932 // current total is written to the block table element.
2933 const size_t Log2BlockSize = ParallelCompactData::Log2BlockSize;
2934 const size_t Log2RegionSize = ParallelCompactData::Log2RegionSize;
2935 const size_t RegionSize = ParallelCompactData::RegionSize;
2936
2937 ParallelCompactData& sd = summary_data();
2938 const size_t partial_obj_size = sd.region(region_idx)->partial_obj_size();
2939 if (partial_obj_size >= RegionSize) {
2940 return; // No objects start in this region.
2941 }
2942
2943 // Ensure the first loop iteration decides that the block has changed.
2944 size_t cur_block = sd.block_count();
2945
2946 const ParMarkBitMap* const bitmap = mark_bitmap();
2947
2948 const size_t Log2BitsPerBlock = Log2BlockSize - LogMinObjAlignment;
2949 assert((size_t)1 << Log2BitsPerBlock ==
2950 bitmap->words_to_bits(ParallelCompactData::BlockSize), "sanity");
2951
2952 size_t beg_bit = bitmap->words_to_bits(region_idx << Log2RegionSize);
2953 const size_t range_end = beg_bit + bitmap->words_to_bits(RegionSize);
2954 size_t live_bits = bitmap->words_to_bits(partial_obj_size);
2955 beg_bit = bitmap->find_obj_beg(beg_bit + live_bits, range_end);
2956 while (beg_bit < range_end) {
2957 const size_t new_block = beg_bit >> Log2BitsPerBlock;
2958 if (new_block != cur_block) {
2959 cur_block = new_block;
2960 sd.block(cur_block)->set_offset(bitmap->bits_to_words(live_bits));
2961 }
2962
2963 const size_t end_bit = bitmap->find_obj_end(beg_bit, range_end);
2964 if (end_bit < range_end - 1) {
2965 live_bits += end_bit - beg_bit + 1;
2966 beg_bit = bitmap->find_obj_beg(end_bit + 1, range_end);
2967 } else {
2968 return;
2969 }
2970 }
2971 }
2972
2973 void
2974 PSParallelCompact::move_and_update(ParCompactionManager* cm, SpaceId space_id) {
2975 const MutableSpace* sp = space(space_id);
2976 if (sp->is_empty()) {
2977 return;
2978 }
2979
2980 ParallelCompactData& sd = PSParallelCompact::summary_data();
2981 ParMarkBitMap* const bitmap = mark_bitmap();
2982 HeapWord* const dp_addr = dense_prefix(space_id);
2983 HeapWord* beg_addr = sp->bottom();
2984 HeapWord* end_addr = sp->top();
2985
2986 assert(beg_addr <= dp_addr && dp_addr <= end_addr, "bad dense prefix");
2987
2988 const size_t beg_region = sd.addr_to_region_idx(beg_addr);
2989 const size_t dp_region = sd.addr_to_region_idx(dp_addr);
2990 if (beg_region < dp_region) {
2991 update_and_deadwood_in_dense_prefix(cm, space_id, beg_region, dp_region);
2992 }
2993
2994 // The destination of the first live object that starts in the region is one
2995 // past the end of the partial object entering the region (if any).
2996 HeapWord* const dest_addr = sd.partial_obj_end(dp_region);
2997 HeapWord* const new_top = _space_info[space_id].new_top();
2998 assert(new_top >= dest_addr, "bad new_top value");
2999 const size_t words = pointer_delta(new_top, dest_addr);
3000
3001 if (words > 0) {
3002 ObjectStartArray* start_array = _space_info[space_id].start_array();
3003 MoveAndUpdateClosure closure(bitmap, cm, start_array, dest_addr, words);
3004
3005 ParMarkBitMap::IterationStatus status;
3006 status = bitmap->iterate(&closure, dest_addr, end_addr);
3007 assert(status == ParMarkBitMap::full, "iteration not complete");
3008 assert(bitmap->find_obj_beg(closure.source(), end_addr) == end_addr,
3009 "live objects skipped because closure is full");
3010 }
3011 }
3012
3013 jlong PSParallelCompact::millis_since_last_gc() {
3014 // We need a monotonically non-decreasing time in ms but
3015 // os::javaTimeMillis() does not guarantee monotonicity.
3016 jlong now = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3017 jlong ret_val = now - _time_of_last_gc;
3018 // XXX See note in genCollectedHeap::millis_since_last_gc().
3019 if (ret_val < 0) {
3020 NOT_PRODUCT(warning("time warp: " JLONG_FORMAT, ret_val);)
3021 return 0;
3022 }
3023 return ret_val;
3024 }
3025
3026 void PSParallelCompact::reset_millis_since_last_gc() {
3027 // We need a monotonically non-decreasing time in ms but
3028 // os::javaTimeMillis() does not guarantee monotonicity.
3029 _time_of_last_gc = os::javaTimeNanos() / NANOSECS_PER_MILLISEC;
3030 }
3031
3032 ParMarkBitMap::IterationStatus MoveAndUpdateClosure::copy_until_full()
3033 {
3034 if (source() != destination()) {
3035 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3036 Copy::aligned_conjoint_words(source(), destination(), words_remaining());
3037 }
3038 update_state(words_remaining());
3039 assert(is_full(), "sanity");
3040 return ParMarkBitMap::full;
3041 }
3042
3043 void MoveAndUpdateClosure::copy_partial_obj()
3044 {
3045 size_t words = words_remaining();
3046
3047 HeapWord* const range_end = MIN2(source() + words, bitmap()->region_end());
3048 HeapWord* const end_addr = bitmap()->find_obj_end(source(), range_end);
3049 if (end_addr < range_end) {
3050 words = bitmap()->obj_size(source(), end_addr);
3051 }
3052
3053 // This test is necessary; if omitted, the pointer updates to a partial object
3054 // that crosses the dense prefix boundary could be overwritten.
3055 if (source() != destination()) {
3056 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3057 Copy::aligned_conjoint_words(source(), destination(), words);
3058 }
3059 update_state(words);
3060 }
3061
3062 void InstanceKlass::oop_pc_update_pointers(oop obj) {
3063 oop_oop_iterate_oop_maps<true>(obj, PSParallelCompact::adjust_pointer_closure());
3064 }
3065
3066 void InstanceMirrorKlass::oop_pc_update_pointers(oop obj) {
3067 InstanceKlass::oop_pc_update_pointers(obj);
3068
3069 oop_oop_iterate_statics<true>(obj, PSParallelCompact::adjust_pointer_closure());
3070 }
3071
3072 void InstanceClassLoaderKlass::oop_pc_update_pointers(oop obj) {
3073 InstanceKlass::oop_pc_update_pointers(obj);
3074 }
3075
3076 #ifdef ASSERT
3077 template <class T> static void trace_reference_gc(const char *s, oop obj,
3078 T* referent_addr,
3079 T* next_addr,
3080 T* discovered_addr) {
3081 log_develop(gc, ref)("%s obj " PTR_FORMAT, s, p2i(obj));
3082 log_develop(gc, ref)(" referent_addr/* " PTR_FORMAT " / " PTR_FORMAT,
3083 p2i(referent_addr), referent_addr ? p2i(oopDesc::load_decode_heap_oop(referent_addr)) : NULL);
3084 log_develop(gc, ref)(" next_addr/* " PTR_FORMAT " / " PTR_FORMAT,
3085 p2i(next_addr), next_addr ? p2i(oopDesc::load_decode_heap_oop(next_addr)) : NULL);
3086 log_develop(gc, ref)(" discovered_addr/* " PTR_FORMAT " / " PTR_FORMAT,
3087 p2i(discovered_addr), discovered_addr ? p2i(oopDesc::load_decode_heap_oop(discovered_addr)) : NULL);
3088 }
3089 #endif
3090
3091 template <class T>
3092 static void oop_pc_update_pointers_specialized(oop obj) {
3093 T* referent_addr = (T*)java_lang_ref_Reference::referent_addr(obj);
3094 PSParallelCompact::adjust_pointer(referent_addr);
3095 T* next_addr = (T*)java_lang_ref_Reference::next_addr(obj);
3096 PSParallelCompact::adjust_pointer(next_addr);
3097 T* discovered_addr = (T*)java_lang_ref_Reference::discovered_addr(obj);
3098 PSParallelCompact::adjust_pointer(discovered_addr);
3099 debug_only(trace_reference_gc("InstanceRefKlass::oop_update_ptrs", obj,
3100 referent_addr, next_addr, discovered_addr);)
3101 }
3102
3103 void InstanceRefKlass::oop_pc_update_pointers(oop obj) {
3104 InstanceKlass::oop_pc_update_pointers(obj);
3105
3106 if (UseCompressedOops) {
3107 oop_pc_update_pointers_specialized<narrowOop>(obj);
3108 } else {
3109 oop_pc_update_pointers_specialized<oop>(obj);
3110 }
3111 }
3112
3113 void ObjArrayKlass::oop_pc_update_pointers(oop obj) {
3114 assert(obj->is_objArray(), "obj must be obj array");
3115 oop_oop_iterate_elements<true>(objArrayOop(obj), PSParallelCompact::adjust_pointer_closure());
3116 }
3117
3118 void TypeArrayKlass::oop_pc_update_pointers(oop obj) {
3119 assert(obj->is_typeArray(),"must be a type array");
3120 }
3121
3122 ParMarkBitMapClosure::IterationStatus
3123 MoveAndUpdateClosure::do_addr(HeapWord* addr, size_t words) {
3124 assert(destination() != NULL, "sanity");
3125 assert(bitmap()->obj_size(addr) == words, "bad size");
3126
3127 _source = addr;
3128 assert(PSParallelCompact::summary_data().calc_new_pointer(source()) ==
3129 destination(), "wrong destination");
3130
3131 if (words > words_remaining()) {
3132 return ParMarkBitMap::would_overflow;
3133 }
3134
3135 // The start_array must be updated even if the object is not moving.
3136 if (_start_array != NULL) {
3137 _start_array->allocate_block(destination());
3138 }
3139
3140 if (destination() != source()) {
3141 DEBUG_ONLY(PSParallelCompact::check_new_location(source(), destination());)
3142 Copy::aligned_conjoint_words(source(), destination(), words);
3143 }
3144
3145 oop moved_oop = (oop) destination();
3146 compaction_manager()->update_contents(moved_oop);
3147 assert(moved_oop->is_oop_or_null(), "Expected an oop or NULL at " PTR_FORMAT, p2i(moved_oop));
3148
3149 update_state(words);
3150 assert(destination() == (HeapWord*)moved_oop + moved_oop->size(), "sanity");
3151 return is_full() ? ParMarkBitMap::full : ParMarkBitMap::incomplete;
3152 }
3153
3154 UpdateOnlyClosure::UpdateOnlyClosure(ParMarkBitMap* mbm,
3155 ParCompactionManager* cm,
3156 PSParallelCompact::SpaceId space_id) :
3157 ParMarkBitMapClosure(mbm, cm),
3158 _space_id(space_id),
3159 _start_array(PSParallelCompact::start_array(space_id))
3160 {
3161 }
3162
3163 // Updates the references in the object to their new values.
3164 ParMarkBitMapClosure::IterationStatus
3165 UpdateOnlyClosure::do_addr(HeapWord* addr, size_t words) {
3166 do_addr(addr);
3167 return ParMarkBitMap::incomplete;
3168 }