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