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/memflags.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;
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
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--) {
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().flag, 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 { // A committed region inside of/replacing a reserved region
244 // should replace the reserved region's metadata.
245 Tree::RegionData rd{si[0], mtNMT};
246 VMATree::RegionData rd2{si[1], mtTest};
247 Tree tree;
248 tree.reserve_mapping(0, 100, rd);
249 tree.commit_mapping(0, 100, rd2);
250 treap(tree).visit_range_in_order(0, 99999, [&](Node* x) {
251 if (x->key() == 0) {
252 EXPECT_EQ(mtTest, x->val().out.regiondata().flag);
253 }
254 if (x->key() == 100) {
255 EXPECT_EQ(mtTest, x->val().in.regiondata().flag);
256 }
257 });
258 }
259
260 { // Attempting to reserve or commit an empty region should not change the tree.
261 Tree tree;
262 Tree::RegionData rd{si[0], mtNMT};
263 tree.reserve_mapping(0, 0, rd);
264 EXPECT_EQ(nullptr, treap_root(tree));
265 tree.commit_mapping(0, 0, rd);
266 EXPECT_EQ(nullptr, treap_root(tree));
267 }
268 }
269
270 // Tests for summary accounting
|
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/memflags.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 TNode = 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;
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([&](TNode* 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
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([&](TNode* 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([&](TNode* 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--) {
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([&](TNode* x) {
215 EXPECT_TRUE(x->key() == 0 || x->key() == 100);
216 if (x->key() == 0) {
217 EXPECT_EQ(x->val().out.regiondata().flag, 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 { // A committed region inside of/replacing a reserved region
244 // should replace the reserved region's metadata.
245 Tree::RegionData rd{si[0], mtNMT};
246 VMATree::RegionData rd2{si[1], mtTest};
247 Tree tree;
248 tree.reserve_mapping(0, 100, rd);
249 tree.commit_mapping(0, 100, rd2);
250 treap(tree).visit_range_in_order(0, 99999, [&](TNode* x) {
251 if (x->key() == 0) {
252 EXPECT_EQ(mtTest, x->val().out.regiondata().flag);
253 }
254 if (x->key() == 100) {
255 EXPECT_EQ(mtTest, x->val().in.regiondata().flag);
256 }
257 });
258 }
259
260 { // Attempting to reserve or commit an empty region should not change the tree.
261 Tree tree;
262 Tree::RegionData rd{si[0], mtNMT};
263 tree.reserve_mapping(0, 0, rd);
264 EXPECT_EQ(nullptr, treap_root(tree));
265 tree.commit_mapping(0, 0, rd);
266 EXPECT_EQ(nullptr, treap_root(tree));
267 }
268 }
269
270 // Tests for summary accounting
|