/*
 * 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 <http://mevss.jku.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 <http://www.gnu.org/licenses/>.
 *
 */

#ifndef SHARE_VM_EVTRACE_TRACESTACK_HPP
#define SHARE_VM_EVTRACE_TRACESTACK_HPP

#include "evtrace/traceTypes.hpp"

#include "memory/allocation.hpp"
#include "runtime/timer.hpp"

class Method;
class CachedTraceStack;
class TraceMetadata;

#define TRACE_STACK_MAX_FRAMES 128

class CompositeTraceStack;

struct TraceStackFrame {
  bool is_compiled;
  union {
    struct {
      nmethod *nm;
      address  pc;
    } compiled;
    struct {
      Method *method;
      int     bci;
    } interpreted;
  };

  intptr_t hash() const;
  bool equals(const TraceStackFrame& other) const;
};

class TraceStackBuilder: StackObj {
private:
  TraceStackFrame _frames[TRACE_STACK_MAX_FRAMES];
  size_t   _count;
  bool     _truncated;
  intptr_t _hash;

  void add(const TraceStackFrame &f);

public:
  TraceStackBuilder();

  void add_frame(const frame *fr);
  void set_truncated() { _truncated = true; }

  const TraceStackFrame *frame_at(size_t index) const;

  size_t   count() const        { return _count;     }
  bool     is_full() const      { return (_count == EventTracingStackDepthLimit); }
  bool     is_truncated() const { return _truncated; }
  intptr_t hash() const         { return _hash;      }

  bool     range_equals(size_t offset, const CachedTraceStack *cts, size_t cts_offset, size_t count) const;
};

class CachedTraceStack: CHeapObj<mtEventTracing> {
public:
  static CachedTraceStack *create(TraceTypes::stack_id id, const CompositeTraceStack &ts);

  const TraceStackFrame *frame_at(size_t index) const;

  TraceTypes::stack_id  id() const { return _id;        }
  size_t   count() const           { return _count;     }
  bool     is_truncated() const    { return _truncated; }
  intptr_t hash() const            { return _hash;      }

  bool     has_interpreted_method_from_classloader(const ClassLoaderData *loader) const;
  bool     has_nmethod(const nmethod *nm) const;
  bool     range_equals(size_t offset, const CachedTraceStack *other, size_t other_offset, size_t count) const;

  bool     is_valid() const { return _valid; }
  void     invalidate();

  CachedTraceStack *cache_next();
  void     set_cache_next(CachedTraceStack *next);

  void operator delete(void* p);

private:
  void* operator new(size_t size, size_t nframes) throw ();
  CachedTraceStack(TraceTypes::stack_id id, const CompositeTraceStack &ts);

  CachedTraceStack * volatile _cache_next;

  const TraceTypes::stack_id  _id;
  const intptr_t              _hash;
  const size_t                _count;
  const bool                  _truncated;
  bool                        _valid;
  TraceStackFrame             _frames[0];
};

class CompositeTraceStack: StackObj {
private:
  const TraceStackBuilder &_top;
  const CachedTraceStack  *_bottom;
  size_t    _bottom_offset;
  intptr_t  _hash;
  size_t    _count;
  bool      _truncated;

public:
  CompositeTraceStack(TraceStackBuilder &top);

  void set_bottom(const CachedTraceStack *cts, size_t offset);

  bool equals(const CachedTraceStack *cts) const;
  bool equals(const CompositeTraceStack &other) const;

  const TraceStackFrame *frame_at(size_t index) const;

  intptr_t hash() const         { return _hash;      }
  size_t   count() const        { return _count;     }
  bool     is_truncated() const { return _truncated; }
};

class TraceStackVframeIterator: StackObj {
private:
  const CompositeTraceStack &_ts;
  int      _index;
  int      _decode_offset;
  Method  *_method;
  int      _bci;

  void fill_from_compiled_frame();

public:
  TraceStackVframeIterator(const CompositeTraceStack &ts);

  bool has_next();
  void next();
  void reset();

  Method *method() { return _method; }
  int     bci()    { return _bci;    }
};

class TraceStackCache: public CHeapObj<mtEventTracing> {
private:
  TraceMetadata *_metadata;

  CachedTraceStack **_table;
  volatile intptr_t  _count;
  size_t             _size;
  volatile bool      _has_invalid_stacks;

  // statistics
  elapsedTimer   _purge_timer;
  elapsedTimer   _maintenance_timer;
  volatile intptr_t _lookup_counter;
  volatile intptr_t _lookup_miss_counter;
  volatile intptr_t _lookup_collision_counter;
  volatile intptr_t _probe_counter;
  volatile intptr_t _probe_collision_counter;

  void add_for_rehash(CachedTraceStack *cts);

  class CachedTraceStackPredicate;
  class UnloadingClassPredicate;
  class UnloadingNmethodPredicate;
  class AnyPredicate;
  void purge_matches(CachedTraceStackPredicate *pr);

  void update_counters_after_lookup(bool present, jlong probes, jlong collisions);

public:
  TraceStackCache(TraceMetadata *tm);
  virtual ~TraceStackCache();

  const CachedTraceStack * get_or_try_add(const CompositeTraceStack &ts, bool &known, TraceTypes::stack_id preallocated_id = 0);

  void purge_unloading_classes(const ClassLoaderData *loader);
  void purge_unloading_nmethod(const nmethod *nm);
  void purge_all();

  bool has_invalid_stacks() const { return _has_invalid_stacks; }
  void do_maintenance();

  intptr_t lookups()            { return _lookup_counter;                   }
  intptr_t lookup_misses()      { return _lookup_miss_counter;              }
  intptr_t lookup_collisions()  { return _lookup_collision_counter;         }
  intptr_t probes()             { return _probe_counter;                    }
  intptr_t probe_collisions()   { return _probe_collision_counter;          }
  jlong    purge_millis()       { return _purge_timer.milliseconds();       }
  jlong    maintenance_millis() { return _maintenance_timer.milliseconds(); }
  void     reset_stats();
};

#include "evtrace/traceStack.inline.hpp"

#endif /* SHARE_VM_EVTRACE_TRACESTACK_HPP */