jdk

1
/*
2
 * Copyright (c) 2020, 2023 SAP SE. All rights reserved.
3
 * Copyright (c) 2020, 2024, Oracle and/or its affiliates. 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
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 = (int)((max_footprint_words * commit_factor) / (float) 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 possible.
65
  bool could_be_reserve_error() {
66
    return _context.reserve_limit() < max_uintx;
67
  }
68

69
  // Return true if, after an allocation error happened, a commit error seems likely.
70
  bool could_be_commit_error(size_t additional_word_size) {
71

72
    // could it be commit limit hit?
73

74
    // Note that this is difficult to verify precisely, since there are
75
    // several layers of truth:
76
    // a) at the lowest layer (RootChunkArea) we have a bitmap of committed granules;
77
    // b) at the vslist layer, we keep running counters of committed/reserved words;
78
    // c) at the chunk layer, we keep a commit watermark (committed_words).
79
    //
80
    // (a) should mirror reality.
81
    // (a) and (b) should be precisely in sync. This is tested by
82
    // VirtualSpaceList::verify().
83
    // (c) can be, by design, imprecise (too low).
84
    //
85
    // Here, I check (b) and trust it to be correct. We also call vslist::verify().
86
    DEBUG_ONLY(_context.verify();)
87

88
    const size_t commit_add = align_up(additional_word_size, Settings::commit_granule_words());
89
    if (_context.commit_limit() <= (commit_add + _context.vslist().committed_words())) {
90
      return true;
91
    }
92

93
    return false;
94

95
  }
96

97
  // Given a chunk level and a factor, return a random commit size.
98
  static size_t random_committed_words(chunklevel_t lvl, float commit_factor) {
99
    const size_t sz = (size_t)((float)word_size_for_level(lvl) * commit_factor);
100
    if (sz < 2) {
101
      return 0;
102
    }
103
    return MIN2(SizeRange(sz).random_value(), sz);
104
  }
105

106
  //// Chunk allocation ////
107

108
  // Given an slot index, allocate a random chunk and set it into that slot. Slot must be empty.
109
  // Returns false if allocation fails.
110
  bool allocate_random_chunk_at(int slot) {
111

112
    DEBUG_ONLY(_chunks.check_slot_is_null(slot);)
113

114
    const ChunkLevelRange r = _chunklevel_range.random_subrange();
115
    const chunklevel_t pref_level = r.lowest();
116
    const chunklevel_t max_level = r.highest();
117
    const size_t min_committed = random_committed_words(max_level, _commit_factor);
118

119
    Metachunk* c = nullptr;
120
    _context.alloc_chunk(&c, r.lowest(), r.highest(), min_committed);
121
    if (c == nullptr) {
122
      EXPECT_TRUE(could_be_reserve_error() ||
123
                  could_be_commit_error(min_committed));
124
      LOG("Alloc chunk at %d failed.", slot);
125
      return false;
126
    }
127

128
    _chunks.set_at(slot, c);
129

130
    LOG("Allocated chunk at %d: " METACHUNK_FORMAT ".", slot, METACHUNK_FORMAT_ARGS(c));
131

132
    return true;
133

134
  }
135

136
  // Allocates a random number of random chunks
137
  bool allocate_random_chunks() {
138
    int to_alloc = 1 + IntRange(MAX2(1, _chunks.size() / 8)).random_value();
139
    bool success = true;
140
    int slot = _chunks.first_null_slot();
141
    while (to_alloc > 0 && slot != -1 && success) {
142
      success = allocate_random_chunk_at(slot);
143
      slot = _chunks.next_null_slot(slot);
144
      to_alloc --;
145
    }
146
    return success && to_alloc == 0;
147
  }
148

149
  bool fill_all_slots_with_random_chunks() {
150
    bool success = true;
151
    for (int slot = _chunks.first_null_slot();
152
         slot != -1 && success; slot = _chunks.next_null_slot(slot)) {
153
      success = allocate_random_chunk_at(slot);
154
    }
155
    return success;
156
  }
157

158
  //// Chunk return ////
159

160
  // Given an slot index, return the chunk in that slot to the chunk manager.
161
  void return_chunk_at(int slot) {
162
    Metachunk* c = _chunks.at(slot);
163
    LOG("Returning chunk at %d: " METACHUNK_FORMAT ".", slot, METACHUNK_FORMAT_ARGS(c));
164
    _context.return_chunk(c);
165
    _chunks.set_at(slot, nullptr);
166
  }
167

168
  // return a random number of chunks (at most a quarter of the full slot range)
169
  void return_random_chunks() {
170
    int to_free = 1 + IntRange(MAX2(1, _chunks.size() / 8)).random_value();
171
    int index = _chunks.first_non_null_slot();
172
    while (to_free > 0 && index != -1) {
173
      return_chunk_at(index);
174
      index = _chunks.next_non_null_slot(index);
175
      to_free --;
176
    }
177
  }
178

179
  void return_all_chunks() {
180
    for (int slot = _chunks.first_non_null_slot();
181
         slot != -1; slot = _chunks.next_non_null_slot(slot)) {
182
      return_chunk_at(slot);
183
    }
184
  }
185

186
  // adjust test if we change levels
187
  STATIC_ASSERT(HIGHEST_CHUNK_LEVEL == CHUNK_LEVEL_1K);
188
  STATIC_ASSERT(LOWEST_CHUNK_LEVEL == CHUNK_LEVEL_16M);
189

190
  void one_test() {
191

192
    fill_all_slots_with_random_chunks();
193
    _chunks.shuffle();
194

195
    IntRange rand(100);
196

197
    for (int j = 0; j < 750; j++) {
198

199
      bool force_alloc = false;
200
      bool force_free = true;
201

202
      bool do_alloc =
203
          force_alloc ? true :
204
              (force_free ? false : rand.random_value() >= 50);
205
      force_alloc = force_free = false;
206

207
      if (do_alloc) {
208
        if (!allocate_random_chunks()) {
209
          force_free = true;
210
        }
211
      } else {
212
        return_random_chunks();
213
      }
214

215
      _chunks.shuffle();
216

217
    }
218

219
    return_all_chunks();
220

221
  }
222

223
public:
224

225
  // A test with no limits
226
  ChunkManagerRandomChunkAllocTest(ChunkLevelRange r, float commit_factor) :
227
    _context(),
228
    _chunks(max_num_live_chunks(r, commit_factor)),
229
    _chunklevel_range(r),
230
    _commit_factor(commit_factor)
231
  {}
232

233
  // A test with no reserve limit but commit limit
234
  ChunkManagerRandomChunkAllocTest(size_t commit_limit,
235
                                   ChunkLevelRange r, float commit_factor) :
236
    _context(commit_limit),
237
    _chunks(max_num_live_chunks(r, commit_factor)),
238
    _chunklevel_range(r),
239
    _commit_factor(commit_factor)
240
  {}
241

242
  // A test with both reserve and commit limit
243
  // ChunkManagerRandomChunkAllocTest(size_t commit_limit, size_t reserve_limit,
244
  //                                  ChunkLevelRange r, float commit_factor)
245
  // : _helper(commit_limit, reserve_limit),
246
  // _chunks(max_num_live_chunks(r, commit_factor)),
247
  // _chunklevel_range(r),
248
  // _commit_factor(commit_factor)
249
  // {}
250

251
  void do_tests() {
252
    const int num_runs = 3;
253
    for (int n = 0; n < num_runs; n++) {
254
      one_test();
255
    }
256
  }
257

258
};
259

260
#define DEFINE_TEST(name, range, commit_factor) \
261
TEST_VM(metaspace, chunkmanager_random_alloc_##name) { \
262
  ChunkManagerRandomChunkAllocTest test(range, commit_factor); \
263
  test.do_tests(); \
264
}
265

266
DEFINE_TEST(test_nolimit_1, ChunkLevelRanges::small_chunks(), 0.0f)
267
DEFINE_TEST(test_nolimit_2, ChunkLevelRanges::small_chunks(), 0.5f)
268
DEFINE_TEST(test_nolimit_3, ChunkLevelRanges::small_chunks(), 1.0f)
269

270
DEFINE_TEST(test_nolimit_4, ChunkLevelRanges::all_chunks(), 0.0f)
271
DEFINE_TEST(test_nolimit_5, ChunkLevelRanges::all_chunks(), 0.5f)
272
DEFINE_TEST(test_nolimit_6, ChunkLevelRanges::all_chunks(), 1.0f)
273

274
#define DEFINE_TEST_2(name, range, commit_factor) \
275
TEST_VM(metaspace, chunkmanager_random_alloc_##name) { \
276
  const size_t commit_limit = 256 * K; \
277
  ChunkManagerRandomChunkAllocTest test(commit_limit, range, commit_factor); \
278
  test.do_tests(); \
279
}
280

281
DEFINE_TEST_2(test_with_limit_1, ChunkLevelRanges::small_chunks(), 0.0f)
282
DEFINE_TEST_2(test_with_limit_2, ChunkLevelRanges::small_chunks(), 0.5f)
283
DEFINE_TEST_2(test_with_limit_3, ChunkLevelRanges::small_chunks(), 1.0f)
284

285
DEFINE_TEST_2(test_with_limit_4, ChunkLevelRanges::all_chunks(), 0.0f)
286
DEFINE_TEST_2(test_with_limit_5, ChunkLevelRanges::all_chunks(), 0.5f)
287
DEFINE_TEST_2(test_with_limit_6, ChunkLevelRanges::all_chunks(), 1.0f)
288

289