Add Extent map
When installing OTA, we stream operations as data becomes available. For
each operation, update_engine needs to look at the merge sequence and
figure out which blocks should be converted to COW_XOR. To do that, we
need a data structure for querying a disjoint set of extents.
Test: th
Bug: 177104308
Change-Id: I14ec9d72a32e859b65516b894ca94d0153aa7e17
diff --git a/payload_generator/extent_ranges.cc b/payload_generator/extent_ranges.cc
index 2098639..4cc2d6f 100644
--- a/payload_generator/extent_ranges.cc
+++ b/payload_generator/extent_ranges.cc
@@ -45,7 +45,7 @@
bool ExtentRanges::ExtentsOverlap(const Extent& a, const Extent& b) {
if (a.start_block() == b.start_block())
- return true;
+ return a.num_blocks() != 0;
if (a.start_block() == kSparseHole || b.start_block() == kSparseHole)
return false;
if (a.start_block() < b.start_block()) {
@@ -281,6 +281,31 @@
return out;
}
+Range<ExtentRanges::ExtentSet::const_iterator> ExtentRanges::GetCandidateRange(
+ const Extent& extent) const {
+ auto lower_it = extent_set_.lower_bound(extent);
+ if (lower_it != extent_set_.begin()) {
+ --lower_it;
+ }
+
+ const auto upper_it = extent_set_.upper_bound(
+ ExtentForRange(extent.start_block() + extent.num_blocks(), 1));
+ return {lower_it, upper_it};
+}
+
+std::vector<Extent> ExtentRanges::GetIntersectingExtents(
+ const Extent& extent) const {
+ const auto candidates = GetCandidateRange(extent);
+ std::vector<Extent> result;
+ for (const auto& ext : candidates) {
+ if (auto intersection = GetOverlapExtent(ext, extent);
+ intersection.num_blocks() != 0) {
+ result.emplace_back(std::move(intersection));
+ }
+ }
+ return result;
+}
+
vector<Extent> FilterExtentRanges(const vector<Extent>& extents,
const ExtentRanges& ranges) {
vector<Extent> result;
@@ -331,4 +356,15 @@
return result;
}
+Extent GetOverlapExtent(const Extent& extent1, const Extent& extent2) {
+ if (!ExtentRanges::ExtentsOverlap(extent1, extent2)) {
+ return {};
+ }
+ const auto start_block =
+ std::max(extent1.start_block(), extent2.start_block());
+ const auto end_block = std::min(extent1.start_block() + extent1.num_blocks(),
+ extent2.start_block() + extent2.num_blocks());
+ return ExtentForRange(start_block, end_block - start_block);
+}
+
} // namespace chromeos_update_engine
diff --git a/payload_generator/extent_ranges.h b/payload_generator/extent_ranges.h
index 68aa27f..4894831 100644
--- a/payload_generator/extent_ranges.h
+++ b/payload_generator/extent_ranges.h
@@ -23,6 +23,7 @@
#include <base/macros.h>
+#include "update_engine/common/utils.h"
#include "update_engine/update_metadata.pb.h"
// An ExtentRanges object represents an unordered collection of extents (and
@@ -84,6 +85,18 @@
// the number of blocks in this extent set.
std::vector<Extent> GetExtentsForBlockCount(uint64_t count) const;
+ // Compute the intersection between this ExtentRange and the |extent|
+ // parameter. Return results in a vector. If there's no intersection, an empty
+ // vector is returned.
+ std::vector<Extent> GetIntersectingExtents(const Extent& extent) const;
+
+ // Get a range of extents that possibly intersect with |extent|. (Returned
+ // extents do not necessarily intersect!). It is perfectly acceptable to just
+ // return all extents in this set, though more efficient solution using binary
+ // search is preferred.
+ Range<ExtentSet::const_iterator> GetCandidateRange(
+ const Extent& extent) const;
+
private:
ExtentSet extent_set_;
uint64_t blocks_;
@@ -95,6 +108,8 @@
std::vector<Extent> FilterExtentRanges(const std::vector<Extent>& extents,
const ExtentRanges& ranges);
+Extent GetOverlapExtent(const Extent& extent1, const Extent& extent2);
+
} // namespace chromeos_update_engine
#endif // UPDATE_ENGINE_PAYLOAD_GENERATOR_EXTENT_RANGES_H_
diff --git a/payload_generator/extent_ranges_unittest.cc b/payload_generator/extent_ranges_unittest.cc
index f55bb73..314ec54 100644
--- a/payload_generator/extent_ranges_unittest.cc
+++ b/payload_generator/extent_ranges_unittest.cc
@@ -315,4 +315,20 @@
ranges));
}
+TEST(ExtentRangesTest, GetOverlapExtent) {
+ const auto ret1 =
+ GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(10, 10));
+ ASSERT_EQ(ret1.num_blocks(), 0UL) << ret1;
+ const auto ret2 =
+ GetOverlapExtent(ExtentForRange(5, 5), ExtentForRange(9, 10));
+ ASSERT_EQ(ret2, ExtentForRange(9, 1));
+
+ const auto ret3 =
+ GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 10));
+ ASSERT_EQ(ret3, ExtentForRange(7, 5));
+ const auto ret4 =
+ GetOverlapExtent(ExtentForRange(7, 5), ExtentForRange(3, 3));
+ ASSERT_EQ(ret4.num_blocks(), 0UL);
+}
+
} // namespace chromeos_update_engine