author | jwilhelm |
Thu, 03 Oct 2013 21:36:29 +0200 | |
changeset 20398 | b206c580c45f |
parent 17108 | cf72dcf9a8f2 |
child 22234 | da823d78ad65 |
permissions | -rw-r--r-- |
1374 | 1 |
/* |
12381
1438e0fbfa27
7157073: G1: type change size_t -> uint for region counts / indexes
tonyp
parents:
9989
diff
changeset
|
2 |
* Copyright (c) 2001, 2012, Oracle and/or its affiliates. All rights reserved. |
1374 | 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 |
* |
|
5547
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
4902
diff
changeset
|
19 |
* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
4902
diff
changeset
|
20 |
* or visit www.oracle.com if you need additional information or have any |
f4b087cbb361
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
4902
diff
changeset
|
21 |
* questions. |
1374 | 22 |
* |
23 |
*/ |
|
24 |
||
7397 | 25 |
#include "precompiled.hpp" |
26 |
#include "gc_implementation/g1/heapRegion.hpp" |
|
27 |
#include "gc_implementation/g1/heapRegionRemSet.hpp" |
|
28 |
#include "gc_implementation/g1/sparsePRT.hpp" |
|
29 |
#include "memory/allocation.inline.hpp" |
|
30 |
#include "memory/cardTableModRefBS.hpp" |
|
31 |
#include "memory/space.inline.hpp" |
|
32 |
#include "runtime/mutexLocker.hpp" |
|
1374 | 33 |
|
34 |
#define SPARSE_PRT_VERBOSE 0 |
|
35 |
||
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
36 |
#define UNROLL_CARD_LOOPS 1 |
1374 | 37 |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
38 |
void SparsePRTEntry::init(RegionIdx_t region_ind) { |
1374 | 39 |
_region_ind = region_ind; |
40 |
_next_index = NullEntry; |
|
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
41 |
|
1374 | 42 |
#if UNROLL_CARD_LOOPS |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
43 |
assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
44 |
for (int i = 0; i < cards_num(); i += UnrollFactor) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
45 |
_cards[i] = NullEntry; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
46 |
_cards[i + 1] = NullEntry; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
47 |
_cards[i + 2] = NullEntry; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
48 |
_cards[i + 3] = NullEntry; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
49 |
} |
1374 | 50 |
#else |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
51 |
for (int i = 0; i < cards_num(); i++) |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
52 |
_cards[i] = NullEntry; |
1374 | 53 |
#endif |
54 |
} |
|
55 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
56 |
bool SparsePRTEntry::contains_card(CardIdx_t card_index) const { |
1374 | 57 |
#if UNROLL_CARD_LOOPS |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
58 |
assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
59 |
for (int i = 0; i < cards_num(); i += UnrollFactor) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
60 |
if (_cards[i] == card_index || |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
61 |
_cards[i + 1] == card_index || |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
62 |
_cards[i + 2] == card_index || |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
63 |
_cards[i + 3] == card_index) return true; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
64 |
} |
1374 | 65 |
#else |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
66 |
for (int i = 0; i < cards_num(); i++) { |
1374 | 67 |
if (_cards[i] == card_index) return true; |
68 |
} |
|
69 |
#endif |
|
70 |
// Otherwise, we're full. |
|
71 |
return false; |
|
72 |
} |
|
73 |
||
74 |
int SparsePRTEntry::num_valid_cards() const { |
|
75 |
int sum = 0; |
|
76 |
#if UNROLL_CARD_LOOPS |
|
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
77 |
assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
78 |
for (int i = 0; i < cards_num(); i += UnrollFactor) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
79 |
sum += (_cards[i] != NullEntry); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
80 |
sum += (_cards[i + 1] != NullEntry); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
81 |
sum += (_cards[i + 2] != NullEntry); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
82 |
sum += (_cards[i + 3] != NullEntry); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
83 |
} |
1374 | 84 |
#else |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
85 |
for (int i = 0; i < cards_num(); i++) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
86 |
sum += (_cards[i] != NullEntry); |
1374 | 87 |
} |
88 |
#endif |
|
89 |
// Otherwise, we're full. |
|
90 |
return sum; |
|
91 |
} |
|
92 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
93 |
SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) { |
1374 | 94 |
#if UNROLL_CARD_LOOPS |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
95 |
assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
96 |
CardIdx_t c; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
97 |
for (int i = 0; i < cards_num(); i += UnrollFactor) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
98 |
c = _cards[i]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
99 |
if (c == card_index) return found; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
100 |
if (c == NullEntry) { _cards[i] = card_index; return added; } |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
101 |
c = _cards[i + 1]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
102 |
if (c == card_index) return found; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
103 |
if (c == NullEntry) { _cards[i + 1] = card_index; return added; } |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
104 |
c = _cards[i + 2]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
105 |
if (c == card_index) return found; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
106 |
if (c == NullEntry) { _cards[i + 2] = card_index; return added; } |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
107 |
c = _cards[i + 3]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
108 |
if (c == card_index) return found; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
109 |
if (c == NullEntry) { _cards[i + 3] = card_index; return added; } |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
110 |
} |
1374 | 111 |
#else |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
112 |
for (int i = 0; i < cards_num(); i++) { |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
113 |
CardIdx_t c = _cards[i]; |
1374 | 114 |
if (c == card_index) return found; |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
115 |
if (c == NullEntry) { _cards[i] = card_index; return added; } |
1374 | 116 |
} |
117 |
#endif |
|
118 |
// Otherwise, we're full. |
|
119 |
return overflow; |
|
120 |
} |
|
121 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
122 |
void SparsePRTEntry::copy_cards(CardIdx_t* cards) const { |
1374 | 123 |
#if UNROLL_CARD_LOOPS |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
124 |
assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
125 |
for (int i = 0; i < cards_num(); i += UnrollFactor) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
126 |
cards[i] = _cards[i]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
127 |
cards[i + 1] = _cards[i + 1]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
128 |
cards[i + 2] = _cards[i + 2]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
129 |
cards[i + 3] = _cards[i + 3]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
130 |
} |
1374 | 131 |
#else |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
132 |
for (int i = 0; i < cards_num(); i++) { |
1374 | 133 |
cards[i] = _cards[i]; |
134 |
} |
|
135 |
#endif |
|
136 |
} |
|
137 |
||
138 |
void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const { |
|
139 |
copy_cards(&e->_cards[0]); |
|
140 |
} |
|
141 |
||
142 |
// ---------------------------------------------------------------------- |
|
143 |
||
144 |
RSHashTable::RSHashTable(size_t capacity) : |
|
145 |
_capacity(capacity), _capacity_mask(capacity-1), |
|
146 |
_occupied_entries(0), _occupied_cards(0), |
|
13195 | 147 |
_entries((SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, SparsePRTEntry::size() * capacity, mtGC)), |
148 |
_buckets(NEW_C_HEAP_ARRAY(int, capacity, mtGC)), |
|
1374 | 149 |
_free_list(NullEntry), _free_region(0) |
150 |
{ |
|
151 |
clear(); |
|
152 |
} |
|
153 |
||
154 |
RSHashTable::~RSHashTable() { |
|
155 |
if (_entries != NULL) { |
|
13195 | 156 |
FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries, mtGC); |
1374 | 157 |
_entries = NULL; |
158 |
} |
|
159 |
if (_buckets != NULL) { |
|
13195 | 160 |
FREE_C_HEAP_ARRAY(int, _buckets, mtGC); |
1374 | 161 |
_buckets = NULL; |
162 |
} |
|
163 |
} |
|
164 |
||
165 |
void RSHashTable::clear() { |
|
166 |
_occupied_entries = 0; |
|
167 |
_occupied_cards = 0; |
|
168 |
guarantee(_entries != NULL, "INV"); |
|
169 |
guarantee(_buckets != NULL, "INV"); |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
170 |
|
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
171 |
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
|
172 |
"_capacity too large"); |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
173 |
|
1374 | 174 |
// This will put -1 == NullEntry in the key field of all entries. |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
175 |
memset(_entries, NullEntry, _capacity * SparsePRTEntry::size()); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
176 |
memset(_buckets, NullEntry, _capacity * sizeof(int)); |
1374 | 177 |
_free_list = NullEntry; |
178 |
_free_region = 0; |
|
179 |
} |
|
180 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
181 |
bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) { |
1374 | 182 |
SparsePRTEntry* e = entry_for_region_ind_create(region_ind); |
183 |
assert(e != NULL && e->r_ind() == region_ind, |
|
184 |
"Postcondition of call above."); |
|
185 |
SparsePRTEntry::AddCardResult res = e->add_card(card_index); |
|
186 |
if (res == SparsePRTEntry::added) _occupied_cards++; |
|
187 |
#if SPARSE_PRT_VERBOSE |
|
188 |
gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", |
|
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
189 |
pointer_delta(e, _entries, SparsePRTEntry::size()), |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
190 |
e->num_valid_cards()); |
1374 | 191 |
#endif |
192 |
assert(e->num_valid_cards() > 0, "Postcondition"); |
|
193 |
return res != SparsePRTEntry::overflow; |
|
194 |
} |
|
195 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
196 |
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
|
197 |
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
|
198 |
int cur_ind = _buckets[ind]; |
1374 | 199 |
SparsePRTEntry* cur; |
200 |
while (cur_ind != NullEntry && |
|
201 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
202 |
cur_ind = cur->next_index(); |
|
203 |
} |
|
204 |
||
205 |
if (cur_ind == NullEntry) return false; |
|
206 |
// Otherwise... |
|
207 |
assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); |
|
208 |
assert(cur->num_valid_cards() > 0, "Inv"); |
|
209 |
cur->copy_cards(cards); |
|
210 |
return true; |
|
211 |
} |
|
212 |
||
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
213 |
SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
214 |
int ind = (int) (region_ind & capacity_mask()); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
215 |
int cur_ind = _buckets[ind]; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
216 |
SparsePRTEntry* cur; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
217 |
while (cur_ind != NullEntry && |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
218 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
219 |
cur_ind = cur->next_index(); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
220 |
} |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
221 |
|
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
222 |
if (cur_ind == NullEntry) return NULL; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
223 |
// Otherwise... |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
224 |
assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
225 |
assert(cur->num_valid_cards() > 0, "Inv"); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
226 |
return cur; |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
227 |
} |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
228 |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
229 |
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
|
230 |
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
|
231 |
int* prev_loc = &_buckets[ind]; |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
232 |
int cur_ind = *prev_loc; |
1374 | 233 |
SparsePRTEntry* cur; |
234 |
while (cur_ind != NullEntry && |
|
235 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
236 |
prev_loc = cur->next_index_addr(); |
|
237 |
cur_ind = *prev_loc; |
|
238 |
} |
|
239 |
||
240 |
if (cur_ind == NullEntry) return false; |
|
241 |
// Otherwise, splice out "cur". |
|
242 |
*prev_loc = cur->next_index(); |
|
243 |
_occupied_cards -= cur->num_valid_cards(); |
|
244 |
free_entry(cur_ind); |
|
245 |
_occupied_entries--; |
|
246 |
return true; |
|
247 |
} |
|
248 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
249 |
SparsePRTEntry* |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
250 |
RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const { |
1374 | 251 |
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
|
252 |
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
|
253 |
int cur_ind = _buckets[ind]; |
1374 | 254 |
SparsePRTEntry* cur; |
255 |
while (cur_ind != NullEntry && |
|
256 |
(cur = entry(cur_ind))->r_ind() != region_ind) { |
|
257 |
cur_ind = cur->next_index(); |
|
258 |
} |
|
259 |
||
260 |
if (cur_ind != NullEntry) { |
|
261 |
assert(cur->r_ind() == region_ind, "Loop postcondition + test"); |
|
262 |
return cur; |
|
263 |
} else { |
|
264 |
return NULL; |
|
265 |
} |
|
266 |
} |
|
267 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
268 |
SparsePRTEntry* |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
269 |
RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) { |
1374 | 270 |
SparsePRTEntry* res = entry_for_region_ind(region_ind); |
271 |
if (res == NULL) { |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
272 |
int new_ind = alloc_entry(); |
1374 | 273 |
assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room."); |
274 |
res = entry(new_ind); |
|
275 |
res->init(region_ind); |
|
276 |
// Insert at front. |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
277 |
int ind = (int) (region_ind & capacity_mask()); |
1374 | 278 |
res->set_next_index(_buckets[ind]); |
279 |
_buckets[ind] = new_ind; |
|
280 |
_occupied_entries++; |
|
281 |
} |
|
282 |
return res; |
|
283 |
} |
|
284 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
285 |
int RSHashTable::alloc_entry() { |
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
286 |
int res; |
1374 | 287 |
if (_free_list != NullEntry) { |
288 |
res = _free_list; |
|
289 |
_free_list = entry(res)->next_index(); |
|
290 |
return res; |
|
291 |
} else if ((size_t) _free_region+1 < capacity()) { |
|
292 |
res = _free_region; |
|
293 |
_free_region++; |
|
294 |
return res; |
|
295 |
} else { |
|
296 |
return NullEntry; |
|
297 |
} |
|
298 |
} |
|
299 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
300 |
void RSHashTable::free_entry(int fi) { |
1374 | 301 |
entry(fi)->set_next_index(_free_list); |
302 |
_free_list = fi; |
|
303 |
} |
|
304 |
||
305 |
void RSHashTable::add_entry(SparsePRTEntry* e) { |
|
306 |
assert(e->num_valid_cards() > 0, "Precondition."); |
|
307 |
SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind()); |
|
308 |
e->copy_cards(e2); |
|
309 |
_occupied_cards += e2->num_valid_cards(); |
|
310 |
assert(e2->num_valid_cards() > 0, "Postcondition."); |
|
311 |
} |
|
312 |
||
6983
a8c50cedbce9
6991377: G1: race between concurrent refinement and humongous object allocation
tonyp
parents:
6981
diff
changeset
|
313 |
CardIdx_t RSHashTableIter::find_first_card_in_list() { |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
314 |
CardIdx_t res; |
1374 | 315 |
while (_bl_ind != RSHashTable::NullEntry) { |
316 |
res = _rsht->entry(_bl_ind)->card(0); |
|
317 |
if (res != SparsePRTEntry::NullEntry) { |
|
318 |
return res; |
|
319 |
} else { |
|
320 |
_bl_ind = _rsht->entry(_bl_ind)->next_index(); |
|
321 |
} |
|
322 |
} |
|
323 |
// Otherwise, none found: |
|
324 |
return SparsePRTEntry::NullEntry; |
|
325 |
} |
|
326 |
||
6983
a8c50cedbce9
6991377: G1: race between concurrent refinement and humongous object allocation
tonyp
parents:
6981
diff
changeset
|
327 |
size_t RSHashTableIter::compute_card_ind(CardIdx_t ci) { |
6981
ecfe524b1fa7
6992189: G1: inconsistent base used in sparse rem set iterator
tonyp
parents:
6250
diff
changeset
|
328 |
return (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) + ci; |
1374 | 329 |
} |
330 |
||
6983
a8c50cedbce9
6991377: G1: race between concurrent refinement and humongous object allocation
tonyp
parents:
6981
diff
changeset
|
331 |
bool RSHashTableIter::has_next(size_t& card_index) { |
1374 | 332 |
_card_ind++; |
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
333 |
CardIdx_t ci; |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
334 |
if (_card_ind < SparsePRTEntry::cards_num() && |
1374 | 335 |
((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != |
336 |
SparsePRTEntry::NullEntry)) { |
|
337 |
card_index = compute_card_ind(ci); |
|
338 |
return true; |
|
339 |
} |
|
340 |
// Otherwise, must find the next valid entry. |
|
341 |
_card_ind = 0; |
|
342 |
||
343 |
if (_bl_ind != RSHashTable::NullEntry) { |
|
344 |
_bl_ind = _rsht->entry(_bl_ind)->next_index(); |
|
345 |
ci = find_first_card_in_list(); |
|
346 |
if (ci != SparsePRTEntry::NullEntry) { |
|
347 |
card_index = compute_card_ind(ci); |
|
348 |
return true; |
|
349 |
} |
|
350 |
} |
|
351 |
// If we didn't return above, must go to the next non-null table index. |
|
352 |
_tbl_ind++; |
|
353 |
while ((size_t)_tbl_ind < _rsht->capacity()) { |
|
354 |
_bl_ind = _rsht->_buckets[_tbl_ind]; |
|
355 |
ci = find_first_card_in_list(); |
|
356 |
if (ci != SparsePRTEntry::NullEntry) { |
|
357 |
card_index = compute_card_ind(ci); |
|
358 |
return true; |
|
359 |
} |
|
360 |
// Otherwise, try next entry. |
|
361 |
_tbl_ind++; |
|
362 |
} |
|
363 |
// Otherwise, there were no entry. |
|
364 |
return false; |
|
365 |
} |
|
366 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
367 |
bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const { |
1374 | 368 |
SparsePRTEntry* e = entry_for_region_ind(region_index); |
369 |
return (e != NULL && e->contains_card(card_index)); |
|
370 |
} |
|
371 |
||
372 |
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
|
373 |
return sizeof(this) + |
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
374 |
capacity() * (SparsePRTEntry::size() + sizeof(int)); |
1374 | 375 |
} |
376 |
||
377 |
// ---------------------------------------------------------------------- |
|
378 |
||
379 |
SparsePRT* SparsePRT::_head_expanded_list = NULL; |
|
380 |
||
381 |
void SparsePRT::add_to_expanded_list(SparsePRT* sprt) { |
|
382 |
// We could expand multiple times in a pause -- only put on list once. |
|
383 |
if (sprt->expanded()) return; |
|
384 |
sprt->set_expanded(true); |
|
385 |
SparsePRT* hd = _head_expanded_list; |
|
386 |
while (true) { |
|
387 |
sprt->_next_expanded = hd; |
|
388 |
SparsePRT* res = |
|
389 |
(SparsePRT*) |
|
390 |
Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd); |
|
391 |
if (res == hd) return; |
|
392 |
else hd = res; |
|
393 |
} |
|
394 |
} |
|
395 |
||
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
396 |
|
1374 | 397 |
SparsePRT* SparsePRT::get_from_expanded_list() { |
398 |
SparsePRT* hd = _head_expanded_list; |
|
399 |
while (hd != NULL) { |
|
400 |
SparsePRT* next = hd->next_expanded(); |
|
401 |
SparsePRT* res = |
|
402 |
(SparsePRT*) |
|
403 |
Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd); |
|
404 |
if (res == hd) { |
|
405 |
hd->set_next_expanded(NULL); |
|
406 |
return hd; |
|
407 |
} else { |
|
408 |
hd = res; |
|
409 |
} |
|
410 |
} |
|
411 |
return NULL; |
|
412 |
} |
|
413 |
||
8072 | 414 |
void SparsePRT::reset_for_cleanup_tasks() { |
415 |
_head_expanded_list = NULL; |
|
416 |
} |
|
417 |
||
418 |
void SparsePRT::do_cleanup_work(SparsePRTCleanupTask* sprt_cleanup_task) { |
|
419 |
if (should_be_on_expanded_list()) { |
|
420 |
sprt_cleanup_task->add(this); |
|
421 |
} |
|
422 |
} |
|
423 |
||
424 |
void SparsePRT::finish_cleanup_task(SparsePRTCleanupTask* sprt_cleanup_task) { |
|
425 |
assert(ParGCRareEvent_lock->owned_by_self(), "pre-condition"); |
|
426 |
SparsePRT* head = sprt_cleanup_task->head(); |
|
427 |
SparsePRT* tail = sprt_cleanup_task->tail(); |
|
428 |
if (head != NULL) { |
|
429 |
assert(tail != NULL, "if head is not NULL, so should tail"); |
|
430 |
||
431 |
tail->set_next_expanded(_head_expanded_list); |
|
432 |
_head_expanded_list = head; |
|
433 |
} else { |
|
434 |
assert(tail == NULL, "if head is NULL, so should tail"); |
|
435 |
} |
|
436 |
} |
|
437 |
||
438 |
bool SparsePRT::should_be_on_expanded_list() { |
|
439 |
if (_expanded) { |
|
440 |
assert(_cur != _next, "if _expanded is true, cur should be != _next"); |
|
441 |
} else { |
|
442 |
assert(_cur == _next, "if _expanded is false, cur should be == _next"); |
|
443 |
} |
|
444 |
return expanded(); |
|
445 |
} |
|
1374 | 446 |
|
447 |
void SparsePRT::cleanup_all() { |
|
448 |
// First clean up all expanded tables so they agree on next and cur. |
|
449 |
SparsePRT* sprt = get_from_expanded_list(); |
|
450 |
while (sprt != NULL) { |
|
451 |
sprt->cleanup(); |
|
452 |
sprt = get_from_expanded_list(); |
|
453 |
} |
|
454 |
} |
|
455 |
||
456 |
||
457 |
SparsePRT::SparsePRT(HeapRegion* hr) : |
|
6250
5680f968c721
6930581: G1: assert(ParallelGCThreads > 1 || n_yielded() == _hrrs->occupied(),"Should have yielded all the ..
johnc
parents:
5547
diff
changeset
|
458 |
_hr(hr), _expanded(false), _next_expanded(NULL) |
1374 | 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 |
12381
1438e0fbfa27
7157073: G1: type change size_t -> uint for region counts / indexes
tonyp
parents:
9989
diff
changeset
|
480 |
gclog_or_tty->print_cr(" Adding card %d from region %d to region %u sparse.", |
9989 | 481 |
card_index, region_id, _hr->hrs_index()); |
1374 | 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 |
||
4902
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
493 |
SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
494 |
return _next->get_entry(region_id); |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
495 |
} |
991aaddb5165
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
4100
diff
changeset
|
496 |
|
2996
1097030e5ec3
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
2143
diff
changeset
|
497 |
bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
1374 | 498 |
return _next->delete_entry(region_id); |
499 |
} |
|
500 |
||
501 |
void SparsePRT::clear() { |
|
502 |
// If they differ, _next is bigger then cur, so next has no chance of |
|
503 |
// being the initial size. |
|
504 |
if (_next != _cur) { |
|
505 |
delete _next; |
|
506 |
} |
|
507 |
||
508 |
if (_cur->capacity() != InitialCapacity) { |
|
509 |
delete _cur; |
|
510 |
_cur = new RSHashTable(InitialCapacity); |
|
511 |
} else { |
|
512 |
_cur->clear(); |
|
513 |
} |
|
514 |
_next = _cur; |
|
8072 | 515 |
_expanded = false; |
1374 | 516 |
} |
517 |
||
518 |
void SparsePRT::cleanup() { |
|
4100 | 519 |
// Make sure that the current and next tables agree. |
520 |
if (_cur != _next) { |
|
521 |
delete _cur; |
|
522 |
} |
|
1374 | 523 |
_cur = _next; |
2143
61babb9fbd6f
6810698: G1: two small bugs in the sparse remembered sets
tonyp
parents:
1374
diff
changeset
|
524 |
set_expanded(false); |
1374 | 525 |
} |
526 |
||
527 |
void SparsePRT::expand() { |
|
528 |
RSHashTable* last = _next; |
|
529 |
_next = new RSHashTable(last->capacity() * 2); |
|
530 |
||
531 |
#if SPARSE_PRT_VERBOSE |
|
12381
1438e0fbfa27
7157073: G1: type change size_t -> uint for region counts / indexes
tonyp
parents:
9989
diff
changeset
|
532 |
gclog_or_tty->print_cr(" Expanded sparse table for %u to %d.", |
9989 | 533 |
_hr->hrs_index(), _next->capacity()); |
1374 | 534 |
#endif |
535 |
for (size_t i = 0; i < last->capacity(); i++) { |
|
536 |
SparsePRTEntry* e = last->entry((int)i); |
|
537 |
if (e->valid_entry()) { |
|
538 |
#if SPARSE_PRT_VERBOSE |
|
539 |
gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", |
|
540 |
e->r_ind()); |
|
541 |
#endif |
|
542 |
_next->add_entry(e); |
|
543 |
} |
|
544 |
} |
|
4100 | 545 |
if (last != _cur) { |
546 |
delete last; |
|
547 |
} |
|
1374 | 548 |
add_to_expanded_list(this); |
549 |
} |
|
8072 | 550 |
|
551 |
void SparsePRTCleanupTask::add(SparsePRT* sprt) { |
|
552 |
assert(sprt->should_be_on_expanded_list(), "pre-condition"); |
|
553 |
||
554 |
sprt->set_next_expanded(NULL); |
|
555 |
if (_tail != NULL) { |
|
556 |
_tail->set_next_expanded(sprt); |
|
557 |
} else { |
|
558 |
_head = sprt; |
|
559 |
} |
|
560 |
_tail = sprt; |
|
561 |
} |