Mercurial > hg > graal-jvmci-8
annotate src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 2152:0fa27f37d4d4
6977804: G1: remove the zero-filling thread
Summary: This changeset removes the zero-filling thread from G1 and collapses the two free region lists we had before (the "free" and "unclean" lists) into one. The new free list uses the new heap region sets / lists abstractions that we'll ultimately use it to keep track of all regions in the heap. A heap region set was also introduced for the humongous regions. Finally, this change increases the concurrency between the thread that completes freeing regions (after a cleanup pause) and the rest of the system (before we'd have to wait for said thread to complete before allocating a new region). The changest also includes a lot of refactoring and code simplification.
Reviewed-by: jcoomes, johnc
author | tonyp |
---|---|
date | Wed, 19 Jan 2011 19:30:42 -0500 |
parents | f95d63e2154a |
children | 97ba643ea3ed |
rev | line source |
---|---|
342 | 1 /* |
1972 | 2 * Copyright (c) 2001, 2010, 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 | |
418 | |
419 void SparsePRT::cleanup_all() { | |
420 // First clean up all expanded tables so they agree on next and cur. | |
421 SparsePRT* sprt = get_from_expanded_list(); | |
422 while (sprt != NULL) { | |
423 sprt->cleanup(); | |
424 sprt = get_from_expanded_list(); | |
425 } | |
426 } | |
427 | |
428 | |
429 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
|
430 _hr(hr), _expanded(false), _next_expanded(NULL) |
342 | 431 { |
432 _cur = new RSHashTable(InitialCapacity); | |
433 _next = _cur; | |
434 } | |
435 | |
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
436 |
342 | 437 SparsePRT::~SparsePRT() { |
438 assert(_next != NULL && _cur != NULL, "Inv"); | |
439 if (_cur != _next) { delete _cur; } | |
440 delete _next; | |
441 } | |
442 | |
443 | |
444 size_t SparsePRT::mem_size() const { | |
445 // We ignore "_cur" here, because it either = _next, or else it is | |
446 // on the deleted list. | |
447 return sizeof(this) + _next->mem_size(); | |
448 } | |
449 | |
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
450 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) { |
342 | 451 #if SPARSE_PRT_VERBOSE |
452 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", | |
453 card_index, region_id, _hr->hrs_index()); | |
454 #endif | |
455 if (_next->occupied_entries() * 2 > _next->capacity()) { | |
456 expand(); | |
457 } | |
458 return _next->add_card(region_id, card_index); | |
459 } | |
460 | |
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
461 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) { |
342 | 462 return _next->get_cards(region_id, cards); |
463 } | |
464 | |
1261
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
465 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) { |
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
466 return _next->get_entry(region_id); |
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
467 } |
0414c1049f15
6923991: G1: improve scalability of RSet scanning
iveresov
parents:
1045
diff
changeset
|
468 |
807
d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
johnc
parents:
617
diff
changeset
|
469 bool SparsePRT::delete_entry(RegionIdx_t region_id) { |
342 | 470 return _next->delete_entry(region_id); |
471 } | |
472 | |
473 void SparsePRT::clear() { | |
474 // If they differ, _next is bigger then cur, so next has no chance of | |
475 // being the initial size. | |
476 if (_next != _cur) { | |
477 delete _next; | |
478 } | |
479 | |
480 if (_cur->capacity() != InitialCapacity) { | |
481 delete _cur; | |
482 _cur = new RSHashTable(InitialCapacity); | |
483 } else { | |
484 _cur->clear(); | |
485 } | |
486 _next = _cur; | |
487 } | |
488 | |
489 void SparsePRT::cleanup() { | |
1045 | 490 // Make sure that the current and next tables agree. |
491 if (_cur != _next) { | |
492 delete _cur; | |
493 } | |
342 | 494 _cur = _next; |
617
0db4adb6e914
6810698: G1: two small bugs in the sparse remembered sets
tonyp
parents:
342
diff
changeset
|
495 set_expanded(false); |
342 | 496 } |
497 | |
498 void SparsePRT::expand() { | |
499 RSHashTable* last = _next; | |
500 _next = new RSHashTable(last->capacity() * 2); | |
501 | |
502 #if SPARSE_PRT_VERBOSE | |
503 gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.", | |
504 _hr->hrs_index(), _next->capacity()); | |
505 #endif | |
506 for (size_t i = 0; i < last->capacity(); i++) { | |
507 SparsePRTEntry* e = last->entry((int)i); | |
508 if (e->valid_entry()) { | |
509 #if SPARSE_PRT_VERBOSE | |
510 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", | |
511 e->r_ind()); | |
512 #endif | |
513 _next->add_entry(e); | |
514 } | |
515 } | |
1045 | 516 if (last != _cur) { |
517 delete last; | |
518 } | |
342 | 519 add_to_expanded_list(this); |
520 } |