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 puffin::BitExtent;
35 using puffin::ByteExtent;
36 using std::string;
37 using std::vector;
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 bool IsRegularFile(const FilesystemInterface::File& file) {
78   // If inode is 0, then stat information is invalid for some psuedo files
79   if (file.file_stat.st_ino != 0 &&
80       (file.file_stat.st_mode & S_IFMT) == S_IFREG) {
81     return true;
82   }
83   return false;
84 }
85 
86 // Realigns subfiles |files| of a splitted file |file| into its correct
87 // positions. This can be used for squashfs, zip, apk, etc.
88 bool RealignSplittedFiles(const FilesystemInterface::File& file,
89                           vector<FilesystemInterface::File>* files) {
90   // We have to shift all the Extents in |files|, based on the Extents of the
91   // |file| itself.
92   size_t num_blocks = 0;
93   for (auto& in_file : *files) {  // We need to modify so no constant.
94     TEST_AND_RETURN_FALSE(
95         ShiftExtentsOverExtents(file.extents, &in_file.extents));
96     TEST_AND_RETURN_FALSE(
97         ShiftBitExtentsOverExtents(file.extents, &in_file.deflates));
98 
99     in_file.name = file.name + "/" + in_file.name;
100     num_blocks += utils::BlocksInExtents(in_file.extents);
101   }
102 
103   // Check that all files in |in_files| cover the entire image.
104   TEST_AND_RETURN_FALSE(utils::BlocksInExtents(file.extents) == num_blocks);
105   return true;
106 }
107 
108 bool IsBitExtentInExtent(const Extent& extent, const BitExtent& bit_extent) {
109   return (bit_extent.offset / 8) >= (extent.start_block() * kBlockSize) &&
110          ((bit_extent.offset + bit_extent.length + 7) / 8) <=
111              ((extent.start_block() + extent.num_blocks()) * kBlockSize);
112 }
113 
114 // Returns whether the given file |name| has an extension listed in
115 // |extensions|.
116 bool IsFileExtensions(const string& name,
117                       const std::initializer_list<string>& extensions) {
118   return any_of(extensions.begin(), extensions.end(), [&name](const auto& ext) {
119     return base::EndsWith(name, ext, base::CompareCase::INSENSITIVE_ASCII);
120   });
121 }
122 
123 }  // namespace
124 
125 ByteExtent ExpandToByteExtent(const BitExtent& extent) {
126   uint64_t offset = extent.offset / 8;
127   uint64_t length = ((extent.offset + extent.length + 7) / 8) - offset;
128   return {offset, length};
129 }
130 
131 bool ShiftExtentsOverExtents(const vector<Extent>& base_extents,
132                              vector<Extent>* over_extents) {
133   if (utils::BlocksInExtents(base_extents) <
134       utils::BlocksInExtents(*over_extents)) {
135     LOG(ERROR) << "over_extents have more blocks than base_extents! Invalid!";
136     return false;
137   }
138   for (size_t idx = 0; idx < over_extents->size(); idx++) {
139     auto over_ext = &over_extents->at(idx);
140     auto gap_blocks = base_extents[0].start_block();
141     auto last_end_block = base_extents[0].start_block();
142     for (auto base_ext : base_extents) {  // We need to modify |base_ext|, so we
143                                           // use copy.
144       gap_blocks += base_ext.start_block() - last_end_block;
145       last_end_block = base_ext.start_block() + base_ext.num_blocks();
146       base_ext.set_start_block(base_ext.start_block() - gap_blocks);
147       if (over_ext->start_block() >= base_ext.start_block() &&
148           over_ext->start_block() <
149               base_ext.start_block() + base_ext.num_blocks()) {
150         if (over_ext->start_block() + over_ext->num_blocks() <=
151             base_ext.start_block() + base_ext.num_blocks()) {
152           // |over_ext| is inside |base_ext|, increase its start block.
153           over_ext->set_start_block(over_ext->start_block() + gap_blocks);
154         } else {
155           // |over_ext| spills over this |base_ext|, split it into two.
156           auto new_blocks = base_ext.start_block() + base_ext.num_blocks() -
157                             over_ext->start_block();
158           vector<Extent> new_extents = {
159               ExtentForRange(gap_blocks + over_ext->start_block(), new_blocks),
160               ExtentForRange(over_ext->start_block() + new_blocks,
161                              over_ext->num_blocks() - new_blocks)};
162           *over_ext = new_extents[0];
163           over_extents->insert(std::next(over_extents->begin(), idx + 1),
164                                new_extents[1]);
165         }
166         break;  // We processed |over_ext|, so break the loop;
167       }
168     }
169   }
170   return true;
171 }
172 
173 bool ShiftBitExtentsOverExtents(const vector<Extent>& base_extents,
174                                 vector<BitExtent>* over_extents) {
175   if (over_extents->empty()) {
176     return true;
177   }
178 
179   // This check is needed to make sure the number of bytes in |over_extents|
180   // does not exceed |base_extents|.
181   auto last_extent = ExpandToByteExtent(over_extents->back());
182   TEST_AND_RETURN_FALSE(last_extent.offset + last_extent.length <=
183                         utils::BlocksInExtents(base_extents) * kBlockSize);
184 
185   for (auto o_ext = over_extents->begin(); o_ext != over_extents->end();) {
186     size_t gap_blocks = base_extents[0].start_block();
187     size_t last_end_block = base_extents[0].start_block();
188     bool o_ext_processed = false;
189     for (auto b_ext : base_extents) {  // We need to modify |b_ext|, so we copy.
190       gap_blocks += b_ext.start_block() - last_end_block;
191       last_end_block = b_ext.start_block() + b_ext.num_blocks();
192       b_ext.set_start_block(b_ext.start_block() - gap_blocks);
193       auto byte_o_ext = ExpandToByteExtent(*o_ext);
194       if (byte_o_ext.offset >= b_ext.start_block() * kBlockSize &&
195           byte_o_ext.offset <
196               (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) {
197         if ((byte_o_ext.offset + byte_o_ext.length) <=
198             (b_ext.start_block() + b_ext.num_blocks()) * kBlockSize) {
199           // |o_ext| is inside |b_ext|, increase its start block.
200           o_ext->offset += gap_blocks * kBlockSize * 8;
201           ++o_ext;
202         } else {
203           // |o_ext| spills over this |b_ext|, remove it.
204           o_ext = over_extents->erase(o_ext);
205         }
206         o_ext_processed = true;
207         break;  // We processed o_ext, so break the loop;
208       }
209     }
210     TEST_AND_RETURN_FALSE(o_ext_processed);
211   }
212   return true;
213 }
214 
215 vector<BitExtent> FindDeflates(const vector<Extent>& extents,
216                                const vector<BitExtent>& in_deflates) {
217   vector<BitExtent> result;
218   // TODO(ahassani): Replace this with binary_search style search.
219   for (const auto& deflate : in_deflates) {
220     for (const auto& extent : extents) {
221       if (IsBitExtentInExtent(extent, deflate)) {
222         result.push_back(deflate);
223         break;
224       }
225     }
226   }
227   return result;
228 }
229 
230 bool CompactDeflates(const vector<Extent>& extents,
231                      const vector<BitExtent>& in_deflates,
232                      vector<BitExtent>* out_deflates) {
233   size_t bytes_passed = 0;
234   out_deflates->reserve(in_deflates.size());
235   for (const auto& extent : extents) {
236     size_t gap_bytes = extent.start_block() * kBlockSize - bytes_passed;
237     for (const auto& deflate : in_deflates) {
238       if (IsBitExtentInExtent(extent, deflate)) {
239         out_deflates->emplace_back(deflate.offset - (gap_bytes * 8),
240                                    deflate.length);
241       }
242     }
243     bytes_passed += extent.num_blocks() * kBlockSize;
244   }
245 
246   // All given |in_deflates| items should've been inside one of the extents in
247   // |extents|.
248   TEST_AND_RETURN_FALSE(in_deflates.size() == out_deflates->size());
249 
250   // Make sure all outgoing deflates are ordered and non-overlapping.
251   auto result = std::adjacent_find(out_deflates->begin(),
252                                    out_deflates->end(),
253                                    [](const BitExtent& a, const BitExtent& b) {
254                                      return (a.offset + a.length) > b.offset;
255                                    });
256   TEST_AND_RETURN_FALSE(result == out_deflates->end());
257   return true;
258 }
259 
260 bool FindAndCompactDeflates(const vector<Extent>& extents,
261                             const vector<BitExtent>& in_deflates,
262                             vector<BitExtent>* out_deflates) {
263   auto found_deflates = FindDeflates(extents, in_deflates);
264   TEST_AND_RETURN_FALSE(CompactDeflates(extents, found_deflates, out_deflates));
265   return true;
266 }
267 
268 bool PreprocessPartitionFiles(const PartitionConfig& part,
269                               vector<FilesystemInterface::File>* result_files,
270                               bool extract_deflates) {
271   // Get the file system files.
272   vector<FilesystemInterface::File> tmp_files;
273   part.fs_interface->GetFiles(&tmp_files);
274   result_files->reserve(tmp_files.size());
275 
276   for (auto& file : tmp_files) {
277     auto is_regular_file = IsRegularFile(file);
278 
279     if (is_regular_file && IsSquashfsImage(part.path, file)) {
280       // Read the image into a file.
281       base::FilePath path;
282       TEST_AND_RETURN_FALSE(base::CreateTemporaryFile(&path));
283       ScopedPathUnlinker old_unlinker(path.value());
284       TEST_AND_RETURN_FALSE(
285           CopyExtentsToFile(part.path, file.extents, path.value(), kBlockSize));
286       // Test if it is actually a Squashfs file.
287       auto sqfs =
288           SquashfsFilesystem::CreateFromFile(path.value(), extract_deflates);
289       if (sqfs) {
290         // It is an squashfs file. Get its files to replace with itself.
291         vector<FilesystemInterface::File> files;
292         sqfs->GetFiles(&files);
293 
294         // Replace squashfs file with its files only if |files| has at least two
295         // files or if it has some deflates (since it is better to replace it to
296         // take advantage of the deflates.)
297         if (files.size() > 1 ||
298             (files.size() == 1 && !files[0].deflates.empty())) {
299           TEST_AND_RETURN_FALSE(RealignSplittedFiles(file, &files));
300           result_files->insert(result_files->end(), files.begin(), files.end());
301           continue;
302         }
303       } else {
304         LOG(WARNING) << "We thought file: " << file.name
305                      << " was a Squashfs file, but it was not.";
306       }
307     }
308 
309     if (is_regular_file && extract_deflates) {
310       // Search for deflates if the file is in zip or gzip format.
311       // .zvoice files may eventually move out of rootfs. If that happens,
312       // remove ".zvoice" (crbug.com/782918).
313       bool is_zip = IsFileExtensions(
314           file.name, {".apk", ".zip", ".jar", ".zvoice", ".apex"});
315       bool is_gzip = IsFileExtensions(file.name, {".gz", ".gzip", ".tgz"});
316       if (is_zip || is_gzip) {
317         brillo::Blob data;
318         TEST_AND_RETURN_FALSE(utils::ReadExtents(
319             part.path,
320             file.extents,
321             &data,
322             kBlockSize * utils::BlocksInExtents(file.extents),
323             kBlockSize));
324         vector<puffin::BitExtent> deflates;
325         if (is_zip) {
326           TEST_AND_RETURN_FALSE(
327               puffin::LocateDeflatesInZipArchive(data, &deflates));
328         } else if (is_gzip) {
329           TEST_AND_RETURN_FALSE(puffin::LocateDeflatesInGzip(data, &deflates));
330         }
331         // Shift the deflate's extent to the offset starting from the beginning
332         // of the current partition; and the delta processor will align the
333         // extents in a continuous buffer later.
334         TEST_AND_RETURN_FALSE(
335             ShiftBitExtentsOverExtents(file.extents, &deflates));
336         file.deflates = std::move(deflates);
337       }
338     }
339 
340     result_files->push_back(file);
341   }
342   return true;
343 }
344 
345 }  // namespace deflate_utils
346 }  // namespace chromeos_update_engine
347