Mercurial > hg > graal-jvmci-8
annotate src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 1708:a03ae377b2e8
6930581: G1: assert(ParallelGCThreads > 1 || n_yielded() == _hrrs->occupied(),"Should have yielded all the ..
Summary: During RSet updating, when ParallelGCThreads is zero, references that point into the collection set are added directly the referenced region's RSet. This can cause the sparse table in the RSet to expand. RSet scanning and the "occupied" routine will then operate on different instances of the sparse table causing the assert to trip. This may also cause some cards added post expansion to be missed during RSet scanning. When ParallelGCThreads is non-zero such references are recorded on the "references to be scanned" queue and the card containing the reference is recorded in a dirty card queue for use in the event of an evacuation failure. Employ the parallel code in the serial case to avoid expanding the RSets of regions in the collection set.
Reviewed-by: iveresov, ysr, tonyp
| author | johnc |
|---|---|
| date | Fri, 06 Aug 2010 10:17:21 -0700 |
| parents | c18cbe5936b8 |
| children | 9f4848ebbabd |
| 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 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
311 CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() { |
|
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 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
325 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) { |
| 342 | 326 return |
| 327 _heap_bot_card_ind | |
|
942
2c79770d1f6e
6819085: G1: use larger and/or user settable region size
tonyp
parents:
844
diff
changeset
|
328 + (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion) |
| 342 | 329 + ci; |
| 330 } | |
| 331 | |
| 332 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { | |
| 333 _card_ind++; | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
334 CardIdx_t ci; |
|
1261
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
335 if (_card_ind < SparsePRTEntry::cards_num() && |
| 342 | 336 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != |
| 337 SparsePRTEntry::NullEntry)) { | |
| 338 card_index = compute_card_ind(ci); | |
| 339 return true; | |
| 340 } | |
| 341 // Otherwise, must find the next valid entry. | |
| 342 _card_ind = 0; | |
| 343 | |
| 344 if (_bl_ind != RSHashTable::NullEntry) { | |
| 345 _bl_ind = _rsht->entry(_bl_ind)->next_index(); | |
| 346 ci = find_first_card_in_list(); | |
| 347 if (ci != SparsePRTEntry::NullEntry) { | |
| 348 card_index = compute_card_ind(ci); | |
| 349 return true; | |
| 350 } | |
| 351 } | |
| 352 // If we didn't return above, must go to the next non-null table index. | |
| 353 _tbl_ind++; | |
| 354 while ((size_t)_tbl_ind < _rsht->capacity()) { | |
| 355 _bl_ind = _rsht->_buckets[_tbl_ind]; | |
| 356 ci = find_first_card_in_list(); | |
| 357 if (ci != SparsePRTEntry::NullEntry) { | |
| 358 card_index = compute_card_ind(ci); | |
| 359 return true; | |
| 360 } | |
| 361 // Otherwise, try next entry. | |
| 362 _tbl_ind++; | |
| 363 } | |
| 364 // Otherwise, there were no entry. | |
| 365 return false; | |
| 366 } | |
| 367 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
368 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const { |
| 342 | 369 SparsePRTEntry* e = entry_for_region_ind(region_index); |
| 370 return (e != NULL && e->contains_card(card_index)); | |
| 371 } | |
| 372 | |
| 373 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
|
374 return sizeof(this) + |
|
1261
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
375 capacity() * (SparsePRTEntry::size() + sizeof(int)); |
| 342 | 376 } |
| 377 | |
| 378 // ---------------------------------------------------------------------- | |
| 379 | |
| 380 SparsePRT* SparsePRT::_head_expanded_list = NULL; | |
| 381 | |
| 382 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) { | |
| 383 // We could expand multiple times in a pause -- only put on list once. | |
| 384 if (sprt->expanded()) return; | |
| 385 sprt->set_expanded(true); | |
| 386 SparsePRT* hd = _head_expanded_list; | |
| 387 while (true) { | |
| 388 sprt->_next_expanded = hd; | |
| 389 SparsePRT* res = | |
| 390 (SparsePRT*) | |
| 391 Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd); | |
| 392 if (res == hd) return; | |
| 393 else hd = res; | |
| 394 } | |
| 395 } | |
| 396 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
397 |
| 342 | 398 SparsePRT* SparsePRT::get_from_expanded_list() { |
| 399 SparsePRT* hd = _head_expanded_list; | |
| 400 while (hd != NULL) { | |
| 401 SparsePRT* next = hd->next_expanded(); | |
| 402 SparsePRT* res = | |
| 403 (SparsePRT*) | |
| 404 Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd); | |
| 405 if (res == hd) { | |
| 406 hd->set_next_expanded(NULL); | |
| 407 return hd; | |
| 408 } else { | |
| 409 hd = res; | |
| 410 } | |
| 411 } | |
| 412 return NULL; | |
| 413 } | |
| 414 | |
| 415 | |
| 416 void SparsePRT::cleanup_all() { | |
| 417 // First clean up all expanded tables so they agree on next and cur. | |
| 418 SparsePRT* sprt = get_from_expanded_list(); | |
| 419 while (sprt != NULL) { | |
| 420 sprt->cleanup(); | |
| 421 sprt = get_from_expanded_list(); | |
| 422 } | |
| 423 } | |
| 424 | |
| 425 | |
| 426 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
|
427 _hr(hr), _expanded(false), _next_expanded(NULL) |
| 342 | 428 { |
| 429 _cur = new RSHashTable(InitialCapacity); | |
| 430 _next = _cur; | |
| 431 } | |
| 432 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
433 |
| 342 | 434 SparsePRT::~SparsePRT() { |
| 435 assert(_next != NULL && _cur != NULL, "Inv"); | |
| 436 if (_cur != _next) { delete _cur; } | |
| 437 delete _next; | |
| 438 } | |
| 439 | |
| 440 | |
| 441 size_t SparsePRT::mem_size() const { | |
| 442 // We ignore "_cur" here, because it either = _next, or else it is | |
| 443 // on the deleted list. | |
| 444 return sizeof(this) + _next->mem_size(); | |
| 445 } | |
| 446 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
447 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) { |
| 342 | 448 #if SPARSE_PRT_VERBOSE |
| 449 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", | |
| 450 card_index, region_id, _hr->hrs_index()); | |
| 451 #endif | |
| 452 if (_next->occupied_entries() * 2 > _next->capacity()) { | |
| 453 expand(); | |
| 454 } | |
| 455 return _next->add_card(region_id, card_index); | |
| 456 } | |
| 457 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
458 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { |
| 342 | 459 return _next->get_cards(region_id, cards); |
| 460 } | |
| 461 | |
|
1261
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
462 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
463 return _next->get_entry(region_id); |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
464 } |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
465 |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
466 bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
| 342 | 467 return _next->delete_entry(region_id); |
| 468 } | |
| 469 | |
| 470 void SparsePRT::clear() { | |
| 471 // If they differ, _next is bigger then cur, so next has no chance of | |
| 472 // being the initial size. | |
| 473 if (_next != _cur) { | |
| 474 delete _next; | |
| 475 } | |
| 476 | |
| 477 if (_cur->capacity() != InitialCapacity) { | |
| 478 delete _cur; | |
| 479 _cur = new RSHashTable(InitialCapacity); | |
| 480 } else { | |
| 481 _cur->clear(); | |
| 482 } | |
| 483 _next = _cur; | |
| 484 } | |
| 485 | |
| 486 void SparsePRT::cleanup() { | |
| 1045 | 487 // Make sure that the current and next tables agree. |
| 488 if (_cur != _next) { | |
| 489 delete _cur; | |
| 490 } | |
| 342 | 491 _cur = _next; |
|
617
0db4adb6e914
6810698: G1: two small bugs in the sparse remembered sets
tonyp
parents:
342
diff
changeset
|
492 set_expanded(false); |
| 342 | 493 } |
| 494 | |
| 495 void SparsePRT::expand() { | |
| 496 RSHashTable* last = _next; | |
| 497 _next = new RSHashTable(last->capacity() * 2); | |
| 498 | |
| 499 #if SPARSE_PRT_VERBOSE | |
| 500 gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.", | |
| 501 _hr->hrs_index(), _next->capacity()); | |
| 502 #endif | |
| 503 for (size_t i = 0; i < last->capacity(); i++) { | |
| 504 SparsePRTEntry* e = last->entry((int)i); | |
| 505 if (e->valid_entry()) { | |
| 506 #if SPARSE_PRT_VERBOSE | |
| 507 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", | |
| 508 e->r_ind()); | |
| 509 #endif | |
| 510 _next->add_entry(e); | |
| 511 } | |
| 512 } | |
| 1045 | 513 if (last != _cur) { |
| 514 delete last; | |
| 515 } | |
| 342 | 516 add_to_expanded_list(this); |
| 517 } |