1 /*
2 * Copyright (c) 2003, 2008, Oracle and/or its affiliates. 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 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 # include "incls/_precompiled.incl"
26 # include "incls/_hashtable.cpp.incl"
27
28 HS_DTRACE_PROBE_DECL4(hs_private, hashtable__new_entry,
29 void*, unsigned int, oop, void*);
30
31 // This is a generic hashtable, designed to be used for the symbol
32 // and string tables.
33 //
34 // It is implemented as an open hash table with a fixed number of buckets.
35 //
36 // %note:
37 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
38
39 BasicHashtableEntry* BasicHashtable::new_entry(unsigned int hashValue) {
40 BasicHashtableEntry* entry;
41
42 if (_free_list) {
43 entry = _free_list;
44 _free_list = _free_list->next();
45 } else {
46 if (_first_free_entry + _entry_size >= _end_block) {
47 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
48 int len = _entry_size * block_size;
49 len = 1 << log2_intptr(len); // round down to power of 2
50 assert(len >= _entry_size, "");
51 _first_free_entry = NEW_C_HEAP_ARRAY(char, len);
52 _end_block = _first_free_entry + len;
53 }
54 entry = (BasicHashtableEntry*)_first_free_entry;
55 _first_free_entry += _entry_size;
56 }
57
58 assert(_entry_size % HeapWordSize == 0, "");
59 entry->set_hash(hashValue);
60 return entry;
61 }
62
63
64 HashtableEntry* Hashtable::new_entry(unsigned int hashValue, oop obj) {
65 HashtableEntry* entry;
66
67 entry = (HashtableEntry*)BasicHashtable::new_entry(hashValue);
68 entry->set_literal(obj); // clears literal string field
69 HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,
70 this, hashValue, obj, entry);
71 return entry;
72 }
73
74
75 // GC support
76
77 void Hashtable::unlink(BoolObjectClosure* is_alive) {
78 // Readers of the table are unlocked, so we should only be removing
79 // entries at a safepoint.
80 assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
81 for (int i = 0; i < table_size(); ++i) {
82 for (HashtableEntry** p = bucket_addr(i); *p != NULL; ) {
83 HashtableEntry* entry = *p;
84 if (entry->is_shared()) {
85 break;
86 }
87 assert(entry->literal() != NULL, "just checking");
88 if (is_alive->do_object_b(entry->literal())) {
89 p = entry->next_addr();
90 } else {
91 *p = entry->next();
92 free_entry(entry);
93 }
94 }
95 }
96 }
97
98
99 void Hashtable::oops_do(OopClosure* f) {
100 for (int i = 0; i < table_size(); ++i) {
101 HashtableEntry** p = bucket_addr(i);
102 HashtableEntry* entry = bucket(i);
103 while (entry != NULL) {
104 f->do_oop(entry->literal_addr());
105
106 // Did the closure remove the literal from the table?
107 if (entry->literal() == NULL) {
108 assert(!entry->is_shared(), "immutable hashtable entry?");
109 *p = entry->next();
110 free_entry(entry);
111 } else {
112 p = entry->next_addr();
113 }
114 entry = (HashtableEntry*)HashtableEntry::make_ptr(*p);
115 }
116 }
117 }
118
119
120 // Reverse the order of elements in the hash buckets.
121
122 void BasicHashtable::reverse() {
123
124 for (int i = 0; i < _table_size; ++i) {
125 BasicHashtableEntry* new_list = NULL;
126 BasicHashtableEntry* p = bucket(i);
127 while (p != NULL) {
128 BasicHashtableEntry* next = p->next();
129 p->set_next(new_list);
130 new_list = p;
131 p = next;
132 }
133 *bucket_addr(i) = new_list;
134 }
135 }
136
137
138 // Copy the table to the shared space.
139
140 void BasicHashtable::copy_table(char** top, char* end) {
141
142 // Dump the hash table entries.
143
144 intptr_t *plen = (intptr_t*)(*top);
145 *top += sizeof(*plen);
146
147 int i;
148 for (i = 0; i < _table_size; ++i) {
149 for (BasicHashtableEntry** p = _buckets[i].entry_addr();
150 *p != NULL;
151 p = (*p)->next_addr()) {
152 if (*top + entry_size() > end) {
153 warning("\nThe shared miscellaneous data space is not large "
154 "enough to \npreload requested classes. Use "
155 "-XX:SharedMiscDataSize= to increase \nthe initial "
156 "size of the miscellaneous data space.\n");
157 exit(2);
158 }
159 *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());
160 *top += entry_size();
161 }
162 }
163 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
164
165 // Set the shared bit.
166
167 for (i = 0; i < _table_size; ++i) {
168 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
169 p->set_shared();
170 }
171 }
172 }
173
174
175
176 // Reverse the order of elements in the hash buckets.
177
178 void Hashtable::reverse(void* boundary) {
179
180 for (int i = 0; i < table_size(); ++i) {
181 HashtableEntry* high_list = NULL;
182 HashtableEntry* low_list = NULL;
183 HashtableEntry* last_low_entry = NULL;
184 HashtableEntry* p = bucket(i);
185 while (p != NULL) {
186 HashtableEntry* next = p->next();
187 if ((void*)p->literal() >= boundary) {
188 p->set_next(high_list);
189 high_list = p;
190 } else {
191 p->set_next(low_list);
192 low_list = p;
193 if (last_low_entry == NULL) {
194 last_low_entry = p;
195 }
196 }
197 p = next;
198 }
199 if (low_list != NULL) {
200 *bucket_addr(i) = low_list;
201 last_low_entry->set_next(high_list);
202 } else {
203 *bucket_addr(i) = high_list;
204 }
205 }
206 }
207
208
209 // Dump the hash table buckets.
210
211 void BasicHashtable::copy_buckets(char** top, char* end) {
212 intptr_t len = _table_size * sizeof(HashtableBucket);
213 *(intptr_t*)(*top) = len;
214 *top += sizeof(intptr_t);
215
216 *(intptr_t*)(*top) = _number_of_entries;
217 *top += sizeof(intptr_t);
218
219 if (*top + len > end) {
220 warning("\nThe shared miscellaneous data space is not large "
221 "enough to \npreload requested classes. Use "
222 "-XX:SharedMiscDataSize= to increase \nthe initial "
223 "size of the miscellaneous data space.\n");
224 exit(2);
225 }
226 _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);
227 *top += len;
228 }
229
230
231 #ifndef PRODUCT
232
233 void Hashtable::print() {
234 ResourceMark rm;
235
236 for (int i = 0; i < table_size(); i++) {
237 HashtableEntry* entry = bucket(i);
238 while(entry != NULL) {
239 tty->print("%d : ", i);
240 entry->literal()->print();
241 tty->cr();
242 entry = entry->next();
243 }
244 }
245 }
246
247
248 void BasicHashtable::verify() {
249 int count = 0;
250 for (int i = 0; i < table_size(); i++) {
251 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
252 ++count;
253 }
254 }
255 assert(count == number_of_entries(), "number of hashtable entries incorrect");
256 }
257
258
259 #endif // PRODUCT
260
261
262 #ifdef ASSERT
263
264 void BasicHashtable::verify_lookup_length(double load) {
265 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
266 warning("Performance bug: SystemDictionary lookup_count=%d "
267 "lookup_length=%d average=%lf load=%f",
268 _lookup_count, _lookup_length,
269 (double) _lookup_length / _lookup_count, load);
270 }
271 }
272
273 #endif