1 /*
2 * Copyright (c) 2018, 2020, Oracle and/or its affiliates. All rights reserved.
3 * Copyright (c) 2018, 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 #include "precompiled.hpp"
27
28 //#define LOG_PLEASE
29
30 #include "metaspace/metaspace_sparsearray.hpp"
31 #include "metaspace/metaspaceTestsCommon.hpp"
32 #include "metaspace/metaspaceTestContexts.hpp"
33
34
35 class ChunkManagerRandomChunkAllocTest {
36
37 static const size_t max_footprint_words = 8 * M;
38
39 ChunkTestsContext _helper;
40
41 // All allocated live chunks
42 typedef SparseArray<Metachunk*> SparseArrayOfChunks;
43 SparseArrayOfChunks _chunks;
44
45 const ChunkLevelRange _chunklevel_range;
46 const float _commit_factor;
47
48 // Depending on a probability pattern, come up with a reasonable limit to number of live chunks
49 static int max_num_live_chunks(ChunkLevelRange r, float commit_factor) {
50 // Assuming we allocate only the largest type of chunk, committed to the fullest commit factor,
51 // how many chunks can we accomodate before hitting max_footprint_words?
52 const size_t largest_chunk_size = word_size_for_level(r.lowest());
53 int max_chunks = (max_footprint_words * commit_factor) / largest_chunk_size;
54 // .. but cap at (min) 50 and (max) 1000
55 max_chunks = MIN2(1000, max_chunks);
56 max_chunks = MAX2(50, max_chunks);
57 return max_chunks;
58 }
59
60 // Return true if, after an allocation error happened, a reserve error seems likely.
61 bool could_be_reserve_error() {
62 return _helper.vslist().is_full();
63 }
64
65 // Return true if, after an allocation error happened, a commit error seems likely.
66 bool could_be_commit_error(size_t additional_word_size) {
67
68 // could it be commit limit hit?
69
70 if (Settings::new_chunks_are_fully_committed()) {
71 // For all we know we may have just failed to fully-commit a new root chunk.
72 additional_word_size = MAX_CHUNK_WORD_SIZE;
73 }
74
75 // Note that this is difficult to verify precisely, since there are
76 // several layers of truth:
77 // a) at the lowest layer (RootChunkArea) we have a bitmap of committed granules;
78 // b) at the vslist layer, we keep running counters of committed/reserved words;
79 // c) at the chunk layer, we keep a commit watermark (committed_words).
80 //
81 // (a) should mirror reality.
82 // (a) and (b) should be precisely in sync. This is tested by
83 // VirtualSpaceList::verify().
84 // (c) can be, by design, imprecise (too low).
85 //
86 // Here, I check (b) and trust it to be correct. We also call vslist::verify().
87 DEBUG_ONLY(_helper.verify();)
88
89 const size_t commit_add = align_up(additional_word_size, Settings::commit_granule_words());
90 if (_helper.commit_limit() <= (commit_add + _helper.vslist().committed_words())) {
91 return true;
92 }
93
94 return false;
95
96 }
97
98 // Given a chunk level and a factor, return a random commit size.
99 static size_t random_committed_words(chunklevel_t lvl, float commit_factor) {
100 const size_t sz = word_size_for_level(lvl) * commit_factor;
101 if (sz < 2) {
102 return 0;
103 }
104 return MIN2(SizeRange(sz).random_value(), sz);
105 }
106
107
108 //// Chunk allocation ////
109
110 // Given an slot index, allocate a random chunk and set it into that slot. Slot must be empty.
111 // Returns false if allocation fails.
112 bool allocate_random_chunk_at(int slot) {
113
114 DEBUG_ONLY(_chunks.check_slot_is_null(slot);)
115
116 const ChunkLevelRange r = _chunklevel_range.random_subrange();
117 const chunklevel_t pref_level = r.lowest();
118 const chunklevel_t max_level = r.highest();
119 const size_t min_committed = random_committed_words(max_level, _commit_factor);
120
121 Metachunk* c = NULL;
122 _helper.alloc_chunk(&c, r.lowest(), r.highest(), min_committed);
123 if (c == NULL) {
124 EXPECT_TRUE(could_be_reserve_error() ||
125 could_be_commit_error(min_committed));
126 LOG("Alloc chunk at %d failed.", slot);
127 return false;
128 }
129
130 _chunks.set_at(slot, c);
131
132 LOG("Allocated chunk at %d: " METACHUNK_FORMAT ".", slot, METACHUNK_FORMAT_ARGS(c));
133
134 return true;
135
136 }
137
138 // Allocates a random number of random chunks
139 bool allocate_random_chunks() {
140 int to_alloc = 1 + IntRange(MAX2(1, _chunks.size() / 8)).random_value();
141 bool success = true;
142 int slot = _chunks.first_null_slot();
143 while (to_alloc > 0 && slot != -1 && success) {
144 success = allocate_random_chunk_at(slot);
145 slot = _chunks.next_null_slot(slot);
146 to_alloc --;
147 }
148 return success && to_alloc == 0;
149 }
150
151 bool fill_all_slots_with_random_chunks() {
152 bool success = true;
153 for (int slot = _chunks.first_null_slot();
154 slot != -1 && success; slot = _chunks.next_null_slot(slot)) {
155 success = allocate_random_chunk_at(slot);
156 }
157 return success;
158 }
159
160 //// Chunk return ////
161
162 // Given an slot index, return the chunk in that slot to the chunk manager.
163 void return_chunk_at(int slot) {
164 Metachunk* c = _chunks.at(slot);
165 LOG("Returning chunk at %d: " METACHUNK_FORMAT ".", slot, METACHUNK_FORMAT_ARGS(c));
166 _helper.return_chunk(c);
167 _chunks.set_at(slot, NULL);
168 }
169
170 // return a random number of chunks (at most a quarter of the full slot range)
171 void return_random_chunks() {
172 int to_free = 1 + IntRange(MAX2(1, _chunks.size() / 8)).random_value();
173 int index = _chunks.first_non_null_slot();
174 while (to_free > 0 && index != -1) {
175 return_chunk_at(index);
176 index = _chunks.next_non_null_slot(index);
177 to_free --;
178 }
179 }
180
181 void return_all_chunks() {
182 for (int slot = _chunks.first_non_null_slot();
183 slot != -1; slot = _chunks.next_non_null_slot(slot)) {
184 return_chunk_at(slot);
185 }
186 }
187
188 // adjust test if we change levels
189 STATIC_ASSERT(HIGHEST_CHUNK_LEVEL == CHUNK_LEVEL_1K);
190 STATIC_ASSERT(LOWEST_CHUNK_LEVEL == CHUNK_LEVEL_4M);
191
192 void one_test() {
193
194 fill_all_slots_with_random_chunks();
195 _chunks.shuffle();
196
197 IntRange rand(100);
198
199 for (int j = 0; j < 1000; j ++) {
200
201 bool force_alloc = false;
202 bool force_free = true;
203
204 bool do_alloc =
205 force_alloc ? true :
206 (force_free ? false : rand.random_value() >= 50);
207 force_alloc = force_free = false;
208
209 if (do_alloc) {
210 if (!allocate_random_chunks()) {
211 force_free = true;
212 }
213 } else {
214 return_random_chunks();
215 }
216
217 _chunks.shuffle();
218
219 }
220
221 return_all_chunks();
222
223 }
224
225
226 public:
227
228 // A test with no limits
229 ChunkManagerRandomChunkAllocTest(ChunkLevelRange r, float commit_factor)
230 : _helper(),
231 _chunks(max_num_live_chunks(r, commit_factor)),
232 _chunklevel_range(r),
233 _commit_factor(commit_factor)
234 {}
235
236 // A test with no reserve limit but commit limit
237 ChunkManagerRandomChunkAllocTest(size_t commit_limit,
238 ChunkLevelRange r, float commit_factor)
239 : _helper(commit_limit),
240 _chunks(max_num_live_chunks(r, commit_factor)),
241 _chunklevel_range(r),
242 _commit_factor(commit_factor)
243 {}
244
245 // A test with both reserve and commit limit
246 // ChunkManagerRandomChunkAllocTest(size_t commit_limit, size_t reserve_limit,
247 // ChunkLevelRange r, float commit_factor)
248 // : _helper(commit_limit, reserve_limit),
249 // _chunks(max_num_live_chunks(r, commit_factor)),
250 // _chunklevel_range(r),
251 // _commit_factor(commit_factor)
252 // {}
253
254
255 void do_tests() {
256 const int num_runs = 5;
257 for (int n = 0; n < num_runs; n ++) {
258 one_test();
259 }
260 }
261
262 };
263
264 #define DEFINE_TEST(name, range, commit_factor) \
265 TEST_VM(metaspace, chunkmanager_random_alloc_##name) { \
266 ChunkManagerRandomChunkAllocTest test(range, commit_factor); \
267 test.do_tests(); \
268 }
269
270 DEFINE_TEST(test_nolimit_1, ChunkLevelRanges::small_chunks(), 0.0f)
271 DEFINE_TEST(test_nolimit_2, ChunkLevelRanges::small_chunks(), 0.5f)
272 DEFINE_TEST(test_nolimit_3, ChunkLevelRanges::small_chunks(), 1.0f)
273
274 DEFINE_TEST(test_nolimit_4, ChunkLevelRanges::all_chunks(), 0.0f)
275 DEFINE_TEST(test_nolimit_5, ChunkLevelRanges::all_chunks(), 0.5f)
276 DEFINE_TEST(test_nolimit_6, ChunkLevelRanges::all_chunks(), 1.0f)
277
278 #define DEFINE_TEST_2(name, range, commit_factor) \
279 TEST_VM(metaspace, chunkmanager_random_alloc_##name) { \
280 const size_t commit_limit = 256 * K; \
281 ChunkManagerRandomChunkAllocTest test(commit_limit, range, commit_factor); \
282 test.do_tests(); \
283 }
284
285 DEFINE_TEST_2(test_with_limit_1, ChunkLevelRanges::small_chunks(), 0.0f)
286 DEFINE_TEST_2(test_with_limit_2, ChunkLevelRanges::small_chunks(), 0.5f)
287 DEFINE_TEST_2(test_with_limit_3, ChunkLevelRanges::small_chunks(), 1.0f)
288
289 DEFINE_TEST_2(test_with_limit_4, ChunkLevelRanges::all_chunks(), 0.0f)
290 DEFINE_TEST_2(test_with_limit_5, ChunkLevelRanges::all_chunks(), 0.5f)
291 DEFINE_TEST_2(test_with_limit_6, ChunkLevelRanges::all_chunks(), 1.0f)
292
293