block_mapping.h 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#ifndef UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
18#define UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
19
20#include <map>
21#include <string>
22#include <vector>
23
24#include <brillo/secure_blob.h>
25#include <gtest/gtest_prod.h>  // for FRIEND_TEST
26
27#include "update_engine/payload_generator/payload_generation_config.h"
28
29namespace chromeos_update_engine {
30
31// BlockMapping allows to map data blocks (brillo::Blobs of block_size size)
32// into unique integer values called "block ids". This mapping differs from a
33// hash function in that two blocks with the same data will have the same id but
34// also two blocks with the same id will have the same data. This is only valid
35// in the context of the same BlockMapping instance.
36class BlockMapping {
37 public:
38  using BlockId = int64_t;
39
40  explicit BlockMapping(size_t block_size) : block_size_(block_size) {}
41
42  // Add a single data block to the mapping. Returns its unique block id.
43  // In case of error returns -1.
44  BlockId AddBlock(const brillo::Blob& block_data);
45
46  // Add a block from disk reading it from the file descriptor |fd| from the
47  // offset in bytes |byte_offset|. The data block may or may not be cached, so
48  // the file descriptor must be available until the BlockMapping is destroyed.
49  // Returns the unique block id of the added block or -1 in case of error.
50  BlockId AddDiskBlock(int fd, off_t byte_offset);
51
52  // This is a helper method to add |num_blocks| contiguous blocks reading them
53  // from the file descriptor |fd| starting at offset |initial_byte_offset|.
54  // Returns whether it succeeded to add all the disk blocks and stores in
55  // |block_ids| the block id for each one of the added blocks.
56  bool AddManyDiskBlocks(int fd, off_t initial_byte_offset, size_t num_blocks,
57                         std::vector<BlockId>* block_ids);
58
59 private:
60  FRIEND_TEST(BlockMappingTest, BlocksAreNotKeptInMemory);
61
62  // Add a single block passed in |block_data|. If |fd| is not -1, the block
63  // can be discarded to save RAM and retrieved later from |fd| at the position
64  // |byte_offset|.
65  BlockId AddBlock(int fd, off_t byte_offset, const brillo::Blob& block_data);
66
67  size_t block_size_;
68
69  BlockId used_block_ids{0};
70
71  // The UniqueBlock represents the data of a block associated to a unique
72  // block id.
73  struct UniqueBlock {
74    brillo::Blob block_data;
75
76    // The block id assigned to this unique block.
77    BlockId block_id;
78
79    // The location on this unique block on disk (if not cached in block_data).
80    int fd{-1};
81    off_t byte_offset{0};
82
83    // Number of times we have seen this data block. Used for caching.
84    uint32_t times_read{0};
85
86    // Compares the UniqueBlock data with the other_block data and stores if
87    // they are equal in |equals|. Returns whether there was an error reading
88    // the block from disk while comparing it.
89    bool CompareData(const brillo::Blob& other_block, bool* equals);
90  };
91
92  // A mapping from hash values to possible block ids.
93  std::map<size_t, std::vector<UniqueBlock>> mapping_;
94};
95
96// Maps the blocks of the old and new partitions |old_part| and |new_part| whose
97// size in bytes are |old_size| and |new_size| into block ids where two blocks
98// with the same data will have the same block id and vice versa, regardless of
99// the partition they are on.
100// The block ids number 0 corresponds to the block with all zeros, but any
101// other block id number is assigned randomly.
102bool MapPartitionBlocks(const std::string& old_part,
103                        const std::string& new_part,
104                        size_t old_size,
105                        size_t new_size,
106                        size_t block_size,
107                        std::vector<BlockMapping::BlockId>* old_block_ids,
108                        std::vector<BlockMapping::BlockId>* new_block_ids);
109
110}  // namespace chromeos_update_engine
111
112#endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
113