1 //
2 // Copyright (C) 2021 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 #include <gtest/gtest.h>
18 #include <optional>
19 #include <vector>
20
21 #include "update_engine/payload_consumer/extent_map.h"
22 #include "update_engine/payload_generator/extent_ranges.h"
23 #include "update_engine/payload_generator/extent_utils.h"
24
25 namespace chromeos_update_engine {
26
27 class ExtentMapTest : public ::testing::Test {
28 public:
29 ExtentMap<int> map_;
30 };
31
TEST_F(ExtentMapTest,QueryExactExtent)32 TEST_F(ExtentMapTest, QueryExactExtent) {
33 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
34 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
35 auto ret = map_.Get(ExtentForRange(0, 5));
36 ASSERT_NE(ret, std::nullopt);
37 ASSERT_EQ(*ret, 7);
38 }
39
TEST_F(ExtentMapTest,QuerySubset)40 TEST_F(ExtentMapTest, QuerySubset) {
41 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
42 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
43 auto ret = map_.Get(ExtentForRange(1, 2));
44 ASSERT_EQ(ret, std::nullopt);
45 }
46
TEST_F(ExtentMapTest,QueryTouching)47 TEST_F(ExtentMapTest, QueryTouching) {
48 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
49 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 1));
50 auto ret = map_.Get(ExtentForRange(3, 2));
51 ASSERT_EQ(ret, std::nullopt);
52 ret = map_.Get(ExtentForRange(4, 1));
53 ASSERT_EQ(ret, std::nullopt);
54 ret = map_.Get(ExtentForRange(5, 5));
55 ASSERT_EQ(ret, std::nullopt);
56 ret = map_.Get(ExtentForRange(5, 6));
57 ASSERT_EQ(ret, std::nullopt);
58 }
59
TEST_F(ExtentMapTest,GetIntersectingExtents)60 TEST_F(ExtentMapTest, GetIntersectingExtents) {
61 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
62 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 7));
63 auto ret = std::vector<Extent>{};
64 ret = map_.GetIntersectingExtents(ExtentForRange(2, 10));
65 ASSERT_EQ(ret.size(), 2U);
66 ASSERT_EQ(ret[0].start_block(), 2U);
67 ASSERT_EQ(ret[0].num_blocks(), 3U);
68
69 ASSERT_EQ(ret[1].start_block(), 10U);
70 ASSERT_EQ(ret[1].num_blocks(), 2U);
71
72 ret = map_.GetIntersectingExtents(ExtentForRange(2, 17));
73 ASSERT_EQ(ret.size(), 2U);
74 ASSERT_EQ(ret[0].start_block(), 2U);
75 ASSERT_EQ(ret[0].num_blocks(), 3U);
76
77 ASSERT_EQ(ret[1].start_block(), 10U);
78 ASSERT_EQ(ret[1].num_blocks(), 5U);
79
80 ret = map_.GetIntersectingExtents(ExtentForRange(2, 2));
81 ASSERT_EQ(ret, std::vector<Extent>{ExtentForRange(2, 2)});
82
83 ret = map_.GetIntersectingExtents(ExtentForRange(10, 5));
84 ASSERT_EQ(ret, std::vector<Extent>{ExtentForRange(10, 5)});
85
86 ASSERT_TRUE(map_.AddExtent(ExtentForRange(20, 5), 7));
87 ret = map_.GetIntersectingExtents(ExtentForRange(0, 30));
88 ASSERT_EQ(ret.size(), 3U);
89 ASSERT_EQ(ret[0].start_block(), 0U);
90 ASSERT_EQ(ret[0].num_blocks(), 5U);
91
92 ASSERT_EQ(ret[1].start_block(), 10U);
93 ASSERT_EQ(ret[1].num_blocks(), 5U);
94
95 ASSERT_EQ(ret[2].start_block(), 20U);
96 ASSERT_EQ(ret[2].num_blocks(), 5U);
97 }
98
TEST_F(ExtentMapTest,GetNonIntersectingExtents)99 TEST_F(ExtentMapTest, GetNonIntersectingExtents) {
100 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
101 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 7));
102 ASSERT_TRUE(map_.AddExtent(ExtentForRange(20, 5), 7));
103
104 auto ret = std::vector<Extent>{};
105 ret = map_.GetNonIntersectingExtents(ExtentForRange(2, 13));
106
107 ASSERT_EQ(ret.size(), 1U);
108 ASSERT_EQ(ret[0].start_block(), 5U);
109 ASSERT_EQ(ret[0].num_blocks(), 5U);
110
111 ret = map_.GetNonIntersectingExtents(ExtentForRange(7, 20));
112 ASSERT_EQ(ret.size(), 3U);
113 ASSERT_EQ(ret[0].start_block(), 7U);
114 ASSERT_EQ(ret[0].num_blocks(), 3U);
115
116 ASSERT_EQ(ret[1].start_block(), 15U);
117 ASSERT_EQ(ret[1].num_blocks(), 5U);
118
119 ASSERT_EQ(ret[2].start_block(), 25U);
120 ASSERT_EQ(ret[2].num_blocks(), 2U);
121 }
122
TEST_F(ExtentMapTest,GetSameStartBlock)123 TEST_F(ExtentMapTest, GetSameStartBlock) {
124 ASSERT_TRUE(map_.AddExtent(ExtentForRange(0, 5), 7));
125 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 12));
126
127 const auto ret = map_.Get(ExtentForRange(0, 10));
128 // ASSERT_FALSE(ret.has_value()) << ret.value() won't work, because when |ret|
129 // doesn't have value, the part after '<<' after still evaluated, resulting in
130 // undefined behavior.
131 if (ret.has_value()) {
132 FAIL() << ret.value();
133 }
134 }
135
TEST_F(ExtentMapTest,GetTouchingExtents)136 TEST_F(ExtentMapTest, GetTouchingExtents) {
137 ASSERT_TRUE(map_.AddExtent(ExtentForRange(5, 5), 7));
138 ASSERT_TRUE(map_.AddExtent(ExtentForRange(10, 5), 12));
139 const auto ret = map_.Get(ExtentForRange(5, 10));
140 if (ret.has_value()) {
141 ASSERT_FALSE(ret.has_value()) << ret.value();
142 }
143 const auto extents = map_.GetIntersectingExtents(ExtentForRange(0, 20));
144 ASSERT_GT(extents.size(), 0UL);
145 ASSERT_EQ(extents.size(), 2UL)
146 << "Expecting unmerged extents [5-9] and [10-14], actual: " << extents;
147 ASSERT_EQ(extents[0], ExtentForRange(5, 5));
148 ASSERT_EQ(extents[1], ExtentForRange(10, 5));
149 }
150
151 } // namespace chromeos_update_engine
152