ceph/src/rocksdb/env/unique_id_gen.cc

   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
  45   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
  64   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
  83   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
 100   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
 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
 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
 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
 144 void SemiStructuredUniqueIdGen::Reset() {
 145   saved_process_id_ = port::GetProcessID();
 146   GenerateRawUniqueId(&base_upper_, &base_lower_);
 147   counter_ = 0;
 148 }
 149
 150 void SemiStructuredUniqueIdGen::GenerateNext(uint64_t* upper, uint64_t* lower) {
 151   if (port::GetProcessID() == saved_process_id_) {
 152     // Safe to increment the atomic for guaranteed uniqueness within this
 153     // process lifetime. Xor slightly better than +. See
 154     // https://github.com/pdillinger/unique_id
 155     *lower = base_lower_ ^ counter_.fetch_add(1);
 156     *upper = base_upper_;
 157   } else {
 158     // There must have been a fork() or something. Rather than attempting to
 159     // update in a thread-safe way, simply fall back on GenerateRawUniqueId.
 160     GenerateRawUniqueId(upper, lower);
 161   }
 162 }
 163
 164 }  // namespace ROCKSDB_NAMESPACE