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