1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000 1.2 +++ b/src/share/vm/classfile/symbolTable.cpp Sat Dec 01 00:00:00 2007 +0000 1.3 @@ -0,0 +1,484 @@ 1.4 +/* 1.5 + * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved. 1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1.7 + * 1.8 + * This code is free software; you can redistribute it and/or modify it 1.9 + * under the terms of the GNU General Public License version 2 only, as 1.10 + * published by the Free Software Foundation. 1.11 + * 1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT 1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1.15 + * version 2 for more details (a copy is included in the LICENSE file that 1.16 + * accompanied this code). 1.17 + * 1.18 + * You should have received a copy of the GNU General Public License version 1.19 + * 2 along with this work; if not, write to the Free Software Foundation, 1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1.21 + * 1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, 1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or 1.24 + * have any questions. 1.25 + * 1.26 + */ 1.27 + 1.28 +# include "incls/_precompiled.incl" 1.29 +# include "incls/_symbolTable.cpp.incl" 1.30 + 1.31 +// -------------------------------------------------------------------------- 1.32 + 1.33 +SymbolTable* SymbolTable::_the_table = NULL; 1.34 + 1.35 +// Lookup a symbol in a bucket. 1.36 + 1.37 +symbolOop SymbolTable::lookup(int index, const char* name, 1.38 + int len, unsigned int hash) { 1.39 + for (HashtableEntry* e = bucket(index); e != NULL; e = e->next()) { 1.40 + if (e->hash() == hash) { 1.41 + symbolOop sym = symbolOop(e->literal()); 1.42 + if (sym->equals(name, len)) { 1.43 + return sym; 1.44 + } 1.45 + } 1.46 + } 1.47 + return NULL; 1.48 +} 1.49 + 1.50 + 1.51 +// We take care not to be blocking while holding the 1.52 +// SymbolTable_lock. Otherwise, the system might deadlock, since the 1.53 +// symboltable is used during compilation (VM_thread) The lock free 1.54 +// synchronization is simplified by the fact that we do not delete 1.55 +// entries in the symbol table during normal execution (only during 1.56 +// safepoints). 1.57 + 1.58 +symbolOop SymbolTable::lookup(const char* name, int len, TRAPS) { 1.59 + unsigned int hashValue = hash_symbol(name, len); 1.60 + int index = the_table()->hash_to_index(hashValue); 1.61 + 1.62 + symbolOop s = the_table()->lookup(index, name, len, hashValue); 1.63 + 1.64 + // Found 1.65 + if (s != NULL) return s; 1.66 + 1.67 + // Otherwise, add to symbol to table 1.68 + return the_table()->basic_add(index, (u1*)name, len, hashValue, CHECK_NULL); 1.69 +} 1.70 + 1.71 +symbolOop SymbolTable::lookup(symbolHandle sym, int begin, int end, TRAPS) { 1.72 + char* buffer; 1.73 + int index, len; 1.74 + unsigned int hashValue; 1.75 + char* name; 1.76 + { 1.77 + debug_only(No_Safepoint_Verifier nsv;) 1.78 + 1.79 + name = (char*)sym->base() + begin; 1.80 + len = end - begin; 1.81 + hashValue = hash_symbol(name, len); 1.82 + index = the_table()->hash_to_index(hashValue); 1.83 + symbolOop s = the_table()->lookup(index, name, len, hashValue); 1.84 + 1.85 + // Found 1.86 + if (s != NULL) return s; 1.87 + } 1.88 + 1.89 + // Otherwise, add to symbol to table. Copy to a C string first. 1.90 + char stack_buf[128]; 1.91 + ResourceMark rm(THREAD); 1.92 + if (len <= 128) { 1.93 + buffer = stack_buf; 1.94 + } else { 1.95 + buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len); 1.96 + } 1.97 + for (int i=0; i<len; i++) { 1.98 + buffer[i] = name[i]; 1.99 + } 1.100 + // Make sure there is no safepoint in the code above since name can't move. 1.101 + // We can't include the code in No_Safepoint_Verifier because of the 1.102 + // ResourceMark. 1.103 + 1.104 + return the_table()->basic_add(index, (u1*)buffer, len, hashValue, CHECK_NULL); 1.105 +} 1.106 + 1.107 +symbolOop SymbolTable::lookup_only(const char* name, int len, 1.108 + unsigned int& hash) { 1.109 + hash = hash_symbol(name, len); 1.110 + int index = the_table()->hash_to_index(hash); 1.111 + 1.112 + return the_table()->lookup(index, name, len, hash); 1.113 +} 1.114 + 1.115 +void SymbolTable::add(constantPoolHandle cp, int names_count, 1.116 + const char** names, int* lengths, int* cp_indices, 1.117 + unsigned int* hashValues, TRAPS) { 1.118 + SymbolTable* table = the_table(); 1.119 + bool added = table->basic_add(cp, names_count, names, lengths, 1.120 + cp_indices, hashValues, CHECK); 1.121 + if (!added) { 1.122 + // do it the hard way 1.123 + for (int i=0; i<names_count; i++) { 1.124 + int index = table->hash_to_index(hashValues[i]); 1.125 + symbolOop sym = table->basic_add(index, (u1*)names[i], lengths[i], 1.126 + hashValues[i], CHECK); 1.127 + cp->symbol_at_put(cp_indices[i], sym); 1.128 + } 1.129 + } 1.130 +} 1.131 + 1.132 +// Needed for preloading classes in signatures when compiling. 1.133 + 1.134 +symbolOop SymbolTable::probe(const char* name, int len) { 1.135 + unsigned int hashValue = hash_symbol(name, len); 1.136 + int index = the_table()->hash_to_index(hashValue); 1.137 + return the_table()->lookup(index, name, len, hashValue); 1.138 +} 1.139 + 1.140 + 1.141 +symbolOop SymbolTable::basic_add(int index, u1 *name, int len, 1.142 + unsigned int hashValue, TRAPS) { 1.143 + assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), 1.144 + "proposed name of symbol must be stable"); 1.145 + 1.146 + // We assume that lookup() has been called already, that it failed, 1.147 + // and symbol was not found. We create the symbol here. 1.148 + symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part(); 1.149 + symbolOop s_oop = sk->allocate_symbol(name, len, CHECK_NULL); 1.150 + symbolHandle sym (THREAD, s_oop); 1.151 + 1.152 + // Allocation must be done before grapping the SymbolTable_lock lock 1.153 + MutexLocker ml(SymbolTable_lock, THREAD); 1.154 + 1.155 + assert(sym->equals((char*)name, len), "symbol must be properly initialized"); 1.156 + 1.157 + // Since look-up was done lock-free, we need to check if another 1.158 + // thread beat us in the race to insert the symbol. 1.159 + 1.160 + symbolOop test = lookup(index, (char*)name, len, hashValue); 1.161 + if (test != NULL) { 1.162 + // A race occured and another thread introduced the symbol, this one 1.163 + // will be dropped and collected. 1.164 + return test; 1.165 + } 1.166 + 1.167 + HashtableEntry* entry = new_entry(hashValue, sym()); 1.168 + add_entry(index, entry); 1.169 + return sym(); 1.170 +} 1.171 + 1.172 +bool SymbolTable::basic_add(constantPoolHandle cp, int names_count, 1.173 + const char** names, int* lengths, 1.174 + int* cp_indices, unsigned int* hashValues, 1.175 + TRAPS) { 1.176 + symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part(); 1.177 + symbolOop sym_oops[symbol_alloc_batch_size]; 1.178 + bool allocated = sk->allocate_symbols(names_count, names, lengths, 1.179 + sym_oops, CHECK_false); 1.180 + if (!allocated) { 1.181 + return false; 1.182 + } 1.183 + symbolHandle syms[symbol_alloc_batch_size]; 1.184 + int i; 1.185 + for (i=0; i<names_count; i++) { 1.186 + syms[i] = symbolHandle(THREAD, sym_oops[i]); 1.187 + } 1.188 + 1.189 + // Allocation must be done before grabbing the SymbolTable_lock lock 1.190 + MutexLocker ml(SymbolTable_lock, THREAD); 1.191 + 1.192 + for (i=0; i<names_count; i++) { 1.193 + assert(syms[i]->equals(names[i], lengths[i]), "symbol must be properly initialized"); 1.194 + // Since look-up was done lock-free, we need to check if another 1.195 + // thread beat us in the race to insert the symbol. 1.196 + int index = hash_to_index(hashValues[i]); 1.197 + symbolOop test = lookup(index, names[i], lengths[i], hashValues[i]); 1.198 + if (test != NULL) { 1.199 + // A race occured and another thread introduced the symbol, this one 1.200 + // will be dropped and collected. Use test instead. 1.201 + cp->symbol_at_put(cp_indices[i], test); 1.202 + } else { 1.203 + symbolOop sym = syms[i](); 1.204 + HashtableEntry* entry = new_entry(hashValues[i], sym); 1.205 + add_entry(index, entry); 1.206 + cp->symbol_at_put(cp_indices[i], sym); 1.207 + } 1.208 + } 1.209 + 1.210 + return true; 1.211 +} 1.212 + 1.213 + 1.214 +void SymbolTable::verify() { 1.215 + for (int i = 0; i < the_table()->table_size(); ++i) { 1.216 + HashtableEntry* p = the_table()->bucket(i); 1.217 + for ( ; p != NULL; p = p->next()) { 1.218 + symbolOop s = symbolOop(p->literal()); 1.219 + guarantee(s != NULL, "symbol is NULL"); 1.220 + s->verify(); 1.221 + guarantee(s->is_perm(), "symbol not in permspace"); 1.222 + unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length()); 1.223 + guarantee(p->hash() == h, "broken hash in symbol table entry"); 1.224 + guarantee(the_table()->hash_to_index(h) == i, 1.225 + "wrong index in symbol table"); 1.226 + } 1.227 + } 1.228 +} 1.229 + 1.230 + 1.231 +//--------------------------------------------------------------------------- 1.232 +// Non-product code 1.233 + 1.234 +#ifndef PRODUCT 1.235 + 1.236 +void SymbolTable::print_histogram() { 1.237 + MutexLocker ml(SymbolTable_lock); 1.238 + const int results_length = 100; 1.239 + int results[results_length]; 1.240 + int i,j; 1.241 + 1.242 + // initialize results to zero 1.243 + for (j = 0; j < results_length; j++) { 1.244 + results[j] = 0; 1.245 + } 1.246 + 1.247 + int total = 0; 1.248 + int max_symbols = 0; 1.249 + int out_of_range = 0; 1.250 + for (i = 0; i < the_table()->table_size(); i++) { 1.251 + HashtableEntry* p = the_table()->bucket(i); 1.252 + for ( ; p != NULL; p = p->next()) { 1.253 + int counter = symbolOop(p->literal())->utf8_length(); 1.254 + total += counter; 1.255 + if (counter < results_length) { 1.256 + results[counter]++; 1.257 + } else { 1.258 + out_of_range++; 1.259 + } 1.260 + max_symbols = MAX2(max_symbols, counter); 1.261 + } 1.262 + } 1.263 + tty->print_cr("Symbol Table:"); 1.264 + tty->print_cr("%8s %5d", "Total ", total); 1.265 + tty->print_cr("%8s %5d", "Maximum", max_symbols); 1.266 + tty->print_cr("%8s %3.2f", "Average", 1.267 + ((float) total / (float) the_table()->table_size())); 1.268 + tty->print_cr("%s", "Histogram:"); 1.269 + tty->print_cr(" %s %29s", "Length", "Number chains that length"); 1.270 + for (i = 0; i < results_length; i++) { 1.271 + if (results[i] > 0) { 1.272 + tty->print_cr("%6d %10d", i, results[i]); 1.273 + } 1.274 + } 1.275 + int line_length = 70; 1.276 + tty->print_cr("%s %30s", " Length", "Number chains that length"); 1.277 + for (i = 0; i < results_length; i++) { 1.278 + if (results[i] > 0) { 1.279 + tty->print("%4d", i); 1.280 + for (j = 0; (j < results[i]) && (j < line_length); j++) { 1.281 + tty->print("%1s", "*"); 1.282 + } 1.283 + if (j == line_length) { 1.284 + tty->print("%1s", "+"); 1.285 + } 1.286 + tty->cr(); 1.287 + } 1.288 + } 1.289 + tty->print_cr(" %s %d: %d\n", "Number chains longer than", 1.290 + results_length, out_of_range); 1.291 +} 1.292 + 1.293 +#endif // PRODUCT 1.294 + 1.295 +// -------------------------------------------------------------------------- 1.296 + 1.297 +#ifdef ASSERT 1.298 +class StableMemoryChecker : public StackObj { 1.299 + enum { _bufsize = wordSize*4 }; 1.300 + 1.301 + address _region; 1.302 + jint _size; 1.303 + u1 _save_buf[_bufsize]; 1.304 + 1.305 + int sample(u1* save_buf) { 1.306 + if (_size <= _bufsize) { 1.307 + memcpy(save_buf, _region, _size); 1.308 + return _size; 1.309 + } else { 1.310 + // copy head and tail 1.311 + memcpy(&save_buf[0], _region, _bufsize/2); 1.312 + memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2); 1.313 + return (_bufsize/2)*2; 1.314 + } 1.315 + } 1.316 + 1.317 + public: 1.318 + StableMemoryChecker(const void* region, jint size) { 1.319 + _region = (address) region; 1.320 + _size = size; 1.321 + sample(_save_buf); 1.322 + } 1.323 + 1.324 + bool verify() { 1.325 + u1 check_buf[sizeof(_save_buf)]; 1.326 + int check_size = sample(check_buf); 1.327 + return (0 == memcmp(_save_buf, check_buf, check_size)); 1.328 + } 1.329 + 1.330 + void set_region(const void* region) { _region = (address) region; } 1.331 +}; 1.332 +#endif 1.333 + 1.334 + 1.335 +// -------------------------------------------------------------------------- 1.336 + 1.337 + 1.338 +// Compute the hash value for a java.lang.String object which would 1.339 +// contain the characters passed in. This hash value is used for at 1.340 +// least two purposes. 1.341 +// 1.342 +// (a) As the hash value used by the StringTable for bucket selection 1.343 +// and comparison (stored in the HashtableEntry structures). This 1.344 +// is used in the String.intern() method. 1.345 +// 1.346 +// (b) As the hash value used by the String object itself, in 1.347 +// String.hashCode(). This value is normally calculate in Java code 1.348 +// in the String.hashCode method(), but is precomputed for String 1.349 +// objects in the shared archive file. 1.350 +// 1.351 +// For this reason, THIS ALGORITHM MUST MATCH String.hashCode(). 1.352 + 1.353 +int StringTable::hash_string(jchar* s, int len) { 1.354 + unsigned h = 0; 1.355 + while (len-- > 0) { 1.356 + h = 31*h + (unsigned) *s; 1.357 + s++; 1.358 + } 1.359 + return h; 1.360 +} 1.361 + 1.362 + 1.363 +StringTable* StringTable::_the_table = NULL; 1.364 + 1.365 +oop StringTable::lookup(int index, jchar* name, 1.366 + int len, unsigned int hash) { 1.367 + for (HashtableEntry* l = bucket(index); l != NULL; l = l->next()) { 1.368 + if (l->hash() == hash) { 1.369 + if (java_lang_String::equals(l->literal(), name, len)) { 1.370 + return l->literal(); 1.371 + } 1.372 + } 1.373 + } 1.374 + return NULL; 1.375 +} 1.376 + 1.377 + 1.378 +oop StringTable::basic_add(int index, Handle string_or_null, jchar* name, 1.379 + int len, unsigned int hashValue, TRAPS) { 1.380 + debug_only(StableMemoryChecker smc(name, len * sizeof(name[0]))); 1.381 + assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(), 1.382 + "proposed name of symbol must be stable"); 1.383 + 1.384 + Handle string; 1.385 + // try to reuse the string if possible 1.386 + if (!string_or_null.is_null() && string_or_null()->is_perm()) { 1.387 + string = string_or_null; 1.388 + } else { 1.389 + string = java_lang_String::create_tenured_from_unicode(name, len, CHECK_NULL); 1.390 + } 1.391 + 1.392 + // Allocation must be done before grapping the SymbolTable_lock lock 1.393 + MutexLocker ml(StringTable_lock, THREAD); 1.394 + 1.395 + assert(java_lang_String::equals(string(), name, len), 1.396 + "string must be properly initialized"); 1.397 + 1.398 + // Since look-up was done lock-free, we need to check if another 1.399 + // thread beat us in the race to insert the symbol. 1.400 + 1.401 + oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int) 1.402 + if (test != NULL) { 1.403 + // Entry already added 1.404 + return test; 1.405 + } 1.406 + 1.407 + HashtableEntry* entry = new_entry(hashValue, string()); 1.408 + add_entry(index, entry); 1.409 + return string(); 1.410 +} 1.411 + 1.412 + 1.413 +oop StringTable::lookup(symbolOop symbol) { 1.414 + ResourceMark rm; 1.415 + int length; 1.416 + jchar* chars = symbol->as_unicode(length); 1.417 + unsigned int hashValue = hash_string(chars, length); 1.418 + int index = the_table()->hash_to_index(hashValue); 1.419 + return the_table()->lookup(index, chars, length, hashValue); 1.420 +} 1.421 + 1.422 + 1.423 +oop StringTable::intern(Handle string_or_null, jchar* name, 1.424 + int len, TRAPS) { 1.425 + unsigned int hashValue = hash_string(name, len); 1.426 + int index = the_table()->hash_to_index(hashValue); 1.427 + oop string = the_table()->lookup(index, name, len, hashValue); 1.428 + 1.429 + // Found 1.430 + if (string != NULL) return string; 1.431 + 1.432 + // Otherwise, add to symbol to table 1.433 + return the_table()->basic_add(index, string_or_null, name, len, 1.434 + hashValue, CHECK_NULL); 1.435 +} 1.436 + 1.437 +oop StringTable::intern(symbolOop symbol, TRAPS) { 1.438 + if (symbol == NULL) return NULL; 1.439 + ResourceMark rm(THREAD); 1.440 + int length; 1.441 + jchar* chars = symbol->as_unicode(length); 1.442 + Handle string; 1.443 + oop result = intern(string, chars, length, CHECK_NULL); 1.444 + return result; 1.445 +} 1.446 + 1.447 + 1.448 +oop StringTable::intern(oop string, TRAPS) 1.449 +{ 1.450 + if (string == NULL) return NULL; 1.451 + ResourceMark rm(THREAD); 1.452 + int length; 1.453 + Handle h_string (THREAD, string); 1.454 + jchar* chars = java_lang_String::as_unicode_string(string, length); 1.455 + oop result = intern(h_string, chars, length, CHECK_NULL); 1.456 + return result; 1.457 +} 1.458 + 1.459 + 1.460 +oop StringTable::intern(const char* utf8_string, TRAPS) { 1.461 + if (utf8_string == NULL) return NULL; 1.462 + ResourceMark rm(THREAD); 1.463 + int length = UTF8::unicode_length(utf8_string); 1.464 + jchar* chars = NEW_RESOURCE_ARRAY(jchar, length); 1.465 + UTF8::convert_to_unicode(utf8_string, chars, length); 1.466 + Handle string; 1.467 + oop result = intern(string, chars, length, CHECK_NULL); 1.468 + return result; 1.469 +} 1.470 + 1.471 +void StringTable::verify() { 1.472 + for (int i = 0; i < the_table()->table_size(); ++i) { 1.473 + HashtableEntry* p = the_table()->bucket(i); 1.474 + for ( ; p != NULL; p = p->next()) { 1.475 + oop s = p->literal(); 1.476 + guarantee(s != NULL, "interned string is NULL"); 1.477 + guarantee(s->is_perm(), "interned string not in permspace"); 1.478 + 1.479 + int length; 1.480 + jchar* chars = java_lang_String::as_unicode_string(s, length); 1.481 + unsigned int h = hash_string(chars, length); 1.482 + guarantee(p->hash() == h, "broken hash in string table entry"); 1.483 + guarantee(the_table()->hash_to_index(h) == i, 1.484 + "wrong index in string table"); 1.485 + } 1.486 + } 1.487 +}