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