OLD | NEW |
1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. | 1 // Copyright (c) 2009 The Chromium Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include <sys/types.h> | 5 #include <sys/types.h> |
6 #include <sys/stat.h> | 6 #include <sys/stat.h> |
7 #include <fcntl.h> | 7 #include <fcntl.h> |
8 #include <unistd.h> | 8 #include <unistd.h> |
9 #include <set> | 9 #include <set> |
10 #include <string> | 10 #include <string> |
| 11 #include <utility> |
11 #include <vector> | 12 #include <vector> |
12 #include "base/string_util.h" | |
13 #include <gtest/gtest.h> | 13 #include <gtest/gtest.h> |
14 #include "chromeos/obsolete_logging.h" | 14 #include "chromeos/obsolete_logging.h" |
15 #include "update_engine/decompressing_file_writer.h" | 15 #include "update_engine/cycle_breaker.h" |
16 #include "update_engine/delta_diff_generator.h" | 16 #include "update_engine/delta_diff_generator.h" |
17 #include "update_engine/delta_diff_parser.h" | 17 #include "update_engine/graph_types.h" |
18 #include "update_engine/gzip.h" | 18 #include "update_engine/graph_utils.h" |
19 #include "update_engine/mock_file_writer.h" | |
20 #include "update_engine/subprocess.h" | 19 #include "update_engine/subprocess.h" |
21 #include "update_engine/test_utils.h" | 20 #include "update_engine/test_utils.h" |
22 #include "update_engine/utils.h" | 21 #include "update_engine/utils.h" |
23 | 22 |
| 23 using std::make_pair; |
| 24 using std::set; |
| 25 using std::string; |
| 26 using std::vector; |
| 27 |
24 namespace chromeos_update_engine { | 28 namespace chromeos_update_engine { |
25 | 29 |
26 class DeltaDiffGeneratorTest : public ::testing::Test {}; | 30 typedef DeltaDiffGenerator::Block Block; |
| 31 |
| 32 namespace { |
| 33 int64 BlocksInExtents( |
| 34 const google::protobuf::RepeatedPtrField<Extent>& extents) { |
| 35 int64 ret = 0; |
| 36 for (int i = 0; i < extents.size(); i++) { |
| 37 ret += extents.Get(i).num_blocks(); |
| 38 } |
| 39 return ret; |
| 40 } |
| 41 } // namespace {} |
| 42 |
| 43 class DeltaDiffGeneratorTest : public ::testing::Test { |
| 44 protected: |
| 45 const string old_path() { return "DeltaDiffGeneratorTest-old_path"; } |
| 46 const string new_path() { return "DeltaDiffGeneratorTest-new_path"; } |
| 47 virtual void TearDown() { |
| 48 unlink(old_path().c_str()); |
| 49 unlink(new_path().c_str()); |
| 50 } |
| 51 }; |
| 52 |
| 53 TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveSmallTest) { |
| 54 EXPECT_TRUE(utils::WriteFile(old_path().c_str(), |
| 55 reinterpret_cast<const char*>(kRandomString), |
| 56 sizeof(kRandomString))); |
| 57 EXPECT_TRUE(utils::WriteFile(new_path().c_str(), |
| 58 reinterpret_cast<const char*>(kRandomString), |
| 59 sizeof(kRandomString))); |
| 60 vector<char> data; |
| 61 DeltaArchiveManifest_InstallOperation op; |
| 62 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(), |
| 63 new_path(), |
| 64 &data, |
| 65 &op)); |
| 66 EXPECT_TRUE(data.empty()); |
| 67 |
| 68 EXPECT_TRUE(op.has_type()); |
| 69 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type()); |
| 70 EXPECT_FALSE(op.has_data_offset()); |
| 71 EXPECT_FALSE(op.has_data_length()); |
| 72 EXPECT_EQ(1, op.src_extents_size()); |
| 73 EXPECT_EQ(sizeof(kRandomString), op.src_length()); |
| 74 EXPECT_EQ(1, op.dst_extents_size()); |
| 75 EXPECT_EQ(sizeof(kRandomString), op.dst_length()); |
| 76 EXPECT_EQ(BlocksInExtents(op.src_extents()), |
| 77 BlocksInExtents(op.dst_extents())); |
| 78 EXPECT_EQ(1, BlocksInExtents(op.dst_extents())); |
| 79 } |
| 80 |
| 81 TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffSmallTest) { |
| 82 EXPECT_TRUE(utils::WriteFile(old_path().c_str(), |
| 83 reinterpret_cast<const char*>(kRandomString), |
| 84 sizeof(kRandomString) - 1)); |
| 85 EXPECT_TRUE(utils::WriteFile(new_path().c_str(), |
| 86 reinterpret_cast<const char*>(kRandomString), |
| 87 sizeof(kRandomString))); |
| 88 vector<char> data; |
| 89 DeltaArchiveManifest_InstallOperation op; |
| 90 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(), |
| 91 new_path(), |
| 92 &data, |
| 93 &op)); |
| 94 EXPECT_FALSE(data.empty()); |
| 95 |
| 96 EXPECT_TRUE(op.has_type()); |
| 97 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type()); |
| 98 EXPECT_FALSE(op.has_data_offset()); |
| 99 EXPECT_FALSE(op.has_data_length()); |
| 100 EXPECT_EQ(1, op.src_extents_size()); |
| 101 EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length()); |
| 102 EXPECT_EQ(1, op.dst_extents_size()); |
| 103 EXPECT_EQ(sizeof(kRandomString), op.dst_length()); |
| 104 EXPECT_EQ(BlocksInExtents(op.src_extents()), |
| 105 BlocksInExtents(op.dst_extents())); |
| 106 EXPECT_EQ(1, BlocksInExtents(op.dst_extents())); |
| 107 } |
| 108 |
| 109 TEST_F(DeltaDiffGeneratorTest, RunAsRootReplaceSmallTest) { |
| 110 vector<char> new_data; |
| 111 for (int i = 0; i < 2; i++) { |
| 112 new_data.insert(new_data.end(), |
| 113 kRandomString, |
| 114 kRandomString + sizeof(kRandomString)); |
| 115 EXPECT_TRUE(utils::WriteFile(new_path().c_str(), |
| 116 &new_data[0], |
| 117 new_data.size())); |
| 118 vector<char> data; |
| 119 DeltaArchiveManifest_InstallOperation op; |
| 120 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(), |
| 121 new_path(), |
| 122 &data, |
| 123 &op)); |
| 124 EXPECT_FALSE(data.empty()); |
| 125 |
| 126 EXPECT_TRUE(op.has_type()); |
| 127 const DeltaArchiveManifest_InstallOperation_Type expected_type = |
| 128 (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE : |
| 129 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); |
| 130 EXPECT_EQ(expected_type, op.type()); |
| 131 EXPECT_FALSE(op.has_data_offset()); |
| 132 EXPECT_FALSE(op.has_data_length()); |
| 133 EXPECT_EQ(0, op.src_extents_size()); |
| 134 EXPECT_FALSE(op.has_src_length()); |
| 135 EXPECT_EQ(1, op.dst_extents_size()); |
| 136 EXPECT_EQ(new_data.size(), op.dst_length()); |
| 137 EXPECT_EQ(1, BlocksInExtents(op.dst_extents())); |
| 138 } |
| 139 } |
| 140 |
| 141 namespace { |
| 142 void AppendExtent(vector<Extent>* vect, uint64 start, uint64 length) { |
| 143 vect->resize(vect->size() + 1); |
| 144 vect->back().set_start_block(start); |
| 145 vect->back().set_num_blocks(length); |
| 146 } |
| 147 void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op, |
| 148 uint64 start, |
| 149 uint64 length) { |
| 150 Extent* extent = op->add_src_extents(); |
| 151 extent->set_start_block(start); |
| 152 extent->set_num_blocks(length); |
| 153 } |
| 154 } |
| 155 |
| 156 TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) { |
| 157 vector<Extent> remove_blocks; |
| 158 AppendExtent(&remove_blocks, 3, 3); |
| 159 AppendExtent(&remove_blocks, 7, 1); |
| 160 vector<Extent> replace_blocks; |
| 161 AppendExtent(&replace_blocks, 10, 2); |
| 162 AppendExtent(&replace_blocks, 13, 2); |
| 163 DeltaArchiveManifest_InstallOperation op; |
| 164 OpAppendExtent(&op, 4, 3); |
| 165 OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file |
| 166 OpAppendExtent(&op, 3, 1); |
| 167 OpAppendExtent(&op, 7, 3); |
| 168 |
| 169 DeltaDiffGenerator::SubstituteBlocks(&op, remove_blocks, replace_blocks); |
| 170 |
| 171 EXPECT_EQ(7, op.src_extents_size()); |
| 172 EXPECT_EQ(11, op.src_extents(0).start_block()); |
| 173 EXPECT_EQ(1, op.src_extents(0).num_blocks()); |
| 174 EXPECT_EQ(13, op.src_extents(1).start_block()); |
| 175 EXPECT_EQ(1, op.src_extents(1).num_blocks()); |
| 176 EXPECT_EQ(6, op.src_extents(2).start_block()); |
| 177 EXPECT_EQ(1, op.src_extents(2).num_blocks()); |
| 178 EXPECT_EQ(kSparseHole, op.src_extents(3).start_block()); |
| 179 EXPECT_EQ(4, op.src_extents(3).num_blocks()); |
| 180 EXPECT_EQ(10, op.src_extents(4).start_block()); |
| 181 EXPECT_EQ(1, op.src_extents(4).num_blocks()); |
| 182 EXPECT_EQ(14, op.src_extents(5).start_block()); |
| 183 EXPECT_EQ(1, op.src_extents(5).num_blocks()); |
| 184 EXPECT_EQ(8, op.src_extents(6).start_block()); |
| 185 EXPECT_EQ(2, op.src_extents(6).num_blocks()); |
| 186 } |
| 187 |
| 188 TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) { |
| 189 Graph graph; |
| 190 vector<Block> blocks(9); |
| 191 |
| 192 // Create nodes in graph |
| 193 { |
| 194 graph.resize(graph.size() + 1); |
| 195 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); |
| 196 // Reads from blocks 3, 5, 7 |
| 197 vector<Extent> extents; |
| 198 graph_utils::AppendBlockToExtents(&extents, 3); |
| 199 graph_utils::AppendBlockToExtents(&extents, 5); |
| 200 graph_utils::AppendBlockToExtents(&extents, 7); |
| 201 DeltaDiffGenerator::StoreExtents(extents, |
| 202 graph.back().op.mutable_src_extents()); |
| 203 blocks[3].reader = graph.size() - 1; |
| 204 blocks[5].reader = graph.size() - 1; |
| 205 blocks[7].reader = graph.size() - 1; |
| 206 |
| 207 // Writes to blocks 1, 2, 4 |
| 208 extents.clear(); |
| 209 graph_utils::AppendBlockToExtents(&extents, 1); |
| 210 graph_utils::AppendBlockToExtents(&extents, 2); |
| 211 graph_utils::AppendBlockToExtents(&extents, 4); |
| 212 DeltaDiffGenerator::StoreExtents(extents, |
| 213 graph.back().op.mutable_dst_extents()); |
| 214 blocks[1].writer = graph.size() - 1; |
| 215 blocks[2].writer = graph.size() - 1; |
| 216 blocks[4].writer = graph.size() - 1; |
| 217 } |
| 218 { |
| 219 graph.resize(graph.size() + 1); |
| 220 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); |
| 221 // Reads from blocks 1, 2, 4 |
| 222 vector<Extent> extents; |
| 223 graph_utils::AppendBlockToExtents(&extents, 1); |
| 224 graph_utils::AppendBlockToExtents(&extents, 2); |
| 225 graph_utils::AppendBlockToExtents(&extents, 4); |
| 226 DeltaDiffGenerator::StoreExtents(extents, |
| 227 graph.back().op.mutable_src_extents()); |
| 228 blocks[1].reader = graph.size() - 1; |
| 229 blocks[2].reader = graph.size() - 1; |
| 230 blocks[4].reader = graph.size() - 1; |
| 231 |
| 232 // Writes to blocks 3, 5, 6 |
| 233 extents.clear(); |
| 234 graph_utils::AppendBlockToExtents(&extents, 3); |
| 235 graph_utils::AppendBlockToExtents(&extents, 5); |
| 236 graph_utils::AppendBlockToExtents(&extents, 6); |
| 237 DeltaDiffGenerator::StoreExtents(extents, |
| 238 graph.back().op.mutable_dst_extents()); |
| 239 blocks[3].writer = graph.size() - 1; |
| 240 blocks[5].writer = graph.size() - 1; |
| 241 blocks[6].writer = graph.size() - 1; |
| 242 } |
| 243 |
| 244 // Create edges |
| 245 DeltaDiffGenerator::CreateEdges(&graph, blocks); |
| 246 |
| 247 // Find cycles |
| 248 CycleBreaker cycle_breaker; |
| 249 set<Edge> cut_edges; |
| 250 cycle_breaker.BreakCycles(graph, &cut_edges); |
| 251 |
| 252 EXPECT_EQ(1, cut_edges.size()); |
| 253 EXPECT_TRUE(cut_edges.end() != cut_edges.find(make_pair<Vertex::Index>(1, |
| 254 0))); |
| 255 |
| 256 EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, blocks, cut_edges)); |
| 257 |
| 258 EXPECT_EQ(3, graph.size()); |
| 259 |
| 260 // Check new node in graph: |
| 261 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, |
| 262 graph.back().op.type()); |
| 263 EXPECT_EQ(2, graph.back().op.src_extents_size()); |
| 264 EXPECT_EQ(2, graph.back().op.dst_extents_size()); |
| 265 EXPECT_EQ(0, graph.back().op.dst_extents(0).start_block()); |
| 266 EXPECT_EQ(1, graph.back().op.dst_extents(0).num_blocks()); |
| 267 EXPECT_EQ(8, graph.back().op.dst_extents(1).start_block()); |
| 268 EXPECT_EQ(1, graph.back().op.dst_extents(1).num_blocks()); |
| 269 EXPECT_TRUE(graph.back().out_edges.empty()); |
| 270 |
| 271 // Check that old node reads from new blocks |
| 272 EXPECT_EQ(3, graph[0].op.src_extents_size()); |
| 273 EXPECT_EQ(0, graph[0].op.src_extents(0).start_block()); |
| 274 EXPECT_EQ(1, graph[0].op.src_extents(0).num_blocks()); |
| 275 EXPECT_EQ(8, graph[0].op.src_extents(1).start_block()); |
| 276 EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks()); |
| 277 EXPECT_EQ(7, graph[0].op.src_extents(2).start_block()); |
| 278 EXPECT_EQ(1, graph[0].op.src_extents(2).num_blocks()); |
| 279 |
| 280 // And that the old dst extents haven't changed |
| 281 EXPECT_EQ(2, graph[0].op.dst_extents_size()); |
| 282 EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block()); |
| 283 EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks()); |
| 284 EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block()); |
| 285 EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks()); |
| 286 |
| 287 // Ensure it only depends on the next node |
| 288 EXPECT_EQ(1, graph[0].out_edges.size()); |
| 289 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1)); |
| 290 |
| 291 // Check second node has unchanged extents |
| 292 EXPECT_EQ(2, graph[1].op.src_extents_size()); |
| 293 EXPECT_EQ(1, graph[1].op.src_extents(0).start_block()); |
| 294 EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks()); |
| 295 EXPECT_EQ(4, graph[1].op.src_extents(1).start_block()); |
| 296 EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks()); |
| 297 |
| 298 EXPECT_EQ(2, graph[1].op.dst_extents_size()); |
| 299 EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block()); |
| 300 EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks()); |
| 301 EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block()); |
| 302 EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks()); |
| 303 |
| 304 // Ensure it only depends on the next node |
| 305 EXPECT_EQ(1, graph[1].out_edges.size()); |
| 306 EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2)); |
| 307 } |
| 308 |
| 309 TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) { |
| 310 string orig_blobs; |
| 311 EXPECT_TRUE( |
| 312 utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs, NULL)); |
| 313 |
| 314 string orig_data = "abcd"; |
| 315 EXPECT_TRUE( |
| 316 utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size())); |
| 317 |
| 318 string new_blobs; |
| 319 EXPECT_TRUE( |
| 320 utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, NULL)); |
| 321 |
| 322 DeltaArchiveManifest manifest; |
| 323 DeltaArchiveManifest_InstallOperation* op = |
| 324 manifest.add_install_operations(); |
| 325 op->set_data_offset(1); |
| 326 op->set_data_length(3); |
| 327 op = manifest.add_install_operations(); |
| 328 op->set_data_offset(0); |
| 329 op->set_data_length(1); |
| 330 |
| 331 EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest, |
| 332 orig_blobs, |
| 333 new_blobs)); |
| 334 |
| 335 string new_data; |
| 336 EXPECT_TRUE(utils::ReadFileToString(new_blobs, &new_data)); |
| 337 EXPECT_EQ("bcda", new_data); |
| 338 EXPECT_EQ(2, manifest.install_operations_size()); |
| 339 EXPECT_EQ(0, manifest.install_operations(0).data_offset()); |
| 340 EXPECT_EQ(3, manifest.install_operations(0).data_length()); |
| 341 EXPECT_EQ(3, manifest.install_operations(1).data_offset()); |
| 342 EXPECT_EQ(1, manifest.install_operations(1).data_length()); |
| 343 |
| 344 unlink(orig_blobs.c_str()); |
| 345 unlink(new_blobs.c_str()); |
| 346 } |
27 | 347 |
28 } // namespace chromeos_update_engine | 348 } // namespace chromeos_update_engine |
OLD | NEW |