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 #include <afs/param.h>
  47
  48 #ifndef KERNEL
  49 # include <roken.h>
  50
  51 # ifdef AFS_NT40_ENV
  52 #  include <rpc.h>
  53 # else
  54 #  include <net/if.h>
  55 #  if !defined(AFS_LINUX20_ENV) && !defined(AFS_ARM_DARWIN_ENV)
  56 #   include <netinet/if_ether.h>
  57 #  endif
  58 # endif
  59
  60 #include "afsutil.h"
  61
  62 #else
  63 # include "afs/sysincludes.h"
  64 # include "afsincludes.h"
  65 #endif
  66 #ifdef UKERNEL
  67 # include "rx/rx_prototypes.h"
  68 #endif
  69
  70 typedef struct {
  71     char eaddr[6];              /* 6 bytes of ethernet hardware address */
  72 } uuid_address_t, *uuid_address_p_t;
  73
  74
  75 typedef struct {
  76     afs_uint32 lo;
  77     afs_uint32 hi;
  78 } uuid_time_t, *uuid_time_p_t;
  79
  80 static int uuid_get_address(uuid_address_p_t addr);
  81 void uuid__get_os_time(uuid_time_t * os_time);
  82
  83 /*
  84  * |<------------------------- 32 bits -------------------------->|
  85  *
  86  * +--------------------------------------------------------------+
  87  * |                     low 32 bits of time                      |  0-3  .time_low
  88  * +-------------------------------+-------------------------------
  89  * |     mid 16 bits of time       |  4-5               .time_mid
  90  * +-------+-----------------------+
  91  * | vers. |   hi 12 bits of time  |  6-7               .time_hi_and_version
  92  * +-------+-------+---------------+
  93  * |Res|  clkSeqHi |  8                                 .clock_seq_hi_and_reserved
  94  * +---------------+
  95  * |   clkSeqLow   |  9                                 .clock_seq_low
  96  * +---------------+----------...-----+
  97  * |            node ID               |  8-16           .node
  98  * +--------------------------...-----+
  99  */
 100
 101 afsUUID afs_uuid_g_nil_uuid;
 102 static uuid_time_t time_now, time_last;
 103 static u_short uuid_time_adjust, clock_seq;
 104 static afs_uint32 rand_m, rand_ia, rand_ib, rand_irand, uuid_init_done = 0;
 105
 106 #define uuid_create_nil(uuid) memset(uuid, 0, sizeof(afsUUID))
 107
 108 afs_int32
 109 afs_uuid_equal(afsUUID * u1, afsUUID * u2)
 110 {
 111     return (memcmp(u1, u2, sizeof(afsUUID)) == 0);
 112 }
 113
 114 afs_int32
 115 afs_uuid_is_nil(afsUUID * u1)
 116 {
 117     if (!u1)
 118         return 1;
 119     return afs_uuid_equal(u1, &afs_uuid_g_nil_uuid);
 120 }
 121
 122 void
 123 afs_htonuuid(afsUUID * uuidp)
 124 {
 125     uuidp->time_low = htonl(uuidp->time_low);
 126     uuidp->time_mid = htons(uuidp->time_mid);
 127     uuidp->time_hi_and_version = htons(uuidp->time_hi_and_version);
 128 }
 129
 130 void
 131 afs_ntohuuid(afsUUID * uuidp)
 132 {
 133     uuidp->time_low = ntohl(uuidp->time_low);
 134     uuidp->time_mid = ntohs(uuidp->time_mid);
 135     uuidp->time_hi_and_version = ntohs(uuidp->time_hi_and_version);
 136 }
 137
 138 static u_short
 139 true_random(void)
 140 {
 141     rand_m += 7;
 142     rand_ia += 1907;
 143     rand_ib += 73939;
 144     if (rand_m >= 9973)
 145         rand_m -= 9871;
 146     if (rand_ia >= 99991)
 147         rand_ia -= 89989;
 148     if (rand_ib >= 224729)
 149         rand_ib -= 96233;
 150     rand_irand = (rand_irand * rand_m) + rand_ia + rand_ib;
 151     return (((rand_irand) >> 16) ^ (rand_irand & 0x3fff));
 152 }
 153
 154
 155 static afs_int32
 156 time_cmp(uuid_time_p_t time1, uuid_time_p_t time2)
 157 {
 158     if (time1->hi < time2->hi)
 159         return (-1);
 160     if (time1->hi > time2->hi)
 161         return (1);
 162     if (time1->lo < time2->lo)
 163         return (-1);
 164     if (time1->lo > time2->lo)
 165         return (1);
 166     return (0);
 167 }
 168
 169 /*
 170  *    Converts a string UUID to binary representation.
 171  */
 172
 173 #if !defined(KERNEL) && !defined(UKERNEL)
 174 int
 175 afsUUID_from_string(const char *str, afsUUID * uuid)
 176 {
 177     unsigned int time_low, time_mid, time_hi_and_version;
 178     unsigned int clock_seq_hi_and_reserved, clock_seq_low;
 179     unsigned int node[6];
 180     int i;
 181
 182     i = sscanf(str, "%08x-%04x-%04x-%02x-%02x-%02x%02x%02x%02x%02x%02x",
 183                &time_low, &time_mid, &time_hi_and_version,
 184                &clock_seq_hi_and_reserved, &clock_seq_low, &node[0], &node[1],
 185                &node[2], &node[3], &node[4], &node[5]);
 186     if (i != 11)
 187         return -1;
 188
 189     uuid->time_low = time_low;
 190     uuid->time_mid = time_mid;
 191     uuid->time_hi_and_version = time_hi_and_version;
 192     uuid->clock_seq_hi_and_reserved = clock_seq_hi_and_reserved;
 193     uuid->clock_seq_low = clock_seq_low;
 194
 195     for (i = 0; i < 6; i++)
 196         uuid->node[i] = node[i];
 197
 198     return 0;
 199 }
 200
 201 /*
 202  *    Converts a UUID from binary representation to a string representation.
 203  */
 204
 205 int
 206 afsUUID_to_string(const afsUUID * uuid, char *str, size_t strsz)
 207 {
 208     snprintf(str, strsz, "%08x-%04x-%04x-%02x-%02x-%02x%02x%02x%02x%02x%02x",
 209              uuid->time_low, uuid->time_mid, uuid->time_hi_and_version,
 210              (unsigned char)uuid->clock_seq_hi_and_reserved,
 211              (unsigned char)uuid->clock_seq_low, (unsigned char)uuid->node[0],
 212              (unsigned char)uuid->node[1], (unsigned char)uuid->node[2],
 213              (unsigned char)uuid->node[3], (unsigned char)uuid->node[4],
 214              (unsigned char)uuid->node[5]);
 215
 216     return 0;
 217 }
 218 #endif
 219
 220 afs_int32
 221 afs_uuid_create(afsUUID * uuid)
 222 {
 223 #ifdef AFS_NT40_ENV
 224     UuidCreate((UUID *) uuid);
 225 #else /* AFS_NT40_ENV */
 226     uuid_address_t eaddr;
 227     afs_int32 got_no_time = 0, code;
 228
 229     if (!uuid_init_done) {
 230         uuid_time_t t;
 231         u_short seedp[4], seed = 0;
 232         rand_m = 971;;
 233         rand_ia = 11113;
 234         rand_ib = 104322;
 235         rand_irand = 4181;
 236         /*
 237          * Generating our 'seed' value
 238          *
 239          * We start with the current time, but, since the resolution of clocks is
 240          * system hardware dependent (eg. Ultrix is 10 msec.) and most likely
 241          * coarser than our resolution (10 usec) we 'mixup' the bits by xor'ing
 242          * all the bits together.  This will have the effect of involving all of
 243          * the bits in the determination of the seed value while remaining system
 244          * independent.  Then for good measure to ensure a unique seed when there
 245          * are multiple processes creating UUID's on a system, we add in the PID.
 246          */
 247         uuid__get_os_time(&t);
 248         memcpy(&seedp, &t, sizeof(seedp));
 249         seed ^= seedp[0];
 250         seed ^= seedp[1];
 251         seed ^= seedp[2];
 252         seed ^= seedp[3];
 253 #if defined(KERNEL) && defined(AFS_XBSD_ENV)
 254         rand_irand += seed + (afs_uint32) curproc->p_pid;
 255 #elif defined(UKERNEL)
 256         rand_irand += seed + (afs_uint32) osi_getpid();
 257 #else
 258         rand_irand += seed + (afs_uint32) getpid();
 259 #endif
 260         uuid__get_os_time(&time_last);
 261         clock_seq = true_random();
 262 #ifdef AFS_NT40_ENV
 263         if (afs_winsockInit() < 0) {
 264             return WSAGetLastError();
 265         }
 266 #endif
 267         uuid_init_done = 1;
 268     }
 269     if ((code = uuid_get_address(&eaddr)))
 270         return code;            /* get our hardware network address */
 271     do {
 272         /* get the current time */
 273         uuid__get_os_time(&time_now);
 274         /*
 275          * check that our clock hasn't gone backwards and handle it
 276          *    accordingly with clock_seq
 277          * check that we're not generating uuid's faster than we
 278          *    can accommodate with our uuid_time_adjust fudge factor
 279          */
 280         if ((code = time_cmp(&time_now, &time_last)) == -1) {
 281             /* A clock_seq value of 0 indicates that it hasn't been initialized. */
 282             if (clock_seq == 0) {
 283                 clock_seq = true_random();
 284             }
 285             clock_seq = (clock_seq + 1) & 0x3fff;
 286             if (clock_seq == 0)
 287                 clock_seq = clock_seq + 1;
 288             uuid_time_adjust = 0;
 289         } else if (code == 1) {
 290             uuid_time_adjust = 0;
 291         } else {
 292             if (uuid_time_adjust == 0x7fff)     /* spin while we wait for the clock to tick */
 293                 got_no_time = 1;
 294             else
 295                 uuid_time_adjust++;
 296         }
 297     } while (got_no_time);
 298     time_last.lo = time_now.lo;
 299     time_last.hi = time_now.hi;
 300     if (uuid_time_adjust != 0) {
 301         if (time_now.lo & 0x80000000) {
 302             time_now.lo += uuid_time_adjust;
 303             if (!(time_now.lo & 0x80000000))
 304                 time_now.hi++;
 305         } else
 306             time_now.lo += uuid_time_adjust;
 307     }
 308     uuid->time_low = time_now.lo;
 309     uuid->time_mid = time_now.hi & 0x0000ffff;
 310     uuid->time_hi_and_version = (time_now.hi & 0x0fff0000) >> 16;
 311     uuid->time_hi_and_version |= (1 << 12);
 312     uuid->clock_seq_low = clock_seq & 0xff;
 313     uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3f00) >> 8;
 314     uuid->clock_seq_hi_and_reserved |= 0x80;
 315     memcpy(uuid->node, &eaddr, sizeof(uuid_address_t));
 316 #endif /* AFS_NT40_ENV */
 317     return 0;
 318 }
 319
 320 u_short
 321 afs_uuid_hash(afsUUID * uuid)
 322 {
 323     short c0 = 0, c1 = 0, x, y;
 324     char *next_uuid = (char *)uuid;
 325
 326     /*
 327      * For speed lets unroll the following loop:
 328      *
 329      *   for (i = 0; i < UUID_K_LENGTH; i++)
 330      *   {
 331      *       c0 = c0 + *next_uuid++;
 332      *       c1 = c1 + c0;
 333      *   }
 334      */
 335     c0 = c0 + *next_uuid++;
 336     c1 = c1 + c0;
 337     c0 = c0 + *next_uuid++;
 338     c1 = c1 + c0;
 339     c0 = c0 + *next_uuid++;
 340     c1 = c1 + c0;
 341     c0 = c0 + *next_uuid++;
 342     c1 = c1 + c0;
 343     c0 = c0 + *next_uuid++;
 344     c1 = c1 + c0;
 345     c0 = c0 + *next_uuid++;
 346     c1 = c1 + c0;
 347     c0 = c0 + *next_uuid++;
 348     c1 = c1 + c0;
 349     c0 = c0 + *next_uuid++;
 350     c1 = c1 + c0;
 351     c0 = c0 + *next_uuid++;
 352     c1 = c1 + c0;
 353     c0 = c0 + *next_uuid++;
 354     c1 = c1 + c0;
 355     c0 = c0 + *next_uuid++;
 356     c1 = c1 + c0;
 357     c0 = c0 + *next_uuid++;
 358     c1 = c1 + c0;
 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     /*  Calculate the value for "First octet" of the hash  */
 368     x = -c1 % 255;
 369     if (x < 0) {
 370         x = x + 255;
 371     }
 372     /*  Calculate the value for "second octet" of the hash */
 373     y = (c1 - c0) % 255;
 374     if (y < 0) {
 375         y = y + 255;
 376     }
 377     return ((y * 256) + x);
 378 }
 379
 380 #ifdef KERNEL
 381
 382 extern struct interfaceAddr afs_cb_interface;
 383
 384 static int
 385 uuid_get_address(uuid_address_p_t addr)
 386 {
 387     memcpy(addr->eaddr, &afs_cb_interface.addr_in[0], 4);
 388     addr->eaddr[4] = 0xaa;
 389     addr->eaddr[5] = 0x77;
 390     return 0;
 391 }
 392
 393 void
 394 uuid__get_os_time(uuid_time_t * os_time)
 395 {
 396     osi_timeval_t tp;
 397
 398     osi_GetTime(&tp);
 399     os_time->hi = tp.tv_sec;
 400     os_time->lo = tp.tv_usec * 10;
 401 }
 402
 403 #else /* KERNEL */
 404
 405 char hostName1[128] = "localhost";
 406 static int
 407 uuid_get_address(uuid_address_p_t addr)
 408 {
 409     afs_int32 code;
 410     afs_uint32 addr1 = 0;
 411     struct hostent *he = NULL;
 412
 413     code = gethostname(hostName1, 64);
 414     if (!code)
 415         he = gethostbyname(hostName1);
 416
 417     if (he)
 418         memcpy(&addr1, he->h_addr_list[0], 4);
 419 #ifdef UKERNEL
 420     else
 421         addr1=rxi_getaddr();
 422 #endif
 423
 424     if (!addr1) {
 425 #ifdef AFS_NT40_ENV
 426         return ENOENT;
 427 #else
 428         return errno;
 429 #endif
 430     }
 431
 432     addr1 = ntohl(addr1);
 433     memcpy(addr->eaddr, &addr1, 4);
 434     addr->eaddr[4] = 0xaa;
 435     addr->eaddr[5] = 0x77;
 436 #ifdef  UUID_DEBUG
 437     printf("uuid_get_address: %02x-%02x-%02x-%02x-%02x-%02x\n",
 438            addr->eaddr[0], addr->eaddr[1], addr->eaddr[2], addr->eaddr[3],
 439            addr->eaddr[4], addr->eaddr[5]);
 440 #endif
 441     return 0;
 442 }
 443
 444 void
 445 uuid__get_os_time(uuid_time_t * os_time)
 446 {
 447     struct timeval tp;
 448
 449     if (gettimeofday(&tp, NULL)) {
 450         perror("uuid__get_time");
 451         exit(-1);
 452     }
 453     os_time->hi = tp.tv_sec;
 454     os_time->lo = tp.tv_usec * 10;
 455 }
 456
 457 #endif /* KERNEL */