| // |
| // 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 <algorithm> |
| #include <array> |
| #include <initializer_list> |
| |
| #include <gtest/gtest.h> |
| |
| #include "update_engine/common/cow_operation_convert.h" |
| #include "update_engine/payload_generator/extent_ranges.h" |
| #include "update_engine/update_metadata.pb.h" |
| |
| namespace chromeos_update_engine { |
| using OperationList = ::google::protobuf::RepeatedPtrField< |
| ::chromeos_update_engine::InstallOperation>; |
| using MergeOplist = ::google::protobuf::RepeatedPtrField< |
| ::chromeos_update_engine::CowMergeOperation>; |
| |
| std::ostream& operator<<(std::ostream& out, CowOperation::Type op) { |
| switch (op) { |
| case CowOperation::Type::CowCopy: |
| out << "CowCopy"; |
| break; |
| case CowOperation::Type::CowReplace: |
| out << "CowReplace"; |
| break; |
| default: |
| out << op; |
| break; |
| } |
| return out; |
| } |
| |
| std::ostream& operator<<(std::ostream& out, const CowOperation& c) { |
| out << "{" << c.op << ", " << c.src_block << ", " << c.dst_block << ", " |
| << c.block_count << "}"; |
| return out; |
| } |
| |
| class CowOperationConvertTest : public testing::Test { |
| public: |
| void VerifyCowMergeOp(const std::vector<CowOperation>& cow_ops) { |
| // Build a set of all extents covered by InstallOps. |
| ExtentRanges src_extent_set; |
| ExtentRanges dst_extent_set; |
| for (auto&& op : operations_) { |
| src_extent_set.AddRepeatedExtents(op.src_extents()); |
| dst_extent_set.AddRepeatedExtents(op.dst_extents()); |
| } |
| ExtentRanges modified_extents; |
| for (auto&& cow_op : cow_ops) { |
| if (cow_op.op == CowOperation::CowCopy) { |
| for (size_t i = 0; i < cow_op.block_count; i++) { |
| ASSERT_TRUE(src_extent_set.ContainsBlock(cow_op.src_block + i)); |
| // converted operations should be conflict free. |
| ASSERT_FALSE(modified_extents.ContainsBlock(cow_op.src_block + i)) |
| << "SOURCE_COPY operation " << cow_op |
| << " read from a modified block"; |
| } |
| } |
| for (size_t i = 0; i < cow_op.block_count; i++) { |
| ASSERT_TRUE(dst_extent_set.ContainsBlock(cow_op.dst_block + i)); |
| } |
| dst_extent_set.SubtractExtent( |
| ExtentForRange(cow_op.dst_block, cow_op.block_count)); |
| modified_extents.AddExtent( |
| ExtentForRange(cow_op.dst_block, cow_op.block_count)); |
| } |
| // The generated CowOps should cover all extents in InstallOps. |
| ASSERT_EQ(dst_extent_set.blocks(), 0UL); |
| // It's possible that src_extent_set is non-empty, because some operations |
| // will be converted to CowReplace, and we don't count the source extent for |
| // those. |
| } |
| OperationList operations_; |
| MergeOplist merge_operations_; |
| }; |
| |
| void AddOperation(OperationList* operations, |
| ::chromeos_update_engine::InstallOperation_Type op_type, |
| std::initializer_list<std::array<int, 2>> src_extents, |
| std::initializer_list<std::array<int, 2>> dst_extents) { |
| auto&& op = operations->Add(); |
| op->set_type(op_type); |
| for (const auto& extent : src_extents) { |
| *op->add_src_extents() = ExtentForRange(extent[0], extent[1]); |
| } |
| for (const auto& extent : dst_extents) { |
| *op->add_dst_extents() = ExtentForRange(extent[0], extent[1]); |
| } |
| } |
| |
| void AddMergeOperation(MergeOplist* operations, |
| ::chromeos_update_engine::CowMergeOperation_Type op_type, |
| std::array<int, 2> src_extent, |
| std::array<int, 2> dst_extent) { |
| auto&& op = operations->Add(); |
| op->set_type(op_type); |
| *op->mutable_src_extent() = ExtentForRange(src_extent[0], src_extent[1]); |
| *op->mutable_dst_extent() = ExtentForRange(dst_extent[0], dst_extent[1]); |
| } |
| |
| TEST_F(CowOperationConvertTest, NoConflict) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| ASSERT_EQ(cow_ops.size(), 3UL); |
| ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| })); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, CowReplace) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{0, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{30, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{20, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{0, 1}}, {{10, 1}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {30, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {20, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {0, 1}, {10, 1}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| ASSERT_EQ(cow_ops.size(), 4UL); |
| // Expect 3 COW_COPY and 1 COW_REPLACE |
| ASSERT_EQ(std::count_if(cow_ops.begin(), |
| cow_ops.end(), |
| [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| }), |
| 3); |
| ASSERT_EQ(std::count_if(cow_ops.begin(), |
| cow_ops.end(), |
| [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowReplace; |
| }), |
| 1); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, ReOrderSourceCopy) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{30, 1}}, {{20, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {30, 1}, {20, 1}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| ASSERT_EQ(cow_ops.size(), 3UL); |
| // Expect 3 COW_COPY |
| ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| })); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, InterleavingSrcExtent) { |
| AddOperation(&operations_, |
| InstallOperation::SOURCE_COPY, |
| {{30, 5}, {35, 5}}, |
| {{20, 10}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{20, 1}}, {{10, 1}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{10, 1}}, {{0, 1}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {10, 1}, {0, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {20, 1}, {10, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {30, 5}, {20, 5}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {35, 5}, {25, 5}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| // Expect 4 COW_COPY |
| ASSERT_EQ(cow_ops.size(), 12UL); |
| ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| })); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, SelfOverlappingOperation) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{20, 10}}, {{25, 10}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {20, 10}, {25, 10}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| // Expect 10 COW_COPY |
| ASSERT_EQ(cow_ops.size(), 10UL); |
| ASSERT_TRUE(std::all_of(cow_ops.begin(), cow_ops.end(), [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| })); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, CowReplaceCoalesce) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{30, 10}}, {{0, 10}}); |
| |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {30, 1}, {0, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {31, 1}, {1, 1}); |
| AddMergeOperation( |
| &merge_operations_, CowMergeOperation::COW_COPY, {32, 1}, {2, 1}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| for (const auto& op : cow_ops) { |
| LOG(INFO) << op; |
| } |
| ASSERT_EQ(cow_ops.size(), 4UL); |
| // Expect 3 COW_COPY and 1 COW_REPLACE |
| ASSERT_EQ(std::count_if(cow_ops.begin(), |
| cow_ops.end(), |
| [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowCopy; |
| }), |
| 3); |
| ASSERT_EQ(std::count_if(cow_ops.begin(), |
| cow_ops.end(), |
| [](auto&& cow_op) { |
| return cow_op.op == CowOperation::CowReplace; |
| }), |
| 1); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| TEST_F(CowOperationConvertTest, CowReplaceDifferenceSrc) { |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{30, 10}}, {{0, 10}}); |
| AddOperation( |
| &operations_, InstallOperation::SOURCE_COPY, {{100, 10}}, {{10, 10}}); |
| |
| auto cow_ops = ConvertToCowOperations(operations_, merge_operations_); |
| for (const auto& op : cow_ops) { |
| LOG(INFO) << op; |
| } |
| ASSERT_EQ(cow_ops.size(), 2UL); |
| // |src_block| matters. Even for ReplaceOperation. |
| // As update_engine still need to know where the data come from. |
| ASSERT_EQ(cow_ops[0].op, CowOperation::CowReplace); |
| ASSERT_EQ(cow_ops[0].src_block, 30UL); |
| ASSERT_EQ(cow_ops[0].dst_block, 0UL); |
| ASSERT_EQ(cow_ops[0].block_count, 10UL); |
| |
| ASSERT_EQ(cow_ops[1].op, CowOperation::CowReplace); |
| ASSERT_EQ(cow_ops[1].src_block, 100UL); |
| ASSERT_EQ(cow_ops[1].dst_block, 10UL); |
| ASSERT_EQ(cow_ops[1].block_count, 10UL); |
| VerifyCowMergeOp(cow_ops); |
| } |
| |
| } // namespace chromeos_update_engine |