tree 591b39bdc3910160f9358c6ed033cbd8d51bc624
parent 73058b421f91e04cc605c2a113e0010009a63594
author Andrew de los Reyes <adlr@chromium.org> 1286413072 -0700
committer Andrew de los Reyes <adlr@chromium.org> 1286413072 -0700

AU: reuse scratch blocks in delta generation, tolerate insufficient scratch.

Changes the delta generator cycle cutting algorithm. The old algorithm
looked for scratch space on the disk, then allocated that scratch
sequentially to operations that needed it, bailing if it ran out of
scratch.

The new algorithm first allocates non-existent blocks (those at
kTempBlockStart and higher) at first to break cycles. It then comes up
with a valid topological order for all nodes. It then tries to find
real blocks for all the non-existent temp blocks allocated. For each
cut edge ( A->B => A->N<-B ), there are 3 nodes of importance: the old
source (A) the old dst (B) and the new node (N). N writes to temp
blocks, then B reads from those temp blocks. The new algorithm starts
at node B and scans the topological order up, knowing that any
dependency from a found node to B would be valid, as it doesn't
require a change in the topo order. If a node is found, which has
blocks written, and these blocks aren't in a read-before dependence
from the found node to another node, we use those blocks as temp
space.  Notice that after we find temp blocks for a cut, a future cut
could use the blocks written by N of this cut, thus allowing temp
blocks to be reused.

Another change this algorithm makes is that if no node is found for
supplying temp blocks, the cut is resolved by making the old dst node
(B) a full operation, and moving it to the end of the topological
order (so it may supply temp blocks to other cuts).

Thus, if there is insufficient scratch, we lose compression ratio
rather than failing.

In a resent image that used a lot of scratch, I found this new algo
didn't have to convert any ops to full, as reuing scratch was enough.

This CL does perform a regression. Our filesystems do not take up the
full space in the partition. The existing delta generator makes use of
that extra space for scratch, but this new algo doesn't. We could fix
this new algorithm by creating a dummy node that writes to this extra
space at the end of the partition, then removing it from the update
file so the client doesn't actually do that write. If the reviewer is
okay with it, I'll file an Issue for this.

BUG=None
TEST=Attached unittests, create/perform delta w/ new algo

Review URL: http://codereview.chromium.org/3597014