1 // 2 // Copyright (C) 2015 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/block_mapping.h" 18 19 #include <fcntl.h> 20 #include <sys/stat.h> 21 #include <sys/types.h> 22 23 #include <functional> 24 #include <string> 25 #include <vector> 26 27 #include "update_engine/common/utils.h" 28 29 using std::string; 30 using std::vector; 31 32 namespace { 33 34 size_t HashValue(const brillo::Blob& blob) { 35 std::hash<string> hash_fn; 36 return hash_fn(string(blob.begin(), blob.end())); 37 } 38 39 } // namespace 40 41 namespace chromeos_update_engine { 42 43 BlockMapping::BlockId BlockMapping::AddBlock(const brillo::Blob& block_data) { 44 return AddBlock(-1, 0, block_data); 45 } 46 47 BlockMapping::BlockId BlockMapping::AddDiskBlock(int fd, off_t byte_offset) { 48 brillo::Blob blob(block_size_); 49 ssize_t bytes_read = 0; 50 if (!utils::PReadAll(fd, blob.data(), block_size_, byte_offset, &bytes_read)) 51 return -1; 52 if (static_cast<size_t>(bytes_read) != block_size_) 53 return -1; 54 return AddBlock(fd, byte_offset, blob); 55 } 56 57 bool BlockMapping::AddManyDiskBlocks(int fd, 58 off_t initial_byte_offset, 59 size_t num_blocks, 60 vector<BlockId>* block_ids) { 61 bool ret = true; 62 block_ids->resize(num_blocks); 63 for (size_t block = 0; block < num_blocks; block++) { 64 (*block_ids)[block] = AddDiskBlock( 65 fd, initial_byte_offset + block * block_size_); 66 ret = ret && (*block_ids)[block] != -1; 67 } 68 return ret; 69 } 70 71 BlockMapping::BlockId BlockMapping::AddBlock(int fd, 72 off_t byte_offset, 73 const brillo::Blob& block_data) { 74 if (block_data.size() != block_size_) 75 return -1; 76 size_t h = HashValue(block_data); 77 78 // We either reuse a UniqueBlock or create a new one. If we need a new 79 // UniqueBlock it could also be part of a new or existing bucket (if there is 80 // a hash collision). 81 vector<UniqueBlock> *bucket = nullptr; 82 83 auto mapping_it = mapping_.find(h); 84 if (mapping_it == mapping_.end()) { 85 bucket = &mapping_[h]; 86 } else { 87 for (UniqueBlock& existing_block : mapping_it->second) { 88 bool equals = false; 89 if (!existing_block.CompareData(block_data, &equals)) 90 return -1; 91 if (equals) 92 return existing_block.block_id; 93 } 94 bucket = &mapping_it->second; 95 } 96 97 // No existing block was found at this point, so we create and fill in a new 98 // one. 99 bucket->emplace_back(); 100 UniqueBlock *new_ublock = &bucket->back(); 101 102 new_ublock->times_read = 1; 103 new_ublock->fd = fd; 104 new_ublock->byte_offset = byte_offset; 105 new_ublock->block_id = used_block_ids++; 106 // We need to cache blocks that are not referencing any disk location. 107 if (fd == -1) 108 new_ublock->block_data = block_data; 109 110 return new_ublock->block_id; 111 } 112 113 bool BlockMapping::UniqueBlock::CompareData(const brillo::Blob& other_block, 114 bool* equals) { 115 if (!block_data.empty()) { 116 *equals = block_data == other_block; 117 return true; 118 } 119 const size_t block_size = other_block.size(); 120 brillo::Blob blob(block_size); 121 ssize_t bytes_read = 0; 122 if (!utils::PReadAll(fd, blob.data(), block_size, byte_offset, &bytes_read)) 123 return false; 124 if (static_cast<size_t>(bytes_read) != block_size) 125 return false; 126 *equals = blob == other_block; 127 128 // We increase the number of times we had to read this block from disk and 129 // we cache this block based on that. This caching method is optimized for 130 // the common use case of having two partitions that share blocks between them 131 // but have few repeated blocks inside each partition, such as the block 132 // with all zeros or duplicated files. 133 times_read++; 134 if (times_read > 3) 135 block_data = std::move(blob); 136 return true; 137 } 138 139 bool MapPartitionBlocks(const string& old_part, 140 const string& new_part, 141 size_t old_size, 142 size_t new_size, 143 size_t block_size, 144 vector<BlockMapping::BlockId>* old_block_ids, 145 vector<BlockMapping::BlockId>* new_block_ids) { 146 BlockMapping mapping(block_size); 147 if (mapping.AddBlock(brillo::Blob(block_size, '\0')) != 0) 148 return false; 149 int old_fd = HANDLE_EINTR(open(old_part.c_str(), O_RDONLY)); 150 int new_fd = HANDLE_EINTR(open(new_part.c_str(), O_RDONLY)); 151 ScopedFdCloser old_fd_closer(&old_fd); 152 ScopedFdCloser new_fd_closer(&new_fd); 153 154 TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks( 155 old_fd, 0, old_size / block_size, old_block_ids)); 156 TEST_AND_RETURN_FALSE(mapping.AddManyDiskBlocks( 157 new_fd, 0, new_size / block_size, new_block_ids)); 158 return true; 159 } 160 161 } // namespace chromeos_update_engine 162
