1 /*
2 * Copyright (c) 2001, 2014, 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 */
24
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"
46
47 /////////////////////////////////////////////////////////////////////////
48 //// CompactibleFreeListSpace
49 /////////////////////////////////////////////////////////////////////////
50
51 // highest ranked free list lock rank
52 int CompactibleFreeListSpace::_lockRank = Mutex::leaf + 3;
53
54 // Defaults are 0 so things will break badly if incorrectly initialized.
55 size_t CompactibleFreeListSpace::IndexSetStart = 0;
56 size_t CompactibleFreeListSpace::IndexSetStride = 0;
57
58 size_t MinChunkSize = 0;
59
60 void CompactibleFreeListSpace::set_cms_values() {
61 // Set CMS global values
62 assert(MinChunkSize == 0, "already set");
63
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;
68
69 assert(IndexSetStart == 0 && IndexSetStride == 0, "already set");
70 IndexSetStart = MinChunkSize;
71 IndexSetStride = MinObjAlignment;
72 }
73
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();
119
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();
150
151 // Initialize locks for parallel case.
152
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 }
164
165 _used_stable = 0;
166 }
167
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 }
208
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 }
219
220 compact_top += adjusted_size;
221
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.
225
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 }
233
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.
238
239 HeapWord* CompactibleFreeListSpace::cross_threshold(HeapWord* start, HeapWord* the_end) {
240 _bt.single_block(start, the_end);
241 return end();
242 }
243
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 }
258
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 }
270
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 }
296
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 }
319
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() {
324
325 assert_lock_strong(&_freelistLock);
326
327 return dictionary()->find_chunk_ends_at(end());
328 }
329
330
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 }
337
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 }
345
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 }
362
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
372
373 bool CompactibleFreeListSpace::is_free_block(const HeapWord* p) const {
374 FreeChunk* fc = (FreeChunk*) p;
375 return fc->is_free();
376 }
377
378 size_t CompactibleFreeListSpace::used() const {
379 return capacity() - free();
380 }
381
382 size_t CompactibleFreeListSpace::used_stable() const {
383 return _used_stable;
384 }
385
386 void CompactibleFreeListSpace::recalculate_used_stable() {
387 _used_stable = used();
388 }
389
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 }
414
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 }
438
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 }
444
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);
449
450 st->print_cr("promoInfo:");
451 _promoInfo.print_on(st);
452
453 st->print_cr("_smallLinearAllocBlock");
454 _smallLinearAllocBlock.print_on(st);
455
456 // dump_memory_block(_smallLinearAllocBlock->_ptr, 128);
457
458 st->print_cr(" _fitStrategy = %s, _adaptive_freelists = %s",
459 _fitStrategy?"true":"false", _adaptive_freelists?"true":"false");
460 }
461
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 }
478
479 void CompactibleFreeListSpace::print_promo_info_blocks(outputStream* st)
480 const {
481 _promoInfo.print_on(st);
482 }
483
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 }
491
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 };
510
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 }
535
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);
543
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);
548
549 st->print_cr("\n===========================");
550 st->print_cr("Order of Indexed Free Lists");
551 st->print_cr("=========================");
552 print_indexed_free_lists(st);
553
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 }
559
560
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 }
572
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 }
586
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 }
603
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 }
613
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 }
656
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);
674
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 };
684
685 // We de-virtualize the block-related calls below, since we know that our
686 // space is a CompactibleFreeListSpace.
687
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 }
756
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)
762
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 }
769
770
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.
777
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 }
785
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 }
793
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 }
807
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 }
822
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 }
837
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.
847
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 }
861
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");
882
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 }
919
920
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 }
962
963
964 HeapWord* CompactibleFreeListSpace::block_start_const(const void* p) const {
965 NOT_PRODUCT(verify_objects_initialized());
966 return _bt.block_start(p);
967 }
968
969 HeapWord* CompactibleFreeListSpace::block_start_careful(const void* p) const {
970 return _bt.block_start_careful(p);
971 }
972
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();
983
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();
989
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 // must read from what 'p' points to in each loop.
998 Klass* k = ((volatile oopDesc*)p)->klass_or_null();
999 if (k != NULL) {
1000 assert(k->is_klass(), "Should really be klass oop.");
1001 oop o = (oop)p;
1002 assert(o->is_oop(true /* ignore mark word */), "Should be an oop.");
1003
1004 // Bugfix for systems with weak memory model (PPC64/IA64).
1005 // The object o may be an array. Acquire to make sure that the array
1006 // size (third word) is consistent.
1007 OrderAccess::acquire();
1008
1009 size_t res = o->size_given_klass(k);
1010 res = adjustObjectSize(res);
1011 assert(res != 0, "Block size should not be 0");
1012 return res;
1013 }
1014 }
1015 }
1016 }
1017
1018 // TODO: Now that is_parsable is gone, we should combine these two functions.
1019 // A variant of the above that uses the Printezis bits for
1020 // unparsable but allocated objects. This avoids any possible
1021 // stalls waiting for mutators to initialize objects, and is
1022 // thus potentially faster than the variant above. However,
1023 // this variant may return a zero size for a block that is
1024 // under mutation and for which a consistent size cannot be
1025 // inferred without stalling; see CMSCollector::block_size_if_printezis_bits().
1026 size_t CompactibleFreeListSpace::block_size_no_stall(HeapWord* p,
1027 const CMSCollector* c)
1028 const {
1029 assert(MemRegion(bottom(), end()).contains(p), "p not in space");
1030 // This must be volatile, or else there is a danger that the compiler
1031 // will compile the code below into a sometimes-infinite loop, by keeping
1032 // the value read the first time in a register.
1033 DEBUG_ONLY(uint loops = 0;)
1034 while (true) {
1035 // We must do this until we get a consistent view of the object.
1036 if (FreeChunk::indicatesFreeChunk(p)) {
1037 volatile FreeChunk* fc = (volatile FreeChunk*)p;
1038 size_t res = fc->size();
1039
1040 // Bugfix for systems with weak memory model (PPC64/IA64). The
1041 // free bit of the block was set and we have read the size of
1042 // the block. Acquire and check the free bit again. If the
1043 // block is still free, the read size is correct.
1044 OrderAccess::acquire();
1045
1046 if (FreeChunk::indicatesFreeChunk(p)) {
1047 assert(res != 0, "Block size should not be 0");
1048 assert(loops == 0, "Should be 0");
1049 return res;
1050 }
1051 } else {
1052 // must read from what 'p' points to in each loop.
1053 Klass* k = ((volatile oopDesc*)p)->klass_or_null();
1054 // We trust the size of any object that has a non-NULL
1055 // klass and (for those in the perm gen) is parsable
1056 // -- irrespective of its conc_safe-ty.
1057 if (k != NULL) {
1058 assert(k->is_klass(), "Should really be klass oop.");
1059 oop o = (oop)p;
1060 assert(o->is_oop(), "Should be an oop");
1061
1062 // Bugfix for systems with weak memory model (PPC64/IA64).
1063 // The object o may be an array. Acquire to make sure that the array
1064 // size (third word) is consistent.
1065 OrderAccess::acquire();
1066
1067 size_t res = o->size_given_klass(k);
1068 res = adjustObjectSize(res);
1069 assert(res != 0, "Block size should not be 0");
1070 return res;
1071 } else {
1072 // May return 0 if P-bits not present.
1073 return c->block_size_if_printezis_bits(p);
1074 }
1075 }
1076 assert(loops == 0, "Can loop at most once");
1077 DEBUG_ONLY(loops++;)
1078 }
1079 }
1080
1081 size_t CompactibleFreeListSpace::block_size_nopar(const HeapWord* p) const {
1082 NOT_PRODUCT(verify_objects_initialized());
1083 assert(MemRegion(bottom(), end()).contains(p), "p not in space");
1084 FreeChunk* fc = (FreeChunk*)p;
1085 if (fc->is_free()) {
1086 return fc->size();
1087 } else {
1088 // Ignore mark word because this may be a recently promoted
1089 // object whose mark word is used to chain together grey
1090 // objects (the last one would have a null value).
1091 assert(oop(p)->is_oop(true), "Should be an oop");
1092 return adjustObjectSize(oop(p)->size());
1093 }
1094 }
1095
1096 // This implementation assumes that the property of "being an object" is
1097 // stable. But being a free chunk may not be (because of parallel
1098 // promotion.)
1099 bool CompactibleFreeListSpace::block_is_obj(const HeapWord* p) const {
1100 FreeChunk* fc = (FreeChunk*)p;
1101 assert(is_in_reserved(p), "Should be in space");
1102 // When doing a mark-sweep-compact of the CMS generation, this
1103 // assertion may fail because prepare_for_compaction() uses
1104 // space that is garbage to maintain information on ranges of
1105 // live objects so that these live ranges can be moved as a whole.
1106 // Comment out this assertion until that problem can be solved
1107 // (i.e., that the block start calculation may look at objects
1108 // at address below "p" in finding the object that contains "p"
1109 // and those objects (if garbage) may have been modified to hold
1110 // live range information.
1111 // assert(CollectedHeap::use_parallel_gc_threads() || _bt.block_start(p) == p,
1112 // "Should be a block boundary");
1113 if (FreeChunk::indicatesFreeChunk(p)) return false;
1114 Klass* k = oop(p)->klass_or_null();
1115 if (k != NULL) {
1116 // Ignore mark word because it may have been used to
1117 // chain together promoted objects (the last one
1118 // would have a null value).
1119 assert(oop(p)->is_oop(true), "Should be an oop");
1120 return true;
1121 } else {
1122 return false; // Was not an object at the start of collection.
1123 }
1124 }
1125
1126 // Check if the object is alive. This fact is checked either by consulting
1127 // the main marking bitmap in the sweeping phase or, if it's a permanent
1128 // generation and we're not in the sweeping phase, by checking the
1129 // perm_gen_verify_bit_map where we store the "deadness" information if
1130 // we did not sweep the perm gen in the most recent previous GC cycle.
1131 bool CompactibleFreeListSpace::obj_is_alive(const HeapWord* p) const {
1132 assert(SafepointSynchronize::is_at_safepoint() || !is_init_completed(),
1133 "Else races are possible");
1134 assert(block_is_obj(p), "The address should point to an object");
1135
1136 // If we're sweeping, we use object liveness information from the main bit map
1137 // for both perm gen and old gen.
1138 // We don't need to lock the bitmap (live_map or dead_map below), because
1139 // EITHER we are in the middle of the sweeping phase, and the
1140 // main marking bit map (live_map below) is locked,
1141 // OR we're in other phases and perm_gen_verify_bit_map (dead_map below)
1142 // is stable, because it's mutated only in the sweeping phase.
1143 // NOTE: This method is also used by jmap where, if class unloading is
1144 // off, the results can return "false" for legitimate perm objects,
1145 // when we are not in the midst of a sweeping phase, which can result
1146 // in jmap not reporting certain perm gen objects. This will be moot
1147 // if/when the perm gen goes away in the future.
1148 if (_collector->abstract_state() == CMSCollector::Sweeping) {
1149 CMSBitMap* live_map = _collector->markBitMap();
1150 return live_map->par_isMarked((HeapWord*) p);
1151 }
1152 return true;
1153 }
1154
1155 bool CompactibleFreeListSpace::block_is_obj_nopar(const HeapWord* p) const {
1156 FreeChunk* fc = (FreeChunk*)p;
1157 assert(is_in_reserved(p), "Should be in space");
1158 assert(_bt.block_start(p) == p, "Should be a block boundary");
1159 if (!fc->is_free()) {
1160 // Ignore mark word because it may have been used to
1161 // chain together promoted objects (the last one
1162 // would have a null value).
1163 assert(oop(p)->is_oop(true), "Should be an oop");
1164 return true;
1165 }
1166 return false;
1167 }
1168
1169 // "MT-safe but not guaranteed MT-precise" (TM); you may get an
1170 // approximate answer if you don't hold the freelistlock when you call this.
1171 size_t CompactibleFreeListSpace::totalSizeInIndexedFreeLists() const {
1172 size_t size = 0;
1173 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
1174 debug_only(
1175 // We may be calling here without the lock in which case we
1176 // won't do this modest sanity check.
1177 if (freelistLock()->owned_by_self()) {
1178 size_t total_list_size = 0;
1179 for (FreeChunk* fc = _indexedFreeList[i].head(); fc != NULL;
1180 fc = fc->next()) {
1181 total_list_size += i;
1182 }
1183 assert(total_list_size == i * _indexedFreeList[i].count(),
1184 "Count in list is incorrect");
1185 }
1186 )
1187 size += i * _indexedFreeList[i].count();
1188 }
1189 return size;
1190 }
1191
1192 HeapWord* CompactibleFreeListSpace::par_allocate(size_t size) {
1193 MutexLockerEx x(freelistLock(), Mutex::_no_safepoint_check_flag);
1194 return allocate(size);
1195 }
1196
1197 HeapWord*
1198 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlockRemainder(size_t size) {
1199 return getChunkFromLinearAllocBlockRemainder(&_smallLinearAllocBlock, size);
1200 }
1201
1202 HeapWord* CompactibleFreeListSpace::allocate(size_t size) {
1203 assert_lock_strong(freelistLock());
1204 HeapWord* res = NULL;
1205 assert(size == adjustObjectSize(size),
1206 "use adjustObjectSize() before calling into allocate()");
1207
1208 if (_adaptive_freelists) {
1209 res = allocate_adaptive_freelists(size);
1210 } else { // non-adaptive free lists
1211 res = allocate_non_adaptive_freelists(size);
1212 }
1213
1214 if (res != NULL) {
1215 // check that res does lie in this space!
1216 assert(is_in_reserved(res), "Not in this space!");
1217 assert(is_aligned((void*)res), "alignment check");
1218
1219 FreeChunk* fc = (FreeChunk*)res;
1220 fc->markNotFree();
1221 assert(!fc->is_free(), "shouldn't be marked free");
1222 assert(oop(fc)->klass_or_null() == NULL, "should look uninitialized");
1223 // Verify that the block offset table shows this to
1224 // be a single block, but not one which is unallocated.
1225 _bt.verify_single_block(res, size);
1226 _bt.verify_not_unallocated(res, size);
1227 // mangle a just allocated object with a distinct pattern.
1228 debug_only(fc->mangleAllocated(size));
1229 }
1230
1231 // During GC we do not need to recalculate the stable used value for
1232 // every allocation in old gen. It is done once at the end of GC instead
1233 // for performance reasons.
1234 if (!Universe::heap()->is_gc_active()) {
1235 recalculate_used_stable();
1236 }
1237
1238 return res;
1239 }
1240
1241 HeapWord* CompactibleFreeListSpace::allocate_non_adaptive_freelists(size_t size) {
1242 HeapWord* res = NULL;
1243 // try and use linear allocation for smaller blocks
1244 if (size < _smallLinearAllocBlock._allocation_size_limit) {
1245 // if successful, the following also adjusts block offset table
1246 res = getChunkFromSmallLinearAllocBlock(size);
1247 }
1248 // Else triage to indexed lists for smaller sizes
1249 if (res == NULL) {
1250 if (size < SmallForDictionary) {
1251 res = (HeapWord*) getChunkFromIndexedFreeList(size);
1252 } else {
1253 // else get it from the big dictionary; if even this doesn't
1254 // work we are out of luck.
1255 res = (HeapWord*)getChunkFromDictionaryExact(size);
1256 }
1257 }
1258
1259 return res;
1260 }
1261
1262 HeapWord* CompactibleFreeListSpace::allocate_adaptive_freelists(size_t size) {
1263 assert_lock_strong(freelistLock());
1264 HeapWord* res = NULL;
1265 assert(size == adjustObjectSize(size),
1266 "use adjustObjectSize() before calling into allocate()");
1267
1268 // Strategy
1269 // if small
1270 // exact size from small object indexed list if small
1271 // small or large linear allocation block (linAB) as appropriate
1272 // take from lists of greater sized chunks
1273 // else
1274 // dictionary
1275 // small or large linear allocation block if it has the space
1276 // Try allocating exact size from indexTable first
1277 if (size < IndexSetSize) {
1278 res = (HeapWord*) getChunkFromIndexedFreeList(size);
1279 if(res != NULL) {
1280 assert(res != (HeapWord*)_indexedFreeList[size].head(),
1281 "Not removed from free list");
1282 // no block offset table adjustment is necessary on blocks in
1283 // the indexed lists.
1284
1285 // Try allocating from the small LinAB
1286 } else if (size < _smallLinearAllocBlock._allocation_size_limit &&
1287 (res = getChunkFromSmallLinearAllocBlock(size)) != NULL) {
1288 // if successful, the above also adjusts block offset table
1289 // Note that this call will refill the LinAB to
1290 // satisfy the request. This is different that
1291 // evm.
1292 // Don't record chunk off a LinAB? smallSplitBirth(size);
1293 } else {
1294 // Raid the exact free lists larger than size, even if they are not
1295 // overpopulated.
1296 res = (HeapWord*) getChunkFromGreater(size);
1297 }
1298 } else {
1299 // Big objects get allocated directly from the dictionary.
1300 res = (HeapWord*) getChunkFromDictionaryExact(size);
1301 if (res == NULL) {
1302 // Try hard not to fail since an allocation failure will likely
1303 // trigger a synchronous GC. Try to get the space from the
1304 // allocation blocks.
1305 res = getChunkFromSmallLinearAllocBlockRemainder(size);
1306 }
1307 }
1308
1309 return res;
1310 }
1311
1312 // A worst-case estimate of the space required (in HeapWords) to expand the heap
1313 // when promoting obj.
1314 size_t CompactibleFreeListSpace::expansionSpaceRequired(size_t obj_size) const {
1315 // Depending on the object size, expansion may require refilling either a
1316 // bigLAB or a smallLAB plus refilling a PromotionInfo object. MinChunkSize
1317 // is added because the dictionary may over-allocate to avoid fragmentation.
1318 size_t space = obj_size;
1319 if (!_adaptive_freelists) {
1320 space = MAX2(space, _smallLinearAllocBlock._refillSize);
1321 }
1322 space += _promoInfo.refillSize() + 2 * MinChunkSize;
1323 return space;
1324 }
1325
1326 FreeChunk* CompactibleFreeListSpace::getChunkFromGreater(size_t numWords) {
1327 FreeChunk* ret;
1328
1329 assert(numWords >= MinChunkSize, "Size is less than minimum");
1330 assert(linearAllocationWouldFail() || bestFitFirst(),
1331 "Should not be here");
1332
1333 size_t i;
1334 size_t currSize = numWords + MinChunkSize;
1335 assert(currSize % MinObjAlignment == 0, "currSize should be aligned");
1336 for (i = currSize; i < IndexSetSize; i += IndexSetStride) {
1337 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
1338 if (fl->head()) {
1339 ret = getFromListGreater(fl, numWords);
1340 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
1341 return ret;
1342 }
1343 }
1344
1345 currSize = MAX2((size_t)SmallForDictionary,
1346 (size_t)(numWords + MinChunkSize));
1347
1348 /* Try to get a chunk that satisfies request, while avoiding
1349 fragmentation that can't be handled. */
1350 {
1351 ret = dictionary()->get_chunk(currSize);
1352 if (ret != NULL) {
1353 assert(ret->size() - numWords >= MinChunkSize,
1354 "Chunk is too small");
1355 _bt.allocated((HeapWord*)ret, ret->size());
1356 /* Carve returned chunk. */
1357 (void) splitChunkAndReturnRemainder(ret, numWords);
1358 /* Label this as no longer a free chunk. */
1359 assert(ret->is_free(), "This chunk should be free");
1360 ret->link_prev(NULL);
1361 }
1362 assert(ret == NULL || ret->is_free(), "Should be returning a free chunk");
1363 return ret;
1364 }
1365 ShouldNotReachHere();
1366 }
1367
1368 bool CompactibleFreeListSpace::verifyChunkInIndexedFreeLists(FreeChunk* fc) const {
1369 assert(fc->size() < IndexSetSize, "Size of chunk is too large");
1370 return _indexedFreeList[fc->size()].verify_chunk_in_free_list(fc);
1371 }
1372
1373 bool CompactibleFreeListSpace::verify_chunk_is_linear_alloc_block(FreeChunk* fc) const {
1374 assert((_smallLinearAllocBlock._ptr != (HeapWord*)fc) ||
1375 (_smallLinearAllocBlock._word_size == fc->size()),
1376 "Linear allocation block shows incorrect size");
1377 return ((_smallLinearAllocBlock._ptr == (HeapWord*)fc) &&
1378 (_smallLinearAllocBlock._word_size == fc->size()));
1379 }
1380
1381 // Check if the purported free chunk is present either as a linear
1382 // allocation block, the size-indexed table of (smaller) free blocks,
1383 // or the larger free blocks kept in the binary tree dictionary.
1384 bool CompactibleFreeListSpace::verify_chunk_in_free_list(FreeChunk* fc) const {
1385 if (verify_chunk_is_linear_alloc_block(fc)) {
1386 return true;
1387 } else if (fc->size() < IndexSetSize) {
1388 return verifyChunkInIndexedFreeLists(fc);
1389 } else {
1390 return dictionary()->verify_chunk_in_free_list(fc);
1391 }
1392 }
1393
1394 #ifndef PRODUCT
1395 void CompactibleFreeListSpace::assert_locked() const {
1396 CMSLockVerifier::assert_locked(freelistLock(), parDictionaryAllocLock());
1397 }
1398
1399 void CompactibleFreeListSpace::assert_locked(const Mutex* lock) const {
1400 CMSLockVerifier::assert_locked(lock);
1401 }
1402 #endif
1403
1404 FreeChunk* CompactibleFreeListSpace::allocateScratch(size_t size) {
1405 // In the parallel case, the main thread holds the free list lock
1406 // on behalf the parallel threads.
1407 FreeChunk* fc;
1408 {
1409 // If GC is parallel, this might be called by several threads.
1410 // This should be rare enough that the locking overhead won't affect
1411 // the sequential code.
1412 MutexLockerEx x(parDictionaryAllocLock(),
1413 Mutex::_no_safepoint_check_flag);
1414 fc = getChunkFromDictionary(size);
1415 }
1416 if (fc != NULL) {
1417 fc->dontCoalesce();
1418 assert(fc->is_free(), "Should be free, but not coalescable");
1419 // Verify that the block offset table shows this to
1420 // be a single block, but not one which is unallocated.
1421 _bt.verify_single_block((HeapWord*)fc, fc->size());
1422 _bt.verify_not_unallocated((HeapWord*)fc, fc->size());
1423 }
1424 return fc;
1425 }
1426
1427 oop CompactibleFreeListSpace::promote(oop obj, size_t obj_size) {
1428 assert(obj_size == (size_t)obj->size(), "bad obj_size passed in");
1429 assert_locked();
1430
1431 // if we are tracking promotions, then first ensure space for
1432 // promotion (including spooling space for saving header if necessary).
1433 // then allocate and copy, then track promoted info if needed.
1434 // When tracking (see PromotionInfo::track()), the mark word may
1435 // be displaced and in this case restoration of the mark word
1436 // occurs in the (oop_since_save_marks_)iterate phase.
1437 if (_promoInfo.tracking() && !_promoInfo.ensure_spooling_space()) {
1438 return NULL;
1439 }
1440 // Call the allocate(size_t, bool) form directly to avoid the
1441 // additional call through the allocate(size_t) form. Having
1442 // the compile inline the call is problematic because allocate(size_t)
1443 // is a virtual method.
1444 HeapWord* res = allocate(adjustObjectSize(obj_size));
1445 if (res != NULL) {
1446 Copy::aligned_disjoint_words((HeapWord*)obj, res, obj_size);
1447 // if we should be tracking promotions, do so.
1448 if (_promoInfo.tracking()) {
1449 _promoInfo.track((PromotedObject*)res);
1450 }
1451 }
1452 return oop(res);
1453 }
1454
1455 HeapWord*
1456 CompactibleFreeListSpace::getChunkFromSmallLinearAllocBlock(size_t size) {
1457 assert_locked();
1458 assert(size >= MinChunkSize, "minimum chunk size");
1459 assert(size < _smallLinearAllocBlock._allocation_size_limit,
1460 "maximum from smallLinearAllocBlock");
1461 return getChunkFromLinearAllocBlock(&_smallLinearAllocBlock, size);
1462 }
1463
1464 HeapWord*
1465 CompactibleFreeListSpace::getChunkFromLinearAllocBlock(LinearAllocBlock *blk,
1466 size_t size) {
1467 assert_locked();
1468 assert(size >= MinChunkSize, "too small");
1469 HeapWord* res = NULL;
1470 // Try to do linear allocation from blk, making sure that
1471 if (blk->_word_size == 0) {
1472 // We have probably been unable to fill this either in the prologue or
1473 // when it was exhausted at the last linear allocation. Bail out until
1474 // next time.
1475 assert(blk->_ptr == NULL, "consistency check");
1476 return NULL;
1477 }
1478 assert(blk->_word_size != 0 && blk->_ptr != NULL, "consistency check");
1479 res = getChunkFromLinearAllocBlockRemainder(blk, size);
1480 if (res != NULL) return res;
1481
1482 // about to exhaust this linear allocation block
1483 if (blk->_word_size == size) { // exactly satisfied
1484 res = blk->_ptr;
1485 _bt.allocated(res, blk->_word_size);
1486 } else if (size + MinChunkSize <= blk->_refillSize) {
1487 size_t sz = blk->_word_size;
1488 // Update _unallocated_block if the size is such that chunk would be
1489 // returned to the indexed free list. All other chunks in the indexed
1490 // free lists are allocated from the dictionary so that _unallocated_block
1491 // has already been adjusted for them. Do it here so that the cost
1492 // for all chunks added back to the indexed free lists.
1493 if (sz < SmallForDictionary) {
1494 _bt.allocated(blk->_ptr, sz);
1495 }
1496 // Return the chunk that isn't big enough, and then refill below.
1497 addChunkToFreeLists(blk->_ptr, sz);
1498 split_birth(sz);
1499 // Don't keep statistics on adding back chunk from a LinAB.
1500 } else {
1501 // A refilled block would not satisfy the request.
1502 return NULL;
1503 }
1504
1505 blk->_ptr = NULL; blk->_word_size = 0;
1506 refillLinearAllocBlock(blk);
1507 assert(blk->_ptr == NULL || blk->_word_size >= size + MinChunkSize,
1508 "block was replenished");
1509 if (res != NULL) {
1510 split_birth(size);
1511 repairLinearAllocBlock(blk);
1512 } else if (blk->_ptr != NULL) {
1513 res = blk->_ptr;
1514 size_t blk_size = blk->_word_size;
1515 blk->_word_size -= size;
1516 blk->_ptr += size;
1517 split_birth(size);
1518 repairLinearAllocBlock(blk);
1519 // Update BOT last so that other (parallel) GC threads see a consistent
1520 // view of the BOT and free blocks.
1521 // Above must occur before BOT is updated below.
1522 OrderAccess::storestore();
1523 _bt.split_block(res, blk_size, size); // adjust block offset table
1524 }
1525 return res;
1526 }
1527
1528 HeapWord* CompactibleFreeListSpace::getChunkFromLinearAllocBlockRemainder(
1529 LinearAllocBlock* blk,
1530 size_t size) {
1531 assert_locked();
1532 assert(size >= MinChunkSize, "too small");
1533
1534 HeapWord* res = NULL;
1535 // This is the common case. Keep it simple.
1536 if (blk->_word_size >= size + MinChunkSize) {
1537 assert(blk->_ptr != NULL, "consistency check");
1538 res = blk->_ptr;
1539 // Note that the BOT is up-to-date for the linAB before allocation. It
1540 // indicates the start of the linAB. The split_block() updates the
1541 // BOT for the linAB after the allocation (indicates the start of the
1542 // next chunk to be allocated).
1543 size_t blk_size = blk->_word_size;
1544 blk->_word_size -= size;
1545 blk->_ptr += size;
1546 split_birth(size);
1547 repairLinearAllocBlock(blk);
1548 // Update BOT last so that other (parallel) GC threads see a consistent
1549 // view of the BOT and free blocks.
1550 // Above must occur before BOT is updated below.
1551 OrderAccess::storestore();
1552 _bt.split_block(res, blk_size, size); // adjust block offset table
1553 _bt.allocated(res, size);
1554 }
1555 return res;
1556 }
1557
1558 FreeChunk*
1559 CompactibleFreeListSpace::getChunkFromIndexedFreeList(size_t size) {
1560 assert_locked();
1561 assert(size < SmallForDictionary, "just checking");
1562 FreeChunk* res;
1563 res = _indexedFreeList[size].get_chunk_at_head();
1564 if (res == NULL) {
1565 res = getChunkFromIndexedFreeListHelper(size);
1566 }
1567 _bt.verify_not_unallocated((HeapWord*) res, size);
1568 assert(res == NULL || res->size() == size, "Incorrect block size");
1569 return res;
1570 }
1571
1572 FreeChunk*
1573 CompactibleFreeListSpace::getChunkFromIndexedFreeListHelper(size_t size,
1574 bool replenish) {
1575 assert_locked();
1576 FreeChunk* fc = NULL;
1577 if (size < SmallForDictionary) {
1578 assert(_indexedFreeList[size].head() == NULL ||
1579 _indexedFreeList[size].surplus() <= 0,
1580 "List for this size should be empty or under populated");
1581 // Try best fit in exact lists before replenishing the list
1582 if (!bestFitFirst() || (fc = bestFitSmall(size)) == NULL) {
1583 // Replenish list.
1584 //
1585 // Things tried that failed.
1586 // Tried allocating out of the two LinAB's first before
1587 // replenishing lists.
1588 // Tried small linAB of size 256 (size in indexed list)
1589 // and replenishing indexed lists from the small linAB.
1590 //
1591 FreeChunk* newFc = NULL;
1592 const size_t replenish_size = CMSIndexedFreeListReplenish * size;
1593 if (replenish_size < SmallForDictionary) {
1594 // Do not replenish from an underpopulated size.
1595 if (_indexedFreeList[replenish_size].surplus() > 0 &&
1596 _indexedFreeList[replenish_size].head() != NULL) {
1597 newFc = _indexedFreeList[replenish_size].get_chunk_at_head();
1598 } else if (bestFitFirst()) {
1599 newFc = bestFitSmall(replenish_size);
1600 }
1601 }
1602 if (newFc == NULL && replenish_size > size) {
1603 assert(CMSIndexedFreeListReplenish > 1, "ctl pt invariant");
1604 newFc = getChunkFromIndexedFreeListHelper(replenish_size, false);
1605 }
1606 // Note: The stats update re split-death of block obtained above
1607 // will be recorded below precisely when we know we are going to
1608 // be actually splitting it into more than one pieces below.
1609 if (newFc != NULL) {
1610 if (replenish || CMSReplenishIntermediate) {
1611 // Replenish this list and return one block to caller.
1612 size_t i;
1613 FreeChunk *curFc, *nextFc;
1614 size_t num_blk = newFc->size() / size;
1615 assert(num_blk >= 1, "Smaller than requested?");
1616 assert(newFc->size() % size == 0, "Should be integral multiple of request");
1617 if (num_blk > 1) {
1618 // we are sure we will be splitting the block just obtained
1619 // into multiple pieces; record the split-death of the original
1620 splitDeath(replenish_size);
1621 }
1622 // carve up and link blocks 0, ..., num_blk - 2
1623 // The last chunk is not added to the lists but is returned as the
1624 // free chunk.
1625 for (curFc = newFc, nextFc = (FreeChunk*)((HeapWord*)curFc + size),
1626 i = 0;
1627 i < (num_blk - 1);
1628 curFc = nextFc, nextFc = (FreeChunk*)((HeapWord*)nextFc + size),
1629 i++) {
1630 curFc->set_size(size);
1631 // Don't record this as a return in order to try and
1632 // determine the "returns" from a GC.
1633 _bt.verify_not_unallocated((HeapWord*) fc, size);
1634 _indexedFreeList[size].return_chunk_at_tail(curFc, false);
1635 _bt.mark_block((HeapWord*)curFc, size);
1636 split_birth(size);
1637 // Don't record the initial population of the indexed list
1638 // as a split birth.
1639 }
1640
1641 // check that the arithmetic was OK above
1642 assert((HeapWord*)nextFc == (HeapWord*)newFc + num_blk*size,
1643 "inconsistency in carving newFc");
1644 curFc->set_size(size);
1645 _bt.mark_block((HeapWord*)curFc, size);
1646 split_birth(size);
1647 fc = curFc;
1648 } else {
1649 // Return entire block to caller
1650 fc = newFc;
1651 }
1652 }
1653 }
1654 } else {
1655 // Get a free chunk from the free chunk dictionary to be returned to
1656 // replenish the indexed free list.
1657 fc = getChunkFromDictionaryExact(size);
1658 }
1659 // assert(fc == NULL || fc->is_free(), "Should be returning a free chunk");
1660 return fc;
1661 }
1662
1663 FreeChunk*
1664 CompactibleFreeListSpace::getChunkFromDictionary(size_t size) {
1665 assert_locked();
1666 FreeChunk* fc = _dictionary->get_chunk(size,
1667 FreeBlockDictionary<FreeChunk>::atLeast);
1668 if (fc == NULL) {
1669 return NULL;
1670 }
1671 _bt.allocated((HeapWord*)fc, fc->size());
1672 if (fc->size() >= size + MinChunkSize) {
1673 fc = splitChunkAndReturnRemainder(fc, size);
1674 }
1675 assert(fc->size() >= size, "chunk too small");
1676 assert(fc->size() < size + MinChunkSize, "chunk too big");
1677 _bt.verify_single_block((HeapWord*)fc, fc->size());
1678 return fc;
1679 }
1680
1681 FreeChunk*
1682 CompactibleFreeListSpace::getChunkFromDictionaryExact(size_t size) {
1683 assert_locked();
1684 FreeChunk* fc = _dictionary->get_chunk(size,
1685 FreeBlockDictionary<FreeChunk>::atLeast);
1686 if (fc == NULL) {
1687 return fc;
1688 }
1689 _bt.allocated((HeapWord*)fc, fc->size());
1690 if (fc->size() == size) {
1691 _bt.verify_single_block((HeapWord*)fc, size);
1692 return fc;
1693 }
1694 assert(fc->size() > size, "get_chunk() guarantee");
1695 if (fc->size() < size + MinChunkSize) {
1696 // Return the chunk to the dictionary and go get a bigger one.
1697 returnChunkToDictionary(fc);
1698 fc = _dictionary->get_chunk(size + MinChunkSize,
1699 FreeBlockDictionary<FreeChunk>::atLeast);
1700 if (fc == NULL) {
1701 return NULL;
1702 }
1703 _bt.allocated((HeapWord*)fc, fc->size());
1704 }
1705 assert(fc->size() >= size + MinChunkSize, "tautology");
1706 fc = splitChunkAndReturnRemainder(fc, size);
1707 assert(fc->size() == size, "chunk is wrong size");
1708 _bt.verify_single_block((HeapWord*)fc, size);
1709 return fc;
1710 }
1711
1712 void
1713 CompactibleFreeListSpace::returnChunkToDictionary(FreeChunk* chunk) {
1714 assert_locked();
1715
1716 size_t size = chunk->size();
1717 _bt.verify_single_block((HeapWord*)chunk, size);
1718 // adjust _unallocated_block downward, as necessary
1719 _bt.freed((HeapWord*)chunk, size);
1720 _dictionary->return_chunk(chunk);
1721 #ifndef PRODUCT
1722 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) {
1723 TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >* tc = TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::as_TreeChunk(chunk);
1724 TreeList<FreeChunk, AdaptiveFreeList<FreeChunk> >* tl = tc->list();
1725 tl->verify_stats();
1726 }
1727 #endif // PRODUCT
1728 }
1729
1730 void
1731 CompactibleFreeListSpace::returnChunkToFreeList(FreeChunk* fc) {
1732 assert_locked();
1733 size_t size = fc->size();
1734 _bt.verify_single_block((HeapWord*) fc, size);
1735 _bt.verify_not_unallocated((HeapWord*) fc, size);
1736 if (_adaptive_freelists) {
1737 _indexedFreeList[size].return_chunk_at_tail(fc);
1738 } else {
1739 _indexedFreeList[size].return_chunk_at_head(fc);
1740 }
1741 #ifndef PRODUCT
1742 if (CMSCollector::abstract_state() != CMSCollector::Sweeping) {
1743 _indexedFreeList[size].verify_stats();
1744 }
1745 #endif // PRODUCT
1746 }
1747
1748 // Add chunk to end of last block -- if it's the largest
1749 // block -- and update BOT and census data. We would
1750 // of course have preferred to coalesce it with the
1751 // last block, but it's currently less expensive to find the
1752 // largest block than it is to find the last.
1753 void
1754 CompactibleFreeListSpace::addChunkToFreeListsAtEndRecordingStats(
1755 HeapWord* chunk, size_t size) {
1756 // check that the chunk does lie in this space!
1757 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!");
1758 // One of the parallel gc task threads may be here
1759 // whilst others are allocating.
1760 Mutex* lock = NULL;
1761 if (ParallelGCThreads != 0) {
1762 lock = &_parDictionaryAllocLock;
1763 }
1764 FreeChunk* ec;
1765 {
1766 MutexLockerEx x(lock, Mutex::_no_safepoint_check_flag);
1767 ec = dictionary()->find_largest_dict(); // get largest block
1768 if (ec != NULL && ec->end() == (uintptr_t*) chunk) {
1769 // It's a coterminal block - we can coalesce.
1770 size_t old_size = ec->size();
1771 coalDeath(old_size);
1772 removeChunkFromDictionary(ec);
1773 size += old_size;
1774 } else {
1775 ec = (FreeChunk*)chunk;
1776 }
1777 }
1778 ec->set_size(size);
1779 debug_only(ec->mangleFreed(size));
1780 if (size < SmallForDictionary && ParallelGCThreads != 0) {
1781 lock = _indexedFreeListParLocks[size];
1782 }
1783 MutexLockerEx x(lock, Mutex::_no_safepoint_check_flag);
1784 addChunkAndRepairOffsetTable((HeapWord*)ec, size, true);
1785 // record the birth under the lock since the recording involves
1786 // manipulation of the list on which the chunk lives and
1787 // if the chunk is allocated and is the last on the list,
1788 // the list can go away.
1789 coalBirth(size);
1790 }
1791
1792 void
1793 CompactibleFreeListSpace::addChunkToFreeLists(HeapWord* chunk,
1794 size_t size) {
1795 // check that the chunk does lie in this space!
1796 assert(chunk != NULL && is_in_reserved(chunk), "Not in this space!");
1797 assert_locked();
1798 _bt.verify_single_block(chunk, size);
1799
1800 FreeChunk* fc = (FreeChunk*) chunk;
1801 fc->set_size(size);
1802 debug_only(fc->mangleFreed(size));
1803 if (size < SmallForDictionary) {
1804 returnChunkToFreeList(fc);
1805 } else {
1806 returnChunkToDictionary(fc);
1807 }
1808 }
1809
1810 void
1811 CompactibleFreeListSpace::addChunkAndRepairOffsetTable(HeapWord* chunk,
1812 size_t size, bool coalesced) {
1813 assert_locked();
1814 assert(chunk != NULL, "null chunk");
1815 if (coalesced) {
1816 // repair BOT
1817 _bt.single_block(chunk, size);
1818 }
1819 addChunkToFreeLists(chunk, size);
1820 }
1821
1822 // We _must_ find the purported chunk on our free lists;
1823 // we assert if we don't.
1824 void
1825 CompactibleFreeListSpace::removeFreeChunkFromFreeLists(FreeChunk* fc) {
1826 size_t size = fc->size();
1827 assert_locked();
1828 debug_only(verifyFreeLists());
1829 if (size < SmallForDictionary) {
1830 removeChunkFromIndexedFreeList(fc);
1831 } else {
1832 removeChunkFromDictionary(fc);
1833 }
1834 _bt.verify_single_block((HeapWord*)fc, size);
1835 debug_only(verifyFreeLists());
1836 }
1837
1838 void
1839 CompactibleFreeListSpace::removeChunkFromDictionary(FreeChunk* fc) {
1840 size_t size = fc->size();
1841 assert_locked();
1842 assert(fc != NULL, "null chunk");
1843 _bt.verify_single_block((HeapWord*)fc, size);
1844 _dictionary->remove_chunk(fc);
1845 // adjust _unallocated_block upward, as necessary
1846 _bt.allocated((HeapWord*)fc, size);
1847 }
1848
1849 void
1850 CompactibleFreeListSpace::removeChunkFromIndexedFreeList(FreeChunk* fc) {
1851 assert_locked();
1852 size_t size = fc->size();
1853 _bt.verify_single_block((HeapWord*)fc, size);
1854 NOT_PRODUCT(
1855 if (FLSVerifyIndexTable) {
1856 verifyIndexedFreeList(size);
1857 }
1858 )
1859 _indexedFreeList[size].remove_chunk(fc);
1860 NOT_PRODUCT(
1861 if (FLSVerifyIndexTable) {
1862 verifyIndexedFreeList(size);
1863 }
1864 )
1865 }
1866
1867 FreeChunk* CompactibleFreeListSpace::bestFitSmall(size_t numWords) {
1868 /* A hint is the next larger size that has a surplus.
1869 Start search at a size large enough to guarantee that
1870 the excess is >= MIN_CHUNK. */
1871 size_t start = align_object_size(numWords + MinChunkSize);
1872 if (start < IndexSetSize) {
1873 AdaptiveFreeList<FreeChunk>* it = _indexedFreeList;
1874 size_t hint = _indexedFreeList[start].hint();
1875 while (hint < IndexSetSize) {
1876 assert(hint % MinObjAlignment == 0, "hint should be aligned");
1877 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[hint];
1878 if (fl->surplus() > 0 && fl->head() != NULL) {
1879 // Found a list with surplus, reset original hint
1880 // and split out a free chunk which is returned.
1881 _indexedFreeList[start].set_hint(hint);
1882 FreeChunk* res = getFromListGreater(fl, numWords);
1883 assert(res == NULL || res->is_free(),
1884 "Should be returning a free chunk");
1885 return res;
1886 }
1887 hint = fl->hint(); /* keep looking */
1888 }
1889 /* None found. */
1890 it[start].set_hint(IndexSetSize);
1891 }
1892 return NULL;
1893 }
1894
1895 /* Requires fl->size >= numWords + MinChunkSize */
1896 FreeChunk* CompactibleFreeListSpace::getFromListGreater(AdaptiveFreeList<FreeChunk>* fl,
1897 size_t numWords) {
1898 FreeChunk *curr = fl->head();
1899 size_t oldNumWords = curr->size();
1900 assert(numWords >= MinChunkSize, "Word size is too small");
1901 assert(curr != NULL, "List is empty");
1902 assert(oldNumWords >= numWords + MinChunkSize,
1903 "Size of chunks in the list is too small");
1904
1905 fl->remove_chunk(curr);
1906 // recorded indirectly by splitChunkAndReturnRemainder -
1907 // smallSplit(oldNumWords, numWords);
1908 FreeChunk* new_chunk = splitChunkAndReturnRemainder(curr, numWords);
1909 // Does anything have to be done for the remainder in terms of
1910 // fixing the card table?
1911 assert(new_chunk == NULL || new_chunk->is_free(),
1912 "Should be returning a free chunk");
1913 return new_chunk;
1914 }
1915
1916 FreeChunk*
1917 CompactibleFreeListSpace::splitChunkAndReturnRemainder(FreeChunk* chunk,
1918 size_t new_size) {
1919 assert_locked();
1920 size_t size = chunk->size();
1921 assert(size > new_size, "Split from a smaller block?");
1922 assert(is_aligned(chunk), "alignment problem");
1923 assert(size == adjustObjectSize(size), "alignment problem");
1924 size_t rem_size = size - new_size;
1925 assert(rem_size == adjustObjectSize(rem_size), "alignment problem");
1926 assert(rem_size >= MinChunkSize, "Free chunk smaller than minimum");
1927 FreeChunk* ffc = (FreeChunk*)((HeapWord*)chunk + new_size);
1928 assert(is_aligned(ffc), "alignment problem");
1929 ffc->set_size(rem_size);
1930 ffc->link_next(NULL);
1931 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
1932 // Above must occur before BOT is updated below.
1933 // adjust block offset table
1934 OrderAccess::storestore();
1935 assert(chunk->is_free() && ffc->is_free(), "Error");
1936 _bt.split_block((HeapWord*)chunk, chunk->size(), new_size);
1937 if (rem_size < SmallForDictionary) {
1938 bool is_par = (SharedHeap::heap()->n_par_threads() > 0);
1939 if (is_par) _indexedFreeListParLocks[rem_size]->lock();
1940 assert(!is_par ||
1941 (SharedHeap::heap()->n_par_threads() ==
1942 SharedHeap::heap()->workers()->active_workers()), "Mismatch");
1943 returnChunkToFreeList(ffc);
1944 split(size, rem_size);
1945 if (is_par) _indexedFreeListParLocks[rem_size]->unlock();
1946 } else {
1947 returnChunkToDictionary(ffc);
1948 split(size ,rem_size);
1949 }
1950 chunk->set_size(new_size);
1951 return chunk;
1952 }
1953
1954 void
1955 CompactibleFreeListSpace::sweep_completed() {
1956 // Now that space is probably plentiful, refill linear
1957 // allocation blocks as needed.
1958 refillLinearAllocBlocksIfNeeded();
1959 }
1960
1961 void
1962 CompactibleFreeListSpace::gc_prologue() {
1963 assert_locked();
1964 if (PrintFLSStatistics != 0) {
1965 gclog_or_tty->print("Before GC:\n");
1966 reportFreeListStatistics();
1967 }
1968 refillLinearAllocBlocksIfNeeded();
1969 }
1970
1971 void
1972 CompactibleFreeListSpace::gc_epilogue() {
1973 assert_locked();
1974 if (PrintGCDetails && Verbose && !_adaptive_freelists) {
1975 if (_smallLinearAllocBlock._word_size == 0)
1976 warning("CompactibleFreeListSpace(epilogue):: Linear allocation failure");
1977 }
1978 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
1979 _promoInfo.stopTrackingPromotions();
1980 repairLinearAllocationBlocks();
1981 // Print Space's stats
1982 if (PrintFLSStatistics != 0) {
1983 gclog_or_tty->print("After GC:\n");
1984 reportFreeListStatistics();
1985 }
1986 }
1987
1988 // Iteration support, mostly delegated from a CMS generation
1989
1990 void CompactibleFreeListSpace::save_marks() {
1991 assert(Thread::current()->is_VM_thread(),
1992 "Global variable should only be set when single-threaded");
1993 // Mark the "end" of the used space at the time of this call;
1994 // note, however, that promoted objects from this point
1995 // on are tracked in the _promoInfo below.
1996 set_saved_mark_word(unallocated_block());
1997 #ifdef ASSERT
1998 // Check the sanity of save_marks() etc.
1999 MemRegion ur = used_region();
2000 MemRegion urasm = used_region_at_save_marks();
2001 assert(ur.contains(urasm),
2002 err_msg(" Error at save_marks(): [" PTR_FORMAT "," PTR_FORMAT ")"
2003 " should contain [" PTR_FORMAT "," PTR_FORMAT ")",
2004 p2i(ur.start()), p2i(ur.end()), p2i(urasm.start()), p2i(urasm.end())));
2005 #endif
2006 // inform allocator that promotions should be tracked.
2007 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency");
2008 _promoInfo.startTrackingPromotions();
2009 }
2010
2011 bool CompactibleFreeListSpace::no_allocs_since_save_marks() {
2012 assert(_promoInfo.tracking(), "No preceding save_marks?");
2013 assert(SharedHeap::heap()->n_par_threads() == 0,
2014 "Shouldn't be called if using parallel gc.");
2015 return _promoInfo.noPromotions();
2016 }
2017
2018 #define CFLS_OOP_SINCE_SAVE_MARKS_DEFN(OopClosureType, nv_suffix) \
2019 \
2020 void CompactibleFreeListSpace:: \
2021 oop_since_save_marks_iterate##nv_suffix(OopClosureType* blk) { \
2022 assert(SharedHeap::heap()->n_par_threads() == 0, \
2023 "Shouldn't be called (yet) during parallel part of gc."); \
2024 _promoInfo.promoted_oops_iterate##nv_suffix(blk); \
2025 /* \
2026 * This also restores any displaced headers and removes the elements from \
2027 * the iteration set as they are processed, so that we have a clean slate \
2028 * at the end of the iteration. Note, thus, that if new objects are \
2029 * promoted as a result of the iteration they are iterated over as well. \
2030 */ \
2031 assert(_promoInfo.noPromotions(), "_promoInfo inconsistency"); \
2032 }
2033
2034 ALL_SINCE_SAVE_MARKS_CLOSURES(CFLS_OOP_SINCE_SAVE_MARKS_DEFN)
2035
2036 bool CompactibleFreeListSpace::linearAllocationWouldFail() const {
2037 return _smallLinearAllocBlock._word_size == 0;
2038 }
2039
2040 void CompactibleFreeListSpace::repairLinearAllocationBlocks() {
2041 // Fix up linear allocation blocks to look like free blocks
2042 repairLinearAllocBlock(&_smallLinearAllocBlock);
2043 }
2044
2045 void CompactibleFreeListSpace::repairLinearAllocBlock(LinearAllocBlock* blk) {
2046 assert_locked();
2047 if (blk->_ptr != NULL) {
2048 assert(blk->_word_size != 0 && blk->_word_size >= MinChunkSize,
2049 "Minimum block size requirement");
2050 FreeChunk* fc = (FreeChunk*)(blk->_ptr);
2051 fc->set_size(blk->_word_size);
2052 fc->link_prev(NULL); // mark as free
2053 fc->dontCoalesce();
2054 assert(fc->is_free(), "just marked it free");
2055 assert(fc->cantCoalesce(), "just marked it uncoalescable");
2056 }
2057 }
2058
2059 void CompactibleFreeListSpace::refillLinearAllocBlocksIfNeeded() {
2060 assert_locked();
2061 if (_smallLinearAllocBlock._ptr == NULL) {
2062 assert(_smallLinearAllocBlock._word_size == 0,
2063 "Size of linAB should be zero if the ptr is NULL");
2064 // Reset the linAB refill and allocation size limit.
2065 _smallLinearAllocBlock.set(0, 0, 1024*SmallForLinearAlloc, SmallForLinearAlloc);
2066 }
2067 refillLinearAllocBlockIfNeeded(&_smallLinearAllocBlock);
2068 }
2069
2070 void
2071 CompactibleFreeListSpace::refillLinearAllocBlockIfNeeded(LinearAllocBlock* blk) {
2072 assert_locked();
2073 assert((blk->_ptr == NULL && blk->_word_size == 0) ||
2074 (blk->_ptr != NULL && blk->_word_size >= MinChunkSize),
2075 "blk invariant");
2076 if (blk->_ptr == NULL) {
2077 refillLinearAllocBlock(blk);
2078 }
2079 if (PrintMiscellaneous && Verbose) {
2080 if (blk->_word_size == 0) {
2081 warning("CompactibleFreeListSpace(prologue):: Linear allocation failure");
2082 }
2083 }
2084 }
2085
2086 void
2087 CompactibleFreeListSpace::refillLinearAllocBlock(LinearAllocBlock* blk) {
2088 assert_locked();
2089 assert(blk->_word_size == 0 && blk->_ptr == NULL,
2090 "linear allocation block should be empty");
2091 FreeChunk* fc;
2092 if (blk->_refillSize < SmallForDictionary &&
2093 (fc = getChunkFromIndexedFreeList(blk->_refillSize)) != NULL) {
2094 // A linAB's strategy might be to use small sizes to reduce
2095 // fragmentation but still get the benefits of allocation from a
2096 // linAB.
2097 } else {
2098 fc = getChunkFromDictionary(blk->_refillSize);
2099 }
2100 if (fc != NULL) {
2101 blk->_ptr = (HeapWord*)fc;
2102 blk->_word_size = fc->size();
2103 fc->dontCoalesce(); // to prevent sweeper from sweeping us up
2104 }
2105 }
2106
2107 // Support for concurrent collection policy decisions.
2108 bool CompactibleFreeListSpace::should_concurrent_collect() const {
2109 // In the future we might want to add in frgamentation stats --
2110 // including erosion of the "mountain" into this decision as well.
2111 return !adaptive_freelists() && linearAllocationWouldFail();
2112 }
2113
2114 // Support for compaction
2115
2116 void CompactibleFreeListSpace::prepare_for_compaction(CompactPoint* cp) {
2117 SCAN_AND_FORWARD(cp,end,block_is_obj,block_size);
2118 // prepare_for_compaction() uses the space between live objects
2119 // so that later phase can skip dead space quickly. So verification
2120 // of the free lists doesn't work after.
2121 }
2122
2123 #define obj_size(q) adjustObjectSize(oop(q)->size())
2124 #define adjust_obj_size(s) adjustObjectSize(s)
2125
2126 void CompactibleFreeListSpace::adjust_pointers() {
2127 // In other versions of adjust_pointers(), a bail out
2128 // based on the amount of live data in the generation
2129 // (i.e., if 0, bail out) may be used.
2130 // Cannot test used() == 0 here because the free lists have already
2131 // been mangled by the compaction.
2132
2133 SCAN_AND_ADJUST_POINTERS(adjust_obj_size);
2134 // See note about verification in prepare_for_compaction().
2135 }
2136
2137 void CompactibleFreeListSpace::compact() {
2138 SCAN_AND_COMPACT(obj_size);
2139 }
2140
2141 // fragmentation_metric = 1 - [sum of (fbs**2) / (sum of fbs)**2]
2142 // where fbs is free block sizes
2143 double CompactibleFreeListSpace::flsFrag() const {
2144 size_t itabFree = totalSizeInIndexedFreeLists();
2145 double frag = 0.0;
2146 size_t i;
2147
2148 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2149 double sz = i;
2150 frag += _indexedFreeList[i].count() * (sz * sz);
2151 }
2152
2153 double totFree = itabFree +
2154 _dictionary->total_chunk_size(DEBUG_ONLY(freelistLock()));
2155 if (totFree > 0) {
2156 frag = ((frag + _dictionary->sum_of_squared_block_sizes()) /
2157 (totFree * totFree));
2158 frag = (double)1.0 - frag;
2159 } else {
2160 assert(frag == 0.0, "Follows from totFree == 0");
2161 }
2162 return frag;
2163 }
2164
2165 void CompactibleFreeListSpace::beginSweepFLCensus(
2166 float inter_sweep_current,
2167 float inter_sweep_estimate,
2168 float intra_sweep_estimate) {
2169 assert_locked();
2170 size_t i;
2171 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2172 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[i];
2173 if (PrintFLSStatistics > 1) {
2174 gclog_or_tty->print("size[" SIZE_FORMAT "] : ", i);
2175 }
2176 fl->compute_desired(inter_sweep_current, inter_sweep_estimate, intra_sweep_estimate);
2177 fl->set_coal_desired((ssize_t)((double)fl->desired() * CMSSmallCoalSurplusPercent));
2178 fl->set_before_sweep(fl->count());
2179 fl->set_bfr_surp(fl->surplus());
2180 }
2181 _dictionary->begin_sweep_dict_census(CMSLargeCoalSurplusPercent,
2182 inter_sweep_current,
2183 inter_sweep_estimate,
2184 intra_sweep_estimate);
2185 }
2186
2187 void CompactibleFreeListSpace::setFLSurplus() {
2188 assert_locked();
2189 size_t i;
2190 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2191 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2192 fl->set_surplus(fl->count() -
2193 (ssize_t)((double)fl->desired() * CMSSmallSplitSurplusPercent));
2194 }
2195 }
2196
2197 void CompactibleFreeListSpace::setFLHints() {
2198 assert_locked();
2199 size_t i;
2200 size_t h = IndexSetSize;
2201 for (i = IndexSetSize - 1; i != 0; i -= IndexSetStride) {
2202 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2203 fl->set_hint(h);
2204 if (fl->surplus() > 0) {
2205 h = i;
2206 }
2207 }
2208 }
2209
2210 void CompactibleFreeListSpace::clearFLCensus() {
2211 assert_locked();
2212 size_t i;
2213 for (i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2214 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2215 fl->set_prev_sweep(fl->count());
2216 fl->set_coal_births(0);
2217 fl->set_coal_deaths(0);
2218 fl->set_split_births(0);
2219 fl->set_split_deaths(0);
2220 }
2221 }
2222
2223 void CompactibleFreeListSpace::endSweepFLCensus(size_t sweep_count) {
2224 if (PrintFLSStatistics > 0) {
2225 HeapWord* largestAddr = (HeapWord*) dictionary()->find_largest_dict();
2226 gclog_or_tty->print_cr("CMS: Large block " PTR_FORMAT,
2227 p2i(largestAddr));
2228 }
2229 setFLSurplus();
2230 setFLHints();
2231 if (PrintGC && PrintFLSCensus > 0) {
2232 printFLCensus(sweep_count);
2233 }
2234 clearFLCensus();
2235 assert_locked();
2236 _dictionary->end_sweep_dict_census(CMSLargeSplitSurplusPercent);
2237 }
2238
2239 bool CompactibleFreeListSpace::coalOverPopulated(size_t size) {
2240 if (size < SmallForDictionary) {
2241 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2242 return (fl->coal_desired() < 0) ||
2243 ((int)fl->count() > fl->coal_desired());
2244 } else {
2245 return dictionary()->coal_dict_over_populated(size);
2246 }
2247 }
2248
2249 void CompactibleFreeListSpace::smallCoalBirth(size_t size) {
2250 assert(size < SmallForDictionary, "Size too large for indexed list");
2251 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2252 fl->increment_coal_births();
2253 fl->increment_surplus();
2254 }
2255
2256 void CompactibleFreeListSpace::smallCoalDeath(size_t size) {
2257 assert(size < SmallForDictionary, "Size too large for indexed list");
2258 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2259 fl->increment_coal_deaths();
2260 fl->decrement_surplus();
2261 }
2262
2263 void CompactibleFreeListSpace::coalBirth(size_t size) {
2264 if (size < SmallForDictionary) {
2265 smallCoalBirth(size);
2266 } else {
2267 dictionary()->dict_census_update(size,
2268 false /* split */,
2269 true /* birth */);
2270 }
2271 }
2272
2273 void CompactibleFreeListSpace::coalDeath(size_t size) {
2274 if(size < SmallForDictionary) {
2275 smallCoalDeath(size);
2276 } else {
2277 dictionary()->dict_census_update(size,
2278 false /* split */,
2279 false /* birth */);
2280 }
2281 }
2282
2283 void CompactibleFreeListSpace::smallSplitBirth(size_t size) {
2284 assert(size < SmallForDictionary, "Size too large for indexed list");
2285 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2286 fl->increment_split_births();
2287 fl->increment_surplus();
2288 }
2289
2290 void CompactibleFreeListSpace::smallSplitDeath(size_t size) {
2291 assert(size < SmallForDictionary, "Size too large for indexed list");
2292 AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[size];
2293 fl->increment_split_deaths();
2294 fl->decrement_surplus();
2295 }
2296
2297 void CompactibleFreeListSpace::split_birth(size_t size) {
2298 if (size < SmallForDictionary) {
2299 smallSplitBirth(size);
2300 } else {
2301 dictionary()->dict_census_update(size,
2302 true /* split */,
2303 true /* birth */);
2304 }
2305 }
2306
2307 void CompactibleFreeListSpace::splitDeath(size_t size) {
2308 if (size < SmallForDictionary) {
2309 smallSplitDeath(size);
2310 } else {
2311 dictionary()->dict_census_update(size,
2312 true /* split */,
2313 false /* birth */);
2314 }
2315 }
2316
2317 void CompactibleFreeListSpace::split(size_t from, size_t to1) {
2318 size_t to2 = from - to1;
2319 splitDeath(from);
2320 split_birth(to1);
2321 split_birth(to2);
2322 }
2323
2324 void CompactibleFreeListSpace::print() const {
2325 print_on(tty);
2326 }
2327
2328 void CompactibleFreeListSpace::prepare_for_verify() {
2329 assert_locked();
2330 repairLinearAllocationBlocks();
2331 // Verify that the SpoolBlocks look like free blocks of
2332 // appropriate sizes... To be done ...
2333 }
2334
2335 class VerifyAllBlksClosure: public BlkClosure {
2336 private:
2337 const CompactibleFreeListSpace* _sp;
2338 const MemRegion _span;
2339 HeapWord* _last_addr;
2340 size_t _last_size;
2341 bool _last_was_obj;
2342 bool _last_was_live;
2343
2344 public:
2345 VerifyAllBlksClosure(const CompactibleFreeListSpace* sp,
2346 MemRegion span) : _sp(sp), _span(span),
2347 _last_addr(NULL), _last_size(0),
2348 _last_was_obj(false), _last_was_live(false) { }
2349
2350 virtual size_t do_blk(HeapWord* addr) {
2351 size_t res;
2352 bool was_obj = false;
2353 bool was_live = false;
2354 if (_sp->block_is_obj(addr)) {
2355 was_obj = true;
2356 oop p = oop(addr);
2357 guarantee(p->is_oop(), "Should be an oop");
2358 res = _sp->adjustObjectSize(p->size());
2359 if (_sp->obj_is_alive(addr)) {
2360 was_live = true;
2361 p->verify();
2362 }
2363 } else {
2364 FreeChunk* fc = (FreeChunk*)addr;
2365 res = fc->size();
2366 if (FLSVerifyLists && !fc->cantCoalesce()) {
2367 guarantee(_sp->verify_chunk_in_free_list(fc),
2368 "Chunk should be on a free list");
2369 }
2370 }
2371 if (res == 0) {
2372 gclog_or_tty->print_cr("Livelock: no rank reduction!");
2373 gclog_or_tty->print_cr(
2374 " Current: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n"
2375 " Previous: addr = " PTR_FORMAT ", size = " SIZE_FORMAT ", obj = %s, live = %s \n",
2376 p2i(addr), res, was_obj ?"true":"false", was_live ?"true":"false",
2377 p2i(_last_addr), _last_size, _last_was_obj?"true":"false", _last_was_live?"true":"false");
2378 _sp->print_on(gclog_or_tty);
2379 guarantee(false, "Seppuku!");
2380 }
2381 _last_addr = addr;
2382 _last_size = res;
2383 _last_was_obj = was_obj;
2384 _last_was_live = was_live;
2385 return res;
2386 }
2387 };
2388
2389 class VerifyAllOopsClosure: public OopClosure {
2390 private:
2391 const CMSCollector* _collector;
2392 const CompactibleFreeListSpace* _sp;
2393 const MemRegion _span;
2394 const bool _past_remark;
2395 const CMSBitMap* _bit_map;
2396
2397 protected:
2398 void do_oop(void* p, oop obj) {
2399 if (_span.contains(obj)) { // the interior oop points into CMS heap
2400 if (!_span.contains(p)) { // reference from outside CMS heap
2401 // Should be a valid object; the first disjunct below allows
2402 // us to sidestep an assertion in block_is_obj() that insists
2403 // that p be in _sp. Note that several generations (and spaces)
2404 // are spanned by _span (CMS heap) above.
2405 guarantee(!_sp->is_in_reserved(obj) ||
2406 _sp->block_is_obj((HeapWord*)obj),
2407 "Should be an object");
2408 guarantee(obj->is_oop(), "Should be an oop");
2409 obj->verify();
2410 if (_past_remark) {
2411 // Remark has been completed, the object should be marked
2412 _bit_map->isMarked((HeapWord*)obj);
2413 }
2414 } else { // reference within CMS heap
2415 if (_past_remark) {
2416 // Remark has been completed -- so the referent should have
2417 // been marked, if referring object is.
2418 if (_bit_map->isMarked(_collector->block_start(p))) {
2419 guarantee(_bit_map->isMarked((HeapWord*)obj), "Marking error?");
2420 }
2421 }
2422 }
2423 } else if (_sp->is_in_reserved(p)) {
2424 // the reference is from FLS, and points out of FLS
2425 guarantee(obj->is_oop(), "Should be an oop");
2426 obj->verify();
2427 }
2428 }
2429
2430 template <class T> void do_oop_work(T* p) {
2431 T heap_oop = oopDesc::load_heap_oop(p);
2432 if (!oopDesc::is_null(heap_oop)) {
2433 oop obj = oopDesc::decode_heap_oop_not_null(heap_oop);
2434 do_oop(p, obj);
2435 }
2436 }
2437
2438 public:
2439 VerifyAllOopsClosure(const CMSCollector* collector,
2440 const CompactibleFreeListSpace* sp, MemRegion span,
2441 bool past_remark, CMSBitMap* bit_map) :
2442 _collector(collector), _sp(sp), _span(span),
2443 _past_remark(past_remark), _bit_map(bit_map) { }
2444
2445 virtual void do_oop(oop* p) { VerifyAllOopsClosure::do_oop_work(p); }
2446 virtual void do_oop(narrowOop* p) { VerifyAllOopsClosure::do_oop_work(p); }
2447 };
2448
2449 void CompactibleFreeListSpace::verify() const {
2450 assert_lock_strong(&_freelistLock);
2451 verify_objects_initialized();
2452 MemRegion span = _collector->_span;
2453 bool past_remark = (_collector->abstract_state() ==
2454 CMSCollector::Sweeping);
2455
2456 ResourceMark rm;
2457 HandleMark hm;
2458
2459 // Check integrity of CFL data structures
2460 _promoInfo.verify();
2461 _dictionary->verify();
2462 if (FLSVerifyIndexTable) {
2463 verifyIndexedFreeLists();
2464 }
2465 // Check integrity of all objects and free blocks in space
2466 {
2467 VerifyAllBlksClosure cl(this, span);
2468 ((CompactibleFreeListSpace*)this)->blk_iterate(&cl); // cast off const
2469 }
2470 // Check that all references in the heap to FLS
2471 // are to valid objects in FLS or that references in
2472 // FLS are to valid objects elsewhere in the heap
2473 if (FLSVerifyAllHeapReferences)
2474 {
2475 VerifyAllOopsClosure cl(_collector, this, span, past_remark,
2476 _collector->markBitMap());
2477 CollectedHeap* ch = Universe::heap();
2478
2479 // Iterate over all oops in the heap. Uses the _no_header version
2480 // since we are not interested in following the klass pointers.
2481 ch->oop_iterate_no_header(&cl);
2482 }
2483
2484 if (VerifyObjectStartArray) {
2485 // Verify the block offset table
2486 _bt.verify();
2487 }
2488 }
2489
2490 #ifndef PRODUCT
2491 void CompactibleFreeListSpace::verifyFreeLists() const {
2492 if (FLSVerifyLists) {
2493 _dictionary->verify();
2494 verifyIndexedFreeLists();
2495 } else {
2496 if (FLSVerifyDictionary) {
2497 _dictionary->verify();
2498 }
2499 if (FLSVerifyIndexTable) {
2500 verifyIndexedFreeLists();
2501 }
2502 }
2503 }
2504 #endif
2505
2506 void CompactibleFreeListSpace::verifyIndexedFreeLists() const {
2507 size_t i = 0;
2508 for (; i < IndexSetStart; i++) {
2509 guarantee(_indexedFreeList[i].head() == NULL, "should be NULL");
2510 }
2511 for (; i < IndexSetSize; i++) {
2512 verifyIndexedFreeList(i);
2513 }
2514 }
2515
2516 void CompactibleFreeListSpace::verifyIndexedFreeList(size_t size) const {
2517 FreeChunk* fc = _indexedFreeList[size].head();
2518 FreeChunk* tail = _indexedFreeList[size].tail();
2519 size_t num = _indexedFreeList[size].count();
2520 size_t n = 0;
2521 guarantee(((size >= IndexSetStart) && (size % IndexSetStride == 0)) || fc == NULL,
2522 "Slot should have been empty");
2523 for (; fc != NULL; fc = fc->next(), n++) {
2524 guarantee(fc->size() == size, "Size inconsistency");
2525 guarantee(fc->is_free(), "!free?");
2526 guarantee(fc->next() == NULL || fc->next()->prev() == fc, "Broken list");
2527 guarantee((fc->next() == NULL) == (fc == tail), "Incorrect tail");
2528 }
2529 guarantee(n == num, "Incorrect count");
2530 }
2531
2532 #ifndef PRODUCT
2533 void CompactibleFreeListSpace::check_free_list_consistency() const {
2534 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size() <= IndexSetSize),
2535 "Some sizes can't be allocated without recourse to"
2536 " linear allocation buffers");
2537 assert((TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >::min_size()*HeapWordSize == sizeof(TreeChunk<FreeChunk, AdaptiveFreeList<FreeChunk> >)),
2538 "else MIN_TREE_CHUNK_SIZE is wrong");
2539 assert(IndexSetStart != 0, "IndexSetStart not initialized");
2540 assert(IndexSetStride != 0, "IndexSetStride not initialized");
2541 }
2542 #endif
2543
2544 void CompactibleFreeListSpace::printFLCensus(size_t sweep_count) const {
2545 assert_lock_strong(&_freelistLock);
2546 AdaptiveFreeList<FreeChunk> total;
2547 gclog_or_tty->print("end sweep# " SIZE_FORMAT "\n", sweep_count);
2548 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
2549 size_t total_free = 0;
2550 for (size_t i = IndexSetStart; i < IndexSetSize; i += IndexSetStride) {
2551 const AdaptiveFreeList<FreeChunk> *fl = &_indexedFreeList[i];
2552 total_free += fl->count() * fl->size();
2553 if (i % (40*IndexSetStride) == 0) {
2554 AdaptiveFreeList<FreeChunk>::print_labels_on(gclog_or_tty, "size");
2555 }
2556 fl->print_on(gclog_or_tty);
2557 total.set_bfr_surp( total.bfr_surp() + fl->bfr_surp() );
2558 total.set_surplus( total.surplus() + fl->surplus() );
2559 total.set_desired( total.desired() + fl->desired() );
2560 total.set_prev_sweep( total.prev_sweep() + fl->prev_sweep() );
2561 total.set_before_sweep(total.before_sweep() + fl->before_sweep());
2562 total.set_count( total.count() + fl->count() );
2563 total.set_coal_births( total.coal_births() + fl->coal_births() );
2564 total.set_coal_deaths( total.coal_deaths() + fl->coal_deaths() );
2565 total.set_split_births(total.split_births() + fl->split_births());
2566 total.set_split_deaths(total.split_deaths() + fl->split_deaths());
2567 }
2568 total.print_on(gclog_or_tty, "TOTAL");
2569 gclog_or_tty->print_cr("Total free in indexed lists "
2570 SIZE_FORMAT " words", total_free);
2571 gclog_or_tty->print("growth: %8.5f deficit: %8.5f\n",
2572 (double)(total.split_births()+total.coal_births()-total.split_deaths()-total.coal_deaths())/
2573 (total.prev_sweep() != 0 ? (double)total.prev_sweep() : 1.0),
2574 (double)(total.desired() - total.count())/(total.desired() != 0 ? (double)total.desired() : 1.0));
2575 _dictionary->print_dict_census();
2576 }
2577
2578 ///////////////////////////////////////////////////////////////////////////
2579 // CFLS_LAB
2580 ///////////////////////////////////////////////////////////////////////////
2581
2582 #define VECTOR_257(x) \
2583 /* 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 */ \
2584 { 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, \
2585 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, \
2586 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, \
2587 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, \
2588 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, \
2589 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, \
2590 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, \
2591 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, \
2592 x }
2593
2594 // Initialize with default setting of CMSParPromoteBlocksToClaim, _not_
2595 // OldPLABSize, whose static default is different; if overridden at the
2596 // command-line, this will get reinitialized via a call to
2597 // modify_initialization() below.
2598 AdaptiveWeightedAverage CFLS_LAB::_blocks_to_claim[] =
2599 VECTOR_257(AdaptiveWeightedAverage(OldPLABWeight, (float)CMSParPromoteBlocksToClaim));
2600 size_t CFLS_LAB::_global_num_blocks[] = VECTOR_257(0);
2601 uint CFLS_LAB::_global_num_workers[] = VECTOR_257(0);
2602
2603 CFLS_LAB::CFLS_LAB(CompactibleFreeListSpace* cfls) :
2604 _cfls(cfls)
2605 {
2606 assert(CompactibleFreeListSpace::IndexSetSize == 257, "Modify VECTOR_257() macro above");
2607 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2608 i < CompactibleFreeListSpace::IndexSetSize;
2609 i += CompactibleFreeListSpace::IndexSetStride) {
2610 _indexedFreeList[i].set_size(i);
2611 _num_blocks[i] = 0;
2612 }
2613 }
2614
2615 static bool _CFLS_LAB_modified = false;
2616
2617 void CFLS_LAB::modify_initialization(size_t n, unsigned wt) {
2618 assert(!_CFLS_LAB_modified, "Call only once");
2619 _CFLS_LAB_modified = true;
2620 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2621 i < CompactibleFreeListSpace::IndexSetSize;
2622 i += CompactibleFreeListSpace::IndexSetStride) {
2623 _blocks_to_claim[i].modify(n, wt, true /* force */);
2624 }
2625 }
2626
2627 HeapWord* CFLS_LAB::alloc(size_t word_sz) {
2628 FreeChunk* res;
2629 assert(word_sz == _cfls->adjustObjectSize(word_sz), "Error");
2630 if (word_sz >= CompactibleFreeListSpace::IndexSetSize) {
2631 // This locking manages sync with other large object allocations.
2632 MutexLockerEx x(_cfls->parDictionaryAllocLock(),
2633 Mutex::_no_safepoint_check_flag);
2634 res = _cfls->getChunkFromDictionaryExact(word_sz);
2635 if (res == NULL) return NULL;
2636 } else {
2637 AdaptiveFreeList<FreeChunk>* fl = &_indexedFreeList[word_sz];
2638 if (fl->count() == 0) {
2639 // Attempt to refill this local free list.
2640 get_from_global_pool(word_sz, fl);
2641 // If it didn't work, give up.
2642 if (fl->count() == 0) return NULL;
2643 }
2644 res = fl->get_chunk_at_head();
2645 assert(res != NULL, "Why was count non-zero?");
2646 }
2647 res->markNotFree();
2648 assert(!res->is_free(), "shouldn't be marked free");
2649 assert(oop(res)->klass_or_null() == NULL, "should look uninitialized");
2650 // mangle a just allocated object with a distinct pattern.
2651 debug_only(res->mangleAllocated(word_sz));
2652 return (HeapWord*)res;
2653 }
2654
2655 // Get a chunk of blocks of the right size and update related
2656 // book-keeping stats
2657 void CFLS_LAB::get_from_global_pool(size_t word_sz, AdaptiveFreeList<FreeChunk>* fl) {
2658 // Get the #blocks we want to claim
2659 size_t n_blks = (size_t)_blocks_to_claim[word_sz].average();
2660 assert(n_blks > 0, "Error");
2661 assert(ResizeOldPLAB || n_blks == OldPLABSize, "Error");
2662 // In some cases, when the application has a phase change,
2663 // there may be a sudden and sharp shift in the object survival
2664 // profile, and updating the counts at the end of a scavenge
2665 // may not be quick enough, giving rise to large scavenge pauses
2666 // during these phase changes. It is beneficial to detect such
2667 // changes on-the-fly during a scavenge and avoid such a phase-change
2668 // pothole. The following code is a heuristic attempt to do that.
2669 // It is protected by a product flag until we have gained
2670 // enough experience with this heuristic and fine-tuned its behaviour.
2671 // WARNING: This might increase fragmentation if we overreact to
2672 // small spikes, so some kind of historical smoothing based on
2673 // previous experience with the greater reactivity might be useful.
2674 // Lacking sufficient experience, CMSOldPLABResizeQuicker is disabled by
2675 // default.
2676 if (ResizeOldPLAB && CMSOldPLABResizeQuicker) {
2677 size_t multiple = _num_blocks[word_sz]/(CMSOldPLABToleranceFactor*CMSOldPLABNumRefills*n_blks);
2678 n_blks += CMSOldPLABReactivityFactor*multiple*n_blks;
2679 n_blks = MIN2(n_blks, CMSOldPLABMax);
2680 }
2681 assert(n_blks > 0, "Error");
2682 _cfls->par_get_chunk_of_blocks(word_sz, n_blks, fl);
2683 // Update stats table entry for this block size
2684 _num_blocks[word_sz] += fl->count();
2685 }
2686
2687 void CFLS_LAB::compute_desired_plab_size() {
2688 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2689 i < CompactibleFreeListSpace::IndexSetSize;
2690 i += CompactibleFreeListSpace::IndexSetStride) {
2691 assert((_global_num_workers[i] == 0) == (_global_num_blocks[i] == 0),
2692 "Counter inconsistency");
2693 if (_global_num_workers[i] > 0) {
2694 // Need to smooth wrt historical average
2695 if (ResizeOldPLAB) {
2696 _blocks_to_claim[i].sample(
2697 MAX2((size_t)CMSOldPLABMin,
2698 MIN2((size_t)CMSOldPLABMax,
2699 _global_num_blocks[i]/(_global_num_workers[i]*CMSOldPLABNumRefills))));
2700 }
2701 // Reset counters for next round
2702 _global_num_workers[i] = 0;
2703 _global_num_blocks[i] = 0;
2704 if (PrintOldPLAB) {
2705 gclog_or_tty->print_cr("[" SIZE_FORMAT "]: " SIZE_FORMAT, i, (size_t)_blocks_to_claim[i].average());
2706 }
2707 }
2708 }
2709 }
2710
2711 // If this is changed in the future to allow parallel
2712 // access, one would need to take the FL locks and,
2713 // depending on how it is used, stagger access from
2714 // parallel threads to reduce contention.
2715 void CFLS_LAB::retire(int tid) {
2716 // We run this single threaded with the world stopped;
2717 // so no need for locks and such.
2718 NOT_PRODUCT(Thread* t = Thread::current();)
2719 assert(Thread::current()->is_VM_thread(), "Error");
2720 for (size_t i = CompactibleFreeListSpace::IndexSetStart;
2721 i < CompactibleFreeListSpace::IndexSetSize;
2722 i += CompactibleFreeListSpace::IndexSetStride) {
2723 assert(_num_blocks[i] >= (size_t)_indexedFreeList[i].count(),
2724 "Can't retire more than what we obtained");
2725 if (_num_blocks[i] > 0) {
2726 size_t num_retire = _indexedFreeList[i].count();
2727 assert(_num_blocks[i] > num_retire, "Should have used at least one");
2728 {
2729 // MutexLockerEx x(_cfls->_indexedFreeListParLocks[i],
2730 // Mutex::_no_safepoint_check_flag);
2731
2732 // Update globals stats for num_blocks used
2733 _global_num_blocks[i] += (_num_blocks[i] - num_retire);
2734 _global_num_workers[i]++;
2735 assert(_global_num_workers[i] <= ParallelGCThreads, "Too big");
2736 if (num_retire > 0) {
2737 _cfls->_indexedFreeList[i].prepend(&_indexedFreeList[i]);
2738 // Reset this list.
2739 _indexedFreeList[i] = AdaptiveFreeList<FreeChunk>();
2740 _indexedFreeList[i].set_size(i);
2741 }
2742 }
2743 if (PrintOldPLAB) {
2744 gclog_or_tty->print_cr("%d[" SIZE_FORMAT "]: " SIZE_FORMAT "/" SIZE_FORMAT "/" SIZE_FORMAT,
2745 tid, i, num_retire, _num_blocks[i], (size_t)_blocks_to_claim[i].average());
2746 }
2747 // Reset stats for next round
2748 _num_blocks[i] = 0;
2749 }
2750 }
2751 }
2752
2753 // Used by par_get_chunk_of_blocks() for the chunks from the
2754 // indexed_free_lists. Looks for a chunk with size that is a multiple
2755 // of "word_sz" and if found, splits it into "word_sz" chunks and add
2756 // to the free list "fl". "n" is the maximum number of chunks to
2757 // be added to "fl".
2758 bool CompactibleFreeListSpace:: par_get_chunk_of_blocks_IFL(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2759
2760 // We'll try all multiples of word_sz in the indexed set, starting with
2761 // word_sz itself and, if CMSSplitIndexedFreeListBlocks, try larger multiples,
2762 // then try getting a big chunk and splitting it.
2763 {
2764 bool found;
2765 int k;
2766 size_t cur_sz;
2767 for (k = 1, cur_sz = k * word_sz, found = false;
2768 (cur_sz < CompactibleFreeListSpace::IndexSetSize) &&
2769 (CMSSplitIndexedFreeListBlocks || k <= 1);
2770 k++, cur_sz = k * word_sz) {
2771 AdaptiveFreeList<FreeChunk> fl_for_cur_sz; // Empty.
2772 fl_for_cur_sz.set_size(cur_sz);
2773 {
2774 MutexLockerEx x(_indexedFreeListParLocks[cur_sz],
2775 Mutex::_no_safepoint_check_flag);
2776 AdaptiveFreeList<FreeChunk>* gfl = &_indexedFreeList[cur_sz];
2777 if (gfl->count() != 0) {
2778 // nn is the number of chunks of size cur_sz that
2779 // we'd need to split k-ways each, in order to create
2780 // "n" chunks of size word_sz each.
2781 const size_t nn = MAX2(n/k, (size_t)1);
2782 gfl->getFirstNChunksFromList(nn, &fl_for_cur_sz);
2783 found = true;
2784 if (k > 1) {
2785 // Update split death stats for the cur_sz-size blocks list:
2786 // we increment the split death count by the number of blocks
2787 // we just took from the cur_sz-size blocks list and which
2788 // we will be splitting below.
2789 ssize_t deaths = gfl->split_deaths() +
2790 fl_for_cur_sz.count();
2791 gfl->set_split_deaths(deaths);
2792 }
2793 }
2794 }
2795 // Now transfer fl_for_cur_sz to fl. Common case, we hope, is k = 1.
2796 if (found) {
2797 if (k == 1) {
2798 fl->prepend(&fl_for_cur_sz);
2799 } else {
2800 // Divide each block on fl_for_cur_sz up k ways.
2801 FreeChunk* fc;
2802 while ((fc = fl_for_cur_sz.get_chunk_at_head()) != NULL) {
2803 // Must do this in reverse order, so that anybody attempting to
2804 // access the main chunk sees it as a single free block until we
2805 // change it.
2806 size_t fc_size = fc->size();
2807 assert(fc->is_free(), "Error");
2808 for (int i = k-1; i >= 0; i--) {
2809 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz);
2810 assert((i != 0) ||
2811 ((fc == ffc) && ffc->is_free() &&
2812 (ffc->size() == k*word_sz) && (fc_size == word_sz)),
2813 "Counting error");
2814 ffc->set_size(word_sz);
2815 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2816 ffc->link_next(NULL);
2817 // Above must occur before BOT is updated below.
2818 OrderAccess::storestore();
2819 // splitting from the right, fc_size == i * word_sz
2820 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */);
2821 fc_size -= word_sz;
2822 assert(fc_size == i*word_sz, "Error");
2823 _bt.verify_not_unallocated((HeapWord*)ffc, word_sz);
2824 _bt.verify_single_block((HeapWord*)fc, fc_size);
2825 _bt.verify_single_block((HeapWord*)ffc, word_sz);
2826 // Push this on "fl".
2827 fl->return_chunk_at_head(ffc);
2828 }
2829 // TRAP
2830 assert(fl->tail()->next() == NULL, "List invariant.");
2831 }
2832 }
2833 // Update birth stats for this block size.
2834 size_t num = fl->count();
2835 MutexLockerEx x(_indexedFreeListParLocks[word_sz],
2836 Mutex::_no_safepoint_check_flag);
2837 ssize_t births = _indexedFreeList[word_sz].split_births() + num;
2838 _indexedFreeList[word_sz].set_split_births(births);
2839 return true;
2840 }
2841 }
2842 return found;
2843 }
2844 }
2845
2846 FreeChunk* CompactibleFreeListSpace::get_n_way_chunk_to_split(size_t word_sz, size_t n) {
2847
2848 FreeChunk* fc = NULL;
2849 FreeChunk* rem_fc = NULL;
2850 size_t rem;
2851 {
2852 MutexLockerEx x(parDictionaryAllocLock(),
2853 Mutex::_no_safepoint_check_flag);
2854 while (n > 0) {
2855 fc = dictionary()->get_chunk(MAX2(n * word_sz, _dictionary->min_size()),
2856 FreeBlockDictionary<FreeChunk>::atLeast);
2857 if (fc != NULL) {
2858 break;
2859 } else {
2860 n--;
2861 }
2862 }
2863 if (fc == NULL) return NULL;
2864 // Otherwise, split up that block.
2865 assert((ssize_t)n >= 1, "Control point invariant");
2866 assert(fc->is_free(), "Error: should be a free block");
2867 _bt.verify_single_block((HeapWord*)fc, fc->size());
2868 const size_t nn = fc->size() / word_sz;
2869 n = MIN2(nn, n);
2870 assert((ssize_t)n >= 1, "Control point invariant");
2871 rem = fc->size() - n * word_sz;
2872 // If there is a remainder, and it's too small, allocate one fewer.
2873 if (rem > 0 && rem < MinChunkSize) {
2874 n--; rem += word_sz;
2875 }
2876 // Note that at this point we may have n == 0.
2877 assert((ssize_t)n >= 0, "Control point invariant");
2878
2879 // If n is 0, the chunk fc that was found is not large
2880 // enough to leave a viable remainder. We are unable to
2881 // allocate even one block. Return fc to the
2882 // dictionary and return, leaving "fl" empty.
2883 if (n == 0) {
2884 returnChunkToDictionary(fc);
2885 return NULL;
2886 }
2887
2888 _bt.allocated((HeapWord*)fc, fc->size(), true /* reducing */); // update _unallocated_blk
2889 dictionary()->dict_census_update(fc->size(),
2890 true /*split*/,
2891 false /*birth*/);
2892
2893 // First return the remainder, if any.
2894 // Note that we hold the lock until we decide if we're going to give
2895 // back the remainder to the dictionary, since a concurrent allocation
2896 // may otherwise see the heap as empty. (We're willing to take that
2897 // hit if the block is a small block.)
2898 if (rem > 0) {
2899 size_t prefix_size = n * word_sz;
2900 rem_fc = (FreeChunk*)((HeapWord*)fc + prefix_size);
2901 rem_fc->set_size(rem);
2902 rem_fc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2903 rem_fc->link_next(NULL);
2904 // Above must occur before BOT is updated below.
2905 assert((ssize_t)n > 0 && prefix_size > 0 && rem_fc > fc, "Error");
2906 OrderAccess::storestore();
2907 _bt.split_block((HeapWord*)fc, fc->size(), prefix_size);
2908 assert(fc->is_free(), "Error");
2909 fc->set_size(prefix_size);
2910 if (rem >= IndexSetSize) {
2911 returnChunkToDictionary(rem_fc);
2912 dictionary()->dict_census_update(rem, true /*split*/, true /*birth*/);
2913 rem_fc = NULL;
2914 }
2915 // Otherwise, return it to the small list below.
2916 }
2917 }
2918 if (rem_fc != NULL) {
2919 MutexLockerEx x(_indexedFreeListParLocks[rem],
2920 Mutex::_no_safepoint_check_flag);
2921 _bt.verify_not_unallocated((HeapWord*)rem_fc, rem_fc->size());
2922 _indexedFreeList[rem].return_chunk_at_head(rem_fc);
2923 smallSplitBirth(rem);
2924 }
2925 assert(n * word_sz == fc->size(),
2926 err_msg("Chunk size " SIZE_FORMAT " is not exactly splittable by "
2927 SIZE_FORMAT " sized chunks of size " SIZE_FORMAT,
2928 fc->size(), n, word_sz));
2929 return fc;
2930 }
2931
2932 void CompactibleFreeListSpace:: par_get_chunk_of_blocks_dictionary(size_t word_sz, size_t targetted_number_of_chunks, AdaptiveFreeList<FreeChunk>* fl) {
2933
2934 FreeChunk* fc = get_n_way_chunk_to_split(word_sz, targetted_number_of_chunks);
2935
2936 if (fc == NULL) {
2937 return;
2938 }
2939
2940 size_t n = fc->size() / word_sz;
2941
2942 assert((ssize_t)n > 0, "Consistency");
2943 // Now do the splitting up.
2944 // Must do this in reverse order, so that anybody attempting to
2945 // access the main chunk sees it as a single free block until we
2946 // change it.
2947 size_t fc_size = n * word_sz;
2948 // All but first chunk in this loop
2949 for (ssize_t i = n-1; i > 0; i--) {
2950 FreeChunk* ffc = (FreeChunk*)((HeapWord*)fc + i * word_sz);
2951 ffc->set_size(word_sz);
2952 ffc->link_prev(NULL); // Mark as a free block for other (parallel) GC threads.
2953 ffc->link_next(NULL);
2954 // Above must occur before BOT is updated below.
2955 OrderAccess::storestore();
2956 // splitting from the right, fc_size == (n - i + 1) * wordsize
2957 _bt.mark_block((HeapWord*)ffc, word_sz, true /* reducing */);
2958 fc_size -= word_sz;
2959 _bt.verify_not_unallocated((HeapWord*)ffc, ffc->size());
2960 _bt.verify_single_block((HeapWord*)ffc, ffc->size());
2961 _bt.verify_single_block((HeapWord*)fc, fc_size);
2962 // Push this on "fl".
2963 fl->return_chunk_at_head(ffc);
2964 }
2965 // First chunk
2966 assert(fc->is_free() && fc->size() == n*word_sz, "Error: should still be a free block");
2967 // The blocks above should show their new sizes before the first block below
2968 fc->set_size(word_sz);
2969 fc->link_prev(NULL); // idempotent wrt free-ness, see assert above
2970 fc->link_next(NULL);
2971 _bt.verify_not_unallocated((HeapWord*)fc, fc->size());
2972 _bt.verify_single_block((HeapWord*)fc, fc->size());
2973 fl->return_chunk_at_head(fc);
2974
2975 assert((ssize_t)n > 0 && (ssize_t)n == fl->count(), "Incorrect number of blocks");
2976 {
2977 // Update the stats for this block size.
2978 MutexLockerEx x(_indexedFreeListParLocks[word_sz],
2979 Mutex::_no_safepoint_check_flag);
2980 const ssize_t births = _indexedFreeList[word_sz].split_births() + n;
2981 _indexedFreeList[word_sz].set_split_births(births);
2982 // ssize_t new_surplus = _indexedFreeList[word_sz].surplus() + n;
2983 // _indexedFreeList[word_sz].set_surplus(new_surplus);
2984 }
2985
2986 // TRAP
2987 assert(fl->tail()->next() == NULL, "List invariant.");
2988 }
2989
2990 void CompactibleFreeListSpace:: par_get_chunk_of_blocks(size_t word_sz, size_t n, AdaptiveFreeList<FreeChunk>* fl) {
2991 assert(fl->count() == 0, "Precondition.");
2992 assert(word_sz < CompactibleFreeListSpace::IndexSetSize,
2993 "Precondition");
2994
2995 if (par_get_chunk_of_blocks_IFL(word_sz, n, fl)) {
2996 // Got it
2997 return;
2998 }
2999
3000 // Otherwise, we'll split a block from the dictionary.
3001 par_get_chunk_of_blocks_dictionary(word_sz, n, fl);
3002 }
3003
3004 // Set up the space's par_seq_tasks structure for work claiming
3005 // for parallel rescan. See CMSParRemarkTask where this is currently used.
3006 // XXX Need to suitably abstract and generalize this and the next
3007 // method into one.
3008 void
3009 CompactibleFreeListSpace::
3010 initialize_sequential_subtasks_for_rescan(int n_threads) {
3011 // The "size" of each task is fixed according to rescan_task_size.
3012 assert(n_threads > 0, "Unexpected n_threads argument");
3013 const size_t task_size = rescan_task_size();
3014 size_t n_tasks = (used_region().word_size() + task_size - 1)/task_size;
3015 assert((n_tasks == 0) == used_region().is_empty(), "n_tasks incorrect");
3016 assert(n_tasks == 0 ||
3017 ((used_region().start() + (n_tasks - 1)*task_size < used_region().end()) &&
3018 (used_region().start() + n_tasks*task_size >= used_region().end())),
3019 "n_tasks calculation incorrect");
3020 SequentialSubTasksDone* pst = conc_par_seq_tasks();
3021 assert(!pst->valid(), "Clobbering existing data?");
3022 // Sets the condition for completion of the subtask (how many threads
3023 // need to finish in order to be done).
3024 pst->set_n_threads(n_threads);
3025 pst->set_n_tasks((int)n_tasks);
3026 }
3027
3028 // Set up the space's par_seq_tasks structure for work claiming
3029 // for parallel concurrent marking. See CMSConcMarkTask where this is currently used.
3030 void
3031 CompactibleFreeListSpace::
3032 initialize_sequential_subtasks_for_marking(int n_threads,
3033 HeapWord* low) {
3034 // The "size" of each task is fixed according to rescan_task_size.
3035 assert(n_threads > 0, "Unexpected n_threads argument");
3036 const size_t task_size = marking_task_size();
3037 assert(task_size > CardTableModRefBS::card_size_in_words &&
3038 (task_size % CardTableModRefBS::card_size_in_words == 0),
3039 "Otherwise arithmetic below would be incorrect");
3040 MemRegion span = _gen->reserved();
3041 if (low != NULL) {
3042 if (span.contains(low)) {
3043 // Align low down to a card boundary so that
3044 // we can use block_offset_careful() on span boundaries.
3045 HeapWord* aligned_low = (HeapWord*)align_size_down((uintptr_t)low,
3046 CardTableModRefBS::card_size);
3047 // Clip span prefix at aligned_low
3048 span = span.intersection(MemRegion(aligned_low, span.end()));
3049 } else if (low > span.end()) {
3050 span = MemRegion(low, low); // Null region
3051 } // else use entire span
3052 }
3053 assert(span.is_empty() ||
3054 ((uintptr_t)span.start() % CardTableModRefBS::card_size == 0),
3055 "span should start at a card boundary");
3056 size_t n_tasks = (span.word_size() + task_size - 1)/task_size;
3057 assert((n_tasks == 0) == span.is_empty(), "Inconsistency");
3058 assert(n_tasks == 0 ||
3059 ((span.start() + (n_tasks - 1)*task_size < span.end()) &&
3060 (span.start() + n_tasks*task_size >= span.end())),
3061 "n_tasks calculation incorrect");
3062 SequentialSubTasksDone* pst = conc_par_seq_tasks();
3063 assert(!pst->valid(), "Clobbering existing data?");
3064 // Sets the condition for completion of the subtask (how many threads
3065 // need to finish in order to be done).
3066 pst->set_n_threads(n_threads);
3067 pst->set_n_tasks((int)n_tasks);
3068 }