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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP
26 #define SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP
27
28 #include "oops/array.hpp"
29 #include "oops/symbol.hpp"
30 #include "utilities/hashtable.hpp"
31
32 template <class T, class N> class CompactHashtable;
33 class NumberSeq;
34 class SimpleCompactHashtable;
35 class SerializeClosure;
36
37 // Stats for symbol tables in the CDS archive
38 class CompactHashtableStats {
39 public:
40 int hashentry_count;
41 int hashentry_bytes;
42 int bucket_count;
43 int bucket_bytes;
44 };
45
46 /////////////////////////////////////////////////////////////////////////
47 //
48 // The compact hash table writer. Used at dump time for writing out
49 // the compact table to the shared archive.
50 //
51 // At dump time, the CompactHashtableWriter obtains all entries from the
52 // symbol/string table and adds them to a new temporary hash table. The hash
91 }
92 }; // class CompactHashtableWriter::Entry
93
94 private:
95 int _num_entries;
96 int _num_buckets;
97 int _num_empty_buckets;
98 int _num_value_only_buckets;
99 int _num_other_buckets;
100 GrowableArray<Entry>** _buckets;
101 CompactHashtableStats* _stats;
102 Array<u4>* _compact_buckets;
103 Array<u4>* _compact_entries;
104
105 public:
106 // This is called at dump-time only
107 CompactHashtableWriter(int num_buckets, CompactHashtableStats* stats);
108 ~CompactHashtableWriter();
109
110 void add(unsigned int hash, u4 value);
111 void add(u4 value) {
112 add((unsigned int)value, value);
113 }
114
115 private:
116 void allocate_table();
117 void dump_table(NumberSeq* summary);
118
119 public:
120 void dump(SimpleCompactHashtable *cht, const char* table_name);
121 const char* table_name();
122 };
123
124 class CompactSymbolTableWriter: public CompactHashtableWriter {
125 public:
126 CompactSymbolTableWriter(int num_buckets, CompactHashtableStats* stats) :
127 CompactHashtableWriter(num_buckets, stats) {}
128 void add(unsigned int hash, Symbol *symbol);
129 void dump(CompactHashtable<Symbol*, char> *cht);
130 };
131
132 class CompactStringTableWriter: public CompactHashtableWriter {
133 public:
134 CompactStringTableWriter(int num_entries, CompactHashtableStats* stats) :
135 CompactHashtableWriter(num_entries, stats) {}
136 void add(unsigned int hash, oop string);
137 void dump(CompactHashtable<oop, char> *cht);
138 };
139
140 #define REGULAR_BUCKET_TYPE 0
141 #define VALUE_ONLY_BUCKET_TYPE 1
142 #define TABLEEND_BUCKET_TYPE 3
143 #define BUCKET_OFFSET_MASK 0x3FFFFFFF
144 #define BUCKET_OFFSET(info) ((info) & BUCKET_OFFSET_MASK)
145 #define BUCKET_TYPE_SHIFT 30
146 #define BUCKET_TYPE(info) (((info) & ~BUCKET_OFFSET_MASK) >> BUCKET_TYPE_SHIFT)
147 #define BUCKET_INFO(offset, type) (((type) << BUCKET_TYPE_SHIFT) | ((offset) & BUCKET_OFFSET_MASK))
148
149 /////////////////////////////////////////////////////////////////////////////
150 //
151 // CompactHashtable is used to stored the CDS archive's symbol/string table. Used
152 // at runtime only to access the compact table from the archive.
153 //
154 // Because these tables are read-only (no entries can be added/deleted) at run-time
155 // and tend to have large number of entries, we try to minimize the footprint
156 // cost per entry.
157 //
158 // The CompactHashtable is split into two arrays
159 //
160 // u4 buckets[num_buckets+1]; // bit[31,30]: type; bit[29-0]: offset
161 // u4 entries[<variable size>]
162 //
163 // The size of buckets[] is 'num_buckets + 1'. Each entry of
164 // buckets[] is a 32-bit encoding of the bucket type and bucket offset,
165 // with the type in the left-most 2-bit and offset in the remaining 30-bit.
166 // The last entry is a special type. It contains the end of the last
167 // bucket.
168 //
169 // There are two types of buckets, regular buckets and value_only buckets. The
170 // value_only buckets have '01' in their highest 2-bit, and regular buckets have
171 // '00' in their highest 2-bit.
172 //
208 _bucket_count = 0;
209 _buckets = 0;
210 _entries = 0;
211 }
212
213 void reset() {
214 _bucket_count = 0;
215 _entry_count = 0;
216 _buckets = 0;
217 _entries = 0;
218 }
219
220 void init(address base_address, u4 entry_count, u4 bucket_count, u4* buckets, u4* entries) {
221 _base_address = base_address;
222 _bucket_count = bucket_count;
223 _entry_count = entry_count;
224 _buckets = buckets;
225 _entries = entries;
226 }
227
228 template <class I> inline void iterate(const I& iterator);
229
230 bool exists(u4 value);
231
232 // For reading from/writing to the CDS archive
233 void serialize(SerializeClosure* soc);
234
235 inline bool empty() {
236 return (_entry_count == 0);
237 }
238 };
239
240 template <class T, class N> class CompactHashtable : public SimpleCompactHashtable {
241 friend class VMStructs;
242
243 public:
244 enum CompactHashtableType {
245 _symbol_table = 0,
246 _string_table = 1
247 };
248
249 private:
250 u4 _type;
251
252 inline Symbol* decode_entry(CompactHashtable<Symbol*, char>* const t,
253 u4 offset, const char* name, int len);
254
255 inline oop decode_entry(CompactHashtable<oop, char>* const t,
256 u4 offset, const char* name, int len);
257 public:
258 CompactHashtable() : SimpleCompactHashtable() {}
259
260 void set_type(CompactHashtableType type) {
261 _type = (u4)type;
262 }
263
264 // Lookup an entry from the compact table
265 inline T lookup(const N* name, unsigned int hash, int len);
266
267 // iterate over symbols
268 void symbols_do(SymbolClosure *cl);
269
270 // iterate over strings
271 void oops_do(OopClosure* f);
272
273 // For reading from/writing to the CDS archive
274 void serialize(SerializeClosure* soc);
275
276 uintx base_address() {
277 return (uintx) _base_address;
278 }
279 };
280
281 ////////////////////////////////////////////////////////////////////////
282 //
283 // Read/Write the contents of a hashtable textual dump (created by
284 // SymbolTable::dump and StringTable::dump).
285 // Because the dump file may be big (hundred of MB in extreme cases),
286 // we use mmap for fast access when reading it.
287 //
288 class HashtableTextDump {
289 int _fd;
290 const char* _base;
291 const char* _p;
292 const char* _end;
293 const char* _filename;
294 size_t _size;
295 int _prefix_type;
296 int _line_no;
297 public:
|
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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP
26 #define SHARE_VM_CLASSFILE_COMPACTHASHTABLE_HPP
27
28 #include "oops/array.hpp"
29 #include "oops/symbol.hpp"
30 #include "utilities/hashtable.hpp"
31
32
33 template <
34 typename K,
35 typename V,
36 V (*DECODE)(address base_address, u4 offset),
37 bool (*EQUALS)(V value, K key, int len)
38 >
39 class CompactHashtable;
40 class NumberSeq;
41 class SimpleCompactHashtable;
42 class SerializeClosure;
43
44 // Stats for symbol tables in the CDS archive
45 class CompactHashtableStats {
46 public:
47 int hashentry_count;
48 int hashentry_bytes;
49 int bucket_count;
50 int bucket_bytes;
51 };
52
53 /////////////////////////////////////////////////////////////////////////
54 //
55 // The compact hash table writer. Used at dump time for writing out
56 // the compact table to the shared archive.
57 //
58 // At dump time, the CompactHashtableWriter obtains all entries from the
59 // symbol/string table and adds them to a new temporary hash table. The hash
98 }
99 }; // class CompactHashtableWriter::Entry
100
101 private:
102 int _num_entries;
103 int _num_buckets;
104 int _num_empty_buckets;
105 int _num_value_only_buckets;
106 int _num_other_buckets;
107 GrowableArray<Entry>** _buckets;
108 CompactHashtableStats* _stats;
109 Array<u4>* _compact_buckets;
110 Array<u4>* _compact_entries;
111
112 public:
113 // This is called at dump-time only
114 CompactHashtableWriter(int num_buckets, CompactHashtableStats* stats);
115 ~CompactHashtableWriter();
116
117 void add(unsigned int hash, u4 value);
118
119 private:
120 void allocate_table();
121 void dump_table(NumberSeq* summary);
122
123 public:
124 void dump(SimpleCompactHashtable *cht, const char* table_name);
125 };
126
127 #define REGULAR_BUCKET_TYPE 0
128 #define VALUE_ONLY_BUCKET_TYPE 1
129 #define TABLEEND_BUCKET_TYPE 3
130 #define BUCKET_OFFSET_MASK 0x3FFFFFFF
131 #define BUCKET_OFFSET(info) ((info) & BUCKET_OFFSET_MASK)
132 #define BUCKET_TYPE_SHIFT 30
133 #define BUCKET_TYPE(info) (((info) & ~BUCKET_OFFSET_MASK) >> BUCKET_TYPE_SHIFT)
134 #define BUCKET_INFO(offset, type) (((type) << BUCKET_TYPE_SHIFT) | ((offset) & BUCKET_OFFSET_MASK))
135
136 /////////////////////////////////////////////////////////////////////////////
137 //
138 // CompactHashtable is used to store the CDS archive's symbol/string tables.
139 //
140 // Because these tables are read-only (no entries can be added/deleted) at run-time
141 // and tend to have large number of entries, we try to minimize the footprint
142 // cost per entry.
143 //
144 // The CompactHashtable is split into two arrays
145 //
146 // u4 buckets[num_buckets+1]; // bit[31,30]: type; bit[29-0]: offset
147 // u4 entries[<variable size>]
148 //
149 // The size of buckets[] is 'num_buckets + 1'. Each entry of
150 // buckets[] is a 32-bit encoding of the bucket type and bucket offset,
151 // with the type in the left-most 2-bit and offset in the remaining 30-bit.
152 // The last entry is a special type. It contains the end of the last
153 // bucket.
154 //
155 // There are two types of buckets, regular buckets and value_only buckets. The
156 // value_only buckets have '01' in their highest 2-bit, and regular buckets have
157 // '00' in their highest 2-bit.
158 //
194 _bucket_count = 0;
195 _buckets = 0;
196 _entries = 0;
197 }
198
199 void reset() {
200 _bucket_count = 0;
201 _entry_count = 0;
202 _buckets = 0;
203 _entries = 0;
204 }
205
206 void init(address base_address, u4 entry_count, u4 bucket_count, u4* buckets, u4* entries) {
207 _base_address = base_address;
208 _bucket_count = bucket_count;
209 _entry_count = entry_count;
210 _buckets = buckets;
211 _entries = entries;
212 }
213
214 // For reading from/writing to the CDS archive
215 void serialize(SerializeClosure* soc);
216
217 inline bool empty() {
218 return (_entry_count == 0);
219 }
220 };
221
222 template <
223 typename K,
224 typename V,
225 V (*DECODE)(address base_address, u4 offset),
226 bool (*EQUALS)(V value, K key, int len)
227 >
228 class CompactHashtable : public SimpleCompactHashtable {
229 friend class VMStructs;
230
231 V decode(u4 offset) const {
232 return DECODE(_base_address, offset);
233 }
234
235 public:
236 CompactHashtable() : SimpleCompactHashtable() {}
237
238 // Lookup a value V from the compact table using key K
239 inline V lookup(K key, unsigned int hash, int len) const {
240 if (_entry_count > 0) {
241 int index = hash % _bucket_count;
242 u4 bucket_info = _buckets[index];
243 u4 bucket_offset = BUCKET_OFFSET(bucket_info);
244 int bucket_type = BUCKET_TYPE(bucket_info);
245 u4* entry = _entries + bucket_offset;
246
247 if (bucket_type == VALUE_ONLY_BUCKET_TYPE) {
248 V value = decode(entry[0]);
249 if (EQUALS(value, key, len)) {
250 return value;
251 }
252 } else {
253 // This is a regular bucket, which has more than one
254 // entries. Each entry is a pair of entry (hash, offset).
255 // Seek until the end of the bucket.
256 u4* entry_max = _entries + BUCKET_OFFSET(_buckets[index + 1]);
257 while (entry < entry_max) {
258 unsigned int h = (unsigned int)(entry[0]);
259 if (h == hash) {
260 V value = decode(entry[1]);
261 if (EQUALS(value, key, len)) {
262 return value;
263 }
264 }
265 entry += 2;
266 }
267 }
268 }
269 return NULL;
270 }
271
272 template <class ITER>
273 inline void iterate(ITER* iter) const {
274 for (u4 i = 0; i < _bucket_count; i++) {
275 u4 bucket_info = _buckets[i];
276 u4 bucket_offset = BUCKET_OFFSET(bucket_info);
277 int bucket_type = BUCKET_TYPE(bucket_info);
278 u4* entry = _entries + bucket_offset;
279
280 if (bucket_type == VALUE_ONLY_BUCKET_TYPE) {
281 iter->do_value(decode(entry[0]));
282 } else {
283 u4*entry_max = _entries + BUCKET_OFFSET(_buckets[i + 1]);
284 while (entry < entry_max) {
285 iter->do_value(decode(entry[1]));
286 entry += 2;
287 }
288 }
289 }
290 }
291 };
292
293 ////////////////////////////////////////////////////////////////////////
294 //
295 // Read/Write the contents of a hashtable textual dump (created by
296 // SymbolTable::dump and StringTable::dump).
297 // Because the dump file may be big (hundred of MB in extreme cases),
298 // we use mmap for fast access when reading it.
299 //
300 class HashtableTextDump {
301 int _fd;
302 const char* _base;
303 const char* _p;
304 const char* _end;
305 const char* _filename;
306 size_t _size;
307 int _prefix_type;
308 int _line_no;
309 public:
|