update_engine: Handle moved and zero blocks in payload generation.
Delta generation uses only the file name to detect when files changed.
Therefore, renaming a file doesn't get detected and the new name is
assumed to be a new file. On the other hand, free-space blocks are
often just zeros so they can be easilly encoded independently from the
rest.
This patch detects blocks that moved and blocks with zeros and handles
those blocks beforehand regardless of where are they in the filesystem
(file data, metadata, free space, etc). For blocks that moved,
SOURCE_COPY or MOVE operations are created as needed. For blocks with
zeros we use REPLACE_BZ operations.
Blocks processed in this way will be excluded from other files,
metadata or free space processing done. This solves perfomance issues
when trying to process with bsdiff files with very long runs of zeros.
CQ-DEPEND=CL:283643
BUG=chromium:504445
TEST=Unittest added. Run delta_generator between cid canary 7195 and
7201 and it doesn't take forever to finish.
Change-Id: I892fe7456608e83a2946133da335eb4fbd19a645
Reviewed-on: https://chromium-review.googlesource.com/283172
Commit-Queue: Alex Deymo <deymo@chromium.org>
Trybot-Ready: Alex Deymo <deymo@chromium.org>
Tested-by: Alex Deymo <deymo@chromium.org>
Reviewed-by: Alex Deymo <deymo@chromium.org>
Reviewed-by: Gilad Arnold <garnold@chromium.org>
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index d86bcfc..9151efe 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -180,6 +180,23 @@
}
}
+bool ExtentRanges::ContainsBlock(uint64_t block) const {
+ auto lower = extent_set_.lower_bound(ExtentForRange(block, 1));
+ // The block could be on the extent before the one in |lower|.
+ if (lower != extent_set_.begin())
+ lower--;
+ // Any extent starting at block+1 or later is not interesting, so this is the
+ // upper limit.
+ auto upper = extent_set_.lower_bound(ExtentForRange(block + 1, 0));
+ for (auto iter = lower; iter != upper; ++iter) {
+ if (iter->start_block() <= block &&
+ block < iter->start_block() + iter->num_blocks()) {
+ return true;
+ }
+ }
+ return false;
+}
+
void ExtentRanges::Dump() const {
LOG(INFO) << "ExtentRanges Dump. blocks: " << blocks_;
for (ExtentSet::const_iterator it = extent_set_.begin(),
@@ -223,7 +240,7 @@
return out;
}
-vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
+vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
const ExtentRanges& ranges) {
vector<Extent> result;
const ExtentRanges::ExtentSet& extent_set = ranges.extent_set();