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 <mutex>
20 #include <random>
21
22 #include "perfetto/base/time.h"
23 #include "perfetto/ext/base/no_destructor.h"
24
25 namespace perfetto {
26 namespace base {
27 namespace {
28
29 constexpr char kHexmap[] = {'0', '1', '2', '3', '4', '5', '6', '7',
30 '8', '9', 'a', 'b', 'c', 'd', 'e', 'f'};
31 } // namespace
32
33 // A globally unique 128-bit number.
34 // In the early days of perfetto we were (sorta) respecting rfc4122. Later we
35 // started replacing the LSB of the UUID with the statsd subscription ID in
36 // other parts of the codebase (see perfetto_cmd.cc) for the convenience of
37 // trace lookups, so rfc4122 made no sense as it just reduced entropy.
Uuidv4()38 Uuid Uuidv4() {
39 // Mix different sources of entropy to reduce the chances of collisions.
40 // Only using boot time is not enough. Under the assumption that most traces
41 // are started around the same time at boot, within a 1s window, the birthday
42 // paradox gives a chance of 90% collisions with 70k traces over a 1e9 space
43 // (Number of ns in a 1s window).
44 // &kHexmap >> 14 is used to feed use indirectly ASLR as a source of entropy.
45 // We deliberately don't use /dev/urandom as that might block for
46 // unpredictable time if the system is idle.
47 // The UUID does NOT need to be cryptographically secure, but random enough
48 // to avoid collisions across a large number of devices.
49 static std::minstd_rand rng(
50 static_cast<uint32_t>(static_cast<uint64_t>(GetBootTimeNs().count()) ^
51 static_cast<uint64_t>(GetWallTimeNs().count()) ^
52 (reinterpret_cast<uintptr_t>(&kHexmap) >> 14)));
53 Uuid uuid;
54 auto& data = *uuid.data();
55
56 // std::random is not thread safe and users of this class might mistakenly
57 // assume Uuidv4() is thread_safe because from the outside looks like a
58 // local object.
59 static base::NoDestructor<std::mutex> rand_mutex;
60 std::unique_lock<std::mutex> rand_lock(rand_mutex.ref());
61
62 for (size_t i = 0; i < sizeof(data);) {
63 // Note: the 32-th bit of rng() is always 0 as minstd_rand operates modulo
64 // 2**31. Fill in blocks of 16b rather than 32b to not lose 1b of entropy.
65 const auto rnd_data = static_cast<uint16_t>(rng());
66 memcpy(&data[i], &rnd_data, sizeof(rnd_data));
67 i += sizeof(rnd_data);
68 }
69
70 return uuid;
71 }
72
Uuid()73 Uuid::Uuid() {}
74
Uuid(const std::string & s)75 Uuid::Uuid(const std::string& s) {
76 PERFETTO_CHECK(s.size() == data_.size());
77 memcpy(data_.data(), s.data(), s.size());
78 }
79
Uuid(int64_t lsb,int64_t msb)80 Uuid::Uuid(int64_t lsb, int64_t msb) {
81 set_lsb_msb(lsb, msb);
82 }
83
ToString() const84 std::string Uuid::ToString() const {
85 return std::string(reinterpret_cast<const char*>(data_.data()), data_.size());
86 }
87
ToPrettyString() const88 std::string Uuid::ToPrettyString() const {
89 std::string s(data_.size() * 2 + 4, '-');
90 // Format is 123e4567-e89b-12d3-a456-426655443322.
91 size_t j = 0;
92 for (size_t i = 0; i < data_.size(); ++i) {
93 if (i == 4 || i == 6 || i == 8 || i == 10)
94 j++;
95 s[2 * i + j] = kHexmap[(data_[data_.size() - i - 1] & 0xf0) >> 4];
96 s[2 * i + 1 + j] = kHexmap[(data_[data_.size() - i - 1] & 0x0f)];
97 }
98 return s;
99 }
100
101 } // namespace base
102 } // namespace perfetto
103