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