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 (1 word)
45 //
46 // We want to manage many memory blocks of the same size, but we want
47 // to prevent the tree from blowing up and degenerating into a list. Therefore
48 // there is only one node for each unique block size; subsequent blocks of the
49 // same size are stacked below that first node:
50 //
51 // +-----+
52 // | 100 |
53 // +-----+
54 // / \
55 // +-----+
56 // | 80 |
57 // +-----+
58 // / | \
63 // +-----+
64 // | 80 |
65 // +-----+
66 //
67 //
68 // Todo: This tree is unbalanced. It would be a good fit for a red-black tree.
69 // In order to make this a red-black tree, we need an algorithm which can deal
70 // with nodes which are their own payload (most red-black tree implementations
71 // swap payloads of their nodes at some point, see e.g. j.u.TreeSet).
72 // A good example is the Linux kernel rbtree, which is a clean, easy-to-read
73 // implementation.
74
75 class BlockTree: public CHeapObj<mtMetaspace> {
76
77 struct Node {
78
79 static const intptr_t _canary_value =
80 NOT_LP64(0x4e4f4445) LP64_ONLY(0x4e4f44454e4f4445ULL); // "NODE" resp "NODENODE"
81
82 // Note: we afford us the luxury of an always-there canary value.
83 // The space for that is there (these nodes are only used to manage larger blocks,
84 // see FreeBlocks::MaxSmallBlocksWordSize).
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),
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_range(MetaWord* p, size_t word_size);
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(MetaWord* p, size_t word_size) {
349 DEBUG_ONLY(zap_range(p, word_size));
350 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size);
351 Node* n = new(p) Node(word_size);
352 if (_root == nullptr) {
353 _root = n;
354 } else {
355 insert(_root, n);
356 }
357 _counter.add(word_size);
358 }
359
360 // Given a word_size, search and return the smallest block that is equal or
361 // larger than that size. Upon return, *p_real_word_size contains the actual
362 // block size.
363 MetaWord* remove_block(size_t word_size, size_t* p_real_word_size) {
364 assert(word_size >= MinWordSize, "invalid block size " SIZE_FORMAT, word_size);
365
366 Node* n = find_closest_fit(word_size);
367
368 if (n != nullptr) {
369 DEBUG_ONLY(check_node(n);)
370 assert(n->_word_size >= word_size, "sanity");
371
372 if (n->_next != nullptr) {
373 // If the node is head of a chain of same sized nodes, we leave it alone
374 // and instead remove one of the follow up nodes (which is simpler than
375 // removing the chain head node and then having to graft the follow up
376 // node into its place in the tree).
377 n = remove_from_list(n);
378 } else {
379 remove_node_from_tree(n);
380 }
381
382 MetaWord* p = (MetaWord*)n;
383 *p_real_word_size = n->_word_size;
384
385 _counter.sub(n->_word_size);
386
387 DEBUG_ONLY(zap_range(p, n->_word_size));
388 return p;
389 }
390 return nullptr;
391 }
392
393 // Returns number of blocks in this structure
394 unsigned count() const { return _counter.count(); }
395
396 // Returns total size, in words, of all elements.
397 size_t total_size() const { return _counter.total_size(); }
398
399 bool is_empty() const { return _root == nullptr; }
400
401 DEBUG_ONLY(void print_tree(outputStream* st) const;)
402 DEBUG_ONLY(void verify() const;)
403 };
404
405 } // namespace metaspace
406
407 #endif // SHARE_MEMORY_METASPACE_BLOCKTREE_HPP
|
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 // / | \
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),
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
|