[PATCH] Time-based RFC 4122 UUID generator - Kernel

This is a discussion on [PATCH] Time-based RFC 4122 UUID generator - Kernel ; Andrew, could you please consider adding this patch to your 2.6.25 patch series? This is the third version of the patch in which I cleaned up and fixed quite some stuff according to feedback from Ted. I assume this version ...

+ Reply to Thread
Page 1 of 2 1 2 LastLast
Results 1 to 20 of 22

Thread: [PATCH] Time-based RFC 4122 UUID generator

  1. [PATCH] Time-based RFC 4122 UUID generator

    Andrew,

    could you please consider adding this patch to your 2.6.25 patch series?

    This is the third version of the patch in which I cleaned up and fixed quite some stuff according to feedback from Ted.
    I assume this version is OK, since I didn't received any further feedback since two weeks: http://lkml.org/lkml/2007/11/4/128.

    Thanks,
    Helge
    -------
    Title: Add time-based RFC 4122 UUID generator

    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.

    This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    with which userspace applications can easily get real unique time-based
    UUIDs through /proc/sys/kernel/random/uuid_time.
    A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    so that the clock_seq value can be retained across system bootups (which
    is required by RFC 4122).

    The attached implementation uses getnstimeofday() to get very fine-grained
    granularity. This helps, so that userspace tools can get a lot more UUIDs
    (if needed) per time than before.
    A mutex takes care of the proper locking against a mistaken double creation
    of UUIDs for simultanious running processes.

    Signed-off-by: Helge Deller

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

    diff --git a/drivers/char/random.c b/drivers/char/random.c
    index 5fee056..fc48c29 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 , 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
    #include
    #include
    +#include

    #include
    #include
    @@ -1174,12 +1178,169 @@ 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.
    + * 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);
    +}
    +
    +
    +/*
    + * 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 +1352,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 +1382,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 +1439,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 +1452,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 */
    -
    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/

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

    On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:

    > Title: Add time-based RFC 4122 UUID generator
    >
    > 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.
    >
    > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > with which userspace applications can easily get real unique time-based
    > UUIDs through /proc/sys/kernel/random/uuid_time.
    > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > so that the clock_seq value can be retained across system bootups (which
    > is required by RFC 4122).
    >
    > The attached implementation uses getnstimeofday() to get very fine-grained
    > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > (if needed) per time than before.
    > A mutex takes care of the proper locking against a mistaken double creation
    > of UUIDs for simultanious running processes.


    Who will use this feature, and for what?

    (In fact, who uses the existing UUID generators, and for what?)

    Thanks.
    -
    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/

  3. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Sun, Nov 18, 2007 at 01:05:03PM -0800, Andrew Morton wrote:
    > On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    >
    > > Title: Add time-based RFC 4122 UUID generator
    > >
    > > 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.
    > >
    > > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > > with which userspace applications can easily get real unique time-based
    > > UUIDs through /proc/sys/kernel/random/uuid_time.
    > > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > > so that the clock_seq value can be retained across system bootups (which
    > > is required by RFC 4122).
    > >
    > > The attached implementation uses getnstimeofday() to get very fine-grained
    > > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > > (if needed) per time than before.
    > > A mutex takes care of the proper locking against a mistaken double creation
    > > of UUIDs for simultanious running processes.

    >
    > Who will use this feature, and for what?
    >
    > (In fact, who uses the existing UUID generators, and for what?)


    I use libuuid and I assume libuuid uses some uuid generator support
    from the kernel. libuuid comes from a package that Ted's maintain IIRC.

    I (my company) use uuid to uniquely identify objects in a distributed
    database.
    [Proprietary closed source stuff].

    Sam
    -
    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/

  4. Re: [PATCH] Time-based RFC 4122 UUID generator

    Sam Ravnborg wrote:

    > On Sun, Nov 18, 2007 at 01:05:03PM -0800, Andrew Morton wrote:
    >> On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    >>
    >> > Title: Add time-based RFC 4122 UUID generator
    >> >
    >> > 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.
    >> >
    >> > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    >> > with which userspace applications can easily get real unique time-based
    >> > UUIDs through /proc/sys/kernel/random/uuid_time.
    >> > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is
    >> > available, so that the clock_seq value can be retained across system
    >> > bootups (which is required by RFC 4122).
    >> >
    >> > The attached implementation uses getnstimeofday() to get very
    >> > fine-grained granularity. This helps, so that userspace tools can get a
    >> > lot more UUIDs (if needed) per time than before.
    >> > A mutex takes care of the proper locking against a mistaken double
    >> > creation of UUIDs for simultanious running processes.

    >>
    >> Who will use this feature, and for what?
    >>
    >> (In fact, who uses the existing UUID generators, and for what?)

    >
    > I use libuuid and I assume libuuid uses some uuid generator support
    > from the kernel.


    No, it does not. It's pure userspace and may produce double UUIDs.

    > libuuid comes from a package that Ted's maintain IIRC.
    >
    > I (my company) use uuid to uniquely identify objects in a distributed
    > database.
    > [Proprietary closed source stuff].


    Same here.

    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/

  5. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Sunday 18 November 2007, Andrew Morton wrote:
    > On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    >
    > > Title: Add time-based RFC 4122 UUID generator
    > >
    > > 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.
    > >
    > > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > > with which userspace applications can easily get real unique time-based
    > > UUIDs through /proc/sys/kernel/random/uuid_time.
    > > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > > so that the clock_seq value can be retained across system bootups (which
    > > is required by RFC 4122).
    > >
    > > The attached implementation uses getnstimeofday() to get very fine-grained
    > > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > > (if needed) per time than before.
    > > A mutex takes care of the proper locking against a mistaken double creation
    > > of UUIDs for simultanious running processes.



    > Who will use this feature, and for what?
    > (In fact, who uses the existing UUID generators, and for what?)


    Current users I know of (but there are more):
    - e2fsprogs uses it e.g. to create unique UUIDs for disks (it ships an own library for that)
    - http://commons.apache.org/sandbox/id/uuid.html uses it with own libraries
    - SAP Netweaver on Linux uses it (http://www.sap.com/platform/netweaver/index.epx)

    I'm mostly interested in fixing problems I see with SAP (I'm working for SAP).
    SAP Netweaver often needs during a very short time frame lots of unique UUIDs
    (to reference the data afterwards) when new data is imported into the database.
    Main problem with current implementations is, is that they don't 100%
    guarantee uniqness of the generated UUIDs. Sometimes, esp. on very fast
    multi-processor machines, double UUIDs are generated and returned to the
    application which is very bad and may result in unreliable behaviour.

    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.
    My in-kernel implementation does guarantee the uniquness through the mutex.

    The problem will get even worse with virtualization technologies like XEN and
    containers. There it's even impossible to protect against processes in other VMs.

    Another user which could benefit from it are embedded devices. They could
    drop their userspace-implementations in favour of this smaller kernel version
    to create UUIDs for their disks, using it in the webservers, ...

    Best regards,
    Helge


    PS:
    I did created bugreports against the e2fsprogs userspace implementation
    at Red Hat and Novell (only accessible for RH/Novell employees), but as I
    explained above, the userspace-implementation may not be sufficient:
    https://bugzilla.redhat.com/show_bug.cgi?id=233471
    https://bugzilla.redhat.com/show_bug.cgi?id=218606
    https://bugzilla.novell.com/show_bug.cgi?id=189640
    -
    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/

  6. RE: [PATCH] Time-based RFC 4122 UUID generator


    > > I use libuuid and I assume libuuid uses some uuid generator support
    > > from the kernel.

    >
    > No, it does not. It's pure userspace and may produce double UUIDs.
    >
    > > libuuid comes from a package that Ted's maintain IIRC.
    > >
    > > I (my company) use uuid to uniquely identify objects in a distributed
    > > database.
    > > [Proprietary closed source stuff].

    >
    > Same here.
    >
    > Helge


    Any UUID generator that can produce duplicate UUIDs with probability
    significantly less than purely random UUIDs is so badly broken that it
    should not ever be used. Anyone who finds such a UUID generator should
    immediately either fix it or throw it on the junk heap. Anyone who knowingly
    uses such a UUID generator should be publically shamed.

    Rather than (or at the very least, in addition to) adding a new UUID
    generator, let's fix the one(s) we have.

    DS


    -
    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/

  7. Re: [PATCH] Time-based RFC 4122 UUID generator

    > Any UUID generator that can produce duplicate UUIDs with probability
    > significantly less than purely random UUIDs is so badly broken that it
    > should not ever be used. Anyone who finds such a UUID generator should
    > immediately either fix it or throw it on the junk heap. Anyone who knowingly
    > uses such a UUID generator should be publically shamed.


    That depends what they are using it for. Deliberately colliding with
    other UUIDs is sometimes highly desirable, just not usually in productive
    circles.
    -
    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/

  8. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:

    > Andrew,
    >
    > could you please consider adding this patch to your 2.6.25 patch series?


    please cc netdev on networking-related things

    > This is the third version of the patch in which I cleaned up and fixed quite some stuff according to feedback from Ted.
    > I assume this version is OK, since I didn't received any further feedback since two weeks: http://lkml.org/lkml/2007/11/4/128.
    >
    > Thanks,
    > Helge
    > -------
    > Title: Add time-based RFC 4122 UUID generator
    >
    > 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.
    >
    > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > with which userspace applications can easily get real unique time-based
    > UUIDs through /proc/sys/kernel/random/uuid_time.
    > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > so that the clock_seq value can be retained across system bootups (which
    > is required by RFC 4122).
    >
    > The attached implementation uses getnstimeofday() to get very fine-grained
    > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > (if needed) per time than before.
    > A mutex takes care of the proper locking against a mistaken double creation
    > of UUIDs for simultanious running processes.
    >
    > Signed-off-by: Helge Deller
    >
    > drivers/char/random.c | 205 ++++++++++++++++++++++++++++++++++++++++++++-----
    > include/linux/sysctl.h | 5 -
    > 2 files changed, 190 insertions(+), 20 deletions(-)
    >
    > diff --git a/drivers/char/random.c b/drivers/char/random.c
    > index 5fee056..fc48c29 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 , 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
    > #include
    > #include
    > +#include
    >
    > #include
    > #include
    > @@ -1174,12 +1178,169 @@ 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.
    > + * Helper functions and variables for time based UUID generator
    > + */
    > +static unsigned int clock_seq;
    > +static const unsigned int clock_seq_max = 0x3fff; /* 14 bits */


    There isn't a lot of point in `static const'. Hopefully the compiler will
    do the right thing with it (use literal constant and elide the storage if
    nothing takes its address) but why not just do #define UPPER_CASE_THING in
    the time-homoured manner?

    > +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();


    Seems there's a straightfroward race here where multiple tasks can run
    init_clockseq() concurrently.

    Can't we use a regular initcall here and make init_clockseq() __init? I
    guess that would cast doubt over the quality of the thing which
    get_random_bytes() returned, but that's already the case - super-early
    userspace in initramfs could mount /proc and trigger this call. We end up
    with a predictable sequence number?

    > + 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


    hm. Maybe that should be a helper function over in net/, dunno.

    So you're assuming that the first-encountered netdev's mac address is a
    globally-unique number? That's a key design decision and should 100%
    have appeared front-and-centre in the changelog.

    Is it true? It may be true in a practial sense, but perhaps in some
    private networking environments some organisations have duplicated mac
    addresses?

    What are the implications of this assumption being false?

    > + 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);
    > + }


    What is "bootid's nodeID"?

    I guess I could work it out, but again, this is a core design decision and
    it should be properly covered in your changelog so we can
    understand what your thinking is here.

    > + /* 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;
    > + }


    etc.

    > + /* 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);
    > +}
    > +
    > +
    > +/*
    > + * 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 +1352,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 +1382,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 +1439,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 +1452,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 */
    > };



    -
    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/

  9. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Sun, Nov 18, 2007 at 10:40:34PM +0100, Helge Deller wrote:
    > On Sunday 18 November 2007, Andrew Morton wrote:
    > > On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    > >
    > > > Title: Add time-based RFC 4122 UUID generator
    > > >
    > > > 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.
    > > >
    > > > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > > > with which userspace applications can easily get real unique time-based
    > > > UUIDs through /proc/sys/kernel/random/uuid_time.
    > > > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > > > so that the clock_seq value can be retained across system bootups (which
    > > > is required by RFC 4122).
    > > >
    > > > The attached implementation uses getnstimeofday() to get very fine-grained
    > > > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > > > (if needed) per time than before.
    > > > A mutex takes care of the proper locking against a mistaken double creation
    > > > of UUIDs for simultanious running processes.

    >
    >
    > > Who will use this feature, and for what?
    > > (In fact, who uses the existing UUID generators, and for what?)

    >
    > Current users I know of (but there are more):
    > - e2fsprogs uses it e.g. to create unique UUIDs for disks (it ships an own library for that)
    > - http://commons.apache.org/sandbox/id/uuid.html uses it with own libraries
    > - SAP Netweaver on Linux uses it (http://www.sap.com/platform/netweaver/index.epx)
    >
    > I'm mostly interested in fixing problems I see with SAP (I'm working for SAP).
    > SAP Netweaver often needs during a very short time frame lots of unique UUIDs
    > (to reference the data afterwards) when new data is imported into the database.
    > Main problem with current implementations is, is that they don't 100%
    > guarantee uniqness of the generated UUIDs. Sometimes, esp. on very fast
    > multi-processor machines, double UUIDs are generated and returned to the
    > application which is very bad and may result in unreliable behaviour.
    >
    > 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? 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.

    > The problem will get even worse with virtualization technologies like XEN and
    > containers. There it's even impossible to protect against processes in other VMs.


    Nor does it make sense to try! A virtual machine is an independent machine
    after all.

    > Another user which could benefit from it are embedded devices. They could
    > drop their userspace-implementations in favour of this smaller kernel version
    > to create UUIDs for their disks, using it in the webservers, ...


    That's a silly tradeoff. It's an unusual embedded device that ships
    with any need for a UUID, especially mkfs. And generally, putting a
    feature in the kernel has no inherent size advantage. In fact, it has
    a size disadvantage: it's no longer pageable.

    ps: I'm the listed random.c maintainer so you'll want to cc: me in the
    future.
    --
    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/

  10. Re: [PATCH] Time-based RFC 4122 UUID generator

    David Schwartz wrote:
    >
    > Any UUID generator that can produce duplicate UUIDs with probability
    > significantly less than purely random UUIDs is so badly broken that it
    > should not ever be used. Anyone who finds such a UUID generator should
    > immediately either fix it or throw it on the junk heap. Anyone who knowingly
    > uses such a UUID generator should be publically shamed.
    >
    > Rather than (or at the very least, in addition to) adding a new UUID
    > generator, let's fix the one(s) we have.
    >


    I presume you mean "significantly higher."

    Realistically speaking, a random UUID is probably the best you're going
    to ever get. I highly suspect that any time- and MAC-address-based
    solution is going to suffer from mis-set clocks and misprogrammed MAC
    addresses more often than you will have collisions in a 122-bit random
    number.

    -hpa
    -
    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/

  11. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Tuesday 20 November 2007, Matt Mackall wrote:
    > On Sun, Nov 18, 2007 at 10:40:34PM +0100, Helge Deller wrote:
    > > On Sunday 18 November 2007, Andrew Morton wrote:
    > > > On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    > > >
    > > > > Title: Add time-based RFC 4122 UUID generator
    > > > >
    > > > > 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.
    > > > >
    > > > > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > > > > with which userspace applications can easily get real unique time-based
    > > > > UUIDs through /proc/sys/kernel/random/uuid_time.
    > > > > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > > > > so that the clock_seq value can be retained across system bootups (which
    > > > > is required by RFC 4122).
    > > > >
    > > > > The attached implementation uses getnstimeofday() to get very fine-grained
    > > > > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > > > > (if needed) per time than before.
    > > > > A mutex takes care of the proper locking against a mistaken double creation
    > > > > of UUIDs for simultanious running processes.

    > >
    > >
    > > > Who will use this feature, and for what?
    > > > (In fact, who uses the existing UUID generators, and for what?)

    > >
    > > Current users I know of (but there are more):
    > > - e2fsprogs uses it e.g. to create unique UUIDs for disks (it ships an own library for that)
    > > - http://commons.apache.org/sandbox/id/uuid.html uses it with own libraries
    > > - SAP Netweaver on Linux uses it (http://www.sap.com/platform/netweaver/index.epx)
    > >
    > > I'm mostly interested in fixing problems I see with SAP (I'm working for SAP).
    > > SAP Netweaver often needs during a very short time frame lots of unique UUIDs
    > > (to reference the data afterwards) when new data is imported into the database.
    > > Main problem with current implementations is, is that they don't 100%
    > > guarantee uniqness of the generated UUIDs. Sometimes, esp. on very fast
    > > multi-processor machines, double UUIDs are generated and returned to the
    > > application which is very bad and may result in unreliable behaviour.
    > >
    > > 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 ?
    And I think such an implementation is more complex, would need more memory, file handles, and so on than this simple kernel patch.

    > > The problem will get even worse with virtualization technologies like XEN and
    > > containers. There it's even impossible to protect against processes in other VMs.

    >
    > Nor does it make sense to try! A virtual machine is an independent machine
    > after all.


    Yes.

    > > Another user which could benefit from it are embedded devices. They could
    > > drop their userspace-implementations in favour of this smaller kernel version
    > > to create UUIDs for their disks, using it in the webservers, ...

    >
    > That's a silly tradeoff. It's an unusual embedded device that ships
    > with any need for a UUID, especially mkfs.


    I think mkfs was a very bad example from my side. I should not have mentioned this one.
    Nevertheless, time-based UUIDs are used in quite many other and more critical applications than e2fsprogs tools.

    > And generally, putting a
    > feature in the kernel has no inherent size advantage. In fact, it has
    > a size disadvantage: it's no longer pageable.


    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

    So my patch increases the kernel by 1099 bytes text and 148 bytes data while guaranteeing 100% unique UUIDs.
    libuuid.so takes 8k test and 368 bytes data, and does not guarantees the uniqueness.
    Of course libuuid.so has some helper functions as well in here, which - to be fair - shouldn't be counted.
    Nevertheless, I think you can't get any smaller, faster and more secure implementation than only in the kernel.

    Maybe it would make sense to add a CONFIG_TIME_UUID kernel option, so that distributors can decide themselves if they want the kernel UUID generator compiled in?
    At least for Enterprise-ready Linux distributions it's a must.

    > ps: I'm the listed random.c maintainer so you'll want to cc: me in the
    > future.


    Sure.

    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/

  12. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Tuesday 20 November 2007, Andrew Morton wrote:
    > On Sun, 18 Nov 2007 20:38:21 +0100 Helge Deller wrote:
    >
    > > Andrew,
    > >
    > > could you please consider adding this patch to your 2.6.25 patch series?

    >
    > please cc netdev on networking-related things


    Ok.

    > > This is the third version of the patch in which I cleaned up and fixed quite some stuff according to feedback from Ted.
    > > I assume this version is OK, since I didn't received any further feedback since two weeks: http://lkml.org/lkml/2007/11/4/128.
    > >
    > > Thanks,
    > > Helge
    > > -------
    > > Title: Add time-based RFC 4122 UUID generator
    > >
    > > 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.
    > >
    > > This patch additionally adds the "Time-based UUID" variant of RFC 4122,
    > > with which userspace applications can easily get real unique time-based
    > > UUIDs through /proc/sys/kernel/random/uuid_time.
    > > A new /proc/sys/kernel/random/uuid_time_clockseq sysfs entry is available,
    > > so that the clock_seq value can be retained across system bootups (which
    > > is required by RFC 4122).
    > >
    > > The attached implementation uses getnstimeofday() to get very fine-grained
    > > granularity. This helps, so that userspace tools can get a lot more UUIDs
    > > (if needed) per time than before.
    > > A mutex takes care of the proper locking against a mistaken double creation
    > > of UUIDs for simultanious running processes.
    > >
    > > Signed-off-by: Helge Deller
    > >
    > > drivers/char/random.c | 205 ++++++++++++++++++++++++++++++++++++++++++++-----
    > > include/linux/sysctl.h | 5 -
    > > 2 files changed, 190 insertions(+), 20 deletions(-)
    > >
    > > diff --git a/drivers/char/random.c b/drivers/char/random.c
    > > index 5fee056..fc48c29 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 , 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
    > > #include
    > > #include
    > > +#include
    > >
    > > #include
    > > #include
    > > @@ -1174,12 +1178,169 @@ 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.
    > > + * Helper functions and variables for time based UUID generator
    > > + */
    > > +static unsigned int clock_seq;
    > > +static const unsigned int clock_seq_max = 0x3fff; /* 14 bits */

    >
    > There isn't a lot of point in `static const'. Hopefully the compiler will
    > do the right thing with it (use literal constant and elide the storage if
    > nothing takes its address) but why not just do #define UPPER_CASE_THING in
    > the time-homoured manner?


    Thanks. I'll fix this with a #define.

    > > +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();

    >
    > Seems there's a straightfroward race here where multiple tasks can run
    > init_clockseq() concurrently.
    >
    > Can't we use a regular initcall here and make init_clockseq() __init? I
    > guess that would cast doubt over the quality of the thing which
    > get_random_bytes() returned, but that's already the case - super-early
    > userspace in initramfs could mount /proc and trigger this call. We end up
    > with a predictable sequence number?


    Ok, I'll change that to an initcall.
    It's possible for userspace to write a new random new clock_seq value to
    /proc/sys/kernel/random/uuid_time_clockseq at any time at bootup, although
    this shouldn't be necessary at all if the clock is correct at the time the first
    UUID is asked for.
    So, in principle it shouldn't be a big problem if it's an initcall.

    > > + 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


    > hm. Maybe that should be a helper function over in net/, dunno.


    Me neither :-)
    If people here prefer, I'll come up with a patch for net/.

    What this code basically does is:
    - Look if a net device with a given MAC still exists in this machine. If yes, return this MAC again.
    - If it does not exist any longer, return the MAC address of the _first_ true network card
    - If no network card exists at all, return e.g. 'false' (in which case the UUID function will use a random MAC).

    What does the network people here think ? Should this be a helper function in net/ ?

    > So you're assuming that the first-encountered netdev's mac address is a
    > globally-unique number? That's a key design decision and should 100%
    > have appeared front-and-centre in the changelog.


    Basically that's just the steps the RFC describes. I just sticked to the RFC.
    The RFC is aware, that it's probably not globally-unique, that's why a 'clock_seq' number and
    the time stamp adds some more 'uniqueness' to the full UUID.

    > Is it true? It may be true in a practial sense, but perhaps in some
    > private networking environments some organisations have duplicated mac
    > addresses?
    >
    > What are the implications of this assumption being false?


    See above. Only all pieces together (timestamp + clock_seq + MAC) builds up
    the full UUID.
    The timestamp value is the current time, and clock_seq is a random value.
    MAC is preferrably a real MAC, or if not available a random MAC-like number.

    > > + 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);
    > > + }

    >
    > What is "bootid's nodeID"?


    Acording to the RFC you should generate a random number and use it
    as MAC, if no network device was found.
    The current Linux kernel generates a "random unique boot ID" for
    /proc/sys/kernel/random/uuid, and the last part of this UUID is the
    "bootid/nodeID" (a random MAC). It's then used by my code if no
    network card is found.

    > I guess I could work it out, but again, this is a core design decision and
    > it should be properly covered in your changelog so we can
    > understand what your thinking is here.


    Yes. Basically it's just the RFC 4122 implementation, but I'll better describe
    it with the next patch.

    > > + /* 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;
    > > + }

    >
    > etc.
    >
    > > + /* 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);
    > > +}
    > > +
    > > +
    > > +/*
    > > + * 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 +1352,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 +1382,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 +1439,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 +1452,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 */
    > > };

    >
    >

    -
    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/

  13. Re: [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/

  14. RE: [PATCH] Time-based RFC 4122 UUID generator

    David Schwartz wrote:
    > Any UUID generator that can produce duplicate UUIDs with probability
    > significantly less than purely random UUIDs is so badly broken that it
    > should not ever be used. Anyone who finds such a UUID generator should
    > immediately either fix it or throw it on the junk heap.


    That's what my patch is about: Solve the problem at it's root.

    > Anyone who
    > knowingly uses such a UUID generator should be publically shamed.


    The problem is that on Linux there is currently no time-based UUID generator
    which really solves the problem.
    Good (bad?) thing is: Other UNIXes aren't better either.

    > Rather than (or at the very least, in addition to) adding a new UUID
    > generator, let's fix the one(s) we have.


    Some things aren't fixable with userspace only. At least _some_ kind of help
    is needed from the kernel.
    Why not providing one single working version directly from the kernel and
    dropping others you can't cleanly fix anyway ?

    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/

  15. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Tue, Nov 20, 2007 at 10:59:58PM +0100, Helge Deller wrote:
    > > 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.


    Basically, the only way to solve this problem 100% in userspace would
    be with a userspace daemon running as a privileged user, and some kind
    of Unix domain socket.

    Patches to implement this in the e2fsprogs UUID library would be
    greatfully accepted.

    > 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 ?
    >
    > And I think such an implementation is more complex, would need more
    > memory, file handles, and so on than this simple kernel patch.


    Well, it probably is less code, but keep in mind to really get things
    right, you need to store the UUID counter on disk, so there is some
    complexity which is needed in userspace anyway.

    One bigger question which is why do you want to use time-based UUID's?
    With the kernels random number generator, the random UUID's should be
    quite good enough for your purposes.

    > I think mkfs was a very bad example from my side. I should not have
    > mentioned this one. Nevertheless, time-based UUIDs are used in
    > quite many other and more critical applications than e2fsprogs
    > tools.


    Actually, these days e2fsprogs uses random-based UUID's.

    - Ted
    -
    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/

  16. Re: [PATCH] Time-based RFC 4122 UUID generator

    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/

  17. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Wed, Nov 21, 2007 at 12:11:57AM +0100, Helge Deller wrote:
    > 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.


    That's not an argument; it applies to any proposed feature. And it's
    largely a no-op because most vendors will turn all potentially useful
    features on. So we still end up with 1K of unpageable memory in
    approximately every kernel in the world.

    We don't like to add things to the kernel that can be done
    sufficiently well in userspace. Once it's in the kernel, it's
    potentially stuck there for all of time because people may come to
    depend on it.

    > 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


    Quite silly to have put that in the kernel when we could have done it
    in userspace for 95 bytes, no? But now we're stuck with it for the
    foreseeable future. I'd rather it -not- have any friends to keep it
    company.

    > > 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.


    Sure it is, I'm quite explicitly saying that variant 1 is less safe
    -in practical terms- than variant 4.

    --
    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/

  18. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Wednesday 21 November 2007, Theodore Tso wrote:
    > On Tue, Nov 20, 2007 at 10:59:58PM +0100, Helge Deller wrote:
    > > > 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.

    >
    > Basically, the only way to solve this problem 100% in userspace would
    > be with a userspace daemon running as a privileged user, and some kind
    > of Unix domain socket.


    Yes, probably.

    > Patches to implement this in the e2fsprogs UUID library would be
    > greatfully accepted.
    >
    > > 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 ?
    > >
    > > And I think such an implementation is more complex, would need more
    > > memory, file handles, and so on than this simple kernel patch.

    >
    > Well, it probably is less code, but keep in mind to really get things
    > right, you need to store the UUID counter on disk, so there is some
    > complexity which is needed in userspace anyway.


    Yes, it's at least needed for the case when the wall clock is wrong.
    If it's syncronized with NTP (or similiar), it's not really needed.

    Anyway, if this patch is accepted, I'll be happy send patches against the
    various bootup scripts to save the last seq_number at shutdown and
    restore it at bootup. Maybe something similiar as the /var/lib/random-seed
    which is saved by /etc/init.d/halt in Fedora.

    > One bigger question which is why do you want to use time-based UUID's?
    > With the kernels random number generator, the random UUID's should be
    > quite good enough for your purposes.


    The big difference between random UUIDs and time-based UUIDs is that
    time-based UUIDs can be used more efficiently as indexing keys in databases.
    The true randomness of random UUIDs just break performance, while
    with some further tricks you can get time-based UUIDs easily sorted.
    At least we saw a big speed difference when we used time-based keys, as
    they e.g. were used on Windows with MS SQL server. On Linux I personally
    would like to see a similiar speedup and for that really unique time-based
    UUIDs are needed.

    > > I think mkfs was a very bad example from my side. I should not have
    > > mentioned this one. Nevertheless, time-based UUIDs are used in
    > > quite many other and more critical applications than e2fsprogs
    > > tools.

    >
    > Actually, these days e2fsprogs uses random-based UUID's.


    Yes, but still libuuid from e2fsprogs does a good job for what's really
    needed and sufficient for the e2fsprogs tools like mkfs.
    Sadly the time-based variant of libuuid still hase some way to go.
    Initially I really wanted to send patches for libuuid to fix the
    time-based variant, but now I really think the kernel-solution is
    the better, smaller, cleaner and more reliable approach.

    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/

  19. Re: [PATCH] Time-based RFC 4122 UUID generator

    On Tue, 20 Nov 2007 23:58:38 +0100
    Helge Deller wrote:

    > David Schwartz wrote:
    > > Any UUID generator that can produce duplicate UUIDs with probability
    > > significantly less than purely random UUIDs is so badly broken that it
    > > should not ever be used. Anyone who finds such a UUID generator should
    > > immediately either fix it or throw it on the junk heap.

    >
    > That's what my patch is about: Solve the problem at it's root.


    Time based is not neccessarily random, but the kernel one is also clearly
    not random either.

    Alan
    -
    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/

  20. [e2fsprogs PATCH] Userspace solution to time-based UUID without duplicates

    On Tue, Nov 20, 2007 at 06:00:12PM -0500, Theodore Tso wrote:
    > Basically, the only way to solve this problem 100% in userspace would
    > be with a userspace daemon running as a privileged user, and some kind
    > of Unix domain socket.
    >
    > Patches to implement this in the e2fsprogs UUID library would be
    > greatfully accepted.


    This patch creates a userspace uuidd which correctly generates
    time-based (version 1) UUID's, with the clock sequence number stored
    in the filesystem so we correctly detect time going backwards across
    processes and even across reboots.

    I believe this patch is a better solution than Helge's kernel patch
    solution or the kludgy patch to e2fsprogs in the the SLES RPM which
    tries to solve this problem in another way, but which has been
    problematic in the past.

    Helge, could you try this out and see if it meets your needs?

    - Ted


    commit 84e7405d89cb79b43d84e86051bf2f34d9ae5216
    Author: Theodore Ts'o
    Date: Mon Dec 10 00:22:16 2007 -0500

    Add uuidd daemon to prevent duplicate time-based UUID's

    Also store the clock sequence information in a state file in
    /var/lib/misc/uuid-clock so that if the time goes backwards the clock
    sequence counter can get bumped. This allows us to completely
    correctly generate time-based (version 1) UUID's according to the
    algorithm specified RFC 4122.

    Addresses-Sourceforge-Bug: #1529672

    Signed-off-by: "Theodore Ts'o"

    diff --git a/debian/changelog b/debian/changelog
    index 737242a..04a068b 100644
    --- a/debian/changelog
    +++ b/debian/changelog
    @@ -1,3 +1,9 @@
    +e2fsprogs (1.40.3-2) unstable; urgency=low
    +
    + * Add uuidd daemon
    +
    + -- Theodore Y. Ts'o Sun, 09 Dec 2007 22:47:53 -0500
    +
    e2fsprogs (1.40.3-1) unstable; urgency=medium

    * New upstream release
    diff --git a/debian/control b/debian/control
    index 448be70..03305d6 100644
    --- a/debian/control
    +++ b/debian/control
    @@ -84,6 +84,19 @@ Description: universally unique id library
    libuuid generates and parses 128-bit universally unique id's (UUID's).
    See RFC 4122 for more information.

    +Package: uuid-runtime
    +Section: libs
    +Priority: optional
    +Depends: ${shlibsepends}
    +Replaces: e2fsprogs (<= 1.40.3-1ubuntu1)
    +Architecture: any
    +Description: universally unique id library
    + libuuid generates and parses 128-bit universally unique id's (UUID's).
    + See RFC 4122 for more information.
    + .
    + This package contains the uuidd daemon which is used by libuuid as well as
    + the uuidgen program.
    +
    Package: libuuid1-udeb
    Section: debian-installer
    Priority: optional
    diff --git a/debian/rules b/debian/rules
    index 842965e..ebbe062 100755
    --- a/debian/rules
    +++ b/debian/rules
    @@ -354,7 +354,7 @@ binary-arch: install install-udeb
    DH_OPTIONS= dh_installchangelogs -pe2fsprogs \
    -plibblkid${BLKID_SOVERSION} -plibcomerr${COMERR_SOVERSION} \
    -plibss${SS_SOVERSION} -plibuuid${UUID_SOVERSION} \
    - -pe2fslibs -puuid-dev -pe2fsck-static
    + -pe2fslibs -puuid-dev -puuid-runtime -pe2fsck-static

    dh_fixperms
    ifneq ($(ismips),)
    diff --git a/debian/uuid-runtime.copyright b/debian/uuid-runtime.copyright
    new file mode 100644
    index 0000000..f346739
    --- /dev/null
    +++ b/debian/uuid-runtime.copyright
    @@ -0,0 +1,38 @@
    +This package was added to the e2fsprogs debian source package by
    +Theodore Ts'o on Sat Mar 15 15:33:37 EST 2003
    +
    +It is part of the main e2fsprogs distribution, which can be found at:
    +
    + http://sourceforge.net/projects/e2fsprogs
    +
    +Upstream Author: Theodore Ts'o
    +
    +Copyright:
    +
    +Copyright (C) 1999, 2000, 2003, 2004 by Theodore Ts'o
    +
    +Redistribution and use in source and binary forms, with or without
    +modification, are permitted provided that the following conditions
    +are met:
    +1. Redistributions of source code must retain the above copyright
    + notice, and the entire permission notice in its entirety,
    + including the disclaimer of warranties.
    +2. Redistributions in binary form must reproduce the above copyright
    + notice, this list of conditions and the following disclaimer in the
    + documentation and/or other materials provided with the distribution.
    +3. The name of the author may not be used to endorse or promote
    + products derived from this software without specific prior
    + written permission.
    +
    +THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESS OR IMPLIED
    +WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
    +OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE, ALL OF
    +WHICH ARE HEREBY DISCLAIMED. IN NO EVENT SHALL THE AUTHOR BE
    +LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
    +CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT
    +OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR
    +BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
    +LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
    +(INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE
    +USE OF THIS SOFTWARE, EVEN IF NOT ADVISED OF THE POSSIBILITY OF SUCH
    +DAMAGE.
    diff --git a/debian/uuid-runtime.files b/debian/uuid-runtime.files
    new file mode 100644
    index 0000000..4f3784b
    --- /dev/null
    +++ b/debian/uuid-runtime.files
    @@ -0,0 +1,5 @@
    +usr/bin/uuidgen
    +usr/sbin/uuidd
    +etc/init.d/uuidd
    +usr/share/man/man8/uuidd.*
    +usr/share/man/man1/uuidgen.*
    diff --git a/debian/uuid-runtime.postinst b/debian/uuid-runtime.postinst
    new file mode 100755
    index 0000000..6523637
    --- /dev/null
    +++ b/debian/uuid-runtime.postinst
    @@ -0,0 +1,5 @@
    +#!/bin/sh -e
    +
    +mkdir -p /var/lib/misc
    +update-rc.d uuidd defaults 25 20 > /dev/null
    +invoke-rc.d uuidd start
    diff --git a/debian/uuid-runtime.postrm b/debian/uuid-runtime.postrm
    new file mode 100755
    index 0000000..212cc76
    --- /dev/null
    +++ b/debian/uuid-runtime.postrm
    @@ -0,0 +1,8 @@
    +#!/bin/sh
    +set -e
    +if [ "$1" = purge ]
    +then
    + update-rc.d uuidd remove >/dev/null;
    + rm -rf /var/lib/misc/uuid-clock /var/run/uuidd.sock /var/run/uuidd.pid
    +fi
    +
    diff --git a/debian/uuid-runtime.prerm b/debian/uuid-runtime.prerm
    new file mode 100755
    index 0000000..f83060c
    --- /dev/null
    +++ b/debian/uuid-runtime.prerm
    @@ -0,0 +1,6 @@
    +#! /bin/sh
    +
    +if [ -x /etc/init.d/uuidd ]
    +then
    + invoke-rc.d uuidd stop || true
    +fi
    diff --git a/lib/uuid/gen_uuid.c b/lib/uuid/gen_uuid.c
    index 61f2805..b178fc8 100644
    --- a/lib/uuid/gen_uuid.c
    +++ b/lib/uuid/gen_uuid.c
    @@ -38,6 +38,7 @@
    */
    #define _SVID_SOURCE

    +#include
    #ifdef HAVE_UNISTD_H
    #include
    #endif
    @@ -57,6 +58,7 @@
    #ifdef HAVE_SYS_SOCKET_H
    #include
    #endif
    +#include
    #ifdef HAVE_SYS_SOCKIO_H
    #include
    #endif
    @@ -251,18 +253,54 @@ static int get_clock(uint32_t *clock_high, uint32_t *clock_low, uint16_t *ret_cl
    {
    static int adjustment = 0;
    static struct timeval last = {0, 0};
    + static int state_fd = -2;
    + static FILE *state_f;
    static uint16_t clock_seq;
    struct timeval tv;
    unsigned long long clock_reg;
    -
    -try_again:
    - gettimeofday(&tv, 0);
    +
    + if (state_fd == -2) {
    + state_fd = open("/var/lib/misc/uuid-clock",
    + O_RDWR|O_CREAT, 0600);
    + state_f = fdopen(state_fd, "r+");
    + if (!state_f) {
    + close(state_fd);
    + state_fd = -1;
    + }
    + }
    + if (state_fd >= 0) {
    + rewind(state_f);
    + while (lockf(state_fd, F_LOCK, 0) < 0) {
    + if ((errno == EAGAIN) || (errno == EINTR))
    + continue;
    + fclose(state_f);
    + close(state_fd);
    + state_fd = -1;
    + }
    + }
    + if (state_fd >= 0) {
    + unsigned int cl;
    + unsigned long tv1, tv2;
    + int a;
    +
    + if (fscanf(state_f, "clock: %04x tv: %lu %lu adj: %d\n",
    + &cl, &tv1, &tv2, &a) == 4) {
    + clock_seq = cl & 0x3FFF;
    + last.tv_sec = tv1;
    + last.tv_usec = tv2;
    + adjustment = a;
    + }
    + }
    +
    if ((last.tv_sec == 0) && (last.tv_usec == 0)) {
    get_random_bytes(&clock_seq, sizeof(clock_seq));
    clock_seq &= 0x3FFF;
    last = tv;
    last.tv_sec--;
    }
    +
    +try_again:
    + gettimeofday(&tv, 0);
    if ((tv.tv_sec < last.tv_sec) ||
    ((tv.tv_sec == last.tv_sec) &&
    (tv.tv_usec < last.tv_usec))) {
    @@ -279,6 +317,16 @@ try_again:
    last = tv;
    }

    + if (state_fd > 0) {
    + rewind(state_f);
    + ftruncate(state_fd, 0);
    + fprintf(state_f, "clock: %04x tv: %lu %lu adj: %d\n",
    + clock_seq, last.tv_sec, last.tv_usec, adjustment);
    + fflush(state_f);
    + rewind(state_f);
    + lockf(state_fd, F_ULOCK, 0);
    + }
    +
    clock_reg = tv.tv_usec*10 + adjustment;
    clock_reg += ((unsigned long long) tv.tv_sec)*10000000;
    clock_reg += (((unsigned long long) 0x01B21DD2) << 32) + 0x13814000;
    @@ -289,7 +337,81 @@ try_again:
    return 0;
    }

    -void uuid_generate_time(uuid_t out)
    +static int read_all(int fd, char *buf, size_t count)
    +{
    + ssize_t ret;
    + int c = 0;
    +
    + memset(buf, 0, count);
    + while (count > 0) {
    + ret = read(fd, buf, count);
    + if (ret < 0) {
    + if ((errno == EAGAIN) || (errno == EINTR))
    + continue;
    + return -1;
    + }
    + count -= ret;
    + buf += ret;
    + c += ret;
    + }
    + return c;
    +}
    +
    +
    +#define OP_TIME 2
    +#define OP_RANDOM 3
    +
    +/*
    + * Try using the uuidd daemon to generate the UUID
    + *
    + * Returns 0 on success, non-zero on failure.
    + */
    +static int get_uuid_via_daemon(int op, uuid_t out)
    +{
    +#define SOCKET_PATH "/var/run/uuidd.sock"
    +
    + char c;
    + int s;
    + ssize_t ret;
    + uint32_t reply_len = 0;
    + struct sockaddr_un srv_addr;
    +
    + if ((s = socket(AF_UNIX, SOCK_STREAM, 0)) < 0)
    + return -1;
    +
    + srv_addr.sun_family = AF_UNIX;
    + strcpy(srv_addr.sun_path, SOCKET_PATH);
    +
    + if (connect(s, (const struct sockaddr *) &srv_addr,
    + sizeof(struct sockaddr_un)) < 0) {
    + close(s);
    + return -1;
    + }
    + c = op;
    + ret = write(s, &c, 1);
    + if (ret < 1) {
    + close(s);
    + return -1;
    + }
    +
    + ret = read_all(s, (char *) &reply_len, sizeof(reply_len));
    + if (ret < 0) {
    + close(s);
    + return -1;
    + }
    + if (reply_len != 16) {
    + close(s);
    + return -1;
    + }
    +
    + ret = read_all(s, out, reply_len);
    +
    + close(s);
    +
    + return ((ret == 16) ? 0 : -1);
    +}
    +
    +void uuid__generate_time(uuid_t out)
    {
    static unsigned char node_id[6];
    static int has_init = 0;
    @@ -316,7 +438,16 @@ void uuid_generate_time(uuid_t out)
    uuid_pack(&uu, out);
    }

    -void uuid_generate_random(uuid_t out)
    +void uuid_generate_time(uuid_t out)
    +{
    + if (get_uuid_via_daemon(OP_TIME, out) == 0)
    + return;
    +
    + uuid__generate_time(out);
    +}
    +
    +
    +void uuid__generate_random(uuid_t out)
    {
    uuid_t buf;
    struct uuid uu;
    @@ -329,6 +460,13 @@ void uuid_generate_random(uuid_t out)
    uuid_pack(&uu, out);
    }

    +void uuid_generate_random(uuid_t out)
    +{
    + /* No real reason to use the daemon for random uuid's -- yet */
    + uuid__generate_random(out);
    +}
    +
    +
    /*
    * This is the generic front-end to uuid_generate_random and
    * uuid_generate_time. It uses uuid_generate_random only if
    diff --git a/misc/Makefile.in b/misc/Makefile.in
    index db18985..8ca7af6 100644
    --- a/misc/Makefile.in
    +++ b/misc/Makefile.in
    @@ -16,10 +16,10 @@ INSTALL = @INSTALL@

    SPROGS= mke2fs badblocks tune2fs dumpe2fs blkid logsave \
    $(E2IMAGE_PROG) @FSCK_PROG@
    -USPROGS= mklost+found filefrag
    +USPROGS= mklost+found filefrag uuidd
    SMANPAGES= tune2fs.8 mklost+found.8 mke2fs.8 dumpe2fs.8 badblocks.8 \
    e2label.8 findfs.8 blkid.8 $(E2IMAGE_MAN) \
    - logsave.8 filefrag.8 @FSCK_MAN@
    + logsave.8 filefrag.8 uuidd.8 @FSCK_MAN@
    FMANPAGES= mke2fs.conf.5

    UPROGS= chattr lsattr uuidgen
    @@ -33,6 +33,7 @@ MKE2FS_OBJS= mke2fs.o util.o profile.o prof_err.o default_profile.o
    CHATTR_OBJS= chattr.o
    LSATTR_OBJS= lsattr.o
    UUIDGEN_OBJS= uuidgen.o
    +UUIDD_OBJS= uuidd.o
    DUMPE2FS_OBJS= dumpe2fs.o
    BADBLOCKS_OBJS= badblocks.o
    E2IMAGE_OBJS= e2image.o
    @@ -144,6 +145,10 @@ uuidgen: $(UUIDGEN_OBJS) $(DEPLIBUUID)
    @echo " LD $@"
    @$(CC) $(ALL_LDFLAGS) -o uuidgen $(UUIDGEN_OBJS) $(LIBUUID) $(LIBINTL)

    +uuidd: $(UUIDD_OBJS) $(DEPLIBUUID)
    + @echo " LD $@"
    + @$(CC) $(ALL_LDFLAGS) -o uuidd $(UUIDD_OBJS) $(LIBUUID) $(LIBINTL)
    +
    dumpe2fs: $(DUMPE2FS_OBJS) $(DEPLIBS) $(DEPLIBS_E2P) $(DEPLIBUUID)
    @echo " LD $@"
    @$(CC) $(ALL_LDFLAGS) -o dumpe2fs $(DUMPE2FS_OBJS) $(LIBS) \
    @@ -213,6 +218,10 @@ logsave.8: $(DEP_SUBSTITUTE) $(srcdir)/logsave.8.in
    @echo " SUBST $@"
    @$(SUBSTITUTE_UPTIME) $(srcdir)/logsave.8.in logsave.8

    +uuidd.8: $(DEP_SUBSTITUTE) $(srcdir)/uuidd.8.in
    + @echo " SUBST $@"
    + @$(SUBSTITUTE_UPTIME) $(srcdir)/uuidd.8.in uuidd.8
    +
    chattr.1: $(DEP_SUBSTITUTE) $(srcdir)/chattr.1.in
    @echo " SUBST $@"
    @$(SUBSTITUTE_UPTIME) $(srcdir)/chattr.1.in chattr.1
    @@ -239,7 +248,8 @@ installdirs:
    $(DESTDIR)$(root_sbindir) $(DESTDIR)$(bindir) \
    $(DESTDIR)$(man1dir) $(DESTDIR)$(man8dir) \
    $(DESTDIR)$(man1dir) $(DESTDIR)$(man5dir) \
    - $(DESTDIR)$(libdir) $(DESTDIR)/$(root_sysconfdir)
    + $(DESTDIR)$(libdir) $(DESTDIR)/$(root_sysconfdir) \
    + $(DESTDIR)/etc/init.d

    install: all $(SMANPAGES) $(UMANPAGES) installdirs
    @for i in $(SPROGS); do \
    @@ -304,6 +314,7 @@ install: all $(SMANPAGES) $(UMANPAGES) installdirs
    $(INSTALL_DATA) $(srcdir)/mke2fs.conf \
    $(DESTDIR)$(root_sysconfdir)/mke2fs.conf; \
    fi
    + $(INSTALL_SCRIPT) $(srcdir)/uuidd.rc $(DESTDIR)/etc/init.d/uuidd

    install-strip: install
    @for i in $(SPROGS); do \
    @@ -350,6 +361,7 @@ uninstall:
    if cmp -s $(srcdir)/mke2fs.conf $(DESTDIR)/$(root_sysconfdir)/mke2fs.conf; then \
    $(RM) $(DESTDIR)/$(root_sysconfdir)/mke2fs.conf; \
    fi
    + $(RM) -f $(DESTDIR)/etc/init.d/uuidd

    clean:
    $(RM) -f $(SPROGS) $(USPROGS) $(UPROGS) $(UMANPAGES) $(SMANPAGES) \
    diff --git a/misc/uuidd.8.in b/misc/uuidd.8.in
    new file mode 100644
    index 0000000..779996d
    --- /dev/null
    +++ b/misc/uuidd.8.in
    @@ -0,0 +1,78 @@
    +.\" -*- nroff -*-
    +.\" Copyright 2007 by Theodore Ts'o. All Rights Reserved.
    +.\" This file may be copied under the terms of the GNU Public License.
    +.\"
    +.TH UUIDD 8 "@E2FSPROGS_MONTH@ @E2FSPROGS_YEAR@" "E2fsprogs version @E2FSPROGS_VERSION@"
    +.SH NAME
    +uuidd \- UUID generation daemon
    +.SH SYNOPSIS
    +.B uuidd
    +[
    +.B \-d
    +]
    +[
    +.B \-p
    +.I pidfile
    +]
    +[
    +.B \-s
    +.I socketpath
    +]
    +
    +.B uuidd
    +[
    +.B \-r
    +|
    +.B \-t
    +]
    +[
    +.B \-s
    +.I socketpath
    +]
    +
    +.B uuidd \-k
    +.SH DESCRIPTION
    +The
    +.B uuidd
    +daemon is used by the UUID library to generate
    +universally unique identifiers (UUIDs), especially time-based UUID's
    +in a secure and guaranteed-unique fashion, even in the face of large
    +numbers of threads trying to grab UUID's running on different CPU's.
    +.SH OPTIONS
    +.TP
    +.B \-d
    +Run
    +.B uuidd
    +in debugging mode. This prevents uuidd from running as a daemon.
    +.TP
    +.B \-k
    +If a currently uuidd daemon is running, kill it.
    +.TP
    +.BI \-p " pidfile"
    +Specify the pathname where the pid file should be written. By default,
    +the pid file is written to /var/run/uuidd.pid.
    +.TP
    +.BI \-s " socketpath"
    +Specify the pathname used for the unix-domain socket used by uuidd. By
    +qdefault, the pathname used is /var/run/uuidd.sock. This is primarily
    +for debugging purposes, since the pathname is hard-coded in the libuuid
    +library.
    +.TP
    +.B \-r
    +Test uuidd by trying to connect to a running uuidd daemon and
    +request it to return a random-based UUID.
    +.TP
    +.B \-t
    +Test uuidd by trying to connect to a running uuidd daemon and
    +request it to return a time-based UUID.
    +.SH AUTHOR
    +The
    +.B uuidd
    +daemon was written by Theodore Ts'o .
    +.SH AVAILABILITY
    +.B uuidd
    +is part of libuuid from the e2fsprogs package and is available from
    +http://e2fsprogs.sourceforge.net.
    +.SH "SEE ALSO"
    +.BR libuuid (3),
    +.BR uuidgen (1)
    diff --git a/misc/uuidd.c b/misc/uuidd.c
    new file mode 100644
    index 0000000..174140c
    --- /dev/null
    +++ b/misc/uuidd.c
    @@ -0,0 +1,331 @@
    +/*
    + * uuidd.c --- UUID-generation daemon
    + *
    + * Copyright (C) 2007 Theodore Ts'o
    + *
    + * %Begin-Header%
    + * This file may be redistributed under the terms of the GNU Public
    + * License.
    + * %End-Header%
    + */
    +
    +#include
    +#ifdef HAVE_STDLIB_H
    +#include
    +#endif
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#include
    +#ifdef HAVE_GETOPT_H
    +#include
    +#else
    +extern int getopt(int argc, char * const argv[], const char *optstring);
    +extern char *optarg;
    +extern int optind;
    +#endif
    +#include "uuid/uuid.h"
    +#include "nls-enable.h"
    +
    +char *socket_path = "/tmp/uuid.sock";
    +
    +static void usage(const char *progname)
    +{
    + fprintf(stderr, _("Usage: %s [-d] [-p pidfile] [-s socketpath]\n"),
    + progname);
    + fprintf(stderr, _(" %s [-r|t] [-s socketpath]\n"), progname);
    + fprintf(stderr, _(" %s -k\n"), progname);
    + exit(1);
    +}
    +
    +void create_daemon(const char *pidfile_path)
    +{
    + pid_t pid;
    + FILE *f;
    +
    + pid = fork();
    + if (pid == -1) {
    + perror("fork");
    + exit(1);
    + } else if (pid != 0) {
    + exit(0);
    + }
    +
    + close(0);
    + close(1);
    + close(2);
    + open("/dev/null", O_RDWR);
    + open("/dev/null", O_RDWR);
    + open("/dev/null", O_RDWR);
    +
    + chdir("/");
    + (void) setsid();
    +
    + f = fopen(pidfile_path, "w");
    + if (f) {
    + fprintf(f, "%d\n", getpid());
    + fclose(f);
    + }
    +}
    +
    +extern void uuid__generate_time(uuid_t out);
    +extern void uuid__generate_random(uuid_t out);
    +
    +void server_loop(char *socket_path, int debug, char *pidfile_path)
    +{
    + char op;
    + socklen_t fromlen;
    + int s, ns, len;
    + char reply_buf[1024];
    + uint32_t reply_len = 0;
    + struct sockaddr_un my_addr, from_addr;
    + uuid_t uu;
    + mode_t save_umask;
    +
    + if ((s = socket(AF_UNIX, SOCK_STREAM, 0)) < 0) {
    + fprintf(stderr, "Couldn't create unix stream socket: %s",
    + strerror(errno));
    + exit(1);
    + }
    +
    + /*
    + * Create the address we will be binding to.
    + */
    + my_addr.sun_family = AF_UNIX;
    + strcpy(my_addr.sun_path, socket_path);
    + (void) unlink(socket_path);
    + save_umask = umask(0);
    + if (bind(s, (const struct sockaddr *) &my_addr,
    + sizeof(struct sockaddr_un)) < 0) {
    + fprintf(stderr, "Couldn't bind unix socket %s: %s\n",
    + socket_path, strerror(errno));
    + exit(1);
    + }
    + umask(save_umask);
    +
    + if (listen(s, 5) < 0) {
    + fprintf(stderr, "Couldn't listen on unix socket %s: %s\n",
    + socket_path, strerror(errno));
    + exit(1);
    + }
    +
    + if (!debug) {
    + create_daemon(pidfile_path);
    + }
    +
    + while (1) {
    + fromlen = sizeof(from_addr);
    + ns = accept(s, (struct sockaddr *) &from_addr, &fromlen);
    + if (ns < 0) {
    + if ((errno == EAGAIN) || (errno == EINTR))
    + continue;
    + perror("accept");
    + exit(1);
    + }
    + len = read(ns, &op, 1);
    + if (len != 1) {
    + if (len < 0)
    + perror("read");
    + else
    + printf("Error reading from client, len = %d\n",
    + len);
    + close(ns);
    + continue;
    + }
    + printf("operation %d\n", op);
    + switch(op) {
    + case 0:
    + sprintf(reply_buf, "%d", getpid());
    + reply_len = strlen(reply_buf)+1;
    + break;
    + case 1:
    + sprintf(reply_buf, "3"); /* Max valid op */
    + reply_len = strlen(reply_buf)+1;
    + break;
    + case 2:
    + uuid__generate_time(uu);
    + memcpy(reply_buf, uu, sizeof(uu));
    + reply_len = sizeof(uu);
    + break;
    + case 3:
    + uuid__generate_random(uu);
    + memcpy(reply_buf, uu, sizeof(uu));
    + reply_len = sizeof(uu);
    + break;
    + }
    + write(ns, &reply_len, sizeof(reply_len));
    + write(ns, reply_buf, reply_len);
    + close(ns);
    + }
    +}
    +
    +int read_all(int fd, char *buf, size_t count)
    +{
    + ssize_t ret;
    + int c = 0;
    +
    + memset(buf, 0, count);
    + while (count > 0) {
    + ret = read(fd, buf, count);
    + if (ret < 0) {
    + if ((errno == EAGAIN) || (errno == EINTR))
    + continue;
    + return -1;
    + }
    + count -= ret;
    + buf += ret;
    + c += ret;
    + }
    + return c;
    +}
    +
    +int call_daemon(char *socket_path, int op, char *buf, int buflen,
    + const char **err_context)
    +{
    + char c;
    + int s;
    + ssize_t ret;
    + uint32_t reply_len = 0;
    + struct sockaddr_un srv_addr;
    +
    + if ((s = socket(AF_UNIX, SOCK_STREAM, 0)) < 0) {
    + if (err_context)
    + *err_context = "socket";
    + return -1;
    + }
    +
    + srv_addr.sun_family = AF_UNIX;
    + strcpy(srv_addr.sun_path, socket_path);
    +
    + if (connect(s, (const struct sockaddr *) &srv_addr,
    + sizeof(struct sockaddr_un)) < 0) {
    + if (err_context)
    + *err_context = "connect";
    + close(s);
    + return -1;
    + }
    +
    + c = op;
    + ret = write(s, &c, 1);
    + if (ret < 1) {
    + if (err_context)
    + *err_context = "write";
    + close(s);
    + return -1;
    + }
    +
    + ret = read_all(s, (char *) &reply_len, sizeof(reply_len));
    + if (ret < 0) {
    + if (err_context)
    + *err_context = "read count";
    + close(s);
    + return -1;
    + }
    + if (reply_len > buflen) {
    + if (err_context)
    + *err_context = "response too big";
    + close(s);
    + return -1;
    + }
    + ret = read_all(s, buf, reply_len);
    +
    + close(s);
    +
    + return ret;
    +}
    +
    +
    +#define DO_TYPE_TIME 2
    +#define DO_TYPE_RANDOM 3
    +
    +int main(int argc, char **argv)
    +{
    + int c;
    + int debug = 0;
    + int do_type = 0;
    + int do_kill = 0;
    + int ret;
    + char *socket_path = "/var/run/uuidd.sock";
    + char *pidfile_path = "/var/run/uuidd.pid";
    + uuid_t uu;
    + const char *err_context;
    + char str[37];
    +
    + while ((c = getopt (argc, argv, "dkp:s:tr")) != EOF) {
    + switch (c) {
    + case 'd':
    + debug++;
    + break;
    + case 'k':
    + do_kill++;
    + break;
    + case 'p':
    + pidfile_path = optarg;
    + break;
    + case 's':
    + socket_path = optarg;
    + break;
    + case 't':
    + do_type = DO_TYPE_TIME;
    + break;
    + case 'r':
    + do_type = DO_TYPE_RANDOM;
    + break;
    + default:
    + usage(argv[0]);
    + }
    + }
    + if (do_type) {
    + ret = call_daemon(socket_path, do_type, (char *) &uu,
    + sizeof(uu), &err_context);
    + if (ret < 0) {
    + printf("Error calling uuidd daemon (%s): %s\n",
    + err_context, strerror(errno));
    + exit(1);
    + }
    + if (ret != sizeof(uu)) {
    + printf("Unexpected reply length from server %d\n",
    + ret);
    + exit(1);
    + }
    + uuid_unparse(uu, str);
    +
    + printf("%s\n", str);
    + exit(0);
    + }
    +
    + /*
    + * Check to make sure there isn't another daemon running already
    + */
    + ret = call_daemon(socket_path, 0, str, sizeof(str), 0);
    + if (ret > 0) {
    + if (do_kill) {
    + do_kill = atoi(str);
    + if (do_kill > 0) {
    + ret = kill(do_kill, SIGTERM);
    + if (ret < 0) {
    + fprintf(stderr,
    + "Couldn't kill uuidd running "
    + "at pid %d: %s\n", do_kill,
    + strerror(errno));
    + exit(1);
    + }
    + printf("Killed uuidd running at pid %d\n",
    + do_kill);
    + }
    + exit(0);
    + }
    + printf("uuidd daemon already running at pid %s\n", str);
    + exit(1);
    + }
    + if (do_kill)
    + exit(0); /* Nothing to kill */
    +
    + server_loop(socket_path, debug, pidfile_path);
    + return 0;
    +}
    diff --git a/misc/uuidd.rc b/misc/uuidd.rc
    new file mode 100644
    index 0000000..73c067a
    --- /dev/null
    +++ b/misc/uuidd.rc
    @@ -0,0 +1,54 @@
    +#! /bin/sh -e
    +### BEGIN INIT INFO
    +# Provides: uuidd
    +# Required-Start: $time $local_fs
    +# Required-Stop: $time $local_fs
    +# Default-Start: 2 3 4 5
    +# Default-Stop: 0 1 6
    +# Short-Description: uuidd daemon
    +# Description: Init script for the uuid generation daemon
    +### END INIT INFO
    +#
    +# Author: "Theodore Ts'o"
    +#
    +set -e
    +
    +PATH=/bin:/usr/bin:/sbin:/usr/sbin
    +DAEMON=/usr/sbin/uuidd
    +
    +test -x $DAEMON || exit 0
    +
    +. /lib/lsb/init-functions
    +
    +case "$1" in
    + start)
    + log_daemon_msg "Starting uuid generator" "uuidd"
    + start_daemon $DAEMON
    + log_end_msg $?
    + ;;
    + stop)
    + log_daemon_msg "Stopping uuidd generator" "uuidd"
    + killproc $DAEMON
    + log_end_msg $?
    + ;;
    + status)
    + if pidofproc $DAEMON >& /dev/null ; then
    + echo "$DAEMON is running";
    + exit 0;
    + else
    + echo "$DAEMON is NOT running";
    + if test -f /var/run/uuidd.pid; then exit 2; fi
    + exit 3;
    + fi
    + ;;
    + force-reload|restart)
    + $0 stop
    + $0 start
    + ;;
    + *)
    + echo "Usage: /etc/init.d/uuidd {start|stop|restart|force-reload}"
    + exit 1
    + ;;
    +esac
    +
    +exit 0
    --
    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/

+ Reply to Thread
Page 1 of 2 1 2 LastLast