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