AU: Don't use sparse holes as scratch space in the delta generator.
This patch fixes a number of bugs related to handling of sparse holes
in the context of scratch space in the delta diff generator and adds
appropriate unit tests. Most notably:
- Ignore sparse holes for the purposes of ExtentRanges. This prevents
the generator from using sparse holes as scratch.
- Adds two unit tests to catch using sparse holes as scratch in a more
deterministric way.
- Handle correctly sparse holes in
GraphUtils::AppendBlockToExtents. For example, previously, if one
adds block 0 to a single-block kSparseHole extent, the extent would
have been simply extended.
BUG=chromium:238440
TEST=unit tests, trybots
Change-Id: I3fedcc93af319ee741821ad9d1a2a57b7a7d5de2
Reviewed-on: https://gerrit.chromium.org/gerrit/50448
Commit-Queue: Darin Petkov <petkov@chromium.org>
Reviewed-by: Darin Petkov <petkov@chromium.org>
Tested-by: Darin Petkov <petkov@chromium.org>
diff --git a/delta_diff_generator_unittest.cc b/delta_diff_generator_unittest.cc
index 7fa28c3..181fd27 100644
--- a/delta_diff_generator_unittest.cc
+++ b/delta_diff_generator_unittest.cc
@@ -657,6 +657,190 @@
}
}
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if all full operations write to sparse holes and there's no extra scratch
+// space, delta operations that need scratch are converted to full. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, RunAsRootNoSparseAsTempTest) {
+ Graph graph(3);
+ const vector<Extent> kEmpty;
+ const string kFilename = "/foo";
+
+ // Make sure this sparse hole is not used as scratch.
+ GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
+
+ // Create a single-block cycle.
+ GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
+ graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
+ GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
+ graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+
+ // Prepare the filesystem with the minimum required for this to work.
+ string temp_dir;
+ EXPECT_TRUE(utils::MakeTempDirectory("/tmp/NoSparseAsTempTest.XXXXXX",
+ &temp_dir));
+ ScopedDirRemover temp_dir_remover(temp_dir);
+
+ const size_t kBlockSize = 4096;
+ vector<char> temp_data(kBlockSize);
+ FillWithData(&temp_data);
+ EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
+ ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
+
+ int fd = -1;
+ EXPECT_TRUE(utils::MakeTempFile("/tmp/NoSparseAsTempTestData.XXXXXX",
+ NULL,
+ &fd));
+ ScopedFdCloser fd_closer(&fd);
+ off_t data_file_size = 0;
+
+ EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+ temp_dir,
+ fd,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ ASSERT_EQ(4, graph.size());
+
+ // The second BSDIFF operation must have been converted to a full operation
+ // (due to insufficient scratch space).
+ EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
+ graph[2].op.type() == OP_REPLACE_BZ);
+
+ // The temporary node created for breaking the cycle must have been marked as
+ // invalid.
+ EXPECT_FALSE(graph[3].valid);
+}
+
+// Test that sparse holes are not used as scratch. More specifically, test that
+// if scratch space comes only from full operations writing to real blocks as
+// well as sparse holes, only the real blocks are utilized. See
+// crbug.com/238440.
+TEST_F(DeltaDiffGeneratorTest, NoSparseAsTempTest) {
+ Graph graph;
+ vector<Block> blocks(4);
+
+ // Create nodes in |graph|.
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(
+ DeltaArchiveManifest_InstallOperation_Type_REPLACE);
+
+ // Write to a sparse hole -- basically a no-op to ensure sparse holes are
+ // not used as scratch.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Scratch space: write to block 0 with sparse holes around.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[0].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_REPLACE);
+
+ // Write to a sparse hole.
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ }
+ // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (2, sparse, sparse).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[2].reader = graph.size() - 1;
+
+ // Write to (1, sparse, 3).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[1].writer = graph.size() - 1;
+ blocks[3].writer = graph.size() - 1;
+ }
+ {
+ graph.resize(graph.size() + 1);
+ graph.back().op.set_type(OP_MOVE);
+ // Read from (1, sparse, 3).
+ vector<Extent> extents;
+ graph_utils::AppendBlockToExtents(&extents, 1);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, 3);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_src_extents());
+ blocks[1].reader = graph.size() - 1;
+ blocks[3].reader = graph.size() - 1;
+
+ // Write to (2, sparse, sparse).
+ extents.clear();
+ graph_utils::AppendBlockToExtents(&extents, 2);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ DeltaDiffGenerator::StoreExtents(extents,
+ graph.back().op.mutable_dst_extents());
+ blocks[2].writer = graph.size() - 1;
+ }
+
+ graph_utils::DumpGraph(graph);
+
+ // Create edges
+ DeltaDiffGenerator::CreateEdges(&graph, blocks);
+
+ graph_utils::DumpGraph(graph);
+
+ vector<Vertex::Index> final_order;
+ off_t data_file_size = 0;
+ EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
+ "/non/existent/dir",
+ -1,
+ &data_file_size,
+ &final_order,
+ Vertex::kInvalidIndex));
+
+ // Check for a single temporary node writing to scratch.
+ ASSERT_EQ(6, graph.size());
+ EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
+ graph[5].op.type());
+ EXPECT_EQ(1, graph[5].op.src_extents_size());
+ ASSERT_EQ(1, graph[5].op.dst_extents_size());
+ EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
+ EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
+
+ // Make sure the cycle nodes still read from and write to sparse holes.
+ for (int i = 3; i < 5; i++) {
+ ASSERT_GE(graph[i].op.src_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
+ ASSERT_GE(graph[i].op.dst_extents_size(), 2);
+ EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
+ }
+}
+
TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
DeltaArchiveManifest_InstallOperation op;
op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
diff --git a/extent_ranges.cc b/extent_ranges.cc
index a8836c9..5193d3d 100644
--- a/extent_ranges.cc
+++ b/extent_ranges.cc
@@ -20,6 +20,8 @@
bool ExtentRanges::ExtentsOverlapOrTouch(const Extent& a, const Extent& b) {
if (a.start_block() == b.start_block())
return true;
+ if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+ return false;
if (a.start_block() < b.start_block()) {
return a.start_block() + a.num_blocks() >= b.start_block();
} else {
@@ -30,6 +32,8 @@
bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
if (a.start_block() == b.start_block())
return true;
+ if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
+ return false;
if (a.start_block() < b.start_block()) {
return a.start_block() + a.num_blocks() > b.start_block();
} else {
@@ -48,16 +52,18 @@
namespace {
Extent UnionOverlappingExtents(const Extent& first, const Extent& second) {
+ CHECK_NE(kSparseHole, first.start_block());
+ CHECK_NE(kSparseHole, second.start_block());
uint64_t start = min(first.start_block(), second.start_block());
uint64_t end = max(first.start_block() + first.num_blocks(),
second.start_block() + second.num_blocks());
return ExtentForRange(start, end - start);
}
-
+
} // namespace {}
void ExtentRanges::AddExtent(Extent extent) {
- if (extent.num_blocks() == 0)
+ if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
return;
ExtentSet::iterator begin_del = extent_set_.end();
@@ -100,7 +106,7 @@
} // namespace {}
void ExtentRanges::SubtractExtent(const Extent& extent) {
- if (extent.num_blocks() == 0)
+ if (extent.start_block() == kSparseHole || extent.num_blocks() == 0)
return;
ExtentSet::iterator begin_del = extent_set_.end();
@@ -111,12 +117,12 @@
it != e; ++it) {
if (!ExtentsOverlap(*it, extent))
continue;
-
+
if (begin_del == extent_set_.end())
begin_del = it;
end_del = it;
++end_del;
-
+
del_blocks += it->num_blocks();
ExtentSet subtraction = SubtractOverlappingExtents(*it, extent);
diff --git a/extent_ranges.h b/extent_ranges.h
index 8fdc302..2ab347a 100644
--- a/extent_ranges.h
+++ b/extent_ranges.h
@@ -15,9 +15,12 @@
#include "update_engine/graph_types.h"
#include "update_engine/update_metadata.pb.h"
-// An ExtentRanges object represents an unordered collection of extents
-// (and therefore blocks). Such an object may be modified by adding or
-// subtracting blocks (think: set addition or set subtraction).
+// An ExtentRanges object represents an unordered collection of extents (and
+// therefore blocks). Such an object may be modified by adding or subtracting
+// blocks (think: set addition or set subtraction). Note that ExtentRanges
+// ignores sparse hole extents mostly to avoid confusion between extending a
+// sparse hole range vs. set addition but also to ensure that the delta
+// generator doesn't use sparse holes as scratch space.
namespace chromeos_update_engine {
@@ -52,7 +55,7 @@
// Dumps contents to the log file. Useful for debugging.
void Dump() const;
-
+
uint64_t blocks() const { return blocks_; }
const ExtentSet& extent_set() const { return extent_set_; }
diff --git a/extent_ranges_unittest.cc b/extent_ranges_unittest.cc
index b5a32d9..1b767f1 100644
--- a/extent_ranges_unittest.cc
+++ b/extent_ranges_unittest.cc
@@ -17,7 +17,7 @@
namespace {
void ExpectRangeEq(const ExtentRanges& ranges,
- uint64_t* expected,
+ const uint64_t* expected,
size_t sz,
int line) {
uint64_t blocks = 0;
@@ -113,39 +113,50 @@
ExpectFalseRangesOverlapOrTouch(10, 20, 35, 10);
ExpectFalseRangesOverlap(10, 20, 30, 10);
ExpectRangesOverlap(12, 4, 12, 3);
+
+ ExpectRangesOverlapOrTouch(kSparseHole, 2, kSparseHole, 3);
+ ExpectRangesOverlap(kSparseHole, 2, kSparseHole, 3);
+ ExpectFalseRangesOverlapOrTouch(kSparseHole, 2, 10, 3);
+ ExpectFalseRangesOverlapOrTouch(10, 2, kSparseHole, 3);
+ ExpectFalseRangesOverlap(kSparseHole, 2, 10, 3);
+ ExpectFalseRangesOverlap(10, 2, kSparseHole, 3);
}
TEST(ExtentRangesTest, SimpleTest) {
ExtentRanges ranges;
{
- uint64_t expected[] = {};
+ static const uint64_t expected[] = {};
// Can't use arraysize() on 0-length arrays:
ExpectRangeEq(ranges, expected, 0, __LINE__);
}
ranges.SubtractBlock(2);
{
- uint64_t expected[] = {};
+ static const uint64_t expected[] = {};
// Can't use arraysize() on 0-length arrays:
ExpectRangeEq(ranges, expected, 0, __LINE__);
}
-
+
ranges.AddBlock(0);
ranges.Dump();
ranges.AddBlock(1);
ranges.AddBlock(3);
-
+
{
- uint64_t expected[] = {0, 2, 3, 1};
+ static const uint64_t expected[] = {0, 2, 3, 1};
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.AddBlock(2);
{
- uint64_t expected[] = {0, 4};
+ static const uint64_t expected[] = {0, 4};
+ EXPECT_RANGE_EQ(ranges, expected);
+ ranges.AddBlock(kSparseHole);
+ EXPECT_RANGE_EQ(ranges, expected);
+ ranges.SubtractBlock(kSparseHole);
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractBlock(2);
{
- uint64_t expected[] = {0, 2, 3, 1};
+ static const uint64_t expected[] = {0, 2, 3, 1};
EXPECT_RANGE_EQ(ranges, expected);
}
@@ -153,27 +164,35 @@
ranges.AddExtent(ExtentForRange(i, 50));
}
{
- uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
- 500, 50, 600, 50, 700, 50, 800, 50, 900, 50};
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 50, 300, 50, 400, 50,
+ 500, 50, 600, 50, 700, 50, 800, 50, 900, 50
+ };
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractExtent(ExtentForRange(210, 410 - 210));
{
- uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
- 600, 50, 700, 50, 800, 50, 900, 50};
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.AddExtent(ExtentForRange(100000, 0));
{
- uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
- 600, 50, 700, 50, 800, 50, 900, 50};
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
EXPECT_RANGE_EQ(ranges, expected);
}
ranges.SubtractExtent(ExtentForRange(3, 0));
{
- uint64_t expected[] = {0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
- 600, 50, 700, 50, 800, 50, 900, 50};
+ static const uint64_t expected[] = {
+ 0, 2, 3, 1, 100, 50, 200, 10, 410, 40, 500, 50,
+ 600, 50, 700, 50, 800, 50, 900, 50
+ };
EXPECT_RANGE_EQ(ranges, expected);
}
}
diff --git a/graph_utils.cc b/graph_utils.cc
index 02b49c3..3e3cc9e 100644
--- a/graph_utils.cc
+++ b/graph_utils.cc
@@ -33,21 +33,17 @@
}
void AppendBlockToExtents(vector<Extent>* extents, uint64_t block) {
+ // First try to extend the last extent in |extents|, if any.
if (!extents->empty()) {
Extent& extent = extents->back();
- if (block == kSparseHole) {
- if (extent.start_block() == kSparseHole) {
- // Extend sparse hole extent
- extent.set_num_blocks(extent.num_blocks() + 1);
- return;
- } else {
- // Create new extent below outer 'if'
- }
- } else if (extent.start_block() + extent.num_blocks() == block) {
+ uint64_t next_block = extent.start_block() == kSparseHole ?
+ kSparseHole : extent.start_block() + extent.num_blocks();
+ if (next_block == block) {
extent.set_num_blocks(extent.num_blocks() + 1);
return;
}
}
+ // If unable to extend the last extent, append a new single-block extent.
Extent new_extent;
new_extent.set_start_block(block);
new_extent.set_num_blocks(1);
diff --git a/graph_utils_unittest.cc b/graph_utils_unittest.cc
index cfa2b5c..3bd9d16 100644
--- a/graph_utils_unittest.cc
+++ b/graph_utils_unittest.cc
@@ -19,7 +19,7 @@
TEST(GraphUtilsTest, SimpleTest) {
Graph graph(2);
-
+
graph[0].out_edges.insert(make_pair(1, EdgeProperties()));
vector<Extent>& extents = graph[0].out_edges[1].extents;
@@ -31,16 +31,36 @@
graph_utils::AppendBlockToExtents(&extents, 2);
EXPECT_EQ(1, extents.size());
graph_utils::AppendBlockToExtents(&extents, 4);
-
+
EXPECT_EQ(2, extents.size());
EXPECT_EQ(0, extents[0].start_block());
EXPECT_EQ(3, extents[0].num_blocks());
EXPECT_EQ(4, extents[1].start_block());
EXPECT_EQ(1, extents[1].num_blocks());
-
+
EXPECT_EQ(4, graph_utils::EdgeWeight(graph, make_pair(0, 1)));
}
+TEST(GraphUtilsTest, AppendSparseToExtentsTest) {
+ vector<Extent> extents;
+
+ EXPECT_EQ(0, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ EXPECT_EQ(1, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, 0);
+ EXPECT_EQ(2, extents.size());
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+ graph_utils::AppendBlockToExtents(&extents, kSparseHole);
+
+ ASSERT_EQ(3, extents.size());
+ EXPECT_EQ(kSparseHole, extents[0].start_block());
+ EXPECT_EQ(1, extents[0].num_blocks());
+ EXPECT_EQ(0, extents[1].start_block());
+ EXPECT_EQ(1, extents[1].num_blocks());
+ EXPECT_EQ(kSparseHole, extents[2].start_block());
+ EXPECT_EQ(2, extents[2].num_blocks());
+}
+
TEST(GraphUtilsTest, BlocksInExtentsTest) {
{
vector<Extent> extents;
@@ -66,7 +86,7 @@
TEST(GraphUtilsTest, DepsTest) {
Graph graph(3);
-
+
graph_utils::AddReadBeforeDep(&graph[0], 1, 3);
EXPECT_EQ(1, graph[0].out_edges.size());
{
@@ -93,7 +113,7 @@
graph[2].out_edges[1].write_extents.swap(graph[2].out_edges[1].extents);
graph_utils::DropWriteBeforeDeps(&graph[2].out_edges);
EXPECT_EQ(0, graph[2].out_edges.size());
-
+
EXPECT_EQ(1, graph[0].out_edges.size());
graph_utils::DropIncomingEdgesTo(&graph, 1);
EXPECT_EQ(0, graph[0].out_edges.size());