Mercurial > hg > truffle
annotate src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 2173:97ba643ea3ed
7014261: G1: RSet-related failures
Summary: A race between the concurrent cleanup thread and the VM thread while it is processing the "expanded sparse table list" causes both threads to try to free the same sparse table entry and either causes one of the threads to fail or leaves the entry in an inconsistent state. The solution is purge all entries on the expanded list that correspond go regions that are being cleaned up.
Reviewed-by: brutisso, johnc
| author | tonyp |
|---|---|
| date | Tue, 25 Jan 2011 17:58:19 -0500 |
| parents | f95d63e2154a |
| children | c3f1170908be |
| 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 |
| 484 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", | |
| 485 card_index, region_id, _hr->hrs_index()); | |
| 486 #endif | |
| 487 if (_next->occupied_entries() * 2 > _next->capacity()) { | |
| 488 expand(); | |
| 489 } | |
| 490 return _next->add_card(region_id, card_index); | |
| 491 } | |
| 492 | |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
493 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { |
| 342 | 494 return _next->get_cards(region_id, cards); |
| 495 } | |
| 496 | |
|
1261
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
497 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
498 return _next->get_entry(region_id); |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
499 } |
|
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
500 |
|
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
501 bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
| 342 | 502 return _next->delete_entry(region_id); |
| 503 } | |
| 504 | |
| 505 void SparsePRT::clear() { | |
| 506 // If they differ, _next is bigger then cur, so next has no chance of | |
| 507 // being the initial size. | |
| 508 if (_next != _cur) { | |
| 509 delete _next; | |
| 510 } | |
| 511 | |
| 512 if (_cur->capacity() != InitialCapacity) { | |
| 513 delete _cur; | |
| 514 _cur = new RSHashTable(InitialCapacity); | |
| 515 } else { | |
| 516 _cur->clear(); | |
| 517 } | |
| 518 _next = _cur; | |
| 2173 | 519 _expanded = false; |
| 342 | 520 } |
| 521 | |
| 522 void SparsePRT::cleanup() { | |
| 1045 | 523 // Make sure that the current and next tables agree. |
| 524 if (_cur != _next) { | |
| 525 delete _cur; | |
| 526 } | |
| 342 | 527 _cur = _next; |
|
617
0db4adb6e914
6810698: G1: two small bugs in the sparse remembered sets
tonyp
parents:
342
diff
changeset
|
528 set_expanded(false); |
| 342 | 529 } |
| 530 | |
| 531 void SparsePRT::expand() { | |
| 532 RSHashTable* last = _next; | |
| 533 _next = new RSHashTable(last->capacity() * 2); | |
| 534 | |
| 535 #if SPARSE_PRT_VERBOSE | |
| 536 gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.", | |
| 537 _hr->hrs_index(), _next->capacity()); | |
| 538 #endif | |
| 539 for (size_t i = 0; i < last->capacity(); i++) { | |
| 540 SparsePRTEntry* e = last->entry((int)i); | |
| 541 if (e->valid_entry()) { | |
| 542 #if SPARSE_PRT_VERBOSE | |
| 543 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", | |
| 544 e->r_ind()); | |
| 545 #endif | |
| 546 _next->add_entry(e); | |
| 547 } | |
| 548 } | |
| 1045 | 549 if (last != _cur) { |
| 550 delete last; | |
| 551 } | |
| 342 | 552 add_to_expanded_list(this); |
| 553 } | |
| 2173 | 554 |
| 555 void SparsePRTCleanupTask::add(SparsePRT* sprt) { | |
| 556 assert(sprt->should_be_on_expanded_list(), "pre-condition"); | |
| 557 | |
| 558 sprt->set_next_expanded(NULL); | |
| 559 if (_tail != NULL) { | |
| 560 _tail->set_next_expanded(sprt); | |
| 561 } else { | |
| 562 _head = sprt; | |
| 563 } | |
| 564 _tail = sprt; | |
| 565 } |