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 }