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 
29 namespace 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.
36 class 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,
57                          off_t initial_byte_offset,
58                          size_t num_blocks,
59                          std::vector<BlockId>* block_ids);
60 
61  private:
62   FRIEND_TEST(BlockMappingTest, BlocksAreNotKeptInMemory);
63 
64   // Add a single block passed in |block_data|. If |fd| is not -1, the block
65   // can be discarded to save RAM and retrieved later from |fd| at the position
66   // |byte_offset|.
67   BlockId AddBlock(int fd, off_t byte_offset, const brillo::Blob& block_data);
68 
69   size_t block_size_;
70 
71   BlockId used_block_ids{0};
72 
73   // The UniqueBlock represents the data of a block associated to a unique
74   // block id.
75   struct UniqueBlock {
76     brillo::Blob block_data;
77 
78     // The block id assigned to this unique block.
79     BlockId block_id;
80 
81     // The location on this unique block on disk (if not cached in block_data).
82     int fd{-1};
83     off_t byte_offset{0};
84 
85     // Number of times we have seen this data block. Used for caching.
86     uint32_t times_read{0};
87 
88     // Compares the UniqueBlock data with the other_block data and stores if
89     // they are equal in |equals|. Returns whether there was an error reading
90     // the block from disk while comparing it.
91     bool CompareData(const brillo::Blob& other_block, bool* equals);
92   };
93 
94   // A mapping from hash values to possible block ids.
95   std::map<size_t, std::vector<UniqueBlock>> mapping_;
96 };
97 
98 // Maps the blocks of the old and new partitions |old_part| and |new_part| whose
99 // size in bytes are |old_size| and |new_size| into block ids where two blocks
100 // with the same data will have the same block id and vice versa, regardless of
101 // the partition they are on.
102 // The block ids number 0 corresponds to the block with all zeros, but any
103 // other block id number is assigned randomly.
104 bool MapPartitionBlocks(const std::string& old_part,
105                         const std::string& new_part,
106                         size_t old_size,
107                         size_t new_size,
108                         size_t block_size,
109                         std::vector<BlockMapping::BlockId>* old_block_ids,
110                         std::vector<BlockMapping::BlockId>* new_block_ids);
111 
112 }  // namespace chromeos_update_engine
113 
114 #endif  // UPDATE_ENGINE_PAYLOAD_GENERATOR_BLOCK_MAPPING_H_
115