comparison src/share/vm/utilities/hashtable.cpp @ 4834:74d14a44c398

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