Mon, 02 Aug 2010 12:51:43 -0700
6814437: G1: remove the _new_refs array
Summary: The per-worker _new_refs array is used to hold references that point into the collection set. It is populated during RSet updating and subsequently processed. In the event of an evacuation failure it processed again to recreate the RSets of regions in the collection set. Remove the per-worker _new_refs array by processing the references directly. Use a DirtyCardQueue to hold the cards containing the references so that the RSets of regions in the collection set can be recreated when handling an evacuation failure.
Reviewed-by: iveresov, jmasa, tonyp
1 /*
2 * Copyright (c) 2001, 2009, Oracle and/or its affiliates. All rights reserved.
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 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 #include "incls/_precompiled.incl"
26 #include "incls/_sparsePRT.cpp.incl"
28 #define SPARSE_PRT_VERBOSE 0
30 #define UNROLL_CARD_LOOPS 1
32 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) {
33 sprt_iter->init(this);
34 }
36 void SparsePRTEntry::init(RegionIdx_t region_ind) {
37 _region_ind = region_ind;
38 _next_index = NullEntry;
40 #if UNROLL_CARD_LOOPS
41 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
42 for (int i = 0; i < cards_num(); i += UnrollFactor) {
43 _cards[i] = NullEntry;
44 _cards[i + 1] = NullEntry;
45 _cards[i + 2] = NullEntry;
46 _cards[i + 3] = NullEntry;
47 }
48 #else
49 for (int i = 0; i < cards_num(); i++)
50 _cards[i] = NullEntry;
51 #endif
52 }
54 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
55 #if UNROLL_CARD_LOOPS
56 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
57 for (int i = 0; i < cards_num(); i += UnrollFactor) {
58 if (_cards[i] == card_index ||
59 _cards[i + 1] == card_index ||
60 _cards[i + 2] == card_index ||
61 _cards[i + 3] == card_index) return true;
62 }
63 #else
64 for (int i = 0; i < cards_num(); i++) {
65 if (_cards[i] == card_index) return true;
66 }
67 #endif
68 // Otherwise, we're full.
69 return false;
70 }
72 int SparsePRTEntry::num_valid_cards() const {
73 int sum = 0;
74 #if UNROLL_CARD_LOOPS
75 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
76 for (int i = 0; i < cards_num(); i += UnrollFactor) {
77 sum += (_cards[i] != NullEntry);
78 sum += (_cards[i + 1] != NullEntry);
79 sum += (_cards[i + 2] != NullEntry);
80 sum += (_cards[i + 3] != NullEntry);
81 }
82 #else
83 for (int i = 0; i < cards_num(); i++) {
84 sum += (_cards[i] != NullEntry);
85 }
86 #endif
87 // Otherwise, we're full.
88 return sum;
89 }
91 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
92 #if UNROLL_CARD_LOOPS
93 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
94 CardIdx_t c;
95 for (int i = 0; i < cards_num(); i += UnrollFactor) {
96 c = _cards[i];
97 if (c == card_index) return found;
98 if (c == NullEntry) { _cards[i] = card_index; return added; }
99 c = _cards[i + 1];
100 if (c == card_index) return found;
101 if (c == NullEntry) { _cards[i + 1] = card_index; return added; }
102 c = _cards[i + 2];
103 if (c == card_index) return found;
104 if (c == NullEntry) { _cards[i + 2] = card_index; return added; }
105 c = _cards[i + 3];
106 if (c == card_index) return found;
107 if (c == NullEntry) { _cards[i + 3] = card_index; return added; }
108 }
109 #else
110 for (int i = 0; i < cards_num(); i++) {
111 CardIdx_t c = _cards[i];
112 if (c == card_index) return found;
113 if (c == NullEntry) { _cards[i] = card_index; return added; }
114 }
115 #endif
116 // Otherwise, we're full.
117 return overflow;
118 }
120 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
121 #if UNROLL_CARD_LOOPS
122 assert((cards_num() & (UnrollFactor - 1)) == 0, "Invalid number of cards in the entry");
123 for (int i = 0; i < cards_num(); i += UnrollFactor) {
124 cards[i] = _cards[i];
125 cards[i + 1] = _cards[i + 1];
126 cards[i + 2] = _cards[i + 2];
127 cards[i + 3] = _cards[i + 3];
128 }
129 #else
130 for (int i = 0; i < cards_num(); i++) {
131 cards[i] = _cards[i];
132 }
133 #endif
134 }
136 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
137 copy_cards(&e->_cards[0]);
138 }
140 // ----------------------------------------------------------------------
142 RSHashTable::RSHashTable(size_t capacity) :
143 _capacity(capacity), _capacity_mask(capacity-1),
144 _occupied_entries(0), _occupied_cards(0),
145 _entries((SparsePRTEntry*)NEW_C_HEAP_ARRAY(char, SparsePRTEntry::size() * capacity)),
146 _buckets(NEW_C_HEAP_ARRAY(int, capacity)),
147 _free_list(NullEntry), _free_region(0)
148 {
149 clear();
150 }
152 RSHashTable::~RSHashTable() {
153 if (_entries != NULL) {
154 FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries);
155 _entries = NULL;
156 }
157 if (_buckets != NULL) {
158 FREE_C_HEAP_ARRAY(int, _buckets);
159 _buckets = NULL;
160 }
161 }
163 void RSHashTable::clear() {
164 _occupied_entries = 0;
165 _occupied_cards = 0;
166 guarantee(_entries != NULL, "INV");
167 guarantee(_buckets != NULL, "INV");
169 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
170 "_capacity too large");
172 // This will put -1 == NullEntry in the key field of all entries.
173 memset(_entries, NullEntry, _capacity * SparsePRTEntry::size());
174 memset(_buckets, NullEntry, _capacity * sizeof(int));
175 _free_list = NullEntry;
176 _free_region = 0;
177 }
179 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
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.",
187 pointer_delta(e, _entries, SparsePRTEntry::size()),
188 e->num_valid_cards());
189 #endif
190 assert(e->num_valid_cards() > 0, "Postcondition");
191 return res != SparsePRTEntry::overflow;
192 }
194 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
195 int ind = (int) (region_ind & capacity_mask());
196 int cur_ind = _buckets[ind];
197 SparsePRTEntry* cur;
198 while (cur_ind != NullEntry &&
199 (cur = entry(cur_ind))->r_ind() != region_ind) {
200 cur_ind = cur->next_index();
201 }
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 }
211 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) {
212 int ind = (int) (region_ind & capacity_mask());
213 int cur_ind = _buckets[ind];
214 SparsePRTEntry* cur;
215 while (cur_ind != NullEntry &&
216 (cur = entry(cur_ind))->r_ind() != region_ind) {
217 cur_ind = cur->next_index();
218 }
220 if (cur_ind == NullEntry) return NULL;
221 // Otherwise...
222 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
223 assert(cur->num_valid_cards() > 0, "Inv");
224 return cur;
225 }
227 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
228 int ind = (int) (region_ind & capacity_mask());
229 int* prev_loc = &_buckets[ind];
230 int cur_ind = *prev_loc;
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 }
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 }
247 SparsePRTEntry*
248 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const {
249 assert(occupied_entries() < capacity(), "Precondition");
250 int ind = (int) (region_ind & capacity_mask());
251 int cur_ind = _buckets[ind];
252 SparsePRTEntry* cur;
253 while (cur_ind != NullEntry &&
254 (cur = entry(cur_ind))->r_ind() != region_ind) {
255 cur_ind = cur->next_index();
256 }
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 }
266 SparsePRTEntry*
267 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
268 SparsePRTEntry* res = entry_for_region_ind(region_ind);
269 if (res == NULL) {
270 int new_ind = alloc_entry();
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.
275 int ind = (int) (region_ind & capacity_mask());
276 res->set_next_index(_buckets[ind]);
277 _buckets[ind] = new_ind;
278 _occupied_entries++;
279 }
280 return res;
281 }
283 int RSHashTable::alloc_entry() {
284 int res;
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 }
298 void RSHashTable::free_entry(int fi) {
299 entry(fi)->set_next_index(_free_list);
300 _free_list = fi;
301 }
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 }
311 CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() {
312 CardIdx_t res;
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 }
325 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) {
326 return
327 _heap_bot_card_ind
328 + (_rsht->entry(_bl_ind)->r_ind() * HeapRegion::CardsPerRegion)
329 + ci;
330 }
332 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) {
333 _card_ind++;
334 CardIdx_t ci;
335 if (_card_ind < SparsePRTEntry::cards_num() &&
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;
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 }
368 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
369 SparsePRTEntry* e = entry_for_region_ind(region_index);
370 return (e != NULL && e->contains_card(card_index));
371 }
373 size_t RSHashTable::mem_size() const {
374 return sizeof(this) +
375 capacity() * (SparsePRTEntry::size() + sizeof(int));
376 }
378 // ----------------------------------------------------------------------
380 SparsePRT* SparsePRT::_head_expanded_list = NULL;
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 }
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 }
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 }
426 SparsePRT::SparsePRT(HeapRegion* hr) :
427 _expanded(false), _next_expanded(NULL)
428 {
429 _cur = new RSHashTable(InitialCapacity);
430 _next = _cur;
431 }
434 SparsePRT::~SparsePRT() {
435 assert(_next != NULL && _cur != NULL, "Inv");
436 if (_cur != _next) { delete _cur; }
437 delete _next;
438 }
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 }
447 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
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 }
458 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
459 return _next->get_cards(region_id, cards);
460 }
462 SparsePRTEntry* SparsePRT::get_entry(RegionIdx_t region_id) {
463 return _next->get_entry(region_id);
464 }
466 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
467 return _next->delete_entry(region_id);
468 }
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 }
477 if (_cur->capacity() != InitialCapacity) {
478 delete _cur;
479 _cur = new RSHashTable(InitialCapacity);
480 } else {
481 _cur->clear();
482 }
483 _next = _cur;
484 }
486 void SparsePRT::cleanup() {
487 // Make sure that the current and next tables agree.
488 if (_cur != _next) {
489 delete _cur;
490 }
491 _cur = _next;
492 set_expanded(false);
493 }
495 void SparsePRT::expand() {
496 RSHashTable* last = _next;
497 _next = new RSHashTable(last->capacity() * 2);
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 }
513 if (last != _cur) {
514 delete last;
515 }
516 add_to_expanded_list(this);
517 }