idnits 2.17.1 draft-mealling-uuid-urn-00.txt: Checking boilerplate required by RFC 5378 and the IETF Trust (see https://trustee.ietf.org/license-info): ---------------------------------------------------------------------------- ** Looks like you're using RFC 2026 boilerplate. This must be updated to follow RFC 3978/3979, as updated by RFC 4748. Checking nits according to https://www.ietf.org/id-info/1id-guidelines.txt: ---------------------------------------------------------------------------- == No 'Intended status' indicated for this document; assuming Proposed Standard Checking nits according to https://www.ietf.org/id-info/checklist : ---------------------------------------------------------------------------- ** The document seems to lack an IANA Considerations section. (See Section 2.2 of https://www.ietf.org/id-info/checklist for how to handle the case when there are no actions for IANA.) ** There are 23 instances of too long lines in the document, the longest one being 3 characters in excess of 72. ** The abstract seems to contain references ([2], [1]), which it shouldn't. Please replace those with straight textual mentions of the documents in question. ** The document seems to lack a both a reference to RFC 2119 and the recommended RFC 2119 boilerplate, even if it appears to use RFC 2119 keywords. RFC 2119 keyword, line 369: '... they MAY use local time instead of ...' RFC 2119 keyword, line 370: '... the system. This is NOT RECOMMENDED,...' RFC 2119 keyword, line 400: '...e clock sequence MUST be originally (i...' RFC 2119 keyword, line 404: '...he initial value MUST NOT be correlate...' RFC 2119 keyword, line 518: '...nterval, the UUID service MUST either:...' (3 more instances...) Miscellaneous warnings: ---------------------------------------------------------------------------- == The copyright year in the RFC 3978 Section 5.4 Copyright Line does not match the current year == Line 321 has weird spacing: '...version uns...' == Line 325 has weird spacing: '...nd_rese unsig...' == Line 636 has weird spacing: '... 0-3 of time_...' == Line 638 has weird spacing: '... 0-1 of time_...' == Line 640 has weird spacing: '... 0-1 of time_...' == (4 more instances...) -- The document seems to lack a disclaimer for pre-RFC5378 work, but may have content which was first submitted before 10 November 2008. If you have contacted all the original authors and they are all willing to grant the BCP78 rights to the IETF Trust, then this is fine, and you can ignore this comment. If not, you may need to add the pre-RFC5378 disclaimer. (See the Legal Provisions document at https://trustee.ietf.org/license-info for more information.) -- The document date (October 2002) is 7857 days in the past. Is this intentional? -- Found something which looks like a code comment -- if you have code sections in the document, please surround them with '' and '' lines. Checking references for intended status: Proposed Standard ---------------------------------------------------------------------------- (See RFCs 3967 and 4897 for information about using normative references to lower-maturity documents in RFCs) == Missing Reference: '6' is mentioned on line 1266, but not defined == Missing Reference: '16' is mentioned on line 1380, but not defined == Missing Reference: '0' is mentioned on line 1295, but not defined == Missing Reference: '257' is mentioned on line 1385, but not defined -- Possible downref: Non-RFC (?) normative reference: ref. '1' -- Possible downref: Non-RFC (?) normative reference: ref. '2' ** Downref: Normative reference to an Informational RFC: RFC 1321 (ref. '3') ** Obsolete normative reference: RFC 2141 (ref. '4') (Obsoleted by RFC 8141) -- Possible downref: Non-RFC (?) normative reference: ref. '5' Summary: 7 errors (**), 0 flaws (~~), 12 warnings (==), 6 comments (--). Run idnits with the --verbose option for more detailed information about the items above. -------------------------------------------------------------------------------- 2 Network Working Group M. Mealling 3 Internet-Draft VeriSign, Inc. 4 Expires: April 1, 2003 P. Leach 5 Microsoft 6 R. Salz 7 Datapower Technology, Inc. 8 October 2002 10 A UUID URN Namespace 11 draft-mealling-uuid-urn-00.txt 13 Status of this Memo 15 This document is an Internet-Draft and is in full conformance with 16 all provisions of Section 10 of RFC2026. 18 Internet-Drafts are working documents of the Internet Engineering 19 Task Force (IETF), its areas, and its working groups. Note that 20 other groups may also distribute working documents as Internet- 21 Drafts. 23 Internet-Drafts are draft documents valid for a maximum of six months 24 and may be updated, replaced, or obsoleted by other documents at any 25 time. It is inappropriate to use Internet-Drafts as reference 26 material or to cite them other than as "work in progress." 28 The list of current Internet-Drafts can be accessed at http:// 29 www.ietf.org/ietf/1id-abstracts.txt. 31 The list of Internet-Draft Shadow Directories can be accessed at 32 http://www.ietf.org/shadow.html. 34 This Internet-Draft will expire on April 1, 2003. 36 Copyright Notice 38 Copyright (C) The Internet Society (2002). All Rights Reserved. 40 Abstract 42 This specification defines a Uniform Resource Name namespace for 43 UUIDs ( (Universally Unique IDentifier), also known as GUIDs 44 (Globally Unique IDentifier). A UUID is 128 bits long, and if 45 generated according to the one of the mechanisms in this document, is 46 either guaranteed to be different from all other UUIDs/GUIDs 47 generated until 3400 A.D. or extremely likely to be different 48 (depending on the mechanism chosen). UUIDs were originally used in 49 the Network Computing System (NCS) [1] and later in the Open Software 50 Foundation's (OSF) Distributed Computing Environment [2]. 52 This specification is derived from the latter specification with the 53 kind permission of the OSF. The original version of this document 54 was written by Paul Leach and Rich Salz but was unpublished for 55 several years. This is an updated version incorporated as part of 56 the URN registration document. 58 Table of Contents 60 1. Introduction . . . . . . . . . . . . . . . . . . . . . . . . 4 61 2. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . 4 62 3. Namespace Registration Template . . . . . . . . . . . . . . 4 63 4. Specification . . . . . . . . . . . . . . . . . . . . . . . 7 64 4.1 Format . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 65 4.1.1 Variant . . . . . . . . . . . . . . . . . . . . . . . . . . 7 66 4.1.2 UUID Layout . . . . . . . . . . . . . . . . . . . . . . . . 8 67 4.1.3 Version . . . . . . . . . . . . . . . . . . . . . . . . . . 9 68 4.1.4 Timestamp . . . . . . . . . . . . . . . . . . . . . . . . . 10 69 4.1.5 Clock sequence . . . . . . . . . . . . . . . . . . . . . . . 10 70 4.1.6 Node . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 71 4.1.7 Nil UUID . . . . . . . . . . . . . . . . . . . . . . . . . . 11 72 4.2 Algorithms for creating a time-based UUID . . . . . . . . . 12 73 4.2.1 Basic algorithm . . . . . . . . . . . . . . . . . . . . . . 12 74 4.2.2 Reading stable storage . . . . . . . . . . . . . . . . . . . 13 75 4.2.3 System clock resolution . . . . . . . . . . . . . . . . . . 13 76 4.2.4 Writing stable storage . . . . . . . . . . . . . . . . . . . 14 77 4.2.5 Sharing state across processes . . . . . . . . . . . . . . . 14 78 4.2.6 UUID Generation details . . . . . . . . . . . . . . . . . . 14 79 4.3 Algorithm for creating a name-based UUID . . . . . . . . . . 15 80 5. Algorithms for creating a UUID from truly random or 81 pseudo-random numbers . . . . . . . . . . . . . . . . . . . 16 82 6. Byte order of UUIDs . . . . . . . . . . . . . . . . . . . . 17 83 7. Node IDs when no IEEE 802 network card is available . . . . 17 84 8. Obtaining IEEE 802 addresses . . . . . . . . . . . . . . . . 19 85 9. Community Considerations . . . . . . . . . . . . . . . . . . 19 86 10. Security Considerations . . . . . . . . . . . . . . . . . . 20 87 11. Acknowledgements . . . . . . . . . . . . . . . . . . . . . . 20 88 Normative References . . . . . . . . . . . . . . . . . . . . 20 89 Authors' Addresses . . . . . . . . . . . . . . . . . . . . . 21 90 A. Appendix A - UUID Sample Implementation . . . . . . . . . . 21 91 B. Appendix B - Sample output of utest . . . . . . . . . . . . 33 92 C. Appendix C - Some name space IDs . . . . . . . . . . . . . . 33 93 Full Copyright Statement . . . . . . . . . . . . . . . . . . 35 95 1. Introduction 97 This specification defines a Uniform Resource Name (URN) [4] 98 namespace for UUIDs (Universally Unique IDentifiers), also known as 99 GUIDs (Globally Unique IDentifiers). A UUID is 128 bits long, and if 100 generated according to the one of the mechanisms in this document, is 101 either guaranteed to be different from all other UUIDs/GUIDs 102 generated until 3400 A.D. or extremely likely to be different 103 (depending on the mechanism chosen). 105 It is extremely important to note that most of the text in this 106 document originated with Paul Leach and Rich Salz. It has been 107 modified in order to be compliant with URN namespace registration 108 procedures. Nothing in this document should be construed to mean 109 that it supercedes the DCE standards that defined UUIDs to begin 110 with. The information here is simply meant as a concise guide for 111 those wishing to implement services using UUIDs as URNs. 113 2. Motivation 115 One of the main reasons for using UUIDs is that no centralized 116 authority is required to administer them (beyond the one that 117 allocates IEEE 802.1 node identifiers). As a result, generation on 118 demand can be completely automated, and they can be used for a wide 119 variety of purposes. The UUID generation algorithm described here 120 supports very high allocation rates: 10 million per second per 121 machine if you need it, so that they could even be used as 122 transaction IDs. 124 UUIDs are fixed-size (128-bits) which is reasonably small relative to 125 other alternatives. This fixed, relatively small size lends itself 126 well to sorting, ordering, and hashing of all sorts, storing in 127 databases, simple allocation, and ease of programming in general. 129 Since UUIDs are unique and persistent given correct time settings, 130 they make excellent Uniform Resource Names. The unique ability to 131 generate new UUIDs without a registration process allows for UUIDs to 132 be one the URN with the lowest minting cost. 134 3. Namespace Registration Template 136 Namespace ID: UUID 138 Registration Information: 139 Registration date: 2002-10-01 141 Declared registrant of the namespace: 142 JTC 1/SC6 (ASN.1 Rapporteur Group) 144 Declaration of syntactic structure: 145 A UUID is an identifier that is unique across both space and time, 146 with respect to the space of all UUIDs. To be precise, the UUID 147 consists of a finite bit space. Thus the time value used for 148 constructing a UUID is limited and will roll over in the future 149 (approximately at A.D. 3400, based on the specified algorithm). 150 A UUID can be used for multiple purposes, from tagging objects 151 with an extremely short lifetime, to reliably identifying very 152 persistent objects across a network. 154 The internal representation of a UUID is a specfic sequence of 155 bits in memory. In order to accurately represent a UUID as a URN 156 it is necessary to convert the bit sequence to a string 157 representation. The exact sequence and meaning of this bit 158 sequence is covered in Section 4 160 Each field is treated as an integer and has its value printed as a 161 zero-filled hexadecimal digit string with the most significant 162 digit first. The hexadecimal values a to f inclusive are output 163 as lower case characters, and are case insensitive on input. The 164 sequence is the same as the UUID constructed type. 166 The formal definition of the UUID string representation is 167 provided by the following extended BNF: 169 UUID = "-" "-" 170 "-" 171 172 "-" 173 time_low = 4* 174 time_mid = 2* 175 time_high_and_version = 2* 176 clock_seq_and_reserved = 177 clock_seq_low = 178 node = 6* 180 hexDigit = 181 "0" | "1" | "2" | "3" | "4" | "5" | "6" | "7" | "8" | "9" 182 | "a" | "b" | "c" | "d" | "e" | "f" 183 | "A" | "B" | "C" | "D" | "E" | "F" 185 The following is an example of the string representation of a UUID 186 as a URN: 188 urn:uuid:f81d4fae-7dec-11d0-a765-00a0c91e6bf6 190 Relevant ancillary documentation: 191 [2] 193 Identifier uniqueness considerations: 194 Due to the combination of spacial and temporal components and the 195 fact that spatial uniqueness is maintained via 802.1 MAC 196 addresses, all UUIDs that are generated according to the standards 197 and techniques mentioned in this document are unique from all 198 other UUIDs that have been or will be assigned. 200 Identifier persistence considerations: 201 UUIDs are inherently very difficult to resolve in a global sense. 202 This, coupled with the fact that UUIDs are temporally unique 203 within their spatial context, ensures that UUIDs will remain as 204 persistent as possible. 206 Process of identifier assignment: 207 The generation of UUIDs does not require that a registration 208 authority be contacted for each identifier. Instead, it requires 209 a unique value over space for each UUID generator. This spatially 210 unique value is specified as an IEEE 802 address, which is usually 211 already available to network-connected systems. This 48-bit 212 address can be assigned based on an address block obtained through 213 the IEEE registration authority. This section of the UUID 214 specification assumes the availability of an IEEE 802 address to a 215 system desiring to generate a UUID, but if one is not available 216 Section 7 specifies a way to generate a probabilistically unique 217 one that can not conflict with any properly assigned IEEE 802 218 address. 220 Process for identifier resolution: 221 Due to UUIDs not being globally resolvable, this value is not 222 applicable. 224 Rules for Lexical Equivalence: 225 Consider each field of the UUID to be an unsigned integer as shown 226 in the table in section 3.1. Then, to compare a pair of UUIDs, 227 arithmetically compare the corresponding fields from each UUID in 228 order of significance and according to their data type. Two UUIDs 229 are equal if and only if all the corresponding fields are equal. 231 Note: as a practical matter, on many systems comparison of two 232 UUIDs for equality can be performed simply by comparing the 128 233 bits of their in-memory representation considered as a 128 bit 234 unsigned integer. Here, it is presumed that by the time the in- 235 memory representation is obtained the appropriate byte-order 236 canonicalizations have been carried out. 238 Two UUIDs allocated according to the same variant can also be 239 ordered lexicographically. For the UUID variant herein defined, 240 the first of two UUIDs follows the second if the most significant 241 field in which the UUIDs differ is greater for the first UUID. 242 The first of a pair of UUIDs precedes the second if the most 243 significant field in which the UUIDs differ is greater for the 244 second UUID. 246 Conformance with URN Syntax: 247 The string representation of a UUID produces a string that is 248 fully compatible with the URN syntax. When converting from an 249 bit-oriented, in-memory representation of a UUID into a URN, care 250 must be taken to strictly adhere to the byte order issues 251 mentioned in the string representation section. 253 Validation mechanism: 254 Appart from determining if the timestamp portion of the UUID is in 255 the future and thus no yet assignable, there is no mechanism for 256 determining if a UUID is 'valid' in any real sense. 258 Scope: 259 UUIDs are global in scope. 261 4. Specification 263 4.1 Format 265 In its most general form, all that can be said of the UUID format is 266 that a UUID is 16 octets, and that some bits of octet 8 of the UUID 267 called the variant field (specified in the next section) determine 268 finer structure. 270 4.1.1 Variant 272 The variant field determines the layout of the UUID. That is, the 273 interpretation of all other bits in the UUID depends on the setting 274 of the bits in the variant field. The variant field consists of a 275 variable number of the msbs of octet 8 of the UUID. 277 The following table lists the contents of the variant field. 279 Msb0 Msb1 Msb2 Description 281 0 - - Reserved, NCS backward compatibility. 283 1 0 - The variant specified in this document. 285 1 1 0 Reserved, Microsoft Corporation backward 286 compatibility 288 1 1 1 Reserved for future definition. 290 Other UUID variants may not interoperate with the UUID variant 291 specified in this document, where interoperability is defined as the 292 applicability of operations such as string conversion and lexical 293 ordering across different systems. However, UUIDs allocated 294 according to the stricture of different variants, though they may 295 define different interpretations of the bits outside the variant 296 field, will not result in duplicate UUID allocation, because of the 297 differing values of the variant field itself. 299 The remaining fields described below (version, timestamp, etc.) are 300 defined only for the UUID variant noted above. 302 4.1.2 UUID Layout 304 The following table gives the format of a UUID for the variant 305 specified herein. The UUID consists of a record of 16 octets. To 306 minimize confusion about bit assignments within octets, the UUID 307 record definition is defined only in terms of fields that are 308 integral numbers of octets. The fields are in order of significance 309 for comparison purposes, with "time_low" the most significant, and 310 "node" the least significant. 312 Field Data Type Octet Note 313 # 315 time_low unsigned 32 0-3 The low field of the 316 bit integer timestamp. 318 time_mid unsigned 16 4-5 The middle field of the 319 bit integer timestamp. 321 time_hi_and_version unsigned 16 6-7 The high field of the 322 bit integer timestamp multiplexed 323 with the version number. 325 clock_seq_hi_and_rese unsigned 8 8 The high field of the 326 rved bit integer clock sequence 327 multiplexed with the 328 variant. 330 clock_seq_low unsigned 8 9 The low field of the 331 bit integer clock sequence. 333 node unsigned 48 10-15 The spatially unique 334 bit integer node identifier. 336 4.1.3 Version 338 The version number is in the most significant 4 bits of the time 339 stamp (time_hi_and_version). 341 The following table lists currently defined versions of the UUID. 343 Msb0 Msb1 Msb2 Msb3 Version Description 345 0 0 0 1 1 The time-based version 346 specified in this 347 document. 349 0 0 1 0 2 Reserved for DCE 350 Security version, with 351 embedded POSIX UIDs. 353 0 0 1 1 3 The name-based version 354 specified in this document 356 0 1 0 0 4 The randomly or pseudo- 357 randomly generated 358 version specified in 359 this document 361 4.1.4 Timestamp 363 The timestamp is a 60 bit value. For UUID version 1, this is 364 represented by Coordinated Universal Time (UTC) as a count of 100- 365 nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of 366 Gregorian reform to the Christian calendar). 368 For systems that do not have UTC available, but do have local time, 369 they MAY use local time instead of UTC, as long as they do so 370 consistently throughout the system. This is NOT RECOMMENDED, 371 however, and it should be noted that all that is needed to generate 372 UTC, given local time, is a time zone offset. 374 For UUID version 3, it is a 60 bit value constructed from a name. 376 For UUID version 4, it is a randomly or pseudo-randomly generated 60 377 bit value. 379 4.1.5 Clock sequence 381 For UUID version 1, the clock sequence is used to help avoid 382 duplicates that could arise when the clock is set backwards in time 383 or if the node ID changes. 385 If the clock is set backwards, or even might have been set backwards 386 (e.g., while the system was powered off), and the UUID generator can 387 not be sure that no UUIDs were generated with timestamps larger than 388 the value to which the clock was set, then the clock sequence has to 389 be changed. If the previous value of the clock sequence is known, it 390 can be just incremented; otherwise it should be set to a random or 391 high-quality pseudo random value. 393 Similarly, if the node ID changes (e.g. because a network card has 394 been moved between machines), setting the clock sequence to a random 395 number minimizes the probability of a duplicate due to slight 396 differences in the clock settings of the machines. (If the value of 397 clock sequence associated with the changed node ID were known, then 398 the clock sequence could just be incremented, but that is unlikely.) 400 The clock sequence MUST be originally (i.e., once in the lifetime of 401 a system) initialized to a random number to minimize the correlation 402 across systems. This provides maximum protection against node 403 identifiers that may move or switch from system to system rapidly. 404 The initial value MUST NOT be correlated to the node identifier. 406 For UUID version 3, it is a 14 bit value constructed from a name. 408 For UUID version 4, it is a randomly or pseudo-randomly generated 14 409 bit value. 411 4.1.6 Node 413 For UUID version 1, the node field consists of the IEEE address, 414 usually the host address. For systems with multiple IEEE 802 415 addresses, any available address can be used. The lowest addressed 416 octet (octet number 10) contains the global/local bit and the 417 unicast/multicast bit, and is the first octet of the address 418 transmitted on an 802.3 LAN. 420 For systems with no IEEE address, a randomly or pseudo-randomly 421 generated value may be used (see section 4). The multicast bit must 422 be set in such addresses, in order that they will never conflict with 423 addresses obtained from network cards. 425 For UUID version 3, the node field is a 48 bit value constructed from 426 a name. 428 For UUID version 4, the node field is a randomly or pseudo-randomly 429 generated 48 bit value. 431 4.1.7 Nil UUID 433 The nil UUID is special form of UUID that is specified to have all 434 128 bits set to 0 (zero). 436 4.2 Algorithms for creating a time-based UUID 438 Various aspects of the algorithm for creating a version 1 UUID are 439 discussed in the following sections. UUID generation requires a 440 guarantee of uniqueness within the node ID for a given variant and 441 version. Interoperability is provided by complying with the 442 specified data structure. 444 4.2.1 Basic algorithm 446 The following algorithm is simple, correct, and inefficient: 448 o Obtain a system wide global lock 450 o From a system wide shared stable store (e.g., a file), read the 451 UUID generator state: the values of the time stamp, clock 452 sequence, and node ID used to generate the last UUID. 454 o Get the current time as a 60 bit count of 100-nanosecond intervals 455 since 00:00:00.00, 15 October 1582 457 o Get the current node ID 459 o If the state was unavailable (non-existent or corrupted), or the 460 saved node ID is different than the current node ID, generate a 461 random clock sequence value 463 o If the state was available, but the saved time stamp is later than 464 the current time stamp, increment the clock sequence value 466 o Format a UUID from the current time stamp, clock sequence, and 467 node ID values according to the structure in section 3.1 (see 468 section 3.2.6 for more details) 470 o Save the state (current time stamp, clock sequence, and node ID) 471 back to the stable store 473 o Release the system wide global lock 475 If UUIDs do not need to be frequently generated, the above algorithm 476 may be perfectly adequate. For higher performance requirements, 477 however, issues with the basic algorithm include: 479 o Reading the state from stable storage each time is inefficient 481 o The resolution of the system clock may not be 100-nanoseconds 483 o Writing the state to stable storage each time is inefficient 484 o Sharing the state across process boundaries may be inefficient 486 Each of these issues can be addressed in a modular fashion by local 487 improvements in the functions that read and write the state and read 488 the clock. We address each of them in turn in the following 489 sections. 491 4.2.2 Reading stable storage 493 The state only needs to be read from stable storage once at boot 494 time, if it is read into a system wide shared volatile store (and 495 updated whenever the stable store is updated). 497 If an implementation does not have any stable store available, then 498 it can always say that the values were unavailable. This is the 499 least desirable implementation, because it will increase the 500 frequency of creation of new clock sequence numbers, which increases 501 the probability of duplicates. 503 If the node ID can never change (e.g., the net card is inseparable 504 from the system), or if any change also reinitializes the clock 505 sequence to a random value, then instead of keeping it in stable 506 store, the current node ID may be returned. 508 4.2.3 System clock resolution 510 The time stamp is generated from the system time, whose resolution 511 may be less than the resolution of the UUID time stamp. 513 If UUIDs do not need to be frequently generated, the time stamp can 514 simply be the system time multiplied by the number of 100-nanosecond 515 intervals per system time interval. 517 If a system overruns the generator by requesting too many UUIDs 518 within a single system time interval, the UUID service MUST either: 519 return an error, or stall the UUID generator until the system clock 520 catches up. 522 A high resolution time stamp can be simulated by keeping a count of 523 how many UUIDs have been generated with the same value of the system 524 time, and using it to construction the low-order bits of the time 525 stamp. The count will range between zero and the number of 100- 526 nanosecond intervals per system time interval. 528 Note: if the processors overrun the UUID generation frequently, 529 additional node identifiers can be allocated to the system, which 530 will permit higher speed allocation by making multiple UUIDs 531 potentially available for each time stamp value. 533 4.2.4 Writing stable storage 535 The state does not always need to be written to stable store every 536 time a UUID is generated. The timestamp in the stable store can be 537 periodically set to a value larger than any yet used in a UUID; as 538 long as the generated UUIDs have time stamps less than that value, 539 and the clock sequence and node ID remain unchanged, only the shared 540 volatile copy of the state needs to be updated. Furthermore, if the 541 time stamp value in stable store is in the future by less than the 542 typical time it takes the system to reboot, a crash will not cause a 543 reinitialization of the clock sequence. 545 4.2.5 Sharing state across processes 547 If it is too expensive to access shared state each time a UUID is 548 generated, then the system wide generator can be implemented to 549 allocate a block of time stamps each time it is called, and a per- 550 process generator can allocate from that block until it is exhausted. 552 4.2.6 UUID Generation details 554 UUIDs are generated according to the following algorithm: 556 o Determine the values for the UTC-based timestamp and clock 557 sequence to be used in the UUID, as described above. 559 o For the purposes of this algorithm, consider the timestamp to be a 560 60-bit unsigned integer and the clock sequence to be a 14-bit 561 unsigned integer. Sequentially number the bits in a field, 562 starting from 0 (zero) for the least significant bit. 564 o Set the time_low field equal to the least significant 32-bits 565 (bits numbered 0 to 31 inclusive) of the time stamp in the same 566 order of significance. 568 o Set the time_mid field equal to the bits numbered 32 to 47 569 inclusive of the time stamp in the same order of significance. 571 o Set the 12 least significant bits (bits numbered 0 to 11 572 inclusive) of the time_hi_and_version field equal to the bits 573 numbered 48 to 59 inclusive of the time stamp in the same order of 574 significance. 576 o Set the 4 most significant bits (bits numbered 12 to 15 inclusive) 577 of the time_hi_and_version field to the 4-bit version number 578 corresponding to the UUID version being created, as shown in the 579 table in section 3.1.3. 581 o Set the clock_seq_low field to the 8 least significant bits (bits 582 numbered 0 to 7 inclusive) of the clock sequence in the same order 583 of significance. 585 o Set the 6 least significant bits (bits numbered 0 to 5 inclusive) 586 of the clock_seq_hi_and_reserved field to the 6 most significant 587 bits (bits numbered 8 to 13 inclusive) of the clock sequence in 588 the same order of significance. 590 o Set the 2 most significant bits (bits numbered 6 and 7) of the 591 clock_seq_hi_and_reserved to 0 and 1, respectively. 593 o Set the node field to the 48-bit IEEE address in the same order of 594 significance as the address. 596 4.3 Algorithm for creating a name-based UUID 598 The version 3 UUID is meant for generating UUIDs from "names" that 599 are drawn from, and unique within, some "name space". Some examples 600 of names (and, implicitly, name spaces) might be DNS names, URLs, ISO 601 Object IDs (OIDs), reserved words in a programming language, or X.500 602 Distinguished Names (DNs); thus, the concept of name and name space 603 should be broadly construed, and not limited to textual names. The 604 mechanisms or conventions for allocating names from, and ensuring 605 their uniqueness within, their name spaces are beyond the scope of 606 this specification. 608 The requirements for such UUIDs are as follows: 610 o The UUIDs generated at different times from the same name in the 611 same namespace MUST be equal 613 o The UUIDs generated from two different names in the same namespace 614 should be different (with very high probability) 616 o The UUIDs generated from the same name in two different namespaces 617 should be different with (very high probability) 619 o If two UUIDs that were generated from names are equal, then they 620 were generated from the same name in the same namespace (with very 621 high probability). 623 The algorithm for generating the a UUID from a name and a name space 624 are as follows: 626 o Allocate a UUID to use as a "name space ID" for all UUIDs 627 generated from names in that name space 629 o Convert the name to a canonical sequence of octets (as defined by 630 the standards or conventions of its name space); put the name 631 space ID in network byte order 633 o Compute the MD5 [3] hash of the name space ID concatenated with 634 the name 636 o Set octets 0-3 of time_low field to octets 0-3 of the MD5 hash 638 o Set octets 0-1 of time_mid field to octets 4-5 of the MD5 hash 640 o Set octets 0-1 of time_hi_and_version field to octets 6-7 of the 641 MD5 hash 643 o Set the clock_seq_hi_and_reserved field to octet 8 of the MD5 hash 645 o Set the clock_seq_low field to octet 9 of the MD5 hash 647 o Set octets 0-5 of the node field to octets 10-15 of the MD5 hash 649 o Set the 2 most significant bits (bits numbered 6 and 7) of the 650 clock_seq_hi_and_reserved to 0 and 1, respectively. 652 o Set the 4 most significant bits (bits numbered 12 to 15 inclusive) 653 of the time_hi_and_version field to the 4-bit version number 654 corresponding to the UUID version being created, as shown in the 655 table above. 657 o Convert the resulting UUID to local byte order. 659 5. Algorithms for creating a UUID from truly random or pseudo-random 660 numbers 662 The version 4 UUID is meant for generating UUIDs from truly-random or 663 pseudo-random numbers. 665 The algorithm is as follows: 667 o Set the 2 most significant bits (bits numbered 6 and 7) of the 668 clock_seq_hi_and_reserved to 0 and 1, respectively. 670 o Set the 4 most significant bits (bits numbered 12 to 15 inclusive) 671 of the time_hi_and_version field to the 4-bit version number 672 corresponding to the UUID version being created, as shown in the 673 table above. 675 o Set all the other bits to randomly (or pseudo-randomly) chosen 676 values. 678 Here are several possible ways to generate the random values: 680 o Use a physical source of randomness: for example, a white noise 681 generator, radioactive decay, or a lava lamp. 683 o Use a cryptographic strength random number generator. 685 6. Byte order of UUIDs 687 UUIDs may be transmitted in many different forms, some of which may 688 be dependent on the presentation or application protocol where the 689 UUID may be used. In such cases, the order, sizes and byte orders of 690 the UUIDs fields on the wire will depend on the relevant presentation 691 or application protocol. However, it is strongly RECOMMENDED that 692 the order of the fields conform with ordering set out in section 3.1 693 above. Furthermore, the payload size of each field in the 694 application or presentation protocol MUST be large enough that no 695 information lost in the process of encoding them for transmission. 697 In the absence of explicit application or presentation protocol 698 specification to the contrary, a UUID is encoded as a 128-bit object, 699 as follows: the fields are encoded as 16 octets, with the sizes and 700 order of the fields defined in section 3.1, and with each field 701 encoded with the Most Significant Byte first (also known as network 702 byte order). 704 0 1 2 3 705 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 706 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 707 | time_low | 708 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 709 | time_mid | time_hi_and_version | 710 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 711 |clk_seq_hi_res | clk_seq_low | node (0-1) | 712 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 713 | node (2-5) | 714 +-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+ 716 7. Node IDs when no IEEE 802 network card is available 718 If a system wants to generate UUIDs but has no IEE 802 compliant 719 network card or other source of IEEE 802 addresses, then this section 720 describes how to generate one. 722 The ideal solution is to obtain a 47 bit cryptographic quality random 723 number, and use it as the low 47 bits of the node ID, with the most 724 significant bit of the first octet of the node ID set to 1. This bit 725 is the unicast/multicast bit, which will never be set in IEEE 802 726 addresses obtained from network cards; hence, there can never be a 727 conflict between UUIDs generated by machines with and without network 728 cards. 730 If a system does not have a primitive to generate cryptographic 731 quality random numbers, then in most systems there are usually a 732 fairly large number of sources of randomness available from which one 733 can be generated. Such sources are system specific, but often 734 include: 736 o the percent of memory in use 738 o the size of main memory in bytes 740 o the amount of free main memory in bytes 742 o the size of the paging or swap file in bytes 744 o free bytes of paging or swap file 746 o the total size of user virtual address space in bytes 748 o the total available user address space bytes 750 o the size of boot disk drive in bytes 752 o the free disk space on boot drive in bytes 754 o the current time 756 o the amount of time since the system booted 758 o the individual sizes of files in various system directories 760 o the creation, last read, and modification times of files in 761 various system directories 763 o the utilization factors of various system resources (heap, etc.) 765 o current mouse cursor position 767 o current caret position 769 o current number of running processes, threads 770 o handles or IDs of the desktop window and the active window 772 o the value of stack pointer of the caller 774 o the process and thread ID of caller 776 o various processor architecture specific performance counters 777 (instructions executed, cache misses, TLB misses) 779 (Note that it precisely the above kinds of sources of randomness that 780 are used to seed cryptographic quality random number generators on 781 systems without special hardware for their construction.) 783 In addition, items such as the computer's name and the name of the 784 operating system, while not strictly speaking random, will help 785 differentiate the results from those obtained by other systems. 787 The exact algorithm to generate a node ID using these data is system 788 specific, because both the data available and the functions to obtain 789 them are often very system specific. However, assuming that one can 790 concatenate all the values from the randomness sources into a buffer, 791 and that a cryptographic hash function such as MD5 [3] is available, 792 then any 6 bytes of the MD5 hash of the buffer, with the multicast 793 bit (the high bit of the first byte) set will be an appropriately 794 random node ID. 796 Other hash functions, such as SHA-1 [5] , can also be used. The only 797 requirement is that the result be suitably random _ in the sense that 798 the outputs from a set uniformly distributed inputs are themselves 799 uniformly distributed, and that a single bit change in the input can 800 be expected to cause half of the output bits to change. 802 8. Obtaining IEEE 802 addresses 804 At the time of writing, the following URL 806 http://standards.ieee.org/regauth/oui/pilot-ind.html 808 contains information on how to obtain an IEEE 802 address or 809 "company_id" block. At the time of writing, the cost is $550 US. 811 9. Community Considerations 813 The use of UUIDs is extremely pervasive in computing. They comprise 814 the core identifier infrastructure for many operating systems 815 (Microsoft Windows) and applications (the Mozilla browser) and in 816 many cases, become exposed to the web in many non-standard ways. 817 This specification attempts to standardize that practice as openly as 818 possible and in a way that attempts to benefit the entire Internet. 820 10. Security Considerations 822 It should not be assumed that UUIDs are hard to guess; they should 823 not be used as capabilities. It should also not be assumed that it 824 is easy to determine if a UUID has been slightly transposed in order 825 to redirect a reference to another object. Humans do not have the 826 ability to easily check the integrity of a UUID by simply glancing at 827 it. 829 11. Acknowledgements 831 Ninety-five percent of this document is original to Paul Leach and 832 Rich Salz. The conversion to the format for registering a URN 833 namespace was done by Michael Mealling who is indebted to them for 834 providing a clear and extremely thorough document from which to 835 start. The fact that their original document is still referenced 836 even in draft form is a testament to a well done document that is 837 timely and useful. 839 This document draws heavily on the OSF DCE specification for UUIDs. 840 Ted Ts'o provided helpful comments, especially on the byte ordering 841 section which we mostly plagiarized from a proposed wording he 842 supplied (all errors in that section are our responsibility, 843 however). 845 Normative References 847 [1] Zahn, L., Dineen, T. and P. Leach, "Network Computing 848 Architecture", ISBN 0-13-611674-4, January 1990. 850 [2] "DCE: Remote Procedure Call", Open Group CAE Specification C309, 851 ISBN 1-85912-041-5, August 1994. 853 [3] Rivest, R., "The MD5 Message-Digest Algorithm", RFC 1321, April 854 1992. 856 [4] Moats, R., "URN Syntax", RFC 2141, May 1997. 858 [5] National Institute of Standards and Technology, "Secure Hash 859 Standard", FIPS PUB 180-1, April 1995, . 862 Authors' Addresses 864 Michael Mealling 865 VeriSign, Inc. 866 21345 Ridgetop Circle 867 Dulles, VA 21345 868 US 870 Phone: +1 770-717-0732 871 EMail: michael@neonym.net 872 URI: http://www.verisignlabs.com 874 Paul J. Leach 875 Microsoft 876 1 Microsoft Way 877 Redmond, WA 98052 878 US 880 Phone: +1 425-882-8080 881 EMail: paulle@microsoft.com 883 Rich Salz 884 Datapower Technology, Inc. 885 1 Alewife Center 886 Cambridge, MA 02142 887 US 889 Phone: +1 617-864-0455 890 EMail: rsalz@datapower.com 891 URI: http://www.datapower.com 893 Appendix A. Appendix A - UUID Sample Implementation 895 This implementation consists of 5 files: uuid.h, uuid.c, sysdep.h, 896 sysdep.c and utest.c. The uuid.* files are the system independent 897 implementation of the UUID generation algorithms described above, 898 with all the optimizations described above except efficient state 899 sharing across processes included. The code has been tested on Linux 900 (Red Hat 4.0) with GCC (2.7.2), and Windows NT 4.0 with VC++ 5.0. 901 The code assumes 64 bit integer support, which makes it a lot 902 clearer. 904 All the following source files should be considered to have the 905 following copyright notice included: 907 copyrt.h 909 /* 910 ** Copyright (c) 1990- 1993, 1996 Open Software Foundation, Inc. 911 ** Copyright (c) 1989 by Hewlett-Packard Company, Palo Alto, Ca. & 912 ** Digital Equipment Corporation, Maynard, Mass. 913 ** Copyright (c) 1998 Microsoft. 914 ** To anyone who acknowledges that this file is provided "AS IS" 915 ** without any express or implied warranty: permission to use, copy, 916 ** modify, and distribute this file for any purpose is hereby 917 ** granted without fee, provided that the above copyright notices and 918 ** this notice appears in all source code copies, and that none of 919 ** the names of Open Software Foundation, Inc., Hewlett-Packard 920 ** Company, or Digital Equipment Corporation be used in advertising 921 ** or publicity pertaining to distribution of the software without 922 ** specific, written prior permission. Neither Open Software 923 ** Foundation, Inc., Hewlett-Packard Company, Microsoft, nor Digital 924 Equipment 925 ** Corporation makes any representations about the suitability of 926 ** this software for any purpose. 927 */ 929 uuid.h 931 #include "copyrt.h" 932 #undef uuid_t 933 typedef struct _uuid_t { 934 unsigned32 time_low; 935 unsigned16 time_mid; 936 unsigned16 time_hi_and_version; 937 unsigned8 clock_seq_hi_and_reserved; 938 unsigned8 clock_seq_low; 939 byte node[6]; 940 } uuid_t; 942 /* uuid_create -- generate a UUID */ 943 int uuid_create(uuid_t * uuid); 945 /* uuid_create_from_name -- create a UUID using a "name" 946 from a "name space" */ 947 void uuid_create_from_name( 948 uuid_t * uuid, /* resulting UUID */ 949 uuid_t nsid, /* UUID to serve as context, so identical 950 names from different name spaces generate 951 different UUIDs */ 952 void * name, /* the name from which to generate a UUID */ 953 int namelen /* the length of the name */ 955 ); 957 /* uuid_compare -- Compare two UUID's "lexically" and return 958 -1 u1 is lexically before u2 959 0 u1 is equal to u2 960 1 u1 is lexically after u2 961 Note: lexical ordering is not temporal ordering! 962 */ 963 int uuid_compare(uuid_t *u1, uuid_t *u2); 965 uuid.c 967 #include "copyrt.h" 968 #include 969 #include 970 #include 971 #include 972 #include "sysdep.h" 973 #include "uuid.h" 975 /* various forward declarations */ 976 static int read_state(unsigned16 *clockseq, uuid_time_t *timestamp, 977 uuid_node_t * node); 978 static void write_state(unsigned16 clockseq, uuid_time_t timestamp, 979 uuid_node_t node); 980 static void format_uuid_v1(uuid_t * uuid, unsigned16 clockseq, 981 uuid_time_t timestamp, uuid_node_t node); 982 static void format_uuid_v3(uuid_t * uuid, unsigned char hash[16]); 983 static void get_current_time(uuid_time_t * timestamp); 984 static unsigned16 true_random(void); 986 /* uuid_create -- generator a UUID */ 987 int uuid_create(uuid_t * uuid) { 988 uuid_time_t timestamp, last_time; 989 unsigned16 clockseq; 990 uuid_node_t node; 991 uuid_node_t last_node; 992 int f; 994 /* acquire system wide lock so we're alone */ 995 LOCK; 997 /* get current time */ 998 get_current_time(×tamp); 1000 /* get node ID */ 1001 get_ieee_node_identifier(&node); 1002 /* get saved state from NV storage */ 1003 f = read_state(&clockseq, &last_time, &last_node); 1005 /* if no NV state, or if clock went backwards, or node ID changed 1006 (e.g., net card swap) change clockseq */ 1007 if (!f || memcmp(&node, &last_node, sizeof(uuid_node_t))) 1008 clockseq = true_random(); 1009 else if (timestamp < last_time) 1010 clockseq++; 1012 /* stuff fields into the UUID */ 1013 format_uuid_v1(uuid, clockseq, timestamp, node); 1015 /* save the state for next time */ 1016 write_state(clockseq, timestamp, node); 1018 UNLOCK; 1019 return(1); 1020 }; 1022 /* format_uuid_v1 -- make a UUID from the timestamp, clockseq, 1023 and node ID */ 1024 void format_uuid_v1(uuid_t * uuid, unsigned16 clock_seq, uuid_time_t 1025 timestamp, uuid_node_t node) { 1026 /* Construct a version 1 uuid with the information we've gathered 1027 * plus a few constants. */ 1028 uuid->time_low = (unsigned long)(timestamp & 0xFFFFFFFF); 1029 uuid->time_mid = (unsigned short)((timestamp >> 32) & 0xFFFF); 1030 uuid->time_hi_and_version = (unsigned short)((timestamp >> 48) & 1031 0x0FFF); 1032 uuid->time_hi_and_version |= (1 << 12); 1033 uuid->clock_seq_low = clock_seq & 0xFF; 1034 uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3F00) >> 8; 1035 uuid->clock_seq_hi_and_reserved |= 0x80; 1036 memcpy(&uuid->node, &node, sizeof uuid->node); 1037 }; 1039 /* data type for UUID generator persistent state */ 1040 typedef struct { 1041 uuid_time_t ts; /* saved timestamp */ 1042 uuid_node_t node; /* saved node ID */ 1043 unsigned16 cs; /* saved clock sequence */ 1044 } uuid_state; 1046 static uuid_state st; 1048 /* read_state -- read UUID generator state from non-volatile store */ 1049 int read_state(unsigned16 *clockseq, uuid_time_t *timestamp, 1050 uuid_node_t *node) { 1051 FILE * fd; 1052 static int inited = 0; 1054 /* only need to read state once per boot */ 1055 if (!inited) { 1056 fd = fopen("state", "rb"); 1057 if (!fd) 1058 return (0); 1059 fread(&st, sizeof(uuid_state), 1, fd); 1060 fclose(fd); 1061 inited = 1; 1062 }; 1063 *clockseq = st.cs; 1064 *timestamp = st.ts; 1065 *node = st.node; 1066 return(1); 1067 }; 1069 /* write_state -- save UUID generator state back to non-volatile 1070 storage */ 1071 void write_state(unsigned16 clockseq, uuid_time_t timestamp, 1072 uuid_node_t node) { 1073 FILE * fd; 1074 static int inited = 0; 1075 static uuid_time_t next_save; 1077 if (!inited) { 1078 next_save = timestamp; 1079 inited = 1; 1080 }; 1081 /* always save state to volatile shared state */ 1082 st.cs = clockseq; 1083 st.ts = timestamp; 1084 st.node = node; 1085 if (timestamp >= next_save) { 1086 fd = fopen("state", "wb"); 1087 fwrite(&st, sizeof(uuid_state), 1, fd); 1088 fclose(fd); 1089 /* schedule next save for 10 seconds from now */ 1090 next_save = timestamp + (10 * 10 * 1000 * 1000); 1091 }; 1092 }; 1094 /* get-current_time -- get time as 60 bit 100ns ticks since whenever. 1095 Compensate for the fact that real clock resolution is 1096 less than 100ns. */ 1097 void get_current_time(uuid_time_t * timestamp) { 1098 uuid_time_t time_now; 1099 static uuid_time_t time_last; 1100 static unsigned16 uuids_this_tick; 1101 static int inited = 0; 1103 if (!inited) { 1104 get_system_time(&time_now); 1105 uuids_this_tick = UUIDS_PER_TICK; 1106 inited = 1; 1107 }; 1109 while (1) { 1110 get_system_time(&time_now); 1112 /* if clock reading changed since last UUID generated... */ 1113 if (time_last != time_now) { 1114 /* reset count of uuids gen'd with this clock reading */ 1115 uuids_this_tick = 0; 1116 break; 1117 }; 1118 if (uuids_this_tick < UUIDS_PER_TICK) { 1119 uuids_this_tick++; 1120 break; 1121 }; 1122 /* going too fast for our clock; spin */ 1123 }; 1124 /* add the count of uuids to low order bits of the clock reading */ 1125 *timestamp = time_now + uuids_this_tick; 1126 }; 1128 /* true_random -- generate a crypto-quality random number. 1129 This sample doesn't do that. */ 1130 static unsigned16 1131 true_random(void) 1132 { 1133 static int inited = 0; 1134 uuid_time_t time_now; 1136 if (!inited) { 1137 get_system_time(&time_now); 1138 time_now = time_now/UUIDS_PER_TICK; 1139 srand((unsigned int)(((time_now >> 32) ^ time_now)&0xffffffff)); 1140 inited = 1; 1141 }; 1143 return (rand()); 1144 } 1145 /* uuid_create_from_name -- create a UUID using a "name" from a "name 1146 space" */ 1147 void uuid_create_from_name( 1148 uuid_t * uuid, /* resulting UUID */ 1149 uuid_t nsid, /* UUID to serve as context, so identical 1150 names from different name spaces generate 1151 different UUIDs */ 1152 void * name, /* the name from which to generate a UUID */ 1153 int namelen /* the length of the name */ 1154 ) { 1155 MD5_CTX c; 1156 unsigned char hash[16]; 1157 uuid_t net_nsid; /* context UUID in network byte order */ 1159 /* put name space ID in network byte order so it hashes the same 1160 no matter what endian machine we're on */ 1161 net_nsid = nsid; 1162 htonl(net_nsid.time_low); 1163 htons(net_nsid.time_mid); 1164 htons(net_nsid.time_hi_and_version); 1166 MD5Init(&c); 1167 MD5Update(&c, &net_nsid, sizeof(uuid_t)); 1168 MD5Update(&c, name, namelen); 1169 MD5Final(hash, &c); 1171 /* the hash is in network byte order at this point */ 1172 format_uuid_v3(uuid, hash); 1173 }; 1175 /* format_uuid_v3 -- make a UUID from a (pseudo)random 128 bit number 1176 */ 1177 void format_uuid_v3(uuid_t * uuid, unsigned char hash[16]) { 1178 /* Construct a version 3 uuid with the (pseudo-)random number 1179 * plus a few constants. */ 1181 memcpy(uuid, hash, sizeof(uuid_t)); 1183 /* convert UUID to local byte order */ 1184 ntohl(uuid->time_low); 1185 ntohs(uuid->time_mid); 1186 ntohs(uuid->time_hi_and_version); 1188 /* put in the variant and version bits */ 1189 uuid->time_hi_and_version &= 0x0FFF; 1190 uuid->time_hi_and_version |= (3 << 12); 1191 uuid->clock_seq_hi_and_reserved &= 0x3F; 1192 uuid->clock_seq_hi_and_reserved |= 0x80; 1194 }; 1196 /* uuid_compare -- Compare two UUID's "lexically" and return 1197 -1 u1 is lexically before u2 1198 0 u1 is equal to u2 1199 1 u1 is lexically after u2 1200 Note: lexical ordering is not temporal ordering! 1201 */ 1202 int uuid_compare(uuid_t *u1, uuid_t *u2) 1203 { 1204 int i; 1206 #define CHECK(f1, f2) if (f1 != f2) return f1 < f2 ? -1 : 1; 1207 CHECK(u1->time_low, u2->time_low); 1208 CHECK(u1->time_mid, u2->time_mid); 1209 CHECK(u1->time_hi_and_version, u2->time_hi_and_version); 1210 CHECK(u1->clock_seq_hi_and_reserved, u2->clock_seq_hi_and_reserved); 1211 CHECK(u1->clock_seq_low, u2->clock_seq_low) 1212 for (i = 0; i < 6; i++) { 1213 if (u1->node[i] < u2->node[i]) 1214 return -1; 1215 if (u1->node[i] > u2->node[i]) 1216 return 1; 1217 } 1218 return 0; 1219 }; 1221 sysdep.h 1223 #include "copyrt.h" 1224 /* remove the following define if you aren't running WIN32 */ 1225 #define WININC 0 1227 #ifdef WININC 1228 #include 1229 #else 1230 #include 1231 #include 1232 #include 1233 #endif 1235 /* change to point to where MD5 .h's live */ 1236 /* get MD5 sample implementation from RFC 1321 */ 1237 #include "global.h" 1238 #include "md5.h" 1240 /* set the following to the number of 100ns ticks of the actual 1241 resolution of 1242 your system's clock */ 1243 #define UUIDS_PER_TICK 1024 1245 /* Set the following to a call to acquire a system wide global lock 1246 */ 1247 #define LOCK 1248 #define UNLOCK 1250 typedef unsigned long unsigned32; 1251 typedef unsigned short unsigned16; 1252 typedef unsigned char unsigned8; 1253 typedef unsigned char byte; 1255 /* Set this to what your compiler uses for 64 bit data type */ 1256 #ifdef WININC 1257 #define unsigned64_t unsigned __int64 1258 #define I64(C) C 1259 #else 1260 #define unsigned64_t unsigned long long 1261 #define I64(C) C##LL 1262 #endif 1264 typedef unsigned64_t uuid_time_t; 1265 typedef struct { 1266 char nodeID[6]; 1267 } uuid_node_t; 1269 void get_ieee_node_identifier(uuid_node_t *node); 1270 void get_system_time(uuid_time_t *uuid_time); 1271 void get_random_info(char seed[16]); 1273 sysdep.c 1275 #include "copyrt.h" 1276 #include 1277 #include "sysdep.h" 1279 /* system dependent call to get IEEE node ID. 1280 This sample implementation generates a random node ID 1281 */ 1282 void get_ieee_node_identifier(uuid_node_t *node) { 1283 char seed[16]; 1284 FILE * fd; 1285 static inited = 0; 1286 static uuid_node_t saved_node; 1287 if (!inited) { 1288 fd = fopen("nodeid", "rb"); 1289 if (fd) { 1290 fread(&saved_node, sizeof(uuid_node_t), 1, fd); 1291 fclose(fd); 1292 } 1293 else { 1294 get_random_info(seed); 1295 seed[0] |= 0x80; 1296 memcpy(&saved_node, seed, sizeof(uuid_node_t)); 1297 fd = fopen("nodeid", "wb"); 1298 if (fd) { 1299 fwrite(&saved_node, sizeof(uuid_node_t), 1, fd); 1300 fclose(fd); 1301 }; 1302 }; 1303 inited = 1; 1304 }; 1306 *node = saved_node; 1307 }; 1309 /* system dependent call to get the current system time. 1310 Returned as 100ns ticks since Oct 15, 1582, but resolution may be 1311 less than 100ns. 1312 */ 1313 #ifdef _WINDOWS_ 1315 void get_system_time(uuid_time_t *uuid_time) { 1316 ULARGE_INTEGER time; 1318 GetSystemTimeAsFileTime((FILETIME *)&time); 1320 /* NT keeps time in FILETIME format which is 100ns ticks since 1321 Jan 1, 1601. UUIDs use time in 100ns ticks since Oct 15, 1582. 1322 The difference is 17 Days in Oct + 30 (Nov) + 31 (Dec) 1323 + 18 years and 5 leap days. 1324 */ 1326 time.QuadPart += 1327 (unsigned __int64) (1000*1000*10) // seconds 1328 * (unsigned __int64) (60 * 60 * 24) // days 1329 * (unsigned __int64) (17+30+31+365*18+5); // # of days 1331 *uuid_time = time.QuadPart; 1333 }; 1334 void get_random_info(char seed[16]) { 1335 MD5_CTX c; 1336 typedef struct { 1337 MEMORYSTATUS m; 1338 SYSTEM_INFO s; 1339 FILETIME t; 1340 LARGE_INTEGER pc; 1341 DWORD tc; 1342 DWORD l; 1343 char hostname[MAX_COMPUTERNAME_LENGTH + 1]; 1344 } randomness; 1345 randomness r; 1347 MD5Init(&c); 1348 /* memory usage stats */ 1349 GlobalMemoryStatus(&r.m); 1350 /* random system stats */ 1351 GetSystemInfo(&r.s); 1352 /* 100ns resolution (nominally) time of day */ 1353 GetSystemTimeAsFileTime(&r.t); 1354 /* high resolution performance counter */ 1355 QueryPerformanceCounter(&r.pc); 1356 /* milliseconds since last boot */ 1357 r.tc = GetTickCount(); 1358 r.l = MAX_COMPUTERNAME_LENGTH + 1; 1360 GetComputerName(r.hostname, &r.l ); 1361 MD5Update(&c, &r, sizeof(randomness)); 1362 MD5Final(seed, &c); 1363 }; 1364 #else 1366 void get_system_time(uuid_time_t *uuid_time) 1367 { 1368 struct timeval tp; 1370 gettimeofday(&tp, (struct timezone *)0); 1372 /* Offset between UUID formatted times and Unix formatted times. 1373 UUID UTC base time is October 15, 1582. 1374 Unix base time is January 1, 1970. 1375 */ 1376 *uuid_time = (tp.tv_sec * 10000000) + (tp.tv_usec * 10) + 1377 I64(0x01B21DD213814000); 1378 }; 1380 void get_random_info(char seed[16]) { 1381 MD5_CTX c; 1382 typedef struct { 1383 struct sysinfo s; 1384 struct timeval t; 1385 char hostname[257]; 1386 } randomness; 1387 randomness r; 1389 MD5Init(&c); 1390 sysinfo(&r.s); 1391 gettimeofday(&r.t, (struct timezone *)0); 1392 gethostname(r.hostname, 256); 1393 MD5Update(&c, &r, sizeof(randomness)); 1394 MD5Final(seed, &c); 1395 }; 1397 #endif 1399 utest.c 1401 #include "copyrt.h" 1402 #include "sysdep.h" 1403 #include 1404 #include "uuid.h" 1406 uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */ 1407 0x6ba7b810, 1408 0x9dad, 1409 0x11d1, 1410 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8 1411 }; 1413 /* puid -- print a UUID */ 1414 void puid(uuid_t u); 1416 /* Simple driver for UUID generator */ 1417 void main(int argc, char **argv) { 1418 uuid_t u; 1419 int f; 1421 uuid_create(&u); 1422 printf("uuid_create() -> "); puid(u); 1424 f = uuid_compare(&u, &u); 1425 printf("uuid_compare(u,u): %d\n", f); /* should be 0 */ 1426 f = uuid_compare(&u, &NameSpace_DNS); 1427 printf("uuid_compare(u, NameSpace_DNS): %d\n", f); /* s.b. 1 */ 1428 f = uuid_compare(&NameSpace_DNS, &u); 1429 printf("uuid_compare(NameSpace_DNS, u): %d\n", f); /* s.b. -1 */ 1431 uuid_create_from_name(&u, NameSpace_DNS, "www.widgets.com", 15); 1432 printf("uuid_create_from_name() -> "); puid(u); 1433 }; 1435 void puid(uuid_t u) { 1436 int i; 1438 printf("%8.8x-%4.4x-%4.4x-%2.2x%2.2x-", u.time_low, u.time_mid, 1439 u.time_hi_and_version, u.clock_seq_hi_and_reserved, 1440 u.clock_seq_low); 1441 for (i = 0; i < 6; i++) 1442 printf("%2.2x", u.node[i]); 1443 printf("\n"); 1444 }; 1446 Appendix B. Appendix B - Sample output of utest 1448 uuid_create() -> 7d444840-9dc0-11d1-b245-5ffdce74fad2 1449 uuid_compare(u,u): 0 1450 uuid_compare(u, NameSpace_DNS): 1 1451 uuid_compare(NameSpace_DNS, u): -1 1452 uuid_create_from_name() -> e902893a-9d22-3c7e-a7b8-d6e313b71d9f 1454 Appendix C. Appendix C - Some name space IDs 1456 This appendix lists the name space IDs for some potentially 1457 interesting name spaces, as initialized C structures and in the 1458 string representation defined in section 3.5 1459 uuid_t NameSpace_DNS = { /* 6ba7b810-9dad-11d1-80b4-00c04fd430c8 */ 1460 0x6ba7b810, 1461 0x9dad, 1462 0x11d1, 1463 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8 1464 }; 1466 uuid_t NameSpace_URL = { /* 6ba7b811-9dad-11d1-80b4-00c04fd430c8 */ 1467 0x6ba7b811, 1468 0x9dad, 1469 0x11d1, 1470 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8 1471 }; 1473 uuid_t NameSpace_OID = { /* 6ba7b812-9dad-11d1-80b4-00c04fd430c8 */ 1474 0x6ba7b812, 1475 0x9dad, 1476 0x11d1, 1477 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8 1478 }; 1480 uuid_t NameSpace_X500 = { /* 6ba7b814-9dad-11d1-80b4-00c04fd430c8 */ 1481 0x6ba7b814, 1482 0x9dad, 1483 0x11d1, 1484 0x80, 0xb4, 0x00, 0xc0, 0x4f, 0xd4, 0x30, 0xc8 1485 }; 1487 Full Copyright Statement 1489 Copyright (C) The Internet Society (2002). All Rights Reserved. 1491 This document and translations of it may be copied and furnished to 1492 others, and derivative works that comment on or otherwise explain it 1493 or assist in its implementation may be prepared, copied, published 1494 and distributed, in whole or in part, without restriction of any 1495 kind, provided that the above copyright notice and this paragraph are 1496 included on all such copies and derivative works. However, this 1497 document itself may not be modified in any way, such as by removing 1498 the copyright notice or references to the Internet Society or other 1499 Internet organizations, except as needed for the purpose of 1500 developing Internet standards in which case the procedures for 1501 copyrights defined in the Internet Standards process must be 1502 followed, or as required to translate it into languages other than 1503 English. 1505 The limited permissions granted above are perpetual and will not be 1506 revoked by the Internet Society or its successors or assigns. 1508 This document and the information contained herein is provided on an 1509 "AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING 1510 TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING 1511 BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION 1512 HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF 1513 MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. 1515 Acknowledgement 1517 Funding for the RFC Editor function is currently provided by the 1518 Internet Society.