SL-16024: Add ThreadSafeSchedule, a timestamped LLThreadSafeQueue.

ThreadSafeSchedule orders its items by timestamp, which can be passed either
implicitly or explicitly. The timestamp specifies earliest delivery time: an
item cannot be popped until that time.

Add initial tests.

Tweak the LLThreadSafeQueue base class to support ThreadSafeSchedule:
introduce virtual canPop() method to report whether the current head item is
available to pop. The base class unconditionally says yes, ThreadSafeSchedule
says it depends on whether its timestamp is still in the future.

This replaces the protected pop_() overload accepting a predicate. Rather than
explicitly passing a predicate through a couple levels of function call, use
canPop() at the level it matters. Runtime behavior that varies depending on
an object's leaf class is what virtual functions were invented for.

Give pop_() a three-state enum return so pop() can distinguish between "closed
and empty" (throws exception) versus "closed, not yet drained because we're
not yet ready to pop the head item" (waits).

Also break out protected tryPopUntil_() method, the body logic of
tryPopUntil(). The public method locks the data structure, the protected
method requires that its caller has already done so.

Add chrono.h with a more full-featured LL::time_point_cast() function than the
one found in <chrono>, which only converts between time_point durations, not
between time_points based on different clocks.

1 files changed, 65 insertions, 0 deletions

diff --git a/indra/llcommon/chrono.h b/indra/llcommon/chrono.h
new file mode 100644
index 0000000000..806e871892
--- /dev/null
+++ b/indra/llcommon/chrono.h
@@ -0,0 +1,65 @@
+/**
+ * @file   chrono.h
+ * @author Nat Goodspeed
+ * @date   2021-10-05
+ * @brief  supplement <chrono> with utility functions
+ * 
+ * $LicenseInfo:firstyear=2021&license=viewerlgpl$
+ * Copyright (c) 2021, Linden Research, Inc.
+ * $/LicenseInfo$
+ */
+
+#if ! defined(LL_CHRONO_H)
+#define LL_CHRONO_H
+
+#include <chrono>
+#include <type_traits>              // std::enable_if
+
+namespace LL
+{
+
+// time_point_cast() is derived from https://stackoverflow.com/a/35293183
+// without the iteration: we think errors in the ~1 microsecond range are
+// probably acceptable.
+
+// This variant is for the optimal case when the source and dest use the same
+// clock: that case is handled by std::chrono.
+template <typename DestTimePoint, typename SrcTimePoint,
+          typename std::enable_if<std::is_same<typename DestTimePoint::clock,
+                                               typename SrcTimePoint::clock>::value,
+                                  bool>::type = true>
+DestTimePoint time_point_cast(const SrcTimePoint& time)
+{
+    return std::chrono::time_point_cast<typename DestTimePoint::duration>(time);
+}
+
+// This variant is for when the source and dest use different clocks -- see
+// the linked StackOverflow answer, also Howard Hinnant's, for more context.
+template <typename DestTimePoint, typename SrcTimePoint,
+          typename std::enable_if<! std::is_same<typename DestTimePoint::clock,
+                                                 typename SrcTimePoint::clock>::value,
+                                  bool>::type = true>
+DestTimePoint time_point_cast(const SrcTimePoint& time)
+{
+    // The basic idea is that we must adjust the passed time_point by the
+    // difference between the clocks' epochs. But since time_point doesn't
+    // expose its epoch, we fall back on what each of them thinks is now().
+    // However, since we necessarily make sequential calls to those now()
+    // functions, the answers differ not only by the cycles spent executing
+    // those calls, but by potential OS interruptions between them. Try to
+    // reduce that error by capturing the source clock time both before and
+    // after the dest clock, and splitting the difference. Of course an
+    // interruption between two of these now() calls without a comparable
+    // interruption between the other two will skew the result, but better is
+    // more expensive.
+    const auto src_before = typename SrcTimePoint::clock::now();
+    const auto dest_now   = typename DestTimePoint::clock::now();
+    const auto src_after  = typename SrcTimePoint::clock::now();
+    const auto src_diff   = src_after - src_before;
+    const auto src_now    = src_before + src_diff / 2;
+    return dest_now + (time - src_now);
+}
+
+} // namespace LL
+
+#endif /* ! defined(LL_CHRONO_H) */