1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2015 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 16cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 17cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/inplace_generator.h" 18cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 1914158570d3995008dc93a628004118b87a6bca01Alex Deymo#include <map> 20cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <set> 21cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <sstream> 22cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <string> 23cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <utility> 24cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <vector> 25cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 26896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo#include <base/format_macros.h> 27cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <base/logging.h> 28cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <base/strings/string_util.h> 29896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo#include <base/strings/stringprintf.h> 30cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include <gtest/gtest.h> 31cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 3239910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/common/test_utils.h" 3339910dcd1d68987ccee7c3031dc269233a8490bbAlex Deymo#include "update_engine/common/utils.h" 34cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/cycle_breaker.h" 35cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/delta_diff_generator.h" 3605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo#include "update_engine/payload_generator/delta_diff_utils.h" 371beda780333ce51d7872603b70712772eb2383fbAlex Deymo#include "update_engine/payload_generator/extent_ranges.h" 38cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/graph_types.h" 395c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo#include "update_engine/payload_generator/graph_utils.h" 40cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 4114158570d3995008dc93a628004118b87a6bca01Alex Deymousing std::map; 42cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::set; 43cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::string; 44cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::stringstream; 45cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::vector; 46cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 47cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace chromeos_update_engine { 48cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 496b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymousing Block = InplaceGenerator::Block; 50cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 51cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace { 52cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 53cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid GenVertex(Vertex* out, 54cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& src_extents, 55cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& dst_extents, 56cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string& path, 57a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation_Type type) { 583b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo out->aop.op.set_type(type); 593b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo out->aop.name = path; 603b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(src_extents, out->aop.op.mutable_src_extents()); 613b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(dst_extents, out->aop.op.mutable_dst_extents()); 62cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 63cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 64cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) { 65cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return vector<Extent>(1, ExtentForRange(start_block, num_blocks)); 66cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 67cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 68cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodEdgeProperties EdgeWithReadDep(const vector<Extent>& extents) { 69cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties ret; 70cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.extents = extents; 71cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return ret; 72cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 73cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 74cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodEdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) { 75cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties ret; 76cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.write_extents = extents; 77cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return ret; 78cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 79cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 80cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodtemplate<typename T> 81cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid DumpVect(const vector<T>& vect) { 82cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood stringstream ss(stringstream::out); 83cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end(); 84cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood it != e; ++it) { 85cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ss << *it << ", "; 86cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 87cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "{" << ss.str() << "}"; 88cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 89cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 90cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) { 91cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->resize(vect->size() + 1); 92cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->back().set_start_block(start); 93cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->back().set_num_blocks(length); 94cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 95cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 96a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymovoid OpAppendExtent(InstallOperation* op, uint64_t start, uint64_t length) { 97cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Extent* extent = op->add_src_extents(); 98cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_start_block(start); 99cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_num_blocks(length); 100cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 101cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 102cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace 103cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 104cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodclass InplaceGeneratorTest : public ::testing::Test { 105896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo protected: 106896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables 107896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // with a new blob file. The file is closed and removed automatically when 108896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // the test finishes. 109896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo void CreateBlobFile() { 110896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a 111896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // previous instance before overriding blob_fd_. 112896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_fd_closer_.reset(); 113896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_TRUE(utils::MakeTempFile( 114896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_)); 115896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_)); 116896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_)); 117896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_file_size_ = 0; 118896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_GE(blob_fd_, 0); 1198cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_)); 120896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 121896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 12205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // Dump the list of operations |aops| in case of test failure. 12305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) { 12405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo if (HasNonfatalFailure()) { 12505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo LOG(INFO) << "Result operation list:"; 12605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo for (const auto& aop : aops) { 12705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo LOG(INFO) << aop; 12805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 12905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 13005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 13105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 132896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Blob file name, file descriptor and file size used to store operation 133896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blobs. 134896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo string blob_path_; 135896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo int blob_fd_{-1}; 136896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo off_t blob_file_size_{0}; 1378cc502dacbccdab96824d42287f230ce04004784Sen Jiang std::unique_ptr<BlobFileWriter> blob_file_; 138896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_; 139896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo std::unique_ptr<ScopedFdCloser> blob_fd_closer_; 140cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood}; 141cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 1426b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, BlockDefaultValues) { 1436b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // Tests that a Block is initialized with the default values as a 1446b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // Vertex::kInvalidIndex. This is required by the delta generators. 1456b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo Block block; 1466b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo EXPECT_EQ(Vertex::kInvalidIndex, block.reader); 1476b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo EXPECT_EQ(Vertex::kInvalidIndex, block.writer); 1486b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo} 1496b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo 150cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, SubstituteBlocksTest) { 151cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> remove_blocks; 152cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&remove_blocks, 3, 3); 153cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&remove_blocks, 7, 1); 154cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> replace_blocks; 155cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&replace_blocks, 10, 2); 156cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&replace_blocks, 13, 2); 157cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex vertex; 158a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation& op = vertex.aop.op; 159cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 4, 3); 160cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file 161cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 3, 1); 162cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 7, 3); 163cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 164cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks); 165cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 166cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(7, op.src_extents_size()); 16780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(11U, op.src_extents(0).start_block()); 16880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(0).num_blocks()); 16980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(13U, op.src_extents(1).start_block()); 17080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(1).num_blocks()); 17180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(6U, op.src_extents(2).start_block()); 17280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(2).num_blocks()); 173cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(kSparseHole, op.src_extents(3).start_block()); 17480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, op.src_extents(3).num_blocks()); 17580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(10U, op.src_extents(4).start_block()); 17680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(4).num_blocks()); 17780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(14U, op.src_extents(5).start_block()); 17880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(5).num_blocks()); 17980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(8U, op.src_extents(6).start_block()); 18080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, op.src_extents(6).num_blocks()); 181cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 182cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 183cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, CutEdgesTest) { 184cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph; 185cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Block> blocks(9); 186cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 187cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Create nodes in graph 188cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood { 189cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph.resize(graph.size() + 1); 190a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph.back().aop.op.set_type(InstallOperation::MOVE); 191cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Reads from blocks 3, 5, 7 192cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> extents; 1935c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 3); 1945c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 5); 1955c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 7); 1963b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); 197cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[3].reader = graph.size() - 1; 198cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[5].reader = graph.size() - 1; 199cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[7].reader = graph.size() - 1; 200cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 201cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Writes to blocks 1, 2, 4 202cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extents.clear(); 2035c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 1); 2045c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 2); 2055c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 4); 2063b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); 207cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[1].writer = graph.size() - 1; 208cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[2].writer = graph.size() - 1; 209cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[4].writer = graph.size() - 1; 210cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 211cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood { 212cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph.resize(graph.size() + 1); 213a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph.back().aop.op.set_type(InstallOperation::MOVE); 214cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Reads from blocks 1, 2, 4 215cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> extents; 2165c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 1); 2175c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 2); 2185c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 4); 2193b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); 220cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[1].reader = graph.size() - 1; 221cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[2].reader = graph.size() - 1; 222cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[4].reader = graph.size() - 1; 223cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 224cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Writes to blocks 3, 5, 6 225cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extents.clear(); 2265c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 3); 2275c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 5); 2285c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 6); 2293b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); 230cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[3].writer = graph.size() - 1; 231cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[5].writer = graph.size() - 1; 232cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[6].writer = graph.size() - 1; 233cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 234cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 235cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Create edges 236cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::CreateEdges(&graph, blocks); 237cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 238cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Find cycles 239cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CycleBreaker cycle_breaker; 240cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood set<Edge> cut_edges; 241cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cycle_breaker.BreakCycles(graph, &cut_edges); 242cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 24380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, cut_edges.size()); 244cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(cut_edges.end() != cut_edges.find( 245cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood std::pair<Vertex::Index, Vertex::Index>(1, 0))); 246cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 247cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 248cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts)); 249cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 25080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(3U, graph.size()); 251cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 252cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check new node in graph: 253a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type()); 2543b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph.back().aop.op.src_extents_size()); 2553b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, graph.back().aop.op.dst_extents_size()); 2563b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block()); 25780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph.back().aop.op.dst_extents(0).num_blocks()); 258cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph.back().out_edges.empty()); 259cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 260cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check that old node reads from new blocks 2613b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[0].aop.op.src_extents_size()); 2623b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block()); 26380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks()); 26480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block()); 26580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks()); 266cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 267cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // And that the old dst extents haven't changed 2683b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[0].aop.op.dst_extents_size()); 26980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block()); 27080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks()); 27180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block()); 27280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks()); 273cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 274cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Ensure it only depends on the next node and the new temp node 27580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].out_edges.size()); 276cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1)); 277cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() - 278cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 1)); 279cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 280cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check second node has unchanged extents 2813b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[1].aop.op.src_extents_size()); 28280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block()); 28380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks()); 28480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block()); 28580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks()); 2863b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 2873b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[1].aop.op.dst_extents_size()); 28880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block()); 28980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks()); 29080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block()); 29180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks()); 292cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 293cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Ensure it only depends on the next node 29480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].out_edges.size()); 295cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2)); 296cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 297cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 2986b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) { 299cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(9); 300cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 301cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent> empt; 302cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t tmp = kTempBlockStart; 303cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string kFilename = "/foo"; 304cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 305cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 306cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.resize(3); 307cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 308cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Simple broken loop: 309a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 310a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", InstallOperation::MOVE); 311a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[1], 312a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 1), 313a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 1), 314a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 315a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 316a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[2], 317a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(1, 1), 318a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 1), 319a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 320a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 321cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Corresponding edges: 322cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1)); 323cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1)); 324cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1)); 325cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Store the cut: 326cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].old_dst = 1; 327cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].old_src = 0; 328cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].new_vertex = 2; 329cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].tmp_extents = VectOfExt(tmp, 1); 330cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood tmp++; 331cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 332cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Slightly more complex pair of loops: 333a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 334a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", InstallOperation::MOVE); 335a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 336a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE); 337a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[5], 338a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 3), 339a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(4, 3), 340a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo kFilename, 341a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 342a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[6], 343a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(2, 2), 344a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 2), 345a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 346a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 347a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[7], 348a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(7, 1), 349a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp + 2, 1), 350a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 351a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 352cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Corresponding edges: 353cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2)); 354cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1)); 355cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2)); 356cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1)); 357cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2)); 358cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1)); 359cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Store the cuts: 360cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].old_dst = 5; 361cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].old_src = 3; 362cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].new_vertex = 6; 363cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].tmp_extents = VectOfExt(tmp, 2); 364cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].old_dst = 5; 365cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].old_src = 4; 366cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].new_vertex = 7; 367cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].tmp_extents = VectOfExt(tmp + 2, 1); 368cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 369cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Supplier of temp block: 370a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[8], empt, VectOfExt(8, 1), "", InstallOperation::REPLACE); 371cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 372cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Specify the final order: 373cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> op_indexes; 374cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(2); 375cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(0); 376cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(1); 377cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(6); 378cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(3); 379cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(7); 380cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(4); 381cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(5); 382cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(8); 383cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 384cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type> reverse_op_indexes; 385cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes, 386cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &reverse_op_indexes); 387cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 388896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 389cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph, 390568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood "/dev/zero", 3918cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.get(), 392cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &op_indexes, 393cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &reverse_op_indexes, 394cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts)); 395cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph[6].valid); 396cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph[7].valid); 3973b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, graph[1].aop.op.src_extents_size()); 39880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block()); 39980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks()); 400a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type()); 401cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 402cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 4033b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex DeymoTEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) { 404cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(4); 4053b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[0].aop.name = "A"; 406a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[0].aop.op.set_type(InstallOperation::REPLACE); 4073b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[1].aop.name = "B"; 408a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[1].aop.op.set_type(InstallOperation::BSDIFF); 4093b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[2].aop.name = "C"; 410a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ); 4113b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[3].aop.name = "D"; 412a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[3].aop.op.set_type(InstallOperation::MOVE); 413cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 414cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> vect(graph.size()); 415cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 416cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) { 417cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect[i] = i; 418cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 4193b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect); 420cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(vect.size(), graph.size()); 4213b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[0]].aop.name, "B"); 4223b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[1]].aop.name, "D"); 4233b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[2]].aop.name, "A"); 4243b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[3]].aop.name, "C"); 425cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 426cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 4276b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, AssignTempBlocksTest) { 428cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(9); 429cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent> empt; // empty 430cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string kFilename = "/foo"; 431cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 432cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Some scratch space: 433a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE); 434a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE); 435a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE); 436cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 437cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 10 blocks to break: 438a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[3], 439a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(10, 11), 440a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 9), 441a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 442a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 443cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9)); 444a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[4], 445a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 9), 446a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(10, 11), 447a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 448a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 449cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); 450cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 451cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 9 blocks to break: 452a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[5], 453a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(40, 11), 454a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(30, 10), 455a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 456a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 457cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10)); 458a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[6], 459a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(30, 10), 460a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(40, 11), 461a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 462a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 463cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); 464cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 465cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 40 blocks to break (which is too many): 466cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&graph[7], 467cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 468cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 469cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 470a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 471cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40)); 472cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&graph[8], 473cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 474cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 475cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood kFilename, 476a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 477cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); 478cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 479cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::DumpGraph(graph); 480cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 481cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> final_order; 482cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 483896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 484cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph, 485568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood "/dev/zero", 4868cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.get(), 487cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &final_order, 488cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::kInvalidIndex)); 489cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 490cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph expected_graph(12); 491a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[0], 492a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 493a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(200, 1), 494a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 495a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 496a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[1], 497a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 498a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(210, 10), 499a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 500a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 501a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[2], 502a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 503a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(220, 1), 504a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 505a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 506cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[3], 507cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(10, 11), 508cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(0, 9), 509cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 510a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 511cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9)); 512cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[4], 513cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 9), 514cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(10, 11), 515cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 516a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 517cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); 518cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9)); 519cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[5], 520cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(40, 11), 521cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(30, 10), 522cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 523a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 524cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10)); 525cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 526cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[6], 527cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 10), 528cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(40, 11), 529cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 530a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 531cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); 532cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10)); 533cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 534cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[7], 535cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 536cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 537cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 538a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 539cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10)); 540cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 541a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[8], 542a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 543a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 50), 544a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "/foo", 545a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE_BZ); 546cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); 547cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 548cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[9], 549cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(0, 9), 550cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 9), 551cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 552a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 553cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 554cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[10], 555cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(30, 10), 556cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 10), 557cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 558a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 559cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9)); 560cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 56180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(12U, graph.size()); 562cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph.back().valid); 563cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (Graph::size_type i = 0; i < graph.size() - 1; i++) { 564cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges); 565cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (i == 8) { 566cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // special case 567cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } else { 568cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i; 569cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 570cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 571cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 572cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 573cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, CreateScratchNodeTest) { 574cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex vertex; 575cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::CreateScratchNode(12, 34, &vertex); 576a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type()); 57780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(0U, vertex.aop.op.data_offset()); 57880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(0U, vertex.aop.op.data_length()); 5793b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, vertex.aop.op.dst_extents_size()); 58080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block()); 58180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks()); 582cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 583cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 58414158570d3995008dc93a628004118b87a6bca01Alex DeymoTEST_F(InplaceGeneratorTest, ApplyMapTest) { 58514158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> collection = {1, 2, 3, 4, 6}; 58614158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> expected_values = {1, 2, 5, 4, 8}; 58714158570d3995008dc93a628004118b87a6bca01Alex Deymo map<uint64_t, uint64_t> value_map; 58814158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[3] = 5; 58914158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[6] = 8; 59014158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[5] = 10; 59114158570d3995008dc93a628004118b87a6bca01Alex Deymo 59214158570d3995008dc93a628004118b87a6bca01Alex Deymo InplaceGenerator::ApplyMap(&collection, value_map); 59314158570d3995008dc93a628004118b87a6bca01Alex Deymo EXPECT_EQ(expected_values, collection); 59414158570d3995008dc93a628004118b87a6bca01Alex Deymo} 59514158570d3995008dc93a628004118b87a6bca01Alex Deymo 596896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// We can't produce MOVE operations with a source or destination in the block 0. 597896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// This test checks that the cycle breaker procedure doesn't produce such 598896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// operations. 599896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex DeymoTEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) { 600896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t block_size = 4096; 601896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t num_blocks = 4; 602896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo vector<AnnotatedOperation> aops; 603896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 604896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Create a REPLACE_BZ for block 0, and a circular dependency among all other 605896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blocks. This situation would prefer to issue a MOVE to scratch space and 606896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // the only available block is 0. 607896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.emplace_back(); 608896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.back().name = base::StringPrintf("<bz-block-0>"); 609a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo aops.back().op.set_type(InstallOperation::REPLACE_BZ); 610896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents()); 611896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 612896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (size_t i = 1; i < num_blocks; i++) { 613896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo AnnotatedOperation aop; 614896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aop.name = base::StringPrintf("<op-%" PRIuS ">", i); 615a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo aop.op.set_type(InstallOperation::BSDIFF); 616896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)}, 617896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aop.op.mutable_src_extents()); 618896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents()); 619896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.push_back(aop); 620896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 621896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 622625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang PartitionConfig part("part"); 623896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo part.path = "/dev/zero"; 624896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo part.size = num_blocks * block_size; 625896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 626896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 627896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 628896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // We ran two tests here. The first one without enough blocks for the scratch 629896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // space, forcing it to create a new full operation and the second case with 630896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // one extra block in the partition that can be used for the move operation. 631896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) { 63205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo SCOPED_TRACE( 63305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks)); 634896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo vector<AnnotatedOperation> result_aops = aops; 635896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies( 63605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo part, 63705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo part, 63805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo part_blocks * block_size, 63905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo block_size, 64005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo blob_file_.get(), 64105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo &result_aops)); 642896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 643896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t full_ops = 0; 644896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const auto& aop : result_aops) { 64505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo if (diff_utils::IsAReplaceOperation(aop.op.type())) 646896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo full_ops++; 647896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 648a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if (aop.op.type() != InstallOperation::MOVE) 649896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo continue; 650896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const Extent& extent : aop.op.src_extents()) { 65180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_NE(0U, extent.start_block()) 65280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo << "On src extents for aop: " << aop; 653896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 654896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const Extent& extent : aop.op.dst_extents()) { 65580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_NE(0U, extent.start_block()) 65680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo << "On dst extents for aop: " << aop; 657896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 658896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 659896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 660896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // If there's extra space in the partition, it should not use a new full 661896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // operation for it. 66280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops); 663896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 66405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo DumpAopsOnFailure(result_aops); 66505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 66605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo} 66705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 66805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo// Test that we can shrink a filesystem and break cycles. 66905871fab8b32938ad66ce230250ff6db5563bd7aAlex DeymoTEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) { 67005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo size_t block_size = 4096; 67105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo size_t old_blocks = 10; 67205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo size_t new_blocks = 8; 67305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo vector<AnnotatedOperation> aops; 67405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 67505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // Create a loop using the blocks 1-6 and one other operation writing to the 67605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // block 7 from outside the new partition. The loop in the blocks 1-6 uses 67705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // two-block operations, so it needs two blocks of scratch space. It can't use 67805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // the block 0 as scratch space (see previous test) and it can't use the 67905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // blocks 7 or 8 due the last move operation. 68005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 68105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aops.emplace_back(); 68205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aops.back().name = base::StringPrintf("<bz-block-0>"); 68305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aops.back().op.set_type(InstallOperation::REPLACE_BZ); 68405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents()); 68505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 68605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo const size_t num_ops = 3; 68705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo for (size_t i = 0; i < num_ops; i++) { 68805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo AnnotatedOperation aop; 68905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aop.name = base::StringPrintf("<op-%" PRIuS ">", i); 69005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aop.op.set_type(InstallOperation::BSDIFF); 69105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents()); 69205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)}, 69305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aop.op.mutable_dst_extents()); 69405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aops.push_back(aop); 69505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 69605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 69705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo { 69805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo AnnotatedOperation aop; 69905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aop.name = "<op-shrink>"; 70005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aop.op.set_type(InstallOperation::BSDIFF); 70105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents()); 70205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents()); 70305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo aops.push_back(aop); 70405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 70505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 70605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo PartitionConfig old_part("part"); 70705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo old_part.path = "/dev/zero"; 70805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo old_part.size = old_blocks * block_size; 70905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 71005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo PartitionConfig new_part("part"); 71105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo new_part.path = "/dev/zero"; 71205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo new_part.size = new_blocks * block_size; 71305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 71405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo CreateBlobFile(); 71505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 71605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies( 71705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo old_part, 71805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo new_part, 71905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo (old_blocks + 2) * block_size, // enough scratch space. 72005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo block_size, 72105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo blob_file_.get(), 72205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo &aops)); 72305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 72405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo size_t full_ops = 0; 72505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo for (const auto& aop : aops) { 72605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo if (diff_utils::IsAReplaceOperation(aop.op.type())) 72705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo full_ops++; 72805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo } 72905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // There should be only one REPLACE* operation, the one we added for block 0. 73005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo EXPECT_EQ(1U, full_ops); 73105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 73205871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // There should be only one MOVE operation, the one used to break the loop 73305871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // which should write to scratch space past the block 7 (the last block of the 73405871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo // new partition) which is being written later. 73505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo size_t move_ops = 0; 73605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo for (const auto& aop : aops) { 73705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo if (aop.op.type() == InstallOperation::MOVE) { 73805871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo move_ops++; 73905871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo for (const Extent& extent : aop.op.dst_extents()) { 74005871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo EXPECT_LE(7U, extent.start_block()) << "On dst extents for aop: " 74105871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo << aop; 742896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 743896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 744896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 74505871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo EXPECT_EQ(1U, move_ops); 74605871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo 74705871fab8b32938ad66ce230250ff6db5563bd7aAlex Deymo DumpAopsOnFailure(aops); 748896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo} 749896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 750cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace chromeos_update_engine 751