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