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 // This file is for functions that generate unique identifiers by 7 // (at least in part) by extracting novel entropy or sources of uniqueness 8 // from the execution environment. (By contrast, random.h is for algorithmic 9 // pseudorandomness.) 10 // 11 // These functions could eventually migrate to public APIs, such as in Env. 12 13 #pragma once 14 15 #include <atomic> 16 #include <cstdint> 17 18 #include "rocksdb/rocksdb_namespace.h" 19 20 namespace ROCKSDB_NAMESPACE { 21 22 // Generates a new 128-bit identifier that is universally unique 23 // (with high probability) for each call. The result is split into 24 // two 64-bit pieces. This function has NOT been validated for use in 25 // cryptography. 26 // 27 // This is used in generating DB session IDs and by Env::GenerateUniqueId 28 // (used for DB IDENTITY) if the platform does not provide a generator of 29 // RFC 4122 UUIDs or fails somehow. (Set exclude_port_uuid=true if this 30 // function is used as a fallback for GenerateRfcUuid, because no need 31 // trying it again.) 32 void GenerateRawUniqueId(uint64_t* a, uint64_t* b, 33 bool exclude_port_uuid = false); 34 35 #ifndef NDEBUG 36 // A version of above with options for challenge testing 37 void TEST_GenerateRawUniqueId(uint64_t* a, uint64_t* b, bool exclude_port_uuid, 38 bool exclude_env_details, 39 bool exclude_random_device); 40 #endif 41 42 // Generates globally unique ids with lower probability of any collisions 43 // vs. each unique id being independently random (GenerateRawUniqueId). 44 // We call this "semi-structured" because between different 45 // SemiStructuredUniqueIdGen objects, the IDs are separated by random 46 // intervals (unstructured), but within a single SemiStructuredUniqueIdGen 47 // object, the generated IDs are trivially related (structured). See 48 // https://github.com/pdillinger/unique_id for how this improves probability 49 // of no collision. In short, if we have n SemiStructuredUniqueIdGen 50 // objects each generating m IDs, the first collision is expected at 51 // around n = sqrt(2^128 / m), equivalently n * sqrt(m) = 2^64, 52 // rather than n * m = 2^64 for fully random IDs. 53 class SemiStructuredUniqueIdGen { 54 public: 55 // Initializes with random starting state (from GenerateRawUniqueId) 56 SemiStructuredUniqueIdGen(); 57 58 // Assuming no fork(), `lower` is guaranteed unique from one call 59 // to the next (thread safe). 60 void GenerateNext(uint64_t* upper, uint64_t* lower); 61 62 private: 63 uint64_t base_upper_; 64 uint64_t base_lower_; 65 std::atomic<uint64_t> counter_; 66 int64_t saved_process_id_; 67 }; 68 69 } // namespace ROCKSDB_NAMESPACE 70