Mercurial > hg > graal-jvmci-8

comparison src/share/vm/utilities/hashtable.cpp @ 6197:d2a62e0f25eb

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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>;