Mercurial > hg > truffle

comparison src/share/vm/utilities/hashtable.hpp @ 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
38 // %note: 38 // %note:
39 // - TableEntrys are allocated in blocks to reduce the space overhead. 39 // - TableEntrys are allocated in blocks to reduce the space overhead.
40 40
41 41
42 42
43 class BasicHashtableEntry : public CHeapObj { 43 template <MEMFLAGS F> class BasicHashtableEntry : public CHeapObj<F> {
44 friend class VMStructs; 44 friend class VMStructs;
45 private: 45 private:
46 unsigned int _hash; // 32-bit hash for item 46 unsigned int _hash; // 32-bit hash for item
47 47
48 // Link to next element in the linked list for this bucket. EXCEPT 48 // Link to next element in the linked list for this bucket. EXCEPT
50 // unlinked from the table. Bit 0 is set during the dumping of the 50 // unlinked from the table. Bit 0 is set during the dumping of the
51 // archive. Since shared entries are immutable, _next fields in the 51 // archive. Since shared entries are immutable, _next fields in the
52 // shared entries will not change. New entries will always be 52 // shared entries will not change. New entries will always be
53 // unshared and since pointers are align, bit 0 will always remain 0 53 // unshared and since pointers are align, bit 0 will always remain 0
54 // with no extra effort. 54 // with no extra effort.
55 BasicHashtableEntry* _next; 55 BasicHashtableEntry<F>* _next;
56 56
57 // Windows IA64 compiler requires subclasses to be able to access these 57 // Windows IA64 compiler requires subclasses to be able to access these
58 protected: 58 protected:
59 // Entry objects should not be created, they should be taken from the 59 // Entry objects should not be created, they should be taken from the
60 // free list with BasicHashtable.new_entry(). 60 // free list with BasicHashtable.new_entry().
67 67
68 unsigned int hash() const { return _hash; } 68 unsigned int hash() const { return _hash; }
69 void set_hash(unsigned int hash) { _hash = hash; } 69 void set_hash(unsigned int hash) { _hash = hash; }
70 unsigned int* hash_addr() { return &_hash; } 70 unsigned int* hash_addr() { return &_hash; }
71 71
72 static BasicHashtableEntry* make_ptr(BasicHashtableEntry* p) { 72 static BasicHashtableEntry<F>* make_ptr(BasicHashtableEntry<F>* p) {
73 return (BasicHashtableEntry*)((intptr_t)p & -2); 73 return (BasicHashtableEntry*)((intptr_t)p & -2);
74 } 74 }
75 75
76 BasicHashtableEntry* next() const { 76 BasicHashtableEntry<F>* next() const {
77 return make_ptr(_next); 77 return make_ptr(_next);
78 } 78 }
79 79
80 void set_next(BasicHashtableEntry* next) { 80 void set_next(BasicHashtableEntry<F>* next) {
81 _next = next; 81 _next = next;
82 } 82 }
83 83
84 BasicHashtableEntry** next_addr() { 84 BasicHashtableEntry<F>** next_addr() {
85 return &_next; 85 return &_next;
86 } 86 }
87 87
88 bool is_shared() const { 88 bool is_shared() const {
89 return ((intptr_t)_next & 1) != 0; 89 return ((intptr_t)_next & 1) != 0;
90 } 90 }
91 91
92 void set_shared() { 92 void set_shared() {
93 _next = (BasicHashtableEntry*)((intptr_t)_next | 1); 93 _next = (BasicHashtableEntry<F>*)((intptr_t)_next | 1);
94 } 94 }
95 }; 95 };
96 96
97 97
98 98
99 template <class T> class HashtableEntry : public BasicHashtableEntry { 99 template <class T, MEMFLAGS F> class HashtableEntry : public BasicHashtableEntry<F> {
100 friend class VMStructs; 100 friend class VMStructs;
101 private: 101 private:
102 T _literal; // ref to item in table. 102 T _literal; // ref to item in table.
103 103
104 public: 104 public:
106 T literal() const { return _literal; } 106 T literal() const { return _literal; }
107 T* literal_addr() { return &_literal; } 107 T* literal_addr() { return &_literal; }
108 void set_literal(T s) { _literal = s; } 108 void set_literal(T s) { _literal = s; }
109 109
110 HashtableEntry* next() const { 110 HashtableEntry* next() const {
111 return (HashtableEntry*)BasicHashtableEntry::next(); 111 return (HashtableEntry*)BasicHashtableEntry<F>::next();
112 } 112 }
113 HashtableEntry** next_addr() { 113 HashtableEntry** next_addr() {
114 return (HashtableEntry**)BasicHashtableEntry::next_addr(); 114 return (HashtableEntry**)BasicHashtableEntry<F>::next_addr();
115 } 115 }
116 }; 116 };
117 117
118 118
119 119
120 class HashtableBucket : public CHeapObj { 120 template <MEMFLAGS F> class HashtableBucket : public CHeapObj<F> {
121 friend class VMStructs; 121 friend class VMStructs;
122 private: 122 private:
123 // Instance variable 123 // Instance variable
124 BasicHashtableEntry* _entry; 124 BasicHashtableEntry<F>* _entry;
125 125
126 public: 126 public:
127 // Accessing 127 // Accessing
128 void clear() { _entry = NULL; } 128 void clear() { _entry = NULL; }
129 129
130 // The following methods use order access methods to avoid race 130 // The following methods use order access methods to avoid race
131 // conditions in multiprocessor systems. 131 // conditions in multiprocessor systems.
132 BasicHashtableEntry* get_entry() const; 132 BasicHashtableEntry<F>* get_entry() const;
133 void set_entry(BasicHashtableEntry* l); 133 void set_entry(BasicHashtableEntry<F>* l);
134 134
135 // The following method is not MT-safe and must be done under lock. 135 // The following method is not MT-safe and must be done under lock.
136 BasicHashtableEntry** entry_addr() { return &_entry; } 136 BasicHashtableEntry<F>** entry_addr() { return &_entry; }
137 }; 137 };
138 138
139 139
140 class BasicHashtable : public CHeapObj { 140 template <MEMFLAGS F> class BasicHashtable : public CHeapObj<F> {
141 friend class VMStructs; 141 friend class VMStructs;
142 142
143 public: 143 public:
144 BasicHashtable(int table_size, int entry_size); 144 BasicHashtable(int table_size, int entry_size);
145 BasicHashtable(int table_size, int entry_size, 145 BasicHashtable(int table_size, int entry_size,
146 HashtableBucket* buckets, int number_of_entries); 146 HashtableBucket<F>* buckets, int number_of_entries);
147 147
148 // Sharing support. 148 // Sharing support.
149 void copy_buckets(char** top, char* end); 149 void copy_buckets(char** top, char* end);
150 void copy_table(char** top, char* end); 150 void copy_table(char** top, char* end);
151 151
160 void reverse(); 160 void reverse();
161 161
162 private: 162 private:
163 // Instance variables 163 // Instance variables
164 int _table_size; 164 int _table_size;
165 HashtableBucket* _buckets; 165 HashtableBucket<F>* _buckets;
166 BasicHashtableEntry* _free_list; 166 BasicHashtableEntry<F>* _free_list;
167 char* _first_free_entry; 167 char* _first_free_entry;
168 char* _end_block; 168 char* _end_block;
169 int _entry_size; 169 int _entry_size;
170 int _number_of_entries; 170 int _number_of_entries;
171 171
186 186
187 // Accessor 187 // Accessor
188 int entry_size() const { return _entry_size; } 188 int entry_size() const { return _entry_size; }
189 189
190 // The following method is MT-safe and may be used with caution. 190 // The following method is MT-safe and may be used with caution.
191 BasicHashtableEntry* bucket(int i); 191 BasicHashtableEntry<F>* bucket(int i);
192 192
193 // The following method is not MT-safe and must be done under lock. 193 // The following method is not MT-safe and must be done under lock.
194 BasicHashtableEntry** bucket_addr(int i) { return _buckets[i].entry_addr(); } 194 BasicHashtableEntry<F>** bucket_addr(int i) { return _buckets[i].entry_addr(); }
195 195
196 // Table entry management 196 // Table entry management
197 BasicHashtableEntry* new_entry(unsigned int hashValue); 197 BasicHashtableEntry<F>* new_entry(unsigned int hashValue);
198 198
199 // Check that the table is unbalanced 199 // Check that the table is unbalanced
200 bool check_rehash_table(int count); 200 bool check_rehash_table(int count);
201 201
202 // Used when moving the entry to another table 202 // Used when moving the entry to another table
203 // Clean up links, but do not add to free_list 203 // Clean up links, but do not add to free_list
204 void unlink_entry(BasicHashtableEntry* entry) { 204 void unlink_entry(BasicHashtableEntry<F>* entry) {
205 entry->set_next(NULL); 205 entry->set_next(NULL);
206 --_number_of_entries; 206 --_number_of_entries;
207 } 207 }
208 208
209 // Move over freelist and free block for allocation 209 // Move over freelist and free block for allocation
219 // Free the buckets in this hashtable 219 // Free the buckets in this hashtable
220 void free_buckets(); 220 void free_buckets();
221 221
222 public: 222 public:
223 int table_size() { return _table_size; } 223 int table_size() { return _table_size; }
224 void set_entry(int index, BasicHashtableEntry* entry); 224 void set_entry(int index, BasicHashtableEntry<F>* entry);
225 225
226 void add_entry(int index, BasicHashtableEntry* entry); 226 void add_entry(int index, BasicHashtableEntry<F>* entry);
227 227
228 void free_entry(BasicHashtableEntry* entry); 228 void free_entry(BasicHashtableEntry<F>* entry);
229 229
230 int number_of_entries() { return _number_of_entries; } 230 int number_of_entries() { return _number_of_entries; }
231 231
232 void verify() PRODUCT_RETURN; 232 void verify() PRODUCT_RETURN;
233 }; 233 };
234 234
235 235
236 template <class T> class Hashtable : public BasicHashtable { 236 template <class T, MEMFLAGS F> class Hashtable : public BasicHashtable<F> {
237 friend class VMStructs; 237 friend class VMStructs;
238 238
239 public: 239 public:
240 Hashtable(int table_size, int entry_size) 240 Hashtable(int table_size, int entry_size)
241 : BasicHashtable(table_size, entry_size) { } 241 : BasicHashtable<F>(table_size, entry_size) { }
242 242
243 Hashtable(int table_size, int entry_size, 243 Hashtable(int table_size, int entry_size,
244 HashtableBucket* buckets, int number_of_entries) 244 HashtableBucket<F>* buckets, int number_of_entries)
245 : BasicHashtable(table_size, entry_size, buckets, number_of_entries) { } 245 : BasicHashtable<F>(table_size, entry_size, buckets, number_of_entries) { }
246 246
247 // Debugging 247 // Debugging
248 void print() PRODUCT_RETURN; 248 void print() PRODUCT_RETURN;
249 249
250 // Reverse the order of elements in each of the buckets. Hashtable 250 // Reverse the order of elements in each of the buckets. Hashtable
262 int index_for(Symbol* name) { 262 int index_for(Symbol* name) {
263 return hash_to_index(compute_hash(name)); 263 return hash_to_index(compute_hash(name));
264 } 264 }
265 265
266 // Table entry management 266 // Table entry management
267 HashtableEntry<T>* new_entry(unsigned int hashValue, T obj); 267 HashtableEntry<T, F>* new_entry(unsigned int hashValue, T obj);
268 268
269 // The following method is MT-safe and may be used with caution. 269 // The following method is MT-safe and may be used with caution.
270 HashtableEntry<T>* bucket(int i) { 270 HashtableEntry<T, F>* bucket(int i) {
271 return (HashtableEntry<T>*)BasicHashtable::bucket(i); 271 return (HashtableEntry<T, F>*)BasicHashtable<F>::bucket(i);
272 } 272 }
273 273
274 // The following method is not MT-safe and must be done under lock. 274 // The following method is not MT-safe and must be done under lock.
275 HashtableEntry<T>** bucket_addr(int i) { 275 HashtableEntry<T, F>** bucket_addr(int i) {
276 return (HashtableEntry<T>**)BasicHashtable::bucket_addr(i); 276 return (HashtableEntry<T, F>**)BasicHashtable<F>::bucket_addr(i);
277 } 277 }
278 278
279 // Function to move these elements into the new table. 279 // Function to move these elements into the new table.
280 void move_to(Hashtable<T>* new_table); 280 void move_to(Hashtable<T, F>* new_table);
281 virtual unsigned int new_hash(T) { ShouldNotReachHere(); return 0; } // should be overridden 281 virtual unsigned int new_hash(T) { ShouldNotReachHere(); return 0; } // should be overridden
282 }; 282 };
283 283
284 284
285 // Verions of hashtable where two handles are used to compute the index. 285 // Verions of hashtable where two handles are used to compute the index.
286 286
287 template <class T> class TwoOopHashtable : public Hashtable<T> { 287 template <class T, MEMFLAGS F> class TwoOopHashtable : public Hashtable<T, F> {
288 friend class VMStructs; 288 friend class VMStructs;
289 protected: 289 protected:
290 TwoOopHashtable(int table_size, int entry_size) 290 TwoOopHashtable(int table_size, int entry_size)
291 : Hashtable<T>(table_size, entry_size) {} 291 : Hashtable<T, F>(table_size, entry_size) {}
292 292
293 TwoOopHashtable(int table_size, int entry_size, HashtableBucket* t, 293 TwoOopHashtable(int table_size, int entry_size, HashtableBucket<F>* t,
294 int number_of_entries) 294 int number_of_entries)
295 : Hashtable<T>(table_size, entry_size, t, number_of_entries) {} 295 : Hashtable<T, F>(table_size, entry_size, t, number_of_entries) {}
296 296
297 public: 297 public:
298 unsigned int compute_hash(Symbol* name, Handle loader) { 298 unsigned int compute_hash(Symbol* name, Handle loader) {
299 // Be careful with identity_hash(), it can safepoint and if this 299 // Be careful with identity_hash(), it can safepoint and if this
300 // were one expression, the compiler could choose to unhandle each 300 // were one expression, the compiler could choose to unhandle each