utACK.
Plans to test this soon.
Little indentation/tabs nit chain.h L88:90.

Nit fixed, thanks!

Added this PR on top of master and left my pruned bitcoind mainnet node running over night. No issues.
Just copied blocks/chainstate from a full-node to a fresh node and pruned to target 550MB. Worked as expected.

Tested ACK.

Untested ACK. I don't understand the Travis failure.

Rebased.

What is your reasoning behind this? From a conceptual point of view I like the flags to specify what they do now: does the block HAVE data or undo data.

I was trying to eliminate the need to iterate the entire mapBlockIndex whenever a file is pruned (since we currently lack a map from block files to blocks, we check each block to see if it's in a blockfile being deleted). That seems like something that needs to be fixed at some point.

One idea for addressing that would be to just maintain a (memory-only) map from block files to blockindex entries which we iterate when pruning; this would be straightforward, cpu efficient, and preserve existing HAVE_DATA semantics. However I think @sipa was concerned about the additional memory overhead of that approach (I believe it would be roughly an additional 10MB if you're running in prune mode with a target high enough that no files are actually deleted -- which is perhaps relevant if in the future most nodes may run with some level of pruning), and he suggested lazy updating instead.

So I tried implementing the lazy-update approach to see how feasible (and/or cumbersome) this would be. It seems very efficient; the code changes to support it seem relatively minor; and I like the idea of not having to worry about updating state when block files are removed -- that seems like it should make future pruning-related improvements easier to make. I do agree there's a tradeoff, in that the current HAVE_DATA semantics seem cleaner versus the new STORED_DATA semantics, but it's hard for me right now to say which semantics are better in the long run.

I think that uncertainty would be an argument for waiting to see what the future of pruning code looks like and then deciding what solution makes most sense, except one thing I realized after coding this up is that if we decide to go in this direction with lazy updating of block index entries, then I think it would be better if we deploy this behavior with pruning in 0.11 than wait until 0.12 -- otherwise there's a backwards compatibility issue, where once your block index has been lazily updated, you can't easily revert back to a version of pruning code that didn't support that (at least with the present implementation).

At any rate, I don't feel strongly about which approach has the best tradeoffs, and if we end up not merging this for 0.11, then I'd say we may as well just wait until we implement sharding, and decide then what approach makes sense here.

Is the overhead to have to iterate over the (in-memory) block index when a file is pruned significant?

Muddying the database semantics to make a rare action slightly faster would be unfortunate. But I don't feel strongly about it either.

Also: this makes the 'block has data' check more involved and that is performed very often.

@laanwj I believe it's ~20ms to iterate mapBlockIndex. Arguably that is insignificant the way pruning works now, since it can only happen when we're calling FlushStateToDisk() which is already an expensive operation.

Regarding the efficiency of HaveBlockData(), I think that this implementation is very fast if there's no lock contention and that seems to be the case presently; it's unclear to me whether there could be lock contention to worry about down the road, in particular if the code were to change in the future so that the HaveBlockData() function is called from more places.

I think @sdaftuar has a point that if we're ever going to implement lazy updating, the time to do it is now. But personally I think some sort of reverse lookup is eventually going to be needed. I implemented it to try it out and it's fine, but I also think the simple 20ms iteration every time you delete a blockfile is good enough for now and we should just do the reverse lookup in whatever way makes sense with the sharding algorithm we end up with.

Hmm, I was going to say the argument against the 20ms iteration is that once a day or so (when you've got an extra block file you can prune) then it's possible (I think even probable) that you're holding up block propagation. But come to think of it, that's a problem with choosing when we're pruning because even without the 20ms cost, you're still doing a full chainstate flush then. If we think that's problematic, maybe we can move around the pruning calls to only happen when we're a bit less busy, it'll take some testing though..

Updated a few comments and tried to make it clearer that HaveBlockData() can change state when pruning is enabled.

Closing. This apparently need to be rebased, and it's probably not worth it as I don't think we're going to merge for 0.11, and given the backwards compatibility issues this pull would generate if this were accepted later (see description above and #6148 (comment)), I think it'd be better for us to wait until a sharding solution is on the table and revisit this idea in that context.