OLD | NEW |
---|---|
1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. | 1 // Copyright (c) 2010 The Chromium OS Authors. All rights reserved. |
2 // Use of this source code is governed by a BSD-style license that can be | 2 // Use of this source code is governed by a BSD-style license that can be |
3 // found in the LICENSE file. | 3 // found in the LICENSE file. |
4 | 4 |
5 #include "update_engine/delta_diff_generator.h" | 5 #include "update_engine/delta_diff_generator.h" |
6 | 6 |
7 #include <errno.h> | 7 #include <errno.h> |
8 #include <fcntl.h> | 8 #include <fcntl.h> |
9 #include <inttypes.h> | 9 #include <inttypes.h> |
10 #include <sys/stat.h> | 10 #include <sys/stat.h> |
(...skipping 36 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
47 using std::vector; | 47 using std::vector; |
48 | 48 |
49 namespace chromeos_update_engine { | 49 namespace chromeos_update_engine { |
50 | 50 |
51 typedef DeltaDiffGenerator::Block Block; | 51 typedef DeltaDiffGenerator::Block Block; |
52 typedef map<const DeltaArchiveManifest_InstallOperation*, | 52 typedef map<const DeltaArchiveManifest_InstallOperation*, |
53 const string*> OperationNameMap; | 53 const string*> OperationNameMap; |
54 | 54 |
55 namespace { | 55 namespace { |
56 const size_t kBlockSize = 4096; // bytes | 56 const size_t kBlockSize = 4096; // bytes |
57 const size_t kRootFSPartitionSize = 1 * 1024 * 1024 * 1024; // bytes | 57 const size_t kRootFSPartitionSize = 1 * 1024 * 1024 * 1024; // bytes |
petkov
2010/12/02 05:04:06
This is an obsolete dupe now? Remove.
adlr
2010/12/02 19:21:41
Oops missed this. I decided to use this and not ma
| |
58 const uint64_t kVersionNumber = 1; | 58 const uint64_t kVersionNumber = 1; |
59 const uint64_t kFullUpdateChunkSize = 1024 * 1024; // bytes | 59 const uint64_t kFullUpdateChunkSize = 1024 * 1024; // bytes |
60 const uint64_t kRootfsPartitionSize = 1024 * 1024 * 1024; // bytes | |
petkov
2010/12/02 05:04:06
Add a TODO to increase this to 2GiB when we stop c
adlr
2010/12/02 19:21:41
Done.
| |
60 | 61 |
61 static const char* kInstallOperationTypes[] = { | 62 static const char* kInstallOperationTypes[] = { |
62 "REPLACE", | 63 "REPLACE", |
63 "REPLACE_BZ", | 64 "REPLACE_BZ", |
64 "MOVE", | 65 "MOVE", |
65 "BSDIFF" | 66 "BSDIFF" |
66 }; | 67 }; |
67 | 68 |
68 // Stores all Extents for a file into 'out'. Returns true on success. | 69 // Stores all Extents for a file into 'out'. Returns true on success. |
69 bool GatherExtents(const string& path, | 70 bool GatherExtents(const string& path, |
(...skipping 950 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1020 edge_e = (*graph)[test_node].out_edges.end(); | 1021 edge_e = (*graph)[test_node].out_edges.end(); |
1021 edge_i != edge_e; ++edge_i) { | 1022 edge_i != edge_e; ++edge_i) { |
1022 ranges.SubtractExtents(edge_i->second.extents); | 1023 ranges.SubtractExtents(edge_i->second.extents); |
1023 } | 1024 } |
1024 if (ranges.blocks() == 0) | 1025 if (ranges.blocks() == 0) |
1025 continue; | 1026 continue; |
1026 | 1027 |
1027 if (ranges.blocks() + scratch_blocks_found > blocks_needed) { | 1028 if (ranges.blocks() + scratch_blocks_found > blocks_needed) { |
1028 // trim down ranges | 1029 // trim down ranges |
1029 vector<Extent> new_ranges = ranges.GetExtentsForBlockCount( | 1030 vector<Extent> new_ranges = ranges.GetExtentsForBlockCount( |
1030 blocks_needed - scratch_blocks_found); | 1031 blocks_needed - scratch_blocks_found); |
1031 ranges = ExtentRanges(); | 1032 ranges = ExtentRanges(); |
1032 ranges.AddExtents(new_ranges); | 1033 ranges.AddExtents(new_ranges); |
1033 } | 1034 } |
1034 scratch_ranges.AddRanges(ranges); | 1035 scratch_ranges.AddRanges(ranges); |
1035 block_suppliers.push_back(make_pair(test_node, ranges)); | 1036 block_suppliers.push_back(make_pair(test_node, ranges)); |
1036 scratch_blocks_found += ranges.blocks(); | 1037 scratch_blocks_found += ranges.blocks(); |
1037 if (scratch_ranges.blocks() >= blocks_needed) | 1038 if (scratch_ranges.blocks() >= blocks_needed) |
1038 break; | 1039 break; |
1039 } | 1040 } |
1040 if (scratch_ranges.blocks() < blocks_needed) { | 1041 if (scratch_ranges.blocks() < blocks_needed) { |
(...skipping 208 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1249 (*graph)[cut.old_dst].out_edges.end()); | 1250 (*graph)[cut.old_dst].out_edges.end()); |
1250 (*graph)[cut.new_vertex].valid = false; | 1251 (*graph)[cut.new_vertex].valid = false; |
1251 LOG(INFO) << "marked node invalid: " << cut.new_vertex; | 1252 LOG(INFO) << "marked node invalid: " << cut.new_vertex; |
1252 return true; | 1253 return true; |
1253 } | 1254 } |
1254 | 1255 |
1255 bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph, | 1256 bool DeltaDiffGenerator::ConvertGraphToDag(Graph* graph, |
1256 const string& new_root, | 1257 const string& new_root, |
1257 int fd, | 1258 int fd, |
1258 off_t* data_file_size, | 1259 off_t* data_file_size, |
1259 vector<Vertex::Index>* final_order) { | 1260 vector<Vertex::Index>* final_order, |
1261 Vertex::Index scratch_vertex) { | |
1260 CycleBreaker cycle_breaker; | 1262 CycleBreaker cycle_breaker; |
1261 LOG(INFO) << "Finding cycles..."; | 1263 LOG(INFO) << "Finding cycles..."; |
1262 set<Edge> cut_edges; | 1264 set<Edge> cut_edges; |
1263 cycle_breaker.BreakCycles(*graph, &cut_edges); | 1265 cycle_breaker.BreakCycles(*graph, &cut_edges); |
1264 LOG(INFO) << "done finding cycles"; | 1266 LOG(INFO) << "done finding cycles"; |
1265 CheckGraph(*graph); | 1267 CheckGraph(*graph); |
1266 | 1268 |
1267 // Calculate number of scratch blocks needed | 1269 // Calculate number of scratch blocks needed |
1268 | 1270 |
1269 LOG(INFO) << "Cutting cycles..."; | 1271 LOG(INFO) << "Cutting cycles..."; |
(...skipping 20 matching lines...) Expand all Loading... | |
1290 if (!cuts.empty()) | 1292 if (!cuts.empty()) |
1291 TEST_AND_RETURN_FALSE(AssignTempBlocks(graph, | 1293 TEST_AND_RETURN_FALSE(AssignTempBlocks(graph, |
1292 new_root, | 1294 new_root, |
1293 fd, | 1295 fd, |
1294 data_file_size, | 1296 data_file_size, |
1295 final_order, | 1297 final_order, |
1296 &inverse_final_order, | 1298 &inverse_final_order, |
1297 cuts)); | 1299 cuts)); |
1298 LOG(INFO) << "Making sure all temp blocks have been allocated"; | 1300 LOG(INFO) << "Making sure all temp blocks have been allocated"; |
1299 | 1301 |
1302 // Remove the scratch node, if any | |
1303 if (scratch_vertex != Vertex::kInvalidIndex) { | |
1304 final_order->erase(final_order->begin() + | |
1305 inverse_final_order[scratch_vertex]); | |
1306 (*graph)[scratch_vertex].valid = false; | |
1307 GenerateReverseTopoOrderMap(*final_order, &inverse_final_order); | |
1308 } | |
1309 | |
1300 graph_utils::DumpGraph(*graph); | 1310 graph_utils::DumpGraph(*graph); |
1301 CHECK(NoTempBlocksRemain(*graph)); | 1311 CHECK(NoTempBlocksRemain(*graph)); |
1302 LOG(INFO) << "done making sure all temp blocks are allocated"; | 1312 LOG(INFO) << "done making sure all temp blocks are allocated"; |
1303 return true; | 1313 return true; |
1304 } | 1314 } |
1305 | 1315 |
1316 void DeltaDiffGenerator::CreateScratchNode(uint64_t start_block, | |
1317 uint64_t num_blocks, | |
1318 Vertex* vertex) { | |
1319 vertex->file_name = "<scratch>"; | |
1320 vertex->op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); | |
1321 vertex->op.set_data_offset(0); | |
1322 vertex->op.set_data_length(0); | |
1323 Extent* extent = vertex->op.add_dst_extents(); | |
1324 extent->set_start_block(start_block); | |
1325 extent->set_num_blocks(num_blocks); | |
1326 } | |
1327 | |
1306 bool DeltaDiffGenerator::GenerateDeltaUpdateFile( | 1328 bool DeltaDiffGenerator::GenerateDeltaUpdateFile( |
1307 const string& old_root, | 1329 const string& old_root, |
1308 const string& old_image, | 1330 const string& old_image, |
1309 const string& new_root, | 1331 const string& new_root, |
1310 const string& new_image, | 1332 const string& new_image, |
1311 const string& old_kernel_part, | 1333 const string& old_kernel_part, |
1312 const string& new_kernel_part, | 1334 const string& new_kernel_part, |
1313 const string& output_path, | 1335 const string& output_path, |
1314 const string& private_key_path) { | 1336 const string& private_key_path) { |
1315 int old_image_block_count = 0, old_image_block_size = 0; | 1337 int old_image_block_count = 0, old_image_block_size = 0; |
(...skipping 24 matching lines...) Expand all Loading... | |
1340 | 1362 |
1341 const string kTempFileTemplate("/tmp/CrAU_temp_data.XXXXXX"); | 1363 const string kTempFileTemplate("/tmp/CrAU_temp_data.XXXXXX"); |
1342 string temp_file_path; | 1364 string temp_file_path; |
1343 off_t data_file_size = 0; | 1365 off_t data_file_size = 0; |
1344 | 1366 |
1345 LOG(INFO) << "Reading files..."; | 1367 LOG(INFO) << "Reading files..."; |
1346 | 1368 |
1347 vector<DeltaArchiveManifest_InstallOperation> kernel_ops; | 1369 vector<DeltaArchiveManifest_InstallOperation> kernel_ops; |
1348 | 1370 |
1349 vector<Vertex::Index> final_order; | 1371 vector<Vertex::Index> final_order; |
1372 Vertex::Index scratch_vertex = Vertex::kInvalidIndex; | |
1350 { | 1373 { |
1351 int fd; | 1374 int fd; |
1352 TEST_AND_RETURN_FALSE( | 1375 TEST_AND_RETURN_FALSE( |
1353 utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &fd)); | 1376 utils::MakeTempFile(kTempFileTemplate, &temp_file_path, &fd)); |
1354 TEST_AND_RETURN_FALSE(fd >= 0); | 1377 TEST_AND_RETURN_FALSE(fd >= 0); |
1355 ScopedFdCloser fd_closer(&fd); | 1378 ScopedFdCloser fd_closer(&fd); |
1356 if (!old_image.empty()) { | 1379 if (!old_image.empty()) { |
1357 // Delta update | 1380 // Delta update |
1358 | 1381 |
1359 TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph, | 1382 TEST_AND_RETURN_FALSE(DeltaReadFiles(&graph, |
1360 &blocks, | 1383 &blocks, |
1361 old_root, | 1384 old_root, |
1362 new_root, | 1385 new_root, |
1363 fd, | 1386 fd, |
1364 &data_file_size)); | 1387 &data_file_size)); |
1365 LOG(INFO) << "done reading normal files"; | 1388 LOG(INFO) << "done reading normal files"; |
1366 CheckGraph(graph); | 1389 CheckGraph(graph); |
1367 | 1390 |
1368 graph.resize(graph.size() + 1); | 1391 graph.resize(graph.size() + 1); |
1369 TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks, | 1392 TEST_AND_RETURN_FALSE(ReadUnwrittenBlocks(blocks, |
1370 fd, | 1393 fd, |
1371 &data_file_size, | 1394 &data_file_size, |
1372 new_image, | 1395 new_image, |
1373 &graph.back())); | 1396 &graph.back())); |
1374 | 1397 |
1398 // Final scratch block (if there's space) | |
1399 if (blocks.size() < (kRootfsPartitionSize / kBlockSize)) { | |
1400 scratch_vertex = graph.size(); | |
1401 graph.resize(graph.size() + 1); | |
1402 CreateScratchNode(blocks.size(), | |
1403 (kRootfsPartitionSize / kBlockSize) - blocks.size(), | |
1404 &graph.back()); | |
1405 } | |
1406 | |
1375 // Read kernel partition | 1407 // Read kernel partition |
1376 TEST_AND_RETURN_FALSE(DeltaCompressKernelPartition(old_kernel_part, | 1408 TEST_AND_RETURN_FALSE(DeltaCompressKernelPartition(old_kernel_part, |
1377 new_kernel_part, | 1409 new_kernel_part, |
1378 &kernel_ops, | 1410 &kernel_ops, |
1379 fd, | 1411 fd, |
1380 &data_file_size)); | 1412 &data_file_size)); |
1381 | 1413 |
1382 LOG(INFO) << "done reading kernel"; | 1414 LOG(INFO) << "done reading kernel"; |
1383 CheckGraph(graph); | 1415 CheckGraph(graph); |
1384 | 1416 |
1385 LOG(INFO) << "Creating edges..."; | 1417 LOG(INFO) << "Creating edges..."; |
1386 CreateEdges(&graph, blocks); | 1418 CreateEdges(&graph, blocks); |
1387 LOG(INFO) << "Done creating edges"; | 1419 LOG(INFO) << "Done creating edges"; |
1388 CheckGraph(graph); | 1420 CheckGraph(graph); |
1389 | 1421 |
1390 TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph, | 1422 TEST_AND_RETURN_FALSE(ConvertGraphToDag(&graph, |
1391 new_root, | 1423 new_root, |
1392 fd, | 1424 fd, |
1393 &data_file_size, | 1425 &data_file_size, |
1394 &final_order)); | 1426 &final_order, |
1427 scratch_vertex)); | |
1395 } else { | 1428 } else { |
1396 // Full update | 1429 // Full update |
1397 off_t new_image_size = | 1430 off_t new_image_size = |
1398 static_cast<off_t>(new_image_block_count) * new_image_block_size; | 1431 static_cast<off_t>(new_image_block_count) * new_image_block_size; |
1399 TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph, | 1432 TEST_AND_RETURN_FALSE(FullUpdateGenerator::Run(&graph, |
1400 new_kernel_part, | 1433 new_kernel_part, |
1401 new_image, | 1434 new_image, |
1402 new_image_size, | 1435 new_image_size, |
1403 fd, | 1436 fd, |
1404 &data_file_size, | 1437 &data_file_size, |
(...skipping 143 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... | |
1548 | 1581 |
1549 LOG(INFO) << "All done. Successfully created delta file."; | 1582 LOG(INFO) << "All done. Successfully created delta file."; |
1550 return true; | 1583 return true; |
1551 } | 1584 } |
1552 | 1585 |
1553 const char* const kBsdiffPath = "bsdiff"; | 1586 const char* const kBsdiffPath = "bsdiff"; |
1554 const char* const kBspatchPath = "bspatch"; | 1587 const char* const kBspatchPath = "bspatch"; |
1555 const char* const kDeltaMagic = "CrAU"; | 1588 const char* const kDeltaMagic = "CrAU"; |
1556 | 1589 |
1557 }; // namespace chromeos_update_engine | 1590 }; // namespace chromeos_update_engine |
OLD | NEW |