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