// @(#)root/base:$Id$ // Author: Fons Rademakers 30/9/2001 /************************************************************************* * Copyright (C) 1995-2001, Rene Brun and Fons Rademakers. * * All rights reserved. * * * * For the licensing terms see $ROOTSYS/LICENSE. * * For the list of contributors see $ROOTSYS/README/CREDITS. * *************************************************************************/ /** \class TUUID This class defines a UUID (Universally Unique IDentifier), also known as GUIDs (Globally Unique IDentifier). A UUID is 128 bits long, and if generated according to this algorithm, is either guaranteed to be different from all other UUIDs/GUIDs generated until 3400 A.D. or extremely likely to be different. UUIDs were originally used in the Network Computing System (NCS) and later in the Open Software Foundation's (OSF) Distributed Computing Environment (DCE). Structure of universal unique IDs (UUIDs). Depending on the network data representation, the multi- octet unsigned integer fields are subject to byte swapping when communicated between dissimilar endian machines. ~~~ {.cpp} +-----------------------------------+ | low 32 bits of time | 0-3 .fTimeLow +-------------------------------+---- | mid 16 bits of time | 4-5 .fTimeMid +-------+-----------------------+ | vers. | hi 12 bits of time | 6-7 .fTimeHiAndVersion +-------+-------+---------------+ |Res | clkSeqHi | 8 .fClockSeqHiAndReserved +---------------+ | clkSeqLow | 9 .fClockSeqLow +---------------+------------------+ | node ID | 10-15 .fNode +----------------------------------+ ~~~ The adjusted time stamp is split into three fields, and the clockSeq is split into two fields. The timestamp is a 60-bit value. For UUID version 1, this is represented by Coordinated Universal Time (UTC/GMT) as a count of 100-nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of Gregorian reform to the Christian calendar). The version number is multiplexed in the 4 most significant bits of the 'fTimeHiAndVersion' field. There are two defined versions: ~~~ {.cpp} MSB <--- Version 4-Bit Code Description ------------------------------------------------------------ | 1 0 0 0 1 DCE version, as specified herein. | 2 0 0 1 0 DCE Security version, with | embedded POSIX UIDs. | 3 0 0 1 1 node id is a random value ------------------------------------------------------------ ~~~ ## Clock Sequence The clock sequence value must be changed whenever: The UUID generator detects that the local value of UTC has gone backward; this may be due to re-syncing of the system clock. While a node is operational, the UUID service always saves the last UTC used to create a UUID. Each time a new UUID is created, the current UTC is compared to the saved value and if either the current value is less or the saved value was lost, then the clock sequence is incremented modulo 16,384, thus avoiding production of duplicated UUIDs. The clock sequence must be initialized to a random number to minimize the correlation across system. This provides maximum protection against node identifiers that may move or switch from system to system rapidly. ## Clock Adjustment UUIDs may be created at a rate greater than the system clock resolution. Therefore, the system must also maintain an adjustment value to be added to the lower-order bits of the time. Logically, each time the system clock ticks, the adjustment value is cleared. Every time a UUID is generated, the current adjustment value is read and incremented, and then added to the UTC time field of the UUID. ## Clock Overrun The 100-nanosecond granularity of time should prove sufficient even for bursts of UUID production in the next generation of high-performance multiprocessors. If a system overruns the clock adjustment by requesting too many UUIDs within a single system clock tick, the UUID generator will stall until the system clock catches up. */ #include "TROOT.h" #include "TUUID.h" #include "TError.h" #include "TSystem.h" #include "TInetAddress.h" #include "TMD5.h" #include "Bytes.h" #include "TVirtualMutex.h" #include "ThreadLocalStorage.h" #include #include #ifdef R__WIN32 #include "Windows4Root.h" #include #else #include #include #if defined(R__LINUX) && !defined(R__WINGCC) #include #endif #endif ClassImp(TUUID) //////////////////////////////////////////////////////////////////////////////// /// Create a UUID. TUUID::TUUID() { TTHREAD_TLS(uuid_time_t) time_last; TTHREAD_TLS(UShort_t) clockseq(0); TTHREAD_TLS(Bool_t) firstTime(kTRUE); uuid_time_t *time_last_ptr = TTHREAD_TLS_PTR(time_last); if (firstTime) { R__LOCKGUARD2(gROOTMutex); // rand and random are not thread safe. if (gSystem) { // try to get a unique seed per process UInt_t seed = (UInt_t) (Long64_t(gSystem->Now()) + gSystem->GetPid()); #ifdef R__WIN32 srand(seed); #else srandom(seed); #endif } GetCurrentTime(time_last_ptr); #ifdef R__WIN32 clockseq = 1+(UShort_t)(65536*rand()/(RAND_MAX+1.0)); #else clockseq = 1+(UShort_t)(65536*random()/(RAND_MAX+1.0)); #endif firstTime = kFALSE; } uuid_time_t timestamp; // get current time GetCurrentTime(×tamp); // if clock went backward change clockseq if (CmpTime(×tamp, time_last_ptr) == -1) { clockseq = (clockseq + 1) & 0x3FFF; if (clockseq == 0) clockseq++; } Format(clockseq, timestamp); time_last = timestamp; fUUIDIndex = 1<<30; } //////////////////////////////////////////////////////////////////////////////// /// delete this TUUID TUUID::~TUUID() { //gROOT->GetUUIDs()->RemoveUUID(fUUIDIndex); } //////////////////////////////////////////////////////////////////////////////// /// Compare two time values. Int_t TUUID::CmpTime(uuid_time_t *t1, uuid_time_t *t2) { if (t1->high < t2->high) return -1; if (t1->high > t2->high) return 1; if (t1->low < t2->low) return -1; if (t1->low > t2->low) return 1; return 0; } //////////////////////////////////////////////////////////////////////////////// /// Set this UUID to the value specified in uuid ((which must be in /// TUUID::AsString() format). void TUUID::SetFromString(const char *uuid) { // Format is tttttttt-tttt-cccc-cccc-nnnnnnnnnnnn. Long_t timeLo; int timeMid; int timeHiAndVersion; int clockSeqHiAndRes; int clockSeqLo; int node[6]; sscanf(uuid, "%8lx-%4x-%4x-%2x%2x-%2x%2x%2x%2x%2x%2x", &timeLo, &timeMid, &timeHiAndVersion, &clockSeqHiAndRes, &clockSeqLo, &node[0], &node[1], &node[2], &node[3], &node[4], &node[5]); // Note that we're going through this agony because scanf is // defined to know only to scan into "int"s or "long"s. fTimeLow = (UInt_t) timeLo; fTimeMid = (UShort_t) timeMid; fTimeHiAndVersion = (UShort_t) timeHiAndVersion; fClockSeqHiAndReserved = (UChar_t) clockSeqHiAndRes; fClockSeqLow = (UChar_t) clockSeqLo; fNode[0] = (UChar_t) node[0]; fNode[1] = (UChar_t) node[1]; fNode[2] = (UChar_t) node[2]; fNode[3] = (UChar_t) node[3]; fNode[4] = (UChar_t) node[4]; fNode[5] = (UChar_t) node[5]; fUUIDIndex = 1<<30; } //////////////////////////////////////////////////////////////////////////////// /// Initialize a TUUID with uuid (which must be in TUUID::AsString() format). TUUID::TUUID(const char *uuid) { fTimeLow = 0; fTimeMid = 0; fTimeHiAndVersion = 0; fClockSeqHiAndReserved = 0; fClockSeqLow = 0; fNode[0] = 0; fUUIDIndex = 0; if (!uuid || !*uuid) Error("TUUID", "null string not allowed"); else SetFromString(uuid); } //////////////////////////////////////////////////////////////////////////////// /// Stream UUID into output buffer. void TUUID::FillBuffer(char *&buffer) { Version_t version = TUUID::Class_Version(); tobuf(buffer, version); tobuf(buffer, fTimeLow); tobuf(buffer, fTimeMid); tobuf(buffer, fTimeHiAndVersion); tobuf(buffer, fClockSeqHiAndReserved); tobuf(buffer, fClockSeqLow); for (Int_t i = 0; i < 6; i++) tobuf(buffer, fNode[i]); } //////////////////////////////////////////////////////////////////////////////// /// Stream UUID from input buffer. void TUUID::ReadBuffer(char *&buffer) { Version_t version; frombuf(buffer, &version); frombuf(buffer, &fTimeLow); frombuf(buffer, &fTimeMid); frombuf(buffer, &fTimeHiAndVersion); frombuf(buffer, &fClockSeqHiAndReserved); frombuf(buffer, &fClockSeqLow); for (Int_t i = 0; i < 6; i++) frombuf(buffer, &fNode[i]); } //////////////////////////////////////////////////////////////////////////////// /// Stream UUID from input buffer. /// This function is for the exclusive use of TDirectory::Streamer() to /// read a non-versioned version of TUUID. void TUUID::StreamerV1(TBuffer &b) { b >> fTimeLow; b >> fTimeMid; b >> fTimeHiAndVersion; b >> fClockSeqHiAndReserved; b >> fClockSeqLow; for (UInt_t i = 0; i < 6; i++) { b >> fNode[i]; } } //////////////////////////////////////////////////////////////////////////////// /// Make a UUID from timestamp, clockseq and node id. void TUUID::Format(UShort_t clockseq, uuid_time_t ts) { fTimeLow = ts.low; fTimeMid = (UShort_t)(ts.high & 0xFFFF); fTimeHiAndVersion = (UShort_t)((ts.high >> 16) & 0x0FFF); fTimeHiAndVersion |= (1 << 12); fClockSeqLow = clockseq & 0xFF; fClockSeqHiAndReserved = (clockseq & 0x3F00) >> 8; fClockSeqHiAndReserved |= 0x80; GetNodeIdentifier(); } //////////////////////////////////////////////////////////////////////////////// /// Get current time as 60 bit 100ns ticks since whenever. /// Compensate for the fact that real clock resolution is less /// than 100ns. void TUUID::GetCurrentTime(uuid_time_t *timestamp) { const UShort_t uuids_per_tick = 1024; TTHREAD_TLS(uuid_time_t) time_last; TTHREAD_TLS(UShort_t) uuids_this_tick(0); TTHREAD_TLS(Bool_t) init(kFALSE); uuid_time_t *time_last_ptr = TTHREAD_TLS_PTR(time_last); if (!init) { GetSystemTime(time_last_ptr); uuids_this_tick = uuids_per_tick; init = kTRUE; } uuid_time_t time_now; while (1) { GetSystemTime(&time_now); // if clock reading changed since last UUID generated if (CmpTime(time_last_ptr, &time_now)) { // reset count of uuid's generated with this clock reading uuids_this_tick = 0; break; } if (uuids_this_tick < uuids_per_tick) { uuids_this_tick++; break; } // going too fast for our clock; spin } time_last = time_now; if (uuids_this_tick != 0) { if (time_now.low & 0x80000000) { time_now.low += uuids_this_tick; if (!(time_now.low & 0x80000000)) time_now.high++; } else time_now.low += uuids_this_tick; } timestamp->high = time_now.high; timestamp->low = time_now.low; } //////////////////////////////////////////////////////////////////////////////// /// Get system time with 100ns precision. Time is since Oct 15, 1582. void TUUID::GetSystemTime(uuid_time_t *timestamp) { #ifdef R__WIN32 ULARGE_INTEGER time; GetSystemTimeAsFileTime((FILETIME *)&time); // NT keeps time in FILETIME format which is 100ns ticks since // Jan 1, 1601. UUIDs use time in 100ns ticks since Oct 15, 1582. // The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec) // + 18 years and 5 leap days. time.QuadPart += (unsigned __int64) (1000*1000*10) // seconds * (unsigned __int64) (60 * 60 * 24) // days * (unsigned __int64) (17+30+31+365*18+5); // # of days timestamp->high = time.HighPart; timestamp->low = time.LowPart; #else struct timeval tp; gettimeofday(&tp, 0); // Offset between UUID formatted times and Unix formatted times. // UUID UTC base time is October 15, 1582. // Unix base time is January 1, 1970. ULong64_t uuid_time = ((ULong64_t)tp.tv_sec * 10000000) + (tp.tv_usec * 10) + 0x01B21DD213814000LL; timestamp->high = (UInt_t) (uuid_time >> 32); timestamp->low = (UInt_t) (uuid_time & 0xFFFFFFFF); #endif } //////////////////////////////////////////////////////////////////////////////// /// Get node identifier. Try first to get network address, if no /// network interface try random info based on some machine parameters. void TUUID::GetNodeIdentifier() { static UInt_t adr = 0; if (gSystem) { #ifndef R__WIN32 if (!adr) { TInetAddress addr = gSystem->GetHostByName(gSystem->HostName()); if (addr.IsValid()) adr = addr.GetAddress(); else adr = 1; // illegal address } #else // this way to get the machine's IP address is needed because // GetHostByName() on Win32 contacts the DNS which we don't want // as firewall tools like ZoneAlarm are likely to catch it and // alarm the user if (!adr) { PIP_ADAPTER_INFO ainfo = (PIP_ADAPTER_INFO) malloc(sizeof(IP_ADAPTER_INFO)); ULONG buflen = sizeof(IP_ADAPTER_INFO); DWORD stat = GetAdaptersInfo(ainfo, &buflen); if (stat == ERROR_BUFFER_OVERFLOW) { free(ainfo); ainfo = (PIP_ADAPTER_INFO) malloc(buflen); stat = GetAdaptersInfo(ainfo, &buflen); } if (stat != ERROR_SUCCESS) adr = 1; // illegal address else { // take address of first adapter PIP_ADAPTER_INFO adapter = ainfo; int a, b, c, d; sscanf(adapter->IpAddressList.IpAddress.String, "%d.%d.%d.%d", &a, &b, &c, &d); adr = (a << 24) | (b << 16) | (c << 8) | d; } free(ainfo); } #endif if (adr > 2) { memcpy(fNode, &adr, 4); fNode[4] = 0xbe; fNode[5] = 0xef; return; } } static UChar_t seed[16]; if (adr < 2) { GetRandomInfo(seed); seed[0] |= 0x80; if (gSystem) adr = 2; // illegal address } memcpy(fNode, seed, sizeof(fNode)); fTimeHiAndVersion |= (3 << 12); // version == 3: random node info } //////////////////////////////////////////////////////////////////////////////// /// Get random info based on some machine parameters. void TUUID::GetRandomInfo(UChar_t seed[16]) { #ifdef R__WIN32 struct randomness { MEMORYSTATUS m; SYSTEM_INFO s; FILETIME t; LARGE_INTEGER pc; DWORD tc; DWORD l; char hostname[MAX_COMPUTERNAME_LENGTH + 1]; }; randomness r; memset(&r, 0, sizeof(r)); // zero also padding bytes // memory usage stats GlobalMemoryStatus(&r.m); // random system stats GetSystemInfo(&r.s); // 100ns resolution time of day GetSystemTimeAsFileTime(&r.t); // high resolution performance counter QueryPerformanceCounter(&r.pc); // milliseconds since last boot r.tc = GetTickCount(); r.l = MAX_COMPUTERNAME_LENGTH + 1; GetComputerName(r.hostname, &r.l); #else struct randomness { #if defined(R__LINUX) && !defined(R__WINGCC) struct sysinfo s; #endif struct timeval t; char hostname[257]; }; randomness r; memset(&r, 0, sizeof(r)); // zero also padding bytes #if defined(R__LINUX) && !defined(R__WINGCC) sysinfo(&r.s); #endif gettimeofday(&r.t, 0); gethostname(r.hostname, 256); #endif TMD5 md5; md5.Update((UChar_t *)&r, sizeof(randomness)); md5.Final(seed); } //////////////////////////////////////////////////////////////////////////////// /// Print UUID. void TUUID::Print() const { printf("%s\n", AsString()); } //////////////////////////////////////////////////////////////////////////////// /// Return UUID as string. Copy string immediately since it will be reused. const char *TUUID::AsString() const { static char uuid[40]; snprintf(uuid,40, "%08x-%04x-%04x-%02x%02x-%02x%02x%02x%02x%02x%02x", fTimeLow, fTimeMid, fTimeHiAndVersion, fClockSeqHiAndReserved, fClockSeqLow, fNode[0], fNode[1], fNode[2], fNode[3], fNode[4], fNode[5]); return uuid; } //////////////////////////////////////////////////////////////////////////////// /// Compute 16-bit hash value of the UUID. UShort_t TUUID::Hash() const { Short_t c0 = 0, c1 = 0, x, y; char *c = (char *) &fTimeLow; // For speed lets unroll the following loop: // for (i = 0; i < 16; i++) { // c0 += *c++; // c1 += c0; // } c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; c0 += *c++; c1 += c0; // Calculate the value for "First octet" of the hash x = -c1 % 255; if (x < 0) x += 255; // Calculate the value for "second octet" of the hash y = (c1 - c0) % 255; if (y < 0) y += 255; return UShort_t((y << 8) + x); } //////////////////////////////////////////////////////////////////////////////// /// Compare two UUIDs "lexically" and return /// - -1 this is lexically before u /// - 0 this is equal to u /// - 1 this is lexically after u Int_t TUUID::Compare(const TUUID &u) const { #define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1; CHECK(fTimeLow, u.fTimeLow) CHECK(fTimeMid, u.fTimeMid) CHECK(fTimeHiAndVersion, u.fTimeHiAndVersion) CHECK(fClockSeqHiAndReserved, u.fClockSeqHiAndReserved) CHECK(fClockSeqLow, u.fClockSeqLow) for (int i = 0; i < 6; i++) { if (fNode[i] < u.fNode[i]) return -1; if (fNode[i] > u.fNode[i]) return 1; } return 0; } //////////////////////////////////////////////////////////////////////////////// /// Get address of host encoded in UUID. If host id is not an ethernet /// address, but random info, then the returned TInetAddress is not valid. TInetAddress TUUID::GetHostAddress() const { if ((fTimeHiAndVersion >> 12) == 1) { UInt_t addr; memcpy(&addr, fNode, 4); return TInetAddress("????", addr, 0); } return TInetAddress(); } //////////////////////////////////////////////////////////////////////////////// /// Get time from UUID. TDatime TUUID::GetTime() const { TDatime dt; uuid_time_t ts; ts.low = fTimeLow; ts.high = (UInt_t)fTimeMid; ts.high |= (UInt_t)((fTimeHiAndVersion & 0x0FFF) << 16); // Offset between UUID formatted times and Unix formatted times. // UUID UTC base time is October 15, 1582. // Unix base time is January 1, 1970. ULong64_t high = ts.high; ULong64_t uuid_time = (high << 32) + ts.low; uuid_time -= 0x01B21DD213814000LL; uuid_time /= 10000000LL; UInt_t tt = (UInt_t) uuid_time; dt.Set(tt); return dt; } //////////////////////////////////////////////////////////////////////////////// /// Return uuid in specified buffer (16 byte = 128 bits). void TUUID::GetUUID(UChar_t uuid[16]) const { memcpy(uuid, &fTimeLow, 16); } //////////////////////////////////////////////////////////////////////////////// /// Set this UUID to the value specified in uuid ((which must be in /// TUUID::AsString() format). void TUUID::SetUUID(const char *uuid) { if (!uuid || !*uuid) Error("SetUUID", "null string not allowed"); else SetFromString(uuid); } //////////////////////////////////////////////////////////////////////////////// /// Input operator. Delegate to Streamer. TBuffer &operator<<(TBuffer &buf, const TUUID &uuid) { R__ASSERT( buf.IsWriting() ); const_cast(uuid).Streamer(buf); return buf; }