Skip to contentSkip to conversation

Implement continuous clock handling for time based UUIDs

PATCH Applied Michael Trapp 2 participants 3 messages Jun 20, 2022 – Jul 7, 2022 Util-Linux package

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 Implement continuous clock handling for time based UUIDs

In a uuidd setup, the daemon is a singleton and can maintain it's own resources for time based UUID generation. This requires a dedicated 'clock sequence range' but does not need any further lock/update of the LIBUUID_CLOCK_FILE from uuidd. The range of available clock values is extended by a continuous handling of the clock updates - instead of updating the value to the current timestamp, it is incremented by the number of requested UUIDs.
---

Updated version
cont clock handling needs to be activated with '-C' or '--cont-clock'. default value of max_clock_offset is 7200 seconds.
custom value of max_clock_offset can be defined by optional argument. maximum value of max_clock_offest is 365 days.

 libuuid/src/gen_uuid.c  | 91 ++++++++++++++++++++++++++++++++++++++---
 libuuid/src/libuuid.sym |  1 +
 libuuid/src/uuidd.h     |  1 +
 misc-utils/uuidd.8.adoc |  3 ++
 misc-utils/uuidd.c      | 54 +++++++++++++++++++++---
 5 files changed, 140 insertions(+), 10 deletions(-)
libuuid/src/gen_uuid.c +86 -5
index 805b40d90..807dcd115 100644
@@ -209,6 +209,8 @@ static int get_node_id(unsigned char *node_id)
 
 /* Assume that the gettimeofday() has microsecond granularity */
 #define MAX_ADJUSTMENT 10
+/* Reserve a clock_seq value for the 'continuous clock' implementation */
+#define CLOCK_SEQ_CONT 0
 
 /*
  * Get clock from global sequence clock counter.
@@ -275,8 +277,10 @@ static int get_clock(uint32_t *clock_high, uint32_t *clock_low,
 	}
 
 	if ((last.tv_sec == 0) && (last.tv_usec == 0)) {
-		ul_random_get_bytes(&clock_seq, sizeof(clock_seq));
-		clock_seq &= 0x3FFF;
+		do {
+			ul_random_get_bytes(&clock_seq, sizeof(clock_seq));
+			clock_seq &= 0x3FFF;
+		} while (clock_seq == CLOCK_SEQ_CONT);
 		gettimeofday(&last, NULL);
 		last.tv_sec--;
 	}
@@ -286,7 +290,9 @@ try_again:
 	if ((tv.tv_sec < last.tv_sec) ||
 	    ((tv.tv_sec == last.tv_sec) &&
 	     (tv.tv_usec < last.tv_usec))) {
-		clock_seq = (clock_seq+1) & 0x3FFF;
+		do {
+			clock_seq = (clock_seq+1) & 0x3FFF;
+		} while (clock_seq == CLOCK_SEQ_CONT);
 		adjustment = 0;
 		last = tv;
 	} else if ((tv.tv_sec == last.tv_sec) &&
@@ -331,6 +337,64 @@ try_again:
 	return ret;
 }
 
+/*
+ * Get current time in 100ns ticks.
+ */
+static uint64_t get_clock_counter(void)
+{
+	struct timeval tv;
+	uint64_t clock_reg;
+
+	gettimeofday(&tv, NULL);
+	clock_reg = tv.tv_usec*10;
+	clock_reg += ((uint64_t) tv.tv_sec) * 10000000ULL;
+
+	return clock_reg;
+}
+
+/*
+ * Get continuous clock value.
+ *
+ * Return -1 if there is no further clock counter available,
+ * otherwise return 0.
+ *
+ * This implementation doesn't deliver clock counters based on
+ * the current time because last_clock_reg is only incremented
+ * by the number of requested UUIDs.
+ * max_clock_offset is used to limit the offset of last_clock_reg.
+ */
+static int get_clock_cont(uint32_t *clock_high,
+			  uint32_t *clock_low,
+			  int num,
+			  uint32_t max_clock_offset)
+{
+	/* 100ns based time offset according to RFC 4122. 4.1.4. */
+	const uint64_t reg_offset = (((uint64_t) 0x01B21DD2) << 32) + 0x13814000;
+	static uint64_t last_clock_reg = 0;
+	uint64_t clock_reg;
+
+	if (last_clock_reg == 0)
+		last_clock_reg = get_clock_counter();
+
+	clock_reg = get_clock_counter();
+	if (max_clock_offset) {
+		uint64_t clock_offset = max_clock_offset * 10000000ULL;
+		if (last_clock_reg < (clock_reg - clock_offset))
+			last_clock_reg = clock_reg - clock_offset;
+	}
+
+	clock_reg += MAX_ADJUSTMENT;
+
+	if ((last_clock_reg + num) >= clock_reg)
+		return -1;
+
+	*clock_high = (last_clock_reg + reg_offset) >> 32;
+	*clock_low = last_clock_reg + reg_offset;
+	last_clock_reg += num;
+
+	return 0;
+}
+
 #if defined(HAVE_UUIDD) && defined(HAVE_SYS_UN_H)
 
 /*
@@ -403,7 +467,7 @@ static int get_uuid_via_daemon(int op __attribute__((__unused__)),
 }
 #endif
 
-int __uuid_generate_time(uuid_t out, int *num)
+static int __uuid_generate_time_internal(uuid_t out, int *num, uint32_t cont_offset)
 {
 	static unsigned char node_id[6];
 	static int has_init = 0;
@@ -423,7 +487,14 @@ int __uuid_generate_time(uuid_t out, int *num)
 		}
 		has_init = 1;
 	}
-	ret = get_clock(&clock_mid, &uu.time_low, &uu.clock_seq, num);
+	if (cont_offset) {
+		ret = get_clock_cont(&clock_mid, &uu.time_low, *num, cont_offset);
+		uu.clock_seq = CLOCK_SEQ_CONT;
+		if (ret != 0)	/* fallback to previous implpementation */
+			ret = get_clock(&clock_mid, &uu.time_low, &uu.clock_seq, num);
+	} else {
+		ret = get_clock(&clock_mid, &uu.time_low, &uu.clock_seq, num);
+	}
 	uu.clock_seq |= 0x8000;
 	uu.time_mid = (uint16_t) clock_mid;
 	uu.time_hi_and_version = ((clock_mid >> 16) & 0x0FFF) | 0x1000;
@@ -432,6 +503,16 @@ int __uuid_generate_time(uuid_t out, int *num)
 	return ret;
 }
 
+int __uuid_generate_time(uuid_t out, int *num)
+{
+	return __uuid_generate_time_internal(out, num, 0);
+}
+
+int __uuid_generate_time_cont(uuid_t out, int *num, uint32_t cont_offset)
+{
+	return __uuid_generate_time_internal(out, num, cont_offset);
+}
+
 /*
  * Generate time-based UUID and store it to @out
  *
libuuid/src/libuuid.sym +1 -0
index 342453368..96372a857 100644
@@ -60,6 +60,7 @@ global:
 UUIDD_PRIVATE {
 global:
 	__uuid_generate_time;
+	__uuid_generate_time_cont;
 	__uuid_generate_random;
 local:
 	*;
libuuid/src/uuidd.h +1 -0
index fbe821ff3..f76acc8b2 100644
@@ -49,6 +49,7 @@
 #define UUIDD_MAX_OP			UUIDD_OP_BULK_RANDOM_UUID
 
 extern int __uuid_generate_time(uuid_t out, int *num);
+extern int __uuid_generate_time_cont(uuid_t out, int *num, uint32_t cont);
 extern int __uuid_generate_random(uuid_t out, int *num);
 
 #endif /* _UUID_UUID_H */
misc-utils/uuidd.8.adoc +3 -0
index 49e7b6359..8eee3e91b 100644
@@ -24,6 +24,9 @@ The *uuidd* daemon is used by the UUID library to generate universally unique id
 
 == OPTIONS
 
+*-C*, *--cont-clock* _opt_arg_::
+Activate continuous clock handling for time based UUIDs. *uuidd* could use all possible clock values, beginning with the daemon's start time. The optional argument can be used to set a value for the max_clock_offset. This gurantees, that a clock value of a UUID will always be within the range of the max_clock_offset. '-C' or '--cont-clock' enables the feature with a default max_clock_offset of 2 hours. '-C<NUM>[hd]' or '--cont-clock=<NUM>[hd]' enables the feature with a max_clock_offset of NUM seconds. In case of an appended h or d, the NUM value is read in hours or days. The minimum value is 60 seconds, the maximum value is 365 days.
+
 *-d*, *--debug*::
 Run *uuidd* in debugging mode. This prevents *uuidd* from running as a daemon.
 
misc-utils/uuidd.c +49 -5

116 lines not on this page · raw message

Signature · 1 line
2.32.1 (Apple Git-133)
maintainer
#1 lore raw
Quoted 9 lines · Michael Trapp

In a uuidd setup, the daemon is a singleton and can maintain it's own resources for time based UUID generation. This requires a dedicated 'clock sequence range' but does not need any further lock/update of the LIBUUID_CLOCK_FILE from uuidd. The range of available clock values is extended by a continuous handling of the clock updates - instead of updating the value to the current timestamp, it is incremented by the number of requested UUIDs.
---

Quoted 5 lines

Updated version
cont clock handling needs to be activated with '-C' or '--cont-clock'. default value of max_clock_offset is 7200 seconds.
custom value of max_clock_offset can be defined by optional argument. maximum value of max_clock_offest is 365 days.

Looks good, thanks! I'll apply the patch later this week.

BTW, by the reset interval is 7200 seconds? Why not 3600? :-)

Karel

Signature · 2 lines
 Karel Zak  <[email protected]>
 http://karelzak.blogspot.com
maintainer Applied
#2 lore raw
In reply to Michael Trapp
Quoted 6 lines · Michael Trapp
 libuuid/src/gen_uuid.c  | 91 ++++++++++++++++++++++++++++++++++++++---
 libuuid/src/libuuid.sym |  1 +
 libuuid/src/uuidd.h     |  1 +
 misc-utils/uuidd.8.adoc |  3 ++
 misc-utils/uuidd.c      | 54 +++++++++++++++++++++---
 5 files changed, 140 insertions(+), 10 deletions(-)

Applied, thanks!

Signature · 2 lines
 Karel Zak  <[email protected]>
 http://karelzak.blogspot.com