1 /* 2 * Copyright (c) 1997, 2016, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 * 23 */ 24 25 #include "precompiled.hpp" 26 #include "classfile/compactHashtable.inline.hpp" 27 #include "classfile/javaClasses.hpp" 28 #include "memory/metadataFactory.hpp" 29 #include "memory/metaspaceShared.hpp" 30 #include "prims/jvm.h" 31 #include "utilities/numberSeq.hpp" 32 #include <sys/stat.h> 33 34 ///////////////////////////////////////////////////// 35 // 36 // The compact hash table writer implementations 37 // 38 CompactHashtableWriter::CompactHashtableWriter(int num_buckets, 39 CompactHashtableStats* stats) { 40 assert(DumpSharedSpaces, "dump-time only"); 41 assert(num_buckets > 0, "no buckets"); 42 _num_buckets = num_buckets; 43 _num_entries = 0; 44 _buckets = NEW_C_HEAP_ARRAY(GrowableArray<Entry>*, _num_buckets, mtSymbol); 45 for (int i=0; i<_num_buckets; i++) { 46 _buckets[i] = new (ResourceObj::C_HEAP, mtSymbol) GrowableArray<Entry>(0, true, mtSymbol); 47 } 48 49 stats->bucket_count = _num_buckets; 50 stats->bucket_bytes = (_num_buckets + 1) * (sizeof(u4)); 51 _stats = stats; 52 _compact_buckets = NULL; 53 _compact_entries = NULL; 54 _num_empty_buckets = 0; 55 _num_value_only_buckets = 0; 56 _num_other_buckets = 0; 57 } 58 59 CompactHashtableWriter::~CompactHashtableWriter() { 60 for (int index = 0; index < _num_buckets; index++) { 61 GrowableArray<Entry>* bucket = _buckets[index]; 62 delete bucket; 63 } 64 65 FREE_C_HEAP_ARRAY(GrowableArray<Entry>*, _buckets); 66 } 67 68 // Add a symbol entry to the temporary hash table 69 void CompactHashtableWriter::add(unsigned int hash, u4 value) { 70 int index = hash % _num_buckets; 71 _buckets[index]->append_if_missing(Entry(hash, value)); 72 _num_entries++; 73 } 74 75 void CompactHashtableWriter::allocate_table() { 76 int entries_space = 0; 77 for (int index = 0; index < _num_buckets; index++) { 78 GrowableArray<Entry>* bucket = _buckets[index]; 79 int bucket_size = bucket->length(); 80 if (bucket_size == 1) { 81 entries_space++; 82 } else { 83 entries_space += 2 * bucket_size; 84 } 85 } 86 87 if (entries_space & ~BUCKET_OFFSET_MASK) { 88 vm_exit_during_initialization("CompactHashtableWriter::allocate_table: Overflow! " 89 "Too many entries."); 90 } 91 92 Thread* THREAD = VMThread::vm_thread(); 93 ClassLoaderData* loader_data = ClassLoaderData::the_null_class_loader_data(); 94 _compact_buckets = MetadataFactory::new_array<u4>(loader_data, _num_buckets + 1, THREAD); 95 _compact_entries = MetadataFactory::new_array<u4>(loader_data, entries_space, THREAD); 96 97 _stats->hashentry_count = _num_entries; 98 _stats->hashentry_bytes = entries_space * sizeof(u4); 99 } 100 101 // Write the compact table's buckets 102 void CompactHashtableWriter::dump_table(NumberSeq* summary) { 103 u4 offset = 0; 104 for (int index = 0; index < _num_buckets; index++) { 105 GrowableArray<Entry>* bucket = _buckets[index]; 106 int bucket_size = bucket->length(); 107 if (bucket_size == 1) { 108 // bucket with one entry is compacted and only has the symbol offset 109 _compact_buckets->at_put(index, BUCKET_INFO(offset, VALUE_ONLY_BUCKET_TYPE)); 110 111 Entry ent = bucket->at(0); 112 _compact_entries->at_put(offset++, ent.value()); 113 _num_value_only_buckets++; 114 } else { 115 // regular bucket, each entry is a symbol (hash, offset) pair 116 _compact_buckets->at_put(index, BUCKET_INFO(offset, REGULAR_BUCKET_TYPE)); 117 118 for (int i=0; i<bucket_size; i++) { 119 Entry ent = bucket->at(i); 120 _compact_entries->at_put(offset++, u4(ent.hash())); // write entry hash 121 _compact_entries->at_put(offset++, ent.value()); 122 } 123 if (bucket_size == 0) { 124 _num_empty_buckets++; 125 } else { 126 _num_other_buckets++; 127 } 128 } 129 summary->add(bucket_size); 130 } 131 132 // Mark the end of the buckets 133 _compact_buckets->at_put(_num_buckets, BUCKET_INFO(offset, TABLEEND_BUCKET_TYPE)); 134 assert(offset == (u4)_compact_entries->length(), "sanity"); 135 } 136 137 138 // Write the compact table 139 void CompactHashtableWriter::dump(SimpleCompactHashtable *cht, const char* table_name) { 140 NumberSeq summary; 141 allocate_table(); 142 dump_table(&summary); 143 144 int table_bytes = _stats->bucket_bytes + _stats->hashentry_bytes; 145 address base_address = address(MetaspaceShared::shared_rs()->base()); 146 cht->init(base_address, _num_entries, _num_buckets, 147 _compact_buckets->data(), _compact_entries->data()); 148 149 if (PrintSharedSpaces) { 150 double avg_cost = 0.0; 151 if (_num_entries > 0) { 152 avg_cost = double(table_bytes)/double(_num_entries); 153 } 154 tty->print_cr("Shared %s table stats -------- base: " PTR_FORMAT, 155 table_name, (intptr_t)base_address); 156 tty->print_cr("Number of entries : %9d", _num_entries); 157 tty->print_cr("Total bytes used : %9d", table_bytes); 158 tty->print_cr("Average bytes per entry : %9.3f", avg_cost); 159 tty->print_cr("Average bucket size : %9.3f", summary.avg()); 160 tty->print_cr("Variance of bucket size : %9.3f", summary.variance()); 161 tty->print_cr("Std. dev. of bucket size: %9.3f", summary.sd()); 162 tty->print_cr("Empty buckets : %9d", _num_empty_buckets); 163 tty->print_cr("Value_Only buckets : %9d", _num_value_only_buckets); 164 tty->print_cr("Other buckets : %9d", _num_other_buckets); 165 } 166 } 167 168 ///////////////////////////////////////////////////////////// 169 // 170 // Customization for dumping Symbol and String tables 171 172 void CompactSymbolTableWriter::add(unsigned int hash, Symbol *symbol) { 173 address base_address = address(MetaspaceShared::shared_rs()->base()); 174 175 uintx deltax = address(symbol) - base_address; 176 // The symbols are in RO space, which is smaler than MAX_SHARED_DELTA. 177 // The assert below is just to be extra cautious. 178 assert(deltax <= MAX_SHARED_DELTA, "the delta is too large to encode"); 179 u4 delta = u4(deltax); 180 181 CompactHashtableWriter::add(hash, delta); 182 } 183 184 void CompactStringTableWriter::add(unsigned int hash, oop string) { 185 CompactHashtableWriter::add(hash, oopDesc::encode_heap_oop(string)); 186 } 187 188 void CompactSymbolTableWriter::dump(CompactHashtable<Symbol*, char> *cht) { 189 CompactHashtableWriter::dump(cht, "symbol"); 190 } 191 192 void CompactStringTableWriter::dump(CompactHashtable<oop, char> *cht) { 193 CompactHashtableWriter::dump(cht, "string"); 194 } 195 196 ///////////////////////////////////////////////////////////// 197 // 198 // The CompactHashtable implementation 199 // 200 201 void SimpleCompactHashtable::serialize(SerializeClosure* soc) { 202 soc->do_ptr((void**)&_base_address); 203 soc->do_u4(&_entry_count); 204 soc->do_u4(&_bucket_count); 205 soc->do_ptr((void**)&_buckets); 206 soc->do_ptr((void**)&_entries); 207 } 208 209 bool SimpleCompactHashtable::exists(u4 value) { 210 assert(!DumpSharedSpaces, "run-time only"); 211 212 if (_entry_count == 0) { 213 return false; 214 } 215 216 unsigned int hash = (unsigned int)value; 217 int index = hash % _bucket_count; 218 u4 bucket_info = _buckets[index]; 219 u4 bucket_offset = BUCKET_OFFSET(bucket_info); 220 int bucket_type = BUCKET_TYPE(bucket_info); 221 u4* entry = _entries + bucket_offset; 222 223 if (bucket_type == VALUE_ONLY_BUCKET_TYPE) { 224 return (entry[0] == value); 225 } else { 226 u4*entry_max = _entries + BUCKET_OFFSET(_buckets[index + 1]); 227 while (entry <entry_max) { 228 if (entry[1] == value) { 229 return true; 230 } 231 entry += 2; 232 } 233 return false; 234 } 235 } 236 237 template <class I> 238 inline void SimpleCompactHashtable::iterate(const I& iterator) { 239 assert(!DumpSharedSpaces, "run-time only"); 240 for (u4 i = 0; i < _bucket_count; i++) { 241 u4 bucket_info = _buckets[i]; 242 u4 bucket_offset = BUCKET_OFFSET(bucket_info); 243 int bucket_type = BUCKET_TYPE(bucket_info); 244 u4* entry = _entries + bucket_offset; 245 246 if (bucket_type == VALUE_ONLY_BUCKET_TYPE) { 247 iterator.do_value(_base_address, entry[0]); 248 } else { 249 u4*entry_max = _entries + BUCKET_OFFSET(_buckets[i + 1]); 250 while (entry < entry_max) { 251 iterator.do_value(_base_address, entry[1]); 252 entry += 2; 253 } 254 } 255 } 256 } 257 258 template <class T, class N> void CompactHashtable<T, N>::serialize(SerializeClosure* soc) { 259 SimpleCompactHashtable::serialize(soc); 260 soc->do_u4(&_type); 261 } 262 263 class CompactHashtable_SymbolIterator { 264 SymbolClosure* const _closure; 265 public: 266 CompactHashtable_SymbolIterator(SymbolClosure *cl) : _closure(cl) {} 267 inline void do_value(address base_address, u4 offset) const { 268 Symbol* sym = (Symbol*)((void*)(base_address + offset)); 269 _closure->do_symbol(&sym); 270 } 271 }; 272 273 template <class T, class N> void CompactHashtable<T, N>::symbols_do(SymbolClosure *cl) { 274 CompactHashtable_SymbolIterator iterator(cl); 275 iterate(iterator); 276 } 277 278 class CompactHashtable_OopIterator { 279 OopClosure* const _closure; 280 public: 281 CompactHashtable_OopIterator(OopClosure *cl) : _closure(cl) {} 282 inline void do_value(address base_address, u4 offset) const { 283 narrowOop o = (narrowOop)offset; 284 _closure->do_oop(&o); 285 } 286 }; 287 288 template <class T, class N> void CompactHashtable<T, N>::oops_do(OopClosure* cl) { 289 assert(_type == _string_table || _bucket_count == 0, "sanity"); 290 CompactHashtable_OopIterator iterator(cl); 291 iterate(iterator); 292 } 293 294 // Explicitly instantiate these types 295 template class CompactHashtable<Symbol*, char>; 296 template class CompactHashtable<oop, char>; 297 298 #ifndef O_BINARY // if defined (Win32) use binary files. 299 #define O_BINARY 0 // otherwise do nothing. 300 #endif 301 302 //////////////////////////////////////////////////////// 303 // 304 // HashtableTextDump 305 // 306 HashtableTextDump::HashtableTextDump(const char* filename) : _fd(-1) { 307 struct stat st; 308 if (os::stat(filename, &st) != 0) { 309 quit("Unable to get hashtable dump file size", filename); 310 } 311 _size = st.st_size; 312 _fd = open(filename, O_RDONLY | O_BINARY, 0); 313 if (_fd < 0) { 314 quit("Unable to open hashtable dump file", filename); 315 } 316 _base = os::map_memory(_fd, filename, 0, NULL, _size, true, false); 317 if (_base == NULL) { 318 quit("Unable to map hashtable dump file", filename); 319 } 320 _p = _base; 321 _end = _base + st.st_size; 322 _filename = filename; 323 _prefix_type = Unknown; 324 _line_no = 1; 325 } 326 327 HashtableTextDump::~HashtableTextDump() { 328 os::unmap_memory((char*)_base, _size); 329 if (_fd >= 0) { 330 close(_fd); 331 } 332 } 333 334 void HashtableTextDump::quit(const char* err, const char* msg) { 335 vm_exit_during_initialization(err, msg); 336 } 337 338 void HashtableTextDump::corrupted(const char *p, const char* msg) { 339 char info[100]; 340 jio_snprintf(info, sizeof(info), 341 "%s. Corrupted at line %d (file pos %d)", 342 msg, _line_no, (int)(p - _base)); 343 quit(info, _filename); 344 } 345 346 bool HashtableTextDump::skip_newline() { 347 if (_p[0] == '\r' && _p[1] == '\n') { 348 _p += 2; 349 } else if (_p[0] == '\n') { 350 _p += 1; 351 } else { 352 corrupted(_p, "Unexpected character"); 353 } 354 _line_no++; 355 return true; 356 } 357 358 int HashtableTextDump::skip(char must_be_char) { 359 corrupted_if(remain() < 1, "Truncated"); 360 corrupted_if(*_p++ != must_be_char, "Unexpected character"); 361 return 0; 362 } 363 364 void HashtableTextDump::skip_past(char c) { 365 for (;;) { 366 corrupted_if(remain() < 1, "Truncated"); 367 if (*_p++ == c) { 368 return; 369 } 370 } 371 } 372 373 void HashtableTextDump::check_version(const char* ver) { 374 int len = (int)strlen(ver); 375 corrupted_if(remain() < len, "Truncated"); 376 if (strncmp(_p, ver, len) != 0) { 377 quit("wrong version of hashtable dump file", _filename); 378 } 379 _p += len; 380 skip_newline(); 381 } 382 383 void HashtableTextDump::scan_prefix_type() { 384 _p++; 385 if (strncmp(_p, "SECTION: String", 15) == 0) { 386 _p += 15; 387 _prefix_type = StringPrefix; 388 } else if (strncmp(_p, "SECTION: Symbol", 15) == 0) { 389 _p += 15; 390 _prefix_type = SymbolPrefix; 391 } else { 392 _prefix_type = Unknown; 393 } 394 skip_newline(); 395 } 396 397 int HashtableTextDump::scan_prefix(int* utf8_length) { 398 if (*_p == '@') { 399 scan_prefix_type(); 400 } 401 402 switch (_prefix_type) { 403 case SymbolPrefix: 404 *utf8_length = scan_symbol_prefix(); break; 405 case StringPrefix: 406 *utf8_length = scan_string_prefix(); break; 407 default: 408 tty->print_cr("Shared input data type: Unknown."); 409 corrupted(_p, "Unknown data type"); 410 } 411 412 return _prefix_type; 413 } 414 415 int HashtableTextDump::scan_string_prefix() { 416 // Expect /[0-9]+: / 417 int utf8_length = 0; 418 get_num(':', &utf8_length); 419 if (*_p != ' ') { 420 corrupted(_p, "Wrong prefix format for string"); 421 } 422 _p++; 423 return utf8_length; 424 } 425 426 int HashtableTextDump::scan_symbol_prefix() { 427 // Expect /[0-9]+ (-|)[0-9]+: / 428 int utf8_length = 0; 429 get_num(' ', &utf8_length); 430 if (*_p == '-') { 431 _p++; 432 } 433 int ref_num; 434 get_num(':', &ref_num); 435 if (*_p != ' ') { 436 corrupted(_p, "Wrong prefix format for symbol"); 437 } 438 _p++; 439 return utf8_length; 440 } 441 442 jchar HashtableTextDump::unescape(const char* from, const char* end, int count) { 443 jchar value = 0; 444 445 corrupted_if(from + count > end, "Truncated"); 446 447 for (int i=0; i<count; i++) { 448 char c = *from++; 449 switch (c) { 450 case '0': case '1': case '2': case '3': case '4': 451 case '5': case '6': case '7': case '8': case '9': 452 value = (value << 4) + c - '0'; 453 break; 454 case 'a': case 'b': case 'c': 455 case 'd': case 'e': case 'f': 456 value = (value << 4) + 10 + c - 'a'; 457 break; 458 case 'A': case 'B': case 'C': 459 case 'D': case 'E': case 'F': 460 value = (value << 4) + 10 + c - 'A'; 461 break; 462 default: 463 ShouldNotReachHere(); 464 } 465 } 466 return value; 467 } 468 469 void HashtableTextDump::get_utf8(char* utf8_buffer, int utf8_length) { 470 // cache in local vars 471 const char* from = _p; 472 const char* end = _end; 473 char* to = utf8_buffer; 474 int n = utf8_length; 475 476 for (; n > 0 && from < end; n--) { 477 if (*from != '\\') { 478 *to++ = *from++; 479 } else { 480 corrupted_if(from + 2 > end, "Truncated"); 481 char c = from[1]; 482 from += 2; 483 switch (c) { 484 case 'x': 485 { 486 jchar value = unescape(from, end, 2); 487 from += 2; 488 assert(value <= 0xff, "sanity"); 489 *to++ = (char)(value & 0xff); 490 } 491 break; 492 case 't': *to++ = '\t'; break; 493 case 'n': *to++ = '\n'; break; 494 case 'r': *to++ = '\r'; break; 495 case '\\': *to++ = '\\'; break; 496 default: 497 corrupted(_p, "Unsupported character"); 498 } 499 } 500 } 501 corrupted_if(n > 0, "Truncated"); // expected more chars but file has ended 502 _p = from; 503 skip_newline(); 504 } 505 506 // NOTE: the content is NOT the same as 507 // UTF8::as_quoted_ascii(const char* utf8_str, int utf8_length, char* buf, int buflen). 508 // We want to escape \r\n\t so that output [1] is more readable; [2] can be more easily 509 // parsed by scripts; [3] quickly processed by HashtableTextDump::get_utf8() 510 void HashtableTextDump::put_utf8(outputStream* st, const char* utf8_string, int utf8_length) { 511 const char *c = utf8_string; 512 const char *end = c + utf8_length; 513 for (; c < end; c++) { 514 switch (*c) { 515 case '\t': st->print("\\t"); break; 516 case '\r': st->print("\\r"); break; 517 case '\n': st->print("\\n"); break; 518 case '\\': st->print("\\\\"); break; 519 default: 520 if (isprint(*c)) { 521 st->print("%c", *c); 522 } else { 523 st->print("\\x%02x", ((unsigned int)*c) & 0xff); 524 } 525 } 526 } 527 }