/*

 * Copyright (c) 1997, 2018, Oracle and/or its affiliates. All rights reserved.

 * 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 Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

 * or visit www.oracle.com if you need additional information or have any

 * questions.

 *

 */

#include "precompiled.hpp"

#include "classfile/altHashing.hpp"

#include "classfile/compactHashtable.inline.hpp"

#include "classfile/javaClasses.hpp"

#include "classfile/symbolTable.hpp"

#include "memory/allocation.inline.hpp"

#include "memory/metaspaceClosure.hpp"

#include "memory/resourceArea.hpp"

#include "oops/oop.inline.hpp"

#include "runtime/atomic.hpp"

#include "runtime/interfaceSupport.inline.hpp"

#include "runtime/timerTrace.hpp"

#include "services/diagnosticCommand.hpp"

#include "utilities/concurrentHashTable.inline.hpp"

#include "utilities/concurrentHashTableTasks.inline.hpp"

// We used to not resize at all, so let's be conservative

// and not set it too short before we decide to resize,

// to match previous startup behavior

#define PREF_AVG_LIST_LEN           8

// 2^17 (131,072) is max size, which is about 6.5 times as large

// as the previous table size (used to be 20,011),

// which never resized

#define END_SIZE                    17

// If a chain gets to 100 something might be wrong

#define REHASH_LEN                  100

// We only get a chance to check whether we need

// to clean infrequently (on class unloading),

// so if we have even one dead entry then mark table for cleaning

#define CLEAN_DEAD_HIGH_WATER_MARK  0.0

#define ON_STACK_BUFFER_LENGTH 128

// --------------------------------------------------------------------------

SymbolTable* SymbolTable::_the_table = NULL;

CompactHashtable<Symbol*, char> SymbolTable::_shared_table;

volatile bool SymbolTable::_alt_hash = false;

volatile bool SymbolTable::_lookup_shared_first = false;

// Static arena for symbols that are not deallocated

Arena* SymbolTable::_arena = NULL;

static juint murmur_seed = 0;

static inline void log_trace_symboltable_helper(Symbol* sym, const char* msg) {

#ifndef PRODUCT

  ResourceMark rm;

  log_trace(symboltable)("%s [%s]", msg, sym->as_quoted_ascii());

#endif // PRODUCT

}

// Pick hashing algorithm.

static uintx hash_symbol(const char* s, int len, bool useAlt) {

  return useAlt ?

  AltHashing::murmur3_32(murmur_seed, (const jbyte*)s, len) :

  java_lang_String::hash_code((const jbyte*)s, len);

}

static uintx hash_shared_symbol(const char* s, int len) {

  return java_lang_String::hash_code((const jbyte*)s, len);

}

class SymbolTableConfig : public SymbolTableHash::BaseConfig {

private:

public:

  static uintx get_hash(Symbol* const& value, bool* is_dead) {

    *is_dead = (value->refcount() == 0);

    if (*is_dead) {

      return 0;

    } else {

      return hash_symbol((const char*)value->bytes(), value->utf8_length(), SymbolTable::_alt_hash);

    }

  }

  // We use default allocation/deallocation but counted

  static void* allocate_node(size_t size, Symbol* const& value) {

    SymbolTable::item_added();

    return SymbolTableHash::BaseConfig::allocate_node(size, value);

  }

  static void free_node(void* memory, Symbol* const& value) {

    // We get here either because #1 some threads lost a race

    // to insert a newly created Symbol, or #2 we are freeing

    // a symbol during normal cleanup deletion.

    // If #1, then the symbol can be a permanent (refcount==PERM_REFCOUNT),

    // or regular newly created one but with refcount==0 (see SymbolTableCreateEntry)

    // If #2, then the symbol must have refcount==0

    assert((value->refcount() == PERM_REFCOUNT) || (value->refcount() == 0),

           "refcount %d", value->refcount());

    SymbolTable::delete_symbol(value);

    SymbolTableHash::BaseConfig::free_node(memory, value);

    SymbolTable::item_removed();

  }

};

static size_t ceil_log2(size_t value) {

  size_t ret;

  for (ret = 1; ((size_t)1 << ret) < value; ++ret);

  return ret;

}

SymbolTable::SymbolTable() :

  _symbols_removed(0), _symbols_counted(0), _local_table(NULL),

  _current_size(0), _has_work(0), _needs_rehashing(false),

  _items_count(0), _uncleaned_items_count(0) {

  size_t start_size_log_2 = ceil_log2(SymbolTableSize);

  _current_size = ((size_t)1) << start_size_log_2;

  log_trace(symboltable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",

                         _current_size, start_size_log_2);

  _local_table = new SymbolTableHash(start_size_log_2, END_SIZE, REHASH_LEN);

}

void SymbolTable::delete_symbol(Symbol* sym) {

  if (sym->refcount() == PERM_REFCOUNT) {

    // Deleting permanent symbol should not occur very often (insert race condition),

    // so log it.

    log_trace_symboltable_helper(sym, "Freeing permanent symbol");

    if (!arena()->Afree(sym, sym->size())) {

      log_trace_symboltable_helper(sym, "Leaked permanent symbol");

    }

  } else {

    delete sym;

  }

}

void SymbolTable::item_added() {

  Atomic::inc(&(SymbolTable::the_table()->_items_count));

}

void SymbolTable::set_item_clean_count(size_t ncl) {

  Atomic::store(ncl, &(SymbolTable::the_table()->_uncleaned_items_count));

  log_trace(symboltable)("Set uncleaned items:" SIZE_FORMAT, SymbolTable::the_table()->_uncleaned_items_count);

}

void SymbolTable::mark_item_clean_count() {

  if (Atomic::cmpxchg((size_t)1, &(SymbolTable::the_table()->_uncleaned_items_count), (size_t)0) == 0) { // only mark if unset

    log_trace(symboltable)("Marked uncleaned items:" SIZE_FORMAT, SymbolTable::the_table()->_uncleaned_items_count);

  }

}

void SymbolTable::item_removed() {

  Atomic::inc(&(SymbolTable::the_table()->_symbols_removed));

  Atomic::dec(&(SymbolTable::the_table()->_items_count));

}

double SymbolTable::get_load_factor() {

  return (double)_items_count/_current_size;

}

double SymbolTable::get_dead_factor() {

  return (double)_uncleaned_items_count/_current_size;

}

size_t SymbolTable::table_size() {

  return ((size_t)1) << _local_table->get_size_log2(Thread::current());

}

void SymbolTable::trigger_concurrent_work() {

  MutexLockerEx ml(Service_lock, Mutex::_no_safepoint_check_flag);

  SymbolTable::the_table()->_has_work = true;

  Service_lock->notify_all();

}

Symbol* SymbolTable::allocate_symbol(const char* name, int len, bool c_heap, TRAPS) {

  assert (len <= Symbol::max_length(), "should be checked by caller");

  Symbol* sym;

  if (DumpSharedSpaces) {

    c_heap = false;

  }

  if (c_heap) {

    // refcount starts as 1

    sym = new (len, THREAD) Symbol((const u1*)name, len, 1);

    assert(sym != NULL, "new should call vm_exit_out_of_memory if C_HEAP is exhausted");

  } else {

    // Allocate to global arena

    sym = new (len, arena(), THREAD) Symbol((const u1*)name, len, PERM_REFCOUNT);

  }

  return sym;

}

void SymbolTable::initialize_symbols(int arena_alloc_size) {

  // Initialize the arena for global symbols, size passed in depends on CDS.

  if (arena_alloc_size == 0) {

    _arena = new (mtSymbol) Arena(mtSymbol);

  } else {

    _arena = new (mtSymbol) Arena(mtSymbol, arena_alloc_size);

  }

}

class SymbolsDo : StackObj {

  SymbolClosure *_cl;

public:

  SymbolsDo(SymbolClosure *cl) : _cl(cl) {}

  bool operator()(Symbol** value) {

    assert(value != NULL, "expected valid value");

    assert(*value != NULL, "value should point to a symbol");

    _cl->do_symbol(value);

    return true;

  };

};

// Call function for all symbols in the symbol table.

void SymbolTable::symbols_do(SymbolClosure *cl) {

  // all symbols from shared table

  _shared_table.symbols_do(cl);

  // all symbols from the dynamic table

  SymbolsDo sd(cl);

  if (!SymbolTable::the_table()->_local_table->try_scan(Thread::current(), sd)) {

    log_info(stringtable)("symbols_do unavailable at this moment");

  }

}

class MetaspacePointersDo : StackObj {

  MetaspaceClosure *_it;

public:

  MetaspacePointersDo(MetaspaceClosure *it) : _it(it) {}

  bool operator()(Symbol** value) {

    assert(value != NULL, "expected valid value");

    assert(*value != NULL, "value should point to a symbol");

    _it->push(value);

    return true;

  };

};

void SymbolTable::metaspace_pointers_do(MetaspaceClosure* it) {

  assert(DumpSharedSpaces, "called only during dump time");

  MetaspacePointersDo mpd(it);

  SymbolTable::the_table()->_local_table->do_scan(Thread::current(), mpd);

}

Symbol* SymbolTable::lookup_dynamic(const char* name,

                                    int len, unsigned int hash) {

  Symbol* sym = SymbolTable::the_table()->do_lookup(name, len, hash);

  assert((sym == NULL) || sym->refcount() != 0, "refcount must not be zero");

  return sym;

}

Symbol* SymbolTable::lookup_shared(const char* name,

                                   int len, unsigned int hash) {

  if (!_shared_table.empty()) {

    if (SymbolTable::_alt_hash) {

      // hash_code parameter may use alternate hashing algorithm but the shared table

      // always uses the same original hash code.

      hash = hash_shared_symbol(name, len);

    }

    return _shared_table.lookup(name, hash, len);

  } else {

    return NULL;

  }

}

Symbol* SymbolTable::lookup_common(const char* name,

                            int len, unsigned int hash) {

  Symbol* sym;

  if (_lookup_shared_first) {

    sym = lookup_shared(name, len, hash);

    if (sym == NULL) {

      _lookup_shared_first = false;

      sym = lookup_dynamic(name, len, hash);

    }

  } else {

    sym = lookup_dynamic(name, len, hash);

    if (sym == NULL) {

      sym = lookup_shared(name, len, hash);

      if (sym != NULL) {

        _lookup_shared_first = true;

      }

    }

  }

  return sym;

}

Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {

  unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);

  Symbol* sym = SymbolTable::the_table()->lookup_common(name, len, hash);

  if (sym == NULL) {

    sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, CHECK_NULL);

  }

  assert(sym->refcount() != 0, "lookup should have incremented the count");

  assert(sym->equals(name, len), "symbol must be properly initialized");

  return sym;

}

Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) {

  assert(sym->refcount() != 0, "require a valid symbol");

  const char* name = (const char*)sym->base() + begin;

  int len = end - begin;

  unsigned int hash = hash_symbol(name, len, SymbolTable::_alt_hash);

  Symbol* found = SymbolTable::the_table()->lookup_common(name, len, hash);

  if (found == NULL) {

    found = SymbolTable::the_table()->do_add_if_needed(name, len, hash, true, THREAD);

  }

  return found;

}

class SymbolTableLookup : StackObj {

private:

  Thread* _thread;

  uintx _hash;

  int _len;

  const char* _str;

public:

  SymbolTableLookup(Thread* thread, const char* key, int len, uintx hash)

  : _thread(thread), _hash(hash), _len(len), _str(key) {}

  uintx get_hash() const {

    return _hash;

  }

  bool equals(Symbol** value, bool* is_dead) {

    assert(value != NULL, "expected valid value");

    assert(*value != NULL, "value should point to a symbol");

    Symbol *sym = *value;

    if (sym->equals(_str, _len)) {

      if (sym->try_increment_refcount()) {

        // something is referencing this symbol now.

        return true;

      } else {

        assert(sym->refcount() == 0, "expected dead symbol");

        *is_dead = true;

        return false;

      }

    } else {

      *is_dead = (sym->refcount() == 0);

      return false;

    }

  }

};

class SymbolTableGet : public StackObj {

  Symbol* _return;

public:

  SymbolTableGet() : _return(NULL) {}

  void operator()(Symbol** value) {

    assert(value != NULL, "expected valid value");

    assert(*value != NULL, "value should point to a symbol");

    _return = *value;

  }

  Symbol* get_res_sym() {

    return _return;

  }

};

Symbol* SymbolTable::do_lookup(const char* name, int len, uintx hash) {

  Thread* thread = Thread::current();

  SymbolTableLookup lookup(thread, name, len, hash);

  SymbolTableGet stg;

  bool rehash_warning = false;

  _local_table->get(thread, lookup, stg, &rehash_warning);

  if (rehash_warning) {

    _needs_rehashing = true;

  }

  Symbol* sym = stg.get_res_sym();

  assert((sym == NULL) || sym->refcount() != 0, "found dead symbol");

  return sym;

}

Symbol* SymbolTable::lookup_only(const char* name, int len, unsigned int& hash) {

  hash = hash_symbol(name, len, SymbolTable::_alt_hash);

  return SymbolTable::the_table()->lookup_common(name, len, hash);

}

// Suggestion: Push unicode-based lookup all the way into the hashing

// and probing logic, so there is no need for convert_to_utf8 until

// an actual new Symbol* is created.

Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) {

  int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);

  char stack_buf[ON_STACK_BUFFER_LENGTH];

  if (utf8_length < (int) sizeof(stack_buf)) {

    char* chars = stack_buf;

    UNICODE::convert_to_utf8(name, utf16_length, chars);

    return lookup(chars, utf8_length, THREAD);

  } else {

    ResourceMark rm(THREAD);

    char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);

    UNICODE::convert_to_utf8(name, utf16_length, chars);

    return lookup(chars, utf8_length, THREAD);

  }

}

Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,

                                           unsigned int& hash) {

  int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);

  char stack_buf[ON_STACK_BUFFER_LENGTH];

  if (utf8_length < (int) sizeof(stack_buf)) {

    char* chars = stack_buf;

    UNICODE::convert_to_utf8(name, utf16_length, chars);

    return lookup_only(chars, utf8_length, hash);

  } else {

    ResourceMark rm;

    char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);

    UNICODE::convert_to_utf8(name, utf16_length, chars);

    return lookup_only(chars, utf8_length, hash);

  }

}

void SymbolTable::add(ClassLoaderData* loader_data, const constantPoolHandle& cp,

                      int names_count, const char** names, int* lengths,

                      int* cp_indices, unsigned int* hashValues, TRAPS) {

  bool c_heap = !loader_data->is_the_null_class_loader_data();

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

    const char *name = names[i];

    int len = lengths[i];

    unsigned int hash = hashValues[i];

    Symbol* sym = SymbolTable::the_table()->lookup_common(name, len, hash);

    if (sym == NULL) {

      sym = SymbolTable::the_table()->do_add_if_needed(name, len, hash, c_heap, CHECK);

    }

    assert(sym->refcount() != 0, "lookup should have incremented the count");

    cp->symbol_at_put(cp_indices[i], sym);

  }

}

class SymbolTableCreateEntry : public StackObj {

private:

  Thread*     _thread;

  const char* _name;

  int         _len;

  bool        _heap;

  Symbol*     _return;

  Symbol*     _created;

  void assert_for_name(Symbol* sym, const char* where) const {

#ifdef ASSERT

    assert(sym->utf8_length() == _len, "%s [%d,%d]", where, sym->utf8_length(), _len);

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

      assert(sym->byte_at(i) == (jbyte) _name[i],

             "%s [%d,%d,%d]", where, i, sym->byte_at(i), _name[i]);

    }

#endif

  }

public:

  SymbolTableCreateEntry(Thread* thread, const char* name, int len, bool heap)

  : _thread(thread), _name(name) , _len(len), _heap(heap), _return(NULL) , _created(NULL) {

    assert(_name != NULL, "expected valid name");

  }

  Symbol* operator()() {

    _created = SymbolTable::the_table()->allocate_symbol(_name, _len, _heap, _thread);

    assert(_created != NULL, "expected created symbol");

    assert_for_name(_created, "operator()()");

    assert(_created->equals(_name, _len),

           "symbol must be properly initialized [%p,%d,%d]", _name, _len, (int)_heap);

    return _created;

  }

  void operator()(bool inserted, Symbol** value) {

    assert(value != NULL, "expected valid value");

    assert(*value != NULL, "value should point to a symbol");

    if (!inserted && (_created != NULL)) {

      // We created our symbol, but someone else inserted

      // theirs first, so ours will be destroyed.

      // Since symbols are created with refcount of 1,

      // we must decrement it here to 0 to delete,

      // unless it's a permanent one.

      if (_created->refcount() != PERM_REFCOUNT) {

        assert(_created->refcount() == 1, "expected newly created symbol");

        _created->decrement_refcount();

        assert(_created->refcount() == 0, "expected dead symbol");

      }

    }

    _return = *value;

    assert_for_name(_return, "operator()");

  }

  Symbol* get_new_sym() const {

    assert_for_name(_return, "get_new_sym");

    return _return;

  }