Time-based RFC 4122 UUID generator
Subsystems (2)
cover Time-based RFC 4122 UUID generator
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
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.
random.c | 2 ++ 1 file changed, 2 insertions(+)
drivers/char/random.c +2 -0
@@ -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);
PATCH 2/2 UUID: Time-based RFC 4122 UUID generator
In reply to Helge DellerThe 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.
drivers/char/random.c | 160 +++++++++++++++++++++++++++++++++++++++++++------ include/linux/sysctl.h | 5 - 2 files changed, 145 insertions(+), 20 deletions(-)
drivers/char/random.c +142 -18
@@ -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 } };
include/linux/sysctl.h +3 -2
@@ -248,8 +248,9 @@ enumRANDOM_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 */
Theodore Tso
maintainerRe: [PATCH 1/2] UUID: set multicast bit in pseudo-random MAC address
In reply to Helge DellerQuoted 10 lines · 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.
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 2/2] UUID: Time-based RFC 4122 UUID generator
In reply to Helge DellerQuoted 7 lines · Helge Deller
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 withgettimeofday()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.
Quoted 2 lines
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.
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1230
Quoted 6 lines
drivers/char/random.c +6
-0+/* 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.)
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1258
Quoted 13 lines
drivers/char/random.c +13
-0+/* 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.
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1260
Quoted 2 lines
drivers/char/random.c +2
-0+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....
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1273
Quoted 9 lines
drivers/char/random.c +9
-0+/* 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 1/2] UUID: set multicast bit in pseudo-random MAC address
In reply to Theodore TsoQuoted 37 lines · Theodore Tso
Quoted 10 lines · 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.
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_versionfield, 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 NumbersThe 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_reservedto zero and one, respectively.
Quoted 8 lines
o Set the four most significant bits (bits 12 through 15) of the
time_hi_and_versionfield 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
Re: [PATCH 2/2] UUID: Time-based RFC 4122 UUID generator
In reply to Theodore TsoQuoted 7 lines · Theodore Tso
Quoted 2 lines · Helge Deller
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.
Quoted 7 lines
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1230
Quoted 6 lines
drivers/char/random.c +6
-0+/* 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 ;
Quoted 7 lines
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 ?
Quoted 5 lines
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
Quoted 8 lines
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...
Quoted 8 lines
Quoted 8 lines
drivers/char/random.c +8
-0+/* 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 ;
Quoted 8 lines
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1258
Quoted 5 lines
drivers/char/random.c +5
-0+ break; + } + } +read_unlock (&dev_base_lock); +#endif This means you have to grab the
dev_base_lockeach 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.
Quoted 6 lines
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.
Quoted 5 lines
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.
Quoted 4 lines
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.
Quoted 6 lines
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1260
Quoted 2 lines
drivers/char/random.c +2
-0+if (unlikely (!netdev_found)) { +/* use bootid's nodeID if no network interface found */ If
CONFIG_NETis undefined, thenetdev_foundwill always be false, so theunlikely()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).
Quoted 6 lines
Quoted 6 lines
drivers/char/random.c +6
-0+/* 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 ;
Quoted 8 lines
drivers/char/random.c EXPORT_SYMBOL(generate_random_uuid); · line 1273
Quoted 3 lines
drivers/char/random.c +3
-0+else + goto inc_clock_seq; + }The goto loop could be much simplified if you grab the MAC/NodeID *before* you do
clock_seqlogic. Right now, if the Mac/NodeID changes, you end up having to redo a lot of processing for no good reason (and under theuuid_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
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
drivers/char/random.c | 206 ++++++++++++++++++++++++++++++++++++++++++++----- include/linux/sysctl.h | 5 - 2 files changed, 191 insertions(+), 20 deletions(-)
drivers/char/random.c +188 -18
@@ -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 <[email protected]>, 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 } };
include/linux/sysctl.h +3 -2
@@ -248,8 +248,9 @@ enumRANDOM_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 */