Mercurial > hg > truffle
comparison src/share/vm/gc_implementation/g1/sparsePRT.hpp @ 807:d44bdab1c03d
6843694: G1: assert(index < _vs.committed_size(),"bad index"), g1BlockOffsetTable.inline.hpp:55
Summary: For heaps larger than 32Gb, the number of heap regions overflows the data type used to hold the region index in the SparsePRT structure. Changed the region indexes, card indexes, and RSet hash table buckets to ints and added some size overflow guarantees.
Reviewed-by: ysr, tonyp
author | johnc |
---|---|
date | Thu, 11 Jun 2009 17:19:33 -0700 |
parents | 7bb995fbd3c0 |
children | 2c79770d1f6e |
comparison
equal
deleted
inserted
replaced
806:821269eca479 | 807:d44bdab1c03d |
---|---|
33 // old versions synchronously. | 33 // old versions synchronously. |
34 | 34 |
35 | 35 |
36 class SparsePRTEntry: public CHeapObj { | 36 class SparsePRTEntry: public CHeapObj { |
37 public: | 37 public: |
38 | |
38 enum SomePublicConstants { | 39 enum SomePublicConstants { |
39 CardsPerEntry = (short)4, | 40 CardsPerEntry = 4, |
40 NullEntry = (short)-1, | 41 NullEntry = -1 |
41 DeletedEntry = (short)-2 | |
42 }; | 42 }; |
43 | 43 |
44 private: | 44 private: |
45 short _region_ind; | 45 RegionIdx_t _region_ind; |
46 short _next_index; | 46 int _next_index; |
47 short _cards[CardsPerEntry]; | 47 CardIdx_t _cards[CardsPerEntry]; |
48 | 48 |
49 public: | 49 public: |
50 | 50 |
51 // Set the region_ind to the given value, and delete all cards. | 51 // Set the region_ind to the given value, and delete all cards. |
52 inline void init(short region_ind); | 52 inline void init(RegionIdx_t region_ind); |
53 | 53 |
54 short r_ind() const { return _region_ind; } | 54 RegionIdx_t r_ind() const { return _region_ind; } |
55 bool valid_entry() const { return r_ind() >= 0; } | 55 bool valid_entry() const { return r_ind() >= 0; } |
56 void set_r_ind(short rind) { _region_ind = rind; } | 56 void set_r_ind(RegionIdx_t rind) { _region_ind = rind; } |
57 | 57 |
58 short next_index() const { return _next_index; } | 58 int next_index() const { return _next_index; } |
59 short* next_index_addr() { return &_next_index; } | 59 int* next_index_addr() { return &_next_index; } |
60 void set_next_index(short ni) { _next_index = ni; } | 60 void set_next_index(int ni) { _next_index = ni; } |
61 | 61 |
62 // Returns "true" iff the entry contains the given card index. | 62 // Returns "true" iff the entry contains the given card index. |
63 inline bool contains_card(short card_index) const; | 63 inline bool contains_card(CardIdx_t card_index) const; |
64 | 64 |
65 // Returns the number of non-NULL card entries. | 65 // Returns the number of non-NULL card entries. |
66 inline int num_valid_cards() const; | 66 inline int num_valid_cards() const; |
67 | 67 |
68 // Requires that the entry not contain the given card index. If there is | 68 // Requires that the entry not contain the given card index. If there is |
71 enum AddCardResult { | 71 enum AddCardResult { |
72 overflow, | 72 overflow, |
73 found, | 73 found, |
74 added | 74 added |
75 }; | 75 }; |
76 inline AddCardResult add_card(short card_index); | 76 inline AddCardResult add_card(CardIdx_t card_index); |
77 | 77 |
78 // Copy the current entry's cards into "cards". | 78 // Copy the current entry's cards into "cards". |
79 inline void copy_cards(short* cards) const; | 79 inline void copy_cards(CardIdx_t* cards) const; |
80 // Copy the current entry's cards into the "_card" array of "e." | 80 // Copy the current entry's cards into the "_card" array of "e." |
81 inline void copy_cards(SparsePRTEntry* e) const; | 81 inline void copy_cards(SparsePRTEntry* e) const; |
82 | 82 |
83 inline short card(int i) const { return _cards[i]; } | 83 inline CardIdx_t card(int i) const { return _cards[i]; } |
84 }; | 84 }; |
85 | 85 |
86 | 86 |
87 class RSHashTable : public CHeapObj { | 87 class RSHashTable : public CHeapObj { |
88 | 88 |
96 size_t _capacity_mask; | 96 size_t _capacity_mask; |
97 size_t _occupied_entries; | 97 size_t _occupied_entries; |
98 size_t _occupied_cards; | 98 size_t _occupied_cards; |
99 | 99 |
100 SparsePRTEntry* _entries; | 100 SparsePRTEntry* _entries; |
101 short* _buckets; | 101 int* _buckets; |
102 short _free_region; | 102 int _free_region; |
103 short _free_list; | 103 int _free_list; |
104 | 104 |
105 static RSHashTable* _head_deleted_list; | 105 static RSHashTable* _head_deleted_list; |
106 RSHashTable* _next_deleted; | 106 RSHashTable* _next_deleted; |
107 RSHashTable* next_deleted() { return _next_deleted; } | 107 RSHashTable* next_deleted() { return _next_deleted; } |
108 void set_next_deleted(RSHashTable* rsht) { _next_deleted = rsht; } | 108 void set_next_deleted(RSHashTable* rsht) { _next_deleted = rsht; } |
111 | 111 |
112 // Requires that the caller hold a lock preventing parallel modifying | 112 // Requires that the caller hold a lock preventing parallel modifying |
113 // operations, and that the the table be less than completely full. If | 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 | 114 // an entry for "region_ind" is already in the table, finds it and |
115 // returns its address; otherwise returns "NULL." | 115 // returns its address; otherwise returns "NULL." |
116 SparsePRTEntry* entry_for_region_ind(short region_ind) const; | 116 SparsePRTEntry* entry_for_region_ind(RegionIdx_t region_ind) const; |
117 | 117 |
118 // Requires that the caller hold a lock preventing parallel modifying | 118 // Requires that the caller hold a lock preventing parallel modifying |
119 // operations, and that the the table be less than completely full. If | 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 | 120 // an entry for "region_ind" is already in the table, finds it and |
121 // returns its address; otherwise allocates, initializes, inserts and | 121 // returns its address; otherwise allocates, initializes, inserts and |
122 // returns a new entry for "region_ind". | 122 // returns a new entry for "region_ind". |
123 SparsePRTEntry* entry_for_region_ind_create(short region_ind); | 123 SparsePRTEntry* entry_for_region_ind_create(RegionIdx_t region_ind); |
124 | 124 |
125 // Returns the index of the next free entry in "_entries". | 125 // Returns the index of the next free entry in "_entries". |
126 short alloc_entry(); | 126 int alloc_entry(); |
127 // Declares the entry "fi" to be free. (It must have already been | 127 // Declares the entry "fi" to be free. (It must have already been |
128 // deleted from any bucket lists. | 128 // deleted from any bucket lists. |
129 void free_entry(short fi); | 129 void free_entry(int fi); |
130 | 130 |
131 public: | 131 public: |
132 RSHashTable(size_t capacity); | 132 RSHashTable(size_t capacity); |
133 ~RSHashTable(); | 133 ~RSHashTable(); |
134 | 134 |
136 // the sparse table. If successful (because the card was already | 136 // the sparse table. If successful (because the card was already |
137 // present, or because it was successfullly added) returns "true". | 137 // present, or because it was successfullly added) returns "true". |
138 // Otherwise, returns "false" to indicate that the addition would | 138 // Otherwise, returns "false" to indicate that the addition would |
139 // overflow the entry for the region. The caller must transfer these | 139 // overflow the entry for the region. The caller must transfer these |
140 // entries to a larger-capacity representation. | 140 // entries to a larger-capacity representation. |
141 bool add_card(short region_id, short card_index); | 141 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
142 | 142 |
143 bool get_cards(short region_id, short* cards); | 143 bool get_cards(RegionIdx_t region_id, CardIdx_t* cards); |
144 bool delete_entry(short region_id); | 144 bool delete_entry(RegionIdx_t region_id); |
145 | 145 |
146 bool contains_card(short region_id, short card_index) const; | 146 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const; |
147 | 147 |
148 void add_entry(SparsePRTEntry* e); | 148 void add_entry(SparsePRTEntry* e); |
149 | 149 |
150 void clear(); | 150 void clear(); |
151 | 151 |
160 | 160 |
161 void print(); | 161 void print(); |
162 | 162 |
163 static void add_to_deleted_list(RSHashTable* rsht); | 163 static void add_to_deleted_list(RSHashTable* rsht); |
164 static RSHashTable* get_from_deleted_list(); | 164 static RSHashTable* get_from_deleted_list(); |
165 | 165 }; |
166 | 166 |
167 }; | 167 // ValueObj because will be embedded in HRRS iterator. |
168 | |
169 // ValueObj because will be embedded in HRRS iterator. | |
170 class RSHashTableIter VALUE_OBJ_CLASS_SPEC { | 168 class RSHashTableIter VALUE_OBJ_CLASS_SPEC { |
171 short _tbl_ind; | 169 int _tbl_ind; // [-1, 0.._rsht->_capacity) |
172 short _bl_ind; | 170 int _bl_ind; // [-1, 0.._rsht->_capacity) |
173 short _card_ind; | 171 short _card_ind; // [0..CardsPerEntry) |
174 RSHashTable* _rsht; | 172 RSHashTable* _rsht; |
175 size_t _heap_bot_card_ind; | 173 size_t _heap_bot_card_ind; |
176 | 174 |
177 enum SomePrivateConstants { | 175 enum SomePrivateConstants { |
178 CardsPerRegion = HeapRegion::GrainBytes >> CardTableModRefBS::card_shift | 176 CardsPerRegion = HeapRegion::GrainBytes >> CardTableModRefBS::card_shift |
179 }; | 177 }; |
180 | 178 |
181 // If the bucket list pointed to by _bl_ind contains a card, sets | 179 // If the bucket list pointed to by _bl_ind contains a card, sets |
182 // _bl_ind to the index of that entry, and returns the card. | 180 // _bl_ind to the index of that entry, and returns the card. |
183 // Otherwise, returns SparseEntry::NullEnty. | 181 // Otherwise, returns SparseEntry::NullEntry. |
184 short find_first_card_in_list(); | 182 CardIdx_t find_first_card_in_list(); |
185 // Computes the proper card index for the card whose offset in the | 183 |
186 // current region (as indicated by _bl_ind) is "ci". | 184 // Computes the proper card index for the card whose offset in the |
187 // This is subject to errors when there is iteration concurrent with | 185 // current region (as indicated by _bl_ind) is "ci". |
188 // modification, but these errors should be benign. | 186 // This is subject to errors when there is iteration concurrent with |
189 size_t compute_card_ind(short ci); | 187 // modification, but these errors should be benign. |
190 | 188 size_t compute_card_ind(CardIdx_t ci); |
191 public: | 189 |
192 RSHashTableIter(size_t heap_bot_card_ind) : | 190 public: |
193 _tbl_ind(RSHashTable::NullEntry), | 191 RSHashTableIter(size_t heap_bot_card_ind) : |
194 _bl_ind(RSHashTable::NullEntry), | 192 _tbl_ind(RSHashTable::NullEntry), |
195 _card_ind((SparsePRTEntry::CardsPerEntry-1)), | 193 _bl_ind(RSHashTable::NullEntry), |
196 _rsht(NULL), | 194 _card_ind((SparsePRTEntry::CardsPerEntry-1)), |
197 _heap_bot_card_ind(heap_bot_card_ind) | 195 _rsht(NULL), |
198 {} | 196 _heap_bot_card_ind(heap_bot_card_ind) |
199 | 197 {} |
200 void init(RSHashTable* rsht) { | 198 |
201 _rsht = rsht; | 199 void init(RSHashTable* rsht) { |
202 _tbl_ind = -1; // So that first increment gets to 0. | 200 _rsht = rsht; |
203 _bl_ind = RSHashTable::NullEntry; | 201 _tbl_ind = -1; // So that first increment gets to 0. |
204 _card_ind = (SparsePRTEntry::CardsPerEntry-1); | 202 _bl_ind = RSHashTable::NullEntry; |
205 } | 203 _card_ind = (SparsePRTEntry::CardsPerEntry-1); |
206 | 204 } |
207 bool has_next(size_t& card_index); | 205 |
208 | 206 bool has_next(size_t& card_index); |
209 }; | 207 }; |
210 | 208 |
211 // Concurrent accesss to a SparsePRT must be serialized by some external | 209 // Concurrent accesss to a SparsePRT must be serialized by some external |
212 // mutex. | 210 // mutex. |
213 | 211 |
214 class SparsePRTIter; | 212 class SparsePRTIter; |
236 SparsePRT* _next_expanded; | 234 SparsePRT* _next_expanded; |
237 | 235 |
238 SparsePRT* next_expanded() { return _next_expanded; } | 236 SparsePRT* next_expanded() { return _next_expanded; } |
239 void set_next_expanded(SparsePRT* nxt) { _next_expanded = nxt; } | 237 void set_next_expanded(SparsePRT* nxt) { _next_expanded = nxt; } |
240 | 238 |
241 | |
242 static SparsePRT* _head_expanded_list; | 239 static SparsePRT* _head_expanded_list; |
243 | 240 |
244 public: | 241 public: |
245 SparsePRT(HeapRegion* hr); | 242 SparsePRT(HeapRegion* hr); |
246 | 243 |
253 // the sparse table. If successful (because the card was already | 250 // the sparse table. If successful (because the card was already |
254 // present, or because it was successfullly added) returns "true". | 251 // present, or because it was successfullly added) returns "true". |
255 // Otherwise, returns "false" to indicate that the addition would | 252 // Otherwise, returns "false" to indicate that the addition would |
256 // overflow the entry for the region. The caller must transfer these | 253 // overflow the entry for the region. The caller must transfer these |
257 // entries to a larger-capacity representation. | 254 // entries to a larger-capacity representation. |
258 bool add_card(short region_id, short card_index); | 255 bool add_card(RegionIdx_t region_id, CardIdx_t card_index); |
259 | 256 |
260 // If the table hold an entry for "region_ind", Copies its | 257 // If the table hold an entry for "region_ind", Copies its |
261 // cards into "cards", which must be an array of length at least | 258 // cards into "cards", which must be an array of length at least |
262 // "CardsPerEntry", and returns "true"; otherwise, returns "false". | 259 // "CardsPerEntry", and returns "true"; otherwise, returns "false". |
263 bool get_cards(short region_ind, short* cards); | 260 bool get_cards(RegionIdx_t region_ind, CardIdx_t* cards); |
264 | 261 |
265 // If there is an entry for "region_ind", removes it and return "true"; | 262 // If there is an entry for "region_ind", removes it and return "true"; |
266 // otherwise returns "false." | 263 // otherwise returns "false." |
267 bool delete_entry(short region_ind); | 264 bool delete_entry(RegionIdx_t region_ind); |
268 | 265 |
269 // Clear the table, and reinitialize to initial capacity. | 266 // Clear the table, and reinitialize to initial capacity. |
270 void clear(); | 267 void clear(); |
271 | 268 |
272 // Ensure that "_cur" and "_next" point to the same table. | 269 // Ensure that "_cur" and "_next" point to the same table. |
274 | 271 |
275 // Clean up all tables on the expanded list. Called single threaded. | 272 // Clean up all tables on the expanded list. Called single threaded. |
276 static void cleanup_all(); | 273 static void cleanup_all(); |
277 RSHashTable* cur() const { return _cur; } | 274 RSHashTable* cur() const { return _cur; } |
278 | 275 |
279 | |
280 void init_iterator(SparsePRTIter* sprt_iter); | 276 void init_iterator(SparsePRTIter* sprt_iter); |
281 | 277 |
282 static void add_to_expanded_list(SparsePRT* sprt); | 278 static void add_to_expanded_list(SparsePRT* sprt); |
283 static SparsePRT* get_from_expanded_list(); | 279 static SparsePRT* get_from_expanded_list(); |
284 | 280 |
285 bool contains_card(short region_id, short card_index) const { | 281 bool contains_card(RegionIdx_t region_id, CardIdx_t card_index) const { |
286 return _next->contains_card(region_id, card_index); | 282 return _next->contains_card(region_id, card_index); |
287 } | 283 } |
288 | 284 |
289 #if 0 | 285 #if 0 |
290 void verify_is_cleared(); | 286 void verify_is_cleared(); |