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"
31
32 namespace metaspace {
33
34 // Chunks live in a binary tree.
35 //
36
37 class ChunkClosure {
38 public:
39 // Return false to cancel traversal.
40 virtual bool do_chunk(Metachunk* chunk) = 0;
41 };
42
43
44 class ChunkTree {
45
46 typedef u2 ref_t;
47
48 // Root is either a direct pointer to a Metachunk* (in that case, a root chunk of max. size)
49 // or a pointer to a node.
50 ref_t _root;
51
52 struct btnode_t {
53
54 ref_t parent;
55 ref_t child[2];
56
57 };
58
59 typedef AbstractPool<btnode_t, ref_t> NodePoolType;
60 typedef AbstractPool<Metachunk, ref_t> ChunkPoolType;
61 NodePoolType _nodePool;
62 ChunkPoolType _chunkPool;
63
64 // The upper two bits of a reference encode information about it.
65 // bit 0,1: 00 - reference is a btnode_t
66 // 10 - reference is a free chunk
67 // 11 - reference is a chunk in use.
68 // This also means a reference has to get by with 14 bits. Which covers 16K, which is enough for both
69 // chunk headers and nodes within one root chunk area.
70 static const u2 highest_possible_index = (1 << 14) - 1;
71 static const u2 node_marker = 0;
72 static const u2 free_chunk_marker = 2;
73 static const u2 used_chunk_marker = 3;
74
75 static u2 get_raw_index_from_reference(ref_t ref) { return 0x3FFF & ref; }
76 static u2 get_info_from_reference(ref_t ref) { return 0xc000 & ref; }
77
78 static u2 encode_reference(u2 raw_idx, u2 info) {
79 assert(raw_idx <= highest_possible_index, "invalid index");
80 return (info << 14) | raw_idx;
81 }
82
83 #ifdef ASSERT
84 static bool reference_is_node(ref_t ref) { return get_info_from_reference(ref) == node_marker; }
85 static bool reference_is_chunk(ref_t ref) { u2 i = get_info_from_reference(ref); return i == free_chunk_marker || i == used_chunk_marker; }
86 static bool reference_is_used_chunk(ref_t ref) { return get_info_from_reference(ref) == used_chunk_marker; }
87
88 void check_is_valid_node_ref(ref_t ref) { assert(resolve_reference_to_node(ref) != NULL, "invalid node ref"); }
89 void check_is_valid_chunk_ref(ref_t ref) { assert(resolve_reference_to_chunk(ref) != NULL, "invalid chunk ref"); }
90 void check_is_valid_ref(ref_t ref);
91 #endif
92
93 static bool reference_is_free_chunk(ref_t ref) { return get_info_from_reference(ref) == free_chunk_marker; }
94
95 // Given a reference we know to be a node, resolve it to the node pointer.
96 btnode_t* resolve_reference_to_node(ref_t ref) const {
97 assert(reference_is_node(ref), "Not a node ref");
98 return _nodePool.elem_at_index(get_raw_index_from_reference(ref));
99 }
100
101 // Allocate a new node. Node is uninitialized.
102 // Returns pointer to node, and reference in ref.
103 btnode_t* allocate_new_node() {
104 return _nodePool.allocate_element();
105 }
106
107 // Given a node pointer, return its correctly encoded reference.
108 ref_t encode_reference_for_node(const btnode_t* n) const {
109 const u2 raw_idx = _nodePool.index_for_elem(n);
110 return encode_reference(raw_idx, node_marker);
111 }
112
113 // Release a node to the pool.
114 void release_node(btnode_t* n) {
115 _nodePool.return_element(n);
116 }
117
118 // Given a reference we know to be a chunk, resolve it to the chunk pointer.
119 Metachunk* resolve_reference_to_chunk(ref_t ref) const {
120 assert(reference_is_chunk(ref), "Not a chunk ref");
121 return _chunkPool.elem_at_index(get_raw_index_from_reference(ref));
122 }
123
124 // Allocate a new node. Node is uninitialized.
125 // Returns pointer to node, and reference in ref.
126 Metachunk* allocate_new_chunk() {
127 return _chunkPool.allocate_element();
128 }
129
130 // Given a chunk pointer, return its correctly encoded reference.
131 ref_t encode_reference_for_chunk(Metachunk* c, bool is_free) const {
132 const u2 raw_idx = _chunkPool.index_for_elem(c);
133 return encode_reference(raw_idx, is_free ? free_chunk_marker : used_chunk_marker);
134 }
135
136 // Release a chunk to the pool.
137 void release_chunk(Metachunk* c) {
138 _chunkPool.return_element(c);
139 }
140
141 //// Helpers for tree traversal ////
142
143 class ConstChunkClosure;
144 bool iterate_chunks_helper(ref_t ref, ChunkClosure* cc) const;
145
146 #ifdef ASSERT
147 // Verify a life node (one which lives in the tree).
148 void verify_node(const btnode_t* n) const;
149 // Helper for verify()
150 void verify_helper(bool slow, ref_t ref, const MetaWord* p, int* num_chunks, int* num_nodes) const;
151 #endif
152
153 // Given a chunk c, split it once.
154 //
155 // The original chunk must not be part of a freelist.
156 //
157 // Returns pointer to the result chunk; updates the splinters array to return the splintered off chunk.
158 //
159 // Returns NULL if chunk cannot be split any further.
160 Metachunk* split_once(Metachunk* c, Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS]);
161
162 // Given a chunk, attempt to merge it with its sibling if it is free.
163 // Returns pointer to the result chunk if successful, NULL otherwise.
164 //
165 // Returns number of merged chunks, by chunk level, in num_merged array. These numbers
166 // includes the original chunk.
167 //
168 // !!! Please note that if this method returns a non-NULL value, the
169 // original chunk will be invalid and should not be accessed anymore! !!!
170 Metachunk* merge_once(Metachunk* c, int num_merged[chklvl::NUM_CHUNK_LEVELS]);
171
172 public:
173
174 ChunkTree();
175
176 // Initialize: allocate a root node and a root chunk header; return the
177 // root chunk header. It will be partly initialized.
178 // Note: this just allocates a memory-less header; memory itself is allocated inside VirtualSpaceNode.
179 Metachunk* alloc_root_chunk_header();
180
181 // Given a chunk c, split it recursively until you get a chunk of the given target_level.
182 //
183 // The original chunk must not be part of a freelist.
184 //
185 // Returns pointer to the result chunk; returns split off chunks in splinters array.
186 //
187 // Returns NULL if chunk cannot be split at least once.
188 Metachunk* split(chklvl_t target_level, Metachunk* c, Metachunk* splinters[chklvl::NUM_CHUNK_LEVELS]);
189
190 // Given a chunk, attempt to merge it recursively with its neighboring chunks.
191 //
192 // If successful (merged at least once), returns address of
193 // the merged chunk; NULL otherwise.
194 //
195 // The merged chunks are removed from their freelist; the number of merged chunks is
196 // returned, split by level, in num_merged array. Note that these numbers does not
197 // include the original chunk.
198 //
199 // !!! Please note that if this method returns a non-NULL value, the
200 // original chunk will be invalid and should not be accessed anymore! !!!
201 Metachunk* merge(Metachunk* c, int num_merged[chklvl::NUM_CHUNK_LEVELS]);
202
203 //// tree traversal ////
204
205 // Iterate over all nodes in this tree. Returns true for complete traversal,
206 // false if traversal was cancelled.
207 bool iterate_chunks(ChunkClosure* cc) const;
208
209
210 //// Debug stuff ////
211
212 // Verify tree. If base != NULL, it should point to the location assumed
213 // to be base of the first chunk.
214 DEBUG_ONLY(void verify(bool slow, const MetaWord* base) const;)
215
216 // Returns the footprint of this tree, in words.
217 size_t memory_footprint_words() const;
218
219
220 };
221
222
223 ///////////////////////
224 // An C-heap allocated array of chunk trees. Used to describe fragmentation over a range of multiple root chunks.
225 class ChunkTreeArray {
226
227 const MetaWord* const _base;
228 const size_t _word_size;
229
230 ChunkTree** _arr;
231 int _num;
232
233 #ifdef ASSERT
234 void check_pointer(const MetaWord* p) const {
235 assert(p >= _base && p < _base + _word_size, "Invalid pointer");
236 }
237 #endif
238
239 int index_by_address(const MetaWord* p) const {
240 DEBUG_ONLY(check_pointer(p);)
241 return (p - _base) / chklvl::MAX_CHUNK_WORD_SIZE;
242 }
243
244 public:
245
246 // Create an array of ChunkTree objects, all initialized to NULL, covering
247 // a given memory range. Memory range must be aligned to size of root chunks.
248 ChunkTreeArray(const MetaWord* base, size_t word_size);
249
250 ~ChunkTreeArray();
251
252 // Given a memory address into the range the trees cover, return the corresponding
253 // tree. If none existed at this position, create it.
254 ChunkTree* get_tree_by_address(const MetaWord* p) const {
255 assert(p >= _base && p < _base + _word_size, "Invalid pointer");
256 const int idx = index_by_address(p);
257 assert(idx >= 0 && idx < _num, "Invalid index");
258 if (_arr[idx] == NULL) {
259 _arr[idx] = new ChunkTree();
260 }
261 return _arr[idx];
262 }
263
264 // Iterate over all nodes in all trees. Returns true for complete traversal,
265 // false if traversal was cancelled.
266 bool iterate_chunks(ChunkClosure* cc) const;
267
268 DEBUG_ONLY(void verify(bool slow) const;)
269
270 // Returns the footprint of all trees in this array, in words.
271 size_t memory_footprint_words() const;
272
273 };
274
275
276 } // namespace metaspace
277
278 #endif // SHARE_MEMORY_METASPACE_CHUNKTREE_HPP