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 254 //////////////////////////////////////////////////////////////////////// 255 // 256 // Read/Write the contents of a hashtable textual dump (created by 257 // SymbolTable::dump). 258 // Because the dump file may be big (hundred of MB in extreme cases), 259 // we use mmap for fast access when reading it. 260 // 261 class HashtableTextDump VALUE_OBJ_CLASS_SPEC { 262 int _fd; 263 const char* _base; 264 const char* _p; 265 const char* _end; 266 const char* _filename; 267 size_t _size; 268 public: 269 HashtableTextDump(const char* filename); 270 ~HashtableTextDump(); 271 272 void quit(const char* err, const char* msg); 273 274 inline int remain() { 275 return (int)(_end - _p); 276 } 277 278 void corrupted(const char *p); 279 280 inline void corrupted_if(bool cond) { 281 if (cond) { 282 corrupted(_p); 283 } 284 } 285 286 bool skip_newline(); 287 int skip(char must_be_char); 288 void skip_past(char c); 289 void check_version(const char* ver); 290 291 inline int get_num(char delim) { 292 const char* p = _p; 293 const char* end = _end; 294 int num = 0; 295 296 while (p < end) { 297 char c = *p ++; 298 if ('0' <= c && c <= '9') { 299 num = num * 10 + (c - '0'); 300 } else if (c == delim) { 301 _p = p; 302 return num; 303 } else { 304 corrupted(p-1); 305 } 306 } 307 corrupted(_end); 308 ShouldNotReachHere(); 309 return 0; 310 } 311 312 int scan_prefix(); 313 int scan_prefix2(); 314 315 jchar unescape(const char* from, const char* end, int count); 316 void get_utf8(char* utf8_buffer, int utf8_length); 317 static void put_utf8(outputStream* st, const char* utf8_string, int utf8_length); 318 }; 319 320 /////////////////////////////////////////////////////////////////////// 321 // 322 // jcmd command support for symbol table and string table dumping: 323 // VM.symboltable -verbose: for dumping the symbol table 324 // VM.stringtable -verbose: for dumping the string table 325 // 326 class VM_DumpHashtable : public VM_Operation { 327 private: 328 outputStream* _out; 329 int _which; 330 bool _verbose; 331 public: 332 enum { 333 DumpSymbols = 1 << 0, 334 DumpStrings = 1 << 1, 335 DumpSysDict = 1 << 2 // not implemented yet 336 }; 337 VM_DumpHashtable(outputStream* out, int which, bool verbose) { 338 _out = out; 339 _which = which; 340 _verbose = verbose; 341 } 342 343 virtual VMOp_Type type() const { return VMOp_DumpHashtable; } 344 345 virtual void doit() { 346 switch (_which) { 347 case DumpSymbols: 348 SymbolTable::dump(_out, _verbose); 349 break; 350 case DumpStrings: 351 StringTable::dump(_out, _verbose); 352 break; 353 default: 354 ShouldNotReachHere(); 355 } 356 } 357 }; 358 359 class SymboltableDCmd : public DCmdWithParser { 360 protected: 361 DCmdArgument<bool> _verbose; 362 public: 363 SymboltableDCmd(outputStream* output, bool heap); 364 static const char* name() { 365 return "VM.symboltable"; 366 } 367 static const char* description() { 368 return "Dump symbol table."; 369 } 370 static const char* impact() { 371 return "Medium: Depends on Java content."; 372 } 373 static const JavaPermission permission() { 374 JavaPermission p = {"java.lang.management.ManagementPermission", 375 "monitor", NULL}; 376 return p; 377 } 378 static int num_arguments(); 379 virtual void execute(DCmdSource source, TRAPS); 380 }; 381 382 class StringtableDCmd : public DCmdWithParser { 383 protected: 384 DCmdArgument<bool> _verbose; 385 public: 386 StringtableDCmd(outputStream* output, bool heap); 387 static const char* name() { 388 return "VM.stringtable"; 389 } 390 static const char* description() { 391 return "Dump string table."; 392 } 393 static const char* impact() { 394 return "Medium: Depends on Java content."; 395 } 396 static const JavaPermission permission() { 397 JavaPermission p = {"java.lang.management.ManagementPermission", 398 "monitor", NULL}; 399 return p; 400 } 401 static int num_arguments(); 402 virtual void execute(DCmdSource source, TRAPS); 403 }; 404 405 #endif // SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP