|
0
|
1 /*
|
|
|
2 * Copyright 1997-2006 Sun Microsystems, Inc. All Rights Reserved.
|
|
|
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 *
|
|
|
19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
|
|
|
20 * CA 95054 USA or visit www.sun.com if you need additional information or
|
|
|
21 * have any questions.
|
|
|
22 *
|
|
|
23 */
|
|
|
24
|
|
|
25 # include "incls/_precompiled.incl"
|
|
|
26 # include "incls/_symbolTable.cpp.incl"
|
|
|
27
|
|
|
28 // --------------------------------------------------------------------------
|
|
|
29
|
|
|
30 SymbolTable* SymbolTable::_the_table = NULL;
|
|
|
31
|
|
|
32 // Lookup a symbol in a bucket.
|
|
|
33
|
|
|
34 symbolOop SymbolTable::lookup(int index, const char* name,
|
|
|
35 int len, unsigned int hash) {
|
|
|
36 for (HashtableEntry* e = bucket(index); e != NULL; e = e->next()) {
|
|
|
37 if (e->hash() == hash) {
|
|
|
38 symbolOop sym = symbolOop(e->literal());
|
|
|
39 if (sym->equals(name, len)) {
|
|
|
40 return sym;
|
|
|
41 }
|
|
|
42 }
|
|
|
43 }
|
|
|
44 return NULL;
|
|
|
45 }
|
|
|
46
|
|
|
47
|
|
|
48 // We take care not to be blocking while holding the
|
|
|
49 // SymbolTable_lock. Otherwise, the system might deadlock, since the
|
|
|
50 // symboltable is used during compilation (VM_thread) The lock free
|
|
|
51 // synchronization is simplified by the fact that we do not delete
|
|
|
52 // entries in the symbol table during normal execution (only during
|
|
|
53 // safepoints).
|
|
|
54
|
|
|
55 symbolOop SymbolTable::lookup(const char* name, int len, TRAPS) {
|
|
|
56 unsigned int hashValue = hash_symbol(name, len);
|
|
|
57 int index = the_table()->hash_to_index(hashValue);
|
|
|
58
|
|
|
59 symbolOop s = the_table()->lookup(index, name, len, hashValue);
|
|
|
60
|
|
|
61 // Found
|
|
|
62 if (s != NULL) return s;
|
|
|
63
|
|
|
64 // Otherwise, add to symbol to table
|
|
|
65 return the_table()->basic_add(index, (u1*)name, len, hashValue, CHECK_NULL);
|
|
|
66 }
|
|
|
67
|
|
|
68 symbolOop SymbolTable::lookup(symbolHandle sym, int begin, int end, TRAPS) {
|
|
|
69 char* buffer;
|
|
|
70 int index, len;
|
|
|
71 unsigned int hashValue;
|
|
|
72 char* name;
|
|
|
73 {
|
|
|
74 debug_only(No_Safepoint_Verifier nsv;)
|
|
|
75
|
|
|
76 name = (char*)sym->base() + begin;
|
|
|
77 len = end - begin;
|
|
|
78 hashValue = hash_symbol(name, len);
|
|
|
79 index = the_table()->hash_to_index(hashValue);
|
|
|
80 symbolOop s = the_table()->lookup(index, name, len, hashValue);
|
|
|
81
|
|
|
82 // Found
|
|
|
83 if (s != NULL) return s;
|
|
|
84 }
|
|
|
85
|
|
|
86 // Otherwise, add to symbol to table. Copy to a C string first.
|
|
|
87 char stack_buf[128];
|
|
|
88 ResourceMark rm(THREAD);
|
|
|
89 if (len <= 128) {
|
|
|
90 buffer = stack_buf;
|
|
|
91 } else {
|
|
|
92 buffer = NEW_RESOURCE_ARRAY_IN_THREAD(THREAD, char, len);
|
|
|
93 }
|
|
|
94 for (int i=0; i<len; i++) {
|
|
|
95 buffer[i] = name[i];
|
|
|
96 }
|
|
|
97 // Make sure there is no safepoint in the code above since name can't move.
|
|
|
98 // We can't include the code in No_Safepoint_Verifier because of the
|
|
|
99 // ResourceMark.
|
|
|
100
|
|
|
101 return the_table()->basic_add(index, (u1*)buffer, len, hashValue, CHECK_NULL);
|
|
|
102 }
|
|
|
103
|
|
|
104 symbolOop SymbolTable::lookup_only(const char* name, int len,
|
|
|
105 unsigned int& hash) {
|
|
|
106 hash = hash_symbol(name, len);
|
|
|
107 int index = the_table()->hash_to_index(hash);
|
|
|
108
|
|
|
109 return the_table()->lookup(index, name, len, hash);
|
|
|
110 }
|
|
|
111
|
|
|
112 void SymbolTable::add(constantPoolHandle cp, int names_count,
|
|
|
113 const char** names, int* lengths, int* cp_indices,
|
|
|
114 unsigned int* hashValues, TRAPS) {
|
|
|
115 SymbolTable* table = the_table();
|
|
|
116 bool added = table->basic_add(cp, names_count, names, lengths,
|
|
|
117 cp_indices, hashValues, CHECK);
|
|
|
118 if (!added) {
|
|
|
119 // do it the hard way
|
|
|
120 for (int i=0; i<names_count; i++) {
|
|
|
121 int index = table->hash_to_index(hashValues[i]);
|
|
|
122 symbolOop sym = table->basic_add(index, (u1*)names[i], lengths[i],
|
|
|
123 hashValues[i], CHECK);
|
|
|
124 cp->symbol_at_put(cp_indices[i], sym);
|
|
|
125 }
|
|
|
126 }
|
|
|
127 }
|
|
|
128
|
|
|
129 // Needed for preloading classes in signatures when compiling.
|
|
|
130
|
|
|
131 symbolOop SymbolTable::probe(const char* name, int len) {
|
|
|
132 unsigned int hashValue = hash_symbol(name, len);
|
|
|
133 int index = the_table()->hash_to_index(hashValue);
|
|
|
134 return the_table()->lookup(index, name, len, hashValue);
|
|
|
135 }
|
|
|
136
|
|
|
137
|
|
|
138 symbolOop SymbolTable::basic_add(int index, u1 *name, int len,
|
|
|
139 unsigned int hashValue, TRAPS) {
|
|
|
140 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
|
|
|
141 "proposed name of symbol must be stable");
|
|
|
142
|
|
|
143 // We assume that lookup() has been called already, that it failed,
|
|
|
144 // and symbol was not found. We create the symbol here.
|
|
|
145 symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part();
|
|
|
146 symbolOop s_oop = sk->allocate_symbol(name, len, CHECK_NULL);
|
|
|
147 symbolHandle sym (THREAD, s_oop);
|
|
|
148
|
|
|
149 // Allocation must be done before grapping the SymbolTable_lock lock
|
|
|
150 MutexLocker ml(SymbolTable_lock, THREAD);
|
|
|
151
|
|
|
152 assert(sym->equals((char*)name, len), "symbol must be properly initialized");
|
|
|
153
|
|
|
154 // Since look-up was done lock-free, we need to check if another
|
|
|
155 // thread beat us in the race to insert the symbol.
|
|
|
156
|
|
|
157 symbolOop test = lookup(index, (char*)name, len, hashValue);
|
|
|
158 if (test != NULL) {
|
|
605
|
159 // A race occurred and another thread introduced the symbol, this one
|
|
0
|
160 // will be dropped and collected.
|
|
|
161 return test;
|
|
|
162 }
|
|
|
163
|
|
|
164 HashtableEntry* entry = new_entry(hashValue, sym());
|
|
|
165 add_entry(index, entry);
|
|
|
166 return sym();
|
|
|
167 }
|
|
|
168
|
|
|
169 bool SymbolTable::basic_add(constantPoolHandle cp, int names_count,
|
|
|
170 const char** names, int* lengths,
|
|
|
171 int* cp_indices, unsigned int* hashValues,
|
|
|
172 TRAPS) {
|
|
|
173 symbolKlass* sk = (symbolKlass*) Universe::symbolKlassObj()->klass_part();
|
|
|
174 symbolOop sym_oops[symbol_alloc_batch_size];
|
|
|
175 bool allocated = sk->allocate_symbols(names_count, names, lengths,
|
|
|
176 sym_oops, CHECK_false);
|
|
|
177 if (!allocated) {
|
|
|
178 return false;
|
|
|
179 }
|
|
|
180 symbolHandle syms[symbol_alloc_batch_size];
|
|
|
181 int i;
|
|
|
182 for (i=0; i<names_count; i++) {
|
|
|
183 syms[i] = symbolHandle(THREAD, sym_oops[i]);
|
|
|
184 }
|
|
|
185
|
|
|
186 // Allocation must be done before grabbing the SymbolTable_lock lock
|
|
|
187 MutexLocker ml(SymbolTable_lock, THREAD);
|
|
|
188
|
|
|
189 for (i=0; i<names_count; i++) {
|
|
|
190 assert(syms[i]->equals(names[i], lengths[i]), "symbol must be properly initialized");
|
|
|
191 // Since look-up was done lock-free, we need to check if another
|
|
|
192 // thread beat us in the race to insert the symbol.
|
|
|
193 int index = hash_to_index(hashValues[i]);
|
|
|
194 symbolOop test = lookup(index, names[i], lengths[i], hashValues[i]);
|
|
|
195 if (test != NULL) {
|
|
605
|
196 // A race occurred and another thread introduced the symbol, this one
|
|
0
|
197 // will be dropped and collected. Use test instead.
|
|
|
198 cp->symbol_at_put(cp_indices[i], test);
|
|
|
199 } else {
|
|
|
200 symbolOop sym = syms[i]();
|
|
|
201 HashtableEntry* entry = new_entry(hashValues[i], sym);
|
|
|
202 add_entry(index, entry);
|
|
|
203 cp->symbol_at_put(cp_indices[i], sym);
|
|
|
204 }
|
|
|
205 }
|
|
|
206
|
|
|
207 return true;
|
|
|
208 }
|
|
|
209
|
|
|
210
|
|
|
211 void SymbolTable::verify() {
|
|
|
212 for (int i = 0; i < the_table()->table_size(); ++i) {
|
|
|
213 HashtableEntry* p = the_table()->bucket(i);
|
|
|
214 for ( ; p != NULL; p = p->next()) {
|
|
|
215 symbolOop s = symbolOop(p->literal());
|
|
|
216 guarantee(s != NULL, "symbol is NULL");
|
|
|
217 s->verify();
|
|
|
218 guarantee(s->is_perm(), "symbol not in permspace");
|
|
|
219 unsigned int h = hash_symbol((char*)s->bytes(), s->utf8_length());
|
|
|
220 guarantee(p->hash() == h, "broken hash in symbol table entry");
|
|
|
221 guarantee(the_table()->hash_to_index(h) == i,
|
|
|
222 "wrong index in symbol table");
|
|
|
223 }
|
|
|
224 }
|
|
|
225 }
|
|
|
226
|
|
|
227
|
|
|
228 //---------------------------------------------------------------------------
|
|
|
229 // Non-product code
|
|
|
230
|
|
|
231 #ifndef PRODUCT
|
|
|
232
|
|
|
233 void SymbolTable::print_histogram() {
|
|
|
234 MutexLocker ml(SymbolTable_lock);
|
|
|
235 const int results_length = 100;
|
|
|
236 int results[results_length];
|
|
|
237 int i,j;
|
|
|
238
|
|
|
239 // initialize results to zero
|
|
|
240 for (j = 0; j < results_length; j++) {
|
|
|
241 results[j] = 0;
|
|
|
242 }
|
|
|
243
|
|
|
244 int total = 0;
|
|
|
245 int max_symbols = 0;
|
|
|
246 int out_of_range = 0;
|
|
|
247 for (i = 0; i < the_table()->table_size(); i++) {
|
|
|
248 HashtableEntry* p = the_table()->bucket(i);
|
|
|
249 for ( ; p != NULL; p = p->next()) {
|
|
|
250 int counter = symbolOop(p->literal())->utf8_length();
|
|
|
251 total += counter;
|
|
|
252 if (counter < results_length) {
|
|
|
253 results[counter]++;
|
|
|
254 } else {
|
|
|
255 out_of_range++;
|
|
|
256 }
|
|
|
257 max_symbols = MAX2(max_symbols, counter);
|
|
|
258 }
|
|
|
259 }
|
|
|
260 tty->print_cr("Symbol Table:");
|
|
|
261 tty->print_cr("%8s %5d", "Total ", total);
|
|
|
262 tty->print_cr("%8s %5d", "Maximum", max_symbols);
|
|
|
263 tty->print_cr("%8s %3.2f", "Average",
|
|
|
264 ((float) total / (float) the_table()->table_size()));
|
|
|
265 tty->print_cr("%s", "Histogram:");
|
|
|
266 tty->print_cr(" %s %29s", "Length", "Number chains that length");
|
|
|
267 for (i = 0; i < results_length; i++) {
|
|
|
268 if (results[i] > 0) {
|
|
|
269 tty->print_cr("%6d %10d", i, results[i]);
|
|
|
270 }
|
|
|
271 }
|
|
|
272 int line_length = 70;
|
|
|
273 tty->print_cr("%s %30s", " Length", "Number chains that length");
|
|
|
274 for (i = 0; i < results_length; i++) {
|
|
|
275 if (results[i] > 0) {
|
|
|
276 tty->print("%4d", i);
|
|
|
277 for (j = 0; (j < results[i]) && (j < line_length); j++) {
|
|
|
278 tty->print("%1s", "*");
|
|
|
279 }
|
|
|
280 if (j == line_length) {
|
|
|
281 tty->print("%1s", "+");
|
|
|
282 }
|
|
|
283 tty->cr();
|
|
|
284 }
|
|
|
285 }
|
|
|
286 tty->print_cr(" %s %d: %d\n", "Number chains longer than",
|
|
|
287 results_length, out_of_range);
|
|
|
288 }
|
|
|
289
|
|
|
290 #endif // PRODUCT
|
|
|
291
|
|
|
292 // --------------------------------------------------------------------------
|
|
|
293
|
|
|
294 #ifdef ASSERT
|
|
|
295 class StableMemoryChecker : public StackObj {
|
|
|
296 enum { _bufsize = wordSize*4 };
|
|
|
297
|
|
|
298 address _region;
|
|
|
299 jint _size;
|
|
|
300 u1 _save_buf[_bufsize];
|
|
|
301
|
|
|
302 int sample(u1* save_buf) {
|
|
|
303 if (_size <= _bufsize) {
|
|
|
304 memcpy(save_buf, _region, _size);
|
|
|
305 return _size;
|
|
|
306 } else {
|
|
|
307 // copy head and tail
|
|
|
308 memcpy(&save_buf[0], _region, _bufsize/2);
|
|
|
309 memcpy(&save_buf[_bufsize/2], _region + _size - _bufsize/2, _bufsize/2);
|
|
|
310 return (_bufsize/2)*2;
|
|
|
311 }
|
|
|
312 }
|
|
|
313
|
|
|
314 public:
|
|
|
315 StableMemoryChecker(const void* region, jint size) {
|
|
|
316 _region = (address) region;
|
|
|
317 _size = size;
|
|
|
318 sample(_save_buf);
|
|
|
319 }
|
|
|
320
|
|
|
321 bool verify() {
|
|
|
322 u1 check_buf[sizeof(_save_buf)];
|
|
|
323 int check_size = sample(check_buf);
|
|
|
324 return (0 == memcmp(_save_buf, check_buf, check_size));
|
|
|
325 }
|
|
|
326
|
|
|
327 void set_region(const void* region) { _region = (address) region; }
|
|
|
328 };
|
|
|
329 #endif
|
|
|
330
|
|
|
331
|
|
|
332 // --------------------------------------------------------------------------
|
|
|
333
|
|
|
334
|
|
|
335 // Compute the hash value for a java.lang.String object which would
|
|
|
336 // contain the characters passed in. This hash value is used for at
|
|
|
337 // least two purposes.
|
|
|
338 //
|
|
|
339 // (a) As the hash value used by the StringTable for bucket selection
|
|
|
340 // and comparison (stored in the HashtableEntry structures). This
|
|
|
341 // is used in the String.intern() method.
|
|
|
342 //
|
|
|
343 // (b) As the hash value used by the String object itself, in
|
|
|
344 // String.hashCode(). This value is normally calculate in Java code
|
|
|
345 // in the String.hashCode method(), but is precomputed for String
|
|
|
346 // objects in the shared archive file.
|
|
|
347 //
|
|
|
348 // For this reason, THIS ALGORITHM MUST MATCH String.hashCode().
|
|
|
349
|
|
|
350 int StringTable::hash_string(jchar* s, int len) {
|
|
|
351 unsigned h = 0;
|
|
|
352 while (len-- > 0) {
|
|
|
353 h = 31*h + (unsigned) *s;
|
|
|
354 s++;
|
|
|
355 }
|
|
|
356 return h;
|
|
|
357 }
|
|
|
358
|
|
|
359
|
|
|
360 StringTable* StringTable::_the_table = NULL;
|
|
|
361
|
|
|
362 oop StringTable::lookup(int index, jchar* name,
|
|
|
363 int len, unsigned int hash) {
|
|
|
364 for (HashtableEntry* l = bucket(index); l != NULL; l = l->next()) {
|
|
|
365 if (l->hash() == hash) {
|
|
|
366 if (java_lang_String::equals(l->literal(), name, len)) {
|
|
|
367 return l->literal();
|
|
|
368 }
|
|
|
369 }
|
|
|
370 }
|
|
|
371 return NULL;
|
|
|
372 }
|
|
|
373
|
|
|
374
|
|
|
375 oop StringTable::basic_add(int index, Handle string_or_null, jchar* name,
|
|
|
376 int len, unsigned int hashValue, TRAPS) {
|
|
|
377 debug_only(StableMemoryChecker smc(name, len * sizeof(name[0])));
|
|
|
378 assert(!Universe::heap()->is_in_reserved(name) || GC_locker::is_active(),
|
|
|
379 "proposed name of symbol must be stable");
|
|
|
380
|
|
|
381 Handle string;
|
|
|
382 // try to reuse the string if possible
|
|
|
383 if (!string_or_null.is_null() && string_or_null()->is_perm()) {
|
|
|
384 string = string_or_null;
|
|
|
385 } else {
|
|
|
386 string = java_lang_String::create_tenured_from_unicode(name, len, CHECK_NULL);
|
|
|
387 }
|
|
|
388
|
|
|
389 // Allocation must be done before grapping the SymbolTable_lock lock
|
|
|
390 MutexLocker ml(StringTable_lock, THREAD);
|
|
|
391
|
|
|
392 assert(java_lang_String::equals(string(), name, len),
|
|
|
393 "string must be properly initialized");
|
|
|
394
|
|
|
395 // Since look-up was done lock-free, we need to check if another
|
|
|
396 // thread beat us in the race to insert the symbol.
|
|
|
397
|
|
|
398 oop test = lookup(index, name, len, hashValue); // calls lookup(u1*, int)
|
|
|
399 if (test != NULL) {
|
|
|
400 // Entry already added
|
|
|
401 return test;
|
|
|
402 }
|
|
|
403
|
|
|
404 HashtableEntry* entry = new_entry(hashValue, string());
|
|
|
405 add_entry(index, entry);
|
|
|
406 return string();
|
|
|
407 }
|
|
|
408
|
|
|
409
|
|
|
410 oop StringTable::lookup(symbolOop symbol) {
|
|
|
411 ResourceMark rm;
|
|
|
412 int length;
|
|
|
413 jchar* chars = symbol->as_unicode(length);
|
|
|
414 unsigned int hashValue = hash_string(chars, length);
|
|
|
415 int index = the_table()->hash_to_index(hashValue);
|
|
|
416 return the_table()->lookup(index, chars, length, hashValue);
|
|
|
417 }
|
|
|
418
|
|
|
419
|
|
|
420 oop StringTable::intern(Handle string_or_null, jchar* name,
|
|
|
421 int len, TRAPS) {
|
|
|
422 unsigned int hashValue = hash_string(name, len);
|
|
|
423 int index = the_table()->hash_to_index(hashValue);
|
|
|
424 oop string = the_table()->lookup(index, name, len, hashValue);
|
|
|
425
|
|
|
426 // Found
|
|
|
427 if (string != NULL) return string;
|
|
|
428
|
|
|
429 // Otherwise, add to symbol to table
|
|
|
430 return the_table()->basic_add(index, string_or_null, name, len,
|
|
|
431 hashValue, CHECK_NULL);
|
|
|
432 }
|
|
|
433
|
|
|
434 oop StringTable::intern(symbolOop symbol, TRAPS) {
|
|
|
435 if (symbol == NULL) return NULL;
|
|
|
436 ResourceMark rm(THREAD);
|
|
|
437 int length;
|
|
|
438 jchar* chars = symbol->as_unicode(length);
|
|
|
439 Handle string;
|
|
|
440 oop result = intern(string, chars, length, CHECK_NULL);
|
|
|
441 return result;
|
|
|
442 }
|
|
|
443
|
|
|
444
|
|
|
445 oop StringTable::intern(oop string, TRAPS)
|
|
|
446 {
|
|
|
447 if (string == NULL) return NULL;
|
|
|
448 ResourceMark rm(THREAD);
|
|
|
449 int length;
|
|
|
450 Handle h_string (THREAD, string);
|
|
|
451 jchar* chars = java_lang_String::as_unicode_string(string, length);
|
|
|
452 oop result = intern(h_string, chars, length, CHECK_NULL);
|
|
|
453 return result;
|
|
|
454 }
|
|
|
455
|
|
|
456
|
|
|
457 oop StringTable::intern(const char* utf8_string, TRAPS) {
|
|
|
458 if (utf8_string == NULL) return NULL;
|
|
|
459 ResourceMark rm(THREAD);
|
|
|
460 int length = UTF8::unicode_length(utf8_string);
|
|
|
461 jchar* chars = NEW_RESOURCE_ARRAY(jchar, length);
|
|
|
462 UTF8::convert_to_unicode(utf8_string, chars, length);
|
|
|
463 Handle string;
|
|
|
464 oop result = intern(string, chars, length, CHECK_NULL);
|
|
|
465 return result;
|
|
|
466 }
|
|
|
467
|
|
|
468 void StringTable::verify() {
|
|
|
469 for (int i = 0; i < the_table()->table_size(); ++i) {
|
|
|
470 HashtableEntry* p = the_table()->bucket(i);
|
|
|
471 for ( ; p != NULL; p = p->next()) {
|
|
|
472 oop s = p->literal();
|
|
|
473 guarantee(s != NULL, "interned string is NULL");
|
|
|
474 guarantee(s->is_perm(), "interned string not in permspace");
|
|
|
475
|
|
|
476 int length;
|
|
|
477 jchar* chars = java_lang_String::as_unicode_string(s, length);
|
|
|
478 unsigned int h = hash_string(chars, length);
|
|
|
479 guarantee(p->hash() == h, "broken hash in string table entry");
|
|
|
480 guarantee(the_table()->hash_to_index(h) == i,
|
|
|
481 "wrong index in string table");
|
|
|
482 }
|
|
|
483 }
|
|
|
484 }
|
