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 // Sparse remembered set for a heap region (the "owning" region). Maps
26 // indices of other regions to short sequences of cards in the other region
27 // that might contain pointers into the owner region.
29 // These tables only expand while they are accessed in parallel --
30 // deletions may be done in single-threaded code. This allows us to allow
31 // unsynchronized reads/iterations, as long as expansions caused by
32 // insertions only enqueue old versions for deletions, but do not delete
33 // old versions synchronously.
35 class SparsePRTEntry: public CHeapObj {
36 public:
37 enum SomePublicConstants {
38 NullEntry = -1,
39 UnrollFactor = 4
40 };
41 private:
42 RegionIdx_t _region_ind;
43 int _next_index;
44 CardIdx_t _cards[1];
45 // WARNING: Don't put any data members beyond this line. Card array has, in fact, variable length.
46 // It should always be the last data member.
47 public:
48 // Returns the size of the entry, used for entry allocation.
49 static size_t size() { return sizeof(SparsePRTEntry) + sizeof(CardIdx_t) * (cards_num() - 1); }
50 // Returns the size of the card array.
51 static int cards_num() {
52 // The number of cards should be a multiple of 4, because that's our current
53 // unrolling factor.
54 static const int s = MAX2<int>(G1RSetSparseRegionEntries & ~(UnrollFactor - 1), UnrollFactor);
55 return s;
56 }
58 // Set the region_ind to the given value, and delete all cards.
59 inline void init(RegionIdx_t region_ind);
61 RegionIdx_t r_ind() const { return _region_ind; }
62 bool valid_entry() const { return r_ind() >= 0; }
63 void set_r_ind(RegionIdx_t rind) { _region_ind = rind; }
65 int next_index() const { return _next_index; }
66 int* next_index_addr() { return &_next_index; }
67 void set_next_index(int ni) { _next_index = ni; }
69 // Returns "true" iff the entry contains the given card index.
70 inline bool contains_card(CardIdx_t card_index) const;
72 // Returns the number of non-NULL card entries.
73 inline int num_valid_cards() const;
75 // Requires that the entry not contain the given card index. If there is
76 // space available, add the given card index to the entry and return
77 // "true"; otherwise, return "false" to indicate that the entry is full.
78 enum AddCardResult {
79 overflow,
80 found,
81 added
82 };
83 inline AddCardResult add_card(CardIdx_t card_index);
85 // Copy the current entry's cards into "cards".
86 inline void copy_cards(CardIdx_t* cards) const;
87 // Copy the current entry's cards into the "_card" array of "e."
88 inline void copy_cards(SparsePRTEntry* e) const;
90 inline CardIdx_t card(int i) const { return _cards[i]; }
91 };
94 class RSHashTable : public CHeapObj {
96 friend class RSHashTableIter;
98 enum SomePrivateConstants {
99 NullEntry = -1
100 };
102 size_t _capacity;
103 size_t _capacity_mask;
104 size_t _occupied_entries;
105 size_t _occupied_cards;
107 SparsePRTEntry* _entries;
108 int* _buckets;
109 int _free_region;
110 int _free_list;
112 // Requires that the caller hold a lock preventing parallel modifying
113 // operations, and that the the table be less than completely full. If
114 // an entry for "region_ind" is already in the table, finds it and
115 // returns its address; otherwise returns "NULL."
116 SparsePRTEntry* entry_for_region_ind(RegionIdx_t region_ind) const;
118 // Requires that the caller hold a lock preventing parallel modifying
119 // operations, and that the the table be less than completely full. If
120 // an entry for "region_ind" is already in the table, finds it and
121 // returns its address; otherwise allocates, initializes, inserts and
122 // returns a new entry for "region_ind".
123 SparsePRTEntry* entry_for_region_ind_create(RegionIdx_t region_ind);
125 // Returns the index of the next free entry in "_entries".
126 int alloc_entry();
127 // Declares the entry "fi" to be free. (It must have already been
128 // deleted from any bucket lists.
129 void free_entry(int fi);
131 public:
132 RSHashTable(size_t capacity);
133 ~RSHashTable();
135 // Attempts to ensure that the given card_index in the given region is in
136 // the sparse table. If successful (because the card was already
137 // present, or because it was successfullly added) returns "true".
138 // Otherwise, returns "false" to indicate that the addition would
139 // overflow the entry for the region. The caller must transfer these
140 // entries to a larger-capacity representation.
141 bool add_card(RegionIdx_t region_id, CardIdx_t card_index);
143 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards);
145 bool delete_entry(RegionIdx_t region_id);
147 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const;
149 void add_entry(SparsePRTEntry* e);
151 SparsePRTEntry* get_entry(RegionIdx_t region_id);
153 void clear();
155 size_t capacity() const { return _capacity; }
156 size_t capacity_mask() const { return _capacity_mask; }
157 size_t occupied_entries() const { return _occupied_entries; }
158 size_t occupied_cards() const { return _occupied_cards; }
159 size_t mem_size() const;
161 SparsePRTEntry* entry(int i) const { return (SparsePRTEntry*)((char*)_entries + SparsePRTEntry::size() * i); }
163 void print();
164 };
166 // ValueObj because will be embedded in HRRS iterator.
167 class RSHashTableIter VALUE_OBJ_CLASS_SPEC {
168 int _tbl_ind; // [-1, 0.._rsht->_capacity)
169 int _bl_ind; // [-1, 0.._rsht->_capacity)
170 short _card_ind; // [0..SparsePRTEntry::cards_num())
171 RSHashTable* _rsht;
172 size_t _heap_bot_card_ind;
174 // If the bucket list pointed to by _bl_ind contains a card, sets
175 // _bl_ind to the index of that entry, and returns the card.
176 // Otherwise, returns SparseEntry::NullEntry.
177 CardIdx_t find_first_card_in_list();
179 // Computes the proper card index for the card whose offset in the
180 // current region (as indicated by _bl_ind) is "ci".
181 // This is subject to errors when there is iteration concurrent with
182 // modification, but these errors should be benign.
183 size_t compute_card_ind(CardIdx_t ci);
185 public:
186 RSHashTableIter(size_t heap_bot_card_ind) :
187 _tbl_ind(RSHashTable::NullEntry),
188 _bl_ind(RSHashTable::NullEntry),
189 _card_ind((SparsePRTEntry::cards_num() - 1)),
190 _rsht(NULL),
191 _heap_bot_card_ind(heap_bot_card_ind)
192 {}
194 void init(RSHashTable* rsht) {
195 _rsht = rsht;
196 _tbl_ind = -1; // So that first increment gets to 0.
197 _bl_ind = RSHashTable::NullEntry;
198 _card_ind = (SparsePRTEntry::cards_num() - 1);
199 }
201 bool has_next(size_t& card_index);
202 };
204 // Concurrent accesss to a SparsePRT must be serialized by some external
205 // mutex.
207 class SparsePRTIter;
209 class SparsePRT VALUE_OBJ_CLASS_SPEC {
210 // Iterations are done on the _cur hash table, since they only need to
211 // see entries visible at the start of a collection pause.
212 // All other operations are done using the _next hash table.
213 RSHashTable* _cur;
214 RSHashTable* _next;
216 HeapRegion* _hr;
218 enum SomeAdditionalPrivateConstants {
219 InitialCapacity = 16
220 };
222 void expand();
224 bool _expanded;
226 bool expanded() { return _expanded; }
227 void set_expanded(bool b) { _expanded = b; }
229 SparsePRT* _next_expanded;
231 SparsePRT* next_expanded() { return _next_expanded; }
232 void set_next_expanded(SparsePRT* nxt) { _next_expanded = nxt; }
234 static SparsePRT* _head_expanded_list;
236 public:
237 SparsePRT(HeapRegion* hr);
239 ~SparsePRT();
241 size_t occupied() const { return _next->occupied_cards(); }
242 size_t mem_size() const;
244 // Attempts to ensure that the given card_index in the given region is in
245 // the sparse table. If successful (because the card was already
246 // present, or because it was successfullly added) returns "true".
247 // Otherwise, returns "false" to indicate that the addition would
248 // overflow the entry for the region. The caller must transfer these
249 // entries to a larger-capacity representation.
250 bool add_card(RegionIdx_t region_id, CardIdx_t card_index);
252 // If the table hold an entry for "region_ind", Copies its
253 // cards into "cards", which must be an array of length at least
254 // "SparePRTEntry::cards_num()", and returns "true"; otherwise,
255 // returns "false".
256 bool get_cards(RegionIdx_t region_ind, CardIdx_t* cards);
258 // Return the pointer to the entry associated with the given region.
259 SparsePRTEntry* get_entry(RegionIdx_t region_ind);
261 // If there is an entry for "region_ind", removes it and return "true";
262 // otherwise returns "false."
263 bool delete_entry(RegionIdx_t region_ind);
265 // Clear the table, and reinitialize to initial capacity.
266 void clear();
268 // Ensure that "_cur" and "_next" point to the same table.
269 void cleanup();
271 // Clean up all tables on the expanded list. Called single threaded.
272 static void cleanup_all();
273 RSHashTable* cur() const { return _cur; }
275 void init_iterator(SparsePRTIter* sprt_iter);
277 static void add_to_expanded_list(SparsePRT* sprt);
278 static SparsePRT* get_from_expanded_list();
280 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const {
281 return _next->contains_card(region_id, card_index);
282 }
284 #if 0
285 void verify_is_cleared();
286 void print();
287 #endif
288 };
291 class SparsePRTIter: public /* RSHashTable:: */RSHashTableIter {
292 public:
293 SparsePRTIter(size_t heap_bot_card_ind) :
294 /* RSHashTable:: */RSHashTableIter(heap_bot_card_ind)
295 {}
297 void init(const SparsePRT* sprt) {
298 RSHashTableIter::init(sprt->cur());
299 }
300 bool has_next(size_t& card_index) {
301 return RSHashTableIter::has_next(card_index);
302 }
303 };