1 /*
2 * Copyright (C) 2019 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "perfetto/ext/base/uuid.h"
18
19 #include <array>
20 #include <cinttypes>
21 #include <set>
22
23 #include "perfetto/base/logging.h"
24 #include "perfetto/base/time.h"
25 #include "test/gtest_and_gmock.h"
26
27 namespace perfetto {
28 namespace base {
29 namespace {
30
TEST(UuidTest,DefaultConstructorIsBlank)31 TEST(UuidTest, DefaultConstructorIsBlank) {
32 Uuid a;
33 Uuid b;
34 EXPECT_EQ(a, b);
35 EXPECT_EQ(a.msb(), 0);
36 EXPECT_EQ(a.lsb(), 0);
37 }
38
TEST(UuidTest,TwoUuidsShouldBeDifferent)39 TEST(UuidTest, TwoUuidsShouldBeDifferent) {
40 Uuid a = Uuidv4();
41 Uuid b = Uuidv4();
42 EXPECT_NE(a, b);
43 EXPECT_EQ(a, a);
44 EXPECT_EQ(b, b);
45 }
46
TEST(UuidTest,CanRoundTripUuid)47 TEST(UuidTest, CanRoundTripUuid) {
48 Uuid uuid = Uuidv4();
49 EXPECT_EQ(Uuid(uuid.ToString()), uuid);
50 }
51
TEST(UuidTest,SetGet)52 TEST(UuidTest, SetGet) {
53 Uuid a = Uuidv4();
54 Uuid b;
55 b.set_lsb_msb(a.lsb(), a.msb());
56 EXPECT_EQ(a, b);
57 }
58
TEST(UuidTest,LsbMsbConstructor)59 TEST(UuidTest, LsbMsbConstructor) {
60 Uuid uuid(-6605018796207623390, 1314564453825188563);
61 EXPECT_EQ(uuid.ToPrettyString(), "123e4567-e89b-12d3-a456-426655443322");
62 }
63
TEST(UuidTest,UuidToPrettyString)64 TEST(UuidTest, UuidToPrettyString) {
65 Uuid uuid;
66 uuid.set_lsb_msb(-6605018796207623390, 1314564453825188563);
67 EXPECT_EQ(uuid.ToPrettyString(), "123e4567-e89b-12d3-a456-426655443322");
68 }
69
TEST(UuidTest,BoolOperator)70 TEST(UuidTest, BoolOperator) {
71 Uuid uuid;
72 EXPECT_FALSE(uuid);
73
74 uuid.set_lsb(1);
75 EXPECT_TRUE(uuid);
76
77 uuid.set_lsb(0);
78 EXPECT_FALSE(uuid);
79
80 uuid.set_msb(0x80000000);
81 EXPECT_TRUE(uuid);
82
83 uuid = Uuid();
84 EXPECT_FALSE(uuid);
85
86 uuid = Uuidv4();
87 EXPECT_TRUE(uuid);
88 }
89
90 // Generate kRounds UUIDs and check that, for each bit, we see roughly as many
91 // zeros as ones.
92 // Marking as DISABLED as this really checks the STD implementation not our
93 // code. Invoke manually only when needed.
TEST(UuidTest,DISABLED_BitRandomDistribution)94 TEST(UuidTest, DISABLED_BitRandomDistribution) {
95 const int kRounds = 100000;
96 std::array<int64_t, 128> bit_count{};
97 for (int i = 0; i < kRounds; i++) {
98 Uuid uuid = Uuidv4();
99 for (size_t b = 0; b < 64; b++) {
100 bit_count[b] += (uint64_t(uuid.lsb()) & (1ull << b)) ? 1 : -1;
101 bit_count[64 + b] += (uint64_t(uuid.msb()) & (1ull << b)) ? 1 : -1;
102 }
103 }
104
105 // By adding +1 / -1 for each one/zero, `bit_count` contains for each bit,
106 // their embalance. In an ideal world we expect `bit_count` to be 0 at each
107 // position. In practice we accept a 2% embalance to pass the test.
108 int64_t max_diff = 0;
109 for (size_t i = 0; i < bit_count.size(); i++)
110 max_diff = std::max(max_diff, std::abs(bit_count[i]));
111
112 const double diff_pct =
113 100.0 * static_cast<double>(max_diff) / static_cast<double>(kRounds);
114 PERFETTO_DLOG("Max bit embalance: %.2f %%", diff_pct);
115
116 // Local runs show a 1% embalance. We take a 5x margin for the test.
117 ASSERT_LT(diff_pct, 5.0);
118 }
119
120 // This test checks for collisions in a space of 300M traces.
121 // It takes ~20 minutes to run (hence the disabled-by-default)
TEST(UuidTest,DISABLED_NoCollisions)122 TEST(UuidTest, DISABLED_NoCollisions) {
123 std::set<int64_t> rand_nums;
124 uint64_t num_collisions = 0;
125 const uint64_t kSpace = 300ull * 1000ull * 1000ull;
126 const int64_t t_start = base::GetWallTimeMs().count();
127 for (uint64_t i = 0; i < kSpace; i++) {
128 Uuid uuid = Uuidv4();
129 int64_t lsb = uuid.lsb();
130 int64_t msb = uuid.msb();
131 if (!rand_nums.insert(lsb).second || !rand_nums.insert(msb).second) {
132 PERFETTO_ELOG("Found collision @ step %" PRIu64, i);
133 }
134 if (i % 1000000 == 0 && i > 0) {
135 int64_t now = base::GetWallTimeMs().count();
136 uint64_t elapsed = static_cast<uint64_t>(now - t_start);
137 uint64_t eta_ms = kSpace * elapsed / i - elapsed;
138 PERFETTO_LOG("Running... %" PRIu64 " %%, ETA: %" PRIu64 " seconds",
139 i * 100 / kSpace, eta_ms / 1000);
140 }
141 }
142 EXPECT_EQ(num_collisions, 0u);
143 }
144
145 } // namespace
146 } // namespace base
147 } // namespace perfetto
148