annotate hotspot/src/share/vm/utilities/hashtable.cpp @ 8076:96d498ec7ae1

6990754: Use native memory and reference counting to implement SymbolTable Summary: move symbols from permgen into C heap and reference count them Reviewed-by: never, acorn, jmasa, stefank
author coleenp
date Thu, 27 Jan 2011 16:11:27 -0800
parents 5b173b4ca846
children 14bfe81f2a9d
rev   line source
duke@1 1 /*
stefank@7397 2 * Copyright (c) 2003, 2010, Oracle and/or its affiliates. All rights reserved.
duke@1 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@1 4 *
duke@1 5 * This code is free software; you can redistribute it and/or modify it
duke@1 6 * under the terms of the GNU General Public License version 2 only, as
duke@1 7 * published by the Free Software Foundation.
duke@1 8 *
duke@1 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@1 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@1 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@1 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@1 13 * accompanied this code).
duke@1 14 *
duke@1 15 * You should have received a copy of the GNU General Public License version
duke@1 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@1 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@1 18 *
trims@5547 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
trims@5547 20 * or visit www.oracle.com if you need additional information or have any
trims@5547 21 * questions.
duke@1 22 *
duke@1 23 */
duke@1 24
stefank@7397 25 #include "precompiled.hpp"
stefank@7397 26 #include "memory/allocation.inline.hpp"
stefank@7397 27 #include "memory/resourceArea.hpp"
stefank@7397 28 #include "oops/oop.inline.hpp"
stefank@7397 29 #include "runtime/safepoint.hpp"
stefank@7397 30 #include "utilities/dtrace.hpp"
stefank@7397 31 #include "utilities/hashtable.hpp"
stefank@7397 32 #include "utilities/hashtable.inline.hpp"
duke@1 33
coleenp@8076 34
duke@1 35 HS_DTRACE_PROBE_DECL4(hs_private, hashtable__new_entry,
coleenp@8076 36 void*, unsigned int, void*, void*);
duke@1 37
duke@1 38 // This is a generic hashtable, designed to be used for the symbol
duke@1 39 // and string tables.
duke@1 40 //
duke@1 41 // It is implemented as an open hash table with a fixed number of buckets.
duke@1 42 //
duke@1 43 // %note:
duke@1 44 // - HashtableEntrys are allocated in blocks to reduce the space overhead.
duke@1 45
duke@1 46 BasicHashtableEntry* BasicHashtable::new_entry(unsigned int hashValue) {
duke@1 47 BasicHashtableEntry* entry;
duke@1 48
duke@1 49 if (_free_list) {
duke@1 50 entry = _free_list;
duke@1 51 _free_list = _free_list->next();
duke@1 52 } else {
jrose@1551 53 if (_first_free_entry + _entry_size >= _end_block) {
jrose@1551 54 int block_size = MIN2(512, MAX2((int)_table_size / 2, (int)_number_of_entries));
duke@1 55 int len = _entry_size * block_size;
jrose@1551 56 len = 1 << log2_intptr(len); // round down to power of 2
jrose@1551 57 assert(len >= _entry_size, "");
duke@1 58 _first_free_entry = NEW_C_HEAP_ARRAY(char, len);
duke@1 59 _end_block = _first_free_entry + len;
duke@1 60 }
duke@1 61 entry = (BasicHashtableEntry*)_first_free_entry;
duke@1 62 _first_free_entry += _entry_size;
duke@1 63 }
duke@1 64
jrose@1551 65 assert(_entry_size % HeapWordSize == 0, "");
duke@1 66 entry->set_hash(hashValue);
duke@1 67 return entry;
duke@1 68 }
duke@1 69
duke@1 70
coleenp@8076 71 template <class T> HashtableEntry<T>* Hashtable<T>::new_entry(unsigned int hashValue, T obj) {
coleenp@8076 72 HashtableEntry<T>* entry;
duke@1 73
coleenp@8076 74 entry = (HashtableEntry<T>*)BasicHashtable::new_entry(hashValue);
coleenp@8076 75 entry->set_literal(obj);
duke@1 76 HS_DTRACE_PROBE4(hs_private, hashtable__new_entry,
duke@1 77 this, hashValue, obj, entry);
duke@1 78 return entry;
duke@1 79 }
duke@1 80
duke@1 81
duke@1 82 // Reverse the order of elements in the hash buckets.
duke@1 83
duke@1 84 void BasicHashtable::reverse() {
duke@1 85
duke@1 86 for (int i = 0; i < _table_size; ++i) {
duke@1 87 BasicHashtableEntry* new_list = NULL;
duke@1 88 BasicHashtableEntry* p = bucket(i);
duke@1 89 while (p != NULL) {
duke@1 90 BasicHashtableEntry* next = p->next();
duke@1 91 p->set_next(new_list);
duke@1 92 new_list = p;
duke@1 93 p = next;
duke@1 94 }
duke@1 95 *bucket_addr(i) = new_list;
duke@1 96 }
duke@1 97 }
duke@1 98
duke@1 99
duke@1 100 // Copy the table to the shared space.
duke@1 101
duke@1 102 void BasicHashtable::copy_table(char** top, char* end) {
duke@1 103
duke@1 104 // Dump the hash table entries.
duke@1 105
duke@1 106 intptr_t *plen = (intptr_t*)(*top);
duke@1 107 *top += sizeof(*plen);
duke@1 108
duke@1 109 int i;
duke@1 110 for (i = 0; i < _table_size; ++i) {
duke@1 111 for (BasicHashtableEntry** p = _buckets[i].entry_addr();
duke@1 112 *p != NULL;
duke@1 113 p = (*p)->next_addr()) {
duke@1 114 if (*top + entry_size() > end) {
coleenp@8076 115 report_out_of_shared_space(SharedMiscData);
duke@1 116 }
duke@1 117 *p = (BasicHashtableEntry*)memcpy(*top, *p, entry_size());
duke@1 118 *top += entry_size();
duke@1 119 }
duke@1 120 }
duke@1 121 *plen = (char*)(*top) - (char*)plen - sizeof(*plen);
duke@1 122
duke@1 123 // Set the shared bit.
duke@1 124
duke@1 125 for (i = 0; i < _table_size; ++i) {
duke@1 126 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 127 p->set_shared();
duke@1 128 }
duke@1 129 }
duke@1 130 }
duke@1 131
duke@1 132
duke@1 133
duke@1 134 // Reverse the order of elements in the hash buckets.
duke@1 135
coleenp@8076 136 template <class T> void Hashtable<T>::reverse(void* boundary) {
duke@1 137
duke@1 138 for (int i = 0; i < table_size(); ++i) {
coleenp@8076 139 HashtableEntry<T>* high_list = NULL;
coleenp@8076 140 HashtableEntry<T>* low_list = NULL;
coleenp@8076 141 HashtableEntry<T>* last_low_entry = NULL;
coleenp@8076 142 HashtableEntry<T>* p = bucket(i);
duke@1 143 while (p != NULL) {
coleenp@8076 144 HashtableEntry<T>* next = p->next();
duke@1 145 if ((void*)p->literal() >= boundary) {
duke@1 146 p->set_next(high_list);
duke@1 147 high_list = p;
duke@1 148 } else {
duke@1 149 p->set_next(low_list);
duke@1 150 low_list = p;
duke@1 151 if (last_low_entry == NULL) {
duke@1 152 last_low_entry = p;
duke@1 153 }
duke@1 154 }
duke@1 155 p = next;
duke@1 156 }
duke@1 157 if (low_list != NULL) {
duke@1 158 *bucket_addr(i) = low_list;
duke@1 159 last_low_entry->set_next(high_list);
duke@1 160 } else {
duke@1 161 *bucket_addr(i) = high_list;
duke@1 162 }
duke@1 163 }
duke@1 164 }
duke@1 165
duke@1 166
duke@1 167 // Dump the hash table buckets.
duke@1 168
duke@1 169 void BasicHashtable::copy_buckets(char** top, char* end) {
duke@1 170 intptr_t len = _table_size * sizeof(HashtableBucket);
duke@1 171 *(intptr_t*)(*top) = len;
duke@1 172 *top += sizeof(intptr_t);
duke@1 173
duke@1 174 *(intptr_t*)(*top) = _number_of_entries;
duke@1 175 *top += sizeof(intptr_t);
duke@1 176
duke@1 177 if (*top + len > end) {
coleenp@8076 178 report_out_of_shared_space(SharedMiscData);
duke@1 179 }
duke@1 180 _buckets = (HashtableBucket*)memcpy(*top, _buckets, len);
duke@1 181 *top += len;
duke@1 182 }
duke@1 183
duke@1 184
duke@1 185 #ifndef PRODUCT
duke@1 186
coleenp@8076 187 template <class T> void Hashtable<T>::print() {
duke@1 188 ResourceMark rm;
duke@1 189
duke@1 190 for (int i = 0; i < table_size(); i++) {
coleenp@8076 191 HashtableEntry<T>* entry = bucket(i);
duke@1 192 while(entry != NULL) {
duke@1 193 tty->print("%d : ", i);
duke@1 194 entry->literal()->print();
duke@1 195 tty->cr();
duke@1 196 entry = entry->next();
duke@1 197 }
duke@1 198 }
duke@1 199 }
duke@1 200
duke@1 201
duke@1 202 void BasicHashtable::verify() {
duke@1 203 int count = 0;
duke@1 204 for (int i = 0; i < table_size(); i++) {
duke@1 205 for (BasicHashtableEntry* p = bucket(i); p != NULL; p = p->next()) {
duke@1 206 ++count;
duke@1 207 }
duke@1 208 }
duke@1 209 assert(count == number_of_entries(), "number of hashtable entries incorrect");
duke@1 210 }
duke@1 211
duke@1 212
duke@1 213 #endif // PRODUCT
duke@1 214
duke@1 215
duke@1 216 #ifdef ASSERT
duke@1 217
duke@1 218 void BasicHashtable::verify_lookup_length(double load) {
duke@1 219 if ((double)_lookup_length / (double)_lookup_count > load * 2.0) {
duke@1 220 warning("Performance bug: SystemDictionary lookup_count=%d "
duke@1 221 "lookup_length=%d average=%lf load=%f",
duke@1 222 _lookup_count, _lookup_length,
duke@1 223 (double) _lookup_length / _lookup_count, load);
duke@1 224 }
duke@1 225 }
duke@1 226
duke@1 227 #endif
coleenp@8076 228
coleenp@8076 229 // Explicitly instantiate these types
coleenp@8076 230 template class Hashtable<constantPoolOop>;
coleenp@8076 231 template class Hashtable<Symbol*>;
coleenp@8076 232 template class Hashtable<klassOop>;
coleenp@8076 233 template class Hashtable<oop>;
coleenp@8076 234