block_mapping.cc revision 3f39d5cc753905874d8d93bef94f857b8808f19e 
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/utils.h"
28
29using std::string;
30using std::vector;
31
32namespace {
33
34size_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
41namespace chromeos_update_engine {
42
43BlockMapping::BlockId BlockMapping::AddBlock(const brillo::Blob& block_data) {
44  return AddBlock(-1, 0, block_data);
45}
46
47BlockMapping::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
57bool BlockMapping::AddManyDiskBlocks(int fd,
58                                     off_t initial_byte_offset,
59                                     size_t num_blocks,
60                                     std::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
71BlockMapping::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
113bool 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
139bool 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