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