fuzz: Introduce CallOneOf helper to replace switch-case

MarcoFalke commented at 11:53 am on January 2, 2021: member

The current switch (fuzzed_data_provider.ConsumeIntegralInRange<int>(0, nn)) { case 0: ... case 1: ... case nn: ... has several problems:

It makes it hard to review newly added targets, because it requires manual counting of cases
It makes it hard to update a target, because updating all case labels is trivial, but tedious to review and causes merge conflicts
Updating the target raises the question whether the case labels should be preserved to not invalidate the existing fuzz inputs format. Fuzz input format might already change implicitly on every commit, so this isn’t something worthwhile to pursue. Edit: This pull doesn’t fix this problem.

Fix all issues by adding a new CallOneOf helper

MarcoFalke commented at 11:54 am on January 2, 2021: member

I’ll update the remaining fuzz targets once this has one or two Concept ACKs

hebasto commented at 12:01 pm on January 2, 2021: member

I’ll update the remaining fuzz targets once this has one or two Concept ACKs

Concept ACK.

* It makes it hard to update a target, because updating all case labels is trivial, but tedious to review and causes merge conflicts

It will be tedious to review only this pull :)

DrahtBot added the label Tests on Jan 2, 2021

MarcoFalke added the label Refactoring on Jan 2, 2021

MarcoFalke force-pushed on Jan 2, 2021

theStack commented at 3:54 pm on January 2, 2021: member

Concept ACK!

It will be tedious to review only this pull :)

With ignored whitespace (-w or --ignore-all-space) the diff actually looks quite straight-forward to review.

DrahtBot commented at 9:22 pm on January 2, 2021: member

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

Conflicts

Reviewers, this pull request conflicts with the following ones:

#20729 (p2p: standardize on outbound-{full, block}-relay connection type naming by jonatack)
#20715 (util: Add ArgsManager::GetCommand() and use it in bitcoin-wallet by MarcoFalke)
#19825 (rpc: simpler setban and new ban manipulation commands by dhruv)
#19713 (tests: fix -fsanitize=integer complaints by Crypt-iQ)
#16545 (refactor: Implement missing error checking for ArgsManager flags by ryanofsky)

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.

MarcoFalke force-pushed on Jan 2, 2021

ajtowns commented at 1:33 am on January 3, 2021: member

Concept ACK.

Where a case statement previously had a return; this will need to have an abort_loop = true; escape instead, which seems like no big deal.

I’m not a fan of “Fuzz input format might already change implicitly on every commit, so this isn’t something worthwhile to pursue.” – changing the fuzz input format invalidates the code coverage of the qa assets corpus, so it seems like we should try to minimise fuzz input format changes to me. But I think this makes dealing with that easier anyway: to have it behave stably when cases are added or removed I think you could do something like:

0    const size_t call_index{ConsumeIntegral<size_t>}();
1    if (call_index < size) return callables[call_index]();

and have an auto noop = [] () deleted_case { return; } place holder for deleting cases that aren’t at the end?

I was kind of expecting to see a recursive template function here – something like:

 0    template<typename... Cases>
 1    void CallOneOf(size_t selection, Cases... cases);
 2    template<typename T, typename... Cases>
 3    void CallOneOf(size_t selection, T case0, Cases... cases)
 4    {
 5        if (selection == 0) return case0();
 6        else return CallOneOf(selection - 1, cases...);
 7    }
 8    template<>
 9    void CallOneOf(size_t selection) { return; }
10
11    template<typename... Cases>
12    void CallOneOf(FDP& fdp, Cases... cases) {
13        size_t call_index = fdp.ConsumeIntegral<size_t>();
14        return CallOneOf(call_index, cases...);
15    }

Not sure the selection - 1 stuff would get optimised into a switch equivalent though, but it might be worth checking if it’s any better than the std::function indirection.

MarcoFalke commented at 7:50 am on January 3, 2021: member

Coverage:

MarcoFalke commented at 8:17 am on January 3, 2021: member

Where a case statement previously had a return; this will need to have an abort_loop = true; escape instead, which seems like no big deal.

Good point, but a return at that scope generally means that fuzzing will end for the current input. This is very rare and the only return I could find inside a switch was a return inside a CConnman::ForEach lambda, which obviously needs to be kept as is. Conversely, and more importantly for review here, any break inside a switch that isn’t inside another loop or switch will need to be replace by return.

I’m not a fan of “Fuzz input format might already change implicitly on every commit, so this isn’t something worthwhile to pursue.” – changing the fuzz input format invalidates the code coverage of the qa assets corpus, so it seems like we should try to minimise fuzz input format changes to me. But I think this makes dealing with that easier anyway: to have it behave stably when cases are added or removed I think you could do something like:

Ok, I see that my pull doesn’t solve the question whether seeds should be invalidated or not. Maybe it is best to answer this in a separate discussion. Before it was possible to invalidate or not invalidate seeds on a case-by-case basis and with this pull, it is possible, too.

Edit: Let’s discuss this in #20837 .

I was kind of expecting to see a recursive template function here – something like:

~~The recursive template would invalidate all seeds, no? This pull is tagged with “refactoring”, so the goal is that behavior doesn’t change.~~ Edit. No it doesn’t change the format if done correctly.

MarcoFalke force-pushed on Jan 3, 2021

MarcoFalke commented at 12:10 pm on January 3, 2021: member

Removed std::function indirection as requested by @ajtowns . Thanks!

in src/test/fuzz/util.h:46 in fa12a5d69b outdated

40+{
41+    constexpr size_t call_size{sizeof...(callables)};
42+    static_assert(call_size >= 1);
43+    const size_t call_index{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, call_size - 1)};
44+
45+    size_t i{0};

MarcoFalke commented at 12:11 pm on January 3, 2021:

Note: I couldn’t figure out how to make i evaluate at compile time, but I presume that -O1 already flattens this out.

MarcoFalke commented at 1:58 pm on January 3, 2021:

turns out -O1 isn’t enough for clang, but -O2 seems to do it: https://godbolt.org/z/Pz1YGv

ajtowns commented at 0:11 am on January 4, 2021:

You can evaluate i at compile time with more recursive templates:

 0template <size_t i>
 1inline void CallNthOf(size_t n) { }
 2
 3template <size_t i, typename Callable, typename... Callables>
 4inline void CallNthOf(size_t n, Callable callable, Callables... callables)
 5{
 6    switch(n) {
 7    case i:
 8        callable();
 9        break;
10    }
11    CallNthOf<i+1>(n, callables...);
12}

and then do return CallNthOf<0>(call_index, callables...). But it looks to me like clang -O1 doesn’t even do inlining, so doesn’t seem like there’s any reason to poke at this further?

Very impressed that you got it equivalent to a switch though!!

(EDIT: switch is cooler than if :)

MarcoFalke commented at 11:03 am on January 4, 2021:

Closing discussion for now because there is nothing left to do right now

jnewbery commented at 12:14 pm on January 3, 2021: member

Strong concept ACK. Thanks for doing this! Merge conflicts in the fuzz files seem to be very common, so eliminating the majority of them in this way would be a big win.

jonatack commented at 10:50 am on January 4, 2021: member

For a second I thought you were adding Call of Duty into bitcoin. This is a great idea. Concept ACK.

laanwj commented at 3:11 pm on January 7, 2021: member

This is much more elegant! Concept/quick skim code review ACK.

DrahtBot added the label Needs rebase on Jan 7, 2021

practicalswift commented at 8:52 pm on January 10, 2021: contributor

Concept ACK: much better! Thanks!

Will review.

fuzz: Introduce CallOneOf helper to replace switch-case

Can be reviewed with --ignore-all-space

fa75d40ef8

MarcoFalke force-pushed on Jan 11, 2021

in src/test/fuzz/util.h:47 in fa75d40ef8

42+    constexpr size_t call_size{sizeof...(callables)};
43+    static_assert(call_size >= 1);
44+    const size_t call_index{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(0, call_size - 1)};
45+
46+    size_t i{0};
47+    return ((i++ == call_index ? callables() : void()), ...);

jnewbery commented at 9:42 am on January 11, 2021:

No need for an explicit return statement if the return type is void:

0    ((i++ == call_index ? callables() : void()), ...);

I think that’s clearer since you’re not actually returning anything from the fold expression.

promag commented at 9:46 am on January 11, 2021:

TIL.

MarcoFalke commented at 10:00 am on January 11, 2021:

I wanted to keep it to enforce that only void functions can be called. Though, the ternary operator already enforces that.

In the future someone might want to extend this for non-void functions, e.g. a ConstructOneOf(...) could create and return a type constructed according to one of several construction rules).

Will leave as-is for now. Happy to remove if I need to force-push.

jnewbery commented at 10:08 am on January 11, 2021:

Yes, not a big deal. Can be left like this or updated if you have to touch the branch again.

in src/test/fuzz/banman.cpp:54 in fa75d40ef8

94+                                ConsumeBanTimeOffset(fuzzed_data_provider), fuzzed_data_provider.ConsumeBool());
95+                },
96+                [&] {
97+                    ban_man.ClearBanned();
98+                },
99+                [] {},

jnewbery commented at 9:47 am on January 11, 2021:

?

MarcoFalke commented at 9:56 am on January 11, 2021:

This is needed to preserve the “refactoring” nature of this pull request. Whether to remove or keep the noop should be discussed in #20837 .

MarcoFalke commented at 10:01 am on January 11, 2021:

(Note that case 3 does not exists, i.e. is a noop)

jnewbery commented at 10:07 am on January 11, 2021:

Ah! I missed that 3 and 10 don’t exist. Thanks.

in src/test/fuzz/banman.cpp:74 in fa75d40ef8

114+                    ban_man.GetBanned(banmap);
115+                },
116+                [&] {
117+                    ban_man.DumpBanlist();
118+                },
119+                [] {},

jnewbery commented at 9:47 am on January 11, 2021:

?

MarcoFalke commented at 9:56 am on January 11, 2021:

This is needed to preserve the “refactoring” nature of this pull request. Whether to remove or keep the noop should be discussed in #20837 .

MarcoFalke commented at 10:01 am on January 11, 2021:

(Note that case 10 does not exists, i.e. is a noop)

promag commented at 9:48 am on January 11, 2021: member

Concept ACK.

jnewbery commented at 9:54 am on January 11, 2021: member

This is excellent. Thanks for doing this @MarcoFalke!

utACK fa75d40ef866ef9ff8dc115e239ca6763aa23b06

MarcoFalke commented at 10:21 am on January 11, 2021: member

For a second I thought you were adding Call of Duty into bitcoin. This is a great idea. Concept ACK.

Call of Duty is already being fuzzed: https://twitter.com/NedWilliamson/status/1348432573836349441

DrahtBot removed the label Needs rebase on Jan 11, 2021

practicalswift commented at 6:26 pm on January 13, 2021: contributor

~Updating the target raises the question whether the case labels should be preserved to not invalidate the existing fuzz inputs format. Fuzz input format might already change implicitly on every commit, so this isn’t something worthwhile to pursue.~ Edit: This pull doesn’t fix this problem.

When using the switch (fuzzed_data_provider.ConsumeIntegralInRange<int>(0, N)) idiom it is worth noting that every time N is increased by one to accommodate for a new case all existing seeds are invalidated.

Example (all using the same fixed seed input in the form of a finite scream AAAAAAAAAAAAAAAAAAAAAAAAA):

 0FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 1) == 1
 1FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 2) == 2
 2FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 3) == 1
 3FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 4) == 0
 4FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 5) == 5
 5FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 6) == 2
 6FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 7) == 1
 7FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 8) == 2
 8FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 9) == 5
 9FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 10) == 10
10FuzzedDataProvider{buffer.data(), buffer.size()}.ConsumeIntegralInRange<int>(0, 11) == 5

One trick that can be used to tackle this is to choose from a larger range such as [0, 32] even if we only have say 12 case:s ([0, 11]). The non-matching numbers [12, 32] will simply be “ignored” by the coverage-guided fuzzer.

That way we’ll only have to invalidate existing seeds when we’ve exhausted the entire range [0, 32] with matching case:s. Then we can bump to [0, 64], and so on.

In other words: instead of invalidating every time we add a new case we’ll be invalidating every some-power-of-2:th time we add a new case :)

Perhaps that strategy could be incorporated in this PR?

MarcoFalke commented at 6:31 pm on January 13, 2021: member

Perhaps that strategy could be incorporated in this PR?

The pr is tagged with “refactoring”, so behaviour changes are not allowed. The suggestion can be discussed in #20837 and addressed in a follow-up pull request. The changes should be trivial based on this pr.

ajtowns commented at 9:10 am on January 14, 2021: member

ACK fa75d40ef866ef9ff8dc115e239ca6763aa23b06 - code review only

MarcoFalke merged this on Jan 14, 2021

MarcoFalke closed this on Jan 14, 2021

MarcoFalke deleted the branch on Jan 14, 2021

sidhujag referenced this in commit 21baf4c158 on Jan 15, 2021

DrahtBot locked this on Aug 16, 2022

fuzz: Introduce CallOneOf helper to replace switch-case #20828

Conflicts