1 /*
2 * Copyright (c) 2017, 2019, Red Hat, Inc. All rights reserved.
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
26 #include "classfile/altHashing.hpp"
27 #include "gc_implementation/shenandoah/shenandoahCollectionSet.inline.hpp"
28 #include "gc_implementation/shenandoah/shenandoahHeap.inline.hpp"
29 #include "gc_implementation/shenandoah/shenandoahMarkingContext.inline.hpp"
30 #include "gc_implementation/shenandoah/shenandoahPhaseTimings.hpp"
31 #include "gc_implementation/shenandoah/shenandoahStrDedupQueue.inline.hpp"
32 #include "gc_implementation/shenandoah/shenandoahStrDedupTable.hpp"
33 #include "gc_implementation/shenandoah/shenandoahStrDedupThread.hpp"
34 #include "gc_implementation/shenandoah/shenandoahStringDedup.hpp"
35 #include "gc_implementation/shenandoah/shenandoahWorkGroup.hpp"
36 #include "gc_implementation/shenandoah/shenandoahUtils.hpp"
37 #include "runtime/os.hpp"
38 #include "utilities/workgroup.hpp"
39
40 ShenandoahStrDedupQueueSet* ShenandoahStringDedup::_queues = NULL;
41 ShenandoahStrDedupTable* ShenandoahStringDedup::_table = NULL;
42 ShenandoahStrDedupThread* ShenandoahStringDedup::_thread = NULL;
43 ShenandoahStrDedupStats ShenandoahStringDedup::_stats;
44 bool ShenandoahStringDedup::_enabled = false;
45
46 void ShenandoahStringDedup::initialize() {
47 if (UseStringDeduplication) {
48 _queues = new ShenandoahStrDedupQueueSet(ShenandoahHeap::heap()->max_workers());
49 _table = new ShenandoahStrDedupTable();
50 _thread = new ShenandoahStrDedupThread(_queues);
51 _enabled = true;
52 }
53 }
54
55 /* Enqueue candidates for deduplication.
56 * The method should only be called by GC worker threads, during concurrent marking phase.
57 */
58 void ShenandoahStringDedup::enqueue_candidate(oop java_string, ShenandoahStrDedupQueue* q) {
59 assert(Thread::current()->is_Worker_thread(), "Only be GC worker thread");
60
61 if (java_string->age() <= StringDeduplicationAgeThreshold) {
62 const markOop mark = java_string->mark();
63
64 // Having/had displaced header, too risk to deal with them, skip
65 if (mark == markOopDesc::INFLATING() || mark->has_displaced_mark_helper()) {
66 return;
67 }
68
69 // Increase string age and enqueue it when it rearches age threshold
70 markOop new_mark = mark->incr_age();
71 if (mark == java_string->cas_set_mark(new_mark, mark)) {
72 if (mark->age() == StringDeduplicationAgeThreshold) {
73 q->push(java_string);
74 }
75 }
76 }
77 }
78
79 // Deduplicate a string, return true if it is deduplicated.
80 bool ShenandoahStringDedup::deduplicate(oop java_string, bool update_counter) {
81 assert(is_candidate(java_string), "Not a candidate");
82 assert(_table != NULL, "Shenandoah Dedup table not initialized");
83 bool deduped = _table->deduplicate(java_string);
84
85 if (update_counter) {
86 dedup_stats().atomic_inc_inspected(1);
87 if (deduped) {
88 dedup_stats().atomic_inc_skipped(1);
89 } else {
90 dedup_stats().atomic_inc_known(1);
91 }
92 }
93 return deduped;
94 }
95
96 ShenandoahStrDedupQueue* ShenandoahStringDedup::queue(uint worker_id) {
97 assert(_queues != NULL, "QueueSet not initialized");
98 return _queues->queue_at(worker_id);
99 }
100
101 void ShenandoahStringDedup::threads_do(ThreadClosure* tc) {
102 assert(_thread != NULL, "Shenandoah Dedup Thread not initialized");
103 tc->do_thread(_thread);
104 }
105
106 void ShenandoahStringDedup::parallel_oops_do(ShenandoahPhaseTimings::Phase phase, OopClosure* cl, uint worker_id) {
107 {
108 ShenandoahWorkerTimingsTracker x(phase, ShenandoahPhaseTimings::StringDedupQueueRoots, worker_id);
109 _queues->parallel_oops_do(cl);
110 }
111
112 {
113 ShenandoahWorkerTimingsTracker x(phase, ShenandoahPhaseTimings::StringDedupTableRoots, worker_id);
114 _table->parallel_oops_do(cl);
115 }
116
117 {
118 ShenandoahWorkerTimingsTracker x(phase, ShenandoahPhaseTimings::StringDedupThreadRoots, worker_id);
119 _thread->parallel_oops_do(cl);
120 }
121 }
122
123 void ShenandoahStringDedup::oops_do_slow(OopClosure* cl) {
124 _queues->oops_do_slow(cl);
125 _table->oops_do_slow(cl);
126 _thread->oops_do_slow(cl);
127 }
128
129 class ShenandoahStrDedupCleanupTask : public AbstractGangTask {
130 private:
131 ShenandoahStrDedupQueueSet* _queues;
132 ShenandoahStrDedupThread* _thread;
133 ShenandoahStrDedupTable** _table;
134 ShenandoahStrDedupTable* _dest_table;
135
136 ShenandoahStrDedupTableCleanupTask* _dedup_table_cleanup_task;
137
138 public:
139 ShenandoahStrDedupCleanupTask(ShenandoahStrDedupQueueSet* qset,
140 ShenandoahStrDedupThread* thread, ShenandoahStrDedupTable** table)
141 : AbstractGangTask("Shenandoah dedup cleanup task"),
142 _queues(qset), _table(table), _thread(thread), _dest_table(NULL) {
143
144 ShenandoahStrDedupTable* the_table = *table;
145 bool rehash = the_table->need_rehash();
146 size_t table_size = the_table->size();
147 if (the_table->need_expand()) {
148 table_size *= 2;
149 table_size = MIN2(table_size, ShenandoahStrDedupTable::max_size());
150 } else if (the_table->need_shrink()) {
151 table_size /= 2;
152 table_size = MAX2(table_size, ShenandoahStrDedupTable::min_size());
153 }
154
155 if (rehash) {
156 _dest_table = new ShenandoahStrDedupTable(table_size, AltHashing::compute_seed());
157 _dedup_table_cleanup_task = new ShenandoahStrDedupTableRehashTask(the_table, _dest_table);
158 ShenandoahStringDedup::dedup_stats().inc_table_rehashed();
159 } else if (the_table->need_expand()) {
160 _dest_table = new ShenandoahStrDedupTable(table_size, the_table->hash_seed());
161 _dedup_table_cleanup_task = new ShenandoahStrDedupExpandTableTask(the_table, _dest_table);
162 ShenandoahStringDedup::dedup_stats().inc_table_expanded();
163 } else if (the_table->need_shrink()) {
164 _dest_table = new ShenandoahStrDedupTable(table_size, the_table->hash_seed());
165 _dedup_table_cleanup_task = new ShenandoahStrDedupShrinkTableTask(the_table, _dest_table);
166 ShenandoahStringDedup::dedup_stats().inc_table_shrinked();
167 } else {
168 _dedup_table_cleanup_task = new ShenandoahStrDedupTableUnlinkTask(the_table);
169 }
170 }
171
172 ~ShenandoahStrDedupCleanupTask() {
173 assert(_dedup_table_cleanup_task != NULL, "Should not be null");
174 delete _dedup_table_cleanup_task;
175
176 // Install new table
177 if (_dest_table != NULL) {
178 delete *_table;
179 *_table = _dest_table;
180 }
181
182 (*_table)->verify();
183 }
184
185 void work(uint worker_id) {
186 _queues->parallel_cleanup();
187 _thread->parallel_cleanup();
188 _dedup_table_cleanup_task->do_parallel_cleanup();
189 }
190 };
191
192 void ShenandoahStringDedup::parallel_cleanup() {
193 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
194 log_debug(gc, stringdedup)("String dedup cleanup");
195 ShenandoahStringDedup::clear_claimed();
196 ShenandoahStrDedupCleanupTask task(_queues, _thread, &_table);
197 ShenandoahHeap::heap()->workers()->run_task(&task);
198 }
199
200 void ShenandoahStringDedup::stop() {
201 assert(ShenandoahStringDedup::is_enabled(), "Must be enabled");
202 assert(_thread != NULL, "Not dedup thread");
203 _thread->stop();
204 }
205
206 void ShenandoahStringDedup::clear_claimed() {
207 assert(is_enabled(), "Must be enabled");
208 _queues->clear_claimed();
209 _table->clear_claimed();
210 _thread->clear_claimed();
211 }
212
213 void ShenandoahStringDedup::print_statistics(outputStream* out) {
214 assert(is_enabled(), "Must be enabled");
215
216 out->print_cr("Shenandoah String Dedup Statistics:");
217 dedup_stats().print_statistics(out);
218 _table->print_statistics(out);
219 }
220
221 ShenandoahStrDedupStats::ShenandoahStrDedupStats() :
222 _inspected(0), _deduped(0), _skipped(0), _known(0), _idle(0), _exec(0), _block(0),
223 _idle_elapsed(0), _exec_elapsed(0), _block_elapsed(0),
224 _start_phase(0), _start_concurrent(0), _end_concurrent(0),
225 _table_expanded_count(0), _table_shrinked_count(0), _table_rehashed_count(0) {
226 }
227
228 void ShenandoahStrDedupStats::atomic_inc_inspected(size_t count) {
229 Atomic::add((jlong)count, (volatile jlong*)&_inspected);
230 }
231
232 void ShenandoahStrDedupStats::atomic_inc_skipped(size_t count) {
233 Atomic::add((jlong)count, (volatile jlong*)&_skipped);
234 }
235
236 void ShenandoahStrDedupStats::atomic_inc_deduped(size_t count) {
237 Atomic::add((jlong)count, (volatile jlong*)&_deduped);
238 }
239
240 void ShenandoahStrDedupStats::atomic_inc_known(size_t count) {
241 Atomic::add((jlong)count, (volatile jlong*)&_known);
242 }
243
244 void ShenandoahStrDedupStats::mark_idle() {
245 assert_thread();
246 _start_phase = os::elapsedTime();
247 _idle++;
248 }
249
250 void ShenandoahStrDedupStats::mark_exec() {
251 assert_thread();
252 double now = os::elapsedTime();
253 _idle_elapsed = now - _start_phase;
254 _start_phase = now;
255 _start_concurrent = now;
256 _exec++;
257 }
258
259 void ShenandoahStrDedupStats::mark_block() {
260 assert_thread();
261 double now = os::elapsedTime();
262 _exec_elapsed += now - _start_phase;
263 _start_phase = now;
264 _block++;
265 }
266
267 void ShenandoahStrDedupStats::mark_unblock() {
268 assert_thread();
269 double now = os::elapsedTime();
270 _block_elapsed += now - _start_phase;
271 _start_phase = now;
272 }
273
274 void ShenandoahStrDedupStats::mark_done() {
275 assert_thread();
276 double now = os::elapsedTime();
277 _exec_elapsed += now - _start_phase;
278 _end_concurrent = now;
279 }
280
281 void ShenandoahStrDedupStats::update(const ShenandoahStrDedupStats& sts) {
282 assert_thread();
283 // Counters
284 atomic_inc_inspected(sts._inspected);
285 atomic_inc_deduped(sts._deduped);
286 atomic_inc_skipped(sts._skipped);
287 atomic_inc_known(sts._known);
288
289 _idle += sts._idle;
290 _exec += sts._exec;
291 _block += sts._block;
292
293 // Time spent by the deduplication thread in different phases
294 _idle_elapsed += sts._idle_elapsed;
295 _exec_elapsed += sts._exec_elapsed;
296 _block_elapsed += sts._block_elapsed;
297 }
298
299 void ShenandoahStrDedupStats::inc_table_expanded() {
300 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
301 assert(Thread::current() == VMThread::vm_thread(), "Only by VM thread");
302 _table_expanded_count ++;
303 }
304
305 void ShenandoahStrDedupStats::inc_table_shrinked() {
306 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
307 assert(Thread::current() == VMThread::vm_thread(), "Only by VM thread");
308 _table_shrinked_count ++;
309 }
310
311 void ShenandoahStrDedupStats::inc_table_rehashed() {
312 assert(SafepointSynchronize::is_at_safepoint(), "Must be at a safepoint");
313 assert(Thread::current() == VMThread::vm_thread(), "Only by VM thread");
314 _table_rehashed_count ++;
315 }
316
317 void ShenandoahStrDedupStats::print_statistics(outputStream* out) const {
318 out->print_cr(" Inspected: " SIZE_FORMAT_W(12), _inspected);
319 out->print_cr(" Skipped: " SIZE_FORMAT_W(12), _skipped);
320 out->print_cr(" Deduped: " SIZE_FORMAT_W(12), _deduped);
321 out->print_cr(" Known: " SIZE_FORMAT_W(12), _known);
322 out->cr();
323 out->print_cr(" Idle: " STRDEDUP_TIME_FORMAT_MS " Exec: " STRDEDUP_TIME_FORMAT_MS " Block: " STRDEDUP_TIME_FORMAT_MS,
324 STRDEDUP_TIME_PARAM_MS(_idle_elapsed), STRDEDUP_TIME_PARAM_MS(_exec_elapsed), STRDEDUP_TIME_PARAM_MS(_block_elapsed));
325 if (_table_expanded_count != 0 || _table_shrinked_count != 0 || _table_rehashed_count != 0) {
326 out->print_cr(" Table expanded: " SIZE_FORMAT " shrinked: " SIZE_FORMAT " rehashed: " SIZE_FORMAT,
327 _table_expanded_count, _table_shrinked_count, _table_rehashed_count);
328 }
329
330 out->cr();
331 }
332
333 #ifdef ASSERT
334 void ShenandoahStrDedupStats::assert_thread() {
335 assert(Thread::current() == ShenandoahStringDedup::_thread, "Can only be done by dedup thread");
336 }
337
338 #endif