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
--- EOF ---