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. Array lives in C heap and
37 // expands automatically. Free elements can be returned, will be kept in
38 // a freelist. Elements can be retrieved by their index (index type I).
39 // Index 0 will never be allocated and can be relied upon as being invalid.
40 //
41 // E must be of at least sizeof(I), and I must be an integral size.
42 //
43 template <class E, class I>
44 class AbstractPool {
45 public:
46
47 typedef I size_type_t;
48
49 private:
50
51 E* _arr;
52 size_type_t _capacity;
53 size_type_t _top;
54
55 I _freelist;
56 size_type_t _num_in_freelist;
57
58 const size_type_t _max_capacity;
59 const size_type_t _capacity_increase;
60 const char* const _name;
61
62 // Enlarge internal array if needed. Zero out new portion of array.
63 void enlarge_to(size_type_t new_len) {
64 E* p = REALLOC_C_HEAP_ARRAY(E, _arr, new_len, mtInternal);
65 _arr = p;
66 _capacity = new_len;
67 }
68
69 //// freelist handling ////
70
71 struct free_elem_t {
72 I next_idx;
73 };
74
75 // free_elem_t must fit into an E, and sizeof(E) must be aligned such that
76 // one can write free_elem_t at &E.
77 STATIC_ASSERT(sizeof(E) >= sizeof(free_elem_t));
78 STATIC_ASSERT(sizeof(E) % sizeof(free_elem_t) == 0);
79
80 E* take_from_freelist() {
81 I idx = _freelist;
82 if (0 == idx) {
83 assert(_num_in_freelist == 0, "counter mismatch");
84 return NULL;
85 }
86 E* p = elem_at_index(idx);
87 _freelist = ((free_elem_t*)p)->next_idx;
88 assert(_num_in_freelist > 0, "counter underflow");
89 _num_in_freelist --;
90 return p;
91 }
92
93 void add_to_freelist(E* p) {
94 ((free_elem_t*)p)->next_idx = _freelist;
95 _freelist = index_for_elem(p);
96 _num_in_freelist ++;
97 }
98
99 public:
100
101 AbstractPool(const char* name, size_type_t max_capacity, size_type_t capacity_increase)
102 : _arr(NULL), _capacity(0),
103 _top(0),
104 _freelist((I)0), _num_in_freelist(0),
105 _max_capacity(max_capacity), _capacity_increase(capacity_increase),
106 _name(name)
107 {}
108
109 ~AbstractPool() { FREE_C_HEAP_ARRAY(E, _arr); }
110
111 I index_for_elem(const E* p) const {
112 DEBUG_ONLY(check_elem(p));
113 return p - _arr;
114 }
115
116 E* elem_at_index(I i) const {
117 DEBUG_ONLY(check_idx(i));
118 return _arr + i;
119 }
120
121 // Allocate a new element. Enlarge internal array if needed.
122 // Will return NULL if max_size is reached.
123 E* allocate_element() {
124
125 DEBUG_ONLY(verify(false));
126
127 E* p = take_from_freelist();
128 if (p != NULL) {
129 return p;
130 }
131
132 if (_capacity == _top) { // Need to enlarge.
133 size_type_t new_cap = MIN2((size_type_t)(_capacity + _capacity_increase), _max_capacity);
134 if (new_cap == _capacity) {
135 return NULL; // capped out.
136 }
137 enlarge_to(new_cap);
138 }
139
140 // Avoid handing out anything at index 0.
141 // This allows callers to use "I index == 0" as "invalid ref".
142 if (_top == 0) {
143 _top ++;
144 }
145
146 p = _arr + _top;
147 _top ++;
148
149 return p;
150
151 }
152
153 void return_element(E* p) {
154 DEBUG_ONLY(check_elem(p));
155 add_to_freelist(p);
156 }
157
158 // Returns number of allocated elements.
159 size_type_t used() const { return _top - _num_in_freelist; }
160
161 // True if pool is full.
162 bool is_full() const { return used() == max_capacity(); }
163
164 // True if pool is empty.
165 bool is_empty() const { return used() == 0; }
166
167 // Returns number of elements in free list.
168 size_type_t free_elements() const { return _num_in_freelist; }
169
170 // Returns max. capacity of this pool.
171 size_type_t max_capacity() const { return _max_capacity; }
172
173 // Returns size of memory used.
174 size_t memory_footprint_words() const { return _capacity * sizeof(E); }
175
176 // Returns true if p was allocated from this pool.
177 bool is_valid_elem(const E* p) const { return p >= _arr && p < _arr + _top; }
178
179 // Returns true if the index points into the allocated portion of the pool.
180 // Note: may point to an allocated element or one in the freelist.
181 bool is_valid_index(I idx) const { return idx > 0 && idx < _top; }
182
183 #ifdef ASSERT
184 void check_elem(const E* p) const { assert(is_valid_elem(p), "invalid pointer"); }
185 void check_idx(I i) const { assert(i > 0 && i <= _top, "invalid index"); }
186 void verify(bool slow) const {
187 assert(_top <= _capacity && _capacity <= _max_capacity, "Sanity");
188 assert(used() <= _capacity, "Sanity");
189 if (slow) {
190 // check freelist.
191 I idx = _freelist;
192 size_type_t num = 0;
193 while (idx != 0) {
194 num ++;
195 idx = ((free_elem_t*)elem_at_index(idx))->next_idx;
196 }
197 assert(num == _num_in_freelist, "counter mismatch");
198 }
199 }
200 #endif // ASSERT
201
202 };
203
204
205 } // namespace metaspace
206
207
208
209
210 #endif // SHARE_MEMORY_METASPACE_ABSTRACTPOOL_HPP