1 // 2 // Copyright (C) 2017 The Android Open Source Project 3 // 4 // Licensed under the Apache License, Version 2.0 (the "License"); 5 // you may not use this file except in compliance with the License. 6 // You may obtain a copy of the License at 7 // 8 // http://www.apache.org/licenses/LICENSE-2.0 9 // 10 // Unless required by applicable law or agreed to in writing, software 11 // distributed under the License is distributed on an "AS IS" BASIS, 12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13 // See the License for the specific language governing permissions and 14 // limitations under the License. 15 // 16 17 #include "update_engine/payload_generator/deflate_utils.h" 18 19 #include <algorithm> 20 #include <string> 21 #include <utility> 22 23 #include <base/files/file_util.h> 24 #include <base/logging.h> 25 #include <base/strings/string_util.h> 26 27 #include "update_engine/common/utils.h" 28 #include "update_engine/payload_generator/delta_diff_generator.h" 29 #include "update_engine/payload_generator/extent_ranges.h" 30 #include "update_engine/payload_generator/extent_utils.h" 31 #include "update_engine/payload_generator/squashfs_filesystem.h" 32 #include "update_engine/update_metadata.pb.h" 33 34 using std::string; 35 using std::vector; 36 using puffin::BitExtent; 37 using puffin::ByteExtent; 38 39 namespace chromeos_update_engine { 40 namespace deflate_utils { 41 namespace { 42 43 // The minimum size for a squashfs image to be processed. 44 const uint64_t kMinimumSquashfsImageSize = 1 * 1024 * 1024; // bytes 45 46 // TODO(*): Optimize this so we don't have to read all extents into memory in 47 // case it is large. 48 bool CopyExtentsToFile(const string& in_path, 49 const vector<Extent> extents, 50 const string& out_path, 51 size_t block_size) { 52 brillo::Blob data(utils::BlocksInExtents(extents) * block_size); 53 TEST_AND_RETURN_FALSE( 54 utils::ReadExtents(in_path, extents, &data, data.size(), block_size)); 55 TEST_AND_RETURN_FALSE( 56 utils::WriteFile(out_path.c_str(), data.data(), data.size())); 57 return true; 58 } 59 60 bool IsSquashfsImage(const string& part_path, 61 const FilesystemInterface::File& file) { 62 // Only check for files with img postfix. 63 if (base::EndsWith(file.name, ".img", base::CompareCase::SENSITIVE) && 64 utils::BlocksInExtents(file.extents) >= 65 kMinimumSquashfsImageSize / kBlockSize) { 66 brillo::Blob super_block; 67 TEST_AND_RETURN_FALSE( 68 utils::ReadFileChunk(part_path, 69 file.extents[0].start_block() * kBlockSize, 70 100, 71 &super_block)); 72 return SquashfsFilesystem::IsSquashfsImage(super_block); 73 } 74 return false; 75 } 76 77 // Realigns subfiles |files| of a splitted file |file| into its correct 78 // positions. This can be used for squashfs, zip, apk, etc. 79 bool RealignSplittedFiles(const FilesystemInterface::File& file, 80 vector<FilesystemInterface::File>* files) { 81 // We have to shift all the Extents in |files|, based on the Extents of the 82 // |file| itself. 83 size_t num_blocks = 0; 84 for (auto& in_file : *files) { // We need to modify so no constant. 85 TEST_AND_RETURN_FALSE( 86 ShiftExtentsOverExtents(file.extents, &in_file.extents)); 87 TEST_AND_RETURN_FALSE( 88 ShiftBitExtentsOverExtents(file.extents, &in_file.deflates)); 89 90 in_file.name = file.name + "/" + in_file.name; 91 num_blocks += utils::BlocksInExtents(in_file.extents); 92 } 93 94 // Check that all files in |in_files| cover the entire image. 95 TEST_AND_RETURN_FALSE(utils::BlocksInExtents(file.extents) == num_blocks); 96 return true; 97 } 98 99 bool IsBitExtentInExtent(const Extent& extent, const BitExtent& bit_extent) { 100 return (bit_extent.offset / 8) >= (extent.start_block() * kBlockSize) && 101 ((bit_extent.offset + bit_extent.length + 7) / 8) <= 102 ((extent.start_block() + extent.num_blocks()) * kBlockSize); 103 } 104 105 } // namespace 106 107 ByteExtent ExpandToByteExtent(const BitExtent& extent) { 108 uint64_t offset = extent.offset / 8; 109 uint64_t length = ((extent.offset + extent.length + 7) / 8) - offset; 110 return {offset, length}; 111 } 112 113 bool ShiftExtentsOverExtents(const vector<Extent>& base_extents, 114 vector<Extent>* over_extents) { 115 if (utils::BlocksInExtents(base_extents) < 116 utils::BlocksInExtents(*over_extents)) { 117 LOG(ERROR) << "over_extents have more blocks than base_extents! Invalid!"; 118 return false; 119 } 120 for (size_t idx = 0; idx < over_extents->size(); idx++) { 121 auto over_ext = &over_extents->at(idx); 122 auto gap_blocks = base_extents[0].start_block(); 123 auto last_end_block = base_extents[0].start_block(); 124 for (auto base_ext : base_extents) { // We need to modify |base_ext|, so we 125 // use copy. 126 gap_blocks += base_ext.start_block() - last_end_block; 127 last_end_block = base_ext.start_block() + base_ext.num_blocks(); 128 base_ext.set_start_block(base_ext.start_block() - gap_blocks); 129 if (over_ext->start_block() >= base_ext.start_block() && 130 over_ext->start_block() < 131 base_ext.start_block() + base_ext.num_blocks()) { 132 if (over_ext->start_block() + over_ext->num_blocks() <= 133 base_ext.start_block() + base_ext.num_blocks()) { 134 // |over_ext| is inside |base_ext|, increase its start block. 135 over_ext->set_start_block(over_ext->start_block() + gap_blocks); 136 } else { 137 // |over_ext| spills over this |base_ext|, split it into two. 138 auto new_blocks = base_ext.start_block() + base_ext.num_blocks() - 139 over_ext->start_block(); 140 vector<Extent> new_extents = { 141 ExtentForRange(gap_blocks + over_ext->start_block(), new_blocks), 142 ExtentForRange(over_ext->start_block() + new_blocks, 143 over_ext->num_blocks() - new_blocks)}; 144 *over_ext = new_extents[0]; 145 over_extents->insert(std::next(over_extents->begin(), idx + 1), 146 new_extents[1]); 147 } 148 break; // We processed |over_ext|, so break the loop; 149 } 150 } 151 } 152 return true; 153 } 154 155 bool ShiftBitExtentsOverExtents(const vector<Extent>& base_extents, 156 vector<BitExtent>* over_extents) { 157 if (over_extents->empty()) { 158 return true; 159 } 160 161 // This check is needed to make sure the number of bytes in |over_extents| 162 // does not exceed |base_extents|. 163 auto last_extent = ExpandToByteExtent(over_extents->back()); 164 TEST_AND_RETURN_FALSE(last_extent.offset + last_extent.length <= 165 utils::BlocksInExtents(base_extents) * kBlockSize); 166 167 for (auto o_ext = over_extents->begin(); o_ext != over_extents->end();) { 168 size_t gap_blocks = base_extents[0].start_block(); 169 size_t last_end_block = base_extents[0].start_block(); 170 bool o_ext_processed = false; 171 for (auto b_ext : base_extents) { // We need to modify |b_ext|, so we copy. 172 gap_blocks += b_ext.start_block() - last_end_block; 173 last_end_block = b_ext.start_block() + b_ext.num_blocks(); 174 b_ext.set_start_block(b_ext.start_block() - gap_blocks); 175 auto byte_o_ext = ExpandToByteExtent(*o_ext); 176 if (byte_o_ext.offset >= b_ext.start_block() * kBlockSize && 177 byte_o_ext.offset < 178 (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) { 179 if ((byte_o_ext.offset + byte_o_ext.length) <= 180 (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) { 181 // |o_ext| is inside |b_ext|, increase its start block. 182 o_ext->offset += gap_blocks * kBlockSize * 8; 183 ++o_ext; 184 } else { 185 // |o_ext| spills over this |b_ext|, remove it. 186 o_ext = over_extents->erase(o_ext); 187 } 188 o_ext_processed = true; 189 break; // We processed o_ext, so break the loop; 190 } 191 } 192 TEST_AND_RETURN_FALSE(o_ext_processed); 193 } 194 return true; 195 } 196 197 vector<BitExtent> FindDeflates(const vector<Extent>& extents, 198 const vector<BitExtent>& in_deflates) { 199 vector<BitExtent> result; 200 // TODO(ahassani): Replace this with binary_search style search. 201 for (const auto& deflate : in_deflates) { 202 for (const auto& extent : extents) { 203 if (IsBitExtentInExtent(extent, deflate)) { 204 result.push_back(deflate); 205 break; 206 } 207 } 208 } 209 return result; 210 } 211 212 bool CompactDeflates(const vector<Extent>& extents, 213 const vector<BitExtent>& in_deflates, 214 vector<BitExtent>* out_deflates) { 215 size_t bytes_passed = 0; 216 out_deflates->reserve(in_deflates.size()); 217 for (const auto& extent : extents) { 218 size_t gap_bytes = extent.start_block() * kBlockSize - bytes_passed; 219 for (const auto& deflate : in_deflates) { 220 if (IsBitExtentInExtent(extent, deflate)) { 221 out_deflates->emplace_back(deflate.offset - (gap_bytes * 8), 222 deflate.length); 223 } 224 } 225 bytes_passed += extent.num_blocks() * kBlockSize; 226 } 227 228 // All given |in_deflates| items should've been inside one of the extents in 229 // |extents|. 230 TEST_AND_RETURN_FALSE(in_deflates.size() == out_deflates->size()); 231 232 // Make sure all outgoing deflates are ordered and non-overlapping. 233 auto result = std::adjacent_find(out_deflates->begin(), 234 out_deflates->end(), 235 [](const BitExtent& a, const BitExtent& b) { 236 return (a.offset + a.length) > b.offset; 237 }); 238 TEST_AND_RETURN_FALSE(result == out_deflates->end()); 239 return true; 240 } 241 242 bool FindAndCompactDeflates(const vector<Extent>& extents, 243 const vector<BitExtent>& in_deflates, 244 vector<BitExtent>* out_deflates) { 245 auto found_deflates = FindDeflates(extents, in_deflates); 246 TEST_AND_RETURN_FALSE(CompactDeflates(extents, found_deflates, out_deflates)); 247 return true; 248 } 249 250 bool PreprocessParitionFiles(const PartitionConfig& part, 251 vector<FilesystemInterface::File>* result_files, 252 bool extract_deflates) { 253 // Get the file system files. 254 vector<FilesystemInterface::File> tmp_files; 255 part.fs_interface->GetFiles(&tmp_files); 256 result_files->reserve(tmp_files.size()); 257 258 for (auto& file : tmp_files) { 259 if (IsSquashfsImage(part.path, file)) { 260 // Read the image into a file. 261 base::FilePath path; 262 TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&path)); 263 ScopedPathUnlinker old_unlinker(path.value()); 264 TEST_AND_RETURN_FALSE( 265 CopyExtentsToFile(part.path, file.extents, path.value(), kBlockSize)); 266 // Test if it is actually a Squashfs file. 267 auto sqfs = 268 SquashfsFilesystem::CreateFromFile(path.value(), extract_deflates); 269 if (sqfs) { 270 // It is an squashfs file. Get its files to replace with itself. 271 vector<FilesystemInterface::File> files; 272 sqfs->GetFiles(&files); 273 274 // Replace squashfs file with its files only if |files| has at least two 275 // files or if it has some deflates (since it is better to replace it to 276 // take advantage of the deflates.) 277 if (files.size() > 1 || 278 (files.size() == 1 && !files[0].deflates.empty())) { 279 TEST_AND_RETURN_FALSE(RealignSplittedFiles(file, &files)); 280 result_files->insert(result_files->end(), files.begin(), files.end()); 281 continue; 282 } 283 } else { 284 LOG(WARNING) << "We thought file: " << file.name 285 << " was a Squashfs file, but it was not."; 286 } 287 } 288 289 // Search for deflates if the file is in zip format. 290 bool is_zip = 291 base::EndsWith( 292 file.name, ".apk", base::CompareCase::INSENSITIVE_ASCII) || 293 base::EndsWith( 294 file.name, ".zip", base::CompareCase::INSENSITIVE_ASCII) || 295 base::EndsWith(file.name, ".jar", base::CompareCase::INSENSITIVE_ASCII); 296 297 if (is_zip && extract_deflates) { 298 brillo::Blob data; 299 TEST_AND_RETURN_FALSE( 300 utils::ReadExtents(part.path, 301 file.extents, 302 &data, 303 kBlockSize * utils::BlocksInExtents(file.extents), 304 kBlockSize)); 305 std::vector<puffin::BitExtent> deflates_sub_blocks; 306 TEST_AND_RETURN_FALSE(puffin::LocateDeflateSubBlocksInZipArchive( 307 data, &deflates_sub_blocks)); 308 // Shift the deflate's extent to the offset starting from the beginning 309 // of the current partition; and the delta processor will align the 310 // extents in a continuous buffer later. 311 TEST_AND_RETURN_FALSE( 312 ShiftBitExtentsOverExtents(file.extents, &deflates_sub_blocks)); 313 file.deflates = std::move(deflates_sub_blocks); 314 } 315 316 result_files->push_back(file); 317 } 318 return true; 319 } 320 321 } // namespace deflate_utils 322 } // namespace chromeos_update_engine 323
