Mercurial > hg > truffle
annotate src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp @ 452:00b023ae2d78
6722113: CMS: Incorrect overflow handling during precleaning of Reference lists
Summary: When we encounter marking stack overflow during precleaning of Reference lists, we were using the overflow list mechanism, which can cause problems on account of mutating the mark word of the header because of conflicts with mutator accesses and updates of that field. Instead we should use the usual mechanism for overflow handling in concurrent phases, namely dirtying of the card on which the overflowed object lies. Since precleaning effectively does a form of discovered list processing, albeit with discovery enabled, we needed to adjust some code to be correct in the face of interleaved processing and discovery.
Reviewed-by: apetrusenko, jcoomes
| author | ysr |
|---|---|
| date | Thu, 20 Nov 2008 12:27:41 -0800 |
| parents | d1605aabd0a1 |
| children | e018e6884bd8 |
| rev | line source |
|---|---|
| 0 | 1 /* |
| 196 | 2 * Copyright 2001-2008 Sun Microsystems, Inc. All Rights Reserved. |
| 0 | 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 Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, | |
| 20 * CA 95054 USA or visit www.sun.com if you need additional information or | |
| 21 * have any questions. | |
| 22 * | |
| 23 */ | |
| 24 | |
| 25 # include "incls/_precompiled.incl" | |
| 26 # include "incls/_freeList.cpp.incl" | |
| 27 | |
| 28 // Free list. A FreeList is used to access a linked list of chunks | |
| 29 // of space in the heap. The head and tail are maintained so that | |
| 30 // items can be (as in the current implementation) added at the | |
| 31 // at the tail of the list and removed from the head of the list to | |
| 32 // maintain a FIFO queue. | |
| 33 | |
| 34 FreeList::FreeList() : | |
| 35 _head(NULL), _tail(NULL) | |
| 36 #ifdef ASSERT | |
| 37 , _protecting_lock(NULL) | |
| 38 #endif | |
| 39 { | |
| 40 _size = 0; | |
| 41 _count = 0; | |
| 42 _hint = 0; | |
| 43 init_statistics(); | |
| 44 } | |
| 45 | |
| 46 FreeList::FreeList(FreeChunk* fc) : | |
| 47 _head(fc), _tail(fc) | |
| 48 #ifdef ASSERT | |
| 49 , _protecting_lock(NULL) | |
| 50 #endif | |
| 51 { | |
| 52 _size = fc->size(); | |
| 53 _count = 1; | |
| 54 _hint = 0; | |
| 55 init_statistics(); | |
| 56 #ifndef PRODUCT | |
| 57 _allocation_stats.set_returnedBytes(size() * HeapWordSize); | |
| 58 #endif | |
| 59 } | |
| 60 | |
| 61 FreeList::FreeList(HeapWord* addr, size_t size) : | |
| 62 _head((FreeChunk*) addr), _tail((FreeChunk*) addr) | |
| 63 #ifdef ASSERT | |
| 64 , _protecting_lock(NULL) | |
| 65 #endif | |
| 66 { | |
| 67 assert(size > sizeof(FreeChunk), "size is too small"); | |
| 68 head()->setSize(size); | |
| 69 _size = size; | |
| 70 _count = 1; | |
| 71 init_statistics(); | |
| 72 #ifndef PRODUCT | |
| 73 _allocation_stats.set_returnedBytes(_size * HeapWordSize); | |
| 74 #endif | |
| 75 } | |
| 76 | |
| 77 void FreeList::reset(size_t hint) { | |
| 78 set_count(0); | |
| 79 set_head(NULL); | |
| 80 set_tail(NULL); | |
| 81 set_hint(hint); | |
| 82 } | |
| 83 | |
| 84 void FreeList::init_statistics() { | |
| 85 _allocation_stats.initialize(); | |
| 86 } | |
| 87 | |
| 88 FreeChunk* FreeList::getChunkAtHead() { | |
| 89 assert_proper_lock_protection(); | |
| 90 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 91 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 92 FreeChunk* fc = head(); | |
| 93 if (fc != NULL) { | |
| 94 FreeChunk* nextFC = fc->next(); | |
| 95 if (nextFC != NULL) { | |
| 96 // The chunk fc being removed has a "next". Set the "next" to the | |
| 97 // "prev" of fc. | |
| 98 nextFC->linkPrev(NULL); | |
| 99 } else { // removed tail of list | |
| 100 link_tail(NULL); | |
| 101 } | |
| 102 link_head(nextFC); | |
| 103 decrement_count(); | |
| 104 } | |
| 105 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 106 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 107 return fc; | |
| 108 } | |
| 109 | |
| 110 | |
| 111 void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { | |
| 112 assert_proper_lock_protection(); | |
| 113 assert(fl->count() == 0, "Precondition"); | |
| 114 if (count() > 0) { | |
| 115 int k = 1; | |
| 116 fl->set_head(head()); n--; | |
| 117 FreeChunk* tl = head(); | |
| 118 while (tl->next() != NULL && n > 0) { | |
| 119 tl = tl->next(); n--; k++; | |
| 120 } | |
| 121 assert(tl != NULL, "Loop Inv."); | |
| 122 | |
| 123 // First, fix up the list we took from. | |
| 124 FreeChunk* new_head = tl->next(); | |
| 125 set_head(new_head); | |
| 126 set_count(count() - k); | |
| 127 if (new_head == NULL) { | |
| 128 set_tail(NULL); | |
| 129 } else { | |
| 130 new_head->linkPrev(NULL); | |
| 131 } | |
| 132 // Now we can fix up the tail. | |
| 133 tl->linkNext(NULL); | |
| 134 // And return the result. | |
| 135 fl->set_tail(tl); | |
| 136 fl->set_count(k); | |
| 137 } | |
| 138 } | |
| 139 | |
| 140 // Remove this chunk from the list | |
| 141 void FreeList::removeChunk(FreeChunk*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 FreeChunk* prevFC = fc->prev(); | |
| 150 FreeChunk* 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->linkPrev(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->linkNext(nextFC); | |
| 164 assert(tail() != prevFC || prevFC->next() == NULL, | |
| 165 "Next of tail should be NULL"); | |
| 166 } | |
| 167 decrement_count(); | |
| 168 #define TRAP_CODE 1 | |
| 169 #if TRAP_CODE | |
| 170 if (head() == NULL) { | |
| 171 guarantee(tail() == NULL, "INVARIANT"); | |
| 172 guarantee(count() == 0, "INVARIANT"); | |
| 173 } | |
| 174 #endif | |
| 175 // clear next and prev fields of fc, debug only | |
| 176 NOT_PRODUCT( | |
| 177 fc->linkPrev(NULL); | |
| 178 fc->linkNext(NULL); | |
| 179 ) | |
| 180 assert(fc->isFree(), "Should still be a free chunk"); | |
| 181 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 182 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 183 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
| 184 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
| 185 } | |
| 186 | |
| 187 // Add this chunk at the head of the list. | |
| 188 void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) { | |
| 189 assert_proper_lock_protection(); | |
| 190 assert(chunk != NULL, "insert a NULL chunk"); | |
| 191 assert(size() == chunk->size(), "Wrong size"); | |
| 192 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 193 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 194 | |
| 195 FreeChunk* oldHead = head(); | |
| 196 assert(chunk != oldHead, "double insertion"); | |
| 197 chunk->linkAfter(oldHead); | |
| 198 link_head(chunk); | |
| 199 if (oldHead == NULL) { // only chunk in list | |
| 200 assert(tail() == NULL, "inconsistent FreeList"); | |
| 201 link_tail(chunk); | |
| 202 } | |
| 203 increment_count(); // of # of chunks in list | |
| 204 DEBUG_ONLY( | |
| 205 if (record_return) { | |
| 206 increment_returnedBytes_by(size()*HeapWordSize); | |
| 207 } | |
| 208 ) | |
| 209 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 210 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 211 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
| 212 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
| 213 } | |
| 214 | |
| 215 void FreeList::returnChunkAtHead(FreeChunk* chunk) { | |
| 216 assert_proper_lock_protection(); | |
| 217 returnChunkAtHead(chunk, true); | |
| 218 } | |
| 219 | |
| 220 // Add this chunk at the tail of the list. | |
| 221 void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) { | |
| 222 assert_proper_lock_protection(); | |
| 223 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 224 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 225 assert(chunk != NULL, "insert a NULL chunk"); | |
| 226 assert(size() == chunk->size(), "wrong size"); | |
| 227 | |
| 228 FreeChunk* oldTail = tail(); | |
| 229 assert(chunk != oldTail, "double insertion"); | |
| 230 if (oldTail != NULL) { | |
| 231 oldTail->linkAfter(chunk); | |
| 232 } else { // only chunk in list | |
| 233 assert(head() == NULL, "inconsistent FreeList"); | |
| 234 link_head(chunk); | |
| 235 } | |
| 236 link_tail(chunk); | |
| 237 increment_count(); // of # of chunks in list | |
| 238 DEBUG_ONLY( | |
| 239 if (record_return) { | |
| 240 increment_returnedBytes_by(size()*HeapWordSize); | |
| 241 } | |
| 242 ) | |
| 243 assert(head() == NULL || head()->prev() == NULL, "list invariant"); | |
| 244 assert(tail() == NULL || tail()->next() == NULL, "list invariant"); | |
| 245 assert(head() == NULL || head()->size() == size(), "wrong item on list"); | |
| 246 assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); | |
| 247 } | |
| 248 | |
| 249 void FreeList::returnChunkAtTail(FreeChunk* chunk) { | |
| 250 returnChunkAtTail(chunk, true); | |
| 251 } | |
| 252 | |
| 253 void FreeList::prepend(FreeList* 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 FreeChunk* fl_tail = fl->tail(); | |
| 263 FreeChunk* this_head = head(); | |
| 264 assert(fl_tail->next() == NULL, "Well-formedness of fl"); | |
| 265 fl_tail->linkNext(this_head); | |
| 266 this_head->linkPrev(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 // verifyChunkInFreeLists() is used to verify that an item is in this free list. | |
| 277 // It is used as a debugging aid. | |
| 278 bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const { | |
| 279 // This is an internal consistency check, not part of the check that the | |
| 280 // chunk is in the free lists. | |
| 281 guarantee(fc->size() == size(), "Wrong list is being searched"); | |
| 282 FreeChunk* curFC = head(); | |
| 283 while (curFC) { | |
| 284 // This is an internal consistency check. | |
| 285 guarantee(size() == curFC->size(), "Chunk is in wrong list."); | |
| 286 if (fc == curFC) { | |
| 287 return true; | |
| 288 } | |
| 289 curFC = curFC->next(); | |
| 290 } | |
| 291 return false; | |
| 292 } | |
| 293 | |
| 294 #ifndef PRODUCT | |
| 295 void FreeList::assert_proper_lock_protection_work() const { | |
| 296 #ifdef ASSERT | |
| 297 if (_protecting_lock != NULL && | |
| 298 SharedHeap::heap()->n_par_threads() > 0) { | |
| 299 // Should become an assert. | |
| 300 guarantee(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); | |
| 301 } | |
| 302 #endif | |
| 303 } | |
| 304 #endif | |
|
12
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
305 |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
306 // Print the "label line" for free list stats. |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
307 void FreeList::print_labels_on(outputStream* st, const char* c) { |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
308 st->print("%16s\t", c); |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
309 st->print("%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
310 "%14s\t" "%14s\t" "%14s\t" "%14s\t" "%14s\t" "\n", |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
311 "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep", |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
312 "count", "cBirths", "cDeaths", "sBirths", "sDeaths"); |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
313 } |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
314 |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
315 // Print the AllocationStats for the given free list. If the second argument |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
316 // to the call is a non-null string, it is printed in the first column; |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
317 // otherwise, if the argument is null (the default), then the size of the |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
318 // (free list) block is printed in the first column. |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
319 void FreeList::print_on(outputStream* st, const char* c) const { |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
320 if (c != NULL) { |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
321 st->print("%16s", c); |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
322 } else { |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
323 st->print(SIZE_FORMAT_W(16), size()); |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
324 } |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
325 st->print("\t" |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
326 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" |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
327 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", |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
328 bfrSurp(), surplus(), desired(), prevSweep(), beforeSweep(), |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
329 count(), coalBirths(), coalDeaths(), splitBirths(), splitDeaths()); |
|
6432c3bb6240
6668743: CMS: Consolidate block statistics reporting code
ysr
parents:
0
diff
changeset
|
330 } |