Mon, 02 Aug 2010 12:51:43 -0700
6814437: G1: remove the _new_refs array
Summary: The per-worker _new_refs array is used to hold references that point into the collection set. It is populated during RSet updating and subsequently processed. In the event of an evacuation failure it processed again to recreate the RSets of regions in the collection set. Remove the per-worker _new_refs array by processing the references directly. Use a DirtyCardQueue to hold the cards containing the references so that the RSets of regions in the collection set can be recreated when handling an evacuation failure.
Reviewed-by: iveresov, jmasa, tonyp
1 /*
2 * Copyright (c) 2001, 2009, 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 // Remembered set for a heap region. Represent a set of "cards" that
26 // contain pointers into the owner heap region. Cards are defined somewhat
27 // abstractly, in terms of what the "BlockOffsetTable" in use can parse.
29 class G1CollectedHeap;
30 class G1BlockOffsetSharedArray;
31 class HeapRegion;
32 class HeapRegionRemSetIterator;
33 class PosParPRT;
34 class SparsePRT;
37 // The "_coarse_map" is a bitmap with one bit for each region, where set
38 // bits indicate that the corresponding region may contain some pointer
39 // into the owning region.
41 // The "_fine_grain_entries" array is an open hash table of PerRegionTables
42 // (PRTs), indicating regions for which we're keeping the RS as a set of
43 // cards. The strategy is to cap the size of the fine-grain table,
44 // deleting an entry and setting the corresponding coarse-grained bit when
45 // we would overflow this cap.
47 // We use a mixture of locking and lock-free techniques here. We allow
48 // threads to locate PRTs without locking, but threads attempting to alter
49 // a bucket list obtain a lock. This means that any failing attempt to
50 // find a PRT must be retried with the lock. It might seem dangerous that
51 // a read can find a PRT that is concurrently deleted. This is all right,
52 // because:
53 //
54 // 1) We only actually free PRT's at safe points (though we reuse them at
55 // other times).
56 // 2) We find PRT's in an attempt to add entries. If a PRT is deleted,
57 // it's _coarse_map bit is set, so the that we were attempting to add
58 // is represented. If a deleted PRT is re-used, a thread adding a bit,
59 // thinking the PRT is for a different region, does no harm.
61 class OtherRegionsTable VALUE_OBJ_CLASS_SPEC {
62 friend class HeapRegionRemSetIterator;
64 G1CollectedHeap* _g1h;
65 Mutex _m;
66 HeapRegion* _hr;
68 // These are protected by "_m".
69 BitMap _coarse_map;
70 size_t _n_coarse_entries;
71 static jint _n_coarsenings;
73 PosParPRT** _fine_grain_regions;
74 size_t _n_fine_entries;
76 #define SAMPLE_FOR_EVICTION 1
77 #if SAMPLE_FOR_EVICTION
78 size_t _fine_eviction_start;
79 static size_t _fine_eviction_stride;
80 static size_t _fine_eviction_sample_size;
81 #endif
83 SparsePRT _sparse_table;
85 // These are static after init.
86 static size_t _max_fine_entries;
87 static size_t _mod_max_fine_entries_mask;
89 // Requires "prt" to be the first element of the bucket list appropriate
90 // for "hr". If this list contains an entry for "hr", return it,
91 // otherwise return "NULL".
92 PosParPRT* find_region_table(size_t ind, HeapRegion* hr) const;
94 // Find, delete, and return a candidate PosParPRT, if any exists,
95 // adding the deleted region to the coarse bitmap. Requires the caller
96 // to hold _m, and the fine-grain table to be full.
97 PosParPRT* delete_region_table();
99 // If a PRT for "hr" is in the bucket list indicated by "ind" (which must
100 // be the correct index for "hr"), delete it and return true; else return
101 // false.
102 bool del_single_region_table(size_t ind, HeapRegion* hr);
104 static jint _cache_probes;
105 static jint _cache_hits;
107 // Indexed by thread X heap region, to minimize thread contention.
108 static int** _from_card_cache;
109 static size_t _from_card_cache_max_regions;
110 static size_t _from_card_cache_mem_size;
112 public:
113 OtherRegionsTable(HeapRegion* hr);
115 HeapRegion* hr() const { return _hr; }
117 // For now. Could "expand" some tables in the future, so that this made
118 // sense.
119 void add_reference(OopOrNarrowOopStar from, int tid);
121 void add_reference(OopOrNarrowOopStar from) {
122 return add_reference(from, 0);
123 }
125 // Removes any entries shown by the given bitmaps to contain only dead
126 // objects.
127 void scrub(CardTableModRefBS* ctbs, BitMap* region_bm, BitMap* card_bm);
129 // Not const because it takes a lock.
130 size_t occupied() const;
131 size_t occ_fine() const;
132 size_t occ_coarse() const;
133 size_t occ_sparse() const;
135 static jint n_coarsenings() { return _n_coarsenings; }
137 // Returns size in bytes.
138 // Not const because it takes a lock.
139 size_t mem_size() const;
140 static size_t static_mem_size();
141 static size_t fl_mem_size();
143 bool contains_reference(OopOrNarrowOopStar from) const;
144 bool contains_reference_locked(OopOrNarrowOopStar from) const;
146 void clear();
148 // Specifically clear the from_card_cache.
149 void clear_fcc();
151 // "from_hr" is being cleared; remove any entries from it.
152 void clear_incoming_entry(HeapRegion* from_hr);
154 // Declare the heap size (in # of regions) to the OtherRegionsTable.
155 // (Uses it to initialize from_card_cache).
156 static void init_from_card_cache(size_t max_regions);
158 // Declares that only regions i s.t. 0 <= i < new_n_regs are in use.
159 // Make sure any entries for higher regions are invalid.
160 static void shrink_from_card_cache(size_t new_n_regs);
162 static void print_from_card_cache();
164 };
167 class HeapRegionRemSet : public CHeapObj {
168 friend class VMStructs;
169 friend class HeapRegionRemSetIterator;
171 public:
172 enum Event {
173 Event_EvacStart, Event_EvacEnd, Event_RSUpdateEnd
174 };
176 private:
177 G1BlockOffsetSharedArray* _bosa;
178 G1BlockOffsetSharedArray* bosa() const { return _bosa; }
180 OtherRegionsTable _other_regions;
182 enum ParIterState { Unclaimed, Claimed, Complete };
183 volatile ParIterState _iter_state;
184 volatile jlong _iter_claimed;
186 // Unused unless G1RecordHRRSOops is true.
188 static const int MaxRecorded = 1000000;
189 static OopOrNarrowOopStar* _recorded_oops;
190 static HeapWord** _recorded_cards;
191 static HeapRegion** _recorded_regions;
192 static int _n_recorded;
194 static const int MaxRecordedEvents = 1000;
195 static Event* _recorded_events;
196 static int* _recorded_event_index;
197 static int _n_recorded_events;
199 static void print_event(outputStream* str, Event evnt);
201 public:
202 HeapRegionRemSet(G1BlockOffsetSharedArray* bosa,
203 HeapRegion* hr);
205 static int num_par_rem_sets();
206 static void setup_remset_size();
208 HeapRegion* hr() const {
209 return _other_regions.hr();
210 }
212 size_t occupied() const {
213 return _other_regions.occupied();
214 }
215 size_t occ_fine() const {
216 return _other_regions.occ_fine();
217 }
218 size_t occ_coarse() const {
219 return _other_regions.occ_coarse();
220 }
221 size_t occ_sparse() const {
222 return _other_regions.occ_sparse();
223 }
225 static jint n_coarsenings() { return OtherRegionsTable::n_coarsenings(); }
227 /* Used in the sequential case. Returns "true" iff this addition causes
228 the size limit to be reached. */
229 void add_reference(OopOrNarrowOopStar from) {
230 _other_regions.add_reference(from);
231 }
233 /* Used in the parallel case. Returns "true" iff this addition causes
234 the size limit to be reached. */
235 void add_reference(OopOrNarrowOopStar from, int tid) {
236 _other_regions.add_reference(from, tid);
237 }
239 // Removes any entries shown by the given bitmaps to contain only dead
240 // objects.
241 void scrub(CardTableModRefBS* ctbs, BitMap* region_bm, BitMap* card_bm);
243 // The region is being reclaimed; clear its remset, and any mention of
244 // entries for this region in other remsets.
245 void clear();
247 // Forget any entries due to pointers from "from_hr".
248 void clear_incoming_entry(HeapRegion* from_hr) {
249 _other_regions.clear_incoming_entry(from_hr);
250 }
252 #if 0
253 virtual void cleanup() = 0;
254 #endif
256 // Should be called from single-threaded code.
257 void init_for_par_iteration();
258 // Attempt to claim the region. Returns true iff this call caused an
259 // atomic transition from Unclaimed to Claimed.
260 bool claim_iter();
261 // Sets the iteration state to "complete".
262 void set_iter_complete();
263 // Returns "true" iff the region's iteration is complete.
264 bool iter_is_complete();
266 // Support for claiming blocks of cards during iteration
267 void set_iter_claimed(size_t x) { _iter_claimed = (jlong)x; }
268 size_t iter_claimed() const { return (size_t)_iter_claimed; }
269 // Claim the next block of cards
270 size_t iter_claimed_next(size_t step) {
271 size_t current, next;
272 do {
273 current = iter_claimed();
274 next = current + step;
275 } while (Atomic::cmpxchg((jlong)next, &_iter_claimed, (jlong)current) != (jlong)current);
276 return current;
277 }
279 // Initialize the given iterator to iterate over this rem set.
280 void init_iterator(HeapRegionRemSetIterator* iter) const;
282 #if 0
283 // Apply the "do_card" method to the start address of every card in the
284 // rem set. Returns false if some application of the closure aborted.
285 virtual bool card_iterate(CardClosure* iter) = 0;
286 #endif
288 // The actual # of bytes this hr_remset takes up.
289 size_t mem_size() {
290 return _other_regions.mem_size()
291 // This correction is necessary because the above includes the second
292 // part.
293 + sizeof(this) - sizeof(OtherRegionsTable);
294 }
296 // Returns the memory occupancy of all static data structures associated
297 // with remembered sets.
298 static size_t static_mem_size() {
299 return OtherRegionsTable::static_mem_size();
300 }
302 // Returns the memory occupancy of all free_list data structures associated
303 // with remembered sets.
304 static size_t fl_mem_size() {
305 return OtherRegionsTable::fl_mem_size();
306 }
308 bool contains_reference(OopOrNarrowOopStar from) const {
309 return _other_regions.contains_reference(from);
310 }
311 void print() const;
313 // Called during a stop-world phase to perform any deferred cleanups.
314 // The second version may be called by parallel threads after then finish
315 // collection work.
316 static void cleanup();
317 static void par_cleanup();
319 // Declare the heap size (in # of regions) to the HeapRegionRemSet(s).
320 // (Uses it to initialize from_card_cache).
321 static void init_heap(size_t max_regions) {
322 OtherRegionsTable::init_from_card_cache(max_regions);
323 }
325 // Declares that only regions i s.t. 0 <= i < new_n_regs are in use.
326 static void shrink_heap(size_t new_n_regs) {
327 OtherRegionsTable::shrink_from_card_cache(new_n_regs);
328 }
330 #ifndef PRODUCT
331 static void print_from_card_cache() {
332 OtherRegionsTable::print_from_card_cache();
333 }
334 #endif
336 static void record(HeapRegion* hr, OopOrNarrowOopStar f);
337 static void print_recorded();
338 static void record_event(Event evnt);
340 // Run unit tests.
341 #ifndef PRODUCT
342 static void test();
343 #endif
345 };
347 class HeapRegionRemSetIterator : public CHeapObj {
349 // The region over which we're iterating.
350 const HeapRegionRemSet* _hrrs;
352 // Local caching of HRRS fields.
353 const BitMap* _coarse_map;
354 PosParPRT** _fine_grain_regions;
356 G1BlockOffsetSharedArray* _bosa;
357 G1CollectedHeap* _g1h;
359 // The number yielded since initialization.
360 size_t _n_yielded_fine;
361 size_t _n_yielded_coarse;
362 size_t _n_yielded_sparse;
364 // If true we're iterating over the coarse table; if false the fine
365 // table.
366 enum IterState {
367 Sparse,
368 Fine,
369 Coarse
370 };
371 IterState _is;
373 // In both kinds of iteration, heap offset of first card of current
374 // region.
375 size_t _cur_region_card_offset;
376 // Card offset within cur region.
377 size_t _cur_region_cur_card;
379 // Coarse table iteration fields:
381 // Current region index;
382 int _coarse_cur_region_index;
383 int _coarse_cur_region_cur_card;
385 bool coarse_has_next(size_t& card_index);
387 // Fine table iteration fields:
389 // Index of bucket-list we're working on.
390 int _fine_array_index;
391 // Per Region Table we're doing within current bucket list.
392 PosParPRT* _fine_cur_prt;
394 /* SparsePRT::*/ SparsePRTIter _sparse_iter;
396 void fine_find_next_non_null_prt();
398 bool fine_has_next();
399 bool fine_has_next(size_t& card_index);
401 public:
402 // We require an iterator to be initialized before use, so the
403 // constructor does little.
404 HeapRegionRemSetIterator();
406 void initialize(const HeapRegionRemSet* hrrs);
408 // If there remains one or more cards to be yielded, returns true and
409 // sets "card_index" to one of those cards (which is then considered
410 // yielded.) Otherwise, returns false (and leaves "card_index"
411 // undefined.)
412 bool has_next(size_t& card_index);
414 size_t n_yielded_fine() { return _n_yielded_fine; }
415 size_t n_yielded_coarse() { return _n_yielded_coarse; }
416 size_t n_yielded_sparse() { return _n_yielded_sparse; }
417 size_t n_yielded() {
418 return n_yielded_fine() + n_yielded_coarse() + n_yielded_sparse();
419 }
420 };
422 #if 0
423 class CardClosure: public Closure {
424 public:
425 virtual void do_card(HeapWord* card_start) = 0;
426 };
428 #endif