OLD | NEW |
(Empty) | |
| 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 |
| 3 // found in the LICENSE file. |
| 4 |
| 5 #include <algorithm> |
| 6 #include <string> |
| 7 #include <vector> |
| 8 |
| 9 #include <base/string_util.h> |
| 10 #include <et/com_err.h> |
| 11 #include <ext2fs/ext2_io.h> |
| 12 #include <ext2fs/ext2fs.h> |
| 13 |
| 14 #include "update_engine/bzip.h" |
| 15 #include "update_engine/delta_diff_generator.h" |
| 16 #include "update_engine/extent_ranges.h" |
| 17 #include "update_engine/graph_utils.h" |
| 18 #include "update_engine/metadata.h" |
| 19 #include "update_engine/utils.h" |
| 20 |
| 21 using std::min; |
| 22 using std::string; |
| 23 using std::vector; |
| 24 |
| 25 namespace chromeos_update_engine { |
| 26 |
| 27 namespace { |
| 28 const size_t kBlockSize = 4096; |
| 29 |
| 30 typedef DeltaDiffGenerator::Block Block; |
| 31 |
| 32 // Read data from the specified extents. |
| 33 bool ReadExtentsData(const ext2_filsys fs, |
| 34 const vector<Extent>& extents, |
| 35 vector<char>* data) { |
| 36 // Resize the data buffer to hold all data in the extents |
| 37 size_t num_data_blocks = 0; |
| 38 for (vector<Extent>::const_iterator it = extents.begin(); |
| 39 it != extents.end(); it++) { |
| 40 num_data_blocks += it->num_blocks(); |
| 41 } |
| 42 |
| 43 data->resize(num_data_blocks * kBlockSize); |
| 44 |
| 45 // Read in the data blocks |
| 46 const size_t kMaxReadBlocks = 256; |
| 47 vector<Block>::size_type blocks_copied_count = 0; |
| 48 for (vector<Extent>::const_iterator it = extents.begin(); |
| 49 it != extents.end(); it++) { |
| 50 vector<Block>::size_type blocks_read = 0; |
| 51 while (blocks_read < it->num_blocks()) { |
| 52 const int copy_block_cnt = |
| 53 min(kMaxReadBlocks, |
| 54 static_cast<size_t>( |
| 55 it->num_blocks() - blocks_read)); |
| 56 TEST_AND_RETURN_FALSE_ERRCODE( |
| 57 io_channel_read_blk(fs->io, |
| 58 it->start_block() + blocks_read, |
| 59 copy_block_cnt, |
| 60 &(*data)[blocks_copied_count * kBlockSize])); |
| 61 blocks_read += copy_block_cnt; |
| 62 blocks_copied_count += copy_block_cnt; |
| 63 } |
| 64 } |
| 65 |
| 66 return true; |
| 67 } |
| 68 |
| 69 // Compute the bsdiff between two metadata blobs. |
| 70 bool ComputeMetadataBsdiff(const vector<char>& old_metadata, |
| 71 const vector<char>& new_metadata, |
| 72 vector<char>* bsdiff_delta) { |
| 73 const string kTempFileTemplate("/tmp/CrAU_temp_data.XXXXXX"); |
| 74 |
| 75 // Write the metadata buffers to temporary files |
| 76 int old_fd; |
| 77 string temp_old_file_path; |
| 78 TEST_AND_RETURN_FALSE( |
| 79 utils::MakeTempFile(kTempFileTemplate, &temp_old_file_path, &old_fd)); |
| 80 TEST_AND_RETURN_FALSE(old_fd >= 0); |
| 81 ScopedPathUnlinker temp_old_file_path_unlinker(temp_old_file_path); |
| 82 ScopedFdCloser old_fd_closer(&old_fd); |
| 83 TEST_AND_RETURN_FALSE(utils::WriteAll(old_fd, |
| 84 &old_metadata[0], |
| 85 old_metadata.size())); |
| 86 |
| 87 int new_fd; |
| 88 string temp_new_file_path; |
| 89 TEST_AND_RETURN_FALSE( |
| 90 utils::MakeTempFile(kTempFileTemplate, &temp_new_file_path, &new_fd)); |
| 91 TEST_AND_RETURN_FALSE(new_fd >= 0); |
| 92 ScopedPathUnlinker temp_new_file_path_unlinker(temp_new_file_path); |
| 93 ScopedFdCloser new_fd_closer(&new_fd); |
| 94 TEST_AND_RETURN_FALSE(utils::WriteAll(new_fd, |
| 95 &new_metadata[0], |
| 96 new_metadata.size())); |
| 97 |
| 98 // Perform bsdiff on these files |
| 99 TEST_AND_RETURN_FALSE( |
| 100 DeltaDiffGenerator::BsdiffFiles(temp_old_file_path, |
| 101 temp_new_file_path, |
| 102 bsdiff_delta)); |
| 103 |
| 104 return true; |
| 105 } |
| 106 |
| 107 // Add the specified metadata extents to the graph and blocks vector. |
| 108 bool AddMetadataExtents(Graph* graph, |
| 109 vector<Block>* blocks, |
| 110 const ext2_filsys fs_old, |
| 111 const ext2_filsys fs_new, |
| 112 const string& metadata_name, |
| 113 const vector<Extent>& extents, |
| 114 int data_fd, |
| 115 off_t* data_file_size) { |
| 116 vector<char> data; // Data blob that will be written to delta file. |
| 117 DeltaArchiveManifest_InstallOperation op; |
| 118 |
| 119 { |
| 120 // Read in the metadata blocks from the old and new image. |
| 121 vector<char> old_data; |
| 122 TEST_AND_RETURN_FALSE(ReadExtentsData(fs_old, extents, &old_data)); |
| 123 |
| 124 vector<char> new_data; |
| 125 TEST_AND_RETURN_FALSE(ReadExtentsData(fs_new, extents, &new_data)); |
| 126 |
| 127 // Determine the best way to compress this. |
| 128 vector<char> new_data_bz; |
| 129 TEST_AND_RETURN_FALSE(BzipCompress(new_data, &new_data_bz)); |
| 130 CHECK(!new_data_bz.empty()); |
| 131 |
| 132 size_t current_best_size = 0; |
| 133 if (new_data.size() <= new_data_bz.size()) { |
| 134 op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE); |
| 135 current_best_size = new_data.size(); |
| 136 data = new_data; |
| 137 } else { |
| 138 op.set_type(DeltaArchiveManifest_InstallOperation_Type_REPLACE_BZ); |
| 139 current_best_size = new_data_bz.size(); |
| 140 data = new_data_bz; |
| 141 } |
| 142 |
| 143 if (old_data == new_data) { |
| 144 // No change in data. |
| 145 op.set_type(DeltaArchiveManifest_InstallOperation_Type_MOVE); |
| 146 current_best_size = 0; |
| 147 data.clear(); |
| 148 } else { |
| 149 // Try bsdiff of old to new data |
| 150 vector<char> bsdiff_delta; |
| 151 TEST_AND_RETURN_FALSE(ComputeMetadataBsdiff(old_data, |
| 152 new_data, |
| 153 &bsdiff_delta)); |
| 154 CHECK_GT(bsdiff_delta.size(), 0); |
| 155 |
| 156 if (bsdiff_delta.size() < current_best_size) { |
| 157 op.set_type(DeltaArchiveManifest_InstallOperation_Type_BSDIFF); |
| 158 current_best_size = bsdiff_delta.size(); |
| 159 data = bsdiff_delta; |
| 160 } |
| 161 } |
| 162 |
| 163 CHECK_EQ(data.size(), current_best_size); |
| 164 |
| 165 // Set the source and dest extents to be the same since the filesystem |
| 166 // structures are identical |
| 167 if (op.type() == DeltaArchiveManifest_InstallOperation_Type_MOVE || |
| 168 op.type() == DeltaArchiveManifest_InstallOperation_Type_BSDIFF) { |
| 169 DeltaDiffGenerator::StoreExtents(extents, op.mutable_src_extents()); |
| 170 op.set_src_length(old_data.size()); |
| 171 } |
| 172 |
| 173 DeltaDiffGenerator::StoreExtents(extents, op.mutable_dst_extents()); |
| 174 op.set_dst_length(new_data.size()); |
| 175 } |
| 176 |
| 177 // Write data to output file |
| 178 if (op.type() != DeltaArchiveManifest_InstallOperation_Type_MOVE) { |
| 179 op.set_data_offset(*data_file_size); |
| 180 op.set_data_length(data.size()); |
| 181 } |
| 182 |
| 183 TEST_AND_RETURN_FALSE(utils::WriteAll(data_fd, &data[0], data.size())); |
| 184 *data_file_size += data.size(); |
| 185 |
| 186 // Now, insert into graph and blocks vector |
| 187 graph->resize(graph->size() + 1); |
| 188 Vertex::Index vertex = graph->size() - 1; |
| 189 (*graph)[vertex].op = op; |
| 190 CHECK((*graph)[vertex].op.has_type()); |
| 191 (*graph)[vertex].file_name = metadata_name; |
| 192 |
| 193 TEST_AND_RETURN_FALSE(DeltaDiffGenerator::AddInstallOpToBlocksVector( |
| 194 (*graph)[vertex].op, |
| 195 *graph, |
| 196 vertex, |
| 197 blocks)); |
| 198 |
| 199 return true; |
| 200 } |
| 201 |
| 202 // Reads the file system metadata extents. |
| 203 bool ReadFilesystemMetadata(Graph* graph, |
| 204 vector<Block>* blocks, |
| 205 const ext2_filsys fs_old, |
| 206 const ext2_filsys fs_new, |
| 207 int data_fd, |
| 208 off_t* data_file_size) { |
| 209 LOG(INFO) << "Processing <rootfs-metadata>"; |
| 210 |
| 211 // Read all the extents that belong to the main file system metadata. |
| 212 // The metadata blocks are at the start of each block group and goes |
| 213 // until the end of the inode table. |
| 214 for (dgrp_t bg = 0; bg < fs_old->group_desc_count; bg++) { |
| 215 struct ext2_group_desc* group_desc = &fs_old->group_desc[bg]; |
| 216 __u32 num_metadata_blocks = (group_desc->bg_inode_table + |
| 217 fs_old->inode_blocks_per_group) - |
| 218 (bg * fs_old->super->s_blocks_per_group); |
| 219 __u32 bg_start_block = bg * fs_old->super->s_blocks_per_group; |
| 220 |
| 221 // Due to bsdiff slowness, we're going to break each block group down |
| 222 // into metadata chunks and feed them to bsdiff. |
| 223 __u32 num_chunks = 4; |
| 224 __u32 blocks_per_chunk = num_metadata_blocks / num_chunks; |
| 225 __u32 curr_block = bg_start_block; |
| 226 for (__u32 chunk = 0; chunk < num_chunks; chunk++) { |
| 227 Extent extent; |
| 228 if (chunk < num_chunks - 1) { |
| 229 extent = ExtentForRange(curr_block, blocks_per_chunk); |
| 230 } else { |
| 231 extent = ExtentForRange(curr_block, |
| 232 bg_start_block + num_metadata_blocks - |
| 233 curr_block); |
| 234 } |
| 235 |
| 236 vector<Extent> extents; |
| 237 extents.push_back(extent); |
| 238 |
| 239 string metadata_name = StringPrintf("<rootfs-bg-%d-%d-metadata>", |
| 240 bg, chunk); |
| 241 |
| 242 LOG(INFO) << "Processing " << metadata_name; |
| 243 |
| 244 TEST_AND_RETURN_FALSE(AddMetadataExtents(graph, |
| 245 blocks, |
| 246 fs_old, |
| 247 fs_new, |
| 248 metadata_name, |
| 249 extents, |
| 250 data_fd, |
| 251 data_file_size)); |
| 252 |
| 253 curr_block += blocks_per_chunk; |
| 254 } |
| 255 } |
| 256 |
| 257 return true; |
| 258 } |
| 259 |
| 260 // Processes all blocks belonging to an inode |
| 261 int ProcessInodeAllBlocks(ext2_filsys fs, |
| 262 blk_t* blocknr, |
| 263 e2_blkcnt_t blockcnt, |
| 264 blk_t ref_blk, |
| 265 int ref_offset, |
| 266 void* priv) { |
| 267 vector<Extent>* extents = static_cast<vector<Extent>*>(priv); |
| 268 graph_utils::AppendBlockToExtents(extents, *blocknr); |
| 269 return 0; |
| 270 } |
| 271 |
| 272 // Processes only indirect, double indirect or triple indirect metadata |
| 273 // blocks belonging to an inode |
| 274 int ProcessInodeMetadataBlocks(ext2_filsys fs, |
| 275 blk_t* blocknr, |
| 276 e2_blkcnt_t blockcnt, |
| 277 blk_t ref_blk, |
| 278 int ref_offset, |
| 279 void* priv) { |
| 280 vector<Extent>* extents = static_cast<vector<Extent>*>(priv); |
| 281 if (blockcnt < 0) { |
| 282 graph_utils::AppendBlockToExtents(extents, *blocknr); |
| 283 } |
| 284 return 0; |
| 285 } |
| 286 |
| 287 // Read inode metadata blocks. |
| 288 bool ReadInodeMetadata(Graph* graph, |
| 289 vector<Block>* blocks, |
| 290 const ext2_filsys fs_old, |
| 291 const ext2_filsys fs_new, |
| 292 int data_fd, |
| 293 off_t* data_file_size) { |
| 294 TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_old)); |
| 295 TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_read_inode_bitmap(fs_new)); |
| 296 |
| 297 ext2_inode_scan iscan; |
| 298 TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open_inode_scan(fs_old, 0, &iscan)); |
| 299 |
| 300 ext2_ino_t ino; |
| 301 ext2_inode old_inode; |
| 302 while (true) { |
| 303 // Get the next inode on both file systems |
| 304 errcode_t error = ext2fs_get_next_inode(iscan, &ino, &old_inode); |
| 305 |
| 306 // If we get an error enumerating the inodes, we'll just log the error |
| 307 // and exit from our loop which will eventually return a success code |
| 308 // back to the caller. The inode blocks that we cannot account for will |
| 309 // be handled by DeltaDiffGenerator::ReadUnwrittenBlocks(). |
| 310 if (error) { |
| 311 LOG(ERROR) << "Failed to retrieve next inode (" << error << ")"; |
| 312 break; |
| 313 } |
| 314 |
| 315 if (ino == 0) { |
| 316 break; |
| 317 } |
| 318 |
| 319 if (ino == EXT2_RESIZE_INO) { |
| 320 continue; |
| 321 } |
| 322 |
| 323 ext2_inode new_inode; |
| 324 error = ext2fs_read_inode(fs_new, ino, &new_inode); |
| 325 if (error) { |
| 326 LOG(ERROR) << "Failed to retrieve new inode (" << error << ")"; |
| 327 continue; |
| 328 } |
| 329 |
| 330 // Skip inodes that are not in use |
| 331 if (!ext2fs_test_inode_bitmap(fs_old->inode_map, ino) || |
| 332 !ext2fs_test_inode_bitmap(fs_new->inode_map, ino)) { |
| 333 continue; |
| 334 } |
| 335 |
| 336 // Skip inodes that have no data blocks |
| 337 if (old_inode.i_blocks == 0 || new_inode.i_blocks == 0) { |
| 338 continue; |
| 339 } |
| 340 |
| 341 // Skip inodes that are not the same type |
| 342 bool is_old_dir = (ext2fs_check_directory(fs_old, ino) == 0); |
| 343 bool is_new_dir = (ext2fs_check_directory(fs_new, ino) == 0); |
| 344 if (is_old_dir != is_new_dir) { |
| 345 continue; |
| 346 } |
| 347 |
| 348 // Process the inodes metadata blocks |
| 349 // For normal files, metadata blocks are indirect, double indirect |
| 350 // and triple indirect blocks (no data blocks). For directories and |
| 351 // the journal, all blocks are considered metadata blocks. |
| 352 LOG(INFO) << "Processing inode " << ino << " metadata"; |
| 353 |
| 354 bool all_blocks = ((ino == EXT2_JOURNAL_INO) || is_old_dir || is_new_dir); |
| 355 |
| 356 vector<Extent> old_extents; |
| 357 error = ext2fs_block_iterate2(fs_old, ino, 0, NULL, |
| 358 all_blocks ? ProcessInodeAllBlocks : |
| 359 ProcessInodeMetadataBlocks, |
| 360 &old_extents); |
| 361 if (error) { |
| 362 LOG(ERROR) << "Failed to enumerate old inode " << ino |
| 363 << " blocks (" << error << ")"; |
| 364 continue; |
| 365 } |
| 366 |
| 367 vector<Extent> new_extents; |
| 368 error = ext2fs_block_iterate2(fs_new, ino, 0, NULL, |
| 369 all_blocks ? ProcessInodeAllBlocks : |
| 370 ProcessInodeMetadataBlocks, |
| 371 &new_extents); |
| 372 if (error) { |
| 373 LOG(ERROR) << "Failed to enumerate new inode " << ino |
| 374 << " blocks (" << error << ")"; |
| 375 continue; |
| 376 } |
| 377 |
| 378 // Skip inode if there are no metadata blocks |
| 379 if (old_extents.size() == 0 || new_extents.size() == 0) { |
| 380 continue; |
| 381 } |
| 382 |
| 383 // Make sure the two inodes have the same metadata blocks |
| 384 if (old_extents.size() != new_extents.size()) { |
| 385 continue; |
| 386 } |
| 387 |
| 388 bool same_metadata_extents = true; |
| 389 vector<Extent>::iterator it_old; |
| 390 vector<Extent>::iterator it_new; |
| 391 for (it_old = old_extents.begin(), |
| 392 it_new = new_extents.begin(); |
| 393 it_old != old_extents.end() && it_new != new_extents.end(); |
| 394 it_old++, it_new++) { |
| 395 if (it_old->start_block() != it_new->start_block() || |
| 396 it_old->num_blocks() != it_new->num_blocks()) { |
| 397 same_metadata_extents = false; |
| 398 break; |
| 399 } |
| 400 } |
| 401 |
| 402 if (!same_metadata_extents) { |
| 403 continue; |
| 404 } |
| 405 |
| 406 // We have identical inode metadata blocks, we can now add them to |
| 407 // our graph and blocks vector |
| 408 string metadata_name = StringPrintf("<rootfs-inode-%d-metadata>", ino); |
| 409 TEST_AND_RETURN_FALSE(AddMetadataExtents(graph, |
| 410 blocks, |
| 411 fs_old, |
| 412 fs_new, |
| 413 metadata_name, |
| 414 old_extents, |
| 415 data_fd, |
| 416 data_file_size)); |
| 417 } |
| 418 |
| 419 ext2fs_close_inode_scan(iscan); |
| 420 |
| 421 return true; |
| 422 } |
| 423 |
| 424 } // namespace {} |
| 425 |
| 426 // Reads metadata from old image and new image and determines |
| 427 // the smallest way to encode the metadata for the diff. |
| 428 // If there's no change in the metadata, it creates a MOVE |
| 429 // operation. If there is a change, the smallest of REPLACE, REPLACE_BZ, |
| 430 // or BSDIFF wins. It writes the diff to data_fd and updates data_file_size |
| 431 // accordingly. It also adds the required operation to the graph and adds the |
| 432 // metadata extents to blocks. |
| 433 // Returns true on success. |
| 434 bool Metadata::DeltaReadMetadata(Graph* graph, |
| 435 vector<Block>* blocks, |
| 436 const string& old_image, |
| 437 const string& new_image, |
| 438 int data_fd, |
| 439 off_t* data_file_size) { |
| 440 // Open the two file systems. |
| 441 ext2_filsys fs_old; |
| 442 TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(old_image.c_str(), 0, 0, 0, |
| 443 unix_io_manager, &fs_old)); |
| 444 ScopedExt2fsCloser fs_old_closer(fs_old); |
| 445 |
| 446 ext2_filsys fs_new; |
| 447 TEST_AND_RETURN_FALSE_ERRCODE(ext2fs_open(new_image.c_str(), 0, 0, 0, |
| 448 unix_io_manager, &fs_new)); |
| 449 ScopedExt2fsCloser fs_new_closer(fs_new); |
| 450 |
| 451 // Make sure these two file systems are the same. |
| 452 // If they are not the same, the metadata blocks will be packaged up in its |
| 453 // entirety by ReadUnwrittenBlocks(). |
| 454 if (fs_old->blocksize != fs_new->blocksize || |
| 455 fs_old->fragsize != fs_new->fragsize || |
| 456 fs_old->group_desc_count != fs_new->group_desc_count || |
| 457 fs_old->inode_blocks_per_group != fs_new->inode_blocks_per_group || |
| 458 fs_old->super->s_inodes_count != fs_new->super->s_inodes_count || |
| 459 fs_old->super->s_blocks_count != fs_new->super->s_blocks_count) { |
| 460 return true; |
| 461 } |
| 462 |
| 463 // Process the main file system metadata (superblock, inode tables, etc) |
| 464 TEST_AND_RETURN_FALSE(ReadFilesystemMetadata(graph, |
| 465 blocks, |
| 466 fs_old, |
| 467 fs_new, |
| 468 data_fd, |
| 469 data_file_size)); |
| 470 |
| 471 // Process each inode metadata blocks. |
| 472 TEST_AND_RETURN_FALSE(ReadInodeMetadata(graph, |
| 473 blocks, |
| 474 fs_old, |
| 475 fs_new, |
| 476 data_fd, |
| 477 data_file_size)); |
| 478 |
| 479 return true; |
| 480 } |
| 481 |
| 482 }; // namespace chromeos_update_engine |
OLD | NEW |