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