1 /*
2 * Copyright (c) 2017, Google 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
27 #include "gc/shared/collectedHeap.hpp"
28 #include "memory/universe.hpp"
29 #include "runtime/heapMonitoring.hpp"
30 #include "runtime/vframe.hpp"
31
32 static const int MaxStackDepth = 1024;
33
34 // Internal data structure representing traces.
35 struct StackTraceData : CHeapObj<mtInternal> {
36 jvmtiStackTrace *trace;
37 oop obj;
38 int references;
39
40 StackTraceData(jvmtiStackTrace *t, oop o) : trace(t), obj(o), references(0) {}
41
42 StackTraceData() : trace(NULL), obj(NULL), references(0) {}
43
44 // StackTraceDatas are shared around the board between various lists. So
45 // handle this by hand instead of having this in the destructor. There are
46 // cases where the struct is on the stack but holding heap data not to be
47 // freed.
48 static void free_data(StackTraceData *data) {
49 if (data->trace != NULL) {
50 FREE_C_HEAP_ARRAY(jvmtiFrameInfo, data->trace->frames);
51 FREE_C_HEAP_OBJ(data->trace);
52 }
53 delete data;
54 }
55 };
56
57 // Fixed size buffer for holding garbage traces.
58 class GarbageTracesBuffer : public CHeapObj<mtInternal> {
59 public:
60 GarbageTracesBuffer(uint32_t size) : _size(size) {
61 _garbage_traces = NEW_C_HEAP_ARRAY(StackTraceData*,
62 size,
63 mtInternal);
64 memset(_garbage_traces, 0, sizeof(StackTraceData*) * size);
65 }
66
67 virtual ~GarbageTracesBuffer() {
68 FREE_C_HEAP_ARRAY(StackTraceData*, _garbage_traces);
69 }
70
71 StackTraceData** get_traces() const {
72 return _garbage_traces;
73 }
74
75 bool store_trace(StackTraceData *trace) {
76 uint32_t index;
77 if (!select_replacement(&index)) {
78 return false;
79 }
80
81 StackTraceData *old_data = _garbage_traces[index];
82
83 if (old_data != NULL) {
84 old_data->references--;
85
86 if (old_data->references == 0) {
87 StackTraceData::free_data(old_data);
88 }
89 }
90
91 trace->references++;
92 _garbage_traces[index] = trace;
93 return true;
94 }
95
96 uint32_t size() const {
97 return _size;
98 }
99
100 protected:
101 // Subclasses select the trace to replace. Returns false if no replacement
102 // is to happen, otherwise stores the index of the trace to replace in
103 // *index.
104 virtual bool select_replacement(uint32_t *index) = 0;
105
106 const uint32_t _size;
107
108 private:
109 // The current garbage traces. A fixed-size ring buffer.
110 StackTraceData **_garbage_traces;
111 };
112
113 // Keep statistical sample of traces over the lifetime of the server.
114 // When the buffer is full, replace a random entry with probability
115 // 1/samples_seen. This strategy tends towards preserving the most frequently
116 // occuring traces over time.
117 class FrequentGarbageTraces : public GarbageTracesBuffer {
118 public:
119 FrequentGarbageTraces(int size)
120 : GarbageTracesBuffer(size),
121 _garbage_traces_pos(0),
122 _samples_seen(0) {
123 }
124
125 virtual ~FrequentGarbageTraces() {
126 }
127
128 virtual bool select_replacement(uint32_t* index) {
129 ++_samples_seen;
130
131 if (_garbage_traces_pos < _size) {
132 *index = _garbage_traces_pos++;
133 return true;
134 }
135
136 uint64_t random_uint64 =
137 (static_cast<uint64_t>(::random()) << 32) | ::random();
138
139 uint32_t random_index = random_uint64 % _samples_seen;
140 if (random_index < _size) {
141 *index = random_index;
142 return true;
143 }
144
145 return false;
146 }
147
148 private:
149 // The current position in the buffer as we initially fill it.
150 uint32_t _garbage_traces_pos;
151
152 uint64_t _samples_seen;
153 };
154
155 // Store most recent garbage traces.
156 class MostRecentGarbageTraces : public GarbageTracesBuffer {
157 public:
158 MostRecentGarbageTraces(int size)
159 : GarbageTracesBuffer(size),
160 _garbage_traces_pos(0) {
161 }
162
163 virtual ~MostRecentGarbageTraces() {
164 }
165
166 virtual bool select_replacement(uint32_t* index) {
167 *index = _garbage_traces_pos;
168
169 _garbage_traces_pos =
170 (_garbage_traces_pos + 1) % _size;
171
172 return true;
173 }
174
175 private:
176 // The current position in the buffer.
177 uint32_t _garbage_traces_pos;
178 };
179
180 // Each object that we profile is stored as trace with the thread_id.
181 class StackTraceStorage : public CHeapObj<mtInternal> {
182 public:
183 // The function that gets called to add a trace to the list of
184 // traces we are maintaining.
185 void add_trace(jvmtiStackTrace *trace, oop o);
186
187 // The function that gets called by the client to retrieve the list
188 // of stack traces. Passes a jvmtiStackTraces which will get mutated.
189 void get_all_stack_traces(jvmtiStackTraces *traces);
190
191 // The function that gets called by the client to retrieve the list
192 // of stack traces. Passes a jvmtiStackTraces which will get mutated.
193 void get_garbage_stack_traces(jvmtiStackTraces *traces);
194
195 // The function that gets called by the client to retrieve the list
196 // of stack traces. Passes a jvmtiStackTraces which will get mutated.
197 void get_frequent_garbage_stack_traces(jvmtiStackTraces *traces);
198
199 // Executes whenever weak references are traversed. is_alive tells
200 // you if the given oop is still reachable and live.
201 void weak_oops_do(BoolObjectClosure* is_alive, OopClosure *f);
202
203 ~StackTraceStorage();
204 StackTraceStorage();
205
206 static StackTraceStorage* storage() {
207 static StackTraceStorage internal_storage;
208 return &internal_storage;
209 }
210
211 void initialize(int max_storage) {
212 MutexLocker mu(HeapMonitor_lock);
213 free_storage();
214 allocate_storage(max_storage);
215 memset(&_stats, 0, sizeof(_stats));
216 }
217
218 const jvmtiHeapSamplingStats& get_heap_sampling_stats() const {
219 return _stats;
220 }
221
222 void accumulate_sample_rate(size_t rate) {
223 _stats.sample_rate_accumulation += rate;
224 _stats.sample_rate_count++;
225 }
226
227 bool initialized() { return _initialized; }
228
229 private:
230 // The traces currently sampled.
231 GrowableArray<StackTraceData> *_allocated_traces;
232
233 // Recent garbage traces.
234 MostRecentGarbageTraces *_recent_garbage_traces;
235
236 // Frequent garbage traces.
237 FrequentGarbageTraces *_frequent_garbage_traces;
238
239 // Heap Sampling statistics.
240 jvmtiHeapSamplingStats _stats;
241
242 // Maximum amount of storage provided by the JVMTI call initialize_profiling.
243 int _max_gc_storage;
244
245 static StackTraceStorage* internal_storage;
246 volatile bool _initialized;
247
248 // Support functions and classes for copying data to the external
249 // world.
250 class StackTraceDataCopier {
251 public:
252 virtual int size() const = 0;
253 virtual const StackTraceData *get(uint32_t i) const = 0;
254 };
255
256 class LiveStackTraceDataCopier : public StackTraceDataCopier {
257 public:
258 LiveStackTraceDataCopier(GrowableArray<StackTraceData> *data) :
259 _data(data) {}
260 int size() const { return _data ? _data->length() : 0; }
261 const StackTraceData *get(uint32_t i) const { return _data->adr_at(i); }
262
263 private:
264 GrowableArray<StackTraceData> *_data;
265 };
266
267 class GarbageStackTraceDataCopier : public StackTraceDataCopier {
268 public:
269 GarbageStackTraceDataCopier(StackTraceData **data, int size) :
270 _data(data), _size(size) {}
271 int size() const { return _size; }
272 const StackTraceData *get(uint32_t i) const { return _data[i]; }
273
274 private:
275 StackTraceData **_data;
276 int _size;
277 };
278
279 // Copies from StackTraceData to jvmtiStackTrace.
280 bool deep_copy(jvmtiStackTrace *to, const StackTraceData *from);
281
282 // Creates a deep copy of the list of StackTraceData.
283 void copy_stack_traces(const StackTraceDataCopier &copier,
284 jvmtiStackTraces *traces);
285
286 void store_garbage_trace(const StackTraceData &trace);
287
288 void free_garbage();
289 void free_storage();
290 void allocate_storage(int max_gc_storage);
291 };
292
293 StackTraceStorage* StackTraceStorage::internal_storage;
294
295 // Statics for Sampler
296 double HeapMonitoring::_log_table[1 << FastLogNumBits];
297 bool HeapMonitoring::_enabled;
298 AlwaysTrueClosure HeapMonitoring::_always_true;
299 jint HeapMonitoring::_monitoring_rate;
300
301 // Cheap random number generator
302 uint64_t HeapMonitoring::_rnd;
303
304 StackTraceStorage::StackTraceStorage() :
305 _allocated_traces(NULL),
306 _recent_garbage_traces(NULL),
307 _frequent_garbage_traces(NULL),
308 _max_gc_storage(0),
309 _initialized(false) {
310 }
311
312 void StackTraceStorage::free_garbage() {
313 StackTraceData **recent_garbage = NULL;
314 uint32_t recent_size = 0;
315
316 StackTraceData **frequent_garbage = NULL;
317 uint32_t frequent_size = 0;
318
319 if (_recent_garbage_traces != NULL) {
320 recent_garbage = _recent_garbage_traces->get_traces();
321 recent_size = _recent_garbage_traces->size();
322 }
323
324 if (_frequent_garbage_traces != NULL) {
325 frequent_garbage = _frequent_garbage_traces->get_traces();
326 frequent_size = _frequent_garbage_traces->size();
327 }
328
329 // Simple solution since this happens at exit.
330 // Go through the recent and remove any that only are referenced there.
331 for (uint32_t i = 0; i < recent_size; i++) {
332 StackTraceData *trace = recent_garbage[i];
333 if (trace != NULL) {
334 trace->references--;
335
336 if (trace->references == 0) {
337 StackTraceData::free_data(trace);
338 }
339 }
340 }
341
342 // Then go through the frequent and remove those that are now only there.
343 for (uint32_t i = 0; i < frequent_size; i++) {
344 StackTraceData *trace = frequent_garbage[i];
345 if (trace != NULL) {
346 trace->references--;
347
348 if (trace->references == 0) {
349 StackTraceData::free_data(trace);
350 }
351 }
352 }
353 }
354
355 void StackTraceStorage::free_storage() {
356 delete _allocated_traces;
357
358 free_garbage();
359 delete _recent_garbage_traces;
360 delete _frequent_garbage_traces;
361 _initialized = false;
362 }
363
364 StackTraceStorage::~StackTraceStorage() {
365 free_storage();
366 }
367
368 void StackTraceStorage::allocate_storage(int max_gc_storage) {
369 // In case multiple threads got locked and then 1 by 1 got through.
370 if (_initialized) {
371 return;
372 }
373
374 _allocated_traces = new (ResourceObj::C_HEAP, mtInternal)
375 GrowableArray<StackTraceData>(128, true);
376
377 _recent_garbage_traces = new MostRecentGarbageTraces(max_gc_storage);
378 _frequent_garbage_traces = new FrequentGarbageTraces(max_gc_storage);
379
380 _max_gc_storage = max_gc_storage;
381 _initialized = true;
382 }
383
384 void StackTraceStorage::add_trace(jvmtiStackTrace *trace, oop o) {
385 MutexLocker mu(HeapMonitor_lock);
386 StackTraceData new_data(trace, o);
387 _stats.sample_count++;
388 _stats.stack_depth_accumulation += trace->frame_count;
389 _allocated_traces->append(new_data);
390 }
391
392 void StackTraceStorage::weak_oops_do(BoolObjectClosure *is_alive,
393 OopClosure *f) {
394 MutexLocker mu(HeapMonitor_lock);
395 size_t count = 0;
396 if (initialized()) {
397 int len = _allocated_traces->length();
398
399 // Compact the oop traces. Moves the live oops to the beginning of the
400 // growable array, potentially overwriting the dead ones.
401 int curr_pos = 0;
402 for (int i = 0; i < len; i++) {
403 StackTraceData &trace = _allocated_traces->at(i);
404 oop value = trace.obj;
405 if (Universe::heap()->is_in_reserved(value)
406 && is_alive->do_object_b(value)) {
407 // Update the oop to point to the new object if it is still alive.
408 f->do_oop(&(trace.obj));
409
410 // Copy the old trace, if it is still live.
411 _allocated_traces->at_put(curr_pos++, trace);
412
413 count++;
414 } else {
415 // If the old trace is no longer live, add it to the list of
416 // recently collected garbage.
417 store_garbage_trace(trace);
418 }
419 }
420
421 // Zero out remaining array elements. Even though the call to trunc_to
422 // below truncates these values, zeroing them out is good practice.
423 StackTraceData zero_trace;
424 for (int i = curr_pos; i < len; i++) {
425 _allocated_traces->at_put(i, zero_trace);
426 }
427
428 // Set the array's length to the number of live elements.
429 _allocated_traces->trunc_to(curr_pos);
430 }
431
432 log_develop_trace(gc, ref)("Clearing HeapMonitoring weak reference (" INT64_FORMAT ")", count);
433 }
434
435 bool StackTraceStorage::deep_copy(jvmtiStackTrace *to,
436 const StackTraceData *from) {
437 const jvmtiStackTrace *src = from->trace;
438 *to = *src;
439
440 to->frames =
441 NEW_C_HEAP_ARRAY(jvmtiFrameInfo, src->frame_count, mtInternal);
442
443 if (to->frames == NULL) {
444 return false;
445 }
446
447 memcpy(to->frames,
448 src->frames,
449 sizeof(jvmtiFrameInfo) * src->frame_count);
450 return true;
451 }
452
453 // Called by the outside world; returns a copy of the stack traces
454 // (because we could be replacing them as the user handles them).
455 // The array is secretly null-terminated (to make it easier to reclaim).
456 void StackTraceStorage::get_all_stack_traces(jvmtiStackTraces *traces) {
457 LiveStackTraceDataCopier copier(_allocated_traces);
458 copy_stack_traces(copier, traces);
459 }
460
461 // See comment on get_all_stack_traces
462 void StackTraceStorage::get_garbage_stack_traces(jvmtiStackTraces *traces) {
463 GarbageStackTraceDataCopier copier(_recent_garbage_traces->get_traces(),
464 _recent_garbage_traces->size());
465 copy_stack_traces(copier, traces);
466 }
467
468 // See comment on get_all_stack_traces
469 void StackTraceStorage::get_frequent_garbage_stack_traces(
470 jvmtiStackTraces *traces) {
471 GarbageStackTraceDataCopier copier(_frequent_garbage_traces->get_traces(),
472 _frequent_garbage_traces->size());
473 copy_stack_traces(copier, traces);
474 }
475
476
477 void StackTraceStorage::copy_stack_traces(const StackTraceDataCopier &copier,
478 jvmtiStackTraces *traces) {
479 MutexLocker mu(HeapMonitor_lock);
480 int len = copier.size();
481
482 // Create a new array to store the StackTraceData objects.
483 // + 1 for a NULL at the end.
484 jvmtiStackTrace *t =
485 NEW_C_HEAP_ARRAY(jvmtiStackTrace, len + 1, mtInternal);
486 if (t == NULL) {
487 traces->stack_traces = NULL;
488 traces->trace_count = 0;
489 return;
490 }
491 // +1 to have a NULL at the end of the array.
492 memset(t, 0, (len + 1) * sizeof(*t));
493
494 // Copy the StackTraceData objects into the new array.
495 int trace_count = 0;
496 for (int i = 0; i < len; i++) {
497 const StackTraceData *stack_trace = copier.get(i);
498 if (stack_trace != NULL) {
499 jvmtiStackTrace *to = &t[trace_count];
500 if (!deep_copy(to, stack_trace)) {
501 continue;
502 }
503 trace_count++;
504 }
505 }
506
507 traces->stack_traces = t;
508 traces->trace_count = trace_count;
509 }
510
511 void StackTraceStorage::store_garbage_trace(const StackTraceData &trace) {
512 StackTraceData *new_trace = new StackTraceData();
513 *new_trace = trace;
514
515 bool accepted = _recent_garbage_traces->store_trace(new_trace);
516
517 // Accepted is on the right of the boolean to force the store_trace to happen.
518 accepted = _frequent_garbage_traces->store_trace(new_trace) || accepted;
519
520 if (!accepted) {
521 // No one wanted to use it.
522 delete new_trace;
523 }
524
525 _stats.garbage_collected_samples++;
526 }
527
528 void HeapMonitoring::get_live_traces(jvmtiStackTraces *traces) {
529 StackTraceStorage::storage()->get_all_stack_traces(traces);
530 }
531
532 void HeapMonitoring::get_sampling_statistics(jvmtiHeapSamplingStats *stats) {
533 const jvmtiHeapSamplingStats& internal_stats =
534 StackTraceStorage::storage()->get_heap_sampling_stats();
535 *stats = internal_stats;
536 }
537
538 void HeapMonitoring::get_frequent_garbage_traces(jvmtiStackTraces *traces) {
539 StackTraceStorage::storage()->get_frequent_garbage_stack_traces(traces);
540 }
541
542 void HeapMonitoring::get_garbage_traces(jvmtiStackTraces *traces) {
543 StackTraceStorage::storage()->get_garbage_stack_traces(traces);
544 }
545
546 void HeapMonitoring::release_traces(jvmtiStackTraces *traces) {
547 jint trace_count = traces->trace_count;
548 jvmtiStackTrace *stack_traces = traces->stack_traces;
549
550 for (jint i = 0; i < trace_count; i++) {
551 jvmtiStackTrace *current_trace = stack_traces + i;
552 FREE_C_HEAP_ARRAY(jvmtiFrameInfo, current_trace->frames);
553 }
554
555 FREE_C_HEAP_ARRAY(jvmtiStackTrace, traces->stack_traces);
556 traces->trace_count = 0;
557 traces->stack_traces = NULL;
558 }
559
560 // Invoked by the GC to clean up old stack traces and remove old arrays
561 // of instrumentation that are still lying around.
562 void HeapMonitoring::weak_oops_do(BoolObjectClosure* is_alive, OopClosure *f) {
563 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
564 StackTraceStorage::storage()->weak_oops_do(is_alive, f);
565 }
566
567 void HeapMonitoring::initialize_profiling(jint monitoring_rate,
568 jint max_gc_storage) {
569 // Ignore if already enabled.
570 if (_enabled) {
571 return;
572 }
573
574 _monitoring_rate = monitoring_rate;
575
576 // Populate the lookup table for fast_log2.
577 // This approximates the log2 curve with a step function.
578 // Steps have height equal to log2 of the mid-point of the step.
579 for (int i = 0; i < (1 << FastLogNumBits); i++) {
580 double half_way = static_cast<double>(i + 0.5);
581 _log_table[i] = (log(1.0 + half_way / (1 << FastLogNumBits)) / log(2.0));
582 }
583
584 JavaThread *t = static_cast<JavaThread *>(Thread::current());
585 _rnd = static_cast<uint32_t>(reinterpret_cast<uintptr_t>(t));
586 if (_rnd == 0) {
587 _rnd = 1;
588 }
589
590 StackTraceStorage::storage()->initialize(max_gc_storage);
591 _enabled = true;
592 }
593
594 void HeapMonitoring::stop_profiling() {
595 _enabled = false;
596 }
597
598 // Generates a geometric variable with the specified mean (512K by default).
599 // This is done by generating a random number between 0 and 1 and applying
600 // the inverse cumulative distribution function for an exponential.
601 // Specifically: Let m be the inverse of the sample rate, then
602 // the probability distribution function is m*exp(-mx) so the CDF is
603 // p = 1 - exp(-mx), so
604 // q = 1 - p = exp(-mx)
605 // log_e(q) = -mx
606 // -log_e(q)/m = x
607 // log_2(q) * (-log_e(2) * 1/m) = x
608 // In the code, q is actually in the range 1 to 2**26, hence the -26 below
609 void HeapMonitoring::pick_next_sample(size_t *ptr) {
610 _rnd = next_random(_rnd);
611 // Take the top 26 bits as the random number
612 // (This plus a 1<<58 sampling bound gives a max possible step of
613 // 5194297183973780480 bytes. In this case,
614 // for sample_parameter = 1<<19, max possible step is
615 // 9448372 bytes (24 bits).
616 const uint64_t prng_mod_power = 48; // Number of bits in prng
617 // The uint32_t cast is to prevent a (hard-to-reproduce) NAN
618 // under piii debug for some binaries.
619 double q = static_cast<uint32_t>(_rnd >> (prng_mod_power - 26)) + 1.0;
620 // Put the computed p-value through the CDF of a geometric.
621 // For faster performance (save ~1/20th exec time), replace
622 // min(0.0, FastLog2(q) - 26) by (Fastlog2(q) - 26.000705)
623 // The value 26.000705 is used rather than 26 to compensate
624 // for inaccuracies in FastLog2 which otherwise result in a
625 // negative answer.
626 double log_val = (fast_log2(q) - 26);
627 size_t rate = static_cast<size_t>(
628 (0.0 < log_val ? 0.0 : log_val) * (-log(2.0) * (_monitoring_rate)) + 1);
629 *ptr = rate;
630
631 StackTraceStorage::storage()->accumulate_sample_rate(rate);
632 }
633
634 void HeapMonitoring::object_alloc_do_sample(Thread *t, oopDesc *o, intx byte_size) {
635 #if defined(X86) || defined(PPC)
636 JavaThread *thread = static_cast<JavaThread *>(t);
637 if (StackTraceStorage::storage()->initialized()) {
638 assert(t->is_Java_thread(), "non-Java thread passed to do_sample");
639 JavaThread *thread = static_cast<JavaThread *>(t);
640
641 jvmtiStackTrace *trace = NEW_C_HEAP_OBJ(jvmtiStackTrace, mtInternal);
642 if (trace == NULL) {
643 return;
644 }
645
646 jvmtiFrameInfo *frames =
647 NEW_C_HEAP_ARRAY(jvmtiFrameInfo, MaxStackDepth, mtInternal);
648
649 if (frames == NULL) {
650 FREE_C_HEAP_OBJ(trace);
651 return;
652 }
653
654 trace->frames = frames;
655 trace->thread_id = SharedRuntime::get_java_tid(thread);
656 trace->size = byte_size;
657 trace->frame_count = 0;
658
659 if (thread->has_last_Java_frame()) { // just to be safe
660 vframeStream vfst(thread, true);
661 int count = 0;
662 while (!vfst.at_end() && count < MaxStackDepth) {
663 Method* m = vfst.method();
664 frames[count].location = vfst.bci();
665 frames[count].method = m->jmethod_id();
666 count++;
667
668 vfst.next();
669 }
670 trace->frame_count = count;
671 }
672
673 if (trace->frame_count> 0) {
674 // Success!
675 StackTraceStorage::storage()->add_trace(trace, o);
676 return;
677 }
678
679 // Failure!
680 FREE_C_HEAP_ARRAY(jvmtiFrameInfo, trace->frames);
681 FREE_C_HEAP_OBJ(trace);
682 }
683 #else
684 Unimplemented();
685 #endif
686 }