1 /*
2 * Copyright (c) 2014, 2015, Dynatrace and/or its affiliates. All rights reserved.
3 *
4 * This file is part of the Lock Contention Tracing Subsystem for the HotSpot
5 * Virtual Machine, which is developed at Christian Doppler Laboratory on
6 * Monitoring and Evolution of Very-Large-Scale Software Systems. Please
7 * contact us at <http://mevss.jku.at/> if you need additional information
8 * or have any questions.
9 *
10 * This code is free software; you can redistribute it and/or modify it
11 * under the terms of the GNU General Public License version 2 only, as
12 * published by the Free Software Foundation.
13 *
14 * This code is distributed in the hope that it will be useful, but WITHOUT
15 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 * version 2 for more details (a copy is included in the LICENSE file that
18 * accompanied this code).
19 *
20 * You should have received a copy of the GNU General Public License version
21 * 2 along with this work. If not, see <http://www.gnu.org/licenses/>.
22 *
23 */
24
25 #include "evtrace/traceStack.hpp"
26
27 #include "evtrace/traceEvents.hpp"
28 #include "evtrace/traceMetadata.hpp"
29
30 #include "runtime/vframe.hpp"
31 #include "runtime/init.hpp"
32
33 //
34 // TraceStackBuilder
35 //
36
37 void TraceStackBuilder::add(const TraceStackFrame &f) {
38 assert(!is_full(), "already full");
39 _frames[_count] = f;
40 _hash ^= f.hash();
41 _count++;
42 }
43
44 void TraceStackBuilder::add_frame(const frame *fr) {
45 TraceStackFrame f;
46 f.is_compiled = fr->cb()->is_nmethod();
47 if (f.is_compiled) {
48 assert(fr->is_compiled_frame() || fr->is_native_frame(), "unsupported frame type");
49 f.compiled.pc = fr->pc();
50 f.compiled.nm = (nmethod *) fr->cb();
51 } else {
52 assert(fr->is_interpreted_frame(), "unsupported frame type");
53 f.interpreted.method = fr->interpreter_frame_method();
54 f.interpreted.bci = fr->interpreter_frame_bci();
55 }
56 add(f);
57 }
58
59 bool TraceStackBuilder::range_equals(size_t offset, const CachedTraceStack *cts, size_t cts_offset, size_t count) const {
60 for (size_t i = 0; i < count; i++) {
61 if (!frame_at(offset + i)->equals(*cts->frame_at(cts_offset + i))) {
62 return false;
63 }
64 }
65 return true;
66 }
67
68 //
69 // CachedTraceStack
70 //
71
72 CachedTraceStack *CachedTraceStack::create(TraceTypes::stack_id id, const CompositeTraceStack &ts) {
73 assert (in_bytes(byte_offset_of(CachedTraceStack, _frames)) == sizeof(CachedTraceStack),
74 "variable-sized frame array must be last field");
75 return new (ts.count()) CachedTraceStack(id, ts);
76 }
77
78 void* CachedTraceStack::operator new(size_t size, size_t nframes) throw () {
79 return CHeapObj<mtEventTracing>::operator new(size + sizeof(_frames[0]) * nframes, CALLER_PC);
80 }
81
82 void CachedTraceStack::operator delete(void* p) {
83 CHeapObj<mtEventTracing>::operator delete(p);
84 }
85
86 CachedTraceStack::CachedTraceStack(TraceTypes::stack_id id, const CompositeTraceStack& ts)
87 : _id(id),
88 _count(ts.count()),
89 _hash(ts.hash()),
90 _truncated(ts.is_truncated()),
91 _valid(true)
92 {
93 for (size_t i = 0; i < ts.count(); i++) {
94 _frames[i] = *ts.frame_at(i);
95 }
96 }
97
98 bool CachedTraceStack::has_interpreted_method_from_classloader(const ClassLoaderData* loader) const {
99 assert(is_valid(), "sanity");
100 for (size_t i = 0; i < _count; i++) {
101 if (!_frames[i].is_compiled && _frames[i].interpreted.method->method_holder()->class_loader_data() == loader) {
102 return true;
103 }
104 }
105 return false;
106 }
107
108 bool CachedTraceStack::has_nmethod(const nmethod *nm) const {
109 assert(is_valid(), "sanity");
110 for (size_t i = 0; i < _count; i++) {
111 if (_frames[i].is_compiled && _frames[i].compiled.nm == nm) {
112 return true;
113 }
114 }
115 return false;
116 }
117
118 bool CachedTraceStack::range_equals(size_t offset, const CachedTraceStack *other, size_t other_offset, size_t count) const {
119 for (size_t i = 0; i < count; i++) {
120 if (!frame_at(offset + i)->equals(*other->frame_at(other_offset + i))) {
121 return false;
122 }
123 }
124 return true;
125 }
126
127 //
128 // CompositeTraceStack
129 //
130
131 void CompositeTraceStack::set_bottom(const CachedTraceStack *bottom, size_t offset) {
132 _hash = _top.hash();
133 _count = _top.count();
134 _truncated = _top.is_truncated();
135
136 _bottom = bottom;
137 _bottom_offset = offset;
138 if (bottom != NULL) {
139 if (_top.count() < EventTracingStackDepthLimit) {
140 assert(!_top.is_truncated(), "missing frames between top and bottom");
141 _count += bottom->count() - offset;
142 _truncated = _truncated || bottom->is_truncated();
143 if (_count > EventTracingStackDepthLimit) {
144 _truncated = true;
145 _count = EventTracingStackDepthLimit;
146 }
147 _hash ^= bottom->hash();
148 // drop frames before offset from hash
149 for (size_t i = 0; i < offset; i++) {
150 _hash ^= bottom->frame_at(i)->hash();
151 }
152 // drop truncated frames from hash
153 for (size_t i = EventTracingStackDepthLimit - _top.count() + offset; i < _bottom->count(); i++) {
154 _hash ^= bottom->frame_at(i)->hash();
155 }
156 } else {
157 _truncated = _truncated || (bottom->count() > offset);
158 }
159 }
160
161 #ifdef ASSERT
162 intptr_t h = 0;
163 for (size_t i = 0; i < count(); i++) {
164 h ^= frame_at(i)->hash();
165 }
166 assert(h == hash(), "hash mismatch");
167 #endif
168 }
169
170 bool CompositeTraceStack::equals(const CachedTraceStack* cts) const {
171 if (hash() != cts->hash() || count() != cts->count() || is_truncated() != cts->is_truncated()) {
172 return false;
173 }
174 return _top.range_equals(0, cts, 0, _top.count())
175 && (_bottom == NULL || _bottom->range_equals(_bottom_offset, cts, _top.count(), count() - _top.count()));
176 }
177
178 bool CompositeTraceStack::equals(const CompositeTraceStack &other) const {
179 if (hash() != other.hash() || count() != other.count() || is_truncated() != other.is_truncated()) {
180 return false;
181 }
182 for (size_t i = 0; i < count(); i++) {
183 if (!frame_at(i)->equals(*other.frame_at(i))) {
184 return false;
185 }
186 }
187 return true;
188 }
189
190 //
191 // TraceStackCache
192 //
193
194 TraceStackCache::TraceStackCache(TraceMetadata *tm)
195 {
196 _metadata = tm;
197
198 _table = NULL;
199 _count = 0;
200 _has_invalid_stacks = false;
201
202 _lookup_counter = _lookup_miss_counter = _lookup_collision_counter = _probe_counter = _probe_collision_counter = 0;
203
204 _size = (1 << 12);
205 assert(is_power_of_2(_size), "sanity");
206 _table = (CachedTraceStack **) os::malloc(_size * sizeof(_table[0]), mtEventTracing, CURRENT_PC);
207 memset(_table, 0, _size * sizeof(_table[0]));
208 }
209
210 TraceStackCache::~TraceStackCache() {
211 for (size_t i = 0; i < _size; i++) {
212 CachedTraceStack *p = _table[i];
213 while (p != NULL) {
214 CachedTraceStack *next = p->cache_next();
215 delete p;
216 p = next;
217 }
218 }
219 os::free(_table, mtEventTracing);
220 }
221
222 void TraceStackCache::add_for_rehash(CachedTraceStack *cts) {
223 const size_t mask = (_size - 1);
224 intptr_t index = cts->hash() & mask;
225 cts->set_cache_next(_table[index]);
226 _table[index] = cts;
227 _count++;
228 }
229
230 inline void TraceStackCache::update_counters_after_lookup(bool present, jlong probes, jlong collisions) {
231 if (EnableEventTracingDiagnostics) {
232 Atomic::inc_ptr(&_lookup_counter);
233 Atomic::add_ptr(probes, &_probe_counter);
234 if (!present) {
235 Atomic::inc_ptr(&_lookup_miss_counter);
236 }
237 if (collisions > 0) {
238 Atomic::inc_ptr(&_lookup_collision_counter);
239 Atomic::add_ptr(collisions, &_probe_collision_counter);
240 }
241 }
242 }
243
244 const CachedTraceStack * TraceStackCache::get_or_try_add(const CompositeTraceStack &ts, bool &known, TraceTypes::stack_id preallocated_id) {
245 jlong probes = 0, collisions = 0;
246
247 CachedTraceStack *created = NULL;
248
249 const size_t mask = (_size - 1);
250 const size_t index = ts.hash() & mask;
251 // XXX: probably need barriers here on non-x86
252 for(;;) {
253 CachedTraceStack *head = _table[index];
254 if (head == NULL) {
255 probes++;
256 }
257 CachedTraceStack *p = head;
258 while (p != NULL) {
259 probes++;
260 if (ts.hash() == p->hash()) {
261 if (ts.equals(p)) {
262 delete created;
263 known = true;
264 update_counters_after_lookup(true, probes, collisions);
265 return p;
266 } else {
267 collisions++;
268 }
269 }
270 p = p->cache_next();
271 }
272 // not found
273 if (created == NULL) {
274 TraceTypes::stack_id id = preallocated_id;
275 if (id == 0) {
276 id = _metadata->next_stack_id();
277 }
278 created = CachedTraceStack::create(id, ts);
279 }
280 created->set_cache_next(head);
281 if (Atomic::cmpxchg_ptr(created, &_table[index], head) == head) {
282 Atomic::inc_ptr(&_count);
283 known = false;
284 update_counters_after_lookup(false, probes, collisions);
285 return created;
286 }
287 // head of collision chain changed: walk the entire chain again in the next
288 // next iteration to check whether the stack trace has been inserted by
289 // another thread (head is not enough, multiple threads may have inserted)
290 }
291 }
292
293 class TraceStackCache::CachedTraceStackPredicate {
294 public:
295 virtual bool test(CachedTraceStack *cts) = 0;
296 };
297
298 inline void TraceStackCache::purge_matches(TraceStackCache::CachedTraceStackPredicate *pr) {
299 if (EnableEventTracingDiagnostics) {
300 _purge_timer.start();
301 }
302
303 for (size_t i = 0; i < _size; i++) {
304 CachedTraceStack *p = _table[i];
305 while (p != NULL) {
306 if (p->is_valid() && pr->test(p)) {
307 p->invalidate();
308 _has_invalid_stacks = true;
309 }
310 p = p->cache_next();
311 }
312 }
313
314 if (EnableEventTracingDiagnostics) {
315 _purge_timer.stop();
316 }
317 }
318
319 class TraceStackCache::UnloadingClassPredicate : public TraceStackCache::CachedTraceStackPredicate {
320 const ClassLoaderData *_loader;
321 public:
322 UnloadingClassPredicate(const ClassLoaderData *loader) : _loader(loader) { }
323 virtual bool test(CachedTraceStack *stack) {
324 return stack->has_interpreted_method_from_classloader(_loader);
325 }
326 };
327
328 void TraceStackCache::purge_unloading_classes(const ClassLoaderData* loader) {
329 assert(SafepointSynchronize::is_at_safepoint() && Thread::current()->is_VM_thread(), "must be done in VM thread at safepoint");
330
331 // NOTE: only purges stack traces with *interpreted* frames that refer to
332 // unloading classes. nmethods with code from unloaded classes are unloaded
333 // in a later step, at which point we also unload the stack traces that
334 // contain those nmethods.
335 UnloadingClassPredicate pr(loader);
336 purge_matches(&pr);
337 }
338
339 class TraceStackCache::UnloadingNmethodPredicate : public TraceStackCache::CachedTraceStackPredicate {
340 const nmethod *_nmethod;
341 public:
342 UnloadingNmethodPredicate(const nmethod *nm) : _nmethod(nm) { }
343 virtual bool test(CachedTraceStack *stack) {
344 return stack->has_nmethod(_nmethod);
345 }
346 };
347
348 void TraceStackCache::purge_unloading_nmethod(const nmethod *nm) {
349 UnloadingNmethodPredicate pr(nm);
350 purge_matches(&pr);
351 }
352
353 class TraceStackCache::AnyPredicate : public TraceStackCache::CachedTraceStackPredicate {
354 public:
355 virtual bool test(CachedTraceStack *stack) {
356 return true;
357 }
358 };
359
360 void TraceStackCache::purge_all() {
361 AnyPredicate pr;
362 purge_matches(&pr);
363 }
364
365 void TraceStackCache::do_maintenance() {
366 assert(SafepointSynchronize::is_at_safepoint() && Thread::current()->is_VM_thread(), "must be done in VM thread at safepoint");
367
368 bool should_grow = (_count / (float) _size > 0.7f);
369 if (should_grow || has_invalid_stacks()) {
370 if (EnableEventTracingDiagnostics) {
371 _maintenance_timer.start();
372 }
373
374 CachedTraceStack **old_table = _table;
375 size_t old_capacity = _size;
376
377 if (should_grow) {
378 _size <<= 1;
379 assert(is_power_of_2(_size), "sanity");
380 }
381 _count = 0;
382 _table = (CachedTraceStack **) os::malloc(_size * sizeof(_table[0]), mtEventTracing, CURRENT_PC);
383 memset(_table, 0, _size * sizeof(_table[0]));
384 for (size_t i = 0; i < old_capacity; i++) {
385 CachedTraceStack *p = old_table[i];
386 while (p != NULL) {
387 CachedTraceStack *next = p->cache_next();
388 if (p->is_valid()) {
389 add_for_rehash(p);
390 } else {
391 delete p;
392 }
393 p = next;
394 }
395 }
396 os::free(old_table, mtEventTracing);
397
398 if (EnableEventTracingDiagnostics) {
399 _maintenance_timer.stop();
400 }
401
402 _has_invalid_stacks = false;
403 }
404 }
405
406 void TraceStackCache::reset_stats() {
407 _lookup_counter = _lookup_miss_counter = _lookup_collision_counter = _probe_counter = _probe_collision_counter = 0;
408
409 // these are only used in a safepoint: we should be fine either way
410 _purge_timer.reset();
411 _maintenance_timer.reset();
412 }