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