1 /*
2 * Copyright (c) 2024, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
23 */
24
25 #include "precompiled.hpp"
26 #include "memory/allocation.hpp"
27 #include "nmt/memTag.hpp"
28 #include "nmt/nmtNativeCallStackStorage.hpp"
29 #include "nmt/vmatree.hpp"
30 #include "runtime/os.hpp"
31 #include "unittest.hpp"
32
33 using Tree = VMATree;
34 using Node = Tree::TreapNode;
35 using NCS = NativeCallStackStorage;
36
37 class NMTVMATreeTest : public testing::Test {
38 public:
39 NCS ncs;
40 constexpr static const int si_len = 2;
41 NCS::StackIndex si[si_len];
42 NativeCallStack stacks[si_len];
43
44 NMTVMATreeTest() : ncs(true) {
45 stacks[0] = make_stack(0xA);
46 stacks[1] = make_stack(0xB);
47 si[0] = ncs.push(stacks[0]);
48 si[1] = ncs.push(stacks[0]);
49 }
50
51 // Utilities
52
53 VMATree::TreapNode* treap_root(VMATree& tree) {
54 return tree._tree._root;
55 }
56
57 VMATree::VMATreap& treap(VMATree& tree) {
58 return tree._tree;
59 }
60
61 VMATree::TreapNode* find(VMATree::VMATreap& treap, const VMATree::position key) {
62 return treap.find(treap._root, key);
63 }
64
65 NativeCallStack make_stack(size_t a) {
66 NativeCallStack stack((address*)&a, 1);
67 return stack;
68 }
69
70 VMATree::StateType in_type_of(VMATree::TreapNode* x) {
71 return x->val().in.type();
72 }
73
74 VMATree::StateType out_type_of(VMATree::TreapNode* x) {
75 return x->val().out.type();
76 }
77
78 int count_nodes(Tree& tree) {
79 int count = 0;
80 treap(tree).visit_in_order([&](Node* x) {
81 ++count;
82 });
83 return count;
84 }
85
86 // Tests
87 // Adjacent reservations are merged if the properties match.
88 void adjacent_2_nodes(const VMATree::RegionData& rd) {
89 Tree tree;
90 for (int i = 0; i < 10; i++) {
91 tree.reserve_mapping(i * 100, 100, rd);
92 }
93 EXPECT_EQ(2, count_nodes(tree));
94
95 // Reserving the exact same space again should result in still having only 2 nodes
96 for (int i = 0; i < 10; i++) {
97 tree.reserve_mapping(i * 100, 100, rd);
98 }
99 EXPECT_EQ(2, count_nodes(tree));
100
101 // Do it backwards instead.
102 Tree tree2;
103 for (int i = 9; i >= 0; i--) {
104 tree2.reserve_mapping(i * 100, 100, rd);
105 }
106 EXPECT_EQ(2, count_nodes(tree2));
107 }
108
109 // After removing all ranges we should be left with an entirely empty tree
110 void remove_all_leaves_empty_tree(const VMATree::RegionData& rd) {
111 Tree tree;
112 tree.reserve_mapping(0, 100 * 10, rd);
113 for (int i = 0; i < 10; i++) {
114 tree.release_mapping(i * 100, 100);
115 }
116 EXPECT_EQ(nullptr, treap_root(tree));
117
118 // Other way around
119 tree.reserve_mapping(0, 100 * 10, rd);
120 for (int i = 9; i >= 0; i--) {
121 tree.release_mapping(i * 100, 100);
122 }
123 EXPECT_EQ(nullptr, treap_root(tree));
124 }
125
126 // Committing in a whole reserved range results in 2 nodes
127 void commit_whole(const VMATree::RegionData& rd) {
128 Tree tree;
129 tree.reserve_mapping(0, 100 * 10, rd);
130 for (int i = 0; i < 10; i++) {
131 tree.commit_mapping(i * 100, 100, rd);
132 }
133 treap(tree).visit_in_order([&](Node* x) {
134 VMATree::StateType in = in_type_of(x);
135 VMATree::StateType out = out_type_of(x);
136 EXPECT_TRUE((in == VMATree::StateType::Released && out == VMATree::StateType::Committed) ||
137 (in == VMATree::StateType::Committed && out == VMATree::StateType::Released));
138 });
139 EXPECT_EQ(2, count_nodes(tree));
140 }
141
142 // Committing in middle of reservation ends with a sequence of 4 nodes
143 void commit_middle(const VMATree::RegionData& rd) {
144 Tree tree;
145 tree.reserve_mapping(0, 100, rd);
146 tree.commit_mapping(50, 25, rd);
147
148 size_t found[16];
149 size_t wanted[4] = {0, 50, 75, 100};
150 auto exists = [&](size_t x) {
151 for (int i = 0; i < 4; i++) {
152 if (wanted[i] == x) return true;
153 }
154 return false;
155 };
156
157 int i = 0;
158 treap(tree).visit_in_order([&](Node* x) {
159 if (i < 16) {
160 found[i] = x->key();
161 }
162 i++;
163 });
164
165 ASSERT_EQ(4, i) << "0 - 50 - 75 - 100 nodes expected";
166 EXPECT_TRUE(exists(found[0]));
167 EXPECT_TRUE(exists(found[1]));
168 EXPECT_TRUE(exists(found[2]));
169 EXPECT_TRUE(exists(found[3]));
170 };
171 };
172
173
174
175 TEST_VM_F(NMTVMATreeTest, OverlappingReservationsResultInTwoNodes) {
176 VMATree::RegionData rd{si[0], mtTest};
177 Tree tree;
178 for (int i = 99; i >= 0; i--) {
179 tree.reserve_mapping(i * 100, 101, rd);
180 }
181 EXPECT_EQ(2, count_nodes(tree));
182 }
183
184 // Low-level tests inspecting the state of the tree.
185 TEST_VM_F(NMTVMATreeTest, LowLevel) {
186 adjacent_2_nodes(VMATree::empty_regiondata);
187 remove_all_leaves_empty_tree(VMATree::empty_regiondata);
188 commit_middle(VMATree::empty_regiondata);
189 commit_whole(VMATree::empty_regiondata);
190
191 VMATree::RegionData rd{si[0], mtTest };
192 adjacent_2_nodes(rd);
193 remove_all_leaves_empty_tree(rd);
194 commit_middle(rd);
195 commit_whole(rd);
196
197 { // Identical operation but different metadata should not merge
198 Tree tree;
199 VMATree::RegionData rd{si[0], mtTest };
200 VMATree::RegionData rd2{si[1], mtNMT };
201 tree.reserve_mapping(0, 100, rd);
202 tree.reserve_mapping(100, 100, rd2);
203
204 EXPECT_EQ(3, count_nodes(tree));
205 int found_nodes = 0;
206 }
207
208 { // Reserving after commit should overwrite commit
209 Tree tree;
210 VMATree::RegionData rd{si[0], mtTest };
211 VMATree::RegionData rd2{si[1], mtNMT };
212 tree.commit_mapping(50, 50, rd2);
213 tree.reserve_mapping(0, 100, rd);
214 treap(tree).visit_in_order([&](Node* x) {
215 EXPECT_TRUE(x->key() == 0 || x->key() == 100);
216 if (x->key() == 0) {
217 EXPECT_EQ(x->val().out.regiondata().mem_tag, mtTest);
218 }
219 });
220
221 EXPECT_EQ(2, count_nodes(tree));
222 }
223
224 { // Split a reserved region into two different reserved regions
225 Tree tree;
226 VMATree::RegionData rd{si[0], mtTest };
227 VMATree::RegionData rd2{si[1], mtNMT };
228 VMATree::RegionData rd3{si[0], mtNone };
229 tree.reserve_mapping(0, 100, rd);
230 tree.reserve_mapping(0, 50, rd2);
231 tree.reserve_mapping(50, 50, rd3);
232
233 EXPECT_EQ(3, count_nodes(tree));
234 }
235 { // One big reserve + release leaves an empty tree
236 Tree::RegionData rd{si[0], mtNMT};
237 Tree tree;
238 tree.reserve_mapping(0, 500000, rd);
239 tree.release_mapping(0, 500000);
240
241 EXPECT_EQ(nullptr, treap_root(tree));
242 }
243
244 { // A committed region inside of/replacing a reserved region
245 // should replace the reserved region's metadata.
246 Tree::RegionData rd{si[0], mtNMT};
247 VMATree::RegionData rd2{si[1], mtTest};
248 Tree tree;
249 tree.reserve_mapping(0, 100, rd);
250 tree.commit_mapping(0, 100, rd2);
251 treap(tree).visit_range_in_order(0, 99999, [&](Node* x) {
252 if (x->key() == 0) {
253 EXPECT_EQ(mtTest, x->val().out.regiondata().mem_tag);
254 }
255 if (x->key() == 100) {
256 EXPECT_EQ(mtTest, x->val().in.regiondata().mem_tag);
257 }
258 });
259 }
260
261 { // Attempting to reserve or commit an empty region should not change the tree.
262 Tree tree;
263 Tree::RegionData rd{si[0], mtNMT};
264 tree.reserve_mapping(0, 0, rd);
265 EXPECT_EQ(nullptr, treap_root(tree));
266 tree.commit_mapping(0, 0, rd);
267 EXPECT_EQ(nullptr, treap_root(tree));
268 }
269 }
270
271 // Tests for summary accounting
272 TEST_VM_F(NMTVMATreeTest, SummaryAccounting) {
273 { // Fully enclosed re-reserving works correctly.
274 Tree::RegionData rd(NCS::StackIndex(), mtTest);
275 Tree::RegionData rd2(NCS::StackIndex(), mtNMT);
276 Tree tree;
277 VMATree::SummaryDiff all_diff = tree.reserve_mapping(0, 100, rd);
278 VMATree::SingleDiff diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
279 EXPECT_EQ(100, diff.reserve);
280 all_diff = tree.reserve_mapping(50, 25, rd2);
281 diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
282 VMATree::SingleDiff diff2 = all_diff.tag[NMTUtil::tag_to_index(mtNMT)];
283 EXPECT_EQ(-25, diff.reserve);
284 EXPECT_EQ(25, diff2.reserve);
285 }
286 { // Fully release reserved mapping
287 Tree::RegionData rd(NCS::StackIndex(), mtTest);
288 Tree tree;
289 VMATree::SummaryDiff all_diff = tree.reserve_mapping(0, 100, rd);
290 VMATree::SingleDiff diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
291 EXPECT_EQ(100, diff.reserve);
292 all_diff = tree.release_mapping(0, 100);
293 diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
294 EXPECT_EQ(-100, diff.reserve);
295 }
296 { // Convert some of a released mapping to a committed one
297 Tree::RegionData rd(NCS::StackIndex(), mtTest);
298 Tree tree;
299 VMATree::SummaryDiff all_diff = tree.reserve_mapping(0, 100, rd);
300 VMATree::SingleDiff diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
301 EXPECT_EQ(diff.reserve, 100);
302 all_diff = tree.commit_mapping(0, 100, rd);
303 diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
304 EXPECT_EQ(0, diff.reserve);
305 EXPECT_EQ(100, diff.commit);
306 }
307 { // Adjacent reserved mappings with same type
308 Tree::RegionData rd(NCS::StackIndex(), mtTest);
309 Tree tree;
310 VMATree::SummaryDiff all_diff = tree.reserve_mapping(0, 100, rd);
311 VMATree::SingleDiff diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
312 EXPECT_EQ(diff.reserve, 100);
313 all_diff = tree.reserve_mapping(100, 100, rd);
314 diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
315 EXPECT_EQ(100, diff.reserve);
316 }
317 { // Adjacent reserved mappings with different flags
318 Tree::RegionData rd(NCS::StackIndex(), mtTest);
319 Tree::RegionData rd2(NCS::StackIndex(), mtNMT);
320 Tree tree;
321 VMATree::SummaryDiff all_diff = tree.reserve_mapping(0, 100, rd);
322 VMATree::SingleDiff diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
323 EXPECT_EQ(diff.reserve, 100);
324 all_diff = tree.reserve_mapping(100, 100, rd2);
325 diff = all_diff.tag[NMTUtil::tag_to_index(mtTest)];
326 EXPECT_EQ(0, diff.reserve);
327 diff = all_diff.tag[NMTUtil::tag_to_index(mtNMT)];
328 EXPECT_EQ(100, diff.reserve);
329 }
330
331 { // A commit with two previous commits inside of it should only register
332 // the new memory in the commit diff.
333 Tree tree;
334 Tree::RegionData rd(NCS::StackIndex(), mtTest);
335 tree.commit_mapping(128, 128, rd);
336 tree.commit_mapping(512, 128, rd);
337 VMATree::SummaryDiff diff = tree.commit_mapping(0, 1024, rd);
338 EXPECT_EQ(768, diff.tag[NMTUtil::tag_to_index(mtTest)].commit);
339 EXPECT_EQ(768, diff.tag[NMTUtil::tag_to_index(mtTest)].reserve);
340 }
341 }
342
343 // Exceedingly simple tracker for page-granular allocations
344 // Use it for testing consistency with VMATree.
345 struct SimpleVMATracker : public CHeapObj<mtTest> {
346 const size_t page_size = 4096;
347 enum Kind { Reserved, Committed, Free };
348 struct Info {
349 Kind kind;
350 MemTag mem_tag;
351 NativeCallStack stack;
352 Info() : kind(Free), mem_tag(mtNone), stack() {}
353
354 Info(Kind kind, NativeCallStack stack, MemTag mem_tag)
355 : kind(kind), mem_tag(mem_tag), stack(stack) {}
356
357 bool eq(Info other) {
358 return kind == other.kind && stack.equals(other.stack);
359 }
360 };
361 // Page (4KiB) granular array
362 static constexpr const size_t num_pages = 1024 * 4;
363 Info pages[num_pages];
364
365 SimpleVMATracker()
366 : pages() {
367 for (size_t i = 0; i < num_pages; i++) {
368 pages[i] = Info();
369 }
370 }
371
372 VMATree::SummaryDiff do_it(Kind kind, size_t start, size_t size, NativeCallStack stack, MemTag mem_tag) {
373 assert(is_aligned(size, page_size) && is_aligned(start, page_size), "page alignment");
374
375 VMATree::SummaryDiff diff;
376 const size_t page_count = size / page_size;
377 const size_t start_idx = start / page_size;
378 const size_t end_idx = start_idx + page_count;
379 assert(end_idx < SimpleVMATracker::num_pages, "");
380
381 Info new_info(kind, stack, mem_tag);
382 for (size_t i = start_idx; i < end_idx; i++) {
383 Info& old_info = pages[i];
384
385 // Register diff
386 if (old_info.kind == Reserved) {
387 diff.tag[(int)old_info.mem_tag].reserve -= page_size;
388 } else if (old_info.kind == Committed) {
389 diff.tag[(int)old_info.mem_tag].reserve -= page_size;
390 diff.tag[(int)old_info.mem_tag].commit -= page_size;
391 }
392
393 if (kind == Reserved) {
394 diff.tag[(int)new_info.mem_tag].reserve += page_size;
395 } else if (kind == Committed) {
396 diff.tag[(int)new_info.mem_tag].reserve += page_size;
397 diff.tag[(int)new_info.mem_tag].commit += page_size;
398 }
399 // Overwrite old one with new
400 pages[i] = new_info;
401 }
402 return diff;
403 }
404
405 VMATree::SummaryDiff reserve(size_t start, size_t size, NativeCallStack stack, MemTag mem_tag) {
406 return do_it(Reserved, start, size, stack, mem_tag);
407 }
408
409 VMATree::SummaryDiff commit(size_t start, size_t size, NativeCallStack stack, MemTag mem_tag) {
410 return do_it(Committed, start, size, stack, mem_tag);
411 }
412
413 VMATree::SummaryDiff release(size_t start, size_t size) {
414 return do_it(Free, start, size, NativeCallStack(), mtNone);
415 }
416 };
417
418 constexpr const size_t SimpleVMATracker::num_pages;
419
420 TEST_VM_F(NMTVMATreeTest, TestConsistencyWithSimpleTracker) {
421 // In this test we use ASSERT macros from gtest instead of EXPECT
422 // as any error will propagate and become larger as the test progresses.
423 SimpleVMATracker* tr = new SimpleVMATracker();
424 const size_t page_size = tr->page_size;
425 VMATree tree;
426 NCS ncss(true);
427 constexpr const int candidates_len_tags = 4;
428 constexpr const int candidates_len_stacks = 2;
429
430 NativeCallStack candidate_stacks[candidates_len_stacks] = {
431 make_stack(0xA),
432 make_stack(0xB),
433 };
434
435 const MemTag candidate_tags[candidates_len_tags] = {
436 mtNMT,
437 mtTest,
438 };
439
440 const int operation_count = 100000; // One hundred thousand
441 for (int i = 0; i < operation_count; i++) {
442 size_t page_start = (size_t)(os::random() % SimpleVMATracker::num_pages);
443 size_t page_end = (size_t)(os::random() % (SimpleVMATracker::num_pages));
444
445 if (page_end < page_start) {
446 const size_t temp = page_start;
447 page_start = page_end;
448 page_end = page_start;
449 }
450 const size_t num_pages = page_end - page_start;
451
452 if (num_pages == 0) {
453 i--; continue;
454 }
455
456 const size_t start = page_start * page_size;
457 const size_t size = num_pages * page_size;
458
459 const MemTag mem_tag = candidate_tags[os::random() % candidates_len_tags];
460 const NativeCallStack stack = candidate_stacks[os::random() % candidates_len_stacks];
461
462 const NCS::StackIndex si = ncss.push(stack);
463 VMATree::RegionData data(si, mem_tag);
464
465 const SimpleVMATracker::Kind kind = (SimpleVMATracker::Kind)(os::random() % 3);
466
467 VMATree::SummaryDiff tree_diff;
468 VMATree::SummaryDiff simple_diff;
469 if (kind == SimpleVMATracker::Reserved) {
470 simple_diff = tr->reserve(start, size, stack, mem_tag);
471 tree_diff = tree.reserve_mapping(start, size, data);
472 } else if (kind == SimpleVMATracker::Committed) {
473 simple_diff = tr->commit(start, size, stack, mem_tag);
474 tree_diff = tree.commit_mapping(start, size, data);
475 } else {
476 simple_diff = tr->release(start, size);
477 tree_diff = tree.release_mapping(start, size);
478 }
479
480 for (int j = 0; j < mt_number_of_tags; j++) {
481 VMATree::SingleDiff td = tree_diff.tag[j];
482 VMATree::SingleDiff sd = simple_diff.tag[j];
483 ASSERT_EQ(td.reserve, sd.reserve);
484 ASSERT_EQ(td.commit, sd.commit);
485 }
486
487
488 // Do an in-depth check every 25 000 iterations.
489 if (i % 25000 == 0) {
490 size_t j = 0;
491 while (j < SimpleVMATracker::num_pages) {
492 while (j < SimpleVMATracker::num_pages &&
493 tr->pages[j].kind == SimpleVMATracker::Free) {
494 j++;
495 }
496
497 if (j == SimpleVMATracker::num_pages) {
498 break;
499 }
500
501 size_t start = j;
502 SimpleVMATracker::Info starti = tr->pages[start];
503
504 while (j < SimpleVMATracker::num_pages &&
505 tr->pages[j].eq(starti)) {
506 j++;
507 }
508
509 size_t end = j-1;
510 ASSERT_LE(end, SimpleVMATracker::num_pages);
511 SimpleVMATracker::Info endi = tr->pages[end];
512
513 VMATree::VMATreap& treap = this->treap(tree);
514 VMATree::TreapNode* startn = find(treap, start * page_size);
515 ASSERT_NE(nullptr, startn);
516 VMATree::TreapNode* endn = find(treap, (end * page_size) + page_size);
517 ASSERT_NE(nullptr, endn);
518
519 const NativeCallStack& start_stack = ncss.get(startn->val().out.stack());
520 const NativeCallStack& end_stack = ncss.get(endn->val().in.stack());
521 ASSERT_TRUE(starti.stack.equals(start_stack));
522 ASSERT_TRUE(endi.stack.equals(end_stack));
523
524 ASSERT_EQ(starti.mem_tag, startn->val().out.mem_tag());
525 ASSERT_EQ(endi.mem_tag, endn->val().in.mem_tag());
526 }
527 }
528 }
529 }