Mercurial > hg > truffle

comparison src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 807:d44bdab1c03d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
author johnc
date Thu, 11 Jun 2009 17:19:33 -0700
parents 0db4adb6e914
children bd02caa94611
comparison
equal deleted inserted replaced
806:821269eca479 807:d44bdab1c03d
31 31
32 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { 32 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) {
33 sprt_iter->init(this); 33 sprt_iter->init(this);
34 } 34 }
35 35
36 void SparsePRTEntry::init(short region_ind) { 36 void SparsePRTEntry::init(RegionIdx_t region_ind) {
37 _region_ind = region_ind; 37 _region_ind = region_ind;
38 _next_index = NullEntry; 38 _next_index = NullEntry;
39 #if UNROLL_CARD_LOOPS 39 #if UNROLL_CARD_LOOPS
40 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); 40 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
41 _cards[0] = NullEntry; 41 _cards[0] = NullEntry;
42 _cards[1] = NullEntry; 42 _cards[1] = NullEntry;
43 _cards[2] = NullEntry; 43 _cards[2] = NullEntry;
44 _cards[3] = NullEntry; 44 _cards[3] = NullEntry;
45 #else 45 #else
46 for (int i = 0; i < CardsPerEntry; i++) _cards[i] = NullEntry; 46 for (int i = 0; i < CardsPerEntry; i++)
47 #endif 47 _cards[i] = NullEntry;
48 } 48 #endif
49 49 }
50 bool SparsePRTEntry::contains_card(short card_index) const { 50
51 bool SparsePRTEntry::contains_card(CardIdx_t card_index) const {
51 #if UNROLL_CARD_LOOPS 52 #if UNROLL_CARD_LOOPS
52 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); 53 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
53 if (_cards[0] == card_index) return true; 54 if (_cards[0] == card_index) return true;
54 if (_cards[1] == card_index) return true; 55 if (_cards[1] == card_index) return true;
55 if (_cards[2] == card_index) return true; 56 if (_cards[2] == card_index) return true;
78 #endif 79 #endif
79 // Otherwise, we're full. 80 // Otherwise, we're full.
80 return sum; 81 return sum;
81 } 82 }
82 83
83 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(short card_index) { 84 SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(CardIdx_t card_index) {
84 #if UNROLL_CARD_LOOPS 85 #if UNROLL_CARD_LOOPS
85 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); 86 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
86 short c = _cards[0]; 87 CardIdx_t c = _cards[0];
87 if (c == card_index) return found; 88 if (c == card_index) return found;
88 if (c == NullEntry) { _cards[0] = card_index; return added; } 89 if (c == NullEntry) { _cards[0] = card_index; return added; }
89 c = _cards[1]; 90 c = _cards[1];
90 if (c == card_index) return found; 91 if (c == card_index) return found;
91 if (c == NullEntry) { _cards[1] = card_index; return added; } 92 if (c == NullEntry) { _cards[1] = card_index; return added; }
95 c = _cards[3]; 96 c = _cards[3];
96 if (c == card_index) return found; 97 if (c == card_index) return found;
97 if (c == NullEntry) { _cards[3] = card_index; return added; } 98 if (c == NullEntry) { _cards[3] = card_index; return added; }
98 #else 99 #else
99 for (int i = 0; i < CardsPerEntry; i++) { 100 for (int i = 0; i < CardsPerEntry; i++) {
100 short c = _cards[i]; 101 CardIdx_t c = _cards[i];
101 if (c == card_index) return found; 102 if (c == card_index) return found;
102 if (c == NullEntry) { _cards[i] = card_index; return added; } 103 if (c == NullEntry) {
104 _cards[i] = card_index;
105 return added;
106 }
103 } 107 }
104 #endif 108 #endif
105 // Otherwise, we're full. 109 // Otherwise, we're full.
106 return overflow; 110 return overflow;
107 } 111 }
108 112
109 void SparsePRTEntry::copy_cards(short* cards) const { 113 void SparsePRTEntry::copy_cards(CardIdx_t* cards) const {
110 #if UNROLL_CARD_LOOPS 114 #if UNROLL_CARD_LOOPS
111 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); 115 assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll.");
112 cards[0] = _cards[0]; 116 cards[0] = _cards[0];
113 cards[1] = _cards[1]; 117 cards[1] = _cards[1];
114 cards[2] = _cards[2]; 118 cards[2] = _cards[2];
128 132
129 RSHashTable::RSHashTable(size_t capacity) : 133 RSHashTable::RSHashTable(size_t capacity) :
130 _capacity(capacity), _capacity_mask(capacity-1), 134 _capacity(capacity), _capacity_mask(capacity-1),
131 _occupied_entries(0), _occupied_cards(0), 135 _occupied_entries(0), _occupied_cards(0),
132 _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)), 136 _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)),
133 _buckets(NEW_C_HEAP_ARRAY(short, capacity)), 137 _buckets(NEW_C_HEAP_ARRAY(int, capacity)),
134 _next_deleted(NULL), _deleted(false), 138 _next_deleted(NULL), _deleted(false),
135 _free_list(NullEntry), _free_region(0) 139 _free_list(NullEntry), _free_region(0)
136 { 140 {
137 clear(); 141 clear();
138 } 142 }
141 if (_entries != NULL) { 145 if (_entries != NULL) {
142 FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries); 146 FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries);
143 _entries = NULL; 147 _entries = NULL;
144 } 148 }
145 if (_buckets != NULL) { 149 if (_buckets != NULL) {
146 FREE_C_HEAP_ARRAY(short, _buckets); 150 FREE_C_HEAP_ARRAY(int, _buckets);
147 _buckets = NULL; 151 _buckets = NULL;
148 } 152 }
149 } 153 }
150 154
151 void RSHashTable::clear() { 155 void RSHashTable::clear() {
152 _occupied_entries = 0; 156 _occupied_entries = 0;
153 _occupied_cards = 0; 157 _occupied_cards = 0;
154 guarantee(_entries != NULL, "INV"); 158 guarantee(_entries != NULL, "INV");
155 guarantee(_buckets != NULL, "INV"); 159 guarantee(_buckets != NULL, "INV");
160
161 guarantee(_capacity <= ((size_t)1 << (sizeof(int)*BitsPerByte-1)) - 1,
162 "_capacity too large");
163
156 // This will put -1 == NullEntry in the key field of all entries. 164 // This will put -1 == NullEntry in the key field of all entries.
157 memset(_entries, -1, _capacity * sizeof(SparsePRTEntry)); 165 memset(_entries, -1, _capacity * sizeof(SparsePRTEntry));
158 memset(_buckets, -1, _capacity * sizeof(short)); 166 memset(_buckets, -1, _capacity * sizeof(int));
159 _free_list = NullEntry; 167 _free_list = NullEntry;
160 _free_region = 0; 168 _free_region = 0;
161 } 169 }
162 170
163 bool RSHashTable::add_card(short region_ind, short card_index) { 171 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
164 SparsePRTEntry* e = entry_for_region_ind_create(region_ind); 172 SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
165 assert(e != NULL && e->r_ind() == region_ind, 173 assert(e != NULL && e->r_ind() == region_ind,
166 "Postcondition of call above."); 174 "Postcondition of call above.");
167 SparsePRTEntry::AddCardResult res = e->add_card(card_index); 175 SparsePRTEntry::AddCardResult res = e->add_card(card_index);
168 if (res == SparsePRTEntry::added) _occupied_cards++; 176 if (res == SparsePRTEntry::added) _occupied_cards++;
173 #endif 181 #endif
174 assert(e->num_valid_cards() > 0, "Postcondition"); 182 assert(e->num_valid_cards() > 0, "Postcondition");
175 return res != SparsePRTEntry::overflow; 183 return res != SparsePRTEntry::overflow;
176 } 184 }
177 185
178 bool RSHashTable::get_cards(short region_ind, short* cards) { 186 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
179 short ind = (short) (region_ind & capacity_mask()); 187 int ind = (int) (region_ind & capacity_mask());
180 short cur_ind = _buckets[ind]; 188 int cur_ind = _buckets[ind];
181 SparsePRTEntry* cur; 189 SparsePRTEntry* cur;
182 while (cur_ind != NullEntry && 190 while (cur_ind != NullEntry &&
183 (cur = entry(cur_ind))->r_ind() != region_ind) { 191 (cur = entry(cur_ind))->r_ind() != region_ind) {
184 cur_ind = cur->next_index(); 192 cur_ind = cur->next_index();
185 } 193 }
190 assert(cur->num_valid_cards() > 0, "Inv"); 198 assert(cur->num_valid_cards() > 0, "Inv");
191 cur->copy_cards(cards); 199 cur->copy_cards(cards);
192 return true; 200 return true;
193 } 201 }
194 202
195 bool RSHashTable::delete_entry(short region_ind) { 203 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
196 short ind = (short) (region_ind & capacity_mask()); 204 int ind = (int) (region_ind & capacity_mask());
197 short* prev_loc = &_buckets[ind]; 205 int* prev_loc = &_buckets[ind];
198 short cur_ind = *prev_loc; 206 int cur_ind = *prev_loc;
199 SparsePRTEntry* cur; 207 SparsePRTEntry* cur;
200 while (cur_ind != NullEntry && 208 while (cur_ind != NullEntry &&
201 (cur = entry(cur_ind))->r_ind() != region_ind) { 209 (cur = entry(cur_ind))->r_ind() != region_ind) {
202 prev_loc = cur->next_index_addr(); 210 prev_loc = cur->next_index_addr();
203 cur_ind = *prev_loc; 211 cur_ind = *prev_loc;
210 free_entry(cur_ind); 218 free_entry(cur_ind);
211 _occupied_entries--; 219 _occupied_entries--;
212 return true; 220 return true;
213 } 221 }
214 222
215 SparsePRTEntry* RSHashTable::entry_for_region_ind(short region_ind) const { 223 SparsePRTEntry*
224 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const {
216 assert(occupied_entries() < capacity(), "Precondition"); 225 assert(occupied_entries() < capacity(), "Precondition");
217 short ind = (short) (region_ind & capacity_mask()); 226 int ind = (int) (region_ind & capacity_mask());
218 short cur_ind = _buckets[ind]; 227 int cur_ind = _buckets[ind];
219 SparsePRTEntry* cur; 228 SparsePRTEntry* cur;
220 // XXX 229 // XXX
221 // int k = 0; 230 // int k = 0;
222 while (cur_ind != NullEntry && 231 while (cur_ind != NullEntry &&
223 (cur = entry(cur_ind))->r_ind() != region_ind) { 232 (cur = entry(cur_ind))->r_ind() != region_ind) {
240 } else { 249 } else {
241 return NULL; 250 return NULL;
242 } 251 }
243 } 252 }
244 253
245 SparsePRTEntry* RSHashTable::entry_for_region_ind_create(short region_ind) { 254 SparsePRTEntry*
255 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
246 SparsePRTEntry* res = entry_for_region_ind(region_ind); 256 SparsePRTEntry* res = entry_for_region_ind(region_ind);
247 if (res == NULL) { 257 if (res == NULL) {
248 short new_ind = alloc_entry(); 258 int new_ind = alloc_entry();
249 assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room."); 259 assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
250 res = entry(new_ind); 260 res = entry(new_ind);
251 res->init(region_ind); 261 res->init(region_ind);
252 // Insert at front. 262 // Insert at front.
253 short ind = (short) (region_ind & capacity_mask()); 263 int ind = (int) (region_ind & capacity_mask());
254 res->set_next_index(_buckets[ind]); 264 res->set_next_index(_buckets[ind]);
255 _buckets[ind] = new_ind; 265 _buckets[ind] = new_ind;
256 _occupied_entries++; 266 _occupied_entries++;
257 } 267 }
258 return res; 268 return res;
259 } 269 }
260 270
261 short RSHashTable::alloc_entry() { 271 int RSHashTable::alloc_entry() {
262 short res; 272 int res;
263 if (_free_list != NullEntry) { 273 if (_free_list != NullEntry) {
264 res = _free_list; 274 res = _free_list;
265 _free_list = entry(res)->next_index(); 275 _free_list = entry(res)->next_index();
266 return res; 276 return res;
267 } else if ((size_t) _free_region+1 < capacity()) { 277 } else if ((size_t) _free_region+1 < capacity()) {
271 } else { 281 } else {
272 return NullEntry; 282 return NullEntry;
273 } 283 }
274 } 284 }
275 285
276 286 void RSHashTable::free_entry(int fi) {
277 void RSHashTable::free_entry(short fi) {
278 entry(fi)->set_next_index(_free_list); 287 entry(fi)->set_next_index(_free_list);
279 _free_list = fi; 288 _free_list = fi;
280 } 289 }
281
282 290
283 void RSHashTable::add_entry(SparsePRTEntry* e) { 291 void RSHashTable::add_entry(SparsePRTEntry* e) {
284 assert(e->num_valid_cards() > 0, "Precondition."); 292 assert(e->num_valid_cards() > 0, "Precondition.");
285 SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind()); 293 SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind());
286 e->copy_cards(e2); 294 e->copy_cards(e2);
320 } 328 }
321 } 329 }
322 return NULL; 330 return NULL;
323 } 331 }
324 332
325 short /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() { 333 CardIdx_t /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() {
326 short res; 334 CardIdx_t res;
327 while (_bl_ind != RSHashTable::NullEntry) { 335 while (_bl_ind != RSHashTable::NullEntry) {
328 res = _rsht->entry(_bl_ind)->card(0); 336 res = _rsht->entry(_bl_ind)->card(0);
329 if (res != SparsePRTEntry::NullEntry) { 337 if (res != SparsePRTEntry::NullEntry) {
330 return res; 338 return res;
331 } else { 339 } else {
334 } 342 }
335 // Otherwise, none found: 343 // Otherwise, none found:
336 return SparsePRTEntry::NullEntry; 344 return SparsePRTEntry::NullEntry;
337 } 345 }
338 346
339 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(short ci) { 347 size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(CardIdx_t ci) {
340 return 348 return
341 _heap_bot_card_ind 349 _heap_bot_card_ind
342 + (_rsht->entry(_bl_ind)->r_ind() * CardsPerRegion) 350 + (_rsht->entry(_bl_ind)->r_ind() * CardsPerRegion)
343 + ci; 351 + ci;
344 } 352 }
345 353
346 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { 354 bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) {
347 _card_ind++; 355 _card_ind++;
348 short ci; 356 CardIdx_t ci;
349 if (_card_ind < SparsePRTEntry::CardsPerEntry && 357 if (_card_ind < SparsePRTEntry::CardsPerEntry &&
350 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != 358 ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) !=
351 SparsePRTEntry::NullEntry)) { 359 SparsePRTEntry::NullEntry)) {
352 card_index = compute_card_ind(ci); 360 card_index = compute_card_ind(ci);
353 return true; 361 return true;
377 } 385 }
378 // Otherwise, there were no entry. 386 // Otherwise, there were no entry.
379 return false; 387 return false;
380 } 388 }
381 389
382 bool RSHashTable::contains_card(short region_index, short card_index) const { 390 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
383 SparsePRTEntry* e = entry_for_region_ind(region_index); 391 SparsePRTEntry* e = entry_for_region_ind(region_index);
384 return (e != NULL && e->contains_card(card_index)); 392 return (e != NULL && e->contains_card(card_index));
385 } 393 }
386 394
387 size_t RSHashTable::mem_size() const { 395 size_t RSHashTable::mem_size() const {
388 return sizeof(this) + capacity() * (sizeof(SparsePRTEntry) + sizeof(short)); 396 return sizeof(this) +
389 } 397 capacity() * (sizeof(SparsePRTEntry) + sizeof(int));
390 398 }
391 399
392 // ---------------------------------------------------------------------- 400 // ----------------------------------------------------------------------
393 401
394 SparsePRT* SparsePRT::_head_expanded_list = NULL; 402 SparsePRT* SparsePRT::_head_expanded_list = NULL;
395 403
406 if (res == hd) return; 414 if (res == hd) return;
407 else hd = res; 415 else hd = res;
408 } 416 }
409 } 417 }
410 418
419
411 SparsePRT* SparsePRT::get_from_expanded_list() { 420 SparsePRT* SparsePRT::get_from_expanded_list() {
412 SparsePRT* hd = _head_expanded_list; 421 SparsePRT* hd = _head_expanded_list;
413 while (hd != NULL) { 422 while (hd != NULL) {
414 SparsePRT* next = hd->next_expanded(); 423 SparsePRT* next = hd->next_expanded();
415 SparsePRT* res = 424 SparsePRT* res =
450 { 459 {
451 _cur = new RSHashTable(InitialCapacity); 460 _cur = new RSHashTable(InitialCapacity);
452 _next = _cur; 461 _next = _cur;
453 } 462 }
454 463
464
455 SparsePRT::~SparsePRT() { 465 SparsePRT::~SparsePRT() {
456 assert(_next != NULL && _cur != NULL, "Inv"); 466 assert(_next != NULL && _cur != NULL, "Inv");
457 if (_cur != _next) { delete _cur; } 467 if (_cur != _next) { delete _cur; }
458 delete _next; 468 delete _next;
459 } 469 }
463 // We ignore "_cur" here, because it either = _next, or else it is 473 // We ignore "_cur" here, because it either = _next, or else it is
464 // on the deleted list. 474 // on the deleted list.
465 return sizeof(this) + _next->mem_size(); 475 return sizeof(this) + _next->mem_size();
466 } 476 }
467 477
468 bool SparsePRT::add_card(short region_id, short card_index) { 478 bool SparsePRT::add_card(RegionIdx_t region_id, CardIdx_t card_index) {
469 #if SPARSE_PRT_VERBOSE 479 #if SPARSE_PRT_VERBOSE
470 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", 480 gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.",
471 card_index, region_id, _hr->hrs_index()); 481 card_index, region_id, _hr->hrs_index());
472 #endif 482 #endif
473 if (_next->occupied_entries() * 2 > _next->capacity()) { 483 if (_next->occupied_entries() * 2 > _next->capacity()) {
474 expand(); 484 expand();
475 } 485 }
476 return _next->add_card(region_id, card_index); 486 return _next->add_card(region_id, card_index);
477 } 487 }
478 488
479 bool SparsePRT::get_cards(short region_id, short* cards) { 489 bool SparsePRT::get_cards(RegionIdx_t region_id, CardIdx_t* cards) {
480 return _next->get_cards(region_id, cards); 490 return _next->get_cards(region_id, cards);
481 } 491 }
482 492
483 bool SparsePRT::delete_entry(short region_id) { 493 bool SparsePRT::delete_entry(RegionIdx_t region_id) {
484 return _next->delete_entry(region_id); 494 return _next->delete_entry(region_id);
485 } 495 }
486 496
487 void SparsePRT::clear() { 497 void SparsePRT::clear() {
488 // If they differ, _next is bigger then cur, so next has no chance of 498 // If they differ, _next is bigger then cur, so next has no chance of