Mercurial > hg > graal-jvmci-8
comparison src/share/vm/utilities/hashtable.cpp @ 6197:d2a62e0f25eb
6995781: Native Memory Tracking (Phase 1)
7151532: DCmd for hotspot native memory tracking
Summary: Implementation of native memory tracking phase 1, which tracks VM native memory usage, and related DCmd
Reviewed-by: acorn, coleenp, fparain
author | zgu |
---|---|
date | Thu, 28 Jun 2012 17:03:16 -0400 |
parents | 246d977b51f2 |
children | ace99a6ffc83 |
comparison
equal
deleted
inserted
replaced
6174:74533f63b116 | 6197:d2a62e0f25eb |
---|---|
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>; |