Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. #9490

gmaxwell · 2017-01-08T07:23:30Z

In spite of the name FindLatestBefore used std::lower_bound to try
to find the earliest block with a nTime greater or equal to the
the requested value. But lower_bound uses bisection and requires
the input to be ordered with respect to the comparison operation.
Block times are not well ordered.

I don't know what lower_bound is permitted to do when the data
is not sufficiently ordered, but it's probably not good.
(I could construct an implementation which would infinite loop...)

To resolve the issue this commit introduces a maximum-so-far to the
block indexes and searches that.

For clarity the function is renamed to reflect what it actually does.

An issue that remains is that there is no grace period in importmulti:
If a address is created at time T and a send is immediately broadcast
and included by a miner with a slow clock there may not yet have been
any block with at least time T.

The normal rescan has a grace period of 7200 seconds, but importmulti
does not.

gmaxwell · 2017-01-08T07:32:29Z

Tag for 0.14 please. Comments on if we should do something about the lack of grace in importmulti?

This came up while I was reviewing #7871 and realized that an obvious use of it would be making sure that you only pruned after performing your relevant importmultis, so it's important that we be able to prune and importmulti on the same basis. (also, looks like importmulti will crash on pruned nodes... but thats another issue.)

ryanofsky · 2017-01-09T15:43:27Z

src/validation.cpp

@@ -2601,6 +2601,7 @@ CBlockIndex* AddToBlockIndex(const CBlockHeader& block)
        pindexNew->nHeight = pindexNew->pprev->nHeight + 1;
        pindexNew->BuildSkip();
    }
+    pindexNew->nTimeMax = (pindexNew->pprev ? std::max(pindexNew->pprev->nTimeMax, pindexNew->nTime) : pindexNew->nTime);


How does nTimeMax get assigned when the block index is loaded on startup? Do you need to add a similar assignment to LoadBlockIndexDB?

::facepalm:: fixed.

ryanofsky · 2017-01-11T16:33:57Z

Will need to rebase now that #7871 is merged (it added a new FindLatestBefore call)

gmaxwell · 2017-01-11T22:06:13Z

Rebased.

sipa · 2017-01-11T22:14:54Z

At least on x86_64 + glibc malloc, this does not actually increase memory usage.

jtimon · 2017-01-11T23:18:56Z

I can't think of a better solution, but in principle it looks like introducing unsigned int CBlockIndex::nTimeMax should hurt in terms of memory. I didn't tried sipa's memory test though.

As an aside, I don't really understand the recommended policy for choosing between unsigned int, uint_32t and uint_64t for class attributes.

gmaxwell · 2017-01-12T00:57:19Z

I can't think of a better solution, but in principle it looks like introducing unsigned int CBlockIndex::nTimeMax should hurt in terms of memory. I didn't tried sipa's memory test though.

It doesn't increase the usage because the alignment requirements of the existing objects required padding.

sdaftuar · 2017-01-12T02:52:18Z

ACK 336289e. Tested FindEarliestAtLeast() with a unit test here: 3e1f598

laanwj · 2017-01-12T11:17:37Z

utACK 336289e, will merge after pull 3e1f598 into this.

In spite of the name FindLatestBefore used std::lower_bound to try to find the earliest block with a nTime greater or equal to the the requested value. But lower_bound uses bisection and requires the input to be ordered with respect to the comparison operation. Block times are not well ordered. I don't know what lower_bound is permitted to do when the data is not sufficiently ordered, but it's probably not good. (I could construct an implementation which would infinite loop...) To resolve the issue this commit introduces a maximum-so-far to the block indexes and searches that. For clarity the function is renamed to reflect what it actually does. An issue that remains is that there is no grace period in importmulti: If a address is created at time T and a send is immediately broadcast and included by a miner with a slow clock there may not yet have been any block with at least time T. The normal rescan has a grace period of 7200 seconds, but importmulti does not.

gmaxwell · 2017-01-12T14:25:17Z

@laanwj Pulled it in. @sdaftuar Thank you so much for the test!

morcos · 2017-01-12T18:52:24Z

utACK

@gmaxwell +1 on adding a grace period. I can't really imagine any downside to and only annoying hard to debug potential issues if we don't.

sipa · 2017-01-13T23:45:41Z

utACK 4b06e41

…liestAtLeast. 4b06e41 Add unit test for FindEarliestAtLeast (Suhas Daftuar) 997a98a Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. (Gregory Maxwell)

ryanofsky · 2017-02-14T15:36:53Z

An issue that remains is that there is no grace period in importmulti:
If a address is created at time T and a send is immediately broadcast
and included by a miner with a slow clock there may not yet have been
any block with at least time T.

The normal rescan has a grace period of 7200 seconds, but importmulti
does not.

This is not actually true. There is a check in importmulti that appears to skip rescan if the lowest imported key timestamp is higher than the highest blocktime:

bitcoin/src/wallet/rpcdump.cpp

Line 1051 in ec66d06

    
           if (fRescan && fRunScan && requests.size() && nLowestTimestamp <= chainActive.Tip()->GetBlockTimeMax()) {

But this check doesn't actually do anything, because of the way the lowest key timestamp is initialized

bitcoin/src/wallet/rpcdump.cpp

Line 1023 in ec66d06

nLowestTimestamp = chainActive.Tip()->GetBlockTime();

I made a change in #9760 to just drop this check since it doesn't do anything. An alternative would be to initialize nLowestTimestamp to numeric_limits<int64_t>::max() so the check does what it appears to do, and then add a grace period.

ryanofsky · 2017-02-14T15:50:50Z

The normal rescan has a grace period of 7200 seconds, but importmulti
does not.

This is not actually true.

Actually it is true. @morcos pointed out the lack of grace period wasn't in the GetBlockTimeMax comparison, but in the FindEarliestAtLeast call. I can make another PR to add a grace period to that call.

Gregory Maxwell <greg@xiph.org> pointed out the lack of grace period in bitcoin#9490 (comment). The importwallet RPC which uses key timestamps in a similar way already has a 2 hour grace period.

ryanofsky · 2017-02-14T23:07:52Z

Added grace period in #9761.

Gregory Maxwell <greg@xiph.org> pointed out the lack of grace period in bitcoin#9490 (comment). The importwallet RPC which uses key timestamps in a similar way already has a 2 hour grace period.

…FindEarliestAtLeast. 4b06e41 Add unit test for FindEarliestAtLeast (Suhas Daftuar) 997a98a Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. (Gregory Maxwell)

Gregory Maxwell <greg@xiph.org> pointed out the lack of grace period in bitcoin#9490 (comment). The importwallet RPC which uses key timestamps in a similar way already has a 2 hour grace period. Conflicts: qa/rpc-tests/import-rescan.py

Gregory Maxwell <greg@xiph.org> pointed out the lack of grace period in bitcoin#9490 (comment). The importwallet RPC which uses key timestamps in a similar way already has a 2 hour grace period.

…FindEarliestAtLeast. 4b06e41 Add unit test for FindEarliestAtLeast (Suhas Daftuar) 997a98a Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. (Gregory Maxwell)

@codablock

…dablock committed on Jan 20, 2018 Use version 2 blocks for miner_tests … @codablock codablock committed on Jan 20, 2018 Merge bitcoin#7871: Manual block file pruning. … @laanwj @codablock laanwj authored and codablock committed on Jan 11, 2017 Merge bitcoin#9507: Fix use-after-free in CTxMemPool::removeConflicts() … @sipa @codablock sipa authored and codablock committed on Jan 11, 2017 Merge bitcoin#9297: Various RPC help outputs updated … @MarcoFalke @codablock MarcoFalke authored and codablock committed on Jan 12, 2017 Merge bitcoin#9416: travis: make distdir before make … @MarcoFalke @codablock MarcoFalke authored and codablock committed on Jan 12, 2017 Merge bitcoin#9520: Deprecate non-txindex getrawtransaction and bette… … @MarcoFalke @codablock MarcoFalke authored and codablock committed on Jan 12, 2017 Merge bitcoin#9518: Return height of last block pruned by pruneblockc… … @MarcoFalke @codablock MarcoFalke authored and codablock committed on Jan 12, 2017 Merge bitcoin#9472: Disentangle progress estimation from checkpoints … … @laanwj @codablock laanwj authored and codablock committed on Jan 12, 2017 Merge bitcoin#8883: Add all standard TXO types to bitcoin-tx … @laanwj @codablock laanwj authored and codablock committed on Jan 12, 2017 Merge bitcoin#9261: Add unstored orphans with rejected parents to rec… … @laanwj @codablock laanwj authored and codablock committed on Jan 12, 2017 Merge bitcoin#9468: [Depends] Dependency updates for 0.14.0 … @laanwj @codablock laanwj authored and codablock committed on Jan 12, 2017 Merge bitcoin#9222: Add 'subtractFeeFromAmount' option to 'fundrawtra… … @laanwj @codablock laanwj authored and codablock committed on Jan 12, 2017 Merge bitcoin#9490: Replace FindLatestBefore used by importmuti with … … @sipa @codablock sipa authored and codablock committed on Jan 13, 2017 Merge bitcoin#9469: [depends] Qt 5.7.1 … @laanwj @codablock laanwj authored and codablock committed on Jan 15, 2017 Merge bitcoin#9380: Separate different uses of minimum fees … @laanwj @codablock laanwj authored and codablock committed on Jan 16, 2017 Remove SegWit related code in dash-tx @codablock codablock committed on Sep 21, 2017 Merge bitcoin#9561: Wake message handling thread when we receive a ne… … @sipa @codablock sipa authored and codablock committed on Jan 17, 2017 Merge bitcoin#9508: Remove unused Python imports … @MarcoFalke @codablock MarcoFalke authored and codablock committed on Jan 18, 2017 Merge bitcoin#9512: Fix various things -fsanitize complains about

7e0c709 Clean up importmulti help text (Fuzzbawls) 1cacda6 [Tests] Fix and Re-enable wallet_importmulti.py (random-zebra) 4ff0b4a [Trivial] NULL --> nullptr in skiplist_tests (random-zebra) b53a986 Add unit test for FindEarliestAtLeast (Suhas Daftuar) d1bb973 [RPC] Add importmulti call (random-zebra) Pull request description: Based on top of: - [x] #2240 Essentially backport bitcoin#7551 and bitcoin#9490, with more recent changes to adapt to the current sources. Fix and re-enable the `wallet_importmulti.py` functional test. ACKs for top commit: Fuzzbawls: ACK 7e0c709 furszy: ACK 7e0c709 and merging.. Tree-SHA512: 47a4452bfaeae16d09268d3eaa0c1a5d94a39accf86b7345818f8436222650515a8bf66ef331ba478058aabcbcfcf978192f39b349027e189b7ac41cd3e69a6e

fanquake added this to the 0.14.0 milestone Jan 8, 2017

fanquake added Validation Wallet labels Jan 8, 2017

ryanofsky reviewed Jan 9, 2017

View reviewed changes

gmaxwell and others added 2 commits January 12, 2017 14:21

Add unit test for FindEarliestAtLeast

4b06e41

sipa merged commit 4b06e41 into bitcoin:master Jan 14, 2017

ryanofsky mentioned this pull request Feb 14, 2017

Use 2 hour grace period for key timestamps in importmulti rescans #9761

Merged

sipa mentioned this pull request Mar 7, 2017

tests: Add FindEarliestAtLeast test for edge cases #9909

Merged

random-zebra mentioned this pull request Mar 30, 2021

[RPC] Add importmulti RPC command and functional test PIVX-Project/PIVX#2277

Merged

1 task

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. #9490

Replace FindLatestBefore used by importmuti with FindEarliestAtLeast. #9490

Uh oh!

Conversation

gmaxwell commented Jan 8, 2017

Uh oh!

gmaxwell commented Jan 8, 2017

Uh oh!

ryanofsky Jan 9, 2017

Choose a reason for hiding this comment

Uh oh!

gmaxwell Jan 9, 2017

Choose a reason for hiding this comment

Uh oh!

ryanofsky commented Jan 11, 2017

Uh oh!

gmaxwell commented Jan 11, 2017

Uh oh!

sipa commented Jan 11, 2017

Uh oh!

jtimon commented Jan 11, 2017

Uh oh!

gmaxwell commented Jan 12, 2017

Uh oh!

sdaftuar commented Jan 12, 2017

Uh oh!

laanwj commented Jan 12, 2017

Uh oh!

gmaxwell commented Jan 12, 2017

Uh oh!

morcos commented Jan 12, 2017

Uh oh!

sipa commented Jan 13, 2017

Uh oh!

ryanofsky commented Feb 14, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

ryanofsky commented Feb 14, 2017

Uh oh!

ryanofsky commented Feb 14, 2017

Uh oh!

Uh oh!

ryanofsky commented Feb 14, 2017 •

edited

Loading