util: CBufferedFile fixes and unit test

LarryRuane commented at 6:58 pm on August 9, 2019: contributor

The CBufferedFile object guarantees its user is able to “rewind” the data stream (that’s being read from a file) up to a certain number of bytes, as specified by the user in the constructor. This guarantee is not honored due to a bug in the SetPos method.

Such rewinding is done in LoadExternalBlockFile() (currently the only user of this object), which deserializes a series of CBlock objects. If that function encounters something unexpected in the data stream, which is coming from a blocks/blk00???.dat file, it “rewinds” to an earlier position in the stream to try to get in sync again. The CBufferedFile object does not actually rewind its file offset; it simply repositions its internal offset, nReadPos, to an earlier position within the object’s private buffer; this is why there’s a limit to how far the user may rewind.

If LoadExternalBlockFile() needs to rewind (call blkdat.SetPos()), the stream may not be positioned as it should be, causing errors in deserialization. This need to rewind is probably rare, which is likely why this bug hasn’t been noticed already. But if this object is used elsewhere in the future, this could be a serious problem, especially as, due to the nature of the bug, the SetPos() sometimes works.

This PR adds a unit test for CBufferedFile that fails due to this bug. (Until now it has had no unit tests.) The unit test provides good documentation and examples for developers trying to understand LoadExternalBlockFile() and for future users of this object.

This PR also adds code to throw an exception from the constructor if the rewind argument is not less than the buffer size (since that doesn’t make any sense).

Finally, I discovered that the object is too restrictive in one respect: When the deserialization methods call this object’s read method, a check ensures that the number of bytes being requested is less than the size of the buffer (adjusting for the rewind size), else it throws an exception. This restriction is unnecessary; the object being deserialized can be larger than the buffer because multiple reads from disk can satisfy the request.

DrahtBot added the label Tests on Aug 9, 2019

fanquake added the label Utils/log/libs on Aug 9, 2019

in src/streams.h:737 in b1aee23057 outdated

733@@ -734,17 +734,21 @@ class CBufferedFile
734             return false;
735         size_t nBytes = fread((void*)&vchBuf[pos], 1, readNow, src);
736         if (nBytes == 0) {
737-            throw std::ios_base::failure(feof(src) ? "CBufferedFile::Fill: end of file" : "CBufferedFile::Fill: fread failed");
738-        } else {
739-            nSrcPos += nBytes;
740-            return true;
741+            throw std::ios_base::failure(feof(src) ?

promag commented at 9:26 am on August 10, 2019:

NACK this hunk, it only changes formatting.

in src/streams.h:748 in b1aee23057 outdated

748 
749 public:
750     CBufferedFile(FILE *fileIn, uint64_t nBufSize, uint64_t nRewindIn, int nTypeIn, int nVersionIn) :
751-        nType(nTypeIn), nVersion(nVersionIn), nSrcPos(0), nReadPos(0), nReadLimit(std::numeric_limits<uint64_t>::max()), nRewind(nRewindIn), vchBuf(nBufSize, 0)
752+        nType(nTypeIn), nVersion(nVersionIn), nSrcPos(0), nReadPos(0),
753+        nReadLimit(std::numeric_limits<uint64_t>::max()), nRewind(nRewindIn), vchBuf(nBufSize, 0)

promag commented at 9:27 am on August 10, 2019:

NACK this hunk, only splits the line in 2 lines.

in src/streams.h:809 in b1aee23057 outdated

811+        if (nSrcPos > bufsize && nPos < nSrcPos - bufsize) {
812+            // rewinding too far, rewind as far as possible
813+            nReadPos = nSrcPos - bufsize;
814             return false;
815-        } else if (nReadPos > nSrcPos) {
816+        }

promag commented at 9:35 am on August 10, 2019:

I’d keep elses.

in src/streams.h:808 in b1aee23057 outdated

803@@ -802,16 +804,19 @@ class CBufferedFile
804 
805     //! rewind to a given reading position
806     bool SetPos(uint64_t nPos) {
807-        nReadPos = nPos;
808-        if (nReadPos + nRewind < nSrcPos) {
809-            nReadPos = nSrcPos - nRewind;
810+        size_t bufsize = vchBuf.size();
811+        if (nSrcPos > bufsize && nPos < nSrcPos - bufsize) {

promag commented at 9:44 am on August 10, 2019:

I think this is wrong, vchBuf.size() if constant and the actual read position is obtained from nReadPos % vchBuf.size() - it’s a ring buffer.

LarryRuane commented at 6:32 am on August 12, 2019:

I checked this carefully, and I’m pretty sure it’s right, please check again. I did simplify it slightly (without changing the behavior) in the second commit; it’s now like this:

0if (nPos + bufsize < nSrcPos) {

This says that the distance from the new (requested) read position, nPos, to the source pointer, nSrcPos must be no greater than bufsize. If nPos is further back than that, it will be pointing to bytes from a later write pass across the buffer and will get data that’s too new. Maybe a small example will help. Suppose the file consists of a b c d e f g ... and the buffer is 5 bytes. After reading g (total of 7 bytes) from the file into the ring buffer, the buffer looks like this:

0[ f g c d e ]
1      ^
2      nSrcPos = 7

The nReadPos (file read position) can be in the range 2 through 7 and we will get correct data. If nReadPos is less than 2, let’s say it’s 1, then reading at that position should return b but will instead will return g, which is incorrect (g is too new). The smallest nReadPos can be is 2, which is 7 - 5 (nSrcPos - bufsize).

The existing SetPos() is wrong; it should not depend on nRewind. That variable is only needed during filling, and prevents nSrcPos from getting too far ahead of nReadPos, because if that happens, then nReadPos can’t back up. So, in this little example, if nRewind is 2, then Fill() will not let nSrcPos to get more than 5 (buffer size - rewind size) ahead of nReadPos. But, again, nRewind has no relevance to SetPos().

mzumsande commented at 3:20 pm on August 19, 2019:

I also think that the first check in SetPos() is incorrect. This does not lead to problems in production thanks to the initialization values of CBufferedFile vchBuf.size()=2*MAX_BLOCK_SERIALIZED_SIZE=8000000 and nRewind=MAX_BLOCK_SERIALIZED_SIZE+8=4000008 in LoadExternalBlockFile().

Accordingly, nSrcPos = vchBuf.size() - nRewind = 3999992 < nRewind after the first buffer fill and the (erroneous) condition nReadPos + nRewind < nSrcPos in SetPos() is never true.

When I change LoadExternalBlockFile() slightly by initializing CBufferedFile with nRewind= MAX_BLOCK_SERIALIZED_SIZE-8 instead of MAX_BLOCK_SERIALIZED_SIZE+8, the functional test feature_reindex fails because now above condition can be true. Since all blocks in this test are much smaller than the maximum block size, this shouldn’t happen.

LarryRuane commented at 0:01 am on August 20, 2019:

@mzumsande, it’s broken even with the current production initialization values. I made a temporary branch, https://github.com/LarryRuane/bitcoin/commit/bc9c987300782a7881edaabf7b7c5463a7688041, that simulates, after reading each block (during reindexing), what would happen if we really did need to rewind. (This temp branch doesn’t include the changes from this PR.) bitcoind --reindex failed pretty quickly (at line 4405).

The temp branch actually verifies two things, (1) the call to SetPos() returns true (the production code doesn’t look at the return value), which means that the requested position was accommodated (as it should always be in the current context), and, (2), after rewinding, we get the expected data (by reading one byte).

I ran the same test with the code in the current PR’s branch, and it doesn’t fail.

I think the easiest way to understand why the current code is broken is to note that Fill() can push nSrcPos far ahead of nReadPos. For best efficiency,Fill() always reads as much as it can from the file in a single read, so if there’s a lot of “runway” ahead of it (lots of space to the end of the buffer), it will read a lot. It may not go quite to the end of the buffer, if doing so would violate the rewind guarantee, but it can go much farther ahead of nReadPos than the rewind amount. Now look again at the current SetPos():

0if (nReadPos + nRewind < nSrcPos) {
1    nReadPos = nSrcPos - nRewind;
2    return false;
3}

This condition could easily be true if nSrcPos has gotten far ahead of nReadPos. But that doesn’t mean that nReadPos needs to be adjusted. Actually, this code could move nReadPos beyond the maximum position it’s ever had, meaning that it’s skipping data! You’re at the farthest position you’ve ever reached, say, offset 40, and you request to rewind to position 35, and you end up at position 45! The condition is just wrong.

mzumsande commented at 9:58 pm on September 10, 2019:

You are right, I was more trying to understand why reindexing currently works in spite of the wrong condition. With different initialization values even no-rewind uses of SetPos like SetPos(current_position) could fail.

promag commented at 9:45 am on August 10, 2019: member

Travis is failing https://travis-ci.org/bitcoin/bitcoin/jobs/569970060#L3130-L3131.

LarryRuane renamed this:
~~util: CBufferedFile fixes and unit test~~
[WIP] util: CBufferedFile fixes and unit test
on Aug 10, 2019

LarryRuane force-pushed on Aug 12, 2019

LarryRuane commented at 6:39 am on August 12, 2019: contributor

The second commit also adds a randomized test. It’s pretty common for the kind of code under scrutiny here (the CBufferedFile object) to have subtle off-by-one and boundary condition bugs. A functional unit test like the one in the first commit is good, but it’s hard to be sure the test covers all possible strange conditions. A random test will try many weird things that no person would ever think of.

I ran this random test several million iterations, which makes me extremely confident that the code under test is correct. Of course, whether the test code itself is correct is very crucial! So please review the test code, thanks.

LarryRuane renamed this:
~~[WIP] util: CBufferedFile fixes and unit test~~
util: CBufferedFile fixes and unit test
on Aug 12, 2019

practicalswift commented at 12:11 pm on August 12, 2019: contributor

@LarryRuane I haven’t looked at your changes yet but wanted to mention that you might want to check using contrib/devtools/test_deterministic_coverage.sh that the unit test is line coverage deterministic after this change.

Line coverage determinism is a necessary condition for meaningful line coverage measuring :-)

LarryRuane commented at 2:32 pm on August 12, 2019: contributor

@practicalswift, thanks, I don’t understand that script yet, but you reminded me that I have a question about the random test I wrote. It can trivially be made deterministic by seeding the random number generator at the beginning of the test. Would that be desirable, or not? It seems to me there are advantages either way. If the test is deterministic, then every time CI runs, it’s not testing anything new; there could be a bug that by chance isn’t uncovered (but would be by a different seed). On the other hand, if the test is non-deterministic, it’s possible that a CI run would randomly fail for reasons having nothing to do with the PR that’s causing CI to run. That would be very mysterious (at least until investigated).

If I had to decide, I’d say it’s better for the test to be deterministic. But I don’t know what the conventions are here. (Apologies in advance if this is documented somewhere.)

I’ll also try to understand the coverage tool, looks very interesting, thank you.

LarryRuane force-pushed on Aug 12, 2019

LarryRuane renamed this:
~~util: CBufferedFile fixes and unit test~~
[WIP] util: CBufferedFile fixes and unit test
on Aug 12, 2019

LarryRuane renamed this:
~~[WIP] util: CBufferedFile fixes and unit test~~
util: CBufferedFile fixes and unit test
on Aug 12, 2019

in src/test/streams_tests.cpp:396 in 3c874f5921 outdated

391+            case 3: {
392+                // Find a byte value (that is at or ahead of the current position).
393+                size_t find = currentOffset + InsecureRandRange(8);
394+                if (find >= fileSize)
395+                    find = fileSize - 1;
396+                bf.FindByte(find);

practicalswift commented at 7:43 am on August 14, 2019:

When testing this I encountered the following UBSan warning:

0test/streams_tests.cpp:396:29: runtime error: implicit conversion from type 'size_t' (aka 'unsigned long') of value 132 (64-bit, unsigned) to type 'char' changed the value to -124 (8-bit, signed)

laanwj commented at 11:12 am on August 14, 2019: member

It can trivially be made deterministic by seeding the random number generator at the beginning of the test. Would that be desirable, or not?

Deterministic tests are preferred in this project. No one really investigates individual random CI failures because there tends to be a lot of spurious failures that have nothing to do with the code, but with unreliability of the Travis platform such as timeouts.

MarcoFalke commented at 11:43 am on August 14, 2019: member

I think you have two options:

Pick a random seed, print/log it at the beginning of the test in some way
Pick a constant as the seed

in src/test/streams_tests.cpp:244 in b1aee23057 outdated

239+
240+    // Read from current offset, 3, forward until the buffer is full
241+    // (based on our knowledge of the object's internals).
242+    for (i = 3; i < 10; ++i) {
243+        bf >> i;
244+        BOOST_CHECK_EQUAL(i, i);

mzumsande commented at 9:28 pm on August 15, 2019:

Does this test for an identity? Did you mean to use a different variable as loop counter?

LarryRuane commented at 9:16 pm on August 16, 2019:

@mzumsande, good catch, very silly of me! Fixed in the latest commit, 166358663eff37ea59ce1ec2f74685a46187e926.

mzumsande commented at 9:30 pm on August 15, 2019: member

Hi, I am currently trying to understand CBufferedFile and the tests, both confuse me still :smiley:. Seems like substantial parts of streams_buffered_file test are added first and removed again in a later commit. Could you squash commits that fix errors in earlier ones?

LarryRuane force-pushed on Aug 16, 2019

LarryRuane commented at 9:19 pm on August 16, 2019: contributor

Could you squash commits that fix errors in earlier ones?

Yes, I ended up squashing down to a single commit, because there really are no phases or stages to this PR. Thanks for reviewing.

in src/streams.h:736 in 166358663e outdated

732@@ -733,18 +733,18 @@ class CBufferedFile
733         if (readNow == 0)
734             return false;
735         size_t nBytes = fread((void*)&vchBuf[pos], 1, readNow, src);
736-        if (nBytes == 0) {
737+        if (nBytes == 0)

laanwj commented at 2:51 pm on August 19, 2019:

Please keep the {}, according to the coding style: “If an if only has a single-statement then-clause, it can appear on the same line as the if, without braces. In every other case, braces are required, and the then and else clauses must appear correctly indented on a new line.” (some cases below, too)

in src/streams.h:807 in 166358663e outdated

804-        if (nReadPos + nRewind < nSrcPos) {
805-            nReadPos = nSrcPos - nRewind;
806+        size_t bufsize = vchBuf.size();
807+        if (nPos + bufsize < nSrcPos) {
808+            // rewinding too far, rewind as far as possible
809+            nReadPos = nSrcPos - bufsize;

mzumsande commented at 3:27 pm on August 19, 2019:

Would be nice to have a test case for “rewinding too far” in the test streams_buffered_file as well, since this code was changed.

LarryRuane commented at 8:56 pm on August 19, 2019:

Done, https://github.com/bitcoin/bitcoin/pull/16577/commits/723baf279ecf42c42c4c73378e6bc175ae07b631.

mzumsande commented at 3:33 pm on August 19, 2019: member

Thanks for squashing - I agree that this fixes a bug, which hasn’t lead to errors because of how CBufferedFile is initialized in LoadExternalBlockFile() (see comment above). Tests look good to me, will look at them in more detail (and also perform a reindex on testnet) in the next days.

DrahtBot commented at 5:49 am on August 24, 2019: member

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

Conflicts

No conflicts as of last run.

laanwj commented at 8:55 am on September 10, 2019: member

Looks good to me, thanks for adding the extensive testing.

ACK ~after squash.~ efd2474d17098c754367b844ec646ebececc7c74

util: CBufferedFile fixes efd2474d17

LarryRuane force-pushed on Sep 10, 2019

mzumsande commented at 10:00 pm on September 10, 2019: member

I had intended to follow up earlier on my last comment, ACK efd2474d17098c754367b844ec646ebececc7c74. I reviewed the code, ran tests and did a successful reindex on testnet with this branch.

laanwj referenced this in commit ab765c2ec7 on Sep 26, 2019

laanwj merged this on Sep 26, 2019

laanwj closed this on Sep 26, 2019

sidhujag referenced this in commit b2caa165d8 on Sep 26, 2019

LarryRuane deleted the branch on Nov 7, 2019

zkbot referenced this in commit 28e0a72995 on Feb 27, 2020

zkbot referenced this in commit 26a24da745 on Mar 3, 2020

DeckerSU referenced this in commit 9700247d31 on Mar 16, 2020

DeckerSU referenced this in commit 354abc52b6 on Mar 17, 2020

jasonbcox referenced this in commit 06a61dcb12 on Oct 23, 2020

PastaPastaPasta referenced this in commit a458081dee on Jun 27, 2021

PastaPastaPasta referenced this in commit b49a1fd25e on Jun 28, 2021

PastaPastaPasta referenced this in commit e668aeb77b on Jun 29, 2021

PastaPastaPasta referenced this in commit a67243df43 on Jul 1, 2021

PastaPastaPasta referenced this in commit d20b716b00 on Jul 1, 2021

PastaPastaPasta referenced this in commit e18d4f9365 on Jul 12, 2021

PastaPastaPasta referenced this in commit a5ab3fe1e6 on Jul 13, 2021

PastaPastaPasta referenced this in commit a597c1bb8e on Jul 13, 2021

random-zebra referenced this in commit b4751e10ce on Aug 11, 2021

DrahtBot locked this on Dec 16, 2021

util: CBufferedFile fixes and unit test #16577

Conflicts