1 /*
   2  * Copyright (c) 2018, 2019, 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_MEMORY_METASPACE_ABSTRACTPOOL_HPP
  26 #define SHARE_MEMORY_METASPACE_ABSTRACTPOOL_HPP
  27 
  28 #include "memory/allocation.hpp"
  29 #include "utilities/debug.hpp"
  30 #include "utilities/globalDefinitions.hpp"
  31 
  32 namespace metaspace {
  33 
  34 // A simple helper class;
  35 //
  36 // holds a linear array of elements of type E;
  37 //
  38 // array lives in C heap and expands automatically;
  39 //
  40 // free elements can be returned and are kept in a freelist;
  41 //
  42 // elements can be retrieved by their index (index type I).
  43 //
  44 // E must be of at least sizeof(I), and I must be an integral size.
  45 //
  46 template <class E, class I, I initial_size, I size_increase, I max_size>
  47 class AbstractPool {
  48 public:
  49 
  50   typedef I size_type_t;
  51 
  52   static const I invalid_idx = (I)0;
  53 
  54 private:
  55 
  56   E* _arr;
  57   size_type_t _capacity;
  58   size_type_t _used;
  59   I _freelist;
  60 
  61   const char* const _name;
  62 
  63   // Number of elements in the freelist
  64   DEBUG_ONLY(size_type_t _num_in_freelist;)
  65 
  66   // Enlarge internal array if needed. Zero out new portion of array.
  67   void enlarge_to(size_type_t new_len) {
  68     assert(new_len > _capacity && new_len <= max_size, "Sanity");
  69     const size_t new_size_bytes = new_len * sizeof(E);
  70     E* p = (E*) os::realloc(_arr, new_size_bytes, mtInternal);
  71     if (p == NULL) {
  72       vm_exit_out_of_memory(new_size_bytes, OOM_MALLOC_ERROR, "Pool %s: not enough space", _name);
  73     }
  74     _arr = p; _capacity = new_len;
  75   }
  76 
  77   //// freelist handling ////
  78 
  79   struct free_elem_t {
  80     I next_idx;
  81   };
  82 
  83   STATIC_ASSERT(sizeof(E) >= sizeof(free_elem_t));
  84   STATIC_ASSERT(initial_size > 0);
  85   STATIC_ASSERT(size_increase > 0);
  86   STATIC_ASSERT(max_size >= size_increase + initial_size);
  87 
  88   E* take_from_freelist() {
  89     I idx = _freelist;
  90     if (invalid_idx == idx) {
  91       return NULL;
  92     }
  93     E* p = elem_at_index(idx);
  94     _freelist = ((free_elem_t*)p)->next_idx;
  95     assert(_num_in_freelist > 0, "counter underflow");
  96     DEBUG_ONLY(_num_in_freelist --;)
  97     return p;
  98   }
  99 
 100   void add_to_freelist(E* p) {
 101     ((free_elem_t*)p)->next_idx = _freelist;
 102     _freelist = index_for_elem(p);
 103     DEBUG_ONLY(_num_in_freelist ++;)
 104   }
 105 
 106 
 107 #ifdef ASSERT
 108   void check_elem(E* p) { assert(is_valid_elem(p), "invalid pointer"); }
 109   void check_idx(I i) { assert(i <= _used, "invalid index"); }
 110 #endif
 111 
 112 public:
 113 
 114   AbstractPool(const char* name)
 115     : _arr(NULL), _capacity(0), _used(0), _name(name), _freelist(NULL) {}
 116   ~AbstractPool() { os::free(_arr); }
 117 
 118   I index_for_elem(const E* p) const {
 119     DEBUG_ONLY(check_elem(p));
 120     return p - _arr;
 121   }
 122 
 123   E* elem_at_index(I i) const {
 124     DEBUG_ONLY(check_idx(i));
 125     return _arr + i;
 126   }
 127 
 128   // Allocate a new element. Enlarge internal array if needed.
 129   // Will return NULL if max_size is reached.
 130   E* allocate_element() {
 131 
 132     E* p = take_from_freelist();
 133     if (p != NULL) {
 134       return p;
 135     }
 136 
 137     if (_capacity == _used) {
 138       size_type_t new_len = _capacity == 0 ? initial_size : _capacity + size_increase;
 139       if (new_len > max_size) {
 140         new_len = max_size;
 141         if (new_len <= _capacity) {
 142           return NULL;
 143         }
 144       }
 145       enlarge_to(new_len);
 146     }
 147 
 148     // Avoid handing out anything at index 0.
 149     // This allows callers to use "I index == 0" as "invalid ref".
 150     if (_used == 0) {
 151       _used ++;
 152     }
 153 
 154     E* p = _arr[_used ++];
 155     return p;
 156 
 157   }
 158 
 159   void return_element(E* p) {
 160     DEBUG_ONLY(check_elem(p));
 161     add_to_freelist(p);
 162   }
 163 
 164   // Returns true if p was allocated from this pool.
 165   bool is_valid_elem(const E* p) const { return p >= _arr && p < _arr + _used; }
 166 
 167   bool is_valid_index(I idx) const     { return idx < _used; }
 168 
 169   // Returns number of allocated elements (including those returned to free list)
 170   size_type_t used() const { return _used; }
 171 
 172   // Returns number of elements in free list
 173   size_type_t free() const { return _num_in_freelist; }
 174 
 175   // Returns size of memory used.
 176   size_t memory_footprint() const { return _capacity * sizeof(E); }
 177 
 178 };
 179 
 180 
 181 } // namespace metaspace
 182 
 183 #endif // SHARE_MEMORY_METASPACE_ABSTRACTPOOL_HPP