1 /*

     2  * Copyright (c) 2014, 2015, 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_G1_G1STRINGDEDUPTABLE_HPP

    26 #define SHARE_VM_GC_G1_G1STRINGDEDUPTABLE_HPP

    27 

    28 #include "gc/g1/g1StringDedupStat.hpp"

    29 #include "runtime/mutexLocker.hpp"

    30 

    31 class G1StringDedupEntryCache;

    32 class G1StringDedupUnlinkOrOopsDoClosure;

    33 

    34 //

    35 // Table entry in the deduplication hashtable. Points weakly to the

    36 // character array. Can be chained in a linked list in case of hash

    37 // collisions or when placed in a freelist in the entry cache.

    38 //

    39 class G1StringDedupEntry : public CHeapObj<mtGC> {

    40 private:

    41   G1StringDedupEntry* _next;

    42   unsigned int      _hash;

    43   typeArrayOop      _obj;

    44 

    45 public:

    46   G1StringDedupEntry() :

    47     _next(NULL),

    48     _hash(0),

    49     _obj(NULL) {

    50   }

    51 

    52   G1StringDedupEntry* next() {

    53     return _next;

    54   }

    55 

    56   G1StringDedupEntry** next_addr() {

    57     return &_next;

    58   }

    59 

    60   void set_next(G1StringDedupEntry* next) {

    61     _next = next;

    62   }

    63 

    64   unsigned int hash() {

    65     return _hash;

    66   }

    67 

    68   void set_hash(unsigned int hash) {

    69     _hash = hash;

    70   }

    71 

    72   typeArrayOop obj() {

    73     return _obj;

    74   }

    75 

    76   typeArrayOop* obj_addr() {

    77     return &_obj;

    78   }

    79 

    80   void set_obj(typeArrayOop obj) {

    81     _obj = obj;

    82   }

    83 };

    84 

    85 //

    86 // The deduplication hashtable keeps track of all unique character arrays used

    87 // by String objects. Each table entry weakly points to an character array, allowing

    88 // otherwise unreachable character arrays to be declared dead and pruned from the

    89 // table.

    90 //

    91 // The table is dynamically resized to accommodate the current number of table entries.

    92 // The table has hash buckets with chains for hash collision. If the average chain

    93 // length goes above or below given thresholds the table grows or shrinks accordingly.

    94 //

    95 // The table is also dynamically rehashed (using a new hash seed) if it becomes severely

    96 // unbalanced, i.e., a hash chain is significantly longer than average.

    97 //

    98 // All access to the table is protected by the StringDedupTable_lock, except under

    99 // safepoints in which case GC workers are allowed to access a table partitions they

   100 // have claimed without first acquiring the lock. Note however, that this applies only

   101 // the table partition (i.e. a range of elements in _buckets), not other parts of the

   102 // table such as the _entries field, statistics counters, etc.

   103 //

   104 class G1StringDedupTable : public CHeapObj<mtGC> {

   105 private:

   106   // The currently active hashtable instance. Only modified when

   107   // the table is resizes or rehashed.

   108   static G1StringDedupTable*      _table;

   109 

   110   // Cache for reuse and fast alloc/free of table entries.

   111   static G1StringDedupEntryCache* _entry_cache;

   112 

   113   G1StringDedupEntry**            _buckets;

   114   size_t                          _size;

   115   uintx                           _entries;

   116   uintx                           _shrink_threshold;

   117   uintx                           _grow_threshold;

   118   bool                            _rehash_needed;

   119 

   120   // The hash seed also dictates which hash function to use. A

   121   // zero hash seed means we will use the Java compatible hash

   122   // function (which doesn't use a seed), and a non-zero hash

   123   // seed means we use the murmur3 hash function.

   124   jint                            _hash_seed;

   125 

   126   // Constants governing table resize/rehash/cache.

   127   static const size_t             _min_size;

   128   static const size_t             _max_size;

   129   static const double             _grow_load_factor;

   130   static const double             _shrink_load_factor;

   131   static const uintx              _rehash_multiple;

   132   static const uintx              _rehash_threshold;

   133   static const double             _max_cache_factor;

   134 

   135   // Table statistics, only used for logging.

   136   static uintx                    _entries_added;

   137   static uintx                    _entries_removed;

   138   static uintx                    _resize_count;

   139   static uintx                    _rehash_count;

   140 

   141   G1StringDedupTable(size_t size, jint hash_seed = 0);

   142   ~G1StringDedupTable();

   143 

   144   // Returns the hash bucket at the given index.

   145   G1StringDedupEntry** bucket(size_t index) {

   146     return _buckets + index;

   147   }

   148 

   149   // Returns the hash bucket index for the given hash code.

   150   size_t hash_to_index(unsigned int hash) {

   151     return (size_t)hash & (_size - 1);

   152   }

   153 

   154   // Adds a new table entry to the given hash bucket.

   155   void add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list);

   156 

   157   // Removes the given table entry from the table.

   158   void remove(G1StringDedupEntry** pentry, uint worker_id);

   159 

   160   // Transfers a table entry from the current table to the destination table.

   161   void transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest);

   162 

   163   // Returns an existing character array in the given hash bucket, or NULL

   164   // if no matching character array exists.

   165   typeArrayOop lookup(typeArrayOop value, unsigned int hash,

   166                       G1StringDedupEntry** list, uintx &count);

   167 

   168   // Returns an existing character array in the table, or inserts a new

   169   // table entry if no matching character array exists.

   170   typeArrayOop lookup_or_add_inner(typeArrayOop value, unsigned int hash);

   171 

   172   // Thread safe lookup or add of table entry

   173   static typeArrayOop lookup_or_add(typeArrayOop value, unsigned int hash) {

   174     // Protect the table from concurrent access. Also note that this lock

   175     // acts as a fence for _table, which could have been replaced by a new

   176     // instance if the table was resized or rehashed.

   177     MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);

   178     return _table->lookup_or_add_inner(value, hash);

   179   }

   180 

   181   // Returns true if the hashtable is currently using a Java compatible

   182   // hash function.

   183   static bool use_java_hash() {

   184     return _table->_hash_seed == 0;

   185   }

   186 

   187   static bool equals(typeArrayOop value1, typeArrayOop value2);

   188 

   189   // Computes the hash code for the given character array, using the

   190   // currently active hash function and hash seed.

   191   static unsigned int hash_code(typeArrayOop value);

   192 

   193   static uintx unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,

   194                                  size_t partition_begin,

   195                                  size_t partition_end,

   196                                  uint worker_id);

   197 

   198 public:

   199   static void create();

   200 

   201   // Deduplicates the given String object, or adds its backing

   202   // character array to the deduplication hashtable.

   203   static void deduplicate(oop java_string, G1StringDedupStat& stat);

   204 

   205   // If a table resize is needed, returns a newly allocated empty

   206   // hashtable of the proper size.

   207   static G1StringDedupTable* prepare_resize();

   208 

   209   // Installs a newly resized table as the currently active table

   210   // and deletes the previously active table.

   211   static void finish_resize(G1StringDedupTable* resized_table);

   212 

   213   // If a table rehash is needed, returns a newly allocated empty

   214   // hashtable and updates the hash seed.

   215   static G1StringDedupTable* prepare_rehash();

   216 

   217   // Transfers rehashed entries from the currently active table into

   218   // the new table. Installs the new table as the currently active table

   219   // and deletes the previously active table.

   220   static void finish_rehash(G1StringDedupTable* rehashed_table);

   221 

   222   // If the table entry cache has grown too large, trim it down according to policy

   223   static void trim_entry_cache();

   224 

   225   static void unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id);

   226 

   227   static void print_statistics(outputStream* st);

   228   static void verify();

   229 };

   230 

   231 #endif // SHARE_VM_GC_G1_G1STRINGDEDUPTABLE_HPP