1 /*
2 * Copyright (c) 2020, 2023, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2020 SAP SE. All rights reserved.
4 * Copyright (c) 2023 Red Hat, Inc. All rights reserved.
5 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
6 *
7 * This code is free software; you can redistribute it and/or modify it
8 * under the terms of the GNU General Public License version 2 only, as
9 * published by the Free Software Foundation.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 *
25 */
26
27 #ifndef SHARE_MEMORY_METASPACE_BINLIST_HPP
28 #define SHARE_MEMORY_METASPACE_BINLIST_HPP
29
30 #include "memory/metaspace/counters.hpp"
31 #include "memory/metaspace/metablock.hpp"
32 #include "memory/metaspace/metaspaceCommon.hpp"
33 #include "utilities/align.hpp"
34 #include "utilities/debug.hpp"
35 #include "utilities/globalDefinitions.hpp"
36
37 namespace metaspace {
38
39 // BinList is a data structure to manage small to very small memory blocks
40 // (only a few words). It is used to manage deallocated small blocks.
41
42 // Memory blocks are kept in a vector of linked lists of equi-sized blocks:
43 //
44 // wordsize
45 //
46 // +---+ +---+ +---+ +---+
47 // 1 | |-->| |-->| |-...->| |
48 // +---+ +---+ +---+ +---+
49 //
50 // +----+ +----+ +----+ +----+
51 // 2 | |-->| |-->| |-...->| |
52 // +----+ +----+ +----+ +----+
53 //
54 // +-----+ +-----+ +-----+ +-----+
55 // 3 | |-->| |-->| |-...->| |
56 // +-----+ +-----+ +-----+ +-----+
57 // .
58 // .
59 // .
60 //
61 // +----------+ +----------+ +----------+ +----------+
62 // n | |-->| |-->| |-...->| |
63 // +----------+ +----------+ +----------+ +----------+
64
65 // Insertion is of course fast, O(1).
66 //
67 // On retrieval, we attempt to find the closest fit to a given size, walking the
68 // list head vector (a bitmask is used to speed that part up).
69 //
70 // This structure is a bit expensive in memory costs (we pay one pointer per managed
71 // block size) so we only use it for a small number of sizes.
72
73 template <int num_lists>
74 class BinListImpl {
75
76 struct Block {
77 Block* const _next;
78 Block(Block* next) : _next(next) {}
79 };
80
81 #define BLOCK_FORMAT "Block @" PTR_FORMAT ": size: " SIZE_FORMAT ", next: " PTR_FORMAT
82 #define BLOCK_FORMAT_ARGS(b, sz) p2i(b), (sz), p2i((b)->_next)
83
84 // Block size must be exactly one word size.
85 STATIC_ASSERT(sizeof(Block) == BytesPerWord);
86 STATIC_ASSERT(num_lists > 0);
87
88 public:
89
90 // Minimal word size a block must have to be manageable by this structure.
91 const static size_t MinWordSize = 1;
92
93 // Maximal (incl) word size a block can have to be manageable by this structure.
94 const static size_t MaxWordSize = num_lists;
95
96 private:
97
98 Block* _blocks[num_lists];
99
100 MemRangeCounter _counter;
101
102 // Given a word size, returns the index of the list holding blocks of that size
103 static int index_for_word_size(size_t word_size) {
104 int index = (int)(word_size - MinWordSize);
105 assert(index >= 0 && index < num_lists, "Invalid index %d", index);
106 return index;
107 }
108
109 // Given an index of a list, return the word size that list serves
110 static size_t word_size_for_index(int index) {
111 assert(index >= 0 && index < num_lists, "Invalid index %d", index);
112 return index + MinWordSize;
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 while (i2 < num_lists && _blocks[i2] == nullptr) {
120 i2 ++;
121 }
122 return i2 == num_lists ? -1 : i2;
123 }
124
125 #ifdef ASSERT
126 static const uintptr_t canary = 0xFFEEFFEE;
127 static void write_canary(MetaWord* p, size_t word_size) {
128 if (word_size > 1) { // 1-word-sized blocks have no space for a canary
129 ((uintptr_t*)p)[word_size - 1] = canary;
130 }
131 }
132 static bool check_canary(const Block* b, size_t word_size) {
133 return word_size == 1 || // 1-word-sized blocks have no space for a canary
134 ((const uintptr_t*)b)[word_size - 1] == canary;
135 }
136 #endif
137
138 public:
139
140 BinListImpl() {
141 for (int i = 0; i < num_lists; i++) {
142 _blocks[i] = nullptr;
143 }
144 }
145
146 void add_block(MetaBlock mb) {
147 assert(!mb.is_empty(), "Don't add empty blocks");
148 const size_t word_size = mb.word_size();
149 MetaWord* const p = mb.base();
150 assert(word_size >= MinWordSize &&
151 word_size <= MaxWordSize, "bad block size");
152 DEBUG_ONLY(write_canary(p, word_size);)
153 const int index = index_for_word_size(word_size);
154 Block* old_head = _blocks[index];
155 Block* new_head = new (p) Block(old_head);
156 _blocks[index] = new_head;
157 _counter.add(word_size);
158 }
159
160 // Given a word_size, searches and returns a block of at least that size.
161 // Block may be larger.
162 MetaBlock remove_block(size_t word_size) {
163 assert(word_size >= MinWordSize &&
164 word_size <= MaxWordSize, "bad block size " SIZE_FORMAT ".", word_size);
165 MetaBlock result;
166 int index = index_for_word_size(word_size);
167 index = index_for_next_non_empty_list(index);
168 if (index != -1) {
169 Block* b = _blocks[index];
170 const size_t real_word_size = word_size_for_index(index);
171 assert(b != nullptr, "Sanity");
172 assert(check_canary(b, real_word_size),
173 "bad block in list[%d] (" BLOCK_FORMAT ")", index, BLOCK_FORMAT_ARGS(b, real_word_size));
174 _blocks[index] = b->_next;
175 _counter.sub(real_word_size);
176 result = MetaBlock((MetaWord*)b, real_word_size);
177 }
178 return result;
179 }
180
181 // Returns number of blocks in this structure
182 unsigned count() const { return _counter.count(); }
183
184 // Returns total size, in words, of all elements.
185 size_t total_size() const { return _counter.total_size(); }
186
187 bool is_empty() const { return count() == 0; }
188
189 #ifdef ASSERT
190 void verify() const {
191 MemRangeCounter local_counter;
192 for (int i = 0; i < num_lists; i++) {
193 const size_t s = word_size_for_index(i);
194 int pos = 0;
195 Block* b_last = nullptr; // catch simple circularities
196 for (Block* b = _blocks[i]; b != nullptr; b = b->_next, pos++) {
197 assert(check_canary(b, s), "");
198 assert(b != b_last, "Circle");
199 local_counter.add(s);
200 b_last = b;
201 }
202 if (UseNewCode)printf("\n");
203 }
204 local_counter.check(_counter);
205 }
206 #endif // ASSERT
207
208 };
209
210 typedef BinListImpl<32> BinList32;
211
212 } // namespace metaspace
213
214 #endif // SHARE_MEMORY_METASPACE_BINLIST_HPP