Thu, 11 Jun 2009 17:19:33 -0700
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
Summary: For heaps larger than 32Gb, the number of heap regions overflows the data type used to hold the region index in the SparsePRT structure. Changed the region indexes, card indexes, and RSet hash table buckets to ints and added some size overflow guarantees.
Reviewed-by: ysr, tonyp
1 /*
2 * Copyright 2001-2007 Sun Microsystems, Inc. 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
20 * CA 95054 USA or visit www.sun.com if you need additional information or
21 * have any 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;
39 #if UNROLL_CARD_LOOPS
40 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
41 _cards[0] = NullEntry;
42 _cards[1] = NullEntry;
43 _cards[2] = NullEntry;
44 _cards[3] = NullEntry;
45 #else
46 for (int i = 0; i < CardsPerEntry; i++)
47 _cards[i] = NullEntry;
48 #endif
49 }
51 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
52 #if UNROLL_CARD_LOOPS
53 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
54 if (_cards[0] == card_index) return true;
55 if (_cards[1] == card_index) return true;
56 if (_cards[2] == card_index) return true;
57 if (_cards[3] == card_index) return true;
58 #else
59 for (int i = 0; i < CardsPerEntry; i++) {
60 if (_cards[i] == card_index) return true;
61 }
62 #endif
63 // Otherwise, we're full.
64 return false;
65 }
67 int SparsePRTEntry::num_valid_cards() const {
68 int sum = 0;
69 #if UNROLL_CARD_LOOPS
70 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
71 if (_cards[0] != NullEntry) sum++;
72 if (_cards[1] != NullEntry) sum++;
73 if (_cards[2] != NullEntry) sum++;
74 if (_cards[3] != NullEntry) sum++;
75 #else
76 for (int i = 0; i < CardsPerEntry; i++) {
77 if (_cards[i] != NulLEntry) sum++;
78 }
79 #endif
80 // Otherwise, we're full.
81 return sum;
82 }
84 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
85 #if UNROLL_CARD_LOOPS
86 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
87 CardIdx_t c = _cards[0];
88 if (c == card_index) return found;
89 if (c == NullEntry) { _cards[0] = card_index; return added; }
90 c = _cards[1];
91 if (c == card_index) return found;
92 if (c == NullEntry) { _cards[1] = card_index; return added; }
93 c = _cards[2];
94 if (c == card_index) return found;
95 if (c == NullEntry) { _cards[2] = card_index; return added; }
96 c = _cards[3];
97 if (c == card_index) return found;
98 if (c == NullEntry) { _cards[3] = card_index; return added; }
99 #else
100 for (int i = 0; i < CardsPerEntry; i++) {
101 CardIdx_t c = _cards[i];
102 if (c == card_index) return found;
103 if (c == NullEntry) {
104 _cards[i] = card_index;
105 return added;
106 }
107 }
108 #endif
109 // Otherwise, we're full.
110 return overflow;
111 }
113 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
114 #if UNROLL_CARD_LOOPS
115 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
116 cards[0] = _cards[0];
117 cards[1] = _cards[1];
118 cards[2] = _cards[2];
119 cards[3] = _cards[3];
120 #else
121 for (int i = 0; i < CardsPerEntry; i++) {
122 cards[i] = _cards[i];
123 }
124 #endif
125 }
127 void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const {
128 copy_cards(&e->_cards[0]);
129 }
131 // ----------------------------------------------------------------------
133 RSHashTable::RSHashTable(size_t capacity) :
134 _capacity(capacity), _capacity_mask(capacity-1),
135 _occupied_entries(0), _occupied_cards(0),
136 _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)),
137 _buckets(NEW_C_HEAP_ARRAY(int, capacity)),
138 _next_deleted(NULL), _deleted(false),
139 _free_list(NullEntry), _free_region(0)
140 {
141 clear();
142 }
144 RSHashTable::~RSHashTable() {
145 if (_entries != NULL) {
146 FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries);
147 _entries = NULL;
148 }
149 if (_buckets != NULL) {
150 FREE_C_HEAP_ARRAY(int, _buckets);
151 _buckets = NULL;
152 }
153 }
155 void RSHashTable::clear() {
156 _occupied_entries = 0;
157 _occupied_cards = 0;
158 guarantee(_entries != NULL, "INV");
159 guarantee(_buckets != NULL, "INV");
161 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
162 "_capacity too large");
164 // This will put -1 == NullEntry in the key field of all entries.
165 memset(_entries, -1, _capacity * sizeof(SparsePRTEntry));
166 memset(_buckets, -1, _capacity * sizeof(int));
167 _free_list = NullEntry;
168 _free_region = 0;
169 }
171 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
172 SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
173 assert(e != NULL && e->r_ind() == region_ind,
174 "Postcondition of call above.");
175 SparsePRTEntry::AddCardResult res = e->add_card(card_index);
176 if (res == SparsePRTEntry::added) _occupied_cards++;
177 #if SPARSE_PRT_VERBOSE
178 gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.",
179 pointer_delta(e, _entries, sizeof(SparsePRTEntry)),
180 e->num_valid_cards());
181 #endif
182 assert(e->num_valid_cards() > 0, "Postcondition");
183 return res != SparsePRTEntry::overflow;
184 }
186 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
187 int ind = (int) (region_ind & capacity_mask());
188 int cur_ind = _buckets[ind];
189 SparsePRTEntry* cur;
190 while (cur_ind != NullEntry &&
191 (cur = entry(cur_ind))->r_ind() != region_ind) {
192 cur_ind = cur->next_index();
193 }
195 if (cur_ind == NullEntry) return false;
196 // Otherwise...
197 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
198 assert(cur->num_valid_cards() > 0, "Inv");
199 cur->copy_cards(cards);
200 return true;
201 }
203 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
204 int ind = (int) (region_ind & capacity_mask());
205 int* prev_loc = &_buckets[ind];
206 int cur_ind = *prev_loc;
207 SparsePRTEntry* cur;
208 while (cur_ind != NullEntry &&
209 (cur = entry(cur_ind))->r_ind() != region_ind) {
210 prev_loc = cur->next_index_addr();
211 cur_ind = *prev_loc;
212 }
214 if (cur_ind == NullEntry) return false;
215 // Otherwise, splice out "cur".
216 *prev_loc = cur->next_index();
217 _occupied_cards -= cur->num_valid_cards();
218 free_entry(cur_ind);
219 _occupied_entries--;
220 return true;
221 }
223 SparsePRTEntry*
224 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const {
225 assert(occupied_entries() < capacity(), "Precondition");
226 int ind = (int) (region_ind & capacity_mask());
227 int cur_ind = _buckets[ind];
228 SparsePRTEntry* cur;
229 // XXX
230 // int k = 0;
231 while (cur_ind != NullEntry &&
232 (cur = entry(cur_ind))->r_ind() != region_ind) {
233 /*
234 k++;
235 if (k > 10) {
236 gclog_or_tty->print_cr("RSHashTable::entry_for_region_ind(%d): "
237 "k = %d, cur_ind = %d.", region_ind, k, cur_ind);
238 if (k >= 1000) {
239 while (1) ;
240 }
241 }
242 */
243 cur_ind = cur->next_index();
244 }
246 if (cur_ind != NullEntry) {
247 assert(cur->r_ind() == region_ind, "Loop postcondition + test");
248 return cur;
249 } else {
250 return NULL;
251 }
252 }
254 SparsePRTEntry*
255 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
256 SparsePRTEntry* res = entry_for_region_ind(region_ind);
257 if (res == NULL) {
258 int new_ind = alloc_entry();
259 assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
260 res = entry(new_ind);
261 res->init(region_ind);
262 // Insert at front.
263 int ind = (int) (region_ind & capacity_mask());
264 res->set_next_index(_buckets[ind]);
265 _buckets[ind] = new_ind;
266 _occupied_entries++;
267 }
268 return res;
269 }
271 int RSHashTable::alloc_entry() {
272 int res;
273 if (_free_list != NullEntry) {
274 res = _free_list;
275 _free_list = entry(res)->next_index();
276 return res;
277 } else if ((size_t) _free_region+1 < capacity()) {
278 res = _free_region;
279 _free_region++;
280 return res;
281 } else {
282 return NullEntry;
283 }
284 }
286 void RSHashTable::free_entry(int fi) {
287 entry(fi)->set_next_index(_free_list);
288 _free_list = fi;
289 }
291 void RSHashTable::add_entry(SparsePRTEntry* e) {
292 assert(e->num_valid_cards() > 0, "Precondition.");
293 SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind());
294 e->copy_cards(e2);
295 _occupied_cards += e2->num_valid_cards();
296 assert(e2->num_valid_cards() > 0, "Postcondition.");
297 }
299 RSHashTable* RSHashTable::_head_deleted_list = NULL;
301 void RSHashTable::add_to_deleted_list(RSHashTable* rsht) {
302 assert(!rsht->deleted(), "Should delete only once.");
303 rsht->set_deleted(true);
304 RSHashTable* hd = _head_deleted_list;
305 while (true) {
306 rsht->_next_deleted = hd;
307 RSHashTable* res =
308 (RSHashTable*)
309 Atomic::cmpxchg_ptr(rsht, &_head_deleted_list, hd);
310 if (res == hd) return;
311 else hd = res;
312 }
313 }
315 RSHashTable* RSHashTable::get_from_deleted_list() {
316 RSHashTable* hd = _head_deleted_list;
317 while (hd != NULL) {
318 RSHashTable* next = hd->next_deleted();
319 RSHashTable* res =
320 (RSHashTable*)
321 Atomic::cmpxchg_ptr(next, &_head_deleted_list, hd);
322 if (res == hd) {
323 hd->set_next_deleted(NULL);
324 hd->set_deleted(false);
325 return hd;
326 } else {
327 hd = res;
328 }
329 }
330 return NULL;
331 }
333 CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() {
334 CardIdx_t res;
335 while (_bl_ind != RSHashTable::NullEntry) {
336 res = _rsht->entry(_bl_ind)->card(0);
337 if (res != SparsePRTEntry::NullEntry) {
338 return res;
339 } else {
340 _bl_ind = _rsht->entry(_bl_ind)->next_index();
341 }
342 }
343 // Otherwise, none found:
344 return SparsePRTEntry::NullEntry;
345 }
347 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) {
348 return
349 _heap_bot_card_ind
350 + (_rsht->entry(_bl_ind)->r_ind() * CardsPerRegion)
351 + ci;
352 }
354 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) {
355 _card_ind++;
356 CardIdx_t ci;
357 if (_card_ind < SparsePRTEntry::CardsPerEntry &&
358 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
359 SparsePRTEntry::NullEntry)) {
360 card_index = compute_card_ind(ci);
361 return true;
362 }
363 // Otherwise, must find the next valid entry.
364 _card_ind = 0;
366 if (_bl_ind != RSHashTable::NullEntry) {
367 _bl_ind = _rsht->entry(_bl_ind)->next_index();
368 ci = find_first_card_in_list();
369 if (ci != SparsePRTEntry::NullEntry) {
370 card_index = compute_card_ind(ci);
371 return true;
372 }
373 }
374 // If we didn't return above, must go to the next non-null table index.
375 _tbl_ind++;
376 while ((size_t)_tbl_ind < _rsht->capacity()) {
377 _bl_ind = _rsht->_buckets[_tbl_ind];
378 ci = find_first_card_in_list();
379 if (ci != SparsePRTEntry::NullEntry) {
380 card_index = compute_card_ind(ci);
381 return true;
382 }
383 // Otherwise, try next entry.
384 _tbl_ind++;
385 }
386 // Otherwise, there were no entry.
387 return false;
388 }
390 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
391 SparsePRTEntry* e = entry_for_region_ind(region_index);
392 return (e != NULL && e->contains_card(card_index));
393 }
395 size_t RSHashTable::mem_size() const {
396 return sizeof(this) +
397 capacity() * (sizeof(SparsePRTEntry) + sizeof(int));
398 }
400 // ----------------------------------------------------------------------
402 SparsePRT* SparsePRT::_head_expanded_list = NULL;
404 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
405 // We could expand multiple times in a pause -- only put on list once.
406 if (sprt->expanded()) return;
407 sprt->set_expanded(true);
408 SparsePRT* hd = _head_expanded_list;
409 while (true) {
410 sprt->_next_expanded = hd;
411 SparsePRT* res =
412 (SparsePRT*)
413 Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd);
414 if (res == hd) return;
415 else hd = res;
416 }
417 }
420 SparsePRT* SparsePRT::get_from_expanded_list() {
421 SparsePRT* hd = _head_expanded_list;
422 while (hd != NULL) {
423 SparsePRT* next = hd->next_expanded();
424 SparsePRT* res =
425 (SparsePRT*)
426 Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd);
427 if (res == hd) {
428 hd->set_next_expanded(NULL);
429 return hd;
430 } else {
431 hd = res;
432 }
433 }
434 return NULL;
435 }
438 void SparsePRT::cleanup_all() {
439 // First clean up all expanded tables so they agree on next and cur.
440 SparsePRT* sprt = get_from_expanded_list();
441 while (sprt != NULL) {
442 sprt->cleanup();
443 sprt = get_from_expanded_list();
444 }
445 // Now delete all deleted RSHashTables.
446 RSHashTable* rsht = RSHashTable::get_from_deleted_list();
447 while (rsht != NULL) {
448 #if SPARSE_PRT_VERBOSE
449 gclog_or_tty->print_cr("About to delete RSHT " PTR_FORMAT ".", rsht);
450 #endif
451 delete rsht;
452 rsht = RSHashTable::get_from_deleted_list();
453 }
454 }
457 SparsePRT::SparsePRT(HeapRegion* hr) :
458 _expanded(false), _next_expanded(NULL)
459 {
460 _cur = new RSHashTable(InitialCapacity);
461 _next = _cur;
462 }
465 SparsePRT::~SparsePRT() {
466 assert(_next != NULL && _cur != NULL, "Inv");
467 if (_cur != _next) { delete _cur; }
468 delete _next;
469 }
472 size_t SparsePRT::mem_size() const {
473 // We ignore "_cur" here, because it either = _next, or else it is
474 // on the deleted list.
475 return sizeof(this) + _next->mem_size();
476 }
478 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
479 #if SPARSE_PRT_VERBOSE
480 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.",
481 card_index, region_id, _hr->hrs_index());
482 #endif
483 if (_next->occupied_entries() * 2 > _next->capacity()) {
484 expand();
485 }
486 return _next->add_card(region_id, card_index);
487 }
489 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
490 return _next->get_cards(region_id, cards);
491 }
493 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
494 return _next->delete_entry(region_id);
495 }
497 void SparsePRT::clear() {
498 // If they differ, _next is bigger then cur, so next has no chance of
499 // being the initial size.
500 if (_next != _cur) {
501 delete _next;
502 }
504 if (_cur->capacity() != InitialCapacity) {
505 delete _cur;
506 _cur = new RSHashTable(InitialCapacity);
507 } else {
508 _cur->clear();
509 }
510 _next = _cur;
511 }
513 void SparsePRT::cleanup() {
514 // Make sure that the current and next tables agree. (Another mechanism
515 // takes care of deleting now-unused tables.)
516 _cur = _next;
517 set_expanded(false);
518 }
520 void SparsePRT::expand() {
521 RSHashTable* last = _next;
522 _next = new RSHashTable(last->capacity() * 2);
524 #if SPARSE_PRT_VERBOSE
525 gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.",
526 _hr->hrs_index(), _next->capacity());
527 #endif
528 for (size_t i = 0; i < last->capacity(); i++) {
529 SparsePRTEntry* e = last->entry((int)i);
530 if (e->valid_entry()) {
531 #if SPARSE_PRT_VERBOSE
532 gclog_or_tty->print_cr(" During expansion, transferred entry for %d.",
533 e->r_ind());
534 #endif
535 _next->add_entry(e);
536 }
537 }
538 if (last != _cur)
539 RSHashTable::add_to_deleted_list(last);
540 add_to_expanded_list(this);
541 }