1 /*
2 * Copyright (c) 2018, 2019, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #ifndef SHARE_MEMORY_METASPACE_CHUNKTREE_HPP
26 #define SHARE_MEMORY_METASPACE_CHUNKTREE_HPP
27
28 #include "memory/metaspace/abstractPool.hpp"
29 #include "memory/metaspace/chunkLevel.hpp"
30 #include "memory/metaspace/metachunk.hpp" // For MetachunkPool
31
32 namespace metaspace {
33
34 // Chunks live in a quaternary tree.
35 //
36 // Each node has four child nodes.
37 // Leaf nodes are the chunk headers.
38
39 struct qtnode_t;
40
41 struct qtnode_t {
42
43 // parent node; NULL if this is a root node.
44 qtnode_t* parent;
45
46 // Child nodes can be either non-leaf itself, in which case they are qtnode_t*;
47 // or they are leaf nodes, in which case they are Metachunk*.
48 void* child[4];
49
50 // For the purpose of keeping this structure in a free list of the
51 // ChunkTreeNodePool, reuse the parent pointer as next (this only
52 // happens to dead nodes, so the parent pointer is not needed).
53 // See AbstractPool<> class.
54 qtnode_t* next() { return parent; }
55 void set_next(qtnode_t* n) { parent = n; }
56
57 #ifdef ASSERT
58 bool check_is_child(const void* p) const {
59 return child[0] == p || child[1] == p || child[2] == p || child[3] == p;
60 }
61 #endif
62
63 };
64
65 typedef AbstractPool<qtnode_t, uint32_t> ChunkTreeNodePool;
66
67 class ChunkTree {
68
69 // Root is either a direct pointer to a Metachunk* (in that case, a root chunk of max. size)
70 // or a pointer to a node.
71 void* _root;
72
73 /// Node allocation ///
74
75 static ChunkTreeNodePool _nodePool;
76
77 // Returns a new node. Node will be zero'd out completely.
78 static qtnode_t* allocate_node() {
79 qtnode_t* n = _nodePool.allocate_element();
80 memset(n, 0, sizeof(n));
81 return n;
82 }
83
84 static qtnode_t* release_node(qtnode_t* n) {
85 return _nodePool.return_element(n);
86 }
87
88 // Given a pointer to a child which can either be a Metachunk or a node, return a pointer to a
89 // node if it was a node; NULL if it was a Metachunk.
90 static qtnode_t* resolve_node_ptr(void* p) {
91 qtnode_t* n = (qtnode_t*)p;
92 if (_nodePool.is_valid_elem(n)) {
93 return n;
94 }
95 return NULL;
96 }
97
98 // Given a pointer to a child which can either be a Metachunk or a node, return a pointer to a
99 // node if it was a node; NULL if it was a Metachunk.
100 static Metachunk* resolve_chunk_ptr(void* p) {
101 Metachunk* c = (Metachunk*) p;
102 if (MetachunkPool::is_metachunk_pointer(c)) {
103 return c;
104 }
105 return NULL;
106 }
107
108 #ifdef ASSERT
109 // Verify a life node (one which lives in the tree).
110 static void verify_node(const qtnode_t* n);
111 static void verify_parenthood(const qtnode_t* child, const qtnode_t* parent);
112 // Given four leaf nodes, verify their chunks (must be adjacent and in order)
113 static void verify_sibling_chunks(const Metachunk* sibs[4]);
114 #endif
115
116
117 // Given a chunk c, split it into four smaller chunks.
118 // Returns pointer to the result chunk; splintered off chunks are appended to the given linked list.
119 // Returns NULL if chunk cannot be split.
120 Metachunk* split_once(Metachunk* c, Metachunk** p_splinters);
121
122 // Given a chunk, attempt to merge it with its siblings
123 // if they are free.
124 // Returns pointer to the result chunk if successful, NULL otherwise.
125 //
126 // !!! Please note that if this method returns a non-NULL value, the
127 // original chunk will be invalid and should not be accessed anymore! !!!
128 Metachunk* merge_once(Metachunk* c);
129
130
131 public:
132
133 ChunkTree() : _root(NULL) {}
134
135 // Initialize: allocate a root node and a root chunk header; return the
136 // root chunk header.
137 Metachunk* alloc_root();
138
139 // Given a chunk c, split it recursively until you get a chunk of the given target_level.
140 // Returns pointer to the result chunk; returns split off chunks in p_splinters as linked list.
141 // Returns NULL if chunk cannot be split at least once.
142 Metachunk* split(chklvl_t target_level, Metachunk* c, Metachunk** p_splinters);
143
144 // Given a chunk, attempt to merge it recursively with its neighboring chunks.
145 // If successful (merged at least once), returns address of
146 // the merged chunk; NULL otherwise.
147 //
148 // !!! Please note that if this method returns a non-NULL value, the
149 // original chunk will be invalid and should not be accessed anymore! !!!
150 Metachunk* merge(Metachunk* c);
151
152 //// tree traversal ////
153
154 class ConstNodeClosure {
155 public:
156 // Return false to cancel traversal.
157 virtual bool do_node(const qtnode_t* node) = 0;
158 };
159
160 class ConstChunkClosure {
161 public:
162 // Return false to cancel traversal.
163 virtual bool do_chunk(const Metachunk* c) = 0;
164 };
165
166
167 // Iterate over all leafs in this tree. Returns true for complete traversal,
168 // false if traversal was cancelled.
169 bool iterate_nodes(ConstNodeClosure* c) const;
170
171 // Iterate over all nodes in this tree. Returns true for complete traversal,
172 // false if traversal was cancelled.
173 bool iterate_chunks(ConstChunkClosure* c) const;
174
175
176 //// Debug stuff ////
177
178 DEBUG_ONLY(void verify(bool slow);)
179
180 };
181
182
183 ///////////////////////
184 // An C-heap allocated array of chunk trees. Used to describe fragmentation over a range of multiple root chunks.
185 class ChunkTreeArray {
186
187 const MetaWord* const _base;
188 const size_t _word_size;
189
190 ChunkTree* _arr;
191 int _num;
192
193 #ifdef ASSERT
194 void check_pointer(const MetaWord* p) const {
195 assert(p >= _base && p < _base + _word_size, "Invalid pointer");
196 }
197 #endif
198
199 int index_by_address(const MetaWord* p) const {
200 DEBUG_ONLY(check_pointer(p);)
201 return (p - _base) / chklvl::MAX_CHUNK_WORD_SIZE;
202 }
203
204 public:
205
206 // Create an array of ChunkTree objects, all initialized to NULL, covering
207 // a given memory range. Memory range must be aligned to size of root chunks.
208 ChunkTreeArray(const MetaWord* base, size_t word_size);
209
210 ~ChunkTreeArray();
211
212 // Given a memory address into the range the trees cover, return the corresponding
213 // tree. If none existed at this position, create it.
214 ChunkTree* get_tree_by_address(const MetaWord* p) const {
215 assert(p >= _base && p < _base + _word_size, "Invalid pointer");
216 const int idx = index_by_address(p);
217 assert(idx < _num, "Invalid index");
218 if (_arr[idx] == NULL) {
219 _arr[idx] = new ChunkTree();
220 }
221 return _arr[idx];
222 }
223
224 };
225
226
227 } // namespace metaspace
228
229 #endif // SHARE_MEMORY_METASPACE_CHUNKTREE_HPP