1/* 2 * Copyright (c) 2001, 2017, 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/shared/collectedHeap.hpp" 27#include "memory/freeList.hpp" 28#include "memory/metachunk.hpp" 29#include "runtime/globals.hpp" 30#include "runtime/mutex.hpp" 31#include "runtime/vmThread.hpp" 32#include "utilities/macros.hpp" 33#if INCLUDE_ALL_GCS 34#include "gc/cms/freeChunk.hpp" 35#endif // INCLUDE_ALL_GCS 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} 53 54template <class Chunk> 55void FreeList<Chunk>::link_head(Chunk* v) { 56 assert_proper_lock_protection(); 57 set_head(v); 58 // If this method is not used (just set the head instead), 59 // this check can be avoided. 60 if (v != NULL) { 61 v->link_prev(NULL); 62 } 63} 64 65 66 67template <class Chunk> 68void FreeList<Chunk>::reset() { 69 // Don't set the _size to 0 because this method is 70 // used with a existing list that has a size but which has 71 // been emptied. 72 // Don't clear the _protecting_lock of an existing list. 73 set_count(0); 74 set_head(NULL); 75 set_tail(NULL); 76} 77 78template <class Chunk> 79void FreeList<Chunk>::initialize() { 80#ifdef ASSERT 81 // Needed early because it might be checked in other initializing code. 82 set_protecting_lock(NULL); 83#endif 84 reset(); 85 set_size(0); 86} 87 88template <class Chunk_t> 89Chunk_t* FreeList<Chunk_t>::get_chunk_at_head() { 90 assert_proper_lock_protection(); 91 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 92 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 93 Chunk_t* fc = head(); 94 if (fc != NULL) { 95 Chunk_t* nextFC = fc->next(); 96 if (nextFC != NULL) { 97 // The chunk fc being removed has a "next". Set the "next" to the 98 // "prev" of fc. 99 nextFC->link_prev(NULL); 100 } else { // removed tail of list 101 link_tail(NULL); 102 } 103 link_head(nextFC); 104 decrement_count(); 105 } 106 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 107 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 108 return fc; 109} 110 111 112template <class Chunk> 113void FreeList<Chunk>::getFirstNChunksFromList(size_t n, FreeList<Chunk>* fl) { 114 assert_proper_lock_protection(); 115 assert(fl->count() == 0, "Precondition"); 116 if (count() > 0) { 117 int k = 1; 118 fl->set_head(head()); n--; 119 Chunk* tl = head(); 120 while (tl->next() != NULL && n > 0) { 121 tl = tl->next(); n--; k++; 122 } 123 assert(tl != NULL, "Loop Inv."); 124 125 // First, fix up the list we took from. 126 Chunk* new_head = tl->next(); 127 set_head(new_head); 128 set_count(count() - k); 129 if (new_head == NULL) { 130 set_tail(NULL); 131 } else { 132 new_head->link_prev(NULL); 133 } 134 // Now we can fix up the tail. 135 tl->link_next(NULL); 136 // And return the result. 137 fl->set_tail(tl); 138 fl->set_count(k); 139 } 140} 141 142// Remove this chunk from the list 143template <class Chunk> 144void FreeList<Chunk>::remove_chunk(Chunk*fc) { 145 assert_proper_lock_protection(); 146 assert(head() != NULL, "Remove from empty list"); 147 assert(fc != NULL, "Remove a NULL chunk"); 148 assert(size() == fc->size(), "Wrong list"); 149 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 150 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 151 152 Chunk* prevFC = fc->prev(); 153 Chunk* nextFC = fc->next(); 154 if (nextFC != NULL) { 155 // The chunk fc being removed has a "next". Set the "next" to the 156 // "prev" of fc. 157 nextFC->link_prev(prevFC); 158 } else { // removed tail of list 159 link_tail(prevFC); 160 } 161 if (prevFC == NULL) { // removed head of list 162 link_head(nextFC); 163 assert(nextFC == NULL || nextFC->prev() == NULL, 164 "Prev of head should be NULL"); 165 } else { 166 prevFC->link_next(nextFC); 167 assert(tail() != prevFC || prevFC->next() == NULL, 168 "Next of tail should be NULL"); 169 } 170 decrement_count(); 171 assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0, 172 "H/T/C Inconsistency"); 173 // clear next and prev fields of fc, debug only 174 NOT_PRODUCT( 175 fc->link_prev(NULL); 176 fc->link_next(NULL); 177 ) 178 assert(fc->is_free(), "Should still be a free chunk"); 179 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 180 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 181 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 182 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 183} 184 185// Add this chunk at the head of the list. 186template <class Chunk> 187void FreeList<Chunk>::return_chunk_at_head(Chunk* chunk, bool record_return) { 188 assert_proper_lock_protection(); 189 assert(chunk != NULL, "insert a NULL chunk"); 190 assert(size() == chunk->size(), "Wrong size"); 191 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 192 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 193 194 Chunk* oldHead = head(); 195 assert(chunk != oldHead, "double insertion"); 196 chunk->link_after(oldHead); 197 link_head(chunk); 198 if (oldHead == NULL) { // only chunk in list 199 assert(tail() == NULL, "inconsistent FreeList"); 200 link_tail(chunk); 201 } 202 increment_count(); // of # of chunks in list 203 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 204 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 205 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 206 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 207} 208 209template <class Chunk> 210void FreeList<Chunk>::return_chunk_at_head(Chunk* chunk) { 211 assert_proper_lock_protection(); 212 return_chunk_at_head(chunk, true); 213} 214 215// Add this chunk at the tail of the list. 216template <class Chunk> 217void FreeList<Chunk>::return_chunk_at_tail(Chunk* chunk, bool record_return) { 218 assert_proper_lock_protection(); 219 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 220 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 221 assert(chunk != NULL, "insert a NULL chunk"); 222 assert(size() == chunk->size(), "wrong size"); 223 224 Chunk* oldTail = tail(); 225 assert(chunk != oldTail, "double insertion"); 226 if (oldTail != NULL) { 227 oldTail->link_after(chunk); 228 } else { // only chunk in list 229 assert(head() == NULL, "inconsistent FreeList"); 230 link_head(chunk); 231 } 232 link_tail(chunk); 233 increment_count(); // of # of chunks in list 234 assert(head() == NULL || head()->prev() == NULL, "list invariant"); 235 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); 236 assert(head() == NULL || head()->size() == size(), "wrong item on list"); 237 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); 238} 239 240template <class Chunk> 241void FreeList<Chunk>::return_chunk_at_tail(Chunk* chunk) { 242 return_chunk_at_tail(chunk, true); 243} 244 245template <class Chunk> 246void FreeList<Chunk>::prepend(FreeList<Chunk>* fl) { 247 assert_proper_lock_protection(); 248 if (fl->count() > 0) { 249 if (count() == 0) { 250 set_head(fl->head()); 251 set_tail(fl->tail()); 252 set_count(fl->count()); 253 } else { 254 // Both are non-empty. 255 Chunk* fl_tail = fl->tail(); 256 Chunk* this_head = head(); 257 assert(fl_tail->next() == NULL, "Well-formedness of fl"); 258 fl_tail->link_next(this_head); 259 this_head->link_prev(fl_tail); 260 set_head(fl->head()); 261 set_count(count() + fl->count()); 262 } 263 fl->set_head(NULL); 264 fl->set_tail(NULL); 265 fl->set_count(0); 266 } 267} 268 269// verify_chunk_in_free_lists() is used to verify that an item is in this free list. 270// It is used as a debugging aid. 271template <class Chunk> 272bool FreeList<Chunk>::verify_chunk_in_free_list(Chunk* fc) const { 273 // This is an internal consistency check, not part of the check that the 274 // chunk is in the free lists. 275 guarantee(fc->size() == size(), "Wrong list is being searched"); 276 Chunk* curFC = head(); 277 while (curFC) { 278 // This is an internal consistency check. 279 guarantee(size() == curFC->size(), "Chunk is in wrong list."); 280 if (fc == curFC) { 281 return true; 282 } 283 curFC = curFC->next(); 284 } 285 return false; 286} 287 288#ifdef ASSERT 289template <class Chunk> 290void FreeList<Chunk>::assert_proper_lock_protection_work() const { 291 // Nothing to do if the list has no assigned protecting lock 292 if (protecting_lock() == NULL) { 293 return; 294 } 295 296 Thread* thr = Thread::current(); 297 if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) { 298 // assert that we are holding the freelist lock 299 } else if (thr->is_GC_task_thread()) { 300 assert(protecting_lock()->owned_by_self(), "FreeList RACE DETECTED"); 301 } else if (thr->is_Java_thread()) { 302 assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing"); 303 } else { 304 ShouldNotReachHere(); // unaccounted thread type? 305 } 306} 307#endif 308 309// Print the "label line" for free list stats. 310template <class Chunk> 311void FreeList<Chunk>::print_labels_on(outputStream* st, const char* c) { 312 st->print("%16s\t", c); 313 st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" 314 "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", 315 "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", 316 "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); 317} 318 319// Print the AllocationStats for the given free list. If the second argument 320// to the call is a non-null string, it is printed in the first column; 321// otherwise, if the argument is null (the default), then the size of the 322// (free list) block is printed in the first column. 323template <class Chunk_t> 324void FreeList<Chunk_t>::print_on(outputStream* st, const char* c) const { 325 if (c != NULL) { 326 st->print("%16s", c); 327 } else { 328 st->print(SIZE_FORMAT_W(16), size()); 329 } 330} 331 332template class FreeList<Metablock>; 333template class FreeList<Metachunk>; 334#if INCLUDE_ALL_GCS 335template class FreeList<FreeChunk>; 336#endif // INCLUDE_ALL_GCS 337