192 int count = 0;
193 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
194 count++; // count all entries in this bucket, not just ones with same hash
195 if (e->hash() == hash) {
196 Symbol* sym = e->literal();
197 if (sym->equals(name, len)) {
198 // something is referencing this symbol now.
199 sym->increment_refcount();
200 return sym;
201 }
202 }
203 }
204 // If the bucket size is too deep check if this hash code is insufficient.
205 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) {
206 _needs_rehashing = check_rehash_table(count);
207 }
208 return NULL;
209 }
210
211 // Pick hashing algorithm.
212 unsigned int SymbolTable::hash_symbol(const char* s, int len) {
213 return use_alternate_hashcode() ?
214 AltHashing::murmur3_32(seed(), (const jbyte*)s, len) :
215 java_lang_String::hash_code(s, len);
216 }
217
218
219 // We take care not to be blocking while holding the
220 // SymbolTable_lock. Otherwise, the system might deadlock, since the
221 // symboltable is used during compilation (VM_thread) The lock free
222 // synchronization is simplified by the fact that we do not delete
223 // entries in the symbol table during normal execution (only during
224 // safepoints).
225
226 Symbol* SymbolTable::lookup(const char* name, int len, TRAPS) {
227 unsigned int hashValue = hash_symbol(name, len);
228 int index = the_table()->hash_to_index(hashValue);
229
230 Symbol* s = the_table()->lookup(index, name, len, hashValue);
231
232 // Found
233 if (s != NULL) return s;
234
235 // Grab SymbolTable_lock first.
236 MutexLocker ml(SymbolTable_lock, THREAD);
237
238 // Otherwise, add to symbol to table
239 return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL);
240 }
241
242 Symbol* SymbolTable::lookup(const Symbol* sym, int begin, int end, TRAPS) {
243 char* buffer;
244 int index, len;
245 unsigned int hashValue;
246 char* name;
247 {
248 debug_only(No_Safepoint_Verifier nsv;)
249
250 name = (char*)sym->base() + begin;
251 len = end - begin;
252 hashValue = hash_symbol(name, len);
253 index = the_table()->hash_to_index(hashValue);
254 Symbol* s = the_table()->lookup(index, name, len, hashValue);
255
256 // Found
257 if (s != NULL) return s;
258 }
259
260 // Otherwise, add to symbol to table. Copy to a C string first.
261 char stack_buf[128];
262 ResourceMark rm(THREAD);
263 if (len <= 128) {
264 buffer = stack_buf;
265 } else {
266 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);
267 }
268 for (int i=0; i<len; i++) {
269 buffer[i] = name[i];
270 }
271 // Make sure there is no safepoint in the code above since name can't move.
272 // We can't include the code in No_Safepoint_Verifier because of the
273 // ResourceMark.
274
275 // Grab SymbolTable_lock first.
276 MutexLocker ml(SymbolTable_lock, THREAD);
277
278 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL);
279 }
280
281 Symbol* SymbolTable::lookup_only(const char* name, int len,
282 unsigned int& hash) {
283 hash = hash_symbol(name, len);
284 int index = the_table()->hash_to_index(hash);
285
286 Symbol* s = the_table()->lookup(index, name, len, hash);
287 return s;
288 }
289
290 // Look up the address of the literal in the SymbolTable for this Symbol*
291 // Do not create any new symbols
292 // Do not increment the reference count to keep this alive
293 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){
294 unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length());
295 int index = the_table()->hash_to_index(hash);
296
297 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) {
298 if (e->hash() == hash) {
299 Symbol* literal_sym = e->literal();
300 if (sym == literal_sym) {
301 return e->literal_addr();
302 }
303 }
304 }
305 return NULL;
306 }
307
308 // Suggestion: Push unicode-based lookup all the way into the hashing
309 // and probing logic, so there is no need for convert_to_utf8 until
310 // an actual new Symbol* is created.
311 Symbol* SymbolTable::lookup_unicode(const jchar* name, int utf16_length, TRAPS) {
312 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
313 char stack_buf[128];
314 if (utf8_length < (int) sizeof(stack_buf)) {
315 char* chars = stack_buf;
316 UNICODE::convert_to_utf8(name, utf16_length, chars);
317 return lookup(chars, utf8_length, THREAD);
318 } else {
319 ResourceMark rm(THREAD);
320 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
321 UNICODE::convert_to_utf8(name, utf16_length, chars);
322 return lookup(chars, utf8_length, THREAD);
323 }
324 }
325
326 Symbol* SymbolTable::lookup_only_unicode(const jchar* name, int utf16_length,
327 unsigned int& hash) {
328 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
329 char stack_buf[128];
330 if (utf8_length < (int) sizeof(stack_buf)) {
331 char* chars = stack_buf;
332 UNICODE::convert_to_utf8(name, utf16_length, chars);
333 return lookup_only(chars, utf8_length, hash);
334 } else {
335 ResourceMark rm;
336 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);;
337 UNICODE::convert_to_utf8(name, utf16_length, chars);
338 return lookup_only(chars, utf8_length, hash);
339 }
340 }
341
342 void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp,
343 int names_count,
344 const char** names, int* lengths, int* cp_indices,
345 unsigned int* hashValues, TRAPS) {
346 // Grab SymbolTable_lock first.
347 MutexLocker ml(SymbolTable_lock, THREAD);
348
349 SymbolTable* table = the_table();
350 bool added = table->basic_add(loader_data, cp, names_count, names, lengths,
351 cp_indices, hashValues, CHECK);
352 if (!added) {
353 // do it the hard way
354 for (int i=0; i<names_count; i++) {
355 int index = table->hash_to_index(hashValues[i]);
356 bool c_heap = !loader_data->is_the_null_class_loader_data();
357 Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK);
358 cp->symbol_at_put(cp_indices[i], sym);
359 }
360 }
361 }
362
363 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
364 unsigned int hash;
365 Symbol* result = SymbolTable::lookup_only((char*)name, (int)strlen(name), hash);
366 if (result != NULL) {
367 return result;
368 }
369 // Grab SymbolTable_lock first.
370 MutexLocker ml(SymbolTable_lock, THREAD);
371
372 SymbolTable* table = the_table();
373 int index = table->hash_to_index(hash);
374 return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);
375 }
376
377 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
378 unsigned int hashValue_arg, bool c_heap, TRAPS) {
379 assert(!Universe::heap()->is_in_reserved(name),
380 "proposed name of symbol must be stable");
381
382 // Don't allow symbols to be created which cannot fit in a Symbol*.
383 if (len > Symbol::max_length()) {
384 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
385 "name is too long to represent");
408 assert(test->refcount() != 0, "lookup should have incremented the count");
409 return test;
410 }
411
412 // Create a new symbol.
413 Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);
414 assert(sym->equals((char*)name, len), "symbol must be properly initialized");
415
416 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
417 add_entry(index, entry);
418 return sym;
419 }
420
421 // This version of basic_add adds symbols in batch from the constant pool
422 // parsing.
423 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp,
424 int names_count,
425 const char** names, int* lengths,
426 int* cp_indices, unsigned int* hashValues,
427 TRAPS) {
428
429 // Check symbol names are not too long. If any are too long, don't add any.
430 for (int i = 0; i< names_count; i++) {
431 if (lengths[i] > Symbol::max_length()) {
432 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
433 "name is too long to represent");
434 }
435 }
436
437 // Cannot hit a safepoint in this function because the "this" pointer can move.
438 No_Safepoint_Verifier nsv;
439
440 for (int i=0; i<names_count; i++) {
441 // Check if the symbol table has been rehashed, if so, need to recalculate
442 // the hash value.
443 unsigned int hashValue;
444 if (use_alternate_hashcode()) {
445 hashValue = hash_symbol(names[i], lengths[i]);
446 } else {
447 hashValue = hashValues[i];
448 }
452 Symbol* test = lookup(index, names[i], lengths[i], hashValue);
453 if (test != NULL) {
454 // A race occurred and another thread introduced the symbol, this one
455 // will be dropped and collected. Use test instead.
456 cp->symbol_at_put(cp_indices[i], test);
457 assert(test->refcount() != 0, "lookup should have incremented the count");
458 } else {
459 // Create a new symbol. The null class loader is never unloaded so these
460 // are allocated specially in a permanent arena.
461 bool c_heap = !loader_data->is_the_null_class_loader_data();
462 Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));
463 assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized"); // why wouldn't it be???
464 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
465 add_entry(index, entry);
466 cp->symbol_at_put(cp_indices[i], sym);
467 }
468 }
469 return true;
470 }
471
472
473 void SymbolTable::verify() {
474 for (int i = 0; i < the_table()->table_size(); ++i) {
475 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
476 for ( ; p != NULL; p = p->next()) {
477 Symbol* s = (Symbol*)(p->literal());
478 guarantee(s != NULL, "symbol is NULL");
479 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
480 guarantee(p->hash() == h, "broken hash in symbol table entry");
481 guarantee(the_table()->hash_to_index(h) == i,
482 "wrong index in symbol table");
483 }
484 }
485 }
486
487 void SymbolTable::dump(outputStream* st) {
488 the_table()->dump_table(st, "SymbolTable");
489 }
490
491
492 //---------------------------------------------------------------------------
493 // Non-product code
494
495 #ifndef PRODUCT
496
497 void SymbolTable::print_histogram() {
498 MutexLocker ml(SymbolTable_lock);
499 const int results_length = 100;
500 int results[results_length];
501 int i,j;
502
503 // initialize results to zero
504 for (j = 0; j < results_length; j++) {
505 results[j] = 0;
506 }
507
508 int total = 0;
509 int max_symbols = 0;
510 int out_of_range = 0;
511 int memory_total = 0;
|
192 int count = 0;
193 for (HashtableEntry<Symbol*, mtSymbol>* e = bucket(index); e != NULL; e = e->next()) {
194 count++; // count all entries in this bucket, not just ones with same hash
195 if (e->hash() == hash) {
196 Symbol* sym = e->literal();
197 if (sym->equals(name, len)) {
198 // something is referencing this symbol now.
199 sym->increment_refcount();
200 return sym;
201 }
202 }
203 }
204 // If the bucket size is too deep check if this hash code is insufficient.
205 if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) {
206 _needs_rehashing = check_rehash_table(count);
207 }
208 return NULL;
209 }
210
211 // Pick hashing algorithm.
212 unsigned int SymbolTable::hash_symbol(const char* name, int len) {
213 return use_alternate_hashcode() ?
214 AltHashing::murmur3_32(seed(), (const jbyte*)name, len) :
215 java_lang_String::hash_code(name, len);
216 }
217
218
219 // We take care not to be blocking while holding the
220 // SymbolTable_lock. Otherwise, the system might deadlock, since the
221 // symboltable is used during compilation (VM_thread) The lock free
222 // synchronization is simplified by the fact that we do not delete
223 // entries in the symbol table during normal execution (only during
224 // safepoints).
225
226 Symbol* SymbolTable::lookup_and_add(const char* name, int len, TRAPS) {
227 unsigned int hashValue = hash_symbol(name, len);
228 int index = the_table()->hash_to_index(hashValue);
229
230 Symbol* s = the_table()->lookup(index, name, len, hashValue);
231
232 // Found
233 if (s != NULL) return s;
234
235 // Grab SymbolTable_lock first.
236 MutexLocker ml(SymbolTable_lock, THREAD);
237
238 // Otherwise, add to symbol to table
239 return the_table()->basic_add(index, (u1*)name, len, hashValue, true, CHECK_NULL);
240 }
241
242 Symbol* SymbolTable::lookup_and_add(const Symbol* sym, int begin, int end, TRAPS) {
243 char* buffer;
244 int index, len;
245 unsigned int hashValue;
246 char* name;
247 {
248 debug_only(No_Safepoint_Verifier nsv;)
249
250 name = (char*)sym->base() + begin;
251 len = end - begin;
252 hashValue = hash_symbol(name, len);
253 index = the_table()->hash_to_index(hashValue);
254 Symbol* s = the_table()->lookup(index, name, len, hashValue);
255
256 // Found
257 if (s != NULL) return s;
258 }
259
260 // Otherwise, add to symbol to table. Copy to a C string first.
261 char stack_buf[128];
262 ResourceMark rm(THREAD);
263 if (len <= 128) {
264 buffer = stack_buf;
265 } else {
266 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);
267 }
268 for (int i=0; i<len; i++) {
269 buffer[i] = name[i];
270 }
271 // Make sure there is no safepoint in the code above since name can't move.
272 // We can't include the code in No_Safepoint_Verifier because of the
273 // ResourceMark.
274
275 // Grab SymbolTable_lock first.
276 MutexLocker ml(SymbolTable_lock, THREAD);
277
278 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, true, CHECK_NULL);
279 }
280
281 Symbol* SymbolTable::lookup_and_hash(const char* name, int len,
282 unsigned int& hash) {
283 hash = hash_symbol(name, len);
284 int index = the_table()->hash_to_index(hash);
285
286 Symbol* s = the_table()->lookup(index, name, len, hash);
287 return s;
288 }
289
290 // Look up the address of the literal in the SymbolTable for this Symbol*
291 // Do not create any new symbols
292 // Do not increment the reference count to keep this alive
293 Symbol** SymbolTable::lookup_symbol_addr(Symbol* sym){
294 unsigned int hash = hash_symbol((char*)sym->bytes(), sym->utf8_length());
295 int index = the_table()->hash_to_index(hash);
296
297 for (HashtableEntry<Symbol*, mtSymbol>* e = the_table()->bucket(index); e != NULL; e = e->next()) {
298 if (e->hash() == hash) {
299 Symbol* literal_sym = e->literal();
300 if (sym == literal_sym) {
301 return e->literal_addr();
302 }
303 }
304 }
305 return NULL;
306 }
307
308 // Suggestion: Push unicode-based lookup all the way into the hashing
309 // and probing logic, so there is no need for convert_to_utf8 until
310 // an actual new Symbol* is created.
311 Symbol* SymbolTable::lookup_and_add_unicode(const jchar* name, int utf16_length, TRAPS) {
312 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
313 char stack_buf[128];
314 if (utf8_length < (int) sizeof(stack_buf)) {
315 char* chars = stack_buf;
316 UNICODE::convert_to_utf8(name, utf16_length, chars);
317 return lookup_and_add(chars, utf8_length, THREAD);
318 } else {
319 ResourceMark rm(THREAD);
320 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
321 UNICODE::convert_to_utf8(name, utf16_length, chars);
322 return lookup_and_add(chars, utf8_length, THREAD);
323 }
324 }
325
326 Symbol* SymbolTable::lookup_and_hash_unicode(const jchar* name, int utf16_length,
327 unsigned int& hash) {
328 int utf8_length = UNICODE::utf8_length((jchar*) name, utf16_length);
329 char stack_buf[128];
330 if (utf8_length < (int) sizeof(stack_buf)) {
331 char* chars = stack_buf;
332 UNICODE::convert_to_utf8(name, utf16_length, chars);
333 return lookup_and_hash(chars, utf8_length, hash);
334 } else {
335 ResourceMark rm;
336 char* chars = NEW_RESOURCE_ARRAY(char, utf8_length + 1);
337 UNICODE::convert_to_utf8(name, utf16_length, chars);
338 return lookup_and_hash(chars, utf8_length, hash);
339 }
340 }
341
342 void SymbolTable::add(ClassLoaderData* loader_data, constantPoolHandle cp,
343 int names_count,
344 const char** names, int* lengths, int* cp_indices,
345 unsigned int* hashValues, TRAPS) {
346 // Grab SymbolTable_lock first.
347 MutexLocker ml(SymbolTable_lock, THREAD);
348
349 SymbolTable* table = the_table();
350 bool added = table->basic_add(loader_data, cp, names_count, names, lengths,
351 cp_indices, hashValues, CHECK);
352 if (!added) {
353 // do it the hard way
354 for (int i=0; i<names_count; i++) {
355 int index = table->hash_to_index(hashValues[i]);
356 bool c_heap = !loader_data->is_the_null_class_loader_data();
357 Symbol* sym = table->basic_add(index, (u1*)names[i], lengths[i], hashValues[i], c_heap, CHECK);
358 cp->symbol_at_put(cp_indices[i], sym);
359 }
360 }
361 }
362
363 Symbol* SymbolTable::new_permanent_symbol(const char* name, TRAPS) {
364 unsigned int hash;
365 Symbol* result = SymbolTable::lookup_and_hash((char*)name, (int)strlen(name), hash);
366 if (result != NULL) {
367 return result;
368 }
369 // Grab SymbolTable_lock first.
370 MutexLocker ml(SymbolTable_lock, THREAD);
371
372 SymbolTable* table = the_table();
373 int index = table->hash_to_index(hash);
374 return table->basic_add(index, (u1*)name, (int)strlen(name), hash, false, THREAD);
375 }
376
377 Symbol* SymbolTable::basic_add(int index_arg, u1 *name, int len,
378 unsigned int hashValue_arg, bool c_heap, TRAPS) {
379 assert(!Universe::heap()->is_in_reserved(name),
380 "proposed name of symbol must be stable");
381
382 // Don't allow symbols to be created which cannot fit in a Symbol*.
383 if (len > Symbol::max_length()) {
384 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
385 "name is too long to represent");
408 assert(test->refcount() != 0, "lookup should have incremented the count");
409 return test;
410 }
411
412 // Create a new symbol.
413 Symbol* sym = allocate_symbol(name, len, c_heap, CHECK_NULL);
414 assert(sym->equals((char*)name, len), "symbol must be properly initialized");
415
416 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
417 add_entry(index, entry);
418 return sym;
419 }
420
421 // This version of basic_add adds symbols in batch from the constant pool
422 // parsing.
423 bool SymbolTable::basic_add(ClassLoaderData* loader_data, constantPoolHandle cp,
424 int names_count,
425 const char** names, int* lengths,
426 int* cp_indices, unsigned int* hashValues,
427 TRAPS) {
428 // Check symbol names are not too long. If any are too long, don't add any.
429 for (int i = 0; i< names_count; i++) {
430 if (lengths[i] > Symbol::max_length()) {
431 THROW_MSG_0(vmSymbols::java_lang_InternalError(),
432 "name is too long to represent");
433 }
434 }
435
436 // Cannot hit a safepoint in this function because the "this" pointer can move.
437 No_Safepoint_Verifier nsv;
438
439 for (int i=0; i<names_count; i++) {
440 // Check if the symbol table has been rehashed, if so, need to recalculate
441 // the hash value.
442 unsigned int hashValue;
443 if (use_alternate_hashcode()) {
444 hashValue = hash_symbol(names[i], lengths[i]);
445 } else {
446 hashValue = hashValues[i];
447 }
451 Symbol* test = lookup(index, names[i], lengths[i], hashValue);
452 if (test != NULL) {
453 // A race occurred and another thread introduced the symbol, this one
454 // will be dropped and collected. Use test instead.
455 cp->symbol_at_put(cp_indices[i], test);
456 assert(test->refcount() != 0, "lookup should have incremented the count");
457 } else {
458 // Create a new symbol. The null class loader is never unloaded so these
459 // are allocated specially in a permanent arena.
460 bool c_heap = !loader_data->is_the_null_class_loader_data();
461 Symbol* sym = allocate_symbol((const u1*)names[i], lengths[i], c_heap, CHECK_(false));
462 assert(sym->equals(names[i], lengths[i]), "symbol must be properly initialized"); // why wouldn't it be???
463 HashtableEntry<Symbol*, mtSymbol>* entry = new_entry(hashValue, sym);
464 add_entry(index, entry);
465 cp->symbol_at_put(cp_indices[i], sym);
466 }
467 }
468 return true;
469 }
470
471 void SymbolTable::verify() {
472 for (int i = 0; i < the_table()->table_size(); ++i) {
473 HashtableEntry<Symbol*, mtSymbol>* p = the_table()->bucket(i);
474 for ( ; p != NULL; p = p->next()) {
475 Symbol* s = (Symbol*)(p->literal());
476 guarantee(s != NULL, "symbol is NULL");
477 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
478 guarantee(p->hash() == h, "broken hash in symbol table entry");
479 guarantee(the_table()->hash_to_index(h) == i,
480 "wrong index in symbol table");
481 }
482 }
483 }
484
485 void SymbolTable::dump(outputStream* st) {
486 the_table()->dump_table(st, "SymbolTable");
487 }
488
489 //---------------------------------------------------------------------------
490 // Non-product code
491
492 #ifndef PRODUCT
493
494 void SymbolTable::print_histogram() {
495 MutexLocker ml(SymbolTable_lock);
496 const int results_length = 100;
497 int results[results_length];
498 int i,j;
499
500 // initialize results to zero
501 for (j = 0; j < results_length; j++) {
502 results[j] = 0;
503 }
504
505 int total = 0;
506 int max_symbols = 0;
507 int out_of_range = 0;
508 int memory_total = 0;
|