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.
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?
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);
