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