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