Mon, 03 Aug 2009 12:59:30 -0700
6865703: G1: Parallelize hot card cache cleanup
Summary: Have the GC worker threads clear the hot card cache in parallel by having each worker thread claim a chunk of the card cache and process the cards in that chunk. The size of the chunks that each thread will claim is determined at VM initialization from the size of the card cache and the number of worker threads.
Reviewed-by: jmasa, tonyp
1 /*
2 * Copyright 2001-2009 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 */
25 // A "G1CollectedHeap" is an implementation of a java heap for HotSpot.
26 // It uses the "Garbage First" heap organization and algorithm, which
27 // may combine concurrent marking with parallel, incremental compaction of
28 // heap subsets that will yield large amounts of garbage.
30 class HeapRegion;
31 class HeapRegionSeq;
32 class PermanentGenerationSpec;
33 class GenerationSpec;
34 class OopsInHeapRegionClosure;
35 class G1ScanHeapEvacClosure;
36 class ObjectClosure;
37 class SpaceClosure;
38 class CompactibleSpaceClosure;
39 class Space;
40 class G1CollectorPolicy;
41 class GenRemSet;
42 class G1RemSet;
43 class HeapRegionRemSetIterator;
44 class ConcurrentMark;
45 class ConcurrentMarkThread;
46 class ConcurrentG1Refine;
47 class ConcurrentZFThread;
49 // If want to accumulate detailed statistics on work queues
50 // turn this on.
51 #define G1_DETAILED_STATS 0
53 #if G1_DETAILED_STATS
54 # define IF_G1_DETAILED_STATS(code) code
55 #else
56 # define IF_G1_DETAILED_STATS(code)
57 #endif
59 typedef GenericTaskQueue<StarTask> RefToScanQueue;
60 typedef GenericTaskQueueSet<StarTask> RefToScanQueueSet;
62 typedef int RegionIdx_t; // needs to hold [ 0..max_regions() )
63 typedef int CardIdx_t; // needs to hold [ 0..CardsPerRegion )
65 enum G1GCThreadGroups {
66 G1CRGroup = 0,
67 G1ZFGroup = 1,
68 G1CMGroup = 2,
69 G1CLGroup = 3
70 };
72 enum GCAllocPurpose {
73 GCAllocForTenured,
74 GCAllocForSurvived,
75 GCAllocPurposeCount
76 };
78 class YoungList : public CHeapObj {
79 private:
80 G1CollectedHeap* _g1h;
82 HeapRegion* _head;
84 HeapRegion* _scan_only_head;
85 HeapRegion* _scan_only_tail;
86 size_t _length;
87 size_t _scan_only_length;
89 size_t _last_sampled_rs_lengths;
90 size_t _sampled_rs_lengths;
91 HeapRegion* _curr;
92 HeapRegion* _curr_scan_only;
94 HeapRegion* _survivor_head;
95 HeapRegion* _survivor_tail;
96 size_t _survivor_length;
98 void empty_list(HeapRegion* list);
100 public:
101 YoungList(G1CollectedHeap* g1h);
103 void push_region(HeapRegion* hr);
104 void add_survivor_region(HeapRegion* hr);
105 HeapRegion* pop_region();
106 void empty_list();
107 bool is_empty() { return _length == 0; }
108 size_t length() { return _length; }
109 size_t scan_only_length() { return _scan_only_length; }
110 size_t survivor_length() { return _survivor_length; }
112 void rs_length_sampling_init();
113 bool rs_length_sampling_more();
114 void rs_length_sampling_next();
116 void reset_sampled_info() {
117 _last_sampled_rs_lengths = 0;
118 }
119 size_t sampled_rs_lengths() { return _last_sampled_rs_lengths; }
121 // for development purposes
122 void reset_auxilary_lists();
123 HeapRegion* first_region() { return _head; }
124 HeapRegion* first_scan_only_region() { return _scan_only_head; }
125 HeapRegion* first_survivor_region() { return _survivor_head; }
126 HeapRegion* last_survivor_region() { return _survivor_tail; }
127 HeapRegion* par_get_next_scan_only_region() {
128 MutexLockerEx x(ParGCRareEvent_lock, Mutex::_no_safepoint_check_flag);
129 HeapRegion* ret = _curr_scan_only;
130 if (ret != NULL)
131 _curr_scan_only = ret->get_next_young_region();
132 return ret;
133 }
135 // debugging
136 bool check_list_well_formed();
137 bool check_list_empty(bool ignore_scan_only_list,
138 bool check_sample = true);
139 void print();
140 };
142 class RefineCardTableEntryClosure;
143 class G1CollectedHeap : public SharedHeap {
144 friend class VM_G1CollectForAllocation;
145 friend class VM_GenCollectForPermanentAllocation;
146 friend class VM_G1CollectFull;
147 friend class VM_G1IncCollectionPause;
148 friend class VMStructs;
150 // Closures used in implementation.
151 friend class G1ParCopyHelper;
152 friend class G1IsAliveClosure;
153 friend class G1EvacuateFollowersClosure;
154 friend class G1ParScanThreadState;
155 friend class G1ParScanClosureSuper;
156 friend class G1ParEvacuateFollowersClosure;
157 friend class G1ParTask;
158 friend class G1FreeGarbageRegionClosure;
159 friend class RefineCardTableEntryClosure;
160 friend class G1PrepareCompactClosure;
161 friend class RegionSorter;
162 friend class CountRCClosure;
163 friend class EvacPopObjClosure;
164 friend class G1ParCleanupCTTask;
166 // Other related classes.
167 friend class G1MarkSweep;
169 private:
170 enum SomePrivateConstants {
171 VeryLargeInBytes = HeapRegion::GrainBytes/2,
172 VeryLargeInWords = VeryLargeInBytes/HeapWordSize,
173 MinHeapDeltaBytes = 10 * HeapRegion::GrainBytes, // FIXME
174 NumAPIs = HeapRegion::MaxAge
175 };
177 // The one and only G1CollectedHeap, so static functions can find it.
178 static G1CollectedHeap* _g1h;
180 // Storage for the G1 heap (excludes the permanent generation).
181 VirtualSpace _g1_storage;
182 MemRegion _g1_reserved;
184 // The part of _g1_storage that is currently committed.
185 MemRegion _g1_committed;
187 // The maximum part of _g1_storage that has ever been committed.
188 MemRegion _g1_max_committed;
190 // The number of regions that are completely free.
191 size_t _free_regions;
193 // The number of regions we could create by expansion.
194 size_t _expansion_regions;
196 // Return the number of free regions in the heap (by direct counting.)
197 size_t count_free_regions();
198 // Return the number of free regions on the free and unclean lists.
199 size_t count_free_regions_list();
201 // The block offset table for the G1 heap.
202 G1BlockOffsetSharedArray* _bot_shared;
204 // Move all of the regions off the free lists, then rebuild those free
205 // lists, before and after full GC.
206 void tear_down_region_lists();
207 void rebuild_region_lists();
208 // This sets all non-empty regions to need zero-fill (which they will if
209 // they are empty after full collection.)
210 void set_used_regions_to_need_zero_fill();
212 // The sequence of all heap regions in the heap.
213 HeapRegionSeq* _hrs;
215 // The region from which normal-sized objects are currently being
216 // allocated. May be NULL.
217 HeapRegion* _cur_alloc_region;
219 // Postcondition: cur_alloc_region == NULL.
220 void abandon_cur_alloc_region();
221 void abandon_gc_alloc_regions();
223 // The to-space memory regions into which objects are being copied during
224 // a GC.
225 HeapRegion* _gc_alloc_regions[GCAllocPurposeCount];
226 size_t _gc_alloc_region_counts[GCAllocPurposeCount];
227 // These are the regions, one per GCAllocPurpose, that are half-full
228 // at the end of a collection and that we want to reuse during the
229 // next collection.
230 HeapRegion* _retained_gc_alloc_regions[GCAllocPurposeCount];
231 // This specifies whether we will keep the last half-full region at
232 // the end of a collection so that it can be reused during the next
233 // collection (this is specified per GCAllocPurpose)
234 bool _retain_gc_alloc_region[GCAllocPurposeCount];
236 // A list of the regions that have been set to be alloc regions in the
237 // current collection.
238 HeapRegion* _gc_alloc_region_list;
240 // When called by par thread, require par_alloc_during_gc_lock() to be held.
241 void push_gc_alloc_region(HeapRegion* hr);
243 // This should only be called single-threaded. Undeclares all GC alloc
244 // regions.
245 void forget_alloc_region_list();
247 // Should be used to set an alloc region, because there's other
248 // associated bookkeeping.
249 void set_gc_alloc_region(int purpose, HeapRegion* r);
251 // Check well-formedness of alloc region list.
252 bool check_gc_alloc_regions();
254 // Outside of GC pauses, the number of bytes used in all regions other
255 // than the current allocation region.
256 size_t _summary_bytes_used;
258 // This is used for a quick test on whether a reference points into
259 // the collection set or not. Basically, we have an array, with one
260 // byte per region, and that byte denotes whether the corresponding
261 // region is in the collection set or not. The entry corresponding
262 // the bottom of the heap, i.e., region 0, is pointed to by
263 // _in_cset_fast_test_base. The _in_cset_fast_test field has been
264 // biased so that it actually points to address 0 of the address
265 // space, to make the test as fast as possible (we can simply shift
266 // the address to address into it, instead of having to subtract the
267 // bottom of the heap from the address before shifting it; basically
268 // it works in the same way the card table works).
269 bool* _in_cset_fast_test;
271 // The allocated array used for the fast test on whether a reference
272 // points into the collection set or not. This field is also used to
273 // free the array.
274 bool* _in_cset_fast_test_base;
276 // The length of the _in_cset_fast_test_base array.
277 size_t _in_cset_fast_test_length;
279 volatile unsigned _gc_time_stamp;
281 size_t* _surviving_young_words;
283 void setup_surviving_young_words();
284 void update_surviving_young_words(size_t* surv_young_words);
285 void cleanup_surviving_young_words();
287 protected:
289 // Returns "true" iff none of the gc alloc regions have any allocations
290 // since the last call to "save_marks".
291 bool all_alloc_regions_no_allocs_since_save_marks();
292 // Perform finalization stuff on all allocation regions.
293 void retire_all_alloc_regions();
295 // The number of regions allocated to hold humongous objects.
296 int _num_humongous_regions;
297 YoungList* _young_list;
299 // The current policy object for the collector.
300 G1CollectorPolicy* _g1_policy;
302 // Parallel allocation lock to protect the current allocation region.
303 Mutex _par_alloc_during_gc_lock;
304 Mutex* par_alloc_during_gc_lock() { return &_par_alloc_during_gc_lock; }
306 // If possible/desirable, allocate a new HeapRegion for normal object
307 // allocation sufficient for an allocation of the given "word_size".
308 // If "do_expand" is true, will attempt to expand the heap if necessary
309 // to to satisfy the request. If "zero_filled" is true, requires a
310 // zero-filled region.
311 // (Returning NULL will trigger a GC.)
312 virtual HeapRegion* newAllocRegion_work(size_t word_size,
313 bool do_expand,
314 bool zero_filled);
316 virtual HeapRegion* newAllocRegion(size_t word_size,
317 bool zero_filled = true) {
318 return newAllocRegion_work(word_size, false, zero_filled);
319 }
320 virtual HeapRegion* newAllocRegionWithExpansion(int purpose,
321 size_t word_size,
322 bool zero_filled = true);
324 // Attempt to allocate an object of the given (very large) "word_size".
325 // Returns "NULL" on failure.
326 virtual HeapWord* humongousObjAllocate(size_t word_size);
328 // If possible, allocate a block of the given word_size, else return "NULL".
329 // Returning NULL will trigger GC or heap expansion.
330 // These two methods have rather awkward pre- and
331 // post-conditions. If they are called outside a safepoint, then
332 // they assume that the caller is holding the heap lock. Upon return
333 // they release the heap lock, if they are returning a non-NULL
334 // value. attempt_allocation_slow() also dirties the cards of a
335 // newly-allocated young region after it releases the heap
336 // lock. This change in interface was the neatest way to achieve
337 // this card dirtying without affecting mem_allocate(), which is a
338 // more frequently called method. We tried two or three different
339 // approaches, but they were even more hacky.
340 HeapWord* attempt_allocation(size_t word_size,
341 bool permit_collection_pause = true);
343 HeapWord* attempt_allocation_slow(size_t word_size,
344 bool permit_collection_pause = true);
346 // Allocate blocks during garbage collection. Will ensure an
347 // allocation region, either by picking one or expanding the
348 // heap, and then allocate a block of the given size. The block
349 // may not be a humongous - it must fit into a single heap region.
350 HeapWord* allocate_during_gc(GCAllocPurpose purpose, size_t word_size);
351 HeapWord* par_allocate_during_gc(GCAllocPurpose purpose, size_t word_size);
353 HeapWord* allocate_during_gc_slow(GCAllocPurpose purpose,
354 HeapRegion* alloc_region,
355 bool par,
356 size_t word_size);
358 // Ensure that no further allocations can happen in "r", bearing in mind
359 // that parallel threads might be attempting allocations.
360 void par_allocate_remaining_space(HeapRegion* r);
362 // Retires an allocation region when it is full or at the end of a
363 // GC pause.
364 void retire_alloc_region(HeapRegion* alloc_region, bool par);
366 // Helper function for two callbacks below.
367 // "full", if true, indicates that the GC is for a System.gc() request,
368 // and should collect the entire heap. If "clear_all_soft_refs" is true,
369 // all soft references are cleared during the GC. If "full" is false,
370 // "word_size" describes the allocation that the GC should
371 // attempt (at least) to satisfy.
372 void do_collection(bool full, bool clear_all_soft_refs,
373 size_t word_size);
375 // Callback from VM_G1CollectFull operation.
376 // Perform a full collection.
377 void do_full_collection(bool clear_all_soft_refs);
379 // Resize the heap if necessary after a full collection. If this is
380 // after a collect-for allocation, "word_size" is the allocation size,
381 // and will be considered part of the used portion of the heap.
382 void resize_if_necessary_after_full_collection(size_t word_size);
384 // Callback from VM_G1CollectForAllocation operation.
385 // This function does everything necessary/possible to satisfy a
386 // failed allocation request (including collection, expansion, etc.)
387 HeapWord* satisfy_failed_allocation(size_t word_size);
389 // Attempting to expand the heap sufficiently
390 // to support an allocation of the given "word_size". If
391 // successful, perform the allocation and return the address of the
392 // allocated block, or else "NULL".
393 virtual HeapWord* expand_and_allocate(size_t word_size);
395 public:
396 // Expand the garbage-first heap by at least the given size (in bytes!).
397 // (Rounds up to a HeapRegion boundary.)
398 virtual void expand(size_t expand_bytes);
400 // Do anything common to GC's.
401 virtual void gc_prologue(bool full);
402 virtual void gc_epilogue(bool full);
404 // We register a region with the fast "in collection set" test. We
405 // simply set to true the array slot corresponding to this region.
406 void register_region_with_in_cset_fast_test(HeapRegion* r) {
407 assert(_in_cset_fast_test_base != NULL, "sanity");
408 assert(r->in_collection_set(), "invariant");
409 int index = r->hrs_index();
410 assert(0 <= (size_t) index && (size_t) index < _in_cset_fast_test_length,
411 "invariant");
412 assert(!_in_cset_fast_test_base[index], "invariant");
413 _in_cset_fast_test_base[index] = true;
414 }
416 // This is a fast test on whether a reference points into the
417 // collection set or not. It does not assume that the reference
418 // points into the heap; if it doesn't, it will return false.
419 bool in_cset_fast_test(oop obj) {
420 assert(_in_cset_fast_test != NULL, "sanity");
421 if (_g1_committed.contains((HeapWord*) obj)) {
422 // no need to subtract the bottom of the heap from obj,
423 // _in_cset_fast_test is biased
424 size_t index = ((size_t) obj) >> HeapRegion::LogOfHRGrainBytes;
425 bool ret = _in_cset_fast_test[index];
426 // let's make sure the result is consistent with what the slower
427 // test returns
428 assert( ret || !obj_in_cs(obj), "sanity");
429 assert(!ret || obj_in_cs(obj), "sanity");
430 return ret;
431 } else {
432 return false;
433 }
434 }
436 protected:
438 // Shrink the garbage-first heap by at most the given size (in bytes!).
439 // (Rounds down to a HeapRegion boundary.)
440 virtual void shrink(size_t expand_bytes);
441 void shrink_helper(size_t expand_bytes);
443 // Do an incremental collection: identify a collection set, and evacuate
444 // its live objects elsewhere.
445 virtual void do_collection_pause();
447 // The guts of the incremental collection pause, executed by the vm
448 // thread.
449 virtual void do_collection_pause_at_safepoint();
451 // Actually do the work of evacuating the collection set.
452 virtual void evacuate_collection_set();
454 // If this is an appropriate right time, do a collection pause.
455 // The "word_size" argument, if non-zero, indicates the size of an
456 // allocation request that is prompting this query.
457 void do_collection_pause_if_appropriate(size_t word_size);
459 // The g1 remembered set of the heap.
460 G1RemSet* _g1_rem_set;
461 // And it's mod ref barrier set, used to track updates for the above.
462 ModRefBarrierSet* _mr_bs;
464 // A set of cards that cover the objects for which the Rsets should be updated
465 // concurrently after the collection.
466 DirtyCardQueueSet _dirty_card_queue_set;
468 // The Heap Region Rem Set Iterator.
469 HeapRegionRemSetIterator** _rem_set_iterator;
471 // The closure used to refine a single card.
472 RefineCardTableEntryClosure* _refine_cte_cl;
474 // A function to check the consistency of dirty card logs.
475 void check_ct_logs_at_safepoint();
477 // After a collection pause, make the regions in the CS into free
478 // regions.
479 void free_collection_set(HeapRegion* cs_head);
481 // Applies "scan_non_heap_roots" to roots outside the heap,
482 // "scan_rs" to roots inside the heap (having done "set_region" to
483 // indicate the region in which the root resides), and does "scan_perm"
484 // (setting the generation to the perm generation.) If "scan_rs" is
485 // NULL, then this step is skipped. The "worker_i"
486 // param is for use with parallel roots processing, and should be
487 // the "i" of the calling parallel worker thread's work(i) function.
488 // In the sequential case this param will be ignored.
489 void g1_process_strong_roots(bool collecting_perm_gen,
490 SharedHeap::ScanningOption so,
491 OopClosure* scan_non_heap_roots,
492 OopsInHeapRegionClosure* scan_rs,
493 OopsInHeapRegionClosure* scan_so,
494 OopsInGenClosure* scan_perm,
495 int worker_i);
497 void scan_scan_only_set(OopsInHeapRegionClosure* oc,
498 int worker_i);
499 void scan_scan_only_region(HeapRegion* hr,
500 OopsInHeapRegionClosure* oc,
501 int worker_i);
503 // Apply "blk" to all the weak roots of the system. These include
504 // JNI weak roots, the code cache, system dictionary, symbol table,
505 // string table, and referents of reachable weak refs.
506 void g1_process_weak_roots(OopClosure* root_closure,
507 OopClosure* non_root_closure);
509 // Invoke "save_marks" on all heap regions.
510 void save_marks();
512 // Free a heap region.
513 void free_region(HeapRegion* hr);
514 // A component of "free_region", exposed for 'batching'.
515 // All the params after "hr" are out params: the used bytes of the freed
516 // region(s), the number of H regions cleared, the number of regions
517 // freed, and pointers to the head and tail of a list of freed contig
518 // regions, linked throught the "next_on_unclean_list" field.
519 void free_region_work(HeapRegion* hr,
520 size_t& pre_used,
521 size_t& cleared_h,
522 size_t& freed_regions,
523 UncleanRegionList* list,
524 bool par = false);
527 // The concurrent marker (and the thread it runs in.)
528 ConcurrentMark* _cm;
529 ConcurrentMarkThread* _cmThread;
530 bool _mark_in_progress;
532 // The concurrent refiner.
533 ConcurrentG1Refine* _cg1r;
535 // The concurrent zero-fill thread.
536 ConcurrentZFThread* _czft;
538 // The parallel task queues
539 RefToScanQueueSet *_task_queues;
541 // True iff a evacuation has failed in the current collection.
542 bool _evacuation_failed;
544 // Set the attribute indicating whether evacuation has failed in the
545 // current collection.
546 void set_evacuation_failed(bool b) { _evacuation_failed = b; }
548 // Failed evacuations cause some logical from-space objects to have
549 // forwarding pointers to themselves. Reset them.
550 void remove_self_forwarding_pointers();
552 // When one is non-null, so is the other. Together, they each pair is
553 // an object with a preserved mark, and its mark value.
554 GrowableArray<oop>* _objs_with_preserved_marks;
555 GrowableArray<markOop>* _preserved_marks_of_objs;
557 // Preserve the mark of "obj", if necessary, in preparation for its mark
558 // word being overwritten with a self-forwarding-pointer.
559 void preserve_mark_if_necessary(oop obj, markOop m);
561 // The stack of evac-failure objects left to be scanned.
562 GrowableArray<oop>* _evac_failure_scan_stack;
563 // The closure to apply to evac-failure objects.
565 OopsInHeapRegionClosure* _evac_failure_closure;
566 // Set the field above.
567 void
568 set_evac_failure_closure(OopsInHeapRegionClosure* evac_failure_closure) {
569 _evac_failure_closure = evac_failure_closure;
570 }
572 // Push "obj" on the scan stack.
573 void push_on_evac_failure_scan_stack(oop obj);
574 // Process scan stack entries until the stack is empty.
575 void drain_evac_failure_scan_stack();
576 // True iff an invocation of "drain_scan_stack" is in progress; to
577 // prevent unnecessary recursion.
578 bool _drain_in_progress;
580 // Do any necessary initialization for evacuation-failure handling.
581 // "cl" is the closure that will be used to process evac-failure
582 // objects.
583 void init_for_evac_failure(OopsInHeapRegionClosure* cl);
584 // Do any necessary cleanup for evacuation-failure handling data
585 // structures.
586 void finalize_for_evac_failure();
588 // An attempt to evacuate "obj" has failed; take necessary steps.
589 void handle_evacuation_failure(oop obj);
590 oop handle_evacuation_failure_par(OopsInHeapRegionClosure* cl, oop obj);
591 void handle_evacuation_failure_common(oop obj, markOop m);
594 // Ensure that the relevant gc_alloc regions are set.
595 void get_gc_alloc_regions();
596 // We're done with GC alloc regions. We are going to tear down the
597 // gc alloc list and remove the gc alloc tag from all the regions on
598 // that list. However, we will also retain the last (i.e., the one
599 // that is half-full) GC alloc region, per GCAllocPurpose, for
600 // possible reuse during the next collection, provided
601 // _retain_gc_alloc_region[] indicates that it should be the
602 // case. Said regions are kept in the _retained_gc_alloc_regions[]
603 // array. If the parameter totally is set, we will not retain any
604 // regions, irrespective of what _retain_gc_alloc_region[]
605 // indicates.
606 void release_gc_alloc_regions(bool totally);
607 #ifndef PRODUCT
608 // Useful for debugging.
609 void print_gc_alloc_regions();
610 #endif // !PRODUCT
612 // ("Weak") Reference processing support
613 ReferenceProcessor* _ref_processor;
615 enum G1H_process_strong_roots_tasks {
616 G1H_PS_mark_stack_oops_do,
617 G1H_PS_refProcessor_oops_do,
618 // Leave this one last.
619 G1H_PS_NumElements
620 };
622 SubTasksDone* _process_strong_tasks;
624 // List of regions which require zero filling.
625 UncleanRegionList _unclean_region_list;
626 bool _unclean_regions_coming;
628 public:
629 void set_refine_cte_cl_concurrency(bool concurrent);
631 RefToScanQueue *task_queue(int i);
633 // A set of cards where updates happened during the GC
634 DirtyCardQueueSet& dirty_card_queue_set() { return _dirty_card_queue_set; }
636 // Create a G1CollectedHeap with the specified policy.
637 // Must call the initialize method afterwards.
638 // May not return if something goes wrong.
639 G1CollectedHeap(G1CollectorPolicy* policy);
641 // Initialize the G1CollectedHeap to have the initial and
642 // maximum sizes, permanent generation, and remembered and barrier sets
643 // specified by the policy object.
644 jint initialize();
646 void ref_processing_init();
648 void set_par_threads(int t) {
649 SharedHeap::set_par_threads(t);
650 _process_strong_tasks->set_par_threads(t);
651 }
653 virtual CollectedHeap::Name kind() const {
654 return CollectedHeap::G1CollectedHeap;
655 }
657 // The current policy object for the collector.
658 G1CollectorPolicy* g1_policy() const { return _g1_policy; }
660 // Adaptive size policy. No such thing for g1.
661 virtual AdaptiveSizePolicy* size_policy() { return NULL; }
663 // The rem set and barrier set.
664 G1RemSet* g1_rem_set() const { return _g1_rem_set; }
665 ModRefBarrierSet* mr_bs() const { return _mr_bs; }
667 // The rem set iterator.
668 HeapRegionRemSetIterator* rem_set_iterator(int i) {
669 return _rem_set_iterator[i];
670 }
672 HeapRegionRemSetIterator* rem_set_iterator() {
673 return _rem_set_iterator[0];
674 }
676 unsigned get_gc_time_stamp() {
677 return _gc_time_stamp;
678 }
680 void reset_gc_time_stamp() {
681 _gc_time_stamp = 0;
682 OrderAccess::fence();
683 }
685 void increment_gc_time_stamp() {
686 ++_gc_time_stamp;
687 OrderAccess::fence();
688 }
690 void iterate_dirty_card_closure(bool concurrent, int worker_i);
692 // The shared block offset table array.
693 G1BlockOffsetSharedArray* bot_shared() const { return _bot_shared; }
695 // Reference Processing accessor
696 ReferenceProcessor* ref_processor() { return _ref_processor; }
698 // Reserved (g1 only; super method includes perm), capacity and the used
699 // portion in bytes.
700 size_t g1_reserved_obj_bytes() { return _g1_reserved.byte_size(); }
701 virtual size_t capacity() const;
702 virtual size_t used() const;
703 // This should be called when we're not holding the heap lock. The
704 // result might be a bit inaccurate.
705 size_t used_unlocked() const;
706 size_t recalculate_used() const;
707 #ifndef PRODUCT
708 size_t recalculate_used_regions() const;
709 #endif // PRODUCT
711 // These virtual functions do the actual allocation.
712 virtual HeapWord* mem_allocate(size_t word_size,
713 bool is_noref,
714 bool is_tlab,
715 bool* gc_overhead_limit_was_exceeded);
717 // Some heaps may offer a contiguous region for shared non-blocking
718 // allocation, via inlined code (by exporting the address of the top and
719 // end fields defining the extent of the contiguous allocation region.)
720 // But G1CollectedHeap doesn't yet support this.
722 // Return an estimate of the maximum allocation that could be performed
723 // without triggering any collection or expansion activity. In a
724 // generational collector, for example, this is probably the largest
725 // allocation that could be supported (without expansion) in the youngest
726 // generation. It is "unsafe" because no locks are taken; the result
727 // should be treated as an approximation, not a guarantee, for use in
728 // heuristic resizing decisions.
729 virtual size_t unsafe_max_alloc();
731 virtual bool is_maximal_no_gc() const {
732 return _g1_storage.uncommitted_size() == 0;
733 }
735 // The total number of regions in the heap.
736 size_t n_regions();
738 // The number of regions that are completely free.
739 size_t max_regions();
741 // The number of regions that are completely free.
742 size_t free_regions();
744 // The number of regions that are not completely free.
745 size_t used_regions() { return n_regions() - free_regions(); }
747 // True iff the ZF thread should run.
748 bool should_zf();
750 // The number of regions available for "regular" expansion.
751 size_t expansion_regions() { return _expansion_regions; }
753 #ifndef PRODUCT
754 bool regions_accounted_for();
755 bool print_region_accounting_info();
756 void print_region_counts();
757 #endif
759 HeapRegion* alloc_region_from_unclean_list(bool zero_filled);
760 HeapRegion* alloc_region_from_unclean_list_locked(bool zero_filled);
762 void put_region_on_unclean_list(HeapRegion* r);
763 void put_region_on_unclean_list_locked(HeapRegion* r);
765 void prepend_region_list_on_unclean_list(UncleanRegionList* list);
766 void prepend_region_list_on_unclean_list_locked(UncleanRegionList* list);
768 void set_unclean_regions_coming(bool b);
769 void set_unclean_regions_coming_locked(bool b);
770 // Wait for cleanup to be complete.
771 void wait_for_cleanup_complete();
772 // Like above, but assumes that the calling thread owns the Heap_lock.
773 void wait_for_cleanup_complete_locked();
775 // Return the head of the unclean list.
776 HeapRegion* peek_unclean_region_list_locked();
777 // Remove and return the head of the unclean list.
778 HeapRegion* pop_unclean_region_list_locked();
780 // List of regions which are zero filled and ready for allocation.
781 HeapRegion* _free_region_list;
782 // Number of elements on the free list.
783 size_t _free_region_list_size;
785 // If the head of the unclean list is ZeroFilled, move it to the free
786 // list.
787 bool move_cleaned_region_to_free_list_locked();
788 bool move_cleaned_region_to_free_list();
790 void put_free_region_on_list_locked(HeapRegion* r);
791 void put_free_region_on_list(HeapRegion* r);
793 // Remove and return the head element of the free list.
794 HeapRegion* pop_free_region_list_locked();
796 // If "zero_filled" is true, we first try the free list, then we try the
797 // unclean list, zero-filling the result. If "zero_filled" is false, we
798 // first try the unclean list, then the zero-filled list.
799 HeapRegion* alloc_free_region_from_lists(bool zero_filled);
801 // Verify the integrity of the region lists.
802 void remove_allocated_regions_from_lists();
803 bool verify_region_lists();
804 bool verify_region_lists_locked();
805 size_t unclean_region_list_length();
806 size_t free_region_list_length();
808 // Perform a collection of the heap; intended for use in implementing
809 // "System.gc". This probably implies as full a collection as the
810 // "CollectedHeap" supports.
811 virtual void collect(GCCause::Cause cause);
813 // The same as above but assume that the caller holds the Heap_lock.
814 void collect_locked(GCCause::Cause cause);
816 // This interface assumes that it's being called by the
817 // vm thread. It collects the heap assuming that the
818 // heap lock is already held and that we are executing in
819 // the context of the vm thread.
820 virtual void collect_as_vm_thread(GCCause::Cause cause);
822 // True iff a evacuation has failed in the most-recent collection.
823 bool evacuation_failed() { return _evacuation_failed; }
825 // Free a region if it is totally full of garbage. Returns the number of
826 // bytes freed (0 ==> didn't free it).
827 size_t free_region_if_totally_empty(HeapRegion *hr);
828 void free_region_if_totally_empty_work(HeapRegion *hr,
829 size_t& pre_used,
830 size_t& cleared_h_regions,
831 size_t& freed_regions,
832 UncleanRegionList* list,
833 bool par = false);
835 // If we've done free region work that yields the given changes, update
836 // the relevant global variables.
837 void finish_free_region_work(size_t pre_used,
838 size_t cleared_h_regions,
839 size_t freed_regions,
840 UncleanRegionList* list);
843 // Returns "TRUE" iff "p" points into the allocated area of the heap.
844 virtual bool is_in(const void* p) const;
846 // Return "TRUE" iff the given object address is within the collection
847 // set.
848 inline bool obj_in_cs(oop obj);
850 // Return "TRUE" iff the given object address is in the reserved
851 // region of g1 (excluding the permanent generation).
852 bool is_in_g1_reserved(const void* p) const {
853 return _g1_reserved.contains(p);
854 }
856 // Returns a MemRegion that corresponds to the space that has been
857 // committed in the heap
858 MemRegion g1_committed() {
859 return _g1_committed;
860 }
862 NOT_PRODUCT( bool is_in_closed_subset(const void* p) const; )
864 // Dirty card table entries covering a list of young regions.
865 void dirtyCardsForYoungRegions(CardTableModRefBS* ct_bs, HeapRegion* list);
867 // This resets the card table to all zeros. It is used after
868 // a collection pause which used the card table to claim cards.
869 void cleanUpCardTable();
871 // Iteration functions.
873 // Iterate over all the ref-containing fields of all objects, calling
874 // "cl.do_oop" on each.
875 virtual void oop_iterate(OopClosure* cl) {
876 oop_iterate(cl, true);
877 }
878 void oop_iterate(OopClosure* cl, bool do_perm);
880 // Same as above, restricted to a memory region.
881 virtual void oop_iterate(MemRegion mr, OopClosure* cl) {
882 oop_iterate(mr, cl, true);
883 }
884 void oop_iterate(MemRegion mr, OopClosure* cl, bool do_perm);
886 // Iterate over all objects, calling "cl.do_object" on each.
887 virtual void object_iterate(ObjectClosure* cl) {
888 object_iterate(cl, true);
889 }
890 virtual void safe_object_iterate(ObjectClosure* cl) {
891 object_iterate(cl, true);
892 }
893 void object_iterate(ObjectClosure* cl, bool do_perm);
895 // Iterate over all objects allocated since the last collection, calling
896 // "cl.do_object" on each. The heap must have been initialized properly
897 // to support this function, or else this call will fail.
898 virtual void object_iterate_since_last_GC(ObjectClosure* cl);
900 // Iterate over all spaces in use in the heap, in ascending address order.
901 virtual void space_iterate(SpaceClosure* cl);
903 // Iterate over heap regions, in address order, terminating the
904 // iteration early if the "doHeapRegion" method returns "true".
905 void heap_region_iterate(HeapRegionClosure* blk);
907 // Iterate over heap regions starting with r (or the first region if "r"
908 // is NULL), in address order, terminating early if the "doHeapRegion"
909 // method returns "true".
910 void heap_region_iterate_from(HeapRegion* r, HeapRegionClosure* blk);
912 // As above but starting from the region at index idx.
913 void heap_region_iterate_from(int idx, HeapRegionClosure* blk);
915 HeapRegion* region_at(size_t idx);
917 // Divide the heap region sequence into "chunks" of some size (the number
918 // of regions divided by the number of parallel threads times some
919 // overpartition factor, currently 4). Assumes that this will be called
920 // in parallel by ParallelGCThreads worker threads with discinct worker
921 // ids in the range [0..max(ParallelGCThreads-1, 1)], that all parallel
922 // calls will use the same "claim_value", and that that claim value is
923 // different from the claim_value of any heap region before the start of
924 // the iteration. Applies "blk->doHeapRegion" to each of the regions, by
925 // attempting to claim the first region in each chunk, and, if
926 // successful, applying the closure to each region in the chunk (and
927 // setting the claim value of the second and subsequent regions of the
928 // chunk.) For now requires that "doHeapRegion" always returns "false",
929 // i.e., that a closure never attempt to abort a traversal.
930 void heap_region_par_iterate_chunked(HeapRegionClosure* blk,
931 int worker,
932 jint claim_value);
934 // It resets all the region claim values to the default.
935 void reset_heap_region_claim_values();
937 #ifdef ASSERT
938 bool check_heap_region_claim_values(jint claim_value);
939 #endif // ASSERT
941 // Iterate over the regions (if any) in the current collection set.
942 void collection_set_iterate(HeapRegionClosure* blk);
944 // As above but starting from region r
945 void collection_set_iterate_from(HeapRegion* r, HeapRegionClosure *blk);
947 // Returns the first (lowest address) compactible space in the heap.
948 virtual CompactibleSpace* first_compactible_space();
950 // A CollectedHeap will contain some number of spaces. This finds the
951 // space containing a given address, or else returns NULL.
952 virtual Space* space_containing(const void* addr) const;
954 // A G1CollectedHeap will contain some number of heap regions. This
955 // finds the region containing a given address, or else returns NULL.
956 HeapRegion* heap_region_containing(const void* addr) const;
958 // Like the above, but requires "addr" to be in the heap (to avoid a
959 // null-check), and unlike the above, may return an continuing humongous
960 // region.
961 HeapRegion* heap_region_containing_raw(const void* addr) const;
963 // A CollectedHeap is divided into a dense sequence of "blocks"; that is,
964 // each address in the (reserved) heap is a member of exactly
965 // one block. The defining characteristic of a block is that it is
966 // possible to find its size, and thus to progress forward to the next
967 // block. (Blocks may be of different sizes.) Thus, blocks may
968 // represent Java objects, or they might be free blocks in a
969 // free-list-based heap (or subheap), as long as the two kinds are
970 // distinguishable and the size of each is determinable.
972 // Returns the address of the start of the "block" that contains the
973 // address "addr". We say "blocks" instead of "object" since some heaps
974 // may not pack objects densely; a chunk may either be an object or a
975 // non-object.
976 virtual HeapWord* block_start(const void* addr) const;
978 // Requires "addr" to be the start of a chunk, and returns its size.
979 // "addr + size" is required to be the start of a new chunk, or the end
980 // of the active area of the heap.
981 virtual size_t block_size(const HeapWord* addr) const;
983 // Requires "addr" to be the start of a block, and returns "TRUE" iff
984 // the block is an object.
985 virtual bool block_is_obj(const HeapWord* addr) const;
987 // Does this heap support heap inspection? (+PrintClassHistogram)
988 virtual bool supports_heap_inspection() const { return true; }
990 // Section on thread-local allocation buffers (TLABs)
991 // See CollectedHeap for semantics.
993 virtual bool supports_tlab_allocation() const;
994 virtual size_t tlab_capacity(Thread* thr) const;
995 virtual size_t unsafe_max_tlab_alloc(Thread* thr) const;
996 virtual HeapWord* allocate_new_tlab(size_t size);
998 // Can a compiler initialize a new object without store barriers?
999 // This permission only extends from the creation of a new object
1000 // via a TLAB up to the first subsequent safepoint.
1001 virtual bool can_elide_tlab_store_barriers() const {
1002 // Since G1's TLAB's may, on occasion, come from non-young regions
1003 // as well. (Is there a flag controlling that? XXX)
1004 return false;
1005 }
1007 // Can a compiler elide a store barrier when it writes
1008 // a permanent oop into the heap? Applies when the compiler
1009 // is storing x to the heap, where x->is_perm() is true.
1010 virtual bool can_elide_permanent_oop_store_barriers() const {
1011 // At least until perm gen collection is also G1-ified, at
1012 // which point this should return false.
1013 return true;
1014 }
1016 virtual bool allocs_are_zero_filled();
1018 // The boundary between a "large" and "small" array of primitives, in
1019 // words.
1020 virtual size_t large_typearray_limit();
1022 // Returns "true" iff the given word_size is "very large".
1023 static bool isHumongous(size_t word_size) {
1024 return word_size >= VeryLargeInWords;
1025 }
1027 // Update mod union table with the set of dirty cards.
1028 void updateModUnion();
1030 // Set the mod union bits corresponding to the given memRegion. Note
1031 // that this is always a safe operation, since it doesn't clear any
1032 // bits.
1033 void markModUnionRange(MemRegion mr);
1035 // Records the fact that a marking phase is no longer in progress.
1036 void set_marking_complete() {
1037 _mark_in_progress = false;
1038 }
1039 void set_marking_started() {
1040 _mark_in_progress = true;
1041 }
1042 bool mark_in_progress() {
1043 return _mark_in_progress;
1044 }
1046 // Print the maximum heap capacity.
1047 virtual size_t max_capacity() const;
1049 virtual jlong millis_since_last_gc();
1051 // Perform any cleanup actions necessary before allowing a verification.
1052 virtual void prepare_for_verify();
1054 // Perform verification.
1056 // use_prev_marking == true -> use "prev" marking information,
1057 // use_prev_marking == false -> use "next" marking information
1058 // NOTE: Only the "prev" marking information is guaranteed to be
1059 // consistent most of the time, so most calls to this should use
1060 // use_prev_marking == true. Currently, there is only one case where
1061 // this is called with use_prev_marking == false, which is to verify
1062 // the "next" marking information at the end of remark.
1063 void verify(bool allow_dirty, bool silent, bool use_prev_marking);
1065 // Override; it uses the "prev" marking information
1066 virtual void verify(bool allow_dirty, bool silent);
1067 // Default behavior by calling print(tty);
1068 virtual void print() const;
1069 // This calls print_on(st, PrintHeapAtGCExtended).
1070 virtual void print_on(outputStream* st) const;
1071 // If extended is true, it will print out information for all
1072 // regions in the heap by calling print_on_extended(st).
1073 virtual void print_on(outputStream* st, bool extended) const;
1074 virtual void print_on_extended(outputStream* st) const;
1076 virtual void print_gc_threads_on(outputStream* st) const;
1077 virtual void gc_threads_do(ThreadClosure* tc) const;
1079 // Override
1080 void print_tracing_info() const;
1082 // If "addr" is a pointer into the (reserved?) heap, returns a positive
1083 // number indicating the "arena" within the heap in which "addr" falls.
1084 // Or else returns 0.
1085 virtual int addr_to_arena_id(void* addr) const;
1087 // Convenience function to be used in situations where the heap type can be
1088 // asserted to be this type.
1089 static G1CollectedHeap* heap();
1091 void empty_young_list();
1092 bool should_set_young_locked();
1094 void set_region_short_lived_locked(HeapRegion* hr);
1095 // add appropriate methods for any other surv rate groups
1097 void young_list_rs_length_sampling_init() {
1098 _young_list->rs_length_sampling_init();
1099 }
1100 bool young_list_rs_length_sampling_more() {
1101 return _young_list->rs_length_sampling_more();
1102 }
1103 void young_list_rs_length_sampling_next() {
1104 _young_list->rs_length_sampling_next();
1105 }
1106 size_t young_list_sampled_rs_lengths() {
1107 return _young_list->sampled_rs_lengths();
1108 }
1110 size_t young_list_length() { return _young_list->length(); }
1111 size_t young_list_scan_only_length() {
1112 return _young_list->scan_only_length(); }
1114 HeapRegion* pop_region_from_young_list() {
1115 return _young_list->pop_region();
1116 }
1118 HeapRegion* young_list_first_region() {
1119 return _young_list->first_region();
1120 }
1122 // debugging
1123 bool check_young_list_well_formed() {
1124 return _young_list->check_list_well_formed();
1125 }
1126 bool check_young_list_empty(bool ignore_scan_only_list,
1127 bool check_sample = true);
1129 // *** Stuff related to concurrent marking. It's not clear to me that so
1130 // many of these need to be public.
1132 // The functions below are helper functions that a subclass of
1133 // "CollectedHeap" can use in the implementation of its virtual
1134 // functions.
1135 // This performs a concurrent marking of the live objects in a
1136 // bitmap off to the side.
1137 void doConcurrentMark();
1139 // This is called from the marksweep collector which then does
1140 // a concurrent mark and verifies that the results agree with
1141 // the stop the world marking.
1142 void checkConcurrentMark();
1143 void do_sync_mark();
1145 bool isMarkedPrev(oop obj) const;
1146 bool isMarkedNext(oop obj) const;
1148 // use_prev_marking == true -> use "prev" marking information,
1149 // use_prev_marking == false -> use "next" marking information
1150 bool is_obj_dead_cond(const oop obj,
1151 const HeapRegion* hr,
1152 const bool use_prev_marking) const {
1153 if (use_prev_marking) {
1154 return is_obj_dead(obj, hr);
1155 } else {
1156 return is_obj_ill(obj, hr);
1157 }
1158 }
1160 // Determine if an object is dead, given the object and also
1161 // the region to which the object belongs. An object is dead
1162 // iff a) it was not allocated since the last mark and b) it
1163 // is not marked.
1165 bool is_obj_dead(const oop obj, const HeapRegion* hr) const {
1166 return
1167 !hr->obj_allocated_since_prev_marking(obj) &&
1168 !isMarkedPrev(obj);
1169 }
1171 // This is used when copying an object to survivor space.
1172 // If the object is marked live, then we mark the copy live.
1173 // If the object is allocated since the start of this mark
1174 // cycle, then we mark the copy live.
1175 // If the object has been around since the previous mark
1176 // phase, and hasn't been marked yet during this phase,
1177 // then we don't mark it, we just wait for the
1178 // current marking cycle to get to it.
1180 // This function returns true when an object has been
1181 // around since the previous marking and hasn't yet
1182 // been marked during this marking.
1184 bool is_obj_ill(const oop obj, const HeapRegion* hr) const {
1185 return
1186 !hr->obj_allocated_since_next_marking(obj) &&
1187 !isMarkedNext(obj);
1188 }
1190 // Determine if an object is dead, given only the object itself.
1191 // This will find the region to which the object belongs and
1192 // then call the region version of the same function.
1194 // Added if it is in permanent gen it isn't dead.
1195 // Added if it is NULL it isn't dead.
1197 // use_prev_marking == true -> use "prev" marking information,
1198 // use_prev_marking == false -> use "next" marking information
1199 bool is_obj_dead_cond(const oop obj,
1200 const bool use_prev_marking) {
1201 if (use_prev_marking) {
1202 return is_obj_dead(obj);
1203 } else {
1204 return is_obj_ill(obj);
1205 }
1206 }
1208 bool is_obj_dead(const oop obj) {
1209 const HeapRegion* hr = heap_region_containing(obj);
1210 if (hr == NULL) {
1211 if (Universe::heap()->is_in_permanent(obj))
1212 return false;
1213 else if (obj == NULL) return false;
1214 else return true;
1215 }
1216 else return is_obj_dead(obj, hr);
1217 }
1219 bool is_obj_ill(const oop obj) {
1220 const HeapRegion* hr = heap_region_containing(obj);
1221 if (hr == NULL) {
1222 if (Universe::heap()->is_in_permanent(obj))
1223 return false;
1224 else if (obj == NULL) return false;
1225 else return true;
1226 }
1227 else return is_obj_ill(obj, hr);
1228 }
1230 // The following is just to alert the verification code
1231 // that a full collection has occurred and that the
1232 // remembered sets are no longer up to date.
1233 bool _full_collection;
1234 void set_full_collection() { _full_collection = true;}
1235 void clear_full_collection() {_full_collection = false;}
1236 bool full_collection() {return _full_collection;}
1238 ConcurrentMark* concurrent_mark() const { return _cm; }
1239 ConcurrentG1Refine* concurrent_g1_refine() const { return _cg1r; }
1241 // The dirty cards region list is used to record a subset of regions
1242 // whose cards need clearing. The list if populated during the
1243 // remembered set scanning and drained during the card table
1244 // cleanup. Although the methods are reentrant, population/draining
1245 // phases must not overlap. For synchronization purposes the last
1246 // element on the list points to itself.
1247 HeapRegion* _dirty_cards_region_list;
1248 void push_dirty_cards_region(HeapRegion* hr);
1249 HeapRegion* pop_dirty_cards_region();
1251 public:
1252 void stop_conc_gc_threads();
1254 // <NEW PREDICTION>
1256 double predict_region_elapsed_time_ms(HeapRegion* hr, bool young);
1257 void check_if_region_is_too_expensive(double predicted_time_ms);
1258 size_t pending_card_num();
1259 size_t max_pending_card_num();
1260 size_t cards_scanned();
1262 // </NEW PREDICTION>
1264 protected:
1265 size_t _max_heap_capacity;
1267 // debug_only(static void check_for_valid_allocation_state();)
1269 public:
1270 // Temporary: call to mark things unimplemented for the G1 heap (e.g.,
1271 // MemoryService). In productization, we can make this assert false
1272 // to catch such places (as well as searching for calls to this...)
1273 static void g1_unimplemented();
1275 };
1277 #define use_local_bitmaps 1
1278 #define verify_local_bitmaps 0
1279 #define oop_buffer_length 256
1281 #ifndef PRODUCT
1282 class GCLabBitMap;
1283 class GCLabBitMapClosure: public BitMapClosure {
1284 private:
1285 ConcurrentMark* _cm;
1286 GCLabBitMap* _bitmap;
1288 public:
1289 GCLabBitMapClosure(ConcurrentMark* cm,
1290 GCLabBitMap* bitmap) {
1291 _cm = cm;
1292 _bitmap = bitmap;
1293 }
1295 virtual bool do_bit(size_t offset);
1296 };
1297 #endif // !PRODUCT
1299 class GCLabBitMap: public BitMap {
1300 private:
1301 ConcurrentMark* _cm;
1303 int _shifter;
1304 size_t _bitmap_word_covers_words;
1306 // beginning of the heap
1307 HeapWord* _heap_start;
1309 // this is the actual start of the GCLab
1310 HeapWord* _real_start_word;
1312 // this is the actual end of the GCLab
1313 HeapWord* _real_end_word;
1315 // this is the first word, possibly located before the actual start
1316 // of the GCLab, that corresponds to the first bit of the bitmap
1317 HeapWord* _start_word;
1319 // size of a GCLab in words
1320 size_t _gclab_word_size;
1322 static int shifter() {
1323 return MinObjAlignment - 1;
1324 }
1326 // how many heap words does a single bitmap word corresponds to?
1327 static size_t bitmap_word_covers_words() {
1328 return BitsPerWord << shifter();
1329 }
1331 static size_t gclab_word_size() {
1332 return G1ParallelGCAllocBufferSize / HeapWordSize;
1333 }
1335 static size_t bitmap_size_in_bits() {
1336 size_t bits_in_bitmap = gclab_word_size() >> shifter();
1337 // We are going to ensure that the beginning of a word in this
1338 // bitmap also corresponds to the beginning of a word in the
1339 // global marking bitmap. To handle the case where a GCLab
1340 // starts from the middle of the bitmap, we need to add enough
1341 // space (i.e. up to a bitmap word) to ensure that we have
1342 // enough bits in the bitmap.
1343 return bits_in_bitmap + BitsPerWord - 1;
1344 }
1345 public:
1346 GCLabBitMap(HeapWord* heap_start)
1347 : BitMap(bitmap_size_in_bits()),
1348 _cm(G1CollectedHeap::heap()->concurrent_mark()),
1349 _shifter(shifter()),
1350 _bitmap_word_covers_words(bitmap_word_covers_words()),
1351 _heap_start(heap_start),
1352 _gclab_word_size(gclab_word_size()),
1353 _real_start_word(NULL),
1354 _real_end_word(NULL),
1355 _start_word(NULL)
1356 {
1357 guarantee( size_in_words() >= bitmap_size_in_words(),
1358 "just making sure");
1359 }
1361 inline unsigned heapWordToOffset(HeapWord* addr) {
1362 unsigned offset = (unsigned) pointer_delta(addr, _start_word) >> _shifter;
1363 assert(offset < size(), "offset should be within bounds");
1364 return offset;
1365 }
1367 inline HeapWord* offsetToHeapWord(size_t offset) {
1368 HeapWord* addr = _start_word + (offset << _shifter);
1369 assert(_real_start_word <= addr && addr < _real_end_word, "invariant");
1370 return addr;
1371 }
1373 bool fields_well_formed() {
1374 bool ret1 = (_real_start_word == NULL) &&
1375 (_real_end_word == NULL) &&
1376 (_start_word == NULL);
1377 if (ret1)
1378 return true;
1380 bool ret2 = _real_start_word >= _start_word &&
1381 _start_word < _real_end_word &&
1382 (_real_start_word + _gclab_word_size) == _real_end_word &&
1383 (_start_word + _gclab_word_size + _bitmap_word_covers_words)
1384 > _real_end_word;
1385 return ret2;
1386 }
1388 inline bool mark(HeapWord* addr) {
1389 guarantee(use_local_bitmaps, "invariant");
1390 assert(fields_well_formed(), "invariant");
1392 if (addr >= _real_start_word && addr < _real_end_word) {
1393 assert(!isMarked(addr), "should not have already been marked");
1395 // first mark it on the bitmap
1396 at_put(heapWordToOffset(addr), true);
1398 return true;
1399 } else {
1400 return false;
1401 }
1402 }
1404 inline bool isMarked(HeapWord* addr) {
1405 guarantee(use_local_bitmaps, "invariant");
1406 assert(fields_well_formed(), "invariant");
1408 return at(heapWordToOffset(addr));
1409 }
1411 void set_buffer(HeapWord* start) {
1412 guarantee(use_local_bitmaps, "invariant");
1413 clear();
1415 assert(start != NULL, "invariant");
1416 _real_start_word = start;
1417 _real_end_word = start + _gclab_word_size;
1419 size_t diff =
1420 pointer_delta(start, _heap_start) % _bitmap_word_covers_words;
1421 _start_word = start - diff;
1423 assert(fields_well_formed(), "invariant");
1424 }
1426 #ifndef PRODUCT
1427 void verify() {
1428 // verify that the marks have been propagated
1429 GCLabBitMapClosure cl(_cm, this);
1430 iterate(&cl);
1431 }
1432 #endif // PRODUCT
1434 void retire() {
1435 guarantee(use_local_bitmaps, "invariant");
1436 assert(fields_well_formed(), "invariant");
1438 if (_start_word != NULL) {
1439 CMBitMap* mark_bitmap = _cm->nextMarkBitMap();
1441 // this means that the bitmap was set up for the GCLab
1442 assert(_real_start_word != NULL && _real_end_word != NULL, "invariant");
1444 mark_bitmap->mostly_disjoint_range_union(this,
1445 0, // always start from the start of the bitmap
1446 _start_word,
1447 size_in_words());
1448 _cm->grayRegionIfNecessary(MemRegion(_real_start_word, _real_end_word));
1450 #ifndef PRODUCT
1451 if (use_local_bitmaps && verify_local_bitmaps)
1452 verify();
1453 #endif // PRODUCT
1454 } else {
1455 assert(_real_start_word == NULL && _real_end_word == NULL, "invariant");
1456 }
1457 }
1459 static size_t bitmap_size_in_words() {
1460 return (bitmap_size_in_bits() + BitsPerWord - 1) / BitsPerWord;
1461 }
1462 };
1464 class G1ParGCAllocBuffer: public ParGCAllocBuffer {
1465 private:
1466 bool _retired;
1467 bool _during_marking;
1468 GCLabBitMap _bitmap;
1470 public:
1471 G1ParGCAllocBuffer() :
1472 ParGCAllocBuffer(G1ParallelGCAllocBufferSize / HeapWordSize),
1473 _during_marking(G1CollectedHeap::heap()->mark_in_progress()),
1474 _bitmap(G1CollectedHeap::heap()->reserved_region().start()),
1475 _retired(false)
1476 { }
1478 inline bool mark(HeapWord* addr) {
1479 guarantee(use_local_bitmaps, "invariant");
1480 assert(_during_marking, "invariant");
1481 return _bitmap.mark(addr);
1482 }
1484 inline void set_buf(HeapWord* buf) {
1485 if (use_local_bitmaps && _during_marking)
1486 _bitmap.set_buffer(buf);
1487 ParGCAllocBuffer::set_buf(buf);
1488 _retired = false;
1489 }
1491 inline void retire(bool end_of_gc, bool retain) {
1492 if (_retired)
1493 return;
1494 if (use_local_bitmaps && _during_marking) {
1495 _bitmap.retire();
1496 }
1497 ParGCAllocBuffer::retire(end_of_gc, retain);
1498 _retired = true;
1499 }
1500 };
1502 class G1ParScanThreadState : public StackObj {
1503 protected:
1504 G1CollectedHeap* _g1h;
1505 RefToScanQueue* _refs;
1506 DirtyCardQueue _dcq;
1507 CardTableModRefBS* _ct_bs;
1508 G1RemSet* _g1_rem;
1510 typedef GrowableArray<StarTask> OverflowQueue;
1511 OverflowQueue* _overflowed_refs;
1513 G1ParGCAllocBuffer _alloc_buffers[GCAllocPurposeCount];
1514 ageTable _age_table;
1516 size_t _alloc_buffer_waste;
1517 size_t _undo_waste;
1519 OopsInHeapRegionClosure* _evac_failure_cl;
1520 G1ParScanHeapEvacClosure* _evac_cl;
1521 G1ParScanPartialArrayClosure* _partial_scan_cl;
1523 int _hash_seed;
1524 int _queue_num;
1526 int _term_attempts;
1527 #if G1_DETAILED_STATS
1528 int _pushes, _pops, _steals, _steal_attempts;
1529 int _overflow_pushes;
1530 #endif
1532 double _start;
1533 double _start_strong_roots;
1534 double _strong_roots_time;
1535 double _start_term;
1536 double _term_time;
1538 // Map from young-age-index (0 == not young, 1 is youngest) to
1539 // surviving words. base is what we get back from the malloc call
1540 size_t* _surviving_young_words_base;
1541 // this points into the array, as we use the first few entries for padding
1542 size_t* _surviving_young_words;
1544 #define PADDING_ELEM_NUM (64 / sizeof(size_t))
1546 void add_to_alloc_buffer_waste(size_t waste) { _alloc_buffer_waste += waste; }
1548 void add_to_undo_waste(size_t waste) { _undo_waste += waste; }
1550 DirtyCardQueue& dirty_card_queue() { return _dcq; }
1551 CardTableModRefBS* ctbs() { return _ct_bs; }
1553 template <class T> void immediate_rs_update(HeapRegion* from, T* p, int tid) {
1554 if (!from->is_survivor()) {
1555 _g1_rem->par_write_ref(from, p, tid);
1556 }
1557 }
1559 template <class T> void deferred_rs_update(HeapRegion* from, T* p, int tid) {
1560 // If the new value of the field points to the same region or
1561 // is the to-space, we don't need to include it in the Rset updates.
1562 if (!from->is_in_reserved(oopDesc::load_decode_heap_oop(p)) && !from->is_survivor()) {
1563 size_t card_index = ctbs()->index_for(p);
1564 // If the card hasn't been added to the buffer, do it.
1565 if (ctbs()->mark_card_deferred(card_index)) {
1566 dirty_card_queue().enqueue((jbyte*)ctbs()->byte_for_index(card_index));
1567 }
1568 }
1569 }
1571 public:
1572 G1ParScanThreadState(G1CollectedHeap* g1h, int queue_num);
1574 ~G1ParScanThreadState() {
1575 FREE_C_HEAP_ARRAY(size_t, _surviving_young_words_base);
1576 }
1578 RefToScanQueue* refs() { return _refs; }
1579 OverflowQueue* overflowed_refs() { return _overflowed_refs; }
1580 ageTable* age_table() { return &_age_table; }
1582 G1ParGCAllocBuffer* alloc_buffer(GCAllocPurpose purpose) {
1583 return &_alloc_buffers[purpose];
1584 }
1586 size_t alloc_buffer_waste() { return _alloc_buffer_waste; }
1587 size_t undo_waste() { return _undo_waste; }
1589 template <class T> void push_on_queue(T* ref) {
1590 assert(ref != NULL, "invariant");
1591 assert(has_partial_array_mask(ref) ||
1592 _g1h->obj_in_cs(oopDesc::load_decode_heap_oop(ref)), "invariant");
1593 #ifdef ASSERT
1594 if (has_partial_array_mask(ref)) {
1595 oop p = clear_partial_array_mask(ref);
1596 // Verify that we point into the CS
1597 assert(_g1h->obj_in_cs(p), "Should be in CS");
1598 }
1599 #endif
1600 if (!refs()->push(ref)) {
1601 overflowed_refs()->push(ref);
1602 IF_G1_DETAILED_STATS(note_overflow_push());
1603 } else {
1604 IF_G1_DETAILED_STATS(note_push());
1605 }
1606 }
1608 void pop_from_queue(StarTask& ref) {
1609 if (refs()->pop_local(ref)) {
1610 assert((oop*)ref != NULL, "pop_local() returned true");
1611 assert(UseCompressedOops || !ref.is_narrow(), "Error");
1612 assert(has_partial_array_mask((oop*)ref) ||
1613 _g1h->obj_in_cs(ref.is_narrow() ? oopDesc::load_decode_heap_oop((narrowOop*)ref)
1614 : oopDesc::load_decode_heap_oop((oop*)ref)),
1615 "invariant");
1616 IF_G1_DETAILED_STATS(note_pop());
1617 } else {
1618 StarTask null_task;
1619 ref = null_task;
1620 }
1621 }
1623 void pop_from_overflow_queue(StarTask& ref) {
1624 StarTask new_ref = overflowed_refs()->pop();
1625 assert((oop*)new_ref != NULL, "pop() from a local non-empty stack");
1626 assert(UseCompressedOops || !new_ref.is_narrow(), "Error");
1627 assert(has_partial_array_mask((oop*)new_ref) ||
1628 _g1h->obj_in_cs(new_ref.is_narrow() ? oopDesc::load_decode_heap_oop((narrowOop*)new_ref)
1629 : oopDesc::load_decode_heap_oop((oop*)new_ref)),
1630 "invariant");
1631 ref = new_ref;
1632 }
1634 int refs_to_scan() { return refs()->size(); }
1635 int overflowed_refs_to_scan() { return overflowed_refs()->length(); }
1637 template <class T> void update_rs(HeapRegion* from, T* p, int tid) {
1638 if (G1DeferredRSUpdate) {
1639 deferred_rs_update(from, p, tid);
1640 } else {
1641 immediate_rs_update(from, p, tid);
1642 }
1643 }
1645 HeapWord* allocate_slow(GCAllocPurpose purpose, size_t word_sz) {
1647 HeapWord* obj = NULL;
1648 if (word_sz * 100 <
1649 (size_t)(G1ParallelGCAllocBufferSize / HeapWordSize) *
1650 ParallelGCBufferWastePct) {
1651 G1ParGCAllocBuffer* alloc_buf = alloc_buffer(purpose);
1652 add_to_alloc_buffer_waste(alloc_buf->words_remaining());
1653 alloc_buf->retire(false, false);
1655 HeapWord* buf =
1656 _g1h->par_allocate_during_gc(purpose, G1ParallelGCAllocBufferSize / HeapWordSize);
1657 if (buf == NULL) return NULL; // Let caller handle allocation failure.
1658 // Otherwise.
1659 alloc_buf->set_buf(buf);
1661 obj = alloc_buf->allocate(word_sz);
1662 assert(obj != NULL, "buffer was definitely big enough...");
1663 } else {
1664 obj = _g1h->par_allocate_during_gc(purpose, word_sz);
1665 }
1666 return obj;
1667 }
1669 HeapWord* allocate(GCAllocPurpose purpose, size_t word_sz) {
1670 HeapWord* obj = alloc_buffer(purpose)->allocate(word_sz);
1671 if (obj != NULL) return obj;
1672 return allocate_slow(purpose, word_sz);
1673 }
1675 void undo_allocation(GCAllocPurpose purpose, HeapWord* obj, size_t word_sz) {
1676 if (alloc_buffer(purpose)->contains(obj)) {
1677 assert(alloc_buffer(purpose)->contains(obj + word_sz - 1),
1678 "should contain whole object");
1679 alloc_buffer(purpose)->undo_allocation(obj, word_sz);
1680 } else {
1681 CollectedHeap::fill_with_object(obj, word_sz);
1682 add_to_undo_waste(word_sz);
1683 }
1684 }
1686 void set_evac_failure_closure(OopsInHeapRegionClosure* evac_failure_cl) {
1687 _evac_failure_cl = evac_failure_cl;
1688 }
1689 OopsInHeapRegionClosure* evac_failure_closure() {
1690 return _evac_failure_cl;
1691 }
1693 void set_evac_closure(G1ParScanHeapEvacClosure* evac_cl) {
1694 _evac_cl = evac_cl;
1695 }
1697 void set_partial_scan_closure(G1ParScanPartialArrayClosure* partial_scan_cl) {
1698 _partial_scan_cl = partial_scan_cl;
1699 }
1701 int* hash_seed() { return &_hash_seed; }
1702 int queue_num() { return _queue_num; }
1704 int term_attempts() { return _term_attempts; }
1705 void note_term_attempt() { _term_attempts++; }
1707 #if G1_DETAILED_STATS
1708 int pushes() { return _pushes; }
1709 int pops() { return _pops; }
1710 int steals() { return _steals; }
1711 int steal_attempts() { return _steal_attempts; }
1712 int overflow_pushes() { return _overflow_pushes; }
1714 void note_push() { _pushes++; }
1715 void note_pop() { _pops++; }
1716 void note_steal() { _steals++; }
1717 void note_steal_attempt() { _steal_attempts++; }
1718 void note_overflow_push() { _overflow_pushes++; }
1719 #endif
1721 void start_strong_roots() {
1722 _start_strong_roots = os::elapsedTime();
1723 }
1724 void end_strong_roots() {
1725 _strong_roots_time += (os::elapsedTime() - _start_strong_roots);
1726 }
1727 double strong_roots_time() { return _strong_roots_time; }
1729 void start_term_time() {
1730 note_term_attempt();
1731 _start_term = os::elapsedTime();
1732 }
1733 void end_term_time() {
1734 _term_time += (os::elapsedTime() - _start_term);
1735 }
1736 double term_time() { return _term_time; }
1738 double elapsed() {
1739 return os::elapsedTime() - _start;
1740 }
1742 size_t* surviving_young_words() {
1743 // We add on to hide entry 0 which accumulates surviving words for
1744 // age -1 regions (i.e. non-young ones)
1745 return _surviving_young_words;
1746 }
1748 void retire_alloc_buffers() {
1749 for (int ap = 0; ap < GCAllocPurposeCount; ++ap) {
1750 size_t waste = _alloc_buffers[ap].words_remaining();
1751 add_to_alloc_buffer_waste(waste);
1752 _alloc_buffers[ap].retire(true, false);
1753 }
1754 }
1756 private:
1757 template <class T> void deal_with_reference(T* ref_to_scan) {
1758 if (has_partial_array_mask(ref_to_scan)) {
1759 _partial_scan_cl->do_oop_nv(ref_to_scan);
1760 } else {
1761 // Note: we can use "raw" versions of "region_containing" because
1762 // "obj_to_scan" is definitely in the heap, and is not in a
1763 // humongous region.
1764 HeapRegion* r = _g1h->heap_region_containing_raw(ref_to_scan);
1765 _evac_cl->set_region(r);
1766 _evac_cl->do_oop_nv(ref_to_scan);
1767 }
1768 }
1770 public:
1771 void trim_queue() {
1772 // I've replicated the loop twice, first to drain the overflow
1773 // queue, second to drain the task queue. This is better than
1774 // having a single loop, which checks both conditions and, inside
1775 // it, either pops the overflow queue or the task queue, as each
1776 // loop is tighter. Also, the decision to drain the overflow queue
1777 // first is not arbitrary, as the overflow queue is not visible
1778 // to the other workers, whereas the task queue is. So, we want to
1779 // drain the "invisible" entries first, while allowing the other
1780 // workers to potentially steal the "visible" entries.
1782 while (refs_to_scan() > 0 || overflowed_refs_to_scan() > 0) {
1783 while (overflowed_refs_to_scan() > 0) {
1784 StarTask ref_to_scan;
1785 assert((oop*)ref_to_scan == NULL, "Constructed above");
1786 pop_from_overflow_queue(ref_to_scan);
1787 // We shouldn't have pushed it on the queue if it was not
1788 // pointing into the CSet.
1789 assert((oop*)ref_to_scan != NULL, "Follows from inner loop invariant");
1790 if (ref_to_scan.is_narrow()) {
1791 assert(UseCompressedOops, "Error");
1792 narrowOop* p = (narrowOop*)ref_to_scan;
1793 assert(!has_partial_array_mask(p) &&
1794 _g1h->obj_in_cs(oopDesc::load_decode_heap_oop(p)), "sanity");
1795 deal_with_reference(p);
1796 } else {
1797 oop* p = (oop*)ref_to_scan;
1798 assert((has_partial_array_mask(p) && _g1h->obj_in_cs(clear_partial_array_mask(p))) ||
1799 _g1h->obj_in_cs(oopDesc::load_decode_heap_oop(p)), "sanity");
1800 deal_with_reference(p);
1801 }
1802 }
1804 while (refs_to_scan() > 0) {
1805 StarTask ref_to_scan;
1806 assert((oop*)ref_to_scan == NULL, "Constructed above");
1807 pop_from_queue(ref_to_scan);
1808 if ((oop*)ref_to_scan != NULL) {
1809 if (ref_to_scan.is_narrow()) {
1810 assert(UseCompressedOops, "Error");
1811 narrowOop* p = (narrowOop*)ref_to_scan;
1812 assert(!has_partial_array_mask(p) &&
1813 _g1h->obj_in_cs(oopDesc::load_decode_heap_oop(p)), "sanity");
1814 deal_with_reference(p);
1815 } else {
1816 oop* p = (oop*)ref_to_scan;
1817 assert((has_partial_array_mask(p) && _g1h->obj_in_cs(clear_partial_array_mask(p))) ||
1818 _g1h->obj_in_cs(oopDesc::load_decode_heap_oop(p)), "sanity");
1819 deal_with_reference(p);
1820 }
1821 }
1822 }
1823 }
1824 }
1825 };