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