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