/*
* Copyright (c) 2014, 2015, Dynatrace and/or its affiliates. All rights reserved.
*
* This file is part of the Lock Contention Tracing Subsystem for the HotSpot
* Virtual Machine, which is developed at Christian Doppler Laboratory on
* Monitoring and Evolution of Very-Large-Scale Software Systems. Please
* contact us at if you need additional information
* or have any questions.
*
* This code is free software; you can redistribute it and/or modify it
* under the terms of the GNU General Public License version 2 only, as
* published by the Free Software Foundation.
*
* This code is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
* version 2 for more details (a copy is included in the LICENSE file that
* accompanied this code).
*
* You should have received a copy of the GNU General Public License version
* 2 along with this work. If not, see .
*
*/
#include "evtrace/traceStack.hpp"
#include "evtrace/traceEvents.hpp"
#include "evtrace/traceMetadata.hpp"
#include "runtime/vframe.hpp"
#include "runtime/init.hpp"
//
// TraceStackBuilder
//
void TraceStackBuilder::add(const TraceStackFrame &f) {
assert(!is_full(), "already full");
_frames[_count] = f;
_hash ^= f.hash();
_count++;
}
void TraceStackBuilder::add_frame(const frame *fr) {
TraceStackFrame f;
f.is_compiled = fr->cb()->is_nmethod();
if (f.is_compiled) {
assert(fr->is_compiled_frame() || fr->is_native_frame(), "unsupported frame type");
f.compiled.pc = fr->pc();
f.compiled.nm = (nmethod *) fr->cb();
} else {
assert(fr->is_interpreted_frame(), "unsupported frame type");
f.interpreted.method = fr->interpreter_frame_method();
f.interpreted.bci = fr->interpreter_frame_bci();
}
add(f);
}
bool TraceStackBuilder::range_equals(size_t offset, const CachedTraceStack *cts, size_t cts_offset, size_t count) const {
for (size_t i = 0; i < count; i++) {
if (!frame_at(offset + i)->equals(*cts->frame_at(cts_offset + i))) {
return false;
}
}
return true;
}
//
// CachedTraceStack
//
CachedTraceStack *CachedTraceStack::create(TraceTypes::stack_id id, const CompositeTraceStack &ts) {
assert (in_bytes(byte_offset_of(CachedTraceStack, _frames)) == sizeof(CachedTraceStack),
"variable-sized frame array must be last field");
return new (ts.count()) CachedTraceStack(id, ts);
}
void* CachedTraceStack::operator new(size_t size, size_t nframes) throw () {
return CHeapObj::operator new(size + sizeof(_frames[0]) * nframes, CALLER_PC);
}
void CachedTraceStack::operator delete(void* p) {
CHeapObj::operator delete(p);
}
CachedTraceStack::CachedTraceStack(TraceTypes::stack_id id, const CompositeTraceStack& ts)
: _id(id),
_count(ts.count()),
_hash(ts.hash()),
_truncated(ts.is_truncated()),
_valid(true)
{
for (size_t i = 0; i < ts.count(); i++) {
_frames[i] = *ts.frame_at(i);
}
}
bool CachedTraceStack::has_interpreted_method_from_classloader(const ClassLoaderData* loader) const {
assert(is_valid(), "sanity");
for (size_t i = 0; i < _count; i++) {
if (!_frames[i].is_compiled && _frames[i].interpreted.method->method_holder()->class_loader_data() == loader) {
return true;
}
}
return false;
}
bool CachedTraceStack::has_nmethod(const nmethod *nm) const {
assert(is_valid(), "sanity");
for (size_t i = 0; i < _count; i++) {
if (_frames[i].is_compiled && _frames[i].compiled.nm == nm) {
return true;
}
}
return false;
}
bool CachedTraceStack::range_equals(size_t offset, const CachedTraceStack *other, size_t other_offset, size_t count) const {
for (size_t i = 0; i < count; i++) {
if (!frame_at(offset + i)->equals(*other->frame_at(other_offset + i))) {
return false;
}
}
return true;
}
//
// CompositeTraceStack
//
void CompositeTraceStack::set_bottom(const CachedTraceStack *bottom, size_t offset) {
_hash = _top.hash();
_count = _top.count();
_truncated = _top.is_truncated();
_bottom = bottom;
_bottom_offset = offset;
if (bottom != NULL) {
if (_top.count() < EventTracingStackDepthLimit) {
assert(!_top.is_truncated(), "missing frames between top and bottom");
_count += bottom->count() - offset;
_truncated = _truncated || bottom->is_truncated();
if (_count > EventTracingStackDepthLimit) {
_truncated = true;
_count = EventTracingStackDepthLimit;
}
_hash ^= bottom->hash();
// drop frames before offset from hash
for (size_t i = 0; i < offset; i++) {
_hash ^= bottom->frame_at(i)->hash();
}
// drop truncated frames from hash
for (size_t i = EventTracingStackDepthLimit - _top.count() + offset; i < _bottom->count(); i++) {
_hash ^= bottom->frame_at(i)->hash();
}
} else {
_truncated = _truncated || (bottom->count() > offset);
}
}
#ifdef ASSERT
intptr_t h = 0;
for (size_t i = 0; i < count(); i++) {
h ^= frame_at(i)->hash();
}
assert(h == hash(), "hash mismatch");
#endif
}
bool CompositeTraceStack::equals(const CachedTraceStack* cts) const {
if (hash() != cts->hash() || count() != cts->count() || is_truncated() != cts->is_truncated()) {
return false;
}
return _top.range_equals(0, cts, 0, _top.count())
&& (_bottom == NULL || _bottom->range_equals(_bottom_offset, cts, _top.count(), count() - _top.count()));
}
bool CompositeTraceStack::equals(const CompositeTraceStack &other) const {
if (hash() != other.hash() || count() != other.count() || is_truncated() != other.is_truncated()) {
return false;
}
for (size_t i = 0; i < count(); i++) {
if (!frame_at(i)->equals(*other.frame_at(i))) {
return false;
}
}
return true;
}
//
// TraceStackCache
//
TraceStackCache::TraceStackCache(TraceMetadata *tm)
{
_metadata = tm;
_table = NULL;
_count = 0;
_has_invalid_stacks = false;
_lookup_counter = _lookup_miss_counter = _lookup_collision_counter = _probe_counter = _probe_collision_counter = 0;
_size = (1 << 12);
assert(is_power_of_2(_size), "sanity");
_table = (CachedTraceStack **) os::malloc(_size * sizeof(_table[0]), mtEventTracing, CURRENT_PC);
memset(_table, 0, _size * sizeof(_table[0]));
}
TraceStackCache::~TraceStackCache() {
for (size_t i = 0; i < _size; i++) {
CachedTraceStack *p = _table[i];
while (p != NULL) {
CachedTraceStack *next = p->cache_next();
delete p;
p = next;
}
}
os::free(_table, mtEventTracing);
}
void TraceStackCache::add_for_rehash(CachedTraceStack *cts) {
const size_t mask = (_size - 1);
intptr_t index = cts->hash() & mask;
cts->set_cache_next(_table[index]);
_table[index] = cts;
_count++;
}
inline void TraceStackCache::update_counters_after_lookup(bool present, jlong probes, jlong collisions) {
if (EnableEventTracingDiagnostics) {
Atomic::inc_ptr(&_lookup_counter);
Atomic::add_ptr(probes, &_probe_counter);
if (!present) {
Atomic::inc_ptr(&_lookup_miss_counter);
}
if (collisions > 0) {
Atomic::inc_ptr(&_lookup_collision_counter);
Atomic::add_ptr(collisions, &_probe_collision_counter);
}
}
}
const CachedTraceStack * TraceStackCache::get_or_try_add(const CompositeTraceStack &ts, bool &known, TraceTypes::stack_id preallocated_id) {
jlong probes = 0, collisions = 0;
CachedTraceStack *created = NULL;
const size_t mask = (_size - 1);
const size_t index = ts.hash() & mask;
// XXX: probably need barriers here on non-x86
for(;;) {
CachedTraceStack *head = _table[index];
if (head == NULL) {
probes++;
}
CachedTraceStack *p = head;
while (p != NULL) {
probes++;
if (ts.hash() == p->hash()) {
if (ts.equals(p)) {
delete created;
known = true;
update_counters_after_lookup(true, probes, collisions);
return p;
} else {
collisions++;
}
}
p = p->cache_next();
}
// not found
if (created == NULL) {
TraceTypes::stack_id id = preallocated_id;
if (id == 0) {
id = _metadata->next_stack_id();
}
created = CachedTraceStack::create(id, ts);
}
created->set_cache_next(head);
if (Atomic::cmpxchg_ptr(created, &_table[index], head) == head) {
Atomic::inc_ptr(&_count);
known = false;
update_counters_after_lookup(false, probes, collisions);
return created;
}
// head of collision chain changed: walk the entire chain again in the next
// next iteration to check whether the stack trace has been inserted by
// another thread (head is not enough, multiple threads may have inserted)
}
}
class TraceStackCache::CachedTraceStackPredicate {
public:
virtual bool test(CachedTraceStack *cts) = 0;
};
inline void TraceStackCache::purge_matches(TraceStackCache::CachedTraceStackPredicate *pr) {
if (EnableEventTracingDiagnostics) {
_purge_timer.start();
}
for (size_t i = 0; i < _size; i++) {
CachedTraceStack *p = _table[i];
while (p != NULL) {
if (p->is_valid() && pr->test(p)) {
p->invalidate();
_has_invalid_stacks = true;
}
p = p->cache_next();
}
}
if (EnableEventTracingDiagnostics) {
_purge_timer.stop();
}
}
class TraceStackCache::UnloadingClassPredicate : public TraceStackCache::CachedTraceStackPredicate {
const ClassLoaderData *_loader;
public:
UnloadingClassPredicate(const ClassLoaderData *loader) : _loader(loader) { }
virtual bool test(CachedTraceStack *stack) {
return stack->has_interpreted_method_from_classloader(_loader);
}
};
void TraceStackCache::purge_unloading_classes(const ClassLoaderData* loader) {
assert(SafepointSynchronize::is_at_safepoint() && Thread::current()->is_VM_thread(), "must be done in VM thread at safepoint");
// NOTE: only purges stack traces with *interpreted* frames that refer to
// unloading classes. nmethods with code from unloaded classes are unloaded
// in a later step, at which point we also unload the stack traces that
// contain those nmethods.
UnloadingClassPredicate pr(loader);
purge_matches(&pr);
}
class TraceStackCache::UnloadingNmethodPredicate : public TraceStackCache::CachedTraceStackPredicate {
const nmethod *_nmethod;
public:
UnloadingNmethodPredicate(const nmethod *nm) : _nmethod(nm) { }
virtual bool test(CachedTraceStack *stack) {
return stack->has_nmethod(_nmethod);
}
};
void TraceStackCache::purge_unloading_nmethod(const nmethod *nm) {
UnloadingNmethodPredicate pr(nm);
purge_matches(&pr);
}
class TraceStackCache::AnyPredicate : public TraceStackCache::CachedTraceStackPredicate {
public:
virtual bool test(CachedTraceStack *stack) {
return true;
}
};
void TraceStackCache::purge_all() {
AnyPredicate pr;
purge_matches(&pr);
}
void TraceStackCache::do_maintenance() {
assert(SafepointSynchronize::is_at_safepoint() && Thread::current()->is_VM_thread(), "must be done in VM thread at safepoint");
bool should_grow = (_count / (float) _size > 0.7f);
if (should_grow || has_invalid_stacks()) {
if (EnableEventTracingDiagnostics) {
_maintenance_timer.start();
}
CachedTraceStack **old_table = _table;
size_t old_capacity = _size;
if (should_grow) {
_size <<= 1;
assert(is_power_of_2(_size), "sanity");
}
_count = 0;
_table = (CachedTraceStack **) os::malloc(_size * sizeof(_table[0]), mtEventTracing, CURRENT_PC);
memset(_table, 0, _size * sizeof(_table[0]));
for (size_t i = 0; i < old_capacity; i++) {
CachedTraceStack *p = old_table[i];
while (p != NULL) {
CachedTraceStack *next = p->cache_next();
if (p->is_valid()) {
add_for_rehash(p);
} else {
delete p;
}
p = next;
}
}
os::free(old_table, mtEventTracing);
if (EnableEventTracingDiagnostics) {
_maintenance_timer.stop();
}
_has_invalid_stacks = false;
}
}
void TraceStackCache::reset_stats() {
_lookup_counter = _lookup_miss_counter = _lookup_collision_counter = _probe_counter = _probe_collision_counter = 0;
// these are only used in a safepoint: we should be fine either way
_purge_timer.reset();
_maintenance_timer.reset();
}