/*

 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

 *

 * 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, write to the Free Software Foundation,

 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

 *

 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,

 * CA 95054 USA or visit www.sun.com if you need additional information or

 * have any questions.

 *

 */

# include "incls/_precompiled.incl"

# include "incls/_jvmtiTagMap.cpp.incl"

// JvmtiTagHashmapEntry

//

// Each entry encapsulates a JNI weak reference to the tagged object

// and the tag value. In addition an entry includes a next pointer which

// is used to chain entries together.

class JvmtiTagHashmapEntry : public CHeapObj {

 private:

  friend class JvmtiTagMap;

  jweak _object;                        // JNI weak ref to tagged object

  jlong _tag;                           // the tag

  JvmtiTagHashmapEntry* _next;          // next on the list

  inline void init(jweak object, jlong tag) {

    _object = object;

    _tag = tag;

    _next = NULL;

  }

  // constructor

  JvmtiTagHashmapEntry(jweak object, jlong tag)         { init(object, tag); }

 public:

  // accessor methods

  inline jweak object() const                           { return _object; }

  inline jlong tag() const                              { return _tag; }

  inline void set_tag(jlong tag) {

    assert(tag != 0, "can't be zero");

    _tag = tag;

  }

  inline JvmtiTagHashmapEntry* next() const             { return _next; }

  inline void set_next(JvmtiTagHashmapEntry* next)      { _next = next; }

};

// JvmtiTagHashmap

//

// A hashmap is essentially a table of pointers to entries. Entries

// are hashed to a location, or position in the table, and then

// chained from that location. The "key" for hashing is address of

// the object, or oop. The "value" is the JNI weak reference to the

// object and the tag value. Keys are not stored with the entry.

// Instead the weak reference is resolved to obtain the key.

//

// A hashmap maintains a count of the number entries in the hashmap

// and resizes if the number of entries exceeds a given threshold.

// The threshold is specified as a percentage of the size - for

// example a threshold of 0.75 will trigger the hashmap to resize

// if the number of entries is >75% of table size.

//

// A hashmap provides functions for adding, removing, and finding

// entries. It also provides a function to iterate over all entries

// in the hashmap.

class JvmtiTagHashmap : public CHeapObj {

 private:

  friend class JvmtiTagMap;

  enum {

    small_trace_threshold  = 10000,                  // threshold for tracing

    medium_trace_threshold = 100000,

    large_trace_threshold  = 1000000,

    initial_trace_threshold = small_trace_threshold

  };

  static int _sizes[];                  // array of possible hashmap sizes

  int _size;                            // actual size of the table

  int _size_index;                      // index into size table

  int _entry_count;                     // number of entries in the hashmap

  float _load_factor;                   // load factor as a % of the size

  int _resize_threshold;                // computed threshold to trigger resizing.

  bool _resizing_enabled;               // indicates if hashmap can resize

  int _trace_threshold;                 // threshold for trace messages

  JvmtiTagHashmapEntry** _table;        // the table of entries.

  // private accessors

  int resize_threshold() const                  { return _resize_threshold; }

  int trace_threshold() const                   { return _trace_threshold; }

  // initialize the hashmap

  void init(int size_index=0, float load_factor=4.0f) {

    int initial_size =  _sizes[size_index];

    _size_index = size_index;

    _size = initial_size;

    _entry_count = 0;

    if (TraceJVMTIObjectTagging) {

      _trace_threshold = initial_trace_threshold;

    } else {

      _trace_threshold = -1;

    }

    _load_factor = load_factor;

    _resize_threshold = (int)(_load_factor * _size);

    _resizing_enabled = true;

    size_t s = initial_size * sizeof(JvmtiTagHashmapEntry*);

    _table = (JvmtiTagHashmapEntry**)os::malloc(s);

    if (_table == NULL) {

      vm_exit_out_of_memory(s, "unable to allocate initial hashtable for jvmti object tags");

    }

    for (int i=0; i<initial_size; i++) {

      _table[i] = NULL;

    }

  }

  // hash a given key (oop) with the specified size

  static unsigned int hash(oop key, int size) {

    // shift right to get better distribution (as these bits will be zero

    // with aligned addresses)

    unsigned int addr = (unsigned int)((intptr_t)key);

#ifdef _LP64

    return (addr >> 3) % size;

#else

    return (addr >> 2) % size;

#endif

  }

  // hash a given key (oop)

  unsigned int hash(oop key) {

    return hash(key, _size);

  }

  // resize the hashmap - allocates a large table and re-hashes

  // all entries into the new table.

  void resize() {

    int new_size_index = _size_index+1;

    int new_size = _sizes[new_size_index];

    if (new_size < 0) {

      // hashmap already at maximum capacity

      return;

    }

    // allocate new table

    size_t s = new_size * sizeof(JvmtiTagHashmapEntry*);

    JvmtiTagHashmapEntry** new_table = (JvmtiTagHashmapEntry**)os::malloc(s);

    if (new_table == NULL) {

      warning("unable to allocate larger hashtable for jvmti object tags");

      set_resizing_enabled(false);

      return;

    }

    // initialize new table

    int i;

    for (i=0; i<new_size; i++) {

      new_table[i] = NULL;

    }

    // rehash all entries into the new table

    for (i=0; i<_size; i++) {

      JvmtiTagHashmapEntry* entry = _table[i];

      while (entry != NULL) {

        JvmtiTagHashmapEntry* next = entry->next();

        oop key = JNIHandles::resolve(entry->object());

        assert(key != NULL, "jni weak reference cleared!!");

        unsigned int h = hash(key, new_size);

        JvmtiTagHashmapEntry* anchor = new_table[h];

        if (anchor == NULL) {

          new_table[h] = entry;

          entry->set_next(NULL);

        } else {

          entry->set_next(anchor);

          new_table[h] = entry;

        }

        entry = next;

      }

    }

    // free old table and update settings.

    os::free((void*)_table);

    _table = new_table;

    _size_index = new_size_index;

    _size = new_size;

    // compute new resize threshold

    _resize_threshold = (int)(_load_factor * _size);

  }

  // internal remove function - remove an entry at a given position in the

  // table.

  inline void remove(JvmtiTagHashmapEntry* prev, int pos, JvmtiTagHashmapEntry* entry) {

    assert(pos >= 0 && pos < _size, "out of range");

    if (prev == NULL) {

      _table[pos] = entry->next();

    } else {

      prev->set_next(entry->next());

    }

    assert(_entry_count > 0, "checking");

    _entry_count--;

  }

  // resizing switch

  bool is_resizing_enabled() const          { return _resizing_enabled; }

  void set_resizing_enabled(bool enable)    { _resizing_enabled = enable; }

  // debugging

  void print_memory_usage();

  void compute_next_trace_threshold();

 public:

  // create a JvmtiTagHashmap of a preferred size and optionally a load factor.

  // The preferred size is rounded down to an actual size.

  JvmtiTagHashmap(int size, float load_factor=0.0f) {

    int i=0;

    while (_sizes[i] < size) {

      if (_sizes[i] < 0) {

        assert(i > 0, "sanity check");

        i--;

        break;

      }

      i++;

    }

    // if a load factor is specified then use it, otherwise use default

    if (load_factor > 0.01f) {

      init(i, load_factor);

    } else {

      init(i);

    }

  }

  // create a JvmtiTagHashmap with default settings

  JvmtiTagHashmap() {

    init();

  }

  // release table when JvmtiTagHashmap destroyed

  ~JvmtiTagHashmap() {

    if (_table != NULL) {

      os::free((void*)_table);

      _table = NULL;

    }

  }

  // accessors

  int size() const                              { return _size; }

  JvmtiTagHashmapEntry** table() const          { return _table; }

  int entry_count() const                       { return _entry_count; }

  // find an entry in the hashmap, returns NULL if not found.

  inline JvmtiTagHashmapEntry* find(oop key) {

    unsigned int h = hash(key);

    JvmtiTagHashmapEntry* entry = _table[h];

    while (entry != NULL) {

      oop orig_key = JNIHandles::resolve(entry->object());

      assert(orig_key != NULL, "jni weak reference cleared!!");

      if (key == orig_key) {

        break;

      }

      entry = entry->next();

    }

    return entry;

  }

  // add a new entry to hashmap

  inline void add(oop key, JvmtiTagHashmapEntry* entry) {

    assert(key != NULL, "checking");

    assert(find(key) == NULL, "duplicate detected");

    unsigned int h = hash(key);

    JvmtiTagHashmapEntry* anchor = _table[h];

    if (anchor == NULL) {

      _table[h] = entry;

      entry->set_next(NULL);

    } else {

      entry->set_next(anchor);

      _table[h] = entry;

    }

    _entry_count++;

    if (trace_threshold() > 0 && entry_count() >= trace_threshold()) {

      assert(TraceJVMTIObjectTagging, "should only get here when tracing");

      print_memory_usage();

      compute_next_trace_threshold();

    }

    // if the number of entries exceed the threshold then resize

    if (entry_count() > resize_threshold() && is_resizing_enabled()) {

      resize();

    }

  }

  // remove an entry with the given key.

  inline JvmtiTagHashmapEntry* remove(oop key) {

    unsigned int h = hash(key);

    JvmtiTagHashmapEntry* entry = _table[h];

    JvmtiTagHashmapEntry* prev = NULL;

    while (entry != NULL) {

      oop orig_key = JNIHandles::resolve(entry->object());

      assert(orig_key != NULL, "jni weak reference cleared!!");

      if (key == orig_key) {

        break;

      }

      prev = entry;

      entry = entry->next();

    }

    if (entry != NULL) {

      remove(prev, h, entry);

    }

    return entry;

  }

  // iterate over all entries in the hashmap

  void entry_iterate(JvmtiTagHashmapEntryClosure* closure);

};

// possible hashmap sizes - odd primes that roughly double in size.

// To avoid excessive resizing the odd primes from 4801-76831 and

// 76831-307261 have been removed. The list must be terminated by -1.

int JvmtiTagHashmap::_sizes[] =  { 4801, 76831, 307261, 614563, 1228891,

    2457733, 4915219, 9830479, 19660831, 39321619, 78643219, -1 };

// A supporting class for iterating over all entries in Hashmap

class JvmtiTagHashmapEntryClosure {

 public:

  virtual void do_entry(JvmtiTagHashmapEntry* entry) = 0;

};

// iterate over all entries in the hashmap

void JvmtiTagHashmap::entry_iterate(JvmtiTagHashmapEntryClosure* closure) {

  for (int i=0; i<_size; i++) {

    JvmtiTagHashmapEntry* entry = _table[i];

    JvmtiTagHashmapEntry* prev = NULL;

    while (entry != NULL) {

      // obtain the next entry before invoking do_entry - this is

      // necessary because do_entry may remove the entry from the

      // hashmap.

      JvmtiTagHashmapEntry* next = entry->next();

      closure->do_entry(entry);

      entry = next;

     }

  }

}

// debugging

void JvmtiTagHashmap::print_memory_usage() {

  intptr_t p = (intptr_t)this;

  tty->print("[JvmtiTagHashmap @ " INTPTR_FORMAT, p);

  // table + entries in KB

  int hashmap_usage = (size()*sizeof(JvmtiTagHashmapEntry*) +

    entry_count()*sizeof(JvmtiTagHashmapEntry))/K;

  int weak_globals_usage = (int)(JNIHandles::weak_global_handle_memory_usage()/K);

  tty->print_cr(", %d entries (%d KB) <JNI weak globals: %d KB>]",

    entry_count(), hashmap_usage, weak_globals_usage);

}

// compute threshold for the next trace message

void JvmtiTagHashmap::compute_next_trace_threshold() {

  if (trace_threshold() < medium_trace_threshold) {

    _trace_threshold += small_trace_threshold;

  } else {

    if (trace_threshold() < large_trace_threshold) {

      _trace_threshold += medium_trace_threshold;

    } else {

      _trace_threshold += large_trace_threshold;

    }

  }

}

// memory region for young generation

MemRegion JvmtiTagMap::_young_gen;

// get the memory region used for the young generation

void JvmtiTagMap::get_young_generation() {

  CollectedHeap* ch = Universe::heap();

  switch (ch->kind()) {

    case (CollectedHeap::GenCollectedHeap): {

      _young_gen = ((GenCollectedHeap*)ch)->get_gen(0)->reserved();

      break;

    }

#ifndef SERIALGC

    case (CollectedHeap::ParallelScavengeHeap): {

      _young_gen = ((ParallelScavengeHeap*)ch)->young_gen()->reserved();

      break;

    }

    case (CollectedHeap::G1CollectedHeap): {

      // Until a more satisfactory solution is implemented, all

      // oops in the tag map will require rehash at each gc.

      // This is a correct, if extremely inefficient solution.

      // See RFE 6621729 for related commentary.

      _young_gen = ch->reserved_region();

      break;

    }

#endif  // !SERIALGC

    default:

      ShouldNotReachHere();

  }

}

// returns true if oop is in the young generation

inline bool JvmtiTagMap::is_in_young(oop o) {

  assert(_young_gen.start() != NULL, "checking");

  void* p = (void*)o;

  bool in_young = _young_gen.contains(p);

  return in_young;

}

// returns the appropriate hashmap for a given object

inline JvmtiTagHashmap* JvmtiTagMap::hashmap_for(oop o) {

  if (is_in_young(o)) {

    return _hashmap[0];

  } else {

    return _hashmap[1];

  }

}

// create a JvmtiTagMap

JvmtiTagMap::JvmtiTagMap(JvmtiEnv* env) :

  _env(env),

  _lock(Mutex::nonleaf+2, "JvmtiTagMap._lock", false),

  _free_entries(NULL),

  _free_entries_count(0)

{

  assert(JvmtiThreadState_lock->is_locked(), "sanity check");

  assert(((JvmtiEnvBase *)env)->tag_map() == NULL, "tag map already exists for environment");

  // create the hashmaps

  for (int i=0; i<n_hashmaps; i++) {

    _hashmap[i] = new JvmtiTagHashmap();

  }

  // get the memory region used by the young generation

  get_young_generation();

  // finally add us to the environment

  ((JvmtiEnvBase *)env)->set_tag_map(this);

}

// destroy a JvmtiTagMap

JvmtiTagMap::~JvmtiTagMap() {

  // no lock acquired as we assume the enclosing environment is

  // also being destroryed.

  ((JvmtiEnvBase *)_env)->set_tag_map(NULL);

  // iterate over the hashmaps and destroy each of the entries

  for (int i=0; i<n_hashmaps; i++) {

    JvmtiTagHashmap* hashmap = _hashmap[i];

    JvmtiTagHashmapEntry** table = hashmap->table();

    for (int j=0; j<hashmap->size(); j++) {

      JvmtiTagHashmapEntry *entry = table[j];

      while (entry != NULL) {

        JvmtiTagHashmapEntry* next = entry->next();

        jweak ref = entry->object();

        JNIHandles::destroy_weak_global(ref);

        delete entry;

        entry = next;

      }

    }

    // finally destroy the hashmap

    delete hashmap;

  }

  // remove any entries on the free list

  JvmtiTagHashmapEntry* entry = _free_entries;

  while (entry != NULL) {

    JvmtiTagHashmapEntry* next = entry->next();

    delete entry;

    entry = next;

  }

}

// create a hashmap entry

// - if there's an entry on the (per-environment) free list then this

// is returned. Otherwise an new entry is allocated.

JvmtiTagHashmapEntry* JvmtiTagMap::create_entry(jweak ref, jlong tag) {

  assert(Thread::current()->is_VM_thread() || is_locked(), "checking");

  JvmtiTagHashmapEntry* entry;

  if (_free_entries == NULL) {

    entry = new JvmtiTagHashmapEntry(ref, tag);

  } else {

    assert(_free_entries_count > 0, "mismatched _free_entries_count");

    _free_entries_count--;

    entry = _free_entries;

    _free_entries = entry->next();

    entry->init(ref, tag);

  }

  return entry;

}

// destroy an entry by returning it to the free list

void JvmtiTagMap::destroy_entry(JvmtiTagHashmapEntry* entry) {

  assert(SafepointSynchronize::is_at_safepoint() || is_locked(), "checking");

  // limit the size of the free list

  if (_free_entries_count >= max_free_entries) {

    delete entry;