Mercurial > hg > truffle
diff src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp @ 0:a61af66fc99e jdk7-b24
Initial load
author | duke |
---|---|
date | Sat, 01 Dec 2007 00:00:00 +0000 |
parents | |
children | 6432c3bb6240 |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/src/share/vm/gc_implementation/concurrentMarkSweep/freeList.cpp Sat Dec 01 00:00:00 2007 +0000 @@ -0,0 +1,304 @@ +/* + * Copyright 2001-2006 Sun Microsystems, Inc. All Rights Reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara, + * CA 95054 USA or visit www.sun.com if you need additional information or + * have any questions. + * + */ + +# include "incls/_precompiled.incl" +# include "incls/_freeList.cpp.incl" + +// Free list. A FreeList is used to access a linked list of chunks +// of space in the heap. The head and tail are maintained so that +// items can be (as in the current implementation) added at the +// at the tail of the list and removed from the head of the list to +// maintain a FIFO queue. + +FreeList::FreeList() : + _head(NULL), _tail(NULL) +#ifdef ASSERT + , _protecting_lock(NULL) +#endif +{ + _size = 0; + _count = 0; + _hint = 0; + init_statistics(); +} + +FreeList::FreeList(FreeChunk* fc) : + _head(fc), _tail(fc) +#ifdef ASSERT + , _protecting_lock(NULL) +#endif +{ + _size = fc->size(); + _count = 1; + _hint = 0; + init_statistics(); +#ifndef PRODUCT + _allocation_stats.set_returnedBytes(size() * HeapWordSize); +#endif +} + +FreeList::FreeList(HeapWord* addr, size_t size) : + _head((FreeChunk*) addr), _tail((FreeChunk*) addr) +#ifdef ASSERT + , _protecting_lock(NULL) +#endif +{ + assert(size > sizeof(FreeChunk), "size is too small"); + head()->setSize(size); + _size = size; + _count = 1; + init_statistics(); +#ifndef PRODUCT + _allocation_stats.set_returnedBytes(_size * HeapWordSize); +#endif +} + +void FreeList::reset(size_t hint) { + set_count(0); + set_head(NULL); + set_tail(NULL); + set_hint(hint); +} + +void FreeList::init_statistics() { + _allocation_stats.initialize(); +} + +FreeChunk* FreeList::getChunkAtHead() { + assert_proper_lock_protection(); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + FreeChunk* fc = head(); + if (fc != NULL) { + FreeChunk* nextFC = fc->next(); + if (nextFC != NULL) { + // The chunk fc being removed has a "next". Set the "next" to the + // "prev" of fc. + nextFC->linkPrev(NULL); + } else { // removed tail of list + link_tail(NULL); + } + link_head(nextFC); + decrement_count(); + } + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + return fc; +} + + +void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) { + assert_proper_lock_protection(); + assert(fl->count() == 0, "Precondition"); + if (count() > 0) { + int k = 1; + fl->set_head(head()); n--; + FreeChunk* tl = head(); + while (tl->next() != NULL && n > 0) { + tl = tl->next(); n--; k++; + } + assert(tl != NULL, "Loop Inv."); + + // First, fix up the list we took from. + FreeChunk* new_head = tl->next(); + set_head(new_head); + set_count(count() - k); + if (new_head == NULL) { + set_tail(NULL); + } else { + new_head->linkPrev(NULL); + } + // Now we can fix up the tail. + tl->linkNext(NULL); + // And return the result. + fl->set_tail(tl); + fl->set_count(k); + } +} + +// Remove this chunk from the list +void FreeList::removeChunk(FreeChunk*fc) { + assert_proper_lock_protection(); + assert(head() != NULL, "Remove from empty list"); + assert(fc != NULL, "Remove a NULL chunk"); + assert(size() == fc->size(), "Wrong list"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + FreeChunk* prevFC = fc->prev(); + FreeChunk* nextFC = fc->next(); + if (nextFC != NULL) { + // The chunk fc being removed has a "next". Set the "next" to the + // "prev" of fc. + nextFC->linkPrev(prevFC); + } else { // removed tail of list + link_tail(prevFC); + } + if (prevFC == NULL) { // removed head of list + link_head(nextFC); + assert(nextFC == NULL || nextFC->prev() == NULL, + "Prev of head should be NULL"); + } else { + prevFC->linkNext(nextFC); + assert(tail() != prevFC || prevFC->next() == NULL, + "Next of tail should be NULL"); + } + decrement_count(); +#define TRAP_CODE 1 +#if TRAP_CODE + if (head() == NULL) { + guarantee(tail() == NULL, "INVARIANT"); + guarantee(count() == 0, "INVARIANT"); + } +#endif + // clear next and prev fields of fc, debug only + NOT_PRODUCT( + fc->linkPrev(NULL); + fc->linkNext(NULL); + ) + assert(fc->isFree(), "Should still be a free chunk"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +// Add this chunk at the head of the list. +void FreeList::returnChunkAtHead(FreeChunk* chunk, bool record_return) { + assert_proper_lock_protection(); + assert(chunk != NULL, "insert a NULL chunk"); + assert(size() == chunk->size(), "Wrong size"); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + + FreeChunk* oldHead = head(); + assert(chunk != oldHead, "double insertion"); + chunk->linkAfter(oldHead); + link_head(chunk); + if (oldHead == NULL) { // only chunk in list + assert(tail() == NULL, "inconsistent FreeList"); + link_tail(chunk); + } + increment_count(); // of # of chunks in list + DEBUG_ONLY( + if (record_return) { + increment_returnedBytes_by(size()*HeapWordSize); + } + ) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +void FreeList::returnChunkAtHead(FreeChunk* chunk) { + assert_proper_lock_protection(); + returnChunkAtHead(chunk, true); +} + +// Add this chunk at the tail of the list. +void FreeList::returnChunkAtTail(FreeChunk* chunk, bool record_return) { + assert_proper_lock_protection(); + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(chunk != NULL, "insert a NULL chunk"); + assert(size() == chunk->size(), "wrong size"); + + FreeChunk* oldTail = tail(); + assert(chunk != oldTail, "double insertion"); + if (oldTail != NULL) { + oldTail->linkAfter(chunk); + } else { // only chunk in list + assert(head() == NULL, "inconsistent FreeList"); + link_head(chunk); + } + link_tail(chunk); + increment_count(); // of # of chunks in list + DEBUG_ONLY( + if (record_return) { + increment_returnedBytes_by(size()*HeapWordSize); + } + ) + assert(head() == NULL || head()->prev() == NULL, "list invariant"); + assert(tail() == NULL || tail()->next() == NULL, "list invariant"); + assert(head() == NULL || head()->size() == size(), "wrong item on list"); + assert(tail() == NULL || tail()->size() == size(), "wrong item on list"); +} + +void FreeList::returnChunkAtTail(FreeChunk* chunk) { + returnChunkAtTail(chunk, true); +} + +void FreeList::prepend(FreeList* fl) { + assert_proper_lock_protection(); + if (fl->count() > 0) { + if (count() == 0) { + set_head(fl->head()); + set_tail(fl->tail()); + set_count(fl->count()); + } else { + // Both are non-empty. + FreeChunk* fl_tail = fl->tail(); + FreeChunk* this_head = head(); + assert(fl_tail->next() == NULL, "Well-formedness of fl"); + fl_tail->linkNext(this_head); + this_head->linkPrev(fl_tail); + set_head(fl->head()); + set_count(count() + fl->count()); + } + fl->set_head(NULL); + fl->set_tail(NULL); + fl->set_count(0); + } +} + +// verifyChunkInFreeLists() is used to verify that an item is in this free list. +// It is used as a debugging aid. +bool FreeList::verifyChunkInFreeLists(FreeChunk* fc) const { + // This is an internal consistency check, not part of the check that the + // chunk is in the free lists. + guarantee(fc->size() == size(), "Wrong list is being searched"); + FreeChunk* curFC = head(); + while (curFC) { + // This is an internal consistency check. + guarantee(size() == curFC->size(), "Chunk is in wrong list."); + if (fc == curFC) { + return true; + } + curFC = curFC->next(); + } + return false; +} + +#ifndef PRODUCT +void FreeList::assert_proper_lock_protection_work() const { +#ifdef ASSERT + if (_protecting_lock != NULL && + SharedHeap::heap()->n_par_threads() > 0) { + // Should become an assert. + guarantee(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED"); + } +#endif +} +#endif