1 /*
2 * Copyright (c) 2001, 2013, 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 *
177 _free_list = NullEntry;
178 _free_region = 0;
179 }
180
181 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
182 SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
183 assert(e != NULL && e->r_ind() == region_ind,
184 "Postcondition of call above.");
185 SparsePRTEntry::AddCardResult res = e->add_card(card_index);
186 if (res == SparsePRTEntry::added) _occupied_cards++;
187 #if SPARSE_PRT_VERBOSE
188 gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.",
189 pointer_delta(e, _entries, SparsePRTEntry::size()),
190 e->num_valid_cards());
191 #endif
192 assert(e->num_valid_cards() > 0, "Postcondition");
193 return res != SparsePRTEntry::overflow;
194 }
195
196 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
197 int ind = (int) (region_ind & capacity_mask());
198 int cur_ind = _buckets[ind];
199 SparsePRTEntry* cur;
200 while (cur_ind != NullEntry &&
201 (cur = entry(cur_ind))->r_ind() != region_ind) {
202 cur_ind = cur->next_index();
203 }
204
205 if (cur_ind == NullEntry) return false;
206 // Otherwise...
207 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
208 assert(cur->num_valid_cards() > 0, "Inv");
209 cur->copy_cards(cards);
210 return true;
211 }
212
213 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) {
214 int ind = (int) (region_ind & capacity_mask());
215 int cur_ind = _buckets[ind];
216 SparsePRTEntry* cur;
217 while (cur_ind != NullEntry &&
218 (cur = entry(cur_ind))->r_ind() != region_ind) {
219 cur_ind = cur->next_index();
220 }
221
222 if (cur_ind == NullEntry) return NULL;
223 // Otherwise...
224 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
225 assert(cur->num_valid_cards() > 0, "Inv");
226 return cur;
227 }
228
229 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
230 int ind = (int) (region_ind & capacity_mask());
231 int* prev_loc = &_buckets[ind];
232 int cur_ind = *prev_loc;
233 SparsePRTEntry* cur;
234 while (cur_ind != NullEntry &&
235 (cur = entry(cur_ind))->r_ind() != region_ind) {
236 prev_loc = cur->next_index_addr();
237 cur_ind = *prev_loc;
238 }
239
240 if (cur_ind == NullEntry) return false;
241 // Otherwise, splice out "cur".
242 *prev_loc = cur->next_index();
243 _occupied_cards -= cur->num_valid_cards();
244 free_entry(cur_ind);
245 _occupied_entries--;
246 return true;
247 }
248
249 SparsePRTEntry*
250 RSHashTable::entry_for_region_ind(RegionIdx_t region_ind) const {
251 assert(occupied_entries() < capacity(), "Precondition");
252 int ind = (int) (region_ind & capacity_mask());
253 int cur_ind = _buckets[ind];
254 SparsePRTEntry* cur;
255 while (cur_ind != NullEntry &&
256 (cur = entry(cur_ind))->r_ind() != region_ind) {
257 cur_ind = cur->next_index();
258 }
259
260 if (cur_ind != NullEntry) {
261 assert(cur->r_ind() == region_ind, "Loop postcondition + test");
262 return cur;
263 } else {
264 return NULL;
265 }
266 }
267
268 SparsePRTEntry*
269 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
270 SparsePRTEntry* res = entry_for_region_ind(region_ind);
271 if (res == NULL) {
272 int new_ind = alloc_entry();
273 assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
274 res = entry(new_ind);
275 res->init(region_ind);
276 // Insert at front.
277 int ind = (int) (region_ind & capacity_mask());
278 res->set_next_index(_buckets[ind]);
279 _buckets[ind] = new_ind;
280 _occupied_entries++;
281 }
282 return res;
283 }
284
285 int RSHashTable::alloc_entry() {
286 int res;
287 if (_free_list != NullEntry) {
288 res = _free_list;
289 _free_list = entry(res)->next_index();
290 return res;
348 return true;
349 }
350 }
351 // If we didn't return above, must go to the next non-null table index.
352 _tbl_ind++;
353 while ((size_t)_tbl_ind < _rsht->capacity()) {
354 _bl_ind = _rsht->_buckets[_tbl_ind];
355 ci = find_first_card_in_list();
356 if (ci != SparsePRTEntry::NullEntry) {
357 card_index = compute_card_ind(ci);
358 return true;
359 }
360 // Otherwise, try next entry.
361 _tbl_ind++;
362 }
363 // Otherwise, there were no entry.
364 return false;
365 }
366
367 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
368 SparsePRTEntry* e = entry_for_region_ind(region_index);
369 return (e != NULL && e->contains_card(card_index));
370 }
371
372 size_t RSHashTable::mem_size() const {
373 return sizeof(RSHashTable) +
374 capacity() * (SparsePRTEntry::size() + sizeof(int));
375 }
376
377 // ----------------------------------------------------------------------
378
379 SparsePRT* SparsePRT::_head_expanded_list = NULL;
380
381 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
382 // We could expand multiple times in a pause -- only put on list once.
383 if (sprt->expanded()) return;
384 sprt->set_expanded(true);
385 SparsePRT* hd = _head_expanded_list;
386 while (true) {
387 sprt->_next_expanded = hd;
388 SparsePRT* res =
|
1 /*
2 * Copyright (c) 2001, 2014, 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 *
177 _free_list = NullEntry;
178 _free_region = 0;
179 }
180
181 bool RSHashTable::add_card(RegionIdx_t region_ind, CardIdx_t card_index) {
182 SparsePRTEntry* e = entry_for_region_ind_create(region_ind);
183 assert(e != NULL && e->r_ind() == region_ind,
184 "Postcondition of call above.");
185 SparsePRTEntry::AddCardResult res = e->add_card(card_index);
186 if (res == SparsePRTEntry::added) _occupied_cards++;
187 #if SPARSE_PRT_VERBOSE
188 gclog_or_tty->print_cr(" after add_card[%d]: valid-cards = %d.",
189 pointer_delta(e, _entries, SparsePRTEntry::size()),
190 e->num_valid_cards());
191 #endif
192 assert(e->num_valid_cards() > 0, "Postcondition");
193 return res != SparsePRTEntry::overflow;
194 }
195
196 bool RSHashTable::get_cards(RegionIdx_t region_ind, CardIdx_t* cards) {
197
198 SparsePRTEntry* entry = get_entry(region_ind);
199 if (entry == NULL) {
200 return false;
201 }
202 // Otherwise...
203 entry->copy_cards(cards);
204 return true;
205 }
206
207 SparsePRTEntry* RSHashTable::get_entry(RegionIdx_t region_ind) const {
208 int ind = (int) (region_ind & capacity_mask());
209 int cur_ind = _buckets[ind];
210 SparsePRTEntry* cur;
211 while (cur_ind != NullEntry &&
212 (cur = entry(cur_ind))->r_ind() != region_ind) {
213 cur_ind = cur->next_index();
214 }
215
216 if (cur_ind == NullEntry) return NULL;
217 // Otherwise...
218 assert(cur->r_ind() == region_ind, "Postcondition of loop + test above.");
219 assert(cur->num_valid_cards() > 0, "Inv");
220 return cur;
221 }
222
223 bool RSHashTable::delete_entry(RegionIdx_t region_ind) {
224 int ind = (int) (region_ind & capacity_mask());
225 int* prev_loc = &_buckets[ind];
226 int cur_ind = *prev_loc;
227 SparsePRTEntry* cur;
228 while (cur_ind != NullEntry &&
229 (cur = entry(cur_ind))->r_ind() != region_ind) {
230 prev_loc = cur->next_index_addr();
231 cur_ind = *prev_loc;
232 }
233
234 if (cur_ind == NullEntry) return false;
235 // Otherwise, splice out "cur".
236 *prev_loc = cur->next_index();
237 _occupied_cards -= cur->num_valid_cards();
238 free_entry(cur_ind);
239 _occupied_entries--;
240 return true;
241 }
242
243 SparsePRTEntry*
244 RSHashTable::entry_for_region_ind_create(RegionIdx_t region_ind) {
245 SparsePRTEntry* res = get_entry(region_ind);
246 if (res == NULL) {
247 int new_ind = alloc_entry();
248 assert(0 <= new_ind && (size_t)new_ind < capacity(), "There should be room.");
249 res = entry(new_ind);
250 res->init(region_ind);
251 // Insert at front.
252 int ind = (int) (region_ind & capacity_mask());
253 res->set_next_index(_buckets[ind]);
254 _buckets[ind] = new_ind;
255 _occupied_entries++;
256 }
257 return res;
258 }
259
260 int RSHashTable::alloc_entry() {
261 int res;
262 if (_free_list != NullEntry) {
263 res = _free_list;
264 _free_list = entry(res)->next_index();
265 return res;
323 return true;
324 }
325 }
326 // If we didn't return above, must go to the next non-null table index.
327 _tbl_ind++;
328 while ((size_t)_tbl_ind < _rsht->capacity()) {
329 _bl_ind = _rsht->_buckets[_tbl_ind];
330 ci = find_first_card_in_list();
331 if (ci != SparsePRTEntry::NullEntry) {
332 card_index = compute_card_ind(ci);
333 return true;
334 }
335 // Otherwise, try next entry.
336 _tbl_ind++;
337 }
338 // Otherwise, there were no entry.
339 return false;
340 }
341
342 bool RSHashTable::contains_card(RegionIdx_t region_index, CardIdx_t card_index) const {
343 SparsePRTEntry* e = get_entry(region_index);
344 return (e != NULL && e->contains_card(card_index));
345 }
346
347 size_t RSHashTable::mem_size() const {
348 return sizeof(RSHashTable) +
349 capacity() * (SparsePRTEntry::size() + sizeof(int));
350 }
351
352 // ----------------------------------------------------------------------
353
354 SparsePRT* SparsePRT::_head_expanded_list = NULL;
355
356 void SparsePRT::add_to_expanded_list(SparsePRT* sprt) {
357 // We could expand multiple times in a pause -- only put on list once.
358 if (sprt->expanded()) return;
359 sprt->set_expanded(true);
360 SparsePRT* hd = _head_expanded_list;
361 while (true) {
362 sprt->_next_expanded = hd;
363 SparsePRT* res =
|