freeList.cpp revision 3718:b9a9ed0f8eeb
1/* 2 * Copyright (c) 2001, 2012, 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 "memory/freeBlockDictionary.hpp" 27#include "memory/freeList.hpp" 28#include "memory/sharedHeap.hpp" 29#include "runtime/globals.hpp" 30#include "runtime/mutex.hpp" 31#include "runtime/vmThread.hpp" 32 33#ifndef SERIALGC 34#include "gc_implementation/concurrentMarkSweep/freeChunk.hpp" 35#endif // SERIALGC 36 37// Free list. A FreeList is used to access a linked list of chunks 38// of space in the heap. The head and tail are maintained so that 39// items can be (as in the current implementation) added at the 40// at the tail of the list and removed from the head of the list to 41// maintain a FIFO queue. 42 43template <class Chunk> 44FreeList<Chunk>::FreeList() : 45 _head(NULL), _tail(NULL) 46#ifdef ASSERT 47 , _protecting_lock(NULL) 48#endif 49{ 50 _size = 0; 51 _count = 0; 52 _hint = 0; 53 init_statistics(); 54} 55 56template <class Chunk> 57FreeList<Chunk>::FreeList(Chunk* fc) : 58 _head(fc), _tail(fc) 59#ifdef ASSERT 60 , _protecting_lock(NULL) 61#endif 62{ 63 _size = fc->size(); 64 _count = 1; 65 _hint = 0; 66 init_statistics(); 67#ifndef PRODUCT 68 _allocation_stats.set_returned_bytes(size() * HeapWordSize); 69#endif 70} 71 72template <class Chunk> 73void FreeList<Chunk>::reset(size_t hint) { 74 set_count(0); 75 set_head(NULL); 76 set_tail(NULL); 77 set_hint(hint); 78} 79 80template <class Chunk> 81void FreeList<Chunk>::init_statistics(bool split_birth) { 82 _allocation_stats.initialize(split_birth); 83} 84 85template <class Chunk> 86Chunk* FreeList<Chunk>::get_chunk_at_head() { 87 assert_proper_lock_protection(); 88 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 89 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 90 Chunk* fc = head(); 91 if (fc != NULL) { 92 Chunk* nextFC = fc->next(); 93 if (nextFC != NULL) { 94 // The chunk fc being removed has a "next". Set the "next" to the 95 // "prev" of fc. 96 nextFC->link_prev(NULL); 97 } else { // removed tail of list 98 link_tail(NULL); 99 } 100 link_head(nextFC); 101 decrement_count(); 102 } 103 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 104 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 105 return fc; 106} 107 108 109template <class Chunk> 110void FreeList<Chunk>::getFirstNChunksFromList(size_t n, FreeList<Chunk>* fl) { 111 assert_proper_lock_protection(); 112 assert(fl->count() == 0, "Precondition"); 113 if (count() > 0) { 114 int k = 1; 115 fl->set_head(head()); n--; 116 Chunk* tl = head(); 117 while (tl->next() != NULL && n > 0) { 118 tl = tl->next(); n--; k++; 119 } 120 assert(tl != NULL, "Loop Inv."); 121 122 // First, fix up the list we took from. 123 Chunk* new_head = tl->next(); 124 set_head(new_head); 125 set_count(count() - k); 126 if (new_head == NULL) { 127 set_tail(NULL); 128 } else { 129 new_head->link_prev(NULL); 130 } 131 // Now we can fix up the tail. 132 tl->link_next(NULL); 133 // And return the result. 134 fl->set_tail(tl); 135 fl->set_count(k); 136 } 137} 138 139// Remove this chunk from the list 140template <class Chunk> 141void FreeList<Chunk>::remove_chunk(Chunk*fc) { 142 assert_proper_lock_protection(); 143 assert(head() != NULL, "Remove from empty list"); 144 assert(fc != NULL, "Remove a NULL chunk"); 145 assert(size() == fc->size(), "Wrong list"); 146 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 147 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 148 149 Chunk* prevFC = fc->prev(); 150 Chunk* nextFC = fc->next(); 151 if (nextFC != NULL) { 152 // The chunk fc being removed has a "next". Set the "next" to the 153 // "prev" of fc. 154 nextFC->link_prev(prevFC); 155 } else { // removed tail of list 156 link_tail(prevFC); 157 } 158 if (prevFC == NULL) { // removed head of list 159 link_head(nextFC); 160 assert(nextFC == NULL || nextFC->prev() == NULL, 161 "Prev of head should be NULL"); 162 } else { 163 prevFC->link_next(nextFC); 164 assert(tail() != prevFC || prevFC->next() == NULL, 165 "Next of tail should be NULL"); 166 } 167 decrement_count(); 168 assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0, 169 "H/T/C Inconsistency"); 170 // clear next and prev fields of fc, debug only 171 NOT_PRODUCT( 172 fc->link_prev(NULL); 173 fc->link_next(NULL); 174 ) 175 assert(fc->is_free(), "Should still be a free chunk"); 176 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 177 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 178 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 179 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 180} 181 182// Add this chunk at the head of the list. 183template <class Chunk> 184void FreeList<Chunk>::return_chunk_at_head(Chunk* chunk, bool record_return) { 185 assert_proper_lock_protection(); 186 assert(chunk != NULL, "insert a NULL chunk"); 187 assert(size() == chunk->size(), "Wrong size"); 188 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 189 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 190 191 Chunk* oldHead = head(); 192 assert(chunk != oldHead, "double insertion"); 193 chunk->link_after(oldHead); 194 link_head(chunk); 195 if (oldHead == NULL) { // only chunk in list 196 assert(tail() == NULL, "inconsistent FreeList"); 197 link_tail(chunk); 198 } 199 increment_count(); // of # of chunks in list 200 DEBUG_ONLY( 201 if (record_return) { 202 increment_returned_bytes_by(size()*HeapWordSize); 203 } 204 ) 205 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 206 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 207 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 208 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 209} 210 211template <class Chunk> 212void FreeList<Chunk>::return_chunk_at_head(Chunk* chunk) { 213 assert_proper_lock_protection(); 214 return_chunk_at_head(chunk, true); 215} 216 217// Add this chunk at the tail of the list. 218template <class Chunk> 219void FreeList<Chunk>::return_chunk_at_tail(Chunk* chunk, bool record_return) { 220 assert_proper_lock_protection(); 221 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 222 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 223 assert(chunk != NULL, "insert a NULL chunk"); 224 assert(size() == chunk->size(), "wrong size"); 225 226 Chunk* oldTail = tail(); 227 assert(chunk != oldTail, "double insertion"); 228 if (oldTail != NULL) { 229 oldTail->link_after(chunk); 230 } else { // only chunk in list 231 assert(head() == NULL, "inconsistent FreeList"); 232 link_head(chunk); 233 } 234 link_tail(chunk); 235 increment_count(); // of # of chunks in list 236 DEBUG_ONLY( 237 if (record_return) { 238 increment_returned_bytes_by(size()*HeapWordSize); 239 } 240 ) 241 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 242 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 243 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 244 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 245} 246 247template <class Chunk> 248void FreeList<Chunk>::return_chunk_at_tail(Chunk* chunk) { 249 return_chunk_at_tail(chunk, true); 250} 251 252template <class Chunk> 253void FreeList<Chunk>::prepend(FreeList<Chunk>* fl) { 254 assert_proper_lock_protection(); 255 if (fl->count() > 0) { 256 if (count() == 0) { 257 set_head(fl->head()); 258 set_tail(fl->tail()); 259 set_count(fl->count()); 260 } else { 261 // Both are non-empty. 262 Chunk* fl_tail = fl->tail(); 263 Chunk* this_head = head(); 264 assert(fl_tail->next() == NULL, "Well-formedness of fl"); 265 fl_tail->link_next(this_head); 266 this_head->link_prev(fl_tail); 267 set_head(fl->head()); 268 set_count(count() + fl->count()); 269 } 270 fl->set_head(NULL); 271 fl->set_tail(NULL); 272 fl->set_count(0); 273 } 274} 275 276// verify_chunk_in_free_list() is used to verify that an item is in this free list. 277// It is used as a debugging aid. 278template <class Chunk> 279bool FreeList<Chunk>::verify_chunk_in_free_list(Chunk* fc) const { 280 // This is an internal consistency check, not part of the check that the 281 // chunk is in the free lists. 282 guarantee(fc->size() == size(), "Wrong list is being searched"); 283 Chunk* curFC = head(); 284 while (curFC) { 285 // This is an internal consistency check. 286 guarantee(size() == curFC->size(), "Chunk is in wrong list."); 287 if (fc == curFC) { 288 return true; 289 } 290 curFC = curFC->next(); 291 } 292 return false; 293} 294 295#ifndef PRODUCT 296template <class Chunk> 297void FreeList<Chunk>::verify_stats() const { 298 // The +1 of the LH comparand is to allow some "looseness" in 299 // checking: we usually call this interface when adding a block 300 // and we'll subsequently update the stats; we cannot update the 301 // stats beforehand because in the case of the large-block BT 302 // dictionary for example, this might be the first block and 303 // in that case there would be no place that we could record 304 // the stats (which are kept in the block itself). 305 assert((_allocation_stats.prev_sweep() + _allocation_stats.split_births() 306 + _allocation_stats.coal_births() + 1) // Total Production Stock + 1 307 >= (_allocation_stats.split_deaths() + _allocation_stats.coal_deaths() 308 + (ssize_t)count()), // Total Current Stock + depletion 309 err_msg("FreeList " PTR_FORMAT " of size " SIZE_FORMAT 310 " violates Conservation Principle: " 311 "prev_sweep(" SIZE_FORMAT ")" 312 " + split_births(" SIZE_FORMAT ")" 313 " + coal_births(" SIZE_FORMAT ") + 1 >= " 314 " split_deaths(" SIZE_FORMAT ")" 315 " coal_deaths(" SIZE_FORMAT ")" 316 " + count(" SSIZE_FORMAT ")", 317 this, _size, _allocation_stats.prev_sweep(), _allocation_stats.split_births(), 318 _allocation_stats.split_births(), _allocation_stats.split_deaths(), 319 _allocation_stats.coal_deaths(), count())); 320} 321 322template <class Chunk> 323void FreeList<Chunk>::assert_proper_lock_protection_work() const { 324 assert(_protecting_lock != NULL, "Don't call this directly"); 325 assert(ParallelGCThreads > 0, "Don't call this directly"); 326 Thread* thr = Thread::current(); 327 if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { 328 // assert that we are holding the freelist lock 329 } else if (thr->is_GC_task_thread()) { 330 assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); 331 } else if (thr->is_Java_thread()) { 332 assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); 333 } else { 334 ShouldNotReachHere(); // unaccounted thread type? 335 } 336} 337#endif 338 339// Print the "label line" for free list stats. 340template <class Chunk> 341void FreeList<Chunk>::print_labels_on(outputStream* st, const char* c) { 342 st->print("%16s\t", c); 343 st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" 344 "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", 345 "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", 346 "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); 347} 348 349// Print the AllocationStats for the given free list. If the second argument 350// to the call is a non-null string, it is printed in the first column; 351// otherwise, if the argument is null (the default), then the size of the 352// (free list) block is printed in the first column. 353template <class Chunk> 354void FreeList<Chunk>::print_on(outputStream* st, const char* c) const { 355 if (c != NULL) { 356 st->print("%16s", c); 357 } else { 358 st->print(SIZE_FORMAT_W(16), size()); 359 } 360 st->print("\t" 361 SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" 362 SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\t" SSIZE_FORMAT_W(14) "\n", 363 bfr_surp(), surplus(), desired(), prev_sweep(), before_sweep(), 364 count(), coal_births(), coal_deaths(), split_births(), split_deaths()); 365} 366 367#ifndef SERIALGC 368// Needs to be after the definitions have been seen. 369template class FreeList<FreeChunk>; 370#endif // SERIALGC 371