gen_uuid.c revision 8cb1c0ef 
1/*
2 * gen_uuid.c --- generate a DCE-compatible uuid
3 *
4 * Copyright (C) 1996, 1997, 1998, 1999 Theodore Ts'o.
5 *
6 * %Begin-Header%
7 * Redistribution and use in source and binary forms, with or without
8 * modification, are permitted provided that the following conditions
9 * are met:
10 * 1. Redistributions of source code must retain the above copyright
11 *    notice, and the entire permission notice in its entirety,
12 *    including the disclaimer of warranties.
13 * 2. Redistributions in binary form must reproduce the above copyright
14 *    notice, this list of conditions and the following disclaimer in the
15 *    documentation and/or other materials provided with the distribution.
16 * 3. The name of the author may not be used to endorse or promote
17 *    products derived from this software without specific prior
18 *    written permission.
19 *
20 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
21 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
22 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
23 * WHICH ARE HEREBY DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR BE
24 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
26 * OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
27 * BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
28 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
29 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
30 * USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
31 * DAMAGE.
32 * %End-Header%
33 */
34
35#ifdef _WIN32
36#define _WIN32_WINNT 0x0500
37#include <windows.h>
38#define UUID MYUUID
39#endif
40#include <stdio.h>
41#ifdef HAVE_UNISTD_H
42#include <unistd.h>
43#endif
44#ifdef HAVE_STDLIB_H
45#include <stdlib.h>
46#endif
47#include <string.h>
48#include <fcntl.h>
49#include <errno.h>
50#include <limits.h>
51#include <sys/types.h>
52#ifdef HAVE_SYS_TIME_H
53#include <sys/time.h>
54#endif
55#include <sys/stat.h>
56#ifdef HAVE_SYS_FILE_H
57#include <sys/file.h>
58#endif
59#ifdef HAVE_SYS_IOCTL_H
60#include <sys/ioctl.h>
61#endif
62#ifdef HAVE_SYS_SOCKET_H
63#include <sys/socket.h>
64#endif
65#ifdef HAVE_SYS_UN_H
66#include <sys/un.h>
67#endif
68#ifdef HAVE_SYS_SOCKIO_H
69#include <sys/sockio.h>
70#endif
71#ifdef HAVE_NET_IF_H
72#include <net/if.h>
73#endif
74#ifdef HAVE_NETINET_IN_H
75#include <netinet/in.h>
76#endif
77#ifdef HAVE_NET_IF_DL_H
78#include <net/if_dl.h>
79#endif
80#if defined(__linux__) && defined(HAVE_SYS_SYSCALL_H)
81#include <sys/syscall.h>
82#endif
83
84#include "all-io.h"
85#include "uuidP.h"
86#include "uuidd.h"
87#include "randutils.h"
88#include "strutils.h"
89#include "c.h"
90#include "md5.h"
91#include "sha1.h"
92
93#ifdef HAVE_TLS
94#define THREAD_LOCAL static __thread
95#else
96#define THREAD_LOCAL static
97#endif
98
99/* index with UUID_VARIANT_xxx and shift 5 bits */
100static unsigned char variant_bits[] = { 0x00, 0x04, 0x06, 0x07 };
101
102#ifdef _WIN32
103static void gettimeofday (struct timeval *tv, void *dummy)
104{
105	FILETIME	ftime;
106	uint64_t	n;
107
108	GetSystemTimeAsFileTime (&ftime);
109	n = (((uint64_t) ftime.dwHighDateTime << 32)
110	     + (uint64_t) ftime.dwLowDateTime);
111	if (n) {
112		n /= 10;
113		n -= ((369 * 365 + 89) * (uint64_t) 86400) * 1000000;
114	}
115
116	tv->tv_sec = n / 1000000;
117	tv->tv_usec = n % 1000000;
118}
119
120static int getuid (void)
121{
122	return 1;
123}
124#endif
125
126/*
127 * Get the ethernet hardware address, if we can find it...
128 *
129 * XXX for a windows version, probably should use GetAdaptersInfo:
130 * http://www.codeguru.com/cpp/i-n/network/networkinformation/article.php/c5451
131 * commenting out get_node_id just to get gen_uuid to compile under windows
132 * is not the right way to go!
133 */
134static int get_node_id(unsigned char *node_id)
135{
136#ifdef HAVE_NET_IF_H
137	int		sd;
138	struct ifreq	ifr, *ifrp;
139	struct ifconf	ifc;
140	char buf[1024];
141	int		n, i;
142	unsigned char	*a;
143#ifdef HAVE_NET_IF_DL_H
144	struct sockaddr_dl *sdlp;
145#endif
146
147/*
148 * BSD 4.4 defines the size of an ifreq to be
149 * max(sizeof(ifreq), sizeof(ifreq.ifr_name)+ifreq.ifr_addr.sa_len
150 * However, under earlier systems, sa_len isn't present, so the size is
151 * just sizeof(struct ifreq)
152 */
153#ifdef HAVE_SA_LEN
154#define ifreq_size(i) max(sizeof(struct ifreq),\
155     sizeof((i).ifr_name)+(i).ifr_addr.sa_len)
156#else
157#define ifreq_size(i) sizeof(struct ifreq)
158#endif /* HAVE_SA_LEN */
159
160	sd = socket(AF_INET, SOCK_DGRAM, IPPROTO_IP);
161	if (sd < 0) {
162		return -1;
163	}
164	memset(buf, 0, sizeof(buf));
165	ifc.ifc_len = sizeof(buf);
166	ifc.ifc_buf = buf;
167	if (ioctl (sd, SIOCGIFCONF, (char *)&ifc) < 0) {
168		close(sd);
169		return -1;
170	}
171	n = ifc.ifc_len;
172	for (i = 0; i < n; i+= ifreq_size(*ifrp) ) {
173		ifrp = (struct ifreq *)((char *) ifc.ifc_buf+i);
174		strncpy(ifr.ifr_name, ifrp->ifr_name, IFNAMSIZ);
175#ifdef SIOCGIFHWADDR
176		if (ioctl(sd, SIOCGIFHWADDR, &ifr) < 0)
177			continue;
178		a = (unsigned char *) &ifr.ifr_hwaddr.sa_data;
179#else
180#ifdef SIOCGENADDR
181		if (ioctl(sd, SIOCGENADDR, &ifr) < 0)
182			continue;
183		a = (unsigned char *) ifr.ifr_enaddr;
184#else
185#ifdef HAVE_NET_IF_DL_H
186		sdlp = (struct sockaddr_dl *) &ifrp->ifr_addr;
187		if ((sdlp->sdl_family != AF_LINK) || (sdlp->sdl_alen != 6))
188			continue;
189		a = (unsigned char *) &sdlp->sdl_data[sdlp->sdl_nlen];
190#else
191		/*
192		 * XXX we don't have a way of getting the hardware
193		 * address
194		 */
195		close(sd);
196		return 0;
197#endif /* HAVE_NET_IF_DL_H */
198#endif /* SIOCGENADDR */
199#endif /* SIOCGIFHWADDR */
200		if (!a[0] && !a[1] && !a[2] && !a[3] && !a[4] && !a[5])
201			continue;
202		if (node_id) {
203			memcpy(node_id, a, 6);
204			close(sd);
205			return 1;
206		}
207	}
208	close(sd);
209#endif
210	return 0;
211}
212
213/* Assume that the gettimeofday() has microsecond granularity */
214#define MAX_ADJUSTMENT 10
215
216/*
217 * Get clock from global sequence clock counter.
218 *
219 * Return -1 if the clock counter could not be opened/locked (in this case
220 * pseudorandom value is returned in @ret_clock_seq), otherwise return 0.
221 */
222static int get_clock(uint32_t *clock_high, uint32_t *clock_low,
223		     uint16_t *ret_clock_seq, int *num)
224{
225	THREAD_LOCAL int		adjustment = 0;
226	THREAD_LOCAL struct timeval	last = {0, 0};
227	THREAD_LOCAL int		state_fd = -2;
228	THREAD_LOCAL FILE		*state_f;
229	THREAD_LOCAL uint16_t		clock_seq;
230	struct timeval			tv;
231	uint64_t			clock_reg;
232	mode_t				save_umask;
233	int				len;
234	int				ret = 0;
235
236	if (state_fd == -1)
237		ret = -1;
238
239	if (state_fd == -2) {
240		save_umask = umask(0);
241		state_fd = open(LIBUUID_CLOCK_FILE, O_RDWR|O_CREAT|O_CLOEXEC, 0660);
242		(void) umask(save_umask);
243		if (state_fd != -1) {
244			state_f = fdopen(state_fd, "r+" UL_CLOEXECSTR);
245			if (!state_f) {
246				close(state_fd);
247				state_fd = -1;
248				ret = -1;
249			}
250		}
251		else
252			ret = -1;
253	}
254	if (state_fd >= 0) {
255		rewind(state_f);
256		while (flock(state_fd, LOCK_EX) < 0) {
257			if ((errno == EAGAIN) || (errno == EINTR))
258				continue;
259			fclose(state_f);
260			close(state_fd);
261			state_fd = -1;
262			ret = -1;
263			break;
264		}
265	}
266	if (state_fd >= 0) {
267		unsigned int cl;
268		unsigned long tv1, tv2;
269		int a;
270
271		if (fscanf(state_f, "clock: %04x tv: %lu %lu adj: %d\n",
272			   &cl, &tv1, &tv2, &a) == 4) {
273			clock_seq = cl & 0x3FFF;
274			last.tv_sec = tv1;
275			last.tv_usec = tv2;
276			adjustment = a;
277		}
278	}
279
280	if ((last.tv_sec == 0) && (last.tv_usec == 0)) {
281		random_get_bytes(&clock_seq, sizeof(clock_seq));
282		clock_seq &= 0x3FFF;
283		gettimeofday(&last, NULL);
284		last.tv_sec--;
285	}
286
287try_again:
288	gettimeofday(&tv, NULL);
289	if ((tv.tv_sec < last.tv_sec) ||
290	    ((tv.tv_sec == last.tv_sec) &&
291	     (tv.tv_usec < last.tv_usec))) {
292		clock_seq = (clock_seq+1) & 0x3FFF;
293		adjustment = 0;
294		last = tv;
295	} else if ((tv.tv_sec == last.tv_sec) &&
296	    (tv.tv_usec == last.tv_usec)) {
297		if (adjustment >= MAX_ADJUSTMENT)
298			goto try_again;
299		adjustment++;
300	} else {
301		adjustment = 0;
302		last = tv;
303	}
304
305	clock_reg = tv.tv_usec*10 + adjustment;
306	clock_reg += ((uint64_t) tv.tv_sec)*10000000;
307	clock_reg += (((uint64_t) 0x01B21DD2) << 32) + 0x13814000;
308
309	if (num && (*num > 1)) {
310		adjustment += *num - 1;
311		last.tv_usec += adjustment / 10;
312		adjustment = adjustment % 10;
313		last.tv_sec += last.tv_usec / 1000000;
314		last.tv_usec = last.tv_usec % 1000000;
315	}
316
317	if (state_fd >= 0) {
318		rewind(state_f);
319		len = fprintf(state_f,
320			      "clock: %04x tv: %016ld %08ld adj: %08d\n",
321			      clock_seq, (long)last.tv_sec, (long)last.tv_usec, adjustment);
322		fflush(state_f);
323		if (ftruncate(state_fd, len) < 0) {
324			fprintf(state_f, "                   \n");
325			fflush(state_f);
326		}
327		rewind(state_f);
328		flock(state_fd, LOCK_UN);
329	}
330
331	*clock_high = clock_reg >> 32;
332	*clock_low = clock_reg;
333	*ret_clock_seq = clock_seq;
334	return ret;
335}
336
337#if defined(HAVE_UUIDD) && defined(HAVE_SYS_UN_H)
338
339/*
340 * Try using the uuidd daemon to generate the UUID
341 *
342 * Returns 0 on success, non-zero on failure.
343 */
344static int get_uuid_via_daemon(int op, uuid_t out, int *num)
345{
346	char op_buf[64];
347	int op_len;
348	int s;
349	ssize_t ret;
350	int32_t reply_len = 0, expected = 16;
351	struct sockaddr_un srv_addr;
352
353	if (sizeof(UUIDD_SOCKET_PATH) > sizeof(srv_addr.sun_path))
354		return -1;
355
356	if ((s = socket(AF_UNIX, SOCK_STREAM, 0)) < 0)
357		return -1;
358
359	srv_addr.sun_family = AF_UNIX;
360	xstrncpy(srv_addr.sun_path, UUIDD_SOCKET_PATH, sizeof(srv_addr.sun_path));
361
362	if (connect(s, (const struct sockaddr *) &srv_addr,
363		    sizeof(struct sockaddr_un)) < 0)
364		goto fail;
365
366	op_buf[0] = op;
367	op_len = 1;
368	if (op == UUIDD_OP_BULK_TIME_UUID) {
369		memcpy(op_buf+1, num, sizeof(*num));
370		op_len += sizeof(*num);
371		expected += sizeof(*num);
372	}
373
374	ret = write(s, op_buf, op_len);
375	if (ret < 1)
376		goto fail;
377
378	ret = read_all(s, (char *) &reply_len, sizeof(reply_len));
379	if (ret < 0)
380		goto fail;
381
382	if (reply_len != expected)
383		goto fail;
384
385	ret = read_all(s, op_buf, reply_len);
386
387	if (op == UUIDD_OP_BULK_TIME_UUID)
388		memcpy(op_buf+16, num, sizeof(int));
389
390	memcpy(out, op_buf, 16);
391
392	close(s);
393	return ((ret == expected) ? 0 : -1);
394
395fail:
396	close(s);
397	return -1;
398}
399
400#else /* !defined(HAVE_UUIDD) && defined(HAVE_SYS_UN_H) */
401static int get_uuid_via_daemon(int op __attribute__((__unused__)),
402				uuid_t out __attribute__((__unused__)),
403				int *num __attribute__((__unused__)))
404{
405	return -1;
406}
407#endif
408
409int __uuid_generate_time(uuid_t out, int *num)
410{
411	static unsigned char node_id[6];
412	static int has_init = 0;
413	struct uuid uu;
414	uint32_t	clock_mid;
415	int ret;
416
417	if (!has_init) {
418		if (get_node_id(node_id) <= 0) {
419			random_get_bytes(node_id, 6);
420			/*
421			 * Set multicast bit, to prevent conflicts
422			 * with IEEE 802 addresses obtained from
423			 * network cards
424			 */
425			node_id[0] |= 0x01;
426		}
427		has_init = 1;
428	}
429	ret = get_clock(&clock_mid, &uu.time_low, &uu.clock_seq, num);
430	uu.clock_seq |= 0x8000;
431	uu.time_mid = (uint16_t) clock_mid;
432	uu.time_hi_and_version = ((clock_mid >> 16) & 0x0FFF) | 0x1000;
433	memcpy(uu.node, node_id, 6);
434	uuid_pack(&uu, out);
435	return ret;
436}
437
438/*
439 * Generate time-based UUID and store it to @out
440 *
441 * Tries to guarantee uniqueness of the generated UUIDs by obtaining them from the uuidd daemon,
442 * or, if uuidd is not usable, by using the global clock state counter (see get_clock()).
443 * If neither of these is possible (e.g. because of insufficient permissions), it generates
444 * the UUID anyway, but returns -1. Otherwise, returns 0.
445 */
446static int uuid_generate_time_generic(uuid_t out) {
447#ifdef HAVE_TLS
448	THREAD_LOCAL int		num = 0;
449	THREAD_LOCAL struct uuid	uu;
450	THREAD_LOCAL time_t		last_time = 0;
451	time_t				now;
452
453	if (num > 0) {
454		now = time(NULL);
455		if (now > last_time+1)
456			num = 0;
457	}
458	if (num <= 0) {
459		num = 1000;
460		if (get_uuid_via_daemon(UUIDD_OP_BULK_TIME_UUID,
461					out, &num) == 0) {
462			last_time = time(NULL);
463			uuid_unpack(out, &uu);
464			num--;
465			return 0;
466		}
467		num = 0;
468	}
469	if (num > 0) {
470		uu.time_low++;
471		if (uu.time_low == 0) {
472			uu.time_mid++;
473			if (uu.time_mid == 0)
474				uu.time_hi_and_version++;
475		}
476		num--;
477		uuid_pack(&uu, out);
478		return 0;
479	}
480#else
481	if (get_uuid_via_daemon(UUIDD_OP_TIME_UUID, out, 0) == 0)
482		return 0;
483#endif
484
485	return __uuid_generate_time(out, NULL);
486}
487
488/*
489 * Generate time-based UUID and store it to @out.
490 *
491 * Discards return value from uuid_generate_time_generic()
492 */
493void uuid_generate_time(uuid_t out)
494{
495	(void)uuid_generate_time_generic(out);
496}
497
498
499int uuid_generate_time_safe(uuid_t out)
500{
501	return uuid_generate_time_generic(out);
502}
503
504
505void __uuid_generate_random(uuid_t out, int *num)
506{
507	uuid_t	buf;
508	struct uuid uu;
509	int i, n;
510
511	if (!num || !*num)
512		n = 1;
513	else
514		n = *num;
515
516	for (i = 0; i < n; i++) {
517		random_get_bytes(buf, sizeof(buf));
518		uuid_unpack(buf, &uu);
519
520		uu.clock_seq = (uu.clock_seq & 0x3FFF) | 0x8000;
521		uu.time_hi_and_version = (uu.time_hi_and_version & 0x0FFF)
522			| 0x4000;
523		uuid_pack(&uu, out);
524		out += sizeof(uuid_t);
525	}
526}
527
528void uuid_generate_random(uuid_t out)
529{
530	int	num = 1;
531	/* No real reason to use the daemon for random uuid's -- yet */
532
533	__uuid_generate_random(out, &num);
534}
535
536/*
537 * Check whether good random source (/dev/random or /dev/urandom)
538 * is available.
539 */
540static int have_random_source(void)
541{
542	return (access("/dev/random", R_OK) == 0 ||
543		access("/dev/urandom", R_OK) == 0);
544}
545
546
547/*
548 * This is the generic front-end to uuid_generate_random and
549 * uuid_generate_time.  It uses uuid_generate_random only if
550 * /dev/urandom is available, since otherwise we won't have
551 * high-quality randomness.
552 */
553void uuid_generate(uuid_t out)
554{
555	if (have_random_source())
556		uuid_generate_random(out);
557	else
558		uuid_generate_time(out);
559}
560
561/*
562 * Generate an MD5 hashed (predictable) UUID based on a well-known UUID
563 * providing the namespace and an arbitrary binary string.
564 */
565void uuid_generate_md5(uuid_t out, const uuid_t ns, const char *name, size_t len)
566{
567	UL_MD5_CTX ctx;
568	char hash[UL_MD5LENGTH];
569
570	ul_MD5Init(&ctx);
571	/* hash concatenation of well-known UUID with name */
572	ul_MD5Update(&ctx, ns, sizeof(uuid_t));
573	ul_MD5Update(&ctx, (const unsigned char *)name, len);
574
575	ul_MD5Final((unsigned char *)hash, &ctx);
576
577	memcpy(out, hash, sizeof(uuid_t));
578
579	out[6] &= ~(UUID_TYPE_MASK << UUID_TYPE_SHIFT);
580	out[6] |= (UUID_TYPE_DCE_MD5 << UUID_TYPE_SHIFT);
581
582	out[8] &= ~(UUID_VARIANT_MASK << UUID_VARIANT_SHIFT);
583	out[8] |= (variant_bits[UUID_VARIANT_DCE] << UUID_VARIANT_SHIFT);
584}
585
586/*
587 * Generate a SHA1 hashed (predictable) UUID based on a well-known UUID
588 * providing the namespace and an arbitrary binary string.
589 */
590void uuid_generate_sha1(uuid_t out, const uuid_t ns, const char *name, size_t len)
591{
592	UL_SHA1_CTX ctx;
593	char hash[UL_SHA1LENGTH];
594
595	ul_SHA1Init(&ctx);
596	/* hash concatenation of well-known UUID with name */
597	ul_SHA1Update(&ctx, ns, sizeof(uuid_t));
598	ul_SHA1Update(&ctx, (const unsigned char *)name, len);
599
600	ul_SHA1Final((unsigned char *)hash, &ctx);
601
602	memcpy(out, hash, sizeof(uuid_t));
603
604	out[6] &= ~(UUID_TYPE_MASK << UUID_TYPE_SHIFT);
605	out[6] |= (UUID_TYPE_DCE_SHA1 << UUID_TYPE_SHIFT);
606
607	out[8] &= ~(UUID_VARIANT_MASK << UUID_VARIANT_SHIFT);
608	out[8] |= (variant_bits[UUID_VARIANT_DCE] << UUID_VARIANT_SHIFT);
609}
610
611