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