blob: 349065fc7fd59f1b555c9ec39bce317d93236205 [file] [log] [blame]
Don Garrettf4b28742012-03-27 20:48:06 -07001// Copyright (c) 2012 The Chromium OS Authors. All rights reserved.
adlr@google.com3defe6a2009-12-04 20:57:17 +00002// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include <sys/types.h>
6#include <sys/stat.h>
7#include <fcntl.h>
8#include <unistd.h>
Thieu Le5c7d9752010-12-15 16:09:28 -08009
Andrew de los Reyes4fe15d02009-12-10 19:01:36 -080010#include <set>
Andrew de los Reyesef017552010-10-06 17:57:52 -070011#include <sstream>
adlr@google.com3defe6a2009-12-04 20:57:17 +000012#include <string>
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070013#include <utility>
adlr@google.com3defe6a2009-12-04 20:57:17 +000014#include <vector>
Thieu Le5c7d9752010-12-15 16:09:28 -080015
16#include <base/logging.h>
17#include <base/string_util.h>
adlr@google.com3defe6a2009-12-04 20:57:17 +000018#include <gtest/gtest.h>
Thieu Le5c7d9752010-12-15 16:09:28 -080019
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070020#include "update_engine/cycle_breaker.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000021#include "update_engine/delta_diff_generator.h"
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070022#include "update_engine/delta_performer.h"
Andrew de los Reyesef017552010-10-06 17:57:52 -070023#include "update_engine/extent_ranges.h"
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070024#include "update_engine/graph_types.h"
25#include "update_engine/graph_utils.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000026#include "update_engine/subprocess.h"
27#include "update_engine/test_utils.h"
Andrew de los Reyesef017552010-10-06 17:57:52 -070028#include "update_engine/topological_sort.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000029#include "update_engine/utils.h"
30
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070031using std::make_pair;
32using std::set;
33using std::string;
Andrew de los Reyesef017552010-10-06 17:57:52 -070034using std::stringstream;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070035using std::vector;
36
adlr@google.com3defe6a2009-12-04 20:57:17 +000037namespace chromeos_update_engine {
38
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070039typedef DeltaDiffGenerator::Block Block;
40
41namespace {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070042int64_t BlocksInExtents(
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070043 const google::protobuf::RepeatedPtrField<Extent>& extents) {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070044 int64_t ret = 0;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070045 for (int i = 0; i < extents.size(); i++) {
46 ret += extents.Get(i).num_blocks();
47 }
48 return ret;
49}
50} // namespace {}
51
52class DeltaDiffGeneratorTest : public ::testing::Test {
53 protected:
54 const string old_path() { return "DeltaDiffGeneratorTest-old_path"; }
55 const string new_path() { return "DeltaDiffGeneratorTest-new_path"; }
56 virtual void TearDown() {
57 unlink(old_path().c_str());
58 unlink(new_path().c_str());
59 }
60};
61
62TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveSmallTest) {
63 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
64 reinterpret_cast<const char*>(kRandomString),
65 sizeof(kRandomString)));
66 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
67 reinterpret_cast<const char*>(kRandomString),
68 sizeof(kRandomString)));
69 vector<char> data;
70 DeltaArchiveManifest_InstallOperation op;
71 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
72 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -070073 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070074 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -070075 &op,
76 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070077 EXPECT_TRUE(data.empty());
78
79 EXPECT_TRUE(op.has_type());
80 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
81 EXPECT_FALSE(op.has_data_offset());
82 EXPECT_FALSE(op.has_data_length());
83 EXPECT_EQ(1, op.src_extents_size());
84 EXPECT_EQ(sizeof(kRandomString), op.src_length());
85 EXPECT_EQ(1, op.dst_extents_size());
86 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
87 EXPECT_EQ(BlocksInExtents(op.src_extents()),
88 BlocksInExtents(op.dst_extents()));
89 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
90}
91
92TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffSmallTest) {
93 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
94 reinterpret_cast<const char*>(kRandomString),
95 sizeof(kRandomString) - 1));
96 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
97 reinterpret_cast<const char*>(kRandomString),
98 sizeof(kRandomString)));
99 vector<char> data;
100 DeltaArchiveManifest_InstallOperation op;
101 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
102 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -0700103 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700104 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -0700105 &op,
106 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700107 EXPECT_FALSE(data.empty());
108
109 EXPECT_TRUE(op.has_type());
110 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
111 EXPECT_FALSE(op.has_data_offset());
112 EXPECT_FALSE(op.has_data_length());
113 EXPECT_EQ(1, op.src_extents_size());
114 EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
115 EXPECT_EQ(1, op.dst_extents_size());
116 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
117 EXPECT_EQ(BlocksInExtents(op.src_extents()),
118 BlocksInExtents(op.dst_extents()));
119 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
120}
121
Don Garrett36e60772012-03-29 10:31:20 -0700122TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedTest) {
Don Garrettf4b28742012-03-27 20:48:06 -0700123 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
124 reinterpret_cast<const char*>(kRandomString),
125 sizeof(kRandomString) - 1));
126 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
127 reinterpret_cast<const char*>(kRandomString),
128 sizeof(kRandomString)));
129 vector<char> data;
130 DeltaArchiveManifest_InstallOperation op;
131
Don Garrettf4b28742012-03-27 20:48:06 -0700132 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
133 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -0700134 false, // bsdiff_allowed
Don Garrettf4b28742012-03-27 20:48:06 -0700135 &data,
136 &op,
137 true));
138 EXPECT_FALSE(data.empty());
139
140 // The point of this test is that we don't use BSDIFF the way the above
141 // did. The rest of the details are to be caught in other tests.
142 EXPECT_TRUE(op.has_type());
143 EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
144}
145
Don Garrett36e60772012-03-29 10:31:20 -0700146TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedMoveTest) {
Don Garrettf4b28742012-03-27 20:48:06 -0700147 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
148 reinterpret_cast<const char*>(kRandomString),
149 sizeof(kRandomString)));
150 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
151 reinterpret_cast<const char*>(kRandomString),
152 sizeof(kRandomString)));
153 vector<char> data;
154 DeltaArchiveManifest_InstallOperation op;
155
Don Garrettf4b28742012-03-27 20:48:06 -0700156 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
157 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -0700158 false, // bsdiff_allowed
Don Garrettf4b28742012-03-27 20:48:06 -0700159 &data,
160 &op,
161 true));
162 EXPECT_TRUE(data.empty());
163
164 // The point of this test is that we can still use a MOVE for a file
165 // that is blacklisted.
166 EXPECT_TRUE(op.has_type());
167 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
168}
169
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700170TEST_F(DeltaDiffGeneratorTest, RunAsRootReplaceSmallTest) {
171 vector<char> new_data;
172 for (int i = 0; i < 2; i++) {
173 new_data.insert(new_data.end(),
174 kRandomString,
175 kRandomString + sizeof(kRandomString));
176 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
177 &new_data[0],
178 new_data.size()));
179 vector<char> data;
180 DeltaArchiveManifest_InstallOperation op;
181 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
182 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -0700183 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700184 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -0700185 &op,
186 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700187 EXPECT_FALSE(data.empty());
188
189 EXPECT_TRUE(op.has_type());
190 const DeltaArchiveManifest_InstallOperation_Type expected_type =
191 (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
192 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
193 EXPECT_EQ(expected_type, op.type());
194 EXPECT_FALSE(op.has_data_offset());
195 EXPECT_FALSE(op.has_data_length());
196 EXPECT_EQ(0, op.src_extents_size());
197 EXPECT_FALSE(op.has_src_length());
198 EXPECT_EQ(1, op.dst_extents_size());
199 EXPECT_EQ(new_data.size(), op.dst_length());
200 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
201 }
202}
203
Darin Petkov68c10d12010-10-14 09:24:37 -0700204TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNoGatherExtentsSmallTest) {
205 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
206 reinterpret_cast<const char*>(kRandomString),
207 sizeof(kRandomString) - 1));
208 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
209 reinterpret_cast<const char*>(kRandomString),
210 sizeof(kRandomString)));
211 vector<char> data;
212 DeltaArchiveManifest_InstallOperation op;
213 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
214 new_path(),
Don Garrett36e60772012-03-29 10:31:20 -0700215 true, // bsdiff_allowed
Darin Petkov68c10d12010-10-14 09:24:37 -0700216 &data,
217 &op,
218 false));
219 EXPECT_FALSE(data.empty());
220
221 EXPECT_TRUE(op.has_type());
222 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
223 EXPECT_FALSE(op.has_data_offset());
224 EXPECT_FALSE(op.has_data_length());
225 EXPECT_EQ(1, op.src_extents_size());
226 EXPECT_EQ(0, op.src_extents().Get(0).start_block());
227 EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
228 EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
229 EXPECT_EQ(1, op.dst_extents_size());
230 EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
231 EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
232 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
233}
234
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700235namespace {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -0700236void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700237 vect->resize(vect->size() + 1);
238 vect->back().set_start_block(start);
239 vect->back().set_num_blocks(length);
240}
241void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
Andrew de los Reyes09e56d62010-04-23 13:45:53 -0700242 uint64_t start,
243 uint64_t length) {
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700244 Extent* extent = op->add_src_extents();
245 extent->set_start_block(start);
246 extent->set_num_blocks(length);
247}
248}
249
250TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
251 vector<Extent> remove_blocks;
252 AppendExtent(&remove_blocks, 3, 3);
253 AppendExtent(&remove_blocks, 7, 1);
254 vector<Extent> replace_blocks;
255 AppendExtent(&replace_blocks, 10, 2);
256 AppendExtent(&replace_blocks, 13, 2);
Andrew de los Reyesef017552010-10-06 17:57:52 -0700257 Vertex vertex;
258 DeltaArchiveManifest_InstallOperation& op = vertex.op;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700259 OpAppendExtent(&op, 4, 3);
260 OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
261 OpAppendExtent(&op, 3, 1);
262 OpAppendExtent(&op, 7, 3);
Darin Petkov68c10d12010-10-14 09:24:37 -0700263
Andrew de los Reyesef017552010-10-06 17:57:52 -0700264 DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
Darin Petkov68c10d12010-10-14 09:24:37 -0700265
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700266 EXPECT_EQ(7, op.src_extents_size());
267 EXPECT_EQ(11, op.src_extents(0).start_block());
268 EXPECT_EQ(1, op.src_extents(0).num_blocks());
269 EXPECT_EQ(13, op.src_extents(1).start_block());
270 EXPECT_EQ(1, op.src_extents(1).num_blocks());
271 EXPECT_EQ(6, op.src_extents(2).start_block());
272 EXPECT_EQ(1, op.src_extents(2).num_blocks());
273 EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
274 EXPECT_EQ(4, op.src_extents(3).num_blocks());
275 EXPECT_EQ(10, op.src_extents(4).start_block());
276 EXPECT_EQ(1, op.src_extents(4).num_blocks());
277 EXPECT_EQ(14, op.src_extents(5).start_block());
278 EXPECT_EQ(1, op.src_extents(5).num_blocks());
279 EXPECT_EQ(8, op.src_extents(6).start_block());
280 EXPECT_EQ(2, op.src_extents(6).num_blocks());
281}
282
283TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
284 Graph graph;
285 vector<Block> blocks(9);
Darin Petkov68c10d12010-10-14 09:24:37 -0700286
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700287 // Create nodes in graph
288 {
289 graph.resize(graph.size() + 1);
290 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
291 // Reads from blocks 3, 5, 7
292 vector<Extent> extents;
293 graph_utils::AppendBlockToExtents(&extents, 3);
294 graph_utils::AppendBlockToExtents(&extents, 5);
295 graph_utils::AppendBlockToExtents(&extents, 7);
296 DeltaDiffGenerator::StoreExtents(extents,
297 graph.back().op.mutable_src_extents());
298 blocks[3].reader = graph.size() - 1;
299 blocks[5].reader = graph.size() - 1;
300 blocks[7].reader = graph.size() - 1;
Darin Petkov68c10d12010-10-14 09:24:37 -0700301
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700302 // Writes to blocks 1, 2, 4
303 extents.clear();
304 graph_utils::AppendBlockToExtents(&extents, 1);
305 graph_utils::AppendBlockToExtents(&extents, 2);
306 graph_utils::AppendBlockToExtents(&extents, 4);
307 DeltaDiffGenerator::StoreExtents(extents,
308 graph.back().op.mutable_dst_extents());
309 blocks[1].writer = graph.size() - 1;
310 blocks[2].writer = graph.size() - 1;
311 blocks[4].writer = graph.size() - 1;
312 }
313 {
314 graph.resize(graph.size() + 1);
315 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
316 // Reads from blocks 1, 2, 4
317 vector<Extent> extents;
318 graph_utils::AppendBlockToExtents(&extents, 1);
319 graph_utils::AppendBlockToExtents(&extents, 2);
320 graph_utils::AppendBlockToExtents(&extents, 4);
321 DeltaDiffGenerator::StoreExtents(extents,
322 graph.back().op.mutable_src_extents());
323 blocks[1].reader = graph.size() - 1;
324 blocks[2].reader = graph.size() - 1;
325 blocks[4].reader = graph.size() - 1;
Darin Petkov68c10d12010-10-14 09:24:37 -0700326
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700327 // Writes to blocks 3, 5, 6
328 extents.clear();
329 graph_utils::AppendBlockToExtents(&extents, 3);
330 graph_utils::AppendBlockToExtents(&extents, 5);
331 graph_utils::AppendBlockToExtents(&extents, 6);
332 DeltaDiffGenerator::StoreExtents(extents,
333 graph.back().op.mutable_dst_extents());
334 blocks[3].writer = graph.size() - 1;
335 blocks[5].writer = graph.size() - 1;
336 blocks[6].writer = graph.size() - 1;
337 }
Darin Petkov68c10d12010-10-14 09:24:37 -0700338
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700339 // Create edges
340 DeltaDiffGenerator::CreateEdges(&graph, blocks);
Darin Petkov68c10d12010-10-14 09:24:37 -0700341
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700342 // Find cycles
343 CycleBreaker cycle_breaker;
344 set<Edge> cut_edges;
345 cycle_breaker.BreakCycles(graph, &cut_edges);
346
347 EXPECT_EQ(1, cut_edges.size());
348 EXPECT_TRUE(cut_edges.end() != cut_edges.find(make_pair<Vertex::Index>(1,
349 0)));
350
Andrew de los Reyesef017552010-10-06 17:57:52 -0700351 vector<CutEdgeVertexes> cuts;
352 EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
Darin Petkov68c10d12010-10-14 09:24:37 -0700353
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700354 EXPECT_EQ(3, graph.size());
Darin Petkov68c10d12010-10-14 09:24:37 -0700355
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700356 // Check new node in graph:
357 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
358 graph.back().op.type());
359 EXPECT_EQ(2, graph.back().op.src_extents_size());
Andrew de los Reyesef017552010-10-06 17:57:52 -0700360 EXPECT_EQ(1, graph.back().op.dst_extents_size());
361 EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
362 EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700363 EXPECT_TRUE(graph.back().out_edges.empty());
Darin Petkov68c10d12010-10-14 09:24:37 -0700364
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700365 // Check that old node reads from new blocks
Andrew de los Reyesef017552010-10-06 17:57:52 -0700366 EXPECT_EQ(2, graph[0].op.src_extents_size());
367 EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
368 EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
369 EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700370 EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700371
372 // And that the old dst extents haven't changed
373 EXPECT_EQ(2, graph[0].op.dst_extents_size());
374 EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
375 EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
376 EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
377 EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
Andrew de los Reyesd12784c2010-07-26 13:55:14 -0700378
379 // Ensure it only depends on the next node and the new temp node
380 EXPECT_EQ(2, graph[0].out_edges.size());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700381 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
Andrew de los Reyesd12784c2010-07-26 13:55:14 -0700382 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
383 1));
384
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700385 // Check second node has unchanged extents
386 EXPECT_EQ(2, graph[1].op.src_extents_size());
387 EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
388 EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
389 EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
390 EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
391
392 EXPECT_EQ(2, graph[1].op.dst_extents_size());
393 EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
394 EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
395 EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
396 EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
Darin Petkov68c10d12010-10-14 09:24:37 -0700397
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700398 // Ensure it only depends on the next node
399 EXPECT_EQ(1, graph[1].out_edges.size());
400 EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
401}
402
403TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
404 string orig_blobs;
405 EXPECT_TRUE(
406 utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs, NULL));
407
408 string orig_data = "abcd";
409 EXPECT_TRUE(
410 utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
411
412 string new_blobs;
413 EXPECT_TRUE(
414 utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, NULL));
Darin Petkov68c10d12010-10-14 09:24:37 -0700415
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700416 DeltaArchiveManifest manifest;
417 DeltaArchiveManifest_InstallOperation* op =
418 manifest.add_install_operations();
419 op->set_data_offset(1);
420 op->set_data_length(3);
421 op = manifest.add_install_operations();
422 op->set_data_offset(0);
423 op->set_data_length(1);
Darin Petkov68c10d12010-10-14 09:24:37 -0700424
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700425 EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest,
426 orig_blobs,
427 new_blobs));
Darin Petkov68c10d12010-10-14 09:24:37 -0700428
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700429 string new_data;
Gilad Arnold19a45f02012-07-19 12:36:10 -0700430 EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700431 EXPECT_EQ("bcda", new_data);
432 EXPECT_EQ(2, manifest.install_operations_size());
433 EXPECT_EQ(0, manifest.install_operations(0).data_offset());
434 EXPECT_EQ(3, manifest.install_operations(0).data_length());
435 EXPECT_EQ(3, manifest.install_operations(1).data_offset());
436 EXPECT_EQ(1, manifest.install_operations(1).data_length());
Darin Petkov68c10d12010-10-14 09:24:37 -0700437
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700438 unlink(orig_blobs.c_str());
439 unlink(new_blobs.c_str());
440}
adlr@google.com3defe6a2009-12-04 20:57:17 +0000441
Andrew de los Reyesef017552010-10-06 17:57:52 -0700442TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
443 Graph graph(4);
444 graph[0].file_name = "A";
445 graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
446 graph[1].file_name = "B";
447 graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
448 graph[2].file_name = "C";
449 graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
450 graph[3].file_name = "D";
451 graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
452
453 vector<Vertex::Index> vect(graph.size());
454
455 for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
456 vect[i] = i;
457 }
458 DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
459 EXPECT_EQ(vect.size(), graph.size());
460 EXPECT_EQ(graph[vect[0]].file_name, "B");
461 EXPECT_EQ(graph[vect[1]].file_name, "D");
462 EXPECT_EQ(graph[vect[2]].file_name, "A");
463 EXPECT_EQ(graph[vect[3]].file_name, "C");
464}
465
466namespace {
467
468#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
469#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
470#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
471#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
472
473void GenVertex(Vertex* out,
474 const vector<Extent>& src_extents,
475 const vector<Extent>& dst_extents,
476 const string& path,
477 DeltaArchiveManifest_InstallOperation_Type type) {
478 out->op.set_type(type);
479 out->file_name = path;
480 DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
481 DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
482}
483
484vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
485 return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
486}
487
488EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
489 EdgeProperties ret;
490 ret.extents = extents;
491 return ret;
492}
493
494EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
495 EdgeProperties ret;
496 ret.write_extents = extents;
497 return ret;
498}
499
500template<typename T>
501void DumpVect(const vector<T>& vect) {
502 std::stringstream ss(stringstream::out);
503 for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
504 it != e; ++it) {
505 ss << *it << ", ";
506 }
507 LOG(INFO) << "{" << ss.str() << "}";
508}
509
510} // namespace {}
511
512TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
513 Graph graph(9);
514 const vector<Extent> empt; // empty
515 const string kFilename = "/foo";
Darin Petkov68c10d12010-10-14 09:24:37 -0700516
Andrew de los Reyesef017552010-10-06 17:57:52 -0700517 // Some scratch space:
518 GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
519 GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
520 GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
521
522 // A cycle that requires 10 blocks to break:
523 GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
524 graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
525 GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
526 graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
527
528 // A cycle that requires 9 blocks to break:
529 GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
530 graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
531 GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
532 graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
533
534 // A cycle that requires 40 blocks to break (which is too many):
535 GenVertex(&graph[7],
536 VectOfExt(120, 50),
537 VectOfExt(60, 40),
538 "",
539 OP_BSDIFF);
540 graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
541 GenVertex(&graph[8],
542 VectOfExt(60, 40),
543 VectOfExt(120, 50),
544 kFilename,
545 OP_BSDIFF);
546 graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
Darin Petkov68c10d12010-10-14 09:24:37 -0700547
Andrew de los Reyesef017552010-10-06 17:57:52 -0700548 graph_utils::DumpGraph(graph);
Darin Petkov68c10d12010-10-14 09:24:37 -0700549
Andrew de los Reyesef017552010-10-06 17:57:52 -0700550 vector<Vertex::Index> final_order;
551
552
553 // Prepare the filesystem with the minimum required for this to work
554 string temp_dir;
555 EXPECT_TRUE(utils::MakeTempDirectory("/tmp/AssignTempBlocksTest.XXXXXX",
556 &temp_dir));
557 ScopedDirRemover temp_dir_remover(temp_dir);
Darin Petkov68c10d12010-10-14 09:24:37 -0700558
Andrew de los Reyesef017552010-10-06 17:57:52 -0700559 const size_t kBlockSize = 4096;
560 vector<char> temp_data(kBlockSize * 50);
561 FillWithData(&temp_data);
562 EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
563 ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
Darin Petkov68c10d12010-10-14 09:24:37 -0700564
Andrew de los Reyesef017552010-10-06 17:57:52 -0700565 int fd;
566 EXPECT_TRUE(utils::MakeTempFile("/tmp/AssignTempBlocksTestData.XXXXXX",
567 NULL,
568 &fd));
569 ScopedFdCloser fd_closer(&fd);
570 off_t data_file_size = 0;
571
572
573 EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
574 temp_dir,
575 fd,
576 &data_file_size,
Andrew de los Reyes927179d2010-12-02 11:26:48 -0800577 &final_order,
578 Vertex::kInvalidIndex));
Andrew de los Reyesef017552010-10-06 17:57:52 -0700579
Darin Petkov68c10d12010-10-14 09:24:37 -0700580
Andrew de los Reyesef017552010-10-06 17:57:52 -0700581 Graph expected_graph(12);
582 GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
583 GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
584 GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
585 GenVertex(&expected_graph[3],
586 VectOfExt(10, 11),
587 VectOfExt(0, 9),
588 "",
589 OP_BSDIFF);
590 expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
591 GenVertex(&expected_graph[4],
592 VectOfExt(60, 9),
593 VectOfExt(10, 11),
594 "",
595 OP_BSDIFF);
596 expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
597 expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
598 GenVertex(&expected_graph[5],
599 VectOfExt(40, 11),
600 VectOfExt(30, 10),
601 "",
602 OP_BSDIFF);
603 expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
604
605 GenVertex(&expected_graph[6],
606 VectOfExt(60, 10),
607 VectOfExt(40, 11),
608 "",
609 OP_BSDIFF);
610 expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
611 expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
Darin Petkov68c10d12010-10-14 09:24:37 -0700612
Andrew de los Reyesef017552010-10-06 17:57:52 -0700613 GenVertex(&expected_graph[7],
614 VectOfExt(120, 50),
615 VectOfExt(60, 40),
616 "",
617 OP_BSDIFF);
618 expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
619
620 GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
621 expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
622
623 GenVertex(&expected_graph[9],
624 VectOfExt(0, 9),
625 VectOfExt(60, 9),
626 "",
627 OP_MOVE);
628
629 GenVertex(&expected_graph[10],
630 VectOfExt(30, 10),
631 VectOfExt(60, 10),
632 "",
633 OP_MOVE);
634 expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
Darin Petkov68c10d12010-10-14 09:24:37 -0700635
Andrew de los Reyesef017552010-10-06 17:57:52 -0700636 EXPECT_EQ(12, graph.size());
637 EXPECT_FALSE(graph.back().valid);
638 for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
639 EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
640 if (i == 8) {
641 // special case
642 } else {
643 // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
644 }
645 }
646}
647
Darin Petkov9fa7ec52010-10-18 11:45:23 -0700648TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
649 DeltaArchiveManifest_InstallOperation op;
650 op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
651 EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
652 op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
653 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
654 *(op.add_src_extents()) = ExtentForRange(3, 2);
655 *(op.add_dst_extents()) = ExtentForRange(3, 2);
656 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
657 *(op.add_src_extents()) = ExtentForRange(7, 5);
658 *(op.add_dst_extents()) = ExtentForRange(7, 5);
659 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
660 *(op.add_src_extents()) = ExtentForRange(20, 2);
661 *(op.add_dst_extents()) = ExtentForRange(20, 1);
662 *(op.add_dst_extents()) = ExtentForRange(21, 1);
663 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
664 *(op.add_src_extents()) = ExtentForRange(kSparseHole, 2);
665 *(op.add_src_extents()) = ExtentForRange(kSparseHole, 1);
666 *(op.add_dst_extents()) = ExtentForRange(kSparseHole, 3);
667 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
668 *(op.add_src_extents()) = ExtentForRange(24, 1);
669 *(op.add_dst_extents()) = ExtentForRange(25, 1);
670 EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
671}
672
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -0700673TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
674 // AssignTempBlocks(Graph* graph,
675 // const string& new_root,
676 // int data_fd,
677 // off_t* data_file_size,
678 // vector<Vertex::Index>* op_indexes,
679 // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
680 // const vector<CutEdgeVertexes>& cuts
681 Graph graph(9);
682
683 const vector<Extent> empt;
684 uint64_t tmp = kTempBlockStart;
685 const string kFilename = "/foo";
686
687 vector<CutEdgeVertexes> cuts;
688 cuts.resize(3);
689
690 // Simple broken loop:
691 GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
692 GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
693 GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
694 // Corresponding edges:
695 graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
696 graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
697 graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
698 // Store the cut:
699 cuts[0].old_dst = 1;
700 cuts[0].old_src = 0;
701 cuts[0].new_vertex = 2;
702 cuts[0].tmp_extents = VectOfExt(tmp, 1);
703 tmp++;
704
705 // Slightly more complex pair of loops:
706 GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
707 GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
708 GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
709 GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
710 GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
711 // Corresponding edges:
712 graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
713 graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
714 graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
715 graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
716 graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
717 graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
718 // Store the cuts:
719 cuts[1].old_dst = 5;
720 cuts[1].old_src = 3;
721 cuts[1].new_vertex = 6;
722 cuts[1].tmp_extents = VectOfExt(tmp, 2);
723 cuts[2].old_dst = 5;
724 cuts[2].old_src = 4;
725 cuts[2].new_vertex = 7;
726 cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
727
728 // Supplier of temp block:
729 GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
730
731 // Specify the final order:
732 vector<Vertex::Index> op_indexes;
733 op_indexes.push_back(2);
734 op_indexes.push_back(0);
735 op_indexes.push_back(1);
736 op_indexes.push_back(6);
737 op_indexes.push_back(3);
738 op_indexes.push_back(7);
739 op_indexes.push_back(4);
740 op_indexes.push_back(5);
741 op_indexes.push_back(8);
742
743 vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
744 DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
745 &reverse_op_indexes);
746
747 // Prepare the filesystem with the minimum required for this to work
748 string temp_dir;
749 EXPECT_TRUE(utils::MakeTempDirectory("/tmp/AssignTempBlocksReuseTest.XXXXXX",
750 &temp_dir));
751 ScopedDirRemover temp_dir_remover(temp_dir);
752
753 const size_t kBlockSize = 4096;
754 vector<char> temp_data(kBlockSize * 3);
755 FillWithData(&temp_data);
756 EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
757 ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
758
759 int fd;
760 EXPECT_TRUE(utils::MakeTempFile("/tmp/AssignTempBlocksReuseTest.XXXXXX",
761 NULL,
762 &fd));
763 ScopedFdCloser fd_closer(&fd);
764 off_t data_file_size = 0;
Thieu Le5c7d9752010-12-15 16:09:28 -0800765
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -0700766 EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
767 temp_dir,
768 fd,
769 &data_file_size,
770 &op_indexes,
771 &reverse_op_indexes,
772 cuts));
773 EXPECT_FALSE(graph[6].valid);
774 EXPECT_FALSE(graph[7].valid);
775 EXPECT_EQ(1, graph[1].op.src_extents_size());
776 EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
777 EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
778 EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
779}
780
Andrew de los Reyes927179d2010-12-02 11:26:48 -0800781TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
782 Vertex vertex;
783 DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
784 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
785 vertex.op.type());
786 EXPECT_EQ(0, vertex.op.data_offset());
787 EXPECT_EQ(0, vertex.op.data_length());
788 EXPECT_EQ(1, vertex.op.dst_extents_size());
789 EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
790 EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
791}
792
adlr@google.com3defe6a2009-12-04 20:57:17 +0000793} // namespace chromeos_update_engine