aoqi@0: /* aoqi@0: * Copyright (c) 2014, Oracle and/or its affiliates. All rights reserved. aoqi@0: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. aoqi@0: * aoqi@0: * This code is free software; you can redistribute it and/or modify it aoqi@0: * under the terms of the GNU General Public License version 2 only, as aoqi@0: * published by the Free Software Foundation. aoqi@0: * aoqi@0: * This code is distributed in the hope that it will be useful, but WITHOUT aoqi@0: * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or aoqi@0: * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License aoqi@0: * version 2 for more details (a copy is included in the LICENSE file that aoqi@0: * accompanied this code). aoqi@0: * aoqi@0: * You should have received a copy of the GNU General Public License version aoqi@0: * 2 along with this work; if not, write to the Free Software Foundation, aoqi@0: * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. aoqi@0: * aoqi@0: * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA aoqi@0: * or visit www.oracle.com if you need additional information or have any aoqi@0: * questions. aoqi@0: * aoqi@0: */ aoqi@0: aoqi@0: #ifndef SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP aoqi@0: #define SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP aoqi@0: aoqi@0: #include "gc_implementation/g1/g1StringDedupStat.hpp" aoqi@0: #include "runtime/mutexLocker.hpp" aoqi@0: aoqi@0: class G1StringDedupEntryCache; aoqi@0: aoqi@0: // aoqi@0: // Table entry in the deduplication hashtable. Points weakly to the aoqi@0: // character array. Can be chained in a linked list in case of hash aoqi@0: // collisions or when placed in a freelist in the entry cache. aoqi@0: // aoqi@0: class G1StringDedupEntry : public CHeapObj { aoqi@0: private: aoqi@0: G1StringDedupEntry* _next; aoqi@0: unsigned int _hash; aoqi@0: typeArrayOop _obj; aoqi@0: aoqi@0: public: aoqi@0: G1StringDedupEntry() : aoqi@0: _next(NULL), aoqi@0: _hash(0), aoqi@0: _obj(NULL) { aoqi@0: } aoqi@0: aoqi@0: G1StringDedupEntry* next() { aoqi@0: return _next; aoqi@0: } aoqi@0: aoqi@0: G1StringDedupEntry** next_addr() { aoqi@0: return &_next; aoqi@0: } aoqi@0: aoqi@0: void set_next(G1StringDedupEntry* next) { aoqi@0: _next = next; aoqi@0: } aoqi@0: aoqi@0: unsigned int hash() { aoqi@0: return _hash; aoqi@0: } aoqi@0: aoqi@0: void set_hash(unsigned int hash) { aoqi@0: _hash = hash; aoqi@0: } aoqi@0: aoqi@0: typeArrayOop obj() { aoqi@0: return _obj; aoqi@0: } aoqi@0: aoqi@0: typeArrayOop* obj_addr() { aoqi@0: return &_obj; aoqi@0: } aoqi@0: aoqi@0: void set_obj(typeArrayOop obj) { aoqi@0: _obj = obj; aoqi@0: } aoqi@0: }; aoqi@0: aoqi@0: // aoqi@0: // The deduplication hashtable keeps track of all unique character arrays used aoqi@0: // by String objects. Each table entry weakly points to an character array, allowing aoqi@0: // otherwise unreachable character arrays to be declared dead and pruned from the aoqi@0: // table. aoqi@0: // aoqi@0: // The table is dynamically resized to accommodate the current number of table entries. aoqi@0: // The table has hash buckets with chains for hash collision. If the average chain aoqi@0: // length goes above or below given thresholds the table grows or shrinks accordingly. aoqi@0: // aoqi@0: // The table is also dynamically rehashed (using a new hash seed) if it becomes severely aoqi@0: // unbalanced, i.e., a hash chain is significantly longer than average. aoqi@0: // aoqi@0: // All access to the table is protected by the StringDedupTable_lock, except under aoqi@0: // safepoints in which case GC workers are allowed to access a table partitions they aoqi@0: // have claimed without first acquiring the lock. Note however, that this applies only aoqi@0: // the table partition (i.e. a range of elements in _buckets), not other parts of the aoqi@0: // table such as the _entries field, statistics counters, etc. aoqi@0: // aoqi@0: class G1StringDedupTable : public CHeapObj { aoqi@0: private: aoqi@0: // The currently active hashtable instance. Only modified when aoqi@0: // the table is resizes or rehashed. aoqi@0: static G1StringDedupTable* _table; aoqi@0: aoqi@0: // Cache for reuse and fast alloc/free of table entries. aoqi@0: static G1StringDedupEntryCache* _entry_cache; aoqi@0: aoqi@0: G1StringDedupEntry** _buckets; aoqi@0: size_t _size; aoqi@0: uintx _entries; aoqi@0: uintx _shrink_threshold; aoqi@0: uintx _grow_threshold; aoqi@0: bool _rehash_needed; aoqi@0: aoqi@0: // The hash seed also dictates which hash function to use. A aoqi@0: // zero hash seed means we will use the Java compatible hash aoqi@0: // function (which doesn't use a seed), and a non-zero hash aoqi@0: // seed means we use the murmur3 hash function. aoqi@0: jint _hash_seed; aoqi@0: aoqi@0: // Constants governing table resize/rehash/cache. aoqi@0: static const size_t _min_size; aoqi@0: static const size_t _max_size; aoqi@0: static const double _grow_load_factor; aoqi@0: static const double _shrink_load_factor; aoqi@0: static const uintx _rehash_multiple; aoqi@0: static const uintx _rehash_threshold; aoqi@0: static const double _max_cache_factor; aoqi@0: aoqi@0: // Table statistics, only used for logging. aoqi@0: static uintx _entries_added; aoqi@0: static uintx _entries_removed; aoqi@0: static uintx _resize_count; aoqi@0: static uintx _rehash_count; aoqi@0: aoqi@0: G1StringDedupTable(size_t size, jint hash_seed = 0); aoqi@0: ~G1StringDedupTable(); aoqi@0: aoqi@0: // Returns the hash bucket at the given index. aoqi@0: G1StringDedupEntry** bucket(size_t index) { aoqi@0: return _buckets + index; aoqi@0: } aoqi@0: aoqi@0: // Returns the hash bucket index for the given hash code. aoqi@0: size_t hash_to_index(unsigned int hash) { aoqi@0: return (size_t)hash & (_size - 1); aoqi@0: } aoqi@0: aoqi@0: // Adds a new table entry to the given hash bucket. aoqi@0: void add(typeArrayOop value, unsigned int hash, G1StringDedupEntry** list); aoqi@0: aoqi@0: // Removes the given table entry from the table. aoqi@0: void remove(G1StringDedupEntry** pentry, uint worker_id); aoqi@0: aoqi@0: // Transfers a table entry from the current table to the destination table. aoqi@0: void transfer(G1StringDedupEntry** pentry, G1StringDedupTable* dest); aoqi@0: aoqi@0: // Returns an existing character array in the given hash bucket, or NULL aoqi@0: // if no matching character array exists. aoqi@0: typeArrayOop lookup(typeArrayOop value, unsigned int hash, aoqi@0: G1StringDedupEntry** list, uintx &count); aoqi@0: aoqi@0: // Returns an existing character array in the table, or inserts a new aoqi@0: // table entry if no matching character array exists. aoqi@0: typeArrayOop lookup_or_add_inner(typeArrayOop value, unsigned int hash); aoqi@0: aoqi@0: // Thread safe lookup or add of table entry aoqi@0: static typeArrayOop lookup_or_add(typeArrayOop value, unsigned int hash) { aoqi@0: // Protect the table from concurrent access. Also note that this lock aoqi@0: // acts as a fence for _table, which could have been replaced by a new aoqi@0: // instance if the table was resized or rehashed. aoqi@0: MutexLockerEx ml(StringDedupTable_lock, Mutex::_no_safepoint_check_flag); aoqi@0: return _table->lookup_or_add_inner(value, hash); aoqi@0: } aoqi@0: aoqi@0: // Returns true if the hashtable is currently using a Java compatible aoqi@0: // hash function. aoqi@0: static bool use_java_hash() { aoqi@0: return _table->_hash_seed == 0; aoqi@0: } aoqi@0: aoqi@0: static bool equals(typeArrayOop value1, typeArrayOop value2); aoqi@0: aoqi@0: // Computes the hash code for the given character array, using the aoqi@0: // currently active hash function and hash seed. aoqi@0: static unsigned int hash_code(typeArrayOop value); aoqi@0: aoqi@0: static uintx unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, aoqi@0: size_t partition_begin, aoqi@0: size_t partition_end, aoqi@0: uint worker_id); aoqi@0: aoqi@0: public: aoqi@0: static void create(); aoqi@0: aoqi@0: // Deduplicates the given String object, or adds its backing aoqi@0: // character array to the deduplication hashtable. aoqi@0: static void deduplicate(oop java_string, G1StringDedupStat& stat); aoqi@0: aoqi@0: // If a table resize is needed, returns a newly allocated empty aoqi@0: // hashtable of the proper size. aoqi@0: static G1StringDedupTable* prepare_resize(); aoqi@0: aoqi@0: // Installs a newly resized table as the currently active table aoqi@0: // and deletes the previously active table. aoqi@0: static void finish_resize(G1StringDedupTable* resized_table); aoqi@0: aoqi@0: // If a table rehash is needed, returns a newly allocated empty aoqi@0: // hashtable and updates the hash seed. aoqi@0: static G1StringDedupTable* prepare_rehash(); aoqi@0: aoqi@0: // Transfers rehashed entries from the currently active table into aoqi@0: // the new table. Installs the new table as the currently active table aoqi@0: // and deletes the previously active table. aoqi@0: static void finish_rehash(G1StringDedupTable* rehashed_table); aoqi@0: aoqi@0: // If the table entry cache has grown too large, trim it down according to policy aoqi@0: static void trim_entry_cache(); aoqi@0: aoqi@0: static void unlink_or_oops_do(G1StringDedupUnlinkOrOopsDoClosure* cl, uint worker_id); aoqi@0: aoqi@0: static void print_statistics(outputStream* st); aoqi@0: static void verify(); aoqi@0: }; aoqi@0: aoqi@0: #endif // SHARE_VM_GC_IMPLEMENTATION_G1_G1STRINGDEDUPTABLE_HPP