[PATCH] mkswap: generate UUID

[Colin Watson]

On Fri, Jun 19, 2009 at 09:30:37AM +0200, Denys Vlasenko wrote:
> On Friday 19 June 2009 04:10, Colin Watson wrote:
> > Please bear in mind that I was replying specifically to Denys' patch,
> > not to an abstract concept of a patch that used proper random numbers.
> > The reason I'm concerned about it is that I *do* understand the scale of
> > these things and that patch (which is in master now) isn't in the right
> > ballpark at all. I spent several days and nights of my life last year on
> > very little sleep dealing with cleanup and mitigation of the notorious
> > Debian openssl bug, in which an accidental mispatch caused a shortage of
> > randomness such that only 2^15 distinct keys were possible for each key
> > type/length combination. I know what powers of two do, and the kinds of
> > thing that happen if you don't have enough of them.
> 
> How about this?
> 
>         i = open("/dev/urandom", O_RDONLY);
>         if (i >= 0) {
>                 read(i, buf, 16);

I'd recommend using full_read.

>                 close(i);
>         }
>         /* Paranoia. /dev/urandom may be missing.
>          * rand() is guaranteed to generate at least [0, 2^15) range,
>          * but lowest bits in some libc are not so "random".  */
>         srand(monotonic_us());
>         pid = getpid();
>         while (1) {
>                 for (i = 0; i < 16; i++)
>                         buf[i] ^= rand() >> 5;
>                 if (pid == 0)
>                         break;
>                 srand(pid);
>                 pid = 0;
>         }

I haven't checked this in detail, but it looks superficially OK.

>         buf[4 + 2    ] = (buf[4 + 2    ] & 0x0f) | 0x40; /* time_hi_and_version */
>         buf[4 + 2 + 2] = (buf[4 + 2 + 2] & 0x3f) | 0x80; /* clk_seq_and_variant */

You should probably also borrow Rob's recommendation of setting the
multicast bit in the node ID so that your random UUIDs can't be confused
with those generated from network cards.

          buf[4 + 4 + 2] |= 1;

> > Now, granted, it doesn't matter so much if swap UUIDs are really
> > universally unique when you compare them to something like SSH keys. But
> > let's consider the example of a large organisation deploying Linux
> > automatically on lots of machines. We can probably expect those machines
> > to be of roughly the same specification such that they'll reach similar
> > stages of the installer at about the same time, plus or minus a few
> > seconds, and we can certainly expect their deployment to be such that
> > the installer takes an identical or nearly identical code path each
> > time. I'd be surprised at this point if you had much more than 2^24
> > random bits to play with. The probability of real collisions within the
> > organisation is no longer negligible.
> 
> Wow, they would mix their swap partitions! Run for your lives.

I attempted to stave off sarcasm later in my post by pointing out that
the same UUID generation function ought to be used for things like
mke2fs too (assuming it's ever turned back on in busybox), in which case
mounting the wrong filesystem can cause data loss. I guess my attempt
didn't work.

(And actually, if you get a swap partition of a different size mounted,
or one on a disk you were planning to phase out, it could well cause
enough confusion to lead to some support costs. Probably not hugely
important but still.)

> > The generation function you (Rob) sent in
> > http://lists.busybox.net/pipermail/busybox/2009-June/069690.html seems
> > much better to me and largely fine, except for two mistakes:
> > 
> >  * RFC2518 appears to be in error when it says that you should set the
> >    most significant bit of the first octet of the node ID to 1. RFC4122
> >    instead says you should set the *least* significant bit, which
> >    matches the description of IEEE 802 MAC addresses in
> >    http://en.wikipedia.org/wiki/MAC_address.
> > 
> >  * Your code uses uuid[11] as if it were the first octet of the node ID.
> >    I think this should in fact be uuid[10].
> > 
> > If I were writing it I think I'd follow libuuid's lead
> 
> That code is a good example of code explosion for no discernible reason
> which is so prevalent nowadays. No wonder just about anything today
> takes megabytes of code.
> 
> Getting a list of present network cards because I am about to mkswap?!
> No thanks.

libuuid supports various methods of generating UUIDs, which are
appropriate in different situations. As I said, in busybox's case it
would make complete sense to strip it down and only support random
UUIDs.

> > Can I recommend at least looking at libuuid and seeing what can be used,
> > though? It could be made a lot smaller simply by stripping out all the
> > time-based UUID stuff and assuming the existence of /dev/urandom, and as
> > I said above this should all be configured off by default.
> 
> The code above does something like that. Is it ok with you?

ENABLE_DESKTOP seems likely to be too heavyweight for me. I use this in
an environment that isn't as stripped-down as a real embedded
environment, but nevertheless I'd rather not turn on an option that's a
dumping ground for all kinds of stuff.

Why not take the opportunity to strip out lots of junk from
old_e2fsprogs after adding UUID handling to libbb? I'm assuming that
ultimately you guys want the old_e2fsprogs bit of the source tree to get
smaller as well as the executable size.

I've attached two alternative patches to this mail:

  1) Add support for CONFIG_FEATURE_MKSWAP_UUID which can be used
     instead of the bloaty CONFIG_DESKTOP.

  2) Add libbb/uuid.c with a heavily stripped-down version of libuuid;
     convert everything to use it, whether currently built or not;
     remove a couple of features from tune2fs (yes, I know it isn't
     currently built) that required more bits from the UUID library and
     didn't seem to be too important to support; strip out all the old
     libuuid source.

master (with CONFIG_DESKTOP) vs. patch 2 (with
CONFIG_FEATURE_MKSWAP_UUID) says -11687 bytes. A fairer comparison is
patch 1 vs. patch 2, both with CONFIG_FEATURE_MKSWAP_UUID; patch 2
produces an executable 126 bytes bigger. Given that this is a feature
that I doubt embedded people are going to enable, this seems like a
fairly worthwhile tradeoff for removing nearly 1000 lines of source
code. What do you think?

Incidentally, all of this probably works out bigger for me than just
linking against libuuid and being done with it, since I need libuuid in
my images *anyway* for other binaries that I need that aren't in
busybox! But hey, I can cope with that.

Thanks,

-- 
Colin Watson                                       [cjwatson at ubuntu.com]
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-mkswap-separate-UUID-feature.patch
Type: text/x-diff
Size: 1250 bytes
Desc: not available
URL: <http://lists.busybox.net/pipermail/busybox/attachments/20090619/832b8abe/attachment-0002.bin>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: 0001-Remove-libuuid-from-old_e2fsprogs-replace-with-libbb.patch
Type: text/x-diff
Size: 47716 bytes
Desc: not available
URL: <http://lists.busybox.net/pipermail/busybox/attachments/20090619/832b8abe/attachment-0003.bin>