Page MenuHomePhabricator

[avalanche] add an OrphanProofPool class
ClosedPublic

Authored by PiRK on Apr 16 2021, 10:08.

Details

Reviewers
Fabien
deadalnix
Group Reviewers
Restricted Project
Commits
rABC58ab732c853a: [avalanche] add an OrphanProofPool class
Summary

This is a data structure designed to keep track of proofs using orphan
transactions as stake. The number of proofs we can store is limited to a
fixed size, and when this size is reached the oldest proofs is removed
when a new one is added.

Test Plan

ninja && ninja check

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
src/avalanche/peermanager.h
9

My thinking was that it is much more likely that the peermanager will use the orphan pool than the other way around.
I actually planned to have the peermanager deal with all the proofs (as it already does for validated proofs).

src/avalanche/peermanager.h
9

But maybe I can move SaltedProofIdHasher to proofid.h. That will solve issue.

Move SaltedProofIdHasher to proofid.h to make it available to both orphanproofpool and peermanager without additional includes.

Use +=

deadalnix requested changes to this revision.Apr 21 2021, 12:22
deadalnix added inline comments.
src/avalanche/orphanproofpool.h
56 ↗(On Diff #28243)

That's the first time I see a ++ used in this way. While this works, it's probably best done as two statements.

57 ↗(On Diff #28243)

If rit was incremented, then aren't you removing the wrong item here?

62 ↗(On Diff #28243)

I'm not sure what's going on in this loop, but it looks liek to me there is an off by one somewhere in there.

src/avalanche/test/orphanproofpool_tests.cpp
165 ↗(On Diff #28243)

First, this unit tests is very hard to follow, because it is not a unit test really, it is a ton of different unit tests merged in one.

But as far as I can tell, it only check proof with two different numbers of inputs, namely 1 and AVALANCHE_MAX_PROOF_STAKES. This make it so that proper stake count tracking is actually not tested (there could be an off by one in the loop as I suspect that the test would likely still pass).

You need to refactor this in such a way that it is obvious what is covered by the test - and, even more importantly what isn't. There are at least 2 or 3 tests waiting to be extracted from this.

This revision now requires changes to proceed.Apr 21 2021, 12:22
src/avalanche/orphanproofpool.h
62 ↗(On Diff #28243)

I'm not sure what's going on in this loop, but it looks liek to me there is an off by one somewhere in there.

I don't think it is off by one. We delete rit.base() because erase requires a forward iterator, and .base() is shifted by one in the correct direction for this to work.

But the rationale for using a reverse iterator is no longer valid, so I will simplify all of this by using a forward iterator.
Initially I put a limit on the number of proofs, not stakes. So it made sense to append new proofs to the front of the container, because it allowed us to use .resize for the trimming operation.

Append new proof to the end of the container, use a forward iterator for trimming from the front, use the fact that erase already returns an iterator to the next element (no need to increment the iterator again).

Add an assertion to the constructor to ensure the size limit is always enough to contain at least one proof, which allows to simply trimToMaximumSize (no need to check for it == proofs_by_sequence.end()).

I still need to refactor the unit tests.

PiRK planned changes to this revision.Apr 21 2021, 15:11

refactor the unit test so that any proof size can be tested, increase the number of tested proof sizes

Split the test into proofpool_add and proofpool_remove.

We now test for more proof sizes and for pools containing various proof sizes.

deadalnix requested changes to this revision.Apr 24 2021, 00:01

You shouldn't put all the method in the header file. No need to recompile them in every module where they are included, unless they are trivial and you want the optimizer to see that.

src/avalanche/orphanproofpool.h
17 ↗(On Diff #28248)
using result_type = ProofId;
24 ↗(On Diff #28248)
using ProofContainer = ...;
57 ↗(On Diff #28248)

That looks more reasonable than the previous iteration.

66 ↗(On Diff #28248)

Even if this is stupid, it is expected that the pool will still work properly. So I really don't see why this needs to crash the node.

74 ↗(On Diff #28248)

Why do you need to insert the proof in this way? proofs.insert(proof) or something doesn't work? Also, if you are taking ownership of the proof, just take it by value.

src/avalanche/test/orphanproofpool_tests.cpp
38 ↗(On Diff #28248)

You are baking the assumption that all proof are of the same stake. You generally don't want to bake too many assumptions in the code.

90 ↗(On Diff #28248)

This is not testing the boundaries condition of the removal. Start with what the test should tests instead of what it does (hint: proofpool_add_variable_size is about what it does). Once you ask yourself what needs to be tested, then the test and test case become obvious. Start with the problem.

This revision now requires changes to proceed.Apr 24 2021, 00:01
This comment was removed by Mengerian.

Address most comments. Use using instead of typedef. Simplify proof insertion, don't use .get<by_sequence>() inderection before inserting a now proof. Take proof by value in addProof.
Remove assertion in constructor to allow for a pool size smaller than the largest possible proof, add a simple unit test for this case.

Don't put all the methods in the header file, add a .cpp file.

Some work remains to be done on the unit tests.

PiRK planned changes to this revision.Apr 26 2021, 15:07

improve the test that adds variables sized proofs to actually check that the number of proofs and number of stakes are exactly as expected.

Make the checkPoolSize helper function a local lambda function to each suite that uses it, because each suite can have different assumptions about proofs sizes.

deadalnix requested changes to this revision.Apr 29 2021, 12:16
deadalnix added inline comments.
src/avalanche/orphanproofpool.cpp
16 ↗(On Diff #28293)

Are you sure this is noexcept? The C++ runtime will hard crash the program here if an exception is thrown. Unless this is something that multi_index guarantees and something that you actually need, then I suggest leaving it off. It seems to me to be unlikely to matter considering you are already looping in there.

19 ↗(On Diff #28293)

Does it really make sense to copy the proof here? I don't think it does.

38 ↗(On Diff #28293)

Why is proof id passed by const ref in the previous function and by value in that one? One of the two must be wrong.

src/avalanche/test/orphanproofpool_tests.cpp
22 ↗(On Diff #28293)

static ?

27 ↗(On Diff #28293)

It doesn't look like this is used anywhere.

67 ↗(On Diff #28293)

Just like for remove_proofs, this is unable to check the overflow behavior properly.

91 ↗(On Diff #28293)

So this seems to be checking the eviction behavior, except it doesn't really check boundary condition - or at least, it doesn't ensure that the boundary conditions are tested.

127 ↗(On Diff #28293)

The size seems to be the only thing that you use in the queue, so why keep a copy of the proof around?

153 ↗(On Diff #28293)

Because al the proof are the same size, you do not check that the size if kept track of accurately. The pool could always remove 42, or remove the size of another proof, that you wouldn't know. This test looks like it is testing something, but it really isn't.

185 ↗(On Diff #28293)

This is an excellent test, but what is it testing? It is testing what happens when you add a proof larger than the pool. This is what the test name should reflect.

This revision now requires changes to proceed.Apr 29 2021, 12:16

Start working on unit tests review:

  • remove unused variable script
  • improve remove_proofs to add proofs of various sizes so that we can control which one is actually removed
  • don't keep unneccessay copies of proofs in various tests, when only the ID (and in one intance the size) is needed
  • add a fail_to_add_same_proof_twice test, remove that test from another test (which removes the need to store the proof)
  • rename small_pool -> add_proof_larger_than_pool
  • add a simple pool_starts_empty test

Remove noexcept, don't make an unecessary copy in addProof, make removeProof take a constant reference as paramater like getProof

TODO: improve add_variable_sizes, maybe remove add_constant_sizes or make it simpler so that it doesn't attempt to test what it cannot really test

PiRK planned changes to this revision.Apr 29 2021, 15:44

rename the add_variable_size test, make sure it covers a case in which the pool is filled to maximum capacity.
Remove the test that add constant sized proofs. I do not think it adds anything in terms of behavior tested, compared with the variable sized proofs test. So better to get rid of it to avoid future maintenance work.

I'm not sure what other boundary cases should be considered. The only real boundaries I can think off happen with pools that are smaller than some proofs, which we should not ever use in production (I think the assert in the constructor should have been kept, to make sure of that).

Failed tests logs:

====== Bitcoin ABC functional tests: abc_mining_basic.py ======

------- Stdout: -------
2021-04-30T10:50:29.111000Z TestFramework (INFO): Initializing test directory /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210430_104612/abc_mining_basic_670
2021-04-30T10:50:29.677000Z TestFramework (ERROR): Assertion failed
Traceback (most recent call last):
  File "/work/test/functional/test_framework/test_framework.py", line 126, in main
    self.run_test()
  File "/work/test/functional/abc_mining_basic.py", line 142, in run_test
    self.run_for_node(self.nodes[1], MINER_FUND_LEGACY_ADDR)
  File "/work/test/functional/abc_mining_basic.py", line 80, in run_for_node
    assert_equal(len(coinbase['vout']), 1)
  File "/work/test/functional/test_framework/util.py", line 60, in assert_equal
    for arg in (thing1, thing2) + args)))
AssertionError: not(2 == 1)
2021-04-30T10:50:29.728000Z TestFramework (INFO): Stopping nodes
2021-04-30T10:50:29.829000Z TestFramework (WARNING): Not cleaning up dir /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210430_104612/abc_mining_basic_670
2021-04-30T10:50:29.829000Z TestFramework (ERROR): Test failed. Test logging available at /work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210430_104612/abc_mining_basic_670/test_framework.log
2021-04-30T10:50:29.829000Z TestFramework (ERROR): 
2021-04-30T10:50:29.830000Z TestFramework (ERROR): Hint: Call /work/test/functional/combine_logs.py '/work/abc-ci-builds/build-debug/test/tmp/test_runner_₿₵_  _20210430_104612/abc_mining_basic_670' to consolidate all logs
2021-04-30T10:50:29.830000Z TestFramework (ERROR): 
2021-04-30T10:50:29.830000Z TestFramework (ERROR): If this failure happened unexpectedly or intermittently, please file a bug and provide a link or upload of the combined log.
2021-04-30T10:50:29.830000Z TestFramework (ERROR): https://github.com/Bitcoin-ABC/bitcoin-abc/issues
2021-04-30T10:50:29.830000Z TestFramework (ERROR):

Each failure log is accessible here:
Bitcoin ABC functional tests: abc_mining_basic.py

rebase (unrelated CI failure)

deadalnix requested changes to this revision.May 3 2021, 01:56
deadalnix added inline comments.
src/avalanche/test/orphanproofpool_tests.cpp
47 ↗(On Diff #28332)

Are the counter maintained properly through this process?

105 ↗(On Diff #28332)

Maybe this is checking boundaries conditions, maybe not. There is no way to really know, except by checking the values provided and what happens with them, but even if this ends up testing everything, it'll do so up to the point someone change something and then it doesn't. this is extremely fragile.

You must test boundary conditions.

109 ↗(On Diff #28332)

If you are going to make this constant size, just use an array.

123 ↗(On Diff #28332)

This is 2 lines, you don't really make anything more readable by factoring this out, especially since parameters are not taken in explicitly, so you got all kind of action at a distance magic going on. Exactly what you do not want for a test.

131 ↗(On Diff #28332)

What does this achieve?

135 ↗(On Diff #28332)

Don't keep accounting. Just tell the goddamn test what is the value you expect.

156 ↗(On Diff #28332)

This is what a good test looks like.

This revision now requires changes to proceed.May 3 2021, 01:56
This comment has been deleted.

revert accidental change when trying to update D9469

PiRK planned changes to this revision.May 3 2021, 09:10

remove all accounting, make the tests simpler and more explicit

Fabien added inline comments.
src/avalanche/test/orphanproofpool_tests.cpp
109 ↗(On Diff #28339)

Nit: remove a

This revision is now accepted and ready to land.May 4 2021, 16:12

fix nit in comment (no code touched)

This revision was automatically updated to reflect the committed changes.