/*

 * Copyright (c) 1997, 2015, 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/compactHashtable.inline.hpp"

#include "classfile/javaClasses.hpp"

#include "memory/metaspaceShared.hpp"

#include "prims/jvm.h"

#include "utilities/numberSeq.hpp"

#include <sys/stat.h>

/////////////////////////////////////////////////////

//

// The compact hash table writer implementations

//

CompactHashtableWriter::CompactHashtableWriter(int table_type,

                                               int num_entries,

                                               CompactHashtableStats* stats) {

  assert(DumpSharedSpaces, "dump-time only");

  _type = table_type;

  _num_entries = num_entries;

  _num_buckets = number_of_buckets(_num_entries);

  _buckets = NEW_C_HEAP_ARRAY(Entry*, _num_buckets, mtSymbol);

  memset(_buckets, 0, sizeof(Entry*) * _num_buckets);

  /* bucket sizes table */

  _bucket_sizes = NEW_C_HEAP_ARRAY(juint, _num_buckets, mtSymbol);

  memset(_bucket_sizes, 0, sizeof(juint) * _num_buckets);

  stats->hashentry_count = _num_entries;

  // Compact buckets' entries will have only the 4-byte offset, but

  // we don't know how many there will be at this point. So use a

  // conservative estimate here. The size is adjusted later when we

  // write out the buckets.

  stats->hashentry_bytes = _num_entries * 8;

  stats->bucket_count    = _num_buckets;

  stats->bucket_bytes    = (_num_buckets + 1) * (sizeof(juint));

  _stats = stats;

  // See compactHashtable.hpp for table layout

  _required_bytes = sizeof(juint) * 2; // _base_address, written as 2 juints

  _required_bytes+= sizeof(juint) +    // num_entries

                    sizeof(juint) +    // num_buckets

                    stats->hashentry_bytes +

                    stats->bucket_bytes;

}

CompactHashtableWriter::~CompactHashtableWriter() {

  for (int index = 0; index < _num_buckets; index++) {

    Entry* next = NULL;

    for (Entry* tent = _buckets[index]; tent; tent = next) {

      next = tent->next();

      delete tent;

    }

  }

  FREE_C_HEAP_ARRAY(juint, _bucket_sizes);

  FREE_C_HEAP_ARRAY(Entry*, _buckets);

}

// Calculate the number of buckets in the temporary hash table

int CompactHashtableWriter::number_of_buckets(int num_entries) {

  const int buksize = (int)SharedSymbolTableBucketSize;

  int num_buckets = (num_entries + buksize - 1) / buksize;

  num_buckets = (num_buckets + 1) & (~0x01);

  return num_buckets;

}

// Add a symbol entry to the temporary hash table

void CompactHashtableWriter::add(unsigned int hash, Entry* entry) {

  int index = hash % _num_buckets;

  entry->set_next(_buckets[index]);

  _buckets[index] = entry;

  _bucket_sizes[index] ++;

}

// Write the compact table's bucket infos

juint* CompactHashtableWriter::dump_table(juint* p, juint** first_bucket,

                                          NumberSeq* summary) {

  int index;

  juint* compact_table = p;

  // Compute the start of the buckets, include the compact_bucket_infos table

  // and the table end offset.

  juint offset = _num_buckets + 1;

  *first_bucket = compact_table + offset;

  for (index = 0; index < _num_buckets; index++) {

    int bucket_size = _bucket_sizes[index];

    if (bucket_size == 1) {

      // bucket with one entry is compacted and only has the symbol offset

      compact_table[index] = BUCKET_INFO(offset, COMPACT_BUCKET_TYPE);

      offset += bucket_size; // each entry contains symbol offset only

    } else {

      // regular bucket, each entry is a symbol (hash, offset) pair

      compact_table[index] = BUCKET_INFO(offset, REGULAR_BUCKET_TYPE);

      offset += bucket_size * 2; // each hash entry is 2 juints

    }

    if (offset & ~BUCKET_OFFSET_MASK) {

      vm_exit_during_initialization("CompactHashtableWriter::dump_table: Overflow! "

                                    "Too many symbols.");

    }

    summary->add(bucket_size);

  }

  // Mark the end of the table

  compact_table[_num_buckets] = BUCKET_INFO(offset, TABLEEND_BUCKET_TYPE);

  return compact_table;

}

// Write the compact table's entries

juint* CompactHashtableWriter::dump_buckets(juint* compact_table, juint* p,

                                            NumberSeq* summary) {

  uintx base_address = 0;

  uintx max_delta = 0;

  int num_compact_buckets = 0;

  if (_type == CompactHashtable<Symbol*, char>::_symbol_table) {

    base_address = uintx(MetaspaceShared::shared_rs()->base());

    max_delta    = uintx(MetaspaceShared::shared_rs()->size());

    assert(max_delta <= MAX_SHARED_DELTA, "range check");

  } else {

    assert((_type == CompactHashtable<oop, char>::_string_table), "unknown table");

    assert(UseCompressedOops, "UseCompressedOops is required");

  }

  assert(p != NULL, "sanity");

  for (int index = 0; index < _num_buckets; index++) {

    juint count = 0;

    int bucket_size = _bucket_sizes[index];

    int bucket_type = BUCKET_TYPE(compact_table[index]);

    if (bucket_size == 1) {

      assert(bucket_type == COMPACT_BUCKET_TYPE, "Bad bucket type");

      num_compact_buckets ++;

    }

    for (Entry* tent = _buckets[index]; tent;

         tent = tent->next()) {

      if (bucket_type == REGULAR_BUCKET_TYPE) {

        *p++ = juint(tent->hash()); // write entry hash

      }

      if (_type == CompactHashtable<Symbol*, char>::_symbol_table) {

        uintx deltax = uintx(tent->value()) - base_address;

        assert(deltax < max_delta, "range check");

        juint delta = juint(deltax);

        *p++ = delta; // write entry offset

      } else {

        *p++ = oopDesc::encode_heap_oop(tent->string());

      }

      count ++;

    }

    assert(count == _bucket_sizes[index], "sanity");

  }

  // Adjust the hashentry_bytes in CompactHashtableStats. Each compact

  // bucket saves 4-byte.

  _stats->hashentry_bytes -= num_compact_buckets * 4;

  return p;

}

// Write the compact table

void CompactHashtableWriter::dump(char** top, char* end) {

  NumberSeq summary;

  char* old_top = *top;

  juint* p = (juint*)(*top);

  uintx base_address = uintx(MetaspaceShared::shared_rs()->base());

  // Now write the following at the beginning of the table:

  //      base_address (uintx)

  //      num_entries  (juint)

  //      num_buckets  (juint)

  *p++ = high(base_address);

  *p++ = low (base_address); // base address

  *p++ = _num_entries;  // number of entries in the table

  *p++ = _num_buckets;  // number of buckets in the table

  juint* first_bucket = NULL;

  juint* compact_table = dump_table(p, &first_bucket, &summary);

  juint* bucket_end = dump_buckets(compact_table, first_bucket, &summary);

  assert(bucket_end <= (juint*)end, "cannot write past end");

  *top = (char*)bucket_end;

  if (PrintSharedSpaces) {

    double avg_cost = 0.0;

    if (_num_entries > 0) {

      avg_cost = double(_required_bytes)/double(_num_entries);

    }

    tty->print_cr("Shared %s table stats -------- base: " PTR_FORMAT,

                  table_name(), (intptr_t)base_address);

    tty->print_cr("Number of entries       : %9d", _num_entries);

    tty->print_cr("Total bytes used        : %9d", (int)((*top) - old_top));

    tty->print_cr("Average bytes per entry : %9.3f", avg_cost);

    tty->print_cr("Average bucket size     : %9.3f", summary.avg());

    tty->print_cr("Variance of bucket size : %9.3f", summary.variance());

    tty->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());

    tty->print_cr("Maximum bucket size     : %9d", (int)summary.maximum());

  }

}

const char* CompactHashtableWriter::table_name() {

  switch (_type) {

  case CompactHashtable<Symbol*, char>::_symbol_table: return "symbol";

  case CompactHashtable<oop, char>::_string_table: return "string";

  default:

    ;

  }

  return "unknown";

}

/////////////////////////////////////////////////////////////

//

// The CompactHashtable implementation

//

template <class T, class N> const char* CompactHashtable<T, N>::init(

                           CompactHashtableType type, const char* buffer) {

  assert(!DumpSharedSpaces, "run-time only");

  _type = type;

  juint*p = (juint*)buffer;

  juint upper = *p++;

  juint lower = *p++;

  _base_address = uintx(jlong_from(upper, lower));

  _entry_count = *p++;

  _bucket_count = *p++;

  _buckets = p;

  _table_end_offset = BUCKET_OFFSET(p[_bucket_count]); // located at the end of the bucket_info table

  juint *end = _buckets + _table_end_offset;

  return (const char*)end;

}

template <class T, class N> void CompactHashtable<T, N>::symbols_do(SymbolClosure *cl) {

  assert(!DumpSharedSpaces, "run-time only");

  for (juint i = 0; i < _bucket_count; i ++) {

    juint bucket_info = _buckets[i];

    juint bucket_offset = BUCKET_OFFSET(bucket_info);

    int   bucket_type = BUCKET_TYPE(bucket_info);

    juint* bucket = _buckets + bucket_offset;

    juint* bucket_end = _buckets;

    Symbol* sym;

    if (bucket_type == COMPACT_BUCKET_TYPE) {

      sym = (Symbol*)((void*)(_base_address + bucket[0]));

      cl->do_symbol(&sym);

    } else {

      bucket_end += BUCKET_OFFSET(_buckets[i + 1]);

      while (bucket < bucket_end) {

        sym = (Symbol*)((void*)(_base_address + bucket[1]));

        cl->do_symbol(&sym);

        bucket += 2;

      }

    }

  }

}

template <class T, class N> void CompactHashtable<T, N>::oops_do(OopClosure* f) {

  assert(!DumpSharedSpaces, "run-time only");

  assert(_type == _string_table || _bucket_count == 0, "sanity");

  for (juint i = 0; i < _bucket_count; i ++) {

    juint bucket_info = _buckets[i];

    juint bucket_offset = BUCKET_OFFSET(bucket_info);

    int   bucket_type = BUCKET_TYPE(bucket_info);

    juint* bucket = _buckets + bucket_offset;

    juint* bucket_end = _buckets;

    narrowOop o;

    if (bucket_type == COMPACT_BUCKET_TYPE) {

      o = (narrowOop)bucket[0];

      f->do_oop(&o);

    } else {

      bucket_end += BUCKET_OFFSET(_buckets[i + 1]);

      while (bucket < bucket_end) {

        o = (narrowOop)bucket[1];

        f->do_oop(&o);

        bucket += 2;

      }

    }

  }

}

// Explicitly instantiate these types

template class CompactHashtable<Symbol*, char>;

template class CompactHashtable<oop, char>;

#ifndef O_BINARY       // if defined (Win32) use binary files.

#define O_BINARY 0     // otherwise do nothing.

#endif

////////////////////////////////////////////////////////

//

// HashtableTextDump

//

HashtableTextDump::HashtableTextDump(const char* filename) : _fd(-1) {

  struct stat st;

  if (os::stat(filename, &st) != 0) {

    quit("Unable to get hashtable dump file size", filename);

  }

  _size = st.st_size;

  _fd = open(filename, O_RDONLY | O_BINARY, 0);

  if (_fd < 0) {

    quit("Unable to open hashtable dump file", filename);

  }

  _base = os::map_memory(_fd, filename, 0, NULL, _size, true, false);

  if (_base == NULL) {

    quit("Unable to map hashtable dump file", filename);

  }

  _p = _base;

  _end = _base + st.st_size;

  _filename = filename;

  _prefix_type = Unknown;

  _line_no = 1;

}

HashtableTextDump::~HashtableTextDump() {

  os::unmap_memory((char*)_base, _size);

  if (_fd >= 0) {

    close(_fd);

  }

}

void HashtableTextDump::quit(const char* err, const char* msg) {

  vm_exit_during_initialization(err, msg);

}

void HashtableTextDump::corrupted(const char *p, const char* msg) {

  char info[100];

  jio_snprintf(info, sizeof(info),

               "%s. Corrupted at line %d (file pos %d)",

               msg, _line_no, (int)(p - _base));

  quit(info, _filename);

}

bool HashtableTextDump::skip_newline() {

  if (_p[0] == '\r' && _p[1] == '\n') {

    _p += 2;

  } else if (_p[0] == '\n') {

    _p += 1;

  } else {

    corrupted(_p, "Unexpected character");

  }

  _line_no ++;

  return true;

}

int HashtableTextDump::skip(char must_be_char) {

  corrupted_if(remain() < 1, "Truncated");

  corrupted_if(*_p++ != must_be_char, "Unexpected character");

  return 0;

}

void HashtableTextDump::skip_past(char c) {

  for (;;) {

    corrupted_if(remain() < 1, "Truncated");

    if (*_p++ == c) {

      return;

    }

  }

}

void HashtableTextDump::check_version(const char* ver) {

  int len = (int)strlen(ver);

  corrupted_if(remain() < len, "Truncated");

  if (strncmp(_p, ver, len) != 0) {

    quit("wrong version of hashtable dump file", _filename);

  }

  _p += len;

  skip_newline();

}

void HashtableTextDump::scan_prefix_type() {

  _p ++;

  if (strncmp(_p, "SECTION: String", 15) == 0) {

    _p += 15;

    _prefix_type = StringPrefix;

  } else if (strncmp(_p, "SECTION: Symbol", 15) == 0) {

    _p += 15;

    _prefix_type = SymbolPrefix;

  } else {

    _prefix_type = Unknown;

  }

  skip_newline();

}

int HashtableTextDump::scan_prefix(int* utf8_length) {

  if (*_p == '@') {

    scan_prefix_type();

  }

  switch (_prefix_type) {

  case SymbolPrefix:

    *utf8_length = scan_symbol_prefix(); break;

  case StringPrefix:

    *utf8_length = scan_string_prefix(); break;

  default:

    tty->print_cr("Shared input data type: Unknown.");

    corrupted(_p, "Unknown data type");

  }

  return _prefix_type;

}

int HashtableTextDump::scan_string_prefix() {

  // Expect /[0-9]+: /

  int utf8_length = 0;

  get_num(':', &utf8_length);

  if (*_p != ' ') {

    corrupted(_p, "Wrong prefix format for string");

  }

  _p++;

  return utf8_length;

}

int HashtableTextDump::scan_symbol_prefix() {

  // Expect /[0-9]+ (-|)[0-9]+: /

  int utf8_length = 0;

  get_num(' ', &utf8_length);

  if (*_p == '-') {

    _p++;

  }

  int ref_num;

  get_num(':', &ref_num);

  if (*_p != ' ') {

    corrupted(_p, "Wrong prefix format for symbol");

  }

  _p++;

  return utf8_length;

}

jchar HashtableTextDump::unescape(const char* from, const char* end, int count) {

  jchar value = 0;

  corrupted_if(from + count > end, "Truncated");

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

    char c = *from++;

    switch (c) {

    case '0': case '1': case '2': case '3': case '4':

    case '5': case '6': case '7': case '8': case '9':

      value = (value << 4) + c - '0';

      break;

    case 'a': case 'b': case 'c':

    case 'd': case 'e': case 'f':

      value = (value << 4) + 10 + c - 'a';

      break;

    case 'A': case 'B': case 'C':

    case 'D': case 'E': case 'F':

      value = (value << 4) + 10 + c - 'A';

      break;

    default:

      ShouldNotReachHere();

    }

  }

  return value;

}

void HashtableTextDump::get_utf8(char* utf8_buffer, int utf8_length) {

  // cache in local vars

  const char* from = _p;

  const char* end = _end;

  char* to = utf8_buffer;

  int n = utf8_length;

  for (; n > 0 && from < end; n--) {

    if (*from != '\\') {

      *to++ = *from++;

    } else {

      corrupted_if(from + 2 > end, "Truncated");

      char c = from[1];

      from += 2;

      switch (c) {

      case 'x':

        {

          jchar value = unescape(from, end, 2);

          from += 2;

          assert(value <= 0xff, "sanity");

          *to++ = (char)(value & 0xff);

        }

        break;

      case 't':  *to++ = '\t'; break;

      case 'n':  *to++ = '\n'; break;

      case 'r':  *to++ = '\r'; break;

      case '\\': *to++ = '\\'; break;

      default:

        corrupted(_p, "Unsupported character");

      }

    }

  }

  corrupted_if(n > 0, "Truncated"); // expected more chars but file has ended

  _p = from;

  skip_newline();

}