38 #if INCLUDE_ALL_GCS

    39 #include "gc_implementation/g1/g1StringDedup.hpp"

    40 #endif

    41 

    42 // --------------------------------------------------------------------------

   590 

   591 // --------------------------------------------------------------------------

   592 

   593 #ifdef ASSERT

   594 class StableMemoryChecker : public StackObj {

   595   enum { _bufsize = wordSize*4 };

   596 

   597   address _region;

   598   jint    _size;

   599   u1      _save_buf[_bufsize];

   600 

   601   int sample(u1* save_buf) {

   602     if (_size <= _bufsize) {

   603       memcpy(save_buf, _region, _size);

   604       return _size;

   605     } else {

   606       // copy head and tail

   607       memcpy(&save_buf[0],          _region,                      _bufsize/2);

   608       memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2);

   609       return (_bufsize/2)*2;

   610     }

   611   }

   612 

   613  public:

   614   StableMemoryChecker(const void* region, jint size) {

   615     _region = (address) region;

   616     _size   = size;

   617     sample(_save_buf);

   618   }

   619 

   620   bool verify() {

   621     u1 check_buf[sizeof(_save_buf)];

   622     int check_size = sample(check_buf);

   623     return (0 == memcmp(_save_buf, check_buf, check_size));

   624   }

   625 

   626   void set_region(const void* region) { _region = (address) region; }

   627 };

   628 #endif

   629 

   630 

   631 // --------------------------------------------------------------------------

   632 StringTable* StringTable::_the_table = NULL;

   633 

   634 bool StringTable::_needs_rehashing = false;

   635 

   636 volatile int StringTable::_parallel_claimed_idx = 0;

   637 

   638 // Pick hashing algorithm

   639 unsigned int StringTable::hash_string(const jchar* s, int len) {

   640   return use_alternate_hashcode() ? AltHashing::murmur3_32(seed(), s, len) :

   641                                     java_lang_String::hash_code(s, len);

   642 }

   643 

   644 oop StringTable::lookup(int index, jchar* name,

   645                         int len, unsigned int hash) {

   646   int count = 0;

   647   for (HashtableEntry<oop, mtSymbol>* l = bucket(index); l != NULL; l = l->next()) {

   648     count++;

   649     if (l->hash() == hash) {

   650       if (java_lang_String::equals(l->literal(), name, len)) {

   651         return l->literal();

   652       }

   653     }

   654   }

   655   // If the bucket size is too deep check if this hash code is insufficient.

   656   if (count >= BasicHashtable<mtSymbol>::rehash_count && !needs_rehashing()) {

   657     _needs_rehashing = check_rehash_table(count);

   658   }

   659   return NULL;

   660 }

   661 

   662 

   663 oop StringTable::basic_add(int index_arg, Handle string, jchar* name,

   664                            int len, unsigned int hashValue_arg, TRAPS) {

   665 

   666   assert(java_lang_String::equals(string(), name, len),

   667          "string must be properly initialized");

   668   // Cannot hit a safepoint in this function because the "this" pointer can move.

   669   No_Safepoint_Verifier nsv;

   670 

   671   // Check if the symbol table has been rehashed, if so, need to recalculate

   672   // the hash value and index before second lookup.

   673   unsigned int hashValue;

   674   int index;

   675   if (use_alternate_hashcode()) {

   676     hashValue = hash_string(name, len);

   677     index = hash_to_index(hashValue);

   678   } else {

   679     hashValue = hashValue_arg;

   680     index = index_arg;

   681   }

   682 

   683   // Since look-up was done lock-free, we need to check if another

   684   // thread beat us in the race to insert the symbol.

   685 

   686   oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)

   687   if (test != NULL) {

   688     // Entry already added

   689     return test;

   690   }

   691 

   692   HashtableEntry<oop, mtSymbol>* entry = new_entry(hashValue, string());

   693   add_entry(index, entry);

   694   return string();

   695 }

   696 

   697 

   698 oop StringTable::lookup(Symbol* symbol) {

   699   ResourceMark rm;

   700   int length;

   701   jchar* chars = symbol->as_unicode(length);

   702   return lookup(chars, length);

   703 }

   704 

   705 

   706 oop StringTable::lookup(jchar* name, int len) {

   707   unsigned int hash = hash_string(name, len);

   708   int index = the_table()->hash_to_index(hash);

   709   return the_table()->lookup(index, name, len, hash);

   710 }

   711 

   712 

   713 oop StringTable::intern(Handle string_or_null, jchar* name,

   714                         int len, TRAPS) {

   715   unsigned int hashValue = hash_string(name, len);

   716   int index = the_table()->hash_to_index(hashValue);

   717   oop found_string = the_table()->lookup(index, name, len, hashValue);

   718 

   719   // Found

   720   if (found_string != NULL) return found_string;

   721 

   722   debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));

   723   assert(!Universe::heap()->is_in_reserved(name),

   724          "proposed name of symbol must be stable");

   725 

   726   Handle string;

   727   // try to reuse the string if possible

   728   if (!string_or_null.is_null()) {

   729     string = string_or_null;

   730   } else {

   731     string = java_lang_String::create_from_unicode(name, len, CHECK_NULL);

   732   }

   733 

   734 #if INCLUDE_ALL_GCS

   735   if (G1StringDedup::is_enabled()) {

   736     // Deduplicate the string before it is interned. Note that we should never

   737     // deduplicate a string after it has been interned. Doing so will counteract

   738     // compiler optimizations done on e.g. interned string literals.

   739     G1StringDedup::deduplicate(string());

   740   }

   741 #endif

   742 

   743   // Grab the StringTable_lock before getting the_table() because it could

   744   // change at safepoint.

   745   MutexLocker ml(StringTable_lock, THREAD);

   746 

   747   // Otherwise, add to symbol to table

   748   return the_table()->basic_add(index, string, name, len,

   749                                 hashValue, CHECK_NULL);

   750 }

   751 

   752 oop StringTable::intern(Symbol* symbol, TRAPS) {

   753   if (symbol == NULL) return NULL;

   754   ResourceMark rm(THREAD);

   755   int length;

   756   jchar* chars = symbol->as_unicode(length);

   757   Handle string;

   758   oop result = intern(string, chars, length, CHECK_NULL);

   759   return result;

   760 }

   761 

   762 

   763 oop StringTable::intern(oop string, TRAPS)

   764 {

   765   if (string == NULL) return NULL;

   766   ResourceMark rm(THREAD);

   767   int length;

   768   Handle h_string (THREAD, string);

   769   jchar* chars = java_lang_String::as_unicode_string(string, length, CHECK_NULL);

   770   oop result = intern(h_string, chars, length, CHECK_NULL);

   771   return result;

   772 }

   773 

   774 

   775 oop StringTable::intern(const char* utf8_string, TRAPS) {

   776   if (utf8_string == NULL) return NULL;

   777   ResourceMark rm(THREAD);

   778   int length = UTF8::unicode_length(utf8_string);

   779   jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);

   780   UTF8::convert_to_unicode(utf8_string, chars, length);

   781   Handle string;

   782   oop result = intern(string, chars, length, CHECK_NULL);

   783   return result;

   784 }

   785 

   786 void StringTable::unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {

   787   buckets_unlink_or_oops_do(is_alive, f, 0, the_table()->table_size(), processed, removed);

   788 }

   789 

   790 void StringTable::possibly_parallel_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int* processed, int* removed) {

   791   // Readers of the table are unlocked, so we should only be removing

   792   // entries at a safepoint.

   793   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");

   794   const int limit = the_table()->table_size();

   795 

   796   for (;;) {

   797     // Grab next set of buckets to scan

   798     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;

   799     if (start_idx >= limit) {

   800       // End of table

   801       break;

   802     }

   803 

   804     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);

   805     buckets_unlink_or_oops_do(is_alive, f, start_idx, end_idx, processed, removed);

   806   }

   807 }

   808 

   809 void StringTable::buckets_oops_do(OopClosure* f, int start_idx, int end_idx) {

   810   const int limit = the_table()->table_size();

   811 

   812   assert(0 <= start_idx && start_idx <= limit,

   813          err_msg("start_idx (%d) is out of bounds", start_idx));

   814   assert(0 <= end_idx && end_idx <= limit,

   815          err_msg("end_idx (%d) is out of bounds", end_idx));

   816   assert(start_idx <= end_idx,

   817          err_msg("Index ordering: start_idx=%d, end_idx=%d",

   818                  start_idx, end_idx));

   819 

   820   for (int i = start_idx; i < end_idx; i += 1) {

   821     HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);

   822     while (entry != NULL) {

   823       assert(!entry->is_shared(), "CDS not used for the StringTable");

   824 

   825       f->do_oop((oop*)entry->literal_addr());

   826 

   827       entry = entry->next();

   828     }

   829   }

   830 }

   831 

   832 void StringTable::buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, int* processed, int* removed) {

   833   const int limit = the_table()->table_size();

   834 

   835   assert(0 <= start_idx && start_idx <= limit,

   836          err_msg("start_idx (%d) is out of bounds", start_idx));

   837   assert(0 <= end_idx && end_idx <= limit,

   838          err_msg("end_idx (%d) is out of bounds", end_idx));

   839   assert(start_idx <= end_idx,

   840          err_msg("Index ordering: start_idx=%d, end_idx=%d",

   841                  start_idx, end_idx));

   842 

   843   for (int i = start_idx; i < end_idx; ++i) {

   844     HashtableEntry<oop, mtSymbol>** p = the_table()->bucket_addr(i);

   845     HashtableEntry<oop, mtSymbol>* entry = the_table()->bucket(i);

   846     while (entry != NULL) {

   847       assert(!entry->is_shared(), "CDS not used for the StringTable");

   848 

   849       if (is_alive->do_object_b(entry->literal())) {

   850         if (f != NULL) {

   851           f->do_oop((oop*)entry->literal_addr());

   852         }

   853         p = entry->next_addr();

   854       } else {

   855         *p = entry->next();

   856         the_table()->free_entry(entry);

   857         (*removed)++;

   858       }

   859       (*processed)++;

   860       entry = *p;

   861     }

   862   }

   863 }

   864 

   865 void StringTable::oops_do(OopClosure* f) {

   866   buckets_oops_do(f, 0, the_table()->table_size());

   867 }

   868 

   869 void StringTable::possibly_parallel_oops_do(OopClosure* f) {

   870   const int limit = the_table()->table_size();

   871 

   872   for (;;) {

   873     // Grab next set of buckets to scan

   874     int start_idx = Atomic::add(ClaimChunkSize, &_parallel_claimed_idx) - ClaimChunkSize;

   875     if (start_idx >= limit) {

   876       // End of table

   877       break;

   878     }

   879 

   880     int end_idx = MIN2(limit, start_idx + ClaimChunkSize);

   881     buckets_oops_do(f, start_idx, end_idx);

   882   }

   883 }

   884 

   885 // This verification is part of Universe::verify() and needs to be quick.

   886 // See StringTable::verify_and_compare() below for exhaustive verification.

   887 void StringTable::verify() {

   888   for (int i = 0; i < the_table()->table_size(); ++i) {

   889     HashtableEntry<oop, mtSymbol>* p = the_table()->bucket(i);

   890     for ( ; p != NULL; p = p->next()) {

   891       oop s = p->literal();

   892       guarantee(s != NULL, "interned string is NULL");

   893       unsigned int h = java_lang_String::hash_string(s);

   894       guarantee(p->hash() == h, "broken hash in string table entry");

   895       guarantee(the_table()->hash_to_index(h) == i,

   896                 "wrong index in string table");

   897     }

   898   }

   899 }

   900 

   901 void StringTable::dump(outputStream* st) {

   902   the_table()->dump_table(st, "StringTable");

   903 }

   904 

   905 StringTable::VerifyRetTypes StringTable::compare_entries(

   906                                       int bkt1, int e_cnt1,

   907                                       HashtableEntry<oop, mtSymbol>* e_ptr1,

   908                                       int bkt2, int e_cnt2,

   909                                       HashtableEntry<oop, mtSymbol>* e_ptr2) {

   910   // These entries are sanity checked by verify_and_compare_entries()

   911   // before this function is called.

   912   oop str1 = e_ptr1->literal();

   913   oop str2 = e_ptr2->literal();

   914 

   915   if (str1 == str2) {

   916     tty->print_cr("ERROR: identical oop values (0x" PTR_FORMAT ") "

   917                   "in entry @ bucket[%d][%d] and entry @ bucket[%d][%d]",

   918                   (void *)str1, bkt1, e_cnt1, bkt2, e_cnt2);

   919     return _verify_fail_continue;

   920   }

   921 

   922   if (java_lang_String::equals(str1, str2)) {

   923     tty->print_cr("ERROR: identical String values in entry @ "

   924                   "bucket[%d][%d] and entry @ bucket[%d][%d]",

   925                   bkt1, e_cnt1, bkt2, e_cnt2);

   926     return _verify_fail_continue;

   927   }

   928 

   929   return _verify_pass;

   930 }

   931 

   932 StringTable::VerifyRetTypes StringTable::verify_entry(int bkt, int e_cnt,

   933                                       HashtableEntry<oop, mtSymbol>* e_ptr,

   934                                       StringTable::VerifyMesgModes mesg_mode) {

   935 

   936   VerifyRetTypes ret = _verify_pass;  // be optimistic

   937 

   938   oop str = e_ptr->literal();

   939   if (str == NULL) {

   940     if (mesg_mode == _verify_with_mesgs) {

   941       tty->print_cr("ERROR: NULL oop value in entry @ bucket[%d][%d]", bkt,

   942                     e_cnt);

   943     }

   944     // NULL oop means no more verifications are possible

   945     return _verify_fail_done;

   946   }

   947 

   948   if (str->klass() != SystemDictionary::String_klass()) {

   949     if (mesg_mode == _verify_with_mesgs) {

   950       tty->print_cr("ERROR: oop is not a String in entry @ bucket[%d][%d]",

   951                     bkt, e_cnt);

   952     }

   953     // not a String means no more verifications are possible

   954     return _verify_fail_done;

   955   }

   956 

   957   unsigned int h = java_lang_String::hash_string(str);

   958   if (e_ptr->hash() != h) {

   959     if (mesg_mode == _verify_with_mesgs) {

   960       tty->print_cr("ERROR: broken hash value in entry @ bucket[%d][%d], "

   961                     "bkt_hash=%d, str_hash=%d", bkt, e_cnt, e_ptr->hash(), h);

   962     }

   963     ret = _verify_fail_continue;

   964   }

   965 

   966   if (the_table()->hash_to_index(h) != bkt) {

   967     if (mesg_mode == _verify_with_mesgs) {

   968       tty->print_cr("ERROR: wrong index value for entry @ bucket[%d][%d], "

   969                     "str_hash=%d, hash_to_index=%d", bkt, e_cnt, h,

   970                     the_table()->hash_to_index(h));

   971     }

   972     ret = _verify_fail_continue;

   973   }

   974 

   975   return ret;

   976 }

   977 

   978 // See StringTable::verify() above for the quick verification that is

   979 // part of Universe::verify(). This verification is exhaustive and

   980 // reports on every issue that is found. StringTable::verify() only

   981 // reports on the first issue that is found.

   982 //

   983 // StringTable::verify_entry() checks:

   984 // - oop value != NULL (same as verify())

   985 // - oop value is a String

   986 // - hash(String) == hash in entry (same as verify())

   987 // - index for hash == index of entry (same as verify())

   988 //

   989 // StringTable::compare_entries() checks:

   990 // - oops are unique across all entries

   991 // - String values are unique across all entries

   992 //

   993 int StringTable::verify_and_compare_entries() {

   994   assert(StringTable_lock->is_locked(), "sanity check");

   995 

   996   int  fail_cnt = 0;

   997 

   998   // first, verify all the entries individually:

   999   for (int bkt = 0; bkt < the_table()->table_size(); bkt++) {

  1000     HashtableEntry<oop, mtSymbol>* e_ptr = the_table()->bucket(bkt);

  1001     for (int e_cnt = 0; e_ptr != NULL; e_ptr = e_ptr->next(), e_cnt++) {

  1002       VerifyRetTypes ret = verify_entry(bkt, e_cnt, e_ptr, _verify_with_mesgs);

  1003       if (ret != _verify_pass) {

  1004         fail_cnt++;

  1005       }

  1006     }

  1007   }

  1008 

  1009   // Optimization: if the above check did not find any failures, then

  1010   // the comparison loop below does not need to call verify_entry()

  1011   // before calling compare_entries(). If there were failures, then we

  1012   // have to call verify_entry() to see if the entry can be passed to

  1013   // compare_entries() safely. When we call verify_entry() in the loop

  1014   // below, we do so quietly to void duplicate messages and we don't

  1015   // increment fail_cnt because the failures have already been counted.

  1016   bool need_entry_verify = (fail_cnt != 0);

  1017 

  1018   // second, verify all entries relative to each other:

  1019   for (int bkt1 = 0; bkt1 < the_table()->table_size(); bkt1++) {

  1020     HashtableEntry<oop, mtSymbol>* e_ptr1 = the_table()->bucket(bkt1);

  1021     for (int e_cnt1 = 0; e_ptr1 != NULL; e_ptr1 = e_ptr1->next(), e_cnt1++) {

  1022       if (need_entry_verify) {

  1023         VerifyRetTypes ret = verify_entry(bkt1, e_cnt1, e_ptr1,

  1024                                           _verify_quietly);

  1025         if (ret == _verify_fail_done) {

  1026           // cannot use the current entry to compare against other entries

  1027           continue;

  1028         }

  1029       }

  1030 

  1031       for (int bkt2 = bkt1; bkt2 < the_table()->table_size(); bkt2++) {

  1032         HashtableEntry<oop, mtSymbol>* e_ptr2 = the_table()->bucket(bkt2);

  1033         int e_cnt2;

  1034         for (e_cnt2 = 0; e_ptr2 != NULL; e_ptr2 = e_ptr2->next(), e_cnt2++) {

  1035           if (bkt1 == bkt2 && e_cnt2 <= e_cnt1) {

  1036             // skip the entries up to and including the one that

  1037             // we're comparing against

  1038             continue;

  1039           }

  1040 

  1041           if (need_entry_verify) {

  1042             VerifyRetTypes ret = verify_entry(bkt2, e_cnt2, e_ptr2,

  1043                                               _verify_quietly);

  1044             if (ret == _verify_fail_done) {

  1045               // cannot compare against this entry

  1046               continue;

  1047             }

  1048           }

  1049 

  1050           // compare two entries, report and count any failures:

  1051           if (compare_entries(bkt1, e_cnt1, e_ptr1, bkt2, e_cnt2, e_ptr2)

  1052               != _verify_pass) {

  1053             fail_cnt++;

  1054           }

  1055         }

  1056       }

  1057     }

  1058   }

  1059   return fail_cnt;

  1060 }

  1061 

  1062 // Create a new table and using alternate hash code, populate the new table

  1063 // with the existing strings.   Set flag to use the alternate hash code afterwards.

  1064 void StringTable::rehash_table() {

  1065   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");

  1066   // This should never happen with -Xshare:dump but it might in testing mode.

  1067   if (DumpSharedSpaces) return;

  1068   StringTable* new_table = new StringTable();

  1069 

  1070   // Rehash the table

  1071   the_table()->move_to(new_table);

  1072 

  1073   // Delete the table and buckets (entries are reused in new table).

  1074   delete _the_table;

  1075   // Don't check if we need rehashing until the table gets unbalanced again.

  1076   // Then rehash with a new global seed.

  1077   _needs_rehashing = false;

  1078   _the_table = new_table;

  1079 }