Thieu Le | 5c7d975 | 2010-12-15 16:09:28 -0800 | [diff] [blame] | 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. |
Thieu Le | 4e8a306 | 2011-01-05 12:46:31 -0800 | [diff] [blame^] | 223 | __u32 num_chunks = 10; |
Thieu Le | 5c7d975 | 2010-12-15 16:09:28 -0800 | [diff] [blame] | 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 |