jdk8-mips64-public/hotspot: src/share/vm/gc_implementation/g1/g1StringDedupTable.cpp@e7d0505c8a30 (annotated)

src/share/vm/gc_implementation/g1/g1StringDedupTable.cpp@e7d0505c8a30 (annotated)

src/share/vm/gc_implementation/g1/g1StringDedupTable.cpp

Fri, 10 Oct 2014 15:51:58 +0200

author: tschatzl
date: Fri, 10 Oct 2014 15:51:58 +0200
changeset 7257: e7d0505c8a30
parent 0: f90c822e73f8
child 8452: 04a62a3d51d7
permissions: -rw-r--r--

8059758: Footprint regressions with JDK-8038423
Summary: Changes in JDK-8038423 always initialize (zero out) virtual memory used for auxiliary data structures. This causes a footprint regression for G1 in startup benchmarks. This is because they do not touch that memory at all, so the operating system does not actually commit these pages. The fix is to, if the initialization value of the data structures matches the default value of just committed memory (=0), do not do anything.
Reviewed-by: jwilhelm, brutisso

 /*
  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
  *
  * This code is free software; you can redistribute it and/or modify it
  * under the terms of the GNU General Public License version 2 only, as
  * published by the Free Software Foundation.
  *
  * This code is distributed in the hope that it will be useful, but WITHOUT
  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  * version 2 for more details (a copy is included in the LICENSE file that
  * accompanied this code).
  *
  * You should have received a copy of the GNU General Public License version
  * 2 along with this work; if not, write to the Free Software Foundation,
  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  *
  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  * or visit www.oracle.com if you need additional information or have any
  * questions.
  *
  */
 #include "precompiled.hpp"
 #include "classfile/altHashing.hpp"
 #include "classfile/javaClasses.hpp"
 #include "gc_implementation/g1/g1CollectedHeap.inline.hpp"
 #include "gc_implementation/g1/g1SATBCardTableModRefBS.hpp"
 #include "gc_implementation/g1/g1StringDedupTable.hpp"
 #include "memory/gcLocker.hpp"
 #include "memory/padded.inline.hpp"
 #include "oops/typeArrayOop.hpp"
 #include "runtime/mutexLocker.hpp"
 //
 // Freelist in the deduplication table entry cache. Links table
 // entries together using their _next fields.
 //
 class G1StringDedupEntryFreeList : public CHeapObj<mtGC> {
 private:
   G1StringDedupEntry* _list;
   size_t              _length;
 public:
   G1StringDedupEntryFreeList() :
     _list(NULL),
     _length(0) {
   }
   void add(G1StringDedupEntry* entry) {
     entry->set_next(_list);
     _list = entry;
     _length++;
   }
   G1StringDedupEntry* remove() {
     G1StringDedupEntry* entry = _list;
     if (entry != NULL) {
       _list = entry->next();
       _length--;
     }
     return entry;
   }
   size_t length() {
     return _length;
   }
 };
 //
 // Cache of deduplication table entries. This cache provides fast allocation and
 // reuse of table entries to lower the pressure on the underlying allocator.
 // But more importantly, it provides fast/deferred freeing of table entries. This
 // is important because freeing of table entries is done during stop-the-world
 // phases and it is not uncommon for large number of entries to be freed at once.
 // Tables entries that are freed during these phases are placed onto a freelist in
 // the cache. The deduplication thread, which executes in a concurrent phase, will
 // later reuse or free the underlying memory for these entries.
 //
 // The cache allows for single-threaded allocations and multi-threaded frees.
 // Allocations are synchronized by StringDedupTable_lock as part of a table
 // modification.
 //
 class G1StringDedupEntryCache : public CHeapObj<mtGC> {
 private:
   // One freelist per GC worker to allow lock less freeing of
   // entries while doing a parallel scan of the table. Using
   // PaddedEnd to avoid false sharing.
   PaddedEnd<G1StringDedupEntryFreeList>* _lists;
   size_t                                 _nlists;
 public:
   G1StringDedupEntryCache();
   ~G1StringDedupEntryCache();
   // Get a table entry from the cache freelist, or allocate a new
   // entry if the cache is empty.
   G1StringDedupEntry* alloc();
   // Insert a table entry into the cache freelist.
   void free(G1StringDedupEntry* entry, uint worker_id);
   // Returns current number of entries in the cache.
   size_t size();
   // If the cache has grown above the given max size, trim it down
   // and deallocate the memory occupied by trimmed of entries.
   void trim(size_t max_size);
 };
 G1StringDedupEntryCache::G1StringDedupEntryCache() {
   _nlists = MAX2(ParallelGCThreads, (size_t)1);
   _lists = PaddedArray<G1StringDedupEntryFreeList, mtGC>::create_unfreeable((uint)_nlists);
 }
 G1StringDedupEntryCache::~G1StringDedupEntryCache() {
   ShouldNotReachHere();
 }
 G1StringDedupEntry* G1StringDedupEntryCache::alloc() {
   for (size_t i = 0; i < _nlists; i++) {
     G1StringDedupEntry* entry = _lists[i].remove();
     if (entry != NULL) {
       return entry;
     }
   }
   return new G1StringDedupEntry();
 }
 void G1StringDedupEntryCache::free(G1StringDedupEntry* entry, uint worker_id) {
   assert(entry->obj() != NULL, "Double free");
   assert(worker_id < _nlists, "Invalid worker id");
   entry->set_obj(NULL);
   entry->set_hash(0);
   _lists[worker_id].add(entry);
 }
 size_t G1StringDedupEntryCache::size() {
   size_t size = 0;
   for (size_t i = 0; i < _nlists; i++) {
     size += _lists[i].length();
   }
   return size;
 }
 void G1StringDedupEntryCache::trim(size_t max_size) {
   size_t cache_size = 0;
   for (size_t i = 0; i < _nlists; i++) {
     G1StringDedupEntryFreeList* list = &_lists[i];
     cache_size += list->length();
     while (cache_size > max_size) {
       G1StringDedupEntry* entry = list->remove();
       assert(entry != NULL, "Should not be null");
       cache_size--;
       delete entry;
     }
   }
 }
 G1StringDedupTable*      G1StringDedupTable::_table = NULL;
 G1StringDedupEntryCache* G1StringDedupTable::_entry_cache = NULL;
 const size_t             G1StringDedupTable::_min_size = (1 << 10);   // 1024
 const size_t             G1StringDedupTable::_max_size = (1 << 24);   // 16777216
 const double             G1StringDedupTable::_grow_load_factor = 2.0; // Grow table at 200% load
 const double             G1StringDedupTable::_shrink_load_factor = _grow_load_factor / 3.0; // Shrink table at 67% load
 const double             G1StringDedupTable::_max_cache_factor = 0.1; // Cache a maximum of 10% of the table size
 const uintx              G1StringDedupTable::_rehash_multiple = 60;   // Hash bucket has 60 times more collisions than expected
 const uintx              G1StringDedupTable::_rehash_threshold = (uintx)(_rehash_multiple * _grow_load_factor);
 uintx                    G1StringDedupTable::_entries_added = 0;
 uintx                    G1StringDedupTable::_entries_removed = 0;
 uintx                    G1StringDedupTable::_resize_count = 0;
 uintx                    G1StringDedupTable::_rehash_count = 0;
 G1StringDedupTable::G1StringDedupTable(size_t size, jint hash_seed) :
   _size(size),
   _entries(0),
   _grow_threshold((uintx)(size * _grow_load_factor)),
   _shrink_threshold((uintx)(size * _shrink_load_factor)),
   _rehash_needed(false),
   _hash_seed(hash_seed) {
   assert(is_power_of_2(size), "Table size must be a power of 2");
   _buckets = NEW_C_HEAP_ARRAY(G1StringDedupEntry*, _size, mtGC);
   memset(_buckets, 0, _size * sizeof(G1StringDedupEntry*));
 }
 G1StringDedupTable::~G1StringDedupTable() {
   FREE_C_HEAP_ARRAY(G1StringDedupEntry*, _buckets, mtGC);
 }
 void G1StringDedupTable::create() {
   assert(_table == NULL, "One string deduplication table allowed");
   _entry_cache = new G1StringDedupEntryCache();
   _table = new G1StringDedupTable(_min_size);
 }
 void G1StringDedupTable::add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list) {
   G1StringDedupEntry* entry = _entry_cache->alloc();
   entry->set_obj(value);
   entry->set_hash(hash);
   entry->set_next(*list);
   *list = entry;
   _entries++;
 }
 void G1StringDedupTable::remove(G1StringDedupEntry** pentry, uint worker_id) {
   G1StringDedupEntry* entry = *pentry;
   *pentry = entry->next();
   _entry_cache->free(entry, worker_id);
 }
 void G1StringDedupTable::transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest) {
   G1StringDedupEntry* entry = *pentry;
   *pentry = entry->next();
   unsigned int hash = entry->hash();
   size_t index = dest->hash_to_index(hash);
   G1StringDedupEntry** list = dest->bucket(index);
   entry->set_next(*list);
   *list = entry;
 }
 bool G1StringDedupTable::equals(typeArrayOop value1, typeArrayOop value2) {
   return (value1 == value2 ||
           (value1->length() == value2->length() &&
            (!memcmp(value1->base(T_CHAR),
                     value2->base(T_CHAR),
                     value1->length() * sizeof(jchar)))));
 }
 typeArrayOop G1StringDedupTable::lookup(typeArrayOop value, unsigned int hash,
                                         G1StringDedupEntry** list, uintx &count) {
   for (G1StringDedupEntry* entry = *list; entry != NULL; entry = entry->next()) {
     if (entry->hash() == hash) {
       typeArrayOop existing_value = entry->obj();
       if (equals(value, existing_value)) {
         // Match found
         return existing_value;
       }
     }
     count++;
   }
   // Not found
   return NULL;
 }
 typeArrayOop G1StringDedupTable::lookup_or_add_inner(typeArrayOop value, unsigned int hash) {
   size_t index = hash_to_index(hash);
   G1StringDedupEntry** list = bucket(index);
   uintx count = 0;
   // Lookup in list
   typeArrayOop existing_value = lookup(value, hash, list, count);
   // Check if rehash is needed
   if (count > _rehash_threshold) {
     _rehash_needed = true;
   }
   if (existing_value == NULL) {
     // Not found, add new entry
     add(value, hash, list);
     // Update statistics
     _entries_added++;
   }
   return existing_value;
 }
 unsigned int G1StringDedupTable::hash_code(typeArrayOop value) {
   unsigned int hash;
   int length = value->length();
   const jchar* data = (jchar*)value->base(T_CHAR);
   if (use_java_hash()) {
     hash = java_lang_String::hash_code(data, length);
   } else {
     hash = AltHashing::murmur3_32(_table->_hash_seed, data, length);
   }
   return hash;
 }
 void G1StringDedupTable::deduplicate(oop java_string, G1StringDedupStat& stat) {
   assert(java_lang_String::is_instance(java_string), "Must be a string");
   No_Safepoint_Verifier nsv;
   stat.inc_inspected();
   typeArrayOop value = java_lang_String::value(java_string);
   if (value == NULL) {
     // String has no value
     stat.inc_skipped();
     return;
   }
   unsigned int hash = 0;
   if (use_java_hash()) {
     // Get hash code from cache
     hash = java_lang_String::hash(java_string);
   }
   if (hash == 0) {
     // Compute hash
     hash = hash_code(value);
     stat.inc_hashed();
   }
   if (use_java_hash() && hash != 0) {
     // Store hash code in cache
     java_lang_String::set_hash(java_string, hash);
   }
   typeArrayOop existing_value = lookup_or_add(value, hash);
   if (existing_value == value) {
     // Same value, already known
     stat.inc_known();
     return;
   }
   // Get size of value array
   uintx size_in_bytes = value->size() * HeapWordSize;
   stat.inc_new(size_in_bytes);
   if (existing_value != NULL) {
     // Enqueue the reference to make sure it is kept alive. Concurrent mark might
     // otherwise declare it dead if there are no other strong references to this object.
     G1SATBCardTableModRefBS::enqueue(existing_value);
     // Existing value found, deduplicate string
     java_lang_String::set_value(java_string, existing_value);
     if (G1CollectedHeap::heap()->is_in_young(value)) {
       stat.inc_deduped_young(size_in_bytes);
     } else {
       stat.inc_deduped_old(size_in_bytes);
     }
   }
 }
 G1StringDedupTable* G1StringDedupTable::prepare_resize() {
   size_t size = _table->_size;
   // Check if the hashtable needs to be resized
   if (_table->_entries > _table->_grow_threshold) {
     // Grow table, double the size
     size *= 2;
     if (size > _max_size) {
       // Too big, don't resize
       return NULL;
     }
   } else if (_table->_entries < _table->_shrink_threshold) {
     // Shrink table, half the size
     size /= 2;
     if (size < _min_size) {
       // Too small, don't resize
       return NULL;
     }
   } else if (StringDeduplicationResizeALot) {
     // Force grow
     size *= 2;
     if (size > _max_size) {
       // Too big, force shrink instead
       size /= 4;
     }
   } else {
     // Resize not needed
     return NULL;
   }
   // Update statistics
   _resize_count++;
   // Allocate the new table. The new table will be populated by workers
   // calling unlink_or_oops_do() and finally installed by finish_resize().
   return new G1StringDedupTable(size, _table->_hash_seed);
 }
 void G1StringDedupTable::finish_resize(G1StringDedupTable* resized_table) {
   assert(resized_table != NULL, "Invalid table");
   resized_table->_entries = _table->_entries;
   // Free old table
   delete _table;
   // Install new table
   _table = resized_table;
 }
 void G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id) {
   // The table is divided into partitions to allow lock-less parallel processing by
   // multiple worker threads. A worker thread first claims a partition, which ensures
   // exclusive access to that part of the table, then continues to process it. To allow
   // shrinking of the table in parallel we also need to make sure that the same worker
   // thread processes all partitions where entries will hash to the same destination
   // partition. Since the table size is always a power of two and we always shrink by
   // dividing the table in half, we know that for a given partition there is only one
   // other partition whoes entries will hash to the same destination partition. That
   // other partition is always the sibling partition in the second half of the table.
   // For example, if the table is divided into 8 partitions, the sibling of partition 0
   // is partition 4, the sibling of partition 1 is partition 5, etc.
   size_t table_half = _table->_size / 2;
   // Let each partition be one page worth of buckets
   size_t partition_size = MIN2(table_half, os::vm_page_size() / sizeof(G1StringDedupEntry*));
   assert(table_half % partition_size == 0, "Invalid partition size");
   // Number of entries removed during the scan
   uintx removed = 0;
   for (;;) {
     // Grab next partition to scan
     size_t partition_begin = cl->claim_table_partition(partition_size);
     size_t partition_end = partition_begin + partition_size;
     if (partition_begin >= table_half) {
       // End of table
       break;
     }
     // Scan the partition followed by the sibling partition in the second half of the table
     removed += unlink_or_oops_do(cl, partition_begin, partition_end, worker_id);
     removed += unlink_or_oops_do(cl, table_half + partition_begin, table_half + partition_end, worker_id);
   }
   // Delayed update avoid contention on the table lock
   if (removed > 0) {
     MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
     _table->_entries -= removed;
     _entries_removed += removed;
   }
 }
 uintx G1StringDedupTable::unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,
                                             size_t partition_begin,
                                             size_t partition_end,
                                             uint worker_id) {
   uintx removed = 0;
   for (size_t bucket = partition_begin; bucket < partition_end; bucket++) {
     G1StringDedupEntry** entry = _table->bucket(bucket);
     while (*entry != NULL) {
       oop* p = (oop*)(*entry)->obj_addr();
       if (cl->is_alive(*p)) {
         cl->keep_alive(p);
         if (cl->is_resizing()) {
           // We are resizing the table, transfer entry to the new table
           _table->transfer(entry, cl->resized_table());
         } else {
           if (cl->is_rehashing()) {
             // We are rehashing the table, rehash the entry but keep it
             // in the table. We can't transfer entries into the new table
             // at this point since we don't have exclusive access to all
             // destination partitions. finish_rehash() will do a single
             // threaded transfer of all entries.
             typeArrayOop value = (typeArrayOop)*p;
             unsigned int hash = hash_code(value);
             (*entry)->set_hash(hash);
           }
           // Move to next entry
           entry = (*entry)->next_addr();
         }
       } else {
         // Not alive, remove entry from table
         _table->remove(entry, worker_id);
         removed++;
       }
     }
   }
   return removed;
 }
 G1StringDedupTable* G1StringDedupTable::prepare_rehash() {
   if (!_table->_rehash_needed && !StringDeduplicationRehashALot) {
     // Rehash not needed
     return NULL;
   }
   // Update statistics
   _rehash_count++;
   // Compute new hash seed
   _table->_hash_seed = AltHashing::compute_seed();
   // Allocate the new table, same size and hash seed
   return new G1StringDedupTable(_table->_size, _table->_hash_seed);
 }
 void G1StringDedupTable::finish_rehash(G1StringDedupTable* rehashed_table) {
   assert(rehashed_table != NULL, "Invalid table");
   // Move all newly rehashed entries into the correct buckets in the new table
   for (size_t bucket = 0; bucket < _table->_size; bucket++) {
     G1StringDedupEntry** entry = _table->bucket(bucket);
     while (*entry != NULL) {
       _table->transfer(entry, rehashed_table);
     }
   }
   rehashed_table->_entries = _table->_entries;
   // Free old table
   delete _table;
   // Install new table
   _table = rehashed_table;
 }
 void G1StringDedupTable::verify() {
   for (size_t bucket = 0; bucket < _table->_size; bucket++) {
     // Verify entries
     G1StringDedupEntry** entry = _table->bucket(bucket);
     while (*entry != NULL) {
       typeArrayOop value = (*entry)->obj();
       guarantee(value != NULL, "Object must not be NULL");
       guarantee(Universe::heap()->is_in_reserved(value), "Object must be on the heap");
       guarantee(!value->is_forwarded(), "Object must not be forwarded");
       guarantee(value->is_typeArray(), "Object must be a typeArrayOop");
       unsigned int hash = hash_code(value);
       guarantee((*entry)->hash() == hash, "Table entry has inorrect hash");
       guarantee(_table->hash_to_index(hash) == bucket, "Table entry has incorrect index");
       entry = (*entry)->next_addr();
     }
     // Verify that we do not have entries with identical oops or identical arrays.
     // We only need to compare entries in the same bucket. If the same oop or an
     // identical array has been inserted more than once into different/incorrect
     // buckets the verification step above will catch that.
     G1StringDedupEntry** entry1 = _table->bucket(bucket);
     while (*entry1 != NULL) {
       typeArrayOop value1 = (*entry1)->obj();
       G1StringDedupEntry** entry2 = (*entry1)->next_addr();
       while (*entry2 != NULL) {
         typeArrayOop value2 = (*entry2)->obj();
         guarantee(!equals(value1, value2), "Table entries must not have identical arrays");
         entry2 = (*entry2)->next_addr();
       }
       entry1 = (*entry1)->next_addr();
     }
   }
 }
 void G1StringDedupTable::trim_entry_cache() {
   MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
   size_t max_cache_size = (size_t)(_table->_size * _max_cache_factor);
   _entry_cache->trim(max_cache_size);
 }
 void G1StringDedupTable::print_statistics(outputStream* st) {
   st->print_cr(
     "   [Table]\n"
     "      [Memory Usage: "G1_STRDEDUP_BYTES_FORMAT_NS"]\n"
     "      [Size: "SIZE_FORMAT", Min: "SIZE_FORMAT", Max: "SIZE_FORMAT"]\n"
     "      [Entries: "UINTX_FORMAT", Load: "G1_STRDEDUP_PERCENT_FORMAT_NS", Cached: " UINTX_FORMAT ", Added: "UINTX_FORMAT", Removed: "UINTX_FORMAT"]\n"
     "      [Resize Count: "UINTX_FORMAT", Shrink Threshold: "UINTX_FORMAT"("G1_STRDEDUP_PERCENT_FORMAT_NS"), Grow Threshold: "UINTX_FORMAT"("G1_STRDEDUP_PERCENT_FORMAT_NS")]\n"
     "      [Rehash Count: "UINTX_FORMAT", Rehash Threshold: "UINTX_FORMAT", Hash Seed: 0x%x]\n"
     "      [Age Threshold: "UINTX_FORMAT"]",
     G1_STRDEDUP_BYTES_PARAM(_table->_size * sizeof(G1StringDedupEntry*) + (_table->_entries + _entry_cache->size()) * sizeof(G1StringDedupEntry)),
     _table->_size, _min_size, _max_size,
     _table->_entries, (double)_table->_entries / (double)_table->_size * 100.0, _entry_cache->size(), _entries_added, _entries_removed,
     _resize_count, _table->_shrink_threshold, _shrink_load_factor * 100.0, _table->_grow_threshold, _grow_load_factor * 100.0,
     _rehash_count, _rehash_threshold, _table->_hash_seed,
     StringDeduplicationAgeThreshold);
 }

Mercurial > jdk8-mips64-public > hotspot / annotate

src/share/vm/gc_implementation/g1/g1StringDedupTable.cpp@e7d0505c8a30 (annotated)

src/share/vm/gc_implementation/g1/g1StringDedupTable.cpp