| // |
| // Copyright (C) 2015 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| #include "update_engine/payload_generator/inplace_generator.h" |
| |
| #include <map> |
| #include <memory> |
| #include <set> |
| #include <sstream> |
| #include <string> |
| #include <utility> |
| #include <vector> |
| |
| #include <base/format_macros.h> |
| #include <base/logging.h> |
| #include <base/strings/string_util.h> |
| #include <base/strings/stringprintf.h> |
| #include <gtest/gtest.h> |
| |
| #include "update_engine/common/test_utils.h" |
| #include "update_engine/common/utils.h" |
| #include "update_engine/payload_generator/cycle_breaker.h" |
| #include "update_engine/payload_generator/delta_diff_generator.h" |
| #include "update_engine/payload_generator/delta_diff_utils.h" |
| #include "update_engine/payload_generator/extent_ranges.h" |
| #include "update_engine/payload_generator/graph_types.h" |
| #include "update_engine/payload_generator/graph_utils.h" |
| |
| using std::map; |
| using std::set; |
| using std::string; |
| using std::stringstream; |
| using std::vector; |
| |
| namespace chromeos_update_engine { |
| |
| using Block = InplaceGenerator::Block; |
| |
| namespace { |
| |
| void GenVertex(Vertex* out, |
| const vector<Extent>& src_extents, |
| const vector<Extent>& dst_extents, |
| const string& path, |
| InstallOperation_Type type) { |
| out->aop.op.set_type(type); |
| out->aop.name = path; |
| StoreExtents(src_extents, out->aop.op.mutable_src_extents()); |
| StoreExtents(dst_extents, out->aop.op.mutable_dst_extents()); |
| } |
| |
| vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) { |
| return vector<Extent>(1, ExtentForRange(start_block, num_blocks)); |
| } |
| |
| EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) { |
| EdgeProperties ret; |
| ret.extents = extents; |
| return ret; |
| } |
| |
| EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) { |
| EdgeProperties ret; |
| ret.write_extents = extents; |
| return ret; |
| } |
| |
| template <typename T> |
| void DumpVect(const vector<T>& vect) { |
| stringstream ss(stringstream::out); |
| for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end(); |
| it != e; |
| ++it) { |
| ss << *it << ", "; |
| } |
| LOG(INFO) << "{" << ss.str() << "}"; |
| } |
| |
| void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) { |
| vect->resize(vect->size() + 1); |
| vect->back().set_start_block(start); |
| vect->back().set_num_blocks(length); |
| } |
| |
| void OpAppendExtent(InstallOperation* op, uint64_t start, uint64_t length) { |
| Extent* extent = op->add_src_extents(); |
| extent->set_start_block(start); |
| extent->set_num_blocks(length); |
| } |
| |
| } // namespace |
| |
| class InplaceGeneratorTest : public ::testing::Test { |
| protected: |
| // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables |
| // with a new blob file. The file is closed and removed automatically when |
| // the test finishes. |
| void CreateBlobFile() { |
| // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a |
| // previous instance before overriding blob_fd_. |
| blob_fd_closer_.reset(); |
| EXPECT_TRUE(utils::MakeTempFile( |
| "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_)); |
| blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_)); |
| blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_)); |
| blob_file_size_ = 0; |
| EXPECT_GE(blob_fd_, 0); |
| blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_)); |
| } |
| |
| // Dump the list of operations |aops| in case of test failure. |
| void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) { |
| if (HasNonfatalFailure()) { |
| LOG(INFO) << "Result operation list:"; |
| for (const auto& aop : aops) { |
| LOG(INFO) << aop; |
| } |
| } |
| } |
| |
| // Blob file name, file descriptor and file size used to store operation |
| // blobs. |
| string blob_path_; |
| int blob_fd_{-1}; |
| off_t blob_file_size_{0}; |
| std::unique_ptr<BlobFileWriter> blob_file_; |
| std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_; |
| std::unique_ptr<ScopedFdCloser> blob_fd_closer_; |
| }; |
| |
| TEST_F(InplaceGeneratorTest, BlockDefaultValues) { |
| // Tests that a Block is initialized with the default values as a |
| // Vertex::kInvalidIndex. This is required by the delta generators. |
| Block block; |
| EXPECT_EQ(Vertex::kInvalidIndex, block.reader); |
| EXPECT_EQ(Vertex::kInvalidIndex, block.writer); |
| } |
| |
| TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) { |
| vector<Extent> remove_blocks; |
| AppendExtent(&remove_blocks, 3, 3); |
| AppendExtent(&remove_blocks, 7, 1); |
| vector<Extent> replace_blocks; |
| AppendExtent(&replace_blocks, 10, 2); |
| AppendExtent(&replace_blocks, 13, 2); |
| Vertex vertex; |
| InstallOperation& op = vertex.aop.op; |
| OpAppendExtent(&op, 4, 3); |
| OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file |
| OpAppendExtent(&op, 3, 1); |
| OpAppendExtent(&op, 7, 3); |
| |
| InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks); |
| |
| EXPECT_EQ(7, op.src_extents_size()); |
| EXPECT_EQ(11U, op.src_extents(0).start_block()); |
| EXPECT_EQ(1U, op.src_extents(0).num_blocks()); |
| EXPECT_EQ(13U, op.src_extents(1).start_block()); |
| EXPECT_EQ(1U, op.src_extents(1).num_blocks()); |
| EXPECT_EQ(6U, op.src_extents(2).start_block()); |
| EXPECT_EQ(1U, op.src_extents(2).num_blocks()); |
| EXPECT_EQ(kSparseHole, op.src_extents(3).start_block()); |
| EXPECT_EQ(4U, op.src_extents(3).num_blocks()); |
| EXPECT_EQ(10U, op.src_extents(4).start_block()); |
| EXPECT_EQ(1U, op.src_extents(4).num_blocks()); |
| EXPECT_EQ(14U, op.src_extents(5).start_block()); |
| EXPECT_EQ(1U, op.src_extents(5).num_blocks()); |
| EXPECT_EQ(8U, op.src_extents(6).start_block()); |
| EXPECT_EQ(2U, op.src_extents(6).num_blocks()); |
| } |
| |
| TEST_F(InplaceGeneratorTest, CutEdgesTest) { |
| Graph graph; |
| vector<Block> blocks(9); |
| |
| // Create nodes in graph |
| { |
| graph.resize(graph.size() + 1); |
| graph.back().aop.op.set_type(InstallOperation::MOVE); |
| // Reads from blocks 3, 5, 7 |
| vector<Extent> extents; |
| AppendBlockToExtents(&extents, 3); |
| AppendBlockToExtents(&extents, 5); |
| AppendBlockToExtents(&extents, 7); |
| StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); |
| blocks[3].reader = graph.size() - 1; |
| blocks[5].reader = graph.size() - 1; |
| blocks[7].reader = graph.size() - 1; |
| |
| // Writes to blocks 1, 2, 4 |
| extents.clear(); |
| AppendBlockToExtents(&extents, 1); |
| AppendBlockToExtents(&extents, 2); |
| AppendBlockToExtents(&extents, 4); |
| StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); |
| blocks[1].writer = graph.size() - 1; |
| blocks[2].writer = graph.size() - 1; |
| blocks[4].writer = graph.size() - 1; |
| } |
| { |
| graph.resize(graph.size() + 1); |
| graph.back().aop.op.set_type(InstallOperation::MOVE); |
| // Reads from blocks 1, 2, 4 |
| vector<Extent> extents; |
| AppendBlockToExtents(&extents, 1); |
| AppendBlockToExtents(&extents, 2); |
| AppendBlockToExtents(&extents, 4); |
| StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); |
| blocks[1].reader = graph.size() - 1; |
| blocks[2].reader = graph.size() - 1; |
| blocks[4].reader = graph.size() - 1; |
| |
| // Writes to blocks 3, 5, 6 |
| extents.clear(); |
| AppendBlockToExtents(&extents, 3); |
| AppendBlockToExtents(&extents, 5); |
| AppendBlockToExtents(&extents, 6); |
| StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); |
| blocks[3].writer = graph.size() - 1; |
| blocks[5].writer = graph.size() - 1; |
| blocks[6].writer = graph.size() - 1; |
| } |
| |
| // Create edges |
| InplaceGenerator::CreateEdges(&graph, blocks); |
| |
| // Find cycles |
| CycleBreaker cycle_breaker; |
| set<Edge> cut_edges; |
| cycle_breaker.BreakCycles(graph, &cut_edges); |
| |
| EXPECT_EQ(1U, cut_edges.size()); |
| EXPECT_TRUE(cut_edges.end() != |
| cut_edges.find(std::pair<Vertex::Index, Vertex::Index>(1, 0))); |
| |
| vector<CutEdgeVertexes> cuts; |
| EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts)); |
| |
| EXPECT_EQ(3U, graph.size()); |
| |
| // Check new node in graph: |
| EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type()); |
| EXPECT_EQ(2, graph.back().aop.op.src_extents_size()); |
| EXPECT_EQ(1, graph.back().aop.op.dst_extents_size()); |
| EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block()); |
| EXPECT_EQ(2U, graph.back().aop.op.dst_extents(0).num_blocks()); |
| EXPECT_TRUE(graph.back().out_edges.empty()); |
| |
| // Check that old node reads from new blocks |
| EXPECT_EQ(2, graph[0].aop.op.src_extents_size()); |
| EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block()); |
| EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks()); |
| EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block()); |
| EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks()); |
| |
| // And that the old dst extents haven't changed |
| EXPECT_EQ(2, graph[0].aop.op.dst_extents_size()); |
| EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block()); |
| EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks()); |
| EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block()); |
| EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks()); |
| |
| // Ensure it only depends on the next node and the new temp node |
| EXPECT_EQ(2U, graph[0].out_edges.size()); |
| EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1)); |
| EXPECT_TRUE(graph[0].out_edges.end() != |
| graph[0].out_edges.find(graph.size() - 1)); |
| |
| // Check second node has unchanged extents |
| EXPECT_EQ(2, graph[1].aop.op.src_extents_size()); |
| EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block()); |
| EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks()); |
| EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block()); |
| EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks()); |
| |
| EXPECT_EQ(2, graph[1].aop.op.dst_extents_size()); |
| EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block()); |
| EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks()); |
| EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block()); |
| EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks()); |
| |
| // Ensure it only depends on the next node |
| EXPECT_EQ(1U, graph[1].out_edges.size()); |
| EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2)); |
| } |
| |
| TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) { |
| Graph graph(9); |
| |
| const vector<Extent> empt; |
| uint64_t tmp = kTempBlockStart; |
| const string kFilename = "/foo"; |
| |
| vector<CutEdgeVertexes> cuts; |
| cuts.resize(3); |
| |
| // Simple broken loop: |
| GenVertex( |
| &graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", InstallOperation::MOVE); |
| GenVertex(&graph[1], |
| VectOfExt(tmp, 1), |
| VectOfExt(0, 1), |
| "", |
| InstallOperation::MOVE); |
| GenVertex(&graph[2], |
| VectOfExt(1, 1), |
| VectOfExt(tmp, 1), |
| "", |
| InstallOperation::MOVE); |
| // Corresponding edges: |
| graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1)); |
| graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1)); |
| graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1)); |
| // Store the cut: |
| cuts[0].old_dst = 1; |
| cuts[0].old_src = 0; |
| cuts[0].new_vertex = 2; |
| cuts[0].tmp_extents = VectOfExt(tmp, 1); |
| tmp++; |
| |
| // Slightly more complex pair of loops: |
| GenVertex( |
| &graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", InstallOperation::MOVE); |
| GenVertex( |
| &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE); |
| GenVertex(&graph[5], |
| VectOfExt(tmp, 3), |
| VectOfExt(4, 3), |
| kFilename, |
| InstallOperation::MOVE); |
| GenVertex(&graph[6], |
| VectOfExt(2, 2), |
| VectOfExt(tmp, 2), |
| "", |
| InstallOperation::MOVE); |
| GenVertex(&graph[7], |
| VectOfExt(7, 1), |
| VectOfExt(tmp + 2, 1), |
| "", |
| InstallOperation::MOVE); |
| // Corresponding edges: |
| graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2)); |
| graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1)); |
| graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2)); |
| graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1)); |
| graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2)); |
| graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1)); |
| // Store the cuts: |
| cuts[1].old_dst = 5; |
| cuts[1].old_src = 3; |
| cuts[1].new_vertex = 6; |
| cuts[1].tmp_extents = VectOfExt(tmp, 2); |
| cuts[2].old_dst = 5; |
| cuts[2].old_src = 4; |
| cuts[2].new_vertex = 7; |
| cuts[2].tmp_extents = VectOfExt(tmp + 2, 1); |
| |
| // Supplier of temp block: |
| GenVertex(&graph[8], empt, VectOfExt(8, 1), "", InstallOperation::REPLACE); |
| |
| // Specify the final order: |
| vector<Vertex::Index> op_indexes; |
| op_indexes.push_back(2); |
| op_indexes.push_back(0); |
| op_indexes.push_back(1); |
| op_indexes.push_back(6); |
| op_indexes.push_back(3); |
| op_indexes.push_back(7); |
| op_indexes.push_back(4); |
| op_indexes.push_back(5); |
| op_indexes.push_back(8); |
| |
| vector<vector<Vertex::Index>::size_type> reverse_op_indexes; |
| InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes, |
| &reverse_op_indexes); |
| |
| CreateBlobFile(); |
| EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph, |
| "/dev/zero", |
| blob_file_.get(), |
| &op_indexes, |
| &reverse_op_indexes, |
| cuts)); |
| EXPECT_FALSE(graph[6].valid); |
| EXPECT_FALSE(graph[7].valid); |
| EXPECT_EQ(1, graph[1].aop.op.src_extents_size()); |
| EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block()); |
| EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks()); |
| EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type()); |
| } |
| |
| TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) { |
| Graph graph(4); |
| graph[0].aop.name = "A"; |
| graph[0].aop.op.set_type(InstallOperation::REPLACE); |
| graph[1].aop.name = "B"; |
| graph[1].aop.op.set_type(InstallOperation::BSDIFF); |
| graph[2].aop.name = "C"; |
| graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ); |
| graph[3].aop.name = "D"; |
| graph[3].aop.op.set_type(InstallOperation::MOVE); |
| |
| vector<Vertex::Index> vect(graph.size()); |
| |
| for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) { |
| vect[i] = i; |
| } |
| InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect); |
| EXPECT_EQ(vect.size(), graph.size()); |
| EXPECT_EQ(graph[vect[0]].aop.name, "B"); |
| EXPECT_EQ(graph[vect[1]].aop.name, "D"); |
| EXPECT_EQ(graph[vect[2]].aop.name, "A"); |
| EXPECT_EQ(graph[vect[3]].aop.name, "C"); |
| } |
| |
| TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) { |
| Graph graph(9); |
| const vector<Extent> empt; // empty |
| const string kFilename = "/foo"; |
| |
| // Some scratch space: |
| GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE); |
| GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE); |
| GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE); |
| |
| // A cycle that requires 10 blocks to break: |
| GenVertex(&graph[3], |
| VectOfExt(10, 11), |
| VectOfExt(0, 9), |
| "", |
| InstallOperation::BSDIFF); |
| graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9)); |
| GenVertex(&graph[4], |
| VectOfExt(0, 9), |
| VectOfExt(10, 11), |
| "", |
| InstallOperation::BSDIFF); |
| graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); |
| |
| // A cycle that requires 9 blocks to break: |
| GenVertex(&graph[5], |
| VectOfExt(40, 11), |
| VectOfExt(30, 10), |
| "", |
| InstallOperation::BSDIFF); |
| graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10)); |
| GenVertex(&graph[6], |
| VectOfExt(30, 10), |
| VectOfExt(40, 11), |
| "", |
| InstallOperation::BSDIFF); |
| graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); |
| |
| // A cycle that requires 40 blocks to break (which is too many): |
| GenVertex(&graph[7], |
| VectOfExt(120, 50), |
| VectOfExt(60, 40), |
| "", |
| InstallOperation::BSDIFF); |
| graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40)); |
| GenVertex(&graph[8], |
| VectOfExt(60, 40), |
| VectOfExt(120, 50), |
| kFilename, |
| InstallOperation::BSDIFF); |
| graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); |
| |
| graph_utils::DumpGraph(graph); |
| |
| vector<Vertex::Index> final_order; |
| |
| CreateBlobFile(); |
| EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph, |
| "/dev/zero", |
| blob_file_.get(), |
| &final_order, |
| Vertex::kInvalidIndex)); |
| |
| Graph expected_graph(12); |
| GenVertex(&expected_graph[0], |
| empt, |
| VectOfExt(200, 1), |
| "", |
| InstallOperation::REPLACE); |
| GenVertex(&expected_graph[1], |
| empt, |
| VectOfExt(210, 10), |
| "", |
| InstallOperation::REPLACE); |
| GenVertex(&expected_graph[2], |
| empt, |
| VectOfExt(220, 1), |
| "", |
| InstallOperation::REPLACE); |
| GenVertex(&expected_graph[3], |
| VectOfExt(10, 11), |
| VectOfExt(0, 9), |
| "", |
| InstallOperation::BSDIFF); |
| expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9)); |
| GenVertex(&expected_graph[4], |
| VectOfExt(60, 9), |
| VectOfExt(10, 11), |
| "", |
| InstallOperation::BSDIFF); |
| expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); |
| expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9)); |
| GenVertex(&expected_graph[5], |
| VectOfExt(40, 11), |
| VectOfExt(30, 10), |
| "", |
| InstallOperation::BSDIFF); |
| expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10)); |
| |
| GenVertex(&expected_graph[6], |
| VectOfExt(60, 10), |
| VectOfExt(40, 11), |
| "", |
| InstallOperation::BSDIFF); |
| expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); |
| expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10)); |
| |
| GenVertex(&expected_graph[7], |
| VectOfExt(120, 50), |
| VectOfExt(60, 40), |
| "", |
| InstallOperation::BSDIFF); |
| expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10)); |
| |
| GenVertex(&expected_graph[8], |
| empt, |
| VectOfExt(0, 50), |
| "/foo", |
| InstallOperation::REPLACE_BZ); |
| expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); |
| |
| GenVertex(&expected_graph[9], |
| VectOfExt(0, 9), |
| VectOfExt(60, 9), |
| "", |
| InstallOperation::MOVE); |
| |
| GenVertex(&expected_graph[10], |
| VectOfExt(30, 10), |
| VectOfExt(60, 10), |
| "", |
| InstallOperation::MOVE); |
| expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9)); |
| |
| EXPECT_EQ(12U, graph.size()); |
| EXPECT_FALSE(graph.back().valid); |
| for (Graph::size_type i = 0; i < graph.size() - 1; i++) { |
| EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges); |
| if (i == 8) { |
| // special case |
| } else { |
| // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i; |
| } |
| } |
| } |
| |
| TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) { |
| Vertex vertex; |
| InplaceGenerator::CreateScratchNode(12, 34, &vertex); |
| EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type()); |
| EXPECT_EQ(0U, vertex.aop.op.data_offset()); |
| EXPECT_EQ(0U, vertex.aop.op.data_length()); |
| EXPECT_EQ(1, vertex.aop.op.dst_extents_size()); |
| EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block()); |
| EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks()); |
| } |
| |
| TEST_F(InplaceGeneratorTest, ApplyMapTest) { |
| vector<uint64_t> collection = {1, 2, 3, 4, 6}; |
| vector<uint64_t> expected_values = {1, 2, 5, 4, 8}; |
| map<uint64_t, uint64_t> value_map; |
| value_map[3] = 5; |
| value_map[6] = 8; |
| value_map[5] = 10; |
| |
| InplaceGenerator::ApplyMap(&collection, value_map); |
| EXPECT_EQ(expected_values, collection); |
| } |
| |
| // We can't produce MOVE operations with a source or destination in the block 0. |
| // This test checks that the cycle breaker procedure doesn't produce such |
| // operations. |
| TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) { |
| size_t block_size = 4096; |
| size_t num_blocks = 4; |
| vector<AnnotatedOperation> aops; |
| |
| // Create a REPLACE_BZ for block 0, and a circular dependency among all other |
| // blocks. This situation would prefer to issue a MOVE to scratch space and |
| // the only available block is 0. |
| aops.emplace_back(); |
| aops.back().name = base::StringPrintf("<bz-block-0>"); |
| aops.back().op.set_type(InstallOperation::REPLACE_BZ); |
| StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents()); |
| |
| for (size_t i = 1; i < num_blocks; i++) { |
| AnnotatedOperation aop; |
| aop.name = base::StringPrintf("<op-%" PRIuS ">", i); |
| aop.op.set_type(InstallOperation::BSDIFF); |
| StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)}, |
| aop.op.mutable_src_extents()); |
| StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents()); |
| aops.push_back(aop); |
| } |
| |
| PartitionConfig part("part"); |
| part.path = "/dev/zero"; |
| part.size = num_blocks * block_size; |
| |
| CreateBlobFile(); |
| |
| // We ran two tests here. The first one without enough blocks for the scratch |
| // space, forcing it to create a new full operation and the second case with |
| // one extra block in the partition that can be used for the move operation. |
| for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) { |
| SCOPED_TRACE( |
| base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks)); |
| vector<AnnotatedOperation> result_aops = aops; |
| EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies( |
| part, |
| part, |
| part_blocks * block_size, |
| block_size, |
| blob_file_.get(), |
| &result_aops)); |
| |
| size_t full_ops = 0; |
| for (const auto& aop : result_aops) { |
| if (diff_utils::IsAReplaceOperation(aop.op.type())) |
| full_ops++; |
| |
| if (aop.op.type() != InstallOperation::MOVE) |
| continue; |
| for (const Extent& extent : aop.op.src_extents()) { |
| EXPECT_NE(0U, extent.start_block()) |
| << "On src extents for aop: " << aop; |
| } |
| for (const Extent& extent : aop.op.dst_extents()) { |
| EXPECT_NE(0U, extent.start_block()) |
| << "On dst extents for aop: " << aop; |
| } |
| } |
| |
| // If there's extra space in the partition, it should not use a new full |
| // operation for it. |
| EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops); |
| |
| DumpAopsOnFailure(result_aops); |
| } |
| } |
| |
| // Test that we can shrink a filesystem and break cycles. |
| TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) { |
| size_t block_size = 4096; |
| size_t old_blocks = 10; |
| size_t new_blocks = 8; |
| vector<AnnotatedOperation> aops; |
| |
| // Create a loop using the blocks 1-6 and one other operation writing to the |
| // block 7 from outside the new partition. The loop in the blocks 1-6 uses |
| // two-block operations, so it needs two blocks of scratch space. It can't use |
| // the block 0 as scratch space (see previous test) and it can't use the |
| // blocks 7 or 8 due the last move operation. |
| |
| aops.emplace_back(); |
| aops.back().name = base::StringPrintf("<bz-block-0>"); |
| aops.back().op.set_type(InstallOperation::REPLACE_BZ); |
| StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents()); |
| |
| const size_t num_ops = 3; |
| for (size_t i = 0; i < num_ops; i++) { |
| AnnotatedOperation aop; |
| aop.name = base::StringPrintf("<op-%" PRIuS ">", i); |
| aop.op.set_type(InstallOperation::BSDIFF); |
| StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents()); |
| StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)}, |
| aop.op.mutable_dst_extents()); |
| aops.push_back(aop); |
| } |
| |
| { |
| AnnotatedOperation aop; |
| aop.name = "<op-shrink>"; |
| aop.op.set_type(InstallOperation::BSDIFF); |
| StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents()); |
| StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents()); |
| aops.push_back(aop); |
| } |
| |
| PartitionConfig old_part("part"); |
| old_part.path = "/dev/zero"; |
| old_part.size = old_blocks * block_size; |
| |
| PartitionConfig new_part("part"); |
| new_part.path = "/dev/zero"; |
| new_part.size = new_blocks * block_size; |
| |
| CreateBlobFile(); |
| |
| EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies( |
| old_part, |
| new_part, |
| (old_blocks + 2) * block_size, // enough scratch space. |
| block_size, |
| blob_file_.get(), |
| &aops)); |
| |
| size_t full_ops = 0; |
| for (const auto& aop : aops) { |
| if (diff_utils::IsAReplaceOperation(aop.op.type())) |
| full_ops++; |
| } |
| // There should be only one REPLACE* operation, the one we added for block 0. |
| EXPECT_EQ(1U, full_ops); |
| |
| // There should be only one MOVE operation, the one used to break the loop |
| // which should write to scratch space past the block 7 (the last block of the |
| // new partition) which is being written later. |
| size_t move_ops = 0; |
| for (const auto& aop : aops) { |
| if (aop.op.type() == InstallOperation::MOVE) { |
| move_ops++; |
| for (const Extent& extent : aop.op.dst_extents()) { |
| EXPECT_LE(7U, extent.start_block()) |
| << "On dst extents for aop: " << aop; |
| } |
| } |
| } |
| EXPECT_EQ(1U, move_ops); |
| |
| DumpAopsOnFailure(aops); |
| } |
| |
| } // namespace chromeos_update_engine |
