1 //
2 // Copyright (C) 2020 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_MERGE_SEQUENCE_GENERATOR_H_
18 #define UPDATE_ENGINE_PAYLOAD_GENERATOR_MERGE_SEQUENCE_GENERATOR_H_
19
20 #include <map>
21 #include <memory>
22 #include <set>
23 #include <utility>
24 #include <vector>
25
26 #include "update_engine/payload_generator/annotated_operation.h"
27 #include "update_engine/update_metadata.pb.h"
28
29 namespace chromeos_update_engine {
30 // Constructs CowMergeOperation from src & dst extents
31 CowMergeOperation CreateCowMergeOperation(const Extent& src_extent,
32 const Extent& dst_extent,
33 CowMergeOperation::Type op_type,
34 uint32_t src_offset = 0);
35
36 // Comparator for CowMergeOperation.
37 bool operator<(const CowMergeOperation& op1, const CowMergeOperation& op2);
38 bool operator==(const CowMergeOperation& op1, const CowMergeOperation& op2);
39
40 std::ostream& operator<<(std::ostream& os,
41 const CowMergeOperation& merge_operation);
42
43 // This class takes a list of CowMergeOperations; and sorts them so that no
44 // read after write will happen by following the sequence. When there is a
45 // cycle, we will omit some operations in the list. Therefore, the result
46 // sequence may not contain all blocks in the input list.
47
48 template <typename T>
Sort(T && container)49 T&& Sort(T&& container) {
50 std::sort(container.begin(), container.end());
51 return container;
52 }
53
54 class MergeSequenceGenerator {
55 public:
56 // Creates an object from a list of OTA InstallOperations. Returns nullptr
57 // on failure.
58 static std::unique_ptr<MergeSequenceGenerator> Create(
59 const std::vector<AnnotatedOperation>& aops,
60 std::string_view partition_name = "");
MergeSequenceGenerator(std::vector<CowMergeOperation> transfers,std::string_view partition_name)61 explicit MergeSequenceGenerator(std::vector<CowMergeOperation> transfers,
62 std::string_view partition_name)
63 : operations_(std::move(Sort(transfers))),
64 merge_after_(FindDependency(operations_)),
65 partition_name_(partition_name) {}
66 // Checks that no read after write happens in the given sequence.
67 static bool ValidateSequence(const std::vector<CowMergeOperation>& sequence);
68
69 // Generates a merge sequence from |operations_|, puts the result in
70 // |sequence|. Returns false on failure.
71 bool Generate(std::vector<CowMergeOperation>* sequence) const;
72
GetOperations()73 const std::vector<CowMergeOperation>& GetOperations() const {
74 return operations_;
75 }
76 const std::map<CowMergeOperation, std::set<CowMergeOperation>>&
GetDependencyMap()77 GetDependencyMap() const {
78 return merge_after_;
79 }
80
81 private:
82 friend class MergeSequenceGeneratorTest;
83
84 // For a given merge operation, finds all the operations that should merge
85 // after myself. Put the result in |merge_after|. |operations| must be sorted
86 static std::map<CowMergeOperation, std::set<CowMergeOperation>>
87 FindDependency(const std::vector<CowMergeOperation>& operations);
88 // The list of CowMergeOperations to sort.
89 const std::vector<CowMergeOperation> operations_;
90 const std::map<CowMergeOperation, std::set<CowMergeOperation>> merge_after_;
91 const std::string_view partition_name_;
92 };
93
94 void SplitSelfOverlapping(const Extent& src_extent,
95 const Extent& dst_extent,
96 std::vector<CowMergeOperation>* sequence);
97
98 } // namespace chromeos_update_engine
99 #endif
100