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" 361beda780333ce51d7872603b70712772eb2383fbAlex Deymo#include "update_engine/payload_generator/extent_ranges.h" 37cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood#include "update_engine/payload_generator/graph_types.h" 385c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo#include "update_engine/payload_generator/graph_utils.h" 39cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 4014158570d3995008dc93a628004118b87a6bca01Alex Deymousing std::map; 41cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::set; 42cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::string; 43cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::stringstream; 44cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodusing std::vector; 45cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 46cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace chromeos_update_engine { 47cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 486b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymousing Block = InplaceGenerator::Block; 49cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 50cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodnamespace { 51cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 52cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid GenVertex(Vertex* out, 53cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& src_extents, 54cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent>& dst_extents, 55cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string& path, 56a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation_Type type) { 573b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo out->aop.op.set_type(type); 583b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo out->aop.name = path; 593b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(src_extents, out->aop.op.mutable_src_extents()); 603b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(dst_extents, out->aop.op.mutable_dst_extents()); 61cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 62cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 63cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) { 64cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return vector<Extent>(1, ExtentForRange(start_block, num_blocks)); 65cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 66cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 67cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodEdgeProperties EdgeWithReadDep(const vector<Extent>& extents) { 68cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties ret; 69cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.extents = extents; 70cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return ret; 71cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 72cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 73cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodEdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) { 74cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EdgeProperties ret; 75cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ret.write_extents = extents; 76cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood return ret; 77cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 78cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 79cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodtemplate<typename T> 80cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid DumpVect(const vector<T>& vect) { 81cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood stringstream ss(stringstream::out); 82cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end(); 83cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood it != e; ++it) { 84cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood ss << *it << ", "; 85cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 86cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood LOG(INFO) << "{" << ss.str() << "}"; 87cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 88cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 89cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodvoid AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) { 90cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->resize(vect->size() + 1); 91cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->back().set_start_block(start); 92cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect->back().set_num_blocks(length); 93cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 94cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 95a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymovoid OpAppendExtent(InstallOperation* op, uint64_t start, uint64_t length) { 96cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Extent* extent = op->add_src_extents(); 97cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_start_block(start); 98cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extent->set_num_blocks(length); 99cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 100cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 101cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace 102cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 103cd514b531a38da1497630fa68b6e3ef45871893dAllie Woodclass InplaceGeneratorTest : public ::testing::Test { 104896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo protected: 105896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables 106896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // with a new blob file. The file is closed and removed automatically when 107896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // the test finishes. 108896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo void CreateBlobFile() { 109896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a 110896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // previous instance before overriding blob_fd_. 111896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_fd_closer_.reset(); 112896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_TRUE(utils::MakeTempFile( 113896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_)); 114896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_)); 115896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_)); 116896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo blob_file_size_ = 0; 117896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_GE(blob_fd_, 0); 1188cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_)); 119896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 120896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 121896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Blob file name, file descriptor and file size used to store operation 122896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blobs. 123896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo string blob_path_; 124896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo int blob_fd_{-1}; 125896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo off_t blob_file_size_{0}; 1268cc502dacbccdab96824d42287f230ce04004784Sen Jiang std::unique_ptr<BlobFileWriter> blob_file_; 127896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_; 128896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo std::unique_ptr<ScopedFdCloser> blob_fd_closer_; 129cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood}; 130cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 1316b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, BlockDefaultValues) { 1326b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // Tests that a Block is initialized with the default values as a 1336b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo // Vertex::kInvalidIndex. This is required by the delta generators. 1346b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo Block block; 1356b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo EXPECT_EQ(Vertex::kInvalidIndex, block.reader); 1366b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo EXPECT_EQ(Vertex::kInvalidIndex, block.writer); 1376b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo} 1386b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex Deymo 139cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, SubstituteBlocksTest) { 140cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> remove_blocks; 141cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&remove_blocks, 3, 3); 142cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&remove_blocks, 7, 1); 143cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> replace_blocks; 144cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&replace_blocks, 10, 2); 145cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood AppendExtent(&replace_blocks, 13, 2); 146cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex vertex; 147a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation& op = vertex.aop.op; 148cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 4, 3); 149cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file 150cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 3, 1); 151cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood OpAppendExtent(&op, 7, 3); 152cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 153cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks); 154cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 155cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(7, op.src_extents_size()); 15680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(11U, op.src_extents(0).start_block()); 15780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(0).num_blocks()); 15880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(13U, op.src_extents(1).start_block()); 15980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(1).num_blocks()); 16080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(6U, op.src_extents(2).start_block()); 16180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(2).num_blocks()); 162cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(kSparseHole, op.src_extents(3).start_block()); 16380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, op.src_extents(3).num_blocks()); 16480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(10U, op.src_extents(4).start_block()); 16580f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(4).num_blocks()); 16680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(14U, op.src_extents(5).start_block()); 16780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, op.src_extents(5).num_blocks()); 16880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(8U, op.src_extents(6).start_block()); 16980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, op.src_extents(6).num_blocks()); 170cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 171cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 172cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, CutEdgesTest) { 173cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph; 174cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Block> blocks(9); 175cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 176cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Create nodes in graph 177cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood { 178cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph.resize(graph.size() + 1); 179a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph.back().aop.op.set_type(InstallOperation::MOVE); 180cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Reads from blocks 3, 5, 7 181cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> extents; 1825c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 3); 1835c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 5); 1845c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 7); 1853b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); 186cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[3].reader = graph.size() - 1; 187cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[5].reader = graph.size() - 1; 188cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[7].reader = graph.size() - 1; 189cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 190cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Writes to blocks 1, 2, 4 191cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extents.clear(); 1925c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 1); 1935c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 2); 1945c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 4); 1953b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); 196cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[1].writer = graph.size() - 1; 197cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[2].writer = graph.size() - 1; 198cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[4].writer = graph.size() - 1; 199cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 200cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood { 201cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph.resize(graph.size() + 1); 202a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph.back().aop.op.set_type(InstallOperation::MOVE); 203cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Reads from blocks 1, 2, 4 204cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Extent> extents; 2055c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 1); 2065c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 2); 2075c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 4); 2083b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_src_extents()); 209cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[1].reader = graph.size() - 1; 210cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[2].reader = graph.size() - 1; 211cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[4].reader = graph.size() - 1; 212cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 213cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Writes to blocks 3, 5, 6 214cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood extents.clear(); 2155c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 3); 2165c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 5); 2175c6c65570013bbdbd67f9bf6391dd295ef5b5ee6Alex Deymo AppendBlockToExtents(&extents, 6); 2183b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo StoreExtents(extents, graph.back().aop.op.mutable_dst_extents()); 219cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[3].writer = graph.size() - 1; 220cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[5].writer = graph.size() - 1; 221cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood blocks[6].writer = graph.size() - 1; 222cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 223cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 224cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Create edges 225cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::CreateEdges(&graph, blocks); 226cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 227cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Find cycles 228cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood CycleBreaker cycle_breaker; 229cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood set<Edge> cut_edges; 230cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cycle_breaker.BreakCycles(graph, &cut_edges); 231cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 23280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, cut_edges.size()); 233cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(cut_edges.end() != cut_edges.find( 234cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood std::pair<Vertex::Index, Vertex::Index>(1, 0))); 235cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 236cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 237cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts)); 238cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 23980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(3U, graph.size()); 240cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 241cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check new node in graph: 242a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type()); 2433b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph.back().aop.op.src_extents_size()); 2443b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, graph.back().aop.op.dst_extents_size()); 2453b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block()); 24680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph.back().aop.op.dst_extents(0).num_blocks()); 247cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph.back().out_edges.empty()); 248cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 249cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check that old node reads from new blocks 2503b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[0].aop.op.src_extents_size()); 2513b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block()); 25280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks()); 25380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block()); 25480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks()); 255cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 256cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // And that the old dst extents haven't changed 2573b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[0].aop.op.dst_extents_size()); 25880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block()); 25980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks()); 26080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block()); 26180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks()); 262cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 263cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Ensure it only depends on the next node and the new temp node 26480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[0].out_edges.size()); 265cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1)); 266cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() - 267cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 1)); 268cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 269cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Check second node has unchanged extents 2703b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[1].aop.op.src_extents_size()); 27180f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block()); 27280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks()); 27380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block()); 27480f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks()); 2753b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 2763b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(2, graph[1].aop.op.dst_extents_size()); 27780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block()); 27880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks()); 27980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block()); 28080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks()); 281cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 282cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Ensure it only depends on the next node 28380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].out_edges.size()); 284cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2)); 285cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 286cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 2876b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) { 288cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(9); 289cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 290cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent> empt; 291cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood uint64_t tmp = kTempBlockStart; 292cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string kFilename = "/foo"; 293cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 294cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<CutEdgeVertexes> cuts; 295cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts.resize(3); 296cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 297cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Simple broken loop: 298a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 299a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", InstallOperation::MOVE); 300a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[1], 301a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 1), 302a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 1), 303a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 304a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 305a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[2], 306a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(1, 1), 307a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 1), 308a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 309a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 310cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Corresponding edges: 311cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1)); 312cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1)); 313cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1)); 314cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Store the cut: 315cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].old_dst = 1; 316cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].old_src = 0; 317cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].new_vertex = 2; 318cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[0].tmp_extents = VectOfExt(tmp, 1); 319cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood tmp++; 320cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 321cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Slightly more complex pair of loops: 322a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 323a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", InstallOperation::MOVE); 324a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex( 325a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE); 326a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[5], 327a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 3), 328a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(4, 3), 329a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo kFilename, 330a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 331a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[6], 332a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(2, 2), 333a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp, 2), 334a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 335a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 336a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[7], 337a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(7, 1), 338a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(tmp + 2, 1), 339a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 340a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 341cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Corresponding edges: 342cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2)); 343cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1)); 344cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2)); 345cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1)); 346cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2)); 347cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1)); 348cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Store the cuts: 349cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].old_dst = 5; 350cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].old_src = 3; 351cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].new_vertex = 6; 352cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[1].tmp_extents = VectOfExt(tmp, 2); 353cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].old_dst = 5; 354cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].old_src = 4; 355cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].new_vertex = 7; 356cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts[2].tmp_extents = VectOfExt(tmp + 2, 1); 357cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 358cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Supplier of temp block: 359a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[8], empt, VectOfExt(8, 1), "", InstallOperation::REPLACE); 360cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 361cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Specify the final order: 362cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> op_indexes; 363cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(2); 364cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(0); 365cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(1); 366cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(6); 367cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(3); 368cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(7); 369cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(4); 370cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(5); 371cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood op_indexes.push_back(8); 372cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 373cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<vector<Vertex::Index>::size_type> reverse_op_indexes; 374cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes, 375cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &reverse_op_indexes); 376cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 377896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 378cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph, 379568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood "/dev/zero", 3808cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.get(), 381cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &op_indexes, 382cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &reverse_op_indexes, 383cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood cuts)); 384cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph[6].valid); 385cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph[7].valid); 3863b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, graph[1].aop.op.src_extents_size()); 38780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block()); 38880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks()); 389a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type()); 390cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 391cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 3923b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex DeymoTEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) { 393cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(4); 3943b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[0].aop.name = "A"; 395a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[0].aop.op.set_type(InstallOperation::REPLACE); 3963b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[1].aop.name = "B"; 397a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[1].aop.op.set_type(InstallOperation::BSDIFF); 3983b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[2].aop.name = "C"; 399a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ); 4003b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo graph[3].aop.name = "D"; 401a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo graph[3].aop.op.set_type(InstallOperation::MOVE); 402cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 403cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> vect(graph.size()); 404cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 405cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) { 406cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vect[i] = i; 407cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 4083b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect); 409cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_EQ(vect.size(), graph.size()); 4103b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[0]].aop.name, "B"); 4113b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[1]].aop.name, "D"); 4123b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[2]].aop.name, "A"); 4133b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(graph[vect[3]].aop.name, "C"); 414cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 415cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 4166b9e38ef1180efe55e4a82bb18536d1b53fe493dAlex DeymoTEST_F(InplaceGeneratorTest, AssignTempBlocksTest) { 417cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph graph(9); 418cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const vector<Extent> empt; // empty 419cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood const string kFilename = "/foo"; 420cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 421cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // Some scratch space: 422a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE); 423a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE); 424a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE); 425cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 426cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 10 blocks to break: 427a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[3], 428a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(10, 11), 429a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 9), 430a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 431a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 432cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9)); 433a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[4], 434a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 9), 435a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(10, 11), 436a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 437a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 438cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); 439cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 440cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 9 blocks to break: 441a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[5], 442a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(40, 11), 443a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(30, 10), 444a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 445a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 446cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10)); 447a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&graph[6], 448a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(30, 10), 449a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(40, 11), 450a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 451a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 452cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); 453cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 454cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // A cycle that requires 40 blocks to break (which is too many): 455cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&graph[7], 456cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 457cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 458cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 459a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 460cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40)); 461cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&graph[8], 462cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 463cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 464cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood kFilename, 465a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 466cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); 467cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 468cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood graph_utils::DumpGraph(graph); 469cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 470cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood vector<Vertex::Index> final_order; 471cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 472896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 473cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph, 474568734533c25a5783ea004aeb0da38244dcd3e5bAllie Wood "/dev/zero", 4758cc502dacbccdab96824d42287f230ce04004784Sen Jiang blob_file_.get(), 476cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood &final_order, 477cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex::kInvalidIndex)); 478cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 479cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Graph expected_graph(12); 480a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[0], 481a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 482a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(200, 1), 483a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 484a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 485a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[1], 486a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 487a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(210, 10), 488a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 489a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 490a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[2], 491a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 492a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(220, 1), 493a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "", 494a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE); 495cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[3], 496cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(10, 11), 497cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(0, 9), 498cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 499a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 500cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9)); 501cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[4], 502cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 9), 503cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(10, 11), 504cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 505a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 506cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11)); 507cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9)); 508cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[5], 509cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(40, 11), 510cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(30, 10), 511cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 512a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 513cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10)); 514cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 515cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[6], 516cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 10), 517cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(40, 11), 518cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 519a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 520cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11)); 521cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10)); 522cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 523cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[7], 524cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(120, 50), 525cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 40), 526cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 527a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::BSDIFF); 528cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10)); 529cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 530a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo GenVertex(&expected_graph[8], 531a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo empt, 532a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo VectOfExt(0, 50), 533a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo "/foo", 534a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::REPLACE_BZ); 535cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50)); 536cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 537cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[9], 538cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(0, 9), 539cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 9), 540cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 541a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 542cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 543cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood GenVertex(&expected_graph[10], 544cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(30, 10), 545cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood VectOfExt(60, 10), 546cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood "", 547a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo InstallOperation::MOVE); 548cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9)); 549cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 55080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(12U, graph.size()); 551cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_FALSE(graph.back().valid); 552cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood for (Graph::size_type i = 0; i < graph.size() - 1; i++) { 553cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges); 554cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood if (i == 8) { 555cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // special case 556cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } else { 557cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i; 558cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 559cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood } 560cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 561cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 562cd514b531a38da1497630fa68b6e3ef45871893dAllie WoodTEST_F(InplaceGeneratorTest, CreateScratchNodeTest) { 563cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood Vertex vertex; 564cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood InplaceGenerator::CreateScratchNode(12, 34, &vertex); 565a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type()); 56680f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(0U, vertex.aop.op.data_offset()); 56780f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(0U, vertex.aop.op.data_length()); 5683b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo EXPECT_EQ(1, vertex.aop.op.dst_extents_size()); 56980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block()); 57080f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks()); 571cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} 572cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood 57314158570d3995008dc93a628004118b87a6bca01Alex DeymoTEST_F(InplaceGeneratorTest, ApplyMapTest) { 57414158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> collection = {1, 2, 3, 4, 6}; 57514158570d3995008dc93a628004118b87a6bca01Alex Deymo vector<uint64_t> expected_values = {1, 2, 5, 4, 8}; 57614158570d3995008dc93a628004118b87a6bca01Alex Deymo map<uint64_t, uint64_t> value_map; 57714158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[3] = 5; 57814158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[6] = 8; 57914158570d3995008dc93a628004118b87a6bca01Alex Deymo value_map[5] = 10; 58014158570d3995008dc93a628004118b87a6bca01Alex Deymo 58114158570d3995008dc93a628004118b87a6bca01Alex Deymo InplaceGenerator::ApplyMap(&collection, value_map); 58214158570d3995008dc93a628004118b87a6bca01Alex Deymo EXPECT_EQ(expected_values, collection); 58314158570d3995008dc93a628004118b87a6bca01Alex Deymo} 58414158570d3995008dc93a628004118b87a6bca01Alex Deymo 585896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// We can't produce MOVE operations with a source or destination in the block 0. 586896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// This test checks that the cycle breaker procedure doesn't produce such 587896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo// operations. 588896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex DeymoTEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) { 589896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t block_size = 4096; 590896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t num_blocks = 4; 591896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo vector<AnnotatedOperation> aops; 592896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 593896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // Create a REPLACE_BZ for block 0, and a circular dependency among all other 594896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // blocks. This situation would prefer to issue a MOVE to scratch space and 595896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // the only available block is 0. 596896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.emplace_back(); 597896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.back().name = base::StringPrintf("<bz-block-0>"); 598a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo aops.back().op.set_type(InstallOperation::REPLACE_BZ); 599896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents()); 600896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 601896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (size_t i = 1; i < num_blocks; i++) { 602896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo AnnotatedOperation aop; 603896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aop.name = base::StringPrintf("<op-%" PRIuS ">", i); 604a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo aop.op.set_type(InstallOperation::BSDIFF); 605896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)}, 606896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aop.op.mutable_src_extents()); 607896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents()); 608896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo aops.push_back(aop); 609896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 610896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 611625406cee9a90ac2ed895f480286b7f0e8497f38Sen Jiang PartitionConfig part("part"); 612896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo part.path = "/dev/zero"; 613896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo part.size = num_blocks * block_size; 614896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 615896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo CreateBlobFile(); 616896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 617896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // We ran two tests here. The first one without enough blocks for the scratch 618896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // space, forcing it to create a new full operation and the second case with 619896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // one extra block in the partition that can be used for the move operation. 620896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) { 621896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo SCOPED_TRACE(base::StringPrintf("Using partition_blocs=%" PRIu64, 622896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo part_blocks)); 623896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo vector<AnnotatedOperation> result_aops = aops; 624896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies( 6258cc502dacbccdab96824d42287f230ce04004784Sen Jiang part, part_blocks * block_size, block_size, blob_file_.get(), 626896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo &result_aops)); 627896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 628896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo size_t full_ops = 0; 629896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const auto& aop : result_aops) { 630a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if (aop.op.type() == InstallOperation::REPLACE || 631a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo aop.op.type() == InstallOperation::REPLACE_BZ) { 632896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo full_ops++; 633a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo } 634896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 635a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymo if (aop.op.type() != InstallOperation::MOVE) 636896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo continue; 637896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const Extent& extent : aop.op.src_extents()) { 63880f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_NE(0U, extent.start_block()) 63980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo << "On src extents for aop: " << aop; 640896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 641896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const Extent& extent : aop.op.dst_extents()) { 64280f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_NE(0U, extent.start_block()) 64380f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo << "On dst extents for aop: " << aop; 644896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 645896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 646896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 647896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // If there's extra space in the partition, it should not use a new full 648896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo // operation for it. 64980f70ff45f8ea9a679c0c3ed0dc143dd2fe2b63eAlex Deymo EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops); 650896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 651896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo if (HasNonfatalFailure()) { 652896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo LOG(INFO) << "Result operation list:"; 653896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo for (const auto& aop : result_aops) { 654896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo LOG(INFO) << aop; 655896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 656896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 657896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo } 658896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo} 659896fdbaa1cc9a422ac36ef455d02c3cef1f27816Alex Deymo 660cd514b531a38da1497630fa68b6e3ef45871893dAllie Wood} // namespace chromeos_update_engine 661