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