       1 /*
       2  * Copyright (c) 1997, 2013, 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 #ifndef SHARE_VM_CLASSFILE_SYMBOLTABLE_HPP
      26 #define SHARE_VM_CLASSFILE_SYMBOLTABLE_HPP
      27
      28 #include "memory/allocation.inline.hpp"
      29 #include "oops/symbol.hpp"
      30 #include "utilities/hashtable.hpp"
      31
      32 // The symbol table holds all Symbol*s and corresponding interned strings.
      33 // Symbol*s and literal strings should be canonicalized.
      34 //
      35 // The interned strings are created lazily.
      36 //
      37 // It is implemented as an open hash table with a fixed number of buckets.
      38 //
      39 // %note:
      40 //  - symbolTableEntrys are allocated in blocks to reduce the space overhead.
      41
      42 class BoolObjectClosure;
      43 class outputStream;
      44
      45
      46 // Class to hold a newly created or referenced Symbol* temporarily in scope.
      47 // new_symbol() and lookup() will create a Symbol* if not already in the
      48 // symbol table and add to the symbol's reference count.
      49 // probe() and lookup_only() will increment the refcount if symbol is found.
      50 class TempNewSymbol : public StackObj {
      51   Symbol* _temp;
      52
      53  public:
      54   TempNewSymbol() : _temp(NULL) {}
      55   // Creating or looking up a symbol increments the symbol's reference count
      56   TempNewSymbol(Symbol *s) : _temp(s) {}
      57
      58   // Operator= increments reference count.
      59   void operator=(const TempNewSymbol &s) {
      60     //clear();  //FIXME
      61     _temp = s._temp;
      62     if (_temp !=NULL) _temp->increment_refcount();
      63   }
      64
      65   // Decrement reference counter so it can go away if it's unique
      66   void clear() { if (_temp != NULL)  _temp->decrement_refcount();  _temp = NULL; }
      67
      68   ~TempNewSymbol() { clear(); }
      69
      70   // Operators so they can be used like Symbols
      71   Symbol* operator -> () const                   { return _temp; }
      72   bool    operator == (Symbol* o) const          { return _temp == o; }
      73   // Sneaky conversion function
      74   operator Symbol*()                             { return _temp; }
      75 };
      76
      77 class SymbolTable : public RehashableHashtable<Symbol*, mtSymbol> {
      78   friend class VMStructs;
      79   friend class ClassFileParser;
      80
      81 private:
      82   // The symbol table
      83   static SymbolTable* _the_table;
      84
      85   // Set if one bucket is out of balance due to hash algorithm deficiency
      86   static bool _needs_rehashing;
      87
      88   // For statistics
      89   static int _symbols_removed;
      90   static int _symbols_counted;
      91
      92   Symbol* allocate_symbol(const u1* name, int len, bool c_heap, TRAPS); // Assumes no characters larger than 0x7F
      93
      94   // Adding elements
      95   Symbol* basic_add(int index, u1* name, int len, unsigned int hashValue,
      96                     bool c_heap, TRAPS);
      97   bool basic_add(ClassLoaderData* loader_data,
      98                  constantPoolHandle cp, int names_count,
      99                  const char** names, int* lengths, int* cp_indices,
     100                  unsigned int* hashValues, TRAPS);
     101
     102   static void new_symbols(ClassLoaderData* loader_data,
     103                           constantPoolHandle cp, int names_count,
     104                           const char** name, int* lengths,
     105                           int* cp_indices, unsigned int* hashValues,
     106                           TRAPS) {
     107     add(loader_data, cp, names_count, name, lengths, cp_indices, hashValues, THREAD);
     108   }
     109
     110   Symbol* lookup(int index, const char* name, int len, unsigned int hash);
     111
     112   SymbolTable()
     113     : RehashableHashtable<Symbol*, mtSymbol>(SymbolTableSize, sizeof (HashtableEntry<Symbol*, mtSymbol>)) {}
     114
     115   SymbolTable(HashtableBucket<mtSymbol>* t, int number_of_entries)
     116     : RehashableHashtable<Symbol*, mtSymbol>(SymbolTableSize, sizeof (HashtableEntry<Symbol*, mtSymbol>), t,
     117                 number_of_entries) {}
     118
     119   // Arena for permanent symbols (null class loader) that are never unloaded
     120   static Arena*  _arena;
     121   static Arena* arena() { return _arena; }  // called for statistics
     122
     123   static void initialize_symbols(int arena_alloc_size = 0);
     124
     125   static volatile int _parallel_claimed_idx;
     126
     127   // Release any dead symbols
     128   static void buckets_unlink(int start_idx, int end_idx, int* processed, int* removed, size_t* memory_total);
     129 public:
     130   enum {
     131     symbol_alloc_batch_size = 8,
     132     // Pick initial size based on java -version size measurements
     133     symbol_alloc_arena_size = 360*K
     134   };
     135
     136   // The symbol table
     137   static SymbolTable* the_table() { return _the_table; }
     138
     139   // Size of one bucket in the string table.  Used when checking for rollover.
     140   static uint bucket_size() { return sizeof(HashtableBucket<mtSymbol>); }
     141
     142   static void create_table() {
     143     assert(_the_table == NULL, "One symbol table allowed.");
     144     _the_table = new SymbolTable();
     145     initialize_symbols(symbol_alloc_arena_size);
     146   }
     147
     148   static void create_table(HashtableBucket<mtSymbol>* t, int length,
     149                            int number_of_entries) {
     150     assert(_the_table == NULL, "One symbol table allowed.");
     151
     152     // If CDS archive used a different symbol table size, use that size instead
     153     // which is better than giving an error.
     154     SymbolTableSize = length/bucket_size();
     155
     156     _the_table = new SymbolTable(t, number_of_entries);
     157     // if CDS give symbol table a default arena size since most symbols
     158     // are already allocated in the shared misc section.
     159     initialize_symbols();
     160   }
     161
     162   static unsigned int hash_symbol(const char* s, int len);
     163
     164   static Symbol* lookup(const char* name, int len, TRAPS);
     165   // lookup only, won't add. Also calculate hash.
     166   static Symbol* lookup_only(const char* name, int len, unsigned int& hash);
     167   // Only copy to C string to be added if lookup failed.
     168   static Symbol* lookup(const Symbol* sym, int begin, int end, TRAPS);
     169
     170   static void release(Symbol* sym);
     171
     172   // Look up the address of the literal in the SymbolTable for this Symbol*
     173   static Symbol** lookup_symbol_addr(Symbol* sym);
     174
     175   // jchar (utf16) version of lookups
     176   static Symbol* lookup_unicode(const jchar* name, int len, TRAPS);
     177   static Symbol* lookup_only_unicode(const jchar* name, int len, unsigned int& hash);
     178
     179   static void add(ClassLoaderData* loader_data,
     180                   constantPoolHandle cp, int names_count,
     181                   const char** names, int* lengths, int* cp_indices,
     182                   unsigned int* hashValues, TRAPS);
     183
     184   // Release any dead symbols
     185   static void unlink() {
     186     int processed = 0;
     187     int removed = 0;
     188     unlink(&processed, &removed);
     189   }
     190   static void unlink(int* processed, int* removed);
     191   // Release any dead symbols, possibly parallel version
     192   static void possibly_parallel_unlink(int* processed, int* removed);
     193
     194   // iterate over symbols
     195   static void symbols_do(SymbolClosure *cl);
     196
     197   // Symbol creation
     198   static Symbol* new_symbol(const char* utf8_buffer, int length, TRAPS) {
     199     assert(utf8_buffer != NULL, "just checking");
     200     return lookup(utf8_buffer, length, THREAD);
     201   }
     202   static Symbol*       new_symbol(const char* name, TRAPS) {
     203     return new_symbol(name, (int)strlen(name), THREAD);
     204   }
     205   static Symbol*       new_symbol(const Symbol* sym, int begin, int end, TRAPS) {
     206     assert(begin <= end && end <= sym->utf8_length(), "just checking");
     207     return lookup(sym, begin, end, THREAD);
     208   }
     209
     210   // Create a symbol in the arena for symbols that are not deleted
     211   static Symbol* new_permanent_symbol(const char* name, TRAPS);
     212
     213   // Symbol lookup
     214   static Symbol* lookup(int index, const char* name, int len, TRAPS);
     215
     216   // Needed for preloading classes in signatures when compiling.
     217   // Returns the symbol is already present in symbol table, otherwise
     218   // NULL.  NO ALLOCATION IS GUARANTEED!
     219   static Symbol* probe(const char* name, int len) {
     220     unsigned int ignore_hash;
     221     return lookup_only(name, len, ignore_hash);
     222   }
     223   static Symbol* probe_unicode(const jchar* name, int len) {
     224     unsigned int ignore_hash;
     225     return lookup_only_unicode(name, len, ignore_hash);
     226   }
     227
     228   // Histogram
     229   static void print_histogram()     PRODUCT_RETURN;
     230   static void print()     PRODUCT_RETURN;
     231
     232   // Debugging
     233   static void verify();
     234   static void dump(outputStream* st);
     235
     236   // Sharing
     237   static void copy_buckets(char** top, char*end) {
     238     the_table()->Hashtable<Symbol*, mtSymbol>::copy_buckets(top, end);
     239   }
     240   static void copy_table(char** top, char*end) {
     241     the_table()->Hashtable<Symbol*, mtSymbol>::copy_table(top, end);
     242   }
     243   static void reverse(void* boundary = NULL) {
     244     the_table()->Hashtable<Symbol*, mtSymbol>::reverse(boundary);
     245   }
     246
     247   // Rehash the symbol table if it gets out of balance
     248   static void rehash_table();
     249   static bool needs_rehashing()         { return _needs_rehashing; }
     250   // Parallel chunked scanning
     251   static void clear_parallel_claimed_index() { _parallel_claimed_idx = 0; }
     252   static int parallel_claimed_index()        { return _parallel_claimed_idx; }
     253 };
     254
     255 class StringTable : public RehashableHashtable<oop, mtSymbol> {
     256   friend class VMStructs;
     257
     258 private:
     259   // The string table
     260   static StringTable* _the_table;
     261
     262   // Set if one bucket is out of balance due to hash algorithm deficiency
     263   static bool _needs_rehashing;
     264
     265   // Claimed high water mark for parallel chunked scanning
     266   static volatile int _parallel_claimed_idx;
     267
     268   static oop intern(Handle string_or_null, jchar* chars, int length, TRAPS);
     269   oop basic_add(int index, Handle string_or_null, jchar* name, int len,
     270                 unsigned int hashValue, TRAPS);
     271
     272   oop lookup(int index, jchar* chars, int length, unsigned int hashValue);
     273
     274   // Apply the give oop closure to the entries to the buckets
     275   // in the range [start_idx, end_idx).
     276   static void buckets_oops_do(OopClosure* f, int start_idx, int end_idx);
     277   // Unlink or apply the give oop closure to the entries to the buckets
     278   // in the range [start_idx, end_idx).
     279   static void buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, int* processed, int* removed);
     280
     281   StringTable() : RehashableHashtable<oop, mtSymbol>((int)StringTableSize,
     282                               sizeof (HashtableEntry<oop, mtSymbol>)) {}
     283
     284   StringTable(HashtableBucket<mtSymbol>* t, int number_of_entries)
     285     : RehashableHashtable<oop, mtSymbol>((int)StringTableSize, sizeof (HashtableEntry<oop, mtSymbol>), t,
     286                      number_of_entries) {}
     287 public:
     288   // The string table
     289   static StringTable* the_table() { return _the_table; }
     290
     291   // Size of one bucket in the string table.  Used when checking for rollover.
     292   static uint bucket_size() { return sizeof(HashtableBucket<mtSymbol>); }
     293
     294   static void create_table() {
     295     assert(_the_table == NULL, "One string table allowed.");
     296     _the_table = new StringTable();
     297   }
     298
     299   // GC support
     300   //   Delete pointers to otherwise-unreachable objects.
     301   static void unlink_or_oops_do(BoolObjectClosure* cl, OopClosure* f) {
     302     int processed = 0;
     303     int removed = 0;
     304     unlink_or_oops_do(cl, f, &processed, &removed);
     305   }
     306   static void unlink(BoolObjectClosure* cl) {
     307     int processed = 0;
     308     int removed = 0;
     309     unlink_or_oops_do(cl, NULL, &processed, &removed);
     310   }
     311   static void unlink_or_oops_do(BoolObjectClosure* cl, OopClosure* f, int* processed, int* removed);
     312   static void unlink(BoolObjectClosure* cl, int* processed, int* removed) {
     313     unlink_or_oops_do(cl, NULL, processed, removed);
     314   }
     315   // Serially invoke "f->do_oop" on the locations of all oops in the table.
     316   static void oops_do(OopClosure* f);
     317
     318   // Possibly parallel versions of the above
     319   static void possibly_parallel_unlink_or_oops_do(BoolObjectClosure* cl, OopClosure* f, int* processed, int* removed);
     320   static void possibly_parallel_unlink(BoolObjectClosure* cl, int* processed, int* removed) {
     321     possibly_parallel_unlink_or_oops_do(cl, NULL, processed, removed);
     322   }
     323   static void possibly_parallel_oops_do(OopClosure* f);
     324
     325   // Hashing algorithm, used as the hash value used by the
     326   //     StringTable for bucket selection and comparison (stored in the
     327   //     HashtableEntry structures).  This is used in the String.intern() method.
     328   static unsigned int hash_string(const jchar* s, int len);
     329
     330   // Internal test.
     331   static void test_alt_hash() PRODUCT_RETURN;
     332
     333   // Probing
     334   static oop lookup(Symbol* symbol);
     335   static oop lookup(jchar* chars, int length);
     336
     337   // Interning
     338   static oop intern(Symbol* symbol, TRAPS);
     339   static oop intern(oop string, TRAPS);
     340   static oop intern(const char *utf8_string, TRAPS);
     341
     342   // Debugging
     343   static void verify();
     344   static void dump(outputStream* st);
     345
     346   enum VerifyMesgModes {
     347     _verify_quietly    = 0,
     348     _verify_with_mesgs = 1
     349   };
     350
     351   enum VerifyRetTypes {
     352     _verify_pass          = 0,
     353     _verify_fail_continue = 1,
     354     _verify_fail_done     = 2
     355   };
     356
     357   static VerifyRetTypes compare_entries(int bkt1, int e_cnt1,
     358                                         HashtableEntry<oop, mtSymbol>* e_ptr1,
     359                                         int bkt2, int e_cnt2,
     360                                         HashtableEntry<oop, mtSymbol>* e_ptr2);
     361   static VerifyRetTypes verify_entry(int bkt, int e_cnt,
     362                                      HashtableEntry<oop, mtSymbol>* e_ptr,
     363                                      VerifyMesgModes mesg_mode);
     364   static int verify_and_compare_entries();
     365
     366   // Sharing
     367   static void copy_buckets(char** top, char*end) {
     368     the_table()->Hashtable<oop, mtSymbol>::copy_buckets(top, end);
     369   }
     370   static void copy_table(char** top, char*end) {
     371     the_table()->Hashtable<oop, mtSymbol>::copy_table(top, end);
     372   }
     373   static void reverse() {
     374     the_table()->Hashtable<oop, mtSymbol>::reverse();
     375   }
     376
     377   // Rehash the symbol table if it gets out of balance
     378   static void rehash_table();
     379   static bool needs_rehashing() { return _needs_rehashing; }
     380
     381   // Parallel chunked scanning
     382   static void clear_parallel_claimed_index() { _parallel_claimed_idx = 0; }
     383   static int parallel_claimed_index() { return _parallel_claimed_idx; }
     384 };
     385 #endif // SHARE_VM_CLASSFILE_SYMBOLTABLE_HPP