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