Print this page
rev 6887 : 8060467: CMS: small OldPLABSize and -XX:-ResizePLAB cause assert(ResizePLAB || n_blks == OldPLABSize) failed: Error
Reviewed-by: tschatzl, jmasa, kbarrett
Split |
Split |
Close |
Expand all |
Collapse all |
--- old/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp
+++ new/hotspot/src/share/vm/gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.cpp
1 1 /*
2 2 * Copyright (c) 2001, 2014, Oracle and/or its affiliates. All rights reserved.
3 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 4 *
5 5 * This code is free software; you can redistribute it and/or modify it
6 6 * under the terms of the GNU General Public License version 2 only, as
7 7 * published by the Free Software Foundation.
8 8 *
9 9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 12 * version 2 for more details (a copy is included in the LICENSE file that
13 13 * accompanied this code).
14 14 *
15 15 * You should have received a copy of the GNU General Public License version
16 16 * 2 along with this work; if not, write to the Free Software Foundation,
17 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 18 *
19 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 20 * or visit www.oracle.com if you need additional information or have any
21 21 * questions.
22 22 *
23 23 */
24 24
25 25 #include "precompiled.hpp"
26 26 #include "gc_implementation/concurrentMarkSweep/cmsLockVerifier.hpp"
27 27 #include "gc_implementation/concurrentMarkSweep/compactibleFreeListSpace.hpp"
28 28 #include "gc_implementation/concurrentMarkSweep/concurrentMarkSweepGeneration.inline.hpp"
29 29 #include "gc_implementation/concurrentMarkSweep/concurrentMarkSweepThread.hpp"
30 30 #include "gc_implementation/shared/liveRange.hpp"
31 31 #include "gc_implementation/shared/spaceDecorator.hpp"
32 32 #include "gc_interface/collectedHeap.inline.hpp"
33 33 #include "memory/allocation.inline.hpp"
34 34 #include "memory/blockOffsetTable.inline.hpp"
35 35 #include "memory/resourceArea.hpp"
36 36 #include "memory/space.inline.hpp"
37 37 #include "memory/universe.inline.hpp"
38 38 #include "oops/oop.inline.hpp"
39 39 #include "runtime/globals.hpp"
40 40 #include "runtime/handles.inline.hpp"
41 41 #include "runtime/init.hpp"
42 42 #include "runtime/java.hpp"
43 43 #include "runtime/orderAccess.inline.hpp"
44 44 #include "runtime/vmThread.hpp"
45 45 #include "utilities/copy.hpp"
46 46
47 47 /////////////////////////////////////////////////////////////////////////
48 48 //// CompactibleFreeListSpace
49 49 /////////////////////////////////////////////////////////////////////////
50 50
51 51 // highest ranked free list lock rank
52 52 int CompactibleFreeListSpace::_lockRank = Mutex::leaf + 3;
53 53
54 54 // Defaults are 0 so things will break badly if incorrectly initialized.
55 55 size_t CompactibleFreeListSpace::IndexSetStart = 0;
56 56 size_t CompactibleFreeListSpace::IndexSetStride = 0;
57 57
58 58 size_t MinChunkSize = 0;
59 59
60 60 void CompactibleFreeListSpace::set_cms_values() {
61 61 // Set CMS global values
62 62 assert(MinChunkSize == 0, "already set");
63 63
64 64 // MinChunkSize should be a multiple of MinObjAlignment and be large enough
65 65 // for chunks to contain a FreeChunk.
66 66 size_t min_chunk_size_in_bytes = align_size_up(sizeof(FreeChunk), MinObjAlignmentInBytes);
67 67 MinChunkSize = min_chunk_size_in_bytes / BytesPerWord;
68 68
69 69 assert(IndexSetStart == 0 && IndexSetStride == 0, "already set");
70 70 IndexSetStart = MinChunkSize;
71 71 IndexSetStride = MinObjAlignment;
72 72 }
73 73
74 74 // Constructor
75 75 CompactibleFreeListSpace::CompactibleFreeListSpace(BlockOffsetSharedArray* bs,
76 76 MemRegion mr, bool use_adaptive_freelists,
77 77 FreeBlockDictionary<FreeChunk>::DictionaryChoice dictionaryChoice) :
78 78 _dictionaryChoice(dictionaryChoice),
79 79 _adaptive_freelists(use_adaptive_freelists),
80 80 _bt(bs, mr),
81 81 // free list locks are in the range of values taken by _lockRank
82 82 // This range currently is [_leaf+2, _leaf+3]
83 83 // Note: this requires that CFLspace c'tors
84 84 // are called serially in the order in which the locks are
85 85 // are acquired in the program text. This is true today.
86 86 _freelistLock(_lockRank--, "CompactibleFreeListSpace._lock", true),
87 87 _parDictionaryAllocLock(Mutex::leaf - 1, // == rank(ExpandHeap_lock) - 1
88 88 "CompactibleFreeListSpace._dict_par_lock", true),
89 89 _rescan_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
90 90 CMSRescanMultiple),
91 91 _marking_task_size(CardTableModRefBS::card_size_in_words * BitsPerWord *
92 92 CMSConcMarkMultiple),
93 93 _collector(NULL)
94 94 {
95 95 assert(sizeof(FreeChunk) / BytesPerWord <= MinChunkSize,
96 96 "FreeChunk is larger than expected");
97 97 _bt.set_space(this);
98 98 initialize(mr, SpaceDecorator::Clear, SpaceDecorator::Mangle);
99 99 // We have all of "mr", all of which we place in the dictionary
100 100 // as one big chunk. We'll need to decide here which of several
101 101 // possible alternative dictionary implementations to use. For
102 102 // now the choice is easy, since we have only one working
103 103 // implementation, namely, the simple binary tree (splaying
104 104 // temporarily disabled).
105 105 switch (dictionaryChoice) {
106 106 case FreeBlockDictionary<FreeChunk>::dictionaryBinaryTree:
107 107 _dictionary = new AFLBinaryTreeDictionary(mr);
108 108 break;
109 109 case FreeBlockDictionary<FreeChunk>::dictionarySplayTree:
110 110 case FreeBlockDictionary<FreeChunk>::dictionarySkipList:
111 111 default:
112 112 warning("dictionaryChoice: selected option not understood; using"
113 113 " default BinaryTreeDictionary implementation instead.");
114 114 }
115 115 assert(_dictionary != NULL, "CMS dictionary initialization");
116 116 // The indexed free lists are initially all empty and are lazily
117 117 // filled in on demand. Initialize the array elements to NULL.
118 118 initializeIndexedFreeListArray();
119 119
120 120 // Not using adaptive free lists assumes that allocation is first
121 121 // from the linAB's. Also a cms perm gen which can be compacted
122 122 // has to have the klass's klassKlass allocated at a lower
123 123 // address in the heap than the klass so that the klassKlass is
124 124 // moved to its new location before the klass is moved.
125 125 // Set the _refillSize for the linear allocation blocks
126 126 if (!use_adaptive_freelists) {
127 127 FreeChunk* fc = _dictionary->get_chunk(mr.word_size(),
128 128 FreeBlockDictionary<FreeChunk>::atLeast);
129 129 // The small linAB initially has all the space and will allocate
130 130 // a chunk of any size.
131 131 HeapWord* addr = (HeapWord*) fc;
132 132 _smallLinearAllocBlock.set(addr, fc->size() ,
133 133 1024*SmallForLinearAlloc, fc->size());
134 134 // Note that _unallocated_block is not updated here.
135 135 // Allocations from the linear allocation block should
136 136 // update it.
137 137 } else {
138 138 _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc,
139 139 SmallForLinearAlloc);
140 140 }
141 141 // CMSIndexedFreeListReplenish should be at least 1
142 142 CMSIndexedFreeListReplenish = MAX2((uintx)1, CMSIndexedFreeListReplenish);
143 143 _promoInfo.setSpace(this);
144 144 if (UseCMSBestFit) {
145 145 _fitStrategy = FreeBlockBestFitFirst;
146 146 } else {
147 147 _fitStrategy = FreeBlockStrategyNone;
148 148 }
149 149 check_free_list_consistency();
150 150
151 151 // Initialize locks for parallel case.
152 152
153 153 if (CollectedHeap::use_parallel_gc_threads()) {
154 154 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
155 155 _indexedFreeListParLocks[i] = new Mutex(Mutex::leaf - 1, // == ExpandHeap_lock - 1
156 156 "a freelist par lock",
157 157 true);
158 158 DEBUG_ONLY(
159 159 _indexedFreeList[i].set_protecting_lock(_indexedFreeListParLocks[i]);
160 160 )
161 161 }
162 162 _dictionary->set_par_lock(&_parDictionaryAllocLock);
163 163 }
164 164 }
165 165
166 166 // Like CompactibleSpace forward() but always calls cross_threshold() to
167 167 // update the block offset table. Removed initialize_threshold call because
168 168 // CFLS does not use a block offset array for contiguous spaces.
169 169 HeapWord* CompactibleFreeListSpace::forward(oop q, size_t size,
170 170 CompactPoint* cp, HeapWord* compact_top) {
171 171 // q is alive
172 172 // First check if we should switch compaction space
173 173 assert(this == cp->space, "'this' should be current compaction space.");
174 174 size_t compaction_max_size = pointer_delta(end(), compact_top);
175 175 assert(adjustObjectSize(size) == cp->space->adjust_object_size_v(size),
176 176 "virtual adjustObjectSize_v() method is not correct");
177 177 size_t adjusted_size = adjustObjectSize(size);
178 178 assert(compaction_max_size >= MinChunkSize || compaction_max_size == 0,
179 179 "no small fragments allowed");
180 180 assert(minimum_free_block_size() == MinChunkSize,
181 181 "for de-virtualized reference below");
182 182 // Can't leave a nonzero size, residual fragment smaller than MinChunkSize
183 183 if (adjusted_size + MinChunkSize > compaction_max_size &&
184 184 adjusted_size != compaction_max_size) {
185 185 do {
186 186 // switch to next compaction space
187 187 cp->space->set_compaction_top(compact_top);
188 188 cp->space = cp->space->next_compaction_space();
189 189 if (cp->space == NULL) {
190 190 cp->gen = GenCollectedHeap::heap()->prev_gen(cp->gen);
191 191 assert(cp->gen != NULL, "compaction must succeed");
192 192 cp->space = cp->gen->first_compaction_space();
193 193 assert(cp->space != NULL, "generation must have a first compaction space");
194 194 }
195 195 compact_top = cp->space->bottom();
196 196 cp->space->set_compaction_top(compact_top);
197 197 // The correct adjusted_size may not be the same as that for this method
198 198 // (i.e., cp->space may no longer be "this" so adjust the size again.
199 199 // Use the virtual method which is not used above to save the virtual
200 200 // dispatch.
201 201 adjusted_size = cp->space->adjust_object_size_v(size);
202 202 compaction_max_size = pointer_delta(cp->space->end(), compact_top);
203 203 assert(cp->space->minimum_free_block_size() == 0, "just checking");
204 204 } while (adjusted_size > compaction_max_size);
205 205 }
206 206
207 207 // store the forwarding pointer into the mark word
208 208 if ((HeapWord*)q != compact_top) {
209 209 q->forward_to(oop(compact_top));
210 210 assert(q->is_gc_marked(), "encoding the pointer should preserve the mark");
211 211 } else {
212 212 // if the object isn't moving we can just set the mark to the default
213 213 // mark and handle it specially later on.
214 214 q->init_mark();
215 215 assert(q->forwardee() == NULL, "should be forwarded to NULL");
216 216 }
217 217
218 218 compact_top += adjusted_size;
219 219
220 220 // we need to update the offset table so that the beginnings of objects can be
221 221 // found during scavenge. Note that we are updating the offset table based on
222 222 // where the object will be once the compaction phase finishes.
223 223
224 224 // Always call cross_threshold(). A contiguous space can only call it when
225 225 // the compaction_top exceeds the current threshold but not for an
226 226 // non-contiguous space.
227 227 cp->threshold =
228 228 cp->space->cross_threshold(compact_top - adjusted_size, compact_top);
229 229 return compact_top;
230 230 }
231 231
232 232 // A modified copy of OffsetTableContigSpace::cross_threshold() with _offsets -> _bt
233 233 // and use of single_block instead of alloc_block. The name here is not really
234 234 // appropriate - maybe a more general name could be invented for both the
235 235 // contiguous and noncontiguous spaces.
236 236
237 237 HeapWord* CompactibleFreeListSpace::cross_threshold(HeapWord* start, HeapWord* the_end) {
238 238 _bt.single_block(start, the_end);
239 239 return end();
240 240 }
241 241
242 242 // Initialize them to NULL.
243 243 void CompactibleFreeListSpace::initializeIndexedFreeListArray() {
244 244 for (size_t i = 0; i < IndexSetSize; i++) {
245 245 // Note that on platforms where objects are double word aligned,
246 246 // the odd array elements are not used. It is convenient, however,
247 247 // to map directly from the object size to the array element.
248 248 _indexedFreeList[i].reset(IndexSetSize);
249 249 _indexedFreeList[i].set_size(i);
250 250 assert(_indexedFreeList[i].count() == 0, "reset check failed");
251 251 assert(_indexedFreeList[i].head() == NULL, "reset check failed");
252 252 assert(_indexedFreeList[i].tail() == NULL, "reset check failed");
253 253 assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed");
254 254 }
255 255 }
256 256
257 257 void CompactibleFreeListSpace::resetIndexedFreeListArray() {
258 258 for (size_t i = 1; i < IndexSetSize; i++) {
259 259 assert(_indexedFreeList[i].size() == (size_t) i,
260 260 "Indexed free list sizes are incorrect");
261 261 _indexedFreeList[i].reset(IndexSetSize);
262 262 assert(_indexedFreeList[i].count() == 0, "reset check failed");
263 263 assert(_indexedFreeList[i].head() == NULL, "reset check failed");
264 264 assert(_indexedFreeList[i].tail() == NULL, "reset check failed");
265 265 assert(_indexedFreeList[i].hint() == IndexSetSize, "reset check failed");
266 266 }
267 267 }
268 268
269 269 void CompactibleFreeListSpace::reset(MemRegion mr) {
270 270 resetIndexedFreeListArray();
271 271 dictionary()->reset();
272 272 if (BlockOffsetArrayUseUnallocatedBlock) {
273 273 assert(end() == mr.end(), "We are compacting to the bottom of CMS gen");
274 274 // Everything's allocated until proven otherwise.
275 275 _bt.set_unallocated_block(end());
276 276 }
277 277 if (!mr.is_empty()) {
278 278 assert(mr.word_size() >= MinChunkSize, "Chunk size is too small");
279 279 _bt.single_block(mr.start(), mr.word_size());
280 280 FreeChunk* fc = (FreeChunk*) mr.start();
281 281 fc->set_size(mr.word_size());
282 282 if (mr.word_size() >= IndexSetSize ) {
283 283 returnChunkToDictionary(fc);
284 284 } else {
285 285 _bt.verify_not_unallocated((HeapWord*)fc, fc->size());
286 286 _indexedFreeList[mr.word_size()].return_chunk_at_head(fc);
287 287 }
288 288 coalBirth(mr.word_size());
289 289 }
290 290 _promoInfo.reset();
291 291 _smallLinearAllocBlock._ptr = NULL;
292 292 _smallLinearAllocBlock._word_size = 0;
293 293 }
294 294
295 295 void CompactibleFreeListSpace::reset_after_compaction() {
296 296 // Reset the space to the new reality - one free chunk.
297 297 MemRegion mr(compaction_top(), end());
298 298 reset(mr);
299 299 // Now refill the linear allocation block(s) if possible.
300 300 if (_adaptive_freelists) {
301 301 refillLinearAllocBlocksIfNeeded();
302 302 } else {
303 303 // Place as much of mr in the linAB as we can get,
304 304 // provided it was big enough to go into the dictionary.
305 305 FreeChunk* fc = dictionary()->find_largest_dict();
306 306 if (fc != NULL) {
307 307 assert(fc->size() == mr.word_size(),
308 308 "Why was the chunk broken up?");
309 309 removeChunkFromDictionary(fc);
310 310 HeapWord* addr = (HeapWord*) fc;
311 311 _smallLinearAllocBlock.set(addr, fc->size() ,
312 312 1024*SmallForLinearAlloc, fc->size());
313 313 // Note that _unallocated_block is not updated here.
314 314 }
315 315 }
316 316 }
317 317
318 318 // Walks the entire dictionary, returning a coterminal
319 319 // chunk, if it exists. Use with caution since it involves
320 320 // a potentially complete walk of a potentially large tree.
321 321 FreeChunk* CompactibleFreeListSpace::find_chunk_at_end() {
322 322
323 323 assert_lock_strong(&_freelistLock);
324 324
325 325 return dictionary()->find_chunk_ends_at(end());
326 326 }
327 327
328 328
329 329 #ifndef PRODUCT
330 330 void CompactibleFreeListSpace::initializeIndexedFreeListArrayReturnedBytes() {
331 331 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
332 332 _indexedFreeList[i].allocation_stats()->set_returned_bytes(0);
333 333 }
334 334 }
335 335
336 336 size_t CompactibleFreeListSpace::sumIndexedFreeListArrayReturnedBytes() {
337 337 size_t sum = 0;
338 338 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
339 339 sum += _indexedFreeList[i].allocation_stats()->returned_bytes();
340 340 }
341 341 return sum;
342 342 }
343 343
344 344 size_t CompactibleFreeListSpace::totalCountInIndexedFreeLists() const {
345 345 size_t count = 0;
346 346 for (size_t i = IndexSetStart; i < IndexSetSize; i++) {
347 347 debug_only(
348 348 ssize_t total_list_count = 0;
349 349 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
350 350 fc = fc->next()) {
351 351 total_list_count++;
352 352 }
353 353 assert(total_list_count == _indexedFreeList[i].count(),
354 354 "Count in list is incorrect");
355 355 )
356 356 count += _indexedFreeList[i].count();
357 357 }
358 358 return count;
359 359 }
360 360
361 361 size_t CompactibleFreeListSpace::totalCount() {
362 362 size_t num = totalCountInIndexedFreeLists();
363 363 num += dictionary()->total_count();
364 364 if (_smallLinearAllocBlock._word_size != 0) {
365 365 num++;
366 366 }
367 367 return num;
368 368 }
369 369 #endif
370 370
371 371 bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const {
372 372 FreeChunk* fc = (FreeChunk*) p;
373 373 return fc->is_free();
374 374 }
375 375
376 376 size_t CompactibleFreeListSpace::used() const {
377 377 return capacity() - free();
378 378 }
379 379
380 380 size_t CompactibleFreeListSpace::free() const {
381 381 // "MT-safe, but not MT-precise"(TM), if you will: i.e.
382 382 // if you do this while the structures are in flux you
383 383 // may get an approximate answer only; for instance
384 384 // because there is concurrent allocation either
385 385 // directly by mutators or for promotion during a GC.
386 386 // It's "MT-safe", however, in the sense that you are guaranteed
387 387 // not to crash and burn, for instance, because of walking
388 388 // pointers that could disappear as you were walking them.
389 389 // The approximation is because the various components
390 390 // that are read below are not read atomically (and
391 391 // further the computation of totalSizeInIndexedFreeLists()
392 392 // is itself a non-atomic computation. The normal use of
393 393 // this is during a resize operation at the end of GC
394 394 // and at that time you are guaranteed to get the
395 395 // correct actual value. However, for instance, this is
396 396 // also read completely asynchronously by the "perf-sampler"
397 397 // that supports jvmstat, and you are apt to see the values
398 398 // flicker in such cases.
399 399 assert(_dictionary != NULL, "No _dictionary?");
400 400 return (_dictionary->total_chunk_size(DEBUG_ONLY(freelistLock())) +
401 401 totalSizeInIndexedFreeLists() +
402 402 _smallLinearAllocBlock._word_size) * HeapWordSize;
403 403 }
404 404
405 405 size_t CompactibleFreeListSpace::max_alloc_in_words() const {
406 406 assert(_dictionary != NULL, "No _dictionary?");
407 407 assert_locked();
408 408 size_t res = _dictionary->max_chunk_size();
409 409 res = MAX2(res, MIN2(_smallLinearAllocBlock._word_size,
410 410 (size_t) SmallForLinearAlloc - 1));
411 411 // XXX the following could potentially be pretty slow;
412 412 // should one, pesimally for the rare cases when res
413 413 // caclulated above is less than IndexSetSize,
414 414 // just return res calculated above? My reasoning was that
415 415 // those cases will be so rare that the extra time spent doesn't
416 416 // really matter....
417 417 // Note: do not change the loop test i >= res + IndexSetStride
418 418 // to i > res below, because i is unsigned and res may be zero.
419 419 for (size_t i = IndexSetSize - 1; i >= res + IndexSetStride;
420 420 i -= IndexSetStride) {
421 421 if (_indexedFreeList[i].head() != NULL) {
422 422 assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList");
423 423 return i;
424 424 }
425 425 }
426 426 return res;
427 427 }
428 428
429 429 void LinearAllocBlock::print_on(outputStream* st) const {
430 430 st->print_cr(" LinearAllocBlock: ptr = " PTR_FORMAT ", word_size = " SIZE_FORMAT
431 431 ", refillsize = " SIZE_FORMAT ", allocation_size_limit = " SIZE_FORMAT,
432 432 p2i(_ptr), _word_size, _refillSize, _allocation_size_limit);
433 433 }
434 434
435 435 void CompactibleFreeListSpace::print_on(outputStream* st) const {
436 436 st->print_cr("COMPACTIBLE FREELIST SPACE");
437 437 st->print_cr(" Space:");
438 438 Space::print_on(st);
439 439
440 440 st->print_cr("promoInfo:");
441 441 _promoInfo.print_on(st);
442 442
443 443 st->print_cr("_smallLinearAllocBlock");
444 444 _smallLinearAllocBlock.print_on(st);
445 445
446 446 // dump_memory_block(_smallLinearAllocBlock->_ptr, 128);
447 447
448 448 st->print_cr(" _fitStrategy = %s, _adaptive_freelists = %s",
449 449 _fitStrategy?"true":"false", _adaptive_freelists?"true":"false");
450 450 }
451 451
452 452 void CompactibleFreeListSpace::print_indexed_free_lists(outputStream* st)
453 453 const {
454 454 reportIndexedFreeListStatistics();
455 455 gclog_or_tty->print_cr("Layout of Indexed Freelists");
456 456 gclog_or_tty->print_cr("---------------------------");
457 457 AdaptiveFreeList<FreeChunk>::print_labels_on(st, "size");
458 458 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
459 459 _indexedFreeList[i].print_on(gclog_or_tty);
460 460 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
461 461 fc = fc->next()) {
462 462 gclog_or_tty->print_cr("\t[" PTR_FORMAT "," PTR_FORMAT ") %s",
463 463 p2i(fc), p2i((HeapWord*)fc + i),
464 464 fc->cantCoalesce() ? "\t CC" : "");
465 465 }
466 466 }
467 467 }
468 468
469 469 void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st)
470 470 const {
471 471 _promoInfo.print_on(st);
472 472 }
473 473
474 474 void CompactibleFreeListSpace::print_dictionary_free_lists(outputStream* st)
475 475 const {
476 476 _dictionary->report_statistics();
477 477 st->print_cr("Layout of Freelists in Tree");
478 478 st->print_cr("---------------------------");
479 479 _dictionary->print_free_lists(st);
480 480 }
481 481
482 482 class BlkPrintingClosure: public BlkClosure {
483 483 const CMSCollector* _collector;
484 484 const CompactibleFreeListSpace* _sp;
485 485 const CMSBitMap* _live_bit_map;
486 486 const bool _post_remark;
487 487 outputStream* _st;
488 488 public:
489 489 BlkPrintingClosure(const CMSCollector* collector,
490 490 const CompactibleFreeListSpace* sp,
491 491 const CMSBitMap* live_bit_map,
492 492 outputStream* st):
493 493 _collector(collector),
494 494 _sp(sp),
495 495 _live_bit_map(live_bit_map),
496 496 _post_remark(collector->abstract_state() > CMSCollector::FinalMarking),
497 497 _st(st) { }
498 498 size_t do_blk(HeapWord* addr);
499 499 };
500 500
501 501 size_t BlkPrintingClosure::do_blk(HeapWord* addr) {
502 502 size_t sz = _sp->block_size_no_stall(addr, _collector);
503 503 assert(sz != 0, "Should always be able to compute a size");
504 504 if (_sp->block_is_obj(addr)) {
505 505 const bool dead = _post_remark && !_live_bit_map->isMarked(addr);
506 506 _st->print_cr(PTR_FORMAT ": %s object of size " SIZE_FORMAT "%s",
507 507 p2i(addr),
508 508 dead ? "dead" : "live",
509 509 sz,
510 510 (!dead && CMSPrintObjectsInDump) ? ":" : ".");
511 511 if (CMSPrintObjectsInDump && !dead) {
512 512 oop(addr)->print_on(_st);
513 513 _st->print_cr("--------------------------------------");
514 514 }
515 515 } else { // free block
516 516 _st->print_cr(PTR_FORMAT ": free block of size " SIZE_FORMAT "%s",
517 517 p2i(addr), sz, CMSPrintChunksInDump ? ":" : ".");
518 518 if (CMSPrintChunksInDump) {
519 519 ((FreeChunk*)addr)->print_on(_st);
520 520 _st->print_cr("--------------------------------------");
521 521 }
522 522 }
523 523 return sz;
524 524 }
525 525
526 526 void CompactibleFreeListSpace::dump_at_safepoint_with_locks(CMSCollector* c,
527 527 outputStream* st) {
528 528 st->print_cr("\n=========================");
529 529 st->print_cr("Block layout in CMS Heap:");
530 530 st->print_cr("=========================");
531 531 BlkPrintingClosure bpcl(c, this, c->markBitMap(), st);
532 532 blk_iterate(&bpcl);
533 533
534 534 st->print_cr("\n=======================================");
535 535 st->print_cr("Order & Layout of Promotion Info Blocks");
536 536 st->print_cr("=======================================");
537 537 print_promo_info_blocks(st);
538 538
539 539 st->print_cr("\n===========================");
540 540 st->print_cr("Order of Indexed Free Lists");
541 541 st->print_cr("=========================");
542 542 print_indexed_free_lists(st);
543 543
544 544 st->print_cr("\n=================================");
545 545 st->print_cr("Order of Free Lists in Dictionary");
546 546 st->print_cr("=================================");
547 547 print_dictionary_free_lists(st);
548 548 }
549 549
550 550
551 551 void CompactibleFreeListSpace::reportFreeListStatistics() const {
552 552 assert_lock_strong(&_freelistLock);
553 553 assert(PrintFLSStatistics != 0, "Reporting error");
554 554 _dictionary->report_statistics();
555 555 if (PrintFLSStatistics > 1) {
556 556 reportIndexedFreeListStatistics();
557 557 size_t total_size = totalSizeInIndexedFreeLists() +
558 558 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
559 559 gclog_or_tty->print(" free=" SIZE_FORMAT " frag=%1.4f\n", total_size, flsFrag());
560 560 }
561 561 }
562 562
563 563 void CompactibleFreeListSpace::reportIndexedFreeListStatistics() const {
564 564 assert_lock_strong(&_freelistLock);
565 565 gclog_or_tty->print("Statistics for IndexedFreeLists:\n"
566 566 "--------------------------------\n");
567 567 size_t total_size = totalSizeInIndexedFreeLists();
568 568 size_t free_blocks = numFreeBlocksInIndexedFreeLists();
569 569 gclog_or_tty->print("Total Free Space: " SIZE_FORMAT "\n", total_size);
570 570 gclog_or_tty->print("Max Chunk Size: " SIZE_FORMAT "\n", maxChunkSizeInIndexedFreeLists());
571 571 gclog_or_tty->print("Number of Blocks: " SIZE_FORMAT "\n", free_blocks);
572 572 if (free_blocks != 0) {
573 573 gclog_or_tty->print("Av. Block Size: " SIZE_FORMAT "\n", total_size/free_blocks);
574 574 }
575 575 }
576 576
577 577 size_t CompactibleFreeListSpace::numFreeBlocksInIndexedFreeLists() const {
578 578 size_t res = 0;
579 579 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
580 580 debug_only(
581 581 ssize_t recount = 0;
582 582 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
583 583 fc = fc->next()) {
584 584 recount += 1;
585 585 }
586 586 assert(recount == _indexedFreeList[i].count(),
587 587 "Incorrect count in list");
588 588 )
589 589 res += _indexedFreeList[i].count();
590 590 }
591 591 return res;
592 592 }
593 593
594 594 size_t CompactibleFreeListSpace::maxChunkSizeInIndexedFreeLists() const {
595 595 for (size_t i = IndexSetSize - 1; i != 0; i -= IndexSetStride) {
596 596 if (_indexedFreeList[i].head() != NULL) {
597 597 assert(_indexedFreeList[i].count() != 0, "Inconsistent FreeList");
598 598 return (size_t)i;
599 599 }
600 600 }
601 601 return 0;
602 602 }
603 603
604 604 void CompactibleFreeListSpace::set_end(HeapWord* value) {
605 605 HeapWord* prevEnd = end();
606 606 assert(prevEnd != value, "unnecessary set_end call");
607 607 assert(prevEnd == NULL || !BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(),
608 608 "New end is below unallocated block");
609 609 _end = value;
610 610 if (prevEnd != NULL) {
611 611 // Resize the underlying block offset table.
612 612 _bt.resize(pointer_delta(value, bottom()));
613 613 if (value <= prevEnd) {
614 614 assert(!BlockOffsetArrayUseUnallocatedBlock || value >= unallocated_block(),
615 615 "New end is below unallocated block");
616 616 } else {
617 617 // Now, take this new chunk and add it to the free blocks.
618 618 // Note that the BOT has not yet been updated for this block.
619 619 size_t newFcSize = pointer_delta(value, prevEnd);
620 620 // XXX This is REALLY UGLY and should be fixed up. XXX
621 621 if (!_adaptive_freelists && _smallLinearAllocBlock._ptr == NULL) {
622 622 // Mark the boundary of the new block in BOT
623 623 _bt.mark_block(prevEnd, value);
624 624 // put it all in the linAB
625 625 if (ParallelGCThreads == 0) {
626 626 _smallLinearAllocBlock._ptr = prevEnd;
627 627 _smallLinearAllocBlock._word_size = newFcSize;
628 628 repairLinearAllocBlock(&_smallLinearAllocBlock);
629 629 } else { // ParallelGCThreads > 0
630 630 MutexLockerEx x(parDictionaryAllocLock(),
631 631 Mutex::_no_safepoint_check_flag);
632 632 _smallLinearAllocBlock._ptr = prevEnd;
633 633 _smallLinearAllocBlock._word_size = newFcSize;
634 634 repairLinearAllocBlock(&_smallLinearAllocBlock);
635 635 }
636 636 // Births of chunks put into a LinAB are not recorded. Births
637 637 // of chunks as they are allocated out of a LinAB are.
638 638 } else {
639 639 // Add the block to the free lists, if possible coalescing it
640 640 // with the last free block, and update the BOT and census data.
641 641 addChunkToFreeListsAtEndRecordingStats(prevEnd, newFcSize);
642 642 }
643 643 }
644 644 }
645 645 }
646 646
647 647 class FreeListSpace_DCTOC : public Filtering_DCTOC {
648 648 CompactibleFreeListSpace* _cfls;
649 649 CMSCollector* _collector;
650 650 protected:
651 651 // Override.
652 652 #define walk_mem_region_with_cl_DECL(ClosureType) \
653 653 virtual void walk_mem_region_with_cl(MemRegion mr, \
654 654 HeapWord* bottom, HeapWord* top, \
655 655 ClosureType* cl); \
656 656 void walk_mem_region_with_cl_par(MemRegion mr, \
657 657 HeapWord* bottom, HeapWord* top, \
658 658 ClosureType* cl); \
659 659 void walk_mem_region_with_cl_nopar(MemRegion mr, \
660 660 HeapWord* bottom, HeapWord* top, \
661 661 ClosureType* cl)
662 662 walk_mem_region_with_cl_DECL(ExtendedOopClosure);
663 663 walk_mem_region_with_cl_DECL(FilteringClosure);
664 664
665 665 public:
666 666 FreeListSpace_DCTOC(CompactibleFreeListSpace* sp,
667 667 CMSCollector* collector,
668 668 ExtendedOopClosure* cl,
669 669 CardTableModRefBS::PrecisionStyle precision,
670 670 HeapWord* boundary) :
671 671 Filtering_DCTOC(sp, cl, precision, boundary),
672 672 _cfls(sp), _collector(collector) {}
673 673 };
674 674
675 675 // We de-virtualize the block-related calls below, since we know that our
676 676 // space is a CompactibleFreeListSpace.
677 677
678 678 #define FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(ClosureType) \
679 679 void FreeListSpace_DCTOC::walk_mem_region_with_cl(MemRegion mr, \
680 680 HeapWord* bottom, \
681 681 HeapWord* top, \
682 682 ClosureType* cl) { \
683 683 bool is_par = SharedHeap::heap()->n_par_threads() > 0; \
684 684 if (is_par) { \
685 685 assert(SharedHeap::heap()->n_par_threads() == \
686 686 SharedHeap::heap()->workers()->active_workers(), "Mismatch"); \
687 687 walk_mem_region_with_cl_par(mr, bottom, top, cl); \
688 688 } else { \
689 689 walk_mem_region_with_cl_nopar(mr, bottom, top, cl); \
690 690 } \
691 691 } \
692 692 void FreeListSpace_DCTOC::walk_mem_region_with_cl_par(MemRegion mr, \
693 693 HeapWord* bottom, \
694 694 HeapWord* top, \
695 695 ClosureType* cl) { \
696 696 /* Skip parts that are before "mr", in case "block_start" sent us \
697 697 back too far. */ \
698 698 HeapWord* mr_start = mr.start(); \
699 699 size_t bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \
700 700 HeapWord* next = bottom + bot_size; \
701 701 while (next < mr_start) { \
702 702 bottom = next; \
703 703 bot_size = _cfls->CompactibleFreeListSpace::block_size(bottom); \
704 704 next = bottom + bot_size; \
705 705 } \
706 706 \
707 707 while (bottom < top) { \
708 708 if (_cfls->CompactibleFreeListSpace::block_is_obj(bottom) && \
709 709 !_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \
710 710 oop(bottom)) && \
711 711 !_collector->CMSCollector::is_dead_obj(oop(bottom))) { \
712 712 size_t word_sz = oop(bottom)->oop_iterate(cl, mr); \
713 713 bottom += _cfls->adjustObjectSize(word_sz); \
714 714 } else { \
715 715 bottom += _cfls->CompactibleFreeListSpace::block_size(bottom); \
716 716 } \
717 717 } \
718 718 } \
719 719 void FreeListSpace_DCTOC::walk_mem_region_with_cl_nopar(MemRegion mr, \
720 720 HeapWord* bottom, \
721 721 HeapWord* top, \
722 722 ClosureType* cl) { \
723 723 /* Skip parts that are before "mr", in case "block_start" sent us \
724 724 back too far. */ \
725 725 HeapWord* mr_start = mr.start(); \
726 726 size_t bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
727 727 HeapWord* next = bottom + bot_size; \
728 728 while (next < mr_start) { \
729 729 bottom = next; \
730 730 bot_size = _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
731 731 next = bottom + bot_size; \
732 732 } \
733 733 \
734 734 while (bottom < top) { \
735 735 if (_cfls->CompactibleFreeListSpace::block_is_obj_nopar(bottom) && \
736 736 !_cfls->CompactibleFreeListSpace::obj_allocated_since_save_marks( \
737 737 oop(bottom)) && \
738 738 !_collector->CMSCollector::is_dead_obj(oop(bottom))) { \
739 739 size_t word_sz = oop(bottom)->oop_iterate(cl, mr); \
740 740 bottom += _cfls->adjustObjectSize(word_sz); \
741 741 } else { \
742 742 bottom += _cfls->CompactibleFreeListSpace::block_size_nopar(bottom); \
743 743 } \
744 744 } \
745 745 }
746 746
747 747 // (There are only two of these, rather than N, because the split is due
748 748 // only to the introduction of the FilteringClosure, a local part of the
749 749 // impl of this abstraction.)
750 750 FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(ExtendedOopClosure)
751 751 FreeListSpace_DCTOC__walk_mem_region_with_cl_DEFN(FilteringClosure)
752 752
753 753 DirtyCardToOopClosure*
754 754 CompactibleFreeListSpace::new_dcto_cl(ExtendedOopClosure* cl,
755 755 CardTableModRefBS::PrecisionStyle precision,
756 756 HeapWord* boundary) {
757 757 return new FreeListSpace_DCTOC(this, _collector, cl, precision, boundary);
758 758 }
759 759
760 760
761 761 // Note on locking for the space iteration functions:
762 762 // since the collector's iteration activities are concurrent with
763 763 // allocation activities by mutators, absent a suitable mutual exclusion
764 764 // mechanism the iterators may go awry. For instace a block being iterated
765 765 // may suddenly be allocated or divided up and part of it allocated and
766 766 // so on.
767 767
768 768 // Apply the given closure to each block in the space.
769 769 void CompactibleFreeListSpace::blk_iterate_careful(BlkClosureCareful* cl) {
770 770 assert_lock_strong(freelistLock());
771 771 HeapWord *cur, *limit;
772 772 for (cur = bottom(), limit = end(); cur < limit;
773 773 cur += cl->do_blk_careful(cur));
774 774 }
775 775
776 776 // Apply the given closure to each block in the space.
777 777 void CompactibleFreeListSpace::blk_iterate(BlkClosure* cl) {
778 778 assert_lock_strong(freelistLock());
779 779 HeapWord *cur, *limit;
780 780 for (cur = bottom(), limit = end(); cur < limit;
781 781 cur += cl->do_blk(cur));
782 782 }
783 783
784 784 // Apply the given closure to each oop in the space.
785 785 void CompactibleFreeListSpace::oop_iterate(ExtendedOopClosure* cl) {
786 786 assert_lock_strong(freelistLock());
787 787 HeapWord *cur, *limit;
788 788 size_t curSize;
789 789 for (cur = bottom(), limit = end(); cur < limit;
790 790 cur += curSize) {
791 791 curSize = block_size(cur);
792 792 if (block_is_obj(cur)) {
793 793 oop(cur)->oop_iterate(cl);
794 794 }
795 795 }
796 796 }
797 797
798 798 // NOTE: In the following methods, in order to safely be able to
799 799 // apply the closure to an object, we need to be sure that the
800 800 // object has been initialized. We are guaranteed that an object
801 801 // is initialized if we are holding the Heap_lock with the
802 802 // world stopped.
803 803 void CompactibleFreeListSpace::verify_objects_initialized() const {
804 804 if (is_init_completed()) {
805 805 assert_locked_or_safepoint(Heap_lock);
806 806 if (Universe::is_fully_initialized()) {
807 807 guarantee(SafepointSynchronize::is_at_safepoint(),
808 808 "Required for objects to be initialized");
809 809 }
810 810 } // else make a concession at vm start-up
811 811 }
812 812
813 813 // Apply the given closure to each object in the space
814 814 void CompactibleFreeListSpace::object_iterate(ObjectClosure* blk) {
815 815 assert_lock_strong(freelistLock());
816 816 NOT_PRODUCT(verify_objects_initialized());
817 817 HeapWord *cur, *limit;
818 818 size_t curSize;
819 819 for (cur = bottom(), limit = end(); cur < limit;
820 820 cur += curSize) {
821 821 curSize = block_size(cur);
822 822 if (block_is_obj(cur)) {
823 823 blk->do_object(oop(cur));
824 824 }
825 825 }
826 826 }
827 827
828 828 // Apply the given closure to each live object in the space
829 829 // The usage of CompactibleFreeListSpace
830 830 // by the ConcurrentMarkSweepGeneration for concurrent GC's allows
831 831 // objects in the space with references to objects that are no longer
832 832 // valid. For example, an object may reference another object
833 833 // that has already been sweep up (collected). This method uses
834 834 // obj_is_alive() to determine whether it is safe to apply the closure to
835 835 // an object. See obj_is_alive() for details on how liveness of an
836 836 // object is decided.
837 837
838 838 void CompactibleFreeListSpace::safe_object_iterate(ObjectClosure* blk) {
839 839 assert_lock_strong(freelistLock());
840 840 NOT_PRODUCT(verify_objects_initialized());
841 841 HeapWord *cur, *limit;
842 842 size_t curSize;
843 843 for (cur = bottom(), limit = end(); cur < limit;
844 844 cur += curSize) {
845 845 curSize = block_size(cur);
846 846 if (block_is_obj(cur) && obj_is_alive(cur)) {
847 847 blk->do_object(oop(cur));
848 848 }
849 849 }
850 850 }
851 851
852 852 void CompactibleFreeListSpace::object_iterate_mem(MemRegion mr,
853 853 UpwardsObjectClosure* cl) {
854 854 assert_locked(freelistLock());
855 855 NOT_PRODUCT(verify_objects_initialized());
856 856 assert(!mr.is_empty(), "Should be non-empty");
857 857 // We use MemRegion(bottom(), end()) rather than used_region() below
858 858 // because the two are not necessarily equal for some kinds of
859 859 // spaces, in particular, certain kinds of free list spaces.
860 860 // We could use the more complicated but more precise:
861 861 // MemRegion(used_region().start(), round_to(used_region().end(), CardSize))
862 862 // but the slight imprecision seems acceptable in the assertion check.
863 863 assert(MemRegion(bottom(), end()).contains(mr),
864 864 "Should be within used space");
865 865 HeapWord* prev = cl->previous(); // max address from last time
866 866 if (prev >= mr.end()) { // nothing to do
867 867 return;
868 868 }
869 869 // This assert will not work when we go from cms space to perm
870 870 // space, and use same closure. Easy fix deferred for later. XXX YSR
871 871 // assert(prev == NULL || contains(prev), "Should be within space");
872 872
873 873 bool last_was_obj_array = false;
874 874 HeapWord *blk_start_addr, *region_start_addr;
875 875 if (prev > mr.start()) {
876 876 region_start_addr = prev;
877 877 blk_start_addr = prev;
878 878 // The previous invocation may have pushed "prev" beyond the
879 879 // last allocated block yet there may be still be blocks
880 880 // in this region due to a particular coalescing policy.
881 881 // Relax the assertion so that the case where the unallocated
882 882 // block is maintained and "prev" is beyond the unallocated
883 883 // block does not cause the assertion to fire.
884 884 assert((BlockOffsetArrayUseUnallocatedBlock &&
885 885 (!is_in(prev))) ||
886 886 (blk_start_addr == block_start(region_start_addr)), "invariant");
887 887 } else {
888 888 region_start_addr = mr.start();
889 889 blk_start_addr = block_start(region_start_addr);
890 890 }
891 891 HeapWord* region_end_addr = mr.end();
892 892 MemRegion derived_mr(region_start_addr, region_end_addr);
893 893 while (blk_start_addr < region_end_addr) {
894 894 const size_t size = block_size(blk_start_addr);
895 895 if (block_is_obj(blk_start_addr)) {
896 896 last_was_obj_array = cl->do_object_bm(oop(blk_start_addr), derived_mr);
897 897 } else {
898 898 last_was_obj_array = false;
899 899 }
900 900 blk_start_addr += size;
901 901 }
902 902 if (!last_was_obj_array) {
903 903 assert((bottom() <= blk_start_addr) && (blk_start_addr <= end()),
904 904 "Should be within (closed) used space");
905 905 assert(blk_start_addr > prev, "Invariant");
906 906 cl->set_previous(blk_start_addr); // min address for next time
907 907 }
908 908 }
909 909
910 910
911 911 // Callers of this iterator beware: The closure application should
912 912 // be robust in the face of uninitialized objects and should (always)
913 913 // return a correct size so that the next addr + size below gives us a
914 914 // valid block boundary. [See for instance,
915 915 // ScanMarkedObjectsAgainCarefullyClosure::do_object_careful()
916 916 // in ConcurrentMarkSweepGeneration.cpp.]
917 917 HeapWord*
918 918 CompactibleFreeListSpace::object_iterate_careful_m(MemRegion mr,
919 919 ObjectClosureCareful* cl) {
920 920 assert_lock_strong(freelistLock());
921 921 // Can't use used_region() below because it may not necessarily
922 922 // be the same as [bottom(),end()); although we could
923 923 // use [used_region().start(),round_to(used_region().end(),CardSize)),
924 924 // that appears too cumbersome, so we just do the simpler check
925 925 // in the assertion below.
926 926 assert(!mr.is_empty() && MemRegion(bottom(),end()).contains(mr),
927 927 "mr should be non-empty and within used space");
928 928 HeapWord *addr, *end;
929 929 size_t size;
930 930 for (addr = block_start_careful(mr.start()), end = mr.end();
931 931 addr < end; addr += size) {
932 932 FreeChunk* fc = (FreeChunk*)addr;
933 933 if (fc->is_free()) {
934 934 // Since we hold the free list lock, which protects direct
935 935 // allocation in this generation by mutators, a free object
936 936 // will remain free throughout this iteration code.
937 937 size = fc->size();
938 938 } else {
939 939 // Note that the object need not necessarily be initialized,
940 940 // because (for instance) the free list lock does NOT protect
941 941 // object initialization. The closure application below must
942 942 // therefore be correct in the face of uninitialized objects.
943 943 size = cl->do_object_careful_m(oop(addr), mr);
944 944 if (size == 0) {
945 945 // An unparsable object found. Signal early termination.
946 946 return addr;
947 947 }
948 948 }
949 949 }
950 950 return NULL;
951 951 }
952 952
953 953
954 954 HeapWord* CompactibleFreeListSpace::block_start_const(const void* p) const {
955 955 NOT_PRODUCT(verify_objects_initialized());
956 956 return _bt.block_start(p);
957 957 }
958 958
959 959 HeapWord* CompactibleFreeListSpace::block_start_careful(const void* p) const {
960 960 return _bt.block_start_careful(p);
961 961 }
962 962
963 963 size_t CompactibleFreeListSpace::block_size(const HeapWord* p) const {
964 964 NOT_PRODUCT(verify_objects_initialized());
965 965 // This must be volatile, or else there is a danger that the compiler
966 966 // will compile the code below into a sometimes-infinite loop, by keeping
967 967 // the value read the first time in a register.
968 968 while (true) {
969 969 // We must do this until we get a consistent view of the object.
970 970 if (FreeChunk::indicatesFreeChunk(p)) {
971 971 volatile FreeChunk* fc = (volatile FreeChunk*)p;
972 972 size_t res = fc->size();
973 973
974 974 // Bugfix for systems with weak memory model (PPC64/IA64). The
975 975 // block's free bit was set and we have read the size of the
976 976 // block. Acquire and check the free bit again. If the block is
977 977 // still free, the read size is correct.
978 978 OrderAccess::acquire();
979 979
980 980 // If the object is still a free chunk, return the size, else it
981 981 // has been allocated so try again.
982 982 if (FreeChunk::indicatesFreeChunk(p)) {
983 983 assert(res != 0, "Block size should not be 0");
984 984 return res;
985 985 }
986 986 } else {
987 987 // must read from what 'p' points to in each loop.
988 988 Klass* k = ((volatile oopDesc*)p)->klass_or_null();
989 989 if (k != NULL) {
990 990 assert(k->is_klass(), "Should really be klass oop.");
991 991 oop o = (oop)p;
992 992 assert(o->is_oop(true /* ignore mark word */), "Should be an oop.");
993 993
994 994 // Bugfix for systems with weak memory model (PPC64/IA64).
995 995 // The object o may be an array. Acquire to make sure that the array
996 996 // size (third word) is consistent.
997 997 OrderAccess::acquire();
998 998
999 999 size_t res = o->size_given_klass(k);
1000 1000 res = adjustObjectSize(res);
1001 1001 assert(res != 0, "Block size should not be 0");
1002 1002 return res;
1003 1003 }
1004 1004 }
1005 1005 }
1006 1006 }
1007 1007
1008 1008 // TODO: Now that is_parsable is gone, we should combine these two functions.
1009 1009 // A variant of the above that uses the Printezis bits for
1010 1010 // unparsable but allocated objects. This avoids any possible
1011 1011 // stalls waiting for mutators to initialize objects, and is
1012 1012 // thus potentially faster than the variant above. However,
1013 1013 // this variant may return a zero size for a block that is
1014 1014 // under mutation and for which a consistent size cannot be
1015 1015 // inferred without stalling; see CMSCollector::block_size_if_printezis_bits().
1016 1016 size_t CompactibleFreeListSpace::block_size_no_stall(HeapWord* p,
1017 1017 const CMSCollector* c)
1018 1018 const {
1019 1019 assert(MemRegion(bottom(), end()).contains(p), "p not in space");
1020 1020 // This must be volatile, or else there is a danger that the compiler
1021 1021 // will compile the code below into a sometimes-infinite loop, by keeping
1022 1022 // the value read the first time in a register.
1023 1023 DEBUG_ONLY(uint loops = 0;)
1024 1024 while (true) {
1025 1025 // We must do this until we get a consistent view of the object.
1026 1026 if (FreeChunk::indicatesFreeChunk(p)) {
1027 1027 volatile FreeChunk* fc = (volatile FreeChunk*)p;
1028 1028 size_t res = fc->size();
1029 1029
1030 1030 // Bugfix for systems with weak memory model (PPC64/IA64). The
1031 1031 // free bit of the block was set and we have read the size of
1032 1032 // the block. Acquire and check the free bit again. If the
1033 1033 // block is still free, the read size is correct.
1034 1034 OrderAccess::acquire();
1035 1035
1036 1036 if (FreeChunk::indicatesFreeChunk(p)) {
1037 1037 assert(res != 0, "Block size should not be 0");
1038 1038 assert(loops == 0, "Should be 0");
1039 1039 return res;
1040 1040 }
1041 1041 } else {
1042 1042 // must read from what 'p' points to in each loop.
1043 1043 Klass* k = ((volatile oopDesc*)p)->klass_or_null();
1044 1044 // We trust the size of any object that has a non-NULL
1045 1045 // klass and (for those in the perm gen) is parsable
1046 1046 // -- irrespective of its conc_safe-ty.
1047 1047 if (k != NULL) {
1048 1048 assert(k->is_klass(), "Should really be klass oop.");
1049 1049 oop o = (oop)p;
1050 1050 assert(o->is_oop(), "Should be an oop");
1051 1051
1052 1052 // Bugfix for systems with weak memory model (PPC64/IA64).
1053 1053 // The object o may be an array. Acquire to make sure that the array
1054 1054 // size (third word) is consistent.
1055 1055 OrderAccess::acquire();
1056 1056
1057 1057 size_t res = o->size_given_klass(k);
1058 1058 res = adjustObjectSize(res);
1059 1059 assert(res != 0, "Block size should not be 0");
1060 1060 return res;
1061 1061 } else {
1062 1062 // May return 0 if P-bits not present.
1063 1063 return c->block_size_if_printezis_bits(p);
1064 1064 }
1065 1065 }
1066 1066 assert(loops == 0, "Can loop at most once");
1067 1067 DEBUG_ONLY(loops++;)
1068 1068 }
1069 1069 }
1070 1070
1071 1071 size_t CompactibleFreeListSpace::block_size_nopar(const HeapWord* p) const {
1072 1072 NOT_PRODUCT(verify_objects_initialized());
1073 1073 assert(MemRegion(bottom(), end()).contains(p), "p not in space");
1074 1074 FreeChunk* fc = (FreeChunk*)p;
1075 1075 if (fc->is_free()) {
1076 1076 return fc->size();
1077 1077 } else {
1078 1078 // Ignore mark word because this may be a recently promoted
1079 1079 // object whose mark word is used to chain together grey
1080 1080 // objects (the last one would have a null value).
1081 1081 assert(oop(p)->is_oop(true), "Should be an oop");
1082 1082 return adjustObjectSize(oop(p)->size());
1083 1083 }
1084 1084 }
1085 1085
1086 1086 // This implementation assumes that the property of "being an object" is
1087 1087 // stable. But being a free chunk may not be (because of parallel
1088 1088 // promotion.)
1089 1089 bool CompactibleFreeListSpace::block_is_obj(const HeapWord* p) const {
1090 1090 FreeChunk* fc = (FreeChunk*)p;
1091 1091 assert(is_in_reserved(p), "Should be in space");
1092 1092 // When doing a mark-sweep-compact of the CMS generation, this
1093 1093 // assertion may fail because prepare_for_compaction() uses
1094 1094 // space that is garbage to maintain information on ranges of
1095 1095 // live objects so that these live ranges can be moved as a whole.
1096 1096 // Comment out this assertion until that problem can be solved
1097 1097 // (i.e., that the block start calculation may look at objects
1098 1098 // at address below "p" in finding the object that contains "p"
1099 1099 // and those objects (if garbage) may have been modified to hold
1100 1100 // live range information.
1101 1101 // assert(CollectedHeap::use_parallel_gc_threads() || _bt.block_start(p) == p,
1102 1102 // "Should be a block boundary");
1103 1103 if (FreeChunk::indicatesFreeChunk(p)) return false;
1104 1104 Klass* k = oop(p)->klass_or_null();
1105 1105 if (k != NULL) {
1106 1106 // Ignore mark word because it may have been used to
1107 1107 // chain together promoted objects (the last one
1108 1108 // would have a null value).
1109 1109 assert(oop(p)->is_oop(true), "Should be an oop");
1110 1110 return true;
1111 1111 } else {
1112 1112 return false; // Was not an object at the start of collection.
1113 1113 }
1114 1114 }
1115 1115
1116 1116 // Check if the object is alive. This fact is checked either by consulting
1117 1117 // the main marking bitmap in the sweeping phase or, if it's a permanent
1118 1118 // generation and we're not in the sweeping phase, by checking the
1119 1119 // perm_gen_verify_bit_map where we store the "deadness" information if
1120 1120 // we did not sweep the perm gen in the most recent previous GC cycle.
1121 1121 bool CompactibleFreeListSpace::obj_is_alive(const HeapWord* p) const {
1122 1122 assert(SafepointSynchronize::is_at_safepoint() || !is_init_completed(),
1123 1123 "Else races are possible");
1124 1124 assert(block_is_obj(p), "The address should point to an object");
1125 1125
1126 1126 // If we're sweeping, we use object liveness information from the main bit map
1127 1127 // for both perm gen and old gen.
1128 1128 // We don't need to lock the bitmap (live_map or dead_map below), because
1129 1129 // EITHER we are in the middle of the sweeping phase, and the
1130 1130 // main marking bit map (live_map below) is locked,
1131 1131 // OR we're in other phases and perm_gen_verify_bit_map (dead_map below)
1132 1132 // is stable, because it's mutated only in the sweeping phase.
1133 1133 // NOTE: This method is also used by jmap where, if class unloading is
1134 1134 // off, the results can return "false" for legitimate perm objects,
1135 1135 // when we are not in the midst of a sweeping phase, which can result
1136 1136 // in jmap not reporting certain perm gen objects. This will be moot
1137 1137 // if/when the perm gen goes away in the future.
1138 1138 if (_collector->abstract_state() == CMSCollector::Sweeping) {
1139 1139 CMSBitMap* live_map = _collector->markBitMap();
1140 1140 return live_map->par_isMarked((HeapWord*) p);
1141 1141 }
1142 1142 return true;
1143 1143 }
1144 1144
1145 1145 bool CompactibleFreeListSpace::block_is_obj_nopar(const HeapWord* p) const {
1146 1146 FreeChunk* fc = (FreeChunk*)p;
1147 1147 assert(is_in_reserved(p), "Should be in space");
1148 1148 assert(_bt.block_start(p) == p, "Should be a block boundary");
1149 1149 if (!fc->is_free()) {
1150 1150 // Ignore mark word because it may have been used to
1151 1151 // chain together promoted objects (the last one
1152 1152 // would have a null value).
1153 1153 assert(oop(p)->is_oop(true), "Should be an oop");
1154 1154 return true;
1155 1155 }
1156 1156 return false;
1157 1157 }
1158 1158
1159 1159 // "MT-safe but not guaranteed MT-precise" (TM); you may get an
1160 1160 // approximate answer if you don't hold the freelistlock when you call this.
1161 1161 size_t CompactibleFreeListSpace::totalSizeInIndexedFreeLists() const {
1162 1162 size_t size = 0;
1163 1163 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
1164 1164 debug_only(
1165 1165 // We may be calling here without the lock in which case we
1166 1166 // won't do this modest sanity check.
1167 1167 if (freelistLock()->owned_by_self()) {
1168 1168 size_t total_list_size = 0;
1169 1169 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
1170 1170 fc = fc->next()) {
1171 1171 total_list_size += i;
1172 1172 }
1173 1173 assert(total_list_size == i * _indexedFreeList[i].count(),
1174 1174 "Count in list is incorrect");
1175 1175 }
1176 1176 )
1177 1177 size += i * _indexedFreeList[i].count();
1178 1178 }
1179 1179 return size;
1180 1180 }
1181 1181
1182 1182 HeapWord* CompactibleFreeListSpace::par_allocate(size_t size) {
1183 1183 MutexLockerEx x(freelistLock(), Mutex::_no_safepoint_check_flag);
1184 1184 return allocate(size);
1185 1185 }
1186 1186
1187 1187 HeapWord*
1188 1188 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlockRemainder(size_t size) {
1189 1189 return getChunkFromLinearAllocBlockRemainder(&_smallLinearAllocBlock, size);
1190 1190 }
1191 1191
1192 1192 HeapWord* CompactibleFreeListSpace::allocate(size_t size) {
1193 1193 assert_lock_strong(freelistLock());
1194 1194 HeapWord* res = NULL;
1195 1195 assert(size == adjustObjectSize(size),
1196 1196 "use adjustObjectSize() before calling into allocate()");
1197 1197
1198 1198 if (_adaptive_freelists) {
1199 1199 res = allocate_adaptive_freelists(size);
1200 1200 } else { // non-adaptive free lists
1201 1201 res = allocate_non_adaptive_freelists(size);
1202 1202 }
1203 1203
1204 1204 if (res != NULL) {
1205 1205 // check that res does lie in this space!
1206 1206 assert(is_in_reserved(res), "Not in this space!");
1207 1207 assert(is_aligned((void*)res), "alignment check");
1208 1208
1209 1209 FreeChunk* fc = (FreeChunk*)res;
1210 1210 fc->markNotFree();
1211 1211 assert(!fc->is_free(), "shouldn't be marked free");
1212 1212 assert(oop(fc)->klass_or_null() == NULL, "should look uninitialized");
1213 1213 // Verify that the block offset table shows this to
1214 1214 // be a single block, but not one which is unallocated.
1215 1215 _bt.verify_single_block(res, size);
1216 1216 _bt.verify_not_unallocated(res, size);
1217 1217 // mangle a just allocated object with a distinct pattern.
1218 1218 debug_only(fc->mangleAllocated(size));
1219 1219 }
1220 1220
1221 1221 return res;
1222 1222 }
1223 1223
1224 1224 HeapWord* CompactibleFreeListSpace::allocate_non_adaptive_freelists(size_t size) {
1225 1225 HeapWord* res = NULL;
1226 1226 // try and use linear allocation for smaller blocks
1227 1227 if (size < _smallLinearAllocBlock._allocation_size_limit) {
1228 1228 // if successful, the following also adjusts block offset table
1229 1229 res = getChunkFromSmallLinearAllocBlock(size);
1230 1230 }
1231 1231 // Else triage to indexed lists for smaller sizes
1232 1232 if (res == NULL) {
1233 1233 if (size < SmallForDictionary) {
1234 1234 res = (HeapWord*) getChunkFromIndexedFreeList(size);
1235 1235 } else {
1236 1236 // else get it from the big dictionary; if even this doesn't
1237 1237 // work we are out of luck.
1238 1238 res = (HeapWord*)getChunkFromDictionaryExact(size);
1239 1239 }
1240 1240 }
1241 1241
1242 1242 return res;
1243 1243 }
1244 1244
1245 1245 HeapWord* CompactibleFreeListSpace::allocate_adaptive_freelists(size_t size) {
1246 1246 assert_lock_strong(freelistLock());
1247 1247 HeapWord* res = NULL;
1248 1248 assert(size == adjustObjectSize(size),
1249 1249 "use adjustObjectSize() before calling into allocate()");
1250 1250
1251 1251 // Strategy
1252 1252 // if small
1253 1253 // exact size from small object indexed list if small
1254 1254 // small or large linear allocation block (linAB) as appropriate
1255 1255 // take from lists of greater sized chunks
1256 1256 // else
1257 1257 // dictionary
1258 1258 // small or large linear allocation block if it has the space
1259 1259 // Try allocating exact size from indexTable first
1260 1260 if (size < IndexSetSize) {
1261 1261 res = (HeapWord*) getChunkFromIndexedFreeList(size);
1262 1262 if(res != NULL) {
1263 1263 assert(res != (HeapWord*)_indexedFreeList[size].head(),
1264 1264 "Not removed from free list");
1265 1265 // no block offset table adjustment is necessary on blocks in
1266 1266 // the indexed lists.
1267 1267
1268 1268 // Try allocating from the small LinAB
1269 1269 } else if (size < _smallLinearAllocBlock._allocation_size_limit &&
1270 1270 (res = getChunkFromSmallLinearAllocBlock(size)) != NULL) {
1271 1271 // if successful, the above also adjusts block offset table
1272 1272 // Note that this call will refill the LinAB to
1273 1273 // satisfy the request. This is different that
1274 1274 // evm.
1275 1275 // Don't record chunk off a LinAB? smallSplitBirth(size);
1276 1276 } else {
1277 1277 // Raid the exact free lists larger than size, even if they are not
1278 1278 // overpopulated.
1279 1279 res = (HeapWord*) getChunkFromGreater(size);
1280 1280 }
1281 1281 } else {
1282 1282 // Big objects get allocated directly from the dictionary.
1283 1283 res = (HeapWord*) getChunkFromDictionaryExact(size);
1284 1284 if (res == NULL) {
1285 1285 // Try hard not to fail since an allocation failure will likely
1286 1286 // trigger a synchronous GC. Try to get the space from the
1287 1287 // allocation blocks.
1288 1288 res = getChunkFromSmallLinearAllocBlockRemainder(size);
1289 1289 }
1290 1290 }
1291 1291
1292 1292 return res;
1293 1293 }
1294 1294
1295 1295 // A worst-case estimate of the space required (in HeapWords) to expand the heap
1296 1296 // when promoting obj.
1297 1297 size_t CompactibleFreeListSpace::expansionSpaceRequired(size_t obj_size) const {
1298 1298 // Depending on the object size, expansion may require refilling either a
1299 1299 // bigLAB or a smallLAB plus refilling a PromotionInfo object. MinChunkSize
1300 1300 // is added because the dictionary may over-allocate to avoid fragmentation.
1301 1301 size_t space = obj_size;
1302 1302 if (!_adaptive_freelists) {
1303 1303 space = MAX2(space, _smallLinearAllocBlock._refillSize);
1304 1304 }
1305 1305 space += _promoInfo.refillSize() + 2 * MinChunkSize;
1306 1306 return space;
1307 1307 }
1308 1308
1309 1309 FreeChunk* CompactibleFreeListSpace::getChunkFromGreater(size_t numWords) {
1310 1310 FreeChunk* ret;
1311 1311
1312 1312 assert(numWords >= MinChunkSize, "Size is less than minimum");
1313 1313 assert(linearAllocationWouldFail() || bestFitFirst(),
1314 1314 "Should not be here");
1315 1315
1316 1316 size_t i;
1317 1317 size_t currSize = numWords + MinChunkSize;
1318 1318 assert(currSize % MinObjAlignment == 0, "currSize should be aligned");
1319 1319 for (i = currSize; i < IndexSetSize; i += IndexSetStride) {
1320 1320 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
1321 1321 if (fl->head()) {
1322 1322 ret = getFromListGreater(fl, numWords);
1323 1323 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
1324 1324 return ret;
1325 1325 }
1326 1326 }
1327 1327
1328 1328 currSize = MAX2((size_t)SmallForDictionary,
1329 1329 (size_t)(numWords + MinChunkSize));
1330 1330
1331 1331 /* Try to get a chunk that satisfies request, while avoiding
1332 1332 fragmentation that can't be handled. */
1333 1333 {
1334 1334 ret = dictionary()->get_chunk(currSize);
1335 1335 if (ret != NULL) {
1336 1336 assert(ret->size() - numWords >= MinChunkSize,
1337 1337 "Chunk is too small");
1338 1338 _bt.allocated((HeapWord*)ret, ret->size());
1339 1339 /* Carve returned chunk. */
1340 1340 (void) splitChunkAndReturnRemainder(ret, numWords);
1341 1341 /* Label this as no longer a free chunk. */
1342 1342 assert(ret->is_free(), "This chunk should be free");
1343 1343 ret->link_prev(NULL);
1344 1344 }
1345 1345 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
1346 1346 return ret;
1347 1347 }
1348 1348 ShouldNotReachHere();
1349 1349 }
1350 1350
1351 1351 bool CompactibleFreeListSpace::verifyChunkInIndexedFreeLists(FreeChunk* fc) const {
1352 1352 assert(fc->size() < IndexSetSize, "Size of chunk is too large");
1353 1353 return _indexedFreeList[fc->size()].verify_chunk_in_free_list(fc);
1354 1354 }
1355 1355
1356 1356 bool CompactibleFreeListSpace::verify_chunk_is_linear_alloc_block(FreeChunk* fc) const {
1357 1357 assert((_smallLinearAllocBlock._ptr != (HeapWord*)fc) ||
1358 1358 (_smallLinearAllocBlock._word_size == fc->size()),
1359 1359 "Linear allocation block shows incorrect size");
1360 1360 return ((_smallLinearAllocBlock._ptr == (HeapWord*)fc) &&
1361 1361 (_smallLinearAllocBlock._word_size == fc->size()));
1362 1362 }
1363 1363
1364 1364 // Check if the purported free chunk is present either as a linear
1365 1365 // allocation block, the size-indexed table of (smaller) free blocks,
1366 1366 // or the larger free blocks kept in the binary tree dictionary.
1367 1367 bool CompactibleFreeListSpace::verify_chunk_in_free_list(FreeChunk* fc) const {
1368 1368 if (verify_chunk_is_linear_alloc_block(fc)) {
1369 1369 return true;
1370 1370 } else if (fc->size() < IndexSetSize) {
1371 1371 return verifyChunkInIndexedFreeLists(fc);
1372 1372 } else {
1373 1373 return dictionary()->verify_chunk_in_free_list(fc);
1374 1374 }
1375 1375 }
1376 1376
1377 1377 #ifndef PRODUCT
1378 1378 void CompactibleFreeListSpace::assert_locked() const {
1379 1379 CMSLockVerifier::assert_locked(freelistLock(), parDictionaryAllocLock());
1380 1380 }
1381 1381
1382 1382 void CompactibleFreeListSpace::assert_locked(const Mutex* lock) const {
1383 1383 CMSLockVerifier::assert_locked(lock);
1384 1384 }
1385 1385 #endif
1386 1386
1387 1387 FreeChunk* CompactibleFreeListSpace::allocateScratch(size_t size) {
1388 1388 // In the parallel case, the main thread holds the free list lock
1389 1389 // on behalf the parallel threads.
1390 1390 FreeChunk* fc;
1391 1391 {
1392 1392 // If GC is parallel, this might be called by several threads.
1393 1393 // This should be rare enough that the locking overhead won't affect
1394 1394 // the sequential code.
1395 1395 MutexLockerEx x(parDictionaryAllocLock(),
1396 1396 Mutex::_no_safepoint_check_flag);
1397 1397 fc = getChunkFromDictionary(size);
1398 1398 }
1399 1399 if (fc != NULL) {
1400 1400 fc->dontCoalesce();
1401 1401 assert(fc->is_free(), "Should be free, but not coalescable");
1402 1402 // Verify that the block offset table shows this to
1403 1403 // be a single block, but not one which is unallocated.
1404 1404 _bt.verify_single_block((HeapWord*)fc, fc->size());
1405 1405 _bt.verify_not_unallocated((HeapWord*)fc, fc->size());
1406 1406 }
1407 1407 return fc;
1408 1408 }
1409 1409
1410 1410 oop CompactibleFreeListSpace::promote(oop obj, size_t obj_size) {
1411 1411 assert(obj_size == (size_t)obj->size(), "bad obj_size passed in");
1412 1412 assert_locked();
1413 1413
1414 1414 // if we are tracking promotions, then first ensure space for
1415 1415 // promotion (including spooling space for saving header if necessary).
1416 1416 // then allocate and copy, then track promoted info if needed.
1417 1417 // When tracking (see PromotionInfo::track()), the mark word may
1418 1418 // be displaced and in this case restoration of the mark word
1419 1419 // occurs in the (oop_since_save_marks_)iterate phase.
1420 1420 if (_promoInfo.tracking() && !_promoInfo.ensure_spooling_space()) {
1421 1421 return NULL;
1422 1422 }
1423 1423 // Call the allocate(size_t, bool) form directly to avoid the
1424 1424 // additional call through the allocate(size_t) form. Having
1425 1425 // the compile inline the call is problematic because allocate(size_t)
1426 1426 // is a virtual method.
1427 1427 HeapWord* res = allocate(adjustObjectSize(obj_size));
1428 1428 if (res != NULL) {
1429 1429 Copy::aligned_disjoint_words((HeapWord*)obj, res, obj_size);
1430 1430 // if we should be tracking promotions, do so.
1431 1431 if (_promoInfo.tracking()) {
1432 1432 _promoInfo.track((PromotedObject*)res);
1433 1433 }
1434 1434 }
1435 1435 return oop(res);
1436 1436 }
1437 1437
1438 1438 HeapWord*
1439 1439 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlock(size_t size) {
1440 1440 assert_locked();
1441 1441 assert(size >= MinChunkSize, "minimum chunk size");
1442 1442 assert(size < _smallLinearAllocBlock._allocation_size_limit,
1443 1443 "maximum from smallLinearAllocBlock");
1444 1444 return getChunkFromLinearAllocBlock(&_smallLinearAllocBlock, size);
1445 1445 }
1446 1446
1447 1447 HeapWord*
1448 1448 CompactibleFreeListSpace::getChunkFromLinearAllocBlock(LinearAllocBlock *blk,
1449 1449 size_t size) {
1450 1450 assert_locked();
1451 1451 assert(size >= MinChunkSize, "too small");
1452 1452 HeapWord* res = NULL;
1453 1453 // Try to do linear allocation from blk, making sure that
1454 1454 if (blk->_word_size == 0) {
1455 1455 // We have probably been unable to fill this either in the prologue or
1456 1456 // when it was exhausted at the last linear allocation. Bail out until
1457 1457 // next time.
1458 1458 assert(blk->_ptr == NULL, "consistency check");
1459 1459 return NULL;
1460 1460 }
1461 1461 assert(blk->_word_size != 0 && blk->_ptr != NULL, "consistency check");
1462 1462 res = getChunkFromLinearAllocBlockRemainder(blk, size);
1463 1463 if (res != NULL) return res;
1464 1464
1465 1465 // about to exhaust this linear allocation block
1466 1466 if (blk->_word_size == size) { // exactly satisfied
1467 1467 res = blk->_ptr;
1468 1468 _bt.allocated(res, blk->_word_size);
1469 1469 } else if (size + MinChunkSize <= blk->_refillSize) {
1470 1470 size_t sz = blk->_word_size;
1471 1471 // Update _unallocated_block if the size is such that chunk would be
1472 1472 // returned to the indexed free list. All other chunks in the indexed
1473 1473 // free lists are allocated from the dictionary so that _unallocated_block
1474 1474 // has already been adjusted for them. Do it here so that the cost
1475 1475 // for all chunks added back to the indexed free lists.
1476 1476 if (sz < SmallForDictionary) {
1477 1477 _bt.allocated(blk->_ptr, sz);
1478 1478 }
1479 1479 // Return the chunk that isn't big enough, and then refill below.
1480 1480 addChunkToFreeLists(blk->_ptr, sz);
1481 1481 split_birth(sz);
1482 1482 // Don't keep statistics on adding back chunk from a LinAB.
1483 1483 } else {
1484 1484 // A refilled block would not satisfy the request.
1485 1485 return NULL;
1486 1486 }
1487 1487
1488 1488 blk->_ptr = NULL; blk->_word_size = 0;
1489 1489 refillLinearAllocBlock(blk);
1490 1490 assert(blk->_ptr == NULL || blk->_word_size >= size + MinChunkSize,
1491 1491 "block was replenished");
1492 1492 if (res != NULL) {
1493 1493 split_birth(size);
1494 1494 repairLinearAllocBlock(blk);
1495 1495 } else if (blk->_ptr != NULL) {
1496 1496 res = blk->_ptr;
1497 1497 size_t blk_size = blk->_word_size;
1498 1498 blk->_word_size -= size;
1499 1499 blk->_ptr += size;
1500 1500 split_birth(size);
1501 1501 repairLinearAllocBlock(blk);
1502 1502 // Update BOT last so that other (parallel) GC threads see a consistent
1503 1503 // view of the BOT and free blocks.
1504 1504 // Above must occur before BOT is updated below.
1505 1505 OrderAccess::storestore();
1506 1506 _bt.split_block(res, blk_size, size); // adjust block offset table
1507 1507 }
1508 1508 return res;
1509 1509 }
1510 1510
1511 1511 HeapWord* CompactibleFreeListSpace::getChunkFromLinearAllocBlockRemainder(
1512 1512 LinearAllocBlock* blk,
1513 1513 size_t size) {
1514 1514 assert_locked();
1515 1515 assert(size >= MinChunkSize, "too small");
1516 1516
1517 1517 HeapWord* res = NULL;
1518 1518 // This is the common case. Keep it simple.
1519 1519 if (blk->_word_size >= size + MinChunkSize) {
1520 1520 assert(blk->_ptr != NULL, "consistency check");
1521 1521 res = blk->_ptr;
1522 1522 // Note that the BOT is up-to-date for the linAB before allocation. It
1523 1523 // indicates the start of the linAB. The split_block() updates the
1524 1524 // BOT for the linAB after the allocation (indicates the start of the
1525 1525 // next chunk to be allocated).
1526 1526 size_t blk_size = blk->_word_size;
1527 1527 blk->_word_size -= size;
1528 1528 blk->_ptr += size;
1529 1529 split_birth(size);
1530 1530 repairLinearAllocBlock(blk);
1531 1531 // Update BOT last so that other (parallel) GC threads see a consistent
1532 1532 // view of the BOT and free blocks.
1533 1533 // Above must occur before BOT is updated below.
1534 1534 OrderAccess::storestore();
1535 1535 _bt.split_block(res, blk_size, size); // adjust block offset table
1536 1536 _bt.allocated(res, size);
1537 1537 }
1538 1538 return res;
1539 1539 }
1540 1540
1541 1541 FreeChunk*
1542 1542 CompactibleFreeListSpace::getChunkFromIndexedFreeList(size_t size) {
1543 1543 assert_locked();
1544 1544 assert(size < SmallForDictionary, "just checking");
1545 1545 FreeChunk* res;
1546 1546 res = _indexedFreeList[size].get_chunk_at_head();
1547 1547 if (res == NULL) {
1548 1548 res = getChunkFromIndexedFreeListHelper(size);
1549 1549 }
1550 1550 _bt.verify_not_unallocated((HeapWord*) res, size);
1551 1551 assert(res == NULL || res->size() == size, "Incorrect block size");
1552 1552 return res;
1553 1553 }
1554 1554
1555 1555 FreeChunk*
1556 1556 CompactibleFreeListSpace::getChunkFromIndexedFreeListHelper(size_t size,
1557 1557 bool replenish) {
1558 1558 assert_locked();
1559 1559 FreeChunk* fc = NULL;
1560 1560 if (size < SmallForDictionary) {
1561 1561 assert(_indexedFreeList[size].head() == NULL ||
1562 1562 _indexedFreeList[size].surplus() <= 0,
1563 1563 "List for this size should be empty or under populated");
1564 1564 // Try best fit in exact lists before replenishing the list
1565 1565 if (!bestFitFirst() || (fc = bestFitSmall(size)) == NULL) {
1566 1566 // Replenish list.
1567 1567 //
1568 1568 // Things tried that failed.
1569 1569 // Tried allocating out of the two LinAB's first before
1570 1570 // replenishing lists.
1571 1571 // Tried small linAB of size 256 (size in indexed list)
1572 1572 // and replenishing indexed lists from the small linAB.
1573 1573 //
1574 1574 FreeChunk* newFc = NULL;
1575 1575 const size_t replenish_size = CMSIndexedFreeListReplenish * size;
1576 1576 if (replenish_size < SmallForDictionary) {
1577 1577 // Do not replenish from an underpopulated size.
1578 1578 if (_indexedFreeList[replenish_size].surplus() > 0 &&
1579 1579 _indexedFreeList[replenish_size].head() != NULL) {
1580 1580 newFc = _indexedFreeList[replenish_size].get_chunk_at_head();
1581 1581 } else if (bestFitFirst()) {
1582 1582 newFc = bestFitSmall(replenish_size);
1583 1583 }
1584 1584 }
1585 1585 if (newFc == NULL && replenish_size > size) {
1586 1586 assert(CMSIndexedFreeListReplenish > 1, "ctl pt invariant");
1587 1587 newFc = getChunkFromIndexedFreeListHelper(replenish_size, false);
1588 1588 }
1589 1589 // Note: The stats update re split-death of block obtained above
1590 1590 // will be recorded below precisely when we know we are going to
1591 1591 // be actually splitting it into more than one pieces below.
1592 1592 if (newFc != NULL) {
1593 1593 if (replenish || CMSReplenishIntermediate) {
1594 1594 // Replenish this list and return one block to caller.
1595 1595 size_t i;
1596 1596 FreeChunk *curFc, *nextFc;
1597 1597 size_t num_blk = newFc->size() / size;
1598 1598 assert(num_blk >= 1, "Smaller than requested?");
1599 1599 assert(newFc->size() % size == 0, "Should be integral multiple of request");
1600 1600 if (num_blk > 1) {
1601 1601 // we are sure we will be splitting the block just obtained
1602 1602 // into multiple pieces; record the split-death of the original
1603 1603 splitDeath(replenish_size);
1604 1604 }
1605 1605 // carve up and link blocks 0, ..., num_blk - 2
1606 1606 // The last chunk is not added to the lists but is returned as the
1607 1607 // free chunk.
1608 1608 for (curFc = newFc, nextFc = (FreeChunk*)((HeapWord*)curFc + size),
1609 1609 i = 0;
1610 1610 i < (num_blk - 1);
1611 1611 curFc = nextFc, nextFc = (FreeChunk*)((HeapWord*)nextFc + size),
1612 1612 i++) {
1613 1613 curFc->set_size(size);
1614 1614 // Don't record this as a return in order to try and
1615 1615 // determine the "returns" from a GC.
1616 1616 _bt.verify_not_unallocated((HeapWord*) fc, size);
1617 1617 _indexedFreeList[size].return_chunk_at_tail(curFc, false);
1618 1618 _bt.mark_block((HeapWord*)curFc, size);
1619 1619 split_birth(size);
1620 1620 // Don't record the initial population of the indexed list
1621 1621 // as a split birth.
1622 1622 }
1623 1623
1624 1624 // check that the arithmetic was OK above
1625 1625 assert((HeapWord*)nextFc == (HeapWord*)newFc + num_blk*size,
1626 1626 "inconsistency in carving newFc");
1627 1627 curFc->set_size(size);
1628 1628 _bt.mark_block((HeapWord*)curFc, size);
1629 1629 split_birth(size);
1630 1630 fc = curFc;
1631 1631 } else {
1632 1632 // Return entire block to caller
1633 1633 fc = newFc;
1634 1634 }
1635 1635 }
1636 1636 }
1637 1637 } else {
1638 1638 // Get a free chunk from the free chunk dictionary to be returned to
1639 1639 // replenish the indexed free list.
1640 1640 fc = getChunkFromDictionaryExact(size);
1641 1641 }
1642 1642 // assert(fc == NULL || fc->is_free(), "Should be returning a free chunk");
1643 1643 return fc;
1644 1644 }
1645 1645
1646 1646 FreeChunk*
1647 1647 CompactibleFreeListSpace::getChunkFromDictionary(size_t size) {
1648 1648 assert_locked();
1649 1649 FreeChunk* fc = _dictionary->get_chunk(size,
1650 1650 FreeBlockDictionary<FreeChunk>::atLeast);
1651 1651 if (fc == NULL) {
1652 1652 return NULL;
1653 1653 }
1654 1654 _bt.allocated((HeapWord*)fc, fc->size());
1655 1655 if (fc->size() >= size + MinChunkSize) {
1656 1656 fc = splitChunkAndReturnRemainder(fc, size);
1657 1657 }
1658 1658 assert(fc->size() >= size, "chunk too small");
1659 1659 assert(fc->size() < size + MinChunkSize, "chunk too big");
1660 1660 _bt.verify_single_block((HeapWord*)fc, fc->size());
1661 1661 return fc;
1662 1662 }
1663 1663
1664 1664 FreeChunk*
1665 1665 CompactibleFreeListSpace::getChunkFromDictionaryExact(size_t size) {
1666 1666 assert_locked();
1667 1667 FreeChunk* fc = _dictionary->get_chunk(size,
1668 1668 FreeBlockDictionary<FreeChunk>::atLeast);
1669 1669 if (fc == NULL) {
1670 1670 return fc;
1671 1671 }
1672 1672 _bt.allocated((HeapWord*)fc, fc->size());
1673 1673 if (fc->size() == size) {
1674 1674 _bt.verify_single_block((HeapWord*)fc, size);
1675 1675 return fc;
1676 1676 }
1677 1677 assert(fc->size() > size, "get_chunk() guarantee");
1678 1678 if (fc->size() < size + MinChunkSize) {
1679 1679 // Return the chunk to the dictionary and go get a bigger one.
1680 1680 returnChunkToDictionary(fc);
1681 1681 fc = _dictionary->get_chunk(size + MinChunkSize,
1682 1682 FreeBlockDictionary<FreeChunk>::atLeast);
1683 1683 if (fc == NULL) {
1684 1684 return NULL;
1685 1685 }
1686 1686 _bt.allocated((HeapWord*)fc, fc->size());
1687 1687 }
1688 1688 assert(fc->size() >= size + MinChunkSize, "tautology");
1689 1689 fc = splitChunkAndReturnRemainder(fc, size);
1690 1690 assert(fc->size() == size, "chunk is wrong size");
1691 1691 _bt.verify_single_block((HeapWord*)fc, size);
1692 1692 return fc;
1693 1693 }
1694 1694
1695 1695 void
1696 1696 CompactibleFreeListSpace::returnChunkToDictionary(FreeChunk* chunk) {
1697 1697 assert_locked();
1698 1698
1699 1699 size_t size = chunk->size();
1700 1700 _bt.verify_single_block((HeapWord*)chunk, size);
1701 1701 // adjust _unallocated_block downward, as necessary
1702 1702 _bt.freed((HeapWord*)chunk, size);
1703 1703 _dictionary->return_chunk(chunk);
1704 1704 #ifndef PRODUCT
1705 1705 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) {
1706 1706 TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >* tc = TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::as_TreeChunk(chunk);
1707 1707 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* tl = tc->list();
1708 1708 tl->verify_stats();
1709 1709 }
1710 1710 #endif // PRODUCT
1711 1711 }
1712 1712
1713 1713 void
1714 1714 CompactibleFreeListSpace::returnChunkToFreeList(FreeChunk* fc) {
1715 1715 assert_locked();
1716 1716 size_t size = fc->size();
1717 1717 _bt.verify_single_block((HeapWord*) fc, size);
1718 1718 _bt.verify_not_unallocated((HeapWord*) fc, size);
1719 1719 if (_adaptive_freelists) {
1720 1720 _indexedFreeList[size].return_chunk_at_tail(fc);
1721 1721 } else {
1722 1722 _indexedFreeList[size].return_chunk_at_head(fc);
1723 1723 }
1724 1724 #ifndef PRODUCT
1725 1725 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) {
1726 1726 _indexedFreeList[size].verify_stats();
1727 1727 }
1728 1728 #endif // PRODUCT
1729 1729 }
1730 1730
1731 1731 // Add chunk to end of last block -- if it's the largest
1732 1732 // block -- and update BOT and census data. We would
1733 1733 // of course have preferred to coalesce it with the
1734 1734 // last block, but it's currently less expensive to find the
1735 1735 // largest block than it is to find the last.
1736 1736 void
1737 1737 CompactibleFreeListSpace::addChunkToFreeListsAtEndRecordingStats(
1738 1738 HeapWord* chunk, size_t size) {
1739 1739 // check that the chunk does lie in this space!
1740 1740 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!");
1741 1741 // One of the parallel gc task threads may be here
1742 1742 // whilst others are allocating.
1743 1743 Mutex* lock = NULL;
1744 1744 if (ParallelGCThreads != 0) {
1745 1745 lock = &_parDictionaryAllocLock;
1746 1746 }
1747 1747 FreeChunk* ec;
1748 1748 {
1749 1749 MutexLockerEx x(lock, Mutex::_no_safepoint_check_flag);
1750 1750 ec = dictionary()->find_largest_dict(); // get largest block
1751 1751 if (ec != NULL && ec->end() == (uintptr_t*) chunk) {
1752 1752 // It's a coterminal block - we can coalesce.
1753 1753 size_t old_size = ec->size();
1754 1754 coalDeath(old_size);
1755 1755 removeChunkFromDictionary(ec);
1756 1756 size += old_size;
1757 1757 } else {
1758 1758 ec = (FreeChunk*)chunk;
1759 1759 }
1760 1760 }
1761 1761 ec->set_size(size);
1762 1762 debug_only(ec->mangleFreed(size));
1763 1763 if (size < SmallForDictionary && ParallelGCThreads != 0) {
1764 1764 lock = _indexedFreeListParLocks[size];
1765 1765 }
1766 1766 MutexLockerEx x(lock, Mutex::_no_safepoint_check_flag);
1767 1767 addChunkAndRepairOffsetTable((HeapWord*)ec, size, true);
1768 1768 // record the birth under the lock since the recording involves
1769 1769 // manipulation of the list on which the chunk lives and
1770 1770 // if the chunk is allocated and is the last on the list,
1771 1771 // the list can go away.
1772 1772 coalBirth(size);
1773 1773 }
1774 1774
1775 1775 void
1776 1776 CompactibleFreeListSpace::addChunkToFreeLists(HeapWord* chunk,
1777 1777 size_t size) {
1778 1778 // check that the chunk does lie in this space!
1779 1779 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!");
1780 1780 assert_locked();
1781 1781 _bt.verify_single_block(chunk, size);
1782 1782
1783 1783 FreeChunk* fc = (FreeChunk*) chunk;
1784 1784 fc->set_size(size);
1785 1785 debug_only(fc->mangleFreed(size));
1786 1786 if (size < SmallForDictionary) {
1787 1787 returnChunkToFreeList(fc);
1788 1788 } else {
1789 1789 returnChunkToDictionary(fc);
1790 1790 }
1791 1791 }
1792 1792
1793 1793 void
1794 1794 CompactibleFreeListSpace::addChunkAndRepairOffsetTable(HeapWord* chunk,
1795 1795 size_t size, bool coalesced) {
1796 1796 assert_locked();
1797 1797 assert(chunk != NULL, "null chunk");
1798 1798 if (coalesced) {
1799 1799 // repair BOT
1800 1800 _bt.single_block(chunk, size);
1801 1801 }
1802 1802 addChunkToFreeLists(chunk, size);
1803 1803 }
1804 1804
1805 1805 // We _must_ find the purported chunk on our free lists;
1806 1806 // we assert if we don't.
1807 1807 void
1808 1808 CompactibleFreeListSpace::removeFreeChunkFromFreeLists(FreeChunk* fc) {
1809 1809 size_t size = fc->size();
1810 1810 assert_locked();
1811 1811 debug_only(verifyFreeLists());
1812 1812 if (size < SmallForDictionary) {
1813 1813 removeChunkFromIndexedFreeList(fc);
1814 1814 } else {
1815 1815 removeChunkFromDictionary(fc);
1816 1816 }
1817 1817 _bt.verify_single_block((HeapWord*)fc, size);
1818 1818 debug_only(verifyFreeLists());
1819 1819 }
1820 1820
1821 1821 void
1822 1822 CompactibleFreeListSpace::removeChunkFromDictionary(FreeChunk* fc) {
1823 1823 size_t size = fc->size();
1824 1824 assert_locked();
1825 1825 assert(fc != NULL, "null chunk");
1826 1826 _bt.verify_single_block((HeapWord*)fc, size);
1827 1827 _dictionary->remove_chunk(fc);
1828 1828 // adjust _unallocated_block upward, as necessary
1829 1829 _bt.allocated((HeapWord*)fc, size);
1830 1830 }
1831 1831
1832 1832 void
1833 1833 CompactibleFreeListSpace::removeChunkFromIndexedFreeList(FreeChunk* fc) {
1834 1834 assert_locked();
1835 1835 size_t size = fc->size();
1836 1836 _bt.verify_single_block((HeapWord*)fc, size);
1837 1837 NOT_PRODUCT(
1838 1838 if (FLSVerifyIndexTable) {
1839 1839 verifyIndexedFreeList(size);
1840 1840 }
1841 1841 )
1842 1842 _indexedFreeList[size].remove_chunk(fc);
1843 1843 NOT_PRODUCT(
1844 1844 if (FLSVerifyIndexTable) {
1845 1845 verifyIndexedFreeList(size);
1846 1846 }
1847 1847 )
1848 1848 }
1849 1849
1850 1850 FreeChunk* CompactibleFreeListSpace::bestFitSmall(size_t numWords) {
1851 1851 /* A hint is the next larger size that has a surplus.
1852 1852 Start search at a size large enough to guarantee that
1853 1853 the excess is >= MIN_CHUNK. */
1854 1854 size_t start = align_object_size(numWords + MinChunkSize);
1855 1855 if (start < IndexSetSize) {
1856 1856 AdaptiveFreeList<FreeChunk>* it = _indexedFreeList;
1857 1857 size_t hint = _indexedFreeList[start].hint();
1858 1858 while (hint < IndexSetSize) {
1859 1859 assert(hint % MinObjAlignment == 0, "hint should be aligned");
1860 1860 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[hint];
1861 1861 if (fl->surplus() > 0 && fl->head() != NULL) {
1862 1862 // Found a list with surplus, reset original hint
1863 1863 // and split out a free chunk which is returned.
1864 1864 _indexedFreeList[start].set_hint(hint);
1865 1865 FreeChunk* res = getFromListGreater(fl, numWords);
1866 1866 assert(res == NULL || res->is_free(),
1867 1867 "Should be returning a free chunk");
1868 1868 return res;
1869 1869 }
1870 1870 hint = fl->hint(); /* keep looking */
1871 1871 }
1872 1872 /* None found. */
1873 1873 it[start].set_hint(IndexSetSize);
1874 1874 }
1875 1875 return NULL;
1876 1876 }
1877 1877
1878 1878 /* Requires fl->size >= numWords + MinChunkSize */
1879 1879 FreeChunk* CompactibleFreeListSpace::getFromListGreater(AdaptiveFreeList<FreeChunk>* fl,
1880 1880 size_t numWords) {
1881 1881 FreeChunk *curr = fl->head();
1882 1882 size_t oldNumWords = curr->size();
1883 1883 assert(numWords >= MinChunkSize, "Word size is too small");
1884 1884 assert(curr != NULL, "List is empty");
1885 1885 assert(oldNumWords >= numWords + MinChunkSize,
1886 1886 "Size of chunks in the list is too small");
1887 1887
1888 1888 fl->remove_chunk(curr);
1889 1889 // recorded indirectly by splitChunkAndReturnRemainder -
1890 1890 // smallSplit(oldNumWords, numWords);
1891 1891 FreeChunk* new_chunk = splitChunkAndReturnRemainder(curr, numWords);
1892 1892 // Does anything have to be done for the remainder in terms of
1893 1893 // fixing the card table?
1894 1894 assert(new_chunk == NULL || new_chunk->is_free(),
1895 1895 "Should be returning a free chunk");
1896 1896 return new_chunk;
1897 1897 }
1898 1898
1899 1899 FreeChunk*
1900 1900 CompactibleFreeListSpace::splitChunkAndReturnRemainder(FreeChunk* chunk,
1901 1901 size_t new_size) {
1902 1902 assert_locked();
1903 1903 size_t size = chunk->size();
1904 1904 assert(size > new_size, "Split from a smaller block?");
1905 1905 assert(is_aligned(chunk), "alignment problem");
1906 1906 assert(size == adjustObjectSize(size), "alignment problem");
1907 1907 size_t rem_size = size - new_size;
1908 1908 assert(rem_size == adjustObjectSize(rem_size), "alignment problem");
1909 1909 assert(rem_size >= MinChunkSize, "Free chunk smaller than minimum");
1910 1910 FreeChunk* ffc = (FreeChunk*)((HeapWord*)chunk + new_size);
1911 1911 assert(is_aligned(ffc), "alignment problem");
1912 1912 ffc->set_size(rem_size);
1913 1913 ffc->link_next(NULL);
1914 1914 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
1915 1915 // Above must occur before BOT is updated below.
1916 1916 // adjust block offset table
1917 1917 OrderAccess::storestore();
1918 1918 assert(chunk->is_free() && ffc->is_free(), "Error");
1919 1919 _bt.split_block((HeapWord*)chunk, chunk->size(), new_size);
1920 1920 if (rem_size < SmallForDictionary) {
1921 1921 bool is_par = (SharedHeap::heap()->n_par_threads() > 0);
1922 1922 if (is_par) _indexedFreeListParLocks[rem_size]->lock();
1923 1923 assert(!is_par ||
1924 1924 (SharedHeap::heap()->n_par_threads() ==
1925 1925 SharedHeap::heap()->workers()->active_workers()), "Mismatch");
1926 1926 returnChunkToFreeList(ffc);
1927 1927 split(size, rem_size);
1928 1928 if (is_par) _indexedFreeListParLocks[rem_size]->unlock();
1929 1929 } else {
1930 1930 returnChunkToDictionary(ffc);
1931 1931 split(size ,rem_size);
1932 1932 }
1933 1933 chunk->set_size(new_size);
1934 1934 return chunk;
1935 1935 }
1936 1936
1937 1937 void
1938 1938 CompactibleFreeListSpace::sweep_completed() {
1939 1939 // Now that space is probably plentiful, refill linear
1940 1940 // allocation blocks as needed.
1941 1941 refillLinearAllocBlocksIfNeeded();
1942 1942 }
1943 1943
1944 1944 void
1945 1945 CompactibleFreeListSpace::gc_prologue() {
1946 1946 assert_locked();
1947 1947 if (PrintFLSStatistics != 0) {
1948 1948 gclog_or_tty->print("Before GC:\n");
1949 1949 reportFreeListStatistics();
1950 1950 }
1951 1951 refillLinearAllocBlocksIfNeeded();
1952 1952 }
1953 1953
1954 1954 void
1955 1955 CompactibleFreeListSpace::gc_epilogue() {
1956 1956 assert_locked();
1957 1957 if (PrintGCDetails && Verbose && !_adaptive_freelists) {
1958 1958 if (_smallLinearAllocBlock._word_size == 0)
1959 1959 warning("CompactibleFreeListSpace(epilogue):: Linear allocation failure");
1960 1960 }
1961 1961 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
1962 1962 _promoInfo.stopTrackingPromotions();
1963 1963 repairLinearAllocationBlocks();
1964 1964 // Print Space's stats
1965 1965 if (PrintFLSStatistics != 0) {
1966 1966 gclog_or_tty->print("After GC:\n");
1967 1967 reportFreeListStatistics();
1968 1968 }
1969 1969 }
1970 1970
1971 1971 // Iteration support, mostly delegated from a CMS generation
1972 1972
1973 1973 void CompactibleFreeListSpace::save_marks() {
1974 1974 assert(Thread::current()->is_VM_thread(),
1975 1975 "Global variable should only be set when single-threaded");
1976 1976 // Mark the "end" of the used space at the time of this call;
1977 1977 // note, however, that promoted objects from this point
1978 1978 // on are tracked in the _promoInfo below.
1979 1979 set_saved_mark_word(unallocated_block());
1980 1980 #ifdef ASSERT
1981 1981 // Check the sanity of save_marks() etc.
1982 1982 MemRegion ur = used_region();
1983 1983 MemRegion urasm = used_region_at_save_marks();
1984 1984 assert(ur.contains(urasm),
1985 1985 err_msg(" Error at save_marks(): [" PTR_FORMAT "," PTR_FORMAT ")"
1986 1986 " should contain [" PTR_FORMAT "," PTR_FORMAT ")",
1987 1987 p2i(ur.start()), p2i(ur.end()), p2i(urasm.start()), p2i(urasm.end())));
1988 1988 #endif
1989 1989 // inform allocator that promotions should be tracked.
1990 1990 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
1991 1991 _promoInfo.startTrackingPromotions();
1992 1992 }
1993 1993
1994 1994 bool CompactibleFreeListSpace::no_allocs_since_save_marks() {
1995 1995 assert(_promoInfo.tracking(), "No preceding save_marks?");
1996 1996 assert(SharedHeap::heap()->n_par_threads() == 0,
1997 1997 "Shouldn't be called if using parallel gc.");
1998 1998 return _promoInfo.noPromotions();
1999 1999 }
2000 2000
2001 2001 #define CFLS_OOP_SINCE_SAVE_MARKS_DEFN(OopClosureType, nv_suffix) \
2002 2002 \
2003 2003 void CompactibleFreeListSpace:: \
2004 2004 oop_since_save_marks_iterate##nv_suffix(OopClosureType* blk) { \
2005 2005 assert(SharedHeap::heap()->n_par_threads() == 0, \
2006 2006 "Shouldn't be called (yet) during parallel part of gc."); \
2007 2007 _promoInfo.promoted_oops_iterate##nv_suffix(blk); \
2008 2008 /* \
2009 2009 * This also restores any displaced headers and removes the elements from \
2010 2010 * the iteration set as they are processed, so that we have a clean slate \
2011 2011 * at the end of the iteration. Note, thus, that if new objects are \
2012 2012 * promoted as a result of the iteration they are iterated over as well. \
2013 2013 */ \
2014 2014 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency"); \
2015 2015 }
2016 2016
2017 2017 ALL_SINCE_SAVE_MARKS_CLOSURES(CFLS_OOP_SINCE_SAVE_MARKS_DEFN)
2018 2018
2019 2019 bool CompactibleFreeListSpace::linearAllocationWouldFail() const {
2020 2020 return _smallLinearAllocBlock._word_size == 0;
2021 2021 }
2022 2022
2023 2023 void CompactibleFreeListSpace::repairLinearAllocationBlocks() {
2024 2024 // Fix up linear allocation blocks to look like free blocks
2025 2025 repairLinearAllocBlock(&_smallLinearAllocBlock);
2026 2026 }
2027 2027
2028 2028 void CompactibleFreeListSpace::repairLinearAllocBlock(LinearAllocBlock* blk) {
2029 2029 assert_locked();
2030 2030 if (blk->_ptr != NULL) {
2031 2031 assert(blk->_word_size != 0 && blk->_word_size >= MinChunkSize,
2032 2032 "Minimum block size requirement");
2033 2033 FreeChunk* fc = (FreeChunk*)(blk->_ptr);
2034 2034 fc->set_size(blk->_word_size);
2035 2035 fc->link_prev(NULL); // mark as free
2036 2036 fc->dontCoalesce();
2037 2037 assert(fc->is_free(), "just marked it free");
2038 2038 assert(fc->cantCoalesce(), "just marked it uncoalescable");
2039 2039 }
2040 2040 }
2041 2041
2042 2042 void CompactibleFreeListSpace::refillLinearAllocBlocksIfNeeded() {
2043 2043 assert_locked();
2044 2044 if (_smallLinearAllocBlock._ptr == NULL) {
2045 2045 assert(_smallLinearAllocBlock._word_size == 0,
2046 2046 "Size of linAB should be zero if the ptr is NULL");
2047 2047 // Reset the linAB refill and allocation size limit.
2048 2048 _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc, SmallForLinearAlloc);
2049 2049 }
2050 2050 refillLinearAllocBlockIfNeeded(&_smallLinearAllocBlock);
2051 2051 }
2052 2052
2053 2053 void
2054 2054 CompactibleFreeListSpace::refillLinearAllocBlockIfNeeded(LinearAllocBlock* blk) {
2055 2055 assert_locked();
2056 2056 assert((blk->_ptr == NULL && blk->_word_size == 0) ||
2057 2057 (blk->_ptr != NULL && blk->_word_size >= MinChunkSize),
2058 2058 "blk invariant");
2059 2059 if (blk->_ptr == NULL) {
2060 2060 refillLinearAllocBlock(blk);
2061 2061 }
2062 2062 if (PrintMiscellaneous && Verbose) {
2063 2063 if (blk->_word_size == 0) {
2064 2064 warning("CompactibleFreeListSpace(prologue):: Linear allocation failure");
2065 2065 }
2066 2066 }
2067 2067 }
2068 2068
2069 2069 void
2070 2070 CompactibleFreeListSpace::refillLinearAllocBlock(LinearAllocBlock* blk) {
2071 2071 assert_locked();
2072 2072 assert(blk->_word_size == 0 && blk->_ptr == NULL,
2073 2073 "linear allocation block should be empty");
2074 2074 FreeChunk* fc;
2075 2075 if (blk->_refillSize < SmallForDictionary &&
2076 2076 (fc = getChunkFromIndexedFreeList(blk->_refillSize)) != NULL) {
2077 2077 // A linAB's strategy might be to use small sizes to reduce
2078 2078 // fragmentation but still get the benefits of allocation from a
2079 2079 // linAB.
2080 2080 } else {
2081 2081 fc = getChunkFromDictionary(blk->_refillSize);
2082 2082 }
2083 2083 if (fc != NULL) {
2084 2084 blk->_ptr = (HeapWord*)fc;
2085 2085 blk->_word_size = fc->size();
2086 2086 fc->dontCoalesce(); // to prevent sweeper from sweeping us up
2087 2087 }
2088 2088 }
2089 2089
2090 2090 // Support for concurrent collection policy decisions.
2091 2091 bool CompactibleFreeListSpace::should_concurrent_collect() const {
2092 2092 // In the future we might want to add in frgamentation stats --
2093 2093 // including erosion of the "mountain" into this decision as well.
2094 2094 return !adaptive_freelists() && linearAllocationWouldFail();
2095 2095 }
2096 2096
2097 2097 // Support for compaction
2098 2098
2099 2099 void CompactibleFreeListSpace::prepare_for_compaction(CompactPoint* cp) {
2100 2100 SCAN_AND_FORWARD(cp,end,block_is_obj,block_size);
2101 2101 // prepare_for_compaction() uses the space between live objects
2102 2102 // so that later phase can skip dead space quickly. So verification
2103 2103 // of the free lists doesn't work after.
2104 2104 }
2105 2105
2106 2106 #define obj_size(q) adjustObjectSize(oop(q)->size())
2107 2107 #define adjust_obj_size(s) adjustObjectSize(s)
2108 2108
2109 2109 void CompactibleFreeListSpace::adjust_pointers() {
2110 2110 // In other versions of adjust_pointers(), a bail out
2111 2111 // based on the amount of live data in the generation
2112 2112 // (i.e., if 0, bail out) may be used.
2113 2113 // Cannot test used() == 0 here because the free lists have already
2114 2114 // been mangled by the compaction.
2115 2115
2116 2116 SCAN_AND_ADJUST_POINTERS(adjust_obj_size);
2117 2117 // See note about verification in prepare_for_compaction().
2118 2118 }
2119 2119
2120 2120 void CompactibleFreeListSpace::compact() {
2121 2121 SCAN_AND_COMPACT(obj_size);
2122 2122 }
2123 2123
2124 2124 // fragmentation_metric = 1 - [sum of (fbs**2) / (sum of fbs)**2]
2125 2125 // where fbs is free block sizes
2126 2126 double CompactibleFreeListSpace::flsFrag() const {
2127 2127 size_t itabFree = totalSizeInIndexedFreeLists();
2128 2128 double frag = 0.0;
2129 2129 size_t i;
2130 2130
2131 2131 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2132 2132 double sz = i;
2133 2133 frag += _indexedFreeList[i].count() * (sz * sz);
2134 2134 }
2135 2135
2136 2136 double totFree = itabFree +
2137 2137 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
2138 2138 if (totFree > 0) {
2139 2139 frag = ((frag + _dictionary->sum_of_squared_block_sizes()) /
2140 2140 (totFree * totFree));
2141 2141 frag = (double)1.0 - frag;
2142 2142 } else {
2143 2143 assert(frag == 0.0, "Follows from totFree == 0");
2144 2144 }
2145 2145 return frag;
2146 2146 }
2147 2147
2148 2148 void CompactibleFreeListSpace::beginSweepFLCensus(
2149 2149 float inter_sweep_current,
2150 2150 float inter_sweep_estimate,
2151 2151 float intra_sweep_estimate) {
2152 2152 assert_locked();
2153 2153 size_t i;
2154 2154 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2155 2155 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
2156 2156 if (PrintFLSStatistics > 1) {
2157 2157 gclog_or_tty->print("size[" SIZE_FORMAT "] : ", i);
2158 2158 }
2159 2159 fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate);
2160 2160 fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent));
2161 2161 fl->set_before_sweep(fl->count());
2162 2162 fl->set_bfr_surp(fl->surplus());
2163 2163 }
2164 2164 _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent,
2165 2165 inter_sweep_current,
2166 2166 inter_sweep_estimate,
2167 2167 intra_sweep_estimate);
2168 2168 }
2169 2169
2170 2170 void CompactibleFreeListSpace::setFLSurplus() {
2171 2171 assert_locked();
2172 2172 size_t i;
2173 2173 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2174 2174 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2175 2175 fl->set_surplus(fl->count() -
2176 2176 (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent));
2177 2177 }
2178 2178 }
2179 2179
2180 2180 void CompactibleFreeListSpace::setFLHints() {
2181 2181 assert_locked();
2182 2182 size_t i;
2183 2183 size_t h = IndexSetSize;
2184 2184 for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) {
2185 2185 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2186 2186 fl->set_hint(h);
2187 2187 if (fl->surplus() > 0) {
2188 2188 h = i;
2189 2189 }
2190 2190 }
2191 2191 }
2192 2192
2193 2193 void CompactibleFreeListSpace::clearFLCensus() {
2194 2194 assert_locked();
2195 2195 size_t i;
2196 2196 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2197 2197 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2198 2198 fl->set_prev_sweep(fl->count());
2199 2199 fl->set_coal_births(0);
2200 2200 fl->set_coal_deaths(0);
2201 2201 fl->set_split_births(0);
2202 2202 fl->set_split_deaths(0);
2203 2203 }
2204 2204 }
2205 2205
2206 2206 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) {
2207 2207 if (PrintFLSStatistics > 0) {
2208 2208 HeapWord* largestAddr = (HeapWord*) dictionary()->find_largest_dict();
2209 2209 gclog_or_tty->print_cr("CMS: Large block " PTR_FORMAT,
2210 2210 p2i(largestAddr));
2211 2211 }
2212 2212 setFLSurplus();
2213 2213 setFLHints();
2214 2214 if (PrintGC && PrintFLSCensus > 0) {
2215 2215 printFLCensus(sweep_count);
2216 2216 }
2217 2217 clearFLCensus();
2218 2218 assert_locked();
2219 2219 _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent);
2220 2220 }
2221 2221
2222 2222 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) {
2223 2223 if (size < SmallForDictionary) {
2224 2224 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2225 2225 return (fl->coal_desired() < 0) ||
2226 2226 ((int)fl->count() > fl->coal_desired());
2227 2227 } else {
2228 2228 return dictionary()->coal_dict_over_populated(size);
2229 2229 }
2230 2230 }
2231 2231
2232 2232 void CompactibleFreeListSpace::smallCoalBirth(size_t size) {
2233 2233 assert(size < SmallForDictionary, "Size too large for indexed list");
2234 2234 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2235 2235 fl->increment_coal_births();
2236 2236 fl->increment_surplus();
2237 2237 }
2238 2238
2239 2239 void CompactibleFreeListSpace::smallCoalDeath(size_t size) {
2240 2240 assert(size < SmallForDictionary, "Size too large for indexed list");
2241 2241 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2242 2242 fl->increment_coal_deaths();
2243 2243 fl->decrement_surplus();
2244 2244 }
2245 2245
2246 2246 void CompactibleFreeListSpace::coalBirth(size_t size) {
2247 2247 if (size < SmallForDictionary) {
2248 2248 smallCoalBirth(size);
2249 2249 } else {
2250 2250 dictionary()->dict_census_update(size,
2251 2251 false /* split */,
2252 2252 true /* birth */);
2253 2253 }
2254 2254 }
2255 2255
2256 2256 void CompactibleFreeListSpace::coalDeath(size_t size) {
2257 2257 if(size < SmallForDictionary) {
2258 2258 smallCoalDeath(size);
2259 2259 } else {
2260 2260 dictionary()->dict_census_update(size,
2261 2261 false /* split */,
2262 2262 false /* birth */);
2263 2263 }
2264 2264 }
2265 2265
2266 2266 void CompactibleFreeListSpace::smallSplitBirth(size_t size) {
2267 2267 assert(size < SmallForDictionary, "Size too large for indexed list");
2268 2268 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2269 2269 fl->increment_split_births();
2270 2270 fl->increment_surplus();
2271 2271 }
2272 2272
2273 2273 void CompactibleFreeListSpace::smallSplitDeath(size_t size) {
2274 2274 assert(size < SmallForDictionary, "Size too large for indexed list");
2275 2275 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2276 2276 fl->increment_split_deaths();
2277 2277 fl->decrement_surplus();
2278 2278 }
2279 2279
2280 2280 void CompactibleFreeListSpace::split_birth(size_t size) {
2281 2281 if (size < SmallForDictionary) {
2282 2282 smallSplitBirth(size);
2283 2283 } else {
2284 2284 dictionary()->dict_census_update(size,
2285 2285 true /* split */,
2286 2286 true /* birth */);
2287 2287 }
2288 2288 }
2289 2289
2290 2290 void CompactibleFreeListSpace::splitDeath(size_t size) {
2291 2291 if (size < SmallForDictionary) {
2292 2292 smallSplitDeath(size);
2293 2293 } else {
2294 2294 dictionary()->dict_census_update(size,
2295 2295 true /* split */,
2296 2296 false /* birth */);
2297 2297 }
2298 2298 }
2299 2299
2300 2300 void CompactibleFreeListSpace::split(size_t from, size_t to1) {
2301 2301 size_t to2 = from - to1;
2302 2302 splitDeath(from);
2303 2303 split_birth(to1);
2304 2304 split_birth(to2);
2305 2305 }
2306 2306
2307 2307 void CompactibleFreeListSpace::print() const {
2308 2308 print_on(tty);
2309 2309 }
2310 2310
2311 2311 void CompactibleFreeListSpace::prepare_for_verify() {
2312 2312 assert_locked();
2313 2313 repairLinearAllocationBlocks();
2314 2314 // Verify that the SpoolBlocks look like free blocks of
2315 2315 // appropriate sizes... To be done ...
2316 2316 }
2317 2317
2318 2318 class VerifyAllBlksClosure: public BlkClosure {
2319 2319 private:
2320 2320 const CompactibleFreeListSpace* _sp;
2321 2321 const MemRegion _span;
2322 2322 HeapWord* _last_addr;
2323 2323 size_t _last_size;
2324 2324 bool _last_was_obj;
2325 2325 bool _last_was_live;
2326 2326
2327 2327 public:
2328 2328 VerifyAllBlksClosure(const CompactibleFreeListSpace* sp,
2329 2329 MemRegion span) : _sp(sp), _span(span),
2330 2330 _last_addr(NULL), _last_size(0),
2331 2331 _last_was_obj(false), _last_was_live(false) { }
2332 2332
2333 2333 virtual size_t do_blk(HeapWord* addr) {
2334 2334 size_t res;
2335 2335 bool was_obj = false;
2336 2336 bool was_live = false;
2337 2337 if (_sp->block_is_obj(addr)) {
2338 2338 was_obj = true;
2339 2339 oop p = oop(addr);
2340 2340 guarantee(p->is_oop(), "Should be an oop");
2341 2341 res = _sp->adjustObjectSize(p->size());
2342 2342 if (_sp->obj_is_alive(addr)) {
2343 2343 was_live = true;
2344 2344 p->verify();
2345 2345 }
2346 2346 } else {
2347 2347 FreeChunk* fc = (FreeChunk*)addr;
2348 2348 res = fc->size();
2349 2349 if (FLSVerifyLists && !fc->cantCoalesce()) {
2350 2350 guarantee(_sp->verify_chunk_in_free_list(fc),
2351 2351 "Chunk should be on a free list");
2352 2352 }
2353 2353 }
2354 2354 if (res == 0) {
2355 2355 gclog_or_tty->print_cr("Livelock: no rank reduction!");
2356 2356 gclog_or_tty->print_cr(
2357 2357 " Current: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n"
2358 2358 " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n",
2359 2359 p2i(addr), res, was_obj ?"true":"false", was_live ?"true":"false",
2360 2360 p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false");
2361 2361 _sp->print_on(gclog_or_tty);
2362 2362 guarantee(false, "Seppuku!");
2363 2363 }
2364 2364 _last_addr = addr;
2365 2365 _last_size = res;
2366 2366 _last_was_obj = was_obj;
2367 2367 _last_was_live = was_live;
2368 2368 return res;
2369 2369 }
2370 2370 };
2371 2371
2372 2372 class VerifyAllOopsClosure: public OopClosure {
2373 2373 private:
2374 2374 const CMSCollector* _collector;
2375 2375 const CompactibleFreeListSpace* _sp;
2376 2376 const MemRegion _span;
2377 2377 const bool _past_remark;
2378 2378 const CMSBitMap* _bit_map;
2379 2379
2380 2380 protected:
2381 2381 void do_oop(void* p, oop obj) {
2382 2382 if (_span.contains(obj)) { // the interior oop points into CMS heap
2383 2383 if (!_span.contains(p)) { // reference from outside CMS heap
2384 2384 // Should be a valid object; the first disjunct below allows
2385 2385 // us to sidestep an assertion in block_is_obj() that insists
2386 2386 // that p be in _sp. Note that several generations (and spaces)
2387 2387 // are spanned by _span (CMS heap) above.
2388 2388 guarantee(!_sp->is_in_reserved(obj) ||
2389 2389 _sp->block_is_obj((HeapWord*)obj),
2390 2390 "Should be an object");
2391 2391 guarantee(obj->is_oop(), "Should be an oop");
2392 2392 obj->verify();
2393 2393 if (_past_remark) {
2394 2394 // Remark has been completed, the object should be marked
2395 2395 _bit_map->isMarked((HeapWord*)obj);
2396 2396 }
2397 2397 } else { // reference within CMS heap
2398 2398 if (_past_remark) {
2399 2399 // Remark has been completed -- so the referent should have
2400 2400 // been marked, if referring object is.
2401 2401 if (_bit_map->isMarked(_collector->block_start(p))) {
2402 2402 guarantee(_bit_map->isMarked((HeapWord*)obj), "Marking error?");
2403 2403 }
2404 2404 }
2405 2405 }
2406 2406 } else if (_sp->is_in_reserved(p)) {
2407 2407 // the reference is from FLS, and points out of FLS
2408 2408 guarantee(obj->is_oop(), "Should be an oop");
2409 2409 obj->verify();
2410 2410 }
2411 2411 }
2412 2412
2413 2413 template <class T> void do_oop_work(T* p) {
2414 2414 T heap_oop = oopDesc::load_heap_oop(p);
2415 2415 if (!oopDesc::is_null(heap_oop)) {
2416 2416 oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);
2417 2417 do_oop(p, obj);
2418 2418 }
2419 2419 }
2420 2420
2421 2421 public:
2422 2422 VerifyAllOopsClosure(const CMSCollector* collector,
2423 2423 const CompactibleFreeListSpace* sp, MemRegion span,
2424 2424 bool past_remark, CMSBitMap* bit_map) :
2425 2425 _collector(collector), _sp(sp), _span(span),
2426 2426 _past_remark(past_remark), _bit_map(bit_map) { }
2427 2427
2428 2428 virtual void do_oop(oop* p) { VerifyAllOopsClosure::do_oop_work(p); }
2429 2429 virtual void do_oop(narrowOop* p) { VerifyAllOopsClosure::do_oop_work(p); }
2430 2430 };
2431 2431
2432 2432 void CompactibleFreeListSpace::verify() const {
2433 2433 assert_lock_strong(&_freelistLock);
2434 2434 verify_objects_initialized();
2435 2435 MemRegion span = _collector->_span;
2436 2436 bool past_remark = (_collector->abstract_state() ==
2437 2437 CMSCollector::Sweeping);
2438 2438
2439 2439 ResourceMark rm;
2440 2440 HandleMark hm;
2441 2441
2442 2442 // Check integrity of CFL data structures
2443 2443 _promoInfo.verify();
2444 2444 _dictionary->verify();
2445 2445 if (FLSVerifyIndexTable) {
2446 2446 verifyIndexedFreeLists();
2447 2447 }
2448 2448 // Check integrity of all objects and free blocks in space
2449 2449 {
2450 2450 VerifyAllBlksClosure cl(this, span);
2451 2451 ((CompactibleFreeListSpace*)this)->blk_iterate(&cl); // cast off const
2452 2452 }
2453 2453 // Check that all references in the heap to FLS
2454 2454 // are to valid objects in FLS or that references in
2455 2455 // FLS are to valid objects elsewhere in the heap
2456 2456 if (FLSVerifyAllHeapReferences)
2457 2457 {
2458 2458 VerifyAllOopsClosure cl(_collector, this, span, past_remark,
2459 2459 _collector->markBitMap());
2460 2460 CollectedHeap* ch = Universe::heap();
2461 2461
2462 2462 // Iterate over all oops in the heap. Uses the _no_header version
2463 2463 // since we are not interested in following the klass pointers.
2464 2464 ch->oop_iterate_no_header(&cl);
2465 2465 }
2466 2466
2467 2467 if (VerifyObjectStartArray) {
2468 2468 // Verify the block offset table
2469 2469 _bt.verify();
2470 2470 }
2471 2471 }
2472 2472
2473 2473 #ifndef PRODUCT
2474 2474 void CompactibleFreeListSpace::verifyFreeLists() const {
2475 2475 if (FLSVerifyLists) {
2476 2476 _dictionary->verify();
2477 2477 verifyIndexedFreeLists();
2478 2478 } else {
2479 2479 if (FLSVerifyDictionary) {
2480 2480 _dictionary->verify();
2481 2481 }
2482 2482 if (FLSVerifyIndexTable) {
2483 2483 verifyIndexedFreeLists();
2484 2484 }
2485 2485 }
2486 2486 }
2487 2487 #endif
2488 2488
2489 2489 void CompactibleFreeListSpace::verifyIndexedFreeLists() const {
2490 2490 size_t i = 0;
2491 2491 for (; i < IndexSetStart; i++) {
2492 2492 guarantee(_indexedFreeList[i].head() == NULL, "should be NULL");
2493 2493 }
2494 2494 for (; i < IndexSetSize; i++) {
2495 2495 verifyIndexedFreeList(i);
2496 2496 }
2497 2497 }
2498 2498
2499 2499 void CompactibleFreeListSpace::verifyIndexedFreeList(size_t size) const {
2500 2500 FreeChunk* fc = _indexedFreeList[size].head();
2501 2501 FreeChunk* tail = _indexedFreeList[size].tail();
2502 2502 size_t num = _indexedFreeList[size].count();
2503 2503 size_t n = 0;
2504 2504 guarantee(((size >= IndexSetStart) && (size % IndexSetStride == 0)) || fc == NULL,
2505 2505 "Slot should have been empty");
2506 2506 for (; fc != NULL; fc = fc->next(), n++) {
2507 2507 guarantee(fc->size() == size, "Size inconsistency");
2508 2508 guarantee(fc->is_free(), "!free?");
2509 2509 guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list");
2510 2510 guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail");
2511 2511 }
2512 2512 guarantee(n == num, "Incorrect count");
2513 2513 }
2514 2514
2515 2515 #ifndef PRODUCT
2516 2516 void CompactibleFreeListSpace::check_free_list_consistency() const {
2517 2517 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize),
2518 2518 "Some sizes can't be allocated without recourse to"
2519 2519 " linear allocation buffers");
2520 2520 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)),
2521 2521 "else MIN_TREE_CHUNK_SIZE is wrong");
2522 2522 assert(IndexSetStart != 0, "IndexSetStart not initialized");
2523 2523 assert(IndexSetStride != 0, "IndexSetStride not initialized");
2524 2524 }
2525 2525 #endif
2526 2526
2527 2527 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const {
2528 2528 assert_lock_strong(&_freelistLock);
2529 2529 AdaptiveFreeList<FreeChunk> total;
2530 2530 gclog_or_tty->print("end sweep# " SIZE_FORMAT "\n", sweep_count);
2531 2531 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
2532 2532 size_t total_free = 0;
2533 2533 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2534 2534 const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2535 2535 total_free += fl->count() * fl->size();
2536 2536 if (i % (40*IndexSetStride) == 0) {
2537 2537 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
2538 2538 }
2539 2539 fl->print_on(gclog_or_tty);
2540 2540 total.set_bfr_surp( total.bfr_surp() + fl->bfr_surp() );
2541 2541 total.set_surplus( total.surplus() + fl->surplus() );
2542 2542 total.set_desired( total.desired() + fl->desired() );
2543 2543 total.set_prev_sweep( total.prev_sweep() + fl->prev_sweep() );
2544 2544 total.set_before_sweep(total.before_sweep() + fl->before_sweep());
2545 2545 total.set_count( total.count() + fl->count() );
2546 2546 total.set_coal_births( total.coal_births() + fl->coal_births() );
2547 2547 total.set_coal_deaths( total.coal_deaths() + fl->coal_deaths() );
2548 2548 total.set_split_births(total.split_births() + fl->split_births());
2549 2549 total.set_split_deaths(total.split_deaths() + fl->split_deaths());
2550 2550 }
2551 2551 total.print_on(gclog_or_tty, "TOTAL");
2552 2552 gclog_or_tty->print_cr("Total free in indexed lists "
2553 2553 SIZE_FORMAT " words", total_free);
2554 2554 gclog_or_tty->print("growth: %8.5f deficit: %8.5f\n",
2555 2555 (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/
2556 2556 (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0),
2557 2557 (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0));
2558 2558 _dictionary->print_dict_census();
2559 2559 }
2560 2560
2561 2561 ///////////////////////////////////////////////////////////////////////////
2562 2562 // CFLS_LAB
2563 2563 ///////////////////////////////////////////////////////////////////////////
2564 2564
2565 2565 #define VECTOR_257(x) \
2566 2566 /* 1 2 3 4 5 6 7 8 9 1x 11 12 13 14 15 16 17 18 19 2x 21 22 23 24 25 26 27 28 29 3x 31 32 */ \
2567 2567 { x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2568 2568 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2569 2569 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2570 2570 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2571 2571 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2572 2572 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2573 2573 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2574 2574 x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, x, \
2575 2575 x }
2576 2576
2577 2577 // Initialize with default setting of CMSParPromoteBlocksToClaim, _not_
2578 2578 // OldPLABSize, whose static default is different; if overridden at the
2579 2579 // command-line, this will get reinitialized via a call to
2580 2580 // modify_initialization() below.
2581 2581 AdaptiveWeightedAverage CFLS_LAB::_blocks_to_claim[] =
2582 2582 VECTOR_257(AdaptiveWeightedAverage(OldPLABWeight, (float)CMSParPromoteBlocksToClaim));
2583 2583 size_t CFLS_LAB::_global_num_blocks[] = VECTOR_257(0);
2584 2584 uint CFLS_LAB::_global_num_workers[] = VECTOR_257(0);
2585 2585
2586 2586 CFLS_LAB::CFLS_LAB(CompactibleFreeListSpace* cfls) :
2587 2587 _cfls(cfls)
2588 2588 {
2589 2589 assert(CompactibleFreeListSpace::IndexSetSize == 257, "Modify VECTOR_257() macro above");
2590 2590 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2591 2591 i < CompactibleFreeListSpace::IndexSetSize;
2592 2592 i += CompactibleFreeListSpace::IndexSetStride) {
2593 2593 _indexedFreeList[i].set_size(i);
2594 2594 _num_blocks[i] = 0;
2595 2595 }
2596 2596 }
2597 2597
2598 2598 static bool _CFLS_LAB_modified = false;
2599 2599
2600 2600 void CFLS_LAB::modify_initialization(size_t n, unsigned wt) {
2601 2601 assert(!_CFLS_LAB_modified, "Call only once");
2602 2602 _CFLS_LAB_modified = true;
2603 2603 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2604 2604 i < CompactibleFreeListSpace::IndexSetSize;
2605 2605 i += CompactibleFreeListSpace::IndexSetStride) {
2606 2606 _blocks_to_claim[i].modify(n, wt, true /* force */);
2607 2607 }
2608 2608 }
2609 2609
2610 2610 HeapWord* CFLS_LAB::alloc(size_t word_sz) {
2611 2611 FreeChunk* res;
2612 2612 assert(word_sz == _cfls->adjustObjectSize(word_sz), "Error");
2613 2613 if (word_sz >= CompactibleFreeListSpace::IndexSetSize) {
2614 2614 // This locking manages sync with other large object allocations.
2615 2615 MutexLockerEx x(_cfls->parDictionaryAllocLock(),
2616 2616 Mutex::_no_safepoint_check_flag);
2617 2617 res = _cfls->getChunkFromDictionaryExact(word_sz);
2618 2618 if (res == NULL) return NULL;
2619 2619 } else {
2620 2620 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[word_sz];
2621 2621 if (fl->count() == 0) {
2622 2622 // Attempt to refill this local free list.
2623 2623 get_from_global_pool(word_sz, fl);
2624 2624 // If it didn't work, give up.
2625 2625 if (fl->count() == 0) return NULL;
2626 2626 }
2627 2627 res = fl->get_chunk_at_head();
2628 2628 assert(res != NULL, "Why was count non-zero?");
2629 2629 }
2630 2630 res->markNotFree();
2631 2631 assert(!res->is_free(), "shouldn't be marked free");
2632 2632 assert(oop(res)->klass_or_null() == NULL, "should look uninitialized");
2633 2633 // mangle a just allocated object with a distinct pattern.
↓ open down ↓ |
2633 lines elided |
↑ open up ↑ |
2634 2634 debug_only(res->mangleAllocated(word_sz));
2635 2635 return (HeapWord*)res;
2636 2636 }
2637 2637
2638 2638 // Get a chunk of blocks of the right size and update related
2639 2639 // book-keeping stats
2640 2640 void CFLS_LAB::get_from_global_pool(size_t word_sz, AdaptiveFreeList<FreeChunk>* fl) {
2641 2641 // Get the #blocks we want to claim
2642 2642 size_t n_blks = (size_t)_blocks_to_claim[word_sz].average();
2643 2643 assert(n_blks > 0, "Error");
2644 - assert(ResizePLAB || n_blks == OldPLABSize, "Error");
2644 + assert(ResizeOldPLAB || n_blks == OldPLABSize, "Error");
2645 2645 // In some cases, when the application has a phase change,
2646 2646 // there may be a sudden and sharp shift in the object survival
2647 2647 // profile, and updating the counts at the end of a scavenge
2648 2648 // may not be quick enough, giving rise to large scavenge pauses
2649 2649 // during these phase changes. It is beneficial to detect such
2650 2650 // changes on-the-fly during a scavenge and avoid such a phase-change
2651 2651 // pothole. The following code is a heuristic attempt to do that.
2652 2652 // It is protected by a product flag until we have gained
2653 2653 // enough experience with this heuristic and fine-tuned its behaviour.
2654 2654 // WARNING: This might increase fragmentation if we overreact to
2655 2655 // small spikes, so some kind of historical smoothing based on
2656 2656 // previous experience with the greater reactivity might be useful.
2657 2657 // Lacking sufficient experience, CMSOldPLABResizeQuicker is disabled by
2658 2658 // default.
2659 2659 if (ResizeOldPLAB && CMSOldPLABResizeQuicker) {
2660 2660 size_t multiple = _num_blocks[word_sz]/(CMSOldPLABToleranceFactor*CMSOldPLABNumRefills*n_blks);
2661 2661 n_blks += CMSOldPLABReactivityFactor*multiple*n_blks;
2662 2662 n_blks = MIN2(n_blks, CMSOldPLABMax);
2663 2663 }
2664 2664 assert(n_blks > 0, "Error");
2665 2665 _cfls->par_get_chunk_of_blocks(word_sz, n_blks, fl);
2666 2666 // Update stats table entry for this block size
2667 2667 _num_blocks[word_sz] += fl->count();
2668 2668 }
2669 2669
2670 2670 void CFLS_LAB::compute_desired_plab_size() {
2671 2671 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2672 2672 i < CompactibleFreeListSpace::IndexSetSize;
2673 2673 i += CompactibleFreeListSpace::IndexSetStride) {
2674 2674 assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0),
2675 2675 "Counter inconsistency");
2676 2676 if (_global_num_workers[i] > 0) {
2677 2677 // Need to smooth wrt historical average
2678 2678 if (ResizeOldPLAB) {
2679 2679 _blocks_to_claim[i].sample(
2680 2680 MAX2((size_t)CMSOldPLABMin,
2681 2681 MIN2((size_t)CMSOldPLABMax,
2682 2682 _global_num_blocks[i]/(_global_num_workers[i]*CMSOldPLABNumRefills))));
2683 2683 }
2684 2684 // Reset counters for next round
2685 2685 _global_num_workers[i] = 0;
2686 2686 _global_num_blocks[i] = 0;
2687 2687 if (PrintOldPLAB) {
2688 2688 gclog_or_tty->print_cr("[" SIZE_FORMAT "]: " SIZE_FORMAT, i, (size_t)_blocks_to_claim[i].average());
2689 2689 }
2690 2690 }
2691 2691 }
2692 2692 }
2693 2693
2694 2694 // If this is changed in the future to allow parallel
2695 2695 // access, one would need to take the FL locks and,
2696 2696 // depending on how it is used, stagger access from
2697 2697 // parallel threads to reduce contention.
2698 2698 void CFLS_LAB::retire(int tid) {
2699 2699 // We run this single threaded with the world stopped;
2700 2700 // so no need for locks and such.
2701 2701 NOT_PRODUCT(Thread* t = Thread::current();)
2702 2702 assert(Thread::current()->is_VM_thread(), "Error");
2703 2703 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2704 2704 i < CompactibleFreeListSpace::IndexSetSize;
2705 2705 i += CompactibleFreeListSpace::IndexSetStride) {
2706 2706 assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(),
2707 2707 "Can't retire more than what we obtained");
2708 2708 if (_num_blocks[i] > 0) {
2709 2709 size_t num_retire = _indexedFreeList[i].count();
2710 2710 assert(_num_blocks[i] > num_retire, "Should have used at least one");
2711 2711 {
2712 2712 // MutexLockerEx x(_cfls->_indexedFreeListParLocks[i],
2713 2713 // Mutex::_no_safepoint_check_flag);
2714 2714
2715 2715 // Update globals stats for num_blocks used
2716 2716 _global_num_blocks[i] += (_num_blocks[i] - num_retire);
2717 2717 _global_num_workers[i]++;
2718 2718 assert(_global_num_workers[i] <= ParallelGCThreads, "Too big");
2719 2719 if (num_retire > 0) {
2720 2720 _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]);
2721 2721 // Reset this list.
2722 2722 _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>();
2723 2723 _indexedFreeList[i].set_size(i);
2724 2724 }
2725 2725 }
2726 2726 if (PrintOldPLAB) {
2727 2727 gclog_or_tty->print_cr("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT,
2728 2728 tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average());
2729 2729 }
2730 2730 // Reset stats for next round
2731 2731 _num_blocks[i] = 0;
2732 2732 }
2733 2733 }
2734 2734 }
2735 2735
2736 2736 // Used by par_get_chunk_of_blocks() for the chunks from the
2737 2737 // indexed_free_lists. Looks for a chunk with size that is a multiple
2738 2738 // of "word_sz" and if found, splits it into "word_sz" chunks and add
2739 2739 // to the free list "fl". "n" is the maximum number of chunks to
2740 2740 // be added to "fl".
2741 2741 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2742 2742
2743 2743 // We'll try all multiples of word_sz in the indexed set, starting with
2744 2744 // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples,
2745 2745 // then try getting a big chunk and splitting it.
2746 2746 {
2747 2747 bool found;
2748 2748 int k;
2749 2749 size_t cur_sz;
2750 2750 for (k = 1, cur_sz = k * word_sz, found = false;
2751 2751 (cur_sz < CompactibleFreeListSpace::IndexSetSize) &&
2752 2752 (CMSSplitIndexedFreeListBlocks || k <= 1);
2753 2753 k++, cur_sz = k * word_sz) {
2754 2754 AdaptiveFreeList<FreeChunk> fl_for_cur_sz; // Empty.
2755 2755 fl_for_cur_sz.set_size(cur_sz);
2756 2756 {
2757 2757 MutexLockerEx x(_indexedFreeListParLocks[cur_sz],
2758 2758 Mutex::_no_safepoint_check_flag);
2759 2759 AdaptiveFreeList<FreeChunk>* gfl = &_indexedFreeList[cur_sz];
2760 2760 if (gfl->count() != 0) {
2761 2761 // nn is the number of chunks of size cur_sz that
2762 2762 // we'd need to split k-ways each, in order to create
2763 2763 // "n" chunks of size word_sz each.
2764 2764 const size_t nn = MAX2(n/k, (size_t)1);
2765 2765 gfl->getFirstNChunksFromList(nn, &fl_for_cur_sz);
2766 2766 found = true;
2767 2767 if (k > 1) {
2768 2768 // Update split death stats for the cur_sz-size blocks list:
2769 2769 // we increment the split death count by the number of blocks
2770 2770 // we just took from the cur_sz-size blocks list and which
2771 2771 // we will be splitting below.
2772 2772 ssize_t deaths = gfl->split_deaths() +
2773 2773 fl_for_cur_sz.count();
2774 2774 gfl->set_split_deaths(deaths);
2775 2775 }
2776 2776 }
2777 2777 }
2778 2778 // Now transfer fl_for_cur_sz to fl. Common case, we hope, is k = 1.
2779 2779 if (found) {
2780 2780 if (k == 1) {
2781 2781 fl->prepend(&fl_for_cur_sz);
2782 2782 } else {
2783 2783 // Divide each block on fl_for_cur_sz up k ways.
2784 2784 FreeChunk* fc;
2785 2785 while ((fc = fl_for_cur_sz.get_chunk_at_head()) != NULL) {
2786 2786 // Must do this in reverse order, so that anybody attempting to
2787 2787 // access the main chunk sees it as a single free block until we
2788 2788 // change it.
2789 2789 size_t fc_size = fc->size();
2790 2790 assert(fc->is_free(), "Error");
2791 2791 for (int i = k-1; i >= 0; i--) {
2792 2792 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz);
2793 2793 assert((i != 0) ||
2794 2794 ((fc == ffc) && ffc->is_free() &&
2795 2795 (ffc->size() == k*word_sz) && (fc_size == word_sz)),
2796 2796 "Counting error");
2797 2797 ffc->set_size(word_sz);
2798 2798 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2799 2799 ffc->link_next(NULL);
2800 2800 // Above must occur before BOT is updated below.
2801 2801 OrderAccess::storestore();
2802 2802 // splitting from the right, fc_size == i * word_sz
2803 2803 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */);
2804 2804 fc_size -= word_sz;
2805 2805 assert(fc_size == i*word_sz, "Error");
2806 2806 _bt.verify_not_unallocated((HeapWord*)ffc, word_sz);
2807 2807 _bt.verify_single_block((HeapWord*)fc, fc_size);
2808 2808 _bt.verify_single_block((HeapWord*)ffc, word_sz);
2809 2809 // Push this on "fl".
2810 2810 fl->return_chunk_at_head(ffc);
2811 2811 }
2812 2812 // TRAP
2813 2813 assert(fl->tail()->next() == NULL, "List invariant.");
2814 2814 }
2815 2815 }
2816 2816 // Update birth stats for this block size.
2817 2817 size_t num = fl->count();
2818 2818 MutexLockerEx x(_indexedFreeListParLocks[word_sz],
2819 2819 Mutex::_no_safepoint_check_flag);
2820 2820 ssize_t births = _indexedFreeList[word_sz].split_births() + num;
2821 2821 _indexedFreeList[word_sz].set_split_births(births);
2822 2822 return true;
2823 2823 }
2824 2824 }
2825 2825 return found;
2826 2826 }
2827 2827 }
2828 2828
2829 2829 FreeChunk* CompactibleFreeListSpace::get_n_way_chunk_to_split(size_t word_sz, size_t n) {
2830 2830
2831 2831 FreeChunk* fc = NULL;
2832 2832 FreeChunk* rem_fc = NULL;
2833 2833 size_t rem;
2834 2834 {
2835 2835 MutexLockerEx x(parDictionaryAllocLock(),
2836 2836 Mutex::_no_safepoint_check_flag);
2837 2837 while (n > 0) {
2838 2838 fc = dictionary()->get_chunk(MAX2(n * word_sz, _dictionary->min_size()),
2839 2839 FreeBlockDictionary<FreeChunk>::atLeast);
2840 2840 if (fc != NULL) {
2841 2841 break;
2842 2842 } else {
2843 2843 n--;
2844 2844 }
2845 2845 }
2846 2846 if (fc == NULL) return NULL;
2847 2847 // Otherwise, split up that block.
2848 2848 assert((ssize_t)n >= 1, "Control point invariant");
2849 2849 assert(fc->is_free(), "Error: should be a free block");
2850 2850 _bt.verify_single_block((HeapWord*)fc, fc->size());
2851 2851 const size_t nn = fc->size() / word_sz;
2852 2852 n = MIN2(nn, n);
2853 2853 assert((ssize_t)n >= 1, "Control point invariant");
2854 2854 rem = fc->size() - n * word_sz;
2855 2855 // If there is a remainder, and it's too small, allocate one fewer.
2856 2856 if (rem > 0 && rem < MinChunkSize) {
2857 2857 n--; rem += word_sz;
2858 2858 }
2859 2859 // Note that at this point we may have n == 0.
2860 2860 assert((ssize_t)n >= 0, "Control point invariant");
2861 2861
2862 2862 // If n is 0, the chunk fc that was found is not large
2863 2863 // enough to leave a viable remainder. We are unable to
2864 2864 // allocate even one block. Return fc to the
2865 2865 // dictionary and return, leaving "fl" empty.
2866 2866 if (n == 0) {
2867 2867 returnChunkToDictionary(fc);
2868 2868 return NULL;
2869 2869 }
2870 2870
2871 2871 _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk
2872 2872 dictionary()->dict_census_update(fc->size(),
2873 2873 true /*split*/,
2874 2874 false /*birth*/);
2875 2875
2876 2876 // First return the remainder, if any.
2877 2877 // Note that we hold the lock until we decide if we're going to give
2878 2878 // back the remainder to the dictionary, since a concurrent allocation
2879 2879 // may otherwise see the heap as empty. (We're willing to take that
2880 2880 // hit if the block is a small block.)
2881 2881 if (rem > 0) {
2882 2882 size_t prefix_size = n * word_sz;
2883 2883 rem_fc = (FreeChunk*)((HeapWord*)fc + prefix_size);
2884 2884 rem_fc->set_size(rem);
2885 2885 rem_fc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2886 2886 rem_fc->link_next(NULL);
2887 2887 // Above must occur before BOT is updated below.
2888 2888 assert((ssize_t)n > 0 && prefix_size > 0 && rem_fc > fc, "Error");
2889 2889 OrderAccess::storestore();
2890 2890 _bt.split_block((HeapWord*)fc, fc->size(), prefix_size);
2891 2891 assert(fc->is_free(), "Error");
2892 2892 fc->set_size(prefix_size);
2893 2893 if (rem >= IndexSetSize) {
2894 2894 returnChunkToDictionary(rem_fc);
2895 2895 dictionary()->dict_census_update(rem, true /*split*/, true /*birth*/);
2896 2896 rem_fc = NULL;
2897 2897 }
2898 2898 // Otherwise, return it to the small list below.
2899 2899 }
2900 2900 }
2901 2901 if (rem_fc != NULL) {
2902 2902 MutexLockerEx x(_indexedFreeListParLocks[rem],
2903 2903 Mutex::_no_safepoint_check_flag);
2904 2904 _bt.verify_not_unallocated((HeapWord*)rem_fc, rem_fc->size());
2905 2905 _indexedFreeList[rem].return_chunk_at_head(rem_fc);
2906 2906 smallSplitBirth(rem);
2907 2907 }
2908 2908 assert(n * word_sz == fc->size(),
2909 2909 err_msg("Chunk size " SIZE_FORMAT " is not exactly splittable by "
2910 2910 SIZE_FORMAT " sized chunks of size " SIZE_FORMAT,
2911 2911 fc->size(), n, word_sz));
2912 2912 return fc;
2913 2913 }
2914 2914
2915 2915 void CompactibleFreeListSpace:: par_get_chunk_of_blocks_dictionary(size_t word_sz, size_t targetted_number_of_chunks, AdaptiveFreeList<FreeChunk>* fl) {
2916 2916
2917 2917 FreeChunk* fc = get_n_way_chunk_to_split(word_sz, targetted_number_of_chunks);
2918 2918
2919 2919 if (fc == NULL) {
2920 2920 return;
2921 2921 }
2922 2922
2923 2923 size_t n = fc->size() / word_sz;
2924 2924
2925 2925 assert((ssize_t)n > 0, "Consistency");
2926 2926 // Now do the splitting up.
2927 2927 // Must do this in reverse order, so that anybody attempting to
2928 2928 // access the main chunk sees it as a single free block until we
2929 2929 // change it.
2930 2930 size_t fc_size = n * word_sz;
2931 2931 // All but first chunk in this loop
2932 2932 for (ssize_t i = n-1; i > 0; i--) {
2933 2933 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz);
2934 2934 ffc->set_size(word_sz);
2935 2935 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2936 2936 ffc->link_next(NULL);
2937 2937 // Above must occur before BOT is updated below.
2938 2938 OrderAccess::storestore();
2939 2939 // splitting from the right, fc_size == (n - i + 1) * wordsize
2940 2940 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */);
2941 2941 fc_size -= word_sz;
2942 2942 _bt.verify_not_unallocated((HeapWord*)ffc, ffc->size());
2943 2943 _bt.verify_single_block((HeapWord*)ffc, ffc->size());
2944 2944 _bt.verify_single_block((HeapWord*)fc, fc_size);
2945 2945 // Push this on "fl".
2946 2946 fl->return_chunk_at_head(ffc);
2947 2947 }
2948 2948 // First chunk
2949 2949 assert(fc->is_free() && fc->size() == n*word_sz, "Error: should still be a free block");
2950 2950 // The blocks above should show their new sizes before the first block below
2951 2951 fc->set_size(word_sz);
2952 2952 fc->link_prev(NULL); // idempotent wrt free-ness, see assert above
2953 2953 fc->link_next(NULL);
2954 2954 _bt.verify_not_unallocated((HeapWord*)fc, fc->size());
2955 2955 _bt.verify_single_block((HeapWord*)fc, fc->size());
2956 2956 fl->return_chunk_at_head(fc);
2957 2957
2958 2958 assert((ssize_t)n > 0 && (ssize_t)n == fl->count(), "Incorrect number of blocks");
2959 2959 {
2960 2960 // Update the stats for this block size.
2961 2961 MutexLockerEx x(_indexedFreeListParLocks[word_sz],
2962 2962 Mutex::_no_safepoint_check_flag);
2963 2963 const ssize_t births = _indexedFreeList[word_sz].split_births() + n;
2964 2964 _indexedFreeList[word_sz].set_split_births(births);
2965 2965 // ssize_t new_surplus = _indexedFreeList[word_sz].surplus() + n;
2966 2966 // _indexedFreeList[word_sz].set_surplus(new_surplus);
2967 2967 }
2968 2968
2969 2969 // TRAP
2970 2970 assert(fl->tail()->next() == NULL, "List invariant.");
2971 2971 }
2972 2972
2973 2973 void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2974 2974 assert(fl->count() == 0, "Precondition.");
2975 2975 assert(word_sz < CompactibleFreeListSpace::IndexSetSize,
2976 2976 "Precondition");
2977 2977
2978 2978 if (par_get_chunk_of_blocks_IFL(word_sz, n, fl)) {
2979 2979 // Got it
2980 2980 return;
2981 2981 }
2982 2982
2983 2983 // Otherwise, we'll split a block from the dictionary.
2984 2984 par_get_chunk_of_blocks_dictionary(word_sz, n, fl);
2985 2985 }
2986 2986
2987 2987 // Set up the space's par_seq_tasks structure for work claiming
2988 2988 // for parallel rescan. See CMSParRemarkTask where this is currently used.
2989 2989 // XXX Need to suitably abstract and generalize this and the next
2990 2990 // method into one.
2991 2991 void
2992 2992 CompactibleFreeListSpace::
2993 2993 initialize_sequential_subtasks_for_rescan(int n_threads) {
2994 2994 // The "size" of each task is fixed according to rescan_task_size.
2995 2995 assert(n_threads > 0, "Unexpected n_threads argument");
2996 2996 const size_t task_size = rescan_task_size();
2997 2997 size_t n_tasks = (used_region().word_size() + task_size - 1)/task_size;
2998 2998 assert((n_tasks == 0) == used_region().is_empty(), "n_tasks incorrect");
2999 2999 assert(n_tasks == 0 ||
3000 3000 ((used_region().start() + (n_tasks - 1)*task_size < used_region().end()) &&
3001 3001 (used_region().start() + n_tasks*task_size >= used_region().end())),
3002 3002 "n_tasks calculation incorrect");
3003 3003 SequentialSubTasksDone* pst = conc_par_seq_tasks();
3004 3004 assert(!pst->valid(), "Clobbering existing data?");
3005 3005 // Sets the condition for completion of the subtask (how many threads
3006 3006 // need to finish in order to be done).
3007 3007 pst->set_n_threads(n_threads);
3008 3008 pst->set_n_tasks((int)n_tasks);
3009 3009 }
3010 3010
3011 3011 // Set up the space's par_seq_tasks structure for work claiming
3012 3012 // for parallel concurrent marking. See CMSConcMarkTask where this is currently used.
3013 3013 void
3014 3014 CompactibleFreeListSpace::
3015 3015 initialize_sequential_subtasks_for_marking(int n_threads,
3016 3016 HeapWord* low) {
3017 3017 // The "size" of each task is fixed according to rescan_task_size.
3018 3018 assert(n_threads > 0, "Unexpected n_threads argument");
3019 3019 const size_t task_size = marking_task_size();
3020 3020 assert(task_size > CardTableModRefBS::card_size_in_words &&
3021 3021 (task_size % CardTableModRefBS::card_size_in_words == 0),
3022 3022 "Otherwise arithmetic below would be incorrect");
3023 3023 MemRegion span = _gen->reserved();
3024 3024 if (low != NULL) {
3025 3025 if (span.contains(low)) {
3026 3026 // Align low down to a card boundary so that
3027 3027 // we can use block_offset_careful() on span boundaries.
3028 3028 HeapWord* aligned_low = (HeapWord*)align_size_down((uintptr_t)low,
3029 3029 CardTableModRefBS::card_size);
3030 3030 // Clip span prefix at aligned_low
3031 3031 span = span.intersection(MemRegion(aligned_low, span.end()));
3032 3032 } else if (low > span.end()) {
3033 3033 span = MemRegion(low, low); // Null region
3034 3034 } // else use entire span
3035 3035 }
3036 3036 assert(span.is_empty() ||
3037 3037 ((uintptr_t)span.start() % CardTableModRefBS::card_size == 0),
3038 3038 "span should start at a card boundary");
3039 3039 size_t n_tasks = (span.word_size() + task_size - 1)/task_size;
3040 3040 assert((n_tasks == 0) == span.is_empty(), "Inconsistency");
3041 3041 assert(n_tasks == 0 ||
3042 3042 ((span.start() + (n_tasks - 1)*task_size < span.end()) &&
3043 3043 (span.start() + n_tasks*task_size >= span.end())),
3044 3044 "n_tasks calculation incorrect");
3045 3045 SequentialSubTasksDone* pst = conc_par_seq_tasks();
3046 3046 assert(!pst->valid(), "Clobbering existing data?");
3047 3047 // Sets the condition for completion of the subtask (how many threads
3048 3048 // need to finish in order to be done).
3049 3049 pst->set_n_threads(n_threads);
3050 3050 pst->set_n_tasks((int)n_tasks);
3051 3051 }
↓ open down ↓ |
397 lines elided |
↑ open up ↑ |
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX