[PATCH 0/2] Time-based RFC 4122 UUID generator

[PATCH 0/2] Time-based RFC 4122 UUID generator

[Helge Deller]

Andrew,

this is a series of two patches for the kernels UUID generator which was already posted two weeks ago to LKML for discussion: 
http://lkml.org/lkml/2007/10/6/37

1) The first patch fixes a real (although not too critical) bug in the current UUID random generator. It would be great if this could go to Linus soon.

2) The second patch implements a time-based UUID generator acording to RFC 4122. It would be great if you could apply this patch to your mm tree for broader testing.

I did tested the patches sucessfully on x86-32 and hppa (big-endian).

Helge

[PATCH 1/2] UUID: set multicast bit in pseudo-random MAC address

[Helge Deller]

Fix a bug in the current random UUID generator:

Section 4.1.6 of RFC 4122 states regarding the "NodeID" of a UUID:
:  For systems with no IEEE address, a randomly or pseudo-randomly
:  generated value may be used; see Section 4.5.  The multicast bit must
:  be set in such addresses, in order that they will never conflict with
:  addresses obtained from network cards. 

So up to now it was just pure ("random") luck if this bit was set or not.
This tiny patch sets the bit explicitely.

Signed-off-by: Helge Deller <deller@gmx.de>
CC:  Valdis.Kletnieks@vt.edu

 random.c |    2 ++
 1 file changed, 2 insertions(+)

--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -1157,6 +1158,8 @@ void generate_random_uuid(unsigned char uuid_out[16])
 	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x40;
 	/* Set the UUID variant to DCE */
 	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+	/* Set multicast bit to avoid conflicts with NIC MAC addresses */
+	uuid_out[10] |= 0x80;
 }
 
 EXPORT_SYMBOL(generate_random_uuid);

Re: [PATCH 1/2] UUID: set multicast bit in pseudo-random MAC address

[Theodore Tso]

On Sat, Oct 20, 2007 at 09:58:40PM +0200, Helge Deller wrote:
> Fix a bug in the current random UUID generator:
> 
> Section 4.1.6 of RFC 4122 states regarding the "NodeID" of a UUID:
> :  For systems with no IEEE address, a randomly or pseudo-randomly
> :  generated value may be used; see Section 4.5.  The multicast bit must
> :  be set in such addresses, in order that they will never conflict with
> :  addresses obtained from network cards. 
> 
> So up to now it was just pure ("random") luck if this bit was set or not.
> This tiny patch sets the bit explicitely.

NACK.  Your patch degrades the random UUID by a bit, for no good reason.

The part of Section 4.1.6 which you quoted only applies to version 1
UUID's --- i.e., MAC and time based UUID's.  Random uuids are version
4 UUID's, and are already distinguished from version 1 UUID's by the
high 4 bits of the time_hi_and_version field, in octets 6-7 of the
URL.  Hence, there is no danger of conflict.  If you had looked 3
paragraphs later section 4.1.6:

   For UUID version 4, the node field is a randomly or pseudo-randomly
   generated 48-bit value as described in Section 4.4.

And the summary can be found in Section 4.4 of RFRC 4122:

4.4.  Algorithms for Creating a UUID from Truly Random or
      Pseudo-Random Numbers

   The version 4 UUID is meant for generating UUIDs from truly-random or
   pseudo-random numbers.

   The algorithm is as follows:

   o  Set the two most significant bits (bits 6 and 7) of the
      clock_seq_hi_and_reserved to zero and one, respectively.

   o  Set the four most significant bits (bits 12 through 15) of the
      time_hi_and_version field to the 4-bit version number from
      Section 4.1.3.

   o  Set all the other bits to randomly (or pseudo-randomly) chosen
      values.

   See Section 4.5 for a discussion on random numbers.

   	     	    	     	       	  	  - Ted

Re: [PATCH 1/2] UUID: set multicast bit in pseudo-random MAC address

[Helge Deller]

On Sunday 21 October 2007, Theodore Tso wrote:
> On Sat, Oct 20, 2007 at 09:58:40PM +0200, Helge Deller wrote:
> > Fix a bug in the current random UUID generator:
> > 
> > Section 4.1.6 of RFC 4122 states regarding the "NodeID" of a UUID:
> > :  For systems with no IEEE address, a randomly or pseudo-randomly
> > :  generated value may be used; see Section 4.5.  The multicast bit must
> > :  be set in such addresses, in order that they will never conflict with
> > :  addresses obtained from network cards. 
> > 
> > So up to now it was just pure ("random") luck if this bit was set or not.
> > This tiny patch sets the bit explicitely.
> 
> NACK.  Your patch degrades the random UUID by a bit, for no good reason.
> 
> The part of Section 4.1.6 which you quoted only applies to version 1
> UUID's --- i.e., MAC and time based UUID's.  Random uuids are version
> 4 UUID's, and are already distinguished from version 1 UUID's by the
> high 4 bits of the time_hi_and_version field, in octets 6-7 of the
> URL.  Hence, there is no danger of conflict.  If you had looked 3
> paragraphs later section 4.1.6:
> 
>    For UUID version 4, the node field is a randomly or pseudo-randomly
>    generated 48-bit value as described in Section 4.4.
> 
> And the summary can be found in Section 4.4 of RFRC 4122:
> 
> 4.4.  Algorithms for Creating a UUID from Truly Random or
>       Pseudo-Random Numbers
> 
>    The version 4 UUID is meant for generating UUIDs from truly-random or
>    pseudo-random numbers.
> 
>    The algorithm is as follows:
> 
>    o  Set the two most significant bits (bits 6 and 7) of the
>       clock_seq_hi_and_reserved to zero and one, respectively.
> 
>    o  Set the four most significant bits (bits 12 through 15) of the
>       time_hi_and_version field to the 4-bit version number from
>       Section 4.1.3.
> 
>    o  Set all the other bits to randomly (or pseudo-randomly) chosen
>       values.
> 
>    See Section 4.5 for a discussion on random numbers.

Hi Ted,

Thanks for looking into it and pointing to the important RFC pieces. 
Of course you are right and I mixed that up.

Herewith I withdraw this patch.

Helge

[PATCH 2/2] UUID: Time-based RFC 4122 UUID generator

[Helge Deller]

The current Linux kernel currently contains the generate_random_uuid() 
function, which creates - based on RFC 4122 - truly random UUIDs and 
provides them to userspace through /proc/sys/kernel/random/boot_id
and /proc/sys/kernel/random/uuid.

The attached patch additionally adds the "Time-based UUID" variant 
of RFC 4122 to the Linux Kernel.
With this patch applied, userspace applications may easily get real unique
time-based UUIDs through /proc/sys/kernel/random/uuid_time.

The attached implementation uses getnstimeofday() to get more fine-grained
granularity than what would be possible with gettimeofday() in userspace.
As such it's in principle possible to provide a lot more UUIDs (if needed) per
time than in userspace.
Additionally a mutex takes care of the proper locking against a mistaken
double creation of UUIDs for simultanious running processes.

Signed-off-by: Helge Deller <deller@gmx.de>
CC:  Valdis.Kletnieks@vt.edu

 drivers/char/random.c  |  160 +++++++++++++++++++++++++++++++++++++++++++------
 include/linux/sysctl.h |    5 -
 2 files changed, 145 insertions(+), 20 deletions(-)


diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1756b1f..3d6b6e0 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -239,6 +239,7 @@
 #include <linux/spinlock.h>
 #include <linux/percpu.h>
 #include <linux/cryptohash.h>
+#include <linux/if_arp.h>
 
 #include <asm/processor.h>
 #include <asm/uaccess.h>
@@ -1174,12 +1177,134 @@ EXPORT_SYMBOL(generate_random_uuid);
 static int min_read_thresh = 8, min_write_thresh;
 static int max_read_thresh = INPUT_POOL_WORDS * 32;
 static int max_write_thresh = INPUT_POOL_WORDS * 32;
-static char sysctl_bootid[16];
+static unsigned char sysctl_bootid[16] __read_mostly;
 
 /*
- * These functions is used to return both the bootid UUID, and random
- * UUID.  The difference is in whether table->data is NULL; if it is,
- * then a new UUID is generated and returned to the user.
+ * Generate time based UUID (RFC 4122)
+ *
+ * This function is protected with a mutex to ensure system-wide
+ * uniqiness of the new time based UUID.
+ */
+static void generate_random_uuid_time(unsigned char uuid_out[16])
+{
+	static DEFINE_MUTEX(uuid_mutex);
+	static u64 last_time_all;
+	static u16 clock_seq, clock_seq_started;
+	static unsigned char last_mac[ETH_ALEN];
+	static int clock_seq_initialized __read_mostly;
+
+	struct timespec ts;
+	u64 time_all;
+	struct net_device *d;
+	int netdev_found = 0;
+
+	mutex_lock(&uuid_mutex);
+
+	/* Determine 60-bit timestamp value. For UUID version 1, this is
+	 * represented by Coordinated Universal Time (UTC) as a count of 100-
+	 * nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of
+	 * Gregorian reform to the Christian calendar).
+	 */
+try_again:
+	getnstimeofday(&ts);
+	time_all = ((u64) ts.tv_sec) * (NSEC_PER_SEC/100);
+	time_all += ts.tv_nsec / 100;
+
+	/* add offset from Gregorian Calendar to Jan 1 1970 */
+	time_all += 12219292800000ULL * (NSEC_PER_MSEC/100);
+	time_all &= 0x0fffffffffffffffULL; /* limit to 60 bits */
+	uuid_out[3] = (u8) time_all;
+	uuid_out[2] = (u8) (time_all >> 8);
+	uuid_out[1] = (u8) (time_all >> 16);
+	uuid_out[0] = (u8) (time_all >> 24);
+	uuid_out[5] = (u8) (time_all >> 32);
+	uuid_out[4] = (u8) (time_all >> 40);
+	uuid_out[7] = (u8) (time_all >> 48);
+	uuid_out[6] = (u8) (time_all >> 56);
+
+	/* Determine clock sequence (max. 14 bit) */
+	if (unlikely(!clock_seq_initialized)) {
+		get_random_bytes(&clock_seq, sizeof(clock_seq));
+		clock_seq &= 0x3fff;
+		clock_seq_started = clock_seq;
+		clock_seq_initialized = 1;
+	} else {
+		if (unlikely(time_all <= last_time_all)) {
+inc_clock_seq:		clock_seq = (clock_seq+1) & 0x3fff;
+			if (unlikely(clock_seq == clock_seq_started)) {
+				clock_seq = (clock_seq-1) & 0x3fff;
+				goto try_again; /* wait until time advanced */
+			}
+		} else
+			clock_seq_started = clock_seq;
+	}
+	last_time_all = time_all;
+
+	uuid_out[8] = clock_seq >> 8;
+	uuid_out[9] = clock_seq & 0xff;
+
+	/* Set the spatially unique node identifier */
+#ifdef CONFIG_NET
+	read_lock(&dev_base_lock);
+	for_each_netdev(&init_net, d) {
+		if (d->type == ARPHRD_ETHER && d->addr_len == ETH_ALEN 
+		    && d != init_net.loopback_dev) {
+			memcpy(&uuid_out[10], d->dev_addr, ETH_ALEN);
+			netdev_found = 1;
+			break;
+		}
+	}
+	read_unlock(&dev_base_lock);
+#endif
+	if (unlikely(!netdev_found)) {
+		/* use bootid's nodeID if no network interface found */
+		if (sysctl_bootid[8] == 0)
+			generate_random_uuid(sysctl_bootid);
+		memcpy(&uuid_out[10], &sysctl_bootid[10], ETH_ALEN);
+	}
+	/* if MAC/NodeID changed, create a new clock_seq value */
+	if (unlikely(memcmp(&uuid_out[10], &last_mac, ETH_ALEN))) {
+		memcpy(&last_mac, &uuid_out[10], ETH_ALEN);
+		/* for very first UUID, do not increment clock_seq */
+		if (unlikely(clock_seq_initialized == 1))
+			clock_seq_initialized = 2;
+		else
+			goto inc_clock_seq;
+	}
+
+	/* Set UUID version to 1 --- time-based generation */
+	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x10;
+	/* Set the UUID variant to DCE */
+	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+
+	mutex_unlock(&uuid_mutex);
+}
+
+
+/*
+ * Get UUID based on requested type.
+ */
+static unsigned char *get_uuid(void *extra1, unsigned char *uuid)
+{
+	switch ((int) extra1) {
+	case RANDOM_BOOT_ID:
+		uuid = sysctl_bootid;
+		if (unlikely(uuid[8] == 0))
+			generate_random_uuid(uuid);
+		break;
+	case RANDOM_UUID:
+		generate_random_uuid(uuid);
+		break;
+	case RANDOM_UUID_TIME:
+		generate_random_uuid_time(uuid);
+		break;
+	}
+	return uuid;
+}
+
+/*
+ * These functions are used to return the bootid UUID, random UUID and
+ * time based UUID.
  *
  * If the user accesses this via the proc interface, it will be returned
  * as an ASCII string in the standard UUID format.  If accesses via the
@@ -1191,13 +1316,13 @@ static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
 	ctl_table fake_table;
 	unsigned char buf[64], tmp_uuid[16], *uuid;
 
-	uuid = table->data;
-	if (!uuid) {
-		uuid = tmp_uuid;
-		uuid[8] = 0;
+	/* random/time UUIDs need to be read completely at once */
+	if ((int)table->extra1 != RANDOM_BOOT_ID && *ppos > 0) {
+		*lenp = 0;
+		return 0;
 	}
-	if (uuid[8] == 0)
-		generate_random_uuid(uuid);
+
+	uuid = get_uuid(table->extra1, tmp_uuid);
 
 	sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
 		"%02x%02x%02x%02x%02x%02x",
@@ -1221,13 +1346,7 @@ static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
 	if (!oldval || !oldlenp)
 		return 1;
 
-	uuid = table->data;
-	if (!uuid) {
-		uuid = tmp_uuid;
-		uuid[8] = 0;
-	}
-	if (uuid[8] == 0)
-		generate_random_uuid(uuid);
+	uuid = get_uuid(table->extra1, tmp_uuid);
 
 	if (get_user(len, oldlenp))
 		return -EFAULT;
@@ -1284,11 +1403,11 @@ ctl_table random_table[] = {
 	{
 		.ctl_name	= RANDOM_BOOT_ID,
 		.procname	= "boot_id",
-		.data		= &sysctl_bootid,
 		.maxlen		= 16,
 		.mode		= 0444,
 		.proc_handler	= &proc_do_uuid,
 		.strategy	= &uuid_strategy,
+		.extra1		= (void *) RANDOM_BOOT_ID,
 	},
 	{
 		.ctl_name	= RANDOM_UUID,
@@ -1297,6 +1416,13 @@ ctl_table random_table[] = {
 		.mode		= 0444,
 		.proc_handler	= &proc_do_uuid,
 		.strategy	= &uuid_strategy,
+		.extra1		= (void *) RANDOM_UUID,
+	},
+	{
+		.procname	= "uuid_time",
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.extra1		= (void *) RANDOM_UUID_TIME,
 	},
 	{ .ctl_name = 0 }
 };
diff --git a/include/linux/sysctl.h b/include/linux/sysctl.h
index e99171f..dd09d97 100644
--- a/include/linux/sysctl.h
+++ b/include/linux/sysctl.h
@@ -248,8 +248,9 @@ enum
 	RANDOM_ENTROPY_COUNT=2,
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
-	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_BOOT_ID=5,	/* rfc4122 version 4, boot UUID */
+	RANDOM_UUID=6,		/* rfc4122 version 4, random-based */
+	RANDOM_UUID_TIME=7	/* rfc4122 version 1, time-based */
 };
 
 /* /proc/sys/kernel/pty */

Re: [PATCH 2/2] UUID: Time-based RFC 4122 UUID generator

[Theodore Tso]

On Sat, Oct 20, 2007 at 10:00:03PM +0200, Helge Deller wrote:
> The attached patch additionally adds the "Time-based UUID" variant 
> of RFC 4122 to the Linux Kernel.
> With this patch applied, userspace applications may easily get real unique
> time-based UUIDs through /proc/sys/kernel/random/uuid_time.

> The attached implementation uses getnstimeofday() to get more fine-grained
> granularity than what would be possible with gettimeofday() in userspace.

I'm not convinced this is really needed, given that we have a UUID
generation library; we can just as easily use clock_gettime() to get
nanosecond granularity in userspace.  The reason why I didn't add this
in libuuid a decade ago was that we didn't have anything that was near
even microsecond resolution back then.  But this is a problem we can
fix in userspace.

> Additionally a mutex takes care of the proper locking against a mistaken
> double creation of UUIDs for simultanious running processes.

This is trickier to do in userspace, given that in userspace we have
to worry about malicious code that might grab and hold the mutex for
long periods of time.  It is soluble, though.

> +	/* Determine clock sequence (max. 14 bit) */
> +	if (unlikely(!clock_seq_initialized)) {
> +		get_random_bytes(&clock_seq, sizeof(clock_seq));
> +		clock_seq &= 0x3fff;
> +		clock_seq_started = clock_seq;
> +		clock_seq_initialized = 1;

If you're really going to do this right, it should be possible to get
and set the clock sequence from userspace, since the clock sequence is
supposed to be retained across system bootups.  Otherwise, it's
possible for you to get really unlucky, and pick the same clock
sequence number just at the same point that the clock gets changed.
Not all that likely, granted, but technically it's good thing to do
and required by RFC 4122.

I don't do this in the userspace library, but again that's because of
the security issue of dealiing with multiple userids needing to update
a file.  (What we really need to do this right in userspace is the
concept of lightweight privileged shared libraries, such as what
Multics had.)  So if that's going to be the justification to do this
in the kernel, it should be possible to set/get the clock sequence
number, so that in an init.d script, the clock sequence numer can be
fetched at bootup and stored at shutdown.  (Yeah, that still leaves
open the possibility of how to handle an unclean shutdown.  If you
really wanted to be anal about guaranteeing that a clock sequence
number was never reused, any time a clock sequence number is changed,
a hal event could be sent that would cause a userspace helper script
to sample the clock sequence and update the file.)

> +	/* Set the spatially unique node identifier */
> +#ifdef CONFIG_NET
> +	read_lock(&dev_base_lock);
> +	for_each_netdev(&init_net, d) {
> +		if (d->type == ARPHRD_ETHER && d->addr_len == ETH_ALEN 
> +		    && d != init_net.loopback_dev) {
> +			memcpy(&uuid_out[10], d->dev_addr, ETH_ALEN);
> +			netdev_found = 1;
> +			break;
> +		}
> +	}
> +	read_unlock(&dev_base_lock);
> +#endif

This means you have to grab the dev_base_lock each time you generate a
UUID.  In addition, since this code always grabs the first ethernet
device in the list, if the list has changed --- for example, if
someone inserts a PCMCIA wireless or ethernet card, or removes the
card for power management reasons --- you could end up changing the
MAC address and forcing a clock sequence bump even though it's not
necessary.  So there are a couple of things that we might do here.

First of all, if we *know* that that a particular mac address is
associated with a card which is hardwired to the machine, we're
actually better off using it even if it is no longer present in the
list.  But aside from getting a userspace hint, I don't see a good way
for us to implement this.

What you probably should do, since you're keeping the MAC address
around to compare if it changes, is to search the list to see if the
MAC address is still on the list, and use it if it's there; and if it
isn't, then you can use the first ethernet address found instead.

> +	if (unlikely(!netdev_found)) {
> +		/* use bootid's nodeID if no network interface found */

If CONFIG_NET is undefined, the netdev_found will always be false, so
the unlikely() would be particularly inappropriate.  Probably will
only matter for embedded systems, but they won't thank you....

> +	/* if MAC/NodeID changed, create a new clock_seq value */
> +	if (unlikely(memcmp(&uuid_out[10], &last_mac, ETH_ALEN))) {
> +		memcpy(&last_mac, &uuid_out[10], ETH_ALEN);
> +		/* for very first UUID, do not increment clock_seq */
> +		if (unlikely(clock_seq_initialized == 1))
> +			clock_seq_initialized = 2;
> +		else
> +			goto inc_clock_seq;
> +	}

The goto loop could be much simplified if you grab the MAC/NodeID
*before* you do clock_seq logic.  Right now, if the Mac/NodeID
changes, you end up having to redo a lot of processing for no good
reason (and under the uuid_mutex).

						- Ted

Re: [PATCH 2/2] UUID: Time-based RFC 4122 UUID generator

[Helge Deller]

On Sunday 21 October 2007, Theodore Tso wrote:
> On Sat, Oct 20, 2007 at 10:00:03PM +0200, Helge Deller wrote:
> > Additionally a mutex takes care of the proper locking against a mistaken
> > double creation of UUIDs for simultanious running processes.
> 
> This is trickier to do in userspace, given that in userspace we have
> to worry about malicious code that might grab and hold the mutex for
> long periods of time.  It is soluble, though.

Yes, userspace would need quite some overhead/syncronization/locking tricks to get it right.
That's basically one of the reasons I prefer the in-kernel solution.
The other reason is, that due to reduced code size compared to user-space, it's even a nice and clean solution for embedded devices.

> > +	/* Determine clock sequence (max. 14 bit) */
> > +	if (unlikely(!clock_seq_initialized)) {
> > +		get_random_bytes(&clock_seq, sizeof(clock_seq));
> > +		clock_seq &= 0x3fff;
> > +		clock_seq_started = clock_seq;
> > +		clock_seq_initialized = 1;
> 
> If you're really going to do this right, it should be possible to get
> and set the clock sequence from userspace, since the clock sequence is
> supposed to be retained across system bootups.  Otherwise, it's
> possible for you to get really unlucky, and pick the same clock
> sequence number just at the same point that the clock gets changed.
> Not all that likely, granted, but technically it's good thing to do
> and required by RFC 4122.

Ok, I'll add that to the next version of the patch.
Do you have a suggestion how to realize that ?
I currently see two possibilities:
a) reading: userspace reads /proc/sys/kernel/random/uuid_time and parses/stores the clock sequence number.
    writing: just echo a value to /proc/sys/kernel/random/uuid_time, kernel will use this value then as new clock sequence number.
b) add a new sysfs entry, e.g. /proc/sys/kernel/random/uuid_time_clockseq, to read/write the current/new value

Possibility b) is probably the cleaner solution, although it adds some more code.
What's your opinion ?

> I don't do this in the userspace library, but again that's because of
> the security issue of dealiing with multiple userids needing to update
> a file.  (What we really need to do this right in userspace is the
> concept of lightweight privileged shared libraries, such as what
> Multics had.)  So if that's going to be the justification to do this
> in the kernel, it should be possible to set/get the clock sequence
> number, so that in an init.d script, the clock sequence numer can be
> fetched at bootup and stored at shutdown.  (Yeah, that still leaves
> open the possibility of how to handle an unclean shutdown.  If you
> really wanted to be anal about guaranteeing that a clock sequence
> number was never reused, any time a clock sequence number is changed,
> a hal event could be sent that would cause a userspace helper script
> to sample the clock sequence and update the file.)

Yuk. If you really want, I'll add that hal event...

> > +	/* Set the spatially unique node identifier */
> > +#ifdef CONFIG_NET
> > +	read_lock(&dev_base_lock);
> > +	for_each_netdev(&init_net, d) {
> > +		if (d->type == ARPHRD_ETHER && d->addr_len == ETH_ALEN 
> > +		    && d != init_net.loopback_dev) {
> > +			memcpy(&uuid_out[10], d->dev_addr, ETH_ALEN);
> > +			netdev_found = 1;
> > +			break;
> > +		}
> > +	}
> > +	read_unlock(&dev_base_lock);
> > +#endif
> 
> This means you have to grab the dev_base_lock each time you generate a
> UUID.  

Yes, IMHO this seems unavoidable. 
Basically even the user-space implementation gets the lock. It's just indirect and less efficient.

> In addition, since this code always grabs the first ethernet 
> device in the list, if the list has changed --- for example, if
> someone inserts a PCMCIA wireless or ethernet card, or removes the
> card for power management reasons --- you could end up changing the
> MAC address and forcing a clock sequence bump even though it's not
> necessary.  So there are a couple of things that we might do here.

Agreed.

> First of all, if we *know* that that a particular mac address is
> associated with a card which is hardwired to the machine, we're
> actually better off using it even if it is no longer present in the
> list.  But aside from getting a userspace hint, I don't see a good way
> for us to implement this.

Me neither.

> What you probably should do, since you're keeping the MAC address
> around to compare if it changes, is to search the list to see if the
> MAC address is still on the list, and use it if it's there; and if it
> isn't, then you can use the first ethernet address found instead.

Yes, I'll do that in the next version of the patch.

> > +	if (unlikely(!netdev_found)) {
> > +		/* use bootid's nodeID if no network interface found */
> 
> If CONFIG_NET is undefined, the netdev_found will always be false, so
> the unlikely() would be particularly inappropriate.  Probably will
> only matter for embedded systems, but they won't thank you....

When I wrote that, I thought the same and my first idea was just to move the if clause before the #endif, e.g. like this:
	if (unlikely(!netdev_found))
	#endif /* CONFIG_NET */
	{ ....
But I didn't like that code folding very much.

On the other side, if CONFIG_NET is undefined, netdev_found still stays at "0", and the compiler should
convert that directly to 
	if (unlikely(!0)) {
	/* use bootid's nodeID if no network interface found */
and just drop the if() and thus the unlikely() statement.
So I think the compiler will just optimize it away and ignore the unlikely (because as it knows, it's not unlikely any more).

> > +	/* if MAC/NodeID changed, create a new clock_seq value */
> > +	if (unlikely(memcmp(&uuid_out[10], &last_mac, ETH_ALEN))) {
> > +		memcpy(&last_mac, &uuid_out[10], ETH_ALEN);
> > +		/* for very first UUID, do not increment clock_seq */
> > +		if (unlikely(clock_seq_initialized == 1))
> > +			clock_seq_initialized = 2;
> > +		else
> > +			goto inc_clock_seq;
> > +	}
> 
> The goto loop could be much simplified if you grab the MAC/NodeID
> *before* you do clock_seq logic.  Right now, if the Mac/NodeID
> changes, you end up having to redo a lot of processing for no good
> reason (and under the uuid_mutex).

I'm not sure if this gains much. Probably the jumps will just be at some other place or the code will become more complex.
MAC/NodeID changes quite seldom. And if it changes, the machine will be quite busy anyway, e.g. configure IP addresses/DHCP, ...
But anyway, I'll give it a try for the next patch.

Thanks,
Helge

Re: [PATCH 2/2] UUID: Time-based RFC 4122 UUID generator

[Helge Deller]

Hi Ted,

Below is the new version of a time-based UUID generator, in which I addressed your feedback.

New features in this patch include
- a new "/proc/sys/kernel/random/uuid_time_clockseq" sysfs entry to read/write the clock_seq value (to be able to be retained across system bootups)
- keep searching for last-used MAC address (use same MAC as long as the NIC is still in the machine)
- moved up the clock_seq calculation in order to simplify the logic and runtime

I kept the unlikely() in the !CONFIG_NET case and did not implemented a HAL callback.

Helge

Signed-off-by: Helge Deller <deller@gmx.de>

 drivers/char/random.c  |  206 ++++++++++++++++++++++++++++++++++++++++++++-----
 include/linux/sysctl.h |    5 -
 2 files changed, 191 insertions(+), 20 deletions(-)

diff --git a/drivers/char/random.c b/drivers/char/random.c
index 1756b1f..56efebc 100644
--- a/drivers/char/random.c
+++ b/drivers/char/random.c
@@ -6,6 +6,9 @@
  * Copyright Theodore Ts'o, 1994, 1995, 1996, 1997, 1998, 1999.  All
  * rights reserved.
  *
+ * Time based UUID (RFC 4122) generator:
+ * Copyright Helge Deller <deller@gmx.de>, 2007
+ *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
@@ -239,6 +242,7 @@
 #include <linux/spinlock.h>
 #include <linux/percpu.h>
 #include <linux/cryptohash.h>
+#include <linux/if_arp.h>
 
 #include <asm/processor.h>
 #include <asm/uaccess.h>
@@ -1174,12 +1178,170 @@ EXPORT_SYMBOL(generate_random_uuid);
 static int min_read_thresh = 8, min_write_thresh;
 static int max_read_thresh = INPUT_POOL_WORDS * 32;
 static int max_write_thresh = INPUT_POOL_WORDS * 32;
-static char sysctl_bootid[16];
+static unsigned char sysctl_bootid[16] __read_mostly;
+
+/*
+ * Helper functions and variables for time based UUID generator
+ */
+static unsigned int clock_seq;
+static const unsigned int clock_seq_max = 0x3fff; /* 14 bits */
+static int clock_seq_initialized __read_mostly;
+
+static void init_clockseq(void)
+{
+	get_random_bytes(&clock_seq, sizeof(clock_seq));
+	clock_seq &= clock_seq_max;
+	clock_seq_initialized = 1;
+}
+
+static int proc_dointvec_clockseq(struct ctl_table *table, int write,
+		struct file *filp, void __user *buffer,
+		size_t *lenp, loff_t *ppos)
+{
+	int ret;
+
+	if (!write && !clock_seq_initialized)
+		init_clockseq();
+
+	ret = proc_dointvec(table, write, filp, buffer, lenp, ppos);
+
+	if (write && ret >= 0) {
+		clock_seq_initialized = 1;
+		clock_seq &= clock_seq_max;
+	}
+
+	return ret;
+}
+
+/*
+ * Generate time based UUID (RFC 4122)
+ *
+ * This function is protected with a mutex to ensure system-wide
+ * uniqiness of the new time based UUID.
+ */
+static void generate_random_uuid_time(unsigned char uuid_out[16])
+{
+	static DEFINE_MUTEX(uuid_mutex);
+	static u64 last_time_all;
+	static unsigned int clock_seq_started;
+	static unsigned char last_mac[ETH_ALEN];
+
+	struct timespec ts;
+	u64 time_all;
+	unsigned char *found_mac = NULL;
+	struct net_device *d __maybe_unused;
+	int inc_clock_seq = 0;
+
+	mutex_lock(&uuid_mutex);
+
+	/* Get the spatially unique node identifier */
+#ifdef CONFIG_NET
+	read_lock(&dev_base_lock);
+	for_each_netdev(&init_net, d) {
+		if (d->type == ARPHRD_ETHER && d->addr_len == ETH_ALEN 
+		    && d != init_net.loopback_dev) {
+			if (!memcmp(&last_mac, d->dev_addr, ETH_ALEN)) {
+				found_mac = last_mac;
+				break;
+			}
+			if (!found_mac)
+				found_mac = d->dev_addr;
+		}
+	}
+	if (found_mac)
+		memcpy(&uuid_out[10], found_mac, ETH_ALEN);
+	read_unlock(&dev_base_lock);
+#endif
+	if (unlikely(!found_mac))
+	{
+		/* use bootid's nodeID if no network interface found */
+		if (sysctl_bootid[8] == 0)
+			generate_random_uuid(sysctl_bootid);
+		memcpy(&uuid_out[10], &sysctl_bootid[10], ETH_ALEN);
+	}
+	/* if MAC/NodeID changed, create a new clock_seq value */
+	if (unlikely(found_mac != last_mac &&
+		     memcmp(&last_mac, &uuid_out[10], ETH_ALEN))) {
+			memcpy(&last_mac, &uuid_out[10], ETH_ALEN);
+			inc_clock_seq = 1;
+	}
+
+	/* Determine 60-bit timestamp value. For UUID version 1, this is
+	 * represented by Coordinated Universal Time (UTC) as a count of 100-
+	 * nanosecond intervals since 00:00:00.00, 15 October 1582 (the date of
+	 * Gregorian reform to the Christian calendar).
+	 */
+advance_time:
+	getnstimeofday(&ts);
+	time_all = ((u64) ts.tv_sec) * (NSEC_PER_SEC/100);
+	time_all += ts.tv_nsec / 100;
+
+	/* add offset from Gregorian Calendar to Jan 1 1970 */
+	time_all += 12219292800000ULL * (NSEC_PER_MSEC/100);
+	time_all &= 0x0fffffffffffffffULL; /* limit to 60 bits */
+
+	/* Determine clock sequence (max. 14 bit) */
+	if (unlikely(!clock_seq_initialized)) {
+		init_clockseq();
+		clock_seq_started = clock_seq;
+	} else {
+		if (unlikely(inc_clock_seq || time_all <= last_time_all)) {
+			clock_seq = (clock_seq+1) & clock_seq_max;
+			if (unlikely(clock_seq == clock_seq_started)) {
+				clock_seq = (clock_seq-1) & clock_seq_max;
+				goto advance_time;
+			}
+		} else
+			clock_seq_started = clock_seq;
+	}
+	last_time_all = time_all;
+
+	/* Fill in timestamp and clock_seq values */
+	uuid_out[3] = (u8) time_all;
+	uuid_out[2] = (u8) (time_all >> 8);
+	uuid_out[1] = (u8) (time_all >> 16);
+	uuid_out[0] = (u8) (time_all >> 24);
+	uuid_out[5] = (u8) (time_all >> 32);
+	uuid_out[4] = (u8) (time_all >> 40);
+	uuid_out[7] = (u8) (time_all >> 48);
+	uuid_out[6] = (u8) (time_all >> 56);
+
+	uuid_out[8] = clock_seq >> 8;
+	uuid_out[9] = clock_seq & 0xff;
+
+	/* Set UUID version to 1 --- time-based generation */
+	uuid_out[6] = (uuid_out[6] & 0x0F) | 0x10;
+	/* Set the UUID variant to DCE */
+	uuid_out[8] = (uuid_out[8] & 0x3F) | 0x80;
+
+	mutex_unlock(&uuid_mutex);
+}
+
 
 /*
- * These functions is used to return both the bootid UUID, and random
- * UUID.  The difference is in whether table->data is NULL; if it is,
- * then a new UUID is generated and returned to the user.
+ * Get UUID based on requested type.
+ */
+static unsigned char *get_uuid(void *extra1, unsigned char *uuid)
+{
+	switch ((int) extra1) {
+	case RANDOM_BOOT_ID:
+		uuid = sysctl_bootid;
+		if (unlikely(uuid[8] == 0))
+			generate_random_uuid(uuid);
+		break;
+	case RANDOM_UUID:
+		generate_random_uuid(uuid);
+		break;
+	case RANDOM_UUID_TIME:
+		generate_random_uuid_time(uuid);
+		break;
+	}
+	return uuid;
+}
+
+/*
+ * These functions are used to return the bootid UUID, random UUID and
+ * time based UUID.
  *
  * If the user accesses this via the proc interface, it will be returned
  * as an ASCII string in the standard UUID format.  If accesses via the
@@ -1191,13 +1353,13 @@ static int proc_do_uuid(ctl_table *table, int write, struct file *filp,
 	ctl_table fake_table;
 	unsigned char buf[64], tmp_uuid[16], *uuid;
 
-	uuid = table->data;
-	if (!uuid) {
-		uuid = tmp_uuid;
-		uuid[8] = 0;
+	/* random/time UUIDs need to be read completely at once */
+	if ((int)table->extra1 != RANDOM_BOOT_ID && *ppos > 0) {
+		*lenp = 0;
+		return 0;
 	}
-	if (uuid[8] == 0)
-		generate_random_uuid(uuid);
+
+	uuid = get_uuid(table->extra1, tmp_uuid);
 
 	sprintf(buf, "%02x%02x%02x%02x-%02x%02x-%02x%02x-%02x%02x-"
 		"%02x%02x%02x%02x%02x%02x",
@@ -1221,13 +1383,7 @@ static int uuid_strategy(ctl_table *table, int __user *name, int nlen,
 	if (!oldval || !oldlenp)
 		return 1;
 
-	uuid = table->data;
-	if (!uuid) {
-		uuid = tmp_uuid;
-		uuid[8] = 0;
-	}
-	if (uuid[8] == 0)
-		generate_random_uuid(uuid);
+	uuid = get_uuid(table->extra1, tmp_uuid);
 
 	if (get_user(len, oldlenp))
 		return -EFAULT;
@@ -1284,11 +1440,11 @@ ctl_table random_table[] = {
 	{
 		.ctl_name	= RANDOM_BOOT_ID,
 		.procname	= "boot_id",
-		.data		= &sysctl_bootid,
 		.maxlen		= 16,
 		.mode		= 0444,
 		.proc_handler	= &proc_do_uuid,
 		.strategy	= &uuid_strategy,
+		.extra1		= (void *) RANDOM_BOOT_ID,
 	},
 	{
 		.ctl_name	= RANDOM_UUID,
@@ -1297,6 +1453,20 @@ ctl_table random_table[] = {
 		.mode		= 0444,
 		.proc_handler	= &proc_do_uuid,
 		.strategy	= &uuid_strategy,
+		.extra1		= (void *) RANDOM_UUID,
+	},
+	{
+		.procname	= "uuid_time",
+		.mode		= 0444,
+		.proc_handler	= &proc_do_uuid,
+		.extra1		= (void *) RANDOM_UUID_TIME,
+	},
+	{
+		.procname	= "uuid_time_clockseq",
+		.data		= &clock_seq,
+		.maxlen		= sizeof(unsigned int),
+		.mode		= 0644,
+		.proc_handler	= &proc_dointvec_clockseq,
 	},
 	{ .ctl_name = 0 }
 };
diff --git a/include/linux/sysctl.h b/include/linux/sysctl.h
index e99171f..dd09d97 100644
--- a/include/linux/sysctl.h
+++ b/include/linux/sysctl.h
@@ -248,8 +248,9 @@ enum
 	RANDOM_ENTROPY_COUNT=2,
 	RANDOM_READ_THRESH=3,
 	RANDOM_WRITE_THRESH=4,
-	RANDOM_BOOT_ID=5,
-	RANDOM_UUID=6
+	RANDOM_BOOT_ID=5,	/* rfc4122 version 4, boot UUID */
+	RANDOM_UUID=6,		/* rfc4122 version 4, random-based */
+	RANDOM_UUID_TIME=7	/* rfc4122 version 1, time-based */
 };
 
 /* /proc/sys/kernel/pty */