| /* |
| * Copyright (c) 2014, 2016, 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. |
| * |
| */ |
| |
| #ifndef SHARE_VM_GC_G1_G1STRINGDEDUPTABLE_HPP |
| #define SHARE_VM_GC_G1_G1STRINGDEDUPTABLE_HPP |
| |
| #include "gc/g1/g1StringDedupStat.hpp" |
| #include "runtime/mutexLocker.hpp" |
| |
| class G1StringDedupEntryCache; |
| class G1StringDedupUnlinkOrOopsDoClosure; |
| |
| // |
| // Table entry in the deduplication hashtable. Points weakly to the |
| // character array. Can be chained in a linked list in case of hash |
| // collisions or when placed in a freelist in the entry cache. |
| // |
| class G1StringDedupEntry : public CHeapObj<mtGC> { |
| private: |
| G1StringDedupEntry* _next; |
| unsigned int _hash; |
| bool _latin1; |
| typeArrayOop _obj; |
| |
| public: |
| G1StringDedupEntry() : |
| _next(NULL), |
| _hash(0), |
| _latin1(false), |
| _obj(NULL) { |
| } |
| |
| G1StringDedupEntry* next() { |
| return _next; |
| } |
| |
| G1StringDedupEntry** next_addr() { |
| return &_next; |
| } |
| |
| void set_next(G1StringDedupEntry* next) { |
| _next = next; |
| } |
| |
| unsigned int hash() { |
| return _hash; |
| } |
| |
| void set_hash(unsigned int hash) { |
| _hash = hash; |
| } |
| |
| bool latin1() { |
| return _latin1; |
| } |
| |
| void set_latin1(bool latin1) { |
| _latin1 = latin1; |
| } |
| |
| typeArrayOop obj() { |
| return _obj; |
| } |
| |
| typeArrayOop* obj_addr() { |
| return &_obj; |
| } |
| |
| void set_obj(typeArrayOop obj) { |
| _obj = obj; |
| } |
| }; |
| |
| // |
| // The deduplication hashtable keeps track of all unique character arrays used |
| // by String objects. Each table entry weakly points to an character array, allowing |
| // otherwise unreachable character arrays to be declared dead and pruned from the |
| // table. |
| // |
| // The table is dynamically resized to accommodate the current number of table entries. |
| // The table has hash buckets with chains for hash collision. If the average chain |
| // length goes above or below given thresholds the table grows or shrinks accordingly. |
| // |
| // The table is also dynamically rehashed (using a new hash seed) if it becomes severely |
| // unbalanced, i.e., a hash chain is significantly longer than average. |
| // |
| // All access to the table is protected by the StringDedupTable_lock, except under |
| // safepoints in which case GC workers are allowed to access a table partitions they |
| // have claimed without first acquiring the lock. Note however, that this applies only |
| // the table partition (i.e. a range of elements in _buckets), not other parts of the |
| // table such as the _entries field, statistics counters, etc. |
| // |
| class G1StringDedupTable : public CHeapObj<mtGC> { |
| private: |
| // The currently active hashtable instance. Only modified when |
| // the table is resizes or rehashed. |
| static G1StringDedupTable* _table; |
| |
| // Cache for reuse and fast alloc/free of table entries. |
| static G1StringDedupEntryCache* _entry_cache; |
| |
| G1StringDedupEntry** _buckets; |
| size_t _size; |
| uintx _entries; |
| uintx _shrink_threshold; |
| uintx _grow_threshold; |
| bool _rehash_needed; |
| |
| // The hash seed also dictates which hash function to use. A |
| // zero hash seed means we will use the Java compatible hash |
| // function (which doesn't use a seed), and a non-zero hash |
| // seed means we use the murmur3 hash function. |
| jint _hash_seed; |
| |
| // Constants governing table resize/rehash/cache. |
| static const size_t _min_size; |
| static const size_t _max_size; |
| static const double _grow_load_factor; |
| static const double _shrink_load_factor; |
| static const uintx _rehash_multiple; |
| static const uintx _rehash_threshold; |
| static const double _max_cache_factor; |
| |
| // Table statistics, only used for logging. |
| static uintx _entries_added; |
| static uintx _entries_removed; |
| static uintx _resize_count; |
| static uintx _rehash_count; |
| |
| G1StringDedupTable(size_t size, jint hash_seed = 0); |
| ~G1StringDedupTable(); |
| |
| // Returns the hash bucket at the given index. |
| G1StringDedupEntry** bucket(size_t index) { |
| return _buckets + index; |
| } |
| |
| // Returns the hash bucket index for the given hash code. |
| size_t hash_to_index(unsigned int hash) { |
| return (size_t)hash & (_size - 1); |
| } |
| |
| // Adds a new table entry to the given hash bucket. |
| void add(typeArrayOop value, bool latin1, unsigned int hash, G1StringDedupEntry** list); |
| |
| // Removes the given table entry from the table. |
| void remove(G1StringDedupEntry** pentry, uint worker_id); |
| |
| // Transfers a table entry from the current table to the destination table. |
| void transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest); |
| |
| // Returns an existing character array in the given hash bucket, or NULL |
| // if no matching character array exists. |
| typeArrayOop lookup(typeArrayOop value, bool latin1, unsigned int hash, |
| G1StringDedupEntry** list, uintx &count); |
| |
| // Returns an existing character array in the table, or inserts a new |
| // table entry if no matching character array exists. |
| typeArrayOop lookup_or_add_inner(typeArrayOop value, bool latin1, unsigned int hash); |
| |
| // Thread safe lookup or add of table entry |
| static typeArrayOop lookup_or_add(typeArrayOop value, bool latin1, unsigned int hash) { |
| // Protect the table from concurrent access. Also note that this lock |
| // acts as a fence for _table, which could have been replaced by a new |
| // instance if the table was resized or rehashed. |
| MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag); |
| return _table->lookup_or_add_inner(value, latin1, hash); |
| } |
| |
| // Returns true if the hashtable is currently using a Java compatible |
| // hash function. |
| static bool use_java_hash() { |
| return _table->_hash_seed == 0; |
| } |
| |
| static bool equals(typeArrayOop value1, typeArrayOop value2); |
| |
| // Computes the hash code for the given character array, using the |
| // currently active hash function and hash seed. |
| static unsigned int hash_code(typeArrayOop value, bool latin1); |
| |
| static uintx unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, |
| size_t partition_begin, |
| size_t partition_end, |
| uint worker_id); |
| |
| public: |
| static void create(); |
| |
| // Deduplicates the given String object, or adds its backing |
| // character array to the deduplication hashtable. |
| static void deduplicate(oop java_string, G1StringDedupStat& stat); |
| |
| // If a table resize is needed, returns a newly allocated empty |
| // hashtable of the proper size. |
| static G1StringDedupTable* prepare_resize(); |
| |
| // Installs a newly resized table as the currently active table |
| // and deletes the previously active table. |
| static void finish_resize(G1StringDedupTable* resized_table); |
| |
| // If a table rehash is needed, returns a newly allocated empty |
| // hashtable and updates the hash seed. |
| static G1StringDedupTable* prepare_rehash(); |
| |
| // Transfers rehashed entries from the currently active table into |
| // the new table. Installs the new table as the currently active table |
| // and deletes the previously active table. |
| static void finish_rehash(G1StringDedupTable* rehashed_table); |
| |
| // If the table entry cache has grown too large, delete overflowed entries. |
| static void clean_entry_cache(); |
| |
| static void unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id); |
| |
| static void print_statistics(); |
| static void verify(); |
| }; |
| |
| #endif // SHARE_VM_GC_G1_G1STRINGDEDUPTABLE_HPP |