1 /* |
1 /* |
2 * Copyright (c) 2001, 2015, Oracle and/or its affiliates. All rights reserved. |
2 * Copyright (c) 2001, 2016, Oracle and/or its affiliates. All rights reserved. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. |
4 * |
4 * |
5 * This code is free software; you can redistribute it and/or modify it |
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 |
6 * under the terms of the GNU General Public License version 2 only, as |
7 * published by the Free Software Foundation. |
7 * published by the Free Software Foundation. |
51 } |
51 } |
52 |
52 |
53 bool G1BlockOffsetTable::is_card_boundary(HeapWord* p) const { |
53 bool G1BlockOffsetTable::is_card_boundary(HeapWord* p) const { |
54 assert(p >= _reserved.start(), "just checking"); |
54 assert(p >= _reserved.start(), "just checking"); |
55 size_t delta = pointer_delta(p, _reserved.start()); |
55 size_t delta = pointer_delta(p, _reserved.start()); |
56 return (delta & right_n_bits(LogN_words)) == (size_t)NoBits; |
56 return (delta & right_n_bits((int)BOTConstants::LogN_words)) == (size_t)NoBits; |
57 } |
57 } |
58 |
58 |
59 #ifdef ASSERT |
59 #ifdef ASSERT |
60 void G1BlockOffsetTable::check_index(size_t index, const char* msg) const { |
60 void G1BlockOffsetTable::check_index(size_t index, const char* msg) const { |
61 assert((index) < (_reserved.word_size() >> LogN_words), |
61 assert((index) < (_reserved.word_size() >> BOTConstants::LogN_words), |
62 "%s - index: " SIZE_FORMAT ", _vs.committed_size: " SIZE_FORMAT, |
62 "%s - index: " SIZE_FORMAT ", _vs.committed_size: " SIZE_FORMAT, |
63 msg, (index), (_reserved.word_size() >> LogN_words)); |
63 msg, (index), (_reserved.word_size() >> BOTConstants::LogN_words)); |
64 assert(G1CollectedHeap::heap()->is_in_exact(address_for_index_raw(index)), |
64 assert(G1CollectedHeap::heap()->is_in_exact(address_for_index_raw(index)), |
65 "Index " SIZE_FORMAT " corresponding to " PTR_FORMAT |
65 "Index " SIZE_FORMAT " corresponding to " PTR_FORMAT |
66 " (%u) is not in committed area.", |
66 " (%u) is not in committed area.", |
67 (index), |
67 (index), |
68 p2i(address_for_index_raw(index)), |
68 p2i(address_for_index_raw(index)), |
126 // value of the new entry |
126 // value of the new entry |
127 // |
127 // |
128 size_t start_card = _bot->index_for(start); |
128 size_t start_card = _bot->index_for(start); |
129 size_t end_card = _bot->index_for(end-1); |
129 size_t end_card = _bot->index_for(end-1); |
130 assert(start ==_bot->address_for_index(start_card), "Precondition"); |
130 assert(start ==_bot->address_for_index(start_card), "Precondition"); |
131 assert(end ==_bot->address_for_index(end_card)+N_words, "Precondition"); |
131 assert(end ==_bot->address_for_index(end_card)+BOTConstants::N_words, "Precondition"); |
132 set_remainder_to_point_to_start_incl(start_card, end_card); // closed interval |
132 set_remainder_to_point_to_start_incl(start_card, end_card); // closed interval |
133 } |
133 } |
134 |
134 |
135 // Unlike the normal convention in this code, the argument here denotes |
135 // Unlike the normal convention in this code, the argument here denotes |
136 // a closed, inclusive interval: [start_card, end_card], cf set_remainder_to_point_to_start() |
136 // a closed, inclusive interval: [start_card, end_card], cf set_remainder_to_point_to_start() |
138 void G1BlockOffsetTablePart::set_remainder_to_point_to_start_incl(size_t start_card, size_t end_card) { |
138 void G1BlockOffsetTablePart::set_remainder_to_point_to_start_incl(size_t start_card, size_t end_card) { |
139 if (start_card > end_card) { |
139 if (start_card > end_card) { |
140 return; |
140 return; |
141 } |
141 } |
142 assert(start_card > _bot->index_for(_space->bottom()), "Cannot be first card"); |
142 assert(start_card > _bot->index_for(_space->bottom()), "Cannot be first card"); |
143 assert(_bot->offset_array(start_card-1) <= N_words, |
143 assert(_bot->offset_array(start_card-1) <= BOTConstants::N_words, |
144 "Offset card has an unexpected value"); |
144 "Offset card has an unexpected value"); |
145 size_t start_card_for_region = start_card; |
145 size_t start_card_for_region = start_card; |
146 u_char offset = max_jubyte; |
146 u_char offset = max_jubyte; |
147 for (int i = 0; i < BlockOffsetArray::N_powers; i++) { |
147 for (uint i = 0; i < BOTConstants::N_powers; i++) { |
148 // -1 so that the the card with the actual offset is counted. Another -1 |
148 // -1 so that the the card with the actual offset is counted. Another -1 |
149 // so that the reach ends in this region and not at the start |
149 // so that the reach ends in this region and not at the start |
150 // of the next. |
150 // of the next. |
151 size_t reach = start_card - 1 + (BlockOffsetArray::power_to_cards_back(i+1) - 1); |
151 size_t reach = start_card - 1 + (BOTConstants::power_to_cards_back(i+1) - 1); |
152 offset = N_words + i; |
152 offset = BOTConstants::N_words + i; |
153 if (reach >= end_card) { |
153 if (reach >= end_card) { |
154 _bot->set_offset_array(start_card_for_region, end_card, offset); |
154 _bot->set_offset_array(start_card_for_region, end_card, offset); |
155 start_card_for_region = reach + 1; |
155 start_card_for_region = reach + 1; |
156 break; |
156 break; |
157 } |
157 } |
168 void G1BlockOffsetTablePart::check_all_cards(size_t start_card, size_t end_card) const { |
168 void G1BlockOffsetTablePart::check_all_cards(size_t start_card, size_t end_card) const { |
169 |
169 |
170 if (end_card < start_card) { |
170 if (end_card < start_card) { |
171 return; |
171 return; |
172 } |
172 } |
173 guarantee(_bot->offset_array(start_card) == N_words, "Wrong value in second card"); |
173 guarantee(_bot->offset_array(start_card) == BOTConstants::N_words, "Wrong value in second card"); |
174 for (size_t c = start_card + 1; c <= end_card; c++ /* yeah! */) { |
174 for (size_t c = start_card + 1; c <= end_card; c++ /* yeah! */) { |
175 u_char entry = _bot->offset_array(c); |
175 u_char entry = _bot->offset_array(c); |
176 if (c - start_card > BlockOffsetArray::power_to_cards_back(1)) { |
176 if (c - start_card > BOTConstants::power_to_cards_back(1)) { |
177 guarantee(entry > N_words, |
177 guarantee(entry > BOTConstants::N_words, |
178 "Should be in logarithmic region - " |
178 "Should be in logarithmic region - " |
179 "entry: %u, " |
179 "entry: %u, " |
180 "_array->offset_array(c): %u, " |
180 "_array->offset_array(c): %u, " |
181 "N_words: %u", |
181 "N_words: %u", |
182 (uint)entry, (uint)_bot->offset_array(c), (uint)N_words); |
182 (uint)entry, (uint)_bot->offset_array(c), BOTConstants::N_words); |
183 } |
183 } |
184 size_t backskip = BlockOffsetArray::entry_to_cards_back(entry); |
184 size_t backskip = BOTConstants::entry_to_cards_back(entry); |
185 size_t landing_card = c - backskip; |
185 size_t landing_card = c - backskip; |
186 guarantee(landing_card >= (start_card - 1), "Inv"); |
186 guarantee(landing_card >= (start_card - 1), "Inv"); |
187 if (landing_card >= start_card) { |
187 if (landing_card >= start_card) { |
188 guarantee(_bot->offset_array(landing_card) <= entry, |
188 guarantee(_bot->offset_array(landing_card) <= entry, |
189 "Monotonicity - landing_card offset: %u, " |
189 "Monotonicity - landing_card offset: %u, " |
190 "entry: %u", |
190 "entry: %u", |
191 (uint)_bot->offset_array(landing_card), (uint)entry); |
191 (uint)_bot->offset_array(landing_card), (uint)entry); |
192 } else { |
192 } else { |
193 guarantee(landing_card == start_card - 1, "Tautology"); |
193 guarantee(landing_card == start_card - 1, "Tautology"); |
194 // Note that N_words is the maximum offset value |
194 // Note that N_words is the maximum offset value |
195 guarantee(_bot->offset_array(landing_card) <= N_words, |
195 guarantee(_bot->offset_array(landing_card) <= BOTConstants::N_words, |
196 "landing card offset: %u, " |
196 "landing card offset: %u, " |
197 "N_words: %u", |
197 "N_words: %u", |
198 (uint)_bot->offset_array(landing_card), (uint)N_words); |
198 (uint)_bot->offset_array(landing_card), (uint)BOTConstants::N_words); |
199 } |
199 } |
200 } |
200 } |
201 } |
201 } |
202 |
202 |
203 HeapWord* G1BlockOffsetTablePart::forward_to_block_containing_addr_slow(HeapWord* q, |
203 HeapWord* G1BlockOffsetTablePart::forward_to_block_containing_addr_slow(HeapWord* q, |
215 size_t n_index = _bot->index_for(n); |
215 size_t n_index = _bot->index_for(n); |
216 size_t next_index = _bot->index_for(n) + !_bot->is_card_boundary(n); |
216 size_t next_index = _bot->index_for(n) + !_bot->is_card_boundary(n); |
217 // Calculate a consistent next boundary. If "n" is not at the boundary |
217 // Calculate a consistent next boundary. If "n" is not at the boundary |
218 // already, step to the boundary. |
218 // already, step to the boundary. |
219 HeapWord* next_boundary = _bot->address_for_index(n_index) + |
219 HeapWord* next_boundary = _bot->address_for_index(n_index) + |
220 (n_index == next_index ? 0 : N_words); |
220 (n_index == next_index ? 0 : BOTConstants::N_words); |
221 assert(next_boundary <= _bot->_reserved.end(), |
221 assert(next_boundary <= _bot->_reserved.end(), |
222 "next_boundary is beyond the end of the covered region " |
222 "next_boundary is beyond the end of the covered region " |
223 " next_boundary " PTR_FORMAT " _array->_end " PTR_FORMAT, |
223 " next_boundary " PTR_FORMAT " _array->_end " PTR_FORMAT, |
224 p2i(next_boundary), p2i(_bot->_reserved.end())); |
224 p2i(next_boundary), p2i(_bot->_reserved.end())); |
225 if (addr >= _space->top()) return _space->top(); |
225 if (addr >= _space->top()) return _space->top(); |
255 |
255 |
256 assert(blk_start != NULL && blk_end > blk_start, |
256 assert(blk_start != NULL && blk_end > blk_start, |
257 "phantom block"); |
257 "phantom block"); |
258 assert(blk_end > threshold, "should be past threshold"); |
258 assert(blk_end > threshold, "should be past threshold"); |
259 assert(blk_start <= threshold, "blk_start should be at or before threshold"); |
259 assert(blk_start <= threshold, "blk_start should be at or before threshold"); |
260 assert(pointer_delta(threshold, blk_start) <= N_words, |
260 assert(pointer_delta(threshold, blk_start) <= BOTConstants::N_words, |
261 "offset should be <= BlockOffsetSharedArray::N"); |
261 "offset should be <= BlockOffsetSharedArray::N"); |
262 assert(G1CollectedHeap::heap()->is_in_reserved(blk_start), |
262 assert(G1CollectedHeap::heap()->is_in_reserved(blk_start), |
263 "reference must be into the heap"); |
263 "reference must be into the heap"); |
264 assert(G1CollectedHeap::heap()->is_in_reserved(blk_end-1), |
264 assert(G1CollectedHeap::heap()->is_in_reserved(blk_end-1), |
265 "limit must be within the heap"); |
265 "limit must be within the heap"); |
266 assert(threshold == _bot->_reserved.start() + index*N_words, |
266 assert(threshold == _bot->_reserved.start() + index*BOTConstants::N_words, |
267 "index must agree with threshold"); |
267 "index must agree with threshold"); |
268 |
268 |
269 DEBUG_ONLY(size_t orig_index = index;) |
269 DEBUG_ONLY(size_t orig_index = index;) |
270 |
270 |
271 // Mark the card that holds the offset into the block. Note |
271 // Mark the card that holds the offset into the block. Note |
281 // Are there more cards left to be updated? |
281 // Are there more cards left to be updated? |
282 if (index + 1 <= end_index) { |
282 if (index + 1 <= end_index) { |
283 HeapWord* rem_st = _bot->address_for_index(index + 1); |
283 HeapWord* rem_st = _bot->address_for_index(index + 1); |
284 // Calculate rem_end this way because end_index |
284 // Calculate rem_end this way because end_index |
285 // may be the last valid index in the covered region. |
285 // may be the last valid index in the covered region. |
286 HeapWord* rem_end = _bot->address_for_index(end_index) + N_words; |
286 HeapWord* rem_end = _bot->address_for_index(end_index) + BOTConstants::N_words; |
287 set_remainder_to_point_to_start(rem_st, rem_end); |
287 set_remainder_to_point_to_start(rem_st, rem_end); |
288 } |
288 } |
289 |
289 |
290 index = end_index + 1; |
290 index = end_index + 1; |
291 // Calculate threshold_ this way because end_index |
291 // Calculate threshold_ this way because end_index |
292 // may be the last valid index in the covered region. |
292 // may be the last valid index in the covered region. |
293 threshold = _bot->address_for_index(end_index) + N_words; |
293 threshold = _bot->address_for_index(end_index) + BOTConstants::N_words; |
294 assert(threshold >= blk_end, "Incorrect offset threshold"); |
294 assert(threshold >= blk_end, "Incorrect offset threshold"); |
295 |
295 |
296 // index_ and threshold_ updated here. |
296 // index_ and threshold_ updated here. |
297 *threshold_ = threshold; |
297 *threshold_ = threshold; |
298 *index_ = index; |
298 *index_ = index; |
301 // The offset can be 0 if the block starts on a boundary. That |
301 // The offset can be 0 if the block starts on a boundary. That |
302 // is checked by an assertion above. |
302 // is checked by an assertion above. |
303 size_t start_index = _bot->index_for(blk_start); |
303 size_t start_index = _bot->index_for(blk_start); |
304 HeapWord* boundary = _bot->address_for_index(start_index); |
304 HeapWord* boundary = _bot->address_for_index(start_index); |
305 assert((_bot->offset_array(orig_index) == 0 && blk_start == boundary) || |
305 assert((_bot->offset_array(orig_index) == 0 && blk_start == boundary) || |
306 (_bot->offset_array(orig_index) > 0 && _bot->offset_array(orig_index) <= N_words), |
306 (_bot->offset_array(orig_index) > 0 && _bot->offset_array(orig_index) <= BOTConstants::N_words), |
307 "offset array should have been set - " |
307 "offset array should have been set - " |
308 "orig_index offset: %u, " |
308 "orig_index offset: %u, " |
309 "blk_start: " PTR_FORMAT ", " |
309 "blk_start: " PTR_FORMAT ", " |
310 "boundary: " PTR_FORMAT, |
310 "boundary: " PTR_FORMAT, |
311 (uint)_bot->offset_array(orig_index), |
311 (uint)_bot->offset_array(orig_index), |
312 p2i(blk_start), p2i(boundary)); |
312 p2i(blk_start), p2i(boundary)); |
313 for (size_t j = orig_index + 1; j <= end_index; j++) { |
313 for (size_t j = orig_index + 1; j <= end_index; j++) { |
314 assert(_bot->offset_array(j) > 0 && |
314 assert(_bot->offset_array(j) > 0 && |
315 _bot->offset_array(j) <= |
315 _bot->offset_array(j) <= |
316 (u_char) (N_words+BlockOffsetArray::N_powers-1), |
316 (u_char) (BOTConstants::N_words+BOTConstants::N_powers-1), |
317 "offset array should have been set - " |
317 "offset array should have been set - " |
318 "%u not > 0 OR %u not <= %u", |
318 "%u not > 0 OR %u not <= %u", |
319 (uint) _bot->offset_array(j), |
319 (uint) _bot->offset_array(j), |
320 (uint) _bot->offset_array(j), |
320 (uint) _bot->offset_array(j), |
321 (uint) (N_words+BlockOffsetArray::N_powers-1)); |
321 (uint) (BOTConstants::N_words+BOTConstants::N_powers-1)); |
322 } |
322 } |
323 #endif |
323 #endif |
324 } |
324 } |
325 |
325 |
326 void G1BlockOffsetTablePart::verify() const { |
326 void G1BlockOffsetTablePart::verify() const { |
328 size_t start_card = _bot->index_for(_space->bottom()); |
328 size_t start_card = _bot->index_for(_space->bottom()); |
329 size_t end_card = _bot->index_for(_space->top() - 1); |
329 size_t end_card = _bot->index_for(_space->top() - 1); |
330 |
330 |
331 for (size_t current_card = start_card; current_card < end_card; current_card++) { |
331 for (size_t current_card = start_card; current_card < end_card; current_card++) { |
332 u_char entry = _bot->offset_array(current_card); |
332 u_char entry = _bot->offset_array(current_card); |
333 if (entry < N_words) { |
333 if (entry < BOTConstants::N_words) { |
334 // The entry should point to an object before the current card. Verify that |
334 // The entry should point to an object before the current card. Verify that |
335 // it is possible to walk from that object in to the current card by just |
335 // it is possible to walk from that object in to the current card by just |
336 // iterating over the objects following it. |
336 // iterating over the objects following it. |
337 HeapWord* card_address = _bot->address_for_index(current_card); |
337 HeapWord* card_address = _bot->address_for_index(current_card); |
338 HeapWord* obj_end = card_address - entry; |
338 HeapWord* obj_end = card_address - entry; |
346 } |
346 } |
347 } else { |
347 } else { |
348 // Because we refine the BOT based on which cards are dirty there is not much we can verify here. |
348 // Because we refine the BOT based on which cards are dirty there is not much we can verify here. |
349 // We need to make sure that we are going backwards and that we don't pass the start of the |
349 // We need to make sure that we are going backwards and that we don't pass the start of the |
350 // corresponding heap region. But that is about all we can verify. |
350 // corresponding heap region. But that is about all we can verify. |
351 size_t backskip = BlockOffsetArray::entry_to_cards_back(entry); |
351 size_t backskip = BOTConstants::entry_to_cards_back(entry); |
352 guarantee(backskip >= 1, "Must be going back at least one card."); |
352 guarantee(backskip >= 1, "Must be going back at least one card."); |
353 |
353 |
354 size_t max_backskip = current_card - start_card; |
354 size_t max_backskip = current_card - start_card; |
355 guarantee(backskip <= max_backskip, |
355 guarantee(backskip <= max_backskip, |
356 "Going backwards beyond the start_card. start_card: " SIZE_FORMAT " current_card: " SIZE_FORMAT " backskip: " SIZE_FORMAT, |
356 "Going backwards beyond the start_card. start_card: " SIZE_FORMAT " current_card: " SIZE_FORMAT " backskip: " SIZE_FORMAT, |