1 /*
2 * Copyright (c) 2016, 2020, 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 #include "precompiled.hpp"
25 #include "gc/z/zAddress.inline.hpp"
26 #include "gc/z/zForwarding.inline.hpp"
27 #include "gc/z/zGlobals.hpp"
28 #include "gc/z/zPage.inline.hpp"
29 #include "unittest.hpp"
30
31 using namespace testing;
32
33 #define CAPTURE_DELIM "\n"
34 #define CAPTURE1(expression) #expression << " evaluates to " << expression
35 #define CAPTURE2(e0, e1) CAPTURE1(e0) << CAPTURE_DELIM << CAPTURE1(e1)
36
37 #define CAPTURE(expression) CAPTURE1(expression)
38
39 class ZForwardingTest : public Test {
40 public:
41 // Helper functions
42
43 class SequenceToFromIndex : AllStatic {
44 public:
45 static uintptr_t even(size_t sequence_number) {
46 return sequence_number * 2;
47 }
48 static uintptr_t odd(size_t sequence_number) {
49 return even(sequence_number) + 1;
50 }
51 static uintptr_t one_to_one(size_t sequence_number) {
52 return sequence_number;
53 }
54 };
55
56 // Test functions
57
58 static void setup(ZForwarding* forwarding) {
59 EXPECT_PRED1(is_power_of_2<size_t>, forwarding->_entries.length()) << CAPTURE(forwarding->_entries.length());
60 }
61
62 static void find_empty(ZForwarding* forwarding) {
63 size_t size = forwarding->_entries.length();
64 size_t entries_to_check = size * 2;
65
66 for (size_t i = 0; i < entries_to_check; i++) {
67 uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
68
69 EXPECT_FALSE(forwarding->find(from_index).populated()) << CAPTURE2(from_index, size);
70 }
71 }
72
73 static void find_full(ZForwarding* forwarding) {
74 size_t size = forwarding->_entries.length();
75 size_t entries_to_populate = size;
76
77 // Populate
78 for (size_t i = 0; i < entries_to_populate; i++) {
79 uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
80
81 ZForwardingCursor cursor;
82 ZForwardingEntry entry = forwarding->find(from_index, &cursor);
83 ASSERT_FALSE(entry.populated()) << CAPTURE2(from_index, size);
84
85 forwarding->insert(from_index, from_index, &cursor);
86 }
87
88 // Verify
89 for (size_t i = 0; i < entries_to_populate; i++) {
90 uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
91
92 ZForwardingEntry entry = forwarding->find(from_index);
93 ASSERT_TRUE(entry.populated()) << CAPTURE2(from_index, size);
94
95 ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);
96 ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);
97 }
98 }
99
100 static void find_every_other(ZForwarding* forwarding) {
101 size_t size = forwarding->_entries.length();
102 size_t entries_to_populate = size / 2;
103
104 // Populate even from indices
105 for (size_t i = 0; i < entries_to_populate; i++) {
106 uintptr_t from_index = SequenceToFromIndex::even(i);
107
108 ZForwardingCursor cursor;
109 ZForwardingEntry entry = forwarding->find(from_index, &cursor);
110 ASSERT_FALSE(entry.populated()) << CAPTURE2(from_index, size);
111
112 forwarding->insert(from_index, from_index, &cursor);
113 }
114
115 // Verify populated even indices
116 for (size_t i = 0; i < entries_to_populate; i++) {
117 uintptr_t from_index = SequenceToFromIndex::even(i);
118
119 ZForwardingCursor cursor;
120 ZForwardingEntry entry = forwarding->find(from_index, &cursor);
121 ASSERT_TRUE(entry.populated()) << CAPTURE2(from_index, size);
122
123 ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);
124 ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);
125 }
126
127 // Verify empty odd indices
128 //
129 // This check could be done on a larger range of sequence numbers,
130 // but currently entries_to_populate is used.
131 for (size_t i = 0; i < entries_to_populate; i++) {
132 uintptr_t from_index = SequenceToFromIndex::odd(i);
133
134 ZForwardingEntry entry = forwarding->find(from_index);
135
136 ASSERT_FALSE(entry.populated()) << CAPTURE2(from_index, size);
137 }
138 }
139
140 static void test(void (*function)(ZForwarding*), uint32_t size) {
141 // Create page
142 const ZVirtualMemory vmem(0, ZPageSizeSmall);
143 const ZPhysicalMemory pmem(ZPhysicalMemorySegment(0, ZPageSizeSmall, true));
144 ZPage page(ZPageTypeSmall, vmem, pmem);
145
146 page.reset();
147
148 const size_t object_size = 16;
149 const uintptr_t object = page.alloc_object(object_size);
150
151 ZGlobalSeqNum++;
152
153 bool dummy = false;
154 page.mark_object(ZAddress::marked(object), dummy, dummy);
155
156 const uint32_t live_objects = size;
157 const size_t live_bytes = live_objects * object_size;
158 page.inc_live(live_objects, live_bytes);
159
160 // Setup forwarding
161 ZForwarding* const forwarding = ZForwarding::create(&page);
162
163 // Actual test function
164 (*function)(forwarding);
165
166 // Teardown forwarding
167 ZForwarding::destroy(forwarding);
168 }
169
170 // Run the given function with a few different input values.
171 static void test(void (*function)(ZForwarding*)) {
172 test(function, 1);
173 test(function, 2);
174 test(function, 3);
175 test(function, 4);
176 test(function, 7);
177 test(function, 8);
178 test(function, 1023);
179 test(function, 1024);
180 test(function, 1025);
181 }
182 };
183
184 TEST_F(ZForwardingTest, setup) {
185 test(&ZForwardingTest::setup);
186 }
187
188 TEST_F(ZForwardingTest, find_empty) {
189 test(&ZForwardingTest::find_empty);
190 }
191
192 TEST_F(ZForwardingTest, find_full) {
193 test(&ZForwardingTest::find_full);
194 }
195
196 TEST_F(ZForwardingTest, find_every_other) {
197 test(&ZForwardingTest::find_every_other);
198 }