refactor: Make FEELER_SLEEP_WINDOW type safe (std::chrono) #24974

MarcoFalke commented at 1:01 PM on April 25, 2022: member

This gets rid of the value*1000 manual conversion.

MarcoFalke added the label Refactoring on Apr 25, 2022

DrahtBot commented at 5:48 PM on April 25, 2022: contributor

The following sections might be updated with supplementary metadata relevant to reviewers and maintainers.

Conflicts

Reviewers, this pull request conflicts with the following ones:

#25619 (net: avoid overriding non-virtual ToString() in CService and use better naming by vasild)
#25203 (logging: update to severity-based logging by jonatack)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

naumenkogs commented at 1:54 PM on April 29, 2022: member

ACK fae94c6591231722f01ccde689f0b36febf824cc

MarcoFalke commented at 2:00 PM on April 29, 2022: member

@ajtowns You might be interested in (N)ACKing this change, based on the conversation in #24697 (review)

in src/net.cpp:1834 in fae94c6591 outdated

2151 | @@ -2151,12 +2152,11 @@ void CConnman::ThreadOpenConnections(const std::vector<std::string> connect)
2152 |          }
2153 |  
2154 |          if (addrConnect.IsValid()) {
2155 | -
2156 |              if (fFeeler) {
2157 |                  // Add small amount of random noise before connection to avoid synchronization.
2158 | -                int randsleep = GetRandInt(FEELER_SLEEP_WINDOW * 1000);
2159 | -                if (!interruptNet.sleep_for(std::chrono::milliseconds(randsleep)))

ajtowns commented at 3:49 PM on April 29, 2022:

I don't think it makes sense to pass in a time point here; even if we used sleep_until that would just end up doing now() + rand - now() which seems silly.

But, rather than parameterise by a duration; we could parameterise by a Clock:

    template <typename C=std::chrono::steady_clock>
    typename C::duration rand_uniform_duration(typename C::duration max) noexcept
    {
        assert(max.count() > 0);
        return typename C::duration{GetRand(max.count())};
    };

which would make it just be:

    if (!interruptNet.sleep_for(rng.rand_uniform_duration(FEELER_SLEEP_WINDOW)))

(That avoids the need for the common_type stuff too)

At least for me, steady_clock operates in nanoseconds, so the existing sleep_for(millis) doesn't work, but replacing the three CThreadInterrupt::sleep_for methods with a single one that accepts std::chrono::steady_clock::duration rel_time would fix that. Alternatively, so would:

    template <typename Dur>
    bool sleep_for(Dur rel_time)
    {
        return sleep_for_ms(std::chrono::duration_cast<std::chrono::milliseconds>(rel_time));
    }

MarcoFalke commented at 8:33 AM on April 30, 2022:

Thanks, changed

MarcoFalke force-pushed on Apr 30, 2022

in src/threadinterrupt.h:22 in fa9970a769 outdated

  18 | @@ -19,13 +19,12 @@
  19 |  class CThreadInterrupt
  20 |  {
  21 |  public:
  22 | +    using Clock = std::chrono::steady_clock;

MarcoFalke commented at 8:41 AM on April 30, 2022:

review note: https://eel.is/c++draft/thread.condition.condvar#24

fanquake requested review from ajtowns on May 6, 2022

fanquake requested review from naumenkogs on May 6, 2022

w0xlt approved

w0xlt commented at 5:03 PM on May 9, 2022: contributor

Code Review ACK https://github.com/bitcoin/bitcoin/pull/24974/commits/fa9970a769a2f03cd5c9b2f4a00e530d395d7ffb

DrahtBot added the label Needs rebase on May 10, 2022

MarcoFalke force-pushed on May 10, 2022

DrahtBot removed the label Needs rebase on May 10, 2022

w0xlt approved

w0xlt commented at 10:06 AM on May 10, 2022: contributor

reACK https://github.com/bitcoin/bitcoin/pull/24974/commits/fac6af70fd14c380a016152ce38c20158da03136

in src/random.h:249 in fac6af70fd outdated

 240 | +    template <typename Chrono>
 241 | +    typename Chrono::duration rand_uniform_duration(typename Chrono::duration range) noexcept
 242 | +    {
 243 | +        using Dur = typename Chrono::duration;
 244 | +        return range.count() > 0 ? /* interval [0..range) */ Dur{randrange(range.count())} :
 245 | +               range.count() < 0 ? /* interval (range..0] */ -Dur{randrange(-range.count())} :

sipa commented at 1:49 PM on May 10, 2022:

Why support negative ranges?

MarcoFalke commented at 1:59 PM on May 10, 2022:

Some call sites may use a negative range. For example in addr relay, the timestamp of some address messages is randomly pushed into the past.

Also, it seems safer when the alternative is either unspecified behaviour, or a crash.

sipa commented at 2:07 PM on May 10, 2022:

The behavior here still seems odd in those cases. I'd expect call sites that actually can result in negative range values to want "rand_uniform_duration(T)" to mean: "give me a uniform duration not exceeding T". If T is negative, that probably means just returning 0?

MarcoFalke commented at 2:14 PM on May 10, 2022:

Yeah, the interval is determined at run-time and the passed in value can either mean the start or the end of the interval, with the other value being 0.

I am not sure if mapping any negative value to a constant 0 is less confusing. And I couldn't find another solution that is well defined at run time (no unspecified behaviour, no crash).

sipa commented at 2:33 PM on May 10, 2022:

Yeah, I'm not objecting to this change. It just strikes me as bizarre semantics; the simplest interpretation of a range is specifying how wide the window of possible values is - and that simply cannot be negative.

An alternative is always returning range itself if it is <= 0. That at least satisfies the constraint "never return a value exceeding range", and probably works just as well for the intended call sites (who I suspect use to determine how long to wait)?

MarcoFalke commented at 2:50 PM on May 10, 2022:

Again, I am not sure that returning any constant is less confusing for a random function that took a non-zero input.

For reference, one potential call site would be:

addr.nTime = GetTime() - rng.randrange(nOneWeek) - nOneWeek;

This (and any other) call site can obviously be written without relying on a negative range, but we'd also need to avoid this with a compile error. Without consteval, this is probably only possible with some template magic?

ajtowns commented at 3:39 PM on May 10, 2022:

I don't think template magic works for this -- you get "non-type template parameter" errors trying to pass chrono::duration's as template parameters. I think you could do it with c++20 which allows "literal class types" as a non-type template parameter. https://en.cppreference.com/w/cpp/language/template_parameters

ajtowns commented at 3:59 PM on May 10, 2022:

Maybe if (Assume(range.count()) > 0) { return Dur{randrange...}; } else { return range; } ? I don't think we could make it a consteval function even with c++20, because rng.randrange() isn't going to be consteval?

naumenkogs commented at 6:33 AM on May 12, 2022:

It would be ideal to enforce non-negative at compile time, and then force every caller to switch to a non-negative construction.

While I don't think how this is possible, I don't have much preference for the behavior if the value is negative. It is indeed annoying. We're not making it worse at least. Perhaps status quo makes more sense in this case.

theuni commented at 2:46 PM on May 13, 2022:

Hmm, if I'm reading this right, this seems like quite an odd api to me. I'm not sure why passing a clock is necessary.

From what I can tell, you pass it a duration and a clock, and it gives you a new random duration in the clock's period. In other words.. we basically want a std::chrono::duration_cast which is hijacked and randomized. So why not use that api?

It'd look like (simplified for positive-only and untested):

template <class ToDuration, class Rep, class Period>
constexpr ToDuration rand_uniform_duration(const std::chrono::duration<Rep, Period>& d)
{
    auto max_ret = std::chrono::duration_cast<ToDuration>(d);
    auto rand_offset = ToDuration(randrange(d.count()));
    return max_ret - rand_offset;
}

Used like:

auto foo = rand_uniform_duration<std::chrono::milliseconds>(30s);

Or in this case:

auto foo = rand_uniform_duration<CThreadInterrupt::Clock::duration>(FEELER_SLEEP_WINDOW);

That way, we effectively communicate that we're randomizing in the target period as opposed to the provided one.

MarcoFalke commented at 3:02 PM on May 13, 2022:

I think a duration_cast is dangerous and not very useful here. Recall that the compiler will do the cast for you if it is safe to do. And in cases where it isn't safe, you are better off not calling this function in the first place.

I used clock, as it was suggested here: #24974 (review)

Though, I think durations should be fine, too.

theuni commented at 3:25 PM on May 13, 2022:

As @ajtowns and I discussed yesterday in the office, here's a quick attempt at compile-time checking (to side-step the question of negative durations) just for fun. It's not completely unreasonable imo.

Edit: Whoops, deleted, that was horribly broken.

MarcoFalke commented at 3:29 PM on May 13, 2022:

Interesting. I guess you'd still have to static_assert against implicit sign conversion when going from 64-bit unsigned to 64-bit signed.

theuni commented at 3:58 PM on May 13, 2022:

Ok, here's a full working test-case. Statically checked for non-negative, passed durations, and no duration_cast as @MarcoFalke suggested:

#include <chrono>
#include <cstdlib>
#include <cstdio>

long int randrange(uint64_t mod)
{
    auto ret = random() % mod;
    return ret;
}

template <typename Duration, typename Duration::rep Ticks>
struct static_duration
{
    using duration = Duration;
    static constexpr typename Duration::rep ticks = Ticks;
};

template <typename ToDuration, typename FromDuration, typename FromDuration::rep Ticks>
constexpr ToDuration rand_uniform_duration(const static_duration<FromDuration, Ticks>&)
{
    static_assert(Ticks >= 0);
    FromDuration from(Ticks);
    ToDuration max_ret{from};
    return ToDuration{randrange(max_ret.count())};
}

static constexpr static_duration<std::chrono::seconds, 30> foo;
static constexpr static_duration<std::chrono::seconds, -30> negfoo;

int main()
{
    srand(time(nullptr));
    auto bar = rand_uniform_duration<std::chrono::milliseconds>(foo);
    // auto negbar = rand_uniform_duration<std::chrono::milliseconds>(negfoo); // Compiler error
    
    printf("duration: %ld\n", bar.count());
}

Edit: I cleaned up a little. Made the static rep duration type dependent on the duration's. Added a static assert and an example compile error.

Edit2: Require a static_duration rather than its parts and no need to subtract.

theuni commented at 4:03 PM on May 13, 2022:

Interesting. I guess you'd still have to static_assert against implicit sign conversion when going from 64-bit unsigned to 64-bit signed.

~Right, I guess you'd want to accept a int64_t and static_assert that it's > 0 instead.~ Fixed above.

Feel free to disregard or clean up and use :)

MarcoFalke commented at 3:42 PM on May 27, 2022:

Ok, glad we figured out how to implement this, but is this something that is actually preferable? :sweat_smile:

theuni commented at 12:52 AM on May 28, 2022:

🤷 It's perfectly expressive and constexpr, so there's not much downside other than (the syntax and) the emitted per-constant symbol. The obvious realistic downside being that it's kinda overkill...

But maybe not it's a bad thing to be able to express only-positive-time more generally? So maybe that's the test... is there somewhere else where it might be useful to describe time constants as positive only?

ajtowns commented at 4:52 PM on May 31, 2022:

I'm happy (or about equally unhappy...) with any of the approaches really; and I guess we'd want to switch to C++20 syntax when that's available either way, so shrug from me. @sipa?

MarcoFalke commented at 4:59 PM on May 31, 2022:

I think there is a minimal, theoretical advantage to disallowing negative values, as the inverting the most negative value is an integer sanitizer violation. Though, this shouldn't affect execution of a program that is not compiled with the integer sanitizer and shouldn't happen in practise either.

What is the "C++20" syntax, if I may ask?

ajtowns commented at 5:22 PM on May 31, 2022:

With C++20 you can pass a duration to a template, and then do a static_assert on its value, so you'd write rand_uniform_duration<dur>() instead of rand_uniform_duration(dur) and get the compile-time check.

MarcoFalke commented at 2:32 PM on June 1, 2022:

Oh, with dur you mean static_duration, not std::chrono::duration?

I can't get it to work with std::chrono::duration:

#include <chrono>

using namespace std::chrono_literals;

struct FRC {
    template <std::chrono::duration range>
    auto rand_uniform_delay(auto time) {
        return time + rand_uniform_duration<decltype(time)::duration, range>();
    }
    template <typename Duration, std::chrono::duration range>
    Duration rand_uniform_duration() noexcept {
        static_assert(range.count() > 0);
        return Duration{randrange(range.count())};
    }
};

int main() {
    FRC frc;
    frc.rand_uniform_delay<9h>(std::chrono::sys_seconds{1s});
    frc.rand_uniform_duration<std::chrono::seconds, 9h>();
}

https://godbolt.org/z/8Y868s98K

ajtowns commented at 5:42 PM on June 1, 2022:

Hmm, I'm not really sure why it doesn't work (well, std::chrono::duration needs template parameters and stuff, but even after fixing that it doesn't work)

Here's something that does, via a wrapper class. Not sure that's any better than @theuni's c++17 compatible wrapper. https://godbolt.org/z/nnKx4fde5

#include <chrono>

int64_t randrange(int64_t x) { return x / 2; }

using namespace std::chrono_literals;

template<typename dur=std::chrono::seconds>
struct template_duration
{
    const int64_t count;
    using duration = dur;
    constexpr template_duration(dur f) : count{f.count()} { }
    constexpr dur to_dur() const { return dur{count}; }
};
template<typename dur>
constexpr template_duration<dur> tmpl_dur(const dur& d) { return {d}; }

struct FRC {
    template <typename Duration, auto range>
    Duration rand_uniform_duration() noexcept {
        static_assert(range.count > 0);
        return Duration{randrange(Duration{range.to_dur()}.count())};
    }

    template <auto range, typename X>
    X rand_uniform_delay(X time) noexcept {
        return time + rand_uniform_duration<typename X::duration, range>();
    }    
};

int main() {
    FRC frc;
    constexpr auto DELAY_HOURS{tmpl_dur(8h)};
    auto now = std::chrono::sys_seconds{1s};
    frc.rand_uniform_duration<std::chrono::seconds, DELAY_HOURS>();
    frc.rand_uniform_delay<DELAY_HOURS>(now);
}

MarcoFalke commented at 3:09 PM on July 13, 2022:

Happy to use different std-lib syntax, but anything that requires a wrapper class that re-implements stuff seems overkill to solve a problem that doesn't exist.

DrahtBot added the label Needs rebase on May 12, 2022

MarcoFalke force-pushed on May 27, 2022

MarcoFalke commented at 3:42 PM on May 27, 2022: member

Rebased only for now

DrahtBot removed the label Needs rebase on May 27, 2022

DrahtBot added the label Needs rebase on Jul 7, 2022

Expose underlying clock in CThreadInterrupt

Overloading sleep_for is not needed, as

* seconds and minutes can be converted to milliseconds by the compiler,
  not needing a duration_cast
* std::condition_variable::wait_for will convert milliseconds to the
  duration type of the underlying clock

So simply expose the clock.

fa3b3cb9b5

refactor: Make FEELER_SLEEP_WINDOW type safe (std::chrono) fa74e726c4

MarcoFalke force-pushed on Jul 13, 2022

DrahtBot removed the label Needs rebase on Jul 13, 2022

MarcoFalke commented at 3:04 PM on July 13, 2022: member

Rebased

naumenkogs commented at 11:56 AM on July 26, 2022: member

utACK fa74e726c414f5f7a1e63126a69463491f66e0ec

fanquake requested review from dergoegge on Jul 26, 2022

fanquake requested review from mzumsande on Jul 26, 2022

dergoegge commented at 2:00 PM on July 26, 2022: member

Code review ACK fa74e726c414f5f7a1e63126a69463491f66e0ec

fanquake merged this on Jul 26, 2022

fanquake closed this on Jul 26, 2022

MarcoFalke deleted the branch on Jul 26, 2022

sidhujag referenced this in commit 95d3e91c72 on Jul 27, 2022

bitcoin locked this on Jul 26, 2023