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 "memory/metaspace/metablock.hpp"
33 #include "utilities/debug.hpp"
34 #include "utilities/globalDefinitions.hpp"
35
36 namespace metaspace {
37
38 // BlockTree is a rather simple binary search tree. It is used to
39 // manage medium to large free memory blocks.
40 //
41 // There is no separation between payload (managed blocks) and nodes: the
42 // memory blocks themselves are the nodes, with the block size being the key.
43 //
44 // We store node pointer information in these blocks when storing them. That
45 // imposes a minimum size to the managed memory blocks (1 word)
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 // It is initialized in debug and release, but only automatically tested
86 // in debug.
87 const intptr_t _canary;
88
89 // Normal tree node stuff...
90 // (Note: all null if this is a stacked node)
91 Node* _parent;
92 Node* _left;
93 Node* _right;
94
95 // Blocks with the same size are put in a list with this node as head.
96 Node* _next;
97
98 // Word size of node. Note that size cannot be larger than max metaspace size,
99 // so this could be very well a 32bit value (in case we ever make this a balancing
100 // tree and need additional space for weighting information).
101 const size_t _word_size;
102
103 Node(size_t word_size) :
104 _canary(_canary_value),
105 _parent(nullptr),
106 _left(nullptr),
107 _right(nullptr),
108 _next(nullptr),
109 _word_size(word_size)
110 {}
111
112 #ifdef ASSERT
113 bool valid() const {
114 return _canary == _canary_value &&
115 _word_size >= sizeof(Node) &&
116 _word_size < chunklevel::MAX_CHUNK_WORD_SIZE;
117 }
118 #endif
119 };
120
121 // Needed for verify() and print_tree()
122 struct walkinfo;
123
124 #ifdef ASSERT
125 // Run a quick check on a node; upon suspicion dive into a full tree check.
126 void check_node(const Node* n) const { if (!n->valid()) verify(); }
127 #endif
128
129 public:
130
131 // Minimum word size a block has to be to be added to this structure (note ceil division).
132 const static size_t MinWordSize =
133 (sizeof(Node) + sizeof(MetaWord) - 1) / sizeof(MetaWord);
134
135 private:
136
137 Node* _root;
138
139 MemRangeCounter _counter;
140
141 // Given a node n, add it to the list starting at head
142 static void add_to_list(Node* n, Node* head) {
143 assert(head->_word_size == n->_word_size, "sanity");
144 n->_next = head->_next;
145 head->_next = n;
146 DEBUG_ONLY(n->_left = n->_right = n->_parent = nullptr;)
147 }
148
149 // Given a node list starting at head, remove one of the follow up nodes from
150 // that list and return it. The head node gets not modified and remains in the
151 // tree.
152 // List must contain at least one other node.
153 static Node* remove_from_list(Node* head) {
154 assert(head->_next != nullptr, "sanity");
155 Node* n = head->_next;
156 head->_next = n->_next;
157 return n;
158 }
159
160 // Given a node c and a node p, wire up c as left child of p.
161 static void set_left_child(Node* p, Node* c) {
162 p->_left = c;
163 if (c != nullptr) {
164 assert(c->_word_size < p->_word_size, "sanity");
165 c->_parent = p;
166 }
167 }
168
169 // Given a node c and a node p, wire up c as right child of p.
170 static void set_right_child(Node* p, Node* c) {
171 p->_right = c;
172 if (c != nullptr) {
173 assert(c->_word_size > p->_word_size, "sanity");
174 c->_parent = p;
175 }
176 }
177
178 // Given a node n, return its successor in the tree
179 // (node with the next-larger size).
180 static Node* successor(Node* n) {
181 Node* succ = nullptr;
182 if (n->_right != nullptr) {
183 // If there is a right child, search the left-most
184 // child of that child.
185 succ = n->_right;
186 while (succ->_left != nullptr) {
187 succ = succ->_left;
188 }
189 } else {
190 succ = n->_parent;
191 Node* n2 = n;
192 // As long as I am the right child of my parent, search upward
193 while (succ != nullptr && n2 == succ->_right) {
194 n2 = succ;
195 succ = succ->_parent;
196 }
197 }
198 return succ;
199 }
200
201 // Given a node, replace it with a replacement node as a child for its parent.
202 // If the node is root and has no parent, sets it as root.
203 void replace_node_in_parent(Node* child, Node* replace) {
204 Node* parent = child->_parent;
205 if (parent != nullptr) {
206 if (parent->_left == child) { // Child is left child
207 set_left_child(parent, replace);
208 } else {
209 set_right_child(parent, replace);
210 }
211 } else {
212 assert(child == _root, "must be root");
213 _root = replace;
214 if (replace != nullptr) {
215 replace->_parent = nullptr;
216 }
217 }
218 return;
219 }
220
221 // Given a node n and an insertion point, insert n under insertion point.
222 void insert(Node* insertion_point, Node* n) {
223 assert(n->_parent == nullptr, "Sanity");
224 for (;;) {
225 DEBUG_ONLY(check_node(insertion_point);)
226 if (n->_word_size == insertion_point->_word_size) {
227 add_to_list(n, insertion_point); // parent stays null in this case.
228 break;
229 } else if (n->_word_size > insertion_point->_word_size) {
230 if (insertion_point->_right == nullptr) {
231 set_right_child(insertion_point, n);
232 break;
233 } else {
234 insertion_point = insertion_point->_right;
235 }
236 } else {
237 if (insertion_point->_left == nullptr) {
238 set_left_child(insertion_point, n);
239 break;
240 } else {
241 insertion_point = insertion_point->_left;
242 }
243 }
244 }
245 }
246
247 // Given a node and a wish size, search this node and all children for
248 // the node closest (equal or larger sized) to the size s.
249 Node* find_closest_fit(Node* n, size_t s) {
250 Node* best_match = nullptr;
251 while (n != nullptr) {
252 DEBUG_ONLY(check_node(n);)
253 if (n->_word_size >= s) {
254 best_match = n;
255 if (n->_word_size == s) {
256 break; // perfect match or max depth reached
257 }
258 n = n->_left;
259 } else {
260 n = n->_right;
261 }
262 }
263 return best_match;
264 }
265
266 // Given a wish size, search the whole tree for a
267 // node closest (equal or larger sized) to the size s.
268 Node* find_closest_fit(size_t s) {
269 if (_root != nullptr) {
270 return find_closest_fit(_root, s);
271 }
272 return nullptr;
273 }
274
275 // Given a node n, remove it from the tree and repair tree.
276 void remove_node_from_tree(Node* n) {
277 assert(n->_next == nullptr, "do not delete a node which has a non-empty list");
278
279 if (n->_left == nullptr && n->_right == nullptr) {
280 replace_node_in_parent(n, nullptr);
281
282 } else if (n->_left == nullptr && n->_right != nullptr) {
283 replace_node_in_parent(n, n->_right);
284
285 } else if (n->_left != nullptr && n->_right == nullptr) {
286 replace_node_in_parent(n, n->_left);
287
288 } else {
289 // Node has two children.
290
291 // 1) Find direct successor (the next larger node).
292 Node* succ = successor(n);
293
294 // There has to be a successor since n->right was != null...
295 assert(succ != nullptr, "must be");
296
297 // ... and it should not have a left child since successor
298 // is supposed to be the next larger node, so it must be the mostleft node
299 // in the sub tree rooted at n->right
300 assert(succ->_left == nullptr, "must be");
301 assert(succ->_word_size > n->_word_size, "sanity");
302
303 Node* successor_parent = succ->_parent;
304 Node* successor_right_child = succ->_right;
305
306 // Remove successor from its parent.
307 if (successor_parent == n) {
308
309 // special case: successor is a direct child of n. Has to be the right child then.
310 assert(n->_right == succ, "sanity");
311
312 // Just replace n with this successor.
313 replace_node_in_parent(n, succ);
314
315 // Take over n's old left child, too.
316 // We keep the successor's right child.
317 set_left_child(succ, n->_left);
318 } else {
319 // If the successors parent is not n, we are deeper in the tree,
320 // the successor has to be the left child of its parent.
321 assert(successor_parent->_left == succ, "sanity");
322
323 // The right child of the successor (if there was one) replaces
324 // the successor at its parent's left child.
325 set_left_child(successor_parent, succ->_right);
326
327 // and the successor replaces n at its parent
328 replace_node_in_parent(n, succ);
329
330 // and takes over n's old children
331 set_left_child(succ, n->_left);
332 set_right_child(succ, n->_right);
333 }
334 }
335 }
336
337 #ifdef ASSERT
338 void zap_block(MetaBlock block);
339 // Helper for verify()
340 void verify_node_pointer(const Node* n) const;
341 #endif // ASSERT
342
343 public:
344
345 BlockTree() : _root(nullptr) {}
346
347 // Add a memory block to the tree. Its content will be overwritten.
348 void add_block(MetaBlock block) {
349 DEBUG_ONLY(zap_block(block);)
350 const size_t word_size = block.word_size();
351 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size);
352 Node* n = new(block.base()) 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.
363 MetaBlock remove_block(size_t word_size) {
364 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size);
365
366 MetaBlock result;
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 result = MetaBlock((MetaWord*)n, n->_word_size);
384
385 _counter.sub(n->_word_size);
386
387 DEBUG_ONLY(zap_block(result);)
388 }
389 return result;
390 }
391
392 // Returns number of blocks in this structure
393 unsigned count() const { return _counter.count(); }
394
395 // Returns total size, in words, of all elements.
396 size_t total_size() const { return _counter.total_size(); }
397
398 bool is_empty() const { return _root == nullptr; }
399
400 DEBUG_ONLY(void print_tree(outputStream* st) const;)
401 DEBUG_ONLY(void verify() const;)
402 };
403
404 } // namespace metaspace
405
406 #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP