1aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 2aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Copyright (C) 2015 The Android Open Source Project 3aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 4aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Licensed under the Apache License, Version 2.0 (the "License"); 5aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// you may not use this file except in compliance with the License. 6aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// You may obtain a copy of the License at 7aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 8aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// http://www.apache.org/licenses/LICENSE-2.0 9aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 10aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// Unless required by applicable law or agreed to in writing, software 11aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// distributed under the License is distributed on an "AS IS" BASIS, 12aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 13aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// See the License for the specific language governing permissions and 14aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// limitations under the License. 15aea4c1cea20dda7ae7e85fc8924a2d784f70d806Alex Deymo// 1614158570d3995008dc93a628004118b87a6bca01Alex Deymo 1714158570d3995008dc93a628004118b87a6bca01Alex Deymo#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_ 1814158570d3995008dc93a628004118b87a6bca01Alex Deymo#define UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_ 1914158570d3995008dc93a628004118b87a6bca01Alex Deymo 2014158570d3995008dc93a628004118b87a6bca01Alex Deymo#include <string> 2114158570d3995008dc93a628004118b87a6bca01Alex Deymo#include <vector> 2214158570d3995008dc93a628004118b87a6bca01Alex Deymo 233f39d5cc753905874d8d93bef94f857b8808f19eAlex Vakulenko#include <brillo/secure_blob.h> 2414158570d3995008dc93a628004118b87a6bca01Alex Deymo 2514158570d3995008dc93a628004118b87a6bca01Alex Deymo#include "update_engine/payload_generator/annotated_operation.h" 26f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo#include "update_engine/payload_generator/extent_ranges.h" 2714158570d3995008dc93a628004118b87a6bca01Alex Deymo#include "update_engine/payload_generator/payload_generation_config.h" 2814158570d3995008dc93a628004118b87a6bca01Alex Deymo#include "update_engine/update_metadata.pb.h" 2914158570d3995008dc93a628004118b87a6bca01Alex Deymo 3014158570d3995008dc93a628004118b87a6bca01Alex Deymonamespace chromeos_update_engine { 3114158570d3995008dc93a628004118b87a6bca01Alex Deymo 3214158570d3995008dc93a628004118b87a6bca01Alex Deymonamespace diff_utils { 3314158570d3995008dc93a628004118b87a6bca01Alex Deymo 34b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo// Create operations in |aops| to produce all the blocks in the |new_part| 35b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo// partition using the filesystem opened in that PartitionConfig. 36b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo// It uses the files reported by the filesystem in |old_part| and the data 37b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo// blocks in that partition (if available) to determine the best way to compress 38b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo// the new files (REPLACE, REPLACE_BZ, COPY, BSDIFF) and writes any necessary 3955c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// data to |blob_file|. |hard_chunk_blocks| and |soft_chunk_blocks| are the hard 4055c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// and soft chunk limits in number of blocks respectively. The soft chunk limit 4155c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// is used to split MOVE and SOURCE_COPY operations and REPLACE_BZ of zeroed 4255c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// blocks, while the hard limit is used to split a file when generating other 4355c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// operations. A value of -1 in |hard_chunk_blocks| means whole files. 44b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymobool DeltaReadPartition(std::vector<AnnotatedOperation>* aops, 45b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo const PartitionConfig& old_part, 46b42b98db059a12c44110588fc0b3d5f82d32a2f8Alex Deymo const PartitionConfig& new_part, 472d3b2d635e50c6886e285afb86c3187d9e0bd360Alex Deymo ssize_t hard_chunk_blocks, 482d3b2d635e50c6886e285afb86c3187d9e0bd360Alex Deymo size_t soft_chunk_blocks, 49a4073ef63482fd08c3678982f7d153360b088094Alex Deymo const PayloadVersion& version, 50a4073ef63482fd08c3678982f7d153360b088094Alex Deymo BlobFileWriter* blob_file); 5114158570d3995008dc93a628004118b87a6bca01Alex Deymo 52f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// Create operations in |aops| for identical blocks that moved around in the old 53f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// and new partition and also handle zeroed blocks. The old and new partition 54f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// are stored in the |old_part| and |new_part| files and have |old_num_blocks| 55f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// and |new_num_blocks| respectively. The maximum operation size is 56f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// |chunk_blocks| blocks, or unlimited if |chunk_blocks| is -1. The blobs of the 5755c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// produced operations are stored in the |blob_file|. 58f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// The collections |old_visited_blocks| and |new_visited_blocks| state what 59f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// blocks already have operations reading or writing them and only operations 60f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// for unvisited blocks are produced by this function updating both collections 61f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo// with the used blocks. 62f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymobool DeltaMovedAndZeroBlocks(std::vector<AnnotatedOperation>* aops, 63f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo const std::string& old_part, 64f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo const std::string& new_part, 65f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo size_t old_num_blocks, 66f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo size_t new_num_blocks, 672d3b2d635e50c6886e285afb86c3187d9e0bd360Alex Deymo ssize_t chunk_blocks, 68a4073ef63482fd08c3678982f7d153360b088094Alex Deymo const PayloadVersion& version, 698cc502dacbccdab96824d42287f230ce04004784Sen Jiang BlobFileWriter* blob_file, 70f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo ExtentRanges* old_visited_blocks, 71f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo ExtentRanges* new_visited_blocks); 72f0061358b5f741baeeb9177b838b289d2ce318f3Alex Deymo 7314158570d3995008dc93a628004118b87a6bca01Alex Deymo// For a given file |name| append operations to |aops| to produce it in the 7414158570d3995008dc93a628004118b87a6bca01Alex Deymo// |new_part|. The file will be split in chunks of |chunk_blocks| blocks each 7514158570d3995008dc93a628004118b87a6bca01Alex Deymo// or treated as a single chunk if |chunk_blocks| is -1. The file data is 7614158570d3995008dc93a628004118b87a6bca01Alex Deymo// stored in |new_part| in the blocks described by |new_extents| and, if it 7714158570d3995008dc93a628004118b87a6bca01Alex Deymo// exists, the old version exists in |old_part| in the blocks described by 7814158570d3995008dc93a628004118b87a6bca01Alex Deymo// |old_extents|. The operations added to |aops| reference the data blob 7955c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// in the |blob_file|. Returns true on success. 8014158570d3995008dc93a628004118b87a6bca01Alex Deymobool DeltaReadFile(std::vector<AnnotatedOperation>* aops, 8114158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::string& old_part, 8214158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::string& new_part, 8314158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::vector<Extent>& old_extents, 8414158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::vector<Extent>& new_extents, 8514158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::string& name, 862d3b2d635e50c6886e285afb86c3187d9e0bd360Alex Deymo ssize_t chunk_blocks, 87a4073ef63482fd08c3678982f7d153360b088094Alex Deymo const PayloadVersion& version, 88a4073ef63482fd08c3678982f7d153360b088094Alex Deymo BlobFileWriter* blob_file); 8914158570d3995008dc93a628004118b87a6bca01Alex Deymo 9014158570d3995008dc93a628004118b87a6bca01Alex Deymo// Reads the blocks |old_extents| from |old_part| (if it exists) and the 9114158570d3995008dc93a628004118b87a6bca01Alex Deymo// |new_extents| from |new_part| and determines the smallest way to encode 9214158570d3995008dc93a628004118b87a6bca01Alex Deymo// this |new_extents| for the diff. It stores necessary data in |out_data| and 9314158570d3995008dc93a628004118b87a6bca01Alex Deymo// fills in |out_op|. If there's no change in old and new files, it creates a 94a4073ef63482fd08c3678982f7d153360b088094Alex Deymo// MOVE or SOURCE_COPY operation. If there is a change, the smallest of the 95a4073ef63482fd08c3678982f7d153360b088094Alex Deymo// operations allowed in the given |version| (REPLACE, REPLACE_BZ, BSDIFF, 96a4073ef63482fd08c3678982f7d153360b088094Alex Deymo// SOURCE_BSDIFF or IMGDIFF) wins. 97a4073ef63482fd08c3678982f7d153360b088094Alex Deymo// |new_extents| must not be empty. Returns true on success. 9814158570d3995008dc93a628004118b87a6bca01Alex Deymobool ReadExtentsToDiff(const std::string& old_part, 9914158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::string& new_part, 10014158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::vector<Extent>& old_extents, 10114158570d3995008dc93a628004118b87a6bca01Alex Deymo const std::vector<Extent>& new_extents, 102a4073ef63482fd08c3678982f7d153360b088094Alex Deymo const PayloadVersion& version, 1033f39d5cc753905874d8d93bef94f857b8808f19eAlex Vakulenko brillo::Blob* out_data, 104a4073ef63482fd08c3678982f7d153360b088094Alex Deymo InstallOperation* out_op); 10514158570d3995008dc93a628004118b87a6bca01Alex Deymo 10655c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// Runs the bsdiff or imgdiff tool in |diff_path| on two files and returns the 10755c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang// resulting delta in |out|. Returns true on success. 10855c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiangbool DiffFiles(const std::string& diff_path, 10955c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang const std::string& old_file, 11055c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang const std::string& new_file, 11155c4f9ba7f5c59e3345f2c1869464433ffa8dc2bSen Jiang brillo::Blob* out); 11214158570d3995008dc93a628004118b87a6bca01Alex Deymo 113726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo// Generates the best allowed full operation to produce |new_data|. The allowed 114726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo// operations are based on |payload_version|. The operation blob will be stored 115726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo// in |out_blob| and the resulting operation type in |out_type|. Returns whether 116726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo// a valid full operation was generated. 117726aeca1c665910593761a1990ee50f22d98f53fAlex Deymobool GenerateBestFullOperation(const brillo::Blob& new_data, 118726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo const PayloadVersion& version, 119726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo brillo::Blob* out_blob, 120726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo InstallOperation_Type* out_type); 121726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo 122726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo// Returns whether op_type is one of the REPLACE full operations. 123726aeca1c665910593761a1990ee50f22d98f53fAlex Deymobool IsAReplaceOperation(InstallOperation_Type op_type); 124726aeca1c665910593761a1990ee50f22d98f53fAlex Deymo 12514158570d3995008dc93a628004118b87a6bca01Alex Deymo// Returns true if |op| is a no-op operation that doesn't do any useful work 12614158570d3995008dc93a628004118b87a6bca01Alex Deymo// (e.g., a move operation that copies blocks onto themselves). 127a12ee11c78ac6d7c2605921a4006b6a7416e0c35Alex Deymobool IsNoopOperation(const InstallOperation& op); 12814158570d3995008dc93a628004118b87a6bca01Alex Deymo 12914158570d3995008dc93a628004118b87a6bca01Alex Deymo// Filters all the operations that are no-op, maintaining the relative order 13014158570d3995008dc93a628004118b87a6bca01Alex Deymo// of the rest of the operations. 13114158570d3995008dc93a628004118b87a6bca01Alex Deymovoid FilterNoopOperations(std::vector<AnnotatedOperation>* ops); 13214158570d3995008dc93a628004118b87a6bca01Alex Deymo 13314158570d3995008dc93a628004118b87a6bca01Alex Deymobool InitializePartitionInfo(const PartitionConfig& partition, 13414158570d3995008dc93a628004118b87a6bca01Alex Deymo PartitionInfo* info); 13514158570d3995008dc93a628004118b87a6bca01Alex Deymo 1363b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo// Compare two AnnotatedOperations by the start block of the first Extent in 1373b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo// their destination extents. 1383b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymobool CompareAopsByDestination(AnnotatedOperation first_aop, 1393b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo AnnotatedOperation second_aop); 1403b2c7d0e6d859e6fc75c82b3417f87cf5968a49dAlex Deymo 141dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748Sen Jiang// Returns whether the filesystem is an ext[234] filesystem. In case of failure, 142dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748Sen Jiang// such as if the file |device| doesn't exists or can't be read, it returns 143dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748Sen Jiang// false. 144dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748Sen Jiangbool IsExtFilesystem(const std::string& device); 145dcbc0ae6a5c48b40a1bc7d3c2ed62ec2a9fe7748Sen Jiang 146c4ad1ebc33abc088aca2909ba5cbaf7ae5e5659fTianjie Xu// Returns the max number of threads to process the files(chunks) in parallel. 147c4ad1ebc33abc088aca2909ba5cbaf7ae5e5659fTianjie Xusize_t GetMaxThreads(); 148c4ad1ebc33abc088aca2909ba5cbaf7ae5e5659fTianjie Xu 14914158570d3995008dc93a628004118b87a6bca01Alex Deymo} // namespace diff_utils 15014158570d3995008dc93a628004118b87a6bca01Alex Deymo 15114158570d3995008dc93a628004118b87a6bca01Alex Deymo} // namespace chromeos_update_engine 15214158570d3995008dc93a628004118b87a6bca01Alex Deymo 15314158570d3995008dc93a628004118b87a6bca01Alex Deymo#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_DELTA_DIFF_UTILS_H_ 154