blob: 65ca23f025a7c4c9d72b0fbb832eb571e547df70 [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
Gilad Arnoldfa404502014-01-01 23:36:12 -080010#include <map>
Andrew de los Reyes4fe15d02009-12-10 19:01:36 -080011#include <set>
Andrew de los Reyesef017552010-10-06 17:57:52 -070012#include <sstream>
adlr@google.com3defe6a2009-12-04 20:57:17 +000013#include <string>
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070014#include <utility>
adlr@google.com3defe6a2009-12-04 20:57:17 +000015#include <vector>
Thieu Le5c7d9752010-12-15 16:09:28 -080016
17#include <base/logging.h>
18#include <base/string_util.h>
adlr@google.com3defe6a2009-12-04 20:57:17 +000019#include <gtest/gtest.h>
Thieu Le5c7d9752010-12-15 16:09:28 -080020
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070021#include "update_engine/cycle_breaker.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000022#include "update_engine/delta_diff_generator.h"
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070023#include "update_engine/delta_performer.h"
Gilad Arnoldfa404502014-01-01 23:36:12 -080024#include "update_engine/extent_mapper.h"
Andrew de los Reyesef017552010-10-06 17:57:52 -070025#include "update_engine/extent_ranges.h"
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070026#include "update_engine/graph_types.h"
27#include "update_engine/graph_utils.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000028#include "update_engine/subprocess.h"
29#include "update_engine/test_utils.h"
Andrew de los Reyesef017552010-10-06 17:57:52 -070030#include "update_engine/topological_sort.h"
adlr@google.com3defe6a2009-12-04 20:57:17 +000031#include "update_engine/utils.h"
32
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070033using std::make_pair;
34using std::set;
35using std::string;
Andrew de los Reyesef017552010-10-06 17:57:52 -070036using std::stringstream;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070037using std::vector;
38
adlr@google.com3defe6a2009-12-04 20:57:17 +000039namespace chromeos_update_engine {
40
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070041typedef DeltaDiffGenerator::Block Block;
42
Gilad Arnoldfa404502014-01-01 23:36:12 -080043typedef bool (*GetExtentsWithChunk)(const std::string&, off_t, off_t,
44 std::vector<Extent>*);
45extern GetExtentsWithChunk get_extents_with_chunk_func;
46
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070047namespace {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070048int64_t BlocksInExtents(
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070049 const google::protobuf::RepeatedPtrField<Extent>& extents) {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -070050 int64_t ret = 0;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070051 for (int i = 0; i < extents.size(); i++) {
52 ret += extents.Get(i).num_blocks();
53 }
54 return ret;
55}
56} // namespace {}
57
58class DeltaDiffGeneratorTest : public ::testing::Test {
59 protected:
Gilad Arnold99dcdc82013-07-16 03:00:20 -070060 const string& old_path() { return old_path_; }
61 const string& new_path() { return new_path_; }
62
63 virtual void SetUp() {
64 ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-old_path-XXXXXX",
65 &old_path_, NULL));
66 ASSERT_TRUE(utils::MakeTempFile("DeltaDiffGeneratorTest-new_path-XXXXXX",
67 &new_path_, NULL));
68 }
69
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070070 virtual void TearDown() {
71 unlink(old_path().c_str());
72 unlink(new_path().c_str());
73 }
Gilad Arnold99dcdc82013-07-16 03:00:20 -070074
75 private:
76 string old_path_;
77 string new_path_;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070078};
79
80TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveSmallTest) {
81 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
82 reinterpret_cast<const char*>(kRandomString),
83 sizeof(kRandomString)));
84 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
85 reinterpret_cast<const char*>(kRandomString),
86 sizeof(kRandomString)));
87 vector<char> data;
88 DeltaArchiveManifest_InstallOperation op;
89 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
90 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +020091 0, // chunk_offset
92 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -070093 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070094 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -070095 &op,
96 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -070097 EXPECT_TRUE(data.empty());
98
99 EXPECT_TRUE(op.has_type());
100 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
101 EXPECT_FALSE(op.has_data_offset());
102 EXPECT_FALSE(op.has_data_length());
103 EXPECT_EQ(1, op.src_extents_size());
104 EXPECT_EQ(sizeof(kRandomString), op.src_length());
105 EXPECT_EQ(1, op.dst_extents_size());
106 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
107 EXPECT_EQ(BlocksInExtents(op.src_extents()),
108 BlocksInExtents(op.dst_extents()));
109 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
110}
111
Gilad Arnoldfa404502014-01-01 23:36:12 -0800112std::map<string, vector<Extent>*> fake_file_extents;
113
114bool FakeGetExtents(const string& path, off_t chunk_offset, off_t chunk_size,
115 vector<Extent>* out) {
116 if (fake_file_extents.count(path) == 1) {
117 *out = *fake_file_extents[path];
118 return true;
119 } else {
120 return false;
121 }
122}
123
124uint64_t AddExtent(uint64_t start_block, uint64_t num_blocks,
125 vector<Extent>* extents) {
126 Extent e;
127 e.set_start_block(start_block);
128 e.set_num_blocks(num_blocks);
129 extents->push_back(e);
130 return num_blocks;
131}
132
133TEST_F(DeltaDiffGeneratorTest, RunAsRootMoveWithSameBlock) {
134 // Mock out the extent gathering function.
135 GetExtentsWithChunk orig_get_extents_with_chunk_func =
136 get_extents_with_chunk_func;
137 get_extents_with_chunk_func = FakeGetExtents;
138
139 // Setup the old/new files so that it has immobile chunks; we make sure to
140 // utilize all sub-cases of such chunks: blocks 21--22 induce a split (src)
141 // and complete removal (dst), whereas blocks 24--25 induce trimming of the
Gilad Arnoldebca5712014-01-10 14:26:37 -0800142 // tail (src) and head (dst) of extents. The final block (29) is used for
143 // ensuring we properly account for the number of bytes removed in cases where
144 // the last block is partly filled. The detailed configuration:
Gilad Arnoldfa404502014-01-01 23:36:12 -0800145 //
Gilad Arnoldebca5712014-01-10 14:26:37 -0800146 // Old: [ 20 21 22 23 24 25 ] [ 28 29 ]
147 // New: [ 18 ] [ 21 22 ] [ 20 ] [ 24 25 26 ] [ 29 ]
148 // Same: ^^ ^^ ^^ ^^ ^^
Gilad Arnoldfa404502014-01-01 23:36:12 -0800149 vector<Extent> old_extents;
150 uint64_t num_extents = 0;
151 num_extents += AddExtent(20, 6, &old_extents);
Gilad Arnoldebca5712014-01-10 14:26:37 -0800152 num_extents += AddExtent(28, 2, &old_extents);
Gilad Arnoldfa404502014-01-01 23:36:12 -0800153 fake_file_extents[old_path()] = &old_extents;
154 vector<Extent> new_extents;
155 AddExtent(18, 1, &new_extents);
156 AddExtent(21, 2, &new_extents);
157 AddExtent(20, 1, &new_extents);
158 AddExtent(24, 3, &new_extents);
Gilad Arnoldebca5712014-01-10 14:26:37 -0800159 AddExtent(29, 1, &new_extents);
Gilad Arnoldfa404502014-01-01 23:36:12 -0800160 fake_file_extents[new_path()] = &new_extents;
161
Gilad Arnoldebca5712014-01-10 14:26:37 -0800162 // The size of the data should match the total number of blocks; the last
163 // block is only partly filled.
164 size_t file_len = 7 * 4096 + 3333;
Gilad Arnoldfa404502014-01-01 23:36:12 -0800165 const string random_string(reinterpret_cast<const char*>(kRandomString),
166 sizeof(kRandomString));
167 string random_data;
168 while (random_data.size() < file_len)
169 random_data += random_string;
170 if (random_data.size() > file_len)
171 random_data.erase(file_len);
172 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
173 random_data.c_str(), file_len));
174 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
175 random_data.c_str(), file_len));
176
177 vector<char> data;
178 DeltaArchiveManifest_InstallOperation op;
179 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
180 new_path(),
181 0, // chunk_offset
182 -1, // chunk_size
183 true, // bsdiff_allowed
184 &data,
185 &op,
186 true));
187
188 // Adjust the old/new extents to remove duplicates.
189 old_extents[0].set_num_blocks(1);
190 Extent e;
191 e.set_start_block(23);
192 e.set_num_blocks(1);
193 old_extents.insert(old_extents.begin() + 1, e);
Gilad Arnoldebca5712014-01-10 14:26:37 -0800194 old_extents[2].set_num_blocks(1);
Gilad Arnoldfa404502014-01-01 23:36:12 -0800195 new_extents.erase(new_extents.begin() + 1);
196 new_extents[2].set_start_block(26);
197 new_extents[2].set_num_blocks(1);
Gilad Arnoldebca5712014-01-10 14:26:37 -0800198 new_extents.erase(new_extents.begin() + 3);
199 num_extents -= 5;
200 file_len -= 4 * 4096 + 3333;
Gilad Arnoldfa404502014-01-01 23:36:12 -0800201
202 EXPECT_TRUE(data.empty());
203
204 EXPECT_TRUE(op.has_type());
205 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
206 EXPECT_FALSE(op.has_data_offset());
207 EXPECT_FALSE(op.has_data_length());
208
209 EXPECT_EQ(file_len, op.src_length());
210 EXPECT_EQ(num_extents, BlocksInExtents(op.src_extents()));
211 EXPECT_EQ(old_extents.size(), op.src_extents_size());
212 for (int i = 0; i < op.src_extents_size(); i++) {
213 EXPECT_EQ(old_extents[i].start_block(), op.src_extents(i).start_block())
214 << "i == " << i;
215 EXPECT_EQ(old_extents[i].num_blocks(), op.src_extents(i).num_blocks())
216 << "i == " << i;
217 }
218
219 EXPECT_EQ(file_len, op.dst_length());
220 EXPECT_EQ(num_extents, BlocksInExtents(op.dst_extents()));
221 EXPECT_EQ(new_extents.size(), op.dst_extents_size());
222 for (int i = 0; i < op.dst_extents_size(); i++) {
223 EXPECT_EQ(new_extents[i].start_block(), op.dst_extents(i).start_block())
224 << "i == " << i;
225 EXPECT_EQ(new_extents[i].num_blocks(), op.dst_extents(i).num_blocks())
226 << "i == " << i;
227 }
228
229 // Clean up fake extents and restore the module's extent gathering logic.
230 fake_file_extents.clear();
231 get_extents_with_chunk_func = orig_get_extents_with_chunk_func;
232}
233
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700234TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffSmallTest) {
235 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
236 reinterpret_cast<const char*>(kRandomString),
237 sizeof(kRandomString) - 1));
238 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
239 reinterpret_cast<const char*>(kRandomString),
240 sizeof(kRandomString)));
241 vector<char> data;
242 DeltaArchiveManifest_InstallOperation op;
243 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
244 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +0200245 0, // chunk_offset
246 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -0700247 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700248 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -0700249 &op,
250 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700251 EXPECT_FALSE(data.empty());
252
253 EXPECT_TRUE(op.has_type());
254 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
255 EXPECT_FALSE(op.has_data_offset());
256 EXPECT_FALSE(op.has_data_length());
257 EXPECT_EQ(1, op.src_extents_size());
258 EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
259 EXPECT_EQ(1, op.dst_extents_size());
260 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
261 EXPECT_EQ(BlocksInExtents(op.src_extents()),
262 BlocksInExtents(op.dst_extents()));
263 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
264}
265
Don Garrett36e60772012-03-29 10:31:20 -0700266TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedTest) {
Don Garrettf4b28742012-03-27 20:48:06 -0700267 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
268 reinterpret_cast<const char*>(kRandomString),
269 sizeof(kRandomString) - 1));
270 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
271 reinterpret_cast<const char*>(kRandomString),
272 sizeof(kRandomString)));
273 vector<char> data;
274 DeltaArchiveManifest_InstallOperation op;
275
Don Garrettf4b28742012-03-27 20:48:06 -0700276 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
277 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +0200278 0, // chunk_offset
279 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -0700280 false, // bsdiff_allowed
Don Garrettf4b28742012-03-27 20:48:06 -0700281 &data,
282 &op,
283 true));
284 EXPECT_FALSE(data.empty());
285
286 // The point of this test is that we don't use BSDIFF the way the above
287 // did. The rest of the details are to be caught in other tests.
288 EXPECT_TRUE(op.has_type());
289 EXPECT_NE(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
290}
291
Don Garrett36e60772012-03-29 10:31:20 -0700292TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNotAllowedMoveTest) {
Don Garrettf4b28742012-03-27 20:48:06 -0700293 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
294 reinterpret_cast<const char*>(kRandomString),
295 sizeof(kRandomString)));
296 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
297 reinterpret_cast<const char*>(kRandomString),
298 sizeof(kRandomString)));
299 vector<char> data;
300 DeltaArchiveManifest_InstallOperation op;
301
Don Garrettf4b28742012-03-27 20:48:06 -0700302 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
303 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +0200304 0, // chunk_offset
305 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -0700306 false, // bsdiff_allowed
Don Garrettf4b28742012-03-27 20:48:06 -0700307 &data,
308 &op,
309 true));
310 EXPECT_TRUE(data.empty());
311
312 // The point of this test is that we can still use a MOVE for a file
313 // that is blacklisted.
314 EXPECT_TRUE(op.has_type());
315 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE, op.type());
316}
317
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700318TEST_F(DeltaDiffGeneratorTest, RunAsRootReplaceSmallTest) {
319 vector<char> new_data;
320 for (int i = 0; i < 2; i++) {
321 new_data.insert(new_data.end(),
322 kRandomString,
323 kRandomString + sizeof(kRandomString));
324 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
325 &new_data[0],
326 new_data.size()));
327 vector<char> data;
328 DeltaArchiveManifest_InstallOperation op;
329 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
330 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +0200331 0, // chunk_offset
332 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -0700333 true, // bsdiff_allowed
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700334 &data,
Darin Petkov68c10d12010-10-14 09:24:37 -0700335 &op,
336 true));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700337 EXPECT_FALSE(data.empty());
338
339 EXPECT_TRUE(op.has_type());
340 const DeltaArchiveManifest_InstallOperation_Type expected_type =
341 (i == 0 ? DeltaArchiveManifest_InstallOperation_Type_REPLACE :
342 DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
343 EXPECT_EQ(expected_type, op.type());
344 EXPECT_FALSE(op.has_data_offset());
345 EXPECT_FALSE(op.has_data_length());
346 EXPECT_EQ(0, op.src_extents_size());
347 EXPECT_FALSE(op.has_src_length());
348 EXPECT_EQ(1, op.dst_extents_size());
349 EXPECT_EQ(new_data.size(), op.dst_length());
350 EXPECT_EQ(1, BlocksInExtents(op.dst_extents()));
351 }
352}
353
Darin Petkov68c10d12010-10-14 09:24:37 -0700354TEST_F(DeltaDiffGeneratorTest, RunAsRootBsdiffNoGatherExtentsSmallTest) {
355 EXPECT_TRUE(utils::WriteFile(old_path().c_str(),
356 reinterpret_cast<const char*>(kRandomString),
357 sizeof(kRandomString) - 1));
358 EXPECT_TRUE(utils::WriteFile(new_path().c_str(),
359 reinterpret_cast<const char*>(kRandomString),
360 sizeof(kRandomString)));
361 vector<char> data;
362 DeltaArchiveManifest_InstallOperation op;
363 EXPECT_TRUE(DeltaDiffGenerator::ReadFileToDiff(old_path(),
364 new_path(),
Darin Petkov8e447e02013-04-16 16:23:50 +0200365 0, // chunk_offset
366 -1, // chunk_size
Don Garrett36e60772012-03-29 10:31:20 -0700367 true, // bsdiff_allowed
Darin Petkov68c10d12010-10-14 09:24:37 -0700368 &data,
369 &op,
370 false));
371 EXPECT_FALSE(data.empty());
372
373 EXPECT_TRUE(op.has_type());
374 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_BSDIFF, op.type());
375 EXPECT_FALSE(op.has_data_offset());
376 EXPECT_FALSE(op.has_data_length());
377 EXPECT_EQ(1, op.src_extents_size());
378 EXPECT_EQ(0, op.src_extents().Get(0).start_block());
379 EXPECT_EQ(1, op.src_extents().Get(0).num_blocks());
380 EXPECT_EQ(sizeof(kRandomString) - 1, op.src_length());
381 EXPECT_EQ(1, op.dst_extents_size());
382 EXPECT_EQ(0, op.dst_extents().Get(0).start_block());
383 EXPECT_EQ(1, op.dst_extents().Get(0).num_blocks());
384 EXPECT_EQ(sizeof(kRandomString), op.dst_length());
385}
386
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700387namespace {
Andrew de los Reyes09e56d62010-04-23 13:45:53 -0700388void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700389 vect->resize(vect->size() + 1);
390 vect->back().set_start_block(start);
391 vect->back().set_num_blocks(length);
392}
393void OpAppendExtent(DeltaArchiveManifest_InstallOperation* op,
Andrew de los Reyes09e56d62010-04-23 13:45:53 -0700394 uint64_t start,
395 uint64_t length) {
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700396 Extent* extent = op->add_src_extents();
397 extent->set_start_block(start);
398 extent->set_num_blocks(length);
399}
400}
401
402TEST_F(DeltaDiffGeneratorTest, SubstituteBlocksTest) {
403 vector<Extent> remove_blocks;
404 AppendExtent(&remove_blocks, 3, 3);
405 AppendExtent(&remove_blocks, 7, 1);
406 vector<Extent> replace_blocks;
407 AppendExtent(&replace_blocks, 10, 2);
408 AppendExtent(&replace_blocks, 13, 2);
Andrew de los Reyesef017552010-10-06 17:57:52 -0700409 Vertex vertex;
410 DeltaArchiveManifest_InstallOperation& op = vertex.op;
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700411 OpAppendExtent(&op, 4, 3);
412 OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
413 OpAppendExtent(&op, 3, 1);
414 OpAppendExtent(&op, 7, 3);
Darin Petkov68c10d12010-10-14 09:24:37 -0700415
Andrew de los Reyesef017552010-10-06 17:57:52 -0700416 DeltaDiffGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
Darin Petkov68c10d12010-10-14 09:24:37 -0700417
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700418 EXPECT_EQ(7, op.src_extents_size());
419 EXPECT_EQ(11, op.src_extents(0).start_block());
420 EXPECT_EQ(1, op.src_extents(0).num_blocks());
421 EXPECT_EQ(13, op.src_extents(1).start_block());
422 EXPECT_EQ(1, op.src_extents(1).num_blocks());
423 EXPECT_EQ(6, op.src_extents(2).start_block());
424 EXPECT_EQ(1, op.src_extents(2).num_blocks());
425 EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
426 EXPECT_EQ(4, op.src_extents(3).num_blocks());
427 EXPECT_EQ(10, op.src_extents(4).start_block());
428 EXPECT_EQ(1, op.src_extents(4).num_blocks());
429 EXPECT_EQ(14, op.src_extents(5).start_block());
430 EXPECT_EQ(1, op.src_extents(5).num_blocks());
431 EXPECT_EQ(8, op.src_extents(6).start_block());
432 EXPECT_EQ(2, op.src_extents(6).num_blocks());
433}
434
435TEST_F(DeltaDiffGeneratorTest, CutEdgesTest) {
436 Graph graph;
437 vector<Block> blocks(9);
Darin Petkov68c10d12010-10-14 09:24:37 -0700438
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700439 // Create nodes in graph
440 {
441 graph.resize(graph.size() + 1);
442 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
443 // Reads from blocks 3, 5, 7
444 vector<Extent> extents;
445 graph_utils::AppendBlockToExtents(&extents, 3);
446 graph_utils::AppendBlockToExtents(&extents, 5);
447 graph_utils::AppendBlockToExtents(&extents, 7);
448 DeltaDiffGenerator::StoreExtents(extents,
449 graph.back().op.mutable_src_extents());
450 blocks[3].reader = graph.size() - 1;
451 blocks[5].reader = graph.size() - 1;
452 blocks[7].reader = graph.size() - 1;
Darin Petkov68c10d12010-10-14 09:24:37 -0700453
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700454 // Writes to blocks 1, 2, 4
455 extents.clear();
456 graph_utils::AppendBlockToExtents(&extents, 1);
457 graph_utils::AppendBlockToExtents(&extents, 2);
458 graph_utils::AppendBlockToExtents(&extents, 4);
459 DeltaDiffGenerator::StoreExtents(extents,
460 graph.back().op.mutable_dst_extents());
461 blocks[1].writer = graph.size() - 1;
462 blocks[2].writer = graph.size() - 1;
463 blocks[4].writer = graph.size() - 1;
464 }
465 {
466 graph.resize(graph.size() + 1);
467 graph.back().op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
468 // Reads from blocks 1, 2, 4
469 vector<Extent> extents;
470 graph_utils::AppendBlockToExtents(&extents, 1);
471 graph_utils::AppendBlockToExtents(&extents, 2);
472 graph_utils::AppendBlockToExtents(&extents, 4);
473 DeltaDiffGenerator::StoreExtents(extents,
474 graph.back().op.mutable_src_extents());
475 blocks[1].reader = graph.size() - 1;
476 blocks[2].reader = graph.size() - 1;
477 blocks[4].reader = graph.size() - 1;
Darin Petkov68c10d12010-10-14 09:24:37 -0700478
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700479 // Writes to blocks 3, 5, 6
480 extents.clear();
481 graph_utils::AppendBlockToExtents(&extents, 3);
482 graph_utils::AppendBlockToExtents(&extents, 5);
483 graph_utils::AppendBlockToExtents(&extents, 6);
484 DeltaDiffGenerator::StoreExtents(extents,
485 graph.back().op.mutable_dst_extents());
486 blocks[3].writer = graph.size() - 1;
487 blocks[5].writer = graph.size() - 1;
488 blocks[6].writer = graph.size() - 1;
489 }
Darin Petkov68c10d12010-10-14 09:24:37 -0700490
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700491 // Create edges
492 DeltaDiffGenerator::CreateEdges(&graph, blocks);
Darin Petkov68c10d12010-10-14 09:24:37 -0700493
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700494 // Find cycles
495 CycleBreaker cycle_breaker;
496 set<Edge> cut_edges;
497 cycle_breaker.BreakCycles(graph, &cut_edges);
498
499 EXPECT_EQ(1, cut_edges.size());
500 EXPECT_TRUE(cut_edges.end() != cut_edges.find(make_pair<Vertex::Index>(1,
501 0)));
502
Andrew de los Reyesef017552010-10-06 17:57:52 -0700503 vector<CutEdgeVertexes> cuts;
504 EXPECT_TRUE(DeltaDiffGenerator::CutEdges(&graph, cut_edges, &cuts));
Darin Petkov68c10d12010-10-14 09:24:37 -0700505
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700506 EXPECT_EQ(3, graph.size());
Darin Petkov68c10d12010-10-14 09:24:37 -0700507
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700508 // Check new node in graph:
509 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
510 graph.back().op.type());
511 EXPECT_EQ(2, graph.back().op.src_extents_size());
Andrew de los Reyesef017552010-10-06 17:57:52 -0700512 EXPECT_EQ(1, graph.back().op.dst_extents_size());
513 EXPECT_EQ(kTempBlockStart, graph.back().op.dst_extents(0).start_block());
514 EXPECT_EQ(2, graph.back().op.dst_extents(0).num_blocks());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700515 EXPECT_TRUE(graph.back().out_edges.empty());
Darin Petkov68c10d12010-10-14 09:24:37 -0700516
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700517 // Check that old node reads from new blocks
Andrew de los Reyesef017552010-10-06 17:57:52 -0700518 EXPECT_EQ(2, graph[0].op.src_extents_size());
519 EXPECT_EQ(kTempBlockStart, graph[0].op.src_extents(0).start_block());
520 EXPECT_EQ(2, graph[0].op.src_extents(0).num_blocks());
521 EXPECT_EQ(7, graph[0].op.src_extents(1).start_block());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700522 EXPECT_EQ(1, graph[0].op.src_extents(1).num_blocks());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700523
524 // And that the old dst extents haven't changed
525 EXPECT_EQ(2, graph[0].op.dst_extents_size());
526 EXPECT_EQ(1, graph[0].op.dst_extents(0).start_block());
527 EXPECT_EQ(2, graph[0].op.dst_extents(0).num_blocks());
528 EXPECT_EQ(4, graph[0].op.dst_extents(1).start_block());
529 EXPECT_EQ(1, graph[0].op.dst_extents(1).num_blocks());
Andrew de los Reyesd12784c2010-07-26 13:55:14 -0700530
531 // Ensure it only depends on the next node and the new temp node
532 EXPECT_EQ(2, graph[0].out_edges.size());
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700533 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
Andrew de los Reyesd12784c2010-07-26 13:55:14 -0700534 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
535 1));
536
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700537 // Check second node has unchanged extents
538 EXPECT_EQ(2, graph[1].op.src_extents_size());
539 EXPECT_EQ(1, graph[1].op.src_extents(0).start_block());
540 EXPECT_EQ(2, graph[1].op.src_extents(0).num_blocks());
541 EXPECT_EQ(4, graph[1].op.src_extents(1).start_block());
542 EXPECT_EQ(1, graph[1].op.src_extents(1).num_blocks());
543
544 EXPECT_EQ(2, graph[1].op.dst_extents_size());
545 EXPECT_EQ(3, graph[1].op.dst_extents(0).start_block());
546 EXPECT_EQ(1, graph[1].op.dst_extents(0).num_blocks());
547 EXPECT_EQ(5, graph[1].op.dst_extents(1).start_block());
548 EXPECT_EQ(2, graph[1].op.dst_extents(1).num_blocks());
Darin Petkov68c10d12010-10-14 09:24:37 -0700549
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700550 // Ensure it only depends on the next node
551 EXPECT_EQ(1, graph[1].out_edges.size());
552 EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
553}
554
555TEST_F(DeltaDiffGeneratorTest, ReorderBlobsTest) {
556 string orig_blobs;
557 EXPECT_TRUE(
558 utils::MakeTempFile("ReorderBlobsTest.orig.XXXXXX", &orig_blobs, NULL));
559
560 string orig_data = "abcd";
561 EXPECT_TRUE(
562 utils::WriteFile(orig_blobs.c_str(), orig_data.data(), orig_data.size()));
563
564 string new_blobs;
565 EXPECT_TRUE(
566 utils::MakeTempFile("ReorderBlobsTest.new.XXXXXX", &new_blobs, NULL));
Darin Petkov68c10d12010-10-14 09:24:37 -0700567
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700568 DeltaArchiveManifest manifest;
569 DeltaArchiveManifest_InstallOperation* op =
570 manifest.add_install_operations();
571 op->set_data_offset(1);
572 op->set_data_length(3);
573 op = manifest.add_install_operations();
574 op->set_data_offset(0);
575 op->set_data_length(1);
Darin Petkov68c10d12010-10-14 09:24:37 -0700576
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700577 EXPECT_TRUE(DeltaDiffGenerator::ReorderDataBlobs(&manifest,
578 orig_blobs,
579 new_blobs));
Darin Petkov68c10d12010-10-14 09:24:37 -0700580
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700581 string new_data;
Gilad Arnold19a45f02012-07-19 12:36:10 -0700582 EXPECT_TRUE(utils::ReadFile(new_blobs, &new_data));
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700583 EXPECT_EQ("bcda", new_data);
584 EXPECT_EQ(2, manifest.install_operations_size());
585 EXPECT_EQ(0, manifest.install_operations(0).data_offset());
586 EXPECT_EQ(3, manifest.install_operations(0).data_length());
587 EXPECT_EQ(3, manifest.install_operations(1).data_offset());
588 EXPECT_EQ(1, manifest.install_operations(1).data_length());
Darin Petkov68c10d12010-10-14 09:24:37 -0700589
Andrew de los Reyesb10320d2010-03-31 16:44:44 -0700590 unlink(orig_blobs.c_str());
591 unlink(new_blobs.c_str());
592}
adlr@google.com3defe6a2009-12-04 20:57:17 +0000593
Andrew de los Reyesef017552010-10-06 17:57:52 -0700594TEST_F(DeltaDiffGeneratorTest, MoveFullOpsToBackTest) {
595 Graph graph(4);
596 graph[0].file_name = "A";
597 graph[0].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE);
598 graph[1].file_name = "B";
599 graph[1].op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF);
600 graph[2].file_name = "C";
601 graph[2].op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
602 graph[3].file_name = "D";
603 graph[3].op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
604
605 vector<Vertex::Index> vect(graph.size());
606
607 for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
608 vect[i] = i;
609 }
610 DeltaDiffGenerator::MoveFullOpsToBack(&graph, &vect);
611 EXPECT_EQ(vect.size(), graph.size());
612 EXPECT_EQ(graph[vect[0]].file_name, "B");
613 EXPECT_EQ(graph[vect[1]].file_name, "D");
614 EXPECT_EQ(graph[vect[2]].file_name, "A");
615 EXPECT_EQ(graph[vect[3]].file_name, "C");
616}
617
618namespace {
619
620#define OP_BSDIFF DeltaArchiveManifest_InstallOperation_Type_BSDIFF
621#define OP_MOVE DeltaArchiveManifest_InstallOperation_Type_MOVE
622#define OP_REPLACE DeltaArchiveManifest_InstallOperation_Type_REPLACE
623#define OP_REPLACE_BZ DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ
624
625void GenVertex(Vertex* out,
626 const vector<Extent>& src_extents,
627 const vector<Extent>& dst_extents,
628 const string& path,
629 DeltaArchiveManifest_InstallOperation_Type type) {
630 out->op.set_type(type);
631 out->file_name = path;
632 DeltaDiffGenerator::StoreExtents(src_extents, out->op.mutable_src_extents());
633 DeltaDiffGenerator::StoreExtents(dst_extents, out->op.mutable_dst_extents());
634}
635
636vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
637 return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
638}
639
640EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
641 EdgeProperties ret;
642 ret.extents = extents;
643 return ret;
644}
645
646EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
647 EdgeProperties ret;
648 ret.write_extents = extents;
649 return ret;
650}
651
652template<typename T>
653void DumpVect(const vector<T>& vect) {
654 std::stringstream ss(stringstream::out);
655 for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
656 it != e; ++it) {
657 ss << *it << ", ";
658 }
659 LOG(INFO) << "{" << ss.str() << "}";
660}
661
662} // namespace {}
663
664TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksTest) {
665 Graph graph(9);
666 const vector<Extent> empt; // empty
667 const string kFilename = "/foo";
Darin Petkov68c10d12010-10-14 09:24:37 -0700668
Andrew de los Reyesef017552010-10-06 17:57:52 -0700669 // Some scratch space:
670 GenVertex(&graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
671 GenVertex(&graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
672 GenVertex(&graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
673
674 // A cycle that requires 10 blocks to break:
675 GenVertex(&graph[3], VectOfExt(10, 11), VectOfExt(0, 9), "", OP_BSDIFF);
676 graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
677 GenVertex(&graph[4], VectOfExt(0, 9), VectOfExt(10, 11), "", OP_BSDIFF);
678 graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
679
680 // A cycle that requires 9 blocks to break:
681 GenVertex(&graph[5], VectOfExt(40, 11), VectOfExt(30, 10), "", OP_BSDIFF);
682 graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
683 GenVertex(&graph[6], VectOfExt(30, 10), VectOfExt(40, 11), "", OP_BSDIFF);
684 graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
685
686 // A cycle that requires 40 blocks to break (which is too many):
687 GenVertex(&graph[7],
688 VectOfExt(120, 50),
689 VectOfExt(60, 40),
690 "",
691 OP_BSDIFF);
692 graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
693 GenVertex(&graph[8],
694 VectOfExt(60, 40),
695 VectOfExt(120, 50),
696 kFilename,
697 OP_BSDIFF);
698 graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
Darin Petkov68c10d12010-10-14 09:24:37 -0700699
Andrew de los Reyesef017552010-10-06 17:57:52 -0700700 graph_utils::DumpGraph(graph);
Darin Petkov68c10d12010-10-14 09:24:37 -0700701
Andrew de los Reyesef017552010-10-06 17:57:52 -0700702 vector<Vertex::Index> final_order;
703
704
705 // Prepare the filesystem with the minimum required for this to work
706 string temp_dir;
Gilad Arnolda6742b32014-01-11 00:18:34 -0800707 EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksTest.XXXXXX",
Andrew de los Reyesef017552010-10-06 17:57:52 -0700708 &temp_dir));
709 ScopedDirRemover temp_dir_remover(temp_dir);
Darin Petkov68c10d12010-10-14 09:24:37 -0700710
Andrew de los Reyesef017552010-10-06 17:57:52 -0700711 const size_t kBlockSize = 4096;
712 vector<char> temp_data(kBlockSize * 50);
713 FillWithData(&temp_data);
714 EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
715 ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
Darin Petkov68c10d12010-10-14 09:24:37 -0700716
Andrew de los Reyesef017552010-10-06 17:57:52 -0700717 int fd;
Gilad Arnolda6742b32014-01-11 00:18:34 -0800718 EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksTestData.XXXXXX",
Andrew de los Reyesef017552010-10-06 17:57:52 -0700719 NULL,
720 &fd));
721 ScopedFdCloser fd_closer(&fd);
722 off_t data_file_size = 0;
723
724
725 EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
726 temp_dir,
727 fd,
728 &data_file_size,
Andrew de los Reyes927179d2010-12-02 11:26:48 -0800729 &final_order,
730 Vertex::kInvalidIndex));
Andrew de los Reyesef017552010-10-06 17:57:52 -0700731
Darin Petkov68c10d12010-10-14 09:24:37 -0700732
Andrew de los Reyesef017552010-10-06 17:57:52 -0700733 Graph expected_graph(12);
734 GenVertex(&expected_graph[0], empt, VectOfExt(200, 1), "", OP_REPLACE);
735 GenVertex(&expected_graph[1], empt, VectOfExt(210, 10), "", OP_REPLACE);
736 GenVertex(&expected_graph[2], empt, VectOfExt(220, 1), "", OP_REPLACE);
737 GenVertex(&expected_graph[3],
738 VectOfExt(10, 11),
739 VectOfExt(0, 9),
740 "",
741 OP_BSDIFF);
742 expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
743 GenVertex(&expected_graph[4],
744 VectOfExt(60, 9),
745 VectOfExt(10, 11),
746 "",
747 OP_BSDIFF);
748 expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
749 expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
750 GenVertex(&expected_graph[5],
751 VectOfExt(40, 11),
752 VectOfExt(30, 10),
753 "",
754 OP_BSDIFF);
755 expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
756
757 GenVertex(&expected_graph[6],
758 VectOfExt(60, 10),
759 VectOfExt(40, 11),
760 "",
761 OP_BSDIFF);
762 expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
763 expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
Darin Petkov68c10d12010-10-14 09:24:37 -0700764
Andrew de los Reyesef017552010-10-06 17:57:52 -0700765 GenVertex(&expected_graph[7],
766 VectOfExt(120, 50),
767 VectOfExt(60, 40),
768 "",
769 OP_BSDIFF);
770 expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
771
772 GenVertex(&expected_graph[8], empt, VectOfExt(0, 50), "/foo", OP_REPLACE_BZ);
773 expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
774
775 GenVertex(&expected_graph[9],
776 VectOfExt(0, 9),
777 VectOfExt(60, 9),
778 "",
779 OP_MOVE);
780
781 GenVertex(&expected_graph[10],
782 VectOfExt(30, 10),
783 VectOfExt(60, 10),
784 "",
785 OP_MOVE);
786 expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
Darin Petkov68c10d12010-10-14 09:24:37 -0700787
Andrew de los Reyesef017552010-10-06 17:57:52 -0700788 EXPECT_EQ(12, graph.size());
789 EXPECT_FALSE(graph.back().valid);
790 for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
791 EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
792 if (i == 8) {
793 // special case
794 } else {
795 // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
796 }
797 }
798}
799
Darin Petkov94817cb2013-05-08 14:33:24 +0200800// Test that sparse holes are not used as scratch. More specifically, test that
801// if all full operations write to sparse holes and there's no extra scratch
802// space, delta operations that need scratch are converted to full. See
803// crbug.com/238440.
804TEST_F(DeltaDiffGeneratorTest, RunAsRootNoSparseAsTempTest) {
805 Graph graph(3);
806 const vector<Extent> kEmpty;
807 const string kFilename = "/foo";
808
809 // Make sure this sparse hole is not used as scratch.
810 GenVertex(&graph[0], kEmpty, VectOfExt(kSparseHole, 1), "", OP_REPLACE);
811
812 // Create a single-block cycle.
813 GenVertex(&graph[1], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_BSDIFF);
814 graph[1].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
815 GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(0, 1), kFilename, OP_BSDIFF);
816 graph[2].out_edges[1] = EdgeWithReadDep(VectOfExt(0, 1));
817
818 graph_utils::DumpGraph(graph);
819
820 vector<Vertex::Index> final_order;
821
822 // Prepare the filesystem with the minimum required for this to work.
823 string temp_dir;
Gilad Arnolda6742b32014-01-11 00:18:34 -0800824 EXPECT_TRUE(utils::MakeTempDirectory("NoSparseAsTempTest.XXXXXX",
Darin Petkov94817cb2013-05-08 14:33:24 +0200825 &temp_dir));
826 ScopedDirRemover temp_dir_remover(temp_dir);
827
828 const size_t kBlockSize = 4096;
829 vector<char> temp_data(kBlockSize);
830 FillWithData(&temp_data);
831 EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
832 ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
833
834 int fd = -1;
Gilad Arnolda6742b32014-01-11 00:18:34 -0800835 EXPECT_TRUE(utils::MakeTempFile("NoSparseAsTempTestData.XXXXXX",
Darin Petkov94817cb2013-05-08 14:33:24 +0200836 NULL,
837 &fd));
838 ScopedFdCloser fd_closer(&fd);
839 off_t data_file_size = 0;
840
841 EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
842 temp_dir,
843 fd,
844 &data_file_size,
845 &final_order,
846 Vertex::kInvalidIndex));
847
848 ASSERT_EQ(4, graph.size());
849
850 // The second BSDIFF operation must have been converted to a full operation
851 // (due to insufficient scratch space).
852 EXPECT_TRUE(graph[2].op.type() == OP_REPLACE ||
853 graph[2].op.type() == OP_REPLACE_BZ);
854
855 // The temporary node created for breaking the cycle must have been marked as
856 // invalid.
857 EXPECT_FALSE(graph[3].valid);
858}
859
860// Test that sparse holes are not used as scratch. More specifically, test that
861// if scratch space comes only from full operations writing to real blocks as
862// well as sparse holes, only the real blocks are utilized. See
863// crbug.com/238440.
864TEST_F(DeltaDiffGeneratorTest, NoSparseAsTempTest) {
865 Graph graph;
866 vector<Block> blocks(4);
867
868 // Create nodes in |graph|.
869 {
870 graph.resize(graph.size() + 1);
871 graph.back().op.set_type(
872 DeltaArchiveManifest_InstallOperation_Type_REPLACE);
873
874 // Write to a sparse hole -- basically a no-op to ensure sparse holes are
875 // not used as scratch.
876 vector<Extent> extents;
877 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
878 DeltaDiffGenerator::StoreExtents(extents,
879 graph.back().op.mutable_dst_extents());
880 }
881 {
882 graph.resize(graph.size() + 1);
883 graph.back().op.set_type(OP_REPLACE);
884
885 // Scratch space: write to block 0 with sparse holes around.
886 vector<Extent> extents;
887 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
888 graph_utils::AppendBlockToExtents(&extents, 0);
889 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
890 DeltaDiffGenerator::StoreExtents(extents,
891 graph.back().op.mutable_dst_extents());
892 blocks[0].writer = graph.size() - 1;
893 }
894 {
895 graph.resize(graph.size() + 1);
896 graph.back().op.set_type(OP_REPLACE);
897
898 // Write to a sparse hole.
899 vector<Extent> extents;
900 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
901 DeltaDiffGenerator::StoreExtents(extents,
902 graph.back().op.mutable_dst_extents());
903 }
904 // Create a two-node cycle between (2, sparse, sparse) and (1, sparse, 3).
905 {
906 graph.resize(graph.size() + 1);
907 graph.back().op.set_type(OP_MOVE);
908 // Read from (2, sparse, sparse).
909 vector<Extent> extents;
910 graph_utils::AppendBlockToExtents(&extents, 2);
911 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
912 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
913 DeltaDiffGenerator::StoreExtents(extents,
914 graph.back().op.mutable_src_extents());
915 blocks[2].reader = graph.size() - 1;
916
917 // Write to (1, sparse, 3).
918 extents.clear();
919 graph_utils::AppendBlockToExtents(&extents, 1);
920 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
921 graph_utils::AppendBlockToExtents(&extents, 3);
922 DeltaDiffGenerator::StoreExtents(extents,
923 graph.back().op.mutable_dst_extents());
924 blocks[1].writer = graph.size() - 1;
925 blocks[3].writer = graph.size() - 1;
926 }
927 {
928 graph.resize(graph.size() + 1);
929 graph.back().op.set_type(OP_MOVE);
930 // Read from (1, sparse, 3).
931 vector<Extent> extents;
932 graph_utils::AppendBlockToExtents(&extents, 1);
933 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
934 graph_utils::AppendBlockToExtents(&extents, 3);
935 DeltaDiffGenerator::StoreExtents(extents,
936 graph.back().op.mutable_src_extents());
937 blocks[1].reader = graph.size() - 1;
938 blocks[3].reader = graph.size() - 1;
939
940 // Write to (2, sparse, sparse).
941 extents.clear();
942 graph_utils::AppendBlockToExtents(&extents, 2);
943 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
944 graph_utils::AppendBlockToExtents(&extents, kSparseHole);
945 DeltaDiffGenerator::StoreExtents(extents,
946 graph.back().op.mutable_dst_extents());
947 blocks[2].writer = graph.size() - 1;
948 }
949
950 graph_utils::DumpGraph(graph);
951
952 // Create edges
953 DeltaDiffGenerator::CreateEdges(&graph, blocks);
954
955 graph_utils::DumpGraph(graph);
956
957 vector<Vertex::Index> final_order;
958 off_t data_file_size = 0;
959 EXPECT_TRUE(DeltaDiffGenerator::ConvertGraphToDag(&graph,
960 "/non/existent/dir",
961 -1,
962 &data_file_size,
963 &final_order,
964 Vertex::kInvalidIndex));
965
966 // Check for a single temporary node writing to scratch.
967 ASSERT_EQ(6, graph.size());
968 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_MOVE,
969 graph[5].op.type());
970 EXPECT_EQ(1, graph[5].op.src_extents_size());
971 ASSERT_EQ(1, graph[5].op.dst_extents_size());
972 EXPECT_EQ(0, graph[5].op.dst_extents(0).start_block());
973 EXPECT_EQ(1, graph[5].op.dst_extents(0).num_blocks());
974
975 // Make sure the cycle nodes still read from and write to sparse holes.
976 for (int i = 3; i < 5; i++) {
977 ASSERT_GE(graph[i].op.src_extents_size(), 2);
978 EXPECT_EQ(kSparseHole, graph[i].op.src_extents(1).start_block());
979 ASSERT_GE(graph[i].op.dst_extents_size(), 2);
980 EXPECT_EQ(kSparseHole, graph[i].op.dst_extents(1).start_block());
981 }
982}
983
Darin Petkov9fa7ec52010-10-18 11:45:23 -0700984TEST_F(DeltaDiffGeneratorTest, IsNoopOperationTest) {
985 DeltaArchiveManifest_InstallOperation op;
986 op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ);
987 EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
988 op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE);
989 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
990 *(op.add_src_extents()) = ExtentForRange(3, 2);
991 *(op.add_dst_extents()) = ExtentForRange(3, 2);
992 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
993 *(op.add_src_extents()) = ExtentForRange(7, 5);
994 *(op.add_dst_extents()) = ExtentForRange(7, 5);
995 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
996 *(op.add_src_extents()) = ExtentForRange(20, 2);
997 *(op.add_dst_extents()) = ExtentForRange(20, 1);
998 *(op.add_dst_extents()) = ExtentForRange(21, 1);
999 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
1000 *(op.add_src_extents()) = ExtentForRange(kSparseHole, 2);
1001 *(op.add_src_extents()) = ExtentForRange(kSparseHole, 1);
1002 *(op.add_dst_extents()) = ExtentForRange(kSparseHole, 3);
1003 EXPECT_TRUE(DeltaDiffGenerator::IsNoopOperation(op));
1004 *(op.add_src_extents()) = ExtentForRange(24, 1);
1005 *(op.add_dst_extents()) = ExtentForRange(25, 1);
1006 EXPECT_FALSE(DeltaDiffGenerator::IsNoopOperation(op));
1007}
1008
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -07001009TEST_F(DeltaDiffGeneratorTest, RunAsRootAssignTempBlocksReuseTest) {
1010 // AssignTempBlocks(Graph* graph,
1011 // const string& new_root,
1012 // int data_fd,
1013 // off_t* data_file_size,
1014 // vector<Vertex::Index>* op_indexes,
1015 // vector<vector<Vertex::Index>::size_type>* reverse_op_indexes,
1016 // const vector<CutEdgeVertexes>& cuts
1017 Graph graph(9);
1018
1019 const vector<Extent> empt;
1020 uint64_t tmp = kTempBlockStart;
1021 const string kFilename = "/foo";
1022
1023 vector<CutEdgeVertexes> cuts;
1024 cuts.resize(3);
1025
1026 // Simple broken loop:
1027 GenVertex(&graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", OP_MOVE);
1028 GenVertex(&graph[1], VectOfExt(tmp, 1), VectOfExt(0, 1), "", OP_MOVE);
1029 GenVertex(&graph[2], VectOfExt(1, 1), VectOfExt(tmp, 1), "", OP_MOVE);
1030 // Corresponding edges:
1031 graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
1032 graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
1033 graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
1034 // Store the cut:
1035 cuts[0].old_dst = 1;
1036 cuts[0].old_src = 0;
1037 cuts[0].new_vertex = 2;
1038 cuts[0].tmp_extents = VectOfExt(tmp, 1);
1039 tmp++;
1040
1041 // Slightly more complex pair of loops:
1042 GenVertex(&graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", OP_MOVE);
1043 GenVertex(&graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", OP_MOVE);
1044 GenVertex(&graph[5], VectOfExt(tmp, 3), VectOfExt(4, 3), kFilename, OP_MOVE);
1045 GenVertex(&graph[6], VectOfExt(2, 2), VectOfExt(tmp, 2), "", OP_MOVE);
1046 GenVertex(&graph[7], VectOfExt(7, 1), VectOfExt(tmp + 2, 1), "", OP_MOVE);
1047 // Corresponding edges:
1048 graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
1049 graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
1050 graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
1051 graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
1052 graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
1053 graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
1054 // Store the cuts:
1055 cuts[1].old_dst = 5;
1056 cuts[1].old_src = 3;
1057 cuts[1].new_vertex = 6;
1058 cuts[1].tmp_extents = VectOfExt(tmp, 2);
1059 cuts[2].old_dst = 5;
1060 cuts[2].old_src = 4;
1061 cuts[2].new_vertex = 7;
1062 cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
1063
1064 // Supplier of temp block:
1065 GenVertex(&graph[8], empt, VectOfExt(8, 1), "", OP_REPLACE);
1066
1067 // Specify the final order:
1068 vector<Vertex::Index> op_indexes;
1069 op_indexes.push_back(2);
1070 op_indexes.push_back(0);
1071 op_indexes.push_back(1);
1072 op_indexes.push_back(6);
1073 op_indexes.push_back(3);
1074 op_indexes.push_back(7);
1075 op_indexes.push_back(4);
1076 op_indexes.push_back(5);
1077 op_indexes.push_back(8);
1078
1079 vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
1080 DeltaDiffGenerator::GenerateReverseTopoOrderMap(op_indexes,
1081 &reverse_op_indexes);
1082
1083 // Prepare the filesystem with the minimum required for this to work
1084 string temp_dir;
Gilad Arnolda6742b32014-01-11 00:18:34 -08001085 EXPECT_TRUE(utils::MakeTempDirectory("AssignTempBlocksReuseTest.XXXXXX",
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -07001086 &temp_dir));
1087 ScopedDirRemover temp_dir_remover(temp_dir);
1088
1089 const size_t kBlockSize = 4096;
1090 vector<char> temp_data(kBlockSize * 3);
1091 FillWithData(&temp_data);
1092 EXPECT_TRUE(WriteFileVector(temp_dir + kFilename, temp_data));
1093 ScopedPathUnlinker filename_unlinker(temp_dir + kFilename);
1094
1095 int fd;
Gilad Arnolda6742b32014-01-11 00:18:34 -08001096 EXPECT_TRUE(utils::MakeTempFile("AssignTempBlocksReuseTest.XXXXXX",
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -07001097 NULL,
1098 &fd));
1099 ScopedFdCloser fd_closer(&fd);
1100 off_t data_file_size = 0;
Thieu Le5c7d9752010-12-15 16:09:28 -08001101
Andrew de los Reyes4ba850d2010-10-25 12:12:40 -07001102 EXPECT_TRUE(DeltaDiffGenerator::AssignTempBlocks(&graph,
1103 temp_dir,
1104 fd,
1105 &data_file_size,
1106 &op_indexes,
1107 &reverse_op_indexes,
1108 cuts));
1109 EXPECT_FALSE(graph[6].valid);
1110 EXPECT_FALSE(graph[7].valid);
1111 EXPECT_EQ(1, graph[1].op.src_extents_size());
1112 EXPECT_EQ(2, graph[1].op.src_extents(0).start_block());
1113 EXPECT_EQ(1, graph[1].op.src_extents(0).num_blocks());
1114 EXPECT_EQ(OP_REPLACE_BZ, graph[5].op.type());
1115}
1116
Andrew de los Reyes927179d2010-12-02 11:26:48 -08001117TEST_F(DeltaDiffGeneratorTest, CreateScratchNodeTest) {
1118 Vertex vertex;
1119 DeltaDiffGenerator::CreateScratchNode(12, 34, &vertex);
1120 EXPECT_EQ(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ,
1121 vertex.op.type());
1122 EXPECT_EQ(0, vertex.op.data_offset());
1123 EXPECT_EQ(0, vertex.op.data_length());
1124 EXPECT_EQ(1, vertex.op.dst_extents_size());
1125 EXPECT_EQ(12, vertex.op.dst_extents(0).start_block());
1126 EXPECT_EQ(34, vertex.op.dst_extents(0).num_blocks());
1127}
1128
adlr@google.com3defe6a2009-12-04 20:57:17 +00001129} // namespace chromeos_update_engine