Mercurial > hg > truffle
annotate src/share/vm/utilities/growableArray.hpp @ 1994:6cd6d394f280
7001033: assert(gch->gc_cause() == GCCause::_scavenge_alot || !gch->incremental_collection_failed())
7002546: regression on SpecJbb2005 on 7b118 comparing to 7b117 on small heaps
Summary: Relaxed assertion checking related to incremental_collection_failed flag to allow for ExplicitGCInvokesConcurrent behaviour where we do not want a failing scavenge to bail to a stop-world collection. Parameterized incremental_collection_will_fail() so we can selectively use, or not use, as appropriate, the statistical prediction at specific use sites. This essentially reverts the scavenge bail-out logic to what it was prior to some recent changes that had inadvertently started using the statistical prediction which can be noisy in the presence of bursty loads. Added some associated verbose non-product debugging messages.
Reviewed-by: johnc, tonyp
| author | ysr |
|---|---|
| date | Tue, 07 Dec 2010 21:55:53 -0800 |
| parents | f95d63e2154a |
| children | f6f3bb0ee072 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 1972 | 2 * Copyright (c) 1997, 2010, Oracle and/or its affiliates. All rights reserved. |
| 0 | 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 * | |
|
1552
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1080
diff
changeset
|
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1080
diff
changeset
|
20 * or visit www.oracle.com if you need additional information or have any |
|
c18cbe5936b8
6941466: Oracle rebranding changes for Hotspot repositories
trims
parents:
1080
diff
changeset
|
21 * questions. |
| 0 | 22 * |
| 23 */ | |
| 24 | |
| 1972 | 25 #ifndef SHARE_VM_UTILITIES_GROWABLEARRAY_HPP |
| 26 #define SHARE_VM_UTILITIES_GROWABLEARRAY_HPP | |
| 27 | |
| 28 #include "memory/allocation.hpp" | |
| 29 #include "memory/allocation.inline.hpp" | |
| 30 #include "utilities/debug.hpp" | |
| 31 #include "utilities/globalDefinitions.hpp" | |
| 32 #include "utilities/top.hpp" | |
| 33 | |
| 0 | 34 // A growable array. |
| 35 | |
| 36 /*************************************************************************/ | |
| 37 /* */ | |
| 38 /* WARNING WARNING WARNING WARNING WARNING WARNING WARNING WARNING */ | |
| 39 /* */ | |
| 40 /* Should you use GrowableArrays to contain handles you must be certain */ | |
| 41 /* the the GrowableArray does not outlive the HandleMark that contains */ | |
| 42 /* the handles. Since GrowableArrays are typically resource allocated */ | |
| 43 /* the following is an example of INCORRECT CODE, */ | |
| 44 /* */ | |
| 45 /* ResourceMark rm; */ | |
| 46 /* GrowableArray<Handle>* arr = new GrowableArray<Handle>(size); */ | |
| 47 /* if (blah) { */ | |
| 48 /* while (...) { */ | |
| 49 /* HandleMark hm; */ | |
| 50 /* ... */ | |
| 51 /* Handle h(THREAD, some_oop); */ | |
| 52 /* arr->append(h); */ | |
| 53 /* } */ | |
| 54 /* } */ | |
| 55 /* if (arr->length() != 0 ) { */ | |
| 56 /* oop bad_oop = arr->at(0)(); // Handle is BAD HERE. */ | |
| 57 /* ... */ | |
| 58 /* } */ | |
| 59 /* */ | |
| 60 /* If the GrowableArrays you are creating is C_Heap allocated then it */ | |
| 61 /* hould not old handles since the handles could trivially try and */ | |
| 62 /* outlive their HandleMark. In some situations you might need to do */ | |
| 63 /* this and it would be legal but be very careful and see if you can do */ | |
| 64 /* the code in some other manner. */ | |
| 65 /* */ | |
| 66 /*************************************************************************/ | |
| 67 | |
| 68 // To call default constructor the placement operator new() is used. | |
| 69 // It should be empty (it only returns the passed void* pointer). | |
| 70 // The definition of placement operator new(size_t, void*) in the <new>. | |
| 71 | |
| 72 #include <new> | |
| 73 | |
| 74 // Need the correct linkage to call qsort without warnings | |
| 75 extern "C" { | |
| 76 typedef int (*_sort_Fn)(const void *, const void *); | |
| 77 } | |
| 78 | |
| 79 class GenericGrowableArray : public ResourceObj { | |
| 80 protected: | |
| 81 int _len; // current length | |
| 82 int _max; // maximum length | |
| 83 Arena* _arena; // Indicates where allocation occurs: | |
| 84 // 0 means default ResourceArea | |
| 85 // 1 means on C heap | |
| 86 // otherwise, allocate in _arena | |
| 87 #ifdef ASSERT | |
| 88 int _nesting; // resource area nesting at creation | |
| 89 void set_nesting(); | |
| 90 void check_nesting(); | |
| 91 #else | |
| 92 #define set_nesting(); | |
| 93 #define check_nesting(); | |
| 94 #endif | |
| 95 | |
| 96 // Where are we going to allocate memory? | |
| 97 bool on_C_heap() { return _arena == (Arena*)1; } | |
| 98 bool on_stack () { return _arena == NULL; } | |
| 99 bool on_arena () { return _arena > (Arena*)1; } | |
| 100 | |
| 101 // This GA will use the resource stack for storage if c_heap==false, | |
| 102 // Else it will use the C heap. Use clear_and_deallocate to avoid leaks. | |
| 103 GenericGrowableArray(int initial_size, int initial_len, bool c_heap) { | |
| 104 _len = initial_len; | |
| 105 _max = initial_size; | |
| 106 assert(_len >= 0 && _len <= _max, "initial_len too big"); | |
| 107 _arena = (c_heap ? (Arena*)1 : NULL); | |
| 108 set_nesting(); | |
| 1685 | 109 assert(!on_C_heap() || allocated_on_C_heap(), "growable array must be on C heap if elements are"); |
| 110 assert(!on_stack() || | |
| 111 (allocated_on_res_area() || allocated_on_stack()), | |
| 112 "growable array must be on stack if elements are not on arena and not on C heap"); | |
| 0 | 113 } |
| 114 | |
| 115 // This GA will use the given arena for storage. | |
| 116 // Consider using new(arena) GrowableArray<T> to allocate the header. | |
| 117 GenericGrowableArray(Arena* arena, int initial_size, int initial_len) { | |
| 118 _len = initial_len; | |
| 119 _max = initial_size; | |
| 120 assert(_len >= 0 && _len <= _max, "initial_len too big"); | |
| 121 _arena = arena; | |
| 122 assert(on_arena(), "arena has taken on reserved value 0 or 1"); | |
| 1685 | 123 // Relax next assert to allow object allocation on resource area, |
| 124 // on stack or embedded into an other object. | |
| 125 assert(allocated_on_arena() || allocated_on_stack(), | |
| 126 "growable array must be on arena or on stack if elements are on arena"); | |
| 0 | 127 } |
| 128 | |
| 129 void* raw_allocate(int elementSize); | |
| 432 | 130 |
| 131 // some uses pass the Thread explicitly for speed (4990299 tuning) | |
| 132 void* raw_allocate(Thread* thread, int elementSize) { | |
| 133 assert(on_stack(), "fast ResourceObj path only"); | |
| 134 return (void*)resource_allocate_bytes(thread, elementSize * _max); | |
| 135 } | |
| 0 | 136 }; |
| 137 | |
| 138 template<class E> class GrowableArray : public GenericGrowableArray { | |
| 139 private: | |
| 140 E* _data; // data array | |
| 141 | |
| 142 void grow(int j); | |
| 143 void raw_at_put_grow(int i, const E& p, const E& fill); | |
| 144 void clear_and_deallocate(); | |
| 145 public: | |
| 432 | 146 GrowableArray(Thread* thread, int initial_size) : GenericGrowableArray(initial_size, 0, false) { |
| 147 _data = (E*)raw_allocate(thread, sizeof(E)); | |
| 148 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 149 } | |
| 150 | |
| 0 | 151 GrowableArray(int initial_size, bool C_heap = false) : GenericGrowableArray(initial_size, 0, C_heap) { |
| 152 _data = (E*)raw_allocate(sizeof(E)); | |
| 153 for (int i = 0; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 154 } | |
| 155 | |
| 156 GrowableArray(int initial_size, int initial_len, const E& filler, bool C_heap = false) : GenericGrowableArray(initial_size, initial_len, C_heap) { | |
| 157 _data = (E*)raw_allocate(sizeof(E)); | |
| 158 int i = 0; | |
| 159 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler); | |
| 160 for (; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 161 } | |
| 162 | |
| 163 GrowableArray(Arena* arena, int initial_size, int initial_len, const E& filler) : GenericGrowableArray(arena, initial_size, initial_len) { | |
| 164 _data = (E*)raw_allocate(sizeof(E)); | |
| 165 int i = 0; | |
| 166 for (; i < _len; i++) ::new ((void*)&_data[i]) E(filler); | |
| 167 for (; i < _max; i++) ::new ((void*)&_data[i]) E(); | |
| 168 } | |
| 169 | |
| 170 GrowableArray() : GenericGrowableArray(2, 0, false) { | |
| 171 _data = (E*)raw_allocate(sizeof(E)); | |
| 172 ::new ((void*)&_data[0]) E(); | |
| 173 ::new ((void*)&_data[1]) E(); | |
| 174 } | |
| 175 | |
| 176 // Does nothing for resource and arena objects | |
| 177 ~GrowableArray() { if (on_C_heap()) clear_and_deallocate(); } | |
| 178 | |
| 179 void clear() { _len = 0; } | |
| 180 int length() const { return _len; } | |
| 181 void trunc_to(int l) { assert(l <= _len,"cannot increase length"); _len = l; } | |
| 182 bool is_empty() const { return _len == 0; } | |
| 183 bool is_nonempty() const { return _len != 0; } | |
| 184 bool is_full() const { return _len == _max; } | |
| 185 DEBUG_ONLY(E* data_addr() const { return _data; }) | |
| 186 | |
| 187 void print(); | |
| 188 | |
| 432 | 189 int append(const E& elem) { |
| 0 | 190 check_nesting(); |
| 191 if (_len == _max) grow(_len); | |
| 432 | 192 int idx = _len++; |
| 193 _data[idx] = elem; | |
| 194 return idx; | |
| 0 | 195 } |
| 196 | |
| 197 void append_if_missing(const E& elem) { | |
| 198 if (!contains(elem)) append(elem); | |
| 199 } | |
| 200 | |
| 201 E at(int i) const { | |
| 202 assert(0 <= i && i < _len, "illegal index"); | |
| 203 return _data[i]; | |
| 204 } | |
| 205 | |
| 206 E* adr_at(int i) const { | |
| 207 assert(0 <= i && i < _len, "illegal index"); | |
| 208 return &_data[i]; | |
| 209 } | |
| 210 | |
| 211 E first() const { | |
| 212 assert(_len > 0, "empty list"); | |
| 213 return _data[0]; | |
| 214 } | |
| 215 | |
| 216 E top() const { | |
| 217 assert(_len > 0, "empty list"); | |
| 218 return _data[_len-1]; | |
| 219 } | |
| 220 | |
| 221 void push(const E& elem) { append(elem); } | |
| 222 | |
| 223 E pop() { | |
| 224 assert(_len > 0, "empty list"); | |
| 225 return _data[--_len]; | |
| 226 } | |
| 227 | |
| 228 void at_put(int i, const E& elem) { | |
| 229 assert(0 <= i && i < _len, "illegal index"); | |
| 230 _data[i] = elem; | |
| 231 } | |
| 232 | |
| 233 E at_grow(int i, const E& fill = E()) { | |
| 234 assert(0 <= i, "negative index"); | |
| 235 check_nesting(); | |
| 236 if (i >= _len) { | |
| 237 if (i >= _max) grow(i); | |
| 238 for (int j = _len; j <= i; j++) | |
| 239 _data[j] = fill; | |
| 240 _len = i+1; | |
| 241 } | |
| 242 return _data[i]; | |
| 243 } | |
| 244 | |
| 245 void at_put_grow(int i, const E& elem, const E& fill = E()) { | |
| 246 assert(0 <= i, "negative index"); | |
| 247 check_nesting(); | |
| 248 raw_at_put_grow(i, elem, fill); | |
| 249 } | |
| 250 | |
| 251 bool contains(const E& elem) const { | |
| 252 for (int i = 0; i < _len; i++) { | |
| 253 if (_data[i] == elem) return true; | |
| 254 } | |
| 255 return false; | |
| 256 } | |
| 257 | |
| 258 int find(const E& elem) const { | |
| 259 for (int i = 0; i < _len; i++) { | |
| 260 if (_data[i] == elem) return i; | |
| 261 } | |
| 262 return -1; | |
| 263 } | |
| 264 | |
| 265 int find(void* token, bool f(void*, E)) const { | |
| 266 for (int i = 0; i < _len; i++) { | |
| 267 if (f(token, _data[i])) return i; | |
| 268 } | |
| 269 return -1; | |
| 270 } | |
| 271 | |
| 272 int find_at_end(void* token, bool f(void*, E)) const { | |
| 273 // start at the end of the array | |
| 274 for (int i = _len-1; i >= 0; i--) { | |
| 275 if (f(token, _data[i])) return i; | |
| 276 } | |
| 277 return -1; | |
| 278 } | |
| 279 | |
| 280 void remove(const E& elem) { | |
| 281 for (int i = 0; i < _len; i++) { | |
| 282 if (_data[i] == elem) { | |
| 283 for (int j = i + 1; j < _len; j++) _data[j-1] = _data[j]; | |
| 284 _len--; | |
| 285 return; | |
| 286 } | |
| 287 } | |
| 288 ShouldNotReachHere(); | |
| 289 } | |
| 290 | |
| 291 void remove_at(int index) { | |
| 292 assert(0 <= index && index < _len, "illegal index"); | |
| 293 for (int j = index + 1; j < _len; j++) _data[j-1] = _data[j]; | |
| 294 _len--; | |
| 295 } | |
| 296 | |
|
1080
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
297 // inserts the given element before the element at index i |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
298 void insert_before(const int idx, const E& elem) { |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
299 check_nesting(); |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
300 if (_len == _max) grow(_len); |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
301 for (int j = _len - 1; j >= idx; j--) { |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
302 _data[j + 1] = _data[j]; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
303 } |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
304 _len++; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
305 _data[idx] = elem; |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
306 } |
|
7c57aead6d3e
6892658: C2 should optimize some stringbuilder patterns
never
parents:
470
diff
changeset
|
307 |
| 0 | 308 void appendAll(const GrowableArray<E>* l) { |
| 309 for (int i = 0; i < l->_len; i++) { | |
| 310 raw_at_put_grow(_len, l->_data[i], 0); | |
| 311 } | |
| 312 } | |
| 313 | |
| 314 void sort(int f(E*,E*)) { | |
| 315 qsort(_data, length(), sizeof(E), (_sort_Fn)f); | |
| 316 } | |
| 317 // sort by fixed-stride sub arrays: | |
| 318 void sort(int f(E*,E*), int stride) { | |
| 319 qsort(_data, length() / stride, sizeof(E) * stride, (_sort_Fn)f); | |
| 320 } | |
| 321 }; | |
| 322 | |
| 323 // Global GrowableArray methods (one instance in the library per each 'E' type). | |
| 324 | |
| 325 template<class E> void GrowableArray<E>::grow(int j) { | |
| 326 // grow the array by doubling its size (amortized growth) | |
| 327 int old_max = _max; | |
| 328 if (_max == 0) _max = 1; // prevent endless loop | |
| 329 while (j >= _max) _max = _max*2; | |
| 330 // j < _max | |
| 331 E* newData = (E*)raw_allocate(sizeof(E)); | |
| 332 int i = 0; | |
| 333 for ( ; i < _len; i++) ::new ((void*)&newData[i]) E(_data[i]); | |
| 334 for ( ; i < _max; i++) ::new ((void*)&newData[i]) E(); | |
| 335 for (i = 0; i < old_max; i++) _data[i].~E(); | |
| 336 if (on_C_heap() && _data != NULL) { | |
| 337 FreeHeap(_data); | |
| 338 } | |
| 339 _data = newData; | |
| 340 } | |
| 341 | |
| 342 template<class E> void GrowableArray<E>::raw_at_put_grow(int i, const E& p, const E& fill) { | |
| 343 if (i >= _len) { | |
| 344 if (i >= _max) grow(i); | |
| 345 for (int j = _len; j < i; j++) | |
| 346 _data[j] = fill; | |
| 347 _len = i+1; | |
| 348 } | |
| 349 _data[i] = p; | |
| 350 } | |
| 351 | |
| 352 // This function clears and deallocate the data in the growable array that | |
| 353 // has been allocated on the C heap. It's not public - called by the | |
| 354 // destructor. | |
| 355 template<class E> void GrowableArray<E>::clear_and_deallocate() { | |
| 356 assert(on_C_heap(), | |
| 357 "clear_and_deallocate should only be called when on C heap"); | |
| 358 clear(); | |
| 359 if (_data != NULL) { | |
| 360 for (int i = 0; i < _max; i++) _data[i].~E(); | |
| 361 FreeHeap(_data); | |
| 362 _data = NULL; | |
| 363 } | |
| 364 } | |
| 365 | |
| 366 template<class E> void GrowableArray<E>::print() { | |
| 367 tty->print("Growable Array " INTPTR_FORMAT, this); | |
| 368 tty->print(": length %ld (_max %ld) { ", _len, _max); | |
| 369 for (int i = 0; i < _len; i++) tty->print(INTPTR_FORMAT " ", *(intptr_t*)&(_data[i])); | |
| 370 tty->print("}\n"); | |
| 371 } | |
| 1972 | 372 |
| 373 #endif // SHARE_VM_UTILITIES_GROWABLEARRAY_HPP |