Thu, 20 Nov 2008 16:56:09 -0800
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
Reviewed-by: jmasa
1 /*
2 * Copyright 2003-2005 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 */
25 // This is a generic hashtable, designed to be used for the symbol
26 // and string tables.
27 //
28 // It is implemented as an open hash table with a fixed number of buckets.
29 //
30 // %note:
31 // - TableEntrys are allocated in blocks to reduce the space overhead.
35 class BasicHashtableEntry : public CHeapObj {
36 friend class VMStructs;
37 private:
38 unsigned int _hash; // 32-bit hash for item
40 // Link to next element in the linked list for this bucket. EXCEPT
41 // bit 0 set indicates that this entry is shared and must not be
42 // unlinked from the table. Bit 0 is set during the dumping of the
43 // archive. Since shared entries are immutable, _next fields in the
44 // shared entries will not change. New entries will always be
45 // unshared and since pointers are align, bit 0 will always remain 0
46 // with no extra effort.
47 BasicHashtableEntry* _next;
49 // Windows IA64 compiler requires subclasses to be able to access these
50 protected:
51 // Entry objects should not be created, they should be taken from the
52 // free list with BasicHashtable.new_entry().
53 BasicHashtableEntry() { ShouldNotReachHere(); }
54 // Entry objects should not be destroyed. They should be placed on
55 // the free list instead with BasicHashtable.free_entry().
56 ~BasicHashtableEntry() { ShouldNotReachHere(); }
58 public:
60 unsigned int hash() const { return _hash; }
61 void set_hash(unsigned int hash) { _hash = hash; }
62 unsigned int* hash_addr() { return &_hash; }
64 static BasicHashtableEntry* make_ptr(BasicHashtableEntry* p) {
65 return (BasicHashtableEntry*)((intptr_t)p & -2);
66 }
68 BasicHashtableEntry* next() const {
69 return make_ptr(_next);
70 }
72 void set_next(BasicHashtableEntry* next) {
73 _next = next;
74 }
76 BasicHashtableEntry** next_addr() {
77 return &_next;
78 }
80 bool is_shared() const {
81 return ((intptr_t)_next & 1) != 0;
82 }
84 void set_shared() {
85 _next = (BasicHashtableEntry*)((intptr_t)_next | 1);
86 }
87 };
91 class HashtableEntry : public BasicHashtableEntry {
92 friend class VMStructs;
93 private:
94 oop _literal; // ref to item in table.
96 public:
97 // Literal
98 oop literal() const { return _literal; }
99 oop* literal_addr() { return &_literal; }
100 void set_literal(oop s) { _literal = s; }
102 HashtableEntry* next() const {
103 return (HashtableEntry*)BasicHashtableEntry::next();
104 }
105 HashtableEntry** next_addr() {
106 return (HashtableEntry**)BasicHashtableEntry::next_addr();
107 }
108 };
112 class HashtableBucket : public CHeapObj {
113 friend class VMStructs;
114 private:
115 // Instance variable
116 BasicHashtableEntry* _entry;
118 public:
119 // Accessing
120 void clear() { _entry = NULL; }
122 // The following methods use order access methods to avoid race
123 // conditions in multiprocessor systems.
124 BasicHashtableEntry* get_entry() const;
125 void set_entry(BasicHashtableEntry* l);
127 // The following method is not MT-safe and must be done under lock.
128 BasicHashtableEntry** entry_addr() { return &_entry; }
129 };
132 class BasicHashtable : public CHeapObj {
133 friend class VMStructs;
135 public:
136 BasicHashtable(int table_size, int entry_size);
137 BasicHashtable(int table_size, int entry_size,
138 HashtableBucket* buckets, int number_of_entries);
140 // Sharing support.
141 void copy_buckets(char** top, char* end);
142 void copy_table(char** top, char* end);
144 // Bucket handling
145 int hash_to_index(unsigned int full_hash) {
146 int h = full_hash % _table_size;
147 assert(h >= 0 && h < _table_size, "Illegal hash value");
148 return h;
149 }
151 // Reverse the order of elements in each of the buckets.
152 void reverse();
154 private:
155 // Instance variables
156 int _table_size;
157 HashtableBucket* _buckets;
158 BasicHashtableEntry* _free_list;
159 char* _first_free_entry;
160 char* _end_block;
161 int _entry_size;
162 int _number_of_entries;
164 protected:
166 #ifdef ASSERT
167 int _lookup_count;
168 int _lookup_length;
169 void verify_lookup_length(double load);
170 #endif
172 void initialize(int table_size, int entry_size, int number_of_entries);
174 // Accessor
175 int entry_size() const { return _entry_size; }
176 int table_size() { return _table_size; }
178 // The following method is MT-safe and may be used with caution.
179 BasicHashtableEntry* bucket(int i);
181 // The following method is not MT-safe and must be done under lock.
182 BasicHashtableEntry** bucket_addr(int i) { return _buckets[i].entry_addr(); }
184 // Table entry management
185 BasicHashtableEntry* new_entry(unsigned int hashValue);
187 public:
188 void set_entry(int index, BasicHashtableEntry* entry);
190 void add_entry(int index, BasicHashtableEntry* entry);
192 void free_entry(BasicHashtableEntry* entry);
194 int number_of_entries() { return _number_of_entries; }
196 void verify() PRODUCT_RETURN;
197 };
200 class Hashtable : public BasicHashtable {
201 friend class VMStructs;
203 public:
204 Hashtable(int table_size, int entry_size)
205 : BasicHashtable(table_size, entry_size) { }
207 Hashtable(int table_size, int entry_size,
208 HashtableBucket* buckets, int number_of_entries)
209 : BasicHashtable(table_size, entry_size, buckets, number_of_entries) { }
211 // Invoke "f->do_oop" on the locations of all oops in the table.
212 void oops_do(OopClosure* f);
214 // Debugging
215 void print() PRODUCT_RETURN;
217 // GC support
218 // Delete pointers to otherwise-unreachable objects.
219 void unlink(BoolObjectClosure* cl);
221 // Reverse the order of elements in each of the buckets. Hashtable
222 // entries which refer to objects at a lower address than 'boundary'
223 // are separated from those which refer to objects at higher
224 // addresses, and appear first in the list.
225 void reverse(void* boundary = NULL);
227 protected:
229 static unsigned int hash_symbol(const char* s, int len);
231 unsigned int compute_hash(symbolHandle name) {
232 return (unsigned int) name->identity_hash();
233 }
235 int index_for(symbolHandle name) {
236 return hash_to_index(compute_hash(name));
237 }
239 // Table entry management
240 HashtableEntry* new_entry(unsigned int hashValue, oop obj);
242 // The following method is MT-safe and may be used with caution.
243 HashtableEntry* bucket(int i) {
244 return (HashtableEntry*)BasicHashtable::bucket(i);
245 }
247 // The following method is not MT-safe and must be done under lock.
248 HashtableEntry** bucket_addr(int i) {
249 return (HashtableEntry**)BasicHashtable::bucket_addr(i);
250 }
251 };
254 // Verions of hashtable where two handles are used to compute the index.
256 class TwoOopHashtable : public Hashtable {
257 friend class VMStructs;
258 protected:
259 TwoOopHashtable(int table_size, int entry_size)
260 : Hashtable(table_size, entry_size) {}
262 TwoOopHashtable(int table_size, int entry_size, HashtableBucket* t,
263 int number_of_entries)
264 : Hashtable(table_size, entry_size, t, number_of_entries) {}
266 public:
267 unsigned int compute_hash(symbolHandle name, Handle loader) {
268 // Be careful with identity_hash(), it can safepoint and if this
269 // were one expression, the compiler could choose to unhandle each
270 // oop before calling identity_hash() for either of them. If the first
271 // causes a GC, the next would fail.
272 unsigned int name_hash = name->identity_hash();
273 unsigned int loader_hash = loader.is_null() ? 0 : loader->identity_hash();
274 return name_hash ^ loader_hash;
275 }
277 int index_for(symbolHandle name, Handle loader) {
278 return hash_to_index(compute_hash(name, loader));
279 }
280 };