lkml.org 
[lkml]   [2007]   [Nov]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH] Time-based RFC 4122 UUID generator
On Tue, Nov 20, 2007 at 10:59:58PM +0100, Helge Deller wrote:
> > > Current implemenations use userspace-libraries. In userspace you e.g. can't
> > > easily protect the uniquness of a UUID against other running _processes_.
> > > If you try do, you'll need to do locking e.g. with shared memory, which can
> > > get very expensive.
> >
> > Even with a futex? Or userspace atomics?
>
> Yes, you'll need a futex or similiar.
> The problem is then more, where will you put that futex to be able to protect against other processes ?
> Best solution is probably shared memory, but then the question will be, who is allowed to access this memory/futex ?
> Will any process (shared library) be allowed to read/write/delete it ?
> At this stage you then suddenly run from a locking-problem into a security problem, which is probably equally hard to solve.
> Btw, this is how Novell tried to solve the time-based UUID generator problem in SLES and it's still not 100% fixed.
>
> > I think something as simple
> > as a server stuffing a bunch of clock sequence numbers into a pipe
> > for clients to pop into their generated UUIDs should be plenty fast
> > enough.
>
> Sounds simple and is probably fast enough.
> But do you really want to add then another daemon to the Linux system, just in case "some" application needs somewhen a UUID ?

This really is the crux of the problem. I really don't want to add 1K
of unpageable memory to every kernel in the world for a feature that
can be implemented in userspace, just in case "some" application needs
a UUID.

> True, but let's look at the facts.
>
> Current libuuid.so (from e2fsprogs) library on Fedora 7 (i386):
> text data bss dec hex filename
> 8101 368 40 8509 213d /lib/libuuid.so.1
>
> And the kernel implementation:
> text data bss dec hex filename
> 4877 604 2080 7561 1d89 drivers/char/random.o.without_uuid
> 5976 752 2080 8808 2268 drivers/char/random.o.withuuid

I don't think that's a very good comparison. Here's a trivial (but untested)
implementation of RFC 4122 (variant 4) that's collision-safe and very tiny:

/* RFC4122-compliant UUID containing 128 - 4 - 2 - 1 = 121 bits of entropy */
void genrfc4122(char *buf)
{
int f;
f = open("/dev/urandom", O_RDONLY);
read(f, buf, 16); /* fill our buffer */
close(f);
/* sec4.4: set clock_seq_hi_and_reserved bits 6 and 7 to 0 and 1 */
buf[8] = (buf[8] & ~0x3f) | 0x80;
/* sec4.4: and high nibble of time_hi_and_version to 4 = "random" */
buf[6] = (buf[6] & 0xf) | 0x40;
/* sec4.5: set multicast bit to indicate random node (lsb of node[0])*/
buf[10] |= 1;
}

$ size rfc4122.o
text data bss dec hex filename
95 0 0 95 5f rfc4122.o

Modern kernels guarantee that simultaneous readers don't see the same
pool state, so collisions should be exceedingly rare. While collisions
are still possible here, frankly I think they are much less likely
than with schemes that involve persistent state, hardware ids, or
time. The odds of the persistent state or hardware ids being
mismanaged or the clock being off are quite terrestrial rather than
astronomical.

--
Mathematics is the supreme nostalgia of our time.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/

\
 
 \ /
  Last update: 2007-11-20 23:59    [W:0.078 / U:0.376 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site