1 /*
   2  * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
   3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
   4  *
   5  * This code is free software; you can redistribute it and/or modify it
   6  * under the terms of the GNU General Public License version 2 only, as
   7  * published by the Free Software Foundation.
   8  *
   9  * This code is distributed in the hope that it will be useful, but WITHOUT
  10  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
  11  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  12  * version 2 for more details (a copy is included in the LICENSE file that
  13  * accompanied this code).
  14  *
  15  * You should have received a copy of the GNU General Public License version
  16  * 2 along with this work; if not, write to the Free Software Foundation,
  17  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
  18  *
  19  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
  20  * or visit www.oracle.com if you need additional information or have any
  21  * questions.
  22  *
  23  */
  24 
  25 #ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
  26 #define SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
  27 
  28 #include "gc_implementation/g1/g1StringDedupStat.hpp"
  29 #include "runtime/mutexLocker.hpp"
  30 
  31 class G1StringDedupEntryCache;
  32 
  33 //
  34 // Table entry in the deduplication hashtable. Points weakly to the
  35 // character array. Can be chained in a linked list in case of hash
  36 // collisions or when placed in a freelist in the entry cache.
  37 //
  38 class G1StringDedupEntry : public CHeapObj<mtGC> {
  39 private:
  40   G1StringDedupEntry* _next;
  41   unsigned int      _hash;
  42   typeArrayOop      _obj;
  43 
  44 public:
  45   G1StringDedupEntry() :
  46     _next(NULL),
  47     _hash(0),
  48     _obj(NULL) {
  49   }
  50 
  51   G1StringDedupEntry* next() {
  52     return _next;
  53   }
  54 
  55   G1StringDedupEntry** next_addr() {
  56     return &_next;
  57   }
  58 
  59   void set_next(G1StringDedupEntry* next) {
  60     _next = next;
  61   }
  62 
  63   unsigned int hash() {
  64     return _hash;
  65   }
  66 
  67   void set_hash(unsigned int hash) {
  68     _hash = hash;
  69   }
  70 
  71   typeArrayOop obj() {
  72     return _obj;
  73   }
  74 
  75   typeArrayOop* obj_addr() {
  76     return &_obj;
  77   }
  78 
  79   void set_obj(typeArrayOop obj) {
  80     _obj = obj;
  81   }
  82 };
  83 
  84 //
  85 // The deduplication hashtable keeps track of all unique character arrays used
  86 // by String objects. Each table entry weakly points to an character array, allowing
  87 // otherwise unreachable character arrays to be declared dead and pruned from the
  88 // table.
  89 //
  90 // The table is dynamically resized to accommodate the current number of table entries.
  91 // The table has hash buckets with chains for hash collision. If the average chain
  92 // length goes above or below given thresholds the table grows or shrinks accordingly.
  93 //
  94 // The table is also dynamically rehashed (using a new hash seed) if it becomes severely
  95 // unbalanced, i.e., a hash chain is significantly longer than average.
  96 //
  97 // All access to the table is protected by the StringDedupTable_lock, except under
  98 // safepoints in which case GC workers are allowed to access a table partitions they
  99 // have claimed without first acquiring the lock. Note however, that this applies only
 100 // the table partition (i.e. a range of elements in _buckets), not other parts of the
 101 // table such as the _entries field, statistics counters, etc.
 102 //
 103 class G1StringDedupTable : public CHeapObj<mtGC> {
 104 private:
 105   // The currently active hashtable instance. Only modified when
 106   // the table is resizes or rehashed.
 107   static G1StringDedupTable*      _table;
 108 
 109   // Cache for reuse and fast alloc/free of table entries.
 110   static G1StringDedupEntryCache* _entry_cache;
 111 
 112   G1StringDedupEntry**            _buckets;
 113   size_t                          _size;
 114   uintx                           _entries;
 115   uintx                           _shrink_threshold;
 116   uintx                           _grow_threshold;
 117   bool                            _rehash_needed;
 118 
 119   // The hash seed also dictates which hash function to use. A
 120   // zero hash seed means we will use the Java compatible hash
 121   // function (which doesn't use a seed), and a non-zero hash
 122   // seed means we use the murmur3 hash function.
 123   jint                            _hash_seed;
 124 
 125   // Constants governing table resize/rehash/cache.
 126   static const size_t             _min_size;
 127   static const size_t             _max_size;
 128   static const double             _grow_load_factor;
 129   static const double             _shrink_load_factor;
 130   static const uintx              _rehash_multiple;
 131   static const uintx              _rehash_threshold;
 132   static const double             _max_cache_factor;
 133 
 134   // Table statistics, only used for logging.
 135   static uintx                    _entries_added;
 136   static uintx                    _entries_removed;
 137   static uintx                    _resize_count;
 138   static uintx                    _rehash_count;
 139 
 140   G1StringDedupTable(size_t size, jint hash_seed = 0);
 141   ~G1StringDedupTable();
 142 
 143   // Returns the hash bucket at the given index.
 144   G1StringDedupEntry** bucket(size_t index) {
 145     return _buckets + index;
 146   }
 147 
 148   // Returns the hash bucket index for the given hash code.
 149   size_t hash_to_index(unsigned int hash) {
 150     return (size_t)hash & (_size - 1);
 151   }
 152 
 153   // Adds a new table entry to the given hash bucket.
 154   void add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list);
 155 
 156   // Removes the given table entry from the table.
 157   void remove(G1StringDedupEntry** pentry, uint worker_id);
 158 
 159   // Transfers a table entry from the current table to the destination table.
 160   void transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest);
 161 
 162   // Returns an existing character array in the given hash bucket, or NULL
 163   // if no matching character array exists.
 164   typeArrayOop lookup(typeArrayOop value, unsigned int hash,
 165                       G1StringDedupEntry** list, uintx &count);
 166 
 167   // Returns an existing character array in the table, or inserts a new
 168   // table entry if no matching character array exists.
 169   typeArrayOop lookup_or_add_inner(typeArrayOop value, unsigned int hash);
 170 
 171   // Thread safe lookup or add of table entry
 172   static typeArrayOop lookup_or_add(typeArrayOop value, unsigned int hash) {
 173     // Protect the table from concurrent access. Also note that this lock
 174     // acts as a fence for _table, which could have been replaced by a new
 175     // instance if the table was resized or rehashed.
 176     MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
 177     return _table->lookup_or_add_inner(value, hash);
 178   }
 179 
 180   // Returns true if the hashtable is currently using a Java compatible
 181   // hash function.
 182   static bool use_java_hash() {
 183     return _table->_hash_seed == 0;
 184   }
 185 
 186   static bool equals(typeArrayOop value1, typeArrayOop value2);
 187 
 188   // Computes the hash code for the given character array, using the
 189   // currently active hash function and hash seed.
 190   static unsigned int hash_code(typeArrayOop value);
 191 
 192   static uintx unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,
 193                                  size_t partition_begin,
 194                                  size_t partition_end,
 195                                  uint worker_id);
 196 
 197 public:
 198   static void create();
 199 
 200   // Deduplicates the given String object, or adds its backing
 201   // character array to the deduplication hashtable.
 202   static void deduplicate(oop java_string, G1StringDedupStat& stat);
 203 
 204   // If a table resize is needed, returns a newly allocated empty
 205   // hashtable of the proper size.
 206   static G1StringDedupTable* prepare_resize();
 207 
 208   // Installs a newly resized table as the currently active table
 209   // and deletes the previously active table.
 210   static void finish_resize(G1StringDedupTable* resized_table);
 211 
 212   // If a table rehash is needed, returns a newly allocated empty
 213   // hashtable and updates the hash seed.
 214   static G1StringDedupTable* prepare_rehash();
 215 
 216   // Transfers rehashed entries from the currently active table into
 217   // the new table. Installs the new table as the currently active table
 218   // and deletes the previously active table.
 219   static void finish_rehash(G1StringDedupTable* rehashed_table);
 220 
 221   // If the table entry cache has grown too large, trim it down according to policy
 222   static void trim_entry_cache();
 223 
 224   static void unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id);
 225 
 226   static void print_statistics(outputStream* st);
 227   static void verify();
 228 };
 229 
 230 #endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP