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