Implement the functions in CowMergeOperations
Implement the function to create an object & validate sequence.
Bug: 162274240
Test: unit tests pass
Change-Id: Id41460a886d94a98e154b222c3401a5f95b9e047
diff --git a/Android.bp b/Android.bp
index 751e355..e5f0dd8 100644
--- a/Android.bp
+++ b/Android.bp
@@ -696,6 +696,7 @@
"payload_generator/fake_filesystem.cc",
"payload_generator/full_update_generator_unittest.cc",
"payload_generator/mapfile_filesystem_unittest.cc",
+ "payload_generator/merge_sequence_generator_unittest.cc",
"payload_generator/payload_file_unittest.cc",
"payload_generator/payload_generation_config_android_unittest.cc",
"payload_generator/payload_generation_config_unittest.cc",
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index 4600efe..2098639 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -202,6 +202,15 @@
}
}
+bool ExtentRanges::OverlapsWithExtent(const Extent& extent) const {
+ for (const auto& entry : extent_set_) {
+ if (ExtentsOverlap(entry, extent)) {
+ return true;
+ }
+ }
+ return false;
+}
+
bool ExtentRanges::ContainsBlock(uint64_t block) const {
auto lower = extent_set_.lower_bound(ExtentForRange(block, 1));
// The block could be on the extent before the one in |lower|.
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
index 62ffff4..68aa27f 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -63,6 +63,9 @@
void AddRanges(const ExtentRanges& ranges);
void SubtractRanges(const ExtentRanges& ranges);
+ // Returns true if the input extent overlaps with the current ExtentRanges.
+ bool OverlapsWithExtent(const Extent& extent) const;
+
// Returns whether the block |block| is in this ExtentRange.
bool ContainsBlock(uint64_t block) const;
diff --git a/payload_generator/merge_sequence_generator.cc b/payload_generator/merge_sequence_generator.cc
index cf73ba3..dd801d6 100644
--- a/payload_generator/merge_sequence_generator.cc
+++ b/payload_generator/merge_sequence_generator.cc
@@ -16,12 +16,77 @@
#include "update_engine/payload_generator/merge_sequence_generator.h"
+#include "update_engine/payload_generator/extent_utils.h"
+
namespace chromeos_update_engine {
+CowMergeOperation CreateCowMergeOperation(const Extent& src_extent,
+ const Extent& dst_extent) {
+ CowMergeOperation ret;
+ ret.set_type(CowMergeOperation::COW_COPY);
+ *ret.mutable_src_extent() = src_extent;
+ *ret.mutable_dst_extent() = dst_extent;
+ return ret;
+}
+
+std::ostream& operator<<(std::ostream& os,
+ const CowMergeOperation& merge_operation) {
+ os << "CowMergeOperation src extent: "
+ << ExtentsToString({merge_operation.src_extent()})
+ << ", dst extent: " << ExtentsToString({merge_operation.dst_extent()});
+ return os;
+}
+
+// The OTA generation guarantees that all blocks in the dst extent will be
+// written only once. So we can use it to order the CowMergeOperation.
+bool operator<(const CowMergeOperation& op1, const CowMergeOperation& op2) {
+ return op1.dst_extent().start_block() < op2.dst_extent().start_block();
+}
+
+bool operator==(const CowMergeOperation& op1, const CowMergeOperation& op2) {
+ return op1.type() == op2.type() && op1.src_extent() == op2.src_extent() &&
+ op1.dst_extent() == op2.dst_extent();
+}
+
std::unique_ptr<MergeSequenceGenerator> MergeSequenceGenerator::Create(
const std::vector<AnnotatedOperation>& aops) {
+ std::vector<CowMergeOperation> sequence;
+ for (const auto& aop : aops) {
+ // Only handle SOURCE_COPY now for the cow size optimization.
+ if (aop.op.type() != InstallOperation::SOURCE_COPY) {
+ continue;
+ }
+ if (aop.op.dst_extents().size() != 1) {
+ std::vector<Extent> out_extents;
+ ExtentsToVector(aop.op.dst_extents(), &out_extents);
+ LOG(ERROR) << "The dst extents for source_copy expects to be contiguous,"
+ << " dst extents: " << ExtentsToString(out_extents);
+ return nullptr;
+ }
+
+ // Split the source extents.
+ size_t used_blocks = 0;
+ for (const auto& src_extent : aop.op.src_extents()) {
+ // The dst_extent in the merge sequence will be a subset of
+ // InstallOperation's dst_extent. This will simplify the OTA -> COW
+ // conversion when we install the payload.
+ Extent dst_extent =
+ ExtentForRange(aop.op.dst_extents(0).start_block() + used_blocks,
+ src_extent.num_blocks());
+ sequence.emplace_back(CreateCowMergeOperation(src_extent, dst_extent));
+ used_blocks += src_extent.num_blocks();
+ }
+
+ if (used_blocks != aop.op.dst_extents(0).num_blocks()) {
+ LOG(ERROR) << "Number of blocks in src extents doesn't equal to the"
+ << " ones in the dst extents, src blocks " << used_blocks
+ << ", dst blocks " << aop.op.dst_extents(0).num_blocks();
+ return nullptr;
+ }
+ }
+
return std::unique_ptr<MergeSequenceGenerator>(
- new MergeSequenceGenerator({}));
+ new MergeSequenceGenerator(sequence));
}
bool MergeSequenceGenerator::FindDependency(
@@ -37,6 +102,21 @@
bool MergeSequenceGenerator::ValidateSequence(
const std::vector<CowMergeOperation>& sequence) {
+ LOG(INFO) << "Validating merge sequence";
+ ExtentRanges visited;
+ for (const auto& op : sequence) {
+ if (visited.OverlapsWithExtent(op.src_extent())) {
+ LOG(ERROR) << "Transfer violates the merge sequence " << op
+ << "Visited extent ranges: ";
+ visited.Dump();
+ return false;
+ }
+
+ CHECK(!visited.OverlapsWithExtent(op.dst_extent()))
+ << "dst extent should write only once.";
+ visited.AddExtent(op.dst_extent());
+ }
+
return true;
}
diff --git a/payload_generator/merge_sequence_generator.h b/payload_generator/merge_sequence_generator.h
index bfc04d9..bc0158e 100644
--- a/payload_generator/merge_sequence_generator.h
+++ b/payload_generator/merge_sequence_generator.h
@@ -29,6 +29,16 @@
#include "update_engine/update_metadata.pb.h"
namespace chromeos_update_engine {
+// Constructs CowMergeOperation from src & dst extents
+CowMergeOperation CreateCowMergeOperation(const Extent& src_extent,
+ const Extent& dst_extent);
+
+// Comparator for CowMergeOperation.
+bool operator<(const CowMergeOperation& op1, const CowMergeOperation& op2);
+bool operator==(const CowMergeOperation& op1, const CowMergeOperation& op2);
+
+std::ostream& operator<<(std::ostream& os,
+ const CowMergeOperation& merge_operation);
// This class takes a list of CowMergeOperations; and sorts them so that no
// read after write will happen by following the sequence. When there is a
@@ -48,6 +58,7 @@
bool Generate(std::vector<CowMergeOperation>* sequence) const;
private:
+ friend class MergeSequenceGeneratorTest;
explicit MergeSequenceGenerator(std::vector<CowMergeOperation> transfers)
: operations_(std::move(transfers)) {}
diff --git a/payload_generator/merge_sequence_generator_unittest.cc b/payload_generator/merge_sequence_generator_unittest.cc
new file mode 100644
index 0000000..83cf78f
--- /dev/null
+++ b/payload_generator/merge_sequence_generator_unittest.cc
@@ -0,0 +1,97 @@
+//
+// Copyright (C) 2020 The Android Open Source Project
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+// http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+//
+
+#include <string>
+#include <vector>
+
+#include <gtest/gtest.h>
+
+#include "update_engine/common/test_utils.h"
+#include "update_engine/payload_consumer/payload_constants.h"
+#include "update_engine/payload_generator/extent_utils.h"
+#include "update_engine/payload_generator/merge_sequence_generator.h"
+
+using chromeos_update_engine::test_utils::FillWithData;
+using std::string;
+using std::vector;
+
+namespace chromeos_update_engine {
+class MergeSequenceGeneratorTest : public ::testing::Test {
+ protected:
+ void VerifyTransfers(MergeSequenceGenerator* generator,
+ const std::vector<CowMergeOperation>& expected) {
+ ASSERT_EQ(expected, generator->operations_);
+ }
+};
+
+TEST_F(MergeSequenceGeneratorTest, Create) {
+ std::vector<AnnotatedOperation> aops{{"file1", {}}, {"file2", {}}};
+ aops[0].op.set_type(InstallOperation::SOURCE_COPY);
+ *aops[0].op.add_src_extents() = ExtentForRange(10, 10);
+ *aops[0].op.add_dst_extents() = ExtentForRange(30, 10);
+
+ aops[1].op.set_type(InstallOperation::SOURCE_COPY);
+ *aops[1].op.add_src_extents() = ExtentForRange(20, 10);
+ *aops[1].op.add_dst_extents() = ExtentForRange(40, 10);
+
+ auto generator = MergeSequenceGenerator::Create(aops);
+ ASSERT_TRUE(generator);
+ std::vector<CowMergeOperation> expected = {
+ CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(30, 10)),
+ CreateCowMergeOperation(ExtentForRange(20, 10), ExtentForRange(40, 10))};
+ VerifyTransfers(generator.get(), expected);
+
+ *aops[1].op.add_src_extents() = ExtentForRange(30, 5);
+ *aops[1].op.add_dst_extents() = ExtentForRange(50, 5);
+ generator = MergeSequenceGenerator::Create(aops);
+ ASSERT_FALSE(generator);
+}
+
+TEST_F(MergeSequenceGeneratorTest, Create_SplitSource) {
+ InstallOperation op;
+ op.set_type(InstallOperation::SOURCE_COPY);
+ *(op.add_src_extents()) = ExtentForRange(2, 3);
+ *(op.add_src_extents()) = ExtentForRange(6, 1);
+ *(op.add_src_extents()) = ExtentForRange(8, 4);
+ *(op.add_dst_extents()) = ExtentForRange(10, 8);
+
+ AnnotatedOperation aop{"file1", op};
+ auto generator = MergeSequenceGenerator::Create({aop});
+ ASSERT_TRUE(generator);
+ std::vector<CowMergeOperation> expected = {
+ CreateCowMergeOperation(ExtentForRange(2, 3), ExtentForRange(10, 3)),
+ CreateCowMergeOperation(ExtentForRange(6, 1), ExtentForRange(13, 1)),
+ CreateCowMergeOperation(ExtentForRange(8, 4), ExtentForRange(14, 4))};
+ VerifyTransfers(generator.get(), expected);
+}
+
+TEST_F(MergeSequenceGeneratorTest, ValidateSequence) {
+ std::vector<CowMergeOperation> transfers = {
+ CreateCowMergeOperation(ExtentForRange(10, 10), ExtentForRange(15, 10)),
+ CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(40, 10)),
+ };
+
+ // Self overlapping
+ ASSERT_TRUE(MergeSequenceGenerator::ValidateSequence(transfers));
+
+ transfers = {
+ CreateCowMergeOperation(ExtentForRange(30, 10), ExtentForRange(20, 10)),
+ CreateCowMergeOperation(ExtentForRange(15, 10), ExtentForRange(10, 10)),
+ };
+ ASSERT_FALSE(MergeSequenceGenerator::ValidateSequence(transfers));
+}
+
+} // namespace chromeos_update_engine