1 /*
2 * Copyright (c) 2020, 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_MSFREECHUNKLIST_HPP
27 #define SHARE_MEMORY_METASPACE_MSFREECHUNKLIST_HPP
28
29 #include "memory/allocation.hpp"
30 #include "memory/metaspace/msChunklevel.hpp"
31 #include "memory/metaspace/msCounter.hpp"
32 #include "memory/metaspace/msMetachunk.hpp"
33 #include "memory/metaspace/msMetachunkList.hpp"
34
35 class outputStream;
36
37 namespace metaspace {
38
39 // This is the free list underlying the ChunkManager.
40 //
41 // Chunks are kept in a vector of double-linked double-headed lists
42 // (using Metachunk::prev/next). One list per chunk level exists.
43 //
44 // Chunks in these lists are roughly ordered: uncommitted chunks
45 // are added to the back of the list, fully or partially committed
46 // chunks to the front.
47 //
48 // (Small caveat: commit state of a chunk may change as a result of
49 // actions on neighboring chunks, if the chunk is smaller than a commit
50 // granule and therefore shares its granule with neighbors. So it may change
51 // after the chunk has been added to the list.
52 // It will never involuntarily uncommit: only chunks >= granule size are uncommitted.
53 // But it may get involuntarily committed if an in-granule neighbor is committed and
54 // causes committing of the whole granule.
55 // In practice this is not a big deal; it has very little consequence.)
56 //
57 // Beyond adding at either front or at back, we do not sort on insert, since the
58 // insert path is used during Metaspace reclamation which may happen at GC pause.
59 //
60 // During retrieval (at class loading), we search the list for a chunk of at least
61 // n committed words to satisfy the caller requested committed word size. We stop
62 // searching at the first fully uncommitted chunk.
63 //
64 // Note that even though this is an O(n) search, in practice this is not a problem:
65 // - in all likelihood the requested commit word size is way smaller than even a single
66 // commit granule, so 99% of all searches would end at the first chunk (which is either
67 // uncommitted or committed to at least one commit granule size).
68 // - in all likelihood chunks, when added to this list, are either fully committed
69 // or fully uncommitted (see Settings::uncommit_on_return_min_word_size()).
70 //
71 // Should we ever encounter situations where the O(n) search is a bottleneck, this
72 // structure can easily be optimized (e.g. a BST). But for now lets keep this simple.
73
74 class FreeChunkList {
75
76 Metachunk* _first;
77 Metachunk* _last;
78
79 IntCounter _num_chunks;
80 SizeCounter _committed_word_size;
81
82 void add_front(Metachunk* c) {
83 if (_first == NULL) {
84 assert(_last == NULL, "Sanity");
85 _first = _last = c;
86 c->set_prev(NULL);
87 c->set_next(NULL);
88 } else {
89 assert(_last != NULL, "Sanity");
90 c->set_next(_first);
91 c->set_prev(NULL);
92 _first->set_prev(c);
93 _first = c;
94 }
95 }
96
97 // Add chunk to the back of the list.
98 void add_back(Metachunk* c) {
99 if (_last == NULL) {
100 assert(_first == NULL, "Sanity");
101 _last = _first = c;
102 c->set_prev(NULL);
103 c->set_next(NULL);
104 } else {
105 assert(_first != NULL, "Sanity");
106 c->set_next(NULL);
107 c->set_prev(_last);
108 _last->set_next(c);
109 _last = c;
110 }
111 }
112
113 public:
114
115 FreeChunkList() :
116 _first(NULL),
117 _last(NULL)
118 {}
119
120 // Remove given chunk from anywhere in the list.
121 Metachunk* remove(Metachunk* c) {
122 assert(contains(c), "Must be contained here");
123 Metachunk* pred = c->prev();
124 Metachunk* succ = c->next();
125 if (pred) {
126 pred->set_next(succ);
127 }
128 if (succ) {
129 succ->set_prev(pred);
130 }
131 if (_first == c) {
132 _first = succ;
133 }
134 if (_last == c) {
135 _last = pred;
136 }
137 c->set_next(NULL);
138 c->set_prev(NULL);
139 _committed_word_size.decrement_by(c->committed_words());
140 _num_chunks.decrement();
141 return c;
142 }
143
144 void add(Metachunk* c) {
145 assert(contains(c) == false, "Chunk already in freelist");
146 assert(_first == NULL || _first->level() == c->level(), "wrong level");
147 // Uncomitted chunks go to the back, fully or partially committed to the front.
148 if (c->committed_words() == 0) {
149 add_back(c);
150 } else {
151 add_front(c);
152 }
153 _committed_word_size.increment_by(c->committed_words());
154 _num_chunks.increment();
155 }
156
157 // Removes the first chunk from the list and returns it. Returns NULL if list is empty.
158 Metachunk* remove_first() {
159 Metachunk* c = _first;
160 if (c != NULL) {
161 remove(c);
162 }
163 return c;
164 }
165
166 // Find and removes a chunk in this list which has at least min_committed_words committed words.
167 // Returns NULL if not found.
168 Metachunk* find_matching(size_t min_committed_words) {
169 Metachunk* c = _first;
170 while (c != NULL && c->committed_words() > 0) {
171 if (c->committed_words() <= min_committed_words) {
172 remove(c);
173 return c;
174 }
175 c = c->next();
176 }
177 return NULL;
178 }
179
180 // Returns reference to the first chunk in the list, or NULL
181 Metachunk* first() const { return _first; }
182
183 #ifdef ASSERT
184 bool contains(const Metachunk* c) const;
185 void verify() const;
186 #endif
187
188 // Returns number of chunks
189 int num_chunks() const { return _num_chunks.get(); }
190
191 // Returns total committed word size
192 size_t committed_word_size() const { return _committed_word_size.get(); }
193
194 void print_on(outputStream* st) const;
195
196 };
197
198 // A vector of free chunk lists, one per chunk level
199 class FreeChunkListVector {
200
201 FreeChunkList _lists[chunklevel::NUM_CHUNK_LEVELS];
202
203 const FreeChunkList* list_for_level(chunklevel_t lvl) const { DEBUG_ONLY(chunklevel::check_valid_level(lvl)); return _lists + lvl; }
204 FreeChunkList* list_for_level(chunklevel_t lvl) { DEBUG_ONLY(chunklevel::check_valid_level(lvl)); return _lists + lvl; }
205
206 const FreeChunkList* list_for_chunk(const Metachunk* c) const { return list_for_level(c->level()); }
207 FreeChunkList* list_for_chunk(const Metachunk* c) { return list_for_level(c->level()); }
208
209 public:
210
211 // Remove given chunk from its list. List must contain that chunk.
212 void remove(Metachunk* c) {
213 list_for_chunk(c)->remove(c);
214 }
215
216 // Remove first node unless empty. Returns node or NULL.
217 Metachunk* remove_first(chunklevel_t lvl) {
218 Metachunk* c = list_for_level(lvl)->remove_first();
219 return c;
220 }
221
222 void add(Metachunk* c) {
223 list_for_chunk(c)->add(c);
224 }
225
226 // Returns number of chunks for a given level.
227 int num_chunks_at_level(chunklevel_t lvl) const {
228 return list_for_level(lvl)->num_chunks();
229 }
230
231 // Returns number of chunks for a given level.
232 size_t committed_word_size_at_level(chunklevel_t lvl) const {
233 return list_for_level(lvl)->committed_word_size();
234 }
235
236 // Returns reference to first chunk at this level, or NULL if sublist is empty.
237 Metachunk* first_at_level(chunklevel_t lvl) const {
238 return list_for_level(lvl)->first();
239 }
240
241 // Look for a chunk: starting at level, up to and including max_level,
242 // return the first chunk whose committed words >= min_committed_words.
243 // Return NULL if no such chunk was found.
244 Metachunk* search_chunk_ascending(chunklevel_t level, chunklevel_t max_level,
245 size_t min_committed_words);
246
247 // Look for a chunk: starting at level, down to (including) the root chunk level,
248 // return the first chunk whose committed words >= min_committed_words.
249 // Return NULL if no such chunk was found.
250 Metachunk* search_chunk_descending(chunklevel_t level, size_t min_committed_words);
251
252 // Returns total size in all lists (regardless of commit state of underlying memory)
253 size_t word_size() const;
254
255 // Returns total committed size in all lists
256 size_t committed_word_size() const;
257
258 // Returns number of chunks in all lists
259 int num_chunks() const;
260
261 #ifdef ASSERT
262 bool contains(const Metachunk* c) const;
263 void verify() const;
264 #endif
265
266 void print_on(outputStream* st) const;
267
268 };
269
270 } // namespace metaspace
271
272 #endif // SHARE_MEMORY_METASPACE_MSFREECHUNKLIST_HPP