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