1 /*
2 * Copyright (c) 2017, Red Hat, Inc. and/or its affiliates.
3 *
4 * This code is free software; you can redistribute it and/or modify it
5 * under the terms of the GNU General Public License version 2 only, as
6 * published by the Free Software Foundation.
7 *
8 * This code is distributed in the hope that it will be useful, but WITHOUT
9 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
10 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
11 * version 2 for more details (a copy is included in the LICENSE file that
12 * accompanied this code).
13 *
14 * You should have received a copy of the GNU General Public License version
15 * 2 along with this work; if not, write to the Free Software Foundation,
16 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
17 *
18 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
19 * or visit www.oracle.com if you need additional information or have any
20 * questions.
21 *
22 */
23
24 #include "precompiled.hpp"
25 #include "gc/shared/gcTraceTime.inline.hpp"
26 #include "gc/shared/workgroup.hpp"
27 #include "gc/shared/taskqueue.inline.hpp"
28 #include "gc/shenandoah/shenandoahBarrierSet.hpp"
29 #include "gc/shenandoah/shenandoahCollectionSet.hpp"
30 #include "gc/shenandoah/shenandoahConnectionMatrix.inline.hpp"
31 #include "gc/shenandoah/shenandoahFreeSet.hpp"
32 #include "gc/shenandoah/shenandoahHeapRegionSet.hpp"
33 #include "gc/shenandoah/shenandoahHeap.inline.hpp"
34 #include "gc/shenandoah/shenandoahPartialGC.hpp"
35 #include "gc/shenandoah/shenandoahRootProcessor.hpp"
36 #include "gc/shenandoah/shenandoahTaskqueue.hpp"
37 #include "memory/iterator.hpp"
38
39 class PartialEvacuateUpdateRootsClosure : public OopClosure {
40 ShenandoahPartialGC* _partial_gc;
41 Thread* _thread;
42 SCMObjToScanQueue* _queue;
43 private:
44 template <class T>
45 void do_oop_work(T* p) { _partial_gc->process_oop<T, false>(p, _thread, _queue); }
46 public:
47 PartialEvacuateUpdateRootsClosure(SCMObjToScanQueue* q) :
48 _partial_gc(ShenandoahHeap::heap()->partial_gc()),
49 _thread(Thread::current()), _queue(q) {}
50 void do_oop(oop* p) {
51 assert(! ShenandoahHeap::heap()->is_in_reserved(p), "sanity");
52 do_oop_work(p);
53 }
54 void do_oop(narrowOop* p) { do_oop_work(p); }
55 };
56
57 class PartialEvacuateUpdateHeapClosure : public ExtendedOopClosure {
58 ShenandoahPartialGC* _partial_gc;
59 Thread* _thread;
60 SCMObjToScanQueue* _queue;
61 private:
62 template <class T>
63 void do_oop_work(T* p) {
64 _partial_gc->process_oop<T, true>(p, _thread, _queue);
65 }
66 public:
67 PartialEvacuateUpdateHeapClosure(SCMObjToScanQueue* q) :
68 _partial_gc(ShenandoahHeap::heap()->partial_gc()),
69 _thread(Thread::current()), _queue(q) {}
70 void do_oop(oop* p) { do_oop_work(p); }
71 void do_oop(narrowOop* p) { do_oop_work(p); }
72 };
73
74 class ShenandoahPartialCollectionTask : public AbstractGangTask {
75 private:
76 ShenandoahRootProcessor* _rp;
77 ParallelTaskTerminator* _terminator;
78 ShenandoahHeapRegionSet* _root_regions;
79 ShenandoahHeap* _heap;
80 public:
81 ShenandoahPartialCollectionTask(ShenandoahRootProcessor* rp,
82 ParallelTaskTerminator* terminator,
83 ShenandoahHeapRegionSet* root_regions) :
84 AbstractGangTask("Shenandoah Partial Collection"),
85 _rp(rp), _terminator(terminator), _root_regions(root_regions),
86 _heap(ShenandoahHeap::heap()) {}
87
88 void work(uint worker_id) {
89 ShenandoahConnectionMatrix* matrix = _heap->connection_matrix();
90 SCMObjToScanQueueSet* queues = _heap->partial_gc()->task_queues();
91 SCMObjToScanQueue* q = queues->queue(worker_id);
92
93 // Step 1: Process ordinary GC roots.
94 {
95 PartialEvacuateUpdateRootsClosure roots_cl(q);
96 CLDToOopClosure cld_cl(&roots_cl);
97 MarkingCodeBlobClosure code_cl(&roots_cl, CodeBlobToOopClosure::FixRelocations);
98 _rp->process_all_roots(&roots_cl, &roots_cl, &cld_cl, &code_cl, worker_id);
99 }
100 if (check_and_handle_cancelled_gc()) return;
101
102 PartialEvacuateUpdateHeapClosure cl(q);
103
104 // Step 2: Process all root regions.
105 {
106 ShenandoahHeapRegion* r = _root_regions->claim_next();
107 while (r != NULL) {
108 assert(r->is_root(), "must be root region");
109 if (! r->is_humongous_continuation()) {
110 _heap->marked_object_oop_iterate(r, &cl);
111 }
112 r->set_root(false);
113 if (check_and_handle_cancelled_gc()) return;
114 r = _root_regions->claim_next();
115 }
116 }
117 if (check_and_handle_cancelled_gc()) return;
118
119 // Step 3: Drain all outstanding work in queues.
120 {
121 int seed = 17;
122 SCMTask task;
123
124 uint stride = ShenandoahMarkLoopStride;
125
126 while (true) {
127 if (check_and_handle_cancelled_gc()) return;
128
129 for (uint i = 0; i < stride; i++) {
130 if ((q->pop_buffer(task) ||
131 q->pop_local(task) ||
132 q->pop_overflow(task) ||
133 queues->steal(worker_id, &seed, task))) {
134 oop obj = task.obj();
135 assert(!oopDesc::is_null(obj), "must not be null");
136 obj->oop_iterate(&cl);
137 } else {
138 if (_terminator->offer_termination()) return;
139 }
140 }
141 }
142 }
143 }
144
145 private:
146 bool check_and_handle_cancelled_gc() {
147 if (_heap->cancelled_concgc()) {
148 ShenandoahCancelledTerminatorTerminator tt;
149 while (! _terminator->offer_termination(&tt));
150 return true;
151 }
152 return false;
153 }
154 };
155
156 ShenandoahPartialGC::ShenandoahPartialGC(ShenandoahHeap* heap, size_t max_regions) :
157 _heap(heap),
158 _matrix(heap->connection_matrix()),
159 _root_regions(new ShenandoahHeapRegionSet(max_regions)),
160 _task_queues(new SCMObjToScanQueueSet(heap->max_workers())) {
161
162 assert(_matrix != NULL, "need matrix");
163
164 uint num_queues = heap->max_workers();
165 for (uint i = 0; i < num_queues; ++i) {
166 SCMObjToScanQueue* task_queue = new SCMObjToScanQueue();
167 task_queue->initialize();
168 _task_queues->register_queue(i, task_queue);
169 }
170
171 }
172
173 void ShenandoahPartialGC::prepare() {
174
175 if (ShenandoahVerify || VerifyShenandoahMatrix) {
176 log_debug(gc, ergo)("Verifying before partial collection");
177 _heap->verify_heap_reachable_at_safepoint();
178 log_debug(gc, ergo)("Verification passed");
179 }
180
181 _heap->collection_set()->clear();
182 assert(_heap->collection_set()->count() == 0, "collection set not clear");
183
184 _heap->ensure_parsability(true);
185
186 ShenandoahConnectionMatrix* matrix = _heap->connection_matrix();
187 ShenandoahHeapRegionSet* regions = _heap->regions();
188 ShenandoahCollectionSet* collection_set = _heap->collection_set();
189 ShenandoahFreeSet* free_set = _heap->free_regions();
190 free_set->clear();
191 _root_regions->clear();
192 assert(_root_regions->count() == 0, "must be cleared");
193 size_t num_regions = _heap->num_regions();
194
195 // First pass: find collection set.
196 for (uint to_idx = 0; to_idx < num_regions; to_idx++) {
197 ShenandoahHeapRegion* region = regions->get(to_idx);
198 region->set_root(false);
199 guarantee(! region->is_root(), "must not be root here");
200 if (region->is_humongous() || region->is_empty() || region->is_pinned()) continue;
201 assert(! _heap->region_in_collection_set(to_idx), "must not be in cset yet");
202 uint num_incoming = 0;
203 for (uint from_idx = 0; from_idx < num_regions; from_idx++) {
204 if (matrix->is_connected(from_idx, to_idx)) {
205 num_incoming++;
206 }
207 }
208 if (num_incoming < ShenandoahPartialInboundThreshold) {
209 collection_set->add_region(region);
210 _heap->set_region_in_collection_set(to_idx, true);
211 }
212 }
213
214 if (UseShenandoahMatrix && PrintShenandoahMatrix) {
215 outputStream* log = Log(gc)::info_stream();
216 matrix->print_on(log);
217 }
218
219 // Second pass: find all root regions.
220 size_t num_cset = collection_set->count();
221 for (uint idx = 0; idx < num_cset; idx++) {
222 ShenandoahHeapRegion* region = collection_set->get(idx);
223 size_t to_idx = region->region_number();
224 assert(! region->is_humongous() && ! region->is_empty() && ! region->is_pinned(), "sanity");
225 assert(_heap->region_in_collection_set(to_idx), "more sanity");
226 for (uint from_idx = 0; from_idx < num_regions; from_idx++) {
227 if (matrix->is_connected(from_idx, to_idx)) {
228 ShenandoahHeapRegion* r = regions->get(from_idx);
229 if (! r->is_root() && ! _heap->region_in_collection_set(from_idx)) {
230 _root_regions->add_region(r);
231 r->set_root(true);
232 }
233 }
234 }
235 }
236 // Final pass: free regions.
237 for (uint to_idx = 0; to_idx < num_regions; to_idx++) {
238 ShenandoahHeapRegion* region = regions->get(to_idx);
239 if (! region->is_humongous() &&
240 ! region->is_pinned() &&
241 ! region->is_root() &&
242 ! _heap->in_collection_set(region)) {
243
244 free_set->add_region(region);
245 }
246 if (region->is_root()) {
247 // We rebuild the outbound matrix for all roots, thus we can clear them before.
248 // This makes the matrix more precise.
249 matrix->clear_region_outbound(region->region_number());
250 }
251 }
252 log_debug(gc, ergo)("got "SIZE_FORMAT" cset regions", collection_set->count());
253 log_debug(gc, ergo)("got "SIZE_FORMAT" root regions", _root_regions->count());
254 }
255
256 void ShenandoahPartialGC::do_partial_collection() {
257
258 _heap->gc_timer()->register_gc_start();
259 ShenandoahCollectorPolicy* policy = _heap->shenandoahPolicy();
260 policy->record_phase_start(ShenandoahCollectorPolicy::partial_gc);
261
262 {
263 GCTraceTime(Info, gc) time("Pause Partial", _heap->gc_timer(), GCCause::_no_gc, true);
264
265 assert(_task_queues->is_empty(), "queues must be empty after partial GC");
266
267 COMPILER2_PRESENT(DerivedPointerTable::clear());
268
269 {
270 ClassLoaderDataGraph::clear_claimed_marks();
271 uint nworkers = _heap->workers()->active_workers();
272 ShenandoahRootProcessor rp(_heap, nworkers);
273
274 if (UseShenandoahOWST) {
275 ShenandoahTaskTerminator terminator(nworkers, task_queues());
276 ShenandoahPartialCollectionTask partial_task(&rp, &terminator, _root_regions);
277 _heap->workers()->run_task(&partial_task);
278 } else {
279 ParallelTaskTerminator terminator(nworkers, task_queues());
280 ShenandoahPartialCollectionTask partial_task(&rp, &terminator, _root_regions);
281 _heap->workers()->run_task(&partial_task);
282 }
283 }
284
285 COMPILER2_PRESENT(DerivedPointerTable::update_pointers());
286
287 if (_heap->cancelled_concgc()) {
288 _task_queues->clear();
289 }
290 assert(_task_queues->is_empty(), "queues must be empty after partial GC");
291
292 if (! _heap->cancelled_concgc()) {
293 if (ShenandoahVerify || VerifyShenandoahMatrix) {
294 log_debug(gc, ergo)("Verifying after partial collection");
295 _heap->verify_heap_reachable_at_safepoint();
296 log_debug(gc, ergo)("Verification passed");
297 }
298
299 ShenandoahHeap::ShenandoahHeapLock heap_lock(_heap);
300 size_t num_cset = _heap->collection_set()->count();
301 for (size_t i = 0; i < num_cset; i++) {
302 ShenandoahHeapRegion* r = _heap->collection_set()->get(i);
303 _heap->decrease_used(r->used());
304 HeapWord* bottom = r->bottom();
305 HeapWord* top = _heap->complete_top_at_mark_start(r->bottom());
306 if (top > bottom) {
307 _heap->complete_mark_bit_map()->clear_range_large(MemRegion(bottom, top));
308 }
309 r->recycle();
310 _heap->free_regions()->add_region(r);
311 }
312
313 reset();
314 }
315 }
316
317 policy->record_phase_end(ShenandoahCollectorPolicy::partial_gc);
318 _heap->gc_timer()->register_gc_end();
319 }
320
321 void ShenandoahPartialGC::reset() {
322 _heap->collection_set()->clear();
323 _heap->clear_cset_fast_test();
324 _root_regions->clear();
325 }
326
327 template <class T, bool UPDATE_MATRIX>
328 void ShenandoahPartialGC::process_oop(T* p, Thread* thread, SCMObjToScanQueue* queue) {
329 T o = oopDesc::load_heap_oop(p);
330 if (! oopDesc::is_null(o)) {
331 oop obj = oopDesc::decode_heap_oop_not_null(o);
332 if (_heap->in_collection_set(obj)) {
333 oop forw = ShenandoahBarrierSet::resolve_oop_static_not_null(obj);
334 if (oopDesc::unsafe_equals(obj, forw)) {
335 bool evacuated = false;
336 forw = _heap->evacuate_object(obj, thread, evacuated);
337
338 // Only the thread that succeeded evacuating this object pushes it to its work queue.
339 if (evacuated) {
340 assert(forw->is_oop(), "sanity");
341 bool succeeded = queue->push(SCMTask(forw));
342 assert(succeeded, "must succeed to push to task queue");
343 }
344 }
345 assert(! oopDesc::unsafe_equals(obj, forw) || _heap->cancelled_concgc(), "must be evacuated");
346 // Update reference.
347 oopDesc::encode_store_heap_oop_not_null(p, forw);
348 obj = forw; // For matrix update below.
349 }
350 if (UPDATE_MATRIX) {
351 #ifdef ASSERT
352 oop forw = ShenandoahBarrierSet::resolve_oop_static_not_null(obj);
353 assert(oopDesc::unsafe_equals(obj, forw) || _heap->cancelled_concgc(), "must not be evacuated: "PTR_FORMAT" -> "PTR_FORMAT, p2i(obj), p2i(forw));
354 #endif
355 _matrix->set_connected(p, obj);
356 }
357 }
358 }
359
360 SCMObjToScanQueueSet* ShenandoahPartialGC::task_queues() {
361 return _task_queues;
362 }