hashtable.cpp revision 3465:d2a62e0f25eb
1/* 2 * Copyright (c) 2003, 2012, 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#include "precompiled.hpp" 26#include "memory/allocation.inline.hpp" 27#include "memory/filemap.hpp" 28#include "memory/resourceArea.hpp" 29#include "oops/oop.inline.hpp" 30#include "runtime/safepoint.hpp" 31#include "utilities/dtrace.hpp" 32#include "utilities/hashtable.hpp" 33#include "utilities/hashtable.inline.hpp" 34 35 36// This is a generic hashtable, designed to be used for the symbol 37// and string tables. 38// 39// It is implemented as an open hash table with a fixed number of buckets. 40// 41// %note: 42// - HashtableEntrys are allocated in blocks to reduce the space overhead. 43 44template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) { 45 BasicHashtableEntry<F>* entry; 46 47 if (_free_list) { 48 entry = _free_list; 49 _free_list = _free_list->next(); 50 } else { 51 if (_first_free_entry + _entry_size >= _end_block) { 52 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries)); 53 int len = _entry_size * block_size; 54 len = 1 << log2_intptr(len); // round down to power of 2 55 assert(len >= _entry_size, ""); 56 _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC); 57 _end_block = _first_free_entry + len; 58 } 59 entry = (BasicHashtableEntry<F>*)_first_free_entry; 60 _first_free_entry += _entry_size; 61 } 62 63 assert(_entry_size % HeapWordSize == 0, ""); 64 entry->set_hash(hashValue); 65 return entry; 66} 67 68 69template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) { 70 HashtableEntry<T, F>* entry; 71 72 entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue); 73 entry->set_literal(obj); 74 return entry; 75} 76 77// Check to see if the hashtable is unbalanced. The caller set a flag to 78// rehash at the next safepoint. If this bucket is 60 times greater than the 79// expected average bucket length, it's an unbalanced hashtable. 80// This is somewhat an arbitrary heuristic but if one bucket gets to 81// rehash_count which is currently 100, there's probably something wrong. 82 83template <MEMFLAGS F> bool BasicHashtable<F>::check_rehash_table(int count) { 84 assert(table_size() != 0, "underflow"); 85 if (count > (((double)number_of_entries()/(double)table_size())*rehash_multiple)) { 86 // Set a flag for the next safepoint, which should be at some guaranteed 87 // safepoint interval. 88 return true; 89 } 90 return false; 91} 92 93// Create a new table and using alternate hash code, populate the new table 94// with the existing elements. This can be used to change the hash code 95// and could in the future change the size of the table. 96 97template <class T, MEMFLAGS F> void Hashtable<T, F>::move_to(Hashtable<T, F>* new_table) { 98 int saved_entry_count = BasicHashtable<F>::number_of_entries(); 99 100 // Iterate through the table and create a new entry for the new table 101 for (int i = 0; i < new_table->table_size(); ++i) { 102 for (HashtableEntry<T, F>* p = bucket(i); p != NULL; ) { 103 HashtableEntry<T, F>* next = p->next(); 104 T string = p->literal(); 105 // Use alternate hashing algorithm on the symbol in the first table 106 unsigned int hashValue = new_hash(string); 107 // Get a new index relative to the new table (can also change size) 108 int index = new_table->hash_to_index(hashValue); 109 p->set_hash(hashValue); 110 // Keep the shared bit in the Hashtable entry to indicate that this entry 111 // can't be deleted. The shared bit is the LSB in the _next field so 112 // walking the hashtable past these entries requires 113 // BasicHashtableEntry::make_ptr() call. 114 bool keep_shared = p->is_shared(); 115 unlink_entry(p); 116 new_table->add_entry(index, p); 117 if (keep_shared) { 118 p->set_shared(); 119 } 120 p = next; 121 } 122 } 123 // give the new table the free list as well 124 new_table->copy_freelist(this); 125 assert(new_table->number_of_entries() == saved_entry_count, "lost entry on dictionary copy?"); 126 127 // Destroy memory used by the buckets in the hashtable. The memory 128 // for the elements has been used in a new table and is not 129 // destroyed. The memory reuse will benefit resizing the SystemDictionary 130 // to avoid a memory allocation spike at safepoint. 131 BasicHashtable<F>::free_buckets(); 132} 133 134template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() { 135 if (NULL != _buckets) { 136 // Don't delete the buckets in the shared space. They aren't 137 // allocated by os::malloc 138 if (!UseSharedSpaces || 139 !FileMapInfo::current_info()->is_in_shared_space(_buckets)) { 140 FREE_C_HEAP_ARRAY(HashtableBucket, _buckets, F); 141 } 142 _buckets = NULL; 143 } 144} 145 146 147// Reverse the order of elements in the hash buckets. 148 149template <MEMFLAGS F> void BasicHashtable<F>::reverse() { 150 151 for (int i = 0; i < _table_size; ++i) { 152 BasicHashtableEntry<F>* new_list = NULL; 153 BasicHashtableEntry<F>* p = bucket(i); 154 while (p != NULL) { 155 BasicHashtableEntry<F>* next = p->next(); 156 p->set_next(new_list); 157 new_list = p; 158 p = next; 159 } 160 *bucket_addr(i) = new_list; 161 } 162} 163 164 165// Copy the table to the shared space. 166 167template <MEMFLAGS F> void BasicHashtable<F>::copy_table(char** top, char* end) { 168 169 // Dump the hash table entries. 170 171 intptr_t *plen = (intptr_t*)(*top); 172 *top += sizeof(*plen); 173 174 int i; 175 for (i = 0; i < _table_size; ++i) { 176 for (BasicHashtableEntry<F>** p = _buckets[i].entry_addr(); 177 *p != NULL; 178 p = (*p)->next_addr()) { 179 if (*top + entry_size() > end) { 180 report_out_of_shared_space(SharedMiscData); 181 } 182 *p = (BasicHashtableEntry<F>*)memcpy(*top, *p, entry_size()); 183 *top += entry_size(); 184 } 185 } 186 *plen = (char*)(*top) - (char*)plen - sizeof(*plen); 187 188 // Set the shared bit. 189 190 for (i = 0; i < _table_size; ++i) { 191 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) { 192 p->set_shared(); 193 } 194 } 195} 196 197 198 199// Reverse the order of elements in the hash buckets. 200 201template <class T, MEMFLAGS F> void Hashtable<T, F>::reverse(void* boundary) { 202 203 for (int i = 0; i < this->table_size(); ++i) { 204 HashtableEntry<T, F>* high_list = NULL; 205 HashtableEntry<T, F>* low_list = NULL; 206 HashtableEntry<T, F>* last_low_entry = NULL; 207 HashtableEntry<T, F>* p = bucket(i); 208 while (p != NULL) { 209 HashtableEntry<T, F>* next = p->next(); 210 if ((void*)p->literal() >= boundary) { 211 p->set_next(high_list); 212 high_list = p; 213 } else { 214 p->set_next(low_list); 215 low_list = p; 216 if (last_low_entry == NULL) { 217 last_low_entry = p; 218 } 219 } 220 p = next; 221 } 222 if (low_list != NULL) { 223 *bucket_addr(i) = low_list; 224 last_low_entry->set_next(high_list); 225 } else { 226 *bucket_addr(i) = high_list; 227 } 228 } 229} 230 231 232// Dump the hash table buckets. 233 234template <MEMFLAGS F> void BasicHashtable<F>::copy_buckets(char** top, char* end) { 235 intptr_t len = _table_size * sizeof(HashtableBucket<F>); 236 *(intptr_t*)(*top) = len; 237 *top += sizeof(intptr_t); 238 239 *(intptr_t*)(*top) = _number_of_entries; 240 *top += sizeof(intptr_t); 241 242 if (*top + len > end) { 243 report_out_of_shared_space(SharedMiscData); 244 } 245 _buckets = (HashtableBucket<F>*)memcpy(*top, _buckets, len); 246 *top += len; 247} 248 249 250#ifndef PRODUCT 251 252template <class T, MEMFLAGS F> void Hashtable<T, F>::print() { 253 ResourceMark rm; 254 255 for (int i = 0; i < BasicHashtable<F>::table_size(); i++) { 256 HashtableEntry<T, F>* entry = bucket(i); 257 while(entry != NULL) { 258 tty->print("%d : ", i); 259 entry->literal()->print(); 260 tty->cr(); 261 entry = entry->next(); 262 } 263 } 264} 265 266 267template <MEMFLAGS F> void BasicHashtable<F>::verify() { 268 int count = 0; 269 for (int i = 0; i < table_size(); i++) { 270 for (BasicHashtableEntry<F>* p = bucket(i); p != NULL; p = p->next()) { 271 ++count; 272 } 273 } 274 assert(count == number_of_entries(), "number of hashtable entries incorrect"); 275} 276 277 278#endif // PRODUCT 279 280 281#ifdef ASSERT 282 283template <MEMFLAGS F> void BasicHashtable<F>::verify_lookup_length(double load) { 284 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) { 285 warning("Performance bug: SystemDictionary lookup_count=%d " 286 "lookup_length=%d average=%lf load=%f", 287 _lookup_count, _lookup_length, 288 (double) _lookup_length / _lookup_count, load); 289 } 290} 291 292#endif 293// Explicitly instantiate these types 294template class Hashtable<constantPoolOop, mtClass>; 295template class Hashtable<Symbol*, mtSymbol>; 296template class Hashtable<klassOop, mtClass>; 297template class Hashtable<oop, mtClass>; 298#ifdef SOLARIS 299template class Hashtable<oop, mtSymbol>; 300#endif 301template class Hashtable<oopDesc*, mtSymbol>; 302template class Hashtable<Symbol*, mtClass>; 303template class HashtableEntry<Symbol*, mtSymbol>; 304template class HashtableEntry<Symbol*, mtClass>; 305template class HashtableEntry<oop, mtSymbol>; 306template class BasicHashtableEntry<mtSymbol>; 307template class BasicHashtableEntry<mtCode>; 308template class BasicHashtable<mtClass>; 309template class BasicHashtable<mtSymbol>; 310template class BasicHashtable<mtCode>; 311template class BasicHashtable<mtInternal>; 312