author | ysr |
Tue, 14 Jul 2009 15:40:39 -0700 | |
changeset 3262 | 30d1c247fc25 |
parent 2996 | 1097030e5ec3 |
child 3261 | c7d5aae8d3f7 |
permissions | -rw-r--r-- |
1374 | 1 |
/* |
2 |
* Copyright 2001-2007 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 |
*/ |
|
24 |
||
25 |
#include "incls/_precompiled.incl" |
|
26 |
#include "incls/_sparsePRT.cpp.incl" |
|
27 |
||
28 |
#define SPARSE_PRT_VERBOSE 0 |
|
29 |
||
30 |
#define UNROLL_CARD_LOOPS 1 |
|
31 |
||
32 |
void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { |
|
33 |
sprt_iter->init(this); |
|
34 |
} |
|
35 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
36 |
void SparsePRTEntry::init(RegionIdx_t region_ind) { |
1374 | 37 |
_region_ind = region_ind; |
38 |
_next_index = NullEntry; |
|
39 |
#if UNROLL_CARD_LOOPS |
|
40 |
assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); |
|
41 |
_cards[0] = NullEntry; |
|
42 |
_cards[1] = NullEntry; |
|
43 |
_cards[2] = NullEntry; |
|
44 |
_cards[3] = NullEntry; |
|
45 |
#else |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
46 |
for (int i = 0; i < CardsPerEntry; i++) |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
47 |
_cards[i] = NullEntry; |
1374 | 48 |
#endif |
49 |
} |
|
50 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
51 |
bool SparsePRTEntry::contains_card(CardIdx_t card_index) const { |
1374 | 52 |
#if UNROLL_CARD_LOOPS |
53 |
assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); |
|
54 |
if (_cards[0] == card_index) return true; |
|
55 |
if (_cards[1] == card_index) return true; |
|
56 |
if (_cards[2] == card_index) return true; |
|
57 |
if (_cards[3] == card_index) return true; |
|
58 |
#else |
|
59 |
for (int i = 0; i < CardsPerEntry; i++) { |
|
60 |
if (_cards[i] == card_index) return true; |
|
61 |
} |
|
62 |
#endif |
|
63 |
// Otherwise, we're full. |
|
64 |
return false; |
|
65 |
} |
|
66 |
||
67 |
int SparsePRTEntry::num_valid_cards() const { |
|
68 |
int sum = 0; |
|
69 |
#if UNROLL_CARD_LOOPS |
|
70 |
assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); |
|
71 |
if (_cards[0] != NullEntry) sum++; |
|
72 |
if (_cards[1] != NullEntry) sum++; |
|
73 |
if (_cards[2] != NullEntry) sum++; |
|
74 |
if (_cards[3] != NullEntry) sum++; |
|
75 |
#else |
|
76 |
for (int i = 0; i < CardsPerEntry; i++) { |
|
77 |
if (_cards[i] != NulLEntry) sum++; |
|
78 |
} |
|
79 |
#endif |
|
80 |
// Otherwise, we're full. |
|
81 |
return sum; |
|
82 |
} |
|
83 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
84 |
SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) { |
1374 | 85 |
#if UNROLL_CARD_LOOPS |
86 |
assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
87 |
CardIdx_t c = _cards[0]; |
1374 | 88 |
if (c == card_index) return found; |
89 |
if (c == NullEntry) { _cards[0] = card_index; return added; } |
|
90 |
c = _cards[1]; |
|
91 |
if (c == card_index) return found; |
|
92 |
if (c == NullEntry) { _cards[1] = card_index; return added; } |
|
93 |
c = _cards[2]; |
|
94 |
if (c == card_index) return found; |
|
95 |
if (c == NullEntry) { _cards[2] = card_index; return added; } |
|
96 |
c = _cards[3]; |
|
97 |
if (c == card_index) return found; |
|
98 |
if (c == NullEntry) { _cards[3] = card_index; return added; } |
|
99 |
#else |
|
100 |
for (int i = 0; i < CardsPerEntry; i++) { |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
101 |
CardIdx_t c = _cards[i]; |
1374 | 102 |
if (c == card_index) return found; |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
103 |
if (c == NullEntry) { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
104 |
_cards[i] = card_index; |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
105 |
return added; |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
106 |
} |
1374 | 107 |
} |
108 |
#endif |
|
109 |
// Otherwise, we're full. |
|
110 |
return overflow; |
|
111 |
} |
|
112 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
113 |
void SparsePRTEntry::copy_cards(CardIdx_t* cards) const { |
1374 | 114 |
#if UNROLL_CARD_LOOPS |
115 |
assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); |
|
116 |
cards[0] = _cards[0]; |
|
117 |
cards[1] = _cards[1]; |
|
118 |
cards[2] = _cards[2]; |
|
119 |
cards[3] = _cards[3]; |
|
120 |
#else |
|
121 |
for (int i = 0; i < CardsPerEntry; i++) { |
|
122 |
cards[i] = _cards[i]; |
|
123 |
} |
|
124 |
#endif |
|
125 |
} |
|
126 |
||
127 |
void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const { |
|
128 |
copy_cards(&e->_cards[0]); |
|
129 |
} |
|
130 |
||
131 |
// ---------------------------------------------------------------------- |
|
132 |
||
133 |
RSHashTable::RSHashTable(size_t capacity) : |
|
134 |
_capacity(capacity), _capacity_mask(capacity-1), |
|
135 |
_occupied_entries(0), _occupied_cards(0), |
|
136 |
_entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)), |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
137 |
_buckets(NEW_C_HEAP_ARRAY(int, capacity)), |
1374 | 138 |
_next_deleted(NULL), _deleted(false), |
139 |
_free_list(NullEntry), _free_region(0) |
|
140 |
{ |
|
141 |
clear(); |
|
142 |
} |
|
143 |
||
144 |
RSHashTable::~RSHashTable() { |
|
145 |
if (_entries != NULL) { |
|
146 |
FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries); |
|
147 |
_entries = NULL; |
|
148 |
} |
|
149 |
if (_buckets != NULL) { |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
150 |
FREE_C_HEAP_ARRAY(int, _buckets); |
1374 | 151 |
_buckets = NULL; |
152 |
} |
|
153 |
} |
|
154 |
||
155 |
void RSHashTable::clear() { |
|
156 |
_occupied_entries = 0; |
|
157 |
_occupied_cards = 0; |
|
158 |
guarantee(_entries != NULL, "INV"); |
|
159 |
guarantee(_buckets != NULL, "INV"); |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
160 |
|
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
161 |
guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1, |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
162 |
"_capacity too large"); |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
163 |
|
1374 | 164 |
// This will put -1 == NullEntry in the key field of all entries. |
165 |
memset(_entries, -1, _capacity * sizeof(SparsePRTEntry)); |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
166 |
memset(_buckets, -1, _capacity * sizeof(int)); |
1374 | 167 |
_free_list = NullEntry; |
168 |
_free_region = 0; |
|
169 |
} |
|
170 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
171 |
bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) { |
1374 | 172 |
SparsePRTEntry* e = entry_for_region_ind_create(region_ind); |
173 |
assert(e != NULL && e->r_ind() == region_ind, |
|
174 |
"Postcondition of call above."); |
|
175 |
SparsePRTEntry::AddCardResult res = e->add_card(card_index); |
|
176 |
if (res == SparsePRTEntry::added) _occupied_cards++; |
|
177 |
#if SPARSE_PRT_VERBOSE |
|
178 |
gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", |
|
179 |
pointer_delta(e, _entries, sizeof(SparsePRTEntry)), |
|
180 |
e->num_valid_cards()); |
|
181 |
#endif |
|
182 |
assert(e->num_valid_cards() > 0, "Postcondition"); |
|
183 |
return res != SparsePRTEntry::overflow; |
|
184 |
} |
|
185 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
186 |
bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
187 |
int ind = (int) (region_ind & capacity_mask()); |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
188 |
int cur_ind = _buckets[ind]; |
1374 | 189 |
SparsePRTEntry* cur; |
190 |
while (cur_ind != NullEntry && |
|
191 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
192 |
cur_ind = cur->next_index(); |
|
193 |
} |
|
194 |
||
195 |
if (cur_ind == NullEntry) return false; |
|
196 |
// Otherwise... |
|
197 |
assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); |
|
198 |
assert(cur->num_valid_cards() > 0, "Inv"); |
|
199 |
cur->copy_cards(cards); |
|
200 |
return true; |
|
201 |
} |
|
202 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
203 |
bool RSHashTable::delete_entry(RegionIdx_t region_ind) { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
204 |
int ind = (int) (region_ind & capacity_mask()); |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
205 |
int* prev_loc = &_buckets[ind]; |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
206 |
int cur_ind = *prev_loc; |
1374 | 207 |
SparsePRTEntry* cur; |
208 |
while (cur_ind != NullEntry && |
|
209 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
210 |
prev_loc = cur->next_index_addr(); |
|
211 |
cur_ind = *prev_loc; |
|
212 |
} |
|
213 |
||
214 |
if (cur_ind == NullEntry) return false; |
|
215 |
// Otherwise, splice out "cur". |
|
216 |
*prev_loc = cur->next_index(); |
|
217 |
_occupied_cards -= cur->num_valid_cards(); |
|
218 |
free_entry(cur_ind); |
|
219 |
_occupied_entries--; |
|
220 |
return true; |
|
221 |
} |
|
222 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
223 |
SparsePRTEntry* |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
224 |
RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const { |
1374 | 225 |
assert(occupied_entries() < capacity(), "Precondition"); |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
226 |
int ind = (int) (region_ind & capacity_mask()); |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
227 |
int cur_ind = _buckets[ind]; |
1374 | 228 |
SparsePRTEntry* cur; |
229 |
// XXX |
|
230 |
// int k = 0; |
|
231 |
while (cur_ind != NullEntry && |
|
232 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
233 |
/* |
|
234 |
k++; |
|
235 |
if (k > 10) { |
|
236 |
gclog_or_tty->print_cr("RSHashTable::entry_for_region_ind(%d): " |
|
237 |
"k = %d, cur_ind = %d.", region_ind, k, cur_ind); |
|
238 |
if (k >= 1000) { |
|
239 |
while (1) ; |
|
240 |
} |
|
241 |
} |
|
242 |
*/ |
|
243 |
cur_ind = cur->next_index(); |
|
244 |
} |
|
245 |
||
246 |
if (cur_ind != NullEntry) { |
|
247 |
assert(cur->r_ind() == region_ind, "Loop postcondition + test"); |
|
248 |
return cur; |
|
249 |
} else { |
|
250 |
return NULL; |
|
251 |
} |
|
252 |
} |
|
253 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
254 |
SparsePRTEntry* |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
255 |
RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) { |
1374 | 256 |
SparsePRTEntry* res = entry_for_region_ind(region_ind); |
257 |
if (res == NULL) { |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
258 |
int new_ind = alloc_entry(); |
1374 | 259 |
assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room."); |
260 |
res = entry(new_ind); |
|
261 |
res->init(region_ind); |
|
262 |
// Insert at front. |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
263 |
int ind = (int) (region_ind & capacity_mask()); |
1374 | 264 |
res->set_next_index(_buckets[ind]); |
265 |
_buckets[ind] = new_ind; |
|
266 |
_occupied_entries++; |
|
267 |
} |
|
268 |
return res; |
|
269 |
} |
|
270 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
271 |
int RSHashTable::alloc_entry() { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
272 |
int res; |
1374 | 273 |
if (_free_list != NullEntry) { |
274 |
res = _free_list; |
|
275 |
_free_list = entry(res)->next_index(); |
|
276 |
return res; |
|
277 |
} else if ((size_t) _free_region+1 < capacity()) { |
|
278 |
res = _free_region; |
|
279 |
_free_region++; |
|
280 |
return res; |
|
281 |
} else { |
|
282 |
return NullEntry; |
|
283 |
} |
|
284 |
} |
|
285 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
286 |
void RSHashTable::free_entry(int fi) { |
1374 | 287 |
entry(fi)->set_next_index(_free_list); |
288 |
_free_list = fi; |
|
289 |
} |
|
290 |
||
291 |
void RSHashTable::add_entry(SparsePRTEntry* e) { |
|
292 |
assert(e->num_valid_cards() > 0, "Precondition."); |
|
293 |
SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind()); |
|
294 |
e->copy_cards(e2); |
|
295 |
_occupied_cards += e2->num_valid_cards(); |
|
296 |
assert(e2->num_valid_cards() > 0, "Postcondition."); |
|
297 |
} |
|
298 |
||
299 |
RSHashTable* RSHashTable::_head_deleted_list = NULL; |
|
300 |
||
301 |
void RSHashTable::add_to_deleted_list(RSHashTable* rsht) { |
|
302 |
assert(!rsht->deleted(), "Should delete only once."); |
|
303 |
rsht->set_deleted(true); |
|
304 |
RSHashTable* hd = _head_deleted_list; |
|
305 |
while (true) { |
|
306 |
rsht->_next_deleted = hd; |
|
307 |
RSHashTable* res = |
|
308 |
(RSHashTable*) |
|
309 |
Atomic::cmpxchg_ptr(rsht, &_head_deleted_list, hd); |
|
310 |
if (res == hd) return; |
|
311 |
else hd = res; |
|
312 |
} |
|
313 |
} |
|
314 |
||
315 |
RSHashTable* RSHashTable::get_from_deleted_list() { |
|
316 |
RSHashTable* hd = _head_deleted_list; |
|
317 |
while (hd != NULL) { |
|
318 |
RSHashTable* next = hd->next_deleted(); |
|
319 |
RSHashTable* res = |
|
320 |
(RSHashTable*) |
|
321 |
Atomic::cmpxchg_ptr(next, &_head_deleted_list, hd); |
|
322 |
if (res == hd) { |
|
323 |
hd->set_next_deleted(NULL); |
|
324 |
hd->set_deleted(false); |
|
325 |
return hd; |
|
326 |
} else { |
|
327 |
hd = res; |
|
328 |
} |
|
329 |
} |
|
330 |
return NULL; |
|
331 |
} |
|
332 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
333 |
CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
334 |
CardIdx_t res; |
1374 | 335 |
while (_bl_ind != RSHashTable::NullEntry) { |
336 |
res = _rsht->entry(_bl_ind)->card(0); |
|
337 |
if (res != SparsePRTEntry::NullEntry) { |
|
338 |
return res; |
|
339 |
} else { |
|
340 |
_bl_ind = _rsht->entry(_bl_ind)->next_index(); |
|
341 |
} |
|
342 |
} |
|
343 |
// Otherwise, none found: |
|
344 |
return SparsePRTEntry::NullEntry; |
|
345 |
} |
|
346 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
347 |
size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) { |
1374 | 348 |
return |
349 |
_heap_bot_card_ind |
|
350 |
+ (_rsht->entry(_bl_ind)->r_ind() * CardsPerRegion) |
|
351 |
+ ci; |
|
352 |
} |
|
353 |
||
354 |
bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { |
|
355 |
_card_ind++; |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
356 |
CardIdx_t ci; |
1374 | 357 |
if (_card_ind < SparsePRTEntry::CardsPerEntry && |
358 |
((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != |
|
359 |
SparsePRTEntry::NullEntry)) { |
|
360 |
card_index = compute_card_ind(ci); |
|
361 |
return true; |
|
362 |
} |
|
363 |
// Otherwise, must find the next valid entry. |
|
364 |
_card_ind = 0; |
|
365 |
||
366 |
if (_bl_ind != RSHashTable::NullEntry) { |
|
367 |
_bl_ind = _rsht->entry(_bl_ind)->next_index(); |
|
368 |
ci = find_first_card_in_list(); |
|
369 |
if (ci != SparsePRTEntry::NullEntry) { |
|
370 |
card_index = compute_card_ind(ci); |
|
371 |
return true; |
|
372 |
} |
|
373 |
} |
|
374 |
// If we didn't return above, must go to the next non-null table index. |
|
375 |
_tbl_ind++; |
|
376 |
while ((size_t)_tbl_ind < _rsht->capacity()) { |
|
377 |
_bl_ind = _rsht->_buckets[_tbl_ind]; |
|
378 |
ci = find_first_card_in_list(); |
|
379 |
if (ci != SparsePRTEntry::NullEntry) { |
|
380 |
card_index = compute_card_ind(ci); |
|
381 |
return true; |
|
382 |
} |
|
383 |
// Otherwise, try next entry. |
|
384 |
_tbl_ind++; |
|
385 |
} |
|
386 |
// Otherwise, there were no entry. |
|
387 |
return false; |
|
388 |
} |
|
389 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
390 |
bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const { |
1374 | 391 |
SparsePRTEntry* e = entry_for_region_ind(region_index); |
392 |
return (e != NULL && e->contains_card(card_index)); |
|
393 |
} |
|
394 |
||
395 |
size_t RSHashTable::mem_size() const { |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
396 |
return sizeof(this) + |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
397 |
capacity() * (sizeof(SparsePRTEntry) + sizeof(int)); |
1374 | 398 |
} |
399 |
||
400 |
// ---------------------------------------------------------------------- |
|
401 |
||
402 |
SparsePRT* SparsePRT::_head_expanded_list = NULL; |
|
403 |
||
404 |
void SparsePRT::add_to_expanded_list(SparsePRT* sprt) { |
|
405 |
// We could expand multiple times in a pause -- only put on list once. |
|
406 |
if (sprt->expanded()) return; |
|
407 |
sprt->set_expanded(true); |
|
408 |
SparsePRT* hd = _head_expanded_list; |
|
409 |
while (true) { |
|
410 |
sprt->_next_expanded = hd; |
|
411 |
SparsePRT* res = |
|
412 |
(SparsePRT*) |
|
413 |
Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd); |
|
414 |
if (res == hd) return; |
|
415 |
else hd = res; |
|
416 |
} |
|
417 |
} |
|
418 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
419 |
|
1374 | 420 |
SparsePRT* SparsePRT::get_from_expanded_list() { |
421 |
SparsePRT* hd = _head_expanded_list; |
|
422 |
while (hd != NULL) { |
|
423 |
SparsePRT* next = hd->next_expanded(); |
|
424 |
SparsePRT* res = |
|
425 |
(SparsePRT*) |
|
426 |
Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd); |
|
427 |
if (res == hd) { |
|
428 |
hd->set_next_expanded(NULL); |
|
429 |
return hd; |
|
430 |
} else { |
|
431 |
hd = res; |
|
432 |
} |
|
433 |
} |
|
434 |
return NULL; |
|
435 |
} |
|
436 |
||
437 |
||
438 |
void SparsePRT::cleanup_all() { |
|
439 |
// First clean up all expanded tables so they agree on next and cur. |
|
440 |
SparsePRT* sprt = get_from_expanded_list(); |
|
441 |
while (sprt != NULL) { |
|
442 |
sprt->cleanup(); |
|
443 |
sprt = get_from_expanded_list(); |
|
444 |
} |
|
445 |
// Now delete all deleted RSHashTables. |
|
446 |
RSHashTable* rsht = RSHashTable::get_from_deleted_list(); |
|
447 |
while (rsht != NULL) { |
|
448 |
#if SPARSE_PRT_VERBOSE |
|
449 |
gclog_or_tty->print_cr("About to delete RSHT " PTR_FORMAT ".", rsht); |
|
450 |
#endif |
|
451 |
delete rsht; |
|
452 |
rsht = RSHashTable::get_from_deleted_list(); |
|
453 |
} |
|
454 |
} |
|
455 |
||
456 |
||
457 |
SparsePRT::SparsePRT(HeapRegion* hr) : |
|
458 |
_expanded(false), _next_expanded(NULL) |
|
459 |
{ |
|
460 |
_cur = new RSHashTable(InitialCapacity); |
|
461 |
_next = _cur; |
|
462 |
} |
|
463 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
464 |
|
1374 | 465 |
SparsePRT::~SparsePRT() { |
466 |
assert(_next != NULL && _cur != NULL, "Inv"); |
|
467 |
if (_cur != _next) { delete _cur; } |
|
468 |
delete _next; |
|
469 |
} |
|
470 |
||
471 |
||
472 |
size_t SparsePRT::mem_size() const { |
|
473 |
// We ignore "_cur" here, because it either = _next, or else it is |
|
474 |
// on the deleted list. |
|
475 |
return sizeof(this) + _next->mem_size(); |
|
476 |
} |
|
477 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
478 |
bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) { |
1374 | 479 |
#if SPARSE_PRT_VERBOSE |
480 |
gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", |
|
481 |
card_index, region_id, _hr->hrs_index()); |
|
482 |
#endif |
|
483 |
if (_next->occupied_entries() * 2 > _next->capacity()) { |
|
484 |
expand(); |
|
485 |
} |
|
486 |
return _next->add_card(region_id, card_index); |
|
487 |
} |
|
488 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
489 |
bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { |
1374 | 490 |
return _next->get_cards(region_id, cards); |
491 |
} |
|
492 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
493 |
bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
1374 | 494 |
return _next->delete_entry(region_id); |
495 |
} |
|
496 |
||
497 |
void SparsePRT::clear() { |
|
498 |
// If they differ, _next is bigger then cur, so next has no chance of |
|
499 |
// being the initial size. |
|
500 |
if (_next != _cur) { |
|
501 |
delete _next; |
|
502 |
} |
|
503 |
||
504 |
if (_cur->capacity() != InitialCapacity) { |
|
505 |
delete _cur; |
|
506 |
_cur = new RSHashTable(InitialCapacity); |
|
507 |
} else { |
|
508 |
_cur->clear(); |
|
509 |
} |
|
510 |
_next = _cur; |
|
511 |
} |
|
512 |
||
513 |
void SparsePRT::cleanup() { |
|
514 |
// Make sure that the current and next tables agree. (Another mechanism |
|
515 |
// takes care of deleting now-unused tables.) |
|
516 |
_cur = _next; |
|
2143
61babb9fbd6f
6810698: G1: two small bugs in the sparse remembered sets
tonyp
parents:
1374
diff
changeset
|
517 |
set_expanded(false); |
1374 | 518 |
} |
519 |
||
520 |
void SparsePRT::expand() { |
|
521 |
RSHashTable* last = _next; |
|
522 |
_next = new RSHashTable(last->capacity() * 2); |
|
523 |
||
524 |
#if SPARSE_PRT_VERBOSE |
|
525 |
gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.", |
|
526 |
_hr->hrs_index(), _next->capacity()); |
|
527 |
#endif |
|
528 |
for (size_t i = 0; i < last->capacity(); i++) { |
|
529 |
SparsePRTEntry* e = last->entry((int)i); |
|
530 |
if (e->valid_entry()) { |
|
531 |
#if SPARSE_PRT_VERBOSE |
|
532 |
gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", |
|
533 |
e->r_ind()); |
|
534 |
#endif |
|
535 |
_next->add_entry(e); |
|
536 |
} |
|
537 |
} |
|
538 |
if (last != _cur) |
|
539 |
RSHashTable::add_to_deleted_list(last); |
|
540 |
add_to_expanded_list(this); |
|
541 |
} |