1 //
2 // Copyright (C) 2015 The Android Open Source Project
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 //
16
17 #include "update_engine/payload_generator/inplace_generator.h"
18
19 #include <map>
20 #include <set>
21 #include <sstream>
22 #include <string>
23 #include <utility>
24 #include <vector>
25
26 #include <base/format_macros.h>
27 #include <base/logging.h>
28 #include <base/strings/string_util.h>
29 #include <base/strings/stringprintf.h>
30 #include <gtest/gtest.h>
31
32 #include "update_engine/common/test_utils.h"
33 #include "update_engine/common/utils.h"
34 #include "update_engine/payload_generator/cycle_breaker.h"
35 #include "update_engine/payload_generator/delta_diff_generator.h"
36 #include "update_engine/payload_generator/delta_diff_utils.h"
37 #include "update_engine/payload_generator/extent_ranges.h"
38 #include "update_engine/payload_generator/graph_types.h"
39 #include "update_engine/payload_generator/graph_utils.h"
40
41 using std::map;
42 using std::set;
43 using std::string;
44 using std::stringstream;
45 using std::vector;
46
47 namespace chromeos_update_engine {
48
49 using Block = InplaceGenerator::Block;
50
51 namespace {
52
GenVertex(Vertex * out,const vector<Extent> & src_extents,const vector<Extent> & dst_extents,const string & path,InstallOperation_Type type)53 void GenVertex(Vertex* out,
54 const vector<Extent>& src_extents,
55 const vector<Extent>& dst_extents,
56 const string& path,
57 InstallOperation_Type type) {
58 out->aop.op.set_type(type);
59 out->aop.name = path;
60 StoreExtents(src_extents, out->aop.op.mutable_src_extents());
61 StoreExtents(dst_extents, out->aop.op.mutable_dst_extents());
62 }
63
VectOfExt(uint64_t start_block,uint64_t num_blocks)64 vector<Extent> VectOfExt(uint64_t start_block, uint64_t num_blocks) {
65 return vector<Extent>(1, ExtentForRange(start_block, num_blocks));
66 }
67
EdgeWithReadDep(const vector<Extent> & extents)68 EdgeProperties EdgeWithReadDep(const vector<Extent>& extents) {
69 EdgeProperties ret;
70 ret.extents = extents;
71 return ret;
72 }
73
EdgeWithWriteDep(const vector<Extent> & extents)74 EdgeProperties EdgeWithWriteDep(const vector<Extent>& extents) {
75 EdgeProperties ret;
76 ret.write_extents = extents;
77 return ret;
78 }
79
80 template<typename T>
DumpVect(const vector<T> & vect)81 void DumpVect(const vector<T>& vect) {
82 stringstream ss(stringstream::out);
83 for (typename vector<T>::const_iterator it = vect.begin(), e = vect.end();
84 it != e; ++it) {
85 ss << *it << ", ";
86 }
87 LOG(INFO) << "{" << ss.str() << "}";
88 }
89
AppendExtent(vector<Extent> * vect,uint64_t start,uint64_t length)90 void AppendExtent(vector<Extent>* vect, uint64_t start, uint64_t length) {
91 vect->resize(vect->size() + 1);
92 vect->back().set_start_block(start);
93 vect->back().set_num_blocks(length);
94 }
95
OpAppendExtent(InstallOperation * op,uint64_t start,uint64_t length)96 void OpAppendExtent(InstallOperation* op, uint64_t start, uint64_t length) {
97 Extent* extent = op->add_src_extents();
98 extent->set_start_block(start);
99 extent->set_num_blocks(length);
100 }
101
102 } // namespace
103
104 class InplaceGeneratorTest : public ::testing::Test {
105 protected:
106 // Initialize |blob_path_|, |blob_file_size_| and |blob_file_fd_| variables
107 // with a new blob file. The file is closed and removed automatically when
108 // the test finishes.
CreateBlobFile()109 void CreateBlobFile() {
110 // blob_fd_closer_ takes a pointer to blob_fd_. Make sure we destroy a
111 // previous instance before overriding blob_fd_.
112 blob_fd_closer_.reset();
113 EXPECT_TRUE(utils::MakeTempFile(
114 "InplaceGenerator_blob_file.XXXXXX", &blob_path_, &blob_fd_));
115 blob_path_unlinker_.reset(new ScopedPathUnlinker(blob_path_));
116 blob_fd_closer_.reset(new ScopedFdCloser(&blob_fd_));
117 blob_file_size_ = 0;
118 EXPECT_GE(blob_fd_, 0);
119 blob_file_.reset(new BlobFileWriter(blob_fd_, &blob_file_size_));
120 }
121
122 // Dump the list of operations |aops| in case of test failure.
DumpAopsOnFailure(const vector<AnnotatedOperation> & aops)123 void DumpAopsOnFailure(const vector<AnnotatedOperation>& aops) {
124 if (HasNonfatalFailure()) {
125 LOG(INFO) << "Result operation list:";
126 for (const auto& aop : aops) {
127 LOG(INFO) << aop;
128 }
129 }
130 }
131
132 // Blob file name, file descriptor and file size used to store operation
133 // blobs.
134 string blob_path_;
135 int blob_fd_{-1};
136 off_t blob_file_size_{0};
137 std::unique_ptr<BlobFileWriter> blob_file_;
138 std::unique_ptr<ScopedPathUnlinker> blob_path_unlinker_;
139 std::unique_ptr<ScopedFdCloser> blob_fd_closer_;
140 };
141
TEST_F(InplaceGeneratorTest,BlockDefaultValues)142 TEST_F(InplaceGeneratorTest, BlockDefaultValues) {
143 // Tests that a Block is initialized with the default values as a
144 // Vertex::kInvalidIndex. This is required by the delta generators.
145 Block block;
146 EXPECT_EQ(Vertex::kInvalidIndex, block.reader);
147 EXPECT_EQ(Vertex::kInvalidIndex, block.writer);
148 }
149
TEST_F(InplaceGeneratorTest,SubstituteBlocksTest)150 TEST_F(InplaceGeneratorTest, SubstituteBlocksTest) {
151 vector<Extent> remove_blocks;
152 AppendExtent(&remove_blocks, 3, 3);
153 AppendExtent(&remove_blocks, 7, 1);
154 vector<Extent> replace_blocks;
155 AppendExtent(&replace_blocks, 10, 2);
156 AppendExtent(&replace_blocks, 13, 2);
157 Vertex vertex;
158 InstallOperation& op = vertex.aop.op;
159 OpAppendExtent(&op, 4, 3);
160 OpAppendExtent(&op, kSparseHole, 4); // Sparse hole in file
161 OpAppendExtent(&op, 3, 1);
162 OpAppendExtent(&op, 7, 3);
163
164 InplaceGenerator::SubstituteBlocks(&vertex, remove_blocks, replace_blocks);
165
166 EXPECT_EQ(7, op.src_extents_size());
167 EXPECT_EQ(11U, op.src_extents(0).start_block());
168 EXPECT_EQ(1U, op.src_extents(0).num_blocks());
169 EXPECT_EQ(13U, op.src_extents(1).start_block());
170 EXPECT_EQ(1U, op.src_extents(1).num_blocks());
171 EXPECT_EQ(6U, op.src_extents(2).start_block());
172 EXPECT_EQ(1U, op.src_extents(2).num_blocks());
173 EXPECT_EQ(kSparseHole, op.src_extents(3).start_block());
174 EXPECT_EQ(4U, op.src_extents(3).num_blocks());
175 EXPECT_EQ(10U, op.src_extents(4).start_block());
176 EXPECT_EQ(1U, op.src_extents(4).num_blocks());
177 EXPECT_EQ(14U, op.src_extents(5).start_block());
178 EXPECT_EQ(1U, op.src_extents(5).num_blocks());
179 EXPECT_EQ(8U, op.src_extents(6).start_block());
180 EXPECT_EQ(2U, op.src_extents(6).num_blocks());
181 }
182
TEST_F(InplaceGeneratorTest,CutEdgesTest)183 TEST_F(InplaceGeneratorTest, CutEdgesTest) {
184 Graph graph;
185 vector<Block> blocks(9);
186
187 // Create nodes in graph
188 {
189 graph.resize(graph.size() + 1);
190 graph.back().aop.op.set_type(InstallOperation::MOVE);
191 // Reads from blocks 3, 5, 7
192 vector<Extent> extents;
193 AppendBlockToExtents(&extents, 3);
194 AppendBlockToExtents(&extents, 5);
195 AppendBlockToExtents(&extents, 7);
196 StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
197 blocks[3].reader = graph.size() - 1;
198 blocks[5].reader = graph.size() - 1;
199 blocks[7].reader = graph.size() - 1;
200
201 // Writes to blocks 1, 2, 4
202 extents.clear();
203 AppendBlockToExtents(&extents, 1);
204 AppendBlockToExtents(&extents, 2);
205 AppendBlockToExtents(&extents, 4);
206 StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
207 blocks[1].writer = graph.size() - 1;
208 blocks[2].writer = graph.size() - 1;
209 blocks[4].writer = graph.size() - 1;
210 }
211 {
212 graph.resize(graph.size() + 1);
213 graph.back().aop.op.set_type(InstallOperation::MOVE);
214 // Reads from blocks 1, 2, 4
215 vector<Extent> extents;
216 AppendBlockToExtents(&extents, 1);
217 AppendBlockToExtents(&extents, 2);
218 AppendBlockToExtents(&extents, 4);
219 StoreExtents(extents, graph.back().aop.op.mutable_src_extents());
220 blocks[1].reader = graph.size() - 1;
221 blocks[2].reader = graph.size() - 1;
222 blocks[4].reader = graph.size() - 1;
223
224 // Writes to blocks 3, 5, 6
225 extents.clear();
226 AppendBlockToExtents(&extents, 3);
227 AppendBlockToExtents(&extents, 5);
228 AppendBlockToExtents(&extents, 6);
229 StoreExtents(extents, graph.back().aop.op.mutable_dst_extents());
230 blocks[3].writer = graph.size() - 1;
231 blocks[5].writer = graph.size() - 1;
232 blocks[6].writer = graph.size() - 1;
233 }
234
235 // Create edges
236 InplaceGenerator::CreateEdges(&graph, blocks);
237
238 // Find cycles
239 CycleBreaker cycle_breaker;
240 set<Edge> cut_edges;
241 cycle_breaker.BreakCycles(graph, &cut_edges);
242
243 EXPECT_EQ(1U, cut_edges.size());
244 EXPECT_TRUE(cut_edges.end() != cut_edges.find(
245 std::pair<Vertex::Index, Vertex::Index>(1, 0)));
246
247 vector<CutEdgeVertexes> cuts;
248 EXPECT_TRUE(InplaceGenerator::CutEdges(&graph, cut_edges, &cuts));
249
250 EXPECT_EQ(3U, graph.size());
251
252 // Check new node in graph:
253 EXPECT_EQ(InstallOperation::MOVE, graph.back().aop.op.type());
254 EXPECT_EQ(2, graph.back().aop.op.src_extents_size());
255 EXPECT_EQ(1, graph.back().aop.op.dst_extents_size());
256 EXPECT_EQ(kTempBlockStart, graph.back().aop.op.dst_extents(0).start_block());
257 EXPECT_EQ(2U, graph.back().aop.op.dst_extents(0).num_blocks());
258 EXPECT_TRUE(graph.back().out_edges.empty());
259
260 // Check that old node reads from new blocks
261 EXPECT_EQ(2, graph[0].aop.op.src_extents_size());
262 EXPECT_EQ(kTempBlockStart, graph[0].aop.op.src_extents(0).start_block());
263 EXPECT_EQ(2U, graph[0].aop.op.src_extents(0).num_blocks());
264 EXPECT_EQ(7U, graph[0].aop.op.src_extents(1).start_block());
265 EXPECT_EQ(1U, graph[0].aop.op.src_extents(1).num_blocks());
266
267 // And that the old dst extents haven't changed
268 EXPECT_EQ(2, graph[0].aop.op.dst_extents_size());
269 EXPECT_EQ(1U, graph[0].aop.op.dst_extents(0).start_block());
270 EXPECT_EQ(2U, graph[0].aop.op.dst_extents(0).num_blocks());
271 EXPECT_EQ(4U, graph[0].aop.op.dst_extents(1).start_block());
272 EXPECT_EQ(1U, graph[0].aop.op.dst_extents(1).num_blocks());
273
274 // Ensure it only depends on the next node and the new temp node
275 EXPECT_EQ(2U, graph[0].out_edges.size());
276 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(1));
277 EXPECT_TRUE(graph[0].out_edges.end() != graph[0].out_edges.find(graph.size() -
278 1));
279
280 // Check second node has unchanged extents
281 EXPECT_EQ(2, graph[1].aop.op.src_extents_size());
282 EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).start_block());
283 EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).num_blocks());
284 EXPECT_EQ(4U, graph[1].aop.op.src_extents(1).start_block());
285 EXPECT_EQ(1U, graph[1].aop.op.src_extents(1).num_blocks());
286
287 EXPECT_EQ(2, graph[1].aop.op.dst_extents_size());
288 EXPECT_EQ(3U, graph[1].aop.op.dst_extents(0).start_block());
289 EXPECT_EQ(1U, graph[1].aop.op.dst_extents(0).num_blocks());
290 EXPECT_EQ(5U, graph[1].aop.op.dst_extents(1).start_block());
291 EXPECT_EQ(2U, graph[1].aop.op.dst_extents(1).num_blocks());
292
293 // Ensure it only depends on the next node
294 EXPECT_EQ(1U, graph[1].out_edges.size());
295 EXPECT_TRUE(graph[1].out_edges.end() != graph[1].out_edges.find(2));
296 }
297
TEST_F(InplaceGeneratorTest,AssignTempBlocksReuseTest)298 TEST_F(InplaceGeneratorTest, AssignTempBlocksReuseTest) {
299 Graph graph(9);
300
301 const vector<Extent> empt;
302 uint64_t tmp = kTempBlockStart;
303 const string kFilename = "/foo";
304
305 vector<CutEdgeVertexes> cuts;
306 cuts.resize(3);
307
308 // Simple broken loop:
309 GenVertex(
310 &graph[0], VectOfExt(0, 1), VectOfExt(1, 1), "", InstallOperation::MOVE);
311 GenVertex(&graph[1],
312 VectOfExt(tmp, 1),
313 VectOfExt(0, 1),
314 "",
315 InstallOperation::MOVE);
316 GenVertex(&graph[2],
317 VectOfExt(1, 1),
318 VectOfExt(tmp, 1),
319 "",
320 InstallOperation::MOVE);
321 // Corresponding edges:
322 graph[0].out_edges[2] = EdgeWithReadDep(VectOfExt(1, 1));
323 graph[1].out_edges[2] = EdgeWithWriteDep(VectOfExt(tmp, 1));
324 graph[1].out_edges[0] = EdgeWithReadDep(VectOfExt(0, 1));
325 // Store the cut:
326 cuts[0].old_dst = 1;
327 cuts[0].old_src = 0;
328 cuts[0].new_vertex = 2;
329 cuts[0].tmp_extents = VectOfExt(tmp, 1);
330 tmp++;
331
332 // Slightly more complex pair of loops:
333 GenVertex(
334 &graph[3], VectOfExt(4, 2), VectOfExt(2, 2), "", InstallOperation::MOVE);
335 GenVertex(
336 &graph[4], VectOfExt(6, 1), VectOfExt(7, 1), "", InstallOperation::MOVE);
337 GenVertex(&graph[5],
338 VectOfExt(tmp, 3),
339 VectOfExt(4, 3),
340 kFilename,
341 InstallOperation::MOVE);
342 GenVertex(&graph[6],
343 VectOfExt(2, 2),
344 VectOfExt(tmp, 2),
345 "",
346 InstallOperation::MOVE);
347 GenVertex(&graph[7],
348 VectOfExt(7, 1),
349 VectOfExt(tmp + 2, 1),
350 "",
351 InstallOperation::MOVE);
352 // Corresponding edges:
353 graph[3].out_edges[6] = EdgeWithReadDep(VectOfExt(2, 2));
354 graph[4].out_edges[7] = EdgeWithReadDep(VectOfExt(7, 1));
355 graph[5].out_edges[6] = EdgeWithWriteDep(VectOfExt(tmp, 2));
356 graph[5].out_edges[7] = EdgeWithWriteDep(VectOfExt(tmp + 2, 1));
357 graph[5].out_edges[3] = EdgeWithReadDep(VectOfExt(4, 2));
358 graph[5].out_edges[4] = EdgeWithReadDep(VectOfExt(6, 1));
359 // Store the cuts:
360 cuts[1].old_dst = 5;
361 cuts[1].old_src = 3;
362 cuts[1].new_vertex = 6;
363 cuts[1].tmp_extents = VectOfExt(tmp, 2);
364 cuts[2].old_dst = 5;
365 cuts[2].old_src = 4;
366 cuts[2].new_vertex = 7;
367 cuts[2].tmp_extents = VectOfExt(tmp + 2, 1);
368
369 // Supplier of temp block:
370 GenVertex(&graph[8], empt, VectOfExt(8, 1), "", InstallOperation::REPLACE);
371
372 // Specify the final order:
373 vector<Vertex::Index> op_indexes;
374 op_indexes.push_back(2);
375 op_indexes.push_back(0);
376 op_indexes.push_back(1);
377 op_indexes.push_back(6);
378 op_indexes.push_back(3);
379 op_indexes.push_back(7);
380 op_indexes.push_back(4);
381 op_indexes.push_back(5);
382 op_indexes.push_back(8);
383
384 vector<vector<Vertex::Index>::size_type> reverse_op_indexes;
385 InplaceGenerator::GenerateReverseTopoOrderMap(op_indexes,
386 &reverse_op_indexes);
387
388 CreateBlobFile();
389 EXPECT_TRUE(InplaceGenerator::AssignTempBlocks(&graph,
390 "/dev/zero",
391 blob_file_.get(),
392 &op_indexes,
393 &reverse_op_indexes,
394 cuts));
395 EXPECT_FALSE(graph[6].valid);
396 EXPECT_FALSE(graph[7].valid);
397 EXPECT_EQ(1, graph[1].aop.op.src_extents_size());
398 EXPECT_EQ(2U, graph[1].aop.op.src_extents(0).start_block());
399 EXPECT_EQ(1U, graph[1].aop.op.src_extents(0).num_blocks());
400 EXPECT_EQ(InstallOperation::REPLACE_BZ, graph[5].aop.op.type());
401 }
402
TEST_F(InplaceGeneratorTest,MoveAndSortFullOpsToBackTest)403 TEST_F(InplaceGeneratorTest, MoveAndSortFullOpsToBackTest) {
404 Graph graph(4);
405 graph[0].aop.name = "A";
406 graph[0].aop.op.set_type(InstallOperation::REPLACE);
407 graph[1].aop.name = "B";
408 graph[1].aop.op.set_type(InstallOperation::BSDIFF);
409 graph[2].aop.name = "C";
410 graph[2].aop.op.set_type(InstallOperation::REPLACE_BZ);
411 graph[3].aop.name = "D";
412 graph[3].aop.op.set_type(InstallOperation::MOVE);
413
414 vector<Vertex::Index> vect(graph.size());
415
416 for (vector<Vertex::Index>::size_type i = 0; i < vect.size(); ++i) {
417 vect[i] = i;
418 }
419 InplaceGenerator::MoveAndSortFullOpsToBack(&graph, &vect);
420 EXPECT_EQ(vect.size(), graph.size());
421 EXPECT_EQ(graph[vect[0]].aop.name, "B");
422 EXPECT_EQ(graph[vect[1]].aop.name, "D");
423 EXPECT_EQ(graph[vect[2]].aop.name, "A");
424 EXPECT_EQ(graph[vect[3]].aop.name, "C");
425 }
426
TEST_F(InplaceGeneratorTest,AssignTempBlocksTest)427 TEST_F(InplaceGeneratorTest, AssignTempBlocksTest) {
428 Graph graph(9);
429 const vector<Extent> empt; // empty
430 const string kFilename = "/foo";
431
432 // Some scratch space:
433 GenVertex(&graph[0], empt, VectOfExt(200, 1), "", InstallOperation::REPLACE);
434 GenVertex(&graph[1], empt, VectOfExt(210, 10), "", InstallOperation::REPLACE);
435 GenVertex(&graph[2], empt, VectOfExt(220, 1), "", InstallOperation::REPLACE);
436
437 // A cycle that requires 10 blocks to break:
438 GenVertex(&graph[3],
439 VectOfExt(10, 11),
440 VectOfExt(0, 9),
441 "",
442 InstallOperation::BSDIFF);
443 graph[3].out_edges[4] = EdgeWithReadDep(VectOfExt(0, 9));
444 GenVertex(&graph[4],
445 VectOfExt(0, 9),
446 VectOfExt(10, 11),
447 "",
448 InstallOperation::BSDIFF);
449 graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
450
451 // A cycle that requires 9 blocks to break:
452 GenVertex(&graph[5],
453 VectOfExt(40, 11),
454 VectOfExt(30, 10),
455 "",
456 InstallOperation::BSDIFF);
457 graph[5].out_edges[6] = EdgeWithReadDep(VectOfExt(30, 10));
458 GenVertex(&graph[6],
459 VectOfExt(30, 10),
460 VectOfExt(40, 11),
461 "",
462 InstallOperation::BSDIFF);
463 graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
464
465 // A cycle that requires 40 blocks to break (which is too many):
466 GenVertex(&graph[7],
467 VectOfExt(120, 50),
468 VectOfExt(60, 40),
469 "",
470 InstallOperation::BSDIFF);
471 graph[7].out_edges[8] = EdgeWithReadDep(VectOfExt(60, 40));
472 GenVertex(&graph[8],
473 VectOfExt(60, 40),
474 VectOfExt(120, 50),
475 kFilename,
476 InstallOperation::BSDIFF);
477 graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
478
479 graph_utils::DumpGraph(graph);
480
481 vector<Vertex::Index> final_order;
482
483 CreateBlobFile();
484 EXPECT_TRUE(InplaceGenerator::ConvertGraphToDag(&graph,
485 "/dev/zero",
486 blob_file_.get(),
487 &final_order,
488 Vertex::kInvalidIndex));
489
490 Graph expected_graph(12);
491 GenVertex(&expected_graph[0],
492 empt,
493 VectOfExt(200, 1),
494 "",
495 InstallOperation::REPLACE);
496 GenVertex(&expected_graph[1],
497 empt,
498 VectOfExt(210, 10),
499 "",
500 InstallOperation::REPLACE);
501 GenVertex(&expected_graph[2],
502 empt,
503 VectOfExt(220, 1),
504 "",
505 InstallOperation::REPLACE);
506 GenVertex(&expected_graph[3],
507 VectOfExt(10, 11),
508 VectOfExt(0, 9),
509 "",
510 InstallOperation::BSDIFF);
511 expected_graph[3].out_edges[9] = EdgeWithReadDep(VectOfExt(0, 9));
512 GenVertex(&expected_graph[4],
513 VectOfExt(60, 9),
514 VectOfExt(10, 11),
515 "",
516 InstallOperation::BSDIFF);
517 expected_graph[4].out_edges[3] = EdgeWithReadDep(VectOfExt(10, 11));
518 expected_graph[4].out_edges[9] = EdgeWithWriteDep(VectOfExt(60, 9));
519 GenVertex(&expected_graph[5],
520 VectOfExt(40, 11),
521 VectOfExt(30, 10),
522 "",
523 InstallOperation::BSDIFF);
524 expected_graph[5].out_edges[10] = EdgeWithReadDep(VectOfExt(30, 10));
525
526 GenVertex(&expected_graph[6],
527 VectOfExt(60, 10),
528 VectOfExt(40, 11),
529 "",
530 InstallOperation::BSDIFF);
531 expected_graph[6].out_edges[5] = EdgeWithReadDep(VectOfExt(40, 11));
532 expected_graph[6].out_edges[10] = EdgeWithWriteDep(VectOfExt(60, 10));
533
534 GenVertex(&expected_graph[7],
535 VectOfExt(120, 50),
536 VectOfExt(60, 40),
537 "",
538 InstallOperation::BSDIFF);
539 expected_graph[7].out_edges[6] = EdgeWithReadDep(VectOfExt(60, 10));
540
541 GenVertex(&expected_graph[8],
542 empt,
543 VectOfExt(0, 50),
544 "/foo",
545 InstallOperation::REPLACE_BZ);
546 expected_graph[8].out_edges[7] = EdgeWithReadDep(VectOfExt(120, 50));
547
548 GenVertex(&expected_graph[9],
549 VectOfExt(0, 9),
550 VectOfExt(60, 9),
551 "",
552 InstallOperation::MOVE);
553
554 GenVertex(&expected_graph[10],
555 VectOfExt(30, 10),
556 VectOfExt(60, 10),
557 "",
558 InstallOperation::MOVE);
559 expected_graph[10].out_edges[4] = EdgeWithReadDep(VectOfExt(60, 9));
560
561 EXPECT_EQ(12U, graph.size());
562 EXPECT_FALSE(graph.back().valid);
563 for (Graph::size_type i = 0; i < graph.size() - 1; i++) {
564 EXPECT_TRUE(graph[i].out_edges == expected_graph[i].out_edges);
565 if (i == 8) {
566 // special case
567 } else {
568 // EXPECT_TRUE(graph[i] == expected_graph[i]) << "i = " << i;
569 }
570 }
571 }
572
TEST_F(InplaceGeneratorTest,CreateScratchNodeTest)573 TEST_F(InplaceGeneratorTest, CreateScratchNodeTest) {
574 Vertex vertex;
575 InplaceGenerator::CreateScratchNode(12, 34, &vertex);
576 EXPECT_EQ(InstallOperation::REPLACE_BZ, vertex.aop.op.type());
577 EXPECT_EQ(0U, vertex.aop.op.data_offset());
578 EXPECT_EQ(0U, vertex.aop.op.data_length());
579 EXPECT_EQ(1, vertex.aop.op.dst_extents_size());
580 EXPECT_EQ(12U, vertex.aop.op.dst_extents(0).start_block());
581 EXPECT_EQ(34U, vertex.aop.op.dst_extents(0).num_blocks());
582 }
583
TEST_F(InplaceGeneratorTest,ApplyMapTest)584 TEST_F(InplaceGeneratorTest, ApplyMapTest) {
585 vector<uint64_t> collection = {1, 2, 3, 4, 6};
586 vector<uint64_t> expected_values = {1, 2, 5, 4, 8};
587 map<uint64_t, uint64_t> value_map;
588 value_map[3] = 5;
589 value_map[6] = 8;
590 value_map[5] = 10;
591
592 InplaceGenerator::ApplyMap(&collection, value_map);
593 EXPECT_EQ(expected_values, collection);
594 }
595
596 // We can't produce MOVE operations with a source or destination in the block 0.
597 // This test checks that the cycle breaker procedure doesn't produce such
598 // operations.
TEST_F(InplaceGeneratorTest,ResolveReadAfterWriteDependenciesAvoidMoveToZero)599 TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesAvoidMoveToZero) {
600 size_t block_size = 4096;
601 size_t num_blocks = 4;
602 vector<AnnotatedOperation> aops;
603
604 // Create a REPLACE_BZ for block 0, and a circular dependency among all other
605 // blocks. This situation would prefer to issue a MOVE to scratch space and
606 // the only available block is 0.
607 aops.emplace_back();
608 aops.back().name = base::StringPrintf("<bz-block-0>");
609 aops.back().op.set_type(InstallOperation::REPLACE_BZ);
610 StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
611
612 for (size_t i = 1; i < num_blocks; i++) {
613 AnnotatedOperation aop;
614 aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
615 aop.op.set_type(InstallOperation::BSDIFF);
616 StoreExtents({ExtentForRange(1 + i % (num_blocks - 1), 1)},
617 aop.op.mutable_src_extents());
618 StoreExtents({ExtentForRange(i, 1)}, aop.op.mutable_dst_extents());
619 aops.push_back(aop);
620 }
621
622 PartitionConfig part("part");
623 part.path = "/dev/zero";
624 part.size = num_blocks * block_size;
625
626 CreateBlobFile();
627
628 // We ran two tests here. The first one without enough blocks for the scratch
629 // space, forcing it to create a new full operation and the second case with
630 // one extra block in the partition that can be used for the move operation.
631 for (const auto part_blocks : vector<uint64_t>{num_blocks, num_blocks + 1}) {
632 SCOPED_TRACE(
633 base::StringPrintf("Using partition_blocks=%" PRIu64, part_blocks));
634 vector<AnnotatedOperation> result_aops = aops;
635 EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
636 part,
637 part,
638 part_blocks * block_size,
639 block_size,
640 blob_file_.get(),
641 &result_aops));
642
643 size_t full_ops = 0;
644 for (const auto& aop : result_aops) {
645 if (diff_utils::IsAReplaceOperation(aop.op.type()))
646 full_ops++;
647
648 if (aop.op.type() != InstallOperation::MOVE)
649 continue;
650 for (const Extent& extent : aop.op.src_extents()) {
651 EXPECT_NE(0U, extent.start_block())
652 << "On src extents for aop: " << aop;
653 }
654 for (const Extent& extent : aop.op.dst_extents()) {
655 EXPECT_NE(0U, extent.start_block())
656 << "On dst extents for aop: " << aop;
657 }
658 }
659
660 // If there's extra space in the partition, it should not use a new full
661 // operation for it.
662 EXPECT_EQ(part_blocks == num_blocks ? 2U : 1U, full_ops);
663
664 DumpAopsOnFailure(result_aops);
665 }
666 }
667
668 // Test that we can shrink a filesystem and break cycles.
TEST_F(InplaceGeneratorTest,ResolveReadAfterWriteDependenciesShrinkData)669 TEST_F(InplaceGeneratorTest, ResolveReadAfterWriteDependenciesShrinkData) {
670 size_t block_size = 4096;
671 size_t old_blocks = 10;
672 size_t new_blocks = 8;
673 vector<AnnotatedOperation> aops;
674
675 // Create a loop using the blocks 1-6 and one other operation writing to the
676 // block 7 from outside the new partition. The loop in the blocks 1-6 uses
677 // two-block operations, so it needs two blocks of scratch space. It can't use
678 // the block 0 as scratch space (see previous test) and it can't use the
679 // blocks 7 or 8 due the last move operation.
680
681 aops.emplace_back();
682 aops.back().name = base::StringPrintf("<bz-block-0>");
683 aops.back().op.set_type(InstallOperation::REPLACE_BZ);
684 StoreExtents({ExtentForRange(0, 1)}, aops.back().op.mutable_dst_extents());
685
686 const size_t num_ops = 3;
687 for (size_t i = 0; i < num_ops; i++) {
688 AnnotatedOperation aop;
689 aop.name = base::StringPrintf("<op-%" PRIuS ">", i);
690 aop.op.set_type(InstallOperation::BSDIFF);
691 StoreExtents({ExtentForRange(1 + 2 * i, 2)}, aop.op.mutable_src_extents());
692 StoreExtents({ExtentForRange(1 + 2 * ((i + 1) % num_ops), 2)},
693 aop.op.mutable_dst_extents());
694 aops.push_back(aop);
695 }
696
697 {
698 AnnotatedOperation aop;
699 aop.name = "<op-shrink>";
700 aop.op.set_type(InstallOperation::BSDIFF);
701 StoreExtents({ExtentForRange(8, 1)}, aop.op.mutable_src_extents());
702 StoreExtents({ExtentForRange(7, 1)}, aop.op.mutable_dst_extents());
703 aops.push_back(aop);
704 }
705
706 PartitionConfig old_part("part");
707 old_part.path = "/dev/zero";
708 old_part.size = old_blocks * block_size;
709
710 PartitionConfig new_part("part");
711 new_part.path = "/dev/zero";
712 new_part.size = new_blocks * block_size;
713
714 CreateBlobFile();
715
716 EXPECT_TRUE(InplaceGenerator::ResolveReadAfterWriteDependencies(
717 old_part,
718 new_part,
719 (old_blocks + 2) * block_size, // enough scratch space.
720 block_size,
721 blob_file_.get(),
722 &aops));
723
724 size_t full_ops = 0;
725 for (const auto& aop : aops) {
726 if (diff_utils::IsAReplaceOperation(aop.op.type()))
727 full_ops++;
728 }
729 // There should be only one REPLACE* operation, the one we added for block 0.
730 EXPECT_EQ(1U, full_ops);
731
732 // There should be only one MOVE operation, the one used to break the loop
733 // which should write to scratch space past the block 7 (the last block of the
734 // new partition) which is being written later.
735 size_t move_ops = 0;
736 for (const auto& aop : aops) {
737 if (aop.op.type() == InstallOperation::MOVE) {
738 move_ops++;
739 for (const Extent& extent : aop.op.dst_extents()) {
740 EXPECT_LE(7U, extent.start_block()) << "On dst extents for aop: "
741 << aop;
742 }
743 }
744 }
745 EXPECT_EQ(1U, move_ops);
746
747 DumpAopsOnFailure(aops);
748 }
749
750 } // namespace chromeos_update_engine
751