1 /* 2 * Copyright (c) 1997, 2014, 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 #ifndef SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP 26 #define SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP 27 28 #include "classfile/stringTable.hpp" 29 #include "classfile/symbolTable.hpp" 30 #include "memory/allocation.inline.hpp" 31 #include "oops/symbol.hpp" 32 #include "services/diagnosticCommand.hpp" 33 #include "utilities/hashtable.hpp" 34 35 class NumberSeq; 36 37 // Stats for symbol tables in the CDS archive 38 class CompactHashtableStats VALUE_OBJ_CLASS_SPEC { 39 public: 40 int hashentry_count; 41 int hashentry_bytes; 42 int bucket_count; 43 int bucket_bytes; 44 }; 45 46 ///////////////////////////////////////////////////////////////////////// 47 // 48 // The compact hash table writer. Used at dump time for writing out 49 // the compact table to the shared archive. 50 // 51 // At dump time, the CompactHashtableWriter obtains all entries from the 52 // symbol table and adds them to a new temporary hash table. The hash 53 // table size (number of buckets) is calculated using 54 // '(num_entries + bucket_size - 1) / bucket_size'. The default bucket 55 // size is 4 and can be changed by -XX:SharedSymbolTableBucketSize option. 56 // 4 is chosen because it produces smaller sized bucket on average for 57 // faster lookup. It also has relatively small number of empty buckets and 58 // good distribution of the entries. 59 // 60 // We use a simple hash function (symbol_hash % num_bucket) for the table. 61 // The new table is compacted when written out. Please see comments 62 // above the CompactHashtable class for the table layout detail. The bucket 63 // offsets are written to the archive as part of the compact table. The 64 // bucket offset is encoded in the low 30-bit (0-29) and the bucket type 65 // (regular or compact) are encoded in bit[31, 30]. For buckets with more 66 // than one entry, both symbol hash and symbol offset are written to the 67 // table. For buckets with only one entry, only the symbol offset is written 68 // to the table and the buckets are tagged as compact in their type bits. 69 // Buckets without entry are skipped from the table. Their offsets are 70 // still written out for faster lookup. 71 // 72 class CompactHashtableWriter: public StackObj { 73 public: 74 class Entry: public CHeapObj<mtSymbol> { 75 Entry* _next; 76 unsigned int _hash; 77 void* _literal; 78 79 public: 80 Entry(unsigned int hash, Symbol *symbol) : _next(NULL), _hash(hash), _literal(symbol) {} 81 82 void *value() { 83 return _literal; 84 } 85 Symbol *symbol() { 86 return (Symbol*)_literal; 87 } 88 unsigned int hash() { 89 return _hash; 90 } 91 Entry *next() {return _next;} 92 void set_next(Entry *p) {_next = p;} 93 }; // class CompactHashtableWriter::Entry 94 95 private: 96 static int number_of_buckets(int num_entries); 97 98 const char* _table_name; 99 int _num_entries; 100 int _num_buckets; 101 juint* _bucket_sizes; 102 Entry** _buckets; 103 int _required_bytes; 104 CompactHashtableStats* _stats; 105 106 public: 107 // This is called at dump-time only 108 CompactHashtableWriter(const char* table_name, int num_entries, CompactHashtableStats* stats); 109 ~CompactHashtableWriter(); 110 111 int get_required_bytes() { 112 return _required_bytes; 113 } 114 115 void add(unsigned int hash, Symbol* symbol) { 116 add(hash, new Entry(hash, symbol)); 117 } 118 119 private: 120 void add(unsigned int hash, Entry* entry); 121 juint* dump_table(juint* p, juint** first_bucket, NumberSeq* summary); 122 juint* dump_buckets(juint* table, juint* p, NumberSeq* summary); 123 124 public: 125 void dump(char** top, char* end); 126 }; 127 128 #define REGULAR_BUCKET_TYPE 0 129 #define COMPACT_BUCKET_TYPE 1 130 #define TABLEEND_BUCKET_TYPE 3 131 #define BUCKET_OFFSET_MASK 0x3FFFFFFF 132 #define BUCKET_OFFSET(info) ((info) & BUCKET_OFFSET_MASK) 133 #define BUCKET_TYPE_SHIFT 30 134 #define BUCKET_TYPE(info) (((info) & ~BUCKET_OFFSET_MASK) >> BUCKET_TYPE_SHIFT) 135 #define BUCKET_INFO(offset, type) (((type) << BUCKET_TYPE_SHIFT) | ((offset) & BUCKET_OFFSET_MASK)) 136 137 ///////////////////////////////////////////////////////////////////////////// 138 // 139 // CompactHashtable is used to stored the CDS archive's symbol table. Used 140 // at runtime only to access the compact table from the archive. 141 // 142 // Because these tables are read-only (no entries can be added/deleted) at run-time 143 // and tend to have large number of entries, we try to minimize the footprint 144 // cost per entry. 145 // 146 // Layout of compact symbol table in the shared archive: 147 // 148 // uintx base_address; 149 // juint num_symbols; 150 // juint num_buckets; 151 // juint bucket_infos[num_buckets+1]; // bit[31,30]: type; bit[29-0]: offset 152 // juint table[] 153 // 154 // ----------------------------------- 155 // | base_address | num_symbols | 156 // |---------------------------------| 157 // | num_buckets | bucket_info0 | 158 // |---------------------------------| 159 // | bucket_info1 | bucket_info2 | 160 // | bucket_info3 ... | 161 // | .... | table_end_info | 162 // |---------------------------------| 163 // | entry0 | 164 // | entry1 | 165 // | entry2 | 166 // | | 167 // | ... | 168 // ----------------------------------- 169 // 170 // The size of the bucket_info table is 'num_buckets + 1'. Each entry of the 171 // bucket_info table is a 32-bit encoding of the bucket type and bucket offset, 172 // with the type in the left-most 2-bit and offset in the remaining 30-bit. 173 // The last entry is a special type. It contains the offset of the last 174 // bucket end. We use that information when traversing the compact table. 175 // 176 // There are two types of buckets, regular buckets and compact buckets. The 177 // compact buckets have '01' in their highest 2-bit, and regular buckets have 178 // '00' in their highest 2-bit. 179 // 180 // For normal buckets, each symbol's entry is 8 bytes in the table[]: 181 // juint hash; /* symbol hash */ 182 // juint offset; /* Symbol* sym = (Symbol*)(base_address + offset) */ 183 // 184 // For compact buckets, each entry has only the 4-byte 'offset' in the table[]. 185 // 186 // See CompactHashtable::lookup() for how the table is searched at runtime. 187 // See CompactHashtableWriter::dump() for how the table is written at CDS 188 // dump time. 189 // 190 template <class T, class N> class CompactHashtable VALUE_OBJ_CLASS_SPEC { 191 uintx _base_address; 192 juint _entry_count; 193 juint _bucket_count; 194 juint _table_end_offset; 195 juint* _buckets; 196 197 inline bool equals(T entry, const char* name, int len) { 198 if (entry->equals(name, len)) { 199 assert(entry->refcount() == -1, "must be shared"); 200 return true; 201 } else { 202 return false; 203 } 204 } 205 206 public: 207 CompactHashtable() { 208 _entry_count = 0; 209 _bucket_count = 0; 210 _table_end_offset = 0; 211 _buckets = 0; 212 } 213 const char* init(const char *buffer); 214 215 // Lookup an entry from the compact table 216 inline T lookup(const N* name, unsigned int hash, int len) { 217 if (_entry_count > 0) { 218 assert(!DumpSharedSpaces, "run-time only"); 219 int index = hash % _bucket_count; 220 juint bucket_info = _buckets[index]; 221 juint bucket_offset = BUCKET_OFFSET(bucket_info); 222 int bucket_type = BUCKET_TYPE(bucket_info); 223 juint* bucket = _buckets + bucket_offset; 224 juint* bucket_end = _buckets; 225 226 if (bucket_type == COMPACT_BUCKET_TYPE) { 227 // the compact bucket has one entry with symbol offset only 228 T entry = (T)((void*)(_base_address + bucket[0])); 229 if (equals(entry, name, len)) { 230 return entry; 231 } 232 } else { 233 // This is a regular bucket, which has more than one 234 // entries. Each entry is a pair of symbol (hash, offset). 235 // Seek until the end of the bucket. 236 bucket_end += BUCKET_OFFSET(_buckets[index + 1]); 237 while (bucket < bucket_end) { 238 unsigned int h = (unsigned int)(bucket[0]); 239 if (h == hash) { 240 juint offset = bucket[1]; 241 T entry = (T)((void*)(_base_address + offset)); 242 if (equals(entry, name, len)) { 243 return entry; 244 } 245 } 246 bucket += 2; 247 } 248 } 249 } 250 return NULL; 251 } 252 253 // iterate over symbols 254 void symbols_do(SymbolClosure *cl); 255 }; 256 257 //////////////////////////////////////////////////////////////////////// 258 // 259 // Read/Write the contents of a hashtable textual dump (created by 260 // SymbolTable::dump). 261 // Because the dump file may be big (hundred of MB in extreme cases), 262 // we use mmap for fast access when reading it. 263 // 264 class HashtableTextDump VALUE_OBJ_CLASS_SPEC { 265 int _fd; 266 const char* _base; 267 const char* _p; 268 const char* _end; 269 const char* _filename; 270 size_t _size; 271 public: 272 HashtableTextDump(const char* filename); 273 ~HashtableTextDump(); 274 275 void quit(const char* err, const char* msg); 276 277 inline int remain() { 278 return (int)(_end - _p); 279 } 280 281 void corrupted(const char *p); 282 283 inline void corrupted_if(bool cond) { 284 if (cond) { 285 corrupted(_p); 286 } 287 } 288 289 bool skip_newline(); 290 int skip(char must_be_char); 291 void skip_past(char c); 292 void check_version(const char* ver); 293 294 inline int get_num(char delim) { 295 const char* p = _p; 296 const char* end = _end; 297 int num = 0; 298 299 while (p < end) { 300 char c = *p ++; 301 if ('0' <= c && c <= '9') { 302 num = num * 10 + (c - '0'); 303 } else if (c == delim) { 304 _p = p; 305 return num; 306 } else { 307 corrupted(p-1); 308 } 309 } 310 corrupted(_end); 311 ShouldNotReachHere(); 312 return 0; 313 } 314 315 int scan_prefix(); 316 int scan_prefix2(); 317 318 jchar unescape(const char* from, const char* end, int count); 319 void get_utf8(char* utf8_buffer, int utf8_length); 320 static void put_utf8(outputStream* st, const char* utf8_string, int utf8_length); 321 }; 322 323 /////////////////////////////////////////////////////////////////////// 324 // 325 // jcmd command support for symbol table and string table dumping: 326 // VM.symboltable -verbose: for dumping the symbol table 327 // VM.stringtable -verbose: for dumping the string table 328 // 329 class VM_DumpHashtable : public VM_Operation { 330 private: 331 outputStream* _out; 332 int _which; 333 bool _verbose; 334 public: 335 enum { 336 DumpSymbols = 1 << 0, 337 DumpStrings = 1 << 1, 338 DumpSysDict = 1 << 2 // not implemented yet 339 }; 340 VM_DumpHashtable(outputStream* out, int which, bool verbose) { 341 _out = out; 342 _which = which; 343 _verbose = verbose; 344 } 345 346 virtual VMOp_Type type() const { return VMOp_DumpHashtable; } 347 348 virtual void doit() { 349 switch (_which) { 350 case DumpSymbols: 351 SymbolTable::dump(_out, _verbose); 352 break; 353 case DumpStrings: 354 StringTable::dump(_out, _verbose); 355 break; 356 default: 357 ShouldNotReachHere(); 358 } 359 } 360 }; 361 362 class SymboltableDCmd : public DCmdWithParser { 363 protected: 364 DCmdArgument<bool> _verbose; 365 public: 366 SymboltableDCmd(outputStream* output, bool heap); 367 static const char* name() { 368 return "VM.symboltable"; 369 } 370 static const char* description() { 371 return "Dump symbol table."; 372 } 373 static const char* impact() { 374 return "Medium: Depends on Java content."; 375 } 376 static const JavaPermission permission() { 377 JavaPermission p = {"java.lang.management.ManagementPermission", 378 "monitor", NULL}; 379 return p; 380 } 381 static int num_arguments(); 382 virtual void execute(DCmdSource source, TRAPS); 383 }; 384 385 class StringtableDCmd : public DCmdWithParser { 386 protected: 387 DCmdArgument<bool> _verbose; 388 public: 389 StringtableDCmd(outputStream* output, bool heap); 390 static const char* name() { 391 return "VM.stringtable"; 392 } 393 static const char* description() { 394 return "Dump string table."; 395 } 396 static const char* impact() { 397 return "Medium: Depends on Java content."; 398 } 399 static const JavaPermission permission() { 400 JavaPermission p = {"java.lang.management.ManagementPermission", 401 "monitor", NULL}; 402 return p; 403 } 404 static int num_arguments(); 405 virtual void execute(DCmdSource source, TRAPS); 406 }; 407 408 #endif // SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP