1 /*
   2  * Copyright (c) 2016, Oracle and/or its affiliates. All rights reserved.
   3  * ORACLE PROPRIETARY/CONFIDENTIAL.  Use is subject to license terms.
   4  */
   5 
   6 #include "precompiled.hpp"
   7 #include "gc/z/zForwardingTable.inline.hpp"
   8 #include "unittest.hpp"
   9 
  10 using namespace testing;
  11 
  12 #define CAPTURE_DELIM "\n"
  13 #define CAPTURE1(expression) #expression << " evaluates to " << expression
  14 #define CAPTURE2(e0, e1)                 CAPTURE1(e0) << CAPTURE_DELIM << CAPTURE1(e1)
  15 
  16 #define CAPTURE(expression) CAPTURE1(expression)
  17 
  18 class ZForwardingTableTest : public Test {
  19 public:
  20   // Helper functions
  21 
  22   static bool is_power_of_2(size_t value) {
  23     return ::is_power_of_2((intptr_t)value);
  24   }
  25 
  26   class SequenceToFromIndex : AllStatic {
  27   public:
  28     static uintptr_t even(uint32_t sequence_number) {
  29       return sequence_number * 2;
  30     }
  31     static uintptr_t odd(uint32_t sequence_number) {
  32       return even(sequence_number) + 1;
  33     }
  34     static uintptr_t one_to_one(uint32_t sequence_number) {
  35       return sequence_number;
  36     }
  37   };
  38 
  39   // Test functions
  40 
  41   static void setup(ZForwardingTable& table) {
  42     EXPECT_PRED1(is_power_of_2, table._size) << CAPTURE(table._size);
  43   }
  44 
  45   static void find_empty(ZForwardingTable& table) {
  46     size_t size = table._size;
  47     size_t entries_to_check = size * 2;
  48 
  49     for (uint32_t i = 0; i < entries_to_check; i++) {
  50       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
  51 
  52       EXPECT_TRUE(table.find(from_index).is_empty()) << CAPTURE2(from_index, size);
  53     }
  54 
  55     EXPECT_TRUE(table.find(uintptr_t(-1)).is_empty()) << CAPTURE(size);
  56   }
  57 
  58   static void find_full(ZForwardingTable& table) {
  59     size_t size = table._size;
  60     size_t entries_to_populate = size;
  61 
  62     // Populate
  63     for (uint32_t i = 0; i < entries_to_populate; i++) {
  64       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
  65 
  66       ZForwardingTableCursor cursor;
  67       ZForwardingTableEntry entry = table.find(from_index, &cursor);
  68       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);
  69 
  70       table.insert(from_index, from_index, &cursor);
  71     }
  72 
  73     // Verify
  74     for (uint32_t i = 0; i < entries_to_populate; i++) {
  75       uintptr_t from_index = SequenceToFromIndex::one_to_one(i);
  76 
  77       ZForwardingTableEntry entry = table.find(from_index);
  78       ASSERT_FALSE(entry.is_empty()) << CAPTURE2(from_index, size);
  79 
  80       ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);
  81       ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);
  82     }
  83   }
  84 
  85   static void find_every_other(ZForwardingTable& table) {
  86     size_t size = table._size;
  87     size_t entries_to_populate = size / 2;
  88 
  89     // Populate even from indices
  90     for (uint32_t i = 0; i < entries_to_populate; i++) {
  91       uintptr_t from_index = SequenceToFromIndex::even(i);
  92 
  93       ZForwardingTableCursor cursor;
  94       ZForwardingTableEntry entry = table.find(from_index, &cursor);
  95       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);
  96 
  97       table.insert(from_index, from_index, &cursor);
  98     }
  99 
 100     // Verify populated even indices
 101     for (uint32_t i = 0; i < entries_to_populate; i++) {
 102       uintptr_t from_index = SequenceToFromIndex::even(i);
 103 
 104       ZForwardingTableCursor cursor;
 105       ZForwardingTableEntry entry = table.find(from_index, &cursor);
 106       ASSERT_FALSE(entry.is_empty()) << CAPTURE2(from_index, size);
 107 
 108       ASSERT_EQ(entry.from_index(), from_index) << CAPTURE(size);
 109       ASSERT_EQ(entry.to_offset(), from_index) << CAPTURE(size);
 110     }
 111 
 112     // Verify empty odd indices
 113     //
 114     // This check could be done on a larger range of sequence numbers,
 115     // but currently entries_to_populate is used.
 116     for (uint32_t i = 0; i < entries_to_populate; i++) {
 117       uintptr_t from_index = SequenceToFromIndex::odd(i);
 118 
 119       ZForwardingTableEntry entry = table.find(from_index);
 120 
 121       ASSERT_TRUE(entry.is_empty()) << CAPTURE2(from_index, size);
 122     }
 123   }
 124 
 125   static void test(void (*function)(ZForwardingTable&), uint32_t size) {
 126     // Setup
 127     ZForwardingTable table;
 128     table.setup(size);
 129     ASSERT_FALSE(table.is_null());
 130 
 131     // Actual test function
 132     (*function)(table);
 133 
 134     // Teardown
 135     table.reset();
 136     ASSERT_TRUE(table.is_null());
 137   }
 138 
 139   // Run the given function with a few different input values.
 140   static void test(void (*function)(ZForwardingTable&)) {
 141     test(function, 1);
 142     test(function, 2);
 143     test(function, 3);
 144     test(function, 4);
 145     test(function, 7);
 146     test(function, 8);
 147     test(function, 1023);
 148     test(function, 1024);
 149     test(function, 1025);
 150   }
 151 };
 152 
 153 TEST_F(ZForwardingTableTest, setup) {
 154   test(&ZForwardingTableTest::setup);
 155 }
 156 
 157 TEST_F(ZForwardingTableTest, find_empty) {
 158   test(&ZForwardingTableTest::find_empty);
 159 }
 160 
 161 TEST_F(ZForwardingTableTest, find_full) {
 162   test(&ZForwardingTableTest::find_full);
 163 }
 164 
 165 TEST_F(ZForwardingTableTest, find_every_other) {
 166   test(&ZForwardingTableTest::find_every_other);
 167 }