1 /*
   2  * Copyright (c) 2001, 2013, 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 #ifndef SHARE_VM_MEMORY_FREELIST_HPP
  26 #define SHARE_VM_MEMORY_FREELIST_HPP
  27 
  28 #include "gc_implementation/shared/allocationStats.hpp"
  29 
  30 class CompactibleFreeListSpace;
  31 
  32 // A class for maintaining a free list of Chunk's.  The FreeList
  33 // maintains a the structure of the list (head, tail, etc.) plus
  34 // statistics for allocations from the list.  The links between items
  35 // are not part of FreeList.  The statistics are
  36 // used to make decisions about coalescing Chunk's when they
  37 // are swept during collection.
  38 //
  39 // See the corresponding .cpp file for a description of the specifics
  40 // for that implementation.
  41 
  42 class Mutex;
  43 
  44 template <class Chunk_t>
  45 class FreeList VALUE_OBJ_CLASS_SPEC {
  46   friend class CompactibleFreeListSpace;
  47   friend class VMStructs;
  48 
  49  private:
  50   Chunk_t*      _head;          // Head of list of free chunks
  51   Chunk_t*      _tail;          // Tail of list of free chunks
  52   size_t        _size;          // Size in Heap words of each chunk
  53   ssize_t       _count;         // Number of entries in list
  54 
  55  protected:
  56 
  57 #ifdef ASSERT
  58   Mutex*        _protecting_lock;
  59 #endif
  60 
  61   // Asserts false if the protecting lock (if any) is not held.
  62   void assert_proper_lock_protection() const;
  63 
  64   void increment_count()    {
  65     _count++;
  66   }
  67 
  68   void decrement_count() {
  69     _count--;
  70     assert(_count >= 0, "Count should not be negative");
  71   }
  72 
  73  public:
  74   // Constructor
  75   // Construct a list without any entries.
  76   FreeList();
  77 
  78   // Do initialization
  79   void initialize();
  80 
  81   // Reset the head, tail, and count of a free list.
  82   void reset();
  83 
  84   // Declare the current free list to be protected by the given lock.
  85 #ifdef ASSERT
  86   Mutex* protecting_lock() const { return _protecting_lock; }
  87   void set_protecting_lock(Mutex* v) {
  88     _protecting_lock = v;
  89   }
  90 #endif
  91 
  92   // Accessors.
  93   Chunk_t* head() const {
  94     assert_proper_lock_protection();
  95     return _head;
  96   }
  97   void set_head(Chunk_t* v) {
  98     assert_proper_lock_protection();
  99     _head = v;
 100     assert(!_head || _head->size() == _size, "bad chunk size");
 101   }
 102   // Set the head of the list and set the prev field of non-null
 103   // values to NULL.
 104   void link_head(Chunk_t* v);
 105 
 106   Chunk_t* tail() const {
 107     assert_proper_lock_protection();
 108     return _tail;
 109   }
 110   void set_tail(Chunk_t* v) {
 111     assert_proper_lock_protection();
 112     _tail = v;
 113     assert(!_tail || _tail->size() == _size, "bad chunk size");
 114   }
 115   // Set the tail of the list and set the next field of non-null
 116   // values to NULL.
 117   void link_tail(Chunk_t* v) {
 118     assert_proper_lock_protection();
 119     set_tail(v);
 120     if (v != NULL) {
 121       v->clear_next();
 122     }
 123   }
 124 
 125   // No locking checks in read-accessors: lock-free reads (only) are benign.
 126   // Readers are expected to have the lock if they are doing work that
 127   // requires atomicity guarantees in sections of code.
 128   size_t size() const {
 129     return _size;
 130   }
 131   void set_size(size_t v) {
 132     assert_proper_lock_protection();
 133     _size = v;
 134   }
 135   ssize_t count() const { return _count; }
 136   void set_count(ssize_t v) { _count = v;}
 137 
 138   size_t get_better_size() { return size(); }
 139 
 140   size_t returned_bytes() const { ShouldNotReachHere(); return 0; }
 141   void set_returned_bytes(size_t v) {}
 142   void increment_returned_bytes_by(size_t v) {}
 143 
 144   // Unlink head of list and return it.  Returns NULL if
 145   // the list is empty.
 146   Chunk_t* get_chunk_at_head();
 147 
 148   // Remove the first "n" or "count", whichever is smaller, chunks from the
 149   // list, setting "fl", which is required to be empty, to point to them.
 150   void getFirstNChunksFromList(size_t n, FreeList<Chunk_t>* fl);
 151 
 152   // Unlink this chunk from it's free list
 153   void remove_chunk(Chunk_t* fc);
 154 
 155   // Add this chunk to this free list.
 156   void return_chunk_at_head(Chunk_t* fc);
 157   void return_chunk_at_tail(Chunk_t* fc);
 158 
 159   // Similar to returnChunk* but also records some diagnostic
 160   // information.
 161   void return_chunk_at_head(Chunk_t* fc, bool record_return);
 162   void return_chunk_at_tail(Chunk_t* fc, bool record_return);
 163 
 164   // Prepend "fl" (whose size is required to be the same as that of "this")
 165   // to the front of "this" list.
 166   void prepend(FreeList<Chunk_t>* fl);
 167 
 168   // Verify that the chunk is in the list.
 169   // found.  Return NULL if "fc" is not found.
 170   bool verify_chunk_in_free_list(Chunk_t* fc) const;
 171 
 172   // Printing support
 173   static void print_labels_on(outputStream* st, const char* c);
 174   void print_on(outputStream* st, const char* c = NULL) const;
 175 };
 176 
 177 #endif // SHARE_VM_MEMORY_FREELIST_HPP