annotate src/share/vm/memory/blockOffsetTable.cpp @ 0:a61af66fc99e

Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children 37f87013dfd8
rev   line source
duke@0 1 /*
duke@0 2 * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved.
duke@0 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@0 4 *
duke@0 5 * This code is free software; you can redistribute it and/or modify it
duke@0 6 * under the terms of the GNU General Public License version 2 only, as
duke@0 7 * published by the Free Software Foundation.
duke@0 8 *
duke@0 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@0 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@0 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@0 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@0 13 * accompanied this code).
duke@0 14 *
duke@0 15 * You should have received a copy of the GNU General Public License version
duke@0 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@0 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@0 18 *
duke@0 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@0 20 * CA 95054 USA or visit www.sun.com if you need additional information or
duke@0 21 * have any questions.
duke@0 22 *
duke@0 23 */
duke@0 24
duke@0 25 # include "incls/_precompiled.incl"
duke@0 26 # include "incls/_blockOffsetTable.cpp.incl"
duke@0 27
duke@0 28 //////////////////////////////////////////////////////////////////////
duke@0 29 // BlockOffsetSharedArray
duke@0 30 //////////////////////////////////////////////////////////////////////
duke@0 31
duke@0 32 BlockOffsetSharedArray::BlockOffsetSharedArray(MemRegion reserved,
duke@0 33 size_t init_word_size):
duke@0 34 _reserved(reserved), _end(NULL)
duke@0 35 {
duke@0 36 size_t size = compute_size(reserved.word_size());
duke@0 37 ReservedSpace rs(size);
duke@0 38 if (!rs.is_reserved()) {
duke@0 39 vm_exit_during_initialization("Could not reserve enough space for heap offset array");
duke@0 40 }
duke@0 41 if (!_vs.initialize(rs, 0)) {
duke@0 42 vm_exit_during_initialization("Could not reserve enough space for heap offset array");
duke@0 43 }
duke@0 44 _offset_array = (u_char*)_vs.low_boundary();
duke@0 45 resize(init_word_size);
duke@0 46 if (TraceBlockOffsetTable) {
duke@0 47 gclog_or_tty->print_cr("BlockOffsetSharedArray::BlockOffsetSharedArray: ");
duke@0 48 gclog_or_tty->print_cr(" "
duke@0 49 " rs.base(): " INTPTR_FORMAT
duke@0 50 " rs.size(): " INTPTR_FORMAT
duke@0 51 " rs end(): " INTPTR_FORMAT,
duke@0 52 rs.base(), rs.size(), rs.base() + rs.size());
duke@0 53 gclog_or_tty->print_cr(" "
duke@0 54 " _vs.low_boundary(): " INTPTR_FORMAT
duke@0 55 " _vs.high_boundary(): " INTPTR_FORMAT,
duke@0 56 _vs.low_boundary(),
duke@0 57 _vs.high_boundary());
duke@0 58 }
duke@0 59 }
duke@0 60
duke@0 61 void BlockOffsetSharedArray::resize(size_t new_word_size) {
duke@0 62 assert(new_word_size <= _reserved.word_size(), "Resize larger than reserved");
duke@0 63 size_t new_size = compute_size(new_word_size);
duke@0 64 size_t old_size = _vs.committed_size();
duke@0 65 size_t delta;
duke@0 66 char* high = _vs.high();
duke@0 67 _end = _reserved.start() + new_word_size;
duke@0 68 if (new_size > old_size) {
duke@0 69 delta = ReservedSpace::page_align_size_up(new_size - old_size);
duke@0 70 assert(delta > 0, "just checking");
duke@0 71 if (!_vs.expand_by(delta)) {
duke@0 72 // Do better than this for Merlin
duke@0 73 vm_exit_out_of_memory(delta, "offset table expansion");
duke@0 74 }
duke@0 75 assert(_vs.high() == high + delta, "invalid expansion");
duke@0 76 } else {
duke@0 77 delta = ReservedSpace::page_align_size_down(old_size - new_size);
duke@0 78 if (delta == 0) return;
duke@0 79 _vs.shrink_by(delta);
duke@0 80 assert(_vs.high() == high - delta, "invalid expansion");
duke@0 81 }
duke@0 82 }
duke@0 83
duke@0 84 bool BlockOffsetSharedArray::is_card_boundary(HeapWord* p) const {
duke@0 85 assert(p >= _reserved.start(), "just checking");
duke@0 86 size_t delta = pointer_delta(p, _reserved.start());
duke@0 87 return (delta & right_n_bits(LogN_words)) == (size_t)NoBits;
duke@0 88 }
duke@0 89
duke@0 90
duke@0 91 void BlockOffsetSharedArray::serialize(SerializeOopClosure* soc,
duke@0 92 HeapWord* start, HeapWord* end) {
duke@0 93 assert(_offset_array[0] == 0, "objects can't cross covered areas");
duke@0 94 assert(start <= end, "bad address range");
duke@0 95 size_t start_index = index_for(start);
duke@0 96 size_t end_index = index_for(end-1)+1;
duke@0 97 soc->do_region(&_offset_array[start_index],
duke@0 98 (end_index - start_index) * sizeof(_offset_array[0]));
duke@0 99 }
duke@0 100
duke@0 101 //////////////////////////////////////////////////////////////////////
duke@0 102 // BlockOffsetArray
duke@0 103 //////////////////////////////////////////////////////////////////////
duke@0 104
duke@0 105 BlockOffsetArray::BlockOffsetArray(BlockOffsetSharedArray* array,
duke@0 106 MemRegion mr, bool init_to_zero) :
duke@0 107 BlockOffsetTable(mr.start(), mr.end()),
duke@0 108 _array(array),
duke@0 109 _init_to_zero(init_to_zero)
duke@0 110 {
duke@0 111 assert(_bottom <= _end, "arguments out of order");
duke@0 112 if (!_init_to_zero) {
duke@0 113 // initialize cards to point back to mr.start()
duke@0 114 set_remainder_to_point_to_start(mr.start() + N_words, mr.end());
duke@0 115 _array->set_offset_array(0, 0); // set first card to 0
duke@0 116 }
duke@0 117 }
duke@0 118
duke@0 119
duke@0 120 // The arguments follow the normal convention of denoting
duke@0 121 // a right-open interval: [start, end)
duke@0 122 void
duke@0 123 BlockOffsetArray::
duke@0 124 set_remainder_to_point_to_start(HeapWord* start, HeapWord* end) {
duke@0 125
duke@0 126 if (start >= end) {
duke@0 127 // The start address is equal to the end address (or to
duke@0 128 // the right of the end address) so there are not cards
duke@0 129 // that need to be updated..
duke@0 130 return;
duke@0 131 }
duke@0 132
duke@0 133 // Write the backskip value for each region.
duke@0 134 //
duke@0 135 // offset
duke@0 136 // card 2nd 3rd
duke@0 137 // | +- 1st | |
duke@0 138 // v v v v
duke@0 139 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-
duke@0 140 // |x|0|0|0|0|0|0|0|1|1|1|1|1|1| ... |1|1|1|1|2|2|2|2|2|2| ...
duke@0 141 // +-+-+-+-+-+-+-+-+-+-+-+-+-+-+ +-+-+-+-+-+-+-+-+-+-+-
duke@0 142 // 11 19 75
duke@0 143 // 12
duke@0 144 //
duke@0 145 // offset card is the card that points to the start of an object
duke@0 146 // x - offset value of offset card
duke@0 147 // 1st - start of first logarithmic region
duke@0 148 // 0 corresponds to logarithmic value N_words + 0 and 2**(3 * 0) = 1
duke@0 149 // 2nd - start of second logarithmic region
duke@0 150 // 1 corresponds to logarithmic value N_words + 1 and 2**(3 * 1) = 8
duke@0 151 // 3rd - start of third logarithmic region
duke@0 152 // 2 corresponds to logarithmic value N_words + 2 and 2**(3 * 2) = 64
duke@0 153 //
duke@0 154 // integer below the block offset entry is an example of
duke@0 155 // the index of the entry
duke@0 156 //
duke@0 157 // Given an address,
duke@0 158 // Find the index for the address
duke@0 159 // Find the block offset table entry
duke@0 160 // Convert the entry to a back slide
duke@0 161 // (e.g., with today's, offset = 0x81 =>
duke@0 162 // back slip = 2**(3*(0x81 - N_words)) = 2**3) = 8
duke@0 163 // Move back N (e.g., 8) entries and repeat with the
duke@0 164 // value of the new entry
duke@0 165 //
duke@0 166 size_t start_card = _array->index_for(start);
duke@0 167 size_t end_card = _array->index_for(end-1);
duke@0 168 assert(start ==_array->address_for_index(start_card), "Precondition");
duke@0 169 assert(end ==_array->address_for_index(end_card)+N_words, "Precondition");
duke@0 170 set_remainder_to_point_to_start_incl(start_card, end_card); // closed interval
duke@0 171 }
duke@0 172
duke@0 173
duke@0 174 // Unlike the normal convention in this code, the argument here denotes
duke@0 175 // a closed, inclusive interval: [start_card, end_card], cf set_remainder_to_point_to_start()
duke@0 176 // above.
duke@0 177 void
duke@0 178 BlockOffsetArray::set_remainder_to_point_to_start_incl(size_t start_card, size_t end_card) {
duke@0 179 if (start_card > end_card) {
duke@0 180 return;
duke@0 181 }
duke@0 182 assert(start_card > _array->index_for(_bottom), "Cannot be first card");
duke@0 183 assert(_array->offset_array(start_card-1) <= N_words,
duke@0 184 "Offset card has an unexpected value");
duke@0 185 size_t start_card_for_region = start_card;
duke@0 186 u_char offset = max_jubyte;
duke@0 187 for (int i = 0; i <= N_powers-1; i++) {
duke@0 188 // -1 so that the the card with the actual offset is counted. Another -1
duke@0 189 // so that the reach ends in this region and not at the start
duke@0 190 // of the next.
duke@0 191 size_t reach = start_card - 1 + (power_to_cards_back(i+1) - 1);
duke@0 192 offset = N_words + i;
duke@0 193 if (reach >= end_card) {
duke@0 194 _array->set_offset_array(start_card_for_region, end_card, offset);
duke@0 195 start_card_for_region = reach + 1;
duke@0 196 break;
duke@0 197 }
duke@0 198 _array->set_offset_array(start_card_for_region, reach, offset);
duke@0 199 start_card_for_region = reach + 1;
duke@0 200 }
duke@0 201 assert(start_card_for_region > end_card, "Sanity check");
duke@0 202 DEBUG_ONLY(check_all_cards(start_card, end_card);)
duke@0 203 }
duke@0 204
duke@0 205 // The card-interval [start_card, end_card] is a closed interval; this
duke@0 206 // is an expensive check -- use with care and only under protection of
duke@0 207 // suitable flag.
duke@0 208 void BlockOffsetArray::check_all_cards(size_t start_card, size_t end_card) const {
duke@0 209
duke@0 210 if (end_card < start_card) {
duke@0 211 return;
duke@0 212 }
duke@0 213 guarantee(_array->offset_array(start_card) == N_words, "Wrong value in second card");
duke@0 214 for (size_t c = start_card + 1; c <= end_card; c++ /* yeah! */) {
duke@0 215 u_char entry = _array->offset_array(c);
duke@0 216 if (c - start_card > power_to_cards_back(1)) {
duke@0 217 guarantee(entry > N_words, "Should be in logarithmic region");
duke@0 218 }
duke@0 219 size_t backskip = entry_to_cards_back(entry);
duke@0 220 size_t landing_card = c - backskip;
duke@0 221 guarantee(landing_card >= (start_card - 1), "Inv");
duke@0 222 if (landing_card >= start_card) {
duke@0 223 guarantee(_array->offset_array(landing_card) <= entry, "monotonicity");
duke@0 224 } else {
duke@0 225 guarantee(landing_card == start_card - 1, "Tautology");
duke@0 226 guarantee(_array->offset_array(landing_card) <= N_words, "Offset value");
duke@0 227 }
duke@0 228 }
duke@0 229 }
duke@0 230
duke@0 231
duke@0 232 void
duke@0 233 BlockOffsetArray::alloc_block(HeapWord* blk_start, HeapWord* blk_end) {
duke@0 234 assert(blk_start != NULL && blk_end > blk_start,
duke@0 235 "phantom block");
duke@0 236 single_block(blk_start, blk_end);
duke@0 237 }
duke@0 238
duke@0 239 // Action_mark - update the BOT for the block [blk_start, blk_end).
duke@0 240 // Current typical use is for splitting a block.
duke@0 241 // Action_single - udpate the BOT for an allocation.
duke@0 242 // Action_verify - BOT verification.
duke@0 243 void
duke@0 244 BlockOffsetArray::do_block_internal(HeapWord* blk_start,
duke@0 245 HeapWord* blk_end,
duke@0 246 Action action) {
duke@0 247 assert(Universe::heap()->is_in_reserved(blk_start),
duke@0 248 "reference must be into the heap");
duke@0 249 assert(Universe::heap()->is_in_reserved(blk_end-1),
duke@0 250 "limit must be within the heap");
duke@0 251 // This is optimized to make the test fast, assuming we only rarely
duke@0 252 // cross boundaries.
duke@0 253 uintptr_t end_ui = (uintptr_t)(blk_end - 1);
duke@0 254 uintptr_t start_ui = (uintptr_t)blk_start;
duke@0 255 // Calculate the last card boundary preceding end of blk
duke@0 256 intptr_t boundary_before_end = (intptr_t)end_ui;
duke@0 257 clear_bits(boundary_before_end, right_n_bits(LogN));
duke@0 258 if (start_ui <= (uintptr_t)boundary_before_end) {
duke@0 259 // blk starts at or crosses a boundary
duke@0 260 // Calculate index of card on which blk begins
duke@0 261 size_t start_index = _array->index_for(blk_start);
duke@0 262 // Index of card on which blk ends
duke@0 263 size_t end_index = _array->index_for(blk_end - 1);
duke@0 264 // Start address of card on which blk begins
duke@0 265 HeapWord* boundary = _array->address_for_index(start_index);
duke@0 266 assert(boundary <= blk_start, "blk should start at or after boundary");
duke@0 267 if (blk_start != boundary) {
duke@0 268 // blk starts strictly after boundary
duke@0 269 // adjust card boundary and start_index forward to next card
duke@0 270 boundary += N_words;
duke@0 271 start_index++;
duke@0 272 }
duke@0 273 assert(start_index <= end_index, "monotonicity of index_for()");
duke@0 274 assert(boundary <= (HeapWord*)boundary_before_end, "tautology");
duke@0 275 switch (action) {
duke@0 276 case Action_mark: {
duke@0 277 if (init_to_zero()) {
duke@0 278 _array->set_offset_array(start_index, boundary, blk_start);
duke@0 279 break;
duke@0 280 } // Else fall through to the next case
duke@0 281 }
duke@0 282 case Action_single: {
duke@0 283 _array->set_offset_array(start_index, boundary, blk_start);
duke@0 284 // We have finished marking the "offset card". We need to now
duke@0 285 // mark the subsequent cards that this blk spans.
duke@0 286 if (start_index < end_index) {
duke@0 287 HeapWord* rem_st = _array->address_for_index(start_index) + N_words;
duke@0 288 HeapWord* rem_end = _array->address_for_index(end_index) + N_words;
duke@0 289 set_remainder_to_point_to_start(rem_st, rem_end);
duke@0 290 }
duke@0 291 break;
duke@0 292 }
duke@0 293 case Action_check: {
duke@0 294 _array->check_offset_array(start_index, boundary, blk_start);
duke@0 295 // We have finished checking the "offset card". We need to now
duke@0 296 // check the subsequent cards that this blk spans.
duke@0 297 check_all_cards(start_index + 1, end_index);
duke@0 298 break;
duke@0 299 }
duke@0 300 default:
duke@0 301 ShouldNotReachHere();
duke@0 302 }
duke@0 303 }
duke@0 304 }
duke@0 305
duke@0 306 // The range [blk_start, blk_end) represents a single contiguous block
duke@0 307 // of storage; modify the block offset table to represent this
duke@0 308 // information; Right-open interval: [blk_start, blk_end)
duke@0 309 // NOTE: this method does _not_ adjust _unallocated_block.
duke@0 310 void
duke@0 311 BlockOffsetArray::single_block(HeapWord* blk_start,
duke@0 312 HeapWord* blk_end) {
duke@0 313 do_block_internal(blk_start, blk_end, Action_single);
duke@0 314 }
duke@0 315
duke@0 316 void BlockOffsetArray::verify() const {
duke@0 317 // For each entry in the block offset table, verify that
duke@0 318 // the entry correctly finds the start of an object at the
duke@0 319 // first address covered by the block or to the left of that
duke@0 320 // first address.
duke@0 321
duke@0 322 size_t next_index = 1;
duke@0 323 size_t last_index = last_active_index();
duke@0 324
duke@0 325 // Use for debugging. Initialize to NULL to distinguish the
duke@0 326 // first iteration through the while loop.
duke@0 327 HeapWord* last_p = NULL;
duke@0 328 HeapWord* last_start = NULL;
duke@0 329 oop last_o = NULL;
duke@0 330
duke@0 331 while (next_index <= last_index) {
duke@0 332 // Use an address past the start of the address for
duke@0 333 // the entry.
duke@0 334 HeapWord* p = _array->address_for_index(next_index) + 1;
duke@0 335 if (p >= _end) {
duke@0 336 // That's all of the allocated block table.
duke@0 337 return;
duke@0 338 }
duke@0 339 // block_start() asserts that start <= p.
duke@0 340 HeapWord* start = block_start(p);
duke@0 341 // First check if the start is an allocated block and only
duke@0 342 // then if it is a valid object.
duke@0 343 oop o = oop(start);
duke@0 344 assert(!Universe::is_fully_initialized() ||
duke@0 345 _sp->is_free_block(start) ||
duke@0 346 o->is_oop_or_null(), "Bad object was found");
duke@0 347 next_index++;
duke@0 348 last_p = p;
duke@0 349 last_start = start;
duke@0 350 last_o = o;
duke@0 351 }
duke@0 352 }
duke@0 353
duke@0 354 //////////////////////////////////////////////////////////////////////
duke@0 355 // BlockOffsetArrayNonContigSpace
duke@0 356 //////////////////////////////////////////////////////////////////////
duke@0 357
duke@0 358 // The block [blk_start, blk_end) has been allocated;
duke@0 359 // adjust the block offset table to represent this information;
duke@0 360 // NOTE: Clients of BlockOffsetArrayNonContigSpace: consider using
duke@0 361 // the somewhat more lightweight split_block() or
duke@0 362 // (when init_to_zero()) mark_block() wherever possible.
duke@0 363 // right-open interval: [blk_start, blk_end)
duke@0 364 void
duke@0 365 BlockOffsetArrayNonContigSpace::alloc_block(HeapWord* blk_start,
duke@0 366 HeapWord* blk_end) {
duke@0 367 assert(blk_start != NULL && blk_end > blk_start,
duke@0 368 "phantom block");
duke@0 369 single_block(blk_start, blk_end);
duke@0 370 allocated(blk_start, blk_end);
duke@0 371 }
duke@0 372
duke@0 373 // Adjust BOT to show that a previously whole block has been split
duke@0 374 // into two. We verify the BOT for the first part (prefix) and
duke@0 375 // update the BOT for the second part (suffix).
duke@0 376 // blk is the start of the block
duke@0 377 // blk_size is the size of the original block
duke@0 378 // left_blk_size is the size of the first part of the split
duke@0 379 void BlockOffsetArrayNonContigSpace::split_block(HeapWord* blk,
duke@0 380 size_t blk_size,
duke@0 381 size_t left_blk_size) {
duke@0 382 // Verify that the BOT shows [blk, blk + blk_size) to be one block.
duke@0 383 verify_single_block(blk, blk_size);
duke@0 384 // Update the BOT to indicate that [blk + left_blk_size, blk + blk_size)
duke@0 385 // is one single block.
duke@0 386 assert(blk_size > 0, "Should be positive");
duke@0 387 assert(left_blk_size > 0, "Should be positive");
duke@0 388 assert(left_blk_size < blk_size, "Not a split");
duke@0 389
duke@0 390 // Start addresses of prefix block and suffix block.
duke@0 391 HeapWord* pref_addr = blk;
duke@0 392 HeapWord* suff_addr = blk + left_blk_size;
duke@0 393 HeapWord* end_addr = blk + blk_size;
duke@0 394
duke@0 395 // Indices for starts of prefix block and suffix block.
duke@0 396 size_t pref_index = _array->index_for(pref_addr);
duke@0 397 if (_array->address_for_index(pref_index) != pref_addr) {
duke@0 398 // pref_addr deos not begin pref_index
duke@0 399 pref_index++;
duke@0 400 }
duke@0 401
duke@0 402 size_t suff_index = _array->index_for(suff_addr);
duke@0 403 if (_array->address_for_index(suff_index) != suff_addr) {
duke@0 404 // suff_addr does not begin suff_index
duke@0 405 suff_index++;
duke@0 406 }
duke@0 407
duke@0 408 // Definition: A block B, denoted [B_start, B_end) __starts__
duke@0 409 // a card C, denoted [C_start, C_end), where C_start and C_end
duke@0 410 // are the heap addresses that card C covers, iff
duke@0 411 // B_start <= C_start < B_end.
duke@0 412 //
duke@0 413 // We say that a card C "is started by" a block B, iff
duke@0 414 // B "starts" C.
duke@0 415 //
duke@0 416 // Note that the cardinality of the set of cards {C}
duke@0 417 // started by a block B can be 0, 1, or more.
duke@0 418 //
duke@0 419 // Below, pref_index and suff_index are, respectively, the
duke@0 420 // first (least) card indices that the prefix and suffix of
duke@0 421 // the split start; end_index is one more than the index of
duke@0 422 // the last (greatest) card that blk starts.
duke@0 423 size_t end_index = _array->index_for(end_addr - 1) + 1;
duke@0 424
duke@0 425 // Calculate the # cards that the prefix and suffix affect.
duke@0 426 size_t num_pref_cards = suff_index - pref_index;
duke@0 427
duke@0 428 size_t num_suff_cards = end_index - suff_index;
duke@0 429 // Change the cards that need changing
duke@0 430 if (num_suff_cards > 0) {
duke@0 431 HeapWord* boundary = _array->address_for_index(suff_index);
duke@0 432 // Set the offset card for suffix block
duke@0 433 _array->set_offset_array(suff_index, boundary, suff_addr);
duke@0 434 // Change any further cards that need changing in the suffix
duke@0 435 if (num_pref_cards > 0) {
duke@0 436 if (num_pref_cards >= num_suff_cards) {
duke@0 437 // Unilaterally fix all of the suffix cards: closed card
duke@0 438 // index interval in args below.
duke@0 439 set_remainder_to_point_to_start_incl(suff_index + 1, end_index - 1);
duke@0 440 } else {
duke@0 441 // Unilaterally fix the first (num_pref_cards - 1) following
duke@0 442 // the "offset card" in the suffix block.
duke@0 443 set_remainder_to_point_to_start_incl(suff_index + 1,
duke@0 444 suff_index + num_pref_cards - 1);
duke@0 445 // Fix the appropriate cards in the remainder of the
duke@0 446 // suffix block -- these are the last num_pref_cards
duke@0 447 // cards in each power block of the "new" range plumbed
duke@0 448 // from suff_addr.
duke@0 449 bool more = true;
duke@0 450 uint i = 1;
duke@0 451 while (more && (i < N_powers)) {
duke@0 452 size_t back_by = power_to_cards_back(i);
duke@0 453 size_t right_index = suff_index + back_by - 1;
duke@0 454 size_t left_index = right_index - num_pref_cards + 1;
duke@0 455 if (right_index >= end_index - 1) { // last iteration
duke@0 456 right_index = end_index - 1;
duke@0 457 more = false;
duke@0 458 }
duke@0 459 if (back_by > num_pref_cards) {
duke@0 460 // Fill in the remainder of this "power block", if it
duke@0 461 // is non-null.
duke@0 462 if (left_index <= right_index) {
duke@0 463 _array->set_offset_array(left_index, right_index,
duke@0 464 N_words + i - 1);
duke@0 465 } else {
duke@0 466 more = false; // we are done
duke@0 467 }
duke@0 468 i++;
duke@0 469 break;
duke@0 470 }
duke@0 471 i++;
duke@0 472 }
duke@0 473 while (more && (i < N_powers)) {
duke@0 474 size_t back_by = power_to_cards_back(i);
duke@0 475 size_t right_index = suff_index + back_by - 1;
duke@0 476 size_t left_index = right_index - num_pref_cards + 1;
duke@0 477 if (right_index >= end_index - 1) { // last iteration
duke@0 478 right_index = end_index - 1;
duke@0 479 if (left_index > right_index) {
duke@0 480 break;
duke@0 481 }
duke@0 482 more = false;
duke@0 483 }
duke@0 484 assert(left_index <= right_index, "Error");
duke@0 485 _array->set_offset_array(left_index, right_index, N_words + i - 1);
duke@0 486 i++;
duke@0 487 }
duke@0 488 }
duke@0 489 } // else no more cards to fix in suffix
duke@0 490 } // else nothing needs to be done
duke@0 491 // Verify that we did the right thing
duke@0 492 verify_single_block(pref_addr, left_blk_size);
duke@0 493 verify_single_block(suff_addr, blk_size - left_blk_size);
duke@0 494 }
duke@0 495
duke@0 496
duke@0 497 // Mark the BOT such that if [blk_start, blk_end) straddles a card
duke@0 498 // boundary, the card following the first such boundary is marked
duke@0 499 // with the appropriate offset.
duke@0 500 // NOTE: this method does _not_ adjust _unallocated_block or
duke@0 501 // any cards subsequent to the first one.
duke@0 502 void
duke@0 503 BlockOffsetArrayNonContigSpace::mark_block(HeapWord* blk_start,
duke@0 504 HeapWord* blk_end) {
duke@0 505 do_block_internal(blk_start, blk_end, Action_mark);
duke@0 506 }
duke@0 507
duke@0 508 HeapWord* BlockOffsetArrayNonContigSpace::block_start_unsafe(
duke@0 509 const void* addr) const {
duke@0 510 assert(_array->offset_array(0) == 0, "objects can't cross covered areas");
duke@0 511
duke@0 512 assert(_bottom <= addr && addr < _end,
duke@0 513 "addr must be covered by this Array");
duke@0 514 // Must read this exactly once because it can be modified by parallel
duke@0 515 // allocation.
duke@0 516 HeapWord* ub = _unallocated_block;
duke@0 517 if (BlockOffsetArrayUseUnallocatedBlock && addr >= ub) {
duke@0 518 assert(ub < _end, "tautology (see above)");
duke@0 519 return ub;
duke@0 520 }
duke@0 521
duke@0 522 // Otherwise, find the block start using the table.
duke@0 523 size_t index = _array->index_for(addr);
duke@0 524 HeapWord* q = _array->address_for_index(index);
duke@0 525
duke@0 526 uint offset = _array->offset_array(index); // Extend u_char to uint.
duke@0 527 while (offset >= N_words) {
duke@0 528 // The excess of the offset from N_words indicates a power of Base
duke@0 529 // to go back by.
duke@0 530 size_t n_cards_back = entry_to_cards_back(offset);
duke@0 531 q -= (N_words * n_cards_back);
duke@0 532 assert(q >= _sp->bottom(), "Went below bottom!");
duke@0 533 index -= n_cards_back;
duke@0 534 offset = _array->offset_array(index);
duke@0 535 }
duke@0 536 assert(offset < N_words, "offset too large");
duke@0 537 index--;
duke@0 538 q -= offset;
duke@0 539 HeapWord* n = q;
duke@0 540
duke@0 541 while (n <= addr) {
duke@0 542 debug_only(HeapWord* last = q); // for debugging
duke@0 543 q = n;
duke@0 544 n += _sp->block_size(n);
duke@0 545 }
duke@0 546 assert(q <= addr, "wrong order for current and arg");
duke@0 547 assert(addr <= n, "wrong order for arg and next");
duke@0 548 return q;
duke@0 549 }
duke@0 550
duke@0 551 HeapWord* BlockOffsetArrayNonContigSpace::block_start_careful(
duke@0 552 const void* addr) const {
duke@0 553 assert(_array->offset_array(0) == 0, "objects can't cross covered areas");
duke@0 554
duke@0 555 assert(_bottom <= addr && addr < _end,
duke@0 556 "addr must be covered by this Array");
duke@0 557 // Must read this exactly once because it can be modified by parallel
duke@0 558 // allocation.
duke@0 559 HeapWord* ub = _unallocated_block;
duke@0 560 if (BlockOffsetArrayUseUnallocatedBlock && addr >= ub) {
duke@0 561 assert(ub < _end, "tautology (see above)");
duke@0 562 return ub;
duke@0 563 }
duke@0 564
duke@0 565 // Otherwise, find the block start using the table, but taking
duke@0 566 // care (cf block_start_unsafe() above) not to parse any objects/blocks
duke@0 567 // on the cards themsleves.
duke@0 568 size_t index = _array->index_for(addr);
duke@0 569 assert(_array->address_for_index(index) == addr,
duke@0 570 "arg should be start of card");
duke@0 571
duke@0 572 HeapWord* q = (HeapWord*)addr;
duke@0 573 uint offset;
duke@0 574 do {
duke@0 575 offset = _array->offset_array(index);
duke@0 576 if (offset < N_words) {
duke@0 577 q -= offset;
duke@0 578 } else {
duke@0 579 size_t n_cards_back = entry_to_cards_back(offset);
duke@0 580 q -= (n_cards_back * N_words);
duke@0 581 index -= n_cards_back;
duke@0 582 }
duke@0 583 } while (offset >= N_words);
duke@0 584 assert(q <= addr, "block start should be to left of arg");
duke@0 585 return q;
duke@0 586 }
duke@0 587
duke@0 588 #ifndef PRODUCT
duke@0 589 // Verification & debugging - ensure that the offset table reflects the fact
duke@0 590 // that the block [blk_start, blk_end) or [blk, blk + size) is a
duke@0 591 // single block of storage. NOTE: can't const this because of
duke@0 592 // call to non-const do_block_internal() below.
duke@0 593 void BlockOffsetArrayNonContigSpace::verify_single_block(
duke@0 594 HeapWord* blk_start, HeapWord* blk_end) {
duke@0 595 if (VerifyBlockOffsetArray) {
duke@0 596 do_block_internal(blk_start, blk_end, Action_check);
duke@0 597 }
duke@0 598 }
duke@0 599
duke@0 600 void BlockOffsetArrayNonContigSpace::verify_single_block(
duke@0 601 HeapWord* blk, size_t size) {
duke@0 602 verify_single_block(blk, blk + size);
duke@0 603 }
duke@0 604
duke@0 605 // Verify that the given block is before _unallocated_block
duke@0 606 void BlockOffsetArrayNonContigSpace::verify_not_unallocated(
duke@0 607 HeapWord* blk_start, HeapWord* blk_end) const {
duke@0 608 if (BlockOffsetArrayUseUnallocatedBlock) {
duke@0 609 assert(blk_start < blk_end, "Block inconsistency?");
duke@0 610 assert(blk_end <= _unallocated_block, "_unallocated_block problem");
duke@0 611 }
duke@0 612 }
duke@0 613
duke@0 614 void BlockOffsetArrayNonContigSpace::verify_not_unallocated(
duke@0 615 HeapWord* blk, size_t size) const {
duke@0 616 verify_not_unallocated(blk, blk + size);
duke@0 617 }
duke@0 618 #endif // PRODUCT
duke@0 619
duke@0 620 size_t BlockOffsetArrayNonContigSpace::last_active_index() const {
duke@0 621 if (_unallocated_block == _bottom) {
duke@0 622 return 0;
duke@0 623 } else {
duke@0 624 return _array->index_for(_unallocated_block - 1);
duke@0 625 }
duke@0 626 }
duke@0 627
duke@0 628 //////////////////////////////////////////////////////////////////////
duke@0 629 // BlockOffsetArrayContigSpace
duke@0 630 //////////////////////////////////////////////////////////////////////
duke@0 631
duke@0 632 HeapWord* BlockOffsetArrayContigSpace::block_start_unsafe(const void* addr) const {
duke@0 633 assert(_array->offset_array(0) == 0, "objects can't cross covered areas");
duke@0 634
duke@0 635 // Otherwise, find the block start using the table.
duke@0 636 assert(_bottom <= addr && addr < _end,
duke@0 637 "addr must be covered by this Array");
duke@0 638 size_t index = _array->index_for(addr);
duke@0 639 // We must make sure that the offset table entry we use is valid. If
duke@0 640 // "addr" is past the end, start at the last known one and go forward.
duke@0 641 index = MIN2(index, _next_offset_index-1);
duke@0 642 HeapWord* q = _array->address_for_index(index);
duke@0 643
duke@0 644 uint offset = _array->offset_array(index); // Extend u_char to uint.
duke@0 645 while (offset > N_words) {
duke@0 646 // The excess of the offset from N_words indicates a power of Base
duke@0 647 // to go back by.
duke@0 648 size_t n_cards_back = entry_to_cards_back(offset);
duke@0 649 q -= (N_words * n_cards_back);
duke@0 650 assert(q >= _sp->bottom(), "Went below bottom!");
duke@0 651 index -= n_cards_back;
duke@0 652 offset = _array->offset_array(index);
duke@0 653 }
duke@0 654 while (offset == N_words) {
duke@0 655 assert(q >= _sp->bottom(), "Went below bottom!");
duke@0 656 q -= N_words;
duke@0 657 index--;
duke@0 658 offset = _array->offset_array(index);
duke@0 659 }
duke@0 660 assert(offset < N_words, "offset too large");
duke@0 661 q -= offset;
duke@0 662 HeapWord* n = q;
duke@0 663
duke@0 664 while (n <= addr) {
duke@0 665 debug_only(HeapWord* last = q); // for debugging
duke@0 666 q = n;
duke@0 667 n += _sp->block_size(n);
duke@0 668 }
duke@0 669 assert(q <= addr, "wrong order for current and arg");
duke@0 670 assert(addr <= n, "wrong order for arg and next");
duke@0 671 return q;
duke@0 672 }
duke@0 673
duke@0 674 //
duke@0 675 // _next_offset_threshold
duke@0 676 // | _next_offset_index
duke@0 677 // v v
duke@0 678 // +-------+-------+-------+-------+-------+
duke@0 679 // | i-1 | i | i+1 | i+2 | i+3 |
duke@0 680 // +-------+-------+-------+-------+-------+
duke@0 681 // ( ^ ]
duke@0 682 // block-start
duke@0 683 //
duke@0 684
duke@0 685 void BlockOffsetArrayContigSpace::alloc_block_work(HeapWord* blk_start,
duke@0 686 HeapWord* blk_end) {
duke@0 687 assert(blk_start != NULL && blk_end > blk_start,
duke@0 688 "phantom block");
duke@0 689 assert(blk_end > _next_offset_threshold,
duke@0 690 "should be past threshold");
duke@0 691 assert(blk_start <= _next_offset_threshold,
duke@0 692 "blk_start should be at or before threshold")
duke@0 693 assert(pointer_delta(_next_offset_threshold, blk_start) <= N_words,
duke@0 694 "offset should be <= BlockOffsetSharedArray::N");
duke@0 695 assert(Universe::heap()->is_in_reserved(blk_start),
duke@0 696 "reference must be into the heap");
duke@0 697 assert(Universe::heap()->is_in_reserved(blk_end-1),
duke@0 698 "limit must be within the heap");
duke@0 699 assert(_next_offset_threshold ==
duke@0 700 _array->_reserved.start() + _next_offset_index*N_words,
duke@0 701 "index must agree with threshold");
duke@0 702
duke@0 703 debug_only(size_t orig_next_offset_index = _next_offset_index;)
duke@0 704
duke@0 705 // Mark the card that holds the offset into the block. Note
duke@0 706 // that _next_offset_index and _next_offset_threshold are not
duke@0 707 // updated until the end of this method.
duke@0 708 _array->set_offset_array(_next_offset_index,
duke@0 709 _next_offset_threshold,
duke@0 710 blk_start);
duke@0 711
duke@0 712 // We need to now mark the subsequent cards that this blk spans.
duke@0 713
duke@0 714 // Index of card on which blk ends.
duke@0 715 size_t end_index = _array->index_for(blk_end - 1);
duke@0 716
duke@0 717 // Are there more cards left to be updated?
duke@0 718 if (_next_offset_index + 1 <= end_index) {
duke@0 719 HeapWord* rem_st = _array->address_for_index(_next_offset_index + 1);
duke@0 720 // Calculate rem_end this way because end_index
duke@0 721 // may be the last valid index in the covered region.
duke@0 722 HeapWord* rem_end = _array->address_for_index(end_index) + N_words;
duke@0 723 set_remainder_to_point_to_start(rem_st, rem_end);
duke@0 724 }
duke@0 725
duke@0 726 // _next_offset_index and _next_offset_threshold updated here.
duke@0 727 _next_offset_index = end_index + 1;
duke@0 728 // Calculate _next_offset_threshold this way because end_index
duke@0 729 // may be the last valid index in the covered region.
duke@0 730 _next_offset_threshold = _array->address_for_index(end_index) +
duke@0 731 N_words;
duke@0 732 assert(_next_offset_threshold >= blk_end, "Incorrent offset threshold");
duke@0 733
duke@0 734 #ifdef ASSERT
duke@0 735 // The offset can be 0 if the block starts on a boundary. That
duke@0 736 // is checked by an assertion above.
duke@0 737 size_t start_index = _array->index_for(blk_start);
duke@0 738 HeapWord* boundary = _array->address_for_index(start_index);
duke@0 739 assert((_array->offset_array(orig_next_offset_index) == 0 &&
duke@0 740 blk_start == boundary) ||
duke@0 741 (_array->offset_array(orig_next_offset_index) > 0 &&
duke@0 742 _array->offset_array(orig_next_offset_index) <= N_words),
duke@0 743 "offset array should have been set");
duke@0 744 for (size_t j = orig_next_offset_index + 1; j <= end_index; j++) {
duke@0 745 assert(_array->offset_array(j) > 0 &&
duke@0 746 _array->offset_array(j) <= (u_char) (N_words+N_powers-1),
duke@0 747 "offset array should have been set");
duke@0 748 }
duke@0 749 #endif
duke@0 750 }
duke@0 751
duke@0 752 HeapWord* BlockOffsetArrayContigSpace::initialize_threshold() {
duke@0 753 assert(!Universe::heap()->is_in_reserved(_array->_offset_array),
duke@0 754 "just checking");
duke@0 755 _next_offset_index = _array->index_for(_bottom);
duke@0 756 _next_offset_index++;
duke@0 757 _next_offset_threshold =
duke@0 758 _array->address_for_index(_next_offset_index);
duke@0 759 return _next_offset_threshold;
duke@0 760 }
duke@0 761
duke@0 762 void BlockOffsetArrayContigSpace::zero_bottom_entry() {
duke@0 763 assert(!Universe::heap()->is_in_reserved(_array->_offset_array),
duke@0 764 "just checking");
duke@0 765 size_t bottom_index = _array->index_for(_bottom);
duke@0 766 _array->set_offset_array(bottom_index, 0);
duke@0 767 }
duke@0 768
duke@0 769
duke@0 770 void BlockOffsetArrayContigSpace::serialize(SerializeOopClosure* soc) {
duke@0 771 if (soc->reading()) {
duke@0 772 // Null these values so that the serializer won't object to updating them.
duke@0 773 _next_offset_threshold = NULL;
duke@0 774 _next_offset_index = 0;
duke@0 775 }
duke@0 776 soc->do_ptr(&_next_offset_threshold);
duke@0 777 soc->do_size_t(&_next_offset_index);
duke@0 778 }
duke@0 779
duke@0 780 size_t BlockOffsetArrayContigSpace::last_active_index() const {
duke@0 781 size_t result = _next_offset_index - 1;
duke@0 782 return result >= 0 ? result : 0;
duke@0 783 }