af6dfa018761dbde0274a4ab8b47ac7968033ec2
[openafs.git] / 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  *    @param[in]  uuid pointer to a afsUUID
205  *    @param[out] buf  format work buffer
206  *
207  *    @returns pointer to buffer containing string representation of "uuid"
208  */
209
210 char *
211 afsUUID_to_string(const afsUUID * uuid, struct uuid_fmtbuf *buf)
212 {
213     memset(buf, 0, sizeof(*buf));
214     snprintf(buf->buffer, sizeof(buf->buffer),
215              "%08x-%04x-%04x-%02x-%02x-%02x%02x%02x%02x%02x%02x",
216              uuid->time_low, uuid->time_mid, uuid->time_hi_and_version,
217              (unsigned char)uuid->clock_seq_hi_and_reserved,
218              (unsigned char)uuid->clock_seq_low, (unsigned char)uuid->node[0],
219              (unsigned char)uuid->node[1], (unsigned char)uuid->node[2],
220              (unsigned char)uuid->node[3], (unsigned char)uuid->node[4],
221              (unsigned char)uuid->node[5]);
222
223     return buf->buffer;
224 }
225 #endif
226
227 afs_int32
228 afs_uuid_create(afsUUID * uuid)
229 {
230 #ifdef AFS_NT40_ENV
231     UuidCreate((UUID *) uuid);
232 #else /* AFS_NT40_ENV */
233     uuid_address_t eaddr;
234     afs_int32 got_no_time = 0, code;
235
236     if (!uuid_init_done) {
237         uuid_time_t t;
238         u_short seedp[4], seed = 0;
239         rand_m = 971;;
240         rand_ia = 11113;
241         rand_ib = 104322;
242         rand_irand = 4181;
243         /*
244          * Generating our 'seed' value
245          *
246          * We start with the current time, but, since the resolution of clocks is
247          * system hardware dependent (eg. Ultrix is 10 msec.) and most likely
248          * coarser than our resolution (10 usec) we 'mixup' the bits by xor'ing
249          * all the bits together.  This will have the effect of involving all of
250          * the bits in the determination of the seed value while remaining system
251          * independent.  Then for good measure to ensure a unique seed when there
252          * are multiple processes creating UUID's on a system, we add in the PID.
253          */
254         uuid__get_os_time(&t);
255         memcpy(&seedp, &t, sizeof(seedp));
256         seed ^= seedp[0];
257         seed ^= seedp[1];
258         seed ^= seedp[2];
259         seed ^= seedp[3];
260 #if defined(KERNEL) && defined(AFS_XBSD_ENV)
261         rand_irand += seed + (afs_uint32) curproc->p_pid;
262 #elif defined(UKERNEL)
263         rand_irand += seed + (afs_uint32) osi_getpid();
264 #else
265         rand_irand += seed + (afs_uint32) getpid();
266 #endif
267         uuid__get_os_time(&time_last);
268         clock_seq = true_random();
269 #ifdef AFS_NT40_ENV
270         if (afs_winsockInit() < 0) {
271             return WSAGetLastError();
272         }
273 #endif
274         uuid_init_done = 1;
275     }
276     if ((code = uuid_get_address(&eaddr)))
277         return code;            /* get our hardware network address */
278     do {
279         /* get the current time */
280         uuid__get_os_time(&time_now);
281         /*
282          * check that our clock hasn't gone backwards and handle it
283          *    accordingly with clock_seq
284          * check that we're not generating uuid's faster than we
285          *    can accommodate with our uuid_time_adjust fudge factor
286          */
287         if ((code = time_cmp(&time_now, &time_last)) == -1) {
288             /* A clock_seq value of 0 indicates that it hasn't been initialized. */
289             if (clock_seq == 0) {
290                 clock_seq = true_random();
291             }
292             clock_seq = (clock_seq + 1) & 0x3fff;
293             if (clock_seq == 0)
294                 clock_seq = clock_seq + 1;
295             uuid_time_adjust = 0;
296         } else if (code == 1) {
297             uuid_time_adjust = 0;
298         } else {
299             if (uuid_time_adjust == 0x7fff)     /* spin while we wait for the clock to tick */
300                 got_no_time = 1;
301             else
302                 uuid_time_adjust++;
303         }
304     } while (got_no_time);
305     time_last.lo = time_now.lo;
306     time_last.hi = time_now.hi;
307     if (uuid_time_adjust != 0) {
308         if (time_now.lo & 0x80000000) {
309             time_now.lo += uuid_time_adjust;
310             if (!(time_now.lo & 0x80000000))
311                 time_now.hi++;
312         } else
313             time_now.lo += uuid_time_adjust;
314     }
315     uuid->time_low = time_now.lo;
316     uuid->time_mid = time_now.hi & 0x0000ffff;
317     uuid->time_hi_and_version = (time_now.hi & 0x0fff0000) >> 16;
318     uuid->time_hi_and_version |= (1 << 12);
319     uuid->clock_seq_low = clock_seq & 0xff;
320     uuid->clock_seq_hi_and_reserved = (clock_seq & 0x3f00) >> 8;
321     uuid->clock_seq_hi_and_reserved |= 0x80;
322     memcpy(uuid->node, &eaddr, sizeof(uuid_address_t));
323 #endif /* AFS_NT40_ENV */
324     return 0;
325 }
326
327 u_short
328 afs_uuid_hash(afsUUID * uuid)
329 {
330     short c0 = 0, c1 = 0, x, y;
331     char *next_uuid = (char *)uuid;
332
333     /*
334      * For speed lets unroll the following loop:
335      *
336      *   for (i = 0; i < UUID_K_LENGTH; i++)
337      *   {
338      *       c0 = c0 + *next_uuid++;
339      *       c1 = c1 + c0;
340      *   }
341      */
342     c0 = c0 + *next_uuid++;
343     c1 = c1 + c0;
344     c0 = c0 + *next_uuid++;
345     c1 = c1 + c0;
346     c0 = c0 + *next_uuid++;
347     c1 = c1 + c0;
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     /*  Calculate the value for "First octet" of the hash  */
375     x = -c1 % 255;
376     if (x < 0) {
377         x = x + 255;
378     }
379     /*  Calculate the value for "second octet" of the hash */
380     y = (c1 - c0) % 255;
381     if (y < 0) {
382         y = y + 255;
383     }
384     return ((y * 256) + x);
385 }
386
387 #ifdef KERNEL
388
389 extern struct interfaceAddr afs_cb_interface;
390
391 static int
392 uuid_get_address(uuid_address_p_t addr)
393 {
394     memcpy(addr->eaddr, &afs_cb_interface.addr_in[0], 4);
395     addr->eaddr[4] = 0xaa;
396     addr->eaddr[5] = 0x77;
397     return 0;
398 }
399
400 void
401 uuid__get_os_time(uuid_time_t * os_time)
402 {
403     osi_timeval32_t tp;
404
405     osi_GetTime(&tp);
406     os_time->hi = tp.tv_sec;
407     os_time->lo = tp.tv_usec * 10;
408 }
409
410 #else /* KERNEL */
411
412 char hostName1[128] = "localhost";
413 static int
414 uuid_get_address(uuid_address_p_t addr)
415 {
416     afs_int32 code;
417     afs_uint32 addr1 = 0;
418     struct hostent *he = NULL;
419
420     code = gethostname(hostName1, 64);
421     if (!code)
422         he = gethostbyname(hostName1);
423
424     if (he)
425         memcpy(&addr1, he->h_addr_list[0], 4);
426 #ifdef UKERNEL
427     else
428         addr1=rxi_getaddr();
429 #endif
430
431     if (!addr1) {
432 #ifdef AFS_NT40_ENV
433         return ENOENT;
434 #else
435         return errno;
436 #endif
437     }
438
439     addr1 = ntohl(addr1);
440     memcpy(addr->eaddr, &addr1, 4);
441     addr->eaddr[4] = 0xaa;
442     addr->eaddr[5] = 0x77;
443 #ifdef  UUID_DEBUG
444     printf("uuid_get_address: %02x-%02x-%02x-%02x-%02x-%02x\n",
445            addr->eaddr[0], addr->eaddr[1], addr->eaddr[2], addr->eaddr[3],
446            addr->eaddr[4], addr->eaddr[5]);
447 #endif
448     return 0;
449 }
450
451 void
452 uuid__get_os_time(uuid_time_t * os_time)
453 {
454     struct timeval tp;
455
456     if (gettimeofday(&tp, NULL)) {
457         perror("uuid__get_time");
458         exit(-1);
459     }
460     os_time->hi = tp.tv_sec;
461     os_time->lo = tp.tv_usec * 10;
462 }
463
464 #endif /* KERNEL */