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 #include "precompiled.hpp"
26 #include "classfile/javaClasses.hpp"
27 #include "memory/metaspaceShared.hpp"
28 #include "utilities/numberSeq.hpp"
29 #include <sys/stat.h>
30
31 /////////////////////////////////////////////////////
32 //
33 // The compact hash table writer implementations
34 //
35 CompactHashtableWriter::CompactHashtableWriter(const char* table_name,
36 int num_entries,
37 CompactHashtableStats* stats) {
38 assert(DumpSharedSpaces, "dump-time only");
39 _table_name = table_name;
40 _num_entries = num_entries;
41 _num_buckets = number_of_buckets(_num_entries);
42 _buckets = NEW_C_HEAP_ARRAY(Entry*, _num_buckets, mtSymbol);
43 memset(_buckets, 0, sizeof(Entry*) * _num_buckets);
44
45 /* bucket sizes table */
46 _bucket_sizes = NEW_C_HEAP_ARRAY(juint, _num_buckets, mtSymbol);
47 memset(_bucket_sizes, 0, sizeof(juint) * _num_buckets);
48
49 stats->hashentry_count = _num_entries;
50 // Compact buckets' entries will have only the 4-byte offset, but
51 // we don't know how many there will be at this point. So use a
52 // conservative estimate here. The size is adjusted later when we
53 // write out the buckets.
54 stats->hashentry_bytes = _num_entries * 8;
55 stats->bucket_count = _num_buckets;
56 stats->bucket_bytes = (_num_buckets + 1) * (sizeof(juint));
57 _stats = stats;
58
59 // See compactHashtable.hpp for table layout
60 _required_bytes = sizeof(juint) * 2; // _base_address, written as 2 juints
61 _required_bytes+= sizeof(juint) + // num_entries
62 sizeof(juint) + // num_buckets
63 stats->hashentry_bytes +
64 stats->bucket_bytes;
65 }
66
67 CompactHashtableWriter::~CompactHashtableWriter() {
68 for (int index = 0; index < _num_buckets; index++) {
69 Entry* next = NULL;
70 for (Entry* tent = _buckets[index]; tent; tent = next) {
71 next = tent->next();
72 delete tent;
73 }
74 }
75
76 FREE_C_HEAP_ARRAY(juint, _bucket_sizes);
77 FREE_C_HEAP_ARRAY(Entry*, _buckets);
78 }
79
80 // Calculate the number of buckets in the temporary hash table
81 int CompactHashtableWriter::number_of_buckets(int num_entries) {
82 const int buksize = (int)SharedSymbolTableBucketSize;
83 int num_buckets = (num_entries + buksize - 1) / buksize;
84 num_buckets = (num_buckets + 1) & (~0x01);
85
86 return num_buckets;
87 }
88
89 // Add a symbol entry to the temporary hash table
90 void CompactHashtableWriter::add(unsigned int hash, Entry* entry) {
91 int index = hash % _num_buckets;
92 entry->set_next(_buckets[index]);
93 _buckets[index] = entry;
94 _bucket_sizes[index] ++;
95 }
96
97 // Write the compact table's bucket infos
98 juint* CompactHashtableWriter::dump_table(juint* p, juint** first_bucket,
99 NumberSeq* summary) {
100 int index;
101 juint* compact_table = p;
102 // Find the start of the buckets, skip the compact_bucket_infos table
103 // and the table end offset.
104 juint offset = _num_buckets + 1;
105 *first_bucket = compact_table + offset;
106
107 for (index = 0; index < _num_buckets; index++) {
108 int bucket_size = _bucket_sizes[index];
109 if (bucket_size == 1) {
110 // bucket with one entry is compacted and only has the symbol offset
111 compact_table[index] = BUCKET_INFO(offset, COMPACT_BUCKET_TYPE);
112 offset += bucket_size; // each entry contains symbol offset only
113 } else {
114 // regular bucket, each entry is a symbol (hash, offset) pair
115 compact_table[index] = BUCKET_INFO(offset, REGULAR_BUCKET_TYPE);
116 offset += bucket_size * 2; // each hash entry is 2 juints
117 }
118 if (offset & ~BUCKET_OFFSET_MASK) {
119 vm_exit_during_initialization("CompactHashtableWriter::dump_table: Overflow! "
120 "Too many symbols.");
121 }
122 summary->add(bucket_size);
123 }
124 // Mark the end of the table
125 compact_table[_num_buckets] = BUCKET_INFO(offset, TABLEEND_BUCKET_TYPE);
126
127 return compact_table;
128 }
129
130 // Write the compact table's entries
131 juint* CompactHashtableWriter::dump_buckets(juint* compact_table, juint* p,
132 NumberSeq* summary) {
133 uintx base_address = uintx(MetaspaceShared::shared_rs()->base());
134 uintx max_delta = uintx(MetaspaceShared::shared_rs()->size());
135 assert(max_delta <= 0x7fffffff, "range check");
136 int num_compact_buckets = 0;
137
138 assert(p != NULL, "sanity");
139 for (int index = 0; index < _num_buckets; index++) {
140 juint count = 0;
141 int bucket_size = _bucket_sizes[index];
142 int bucket_type = BUCKET_TYPE(compact_table[index]);
143
144 if (bucket_size == 1) {
145 assert(bucket_type == COMPACT_BUCKET_TYPE, "Bad bucket type");
146 num_compact_buckets ++;
147 }
148 for (Entry* tent = _buckets[index]; tent;
149 tent = tent->next()) {
150 if (bucket_type == REGULAR_BUCKET_TYPE) {
151 *p++ = juint(tent->hash()); // write symbol hash
152 }
153 uintx deltax = uintx(tent->value()) - base_address;
154 assert(deltax < max_delta, "range check");
155 juint delta = juint(deltax);
156 *p++ = delta; // write symbol offset
157 count ++;
158 }
159 assert(count == _bucket_sizes[index], "sanity");
160 }
161
162 // Adjust the hashentry_bytes in CompactHashtableStats. Each compact
163 // bucket saves 4-byte.
164 _stats->hashentry_bytes -= num_compact_buckets * 4;
165
166 return p;
167 }
168
169 // Write the compact table
170 void CompactHashtableWriter::dump(char** top, char* end) {
171 NumberSeq summary;
172 char* old_top = *top;
173 juint* p = (juint*)(*top);
174
175 uintx base_address = uintx(MetaspaceShared::shared_rs()->base());
176
177 *p++ = high(base_address);
178 *p++ = low (base_address); // base address
179 *p++ = _num_entries; // number of entries in the table
180 *p++ = _num_buckets; // number of buckets in the table
181
182 juint* first_bucket = NULL;
183 juint* compact_table = dump_table(p, &first_bucket, &summary);
184 juint* bucket_end = dump_buckets(compact_table, first_bucket, &summary);
185
186 assert(bucket_end <= (juint*)end, "cannot write past end");
187 *top = (char*)bucket_end;
188
189 if (PrintSharedSpaces) {
190 double avg_cost = 0.0;
191 if (_num_entries > 0) {
192 avg_cost = double(_required_bytes)/double(_num_entries);
193 }
194 tty->print_cr("Shared %s table stats -------- base: " PTR_FORMAT, _table_name, (intptr_t)base_address);
195 tty->print_cr("Number of entries : %9d", _num_entries);
196 tty->print_cr("Total bytes used : %9d", (int)((*top) - old_top));
197 tty->print_cr("Average bytes per entry : %9.3f", avg_cost);
198 tty->print_cr("Average bucket size : %9.3f", summary.avg());
199 tty->print_cr("Variance of bucket size : %9.3f", summary.variance());
200 tty->print_cr("Std. dev. of bucket size: %9.3f", summary.sd());
201 tty->print_cr("Maximum bucket size : %9d", (int)summary.maximum());
202 }
203 }
204
205 /////////////////////////////////////////////////////////////
206 //
207 // The CompactHashtable implementation
208 //
209 template <class T, class N> const char* CompactHashtable<T, N>::init(const char* buffer) {
210 assert(!DumpSharedSpaces, "run-time only");
211 juint*p = (juint*)buffer;
212 juint upper = *p++;
213 juint lower = *p++;
214 _base_address = uintx(jlong_from(upper, lower));
215 _entry_count = *p++;
216 _bucket_count = *p++;
217 _buckets = p;
218 _table_end_offset = BUCKET_OFFSET(p[_bucket_count]); // located at the end of the bucket_info table
219
220 juint *end = _buckets + _table_end_offset;
221 return (const char*)end;
222 }
223
224 template <class T, class N> void CompactHashtable<T, N>::symbols_do(SymbolClosure *cl) {
225 assert(!DumpSharedSpaces, "run-time only");
226 for (juint i = 0; i < _bucket_count; i ++) {
227 juint bucket_info = _buckets[i];
228 juint bucket_offset = BUCKET_OFFSET(bucket_info);
229 int bucket_type = BUCKET_TYPE(bucket_info);
230 juint* bucket = _buckets + bucket_offset;
231 juint* bucket_end = _buckets;
232
233 Symbol* sym;
234 if (bucket_type == COMPACT_BUCKET_TYPE) {
235 sym = (Symbol*)((void*)(_base_address + bucket[0]));
236 cl->do_symbol(&sym);
237 } else {
238 bucket_end += BUCKET_OFFSET(_buckets[i + 1]);
239 while (bucket < bucket_end) {
240 sym = (Symbol*)((void*)(_base_address + bucket[1]));
241 cl->do_symbol(&sym);
242 bucket += 2;
243 }
244 }
245 }
246 }
247
248 // Explicitly instantiate these types
249 template class CompactHashtable<Symbol*, char>;
250
251 #ifndef O_BINARY // if defined (Win32) use binary files.
252 #define O_BINARY 0 // otherwise do nothing.
253 #endif
254
255 ////////////////////////////////////////////////////////
256 //
257 // HashtableTextDump
258 //
259 HashtableTextDump::HashtableTextDump(const char* filename) : _fd(-1) {
260 struct stat st;
261 if (os::stat(filename, &st) != 0) {
262 quit("Unable to get hashtable dump file size", filename);
263 }
264 _size = st.st_size;
265 _fd = open(filename, O_RDONLY | O_BINARY, 0);
266 if (_fd < 0) {
267 quit("Unable to open hashtable dump file", filename);
268 }
269 _base = os::map_memory(_fd, filename, 0, NULL, _size, true, false);
270 if (_base == NULL) {
271 quit("Unable to map hashtable dump file", filename);
272 }
273 _p = _base;
274 _end = _base + st.st_size;
275 _filename = filename;
276 }
277
278 HashtableTextDump::~HashtableTextDump() {
279 os::unmap_memory((char*)_base, _size);
280 if (_fd >= 0) {
281 close(_fd);
282 }
283 }
284
285 void HashtableTextDump::quit(const char* err, const char* msg) {
286 vm_exit_during_initialization(err, msg);
287 }
288
289 void HashtableTextDump::corrupted(const char *p) {
290 char info[60];
291 sprintf(info, "corrupted at pos %d", (int)(p - _base));
292 quit(info, _filename);
293 }
294
295 bool HashtableTextDump::skip_newline() {
296 if (_p[0] == '\r' && _p[1] == '\n') {
297 _p += 2;
298 } else if (_p[0] == '\n') {
299 _p += 1;
300 } else {
301 corrupted(_p);
302 }
303 return true;
304 }
305
306 int HashtableTextDump::skip(char must_be_char) {
307 corrupted_if(remain() < 1);
308 corrupted_if(*_p++ != must_be_char);
309 return 0;
310 }
311
312 void HashtableTextDump::skip_past(char c) {
313 for (;;) {
314 corrupted_if(remain() < 1);
315 if (*_p++ == c) {
316 return;
317 }
318 }
319 }
320
321 void HashtableTextDump::check_version(const char* ver) {
322 int len = (int)strlen(ver);
323 corrupted_if(remain() < len);
324 if (strncmp(_p, ver, len) != 0) {
325 quit("wrong version of hashtable dump file", _filename);
326 }
327 _p += len;
328 skip_newline();
329 }
330
331
332 int HashtableTextDump::scan_prefix() {
333 // Expect /[0-9]+: /
334 int utf8_length = get_num(':');
335 if (*_p != ' ') {
336 corrupted(_p);
337 }
338 _p++;
339 return utf8_length;
340 }
341
342 int HashtableTextDump::scan_prefix2() {
343 // Expect /[0-9]+ (-|)[0-9]+: /
344 int utf8_length = get_num(' ');
345 if (*_p == '-') {
346 _p++;
347 }
348 (void)get_num(':');
349 if (*_p != ' ') {
350 corrupted(_p);
351 }
352 _p++;
353 return utf8_length;
354 }
355
356 jchar HashtableTextDump::unescape(const char* from, const char* end, int count) {
357 jchar value = 0;
358
359 corrupted_if(from + count > end);
360
361 for (int i=0; i<count; i++) {
362 char c = *from++;
363 switch (c) {
364 case '0': case '1': case '2': case '3': case '4':
365 case '5': case '6': case '7': case '8': case '9':
366 value = (value << 4) + c - '0';
367 break;
368 case 'a': case 'b': case 'c':
369 case 'd': case 'e': case 'f':
370 value = (value << 4) + 10 + c - 'a';
371 break;
372 case 'A': case 'B': case 'C':
373 case 'D': case 'E': case 'F':
374 value = (value << 4) + 10 + c - 'A';
375 break;
376 default:
377 ShouldNotReachHere();
378 }
379 }
380 return value;
381 }
382
383 void HashtableTextDump::get_utf8(char* utf8_buffer, int utf8_length) {
384 // cache in local vars
385 const char* from = _p;
386 const char* end = _end;
387 char* to = utf8_buffer;
388 int n = utf8_length;
389
390 for (; n > 0 && from < end; n--) {
391 if (*from != '\\') {
392 *to++ = *from++;
393 } else {
394 corrupted_if(from + 2 > end);
395 char c = from[1];
396 from += 2;
397 switch (c) {
398 case 'x':
399 {
400 jchar value = unescape(from, end, 2);
401 from += 2;
402 assert(value <= 0xff, "sanity");
403 *to++ = (char)(value & 0xff);
404 }
405 break;
406 case 't': *to++ = '\t'; break;
407 case 'n': *to++ = '\n'; break;
408 case 'r': *to++ = '\r'; break;
409 case '\\': *to++ = '\\'; break;
410 default:
411 ShouldNotReachHere();
412 }
413 }
414 }
415 corrupted_if(n > 0); // expected more chars but file has ended
416 _p = from;
417 skip_newline();
418 }
419
420 // NOTE: the content is NOT the same as
421 // UTF8::as_quoted_ascii(const char* utf8_str, int utf8_length, char* buf, int buflen).
422 // We want to escape \r\n\t so that output [1] is more readable; [2] can be more easily
423 // parsed by scripts; [3] quickly processed by HashtableTextDump::get_utf8()
424 void HashtableTextDump::put_utf8(outputStream* st, const char* utf8_string, int utf8_length) {
425 const char *c = utf8_string;
426 const char *end = c + utf8_length;
427 for (; c < end; c++) {
428 switch (*c) {
429 case '\t': st->print("\\t"); break;
430 case '\r': st->print("\\r"); break;
431 case '\n': st->print("\\n"); break;
432 case '\\': st->print("\\\\"); break;
433 default:
434 if (isprint(*c)) {
435 st->print("%c", *c);
436 } else {
437 st->print("\\x%02x", ((unsigned int)*c) & 0xff);
438 }
439 }
440 }
441 }