How to do clocks right?

[thejohnfreeman]

I want to discuss how we handle clocks. First, we have beast::abstract_clock, which is like a std::chrono clock except that now() is a non-static member function instead of a static member function. The idea is that components that need a clock will take a reference to a beast::abstract_clock, which can be chosen at runtime, instead of calling a global, static function like std::chrono::steady_clock::now(), that can't be switched at runtime.

There is a subtype of beast::abstract_clock called beast::manual_clock that lets a caller manually advance the clock. This capability is required for effectively testing components that depend on a clock, much like the ability to choose a seed is required for effectively testing components that depend on randomness. It is used in many of our tests, e.g. for all the aged containers, which take a beast::abstract_clock& in their constructor.

However, there is also a global function, beast::get_abstract_clock(), that returns a non-const reference to a statically-allocated beast::abstract_clock. This function is called in several places, e.g. the constructor of NetworkOpsImp, which passes it to RCLConsensus. These calls cannot be intercepted to use a manual clock, which means the components using them cannot be tested effectively. (There are many more reasons why NetworkOpsImp is not testable in its current state, but it's not the only example, and right now I'm focused on removing this obstacle.)

In fact, there are three calls of beast::get_abstract_clock() in src/ripple, one of which is in wrapper ripple::stopwatch(), which itself has 23 more calls. There are even more direct calls into standard library clocks, e.g. std::chrono::system_clock::now(). Some are through type aliases, which makes them difficult to count.

Am I perceiving this situation correctly? That our direct calls to beast::get_abstract_clock() and std::chrono::{system_clock,steady_clock,high_resolution_clock}::now() make our components untestable?

If it is, then I see two ways to fix it:

• Make every component that needs a clock take and hold a reference to a beast::abstract_clock the way the aged containers do. This is not my preferred approach. It is parameter drilling, which I hate, and it would expand the blast radius to more components than the next method, which I prefer.
• Use a thread-local global for the clock. In fact, a different global for each clock (system clock, steady clock, seconds clock, and any other clock). All callers can get the time through a static global function, they don't have to hold any references, and you can easily substitute manual clocks in tests.

But it's not just our components we need to worry about. We need to be able to give manual clocks to all of our time-sensitive dependencies. The only one that comes to mind is Boost.Asio, but it is everywhere. I found an explanation from the creator on how to define and pass a manual clock for boost::asio::basic_deadline_timer, but we don't use that. We use boost::asio::basic_waitable_timer, which accepts a different traits type parameter whose relationship to the one explained in the blog post is unclear to me.

Thoughts?

[HowardHinnant]

Nice summary!

An additional observation: beast::abstract_clock and its subtypes such as beast::manual_clock do not meet the Cpp17Clock requirements because of the non-static member now(). This doesn't make them bad clocks. But it does mean that these clocks can not be used in the std concurrency library. Examples include std::condition_variable::wait_until and std::this_thread::sleep_until.

So no clock is perfect, and sometimes we have to choose between testability and usability with the std concurrency library.

On a positive note, if we accidentally use a non-Cpp17Clock with the concurrency library, it is a compile-time error, not a run-time error. And we now have a trait to test for the Cpp17Clock requirements: std::is_clock.

[thejohnfreeman]

Good point about std concurrency. I see two options then for manual clocks.

1. Thread-local globals: Substitute clock types have a static now() method that returns the time point pointed-to by a non-const thread-local pointer. The time point can be std::atomic to make it thread-safe. Relaxed ordering should be sufficient, deferring synchronization to callers.

thread_local std::atomic<time_point>* now_;
struct manual_clock {
    static time_point now() {
        return now_->load(std::memory_order_relaxed);
    }
}

We must be careful passing these clocks to components like Boost.Asio. The clock's behavior depends on the thread in which it is called. If we do not carefully control the initialization and waking of worker threads, to make sure the correct clock is in place at the start of execution, then callers will read either the wrong time point (bug) or no time point (UB, likely segfault).

2. Static globals: Substitute clock types have a tag type parameter. Each instance has its own static non-const time point member, again atomic.

template <std::size_t id>
struct manual_clock {
    static std::atomic<time_point> now_;
    static time_point now() {
        return now_.load(std::memory_order_relaxed);
    }
}

The same clock type is no longer an interface to multiple clock values, but we must still be careful. Each test will be tied to a specific clock ID, and two tests with the same clock ID cannot execute concurrently. One possibly disqualifying disadvantage of this approach is that the clock type parameter needs to invade every context.

If performance is a concern and mutable clocks are not necessary in a build, then we can conditionally compile the substitute types as type aliases to the std types.

[Bronek]

In general I like being explicit with all the inputs (because that makes automated testing easier to manage) but you are right that for the clock it would be excessive. Putting it in a thread local static seems sensible to me.

[RichardAH]

Why not just a volatile word-aligned uint64_t that's updated by one thread, and can be read by any thread at any time? You get atomicity for free here.

Suppose the updating thread writes values X-1, X, X+1 in sequence. A reading thread might get X-1, X, or X+1 depending on how it's scheduled, but it will get one of those values. And for a clock this is fine? Am I missing something?

[thejohnfreeman]

We already have this clock, except it uses atomic instead of volatile. It is called basic_seconds_clock and I linked it in the opener. It does not address any of my concerns, however, the main one being testability. Further, it is not good for all situations, notably timings that are sub-second, which are very common in the code.

[RichardAH]

If it is explicitly atomic (i.e. std::atomic) then the compiler will insert LOCK instructions when doing code generation, and then that's not a lock-free clock. If you want finer resolution you can do this a number of ways, the easiest is just to count in increments of the scheduler, such as 15ms. You could also interpolate by using RDTSC. Finally, if you want to modify the behaviour of the clock for testing purposes you can just not start the updater thread and manually modify the word aligned uint64.

[thejohnfreeman]

We also have a manual clock. Did you read any of the discussion? Here's the TLDR: Show me an example of a manual clock that works with boost::asio::basic_waitable_timer and std::condition_variable::wait_until.

[RichardAH]

Tbh I think the abstractions are heavily overengineered here. A system clock is an incrementing integer. You make sure it increments at the right rate.

Can we just back peddle a bit here, do you understand why it's important that a multithreaded application has a lock free clock? Imagine a room with 10 people in it who are all working in parallel, but their work depends on glancing constantly at a hanging wall clock. Now imagine that they can't glance, and in order to read the clock they have to join a queue and read it one at a time. That's no longer multithreaded.

If you need help stuffing an actually lock-free clock into a bunch of these types so they work in deps, I can probably help. But I'll only do that if we agree we need a lock free clock.

[thejohnfreeman]

Yes, I can agree that we need a lock-free clock, but that's a solved problem. The basic_seconds_clock is lock-free, at least where we need it, the static now() method. Here is the Godbolt for basic_seconds_clock on x86-64 and the only lock is implicit on the xchg instruction for the atomic store in seconds_clock_thread::run. More importantly, there is no lock in basic_seconds_clock::now(). It does synchronize the static initialization, but once that is done, calls are fast and effectively:

        movzx   eax, BYTE PTR guard variable for basic_seconds_clock::now()::clk[rip]
        test    al, al
        jne     .L64
.L64:
        mov     rax, QWORD PTR basic_seconds_clock::now()::clk[rip+104]
        ret

We could eliminate the synchronization (which is just a load, test, jump) by explicitly handling initialization in main(), but I don't think it has significant performance impact because I don't think anyone is calling it in a tight loop.

Here is a simpler example that illustrates the xchg instruction for atomic store with the default sequentially-consistent memory ordering. The atomic load is a mov with no lock. I'm in favor of changing basic_seconds_clock to use release-acquire or relaxed memory ordering, both of which use mov for both atomic load and atomic store, but it's not a dealbreaker.

Separately, I don't believe the standard guarantees that std::steady_clock is lock-free, but I would be surprised if it is not in practice on x86.

Where are you seeing lock instructions? Can you show us how to replicate?