1 /*
  2  * Copyright (c) 2003, 2019, 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 "classfile/altHashing.hpp"
 27 #include "classfile/dictionary.hpp"
 28 #include "classfile/javaClasses.inline.hpp"
 29 #include "classfile/moduleEntry.hpp"
 30 #include "classfile/packageEntry.hpp"
 31 #include "classfile/placeholders.hpp"
 32 #include "classfile/protectionDomainCache.hpp"
 33 #include "classfile/stringTable.hpp"
 34 #include "code/nmethod.hpp"
 35 #include "logging/log.hpp"
 36 #include "memory/allocation.inline.hpp"
 37 #include "memory/resourceArea.hpp"
 38 #include "oops/oop.inline.hpp"
 39 #include "oops/weakHandle.inline.hpp"
 40 #include "runtime/safepoint.hpp"
 41 #include "utilities/dtrace.hpp"
 42 #include "utilities/hashtable.hpp"
 43 #include "utilities/hashtable.inline.hpp"
 44 #include "utilities/numberSeq.hpp"
 45 
 46 
 47 // This hashtable is implemented as an open hash table with a fixed number of buckets.
 48 
 49 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry_free_list() {
 50   BasicHashtableEntry<F>* entry = NULL;
 51   if (_free_list != NULL) {
 52     entry = _free_list;
 53     _free_list = _free_list->next();
 54   }
 55   return entry;
 56 }
 57 
 58 // HashtableEntrys are allocated in blocks to reduce the space overhead.
 59 template <MEMFLAGS F> BasicHashtableEntry<F>* BasicHashtable<F>::new_entry(unsigned int hashValue) {
 60   BasicHashtableEntry<F>* entry = new_entry_free_list();
 61 
 62   if (entry == NULL) {
 63     if (_first_free_entry + _entry_size >= _end_block) {
 64       int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
 65       int len = _entry_size * block_size;
 66       len = 1 << log2_int(len); // round down to power of 2
 67       assert(len >= _entry_size, "");
 68       _first_free_entry = NEW_C_HEAP_ARRAY2(char, len, F, CURRENT_PC);
 69       _entry_blocks->append(_first_free_entry);
 70       _end_block = _first_free_entry + len;
 71     }
 72     entry = (BasicHashtableEntry<F>*)_first_free_entry;
 73     _first_free_entry += _entry_size;
 74   }
 75 
 76   assert(_entry_size % HeapWordSize == 0, "");
 77   entry->set_hash(hashValue);
 78   return entry;
 79 }
 80 
 81 
 82 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::new_entry(unsigned int hashValue, T obj) {
 83   HashtableEntry<T, F>* entry;
 84 
 85   entry = (HashtableEntry<T, F>*)BasicHashtable<F>::new_entry(hashValue);
 86   entry->set_literal(obj);
 87   return entry;
 88 }
 89 
 90 // Version of hashtable entry allocation that allocates in the C heap directly.
 91 // The block allocator in BasicHashtable has less fragmentation, but the memory is not freed until
 92 // the whole table is freed. Use allocate_new_entry() if you want to individually free the memory
 93 // used by each entry
 94 template <class T, MEMFLAGS F> HashtableEntry<T, F>* Hashtable<T, F>::allocate_new_entry(unsigned int hashValue, T obj) {
 95   HashtableEntry<T, F>* entry = (HashtableEntry<T, F>*) NEW_C_HEAP_ARRAY(char, this->entry_size(), F);
 96 
 97   entry->set_hash(hashValue);
 98   entry->set_literal(obj);
 99   entry->set_next(NULL);
100   return entry;
101 }
102 
103 template <MEMFLAGS F> void BasicHashtable<F>::free_buckets() {
104   FREE_C_HEAP_ARRAY(HashtableBucket, _buckets);
105   _buckets = NULL;
106 }
107 
108 // For oops and Strings the size of the literal is interesting. For other types, nobody cares.
109 static int literal_size(ConstantPool*) { return 0; }
110 static int literal_size(Klass*)        { return 0; }
111 static int literal_size(nmethod*)      { return 0; }
112 
113 static int literal_size(Symbol *symbol) {
114   return symbol->size() * HeapWordSize;
115 }
116 
117 static int literal_size(oop obj) {
118   // NOTE: this would over-count if (pre-JDK8) java_lang_Class::has_offset_field() is true,
119   // and the String.value array is shared by several Strings. However, starting from JDK8,
120   // the String.value array is not shared anymore.
121   if (obj == NULL) {
122     return 0;
123   } else if (obj->klass() == SystemDictionary::String_klass()) {
124     return (obj->size() + java_lang_String::value(obj)->size()) * HeapWordSize;
125   } else {
126     return obj->size();
127   }
128 }
129 
130 static int literal_size(WeakHandle<vm_class_loader_data> v) {
131   return literal_size(v.peek());
132 }
133 
134 template <MEMFLAGS F> bool BasicHashtable<F>::resize(int new_size) {
135   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
136 
137   // Allocate new buckets
138   HashtableBucket<F>* buckets_new = NEW_C_HEAP_ARRAY2_RETURN_NULL(HashtableBucket<F>, new_size, F, CURRENT_PC);
139   if (buckets_new == NULL) {
140     return false;
141   }
142 
143   // Clear the new buckets
144   for (int i = 0; i < new_size; i++) {
145     buckets_new[i].clear();
146   }
147 
148   int table_size_old = _table_size;
149   // hash_to_index() uses _table_size, so switch the sizes now
150   _table_size = new_size;
151 
152   // Move entries from the old table to a new table
153   for (int index_old = 0; index_old < table_size_old; index_old++) {
154     for (BasicHashtableEntry<F>* p = _buckets[index_old].get_entry(); p != NULL; ) {
155       BasicHashtableEntry<F>* next = p->next();
156       bool keep_shared = p->is_shared();
157       int index_new = hash_to_index(p->hash());
158 
159       p->set_next(buckets_new[index_new].get_entry());
160       buckets_new[index_new].set_entry(p);
161 
162       if (keep_shared) {
163         p->set_shared();
164       }
165       p = next;
166     }
167   }
168 
169   // The old backets now can be released
170   BasicHashtable<F>::free_buckets();
171 
172   // Switch to the new storage
173   _buckets = buckets_new;
174 
175   return true;
176 }
177 
178 template <MEMFLAGS F> bool BasicHashtable<F>::maybe_grow(int max_size, int load_factor) {
179   assert(SafepointSynchronize::is_at_safepoint(), "must be at safepoint");
180 
181   if (table_size() >= max_size) {
182     return false;
183   }
184   if (number_of_entries() / table_size() > load_factor) {
185     resize(MIN2<int>(table_size() * 2, max_size));
186     return true;
187   } else {
188     return false;
189   }
190 }
191 
192 template <class T, MEMFLAGS F> TableStatistics Hashtable<T, F>::statistics_calculate(T (*literal_load_barrier)(HashtableEntry<T, F>*)) {
193   NumberSeq summary;
194   int literal_bytes = 0;
195   for (int i = 0; i < this->table_size(); ++i) {
196     int count = 0;
197     for (HashtableEntry<T, F>* e = this->bucket(i);
198          e != NULL; e = e->next()) {
199       count++;
200       T l = (literal_load_barrier != NULL) ? literal_load_barrier(e) : e->literal();
201       literal_bytes += literal_size(l);
202     }
203     summary.add((double)count);
204   }
205   return TableStatistics(this->_stats_rate, summary, literal_bytes, sizeof(HashtableBucket<F>), sizeof(HashtableEntry<T, F>));
206 }
207 
208 // Dump footprint and bucket length statistics
209 //
210 // Note: if you create a new subclass of Hashtable<MyNewType, F>, you will need to
211 // add a new function static int literal_size(MyNewType lit)
212 // because I can't get template <class T> int literal_size(T) to pick the specializations for Symbol and oop.
213 template <class T, MEMFLAGS F> void Hashtable<T, F>::print_table_statistics(outputStream* st,
214                                                                             const char *table_name,
215                                                                             T (*literal_load_barrier)(HashtableEntry<T, F>*)) {
216   TableStatistics ts = statistics_calculate(literal_load_barrier);
217   ts.print(st, table_name);
218 }
219 
220 #ifndef PRODUCT
221 template <class T> void print_literal(T l) {
222   l->print();
223 }
224 
225 static void print_literal(WeakHandle<vm_class_loader_data> l) {
226   l.print();
227 }
228 
229 template <class T, MEMFLAGS F> void Hashtable<T, F>::print() {
230   ResourceMark rm;
231 
232   for (int i = 0; i < BasicHashtable<F>::table_size(); i++) {
233     HashtableEntry<T, F>* entry = bucket(i);
234     while(entry != NULL) {
235       tty->print("%d : ", i);
236       print_literal(entry->literal());
237       tty->cr();
238       entry = entry->next();
239     }
240   }
241 }
242 
243 template <MEMFLAGS F>
244 template <class T> void BasicHashtable<F>::verify_table(const char* table_name) {
245   int element_count = 0;
246   int max_bucket_count = 0;
247   int max_bucket_number = 0;
248   for (int index = 0; index < table_size(); index++) {
249     int bucket_count = 0;
250     for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
251       probe->verify();
252       bucket_count++;
253     }
254     element_count += bucket_count;
255     if (bucket_count > max_bucket_count) {
256       max_bucket_count = bucket_count;
257       max_bucket_number = index;
258     }
259   }
260   guarantee(number_of_entries() == element_count,
261             "Verify of %s failed", table_name);
262 
263   // Log some statistics about the hashtable
264   log_info(hashtables)("%s max bucket size %d bucket %d element count %d table size %d", table_name,
265                        max_bucket_count, max_bucket_number, _number_of_entries, _table_size);
266   if (_number_of_entries > 0 && log_is_enabled(Debug, hashtables)) {
267     for (int index = 0; index < table_size(); index++) {
268       int bucket_count = 0;
269       for (T* probe = (T*)bucket(index); probe != NULL; probe = probe->next()) {
270         log_debug(hashtables)("bucket %d hash " INTPTR_FORMAT, index, (intptr_t)probe->hash());
271         bucket_count++;
272       }
273       if (bucket_count > 0) {
274         log_debug(hashtables)("bucket %d count %d", index, bucket_count);
275       }
276     }
277   }
278 }
279 #endif // PRODUCT
280 
281 // Explicitly instantiate these types
282 template class Hashtable<nmethod*, mtGC>;
283 template class HashtableEntry<nmethod*, mtGC>;
284 template class BasicHashtable<mtGC>;
285 template class Hashtable<ConstantPool*, mtClass>;
286 template class Hashtable<Symbol*, mtSymbol>;
287 template class Hashtable<Klass*, mtClass>;
288 template class Hashtable<InstanceKlass*, mtClass>;
289 template class Hashtable<WeakHandle<vm_class_loader_data>, mtClass>;
290 template class Hashtable<Symbol*, mtModule>;
291 template class Hashtable<oop, mtSymbol>;
292 template class Hashtable<Symbol*, mtClass>;
293 template class HashtableEntry<Symbol*, mtSymbol>;
294 template class HashtableEntry<Symbol*, mtClass>;
295 template class HashtableEntry<oop, mtSymbol>;
296 template class HashtableEntry<WeakHandle<vm_class_loader_data>, mtClass>;
297 template class HashtableBucket<mtClass>;
298 template class BasicHashtableEntry<mtSymbol>;
299 template class BasicHashtableEntry<mtCode>;
300 template class BasicHashtable<mtClass>;
301 template class BasicHashtable<mtClassShared>;
302 template class BasicHashtable<mtSymbol>;
303 template class BasicHashtable<mtCode>;
304 template class BasicHashtable<mtInternal>;
305 template class BasicHashtable<mtModule>;
306 template class BasicHashtable<mtCompiler>;
307 template class BasicHashtable<mtTracing>;
308 
309 template void BasicHashtable<mtClass>::verify_table<DictionaryEntry>(char const*);
310 template void BasicHashtable<mtModule>::verify_table<ModuleEntry>(char const*);
311 template void BasicHashtable<mtModule>::verify_table<PackageEntry>(char const*);
312 template void BasicHashtable<mtClass>::verify_table<ProtectionDomainCacheEntry>(char const*);
313 template void BasicHashtable<mtClass>::verify_table<PlaceholderEntry>(char const*);