Mercurial > hg > graal-compiler
comparison src/share/vm/classfile/symbolTable.cpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 98cb887364d3 |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:a61af66fc99e |
---|---|
1 /* | |
2 * Copyright 1997-2006 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
21 * have any questions. | |
22 * | |
23 */ | |
24 | |
25 # include "incls/_precompiled.incl" | |
26 # include "incls/_symbolTable.cpp.incl" | |
27 | |
28 // -------------------------------------------------------------------------- | |
29 | |
30 SymbolTable* SymbolTable::_the_table = NULL; | |
31 | |
32 // Lookup a symbol in a bucket. | |
33 | |
34 symbolOop SymbolTable::lookup(int index, const char* name, | |
35 int len, unsigned int hash) { | |
36 for (HashtableEntry* e = bucket(index); e != NULL; e = e->next()) { | |
37 if (e->hash() == hash) { | |
38 symbolOop sym = symbolOop(e->literal()); | |
39 if (sym->equals(name, len)) { | |
40 return sym; | |
41 } | |
42 } | |
43 } | |
44 return NULL; | |
45 } | |
46 | |
47 | |
48 // We take care not to be blocking while holding the | |
49 // SymbolTable_lock. Otherwise, the system might deadlock, since the | |
50 // symboltable is used during compilation (VM_thread) The lock free | |
51 // synchronization is simplified by the fact that we do not delete | |
52 // entries in the symbol table during normal execution (only during | |
53 // safepoints). | |
54 | |
55 symbolOop SymbolTable::lookup(const char* name, int len, TRAPS) { | |
56 unsigned int hashValue = hash_symbol(name, len); | |
57 int index = the_table()->hash_to_index(hashValue); | |
58 | |
59 symbolOop s = the_table()->lookup(index, name, len, hashValue); | |
60 | |
61 // Found | |
62 if (s != NULL) return s; | |
63 | |
64 // Otherwise, add to symbol to table | |
65 return the_table()->basic_add(index, (u1*)name, len, hashValue, CHECK_NULL); | |
66 } | |
67 | |
68 symbolOop SymbolTable::lookup(symbolHandle sym, int begin, int end, TRAPS) { | |
69 char* buffer; | |
70 int index, len; | |
71 unsigned int hashValue; | |
72 char* name; | |
73 { | |
74 debug_only(No_Safepoint_Verifier nsv;) | |
75 | |
76 name = (char*)sym->base() + begin; | |
77 len = end - begin; | |
78 hashValue = hash_symbol(name, len); | |
79 index = the_table()->hash_to_index(hashValue); | |
80 symbolOop s = the_table()->lookup(index, name, len, hashValue); | |
81 | |
82 // Found | |
83 if (s != NULL) return s; | |
84 } | |
85 | |
86 // Otherwise, add to symbol to table. Copy to a C string first. | |
87 char stack_buf[128]; | |
88 ResourceMark rm(THREAD); | |
89 if (len <= 128) { | |
90 buffer = stack_buf; | |
91 } else { | |
92 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len); | |
93 } | |
94 for (int i=0; i<len; i++) { | |
95 buffer[i] = name[i]; | |
96 } | |
97 // Make sure there is no safepoint in the code above since name can't move. | |
98 // We can't include the code in No_Safepoint_Verifier because of the | |
99 // ResourceMark. | |
100 | |
101 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, CHECK_NULL); | |
102 } | |
103 | |
104 symbolOop SymbolTable::lookup_only(const char* name, int len, | |
105 unsigned int& hash) { | |
106 hash = hash_symbol(name, len); | |
107 int index = the_table()->hash_to_index(hash); | |
108 | |
109 return the_table()->lookup(index, name, len, hash); | |
110 } | |
111 | |
112 void SymbolTable::add(constantPoolHandle cp, int names_count, | |
113 const char** names, int* lengths, int* cp_indices, | |
114 unsigned int* hashValues, TRAPS) { | |
115 SymbolTable* table = the_table(); | |
116 bool added = table->basic_add(cp, names_count, names, lengths, | |
117 cp_indices, hashValues, CHECK); | |
118 if (!added) { | |
119 // do it the hard way | |
120 for (int i=0; i<names_count; i++) { | |
121 int index = table->hash_to_index(hashValues[i]); | |
122 symbolOop sym = table->basic_add(index, (u1*)names[i], lengths[i], | |
123 hashValues[i], CHECK); | |
124 cp->symbol_at_put(cp_indices[i], sym); | |
125 } | |
126 } | |
127 } | |
128 | |
129 // Needed for preloading classes in signatures when compiling. | |
130 | |
131 symbolOop SymbolTable::probe(const char* name, int len) { | |
132 unsigned int hashValue = hash_symbol(name, len); | |
133 int index = the_table()->hash_to_index(hashValue); | |
134 return the_table()->lookup(index, name, len, hashValue); | |
135 } | |
136 | |
137 | |
138 symbolOop SymbolTable::basic_add(int index, u1 *name, int len, | |
139 unsigned int hashValue, TRAPS) { | |
140 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), | |
141 "proposed name of symbol must be stable"); | |
142 | |
143 // We assume that lookup() has been called already, that it failed, | |
144 // and symbol was not found. We create the symbol here. | |
145 symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part(); | |
146 symbolOop s_oop = sk->allocate_symbol(name, len, CHECK_NULL); | |
147 symbolHandle sym (THREAD, s_oop); | |
148 | |
149 // Allocation must be done before grapping the SymbolTable_lock lock | |
150 MutexLocker ml(SymbolTable_lock, THREAD); | |
151 | |
152 assert(sym->equals((char*)name, len), "symbol must be properly initialized"); | |
153 | |
154 // Since look-up was done lock-free, we need to check if another | |
155 // thread beat us in the race to insert the symbol. | |
156 | |
157 symbolOop test = lookup(index, (char*)name, len, hashValue); | |
158 if (test != NULL) { | |
159 // A race occured and another thread introduced the symbol, this one | |
160 // will be dropped and collected. | |
161 return test; | |
162 } | |
163 | |
164 HashtableEntry* entry = new_entry(hashValue, sym()); | |
165 add_entry(index, entry); | |
166 return sym(); | |
167 } | |
168 | |
169 bool SymbolTable::basic_add(constantPoolHandle cp, int names_count, | |
170 const char** names, int* lengths, | |
171 int* cp_indices, unsigned int* hashValues, | |
172 TRAPS) { | |
173 symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part(); | |
174 symbolOop sym_oops[symbol_alloc_batch_size]; | |
175 bool allocated = sk->allocate_symbols(names_count, names, lengths, | |
176 sym_oops, CHECK_false); | |
177 if (!allocated) { | |
178 return false; | |
179 } | |
180 symbolHandle syms[symbol_alloc_batch_size]; | |
181 int i; | |
182 for (i=0; i<names_count; i++) { | |
183 syms[i] = symbolHandle(THREAD, sym_oops[i]); | |
184 } | |
185 | |
186 // Allocation must be done before grabbing the SymbolTable_lock lock | |
187 MutexLocker ml(SymbolTable_lock, THREAD); | |
188 | |
189 for (i=0; i<names_count; i++) { | |
190 assert(syms[i]->equals(names[i], lengths[i]), "symbol must be properly initialized"); | |
191 // Since look-up was done lock-free, we need to check if another | |
192 // thread beat us in the race to insert the symbol. | |
193 int index = hash_to_index(hashValues[i]); | |
194 symbolOop test = lookup(index, names[i], lengths[i], hashValues[i]); | |
195 if (test != NULL) { | |
196 // A race occured and another thread introduced the symbol, this one | |
197 // will be dropped and collected. Use test instead. | |
198 cp->symbol_at_put(cp_indices[i], test); | |
199 } else { | |
200 symbolOop sym = syms[i](); | |
201 HashtableEntry* entry = new_entry(hashValues[i], sym); | |
202 add_entry(index, entry); | |
203 cp->symbol_at_put(cp_indices[i], sym); | |
204 } | |
205 } | |
206 | |
207 return true; | |
208 } | |
209 | |
210 | |
211 void SymbolTable::verify() { | |
212 for (int i = 0; i < the_table()->table_size(); ++i) { | |
213 HashtableEntry* p = the_table()->bucket(i); | |
214 for ( ; p != NULL; p = p->next()) { | |
215 symbolOop s = symbolOop(p->literal()); | |
216 guarantee(s != NULL, "symbol is NULL"); | |
217 s->verify(); | |
218 guarantee(s->is_perm(), "symbol not in permspace"); | |
219 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length()); | |
220 guarantee(p->hash() == h, "broken hash in symbol table entry"); | |
221 guarantee(the_table()->hash_to_index(h) == i, | |
222 "wrong index in symbol table"); | |
223 } | |
224 } | |
225 } | |
226 | |
227 | |
228 //--------------------------------------------------------------------------- | |
229 // Non-product code | |
230 | |
231 #ifndef PRODUCT | |
232 | |
233 void SymbolTable::print_histogram() { | |
234 MutexLocker ml(SymbolTable_lock); | |
235 const int results_length = 100; | |
236 int results[results_length]; | |
237 int i,j; | |
238 | |
239 // initialize results to zero | |
240 for (j = 0; j < results_length; j++) { | |
241 results[j] = 0; | |
242 } | |
243 | |
244 int total = 0; | |
245 int max_symbols = 0; | |
246 int out_of_range = 0; | |
247 for (i = 0; i < the_table()->table_size(); i++) { | |
248 HashtableEntry* p = the_table()->bucket(i); | |
249 for ( ; p != NULL; p = p->next()) { | |
250 int counter = symbolOop(p->literal())->utf8_length(); | |
251 total += counter; | |
252 if (counter < results_length) { | |
253 results[counter]++; | |
254 } else { | |
255 out_of_range++; | |
256 } | |
257 max_symbols = MAX2(max_symbols, counter); | |
258 } | |
259 } | |
260 tty->print_cr("Symbol Table:"); | |
261 tty->print_cr("%8s %5d", "Total ", total); | |
262 tty->print_cr("%8s %5d", "Maximum", max_symbols); | |
263 tty->print_cr("%8s %3.2f", "Average", | |
264 ((float) total / (float) the_table()->table_size())); | |
265 tty->print_cr("%s", "Histogram:"); | |
266 tty->print_cr(" %s %29s", "Length", "Number chains that length"); | |
267 for (i = 0; i < results_length; i++) { | |
268 if (results[i] > 0) { | |
269 tty->print_cr("%6d %10d", i, results[i]); | |
270 } | |
271 } | |
272 int line_length = 70; | |
273 tty->print_cr("%s %30s", " Length", "Number chains that length"); | |
274 for (i = 0; i < results_length; i++) { | |
275 if (results[i] > 0) { | |
276 tty->print("%4d", i); | |
277 for (j = 0; (j < results[i]) && (j < line_length); j++) { | |
278 tty->print("%1s", "*"); | |
279 } | |
280 if (j == line_length) { | |
281 tty->print("%1s", "+"); | |
282 } | |
283 tty->cr(); | |
284 } | |
285 } | |
286 tty->print_cr(" %s %d: %d\n", "Number chains longer than", | |
287 results_length, out_of_range); | |
288 } | |
289 | |
290 #endif // PRODUCT | |
291 | |
292 // -------------------------------------------------------------------------- | |
293 | |
294 #ifdef ASSERT | |
295 class StableMemoryChecker : public StackObj { | |
296 enum { _bufsize = wordSize*4 }; | |
297 | |
298 address _region; | |
299 jint _size; | |
300 u1 _save_buf[_bufsize]; | |
301 | |
302 int sample(u1* save_buf) { | |
303 if (_size <= _bufsize) { | |
304 memcpy(save_buf, _region, _size); | |
305 return _size; | |
306 } else { | |
307 // copy head and tail | |
308 memcpy(&save_buf[0], _region, _bufsize/2); | |
309 memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2); | |
310 return (_bufsize/2)*2; | |
311 } | |
312 } | |
313 | |
314 public: | |
315 StableMemoryChecker(const void* region, jint size) { | |
316 _region = (address) region; | |
317 _size = size; | |
318 sample(_save_buf); | |
319 } | |
320 | |
321 bool verify() { | |
322 u1 check_buf[sizeof(_save_buf)]; | |
323 int check_size = sample(check_buf); | |
324 return (0 == memcmp(_save_buf, check_buf, check_size)); | |
325 } | |
326 | |
327 void set_region(const void* region) { _region = (address) region; } | |
328 }; | |
329 #endif | |
330 | |
331 | |
332 // -------------------------------------------------------------------------- | |
333 | |
334 | |
335 // Compute the hash value for a java.lang.String object which would | |
336 // contain the characters passed in. This hash value is used for at | |
337 // least two purposes. | |
338 // | |
339 // (a) As the hash value used by the StringTable for bucket selection | |
340 // and comparison (stored in the HashtableEntry structures). This | |
341 // is used in the String.intern() method. | |
342 // | |
343 // (b) As the hash value used by the String object itself, in | |
344 // String.hashCode(). This value is normally calculate in Java code | |
345 // in the String.hashCode method(), but is precomputed for String | |
346 // objects in the shared archive file. | |
347 // | |
348 // For this reason, THIS ALGORITHM MUST MATCH String.hashCode(). | |
349 | |
350 int StringTable::hash_string(jchar* s, int len) { | |
351 unsigned h = 0; | |
352 while (len-- > 0) { | |
353 h = 31*h + (unsigned) *s; | |
354 s++; | |
355 } | |
356 return h; | |
357 } | |
358 | |
359 | |
360 StringTable* StringTable::_the_table = NULL; | |
361 | |
362 oop StringTable::lookup(int index, jchar* name, | |
363 int len, unsigned int hash) { | |
364 for (HashtableEntry* l = bucket(index); l != NULL; l = l->next()) { | |
365 if (l->hash() == hash) { | |
366 if (java_lang_String::equals(l->literal(), name, len)) { | |
367 return l->literal(); | |
368 } | |
369 } | |
370 } | |
371 return NULL; | |
372 } | |
373 | |
374 | |
375 oop StringTable::basic_add(int index, Handle string_or_null, jchar* name, | |
376 int len, unsigned int hashValue, TRAPS) { | |
377 debug_only(StableMemoryChecker smc(name, len * sizeof(name[0]))); | |
378 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), | |
379 "proposed name of symbol must be stable"); | |
380 | |
381 Handle string; | |
382 // try to reuse the string if possible | |
383 if (!string_or_null.is_null() && string_or_null()->is_perm()) { | |
384 string = string_or_null; | |
385 } else { | |
386 string = java_lang_String::create_tenured_from_unicode(name, len, CHECK_NULL); | |
387 } | |
388 | |
389 // Allocation must be done before grapping the SymbolTable_lock lock | |
390 MutexLocker ml(StringTable_lock, THREAD); | |
391 | |
392 assert(java_lang_String::equals(string(), name, len), | |
393 "string must be properly initialized"); | |
394 | |
395 // Since look-up was done lock-free, we need to check if another | |
396 // thread beat us in the race to insert the symbol. | |
397 | |
398 oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int) | |
399 if (test != NULL) { | |
400 // Entry already added | |
401 return test; | |
402 } | |
403 | |
404 HashtableEntry* entry = new_entry(hashValue, string()); | |
405 add_entry(index, entry); | |
406 return string(); | |
407 } | |
408 | |
409 | |
410 oop StringTable::lookup(symbolOop symbol) { | |
411 ResourceMark rm; | |
412 int length; | |
413 jchar* chars = symbol->as_unicode(length); | |
414 unsigned int hashValue = hash_string(chars, length); | |
415 int index = the_table()->hash_to_index(hashValue); | |
416 return the_table()->lookup(index, chars, length, hashValue); | |
417 } | |
418 | |
419 | |
420 oop StringTable::intern(Handle string_or_null, jchar* name, | |
421 int len, TRAPS) { | |
422 unsigned int hashValue = hash_string(name, len); | |
423 int index = the_table()->hash_to_index(hashValue); | |
424 oop string = the_table()->lookup(index, name, len, hashValue); | |
425 | |
426 // Found | |
427 if (string != NULL) return string; | |
428 | |
429 // Otherwise, add to symbol to table | |
430 return the_table()->basic_add(index, string_or_null, name, len, | |
431 hashValue, CHECK_NULL); | |
432 } | |
433 | |
434 oop StringTable::intern(symbolOop symbol, TRAPS) { | |
435 if (symbol == NULL) return NULL; | |
436 ResourceMark rm(THREAD); | |
437 int length; | |
438 jchar* chars = symbol->as_unicode(length); | |
439 Handle string; | |
440 oop result = intern(string, chars, length, CHECK_NULL); | |
441 return result; | |
442 } | |
443 | |
444 | |
445 oop StringTable::intern(oop string, TRAPS) | |
446 { | |
447 if (string == NULL) return NULL; | |
448 ResourceMark rm(THREAD); | |
449 int length; | |
450 Handle h_string (THREAD, string); | |
451 jchar* chars = java_lang_String::as_unicode_string(string, length); | |
452 oop result = intern(h_string, chars, length, CHECK_NULL); | |
453 return result; | |
454 } | |
455 | |
456 | |
457 oop StringTable::intern(const char* utf8_string, TRAPS) { | |
458 if (utf8_string == NULL) return NULL; | |
459 ResourceMark rm(THREAD); | |
460 int length = UTF8::unicode_length(utf8_string); | |
461 jchar* chars = NEW_RESOURCE_ARRAY(jchar, length); | |
462 UTF8::convert_to_unicode(utf8_string, chars, length); | |
463 Handle string; | |
464 oop result = intern(string, chars, length, CHECK_NULL); | |
465 return result; | |
466 } | |
467 | |
468 void StringTable::verify() { | |
469 for (int i = 0; i < the_table()->table_size(); ++i) { | |
470 HashtableEntry* p = the_table()->bucket(i); | |
471 for ( ; p != NULL; p = p->next()) { | |
472 oop s = p->literal(); | |
473 guarantee(s != NULL, "interned string is NULL"); | |
474 guarantee(s->is_perm(), "interned string not in permspace"); | |
475 | |
476 int length; | |
477 jchar* chars = java_lang_String::as_unicode_string(s, length); | |
478 unsigned int h = hash_string(chars, length); | |
479 guarantee(p->hash() == h, "broken hash in string table entry"); | |
480 guarantee(the_table()->hash_to_index(h) == i, | |
481 "wrong index in string table"); | |
482 } | |
483 } | |
484 } |