1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/gc_implementation/g1/g1StringDedupTable.hpp Tue Mar 18 19:07:22 2014 +0100
1.3 @@ -0,0 +1,230 @@
1.4 +/*
1.5 + * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
1.23 + * or visit www.oracle.com if you need additional information or have any
1.24 + * questions.
1.25 + *
1.26 + */
1.27 +
1.28 +#ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
1.29 +#define SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
1.30 +
1.31 +#include "gc_implementation/g1/g1StringDedupStat.hpp"
1.32 +#include "runtime/mutexLocker.hpp"
1.33 +
1.34 +class G1StringDedupEntryCache;
1.35 +
1.36 +//
1.37 +// Table entry in the deduplication hashtable. Points weakly to the
1.38 +// character array. Can be chained in a linked list in case of hash
1.39 +// collisions or when placed in a freelist in the entry cache.
1.40 +//
1.41 +class G1StringDedupEntry : public CHeapObj<mtGC> {
1.42 +private:
1.43 + G1StringDedupEntry* _next;
1.44 + unsigned int _hash;
1.45 + typeArrayOop _obj;
1.46 +
1.47 +public:
1.48 + G1StringDedupEntry() :
1.49 + _next(NULL),
1.50 + _hash(0),
1.51 + _obj(NULL) {
1.52 + }
1.53 +
1.54 + G1StringDedupEntry* next() {
1.55 + return _next;
1.56 + }
1.57 +
1.58 + G1StringDedupEntry** next_addr() {
1.59 + return &_next;
1.60 + }
1.61 +
1.62 + void set_next(G1StringDedupEntry* next) {
1.63 + _next = next;
1.64 + }
1.65 +
1.66 + unsigned int hash() {
1.67 + return _hash;
1.68 + }
1.69 +
1.70 + void set_hash(unsigned int hash) {
1.71 + _hash = hash;
1.72 + }
1.73 +
1.74 + typeArrayOop obj() {
1.75 + return _obj;
1.76 + }
1.77 +
1.78 + typeArrayOop* obj_addr() {
1.79 + return &_obj;
1.80 + }
1.81 +
1.82 + void set_obj(typeArrayOop obj) {
1.83 + _obj = obj;
1.84 + }
1.85 +};
1.86 +
1.87 +//
1.88 +// The deduplication hashtable keeps track of all unique character arrays used
1.89 +// by String objects. Each table entry weakly points to an character array, allowing
1.90 +// otherwise unreachable character arrays to be declared dead and pruned from the
1.91 +// table.
1.92 +//
1.93 +// The table is dynamically resized to accommodate the current number of table entries.
1.94 +// The table has hash buckets with chains for hash collision. If the average chain
1.95 +// length goes above or below given thresholds the table grows or shrinks accordingly.
1.96 +//
1.97 +// The table is also dynamically rehashed (using a new hash seed) if it becomes severely
1.98 +// unbalanced, i.e., a hash chain is significantly longer than average.
1.99 +//
1.100 +// All access to the table is protected by the StringDedupTable_lock, except under
1.101 +// safepoints in which case GC workers are allowed to access a table partitions they
1.102 +// have claimed without first acquiring the lock. Note however, that this applies only
1.103 +// the table partition (i.e. a range of elements in _buckets), not other parts of the
1.104 +// table such as the _entries field, statistics counters, etc.
1.105 +//
1.106 +class G1StringDedupTable : public CHeapObj<mtGC> {
1.107 +private:
1.108 + // The currently active hashtable instance. Only modified when
1.109 + // the table is resizes or rehashed.
1.110 + static G1StringDedupTable* _table;
1.111 +
1.112 + // Cache for reuse and fast alloc/free of table entries.
1.113 + static G1StringDedupEntryCache* _entry_cache;
1.114 +
1.115 + G1StringDedupEntry** _buckets;
1.116 + size_t _size;
1.117 + uintx _entries;
1.118 + uintx _shrink_threshold;
1.119 + uintx _grow_threshold;
1.120 + bool _rehash_needed;
1.121 +
1.122 + // The hash seed also dictates which hash function to use. A
1.123 + // zero hash seed means we will use the Java compatible hash
1.124 + // function (which doesn't use a seed), and a non-zero hash
1.125 + // seed means we use the murmur3 hash function.
1.126 + jint _hash_seed;
1.127 +
1.128 + // Constants governing table resize/rehash/cache.
1.129 + static const size_t _min_size;
1.130 + static const size_t _max_size;
1.131 + static const double _grow_load_factor;
1.132 + static const double _shrink_load_factor;
1.133 + static const uintx _rehash_multiple;
1.134 + static const uintx _rehash_threshold;
1.135 + static const double _max_cache_factor;
1.136 +
1.137 + // Table statistics, only used for logging.
1.138 + static uintx _entries_added;
1.139 + static uintx _entries_removed;
1.140 + static uintx _resize_count;
1.141 + static uintx _rehash_count;
1.142 +
1.143 + G1StringDedupTable(size_t size, jint hash_seed = 0);
1.144 + ~G1StringDedupTable();
1.145 +
1.146 + // Returns the hash bucket at the given index.
1.147 + G1StringDedupEntry** bucket(size_t index) {
1.148 + return _buckets + index;
1.149 + }
1.150 +
1.151 + // Returns the hash bucket index for the given hash code.
1.152 + size_t hash_to_index(unsigned int hash) {
1.153 + return (size_t)hash & (_size - 1);
1.154 + }
1.155 +
1.156 + // Adds a new table entry to the given hash bucket.
1.157 + void add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list);
1.158 +
1.159 + // Removes the given table entry from the table.
1.160 + void remove(G1StringDedupEntry** pentry, uint worker_id);
1.161 +
1.162 + // Transfers a table entry from the current table to the destination table.
1.163 + void transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest);
1.164 +
1.165 + // Returns an existing character array in the given hash bucket, or NULL
1.166 + // if no matching character array exists.
1.167 + typeArrayOop lookup(typeArrayOop value, unsigned int hash,
1.168 + G1StringDedupEntry** list, uintx &count);
1.169 +
1.170 + // Returns an existing character array in the table, or inserts a new
1.171 + // table entry if no matching character array exists.
1.172 + typeArrayOop lookup_or_add_inner(typeArrayOop value, unsigned int hash);
1.173 +
1.174 + // Thread safe lookup or add of table entry
1.175 + static typeArrayOop lookup_or_add(typeArrayOop value, unsigned int hash) {
1.176 + // Protect the table from concurrent access. Also note that this lock
1.177 + // acts as a fence for _table, which could have been replaced by a new
1.178 + // instance if the table was resized or rehashed.
1.179 + MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag);
1.180 + return _table->lookup_or_add_inner(value, hash);
1.181 + }
1.182 +
1.183 + // Returns true if the hashtable is currently using a Java compatible
1.184 + // hash function.
1.185 + static bool use_java_hash() {
1.186 + return _table->_hash_seed == 0;
1.187 + }
1.188 +
1.189 + static bool equals(typeArrayOop value1, typeArrayOop value2);
1.190 +
1.191 + // Computes the hash code for the given character array, using the
1.192 + // currently active hash function and hash seed.
1.193 + static unsigned int hash_code(typeArrayOop value);
1.194 +
1.195 + static uintx unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl,
1.196 + size_t partition_begin,
1.197 + size_t partition_end,
1.198 + uint worker_id);
1.199 +
1.200 +public:
1.201 + static void create();
1.202 +
1.203 + // Deduplicates the given String object, or adds its backing
1.204 + // character array to the deduplication hashtable.
1.205 + static void deduplicate(oop java_string, G1StringDedupStat& stat);
1.206 +
1.207 + // If a table resize is needed, returns a newly allocated empty
1.208 + // hashtable of the proper size.
1.209 + static G1StringDedupTable* prepare_resize();
1.210 +
1.211 + // Installs a newly resized table as the currently active table
1.212 + // and deletes the previously active table.
1.213 + static void finish_resize(G1StringDedupTable* resized_table);
1.214 +
1.215 + // If a table rehash is needed, returns a newly allocated empty
1.216 + // hashtable and updates the hash seed.
1.217 + static G1StringDedupTable* prepare_rehash();
1.218 +
1.219 + // Transfers rehashed entries from the currently active table into
1.220 + // the new table. Installs the new table as the currently active table
1.221 + // and deletes the previously active table.
1.222 + static void finish_rehash(G1StringDedupTable* rehashed_table);
1.223 +
1.224 + // If the table entry cache has grown too large, trim it down according to policy
1.225 + static void trim_entry_cache();
1.226 +
1.227 + static void unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id);
1.228 +
1.229 + static void print_statistics(outputStream* st);
1.230 + static void verify();
1.231 +};
1.232 +
1.233 +#endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP
