On Wed, Aug 19, 2020 at 09:28:41PM -0500, Scott Cheloha wrote:
> Hi,
>
> I was auditing the tree for odd-looking time structure usage and I
> came across the UUID code in ldapd(8), uuid.c.
>
> time_cmp() is backwards. Or the caller is misusing it. One or the
> other. It returns -1 if tv1 exceeds tv2 but the comments in the
> caller indicate the opposite impression. I don't think this code has
> ever worked as intended.
>
> It would be a lot easier if we just threw the code out and used random
> UUIDs. After reading over the RFC it seems to me that time-based
> UUIDs are collision-prone. Their implementation is also complicated.
> Purely random UUIDs should effectively never collide and are trivial
> to implement.
RFC 4530, defining the entryUUID attribute, says this:
UUID are to be generated in accordance with Section 4 of [RFC4122].
In particular, servers MUST ensure that each generated UUID is unique
in space and time.
Which doesn't rule out random uuids at all. Is arc4random_buf() a better
attempt at ensuring the uuids are unique than doing complicated stuff with
clocks and mac addresses? Maybe. Windows has been generating random uuids
for about 20 years now.
>
> However, assuming we can't just use random UUIDs, here's an attempt at
> improving this code:
>
> - Use clock_gettime(2). With nanosecond resolution we don't need
> a 'counter'.
>
> - Reduce the scope of all the static state to uuid_create().
>
> - Shrink the loop. Just read the clock until it changes, then decide
> what to do re. seq_num. This is effectively what the example code in
> RFC 4122 does.
>
> I'm unsure what the right thing to do is if the system clock predates
> the UUID epoch (Oct 15 1582). My code just returns zero. Maybe we
> should just kill the daemon in that case? The UUIDv1 scheme breaks
> down if time is that seriously screwed up.
>
> Is there an active ldapd(8) person? Or at least someone with an
> ldapd(8) setup who can test this?
I'm kind of an active ldapd person, though I don't actually use it
actively. I can try this out if need be.
>
> Thoughts?
>
> Index: uuid.c
> ===================================================================
> RCS file: /cvs/src/usr.sbin/ldapd/uuid.c,v
> retrieving revision 1.6
> diff -u -p -r1.6 uuid.c
> --- uuid.c 26 Apr 2018 12:42:51 -0000 1.6
> +++ uuid.c 20 Aug 2020 01:44:00 -0000
> @@ -63,27 +63,8 @@
>
> #include "uuid.h"
>
> -static uint32_t seq_num;
> -static struct timeval last_time;
> -static int32_t counter;
> -static char nodeaddr[6];
> -
> enum { UUID_NODE_MULTICAST = 0x80 };
>
> -static int
> -time_cmp(struct timeval *tv1, struct timeval *tv2)
> -{
> - if (tv1->tv_sec > tv2->tv_sec)
> - return -1;
> - if (tv1->tv_sec < tv2->tv_sec)
> - return 1;
> - if (tv1->tv_usec > tv2->tv_usec)
> - return -1;
> - if (tv1->tv_usec < tv2->tv_usec)
> - return 1;
> - return 0;
> -}
> -
> static void
> get_node_addr(char *addr)
> {
> @@ -138,6 +119,40 @@ get_node_addr(char *addr)
> }
>
> /*
> + * A UUID v1 timestamp:
> + *
> + * - 60 bits.
> + * - Unsigned.
> + * - Epoch at Oct 15 1582 00:00:00 UTC.
> + * - Increments every 100 nanoseconds.
> + */
> +#define UUID_EPOCH_OFFSET 12219292800LL
> +#define UUID_TIME_MAX (1ULL << 60)
> +#define UUID_HZ 10000000LL
> +#define NSEC_PER_UUID_TICK 100LL
> +
> +static uint64_t
> +get_uuid_timestamp(void)
> +{
> + static const struct timespec min = { -UUID_EPOCH_OFFSET, 0 };
> + static const struct timespec max = {
> + UUID_TIME_MAX / UUID_HZ,
> + UUID_TIME_MAX % UUID_HZ * NSEC_PER_UUID_TICK
> + };
> + struct timespec utc;
> + uint64_t timestamp;
> +
> + clock_gettime(CLOCK_REALTIME, &utc);
> + if (timespeccmp(&utc, &min, <))
> + return 0;
> + if (timespeccmp(&max, &utc, <))
> + return UUID_TIME_MAX;
> + timestamp = (UUID_EPOCH_OFFSET + utc.tv_sec) * UUID_HZ;
> + timestamp += utc.tv_nsec / NSEC_PER_UUID_TICK;
> + return timestamp;
> +}
> +
> +/*
> * Creates a new UUID.
> */
>
> @@ -145,55 +160,32 @@ void
> uuid_create(afsUUID *uuid)
> {
> static int uuid_inited = 0;
> - struct timeval tv;
> - int ret, got_time;
> + static uint64_t last_time;
> + static uint32_t seq_num;
> + static char nodeaddr[6];
> uint64_t dce_time;
>
> if (uuid_inited == 0) {
> - gettimeofday(&last_time, NULL);
> + last_time = get_uuid_timestamp();
> seq_num = arc4random();
> get_node_addr(nodeaddr);
> uuid_inited = 1;
> }
>
> - gettimeofday(&tv, NULL);
> -
> - got_time = 0;
> + while ((dce_time = get_uuid_timestamp()) == last_time)
> + continue;
>
> - do {
> - ret = time_cmp(&tv, &last_time);
> - if (ret < 0) {
> - /* Time went backward, just inc seq_num and be done.
> - * seq_num is 6 + 8 bit field it the uuid, so let it wrap
> - * around. don't let it be zero.
> - */
> - seq_num = (seq_num + 1) & 0x3fff ;
> - if (seq_num == 0)
> - seq_num++;
> - got_time = 1;
> - counter = 0;
> - last_time = tv;
> - } else if (ret > 0) {
> - /* time went forward, reset counter and be happy */
> - last_time = tv;
> - counter = 0;
> - got_time = 1;
> - } else {
> -#define UUID_MAX_HZ (1) /* make this bigger fix you have larger tickrate */
> -#define MULTIPLIER_100_NANO_SEC 10
> - if (++counter < UUID_MAX_HZ * MULTIPLIER_100_NANO_SEC)
> - got_time = 1;
> - }
> - } while(!got_time);
> + if (dce_time < last_time) {
> + /* Time went backward, just inc seq_num and be done.
> + * seq_num is 6 + 8 bit field it the uuid, so let it wrap
> + * around. don't let it be zero.
> + */
> + seq_num = (seq_num + 1) & 0x3fff ;
> + if (seq_num == 0)
> + seq_num++;
> + }
>
> - /*
> - * now shift time to dce_time, epoch 00:00:00:00, 15 October 1582
> - * dce time ends year ~3400, so start to worry now
> - */
> -
> - dce_time = tv.tv_usec * MULTIPLIER_100_NANO_SEC + counter;
> - dce_time += ((uint64_t)tv.tv_sec) * 10000000;
> - dce_time += (((uint64_t)0x01b21dd2) << 32) + 0x13814000;
> + last_time = dce_time;
>
> uuid->time_low = dce_time & 0xffffffff;
> uuid->time_mid = 0xffff & (dce_time >> 32);
>
