1 /*
2 * Copyright (c) 2020, 2023, 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_BLOCKTREE_HPP
27 #define SHARE_MEMORY_METASPACE_BLOCKTREE_HPP
28
29 #include "memory/allocation.hpp"
30 #include "memory/metaspace/chunklevel.hpp"
31 #include "memory/metaspace/counters.hpp"
32 #include "utilities/debug.hpp"
33 #include "utilities/globalDefinitions.hpp"
34
35 namespace metaspace {
36
37 // BlockTree is a rather simple binary search tree. It is used to
38 // manage small to medium free memory blocks (see class FreeBlocks).
39 //
40 // There is no separation between payload (managed blocks) and nodes: the
41 // memory blocks themselves are the nodes, with the block size being the key.
42 //
43 // We store node pointer information in these blocks when storing them. That
44 // imposes a minimum size to the managed memory blocks.
45 // See get_raw_word_size_for_requested_word_size() (msCommon.hpp).
46 //
47 // We want to manage many memory blocks of the same size, but we want
48 // to prevent the tree from blowing up and degenerating into a list. Therefore
49 // there is only one node for each unique block size; subsequent blocks of the
50 // same size are stacked below that first node:
51 //
52 // +-----+
53 // | 100 |
54 // +-----+
55 // / \
56 // +-----+
57 // | 80 |
58 // +-----+
59 // / | \
60 // / +-----+ \
61 // +-----+ | 80 | +-----+
62 // | 70 | +-----+ | 85 |
63 // +-----+ | +-----+
64 // +-----+
65 // | 80 |
66 // +-----+
67 //
68 //
69 // Todo: This tree is unbalanced. It would be a good fit for a red-black tree.
70 // In order to make this a red-black tree, we need an algorithm which can deal
71 // with nodes which are their own payload (most red-black tree implementations
72 // swap payloads of their nodes at some point, see e.g. j.u.TreeSet).
73 // A good example is the Linux kernel rbtree, which is a clean, easy-to-read
74 // implementation.
75
76 class BlockTree: public CHeapObj<mtMetaspace> {
77
78 struct Node {
79
80 static const intptr_t _canary_value =
81 NOT_LP64(0x4e4f4445) LP64_ONLY(0x4e4f44454e4f4445ULL); // "NODE" resp "NODENODE"
82
83 // Note: we afford us the luxury of an always-there canary value.
84 // The space for that is there (these nodes are only used to manage larger blocks,
85 // see FreeBlocks::MaxSmallBlocksWordSize).
86 // It is initialized in debug and release, but only automatically tested
87 // in debug.
88 const intptr_t _canary;
89
90 // Normal tree node stuff...
91 // (Note: all null if this is a stacked node)
92 Node* _parent;
93 Node* _left;
94 Node* _right;
95
96 // Blocks with the same size are put in a list with this node as head.
97 Node* _next;
98
99 // Word size of node. Note that size cannot be larger than max metaspace size,
100 // so this could be very well a 32bit value (in case we ever make this a balancing
101 // tree and need additional space for weighting information).
102 const size_t _word_size;
103
104 Node(size_t word_size) :
105 _canary(_canary_value),
106 _parent(nullptr),
107 _left(nullptr),
108 _right(nullptr),
109 _next(nullptr),
110 _word_size(word_size)
111 {}
112
113 #ifdef ASSERT
114 bool valid() const {
115 return _canary == _canary_value &&
116 _word_size >= sizeof(Node) &&
117 _word_size < chunklevel::MAX_CHUNK_WORD_SIZE;
118 }
119 #endif
120 };
121
122 // Needed for verify() and print_tree()
123 struct walkinfo;
124
125 #ifdef ASSERT
126 // Run a quick check on a node; upon suspicion dive into a full tree check.
127 void check_node(const Node* n) const { if (!n->valid()) verify(); }
128 #endif
129
130 public:
131
132 // Minimum word size a block has to be to be added to this structure (note ceil division).
133 const static size_t MinWordSize =
134 (sizeof(Node) + sizeof(MetaWord) - 1) / sizeof(MetaWord);
135
136 private:
137
138 Node* _root;
139
140 MemRangeCounter _counter;
141
142 // Given a node n, add it to the list starting at head
143 static void add_to_list(Node* n, Node* head) {
144 assert(head->_word_size == n->_word_size, "sanity");
145 n->_next = head->_next;
146 head->_next = n;
147 DEBUG_ONLY(n->_left = n->_right = n->_parent = nullptr;)
148 }
149
150 // Given a node list starting at head, remove one of the follow up nodes from
151 // that list and return it. The head node gets not modified and remains in the
152 // tree.
153 // List must contain at least one other node.
154 static Node* remove_from_list(Node* head) {
155 assert(head->_next != nullptr, "sanity");
156 Node* n = head->_next;
157 head->_next = n->_next;
158 return n;
159 }
160
161 // Given a node c and a node p, wire up c as left child of p.
162 static void set_left_child(Node* p, Node* c) {
163 p->_left = c;
164 if (c != nullptr) {
165 assert(c->_word_size < p->_word_size, "sanity");
166 c->_parent = p;
167 }
168 }
169
170 // Given a node c and a node p, wire up c as right child of p.
171 static void set_right_child(Node* p, Node* c) {
172 p->_right = c;
173 if (c != nullptr) {
174 assert(c->_word_size > p->_word_size, "sanity");
175 c->_parent = p;
176 }
177 }
178
179 // Given a node n, return its successor in the tree
180 // (node with the next-larger size).
181 static Node* successor(Node* n) {
182 Node* succ = nullptr;
183 if (n->_right != nullptr) {
184 // If there is a right child, search the left-most
185 // child of that child.
186 succ = n->_right;
187 while (succ->_left != nullptr) {
188 succ = succ->_left;
189 }
190 } else {
191 succ = n->_parent;
192 Node* n2 = n;
193 // As long as I am the right child of my parent, search upward
194 while (succ != nullptr && n2 == succ->_right) {
195 n2 = succ;
196 succ = succ->_parent;
197 }
198 }
199 return succ;
200 }
201
202 // Given a node, replace it with a replacement node as a child for its parent.
203 // If the node is root and has no parent, sets it as root.
204 void replace_node_in_parent(Node* child, Node* replace) {
205 Node* parent = child->_parent;
206 if (parent != nullptr) {
207 if (parent->_left == child) { // Child is left child
208 set_left_child(parent, replace);
209 } else {
210 set_right_child(parent, replace);
211 }
212 } else {
213 assert(child == _root, "must be root");
214 _root = replace;
215 if (replace != nullptr) {
216 replace->_parent = nullptr;
217 }
218 }
219 return;
220 }
221
222 // Given a node n and an insertion point, insert n under insertion point.
223 void insert(Node* insertion_point, Node* n) {
224 assert(n->_parent == nullptr, "Sanity");
225 for (;;) {
226 DEBUG_ONLY(check_node(insertion_point);)
227 if (n->_word_size == insertion_point->_word_size) {
228 add_to_list(n, insertion_point); // parent stays null in this case.
229 break;
230 } else if (n->_word_size > insertion_point->_word_size) {
231 if (insertion_point->_right == nullptr) {
232 set_right_child(insertion_point, n);
233 break;
234 } else {
235 insertion_point = insertion_point->_right;
236 }
237 } else {
238 if (insertion_point->_left == nullptr) {
239 set_left_child(insertion_point, n);
240 break;
241 } else {
242 insertion_point = insertion_point->_left;
243 }
244 }
245 }
246 }
247
248 // Given a node and a wish size, search this node and all children for
249 // the node closest (equal or larger sized) to the size s.
250 Node* find_closest_fit(Node* n, size_t s) {
251 Node* best_match = nullptr;
252 while (n != nullptr) {
253 DEBUG_ONLY(check_node(n);)
254 if (n->_word_size >= s) {
255 best_match = n;
256 if (n->_word_size == s) {
257 break; // perfect match or max depth reached
258 }
259 n = n->_left;
260 } else {
261 n = n->_right;
262 }
263 }
264 return best_match;
265 }
266
267 // Given a wish size, search the whole tree for a
268 // node closest (equal or larger sized) to the size s.
269 Node* find_closest_fit(size_t s) {
270 if (_root != nullptr) {
271 return find_closest_fit(_root, s);
272 }
273 return nullptr;
274 }
275
276 // Given a node n, remove it from the tree and repair tree.
277 void remove_node_from_tree(Node* n) {
278 assert(n->_next == nullptr, "do not delete a node which has a non-empty list");
279
280 if (n->_left == nullptr && n->_right == nullptr) {
281 replace_node_in_parent(n, nullptr);
282
283 } else if (n->_left == nullptr && n->_right != nullptr) {
284 replace_node_in_parent(n, n->_right);
285
286 } else if (n->_left != nullptr && n->_right == nullptr) {
287 replace_node_in_parent(n, n->_left);
288
289 } else {
290 // Node has two children.
291
292 // 1) Find direct successor (the next larger node).
293 Node* succ = successor(n);
294
295 // There has to be a successor since n->right was != null...
296 assert(succ != nullptr, "must be");
297
298 // ... and it should not have a left child since successor
299 // is supposed to be the next larger node, so it must be the mostleft node
300 // in the sub tree rooted at n->right
301 assert(succ->_left == nullptr, "must be");
302 assert(succ->_word_size > n->_word_size, "sanity");
303
304 Node* successor_parent = succ->_parent;
305 Node* successor_right_child = succ->_right;
306
307 // Remove successor from its parent.
308 if (successor_parent == n) {
309
310 // special case: successor is a direct child of n. Has to be the right child then.
311 assert(n->_right == succ, "sanity");
312
313 // Just replace n with this successor.
314 replace_node_in_parent(n, succ);
315
316 // Take over n's old left child, too.
317 // We keep the successor's right child.
318 set_left_child(succ, n->_left);
319 } else {
320 // If the successors parent is not n, we are deeper in the tree,
321 // the successor has to be the left child of its parent.
322 assert(successor_parent->_left == succ, "sanity");
323
324 // The right child of the successor (if there was one) replaces
325 // the successor at its parent's left child.
326 set_left_child(successor_parent, succ->_right);
327
328 // and the successor replaces n at its parent
329 replace_node_in_parent(n, succ);
330
331 // and takes over n's old children
332 set_left_child(succ, n->_left);
333 set_right_child(succ, n->_right);
334 }
335 }
336 }
337
338 #ifdef ASSERT
339 void zap_range(MetaWord* p, size_t word_size);
340 // Helper for verify()
341 void verify_node_pointer(const Node* n) const;
342 #endif // ASSERT
343
344 public:
345
346 BlockTree() : _root(nullptr) {}
347
348 // Add a memory block to the tree. Its content will be overwritten.
349 void add_block(MetaWord* p, size_t word_size) {
350 DEBUG_ONLY(zap_range(p, word_size));
351 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size);
352 Node* n = new(p) Node(word_size);
353 if (_root == nullptr) {
354 _root = n;
355 } else {
356 insert(_root, n);
357 }
358 _counter.add(word_size);
359 }
360
361 // Given a word_size, search and return the smallest block that is equal or
362 // larger than that size. Upon return, *p_real_word_size contains the actual
363 // block size.
364 MetaWord* remove_block(size_t word_size, size_t* p_real_word_size) {
365 assert(word_size > 0, "invalid block size " SIZE_FORMAT, word_size);
366
367 Node* n = find_closest_fit(word_size);
368
369 if (n != nullptr) {
370 DEBUG_ONLY(check_node(n);)
371 assert(n->_word_size >= word_size, "sanity");
372
373 if (n->_next != nullptr) {
374 // If the node is head of a chain of same sized nodes, we leave it alone
375 // and instead remove one of the follow up nodes (which is simpler than
376 // removing the chain head node and then having to graft the follow up
377 // node into its place in the tree).
378 n = remove_from_list(n);
379 } else {
380 remove_node_from_tree(n);
381 }
382
383 MetaWord* p = (MetaWord*)n;
384 *p_real_word_size = n->_word_size;
385
386 _counter.sub(n->_word_size);
387
388 DEBUG_ONLY(zap_range(p, n->_word_size));
389 return p;
390 }
391 return nullptr;
392 }
393
394 // Returns number of blocks in this structure
395 unsigned count() const { return _counter.count(); }
396
397 // Returns total size, in words, of all elements.
398 size_t total_size() const { return _counter.total_size(); }
399
400 bool is_empty() const { return _root == nullptr; }
401
402 DEBUG_ONLY(void print_tree(outputStream* st) const;)
403 DEBUG_ONLY(void verify() const;)
404 };
405
406 } // namespace metaspace
407
408 #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP