1 /*

     2  * Copyright (c) 2001, 2010, 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_implementation/concurrentMarkSweep/freeBlockDictionary.hpp"

    27 #include "gc_implementation/concurrentMarkSweep/freeList.hpp"

    28 #include "memory/sharedHeap.hpp"

    29 #include "runtime/globals.hpp"

    30 #include "runtime/mutex.hpp"

    31 #include "runtime/vmThread.hpp"

    32 

    33 // Free list.  A FreeList is used to access a linked list of chunks

    34 // of space in the heap.  The head and tail are maintained so that

    35 // items can be (as in the current implementation) added at the

    36 // at the tail of the list and removed from the head of the list to

    37 // maintain a FIFO queue.

    38 

    39 FreeList::FreeList() :

    40   _head(NULL), _tail(NULL)

    41 #ifdef ASSERT

    42   , _protecting_lock(NULL)

    43 #endif

    44 {

    45   _size         = 0;

    46   _count        = 0;

    47   _hint         = 0;

    48   init_statistics();

    49 }

    50 

    51 FreeList::FreeList(FreeChunk* fc) :

    52   _head(fc), _tail(fc)

    53 #ifdef ASSERT

    54   , _protecting_lock(NULL)

    55 #endif

    56 {

    57   _size         = fc->size();

    58   _count        = 1;

    59   _hint         = 0;

    60   init_statistics();

    61 #ifndef PRODUCT

    62   _allocation_stats.set_returnedBytes(size() * HeapWordSize);

    63 #endif

    64 }

    65 

    66 FreeList::FreeList(HeapWord* addr, size_t size) :

    67   _head((FreeChunk*) addr), _tail((FreeChunk*) addr)

    68 #ifdef ASSERT

    69   , _protecting_lock(NULL)

    70 #endif

    71 {

    72   assert(size > sizeof(FreeChunk), "size is too small");

    73   head()->setSize(size);

    74   _size         = size;

    75   _count        = 1;

    76   init_statistics();

    77 #ifndef PRODUCT

    78   _allocation_stats.set_returnedBytes(_size * HeapWordSize);

    79 #endif

    80 }

    81 

    82 void FreeList::reset(size_t hint) {

    83   set_count(0);

    84   set_head(NULL);

    85   set_tail(NULL);

    86   set_hint(hint);

    87 }

    88 

    89 void FreeList::init_statistics(bool split_birth) {

    90   _allocation_stats.initialize(split_birth);

    91 }

    92 

    93 FreeChunk* FreeList::getChunkAtHead() {

    94   assert_proper_lock_protection();

    95   assert(head() == NULL || head()->prev() == NULL, "list invariant");

    96   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

    97   FreeChunk* fc = head();

    98   if (fc != NULL) {

    99     FreeChunk* nextFC = fc->next();

   100     if (nextFC != NULL) {

   101       // The chunk fc being removed has a "next".  Set the "next" to the

   102       // "prev" of fc.

   103       nextFC->linkPrev(NULL);

   104     } else { // removed tail of list

   105       link_tail(NULL);

   106     }

   107     link_head(nextFC);

   108     decrement_count();

   109   }

   110   assert(head() == NULL || head()->prev() == NULL, "list invariant");

   111   assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   112   return fc;

   113 }

   114 

   115 

   116 void FreeList::getFirstNChunksFromList(size_t n, FreeList* fl) {

   117   assert_proper_lock_protection();

   118   assert(fl->count() == 0, "Precondition");

   119   if (count() > 0) {

   120     int k = 1;

   121     fl->set_head(head()); n--;

   122     FreeChunk* tl = head();

   123     while (tl->next() != NULL && n > 0) {

   124       tl = tl->next(); n--; k++;

   125     }

   126     assert(tl != NULL, "Loop Inv.");

   127 

   128     // First, fix up the list we took from.

   129     FreeChunk* new_head = tl->next();

   130     set_head(new_head);

   131     set_count(count() - k);

   132     if (new_head == NULL) {

   133       set_tail(NULL);

   134     } else {

   135       new_head->linkPrev(NULL);

   136     }

   137     // Now we can fix up the tail.

   138     tl->linkNext(NULL);

   139     // And return the result.

   140     fl->set_tail(tl);

   141     fl->set_count(k);

   142   }

   143 }

   144 

   145 // Remove this chunk from the list

   146 void FreeList::removeChunk(FreeChunk*fc) {

   147    assert_proper_lock_protection();

   148    assert(head() != NULL, "Remove from empty list");

   149    assert(fc != NULL, "Remove a NULL chunk");

   150    assert(size() == fc->size(), "Wrong list");

   151    assert(head() == NULL || head()->prev() == NULL, "list invariant");

   152    assert(tail() == NULL || tail()->next() == NULL, "list invariant");

   153 

   154    FreeChunk* prevFC = fc->prev();

   155    FreeChunk* nextFC = fc->next();

   156    if (nextFC != NULL) {

   157      // The chunk fc being removed has a "next".  Set the "next" to the

   158      // "prev" of fc.

   159      nextFC->linkPrev(prevFC);

   160    } else { // removed tail of list

   161      link_tail(prevFC);

   162    }

   163    if (prevFC == NULL) { // removed head of list

   164      link_head(nextFC);

   165      assert(nextFC == NULL || nextFC->prev() == NULL,

   166        "Prev of head should be NULL");

   167    } else {

   168      prevFC->linkNext(nextFC);

   169      assert(tail() != prevFC || prevFC->next() == NULL,

   170        "Next of tail should be NULL");

   171    }

   172    decrement_count();

   173    assert(((head() == NULL) + (tail() == NULL) + (count() == 0)) % 3 == 0,

   174           "H/T/C Inconsistency");

   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::verify_stats() const {

   296   // The +1 of the LH comparand is to allow some "looseness" in

   297   // checking: we usually call this interface when adding a block

   298   // and we'll subsequently update the stats; we cannot update the

   299   // stats beforehand because in the case of the large-block BT

   300   // dictionary for example, this might be the first block and

   301   // in that case there would be no place that we could record

   302   // the stats (which are kept in the block itself).

   303   assert((_allocation_stats.prevSweep() + _allocation_stats.splitBirths()

   304           + _allocation_stats.coalBirths() + 1)   // Total Production Stock + 1

   305          >= (_allocation_stats.splitDeaths() + _allocation_stats.coalDeaths()

   306              + (ssize_t)count()),                // Total Current Stock + depletion

   307          err_msg("FreeList " PTR_FORMAT " of size " SIZE_FORMAT

   308                  " violates Conservation Principle: "

   309                  "prevSweep(" SIZE_FORMAT ")"

   310                  " + splitBirths(" SIZE_FORMAT ")"

   311                  " + coalBirths(" SIZE_FORMAT ") + 1 >= "

   312                  " splitDeaths(" SIZE_FORMAT ")"

   313                  " coalDeaths(" SIZE_FORMAT ")"

   314                  " + count(" SSIZE_FORMAT ")",

   315                  this, _size, _allocation_stats.prevSweep(), _allocation_stats.splitBirths(),

   316                  _allocation_stats.splitBirths(), _allocation_stats.splitDeaths(),

   317                  _allocation_stats.coalDeaths(), count()));

   318 }

   319 

   320 void FreeList::assert_proper_lock_protection_work() const {

   321   assert(_protecting_lock != NULL, "Don't call this directly");

   322   assert(ParallelGCThreads > 0, "Don't call this directly");

   323   Thread* thr = Thread::current();

   324   if (thr->is_VM_thread() || thr->is_ConcurrentGC_thread()) {

   325     // assert that we are holding the freelist lock

   326   } else if (thr->is_GC_task_thread()) {

   327     assert(_protecting_lock->owned_by_self(), "FreeList RACE DETECTED");

   328   } else if (thr->is_Java_thread()) {

   329     assert(!SafepointSynchronize::is_at_safepoint(), "Should not be executing");

   330   } else {

   331     ShouldNotReachHere();  // unaccounted thread type?

   332   }

   333 }

   334 #endif

   335 

   336 // Print the "label line" for free list stats.

   337 void FreeList::print_labels_on(outputStream* st, const char* c) {

   338   st->print("%16s\t", c);

   339   st->print("%14s\t"    "%14s\t"    "%14s\t"    "%14s\t"    "%14s\t"

   340             "%14s\t"    "%14s\t"    "%14s\t"    "%14s\t"    "%14s\t"    "\n",

   341             "bfrsurp", "surplus", "desired", "prvSwep", "bfrSwep",

   342             "count",   "cBirths", "cDeaths", "sBirths", "sDeaths");

   343 }

   344 

   345 // Print the AllocationStats for the given free list. If the second argument

   346 // to the call is a non-null string, it is printed in the first column;

   347 // otherwise, if the argument is null (the default), then the size of the

   348 // (free list) block is printed in the first column.

   349 void FreeList::print_on(outputStream* st, const char* c) const {

   350   if (c != NULL) {

   351     st->print("%16s", c);

   352   } else {

   353     st->print(SIZE_FORMAT_W(16), size());

   354   }

   355   st->print("\t"

   356            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"

   357            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",

   358            bfrSurp(),             surplus(),             desired(),             prevSweep(),           beforeSweep(),

   359            count(),               coalBirths(),          coalDeaths(),          splitBirths(),         splitDeaths());

   360 }