src/util/uuid.c

   1 /*
   2  * Copyright 2000, International Business Machines Corporation and others.
   3  * All Rights Reserved.
   4  *
   5  * This software has been released under the terms of the IBM Public
   6  * License.  For details, see the LICENSE file in the top-level source
   7  * directory or online at http://www.openafs.org/dl/license10.html
   8  */
   9
  10 /* String conversion routines have the following copyright */
  11
  12 /*
  13  * Copyright (c) 2002 Kungliga Tekniska Högskolan
  14  * (Royal Institute of Technology, Stockholm, Sweden).
  15  * All rights reserved.
  16  *
  17  * Redistribution and use in source and binary forms, with or without
  18  * modification, are permitted provided that the following conditions
  19  * are met:
  20  *
  21  * 1. Redistributions of source code must retain the above copyright
  22  *    notice, this list of conditions and the following disclaimer.
  23  *
  24  * 2. Redistributions in binary form must reproduce the above copyright
  25  *    notice, this list of conditions and the following disclaimer in the
  26  *    documentation and/or other materials provided with the distribution.
  27  *
  28  * 3. Neither the name of the Institute nor the names of its contributors
  29  *    may be used to endorse or promote products derived from this software
  30  *    without specific prior written permission.
  31  *
  32  * THIS SOFTWARE IS PROVIDED BY THE INSTITUTE AND CONTRIBUTORS ``AS IS'' AND
  33  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  34  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  35  * ARE DISCLAIMED.  IN NO EVENT SHALL THE INSTITUTE OR CONTRIBUTORS BE LIABLE
  36  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  37  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  38  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  39  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  40  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  41  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  42  * SUCH DAMAGE.
  43  */
  44
  45 #include <afsconfig.h>
  46 #ifdef KERNEL
  47 #include "afs/param.h"
  48 #else
  49 #include <afs/param.h>
  50 #endif
  51
  52
  53 #ifdef KERNEL
  54 #include "afs/sysincludes.h"
  55 #include "afsincludes.h"
  56 #define uuid_memcmp(A,B,C)      memcmp(A, B, C)
  57 #define uuid_memcpy(A,B,C)      memcpy(A, B, C)
  58 #else /* KERNEL */
  59 #include <stdio.h>
  60 #include <errno.h>
  61 #include <string.h>
  62 #ifdef AFS_NT40_ENV
  63 #include <rpc.h>
  64 #include <winsock2.h>
  65 #include <process.h>
  66 #else
  67 #include <sys/file.h>
  68 #include <netinet/in.h>
  69 #include <netdb.h>
  70 #include <sys/ioctl.h>
  71 #include <sys/socket.h>
  72 #ifndef ITIMER_REAL
  73 #include <sys/time.h>
  74 #endif /* ITIMER_REAL */
  75 #include <net/if.h>
  76 #ifdef HAVE_UNISTD_H
  77 #include <unistd.h>
  78 #endif
  79 #include <stdlib.h>
  80 #endif
  81 #include <sys/stat.h>
  82 #include <fcntl.h>
  83 #if !defined(AFS_NT40_ENV) && !defined(AFS_LINUX20_ENV)
  84 #include <netinet/if_ether.h>
  85 #endif
  86 #include "afsutil.h"
  87
  88 #define uuid_memcmp(A,B,C)      memcmp(A,B,C)
  89 #define uuid_memcpy(A,B,C)      memcpy(A,B,C)
  90 #endif /* KERNEL */
  91
  92
  93 typedef struct {
  94     char eaddr[6];              /* 6 bytes of ethernet hardware address */
  95 } uuid_address_t, *uuid_address_p_t;
  96
  97
  98 typedef struct {
  99     afs_uint32 lo;
 100     afs_uint32 hi;
 101 } uuid_time_t, *uuid_time_p_t;
 102
 103 static int uuid_get_address(uuid_address_p_t addr);
 104 void uuid__get_os_time(uuid_time_t * os_time);
 105
 106 /*
 107  * |<------------------------- 32 bits -------------------------->|
 108  *
 109  * +--------------------------------------------------------------+
 110  * |                     low 32 bits of time                      |  0-3  .time_low
 111  * +-------------------------------+-------------------------------
 112  * |     mid 16 bits of time       |  4-5               .time_mid
 113  * +-------+-----------------------+
 114  * | vers. |   hi 12 bits of time  |  6-7               .time_hi_and_version
 115  * +-------+-------+---------------+
 116  * |Res|  clkSeqHi |  8                                 .clock_seq_hi_and_reserved
 117  * +---------------+
 118  * |   clkSeqLow   |  9                                 .clock_seq_low
 119  * +---------------+----------...-----+
 120  * |            node ID               |  8-16           .node
 121  * +--------------------------...-----+
 122  */
 123
 124 afsUUID afs_uuid_g_nil_uuid = { 0 };
 125 static uuid_time_t time_now, time_last;
 126 static u_short uuid_time_adjust, clock_seq;
 127 static afs_uint32 rand_m, rand_ia, rand_ib, rand_irand, uuid_init_done = 0;
 128
 129 #define uuid_create_nil(uuid) memset(uuid, 0, sizeof(afsUUID))
 130
 131 afs_int32
 132 afs_uuid_equal(afsUUID * u1, afsUUID * u2)
 133 {
 134     return (uuid_memcmp((void *)u1, (void *)u2, sizeof(afsUUID)) == 0);
 135 }
 136
 137 afs_int32
 138 afs_uuid_is_nil(afsUUID * u1)
 139 {
 140     if (!u1)
 141         return 1;
 142     return (uuid_memcmp
 143             ((void *)u1, (void *)&afs_uuid_g_nil_uuid, sizeof(afsUUID)) == 0);
 144 }
 145
 146 void
 147 afs_htonuuid(afsUUID * uuidp)
 148 {
 149     uuidp->time_low = htonl(uuidp->time_low);
 150     uuidp->time_mid = htons(uuidp->time_mid);
 151     uuidp->time_hi_and_version = htons(uuidp->time_hi_and_version);
 152 }
 153
 154 void
 155 afs_ntohuuid(afsUUID * uuidp)
 156 {
 157     uuidp->time_low = ntohl(uuidp->time_low);
 158     uuidp->time_mid = ntohs(uuidp->time_mid);
 159     uuidp->time_hi_and_version = ntohs(uuidp->time_hi_and_version);
 160 }
 161
 162 static u_short
 163 true_random(void)
 164 {
 165     rand_m += 7;
 166     rand_ia += 1907;
 167     rand_ib += 73939;
 168     if (rand_m >= 9973)
 169         rand_m -= 9871;
 170     if (rand_ia >= 99991)
 171         rand_ia -= 89989;
 172     if (rand_ib >= 224729)
 173         rand_ib -= 96233;
 174     rand_irand = (rand_irand * rand_m) + rand_ia + rand_ib;
 175     return (((rand_irand) >> 16) ^ (rand_irand & 0x3fff));
 176 }
 177
 178
 179 static afs_int32
 180 time_cmp(uuid_time_p_t time1, uuid_time_p_t time2)
 181 {
 182     if (time1->hi < time2->hi)
 183         return (-1);
 184     if (time1->hi > time2->hi)
 185         return (1);
 186     if (time1->lo < time2->lo)
 187         return (-1);
 188     if (time1->lo > time2->lo)
 189         return (1);
 190     return (0);
 191 }
 192
 193 /*
 194  *    Converts a string UUID to binary representation.
 195  */
 196
 197 #if !defined(KERNEL) && !defined(UKERNEL)
 198 int
 199 afsUUID_from_string(const char *str, afsUUID * uuid)
 200 {
 201     unsigned int time_low, time_mid, time_hi_and_version;
 202     unsigned int clock_seq_hi_and_reserved, clock_seq_low;
 203     unsigned int node[6];
 204     int i;
 205
 206     i = sscanf(str, "%08x-%04x-%04x-%02x-%02x-%02x%02x%02x%02x%02x%02x",
 207                &time_low, &time_mid, &time_hi_and_version,
 208                &clock_seq_hi_and_reserved, &clock_seq_low, &node[0], &node[1],
 209                &node[2], &node[3], &node[4], &node[5]);
 210     if (i != 11)
 211         return -1;
 212
 213     uuid->time_low = time_low;
 214     uuid->time_mid = time_mid;
 215     uuid->time_hi_and_version = time_hi_and_version;
 216     uuid->clock_seq_hi_and_reserved = clock_seq_hi_and_reserved;
 217     uuid->clock_seq_low = clock_seq_low;
 218
 219     for (i = 0; i < 6; i++)
 220         uuid->node[i] = node[i];
 221
 222     return 0;
 223 }
 224
 225 /*
 226  *    Converts a UUID from binary representation to a string representation.
 227  */
 228
 229 int
 230 afsUUID_to_string(const afsUUID * uuid, char *str, size_t strsz)
 231 {
 232     snprintf(str, strsz, "%08x-%04x-%04x-%02x-%02x-%02x%02x%02x%02x%02x%02x",
 233              uuid->time_low, uuid->time_mid, uuid->time_hi_and_version,
 234              (unsigned char)uuid->clock_seq_hi_and_reserved,
 235              (unsigned char)uuid->clock_seq_low, (unsigned char)uuid->node[0],
 236              (unsigned char)uuid->node[1], (unsigned char)uuid->node[2],
 237              (unsigned char)uuid->node[3], (unsigned char)uuid->node[4],
 238              (unsigned char)uuid->node[5]);
 239
 240     return 0;
 241 }
 242 #endif
 243
 244 afs_int32
 245 afs_uuid_create(afsUUID * uuid)
 246 {
 247 #ifdef AFS_NT40_ENV
 248     UuidCreate((UUID *) uuid);
 249 #else /* AFS_NT40_ENV */
 250     uuid_address_t eaddr;
 251     afs_int32 got_no_time = 0, code;
 252
 253     if (!uuid_init_done) {
 254         uuid_time_t t;
 255         u_short seedp[4], seed = 0;
 256         rand_m = 971;;
 257         rand_ia = 11113;
 258         rand_ib = 104322;
 259         rand_irand = 4181;
 260         /*
 261          * Generating our 'seed' value
 262          *
 263          * We start with the current time, but, since the resolution of clocks is
 264          * system hardware dependent (eg. Ultrix is 10 msec.) and most likely
 265          * coarser than our resolution (10 usec) we 'mixup' the bits by xor'ing
 266          * all the bits together.  This will have the effect of involving all of
 267          * the bits in the determination of the seed value while remaining system
 268          * independent.  Then for good measure to ensure a unique seed when there
 269          * are multiple processes creating UUID's on a system, we add in the PID.
 270          */
 271         uuid__get_os_time(&t);
 272         memcpy(&seedp, &t, sizeof(seedp));
 273         seed ^= seedp[0];
 274         seed ^= seedp[1];
 275         seed ^= seedp[2];
 276         seed ^= seedp[3];
 277 #if defined(KERNEL) && defined(AFS_XBSD_ENV)
 278         rand_irand += seed + (afs_uint32) curproc->p_pid;
 279 #elif defined(UKERNEL)
 280         rand_irand += seed + (afs_uint32) osi_getpid();
 281 #else
 282         rand_irand += seed + (afs_uint32) getpid();
 283 #endif
 284         uuid__get_os_time(&time_last);
 285         clock_seq = true_random();
 286 #ifdef AFS_NT40_ENV
 287         if (afs_winsockInit() < 0) {
 288             return WSAGetLastError();
 289         }
 290 #endif
 291         uuid_init_done = 1;
 292     }
 293     if ((code = uuid_get_address(&eaddr)))
 294         return code;            /* get our hardware network address */
 295     do {
 296         /* get the current time */
 297         uuid__get_os_time(&time_now);
 298         /*
 299          * check that our clock hasn't gone backwards and handle it
 300          *    accordingly with clock_seq
 301          * check that we're not generating uuid's faster than we
 302          *    can accommodate with our uuid_time_adjust fudge factor
 303          */
 304         if ((code = time_cmp(&time_now, &time_last)) == -1) {
 305             /* A clock_seq value of 0 indicates that it hasn't been initialized. */
 306             if (clock_seq == 0) {
 307                 clock_seq = true_random();
 308             }
 309             clock_seq = (clock_seq + 1) & 0x3fff;
 310             if (clock_seq == 0)
 311                 clock_seq = clock_seq + 1;
 312             uuid_time_adjust = 0;
 313         } else if (code == 1) {
 314             uuid_time_adjust = 0;
 315         } else {
 316             if (uuid_time_adjust == 0x7fff)     /* spin while we wait for the clock to tick */
 317                 got_no_time = 1;
 318             else
 319                 uuid_time_adjust++;
 320         }
 321     } while (got_no_time);
 322     time_last.lo = time_now.lo;
 323     time_last.hi = time_now.hi;
 324     if (uuid_time_adjust != 0) {
 325         if (time_now.lo & 0x80000000) {
 326             time_now.lo += uuid_time_adjust;
 327             if (!(time_now.lo & 0x80000000))
 328                 time_now.hi++;
 329         } else
 330             time_now.lo += uuid_time_adjust;
 331     }
 332     uuid->time_low = time_now.lo;
 333     uuid->time_mid = time_now.hi & 0x0000ffff;
 334     uuid->time_hi_and_version = (time_now.hi & 0x0fff0000) >> 16;
 335     uuid->time_hi_and_version |= (1 << 12);
 336     uuid->clock_seq_low = clock_seq & 0xff;
 337     uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3f00) >> 8;
 338     uuid->clock_seq_hi_and_reserved |= 0x80;
 339     uuid_memcpy((void *)uuid->node, (void *)&eaddr, sizeof(uuid_address_t));
 340 #endif /* AFS_NT40_ENV */
 341     return 0;
 342 }
 343
 344 u_short
 345 afs_uuid_hash(afsUUID * uuid)
 346 {
 347     short c0 = 0, c1 = 0, x, y;
 348     char *next_uuid = (char *)uuid;
 349
 350     /*
 351      * For speed lets unroll the following loop:
 352      *
 353      *   for (i = 0; i < UUID_K_LENGTH; i++)
 354      *   {
 355      *       c0 = c0 + *next_uuid++;
 356      *       c1 = c1 + c0;
 357      *   }
 358      */
 359     c0 = c0 + *next_uuid++;
 360     c1 = c1 + c0;
 361     c0 = c0 + *next_uuid++;
 362     c1 = c1 + c0;
 363     c0 = c0 + *next_uuid++;
 364     c1 = c1 + c0;
 365     c0 = c0 + *next_uuid++;
 366     c1 = c1 + c0;
 367     c0 = c0 + *next_uuid++;
 368     c1 = c1 + c0;
 369     c0 = c0 + *next_uuid++;
 370     c1 = c1 + c0;
 371     c0 = c0 + *next_uuid++;
 372     c1 = c1 + c0;
 373     c0 = c0 + *next_uuid++;
 374     c1 = c1 + c0;
 375     c0 = c0 + *next_uuid++;
 376     c1 = c1 + c0;
 377     c0 = c0 + *next_uuid++;
 378     c1 = c1 + c0;
 379     c0 = c0 + *next_uuid++;
 380     c1 = c1 + c0;
 381     c0 = c0 + *next_uuid++;
 382     c1 = c1 + c0;
 383     c0 = c0 + *next_uuid++;
 384     c1 = c1 + c0;
 385     c0 = c0 + *next_uuid++;
 386     c1 = c1 + c0;
 387     c0 = c0 + *next_uuid++;
 388     c1 = c1 + c0;
 389     c0 = c0 + *next_uuid++;
 390     c1 = c1 + c0;
 391     /*  Calculate the value for "First octet" of the hash  */
 392     x = -c1 % 255;
 393     if (x < 0) {
 394         x = x + 255;
 395     }
 396     /*  Calculate the value for "second octet" of the hash */
 397     y = (c1 - c0) % 255;
 398     if (y < 0) {
 399         y = y + 255;
 400     }
 401     return ((y * 256) + x);
 402 }
 403
 404 #ifdef KERNEL
 405
 406 extern struct interfaceAddr afs_cb_interface;
 407
 408 static int
 409 uuid_get_address(uuid_address_p_t addr)
 410 {
 411     uuid_memcpy((void *)addr->eaddr, (void *)&afs_cb_interface.addr_in[0], 4);
 412     addr->eaddr[4] = 0xaa;
 413     addr->eaddr[5] = 0x77;
 414     return 0;
 415 }
 416
 417 void
 418 uuid__get_os_time(uuid_time_t * os_time)
 419 {
 420     osi_timeval_t tp;
 421
 422     osi_GetTime(&tp);
 423     os_time->hi = tp.tv_sec;
 424     os_time->lo = tp.tv_usec * 10;
 425 }
 426
 427 #else /* KERNEL */
 428
 429 char hostName1[128] = "localhost";
 430 static int
 431 uuid_get_address(uuid_address_p_t addr)
 432 {
 433     afs_int32 code;
 434     afs_uint32 addr1;
 435     struct hostent *he;
 436
 437     code = gethostname(hostName1, 64);
 438     if (code) {
 439         printf("gethostname() failed\n");
 440 #ifdef AFS_NT40_ENV
 441         return ENOENT;
 442 #else
 443         return errno;
 444 #endif
 445     }
 446     he = gethostbyname(hostName1);
 447     if (!he) {
 448         printf("Can't find address for '%s'\n", hostName1);
 449 #ifdef AFS_NT40_ENV
 450         return ENOENT;
 451 #else
 452         return errno;
 453 #endif
 454     } else {
 455         uuid_memcpy(&addr1, he->h_addr_list[0], 4);
 456         addr1 = ntohl(addr1);
 457         uuid_memcpy(addr->eaddr, &addr1, 4);
 458         addr->eaddr[4] = 0xaa;
 459         addr->eaddr[5] = 0x77;
 460 #ifdef  UUID_DEBUG
 461         printf("uuid_get_address: %02x-%02x-%02x-%02x-%02x-%02x\n",
 462                addr->eaddr[0], addr->eaddr[1], addr->eaddr[2], addr->eaddr[3],
 463                addr->eaddr[4], addr->eaddr[5]);
 464 #endif
 465     }
 466     return 0;
 467 }
 468
 469 void
 470 uuid__get_os_time(uuid_time_t * os_time)
 471 {
 472     struct timeval tp;
 473
 474     if (gettimeofday(&tp, NULL)) {
 475         perror("uuid__get_time");
 476         exit(-1);
 477     }
 478     os_time->hi = tp.tv_sec;
 479     os_time->lo = tp.tv_usec * 10;
 480 }
 481
 482 #endif /* KERNEL */