1 // Copyright (c) Facebook, Inc. and its affiliates. All Rights Reserved.
2 // This source code is licensed under both the GPLv2 (found in the
3 // COPYING file in the root directory) and Apache 2.0 License
4 // (found in the LICENSE.Apache file in the root directory).
5
6 #include "env/unique_id_gen.h"
7
8 #include <algorithm>
9 #include <array>
10 #include <cstring>
11 #include <random>
12
13 #include "port/port.h"
14 #include "rocksdb/env.h"
15 #include "rocksdb/version.h"
16 #include "util/hash.h"
17
18 namespace ROCKSDB_NAMESPACE {
19
20 namespace {
21
22 struct GenerateRawUniqueIdOpts {
23 Env* env = Env::Default();
24 bool exclude_port_uuid = false;
25 bool exclude_env_details = false;
26 bool exclude_random_device = false;
27 };
28
29 // Each of these "tracks" below should be sufficient for generating 128 bits
30 // of entropy, after hashing the raw bytes. The tracks are separable for
31 // testing purposes, but in production we combine as many tracks as possible
32 // to ensure quality results even if some environments have degraded
33 // capabilities or quality in some APIs.
34 //
35 // This approach has not been validated for use in cryptography. The goal is
36 // generating globally unique values with high probability without coordination
37 // between instances.
38 //
39 // Linux performance: EntropyTrackRandomDevice is much faster than
40 // EntropyTrackEnvDetails, which is much faster than EntropyTrackPortUuid.
41
42 struct EntropyTrackPortUuid {
43 std::array<char, 36> uuid;
44
PopulateROCKSDB_NAMESPACE::__anonaf6974ca0111::EntropyTrackPortUuid45 void Populate(const GenerateRawUniqueIdOpts& opts) {
46 if (opts.exclude_port_uuid) {
47 return;
48 }
49 std::string s;
50 port::GenerateRfcUuid(&s);
51 if (s.size() >= uuid.size()) {
52 std::copy_n(s.begin(), uuid.size(), uuid.begin());
53 }
54 }
55 };
56
57 struct EntropyTrackEnvDetails {
58 std::array<char, 64> hostname_buf;
59 int64_t process_id;
60 uint64_t thread_id;
61 int64_t unix_time;
62 uint64_t nano_time;
63
PopulateROCKSDB_NAMESPACE::__anonaf6974ca0111::EntropyTrackEnvDetails64 void Populate(const GenerateRawUniqueIdOpts& opts) {
65 if (opts.exclude_env_details) {
66 return;
67 }
68 opts.env->GetHostName(hostname_buf.data(), hostname_buf.size())
69 .PermitUncheckedError();
70 process_id = port::GetProcessID();
71 thread_id = opts.env->GetThreadID();
72 opts.env->GetCurrentTime(&unix_time).PermitUncheckedError();
73 nano_time = opts.env->NowNanos();
74 }
75 };
76
77 struct EntropyTrackRandomDevice {
78 using RandType = std::random_device::result_type;
79 static constexpr size_t kNumRandVals =
80 /* generous bits */ 192U / (8U * sizeof(RandType));
81 std::array<RandType, kNumRandVals> rand_vals;
82
PopulateROCKSDB_NAMESPACE::__anonaf6974ca0111::EntropyTrackRandomDevice83 void Populate(const GenerateRawUniqueIdOpts& opts) {
84 if (opts.exclude_random_device) {
85 return;
86 }
87 std::random_device r;
88 for (auto& val : rand_vals) {
89 val = r();
90 }
91 }
92 };
93
94 struct Entropy {
95 uint64_t version_identifier;
96 EntropyTrackRandomDevice et1;
97 EntropyTrackEnvDetails et2;
98 EntropyTrackPortUuid et3;
99
PopulateROCKSDB_NAMESPACE::__anonaf6974ca0111::Entropy100 void Populate(const GenerateRawUniqueIdOpts& opts) {
101 // If we change the format of what goes into the entropy inputs, it's
102 // conceivable there could be a physical collision in the hash input
103 // even though they are logically different. This value should change
104 // if there's a change to the "schema" here, including byte order.
105 version_identifier = (uint64_t{ROCKSDB_MAJOR} << 32) +
106 (uint64_t{ROCKSDB_MINOR} << 16) +
107 uint64_t{ROCKSDB_PATCH};
108 et1.Populate(opts);
109 et2.Populate(opts);
110 et3.Populate(opts);
111 }
112 };
113
GenerateRawUniqueIdImpl(uint64_t * a,uint64_t * b,const GenerateRawUniqueIdOpts & opts)114 void GenerateRawUniqueIdImpl(uint64_t* a, uint64_t* b,
115 const GenerateRawUniqueIdOpts& opts) {
116 Entropy e;
117 std::memset(&e, 0, sizeof(e));
118 e.Populate(opts);
119 Hash2x64(reinterpret_cast<const char*>(&e), sizeof(e), a, b);
120 }
121
122 } // namespace
123
GenerateRawUniqueId(uint64_t * a,uint64_t * b,bool exclude_port_uuid)124 void GenerateRawUniqueId(uint64_t* a, uint64_t* b, bool exclude_port_uuid) {
125 GenerateRawUniqueIdOpts opts;
126 opts.exclude_port_uuid = exclude_port_uuid;
127 assert(!opts.exclude_env_details);
128 assert(!opts.exclude_random_device);
129 GenerateRawUniqueIdImpl(a, b, opts);
130 }
131
132 #ifndef NDEBUG
TEST_GenerateRawUniqueId(uint64_t * a,uint64_t * b,bool exclude_port_uuid,bool exclude_env_details,bool exclude_random_device)133 void TEST_GenerateRawUniqueId(uint64_t* a, uint64_t* b, bool exclude_port_uuid,
134 bool exclude_env_details,
135 bool exclude_random_device) {
136 GenerateRawUniqueIdOpts opts;
137 opts.exclude_port_uuid = exclude_port_uuid;
138 opts.exclude_env_details = exclude_env_details;
139 opts.exclude_random_device = exclude_random_device;
140 GenerateRawUniqueIdImpl(a, b, opts);
141 }
142 #endif
143
SemiStructuredUniqueIdGen()144 SemiStructuredUniqueIdGen::SemiStructuredUniqueIdGen() : counter_{} {
145 saved_process_id_ = port::GetProcessID();
146 GenerateRawUniqueId(&base_upper_, &base_lower_);
147 }
148
GenerateNext(uint64_t * upper,uint64_t * lower)149 void SemiStructuredUniqueIdGen::GenerateNext(uint64_t* upper, uint64_t* lower) {
150 if (port::GetProcessID() == saved_process_id_) {
151 // Safe to increment the atomic for guaranteed uniqueness within this
152 // process lifetime. Xor slightly better than +. See
153 // https://github.com/pdillinger/unique_id
154 *lower = base_lower_ ^ counter_.fetch_add(1);
155 *upper = base_upper_;
156 } else {
157 // There must have been a fork() or something. Rather than attempting to
158 // update in a thread-safe way, simply fall back on GenerateRawUniqueId.
159 GenerateRawUniqueId(upper, lower);
160 }
161 }
162
163 } // namespace ROCKSDB_NAMESPACE
164