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/metaspaceCommon.hpp"
32 #include "utilities/align.hpp"
33 #include "utilities/debug.hpp"
34 #include "utilities/globalDefinitions.hpp"
35
36 namespace metaspace {
37
38 // BinList is a data structure to manage small to very small memory blocks
39 // (only a few words). It is used to manage deallocated blocks - see
40 // class FreeBlocks.
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(MetaWord* p, size_t word_size) {
147 assert(word_size >= MinWordSize &&
148 word_size <= MaxWordSize, "bad block size");
149 DEBUG_ONLY(write_canary(p, word_size);)
150 const int index = index_for_word_size(word_size);
151 Block* old_head = _blocks[index];
152 Block* new_head = new (p) Block(old_head);
153 _blocks[index] = new_head;
154 _counter.add(word_size);
155 }
156
157 // Given a word_size, searches and returns a block of at least that size.
158 // Block may be larger. Real block size is returned in *p_real_word_size.
159 MetaWord* remove_block(size_t word_size, size_t* p_real_word_size) {
160 assert(word_size >= MinWordSize &&
161 word_size <= MaxWordSize, "bad block size " SIZE_FORMAT ".", word_size);
162 int index = index_for_word_size(word_size);
163 index = index_for_next_non_empty_list(index);
164 if (index != -1) {
165 Block* b = _blocks[index];
166 const size_t real_word_size = word_size_for_index(index);
167 assert(b != nullptr, "Sanity");
168 assert(check_canary(b, real_word_size),
169 "bad block in list[%d] (" BLOCK_FORMAT ")", index, BLOCK_FORMAT_ARGS(b, real_word_size));
170 _blocks[index] = b->_next;
171 _counter.sub(real_word_size);
172 *p_real_word_size = real_word_size;
173 return (MetaWord*)b;
174 } else {
175 *p_real_word_size = 0;
176 return nullptr;
177 }
178 }
179
180 // Returns number of blocks in this structure
181 unsigned count() const { return _counter.count(); }
182
183 // Returns total size, in words, of all elements.
184 size_t total_size() const { return _counter.total_size(); }
185
186 bool is_empty() const { return count() == 0; }
187
188 #ifdef ASSERT
189 void verify() const {
190 MemRangeCounter local_counter;
191 for (int i = 0; i < num_lists; i++) {
192 const size_t s = word_size_for_index(i);
193 int pos = 0;
194 for (Block* b = _blocks[i]; b != nullptr; b = b->_next, pos++) {
195 assert(check_canary(b, s), "");
196 local_counter.add(s);
197 }
198 }
199 local_counter.check(_counter);
200 }
201 #endif // ASSERT
202
203 };
204
205 typedef BinListImpl<32> BinList32;
206
207 } // namespace metaspace
208
209 #endif // SHARE_MEMORY_METASPACE_BINLIST_HPP