Mercurial > hg > truffle
annotate src/share/vm/utilities/hashtable.hpp @ 17716:cdb71841f4bc
6498581: ThreadInterruptTest3 produces wrong output on Windows
Summary: There is race condition between os::interrupt and os::is_interrupted on Windows. In JVM_Sleep(Thread.sleep), check if thread gets interrupted, it may see interrupted but not really interrupted so cause spurious waking up (early return from sleep). Fix by checking if interrupt event really gets set thus prevent false return. For intrinsic of _isInterrupted, on Windows, go fastpath only on bit not set.
Reviewed-by: acorn, kvn
Contributed-by: david.holmes@oracle.com, yumin.qi@oracle.com
| author | minqi |
|---|---|
| date | Wed, 26 Feb 2014 15:20:41 -0800 |
| parents | f9e35a9dc8c7 |
| children | 524b54a7f1b5 152cf4afc11f |
| rev | line source |
|---|---|
| 0 | 1 /* |
|
17709
f9e35a9dc8c7
8033792: AltHashing used jint for imprecise bit shifting
minqi
parents:
17467
diff
changeset
|
2 * Copyright (c) 2003, 2014, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
0
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_UTILITIES_HASHTABLE_HPP |
| 26 #define SHARE_VM_UTILITIES_HASHTABLE_HPP | |
| 27 | |
|
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
28 #include "classfile/classLoaderData.hpp" |
| 1972 | 29 #include "memory/allocation.hpp" |
| 30 #include "oops/oop.hpp" | |
|
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
31 #include "oops/symbol.hpp" |
| 1972 | 32 #include "runtime/handles.hpp" |
| 33 | |
| 0 | 34 // This is a generic hashtable, designed to be used for the symbol |
| 35 // and string tables. | |
| 36 // | |
| 37 // It is implemented as an open hash table with a fixed number of buckets. | |
| 38 // | |
| 39 // %note: | |
| 40 // - TableEntrys are allocated in blocks to reduce the space overhead. | |
| 41 | |
| 42 | |
| 43 | |
| 6197 | 44 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> { |
| 0 | 45 friend class VMStructs; |
| 46 private: | |
| 47 unsigned int _hash; // 32-bit hash for item | |
| 48 | |
| 49 // Link to next element in the linked list for this bucket. EXCEPT | |
| 50 // bit 0 set indicates that this entry is shared and must not be | |
| 51 // unlinked from the table. Bit 0 is set during the dumping of the | |
| 52 // archive. Since shared entries are immutable, _next fields in the | |
| 53 // shared entries will not change. New entries will always be | |
| 54 // unshared and since pointers are align, bit 0 will always remain 0 | |
| 55 // with no extra effort. | |
| 6197 | 56 BasicHashtableEntry<F>* _next; |
| 0 | 57 |
| 58 // Windows IA64 compiler requires subclasses to be able to access these | |
| 59 protected: | |
| 60 // Entry objects should not be created, they should be taken from the | |
| 61 // free list with BasicHashtable.new_entry(). | |
| 62 BasicHashtableEntry() { ShouldNotReachHere(); } | |
| 63 // Entry objects should not be destroyed. They should be placed on | |
| 64 // the free list instead with BasicHashtable.free_entry(). | |
| 65 ~BasicHashtableEntry() { ShouldNotReachHere(); } | |
| 66 | |
| 67 public: | |
| 68 | |
| 69 unsigned int hash() const { return _hash; } | |
| 70 void set_hash(unsigned int hash) { _hash = hash; } | |
| 71 unsigned int* hash_addr() { return &_hash; } | |
| 72 | |
| 6197 | 73 static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) { |
| 0 | 74 return (BasicHashtableEntry*)((intptr_t)p & -2); |
| 75 } | |
| 76 | |
| 6197 | 77 BasicHashtableEntry<F>* next() const { |
| 0 | 78 return make_ptr(_next); |
| 79 } | |
| 80 | |
| 6197 | 81 void set_next(BasicHashtableEntry<F>* next) { |
| 0 | 82 _next = next; |
| 83 } | |
| 84 | |
| 6197 | 85 BasicHashtableEntry<F>** next_addr() { |
| 0 | 86 return &_next; |
| 87 } | |
| 88 | |
| 89 bool is_shared() const { | |
| 90 return ((intptr_t)_next & 1) != 0; | |
| 91 } | |
| 92 | |
| 93 void set_shared() { | |
| 6197 | 94 _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1); |
| 0 | 95 } |
| 96 }; | |
| 97 | |
| 98 | |
| 99 | |
| 6197 | 100 template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> { |
| 0 | 101 friend class VMStructs; |
| 102 private: | |
|
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
103 T _literal; // ref to item in table. |
| 0 | 104 |
| 105 public: | |
| 106 // Literal | |
|
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
107 T literal() const { return _literal; } |
|
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
108 T* literal_addr() { return &_literal; } |
|
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
109 void set_literal(T s) { _literal = s; } |
| 0 | 110 |
| 111 HashtableEntry* next() const { | |
| 6197 | 112 return (HashtableEntry*)BasicHashtableEntry<F>::next(); |
| 0 | 113 } |
| 114 HashtableEntry** next_addr() { | |
| 6197 | 115 return (HashtableEntry**)BasicHashtableEntry<F>::next_addr(); |
| 0 | 116 } |
| 117 }; | |
| 118 | |
| 119 | |
| 120 | |
| 6197 | 121 template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> { |
| 0 | 122 friend class VMStructs; |
| 123 private: | |
| 124 // Instance variable | |
| 6197 | 125 BasicHashtableEntry<F>* _entry; |
| 0 | 126 |
| 127 public: | |
| 128 // Accessing | |
| 129 void clear() { _entry = NULL; } | |
| 130 | |
| 131 // The following methods use order access methods to avoid race | |
| 132 // conditions in multiprocessor systems. | |
| 6197 | 133 BasicHashtableEntry<F>* get_entry() const; |
| 134 void set_entry(BasicHashtableEntry<F>* l); | |
| 0 | 135 |
| 136 // The following method is not MT-safe and must be done under lock. | |
| 6197 | 137 BasicHashtableEntry<F>** entry_addr() { return &_entry; } |
| 0 | 138 }; |
| 139 | |
| 140 | |
| 6197 | 141 template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> { |
| 0 | 142 friend class VMStructs; |
| 143 | |
| 144 public: | |
| 145 BasicHashtable(int table_size, int entry_size); | |
| 146 BasicHashtable(int table_size, int entry_size, | |
| 6197 | 147 HashtableBucket<F>* buckets, int number_of_entries); |
| 0 | 148 |
| 149 // Sharing support. | |
| 150 void copy_buckets(char** top, char* end); | |
| 151 void copy_table(char** top, char* end); | |
| 152 | |
| 153 // Bucket handling | |
| 154 int hash_to_index(unsigned int full_hash) { | |
| 155 int h = full_hash % _table_size; | |
| 156 assert(h >= 0 && h < _table_size, "Illegal hash value"); | |
| 157 return h; | |
| 158 } | |
| 159 | |
| 160 // Reverse the order of elements in each of the buckets. | |
| 161 void reverse(); | |
| 162 | |
| 163 private: | |
| 164 // Instance variables | |
| 165 int _table_size; | |
| 6197 | 166 HashtableBucket<F>* _buckets; |
| 167 BasicHashtableEntry<F>* _free_list; | |
| 0 | 168 char* _first_free_entry; |
| 169 char* _end_block; | |
| 170 int _entry_size; | |
| 171 int _number_of_entries; | |
| 172 | |
| 173 protected: | |
| 174 | |
| 175 #ifdef ASSERT | |
| 176 int _lookup_count; | |
| 177 int _lookup_length; | |
| 178 void verify_lookup_length(double load); | |
| 179 #endif | |
| 180 | |
| 6162 | 181 enum { |
| 182 rehash_count = 100, | |
| 183 rehash_multiple = 60 | |
| 184 }; | |
| 185 | |
| 0 | 186 void initialize(int table_size, int entry_size, int number_of_entries); |
| 187 | |
| 188 // Accessor | |
| 189 int entry_size() const { return _entry_size; } | |
| 190 | |
| 191 // The following method is MT-safe and may be used with caution. | |
| 6197 | 192 BasicHashtableEntry<F>* bucket(int i); |
| 0 | 193 |
| 194 // The following method is not MT-safe and must be done under lock. | |
| 6197 | 195 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); } |
| 0 | 196 |
| 197 // Table entry management | |
| 6197 | 198 BasicHashtableEntry<F>* new_entry(unsigned int hashValue); |
| 0 | 199 |
| 6162 | 200 // Check that the table is unbalanced |
| 201 bool check_rehash_table(int count); | |
| 202 | |
| 203 // Used when moving the entry to another table | |
| 204 // Clean up links, but do not add to free_list | |
| 6197 | 205 void unlink_entry(BasicHashtableEntry<F>* entry) { |
| 6162 | 206 entry->set_next(NULL); |
| 207 --_number_of_entries; | |
| 208 } | |
| 209 | |
| 210 // Move over freelist and free block for allocation | |
| 211 void copy_freelist(BasicHashtable* src) { | |
| 212 _free_list = src->_free_list; | |
| 213 src->_free_list = NULL; | |
| 214 _first_free_entry = src->_first_free_entry; | |
| 215 src->_first_free_entry = NULL; | |
| 216 _end_block = src->_end_block; | |
| 217 src->_end_block = NULL; | |
| 218 } | |
| 219 | |
| 220 // Free the buckets in this hashtable | |
|
6172
246d977b51f2
7178670: runtime/7158800/BadUtf8.java fails in SymbolTable::rehash_table
coleenp
parents:
6162
diff
changeset
|
221 void free_buckets(); |
| 6162 | 222 |
| 0 | 223 public: |
|
4864
b2cd0ee8f778
7114376: Make system dictionary hashtable bucket array size configurable
acorn
parents:
2426
diff
changeset
|
224 int table_size() { return _table_size; } |
| 6197 | 225 void set_entry(int index, BasicHashtableEntry<F>* entry); |
| 0 | 226 |
| 6197 | 227 void add_entry(int index, BasicHashtableEntry<F>* entry); |
| 0 | 228 |
| 6197 | 229 void free_entry(BasicHashtableEntry<F>* entry); |
| 0 | 230 |
| 231 int number_of_entries() { return _number_of_entries; } | |
| 232 | |
| 233 void verify() PRODUCT_RETURN; | |
| 234 }; | |
| 235 | |
| 236 | |
| 6197 | 237 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> { |
| 0 | 238 friend class VMStructs; |
| 239 | |
| 240 public: | |
| 241 Hashtable(int table_size, int entry_size) | |
| 6197 | 242 : BasicHashtable<F>(table_size, entry_size) { } |
| 0 | 243 |
| 244 Hashtable(int table_size, int entry_size, | |
| 6197 | 245 HashtableBucket<F>* buckets, int number_of_entries) |
| 246 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { } | |
| 0 | 247 |
| 248 // Debugging | |
| 249 void print() PRODUCT_RETURN; | |
| 250 | |
| 251 // Reverse the order of elements in each of the buckets. Hashtable | |
| 252 // entries which refer to objects at a lower address than 'boundary' | |
| 253 // are separated from those which refer to objects at higher | |
| 254 // addresses, and appear first in the list. | |
| 255 void reverse(void* boundary = NULL); | |
| 256 | |
| 257 protected: | |
| 258 | |
|
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
259 unsigned int compute_hash(Symbol* name) { |
| 0 | 260 return (unsigned int) name->identity_hash(); |
| 261 } | |
| 262 | |
|
2177
3582bf76420e
6990754: Use native memory and reference counting to implement SymbolTable
coleenp
parents:
1972
diff
changeset
|
263 int index_for(Symbol* name) { |
|
6260
5e2dc722e70d
7186278: Build error after CR#6995781 / 7151532 with GCC 4.7.0
andrew
parents:
6201
diff
changeset
|
264 return this->hash_to_index(compute_hash(name)); |
| 0 | 265 } |
| 266 | |
| 267 // Table entry management | |
| 6197 | 268 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj); |
| 0 | 269 |
| 270 // The following method is MT-safe and may be used with caution. | |
| 6197 | 271 HashtableEntry<T, F>* bucket(int i) { |
| 272 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i); | |
| 0 | 273 } |
| 274 | |
| 275 // The following method is not MT-safe and must be done under lock. | |
| 6197 | 276 HashtableEntry<T, F>** bucket_addr(int i) { |
| 277 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i); | |
| 0 | 278 } |
| 6162 | 279 |
| 280 // Function to move these elements into the new table. | |
| 6197 | 281 void move_to(Hashtable<T, F>* new_table); |
|
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
282 static bool use_alternate_hashcode() { return _seed != 0; } |
|
17709
f9e35a9dc8c7
8033792: AltHashing used jint for imprecise bit shifting
minqi
parents:
17467
diff
changeset
|
283 static juint seed() { return _seed; } |
|
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
284 |
|
10312
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
285 static int literal_size(Symbol *symbol); |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
286 static int literal_size(oop oop); |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
287 |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
288 // The following two are currently not used, but are needed anyway because some |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
289 // C++ compilers (MacOS and Solaris) force the instantiation of |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
290 // Hashtable<ConstantPool*, mtClass>::dump_table() even though we never call this function |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
291 // in the VM code. |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
292 static int literal_size(ConstantPool *cp) {Unimplemented(); return 0;} |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
293 static int literal_size(Klass *k) {Unimplemented(); return 0;} |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
294 |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
295 public: |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
296 void dump_table(outputStream* st, const char *table_name); |
|
a5d6f0c3585f
8014262: PrintStringTableStatistics should include more footprint info
iklam
parents:
6725
diff
changeset
|
297 |
|
6201
ace99a6ffc83
7181200: JVM new hashing code breaks SA in product mode
coleenp
parents:
6197
diff
changeset
|
298 private: |
|
17709
f9e35a9dc8c7
8033792: AltHashing used jint for imprecise bit shifting
minqi
parents:
17467
diff
changeset
|
299 static juint _seed; |
| 0 | 300 }; |
| 301 | |
| 302 | |
| 303 // Verions of hashtable where two handles are used to compute the index. | |
| 304 | |
| 6197 | 305 template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> { |
| 0 | 306 friend class VMStructs; |
| 307 protected: | |
| 308 TwoOopHashtable(int table_size, int entry_size) | |
| 6197 | 309 : Hashtable<T, F>(table_size, entry_size) {} |
| 0 | 310 |
| 6197 | 311 TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t, |
| 0 | 312 int number_of_entries) |
| 6197 | 313 : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {} |
| 0 | 314 |
| 315 public: | |
|
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
316 unsigned int compute_hash(Symbol* name, ClassLoaderData* loader_data) { |
| 0 | 317 unsigned int name_hash = name->identity_hash(); |
|
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
318 // loader is null with CDS |
|
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
319 assert(loader_data != NULL || UseSharedSpaces || DumpSharedSpaces, |
|
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
320 "only allowed with shared spaces"); |
|
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
321 unsigned int loader_hash = loader_data == NULL ? 0 : loader_data->identity_hash(); |
| 0 | 322 return name_hash ^ loader_hash; |
| 323 } | |
| 324 | |
|
6725
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
325 int index_for(Symbol* name, ClassLoaderData* loader_data) { |
|
da91efe96a93
6964458: Reimplement class meta-data storage to use native memory
coleenp
parents:
6260
diff
changeset
|
326 return this->hash_to_index(compute_hash(name, loader_data)); |
| 0 | 327 } |
| 328 }; | |
| 1972 | 329 |
| 330 #endif // SHARE_VM_UTILITIES_HASHTABLE_HPP |