Messages in this thread | | | From | Helge Deller <> | Subject | Re: [PATCH] Time-based RFC 4122 UUID generator | Date | Wed, 21 Nov 2007 00:11:57 +0100 |
| |
On Tuesday 20 November 2007, Matt Mackall wrote: > 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.
Again, it could be made a config option in which case you could disable it if you don't want it.
> > > 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
Nice example, but it's not comparable since it's not what this thread is about. As you mentioned, you showed here a variant 4 (fully random) version. You could have shown this even more easily, without any additional code:
[deller@halden linux-2.6]$ cat /proc/sys/kernel/random/uuid 607e598a-b0f2-4d60-9ca7-22838d2120ba
This is already in the kernel and it's allocating some non-swapable memory already.
My patch is about variant 1 (time-based), which is not that easy to make unique!
> 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.
That's only relevant to variant 4, not 1.
Helge - 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/
| |