Mercurial > hg > truffle
view src/share/vm/gc_implementation/g1/sparsePRT.cpp @ 453:c96030fff130
6684579: SoftReference processing can be made more efficient
Summary: For current soft-ref clearing policies, we can decide at marking time if a soft-reference will definitely not be cleared, postponing the decision of whether it will definitely be cleared to the final reference processing phase. This can be especially beneficial in the case of concurrent collectors where the marking is usually concurrent but reference processing is usually not.
Reviewed-by: jmasa
author | ysr |
---|---|
date | Thu, 20 Nov 2008 16:56:09 -0800 |
parents | 37f87013dfd8 |
children | 0db4adb6e914 |
line wrap: on
line source
/* * Copyright 2001-2007 Sun Microsystems, Inc. All Rights Reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, * CA 95054 USA or visit www.sun.com if you need additional information or * have any questions. * */ #include "incls/_precompiled.incl" #include "incls/_sparsePRT.cpp.incl" #define SPARSE_PRT_VERBOSE 0 #define UNROLL_CARD_LOOPS 1 void SparsePRT::init_iterator(SparsePRTIter* sprt_iter) { sprt_iter->init(this); } void SparsePRTEntry::init(short region_ind) { _region_ind = region_ind; _next_index = NullEntry; #if UNROLL_CARD_LOOPS assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); _cards[0] = NullEntry; _cards[1] = NullEntry; _cards[2] = NullEntry; _cards[3] = NullEntry; #else for (int i = 0; i < CardsPerEntry; i++) _cards[i] = NullEntry; #endif } bool SparsePRTEntry::contains_card(short card_index) const { #if UNROLL_CARD_LOOPS assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); if (_cards[0] == card_index) return true; if (_cards[1] == card_index) return true; if (_cards[2] == card_index) return true; if (_cards[3] == card_index) return true; #else for (int i = 0; i < CardsPerEntry; i++) { if (_cards[i] == card_index) return true; } #endif // Otherwise, we're full. return false; } int SparsePRTEntry::num_valid_cards() const { int sum = 0; #if UNROLL_CARD_LOOPS assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); if (_cards[0] != NullEntry) sum++; if (_cards[1] != NullEntry) sum++; if (_cards[2] != NullEntry) sum++; if (_cards[3] != NullEntry) sum++; #else for (int i = 0; i < CardsPerEntry; i++) { if (_cards[i] != NulLEntry) sum++; } #endif // Otherwise, we're full. return sum; } SparsePRTEntry::AddCardResult SparsePRTEntry::add_card(short card_index) { #if UNROLL_CARD_LOOPS assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); short c = _cards[0]; if (c == card_index) return found; if (c == NullEntry) { _cards[0] = card_index; return added; } c = _cards[1]; if (c == card_index) return found; if (c == NullEntry) { _cards[1] = card_index; return added; } c = _cards[2]; if (c == card_index) return found; if (c == NullEntry) { _cards[2] = card_index; return added; } c = _cards[3]; if (c == card_index) return found; if (c == NullEntry) { _cards[3] = card_index; return added; } #else for (int i = 0; i < CardsPerEntry; i++) { short c = _cards[i]; if (c == card_index) return found; if (c == NullEntry) { _cards[i] = card_index; return added; } } #endif // Otherwise, we're full. return overflow; } void SparsePRTEntry::copy_cards(short* cards) const { #if UNROLL_CARD_LOOPS assert(CardsPerEntry == 4, "Assumption. If changes, un-unroll."); cards[0] = _cards[0]; cards[1] = _cards[1]; cards[2] = _cards[2]; cards[3] = _cards[3]; #else for (int i = 0; i < CardsPerEntry; i++) { cards[i] = _cards[i]; } #endif } void SparsePRTEntry::copy_cards(SparsePRTEntry* e) const { copy_cards(&e->_cards[0]); } // ---------------------------------------------------------------------- RSHashTable::RSHashTable(size_t capacity) : _capacity(capacity), _capacity_mask(capacity-1), _occupied_entries(0), _occupied_cards(0), _entries(NEW_C_HEAP_ARRAY(SparsePRTEntry, capacity)), _buckets(NEW_C_HEAP_ARRAY(short, capacity)), _next_deleted(NULL), _deleted(false), _free_list(NullEntry), _free_region(0) { clear(); } RSHashTable::~RSHashTable() { if (_entries != NULL) { FREE_C_HEAP_ARRAY(SparsePRTEntry, _entries); _entries = NULL; } if (_buckets != NULL) { FREE_C_HEAP_ARRAY(short, _buckets); _buckets = NULL; } } void RSHashTable::clear() { _occupied_entries = 0; _occupied_cards = 0; guarantee(_entries != NULL, "INV"); guarantee(_buckets != NULL, "INV"); // This will put -1 == NullEntry in the key field of all entries. memset(_entries, -1, _capacity * sizeof(SparsePRTEntry)); memset(_buckets, -1, _capacity * sizeof(short)); _free_list = NullEntry; _free_region = 0; } bool RSHashTable::add_card(short region_ind, short card_index) { SparsePRTEntry* e = entry_for_region_ind_create(region_ind); assert(e != NULL && e->r_ind() == region_ind, "Postcondition of call above."); SparsePRTEntry::AddCardResult res = e->add_card(card_index); if (res == SparsePRTEntry::added) _occupied_cards++; #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.", pointer_delta(e, _entries, sizeof(SparsePRTEntry)), e->num_valid_cards()); #endif assert(e->num_valid_cards() > 0, "Postcondition"); return res != SparsePRTEntry::overflow; } bool RSHashTable::get_cards(short region_ind, short* cards) { short ind = (short) (region_ind & capacity_mask()); short cur_ind = _buckets[ind]; SparsePRTEntry* cur; while (cur_ind != NullEntry && (cur = entry(cur_ind))->r_ind() != region_ind) { cur_ind = cur->next_index(); } if (cur_ind == NullEntry) return false; // Otherwise... assert(cur->r_ind() == region_ind, "Postcondition of loop + test above."); assert(cur->num_valid_cards() > 0, "Inv"); cur->copy_cards(cards); return true; } bool RSHashTable::delete_entry(short region_ind) { short ind = (short) (region_ind & capacity_mask()); short* prev_loc = &_buckets[ind]; short cur_ind = *prev_loc; SparsePRTEntry* cur; while (cur_ind != NullEntry && (cur = entry(cur_ind))->r_ind() != region_ind) { prev_loc = cur->next_index_addr(); cur_ind = *prev_loc; } if (cur_ind == NullEntry) return false; // Otherwise, splice out "cur". *prev_loc = cur->next_index(); _occupied_cards -= cur->num_valid_cards(); free_entry(cur_ind); _occupied_entries--; return true; } SparsePRTEntry* RSHashTable::entry_for_region_ind(short region_ind) const { assert(occupied_entries() < capacity(), "Precondition"); short ind = (short) (region_ind & capacity_mask()); short cur_ind = _buckets[ind]; SparsePRTEntry* cur; // XXX // int k = 0; while (cur_ind != NullEntry && (cur = entry(cur_ind))->r_ind() != region_ind) { /* k++; if (k > 10) { gclog_or_tty->print_cr("RSHashTable::entry_for_region_ind(%d): " "k = %d, cur_ind = %d.", region_ind, k, cur_ind); if (k >= 1000) { while (1) ; } } */ cur_ind = cur->next_index(); } if (cur_ind != NullEntry) { assert(cur->r_ind() == region_ind, "Loop postcondition + test"); return cur; } else { return NULL; } } SparsePRTEntry* RSHashTable::entry_for_region_ind_create(short region_ind) { SparsePRTEntry* res = entry_for_region_ind(region_ind); if (res == NULL) { short new_ind = alloc_entry(); assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room."); res = entry(new_ind); res->init(region_ind); // Insert at front. short ind = (short) (region_ind & capacity_mask()); res->set_next_index(_buckets[ind]); _buckets[ind] = new_ind; _occupied_entries++; } return res; } short RSHashTable::alloc_entry() { short res; if (_free_list != NullEntry) { res = _free_list; _free_list = entry(res)->next_index(); return res; } else if ((size_t) _free_region+1 < capacity()) { res = _free_region; _free_region++; return res; } else { return NullEntry; } } void RSHashTable::free_entry(short fi) { entry(fi)->set_next_index(_free_list); _free_list = fi; } void RSHashTable::add_entry(SparsePRTEntry* e) { assert(e->num_valid_cards() > 0, "Precondition."); SparsePRTEntry* e2 = entry_for_region_ind_create(e->r_ind()); e->copy_cards(e2); _occupied_cards += e2->num_valid_cards(); assert(e2->num_valid_cards() > 0, "Postcondition."); } RSHashTable* RSHashTable::_head_deleted_list = NULL; void RSHashTable::add_to_deleted_list(RSHashTable* rsht) { assert(!rsht->deleted(), "Should delete only once."); rsht->set_deleted(true); RSHashTable* hd = _head_deleted_list; while (true) { rsht->_next_deleted = hd; RSHashTable* res = (RSHashTable*) Atomic::cmpxchg_ptr(rsht, &_head_deleted_list, hd); if (res == hd) return; else hd = res; } } RSHashTable* RSHashTable::get_from_deleted_list() { RSHashTable* hd = _head_deleted_list; while (hd != NULL) { RSHashTable* next = hd->next_deleted(); RSHashTable* res = (RSHashTable*) Atomic::cmpxchg_ptr(next, &_head_deleted_list, hd); if (res == hd) { hd->set_next_deleted(NULL); hd->set_deleted(false); return hd; } else { hd = res; } } return NULL; } short /* RSHashTable:: */ RSHashTableIter::find_first_card_in_list() { short res; while (_bl_ind != RSHashTable::NullEntry) { res = _rsht->entry(_bl_ind)->card(0); if (res != SparsePRTEntry::NullEntry) { return res; } else { _bl_ind = _rsht->entry(_bl_ind)->next_index(); } } // Otherwise, none found: return SparsePRTEntry::NullEntry; } size_t /* RSHashTable:: */ RSHashTableIter::compute_card_ind(short ci) { return _heap_bot_card_ind + (_rsht->entry(_bl_ind)->r_ind() * CardsPerRegion) + ci; } bool /* RSHashTable:: */ RSHashTableIter::has_next(size_t& card_index) { _card_ind++; short ci; if (_card_ind < SparsePRTEntry::CardsPerEntry && ((ci = _rsht->entry(_bl_ind)->card(_card_ind)) != SparsePRTEntry::NullEntry)) { card_index = compute_card_ind(ci); return true; } // Otherwise, must find the next valid entry. _card_ind = 0; if (_bl_ind != RSHashTable::NullEntry) { _bl_ind = _rsht->entry(_bl_ind)->next_index(); ci = find_first_card_in_list(); if (ci != SparsePRTEntry::NullEntry) { card_index = compute_card_ind(ci); return true; } } // If we didn't return above, must go to the next non-null table index. _tbl_ind++; while ((size_t)_tbl_ind < _rsht->capacity()) { _bl_ind = _rsht->_buckets[_tbl_ind]; ci = find_first_card_in_list(); if (ci != SparsePRTEntry::NullEntry) { card_index = compute_card_ind(ci); return true; } // Otherwise, try next entry. _tbl_ind++; } // Otherwise, there were no entry. return false; } bool RSHashTable::contains_card(short region_index, short card_index) const { SparsePRTEntry* e = entry_for_region_ind(region_index); return (e != NULL && e->contains_card(card_index)); } size_t RSHashTable::mem_size() const { return sizeof(this) + capacity() * (sizeof(SparsePRTEntry) + sizeof(short)); } // ---------------------------------------------------------------------- SparsePRT* SparsePRT::_head_expanded_list = NULL; void SparsePRT::add_to_expanded_list(SparsePRT* sprt) { // We could expand multiple times in a pause -- only put on list once. if (sprt->expanded()) return; sprt->set_expanded(true); SparsePRT* hd = _head_expanded_list; while (true) { sprt->_next_expanded = hd; SparsePRT* res = (SparsePRT*) Atomic::cmpxchg_ptr(sprt, &_head_expanded_list, hd); if (res == hd) return; else hd = res; } } SparsePRT* SparsePRT::get_from_expanded_list() { SparsePRT* hd = _head_expanded_list; while (hd != NULL) { SparsePRT* next = hd->next_expanded(); SparsePRT* res = (SparsePRT*) Atomic::cmpxchg_ptr(next, &_head_expanded_list, hd); if (res == hd) { hd->set_next_expanded(NULL); return hd; } else { hd = res; } } return NULL; } void SparsePRT::cleanup_all() { // First clean up all expanded tables so they agree on next and cur. SparsePRT* sprt = get_from_expanded_list(); while (sprt != NULL) { sprt->cleanup(); sprt = get_from_expanded_list(); } // Now delete all deleted RSHashTables. RSHashTable* rsht = RSHashTable::get_from_deleted_list(); while (rsht != NULL) { #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr("About to delete RSHT " PTR_FORMAT ".", rsht); #endif delete rsht; rsht = RSHashTable::get_from_deleted_list(); } } SparsePRT::SparsePRT(HeapRegion* hr) : _expanded(false), _next_expanded(NULL) { _cur = new RSHashTable(InitialCapacity); _next = _cur; } SparsePRT::~SparsePRT() { assert(_next != NULL && _cur != NULL, "Inv"); if (_cur != _next) { delete _cur; } delete _next; } size_t SparsePRT::mem_size() const { // We ignore "_cur" here, because it either = _next, or else it is // on the deleted list. return sizeof(this) + _next->mem_size(); } bool SparsePRT::add_card(short region_id, short card_index) { #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr(" Adding card %d from region %d to region %d sparse.", card_index, region_id, _hr->hrs_index()); #endif if (_next->occupied_entries() * 2 > _next->capacity()) { expand(); } return _next->add_card(region_id, card_index); } bool SparsePRT::get_cards(short region_id, short* cards) { return _next->get_cards(region_id, cards); } bool SparsePRT::delete_entry(short region_id) { return _next->delete_entry(region_id); } void SparsePRT::clear() { // If they differ, _next is bigger then cur, so next has no chance of // being the initial size. if (_next != _cur) { delete _next; } if (_cur->capacity() != InitialCapacity) { delete _cur; _cur = new RSHashTable(InitialCapacity); } else { _cur->clear(); } _next = _cur; } void SparsePRT::cleanup() { // Make sure that the current and next tables agree. (Another mechanism // takes care of deleting now-unused tables.) _cur = _next; } void SparsePRT::expand() { RSHashTable* last = _next; _next = new RSHashTable(last->capacity() * 2); #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr(" Expanded sparse table for %d to %d.", _hr->hrs_index(), _next->capacity()); #endif for (size_t i = 0; i < last->capacity(); i++) { SparsePRTEntry* e = last->entry((int)i); if (e->valid_entry()) { #if SPARSE_PRT_VERBOSE gclog_or_tty->print_cr(" During expansion, transferred entry for %d.", e->r_ind()); #endif _next->add_entry(e); } } if (last != _cur) RSHashTable::add_to_deleted_list(last); add_to_expanded_list(this); }