1 /*
   2  * Copyright (c) 2001, 2012, 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_work() const PRODUCT_RETURN;
  63   void assert_proper_lock_protection() const {
  64 #ifdef ASSERT
  65     if (_protecting_lock != NULL)
  66       assert_proper_lock_protection_work();
  67 #endif
  68   }
  69 
  70   void increment_count()    {
  71     _count++;
  72   }
  73 
  74   void decrement_count() {
  75     _count--;
  76     assert(_count >= 0, "Count should not be negative");
  77   }
  78 
  79  public:
  80   // Constructor
  81   // Construct a list without any entries.
  82   FreeList();
  83   // Construct a list with "fc" as the first (and lone) entry in the list.
  84   FreeList(Chunk_t* fc);
  85 
  86   // Do initialization
  87   void initialize();
  88 
  89   // Reset the head, tail, and count of a free list.
  90   void reset();
  91 
  92   // Declare the current free list to be protected by the given lock.
  93 #ifdef ASSERT
  94   Mutex* protecting_lock() const { return _protecting_lock; }
  95   void set_protecting_lock(Mutex* v) {
  96     _protecting_lock = v;
  97   }
  98 #endif
  99 
 100   // Accessors.
 101   Chunk_t* head() const {
 102     assert_proper_lock_protection();
 103     return _head;
 104   }
 105   void set_head(Chunk_t* v) {
 106     assert_proper_lock_protection();
 107     _head = v;
 108     assert(!_head || _head->size() == _size, "bad chunk size");
 109   }
 110   // Set the head of the list and set the prev field of non-null
 111   // values to NULL.
 112   void link_head(Chunk_t* v);
 113 
 114   Chunk_t* tail() const {
 115     assert_proper_lock_protection();
 116     return _tail;
 117   }
 118   void set_tail(Chunk_t* v) {
 119     assert_proper_lock_protection();
 120     _tail = v;
 121     assert(!_tail || _tail->size() == _size, "bad chunk size");
 122   }
 123   // Set the tail of the list and set the next field of non-null
 124   // values to NULL.
 125   void link_tail(Chunk_t* v) {
 126     assert_proper_lock_protection();
 127     set_tail(v);
 128     if (v != NULL) {
 129       v->clear_next();
 130     }
 131   }
 132 
 133   // No locking checks in read-accessors: lock-free reads (only) are benign.
 134   // Readers are expected to have the lock if they are doing work that
 135   // requires atomicity guarantees in sections of code.
 136   size_t size() const {
 137     return _size;
 138   }
 139   void set_size(size_t v) {
 140     assert_proper_lock_protection();
 141     _size = v;
 142   }
 143   ssize_t count() const { return _count; }
 144   void set_count(ssize_t v) { _count = v;}
 145 
 146   size_t get_better_size() { return size(); }
 147 
 148   size_t returned_bytes() const { ShouldNotReachHere(); return 0; }
 149   void set_returned_bytes(size_t v) {}
 150   void increment_returned_bytes_by(size_t v) {}
 151 
 152   // Unlink head of list and return it.  Returns NULL if
 153   // the list is empty.
 154   Chunk_t* get_chunk_at_head();
 155 
 156   // Remove the first "n" or "count", whichever is smaller, chunks from the
 157   // list, setting "fl", which is required to be empty, to point to them.
 158   void getFirstNChunksFromList(size_t n, FreeList<Chunk_t>* fl);
 159 
 160   // Unlink this chunk from it's free list
 161   void remove_chunk(Chunk_t* fc);
 162 
 163   // Add this chunk to this free list.
 164   void return_chunk_at_head(Chunk_t* fc);
 165   void return_chunk_at_tail(Chunk_t* fc);
 166 
 167   // Similar to returnChunk* but also records some diagnostic
 168   // information.
 169   void return_chunk_at_head(Chunk_t* fc, bool record_return);
 170   void return_chunk_at_tail(Chunk_t* fc, bool record_return);
 171 
 172   // Prepend "fl" (whose size is required to be the same as that of "this")
 173   // to the front of "this" list.
 174   void prepend(FreeList<Chunk_t>* fl);
 175 
 176   // Verify that the chunk is in the list.
 177   // found.  Return NULL if "fc" is not found.
 178   bool verify_chunk_in_free_list(Chunk_t* fc) const;
 179 
 180   // Stats verification
 181 //  void verify_stats() const { ShouldNotReachHere(); };
 182 
 183   // Printing support
 184   static void print_labels_on(outputStream* st, const char* c);
 185   void print_on(outputStream* st, const char* c = NULL) const;
 186 };
 187 
 188 #endif // SHARE_VM_MEMORY_FREELIST_HPP