1 /*

     2  * Copyright (c) 2016, 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/zForwardingTable.inline.hpp"

    26 #include "unittest.hpp"

    27 

    28 using namespace testing;

    29 

    30 #define CAPTURE_DELIM "\n"

    31 #define CAPTURE1(expression) #expression << " evaluates to " << expression

    32 #define CAPTURE2(e0, e1)                 CAPTURE1(e0) << CAPTURE_DELIM << CAPTURE1(e1)

    33 

    34 #define CAPTURE(expression) CAPTURE1(expression)

    35 

    36 class ZForwardingTableTest : public Test {

    37 public:

    38   // Helper functions

    39 

    40   static bool is_power_of_2(size_t value) {

    41     return ::is_power_of_2((intptr_t)value);

    42   }

    43 

    44   class SequenceToFromIndex : AllStatic {

    45   public:

    46     static uintptr_t even(uint32_t sequence_number) {

    47       return sequence_number * 2;

    48     }

    49     static uintptr_t odd(uint32_t sequence_number) {

    50       return even(sequence_number) + 1;

    51     }

    52     static uintptr_t one_to_one(uint32_t sequence_number) {

    53       return sequence_number;

    54     }

    55   };

    56 

    57   // Test functions

    58 

    59   static void setup(ZForwardingTable& table) {

    60     EXPECT_PRED1(is_power_of_2, table._size) << CAPTURE(table._size);

    61   }

    62 

    63   static void find_empty(ZForwardingTable& table) {

    64     size_t size = table._size;

    65     size_t entries_to_check = size * 2;

    66 

    67     for (uint32_t i = 0; i < entries_to_check; i++) {

    68       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);

    69 

    70       EXPECT_TRUE(table.find(from_index).is_empty()) << CAPTURE2(from_index, size);

    71     }

    72 

    73     EXPECT_TRUE(table.find(uintptr_t(-1)).is_empty()) << CAPTURE(size);

    74   }

    75 

    76   static void find_full(ZForwardingTable& table) {

    77     size_t size = table._size;

    78     size_t entries_to_populate = size;

    79 

    80     // Populate

    81     for (uint32_t i = 0; i < entries_to_populate; i++) {

    82       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);

    83 

    84       ZForwardingTableCursor cursor;

    85       ZForwardingTableEntry entry = table.find(from_index, &cursor);

    86       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);

    87 

    88       table.insert(from_index, from_index, &cursor);

    89     }

    90 

    91     // Verify

    92     for (uint32_t i = 0; i < entries_to_populate; i++) {

    93       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);

    94 

    95       ZForwardingTableEntry entry = table.find(from_index);

    96       ASSERT_FALSE(entry.is_empty()) << CAPTURE2(from_index, size);

    97 

    98       ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);

    99       ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);

   100     }

   101   }

   102 

   103   static void find_every_other(ZForwardingTable& table) {

   104     size_t size = table._size;

   105     size_t entries_to_populate = size / 2;

   106 

   107     // Populate even from indices

   108     for (uint32_t i = 0; i < entries_to_populate; i++) {

   109       uintptr_t from_index = SequenceToFromIndex::even(i);

   110 

   111       ZForwardingTableCursor cursor;

   112       ZForwardingTableEntry entry = table.find(from_index, &cursor);

   113       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);

   114 

   115       table.insert(from_index, from_index, &cursor);

   116     }

   117 

   118     // Verify populated even indices

   119     for (uint32_t i = 0; i < entries_to_populate; i++) {

   120       uintptr_t from_index = SequenceToFromIndex::even(i);

   121 

   122       ZForwardingTableCursor cursor;

   123       ZForwardingTableEntry entry = table.find(from_index, &cursor);

   124       ASSERT_FALSE(entry.is_empty()) << CAPTURE2(from_index, size);

   125 

   126       ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);

   127       ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);

   128     }

   129 

   130     // Verify empty odd indices

   131     //

   132     // This check could be done on a larger range of sequence numbers,

   133     // but currently entries_to_populate is used.

   134     for (uint32_t i = 0; i < entries_to_populate; i++) {

   135       uintptr_t from_index = SequenceToFromIndex::odd(i);

   136 

   137       ZForwardingTableEntry entry = table.find(from_index);

   138 

   139       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);

   140     }

   141   }

   142 

   143   static void test(void (*function)(ZForwardingTable&), uint32_t size) {

   144     // Setup

   145     ZForwardingTable table;

   146     table.setup(size);

   147     ASSERT_FALSE(table.is_null());

   148 

   149     // Actual test function

   150     (*function)(table);

   151 

   152     // Teardown

   153     table.reset();

   154     ASSERT_TRUE(table.is_null());

   155   }

   156 

   157   // Run the given function with a few different input values.

   158   static void test(void (*function)(ZForwardingTable&)) {

   159     test(function, 1);

   160     test(function, 2);

   161     test(function, 3);

   162     test(function, 4);

   163     test(function, 7);

   164     test(function, 8);

   165     test(function, 1023);

   166     test(function, 1024);

   167     test(function, 1025);

   168   }

   169 };

   170 

   171 TEST_F(ZForwardingTableTest, setup) {

   172   test(&ZForwardingTableTest::setup);

   173 }

   174 

   175 TEST_F(ZForwardingTableTest, find_empty) {

   176   test(&ZForwardingTableTest::find_empty);

   177 }

   178 

   179 TEST_F(ZForwardingTableTest, find_full) {

   180   test(&ZForwardingTableTest::find_full);

   181 }

   182 

   183 TEST_F(ZForwardingTableTest, find_every_other) {

   184   test(&ZForwardingTableTest::find_every_other);

   185 }