// @(#)root/base:$Id: TUUID.cxx 24055 2008-05-29 21:07:56Z rdm $ // 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. * *************************************************************************/ ////////////////////////////////////////////////////////////////////////// // // // 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. // // // // +-----------------------------------+ // // | 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: // // 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 duplicted 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 <string.h> #include <stdlib.h> #ifdef R__WIN32 #include "Windows4Root.h" #include <Iphlpapi.h> #else #include <unistd.h> #include <sys/time.h> #if defined(R__LINUX) && !defined(R__WINGCC) #include <sys/sysinfo.h> #endif #endif ClassImp(TUUID) //______________________________________________________________________________ TUUID::TUUID() { // Create a UUID. static uuid_time_t time_last; static UShort_t clockseq; static Bool_t firstTime = kTRUE; if (firstTime) { if (gSystem) { // try to get a unique seed per process UInt_t seed = (UInt_t) (long(gSystem->Now()) + gSystem->GetPid()); #ifdef R__WIN32 srand(seed); #else srandom(seed); #endif } GetCurrentTime(&time_last); #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) == -1) { clockseq = (clockseq + 1) & 0x3FFF; if (clockseq == 0) clockseq++; } Format(clockseq, timestamp); time_last = timestamp; fUUIDIndex = 1<<30; } //______________________________________________________________________________ TUUID::~TUUID() { // delete this TUUID //gROOT->GetUUIDs()->RemoveUUID(fUUIDIndex); } //______________________________________________________________________________ Int_t TUUID::CmpTime(uuid_time_t *t1, uuid_time_t *t2) { // Compare two time values. 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; } //______________________________________________________________________________ void TUUID::SetFromString(const char *uuid) { // Set this UUID to the value specified in uuid ((which must be in // TUUID::AsString() format). // 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; } //______________________________________________________________________________ TUUID::TUUID(const char *uuid) { // Initialize a TUUID with uuid (which must be in TUUID::AsString() format). fTimeLow = 0; fTimeMid = 0; fTimeHiAndVersion = 0; fClockSeqHiAndReserved = 0; fClockSeqLow = 0; fNode[0] = 0; if (!uuid || !*uuid) Error("TUUID", "null string not allowed"); SetFromString(uuid); } //______________________________________________________________________________ void TUUID::FillBuffer(char *&buffer) { // Stream UUID into output 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]); } //______________________________________________________________________________ void TUUID::ReadBuffer(char *&buffer) { // Stream UUID from input 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]); } //______________________________________________________________________________ void TUUID::StreamerV1(TBuffer &b) { // Stream UUID from input buffer. // This function is for the exclusive use of TDirectory::Streamer() to // read a non-versioned version of TUUID. b >> fTimeLow; b >> fTimeMid; b >> fTimeHiAndVersion; b >> fClockSeqHiAndReserved; b >> fClockSeqLow; for (UInt_t i = 0; i < 6; i++) { b >> fNode[i]; } } //______________________________________________________________________________ void TUUID::Format(UShort_t clockseq, uuid_time_t ts) { // Make a UUID from timestamp, clockseq and node id. 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(); } //______________________________________________________________________________ void TUUID::GetCurrentTime(uuid_time_t *timestamp) { // Get current time as 60 bit 100ns ticks since whenever. // Compensate for the fact that real clock resolution is less // than 100ns. const UShort_t uuids_per_tick = 1024; static uuid_time_t time_last; static UShort_t uuids_this_tick; static Bool_t init = kFALSE; if (!init) { GetSystemTime(&time_last); 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, &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; } //______________________________________________________________________________ void TUUID::GetSystemTime(uuid_time_t *timestamp) { // Get system time with 100ns precision. Time is since Oct 15, 1582. #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) + R__LL(0x01B21DD213814000); timestamp->high = (UInt_t) (uuid_time >> 32); timestamp->low = (UInt_t) (uuid_time & 0xFFFFFFFF); #endif } //______________________________________________________________________________ void TUUID::GetNodeIdentifier() { // Get node identifier. Try first to get network address, if no // network interface try random info based on some machine parameters. 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 } //______________________________________________________________________________ void TUUID::GetRandomInfo(UChar_t seed[16]) { // Get random info based on some machine parameters. #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; // 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; #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); } //______________________________________________________________________________ void TUUID::Print() const { // Print UUID. printf("%s\n", AsString()); } //______________________________________________________________________________ const char *TUUID::AsString() const { // Return UUID as string. Copy string immediately since it will be reused. static char uuid[40]; sprintf(uuid, "%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; } //______________________________________________________________________________ UShort_t TUUID::Hash() const { // Compute 16-bit hash value of the UUID. 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); } //______________________________________________________________________________ Int_t TUUID::Compare(const TUUID &u) const { // Compare two UUIDs "lexically" and return // -1 this is lexically before u // 0 this is equal to u // 1 this is lexically after u #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; } //______________________________________________________________________________ TInetAddress TUUID::GetHostAddress() const { // 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. if ((fTimeHiAndVersion >> 12) == 1) { UInt_t addr; memcpy(&addr, fNode, 4); return TInetAddress("????", addr, 0); } return TInetAddress(); } //______________________________________________________________________________ TDatime TUUID::GetTime() const { // Get time from UUID. 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 -= R__LL(0x01B21DD213814000); uuid_time /= R__LL(10000000); UInt_t tt = (UInt_t) uuid_time; dt.Set(tt); return dt; } //______________________________________________________________________________ void TUUID::GetUUID(UChar_t uuid[16]) const { // Return uuid in specified buffer (16 byte = 128 bits). memcpy(uuid, &fTimeLow, 16); } //______________________________________________________________________________ void TUUID::SetUUID(const char *uuid) { // Set this UUID to the value specified in uuid ((which must be in // TUUID::AsString() format). if (!uuid || !*uuid) Error("SetUUID", "null string not allowed"); SetFromString(uuid); }