46 #include "utilities/hashtable.inline.hpp"

    52 #include "utilities/concurrentHashTable.inline.hpp"

    53 #include "utilities/concurrentHashTableTasks.inline.hpp"

    49 // the number of buckets a thread claims

    56 // We prefer short chains of avg 2

    50 const int ClaimChunkSize = 32;

    57 #define PREF_AVG_LIST_LEN   2

    51 

    58 // 2^24 is max size

    52 #ifdef ASSERT

    59 #define END_SIZE           24

    53 class StableMemoryChecker : public StackObj {

    60 // If a chain gets to 32 something might be wrong

    54   enum { _bufsize = wordSize*4 };

    61 #define REHASH_LEN         32

    55 

    62 // If we have as many dead items as 50% of the number of bucket

    56   address _region;

    63 #define CLEAN_DEAD_HIGH_WATER_MARK 0.5

    57   jint    _size;

    58   u1      _save_buf[_bufsize];

    59 

    60   int sample(u1* save_buf) {

    61     if (_size <= _bufsize) {

    62       memcpy(save_buf, _region, _size);

    63       return _size;

    64     } else {

    65       // copy head and tail

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

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

    68       return (_bufsize/2)*2;

    69     }

    70   }

    71 

    72  public:

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

    74     _region = (address) region;

    75     _size   = size;

    76     sample(_save_buf);

    77   }

    78 

    79   bool verify() {

    80     u1 check_buf[sizeof(_save_buf)];

    81     int check_size = sample(check_buf);

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

    83   }

    84 

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

    86 };

    87 #endif

    88 

    98 

    69 bool StringTable::_alt_hash = false;

    99 // Pick hashing algorithm

    70 

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

    71 static juint murmur_seed = 0;

   101   return use_alternate_hashcode() ? alt_hash_string(s, len) :

    72 

   102                                     java_lang_String::hash_code(s, len);

    73 uintx hash_string(const jchar* s, int len, bool useAlt) {

   103 }

    74   return  useAlt ?

   104 

    75     AltHashing::murmur3_32(murmur_seed, s, len) :

   105 unsigned int StringTable::alt_hash_string(const jchar* s, int len) {

    76     java_lang_String::hash_code(s, len);

   106   return AltHashing::murmur3_32(seed(), s, len);

    77 }

   107 }

    78 

   108 

    79 class StringTableConfig : public StringTableHash::BaseConfig {

   109 unsigned int StringTable::hash_string(oop string) {

    80  private:

   110   EXCEPTION_MARK;

    81  public:

   111   if (string == NULL) {

    82   static uintx get_hash(WeakHandle<vm_string_table_data> const& value,

   112     return hash_string((jchar*)NULL, 0);

    83                         bool* is_dead) {

   113   }

    84     EXCEPTION_MARK;

   114   ResourceMark rm(THREAD);

    85     oop val_oop = value.peek();

   115   // All String oops are hashed as unicode

    86     if (val_oop == NULL) {

   116   int length;

    87       *is_dead = true;

   117   jchar* chars = java_lang_String::as_unicode_string(string, length, THREAD);

    88       return 0;

   118   if (chars != NULL) {

    89     }

   119     return hash_string(chars, length);

    90     *is_dead = false;

   120   } else {

    91     ResourceMark rm(THREAD);

   121     vm_exit_out_of_memory(length, OOM_MALLOC_ERROR, "unable to create Unicode string for verification");

    92     // All String oops are hashed as unicode

    93     int length;

    94     jchar* chars = java_lang_String::as_unicode_string(val_oop, length, THREAD);

    95     if (chars != NULL) {

    96       return hash_string(chars, length, StringTable::_alt_hash);

    97     }

    98     vm_exit_out_of_memory(length, OOM_MALLOC_ERROR, "get hash from oop");

   124 }

   101   // We use default allocation/deallocation but counted

   125 

   102   static void* allocate_node(size_t size,

   126 oop StringTable::string_object(HashtableEntry<oop, mtSymbol>* entry) {

   103                              WeakHandle<vm_string_table_data> const& value) {

   127   return RootAccess<ON_PHANTOM_OOP_REF>::oop_load(entry->literal_addr());

   104     StringTable::item_added();

   128 }

   105     return StringTableHash::BaseConfig::allocate_node(size, value);

   129 

   106   }

   130 oop StringTable::string_object_no_keepalive(HashtableEntry<oop, mtSymbol>* entry) {

   107   static void free_node(void* memory,

   131   // The AS_NO_KEEPALIVE peeks at the oop without keeping it alive.

   108                         WeakHandle<vm_string_table_data> const& value) {

   132   // This is *very dangerous* in general but is okay in this specific

   109     value.release();

   133   // case. The subsequent oop_load keeps the oop alive if it it matched

   110     StringTableHash::BaseConfig::free_node(memory, value);

   134   // the jchar* string.

   111     StringTable::item_removed();

   135   return RootAccess<ON_PHANTOM_OOP_REF | AS_NO_KEEPALIVE>::oop_load(entry->literal_addr());

   112   }

   136 }

   113 };

   137 

   114 

   138 void StringTable::set_string_object(HashtableEntry<oop, mtSymbol>* entry, oop string) {

   115 class StringTableLookupJchar : StackObj {

   139   RootAccess<ON_PHANTOM_OOP_REF>::oop_store(entry->literal_addr(), string);

   116  private:

   140 }

   117   Thread* _thread;

   141 

   118   uintx _hash;

   142 oop StringTable::lookup_shared(jchar* name, int len, unsigned int hash) {

   119   int _len;

   143   assert(hash == java_lang_String::hash_code(name, len),

   120   const jchar* _str;

   144          "hash must be computed using java_lang_String::hash_code");

   121   Handle _found;

   145   return _shared_table.lookup((const char*)name, hash, len);

   122 

   146 }

   123  public:

   147 

   124   StringTableLookupJchar(Thread* thread, uintx hash, const jchar* key, int len)

   148 oop StringTable::lookup_in_main_table(int index, jchar* name,

   125     : _thread(thread), _hash(hash), _str(key), _len(len) {

   149                                       int len, unsigned int hash) {

   126   }

   150   int count = 0;

   127   uintx get_hash() const {

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

   128     return _hash;

   152     count++;

   129   }

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

   130   bool equals(WeakHandle<vm_string_table_data>* value, bool* is_dead) {

   154       if (java_lang_String::equals(string_object_no_keepalive(l), name, len)) {

   131     oop val_oop = value->peek();

   155         // We must perform a new load with string_object() that keeps the string

   132     if (val_oop == NULL) {

   156         // alive as we must expose the oop as strongly reachable when exiting

   133       // dead oop, mark this hash dead for cleaning

   157         // this context, in case the oop gets published.

   134       *is_dead = true;

   158         return string_object(l);

   135       return false;

   159       }

   136     }

   160     }

   137     bool equals = java_lang_String::equals(val_oop, (jchar*)_str, _len);

   161   }

   138     if (!equals) {

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

   139       return false;

   163   if (count >= rehash_count && !needs_rehashing()) {

   140     }

   164     _needs_rehashing = check_rehash_table(count);

   141     // Need to resolve weak handle and Handleize through possible safepoint.

   165   }

   142      _found = Handle(_thread, value->resolve());

   166   return NULL;

   143     return true;

   167 }

   144   }

   168 

   145 };

   169 

   146 

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

   147 class StringTableLookupOop : public StackObj {

   171                            int len, unsigned int hashValue_arg, TRAPS) {

   148  private:

   172 

   149   Thread* _thread;

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

   150   uintx _hash;

   174          "string must be properly initialized");

   151   Handle _find;

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

   152   Handle _found;  // Might be a different oop with the same value that's already

   176   NoSafepointVerifier nsv;

   153                   // in the table, which is the point.

   177 

   154  public:

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

   155   StringTableLookupOop(Thread* thread, uintx hash, Handle handle)

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

   156     : _thread(thread), _hash(hash), _find(handle) { }

   180   unsigned int hashValue;

   157 

   181   int index;

   158   uintx get_hash() const {

   182   if (use_alternate_hashcode()) {

   159     return _hash;

   183     hashValue = alt_hash_string(name, len);

   160   }

   184     index = hash_to_index(hashValue);

   161 

   185   } else {

   162   bool equals(WeakHandle<vm_string_table_data>* value, bool* is_dead) {

   186     hashValue = hashValue_arg;

   163     oop val_oop = value->peek();

   187     index = index_arg;

   164     if (val_oop == NULL) {

   188   }

   165       // dead oop, mark this hash dead for cleaning

   189 

   166       *is_dead = true;

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

   167       return false;

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

   168     }

   192 

   169     bool equals = java_lang_String::equals(_find(), val_oop);

   193   // No need to lookup the shared table from here since the caller (intern()) already did

   170     if (!equals) {

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

   171       return false;

   195   if (test != NULL) {

   172     }

   196     // Entry already added

   173     // Need to resolve weak handle and Handleize through possible safepoint.

   197     return test;

   174     _found = Handle(_thread, value->resolve());

   198   }

   175     return true;

   199 

   176   }

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

   177 };

   201   add_entry(index, entry);

   178 

   202   return string();

   179 static size_t ceil_pow_2(uintx val) {

   203 }

   180   size_t ret;

   204 

   181   for (ret = 1; ((size_t)1 << ret) < val; ++ret);

   205 

   182   return ret;

   183 }

   184 

   185 StringTable::StringTable() : _local_table(NULL), _current_size(0), _has_work(0),

   186   _needs_rehashing(false), _weak_handles(NULL), _items(0), _uncleaned_items(0) {

   187   _weak_handles = new OopStorage("StringTable weak",

   188                                  StringTableWeakAlloc_lock,

   189                                  StringTableWeakActive_lock);

   190   size_t start_size_log_2 = ceil_pow_2(StringTableSize);

   191   _current_size = ((size_t)1) << start_size_log_2;

   192   log_trace(stringtable)("Start size: " SIZE_FORMAT " (" SIZE_FORMAT ")",

   193                          _current_size, start_size_log_2);

   194   _local_table = new StringTableHash(start_size_log_2, END_SIZE, REHASH_LEN);

   195 }

   196 

   197 size_t StringTable::item_added() {

   198   return Atomic::add((size_t)1, &(the_table()->_items));

   199 }

   200 

   201 size_t StringTable::items_to_clean(size_t ncl) {

   202   size_t total = Atomic::add((size_t)ncl, &(the_table()->_uncleaned_items));

   203   log_trace(stringtable)(

   204      "Uncleaned items:" SIZE_FORMAT " added: " SIZE_FORMAT " total:" SIZE_FORMAT,

   205      the_table()->_uncleaned_items, ncl, total);

   206   return total;

   207 }

   208 

   209 void StringTable::item_removed() {

   210   Atomic::add((size_t)-1, &(the_table()->_items));

   211   Atomic::add((size_t)-1, &(the_table()->_uncleaned_items));

   212 }

   213 

   214 double StringTable::get_load_factor() {

   215   return (_items*1.0)/_current_size;

   216 }

   217 

   218 double StringTable::get_dead_factor() {

   219   return (_uncleaned_items*1.0)/_current_size;

   220 }

   221 

   222 size_t StringTable::table_size(Thread* thread) {

   223   return ((size_t)(1)) << _local_table->get_size_log2(thread != NULL ? thread

   224                                                       : Thread::current());

   225 }

   226 

   227 void StringTable::trigger_concurrent_work() {

   228   MutexLockerEx ml(Service_lock, Mutex::_no_safepoint_check_flag);

   229   the_table()->_has_work = true;

   230   Service_lock->notify_all();

   231 }

   232 

   233 // Probing

   216   oop string = lookup_shared(name, len, hash);

   243   oop string = StringTable::the_table()->lookup_shared(name, len, hash);

   220   if (use_alternate_hashcode()) {

   247   if (StringTable::_alt_hash) {

   221     hash = alt_hash_string(name, len);

   248     hash = hash_string(name, len, true);

   222   }

   249   }

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

   250   return StringTable::the_table()->do_lookup(name, len, hash);

   224   string = the_table()->lookup_in_main_table(index, name, len, hash);

   251 }

   225 

   252 

   226   return string;

   253 class StringTableGet : public StackObj {

   227 }

   254   Thread* _thread;

   228 

   255   Handle  _return;

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

   256  public:

   230                         int len, TRAPS) {

   257   StringTableGet(Thread* thread) : _thread(thread) {}

   231   // shared table always uses java_lang_String::hash_code

   258   void operator()(WeakHandle<vm_string_table_data>* val) {

   232   unsigned int hashValue = java_lang_String::hash_code(name, len);

   259     oop result = val->resolve();

   233   oop found_string = lookup_shared(name, len, hashValue);

   260     assert(result != NULL, "Result should be reachable");

   234   if (found_string != NULL) {

   261     _return = Handle(_thread, result);

   235     return found_string;

   262   }

   236   }

   263   oop get_res_oop() {

   237   if (use_alternate_hashcode()) {

   264     return _return();

   238     hashValue = alt_hash_string(name, len);

   265   }

   239   }

   266 };

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

   267 

   241   found_string = the_table()->lookup_in_main_table(index, name, len, hashValue);

   268 oop StringTable::do_lookup(jchar* name, int len, uintx hash) {

   242 

   269   Thread* thread = Thread::current();

   243   // Found

   270   StringTableLookupJchar lookup(thread, hash, name, len);

   244   if (found_string != NULL) {

   271   StringTableGet stg(thread);

   245     return found_string;

   272   bool rehash_warning;

   246   }

   273   _local_table->get(thread, lookup, stg, &rehash_warning);

   247 

   274   if (rehash_warning) {

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

   275     _needs_rehashing = true;

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

   276   }

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

   277   return stg.get_res_oop();

   251 

   278 }

   252   HandleMark hm(THREAD);  // cleanup strings created

   279 

   253   Handle string;

   280 // Interning

   254   // try to reuse the string if possible

   255   if (!string_or_null.is_null()) {

   256     string = string_or_null;

   257   } else {

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

   259   }

   260 

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

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

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

   264   Universe::heap()->deduplicate_string(string());

   265 

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

   267   // change at safepoint.

   268   oop added_or_found;

   269   {

   270     MutexLocker ml(StringTable_lock, THREAD);

   271     // Otherwise, add to symbol to table

   272     added_or_found = the_table()->basic_add(index, string, name, len,

   273                                   hashValue, CHECK_NULL);

   274   }

   275 

   276   return added_or_found;

   277 }

   278 

   289 

   291 oop StringTable::intern(oop string, TRAPS) {

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

   291 {

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

   296   jchar* chars = java_lang_String::as_unicode_string(string, length,

   297                                                      CHECK_NULL);

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

   313 oop StringTable::intern(Handle string_or_null_h, jchar* name, int len, TRAPS) {

   314   BucketUnlinkContext context;

   314   // shared table always uses java_lang_String::hash_code

   315   buckets_unlink_or_oops_do(is_alive, f, 0, the_table()->table_size(), &context);

   315   unsigned int hash = java_lang_String::hash_code(name, len);

   316   _the_table->bulk_free_entries(&context);

   316   oop found_string = StringTable::the_table()->lookup_shared(name, len, hash);

   317   *processed = context._num_processed;

   317   if (found_string != NULL) {

   318   *removed = context._num_removed;

   318     return found_string;

   319 }

   319   }

   320 

   320   if (StringTable::_alt_hash) {

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

   321     hash = hash_string(name, len, true);

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

   322   }

   323   // entries at a safepoint.

   323   return StringTable::the_table()->do_intern(string_or_null_h, name, len,

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

   324                                              hash, CHECK_NULL);

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

   325 }

   326 

   326 

   327   BucketUnlinkContext context;

   327 class StringTableCreateEntry : public StackObj {

   328   for (;;) {

   328  private:

   329     // Grab next set of buckets to scan

   329    Thread* _thread;

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

   330    Handle  _return;

   331     if (start_idx >= limit) {

   331    Handle  _store;

   332       // End of table

   332  public:

   333       break;

   333   StringTableCreateEntry(Thread* thread, Handle store)

   334     }

   334     : _thread(thread), _store(store) {}

   335 

   335 

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

   336   WeakHandle<vm_string_table_data> operator()() { // No dups found

   337     buckets_unlink_or_oops_do(is_alive, f, start_idx, end_idx, &context);

   337     WeakHandle<vm_string_table_data> wh =

   338   }

   338       WeakHandle<vm_string_table_data>::create(_store);

   339   _the_table->bulk_free_entries(&context);

   339     return wh;

   340   *processed = context._num_processed;

   340   }

   341   *removed = context._num_removed;

   341   void operator()(bool inserted, WeakHandle<vm_string_table_data>* val) {

   342 }

   342     oop result = val->resolve();

   343 

   343     assert(result != NULL, "Result should be reachable");

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

   344     _return = Handle(_thread, result);

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

   345   }

   346 

   346   oop get_return() const {

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

   347     return _return();

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

   348   }

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

   349 };

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

   350 

   351   assert(start_idx <= end_idx,

   351 oop StringTable::do_intern(Handle string_or_null_h, jchar* name,

   352          "Index ordering: start_idx=%d, end_idx=%d",

   352                            int len, uintx hash, TRAPS) {

   353          start_idx, end_idx);

   353   HandleMark hm(THREAD);  // cleanup strings created

   354 

   354   Handle string_h;

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

   355 

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

   356   if (!string_or_null_h.is_null()) {

   357     while (entry != NULL) {

   357     string_h = string_or_null_h;

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

   358   } else {

   359 

   359     string_h = java_lang_String::create_from_unicode(name, len, CHECK_NULL);

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

   360   }

   361 

   361 

   362       entry = entry->next();

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

   363     }

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

   364   }

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

   365 }

   365   Universe::heap()->deduplicate_string(string_h());

   366 

   366 

   367 void StringTable::buckets_unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f, int start_idx, int end_idx, BucketUnlinkContext* context) {

   367   assert(java_lang_String::equals(string_h(), name, len),

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

   368          "string must be properly initialized");

   369 

   369   assert(len == java_lang_String::length(string_h()), "Must be same length");

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

   370   StringTableLookupOop lookup(THREAD, hash, string_h);

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

   371   StringTableCreateEntry stc(THREAD, string_h);

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

   372 

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

   373   bool rehash_warning;

   374   assert(start_idx <= end_idx,

   374   _local_table->get_insert_lazy(THREAD, lookup, stc, stc, &rehash_warning);

   375          "Index ordering: start_idx=%d, end_idx=%d",

   375   if (rehash_warning) {

   376          start_idx, end_idx);

   376     _needs_rehashing = true;

   377 

   377   }

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

   378   return stc.get_return();

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

   379 }

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

   380 

   381     while (entry != NULL) {

   381 // GC support

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

   382 class StringTableIsAliveCounter : public BoolObjectClosure {

   383 

   383   BoolObjectClosure* _real_boc;

   384       if (is_alive->do_object_b(string_object_no_keepalive(entry))) {

   384  public:

   385         if (f != NULL) {

   385   size_t _count;

   386           f->do_oop(entry->literal_addr());

   386   size_t _count_total;

   387         }

   387   StringTableIsAliveCounter(BoolObjectClosure* boc) : _real_boc(boc), _count(0),

   388         p = entry->next_addr();

   388                                                       _count_total(0) {}

   389   bool do_object_b(oop obj) {

   390     bool ret = _real_boc->do_object_b(obj);

   391     if (!ret) {

   392       ++_count;

   393     }

   394     ++_count_total;

   395     return ret;

   396   }

   397 };

   398 

   399 void StringTable::unlink_or_oops_do(BoolObjectClosure* is_alive, OopClosure* f,

   400                                     int* processed, int* removed) {

   401   DoNothingClosure dnc;

   402   assert(is_alive != NULL, "No closure");

   403   StringTableIsAliveCounter stiac(is_alive);

   404   OopClosure* tmp = f != NULL ? f : &dnc;

   405 

   406   StringTable::the_table()->_weak_handles->weak_oops_do(&stiac, tmp);

   407 

   408   StringTable::the_table()->items_to_clean(stiac._count);

   409   StringTable::the_table()->check_concurrent_work();

   410   if (processed != NULL) {

   411     *processed = (int) stiac._count_total;

   412   }

   413   if (removed != NULL) {

   414     *removed = (int) stiac._count;

   415   }

   416 }

   417 

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

   419   assert(f != NULL, "No closure");

   420   StringTable::the_table()->_weak_handles->oops_do(f);

   421 }

   422 

   423 void StringTable::possibly_parallel_unlink(

   424    OopStorage::ParState<false, false>* _par_state_string, BoolObjectClosure* cl,

   425    int* processed, int* removed)

   426 {

   427   DoNothingClosure dnc;

   428   assert(cl != NULL, "No closure");

   429   StringTableIsAliveCounter stiac(cl);

   430 

   431   _par_state_string->weak_oops_do(&stiac, &dnc);

   432 

   433   StringTable::the_table()->items_to_clean(stiac._count);

   434   StringTable::the_table()->check_concurrent_work();

   435   *processed = (int) stiac._count_total;

   436   *removed = (int) stiac._count;

   437 }

   438 

   439 void StringTable::possibly_parallel_oops_do(

   440    OopStorage::ParState<false /* concurrent */, false /* const */>*

   441    _par_state_string, OopClosure* f)

   442 {

   443   assert(f != NULL, "No closure");

   444   _par_state_string->oops_do(f);

   445 }

   446 

   447 // Concurrent work

   448 void StringTable::grow(JavaThread* jt) {

   449   StringTableHash::GrowTask gt(_local_table);

   450   if (!gt.prepare(jt)) {

   451     return;

   452   }

   453   log_trace(stringtable)("Started to grow");

   454   {

   455     TraceTime timer("Grow", TRACETIME_LOG(Debug, stringtable, perf));

   456     while (gt.doTask(jt)) {

   457       gt.pause(jt);

   458       {

   459         ThreadBlockInVM tbivm(jt);

   460       }

   461       gt.cont(jt);

   462     }

   463   }

   464   gt.done(jt);

   465   _current_size = table_size(jt);

   466   log_debug(stringtable)("Grown to size:" SIZE_FORMAT, _current_size);

   467 }

   468 

   469 struct StringTableDoDelete : StackObj {

   470   long _count;

   471   StringTableDoDelete() : _count(0) {}

   472   void operator()(WeakHandle<vm_string_table_data>* val) {

   473     ++_count;

   474   }

   475 };

   476 

   477 struct StringTableDeleteCheck : StackObj {

   478   long _count;

   479   long _item;

   480   StringTableDeleteCheck() : _count(0), _item(0) {}

   481   bool operator()(WeakHandle<vm_string_table_data>* val) {

   482     ++_item;

   483     oop tmp = val->peek();

   484     if (tmp == NULL) {

   485       ++_count;

   486       return true;

   487     } else {

   488       return false;

   489     }

   490   }

   491 };

   492 

   493 void StringTable::clean_dead_entries(JavaThread* jt) {

   494   StringTableHash::BulkDeleteTask bdt(_local_table);

   495   if (!bdt.prepare(jt)) {

   496     return;

   497   }

   498 

   499   StringTableDeleteCheck stdc;

   500   StringTableDoDelete stdd;

   501   bool interrupted = false;

   502   {

   503     TraceTime timer("Clean", TRACETIME_LOG(Debug, stringtable, perf));

   504     while(bdt.doTask(jt, stdc, stdd)) {

   505       bdt.pause(jt);

   506       {

   507         ThreadBlockInVM tbivm(jt);

   508       }

   509       if (!bdt.cont(jt)) {

   510         interrupted = true;

   511         break;

   512       }

   513     }

   514   }

   515   if (interrupted) {

   516     _has_work = true;

   517   } else {

   518     bdt.done(jt);

   519   }

   520   log_debug(stringtable)("Cleaned %ld of %ld", stdc._count, stdc._item);

   521 }

   522 

   523 void StringTable::check_concurrent_work() {

   524   if (_has_work) {

   525     return;

   526   }

   527   double load_factor = StringTable::get_load_factor();

   528   double dead_factor = StringTable::get_dead_factor();

   529   // We should clean/resize if we have more dead than alive,

   530   // more items than preferred load factor or

   531   // more dead items than water mark.

   532   if ((dead_factor > load_factor) ||

   533       (load_factor > PREF_AVG_LIST_LEN) ||

   534       (dead_factor > CLEAN_DEAD_HIGH_WATER_MARK)) {

   535     log_debug(stringtable)("Concurrent work triggered, live factor:%g dead factor:%g",

   536                            load_factor, dead_factor);

   537     trigger_concurrent_work();

   538   }

   539 }

   540 

   541 void StringTable::concurrent_work(JavaThread* jt) {

   542   _has_work = false;

   543   double load_factor = get_load_factor();

   544   log_debug(stringtable, perf)("Concurrent work, live factor: %g", load_factor);

   545   // We prefer growing, since that also removes dead items

   546   if (load_factor > PREF_AVG_LIST_LEN && !_local_table->is_max_size_reached()) {

   547     grow(jt);

   548   } else {

   549     clean_dead_entries(jt);

   550   }

   551 }

   552 

   553 void StringTable::do_concurrent_work(JavaThread* jt) {

   554   StringTable::the_table()->concurrent_work(jt);

   555 }

   556 

   557 // Rehash

   558 bool StringTable::do_rehash() {

   559   if (!_local_table->is_safepoint_safe()) {

   560     return false;

   561   }

   562 

   563   // We use max size

   564   StringTableHash* new_table = new StringTableHash(END_SIZE, END_SIZE, REHASH_LEN);

   565   // Use alt hash from now on

   566   _alt_hash = true;

   567   if (!_local_table->try_move_nodes_to(Thread::current(), new_table)) {

   568     _alt_hash = false;

   569     delete new_table;

   570     return false;

   571   }

   572 

   573   // free old table

   574   delete _local_table;

   575   _local_table = new_table;

   576 

   577   return true;

   578 }

   579 

   580 void StringTable::try_rehash_table() {

   581   static bool rehashed = false;

   582   log_debug(stringtable)("Table imbalanced, rehashing called.");

   583 

   584   // Grow instead of rehash.

   585   if (get_load_factor() > PREF_AVG_LIST_LEN &&

   586       !_local_table->is_max_size_reached()) {

   587     log_debug(stringtable)("Choosing growing over rehashing.");

   588     trigger_concurrent_work();

   589     _needs_rehashing = false;

   590     return;

   591   }

   592   // Already rehashed.

   593   if (rehashed) {

   594     log_warning(stringtable)("Rehashing already done, still long lists.");

   595     trigger_concurrent_work();

   596     _needs_rehashing = false;

   597     return;

   598   }

   599 

   600   murmur_seed = AltHashing::compute_seed();

   601   {

   602     if (do_rehash()) {

   603       rehashed = true;

   604     } else {

   605       log_info(stringtable)("Resizes in progress rehashing skipped.");

   606     }

   607   }

   608   _needs_rehashing = false;

   609 }

   610 

   611 void StringTable::rehash_table() {

   612   StringTable::the_table()->try_rehash_table();

   613 }

   614 

   615 // Statistics

   616 static int literal_size(oop obj) {

   617   // NOTE: this would over-count if (pre-JDK8)

   618   // java_lang_Class::has_offset_field() is true and the String.value array is

   619   // shared by several Strings. However, starting from JDK8, the String.value

   620   // array is not shared anymore.

   621   if (obj == NULL) {

   622     return 0;

   623   } else if (obj->klass() == SystemDictionary::String_klass()) {

   624     return (obj->size() + java_lang_String::value(obj)->size()) * HeapWordSize;

   625   } else {

   626     return obj->size();

   627   }

   628 }

   629 

   630 struct SizeFunc : StackObj {

   631   size_t operator()(WeakHandle<vm_string_table_data>* val) {

   632     oop s = val->peek();

   633     if (s == NULL) {

   634       // Dead

   635       return 0;

   636     }

   637     return literal_size(s);

   638   };

   639 };

   640 

   641 void StringTable::print_table_statistics(outputStream* st,

   642                                          const char* table_name) {

   643   SizeFunc sz;

   644   _local_table->statistics_to(Thread::current(), sz, st, table_name);

   645 }

   646 

   647 // Verification

   648 class VerifyStrings : StackObj {

   649  public:

   650   bool operator()(WeakHandle<vm_string_table_data>* val) {

   651     oop s = val->peek();

   652     if (s != NULL) {

   653       assert(java_lang_String::length(s) >= 0, "Length on string must work.");

   654     }

   655     return true;

   656   };

   657 };

   658 

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

   660 void StringTable::verify() {

   661   Thread* thr = Thread::current();

   662   VerifyStrings vs;

   663   if (!the_table()->_local_table->try_scan(thr, vs)) {

   664     log_info(stringtable)("verify unavailable at this moment");

   665   }

   666 }

   667 

   668 // Verification and comp

   669 class VerifyCompStrings : StackObj {

   670   GrowableArray<oop>* _oops;

   671  public:

   672   size_t _errors;

   673   VerifyCompStrings(GrowableArray<oop>* oops) : _oops(oops), _errors(0) {}

   674   bool operator()(WeakHandle<vm_string_table_data>* val) {

   675     oop s = val->resolve();

   676     if (s == NULL) {

   677       return true;

   678     }

   679     int len = _oops->length();

   680     for (int i = 0; i < len; i++) {

   681       bool eq = java_lang_String::equals(s, _oops->at(i));

   682       assert(!eq, "Duplicate strings");

   683       if (eq) {

   684         _errors++;

   685       }

   686     }

   687     _oops->push(s);

   688     return true;

   689   };

   690 };

   691 

   692 size_t StringTable::verify_and_compare_entries() {

   693   Thread* thr = Thread::current();

   694   GrowableArray<oop>* oops =

   695     new (ResourceObj::C_HEAP, mtInternal)

   696       GrowableArray<oop>((int)the_table()->_current_size, true);

   697 

   698   VerifyCompStrings vcs(oops);

   699   if (!the_table()->_local_table->try_scan(thr, vcs)) {

   700     log_info(stringtable)("verify unavailable at this moment");

   701   }

   702   delete oops;

   703   return vcs._errors;

   704 }

   705 

   706 // Dumping

   707 class PrintString : StackObj {

   708   Thread* _thr;

   709   outputStream* _st;

   710  public:

   711   PrintString(Thread* thr, outputStream* st) : _thr(thr), _st(st) {}

   712   bool operator()(WeakHandle<vm_string_table_data>* val) {

   713     oop s = val->peek();

   714     if (s == NULL) {

   715       return true;

   716     }

   717     typeArrayOop value     = java_lang_String::value_no_keepalive(s);

   718     int          length    = java_lang_String::length(s);

   719     bool         is_latin1 = java_lang_String::is_latin1(s);

   720 

   721     if (length <= 0) {

   722       _st->print("%d: ", length);

   723     } else {

   724       ResourceMark rm(_thr);

   725       int utf8_length = length;

   726       char* utf8_string;

   727 

   728       if (!is_latin1) {

   729         jchar* chars = value->char_at_addr(0);

   730         utf8_string = UNICODE::as_utf8(chars, utf8_length);

   390         *p = entry->next();

   732         jbyte* bytes = value->byte_at_addr(0);

   391         context->free_entry(entry);

   733         utf8_string = UNICODE::as_utf8(bytes, utf8_length);

   393       context->_num_processed++;

   735 

   394       entry = *p;

   736       _st->print("%d: ", utf8_length);

   395     }

   737       HashtableTextDump::put_utf8(_st, utf8_string, utf8_length);

   396   }

   738     }

   397 }

   739     _st->cr();

   398 

   740     return true;

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

   741   };

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

   742 };

   401 }

   402 

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

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

   405 

   406   for (;;) {

   407     // Grab next set of buckets to scan

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

   409     if (start_idx >= limit) {

   410       // End of table

   411       break;

   412     }

   413 

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

   415     buckets_oops_do(f, start_idx, end_idx);

   416   }

   417 }

   418 

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

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

   421 void StringTable::verify() {

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

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

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

   425       oop s = string_object_no_keepalive(p);

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

   427       unsigned int h = hash_string(s);

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

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

   430                 "wrong index in string table");

   431     }

   432   }

   433 }

   437     the_table()->print_table_statistics(st, "StringTable", string_object_no_keepalive);

   746     the_table()->print_table_statistics(st, "StringTable");

   439     Thread* THREAD = Thread::current();

   748     Thread* thr = Thread::current();

   749     ResourceMark rm(thr);

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

   751     PrintString ps(thr, st);

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

   752     if (!the_table()->_local_table->try_scan(thr, ps)) {

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

   753       st->print_cr("dump unavailable at this moment");

   444         oop s = string_object_no_keepalive(p);

   754     }

   445         typeArrayOop value     = java_lang_String::value_no_keepalive(s);

   755   }

   446         int          length    = java_lang_String::length(s);

   447         bool         is_latin1 = java_lang_String::is_latin1(s);

   448 

   449         if (length <= 0) {

   450           st->print("%d: ", length);

   451         } else {

   452           ResourceMark rm(THREAD);

   453           int utf8_length = length;

   454           char* utf8_string;

   455 

   456           if (!is_latin1) {

   457             jchar* chars = value->char_at_addr(0);

   458             utf8_string = UNICODE::as_utf8(chars, utf8_length);

   459           } else {

   460             jbyte* bytes = value->byte_at_addr(0);

   461             utf8_string = UNICODE::as_utf8(bytes, utf8_length);

   462           }

   463 

   464           st->print("%d: ", utf8_length);

   465           HashtableTextDump::put_utf8(st, utf8_string, utf8_length);

   466         }

   467         st->cr();

   468       }

   469     }

   470   }

   471 }

   472 

   473 StringTable::VerifyRetTypes StringTable::compare_entries(

   474                                       int bkt1, int e_cnt1,

   475                                       HashtableEntry<oop, mtSymbol>* e_ptr1,

   476                                       int bkt2, int e_cnt2,

   477                                       HashtableEntry<oop, mtSymbol>* e_ptr2) {

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

   479   // before this function is called.

   480   oop str1 = string_object_no_keepalive(e_ptr1);

   481   oop str2 = string_object_no_keepalive(e_ptr2);

   482 

   483   if (str1 == str2) {

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

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

   486                   p2i(str1), bkt1, e_cnt1, bkt2, e_cnt2);

   487     return _verify_fail_continue;

   488   }

   489 

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

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

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

   493                   bkt1, e_cnt1, bkt2, e_cnt2);

   494     return _verify_fail_continue;

   495   }

   496 

   497   return _verify_pass;

   498 }

   499 

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

   501                                                       HashtableEntry<oop, mtSymbol>* e_ptr,

   502                                                       StringTable::VerifyMesgModes mesg_mode) {

   503 

   504   VerifyRetTypes ret = _verify_pass;  // be optimistic

   505 

   506   oop str = string_object_no_keepalive(e_ptr);

   507   if (str == NULL) {

   508     if (mesg_mode == _verify_with_mesgs) {

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

   510                     e_cnt);

   511     }

   512     // NULL oop means no more verifications are possible

   513     return _verify_fail_done;

   514   }

   515 

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

   517     if (mesg_mode == _verify_with_mesgs) {

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

   519                     bkt, e_cnt);

   520     }

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

   522     return _verify_fail_done;

   523   }

   524 

   525   unsigned int h = hash_string(str);

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

   527     if (mesg_mode == _verify_with_mesgs) {

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

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

   530     }

   531     ret = _verify_fail_continue;

   532   }

   533 

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

   535     if (mesg_mode == _verify_with_mesgs) {

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

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

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

   539     }

   540     ret = _verify_fail_continue;

   541   }

   542 

   543   return ret;

   544 }

   545 

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

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

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

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

   550 //

   551 // StringTable::verify_entry() checks:

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

   553 // - oop value is a String

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

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

   556 //

   557 // StringTable::compare_entries() checks:

   558 // - oops are unique across all entries

   559 // - String values are unique across all entries

   560 //

   561 int StringTable::verify_and_compare_entries() {

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

   563 

   564   int  fail_cnt = 0;

   565 

   566   // first, verify all the entries individually:

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

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

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

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

   571       if (ret != _verify_pass) {

   572         fail_cnt++;

   573       }

   574     }

   575   }

   576 

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

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

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

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

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

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

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

   584   bool need_entry_verify = (fail_cnt != 0);

   585 

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

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

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

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

   590       if (need_entry_verify) {

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

   592                                           _verify_quietly);

   593         if (ret == _verify_fail_done) {

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

   595           continue;

   596         }

   597       }

   598 

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

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

   601         int e_cnt2;

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

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

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

   605             // we're comparing against

   606             continue;

   607           }

   608 

   609           if (need_entry_verify) {

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

   611                                               _verify_quietly);

   612             if (ret == _verify_fail_done) {

   613               // cannot compare against this entry

   614               continue;

   615             }

   616           }

   617 

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

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

   620               != _verify_pass) {

   621             fail_cnt++;

   622           }

   623         }

   624       }

   625     }

   626   }

   627   return fail_cnt;

   628 }

   629 

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

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

   632 void StringTable::rehash_table() {

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

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

   635   if (DumpSharedSpaces) return;

   636   StringTable* new_table = new StringTable();

   637 

   638   // Rehash the table

   639   the_table()->move_to(new_table);

   640 

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

   642   delete _the_table;

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

   644   // Then rehash with a new global seed.

   645   _needs_rehashing = false;

   646   _the_table = new_table;

   675 // Sharing

   785 oop StringTable::lookup_shared(jchar* name, int len, unsigned int hash) {

   786   assert(hash == java_lang_String::hash_code(name, len),

   787          "hash must be computed using java_lang_String::hash_code");

   788   return _shared_table.lookup((const char*)name, hash, len);

   789 }

   790 

   681   typeArrayOop new_v = (typeArrayOop)MetaspaceShared::archive_heap_object(v, THREAD);

   796   typeArrayOop new_v =

   797     (typeArrayOop)MetaspaceShared::archive_heap_object(v, THREAD);

   695 bool StringTable::copy_shared_string(GrowableArray<MemRegion> *string_space,

   811 struct CopyToArchive : StackObj {

   696                                      CompactStringTableWriter* writer) {

   812   CompactStringTableWriter* _writer;

   813   CopyToArchive(CompactStringTableWriter* writer) : _writer(writer) {}

   814   bool operator()(WeakHandle<vm_string_table_data>* val) {

   815     oop s = val->peek();

   816     if (s == NULL) {

   817       return true;

   818     }

   819     unsigned int hash = java_lang_String::hash_code(s);

   820     if (hash == 0) {

   821       return true;

   822     }

   823 

   824     java_lang_String::set_hash(s, hash);

   825     oop new_s = StringTable::create_archived_string(s, Thread::current());

   826     if (new_s == NULL) {

   827       return true;

   828     }

   829 

   830     val->replace(new_s);

   831     // add to the compact table

   832     _writer->add(hash, new_s);

   833     return true;

   834   }

   835 };

   836 

   837 void StringTable::copy_shared_string_table(CompactStringTableWriter* writer) {

   699   Thread* THREAD = Thread::current();

   840   CopyToArchive copy(writer);

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

   841   StringTable::the_table()->_local_table->do_scan(Thread::current(), copy);

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

   842 }

   702     for ( ; bucket != NULL; bucket = bucket->next()) {

   843 

   703       oop s = string_object_no_keepalive(bucket);

   844 void StringTable::write_to_archive() {

   704       unsigned int hash = java_lang_String::hash_code(s);

   705       if (hash == 0) {

   706         continue;

   707       }

   708 

   709       java_lang_String::set_hash(s, hash);

   710       oop new_s = create_archived_string(s, THREAD);

   711       if (new_s == NULL) {

   712         continue;

   713       }

   714 

   715       // set the archived string in bucket

   716       set_string_object(bucket, new_s);

   717 

   718       // add to the compact table

   719       writer->add(hash, new_s);

   720     }

   721   }

   722 

   723   return true;

   724 }

   725 

   726 void StringTable::write_to_archive(GrowableArray<MemRegion> *string_space) {

   730   int num_buckets = the_table()->number_of_entries() /

   848   int num_buckets = the_table()->_items / SharedSymbolTableBucketSize;

   731                          SharedSymbolTableBucketSize;

   737   if (copy_shared_string(string_space, &writer)) {

   854   copy_shared_string_table(&writer);

   738     writer.dump(&_shared_table);

   855   writer.dump(&_shared_table);

   739   }