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