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