| // |
| // Copyright (C) 2017 The Android Open Source Project |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| // |
| |
| #include "update_engine/payload_generator/deflate_utils.h" |
| |
| #include <algorithm> |
| #include <string> |
| #include <utility> |
| |
| #include <base/files/file_util.h> |
| #include <base/logging.h> |
| #include <base/strings/string_util.h> |
| |
| #include "update_engine/common/utils.h" |
| #include "update_engine/payload_generator/delta_diff_generator.h" |
| #include "update_engine/payload_generator/extent_ranges.h" |
| #include "update_engine/payload_generator/extent_utils.h" |
| #include "update_engine/payload_generator/squashfs_filesystem.h" |
| #include "update_engine/update_metadata.pb.h" |
| |
| using puffin::BitExtent; |
| using puffin::ByteExtent; |
| using std::string; |
| using std::vector; |
| |
| namespace chromeos_update_engine { |
| namespace deflate_utils { |
| namespace { |
| |
| // The minimum size for a squashfs image to be processed. |
| const uint64_t kMinimumSquashfsImageSize = 1 * 1024 * 1024; // bytes |
| |
| // TODO(*): Optimize this so we don't have to read all extents into memory in |
| // case it is large. |
| bool CopyExtentsToFile(const string& in_path, |
| const vector<Extent> extents, |
| const string& out_path, |
| size_t block_size) { |
| brillo::Blob data(utils::BlocksInExtents(extents) * block_size); |
| TEST_AND_RETURN_FALSE( |
| utils::ReadExtents(in_path, extents, &data, data.size(), block_size)); |
| TEST_AND_RETURN_FALSE( |
| utils::WriteFile(out_path.c_str(), data.data(), data.size())); |
| return true; |
| } |
| |
| bool IsSquashfsImage(const string& part_path, |
| const FilesystemInterface::File& file) { |
| // Only check for files with img postfix. |
| if (base::EndsWith(file.name, ".img", base::CompareCase::SENSITIVE) && |
| utils::BlocksInExtents(file.extents) >= |
| kMinimumSquashfsImageSize / kBlockSize) { |
| brillo::Blob super_block; |
| TEST_AND_RETURN_FALSE( |
| utils::ReadFileChunk(part_path, |
| file.extents[0].start_block() * kBlockSize, |
| 100, |
| &super_block)); |
| return SquashfsFilesystem::IsSquashfsImage(super_block); |
| } |
| return false; |
| } |
| |
| // Realigns subfiles |files| of a splitted file |file| into its correct |
| // positions. This can be used for squashfs, zip, apk, etc. |
| bool RealignSplittedFiles(const FilesystemInterface::File& file, |
| vector<FilesystemInterface::File>* files) { |
| // We have to shift all the Extents in |files|, based on the Extents of the |
| // |file| itself. |
| size_t num_blocks = 0; |
| for (auto& in_file : *files) { // We need to modify so no constant. |
| TEST_AND_RETURN_FALSE( |
| ShiftExtentsOverExtents(file.extents, &in_file.extents)); |
| TEST_AND_RETURN_FALSE( |
| ShiftBitExtentsOverExtents(file.extents, &in_file.deflates)); |
| |
| in_file.name = file.name + "/" + in_file.name; |
| num_blocks += utils::BlocksInExtents(in_file.extents); |
| } |
| |
| // Check that all files in |in_files| cover the entire image. |
| TEST_AND_RETURN_FALSE(utils::BlocksInExtents(file.extents) == num_blocks); |
| return true; |
| } |
| |
| bool IsBitExtentInExtent(const Extent& extent, const BitExtent& bit_extent) { |
| return (bit_extent.offset / 8) >= (extent.start_block() * kBlockSize) && |
| ((bit_extent.offset + bit_extent.length + 7) / 8) <= |
| ((extent.start_block() + extent.num_blocks()) * kBlockSize); |
| } |
| |
| // Returns whether the given file |name| has an extension listed in |
| // |extensions|. |
| bool IsFileExtensions(const string& name, |
| const std::initializer_list<string>& extensions) { |
| return any_of(extensions.begin(), extensions.end(), [&name](const auto& ext) { |
| return base::EndsWith(name, ext, base::CompareCase::INSENSITIVE_ASCII); |
| }); |
| } |
| |
| } // namespace |
| |
| ByteExtent ExpandToByteExtent(const BitExtent& extent) { |
| uint64_t offset = extent.offset / 8; |
| uint64_t length = ((extent.offset + extent.length + 7) / 8) - offset; |
| return {offset, length}; |
| } |
| |
| bool ShiftExtentsOverExtents(const vector<Extent>& base_extents, |
| vector<Extent>* over_extents) { |
| if (utils::BlocksInExtents(base_extents) < |
| utils::BlocksInExtents(*over_extents)) { |
| LOG(ERROR) << "over_extents have more blocks than base_extents! Invalid!"; |
| return false; |
| } |
| for (size_t idx = 0; idx < over_extents->size(); idx++) { |
| auto over_ext = &over_extents->at(idx); |
| auto gap_blocks = base_extents[0].start_block(); |
| auto last_end_block = base_extents[0].start_block(); |
| for (auto base_ext : base_extents) { // We need to modify |base_ext|, so we |
| // use copy. |
| gap_blocks += base_ext.start_block() - last_end_block; |
| last_end_block = base_ext.start_block() + base_ext.num_blocks(); |
| base_ext.set_start_block(base_ext.start_block() - gap_blocks); |
| if (over_ext->start_block() >= base_ext.start_block() && |
| over_ext->start_block() < |
| base_ext.start_block() + base_ext.num_blocks()) { |
| if (over_ext->start_block() + over_ext->num_blocks() <= |
| base_ext.start_block() + base_ext.num_blocks()) { |
| // |over_ext| is inside |base_ext|, increase its start block. |
| over_ext->set_start_block(over_ext->start_block() + gap_blocks); |
| } else { |
| // |over_ext| spills over this |base_ext|, split it into two. |
| auto new_blocks = base_ext.start_block() + base_ext.num_blocks() - |
| over_ext->start_block(); |
| vector<Extent> new_extents = { |
| ExtentForRange(gap_blocks + over_ext->start_block(), new_blocks), |
| ExtentForRange(over_ext->start_block() + new_blocks, |
| over_ext->num_blocks() - new_blocks)}; |
| *over_ext = new_extents[0]; |
| over_extents->insert(std::next(over_extents->begin(), idx + 1), |
| new_extents[1]); |
| } |
| break; // We processed |over_ext|, so break the loop; |
| } |
| } |
| } |
| return true; |
| } |
| |
| bool ShiftBitExtentsOverExtents(const vector<Extent>& base_extents, |
| vector<BitExtent>* over_extents) { |
| if (over_extents->empty()) { |
| return true; |
| } |
| |
| // This check is needed to make sure the number of bytes in |over_extents| |
| // does not exceed |base_extents|. |
| auto last_extent = ExpandToByteExtent(over_extents->back()); |
| TEST_AND_RETURN_FALSE(last_extent.offset + last_extent.length <= |
| utils::BlocksInExtents(base_extents) * kBlockSize); |
| |
| for (auto o_ext = over_extents->begin(); o_ext != over_extents->end();) { |
| size_t gap_blocks = base_extents[0].start_block(); |
| size_t last_end_block = base_extents[0].start_block(); |
| bool o_ext_processed = false; |
| for (auto b_ext : base_extents) { // We need to modify |b_ext|, so we copy. |
| gap_blocks += b_ext.start_block() - last_end_block; |
| last_end_block = b_ext.start_block() + b_ext.num_blocks(); |
| b_ext.set_start_block(b_ext.start_block() - gap_blocks); |
| auto byte_o_ext = ExpandToByteExtent(*o_ext); |
| if (byte_o_ext.offset >= b_ext.start_block() * kBlockSize && |
| byte_o_ext.offset < |
| (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) { |
| if ((byte_o_ext.offset + byte_o_ext.length) <= |
| (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) { |
| // |o_ext| is inside |b_ext|, increase its start block. |
| o_ext->offset += gap_blocks * kBlockSize * 8; |
| ++o_ext; |
| } else { |
| // |o_ext| spills over this |b_ext|, remove it. |
| o_ext = over_extents->erase(o_ext); |
| } |
| o_ext_processed = true; |
| break; // We processed o_ext, so break the loop; |
| } |
| } |
| TEST_AND_RETURN_FALSE(o_ext_processed); |
| } |
| return true; |
| } |
| |
| vector<BitExtent> FindDeflates(const vector<Extent>& extents, |
| const vector<BitExtent>& in_deflates) { |
| vector<BitExtent> result; |
| // TODO(ahassani): Replace this with binary_search style search. |
| for (const auto& deflate : in_deflates) { |
| for (const auto& extent : extents) { |
| if (IsBitExtentInExtent(extent, deflate)) { |
| result.push_back(deflate); |
| break; |
| } |
| } |
| } |
| return result; |
| } |
| |
| bool CompactDeflates(const vector<Extent>& extents, |
| const vector<BitExtent>& in_deflates, |
| vector<BitExtent>* out_deflates) { |
| size_t bytes_passed = 0; |
| out_deflates->reserve(in_deflates.size()); |
| for (const auto& extent : extents) { |
| size_t gap_bytes = extent.start_block() * kBlockSize - bytes_passed; |
| for (const auto& deflate : in_deflates) { |
| if (IsBitExtentInExtent(extent, deflate)) { |
| out_deflates->emplace_back(deflate.offset - (gap_bytes * 8), |
| deflate.length); |
| } |
| } |
| bytes_passed += extent.num_blocks() * kBlockSize; |
| } |
| |
| // All given |in_deflates| items should've been inside one of the extents in |
| // |extents|. |
| TEST_AND_RETURN_FALSE(in_deflates.size() == out_deflates->size()); |
| |
| // Make sure all outgoing deflates are ordered and non-overlapping. |
| auto result = std::adjacent_find(out_deflates->begin(), |
| out_deflates->end(), |
| [](const BitExtent& a, const BitExtent& b) { |
| return (a.offset + a.length) > b.offset; |
| }); |
| TEST_AND_RETURN_FALSE(result == out_deflates->end()); |
| return true; |
| } |
| |
| bool FindAndCompactDeflates(const vector<Extent>& extents, |
| const vector<BitExtent>& in_deflates, |
| vector<BitExtent>* out_deflates) { |
| auto found_deflates = FindDeflates(extents, in_deflates); |
| TEST_AND_RETURN_FALSE(CompactDeflates(extents, found_deflates, out_deflates)); |
| return true; |
| } |
| |
| bool PreprocessPartitionFiles(const PartitionConfig& part, |
| vector<FilesystemInterface::File>* result_files, |
| bool extract_deflates) { |
| // Get the file system files. |
| vector<FilesystemInterface::File> tmp_files; |
| part.fs_interface->GetFiles(&tmp_files); |
| result_files->reserve(tmp_files.size()); |
| |
| for (auto& file : tmp_files) { |
| if (IsSquashfsImage(part.path, file)) { |
| // Read the image into a file. |
| base::FilePath path; |
| TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&path)); |
| ScopedPathUnlinker old_unlinker(path.value()); |
| TEST_AND_RETURN_FALSE( |
| CopyExtentsToFile(part.path, file.extents, path.value(), kBlockSize)); |
| // Test if it is actually a Squashfs file. |
| auto sqfs = SquashfsFilesystem::CreateFromFile(path.value(), |
| extract_deflates, |
| /*load_settings=*/false); |
| if (sqfs) { |
| // It is an squashfs file. Get its files to replace with itself. |
| vector<FilesystemInterface::File> files; |
| sqfs->GetFiles(&files); |
| |
| // Replace squashfs file with its files only if |files| has at least two |
| // files or if it has some deflates (since it is better to replace it to |
| // take advantage of the deflates.) |
| if (files.size() > 1 || |
| (files.size() == 1 && !files[0].deflates.empty())) { |
| TEST_AND_RETURN_FALSE(RealignSplittedFiles(file, &files)); |
| result_files->insert(result_files->end(), files.begin(), files.end()); |
| continue; |
| } |
| } else { |
| LOG(WARNING) << "We thought file: " << file.name |
| << " was a Squashfs file, but it was not."; |
| } |
| } |
| |
| if (extract_deflates) { |
| // Search for deflates if the file is in zip or gzip format. |
| // .zvoice files may eventually move out of rootfs. If that happens, |
| // remove ".zvoice" (crbug.com/782918). |
| bool is_zip = IsFileExtensions( |
| file.name, {".apk", ".zip", ".jar", ".zvoice", ".apex"}); |
| bool is_gzip = IsFileExtensions(file.name, {".gz", ".gzip", ".tgz"}); |
| if (is_zip || is_gzip) { |
| brillo::Blob data; |
| TEST_AND_RETURN_FALSE(utils::ReadExtents( |
| part.path, |
| file.extents, |
| &data, |
| kBlockSize * utils::BlocksInExtents(file.extents), |
| kBlockSize)); |
| vector<puffin::BitExtent> deflates; |
| if (is_zip) { |
| TEST_AND_RETURN_FALSE( |
| puffin::LocateDeflatesInZipArchive(data, &deflates)); |
| } else if (is_gzip) { |
| TEST_AND_RETURN_FALSE(puffin::LocateDeflatesInGzip(data, &deflates)); |
| } |
| // Shift the deflate's extent to the offset starting from the beginning |
| // of the current partition; and the delta processor will align the |
| // extents in a continuous buffer later. |
| TEST_AND_RETURN_FALSE( |
| ShiftBitExtentsOverExtents(file.extents, &deflates)); |
| file.deflates = std::move(deflates); |
| } |
| } |
| |
| result_files->push_back(file); |
| } |
| return true; |
| } |
| |
| } // namespace deflate_utils |
| } // namespace chromeos_update_engine |
