Sat, 16 Oct 2010 17:12:19 -0400
6991377: G1: race between concurrent refinement and humongous object allocation
Summary: There is a race between the concurrent refinement threads and the humongous object allocation that can cause the concurrent refinement threads to corrupt the part of the BOT that it is being initialized by the humongous object allocation operation. The solution is to do the humongous object allocation in careful steps to ensure that the concurrent refinement threads always have a consistent view over the BOT, region contents, and top. The fix includes some very minor tidying up in sparsePRT.
Reviewed-by: jcoomes, johnc, ysr
1 /*
2 * Copyright (c) 2001, 2007, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
25 // The CollectedHeap type requires subtypes to implement a method
26 // "block_start". For some subtypes, notably generational
27 // systems using card-table-based write barriers, the efficiency of this
28 // operation may be important. Implementations of the "BlockOffsetArray"
29 // class may be useful in providing such efficient implementations.
30 //
31 // While generally mirroring the structure of the BOT for GenCollectedHeap,
32 // the following types are tailored more towards G1's uses; these should,
33 // however, be merged back into a common BOT to avoid code duplication
34 // and reduce maintenance overhead.
35 //
36 // G1BlockOffsetTable (abstract)
37 // -- G1BlockOffsetArray (uses G1BlockOffsetSharedArray)
38 // -- G1BlockOffsetArrayContigSpace
39 //
40 // A main impediment to the consolidation of this code might be the
41 // effect of making some of the block_start*() calls non-const as
42 // below. Whether that might adversely affect performance optimizations
43 // that compilers might normally perform in the case of non-G1
44 // collectors needs to be carefully investigated prior to any such
45 // consolidation.
47 // Forward declarations
48 class ContiguousSpace;
49 class G1BlockOffsetSharedArray;
51 class G1BlockOffsetTable VALUE_OBJ_CLASS_SPEC {
52 friend class VMStructs;
53 protected:
54 // These members describe the region covered by the table.
56 // The space this table is covering.
57 HeapWord* _bottom; // == reserved.start
58 HeapWord* _end; // End of currently allocated region.
60 public:
61 // Initialize the table to cover the given space.
62 // The contents of the initial table are undefined.
63 G1BlockOffsetTable(HeapWord* bottom, HeapWord* end) :
64 _bottom(bottom), _end(end)
65 {
66 assert(_bottom <= _end, "arguments out of order");
67 }
69 // Note that the committed size of the covered space may have changed,
70 // so the table size might also wish to change.
71 virtual void resize(size_t new_word_size) = 0;
73 virtual void set_bottom(HeapWord* new_bottom) {
74 assert(new_bottom <= _end, "new_bottom > _end");
75 _bottom = new_bottom;
76 resize(pointer_delta(_end, _bottom));
77 }
79 // Requires "addr" to be contained by a block, and returns the address of
80 // the start of that block. (May have side effects, namely updating of
81 // shared array entries that "point" too far backwards. This can occur,
82 // for example, when LAB allocation is used in a space covered by the
83 // table.)
84 virtual HeapWord* block_start_unsafe(const void* addr) = 0;
85 // Same as above, but does not have any of the possible side effects
86 // discussed above.
87 virtual HeapWord* block_start_unsafe_const(const void* addr) const = 0;
89 // Returns the address of the start of the block containing "addr", or
90 // else "null" if it is covered by no block. (May have side effects,
91 // namely updating of shared array entries that "point" too far
92 // backwards. This can occur, for example, when lab allocation is used
93 // in a space covered by the table.)
94 inline HeapWord* block_start(const void* addr);
95 // Same as above, but does not have any of the possible side effects
96 // discussed above.
97 inline HeapWord* block_start_const(const void* addr) const;
98 };
100 // This implementation of "G1BlockOffsetTable" divides the covered region
101 // into "N"-word subregions (where "N" = 2^"LogN". An array with an entry
102 // for each such subregion indicates how far back one must go to find the
103 // start of the chunk that includes the first word of the subregion.
104 //
105 // Each BlockOffsetArray is owned by a Space. However, the actual array
106 // may be shared by several BlockOffsetArrays; this is useful
107 // when a single resizable area (such as a generation) is divided up into
108 // several spaces in which contiguous allocation takes place,
109 // such as, for example, in G1 or in the train generation.)
111 // Here is the shared array type.
113 class G1BlockOffsetSharedArray: public CHeapObj {
114 friend class G1BlockOffsetArray;
115 friend class G1BlockOffsetArrayContigSpace;
116 friend class VMStructs;
118 private:
119 // The reserved region covered by the shared array.
120 MemRegion _reserved;
122 // End of the current committed region.
123 HeapWord* _end;
125 // Array for keeping offsets for retrieving object start fast given an
126 // address.
127 VirtualSpace _vs;
128 u_char* _offset_array; // byte array keeping backwards offsets
130 // Bounds checking accessors:
131 // For performance these have to devolve to array accesses in product builds.
132 u_char offset_array(size_t index) const {
133 assert(index < _vs.committed_size(), "index out of range");
134 return _offset_array[index];
135 }
137 void set_offset_array(size_t index, u_char offset) {
138 assert(index < _vs.committed_size(), "index out of range");
139 assert(offset <= N_words, "offset too large");
140 _offset_array[index] = offset;
141 }
143 void set_offset_array(size_t index, HeapWord* high, HeapWord* low) {
144 assert(index < _vs.committed_size(), "index out of range");
145 assert(high >= low, "addresses out of order");
146 assert(pointer_delta(high, low) <= N_words, "offset too large");
147 _offset_array[index] = (u_char) pointer_delta(high, low);
148 }
150 void set_offset_array(HeapWord* left, HeapWord* right, u_char offset) {
151 assert(index_for(right - 1) < _vs.committed_size(),
152 "right address out of range");
153 assert(left < right, "Heap addresses out of order");
154 size_t num_cards = pointer_delta(right, left) >> LogN_words;
155 memset(&_offset_array[index_for(left)], offset, num_cards);
156 }
158 void set_offset_array(size_t left, size_t right, u_char offset) {
159 assert(right < _vs.committed_size(), "right address out of range");
160 assert(left <= right, "indexes out of order");
161 size_t num_cards = right - left + 1;
162 memset(&_offset_array[left], offset, num_cards);
163 }
165 void check_offset_array(size_t index, HeapWord* high, HeapWord* low) const {
166 assert(index < _vs.committed_size(), "index out of range");
167 assert(high >= low, "addresses out of order");
168 assert(pointer_delta(high, low) <= N_words, "offset too large");
169 assert(_offset_array[index] == pointer_delta(high, low),
170 "Wrong offset");
171 }
173 bool is_card_boundary(HeapWord* p) const;
175 // Return the number of slots needed for an offset array
176 // that covers mem_region_words words.
177 // We always add an extra slot because if an object
178 // ends on a card boundary we put a 0 in the next
179 // offset array slot, so we want that slot always
180 // to be reserved.
182 size_t compute_size(size_t mem_region_words) {
183 size_t number_of_slots = (mem_region_words / N_words) + 1;
184 return ReservedSpace::page_align_size_up(number_of_slots);
185 }
187 public:
188 enum SomePublicConstants {
189 LogN = 9,
190 LogN_words = LogN - LogHeapWordSize,
191 N_bytes = 1 << LogN,
192 N_words = 1 << LogN_words
193 };
195 // Initialize the table to cover from "base" to (at least)
196 // "base + init_word_size". In the future, the table may be expanded
197 // (see "resize" below) up to the size of "_reserved" (which must be at
198 // least "init_word_size".) The contents of the initial table are
199 // undefined; it is the responsibility of the constituent
200 // G1BlockOffsetTable(s) to initialize cards.
201 G1BlockOffsetSharedArray(MemRegion reserved, size_t init_word_size);
203 // Notes a change in the committed size of the region covered by the
204 // table. The "new_word_size" may not be larger than the size of the
205 // reserved region this table covers.
206 void resize(size_t new_word_size);
208 void set_bottom(HeapWord* new_bottom);
210 // Updates all the BlockOffsetArray's sharing this shared array to
211 // reflect the current "top"'s of their spaces.
212 void update_offset_arrays();
214 // Return the appropriate index into "_offset_array" for "p".
215 inline size_t index_for(const void* p) const;
217 // Return the address indicating the start of the region corresponding to
218 // "index" in "_offset_array".
219 inline HeapWord* address_for_index(size_t index) const;
220 };
222 // And here is the G1BlockOffsetTable subtype that uses the array.
224 class G1BlockOffsetArray: public G1BlockOffsetTable {
225 friend class G1BlockOffsetSharedArray;
226 friend class G1BlockOffsetArrayContigSpace;
227 friend class VMStructs;
228 private:
229 enum SomePrivateConstants {
230 N_words = G1BlockOffsetSharedArray::N_words,
231 LogN = G1BlockOffsetSharedArray::LogN
232 };
234 // The following enums are used by do_block_helper
235 enum Action {
236 Action_single, // BOT records a single block (see single_block())
237 Action_mark, // BOT marks the start of a block (see mark_block())
238 Action_check // Check that BOT records block correctly
239 // (see verify_single_block()).
240 };
242 // This is the array, which can be shared by several BlockOffsetArray's
243 // servicing different
244 G1BlockOffsetSharedArray* _array;
246 // The space that owns this subregion.
247 Space* _sp;
249 // If "_sp" is a contiguous space, the field below is the view of "_sp"
250 // as a contiguous space, else NULL.
251 ContiguousSpace* _csp;
253 // If true, array entries are initialized to 0; otherwise, they are
254 // initialized to point backwards to the beginning of the covered region.
255 bool _init_to_zero;
257 // The portion [_unallocated_block, _sp.end()) of the space that
258 // is a single block known not to contain any objects.
259 // NOTE: See BlockOffsetArrayUseUnallocatedBlock flag.
260 HeapWord* _unallocated_block;
262 // Sets the entries
263 // corresponding to the cards starting at "start" and ending at "end"
264 // to point back to the card before "start": the interval [start, end)
265 // is right-open.
266 void set_remainder_to_point_to_start(HeapWord* start, HeapWord* end);
267 // Same as above, except that the args here are a card _index_ interval
268 // that is closed: [start_index, end_index]
269 void set_remainder_to_point_to_start_incl(size_t start, size_t end);
271 // A helper function for BOT adjustment/verification work
272 void do_block_internal(HeapWord* blk_start, HeapWord* blk_end, Action action);
274 protected:
276 ContiguousSpace* csp() const { return _csp; }
278 // Returns the address of a block whose start is at most "addr".
279 // If "has_max_index" is true, "assumes "max_index" is the last valid one
280 // in the array.
281 inline HeapWord* block_at_or_preceding(const void* addr,
282 bool has_max_index,
283 size_t max_index) const;
285 // "q" is a block boundary that is <= "addr"; "n" is the address of the
286 // next block (or the end of the space.) Return the address of the
287 // beginning of the block that contains "addr". Does so without side
288 // effects (see, e.g., spec of block_start.)
289 inline HeapWord*
290 forward_to_block_containing_addr_const(HeapWord* q, HeapWord* n,
291 const void* addr) const;
293 // "q" is a block boundary that is <= "addr"; return the address of the
294 // beginning of the block that contains "addr". May have side effects
295 // on "this", by updating imprecise entries.
296 inline HeapWord* forward_to_block_containing_addr(HeapWord* q,
297 const void* addr);
299 // "q" is a block boundary that is <= "addr"; "n" is the address of the
300 // next block (or the end of the space.) Return the address of the
301 // beginning of the block that contains "addr". May have side effects
302 // on "this", by updating imprecise entries.
303 HeapWord* forward_to_block_containing_addr_slow(HeapWord* q,
304 HeapWord* n,
305 const void* addr);
307 // Requires that "*threshold_" be the first array entry boundary at or
308 // above "blk_start", and that "*index_" be the corresponding array
309 // index. If the block starts at or crosses "*threshold_", records
310 // "blk_start" as the appropriate block start for the array index
311 // starting at "*threshold_", and for any other indices crossed by the
312 // block. Updates "*threshold_" and "*index_" to correspond to the first
313 // index after the block end.
314 void alloc_block_work2(HeapWord** threshold_, size_t* index_,
315 HeapWord* blk_start, HeapWord* blk_end);
317 public:
318 // The space may not have it's bottom and top set yet, which is why the
319 // region is passed as a parameter. If "init_to_zero" is true, the
320 // elements of the array are initialized to zero. Otherwise, they are
321 // initialized to point backwards to the beginning.
322 G1BlockOffsetArray(G1BlockOffsetSharedArray* array, MemRegion mr,
323 bool init_to_zero);
325 // Note: this ought to be part of the constructor, but that would require
326 // "this" to be passed as a parameter to a member constructor for
327 // the containing concrete subtype of Space.
328 // This would be legal C++, but MS VC++ doesn't allow it.
329 void set_space(Space* sp);
331 // Resets the covered region to the given "mr".
332 void set_region(MemRegion mr);
334 // Resets the covered region to one with the same _bottom as before but
335 // the "new_word_size".
336 void resize(size_t new_word_size);
338 // These must be guaranteed to work properly (i.e., do nothing)
339 // when "blk_start" ("blk" for second version) is "NULL".
340 virtual void alloc_block(HeapWord* blk_start, HeapWord* blk_end);
341 virtual void alloc_block(HeapWord* blk, size_t size) {
342 alloc_block(blk, blk + size);
343 }
345 // The following methods are useful and optimized for a
346 // general, non-contiguous space.
348 // The given arguments are required to be the starts of adjacent ("blk1"
349 // before "blk2") well-formed blocks covered by "this". After this call,
350 // they should be considered to form one block.
351 virtual void join_blocks(HeapWord* blk1, HeapWord* blk2);
353 // Given a block [blk_start, blk_start + full_blk_size), and
354 // a left_blk_size < full_blk_size, adjust the BOT to show two
355 // blocks [blk_start, blk_start + left_blk_size) and
356 // [blk_start + left_blk_size, blk_start + full_blk_size).
357 // It is assumed (and verified in the non-product VM) that the
358 // BOT was correct for the original block.
359 void split_block(HeapWord* blk_start, size_t full_blk_size,
360 size_t left_blk_size);
362 // Adjust the BOT to show that it has a single block in the
363 // range [blk_start, blk_start + size). All necessary BOT
364 // cards are adjusted, but _unallocated_block isn't.
365 void single_block(HeapWord* blk_start, HeapWord* blk_end);
366 void single_block(HeapWord* blk, size_t size) {
367 single_block(blk, blk + size);
368 }
370 // Adjust BOT to show that it has a block in the range
371 // [blk_start, blk_start + size). Only the first card
372 // of BOT is touched. It is assumed (and verified in the
373 // non-product VM) that the remaining cards of the block
374 // are correct.
375 void mark_block(HeapWord* blk_start, HeapWord* blk_end);
376 void mark_block(HeapWord* blk, size_t size) {
377 mark_block(blk, blk + size);
378 }
380 // Adjust _unallocated_block to indicate that a particular
381 // block has been newly allocated or freed. It is assumed (and
382 // verified in the non-product VM) that the BOT is correct for
383 // the given block.
384 inline void allocated(HeapWord* blk_start, HeapWord* blk_end) {
385 // Verify that the BOT shows [blk, blk + blk_size) to be one block.
386 verify_single_block(blk_start, blk_end);
387 if (BlockOffsetArrayUseUnallocatedBlock) {
388 _unallocated_block = MAX2(_unallocated_block, blk_end);
389 }
390 }
392 inline void allocated(HeapWord* blk, size_t size) {
393 allocated(blk, blk + size);
394 }
396 inline void freed(HeapWord* blk_start, HeapWord* blk_end);
398 inline void freed(HeapWord* blk, size_t size);
400 virtual HeapWord* block_start_unsafe(const void* addr);
401 virtual HeapWord* block_start_unsafe_const(const void* addr) const;
403 // Requires "addr" to be the start of a card and returns the
404 // start of the block that contains the given address.
405 HeapWord* block_start_careful(const void* addr) const;
407 // If true, initialize array slots with no allocated blocks to zero.
408 // Otherwise, make them point back to the front.
409 bool init_to_zero() { return _init_to_zero; }
411 // Verification & debugging - ensure that the offset table reflects the fact
412 // that the block [blk_start, blk_end) or [blk, blk + size) is a
413 // single block of storage. NOTE: can;t const this because of
414 // call to non-const do_block_internal() below.
415 inline void verify_single_block(HeapWord* blk_start, HeapWord* blk_end) {
416 if (VerifyBlockOffsetArray) {
417 do_block_internal(blk_start, blk_end, Action_check);
418 }
419 }
421 inline void verify_single_block(HeapWord* blk, size_t size) {
422 verify_single_block(blk, blk + size);
423 }
425 // Verify that the given block is before _unallocated_block
426 inline void verify_not_unallocated(HeapWord* blk_start,
427 HeapWord* blk_end) const {
428 if (BlockOffsetArrayUseUnallocatedBlock) {
429 assert(blk_start < blk_end, "Block inconsistency?");
430 assert(blk_end <= _unallocated_block, "_unallocated_block problem");
431 }
432 }
434 inline void verify_not_unallocated(HeapWord* blk, size_t size) const {
435 verify_not_unallocated(blk, blk + size);
436 }
438 void check_all_cards(size_t left_card, size_t right_card) const;
440 virtual void set_for_starts_humongous(HeapWord* new_end);
441 };
443 // A subtype of BlockOffsetArray that takes advantage of the fact
444 // that its underlying space is a ContiguousSpace, so that its "active"
445 // region can be more efficiently tracked (than for a non-contiguous space).
446 class G1BlockOffsetArrayContigSpace: public G1BlockOffsetArray {
447 friend class VMStructs;
449 // allocation boundary at which offset array must be updated
450 HeapWord* _next_offset_threshold;
451 size_t _next_offset_index; // index corresponding to that boundary
453 // Work function to be called when allocation start crosses the next
454 // threshold in the contig space.
455 void alloc_block_work1(HeapWord* blk_start, HeapWord* blk_end) {
456 alloc_block_work2(&_next_offset_threshold, &_next_offset_index,
457 blk_start, blk_end);
458 }
461 public:
462 G1BlockOffsetArrayContigSpace(G1BlockOffsetSharedArray* array, MemRegion mr);
464 // Initialize the threshold to reflect the first boundary after the
465 // bottom of the covered region.
466 HeapWord* initialize_threshold();
468 // Zero out the entry for _bottom (offset will be zero).
469 void zero_bottom_entry();
471 // Return the next threshold, the point at which the table should be
472 // updated.
473 HeapWord* threshold() const { return _next_offset_threshold; }
475 // These must be guaranteed to work properly (i.e., do nothing)
476 // when "blk_start" ("blk" for second version) is "NULL". In this
477 // implementation, that's true because NULL is represented as 0, and thus
478 // never exceeds the "_next_offset_threshold".
479 void alloc_block(HeapWord* blk_start, HeapWord* blk_end) {
480 if (blk_end > _next_offset_threshold)
481 alloc_block_work1(blk_start, blk_end);
482 }
483 void alloc_block(HeapWord* blk, size_t size) {
484 alloc_block(blk, blk+size);
485 }
487 HeapWord* block_start_unsafe(const void* addr);
488 HeapWord* block_start_unsafe_const(const void* addr) const;
490 virtual void set_for_starts_humongous(HeapWord* new_end);
491 };