1 /*
2 * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020 SAP SE. All rights reserved.
4 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 *
6 * This code is free software; you can redistribute it and/or modify it
7 * under the terms of the GNU General Public License version 2 only, as
8 * published by the Free Software Foundation.
9 *
10 * This code is distributed in the hope that it will be useful, but WITHOUT
11 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * version 2 for more details (a copy is included in the LICENSE file that
14 * accompanied this code).
15 *
16 * You should have received a copy of the GNU General Public License version
17 * 2 along with this work; if not, write to the Free Software Foundation,
18 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 *
20 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 * or visit www.oracle.com if you need additional information or have any
22 * questions.
23 *
24 */
25
26 #ifndef SHARE_MEMORY_METASPACE_BINLIST_HPP
27 #define SHARE_MEMORY_METASPACE_BINLIST_HPP
28
29 #include "utilities/align.hpp"
30 #include "utilities/debug.hpp"
31 #include "utilities/globalDefinitions.hpp"
32 #include "memory/metaspace/counter.hpp"
33 #include "memory/metaspace/metaspaceCommon.hpp"
34
35 namespace metaspace {
36
37 // BinList is a data structure to manage small to very small memory blocks
38 // (only a few words). It is used to manage deallocated blocks - see
39 // class FreeBlocks.
40
41 // Memory blocks are kept in linked lists. Each list
42 // contains blocks of only one size. There is a list for blocks of two words,
43 // for blocks of three words, etc. The list heads are kept in a vector,
44 // ordered by block size.
45 //
46
47 // wordsize
48 //
49 // +---+ +---+ +---+ +---+
50 // 1 | |-->| |-->| |-...->| |
51 // +---+ +---+ +---+ +---+
52 //
53 // +----+ +----+ +----+ +----+
54 // 2 | |-->| |-->| |-...->| |
55 // +----+ +----+ +----+ +----+
56 //
57 // +-----+ +-----+ +-----+ +-----+
58 // 3 | |-->| |-->| |-...->| |
59 // +-----+ +-----+ +-----+ +-----+
60 // .
61 // .
62 // .
63 //
64 // +----------+ +----------+ +----------+ +----------+
65 // n | |-->| |-->| |-...->| |
66 // +----------+ +----------+ +----------+ +----------+
67
68
69 // Insertion is of course fast, O(1).
70 //
71 // On retrieval, we attempt to find the closest fit to a given size, walking the
72 // list head vector (a bitmask is used to speed that part up).
73 //
74 // This structure is a bit expensive in memory costs (we pay one pointer per managed
75 // block size) so we only use it for a small number of sizes.
76
77 template <size_t smallest_size, int num_lists>
78 class BinListImpl {
79
80 struct block_t { block_t* next; size_t size; };
81
82 // a mask to speed up searching for populated lists.
83 // 0 marks an empty list, 1 for a non-empty one.
84 typedef uint32_t mask_t;
85 STATIC_ASSERT(num_lists <= sizeof(mask_t) * 8);
86
87 mask_t _mask;
88
89 // minimal block size must be large enough to hold a block.
90 STATIC_ASSERT(smallest_size * sizeof(MetaWord) >= sizeof(block_t));
91
92 public:
93
94 // block sizes this structure can keep are limited by [_min_block_size, _max_block_size)
95 const static size_t minimal_word_size = smallest_size;
96 const static size_t maximal_word_size = minimal_word_size + num_lists;
97
98 private:
99
100 block_t* _v[num_lists];
101
102 MemRangeCounter _counter;
103
104 static int index_for_word_size(size_t word_size) {
105 int index = (int)(word_size - minimal_word_size);
106 assert(index >= 0 && index < num_lists, "Invalid index %d", index);
107 return index;
108 }
109
110 static size_t word_size_for_index(int index) {
111 assert(index >= 0 && index < num_lists, "Invalid index %d", index);
112 return minimal_word_size + index;
113 }
114
115 // Search the range [index, _num_lists) for the smallest non-empty list. Returns -1 on fail.
116 int index_for_next_non_empty_list(int index) {
117 assert(index >= 0 && index < num_lists, "Invalid index %d", index);
118 int i2 = index;
119 mask_t m = _mask >> i2;
120 if (m > 0) {
121 // count leading zeros would be helpful.
122 while ((m & 1) == 0) {
123 assert(_v[i2] == NULL, "mask mismatch");
124 i2 ++;
125 m >>= 1;
126 }
127 // We must have found something.
128 assert(i2 < num_lists, "sanity.");
129 assert(_v[i2] != NULL, "mask mismatch");
130 return i2;
131 }
132 return -1;
133 }
134
135 void mask_set_bit(int bit) { _mask |= (((mask_t)1) << bit); }
136 void mask_clr_bit(int bit) { _mask &= ~(((mask_t)1) << bit); }
137
138 public:
139
140 BinListImpl() : _mask(0) {
141 for (int i = 0; i < num_lists; i ++) {
142 _v[i] = NULL;
143 }
144 }
145
146 void add_block(MetaWord* p, size_t word_size) {
147 assert(word_size >= minimal_word_size &&
148 word_size < maximal_word_size, "bad block size");
149 const int index = index_for_word_size(word_size);
150 block_t* b = (block_t*)p;
151 b->size = word_size;
152 b->next = _v[index];
153 _v[index] = b;
154 _counter.add(word_size);
155 mask_set_bit(index);
156 }
157
158 // Given a word_size, searches and returns a block of at least that size.
159 // Block may be larger. Real block size is returned in *p_real_word_size.
160 MetaWord* get_block(size_t word_size, size_t* p_real_word_size) {
161 assert(word_size >= minimal_word_size &&
162 word_size < maximal_word_size, "bad block size " SIZE_FORMAT ".", word_size);
163 int index = index_for_word_size(word_size);
164 index = index_for_next_non_empty_list(index);
165 if (index != -1) {
166 assert(_v[index] != NULL &&
167 _v[index]->size >= word_size, "sanity");
168
169 MetaWord* const p = (MetaWord*)_v[index];
170 const size_t real_word_size = word_size_for_index(index);
171
172 _v[index] = _v[index]->next;
173 if (_v[index] == NULL) {
174 mask_clr_bit(index);
175 }
176
177 _counter.sub(real_word_size);
178 *p_real_word_size = real_word_size;
179
180 return p;
181
182 } else {
183
184 *p_real_word_size = 0;
185 return NULL;
186
187 }
188 }
189
190
191 // Returns number of blocks in this structure
192 unsigned count() const { return _counter.count(); }
193
194 // Returns total size, in words, of all elements.
195 size_t total_size() const { return _counter.total_size(); }
196
197 bool is_empty() const { return _mask == 0; }
198
199 #ifdef ASSERT
200 void verify() const {
201 MemRangeCounter local_counter;
202 for (int i = 0; i < num_lists; i ++) {
203 assert(((_mask >> i) & 1) == ((_v[i] == 0) ? 0 : 1), "sanity");
204 const size_t s = minimal_word_size + i;
205 for (block_t* b = _v[i]; b != NULL; b = b->next) {
206 assert(b->size == s, "bad block size");
207 local_counter.add(s);
208 }
209 }
210 local_counter.check(_counter);
211 }
212 #endif // ASSERT
213
214
215 };
216
217 typedef BinListImpl<2, 8> BinList8;
218 typedef BinListImpl<2, 16> BinList16;
219 typedef BinListImpl<2, 32> BinList32;
220 typedef BinListImpl<2, 64> BinList64;
221
222 } // namespace metaspace
223
224 #endif // SHARE_MEMORY_METASPACE_BINLIST_HPP