Mercurial > hg > graal-compiler

comparison src/share/vm/gc_implementation/g1/sparsePRT.hpp @ 807:d44bdab1c03d

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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();