annotate src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp @ 0:a61af66fc99e

Initial load
author duke
date Sat, 01 Dec 2007 00:00:00 +0000
parents
children 6432c3bb6240
rev   line source
duke@0 1 /*
duke@0 2 * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved.
duke@0 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
duke@0 4 *
duke@0 5 * This code is free software; you can redistribute it and/or modify it
duke@0 6 * under the terms of the GNU General Public License version 2 only, as
duke@0 7 * published by the Free Software Foundation.
duke@0 8 *
duke@0 9 * This code is distributed in the hope that it will be useful, but WITHOUT
duke@0 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
duke@0 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
duke@0 12 * version 2 for more details (a copy is included in the LICENSE file that
duke@0 13 * accompanied this code).
duke@0 14 *
duke@0 15 * You should have received a copy of the GNU General Public License version
duke@0 16 * 2 along with this work; if not, write to the Free Software Foundation,
duke@0 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
duke@0 18 *
duke@0 19 * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
duke@0 20 * CA 95054 USA or visit www.sun.com if you need additional information or
duke@0 21 * have any questions.
duke@0 22 *
duke@0 23 */
duke@0 24
duke@0 25 # include "incls/_precompiled.incl"
duke@0 26 # include "incls/_freeList.cpp.incl"
duke@0 27
duke@0 28 // Free list. A FreeList is used to access a linked list of chunks
duke@0 29 // of space in the heap. The head and tail are maintained so that
duke@0 30 // items can be (as in the current implementation) added at the
duke@0 31 // at the tail of the list and removed from the head of the list to
duke@0 32 // maintain a FIFO queue.
duke@0 33
duke@0 34 FreeList::FreeList() :
duke@0 35 _head(NULL), _tail(NULL)
duke@0 36 #ifdef ASSERT
duke@0 37 , _protecting_lock(NULL)
duke@0 38 #endif
duke@0 39 {
duke@0 40 _size = 0;
duke@0 41 _count = 0;
duke@0 42 _hint = 0;
duke@0 43 init_statistics();
duke@0 44 }
duke@0 45
duke@0 46 FreeList::FreeList(FreeChunk* fc) :
duke@0 47 _head(fc), _tail(fc)
duke@0 48 #ifdef ASSERT
duke@0 49 , _protecting_lock(NULL)
duke@0 50 #endif
duke@0 51 {
duke@0 52 _size = fc->size();
duke@0 53 _count = 1;
duke@0 54 _hint = 0;
duke@0 55 init_statistics();
duke@0 56 #ifndef PRODUCT
duke@0 57 _allocation_stats.set_returnedBytes(size() * HeapWordSize);
duke@0 58 #endif
duke@0 59 }
duke@0 60
duke@0 61 FreeList::FreeList(HeapWord* addr, size_t size) :
duke@0 62 _head((FreeChunk*) addr), _tail((FreeChunk*) addr)
duke@0 63 #ifdef ASSERT
duke@0 64 , _protecting_lock(NULL)
duke@0 65 #endif
duke@0 66 {
duke@0 67 assert(size > sizeof(FreeChunk), "size is too small");
duke@0 68 head()->setSize(size);
duke@0 69 _size = size;
duke@0 70 _count = 1;
duke@0 71 init_statistics();
duke@0 72 #ifndef PRODUCT
duke@0 73 _allocation_stats.set_returnedBytes(_size * HeapWordSize);
duke@0 74 #endif
duke@0 75 }
duke@0 76
duke@0 77 void FreeList::reset(size_t hint) {
duke@0 78 set_count(0);
duke@0 79 set_head(NULL);
duke@0 80 set_tail(NULL);
duke@0 81 set_hint(hint);
duke@0 82 }
duke@0 83
duke@0 84 void FreeList::init_statistics() {
duke@0 85 _allocation_stats.initialize();
duke@0 86 }
duke@0 87
duke@0 88 FreeChunk* FreeList::getChunkAtHead() {
duke@0 89 assert_proper_lock_protection();
duke@0 90 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 91 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 92 FreeChunk* fc = head();
duke@0 93 if (fc != NULL) {
duke@0 94 FreeChunk* nextFC = fc->next();
duke@0 95 if (nextFC != NULL) {
duke@0 96 // The chunk fc being removed has a "next". Set the "next" to the
duke@0 97 // "prev" of fc.
duke@0 98 nextFC->linkPrev(NULL);
duke@0 99 } else { // removed tail of list
duke@0 100 link_tail(NULL);
duke@0 101 }
duke@0 102 link_head(nextFC);
duke@0 103 decrement_count();
duke@0 104 }
duke@0 105 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 106 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 107 return fc;
duke@0 108 }
duke@0 109
duke@0 110
duke@0 111 void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) {
duke@0 112 assert_proper_lock_protection();
duke@0 113 assert(fl->count() == 0, "Precondition");
duke@0 114 if (count() > 0) {
duke@0 115 int k = 1;
duke@0 116 fl->set_head(head()); n--;
duke@0 117 FreeChunk* tl = head();
duke@0 118 while (tl->next() != NULL && n > 0) {
duke@0 119 tl = tl->next(); n--; k++;
duke@0 120 }
duke@0 121 assert(tl != NULL, "Loop Inv.");
duke@0 122
duke@0 123 // First, fix up the list we took from.
duke@0 124 FreeChunk* new_head = tl->next();
duke@0 125 set_head(new_head);
duke@0 126 set_count(count() - k);
duke@0 127 if (new_head == NULL) {
duke@0 128 set_tail(NULL);
duke@0 129 } else {
duke@0 130 new_head->linkPrev(NULL);
duke@0 131 }
duke@0 132 // Now we can fix up the tail.
duke@0 133 tl->linkNext(NULL);
duke@0 134 // And return the result.
duke@0 135 fl->set_tail(tl);
duke@0 136 fl->set_count(k);
duke@0 137 }
duke@0 138 }
duke@0 139
duke@0 140 // Remove this chunk from the list
duke@0 141 void FreeList::removeChunk(FreeChunk*fc) {
duke@0 142 assert_proper_lock_protection();
duke@0 143 assert(head() != NULL, "Remove from empty list");
duke@0 144 assert(fc != NULL, "Remove a NULL chunk");
duke@0 145 assert(size() == fc->size(), "Wrong list");
duke@0 146 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 147 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 148
duke@0 149 FreeChunk* prevFC = fc->prev();
duke@0 150 FreeChunk* nextFC = fc->next();
duke@0 151 if (nextFC != NULL) {
duke@0 152 // The chunk fc being removed has a "next". Set the "next" to the
duke@0 153 // "prev" of fc.
duke@0 154 nextFC->linkPrev(prevFC);
duke@0 155 } else { // removed tail of list
duke@0 156 link_tail(prevFC);
duke@0 157 }
duke@0 158 if (prevFC == NULL) { // removed head of list
duke@0 159 link_head(nextFC);
duke@0 160 assert(nextFC == NULL || nextFC->prev() == NULL,
duke@0 161 "Prev of head should be NULL");
duke@0 162 } else {
duke@0 163 prevFC->linkNext(nextFC);
duke@0 164 assert(tail() != prevFC || prevFC->next() == NULL,
duke@0 165 "Next of tail should be NULL");
duke@0 166 }
duke@0 167 decrement_count();
duke@0 168 #define TRAP_CODE 1
duke@0 169 #if TRAP_CODE
duke@0 170 if (head() == NULL) {
duke@0 171 guarantee(tail() == NULL, "INVARIANT");
duke@0 172 guarantee(count() == 0, "INVARIANT");
duke@0 173 }
duke@0 174 #endif
duke@0 175 // clear next and prev fields of fc, debug only
duke@0 176 NOT_PRODUCT(
duke@0 177 fc->linkPrev(NULL);
duke@0 178 fc->linkNext(NULL);
duke@0 179 )
duke@0 180 assert(fc->isFree(), "Should still be a free chunk");
duke@0 181 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 182 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 183 assert(head() == NULL || head()->size() == size(), "wrong item on list");
duke@0 184 assert(tail() == NULL || tail()->size() == size(), "wrong item on list");
duke@0 185 }
duke@0 186
duke@0 187 // Add this chunk at the head of the list.
duke@0 188 void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) {
duke@0 189 assert_proper_lock_protection();
duke@0 190 assert(chunk != NULL, "insert a NULL chunk");
duke@0 191 assert(size() == chunk->size(), "Wrong size");
duke@0 192 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 193 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 194
duke@0 195 FreeChunk* oldHead = head();
duke@0 196 assert(chunk != oldHead, "double insertion");
duke@0 197 chunk->linkAfter(oldHead);
duke@0 198 link_head(chunk);
duke@0 199 if (oldHead == NULL) { // only chunk in list
duke@0 200 assert(tail() == NULL, "inconsistent FreeList");
duke@0 201 link_tail(chunk);
duke@0 202 }
duke@0 203 increment_count(); // of # of chunks in list
duke@0 204 DEBUG_ONLY(
duke@0 205 if (record_return) {
duke@0 206 increment_returnedBytes_by(size()*HeapWordSize);
duke@0 207 }
duke@0 208 )
duke@0 209 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 210 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 211 assert(head() == NULL || head()->size() == size(), "wrong item on list");
duke@0 212 assert(tail() == NULL || tail()->size() == size(), "wrong item on list");
duke@0 213 }
duke@0 214
duke@0 215 void FreeList::returnChunkAtHead(FreeChunk* chunk) {
duke@0 216 assert_proper_lock_protection();
duke@0 217 returnChunkAtHead(chunk, true);
duke@0 218 }
duke@0 219
duke@0 220 // Add this chunk at the tail of the list.
duke@0 221 void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) {
duke@0 222 assert_proper_lock_protection();
duke@0 223 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 224 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 225 assert(chunk != NULL, "insert a NULL chunk");
duke@0 226 assert(size() == chunk->size(), "wrong size");
duke@0 227
duke@0 228 FreeChunk* oldTail = tail();
duke@0 229 assert(chunk != oldTail, "double insertion");
duke@0 230 if (oldTail != NULL) {
duke@0 231 oldTail->linkAfter(chunk);
duke@0 232 } else { // only chunk in list
duke@0 233 assert(head() == NULL, "inconsistent FreeList");
duke@0 234 link_head(chunk);
duke@0 235 }
duke@0 236 link_tail(chunk);
duke@0 237 increment_count(); // of # of chunks in list
duke@0 238 DEBUG_ONLY(
duke@0 239 if (record_return) {
duke@0 240 increment_returnedBytes_by(size()*HeapWordSize);
duke@0 241 }
duke@0 242 )
duke@0 243 assert(head() == NULL || head()->prev() == NULL, "list invariant");
duke@0 244 assert(tail() == NULL || tail()->next() == NULL, "list invariant");
duke@0 245 assert(head() == NULL || head()->size() == size(), "wrong item on list");
duke@0 246 assert(tail() == NULL || tail()->size() == size(), "wrong item on list");
duke@0 247 }
duke@0 248
duke@0 249 void FreeList::returnChunkAtTail(FreeChunk* chunk) {
duke@0 250 returnChunkAtTail(chunk, true);
duke@0 251 }
duke@0 252
duke@0 253 void FreeList::prepend(FreeList* fl) {
duke@0 254 assert_proper_lock_protection();
duke@0 255 if (fl->count() > 0) {
duke@0 256 if (count() == 0) {
duke@0 257 set_head(fl->head());
duke@0 258 set_tail(fl->tail());
duke@0 259 set_count(fl->count());
duke@0 260 } else {
duke@0 261 // Both are non-empty.
duke@0 262 FreeChunk* fl_tail = fl->tail();
duke@0 263 FreeChunk* this_head = head();
duke@0 264 assert(fl_tail->next() == NULL, "Well-formedness of fl");
duke@0 265 fl_tail->linkNext(this_head);
duke@0 266 this_head->linkPrev(fl_tail);
duke@0 267 set_head(fl->head());
duke@0 268 set_count(count() + fl->count());
duke@0 269 }
duke@0 270 fl->set_head(NULL);
duke@0 271 fl->set_tail(NULL);
duke@0 272 fl->set_count(0);
duke@0 273 }
duke@0 274 }
duke@0 275
duke@0 276 // verifyChunkInFreeLists() is used to verify that an item is in this free list.
duke@0 277 // It is used as a debugging aid.
duke@0 278 bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const {
duke@0 279 // This is an internal consistency check, not part of the check that the
duke@0 280 // chunk is in the free lists.
duke@0 281 guarantee(fc->size() == size(), "Wrong list is being searched");
duke@0 282 FreeChunk* curFC = head();
duke@0 283 while (curFC) {
duke@0 284 // This is an internal consistency check.
duke@0 285 guarantee(size() == curFC->size(), "Chunk is in wrong list.");
duke@0 286 if (fc == curFC) {
duke@0 287 return true;
duke@0 288 }
duke@0 289 curFC = curFC->next();
duke@0 290 }
duke@0 291 return false;
duke@0 292 }
duke@0 293
duke@0 294 #ifndef PRODUCT
duke@0 295 void FreeList::assert_proper_lock_protection_work() const {
duke@0 296 #ifdef ASSERT
duke@0 297 if (_protecting_lock != NULL &&
duke@0 298 SharedHeap::heap()->n_par_threads() > 0) {
duke@0 299 // Should become an assert.
duke@0 300 guarantee(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED");
duke@0 301 }
duke@0 302 #endif
duke@0 303 }
duke@0 304 #endif