1 //===- llvm/unittest/IR/WaymarkTest.cpp - Waymarking unit tests -----------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8
9 #include "llvm/ADT/Waymarking.h"
10 #include "gtest/gtest.h"
11
12 using namespace llvm;
13
14 static const int N = 100;
15
16 // Get the Waymarking Tag of the pointer.
tag(int * P)17 static int tag(int *P) {
18 return static_cast<int>(reinterpret_cast<uintptr_t>(P) &
19 uintptr_t(alignof(int *) - 1));
20 }
21
22 // Get the actual pointer, by stripping the Waymarking Tag.
ref(int * P)23 static int *ref(int *P) {
24 return reinterpret_cast<int *>(reinterpret_cast<uintptr_t>(P) &
25 ~uintptr_t(alignof(int *) - 1));
26 }
27
createArray(int Len)28 static int **createArray(int Len) {
29 int **A = new int *[Len];
30 for (int I = 0; I < Len; ++I)
31 A[I] = new int(I);
32 return A;
33 }
34
freeArray(int ** A,int Len)35 static void freeArray(int **A, int Len) {
36 for (int I = 0; I < Len; ++I)
37 delete ref(A[I]);
38 delete[] A;
39 }
40
41 // Verify the values stored in the array are as expected, and did not change due
42 // to fillWaymarks.
verifyArrayValues(int ** A,int Begin,int End)43 static void verifyArrayValues(int **A, int Begin, int End) {
44 for (int I = Begin; I < End; ++I)
45 EXPECT_EQ(I, *ref(A[I]));
46 }
47
verifyArrayValues(int ** A,int Len)48 static void verifyArrayValues(int **A, int Len) {
49 verifyArrayValues(A, 0, Len);
50 }
51
52 // Verify that we can follow the waymarks to the array's head from each element
53 // of the array.
verifyFollowWaymarks(int ** A,int Len)54 static void verifyFollowWaymarks(int **A, int Len) {
55 for (int I = 0; I < Len; ++I) {
56 int **P = followWaymarks(A + I);
57 EXPECT_EQ(A, P);
58 }
59 }
60
61 namespace {
62
63 // Test filling and following the waymarks of a single array.
TEST(WaymarkingTest,SingleHead)64 TEST(WaymarkingTest, SingleHead) {
65 const int N2 = 2 * N;
66 int **volatile A = createArray(N2);
67
68 // Fill the first half of the array with waymarks.
69 fillWaymarks(A, A + N, 0);
70 verifyArrayValues(A, N2);
71
72 verifyFollowWaymarks(A, N);
73
74 // Fill the rest of the waymarks (continuing from where we stopped).
75 fillWaymarks(A + N, A + N2, N);
76 verifyArrayValues(A, N2);
77
78 verifyFollowWaymarks(A, N);
79
80 freeArray(A, N2);
81 }
82
83 // Test filling and following the waymarks of an array split into several
84 // different sections of waymarks (treated just like separate arrays).
TEST(WaymarkingTest,MultiHead)85 TEST(WaymarkingTest, MultiHead) {
86 const int N2 = 2 * N;
87 const int N3 = 3 * N;
88 int **volatile A = createArray(N3);
89
90 // Separate the array into 3 sections of waymarks.
91 fillWaymarks(A, A + N, 0);
92 fillWaymarks(A + N, A + N2, 0);
93 fillWaymarks(A + N2, A + N3, 0);
94 verifyArrayValues(A, N3);
95
96 verifyFollowWaymarks(A, N);
97 verifyFollowWaymarks(A + N, N2 - N);
98 verifyFollowWaymarks(A + N2, N3 - N2);
99
100 freeArray(A, N3);
101 }
102
103 // Test reseting (value and tag of) elements inside an array of waymarks.
TEST(WaymarkingTest,Reset)104 TEST(WaymarkingTest, Reset) {
105 int **volatile A = createArray(N);
106
107 fillWaymarks(A, A + N, 0);
108 verifyArrayValues(A, N);
109
110 const int N2 = N / 2;
111 const int N3 = N / 3;
112 const int N4 = N / 4;
113
114 // Reset specific elements and check that the tag remains the same.
115 int T2 = tag(A[N2]);
116 delete ref(A[N2]);
117 A[N2] = new int(N2);
118 fillWaymarks(A + N2, A + N2 + 1, N2);
119 verifyArrayValues(A, N2, N2 + 1);
120 EXPECT_EQ(T2, tag(A[N2]));
121
122 int T3 = tag(A[N3]);
123 delete ref(A[N3]);
124 A[N3] = new int(N3);
125 fillWaymarks(A + N3, A + N3 + 1, N3);
126 verifyArrayValues(A, N3, N3 + 1);
127 EXPECT_EQ(T3, tag(A[N3]));
128
129 int T4 = tag(A[N4]);
130 delete ref(A[N4]);
131 A[N4] = new int(N4);
132 fillWaymarks(A + N4, A + N4 + 1, N4);
133 verifyArrayValues(A, N4, N4 + 1);
134 EXPECT_EQ(T4, tag(A[N4]));
135
136 verifyArrayValues(A, N);
137 verifyFollowWaymarks(A, N);
138
139 freeArray(A, N);
140 }
141
142 } // end anonymous namespace
143